GLODS: Global and Local Optimization using Direct Search

Locating and identifying points as global minimizers is, in general, a hard and time-consuming task. Difficulties increase in the impossibility of using the derivatives of the functions defining the problem. In this work, we propose a new class of methods suited for global derivative-free constrained optimization. Using direct search of directional type, the algorithm alternates between a search step, where potentially good regions are located, and a poll step where the previously located promising regions are explored. This exploitation is made through the launching of several instances of directional direct searches, one in each of the regions of interest. Differently from a simple multistart strategy, direct searches will merge when sufficiently close. The goal is to end with as many direct searches as the number of local minimizers, which would easily allow locating the global extreme value. We describe the algorithmic structure considered, present the corresponding convergence analysis and report numerical results, showing that the proposed method is competitive with currently commonly used global derivative-free optimization solvers.

Global vs. local nonlinear optimization techniques for human-like movement of an anthropomorphic robot

In this paper a comparison between using global and local optimization techniques for solving the problem of generating human-like arm and hand movements for an anthropomorphic dual arm robot is made. Although the objective function involved in each optimization problem is convex, there is no evidence that the admissible regions of these problems are convex sets. For the sequence of movements for which the numerical tests were done there were no significant differences between the optimal solutions obtained using the global and the local techniques. This suggests that the optimal solution obtained using the local solver is indeed a global solution.

ContinuousMultimodal Global Optimization with Differential Evolution-Based Methods

Metaheuristic methods have become increasingly popular approaches in solving global optimization problems. From a practical viewpoint, it is often desirable to perform multimodal optimization which, enables the search of more than one optimal solution to the task at hand. Population-based metaheuristic methods offer a natural basis for multimodal optimization. The topic has received increasing interest especially in the evolutionary computation community. Several niching approaches have been suggested to allow multimodal optimization using evolutionary algorithms. Most global optimization approaches, including metaheuristics, contain global and local search phases. The requirement to locate several optima sets additional requirements for the design of algorithms to be effective in both respects in the context of multimodal optimization. In this thesis, several different multimodal optimization algorithms are studied in regard to how their implementation in the global and local search phases affect their performance in different problems. The study concentrates especially on variations of the Differential Evolution algorithm and their capabilities in multimodal optimization. To separate the global and local search search phases, three multimodal optimization algorithms are proposed, two of which hybridize the Differential Evolution with a local search method. As the theoretical background behind the operation of metaheuristics is not generally thoroughly understood, the research relies heavily on experimental studies in finding out the properties of different approaches. To achieve reliable experimental information, the experimental environment must be carefully chosen to contain appropriate and adequately varying problems. The available selection of multimodal test problems is, however, rather limited, and no general framework exists. As a part of this thesis, such a framework for generating tunable test functions for evaluating different methods of multimodal optimization experimentally is provided and used for testing the algorithms. The results demonstrate that an efficient local phase is essential for creating efficient multimodal optimization algorithms. Adding a suitable global phase has the potential to boost the performance significantly, but the weak local phase may invalidate the advantages gained from the global phase.

Search space pruning and global optimization of multiple gravity assist trajectories with deep space manoeuvres

This paper deals with the design of optimal multiple gravity assist trajectories with deep space manoeuvres. A pruning method which considers the sequential nature of the problem is presented. The method locates feasible vectors using local optimization and applies a clustering algorithm to find reduced bounding boxes which can be used in a subsequent optimization step. Since multiple local minima remain within the pruned search space, the use of a global optimization method, such as Differential Evolution, is suggested for finding solutions which are likely to be close to the global optimum. Two case studies are presented.

Empilhamento sísmico por superfície de reflexão comum: um novo algoritmo usando otimização global e local

