SOMS: SurrOgate MultiStart algorithm for use with nonlinear programming for global optimization

SOMS is a general surrogate-based multistart algorithm, which is used in combination with any local optimizer to find global optima for computationally expensive functions with multiple local minima. SOMS differs from previous multistart methods in that a surrogate approximation is used by the multistart algorithm to help reduce the number of function evaluations necessary to identify the most promising points from which to start each nonlinear programming local search. SOMS’s numerical results are compared with four well-known methods, namely, Multi-Level Single Linkage (MLSL), MATLAB’s MultiStart, MATLAB’s GlobalSearch, and GLOBAL. In addition, we propose a class of wavy test functions that mimic the wavy nature of objective functions arising in many black-box simulations. Extensive comparisons of algorithms on the wavy testfunctions and on earlier standard global-optimization test functions are done for a total of 19 different test problems. The numerical results indicate that SOMS performs favorably in comparison to alternative methods and does especially well on wavy functions when the number of function evaluations allowed is limited.

Distributed collaborative processing in wireless sensor networks with application to target localization and beamforming

Abstract The proliferation of wireless sensor networks and the variety of envisioned applications associated with them has motivated the development of distributed algorithms for collaborative processing over networked systems. One of the applications that has attracted the attention of the researchers is that of target localization where the nodes of the network try to estimate the position of an unknown target that lies within its coverage area. Particularly challenging is the problem of estimating the target’s position when we use received signal strength indicator (RSSI) due to the nonlinear relationship between the measured signal and the true position of the target. Many of the existing approaches suffer either from high computational complexity (e.g., particle filters) or lack of accuracy. Further, many of the proposed solutions are centralized which make their application to a sensor network questionable. Depending on the application at hand and, from a practical perspective it could be convenient to find a balance between localization accuracy and complexity. Into this direction we approach the maximum likelihood location estimation problem by solving a suboptimal (and more tractable) problem. One of the main advantages of the proposed scheme is that it allows for a decentralized implementation using distributed processing tools (e.g., consensus and convex optimization) and therefore, it is very suitable to be implemented in real sensor networks. If further accuracy is needed an additional refinement step could be performed around the found solution. Under the assumption of independent noise among the nodes such local search can be done in a fully distributed way using a distributed version of the Gauss-Newton method based on consensus. Regardless of the underlying application or function of the sensor network it is al¬ways necessary to have a mechanism for data reporting. While some approaches use a special kind of nodes (called sink nodes) for data harvesting and forwarding to the outside world, there are however some scenarios where such an approach is impractical or even impossible to deploy. Further, such sink nodes become a bottleneck in terms of traffic flow and power consumption. To overcome these issues instead of using sink nodes for data reporting one could use collaborative beamforming techniques to forward directly the generated data to a base station or gateway to the outside world. In a dis-tributed environment like a sensor network nodes cooperate in order to form a virtual antenna array that can exploit the benefits of multi-antenna communications. In col-laborative beamforming nodes synchronize their phases in order to add constructively at the receiver. Some of the inconveniences associated with collaborative beamforming techniques is that there is no control over the radiation pattern since it is treated as a random quantity. This may cause interference to other coexisting systems and fast bat-tery depletion at the nodes. Since energy-efficiency is a major design issue we consider the development of a distributed collaborative beamforming scheme that maximizes the network lifetime while meeting some quality of service (QoS) requirement at the re¬ceiver side. Using local information about battery status and channel conditions we find distributed algorithms that converge to the optimal centralized beamformer. While in the first part we consider only battery depletion due to communications beamforming, we extend the model to account for more realistic scenarios by the introduction of an additional random energy consumption. It is shown how the new problem generalizes the original one and under which conditions it is easily solvable. By formulating the problem under the energy-efficiency perspective the network’s lifetime is significantly improved. Resumen La proliferación de las redes inalámbricas de sensores junto con la gran variedad de posi¬bles aplicaciones relacionadas, han motivado el desarrollo de herramientas y algoritmos necesarios para el procesado cooperativo en sistemas distribuidos. Una de las aplicaciones que suscitado mayor interés entre la comunidad científica es la de localization, donde el conjunto de nodos de la red intenta estimar la posición de un blanco localizado dentro de su área de cobertura. El problema de la localization es especialmente desafiante cuando se usan niveles de energía de la seal recibida (RSSI por sus siglas en inglés) como medida para la localization. El principal inconveniente reside en el hecho que el nivel de señal recibida no sigue una relación lineal con la posición del blanco. Muchas de las soluciones actuales al problema de localization usando RSSI se basan en complejos esquemas centralizados como filtros de partículas, mientas que en otras se basan en esquemas mucho más simples pero con menor precisión. Además, en muchos casos las estrategias son centralizadas lo que resulta poco prácticos para su implementación en redes de sensores. Desde un punto de vista práctico y de implementation, es conveniente, para ciertos escenarios y aplicaciones, el desarrollo de alternativas que ofrezcan un compromiso entre complejidad y precisión. En esta línea, en lugar de abordar directamente el problema de la estimación de la posición del blanco bajo el criterio de máxima verosimilitud, proponemos usar una formulación subóptima del problema más manejable analíticamente y que ofrece la ventaja de permitir en¬contrar la solución al problema de localization de una forma totalmente distribuida, convirtiéndola así en una solución atractiva dentro del contexto de redes inalámbricas de sensores. Para ello, se usan herramientas de procesado distribuido como los algorit¬mos de consenso y de optimización convexa en sistemas distribuidos. Para aplicaciones donde se requiera de un mayor grado de precisión se propone una estrategia que con¬siste en la optimización local de la función de verosimilitud entorno a la estimación inicialmente obtenida. Esta optimización se puede realizar de forma descentralizada usando una versión basada en consenso del método de Gauss-Newton siempre y cuando asumamos independencia de los ruidos de medida en los diferentes nodos. Independientemente de la aplicación subyacente de la red de sensores, es necesario tener un mecanismo que permita recopilar los datos provenientes de la red de sensores. Una forma de hacerlo es mediante el uso de uno o varios nodos especiales, llamados nodos “sumidero”, (sink en inglés) que actúen como centros recolectores de información y que estarán equipados con hardware adicional que les permita la interacción con el exterior de la red. La principal desventaja de esta estrategia es que dichos nodos se convierten en cuellos de botella en cuanto a tráfico y capacidad de cálculo. Como alter¬nativa se pueden usar técnicas cooperativas de conformación de haz (beamforming en inglés) de manera que el conjunto de la red puede verse como un único sistema virtual de múltiples antenas y, por tanto, que exploten los beneficios que ofrecen las comu¬nicaciones con múltiples antenas. Para ello, los distintos nodos de la red sincronizan sus transmisiones de manera que se produce una interferencia constructiva en el recep¬tor. No obstante, las actuales técnicas se basan en resultados promedios y asintóticos, cuando el número de nodos es muy grande. Para una configuración específica se pierde el control sobre el diagrama de radiación causando posibles interferencias sobre sis¬temas coexistentes o gastando más potencia de la requerida. La eficiencia energética es una cuestión capital en las redes inalámbricas de sensores ya que los nodos están equipados con baterías. Es por tanto muy importante preservar la batería evitando cambios innecesarios y el consecuente aumento de costes. Bajo estas consideraciones, se propone un esquema de conformación de haz que maximice el tiempo de vida útil de la red, entendiendo como tal el máximo tiempo que la red puede estar operativa garantizando unos requisitos de calidad de servicio (QoS por sus siglas en inglés) que permitan una decodificación fiable de la señal recibida en la estación base. Se proponen además algoritmos distribuidos que convergen a la solución centralizada. Inicialmente se considera que la única causa de consumo energético se debe a las comunicaciones con la estación base. Este modelo de consumo energético es modificado para tener en cuenta otras formas de consumo de energía derivadas de procesos inherentes al funcionamiento de la red como la adquisición y procesado de datos, las comunicaciones locales entre nodos, etc. Dicho consumo adicional de energía se modela como una variable aleatoria en cada nodo. Se cambia por tanto, a un escenario probabilístico que generaliza el caso determinista y se proporcionan condiciones bajo las cuales el problema se puede resolver de forma eficiente. Se demuestra que el tiempo de vida de la red mejora de forma significativa usando el criterio propuesto de eficiencia energética.

