Αλγόριθμοι αποικίας μυρμηγκιών

Νομικός, Φραντζέσκος Γ.

Master Thesis

Author

Νομικός, Φραντζέσκος Γ.

Date

2012-11-27

Abstract

Chapter 1 presents a summary of the ant colony optimization (ACO) – a metaheuretic inspired from the behavior of real ants, a method of solving difficult problems of combinatorial optimization. Chapter 2 analyzes a way to expand ACO in continuous domains without having to do any critical change to its structure. We denote that ACO is extended to continuous domains from ACOR. Chapter 3 demonstrates in section 3.1 an algorithm inspired from the ants for optimization in continuous search spaces based on the production of random vectors with multivariable Gaussian probability density function. It is called MACACO and is compared with the Continuous Ant Colony System (CACS) and the Ant Colony Optimization on Rn (ACOR). In section 3.2 is described an aggregation pheromone system (APS), that is an expansion of ACO for continuous domains, using the collective behavior of the individuals that communicate utilizing aggregation pheromones. APS is tested on several test functions. Results indicate that APS could solve efficiently real parameter optimization problems. Chapter 4 presents in section 4.1 some convergence properties for a class of ant colony optimization algorithms. Furthermore, it is proved that after an optimal solution has been found, it demanded a finite number of iterations to grow higher the pheromone trails that are associated with the search of the optimum solution more than any other pheromone trail. In section 4.2 is presented a convergence analysis of ACO to deceptive problems and it is established that ACO can achieve reachability convergence but not asymptotic convergence for a class of first order deceptive problems (FODS) without the assumption of a minimum pheromone at each iteration of the algorithm.