O método de empilhamento sísmico por Superfície de Reflexão Comum (ou empilhamento SRC) produz a simulação de seções com afastamento nulo (NA) a partir dos dados de cobertura múltipla. Para meios 2D, o operador de empilhamento SRC depende de três parâmetros que são: o ângulo de emergência do raio central com fonte-receptor nulo (β₀), o raio de curvatura da onda ponto de incidência normal (R_NIP) e o raio de curvatura da onda normal (R_N). O problema crucial para a implementação do método de empilhamento SRC consiste na determinação, a partir dos dados sísmicos, dos três parâmetros ótimos associados a cada ponto de amostragem da seção AN a ser simulada. No presente trabalho foi desenvolvido uma nova sequência de processamento para a simulação de seções AN por meio do método de empilhamento SRC. Neste novo algoritmo, a determinação dos três parâmetros ótimos que definem o operador de empilhamento SRC é realizada em três etapas: na primeira etapa são estimados dois parâmetros (β°₀ e R°_NIP) por meio de uma busca global bidimensional nos dados de cobertura múltipla. Na segunda etapa é usado o valor de β°₀ estimado para determinar-se o terceiro parâmetro (R°_N) através de uma busca global unidimensional na seção AN resultante da primeira etapa. Em ambas etapas as buscas globais são realizadas aplicando o método de otimização Simulated Annealing (SA). Na terceira etapa são determinados os três parâmetros finais (β₀, R_NIP e R_N) através uma busca local tridimensional aplicando o método de otimização Variable Metric (VM) nos dados de cobertura múltipla. Nesta última etapa é usado o trio de parâmetros (β°₀, R°_NIP, R°_N) estimado nas duas etapas anteriores como aproximação inicial. Com o propósito de simular corretamente os eventos com mergulhos conflitantes, este novo algoritmo prevê a determinação de dois trios de parâmetros associados a pontos de amostragem da seção AN onde há intersecção de eventos. Em outras palavras, nos pontos da seção AN onde dois eventos sísmicos se cruzam são determinados dois trios de parâmetros SRC, os quais serão usados conjuntamente na simulação dos eventos com mergulhos conflitantes. Para avaliar a precisão e eficiência do novo algoritmo, este foi aplicado em dados sintéticos de dois modelos: um com interfaces contínuas e outro com uma interface descontinua. As seções AN simuladas têm elevada razão sinal-ruído e mostram uma clara definição dos eventos refletidos e difratados. A comparação das seções AN simuladas com as suas similares obtidas por modelamento direto mostra uma correta simulação de reflexões e difrações. Além disso, a comparação dos valores dos três parâmetros otimizados com os seus correspondentes valores exatos calculados por modelamento direto revela também um alto grau de precisão. Usando a aproximação hiperbólica dos tempos de trânsito, porém sob a condição de R_NIP = R_N, foi desenvolvido um novo algoritmo para a simulação de seções AN contendo predominantemente campos de ondas difratados. De forma similar ao algoritmo de empilhamento SRC, este algoritmo denominado empilhamento por Superfícies de Difração Comum (SDC) também usa os métodos de otimização SA e VM para determinar a dupla de parâmetros ótimos (β₀, R_NIP) que definem o melhor operador de empilhamento SDC. Na primeira etapa utiliza-se o método de otimização SA para determinar os parâmetros iniciais β°₀ e R°_NIP usando o operador de empilhamento com grande abertura. Na segunda etapa, usando os valores estimados de β°₀ e R°_NIP, são melhorados as estimativas do parâmetro R_NIP por meio da aplicação do algoritmo VM na seção AN resultante da primeira etapa. Na terceira etapa são determinados os melhores valores de β°₀ e R°_NIP por meio da aplicação do algoritmo VM nos dados de cobertura múltipla. Vale salientar que a aparente repetição de processos tem como efeito a atenuação progressiva dos eventos refletidos. A aplicação do algoritmo de empilhamento SDC em dados sintéticos contendo campos de ondas refletidos e difratados, produz como resultado principal uma seção AN simulada contendo eventos difratados claramente definidos. Como uma aplicação direta deste resultado na interpretação de dados sísmicos, a migração pós-empilhamento em profundidade da seção AN simulada produz uma seção com a localização correta dos pontos difratores associados às descontinuidades do modelo.

An optimization method for conceptual design in engineering systems based on high order singular value decomposition

Se presenta un nuevo método de diseño conceptual en Ingeniería Aeronáutica basado el uso de modelos reducidos, también llamados modelos sustitutos (‘surrogates’). Los ingredientes de la función objetivo se calculan para cada indiviudo mediante la utilización de modelos sustitutos asociados a las distintas disciplinas técnicas que se construyen mediante definiciones de descomposición en valores singulares de alto orden (HOSVD) e interpolaciones unidimensionales. Estos modelos sustitutos se obtienen a partir de un número limitado de cálculos CFD. Los modelos sustitutos pueden combinarse, bien con un método de optimización global de tipo algoritmo genético, o con un método local de tipo gradiente. El método resultate es flexible a la par que mucho más eficiente, computacionalmente hablando, que los modelos convencionales basados en el cálculo directo de la función objetivo, especialmente si aparecen un gran número de parámetros de diseño y/o de modelado. El método se ilustra considerando una versión simplificada del diseño conceptual de un avión. Abstract An optimization method for conceptual design in Aeronautics is presented that is based on the use of surrogate models. The various ingredients in the target function are calculated for each individual using surrogates of the associated technical disciplines that are constructed via high order singular value decomposition and one dimensional interpolation. These surrogates result from a limited number of CFD calculated snapshots. The surrogates are combined with an optimization method, which can be either a global optimization method such as a genetic algorithm or a local optimization method, such as a gradient-like method. The resulting method is both flexible and much more computationally efficient than the conventional method based on direct calculation of the target function, especially if a large number of free design parameters and/or tunablemodeling parameters are present. The method is illustrated considering a simplified version of the conceptual design of an aircraft empennage.

