Investigations On Performances Of Evolutionary Algorithms And Hybrid Algorithms

The evolutionary algorithm (EA) is a bionic algorithm, which is inspired by the naturallaw of the fittest surviving the natural selection. Since it was proposed, the EA has beensuccessfully used to solve a large amount of optimization problems including practicalengineering problems and classical combinatorial optimization problems. However, wetheoretically understand very little about the performance of the EA on optimization problems.In the early stage, researchers mainly focused their attention on pseudo Boolean functions,afterwards on those combinatorial optimization problems in class P, such as minimumspanning tree and Eulerian cycle problems, then on NP-complete (hard) combinatorialoptimization problems. NP-complete (hard) combinatorial optimization problems playimportant roles in the field of computer science. Nevertheless, there are only a few theoreticalresults of EAs on NP-complete (hard) combinatorial optimization problems. It is generallybelieved that no algorithm can solve NP-complete (hard) combinatorial optimizationproblems in polynomial runtime, so we cannot expect that EAs can solve such problems inpolynomial runtime. We care about what approximation ratio the EA can achieve for a givenNP-complete (hard) combinatorial optimization problem, and when it can achieve such anapproximation ratio, etc. To answer these questions, we need to theoretically analyze theperformence of the EA.Combining different individual algorithms to construct hybrid algorithms seems to be apromising way for designing high performance algorithms. In recent years, a great number ofhybrid algorithms have been designed and used to solve complex optimization problems.Among them there are some outstanding representatives. Memetic algorithm is one of suchrepresentatives. While a number of experiments have shown that hybrid algorithmsoutperform individual algorithms on some problems, we theoretically know very little aboutthe phenomenon. Theoretical investigations on hybrid algorithms lag far behind experimentalinvestigations, and the theoretical foundation of hybrid algorithms is extremely weak.In the light of the above, the dissertation includes the main contributions on evolutionaryalgorithms and hybrid algorithms as summarized in the following.(1) Analyze the performances of EAs on the minimum label spanning tree (MLST)problemThe MLST problem is an issue arising from practical engineering, which seeks aspanning tree with the minimum number of labels in a connected undirected graph withlabeled edges. This problem has many applications in real-life, such as communication networks and data compression. To solve the MLST problem, many algorithms have beenproposed. The maximum vertex covering algorithm (MVCA) is one of them, which belongsto greedy algorithms. If each label in the input graph appears at most b times, then MVCAachieves an approximation ratio ofH b1b i1i.A few experimental investigations have shown that EAs are efficient for the MLSTproblem. However, we know in theory little about the performance of the EA on such anNP-hard problem. Therefore, the dissertation analyzes the performances of EAs on the MLSTproblem. The approximation ratios of EAs on this problem are obtained, and EAs have beencompared with local search algorithms on three instances. At the same time, an instance isconstructed where the multiobjective EA is proven to be better than the single objective EA.(2)Analyze the performances of EAs on Steiner tree problems (STP)The STP problem is a famous combinatorial optimization problem which is named afterJakob Steiner, a Swiss mathematician. Given some nodes in a graph or in the plane, the STPproblem looks for a minimum weight tree spanning these given nodes by introducing someauxiliary nodes. All nodes in the given set are called special nodes. The STP problem is alsoan NP-hard combinatorial optimization problem, and has wide applications in many fields,such as circuit layout, networks design.The STP is related to the way how the weight between two nodes is determined, thusseveral special cases are derived. This dissertation considers two cases of the STP. They arethe Steiner tree problem in graphs (GSTP) and the rectilinear Steiner tree problem (RSTP),which are still NP-hard. In the GSTP problem, the input is a weighted and undirected graph;the weight on each edge is given according to the considered problem; the special nodes aresome nodes in the graph. In the RSTP problem, the special nodes are some nodes specified inthe plane, and the weight between two nodes (x1, y1) and (x2, y2) equals to|x1-x2|+|y1-y2|.This dissertation theoretically analyzes the performances of EAs on the GSTP problemand the RSTP problem. On the GSTP problem, the approximation performances of EAs areinvestigated, and the EA is compared with other two heuristics on two instances of the GSTP.At the same time, an instance is constructed to show that the EA needs exponential expectedoptimization runtime. On an RSTP instance, while another heuristic may be trapped in thelocal optimum, the EA can jump out of the local optimum in expected exponential runtime.(3)Analyze the success rates of hybrid algorithmsHybrid algorithm is derived from combining two or more individual algorithms, aimingto exploit advantages of different algorithms. Whether or not a hybrid algorithm is better than the individual algorithms on which the hybrid algorithm is based, when is better, and to whatextent it is better than the individual algorithms? All these problems have not beentheoretically answered so far.In order to theoretically understand the performances of hybrid algorithms, thisdissertation concentrates on rigorously analyzing the success rates of hybrid algorithms, andinvestigates the relationship between the success rate of a hybrid algorithm and that ofindividual algorithms on which the hybrid algorithm is based. In detail, the success rates ofthree hybrid algorithms after h(0) iterations are obtained by utilizing Markov chain. Thesethree hybrid algorithms are based on different ways of combining two individual randomizedsearch heuristics. Then the relationships between the success rate curves of RandomWalk,local (1+1) EA and that of three hybrid algorithms on satisfiability (SAT) problem instanceshave been investigated. These three hybrid algorithms are based on different ways ofcombining RandomWalk and local (1+1) EA.