On The Performance Analysis Of Evolutionary Algorithm And Ant Colony Algorithm

Bio-inspired randomized search heuristics such as Ant Colony Optimization and Evolutionary algorithm are class of popular algorithms which are inspired by the natural phenomena,process and biological feature.These algorithms have been widely used to solve a large variety of practical problems and also have very good results.These algorithms are easy to implement and they can be applied to those problem whose structure is not well enough understood.Evolutionary algorithms are inspired by the natural evolution of species and the algorithm iteratively applys mutation,recombination and selection operators to evolve a set of solutions for an optimization problem.Ant Colony Optimization is inspired from the way that real ants optimize their tracks of searching for food and ants have the ability of finding the shortest path from their nests to food source by exchanging information via pheromones.Many empirical studies have proved the effectiveness of these algorithms for a large number of problems,but a thorough understanding is still far away.In this dissertation,we focus on these algorithms from the perspective of theoretical research and analyze the approximation performances of single-objecitve evolutionary algorithm and ACO for combinational optimization problems and also we analyze the running time of multi-objective evolutionary need to optimize the pseudo-Boolean problems.And this work is done using methods and tools commonly used the analysis of randomized.The main contributions of this dissertation are listed as follows:(1)We study the performance of(1+1)EA on the maximum independent set(MIS)problem which is a classic graph combinational optimization problem.MIS problem is also NP-complete,and it cannot be solved in polynomial time,unless P=NP,therefore a lot of approximation algorithms are used to solve it.Evolutionary algorithms(EAs)are efficiently used to solve many optimization problems.However,we know little about that how the approximability of EAs on the MIS problem.We theoretically analyze the performance of the(1+1)EA on MIS problem.We demonstrate that the(1+1)EA obtains an approximation ratio on this problem in an expected polynomial time.For k-Set Packing problem which is a special case of MIS problem,and we also demonstrate that the(1+1)EA obtains an approximation ratio on this problem in an expected polynomial time.Finally,we reveal that the(1+1)EA has better performances than the local search algorithms on an instance of the MIS problem.We present that the local search algorithm with 3-flip will be trapped in local optimum while the(1+1)EA can find the global optimum.(2)Evolutionary algorithms have been quite successfully used on solving multi-objective optimization problems for a long time.However,theoretical analysis of multi-objective evolutionary algorithms(MOEAs)is mainly restricted to the simple evolutionary multi-objective optimizer(SEMO).The Pareto archived evolution strategy(PAES)is a simple but important multi-objective evolutionary algorithm which is come from the study of telecommunication problems.In this paper,we make a first step towards investigating the rigorous running time analysis for PAES.We show that the PAES outperforms the SEMO on function PATH when the PAES uses a simple mutation operator.However,it can not find the whole Pareto front with overwhelming probability on the well-studied function LOTZ.After that,we propose an improved Pareto archived evolution strategy(IPAES)and show that the IPAES can find the whole Pareto front of LOTZ in an expected polynomial running time.Finally,the running time analyses of IPAES with two other local mutation operators on two pseudo-Boolean functions are presented.Based on these analyses,we can conclude that by selecting an appropriate local mutation operator the performance of algorithm can be greatly improved on some specific problems.(3)We study the performance of two ACO algorithms,called on the traveling salesman problem with distance one and two(TSP(1,2))which is an NP-complete problem.It is shown that two ACO algorithms obtain an approximation ratio of 3/2 with regard to the optimal solutions in expected polynomial runtimes.We also study the influence of pheromone information and heuristic information on the approximation performance.Finally,we construct an instance and demonstrate that ACO outperforms the local search algorithms on this instance.