Development of Shape-Optimization Tools for the Aerodynamic Design of Turbomachinery Blades

The aim of this work is to develop an automated tool for the optimization of turbomachinery blades founded on an evolutionary strategy. This optimization scheme will serve to deal with supersonic blades cascades for application to Organic Rankine Cycle (ORC) turbines. The blade geometry is defined using parameterization techniques based on B-Splines curves, that allow to have a local control of the shape. The location in space of the control points of the B-Spline curve define the design variables of the optimization problem. In the present work, the performance of the blade shape is assessed by means of fully-turbulent flow simulations performed with a CFD package, in which a look-up table method is applied to ensure an accurate thermodynamic treatment. The solver is set along with the optimization tool to determine the optimal shape of the blade. As only blade-to-blade effects are of interest in this study, quasi-3D calculations are performed, and a single-objective evolutionary strategy is applied to the optimization. As a result, a non-intrusive tool, with no need for gradients definition, is developed. The computational cost is reduced by the use of surrogate models. A Gaussian interpolation scheme (Kriging model) is applied for the estimated n-dimensional function, and a surrogate-based local optimization strategy is proved to yield an accurate way for optimization. In particular, the present optimization scheme has been applied to the re-design of a supersonic stator cascade of an axial-flow turbine. In this design exercise very strong shock waves are generated in the rear blade suction side and shock-boundary layer interaction mechanisms occur. A significant efficiency improvement as a consequence of a more uniform flow at the blade outlet section of the stator is achieved. This is also expected to provide beneficial effects on the design of a subsequent downstream rotor. The method provides an improvement to gradient-based methods and an optimized blade geometry is easily achieved using the genetic algorithm.

A methodological approach for the performance optimization of transient seepage models through inverse analysis

The topic of the Ph.D project focuses on the modelling of the soil-water dynamics inside an instrumented embankment section along Secchia River (Cavezzo (MO)) in the period from 2017 to 2018 and the quantification of the performance of the direct and indirect simulations . The commercial code Hydrus2D by Pc-Progress has been chosen to run the direct simulations. Different soil-hydraulic models have been adopted and compared. The parameters of the different hydraulic models are calibrated using a local optimization method based on the Levenberg - Marquardt algorithm implemented in the Hydrus package. The calibration program is carried out using different types of dataset of observation points, different weighting distributions, different combinations of optimized parameters and different initial sets of parameters. The final goal is an in-depth study of the potentialities and limits of the inverse analysis when applied to a complex geotechnical problem as the case study. The second part of the research focuses on the effects of plant roots and soil-vegetation-atmosphere interaction on the spatial and temporal distribution of pore water pressure in soil. The investigated soil belongs to the West Charlestown Bypass embankment, Newcastle, Australia, that showed in the past years shallow instabilities and the use of long stem planting is intended to stabilize the slope. The chosen plant species is the Malaleuca Styphelioides, native of eastern Australia. The research activity included the design and realization of a specific large scale apparatus for laboratory experiments. Local suction measurements at certain intervals of depth and radial distances from the root bulb are recorded within the vegetated soil mass under controlled boundary conditions. The experiments are then reproduced numerically using the commercial code Hydrus 2D. Laboratory data are used to calibrate the RWU parameters and the parameters of the hydraulic model.

Uma avaliação das metodologias de desagregação da exergia física para a modelagem termoeconômica de sistemas

