On The Performance Analysis Of Randomized Search Heuristics

Randomized Search Heuristics including Evolutionary algorithms, Ant Colony Optimization, and Artificial Immune Systems, etc. are class of general algorithms which are inspired by the natural phenomena and process and biological feature. Practice shows that, the class of randomized search heuristics has obtained great success in the problems of scientific research and engineering application, especially for the complex optimization problem whose structure is not known very well, and exhibits superior performance under the case without enough computing resources. In order to better understand the working mechanism of randomized search heuristics, and further guidance the design and applications of the algorithms, the researchers are eager to establish rigours theoretical basis for such algorithms. However, due to the randomness, population and other characteristics in the randomized search heuristics which presents very complex dynamic random behavior during the running process of algorithms, and increases the difficulty of theory. The results of theoretical research are relatively less.This dissertation focuses on the time complexity of randomize search heuristics for solving optimization problem from the perspective of theoretical research, also concerns the approximation performance for the NP-complete(hard) optimization problems. We investigate the relationship between the types of problems and algorithmic features, further explore the effectiveness of the randomize search heuristics for solving the classical optimization problems, and expected to improve and strengthen the theoretical basis of the randomized search heuristics. The main contributions of this dissertation are listed as follows:(1) We study the performance of evolutionary algorithms on the maximum leaf spanning tree(MLST) problem. The MLST problem is one of the classical combinatorial optimization problems in NP-completeness theory, which has strong application background in the practical problems such as network design and circuit layout, etc. This problem seeks a spanning tree with the maximum number of leaves in a connected undirected graph. A lot of heuristic algorithms, such as Evolutionary algorithms(EAs), are used to solve the MLST problem which is NP-hard. However, the performance analysis of EAs on the MLST problem has seldom been studied theoretically. Therefore, we theoretically analyze the performance of the(1+1) EA on the MLST problem. We demonstrate that the(1+1) EA obtains 5-approximation ratio and 3-approximation ratio on this problem in expected polynomial runtime2O(nm) and 4O(nm), respectively, where n is the number of nodes and m is the number of edges in a connected undirected graph. At the same time, we study the performance of the(1+1) EA on two instances of the MLST problem, and show that the local search algorithms may be trapped in the local optimum, while the(1+1) EA can escape the local optimum and obtain the global optimum.(2) We study the performance of Ant colony optimization(ACO) on the quadratic assignment problem(QAP). The QAP problem is one of the great challenges combinatorial optimization problems. This problem has been widely used in many practical problems such as logistics transportation and location. This paper contributes to a theoretical understanding of ACO on the notoriously difficult quadratic assignment problem(QAP). The worst-case bound on a simple ACO algorithm called(1+1) Max-Min Ant Algorithm((1+1) MMAA) for QAP problems is presented. It is shown that a degenerate(1+1) MMAA can obtain solutions with some approximation guarantees. Finally, a QAP instance is presented to demonstrate that ACO can outperform the 2-exchange local search algorithm, and the efficiency of the ACO algorithm is verified.(3) We analyze and compare the performance between the immune inspired hypermutations and standard bit mutations used in EAs on some optimization problems. Artificial immune systems have been widely applied to a variety of complex real-world problems. However, the theoretical work about the Artifficial immune systems is still in its infancy and there is a strong need for a rigorous theoretical foundation to better understand these heuristics. This paper contributes to a theoretical investigation on the performance of immune inspired hypermutations on some optimization problems. Specifically, we are interested in the performance difference between three mutation operators including immune inspired hypermutations, standard bit mutations and local search operators. We reveal that the immune inspired hypermutations can significantly beat local search operators and the standard bit mutation on some well-known pseudo-Boolean functions including Trap and Hierarchical-if-and-only-if functions and instances of two combinatorial optimization problems including the Max-Cut problem and the Minimum s-t-cut problem. The proofs give some insights into the relationships between the problem characteristics and algorithmic features. These analysis results also strengthen the usefulness of Artifficial immune systems from a theoretical perspective.