A practical approach for outdoors distributed target localization in wireless sensor networks

Wireless sensor networks are posed as the new communication paradigm where the use of small, low-complexity, and low-power devices is preferred over costly centralized systems. The spectra of potential applications of sensor networks is very wide, ranging from monitoring, surveillance, and localization, among others. Localization is a key application in sensor networks and the use of simple, efficient, and distributed algorithms is of paramount practical importance. Combining convex optimization tools with consensus algorithms we propose a distributed localization algorithm for scenarios where received signal strength indicator readings are used. We approach the localization problem by formulating an alternative problem that uses distance estimates locally computed at each node. The formulated problem is solved by a relaxed version using semidefinite relaxation technique. Conditions under which the relaxed problem yields to the same solution as the original problem are given and a distributed consensusbased implementation of the algorithm is proposed based on an augmented Lagrangian approach and primaldual decomposition methods. Although suboptimal, the proposed approach is very suitable for its implementation in real sensor networks, i.e., it is scalable, robust against node failures and requires only local communication among neighboring nodes. Simulation results show that running an additional local search around the found solution can yield performance close to the maximum likelihood estimate.

An evolutionary algorithm for the surface structure problem

Many macroscopic properties: hardness, corrosion, catalytic activity, etc. are directly related to the surface structure, that is, to the position and chemical identity of the outermost atoms of the material. Current experimental techniques for its determination produce a “signature” from which the structure must be inferred by solving an inverse problem: a solution is proposed, its corresponding signature computed and then compared to the experiment. This is a challenging optimization problem where the search space and the number of local minima grows exponentially with the number of atoms, hence its solution cannot be achieved for arbitrarily large structures. Nowadays, it is solved by using a mixture of human knowledge and local search techniques: an expert proposes a solution that is refined using a local minimizer. If the outcome does not fit the experiment, a new solution must be proposed again. Solving a small surface can take from days to weeks of this trial and error method. Here we describe our ongoing work in its solution. We use an hybrid algorithm that mixes evolutionary techniques with trusted region methods and reuses knowledge gained during the execution to avoid repeated search of structures. Its parallelization produces good results even when not requiring the gathering of the full population, hence it can be used in loosely coupled environments such as grids. With this algorithm, the solution of test cases that previously took weeks of expert time can be automatically solved in a day or two of uniprocessor time.