Talvez não seja nenhum exagero afirmar que há quase um consenso entre os praticantes da Termoeconomia de que a exergia, ao invés de só entalpia, seja a magnitude Termodinâmica mais adequada para ser combinada com o conceito de custo na modelagem termoeconômica, pois esta leva em conta aspectos da Segunda Lei da Termodinâmica e permite identificar as irreversibilidades. Porém, muitas vezes durante a modelagem termoeconômica se usa a exergia desagregada em suas parcelas (química, térmica e mecânica), ou ainda, se inclui a neguentropia que é um fluxo fictício, permitindo assim a desagregação do sistema em seus componentes (ou subsistemas) visando melhorar e detalhar a modelagem para a otimização local, diagnóstico e alocação dos resíduos e equipamentos dissipativos. Alguns autores também afirmam que a desagregação da exergia física em suas parcelas (térmica e mecânica) permite aumentar a precisão dos resultados na alocação de custos, apesar de fazer aumentar a complexidade do modelo termoeconômico e consequentemente os custos computacionais envolvidos. Recentemente alguns autores apontaram restrições e possíveis inconsistências do uso da neguentropia e deste tipo de desagregação da exergia física, propondo assim alternativas para o tratamento de resíduos e equipamentos dissipativos que permitem a desagregação dos sistemas em seus componentes. Estas alternativas consistem, basicamente, de novas propostas de desagregação da exergia física na modelagem termoeconômica. Sendo assim, este trabalho tem como objetivo avaliar as diferentes metodologias de desagregação da exergia física para a modelagem termoeconômica, tendo em conta alguns aspectos como vantagens, restrições, inconsistências, melhoria na precisão dos resultados, aumento da complexidade e do esforço computacional e o tratamento dos resíduos e equipamentos dissipativos para a total desagregação do sistema térmico. Para isso, as diferentes metodologias e níveis de desagregação da exergia física são aplicados na alocação de custos para os produtos finais (potência líquida e calor útil) em diferentes plantas de cogeração considerando como fluido de trabalho tanto o gás ideal bem como o fluido real. Plantas essas com equipamentos dissipativos (condensador ou válvula) ou resíduos (gases de exaustão da caldeira de recuperação). Porém, foi necessário que uma das plantas de cogeração não incorporasse equipamentos dissipativos e nem caldeira de recuperação com o intuito de avaliar isoladamente o efeito da desagregação da exergia física na melhoria da precisão dos resultados da alocação de custos para os produtos finais.

Deciphering the global organization of clustering in real complex networks

We uncover the global organization of clustering in real complex networks. To this end, we ask whether triangles in real networks organize as in maximally random graphs with given degree and clustering distributions, or as in maximally ordered graph models where triangles are forced into modules. The answer comes by way of exploring m-core landscapes, where the m-core is defined, akin to the k-core, as the maximal subgraph with edges participating in at least m triangles. This property defines a set of nested subgraphs that, contrarily to k-cores, is able to distinguish between hierarchical and modular architectures. We find that the clustering organization in real networks is neither completely random nor ordered although, surprisingly, it is more random than modular. This supports the idea that the structure of real networks may in fact be the outcome of self-organized processes based on local optimization rules, in contrast to global optimization principles.

Procedimientos de exploración de entornos para la programación de operaciones en una máquina con tiempos de preparación

objetivo de minimizar el retraso total en un ambiente con preparaciones quedependen de la secuencia. Se comparan los resultados obtenidos mediante laaplicación de los procedimientos de exploración de entornos AED, ANED,Recocido Simulado, Algoritmos Genéticos, Búsqueda Tabú y GRASP alproblema planteado. Los resultados sugieren que la Búsqueda Tabú es unatécnica viable de solución que puede proporcionar buenas soluciones cuandose considera el objetivo retraso total con tiempos de preparación dependientesde la secuencia.

Multi-vehicle planning using RRT-connect

The problem of planning multiple vehicles deals with the design of an effective algorithm that can cause multiple autonomous vehicles on the road to communicate and generate a collaborative optimal travel plan. Our modelling of the problem considers vehicles to vary greatly in terms of both size and speed, which makes it suboptimal to have a faster vehicle follow a slower vehicle or for vehicles to drive with predefined speed lanes. It is essential to have a fast planning algorithm whilst still being probabilistically complete. The Rapidly Exploring Random Trees (RRT) algorithm developed and reported on here uses a problem specific coordination axis, a local optimization algorithm, priority based coordination, and a module for deciding travel speeds. Vehicles are assumed to remain in their current relative position laterally on the road unless otherwise instructed. Experimental results presented here show regular driving behaviours, namely vehicle following, overtaking, and complex obstacle avoidance. The ability to showcase complex behaviours in the absence of speed lanes is characteristic of the solution developed.

Stochastic Assessment Of Environmental Flows In Semiarid Environments

The regimen of environmental flows (EF) must be included as terms of environmental demand in the management of water resources. Even though there are numerous methods for the computation of EF, the criteria applied at different steps in the calculation process are quite subjective whereas the results are fixed values that must be meet by water planners. This study presents a friendly-user tool for the assessment of the probability of compliance of a certain EF scenario with the natural regimen in a semiarid area in southern Spain. 250 replications of a 25-yr period of different hydrological variables (rainfall, minimum and maximum flows, ...) were obtained at the study site from the combination of Monte Carlo technique and local hydrological relationships. Several assumptions are made such as the independence of annual rainfall from year to year and the variability of occurrence of the meteorological agents, mainly precipitation as the main source of uncertainty. Inputs to the tool are easily selected from a first menu and comprise measured rainfall data, EF values and the hydrological relationships for at least a 20-yr period. The outputs are the probabilities of compliance of the different components of the EF for the study period. From this, local optimization can be applied to establish EF components with a certain level of compliance in the study period. Different options for graphic output and analysis of results are included in terms of graphs and tables in several formats. This methodology turned out to be a useful tool for the implementation of an uncertainty analysis within the scope of environmental flows in water management and allowed the simulation of the impacts of several water resource development scenarios in the study site.

