No description available.

This doctoral thesis will present the results of work into optimisation algorithms. We first give a detailed exploration of the problems involved in comparing optimisation algorithms. In particular we provide extensions and refinements to no free lunch results, exploring algorithms with arbitrary stopping conditions, optimisation under restricted metrics, parallel computing and free lunches, and head-to-head minimax behaviour. We also characterise no free lunch results in terms of order statistics. We then ask what really constitutes understanding of an optimisation algorithm. We argue that one central part of understanding an optimiser is knowing its Bayesian prior and cost function. We then pursue a general Bayesian framing of optimisation, and prove that this Bayesian perspective is applicable to all optimisers, and that even seemingly non-Bayesian optimisers can be understood in this way. Specifically we prove that arbitrary optimisation algorithms can be represented as a prior and a cost function. We examine the relationship between the Kolmogorov complexity of the optimiser and the Kolmogorov complexity of it’s corresponding prior. We also extended our results from deterministic optimisers to stochastic optimisers and forgetful optimisers, and we show that uniform randomly selecting a prior is not equivalent to uniform randomly selecting an optimisation behaviour. Lastly we consider what the best way to go about gaining a Bayesian understanding of real optimisation algorithms is. We use the developed Bayesian framework to explore the affects of some common approaches to constructing meta-heuristic optimisation algorithms, such as on-line parameter adaptation. We conclude by exploring an approach to uncovering the probabilistic beliefs of optimisers with a “shattering” method.

Ant Colony Optimization is a relatively new meta-heuristic that has proven its quality and versatility on various combinatorial optimization problems such as the traveling salesman problem, the vehicle routing problem and the job shop scheduling problem. The paper introduces an Ant Colony Optimization approach to solve the problem of determining a job-sequence that minimizes the overall tardiness for a given set of jobs to be processed on a single, continuously available machine, the Single Machine Total Tardiness Problem. We experiment with various heuristic information as well as with variants for local search. Experiments with 250 benchmark problems with 50 and 100 jobs illustrate that Ant Colony Optimization is an adequate method to tackle the SMTTP. (author's abstract) / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

Published Article / Planning problems are frequently encountered in everyday situations. The brute force approach of evaluating every possible solution for any medium size planning problem is just not feasible. Drools Planner is an open source Java library developed to help solve planning problems by using meta-heuristic algorithms. Drools Planner uses the Drools Expert (rule engine) for score calculation to greatly reduce the complexity and effort required to write scalable constraints in a declarative manner. This paper presents an introduction to Drools Planner, how it can be used to solve problems and concludes with an example scenario.

This thesis aims to produce a novel multi-objective algorithm that is based on Cuckoo Search by Dr. Xin-She Yang. Cuckoo Search is a promising nature-inspired meta-heuristic optimization algorithm, which currently is only able to solve single-objective optimization problems. After an introduction, a number of theoretical points are presented as a basis for the decision of which algorithms to hybridize Cuckoo Search with. These are then reviewed in detail and verified against current benchmark algorithms to evaluate their efficiency. To test the proposed algorithm in a new setting, a real-world combinatorial problem is used. The proposed algorithm is then used as an optimization engine for a simulation-based system and compared against a current implementation.

Software testing plays a necessary role in software development and maintenance. This activity is performed to support quality assurance. It is very common to design a number of testing suite to test their programs manually for most test engineers. To design test data manually is an expensive and labor-wasting process. Base on this reason, how to generate software test data automatically becomes a hot issue. Most researches usually use the meta-heuristic search methods like genetic algorithm or simulated annealing to gain the test data. In most circumstances, test engineers will generate the test suite first if they have a new program. When they debug or change some code to become a new one, they still design another new test suite to test it. Nearly no people will reserve the first test data and reuse it. In this research, we want to discuss whether it is useful to store the original test data.

Yes / In this paper we study a complex real world workforce scheduling problem. We apply constructive search and variable neighbourhood search (VNS) metaheuristics and enhance these methods by using a variable fitness function. The variable fitness function (VFF) uses an evolutionary approach to evolve weights for each of the (multiple) objectives. The variable fitness function can potentially enhance any search based optimisation heuristic where multiple objectives can be defined through evolutionary changes in the search direction. We show that the VFF significantly improves performance of constructive and VNS approaches on training problems, and "learn" problem features which enhance the performance on unseen test problem instances.

O presente trabalho trata da solução para o problema da elaboração de programações de transporte do sistema de distribuição de materiais da Força Aérea Brasileira (FAB). Essas programações de transporte consistem em definir os roteiros de entrega e coleta de materiais a serem realizadas simultaneamente em cada local de entrega/coleta a partir de um centro de distribuição, considerando-se a frota de veículos homogênea. Isto é característico de um Problema de Roteirização de Veículos com Coletas e Entregas Simultâneas (PRVCES). A gestão do sistema de distribuição física da FAB considera a complexidade desse sistema e os dados relativos às demandas de transporte de carga em cada um desses locais para elaborar as programações de transporte. Essas programações são elaboradas tendo em vista os limites de capacidade dos veículos, as características físicas das cargas e as prioridades de embarque. O gestor desse sistema possui boa visibilidade das demandas de transporte, porém, devido à grande quantidade de informações disponíveis e à elevada complexidade desse sistema, é impossível elaborarem-se manualmente programações de transporte que resultem em viagens de distribuição eficientes. O PRVCES foi resolvido por meio da meta-heurística Busca Dispersa (do inglês Scatter Search) integrada com a meta-heurística Descida em Vizinhança Variável (do inglês Variable Neighborhood Descent) utilizada como método de melhoria das soluções. Os resultados superaram ou se igualaram a alguns dos obtidos por outros autores para os mesmos problemas de teste com as mesmas restrições, o que demonstra que a Busca Dispersa implementada é competitiva para solucionar o PRVCES. Quanto à aplicação na FAB, os resultados mostraram que a utilização do método de solução desenvolvido resultará em programações de transporte elaboradas em curto tempo de processamento e que estas incidirão positivamente sobre a eficiência do sistema de distribuição de materiais da FAB. / This work deals with the solution to the problem of drawing up transport schedules in the material distribution system of the Brazilian Air Force (BAF). These transport schedules consist in defining the routes for material pickup and delivery to be accomplished simultaneously in each delivery/pickup location from a distribution center, considering a homogeneous fleet of vehicles. This is characteristic of a Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP). The management of the physical distribution of BAF considers the complexity of this system and the data regarding the cargo transport demands in each one of those locations to draw up transport schedules. These schedules are drawn up regarding the capacity limits of the vehicles, the physical characteristics of the cargoes and the shipping priorities. A good visibility of transport demands in each location is available to the manager of this system, but due to the great quantity of data to deal with and the high complexity of the physical distribution system of BAF, it is impossible to draw up transport schedules that result in efficient distribution trips. The VRPSDP was solved by means of the Scatter Search meta-heuristic integrated with the Variable Neighborhood Descent meta-heuristic as the solution improvement method. The results exceeded or equaled some of those obtained by other authors using the same test problems with the same restrictions, what indicates that the implemented Scatter Search is competitive to solve the VRPSDP. As for the application in the BAF, the results showed that using the solution method developed will result in schedules drawn up in short processing time and focused on the efficiency of the material distribution system of the BAF.

