Modeling analysis and improvement of ant colony optimization algorithms

Optimizacija kolonijom mrava (ACO) je metaheuristika koja se uspješno primjenjuje za rješavanje teških optimizacijskih problema, osobito kombinatoričkih optimizacijskih problema koji pripadaju klasi NP-teških problema. Ciljevi ovoga rada su proširiti spoznaje o načinu djelovanja algoritma ACO i istražiti njegove zakonitosti, omogućiti poboljšanja uvođenjem novih strategija te razviti novi algoritam ACO za probleme kombinatoričke optimizacije. U radu su sistematizirani i analizirani načini mjerenja učinkovitosti stohastičkih optimizacijskih algoritama. Predloženo je i argumentirano korištenje kvantila umjesto uobičajene prakse korištenja aritmetičke sredine za iskazivanje dobrote algoritma. Predložene su poopćene strategije odabira rješenja za ažuriranje feromonskih tragova u algoritmima optimizacije kolonijom mrava. Na ispitnim je instancama problema, uz pomoć neparametarskih statističkih testova, eksperimentalno dokazano da predložene strategije mogu poboljšati svojstva algoritama ACO. Definirane su i analizirane pojave grupiranja i separacije feromonskih tragova na temelju čega je razvijen model za određivanje vjerojatnosti konstrukcije rješenja. Primjenom modela su izvedeni izrazi za vjerojatnost konstrukcije rješenja za problem trgovačkog putnika, nesimetričan problem trgovačkog putnika i problem kvadratnog pridruživanja za algoritme MAKS MIN sustav mrava i sustav kolonije mrava. Predložen je algoritam ACO za koji se umjesto isparavanja feromonskih tragova povremeno provodi stezanje tragova, a koji je funkcionalno ekvivalentan algoritmu MAKS MIN sustavu mrava do iteracije algoritma u kojoj feromonski trag izlazi izvan zadanih feromonskih granica. Zbog drugačijeg postupka ažuriranja feromonskih tragova predloženi algoritam ima nešto manju računsku složenost. Algoritam je uporabljen za rješavanje problema izrade oligonukleotidnih mikropostroja, za koje je pronašao bolja rješenja od do tada poznatih najboljih rješenja.Introduction. The ant colony optimization (ACO) is a metaheuristic which has been successfully used to solve computationally difficult optimization problems, especially combinatorial optimization problems which belong to the class of NP-hard problems. Main objectives of this dissertation were: to improve ACO algorithms by introducing new pheromone update strategies; to model ACO algorithms to allow insights into how the algorithm works, to be able to predict its behavior and improve its performance; to develop a new ACO algorithm for combinatorial optimization problems that will be competitive with other ACO algorithms. For the purpose of these studies, the algorithms were implemented in C++ and performed on a cluster of computers and on personal computers. Sections description. After a short introduction in the Section 1 (“Introduction”), optimization problems, their complexity classes, taxonomies, and algorithmic approaches are explained in the Section 2 (“Optimization problems”). The Section 3 (“Ant Colony Optimization”) explains ACO algorithms, their most important variants, and hybridization with local optimization methods. This section surveys current research trends, ACO applications, and considerations for successful ACO usage. In the Section 4 (“Analysis of Experimental Data”), different possibilities for measuring efficiency of stochastic optimization algorithms are systemized and analyzed. Distributions of the solutions are analyzed and suitable non-parametric statistical methods are chosen and studied. The quantiles are shown to have many better properties for measuring algorithmic efficiency than the prevailing arithmetic mean. In the Section 5 (“Pheromone Update Strategies”), new strategies of choosing solutions for pheromone reinforcement are introduced, named kappa-best, max-kappa-best and kappa/lambda- best, which are generalizations of classical strategies with parametric tunable greediness. In the Section 6 (“Experimental Evaluation of Pheromone Update Strategies”), comprehensive experimental researches were conducted with various pheromone update strategies on instances of Traveling Salesman Problem (TSP), Asymmetric Traveling Salesman Problem (ATSP), and Quadratic Assignment Problem (QAP) with MAX-MIN Ant System (MMAS), with and without local optimizations. Data were analyzed using medians (10-quantiles and 90-quantiles of the solutions are also included in the Appendix A), counting, Kruskal-Wallis, Friedman and Iman Davenport tests, and various post hoc methods. The performed statistical methods confirmed that the new strategies can indeed improve algorithmic behavior. Similarities between different strategies and sensitivity to parameter variations were examined with graphical methods and by using non-parametric variable association measures. The Section 7 (“Phenomena related to pheromone trails values”) investigates what happens to pheromone values as the algorithm progresses. The pheromone grouping and the pheromone separation are formally defined, along with measures that characterize these phenomena, like a degree, expressiveness of phenomena, and a number of pheromone trails inside certain intervals. Predictions about the number of trails inside border intervals in the case of the pheromone separation are derived for TSP, ATSP, and QAP. Comprehensive experimental evaluation confirmed that these phenomena often occur in practice and that the numbers of components inside the intervals match the predicted numbers. The Section 8 (“Solution Construction Probabilities Model”) exploits the phenomena explored in the Section 7 and introduces an exact model for solution construction probabilities in the case that the pheromone separation has occurred. Based on the model, mathematical expressions are derived for ACO algorithms that use the random-proportional and the pseudorandom-proportional rule, for different construction methods (e.g. nearest neighbor or greedy) for TSP, ATSP and QAP. Mathematical expressions for the probability of constructing 2 exchanged and 3 exchanged solutions of the most probable solution for QAP with an ACO algorithm are also presented. To simplify the probability calculation, special factors dependent on the problem size were precalculated and tabulated in the Appendix B. Heuristic information and the parameter beta are taken into account by introducing correction factors chi and zeta. The correction factors are computed for different instances of the TSPs and their values are tabulated in the Appendix C. Based on the developed model, some case studies of algorithmic behavior are presented. In the Section 9 (“Three Bounds Ant System”), a new ACO algorithm named Three Bounds Ant System (TBAS) is presented. Some theoretical properties of TBAS are proven. It is shown that TBAS has lower computational complexity than MMAS, which can cause from negligible to very significant practical speedup. Experimental comparison of MMAS and TBAS for instances of TSPs, ATSPs, and QAPs confirmed that TBAS can achieve better solutions than MMAS. Three Bounds Ant System was applied to the microarray layout problem, and for almost all available instances of the problem, TBAS found solutions (listed in the Appendix D) that are better than the publicly available best known solutions. Conclusion. In this dissertation the usage of quantiles is augmented, various generalized pheromone reinforcement strategies are proposed, the model of calculating solution construction probabilities is introduced, and the algorithm Three Bounds Ants System (TBAS) is developed. The comprehensive experimental evaluation showed that the proposed pheromone reinforcement strategies can improve performance of ACO. The strategy that best suits ACO and its parameters depends on the optimization problem and the implementation details of ACO, although there are some general rules. When an algorithm converges faster, it is usually better to use a greedier strategy. If a local optimization is employed, the algorithm is more robust, i.e. differences between different strategies are smaller. Although one strategy can be the most suitable for many instances of some optimization problem, for a particular instance, some other strategy can be better. Based on the proposed model, the mathematical expressions for various cases of the solution construction are devised, which are exact under some conditions and include heuristic information, unlike previously published expressions based on simplified models that can introduce huge errors. It is shown that the standard definition of heuristic information for TSP largely increases the probability of finding an optimal solution at the beginning of the algorithm, but as the algorithm progresses, benefits of using heuristic information fade. Besides for evaluating the usefulness of heuristic information, the mathematical expressions can be used for choosing suitable pheromone bounds or to estimate a minimal number of iterations for finding the optimal solution. A new ACO algorithm, TBAS, is developed. It is proven that TBAS and MMAS are functionally equivalent, until some limiting iteration is reached. TBAS has lower computational complexity than MMAS. In terms of solution quality, TBAS outperformed MMAS in most tested instances of QAP, and found better solutions than the previously published best known solutions for almost all instances of the microarray layout problem