Stochastic scheduling - A flow shop no wait application and solutions

Minimizing the makespan of a flow-shop no-wait (FSNW) schedule where the processing times are randomly distributed is an important NP-Complete Combinatorial Optimization Problem. In spite of this, it can be found only in very few papers in the literature. By considering the Start Interval Concept, this problem can be formulated, in a practical way, in function of the probability of the success in preserve FSNW constraints for all tasks execution. With this formulation, for the particular case with 3 machines, this paper presents different heuristics solutions: by integrating local optimization steps with insertion procedures and by using genetic algorithms for search the solution space. Computational results and performance evaluations are commented. Copyright (C) 1998 IFAC.

Empilhamento pelo método superfície de reflexão comum 2-D com topografia e introdução ao caso 3-D

O método de empilhamento sísmico CRS simula seções sísmicas ZO a partir de dados de cobertura múltipla, independente do macro-modelo de velocidades. Para meios 2-D, a função tempo de trânsito de empilhamento depende de três parâmetros, a saber: do ângulo de emergência do raio de reflexão normal (em relação à normal da superfície) e das curvaturas das frentes de onda relacionadas às ondas hipotéticas, denominadas NIP e Normal. O empilhamento CRS consiste na soma das amplitudes dos traços sísmicos em dados de múltipla cobertura, ao longo da superfície definida pela função tempo de trânsito do empilhamento CRS, que melhor se ajusta aos dados. O resultado do empilhamento CRS é assinalado a pontos de uma malha pré-definida na seção ZO. Como resultado tem-se a simulação de uma seção sísmica ZO. Isto significa que para cada ponto da seção ZO deve-se estimar o trio de parâmetros ótimos que produz a máxima coerência entre os eventos de reflexão sísmica. Nesta Tese apresenta-se fórmulas para o método CRS 2-D e para a velocidade NMO, que consideram a topografia da superfície de medição. O algoritmo é baseado na estratégia de otimização dos parâmetros de fórmula CRS através de um processo em três etapas: 1) Busca dos parâmetros, o ângulo de emergência e a curvatura da onda NIP, aplicando uma otimização global, 2) busca de um parâmetro, a curvatura da onda N, aplicando uma otimização global, e 3) busca de três parâmetros aplicando uma otimização local para refinar os parâmetros estimados nas etapas anteriores. Na primeira e segunda etapas é usado o algoritmo Simulated Annealing (SA) e na terceira etapa é usado o algoritmo Variable Metric (VM). Para o caso de uma superfície de medição com variações topográficas suaves, foi considerada a curvatura desta superfície no algoritmo do método de empilhamento CRS 2-D, com aplicação a dados sintéticos. O resultado foi uma seção ZO simulada, de alta qualidade ao ser comparada com a seção ZO obtida por modelamento direto, com uma alta razão sinal-ruído, além da estimativa do trio de parâmetros da função tempo de trânsito. Foi realizada uma nálise de sensibilidade para a nova função de tempo de trânsito CRS em relação à curvatura da superfície de medição. Os resultados demonstraram que a função tempo de trânsito CRS é mais sensível nos pontos-médios afastados do ponto central e para grandes afastamentos. As expressões da velocidade NMO apresentadas foram aplicadas para estimar as velocidades e as profundidades dos refletores para um modelo 2-D com topografia suave. Para a inversão destas velocidades e profundidades dos refletores, foi considerado o algoritmo de inversão tipo Dix. A velocidade NMO para uma superfície de medição curva, permite estimar muito melhor estas velocidades e profundidades dos refletores, que as velocidades NMO referidas as superfícies planas. Também apresenta-se uma abordagem do empilhamento CRS no caso 3-D. neste caso a função tempo de trânsito depende de oito parâmetros. São abordadas cinco estratégias de busca destes parâmetros. A combinação de duas destas estratégias (estratégias das três aproximações dos tempos de trânsito e a estratégia das configurações e curvaturas arbitrárias) foi aplicada exitosamente no empilhamento CRS 3-D de dados sintéticos e reais.