Avaliações e testes dos métodos MASW e ReMi por meio do tratamento de dados empíricos e sintéticos em um programa de processamento e inversão desenvolvido em MATLAB e sua implicação em um problema geológico na Bacia de Taubaté

Os métodos de ondas superficiais com ênfase nas ondas Rayleigh foram utilizados como o núcleo desse trabalho de Doutorado. Inicialmente, as ondas Rayleigh foram modeladas permitindo o estudo de sensibilidade de suas curvas de dispersão sob diferentes configurações de parâmetros físicos representando diversos modelos de camadas, em que pôde ser observado parâmetros com maior e menor sensibilidade e também alguns efeitos provocados por baixas razões de Poisson. Além disso, na fase de inversão dos dados a modelagem das ondas Rayleigh foi utilizada para a construção da função objeto, que agregada ao método de mínimos quadrados, a partir do método de Levenberg-Marquardt, permitiu a implementação de um algoritmo de busca local responsável pela inversão de dados das ondas superficiais. Por se tratar de um procedimento de busca local, o algoritmo de inversão foi complementado por uma etapa de pré-inversão com a geração de um modelo inicial para que o procedimento de inversão fosse mais rápido e eficiente. Visando uma eficiência ainda maior do procedimento de inversão, principalmente em modelos de camadas com inversão de velocidades, foi implementado um algoritmo de pós-inversão baseado em um procedimento de tentativa e erro minimizando os valores relativos da raiz quadrada do erro quadrático médio (REQMr) da inversão dos dados. Mais de 50 modelos de camadas foram utilizados para testar a modelagem, a pré-inversão, inversão e pós-inversão dos dados permitindo o ajuste preciso de parâmetros matemáticos e físicos presentes nos diversos scripts implementados em Matlab. Antes de inverter os dados adquiridos em campo, os mesmos precisaram ser tratados na etapa de processamento de dados, cujo objetivo principal é a extração da curva de dispersão originada devido às ondas superficiais. Para isso, foram implementadas, também em Matlab, três metodologias de processamento com abordagens matemáticas distintas. Essas metodologias foram testadas e avaliadas com dados sintéticos e reais em que foi possível constatar as virtudes e deficiências de cada metodologia estudada, bem como as limitações provocadas pela discretização dos dados de campo. Por último, as etapas de processamento, pré-inversão, inversão e pós-inversão dos dados foram unificadas para formar um programa de tratamento de dados de ondas superficiais (Rayleigh). Ele foi utilizado em dados reais originados pelo estudo de um problema geológico na Bacia de Taubaté em que foi possível mapear os contatos geológicos ao longo dos pontos de aquisição sísmica e compará-los a um modelo inicial existente baseado em observações geomorfológicas da área de estudos, mapa geológico da região e informações geológicas globais e locais dos movimentos tectônicos na região. As informações geofísicas associadas às geológicas permitiram a geração de um perfil analítico da região de estudos com duas interpretações geológicas confirmando a suspeita de neotectônica na região em que os contatos geológicos entre os depósitos Terciários e Quaternários foram identificados e se encaixaram no modelo inicial de hemi-graben com mergulho para Sudeste.

