Cooperative methods in optimisationanalysis and results

Resumo

This dissertation focuses on the study, design, development and application of centralised cooperative strategies for optimisation problems, Those models consist on many parallel cooperating agents, where each agent carries out a search in a solution space. Firstly, we study the most known trajectory-based and population-based metaheuristics and next, the cooperative strategies are introduced. The contributions of this thesis start analysing some aspects of the centralised cooperative strategies as the composition and the cooperation scheme. Using the Uncapacitated Single Allocation p-Hub Median Problem as test bed, we compare the performance of homogeneous and heterogeneous strategies and give some insights about the benefits of each type of composition. Using the same problem, we test a cooperation scheme based on Reactive Search ideas proposed by the author and we compare it against other techniques. The results show the better performance of the reactive scheme. Another issue tackled in this dissertation is the application of centralised cooperative strategies to Dynamic Optimisation problems, where they have not been applied before. The method is evaluated over different benchmarks obtaining a very robust performance that improves two state-of-the-art methods for these problems. Finally, a cooperative method that allows the resolution of a set of instances is presented. The strategy is based on a set of operators and a basic learning process that is fed up with the information obtained while solving several instances. The output of the learning process is an adjustment of the operators. The instances can be managed sequentially or simultaneously by the strategy. The method has been tested on different SAT instance classes and the results confirm that a) embedding problem specific algorithms into our strategy, instances can be solved faster than applying these algorithms instance by instance and b) that the simultaneous resolution of instances performs better than the sequential one.