Otimização estrutural é uma área relativamente nova que vem sendo cada vez mais explorada. Existem muitos métodos clássicos, e outros mais recentes vem surgindo para disputar em eficiência, confiabilidade e rapidez na obtenção de um resultado ótimo. Os algoritmos são classificados em algoritmos determinísticos, que utilizam a informação do gradiente, ou seja, usam os valores das funções e suas derivadas, e os meta-heurísticos, algoritmos de otimização aleatórios que são métodos probabilísticos não baseados em gradiente, ou seja, usam somente a avaliação da função objetivo. São apresentados dois algoritmos meta-heurísticos relativamente recentes: o Harmony Search, baseado na improvisação musical em busca da harmonia perfeita, e o Firefly Algorithm, que é inspirado no comportamento da luz dos vagalumes. Vários exemplos clássicos de treliças 2-D e 3-D considerando otimização paramétrica e de forma, com restrições de tensão, deslocamento, flambagem e frequência natural, são apresentados para demonstrar a eficiência dos métodos. Os resultados são comparados aos de outros autores usando diferentes métodos encontrados na literatura. Os resultados indicam que os algoritmos de otimização estudados neste trabalho são melhores ou tão eficientes quanto os demais. Por fim, os métodos são aplicados à estrutura de um projeto de engenharia adaptado. / Structural optimization is a relatively new area that has been increasingly exploited. There are many classical methods, and newer are emerging to compete on efficiency, reliability and speed in obtaining an optimal result. The algorithms are classified into deterministic algorithms, which use the gradient information, i.e., use the values of the functions and their derivatives, and meta-heuristic algorithms, random optimization methods which are probabilistic methods not based on gradient, i.e., they use only objective function evaluation. Two relatively recent meta-heuristics algorithms are presented, Harmony Search, based on musical improvisation in search of the perfect harmony, and Firefly Algorithm, which is inspired by the behavior of the light of fireflies. Several benchmarks of 2-D and 3-D trusses considering size and shape optimization, with stress, displacement, buckling and natural frequency constraints, are presented to demonstrate the effectiveness of the methods. The results are compared to the others authors using different methods found in the literature. The results indicate that optimization algorithms studied in this work are better than or as efficient as others. Finally, the methods are applied to the structure of an adapted engineering design.

A planar single facility location problem, also known as the Fermat&ndash / Weber problem, is to