Amélioration a posteriori de la traduction automatique par métaheuristique

La traduction automatique statistique est un domaine très en demande et où les machines sont encore loin de produire des résultats de qualité humaine. La principale méthode utilisée est une traduction linéaire segment par segment d'une phrase, ce qui empêche de changer des parties de la phrase déjà traduites. La recherche pour ce mémoire se base sur l'approche utilisée dans Langlais, Patry et Gotti 2007, qui tente de corriger une traduction complétée en modifiant des segments suivant une fonction à optimiser. Dans un premier temps, l'exploration de nouveaux traits comme un modèle de langue inverse et un modèle de collocation amène une nouvelle dimension à la fonction à optimiser. Dans un second temps, l'utilisation de différentes métaheuristiques, comme les algorithmes gloutons et gloutons randomisés permet l'exploration plus en profondeur de l'espace de recherche et permet une plus grande amélioration de la fonction objectif.

Amélioration a posteriori de la traduction automatique par métaheuristique

La traduction automatique statistique est un domaine très en demande et où les machines sont encore loin de produire des résultats de qualité humaine. La principale méthode utilisée est une traduction linéaire segment par segment d'une phrase, ce qui empêche de changer des parties de la phrase déjà traduites. La recherche pour ce mémoire se base sur l'approche utilisée dans Langlais, Patry et Gotti 2007, qui tente de corriger une traduction complétée en modifiant des segments suivant une fonction à optimiser. Dans un premier temps, l'exploration de nouveaux traits comme un modèle de langue inverse et un modèle de collocation amène une nouvelle dimension à la fonction à optimiser. Dans un second temps, l'utilisation de différentes métaheuristiques, comme les algorithmes gloutons et gloutons randomisés permet l'exploration plus en profondeur de l'espace de recherche et permet une plus grande amélioration de la fonction objectif.

Physiological and pathological human ocular perfusion characteristics

There were three principle aims to this thesis. Firstly, the acquisition protocols of clinical blood flow apparatus were investigated in order to optimise them for both cross-sectional and longitudinal application. Secondly, the effects of physiological factors including age and systematic circulation on ocular blood flow were investigated. Finally, the ocular perfusion characteristics of patients diagnosed with ocular diseases considered to be of a vascular origin were investigated. The principle findings of this work are:- 1) Optimisation of clinical investigationsPhotodiode sensitivity of the scanning laser Doppler flowmeter should be kept within a range of 70-150 DC when acquiring images of the retina and optic nerve head in order to optimise the reproducibility of capillary blood flow measures. Account of the physiological spatial variation in retinal blood flow measures can be made using standard analysis protocols of the scanning laser Doppler flowmeter combined with a local search strategy. Measurements of pulsatile ocular blood flow using the ocular blood flow analyser are reproducible, however this reproducibility can be improved when consecutive intraocular pressure pulses are used to calculate pulsatile ocular blood flow. Spectral analysis of the intraocular pressure pulse-wave is viable and identifies the first four harmonic components of the waveform. 2) Physiological variation in ocular perfusionAge results in a significant reduction in perfusion of the retinal microcirculation, which is not evident in larger vessel beds such as the choroid. Despite known asymmetry in the systemic vasculature, no evidence of interocular asymmetry in ocular perfusion is apparent. 3) Pathological variation in ocular perfusionIn primary open angle glaucoma, perfusion is reduced in the retinal microcirculation of patients classified as having early to moderate visual field defects. However, ocular pulsatility defects are masked when patients and subjects are matched for systemic variables (pulse rate and mean arterial pressure); differentiation is facilitated by the application of waveform analysis to the continuos intraocular pressure curve even in the early stages of disease. Diabetic patients with adequate glycaemic control, exhibit maintenance of macular blood flow, macular topography and visual function following phacoemulsification.

Optimization of ATM Telecommunication Networks

ATM network optimization problems defined as combinatorial optimization problems are considered. Several approximate algorithms for solving such problems are developed. Results of their comparison by experiments on a set of problems with random input data are presented.

Использование Алгоритма Ускоренного Вероятностного Моделирования в Схеме Табу-Поиска

Рассматривается метаэвристический метод комбинаторной оптимизации, основанный на использовании алгоритмов табу-поиска и ускоренного вероятностного моделирования. Излагается общая вычислительная схема предложенного метода, названного алгоритмом GS-tabu. Приведены результаты серии вычислительных экспериментов по решению известных задач коммивояжера и квадратичных задач о назначении.

An Electromagnetism Metaheuristic for the Uncapacitated Multiple Allocation Hub Location Problem

In this article, the results achieved by applying an electromagnetism (EM) inspired metaheuristic to the uncapacitated multiple allocation hub location problem (UMAHLP) are discussed. An appropriate objective function which natively conform with the problem, 1-swap local search and scaling technique conduce to good overall performance.Computational tests demonstrate the reliability of this method, since the EM-inspired metaheuristic reaches all optimal/best known solutions for UMAHLP, except one, in a reasonable time.

Optimal image colour extraction by differential evolution

Differential evolution is an optimisation technique that has been successfully employed in various applications. In this paper, we apply differential evolution to the problem of extracting the optimal colours of a colour map for quantised images. The choice of entries in the colour map is crucial for the resulting image quality as it forms a look-up table that is used for all pixels in the image. We show that differential evolution can be effectively employed as a method for deriving the entries in the map. In order to optimise the image quality, our differential evolution approach is combined with a local search method that is guaranteed to find the local optimal colour map. This hybrid approach is shown to outperform various commonly used colour quantisation algorithms on a set of standard images. Copyright © 2010 Inderscience Enterprises Ltd.

Web Based Bicycle Trip Planning for Broward County, Florida

To promote the use of bicycle transportation mode in times of increasing urban traffic congestion, Broward County Metropolitan Planning Organization funded the development of a Web-based trip planner for cyclists. This presentation demonstrates the integration of the ArcGIS Server 9.3 environment with the ArcGIS JavaScript Extension for Google Maps API and the Google Local Search Control for Maps API. This allows the use of Google mashup GIS functionality, i.e., Google local search for selection of trip start, trip destination, and intermediate waypoints, and the integration of Google Maps base layers. The ArcGIS Network Analyst extension is used for the route search, where algorithms for fastest, safest, simplest, most scenic, and shortest routes are imbedded. This presentation also describes how attributes of the underlying network sources have been combined to facilitate the search for optimized routes.

Web Based Bicycle Trip Planning for Broward County, Florida

To promote the use of bicycle transportation mode in times of increasing urban traffic congestion, Broward County Metropolitan Planning Organization funded the development of a Web-based trip planner for cyclists. This presentation demonstrates the integration of the ArcGIS Server 9.3 environment with the ArcGIS JavaScript Extension for Google Maps API and the Google Local Search Control for Maps API. This allows the use of Google mashup GIS functionality, i.e., Google local search for selection of trip start, trip destination, and intermediate waypoints, and the integration of Google Maps base layers. The ArcGIS Network Analyst extension is used for the route search, where algorithms for fastest, safest, simplest, most scenic, and shortest routes are imbedded. This presentation also describes how attributes of the underlying network sources have been combined to facilitate the search for optimized routes.

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.