Research On Modified Extremal Optimization Algorithms And Their Applications In Combinatorial Optimization Problems

As a major branch in optimization, combinatorial optimization has been widely applied in many areas, e.g., computer science, artificial intelligence, transportation, production scheduling, network communications, statistical physics, and bioinformatics etc. Recently, borrowing the theories and methods from statistical physics has brought new vitality into the studies on the theories and algorithms of combinatorial optimization. Extremal optimization is such an optimization method inspired by the theory of self-organized critility from statisitical physics community. This new method has been successfully applied to some benchmark and practice engineering problems. However, compared with those well-studied algoirhtms, such as simulated annealing, and genetic algorithm, the studies on this new method have just started. In fact, there are some open problems worthy to solve. For example, the original extremal optimization algorithms have been shown to be not so effective for these strongly-connected problems, e.g., traveling salesman problem (TSP), SK spin glass problem, protein folding problem and so on. So far, only few researches have been reported on the evolutionary probability distribution of extremal optimization. In addition, most of the previous studies have overlooked the structure information, such as backbones, hidden in the combinatorial problems.The thesis focuses on the studies on the modified extremal optimization algorithms and their applications in some typical NP-hard combinatorial problems including TSP, maximum satisifability (Max-SAT) problem, SK-spin glass, and protein folding problem, from these aspects, such as the evolutionary probability distributions, initial solutions, and the structure features of combinatorial problems. Specially, the research works of this thesis are summarized as follows:(1) In view of the power-law based evolutionary probability distribution adopted by the previous EO algorithms, this thesis presents some modified extremal optimization (MEO) algorithms based on some extended evolutionary probability distributions. In addition, inspired by the statistical property of k-neighbor-nodes of the optimal solutions, the modified NNMEO algorithms with heuristic initial solutions are also presented for TSP here. The experimental results on the stochastic and hard TSP instances have firstly shown that the original power-laws are not the best evolutionary probability distributions in EO algorithms while the other distributions, such as exponential and hybrid ones, may be the better choices. In some sense, this can dispel the previous misconception thatμ-EO with exponential distribution perform worse thanτ-EO. Moreover, even for the same evolutionary mechanism, NNMEO algorithms starting from heuristic-based initial solutions are superior to the corresponding MEO algorithms from random ones.(2) In view of the static evolutionary mechanism adopted by most of all the previous EO algorithms, a dynamical evolutionary mechanism based method called multistage extremal optimization (MSEO) is proposed. Dividing the whole optimization process into multistage, MSEO repeats the process that consists of choosing the best configurations obtained by the previous stage as its initial solutions for the current stage and adjusting the different values of the control parameters until obtaing high-quality solutions. The experimental results on some hard TSP instances have demonstrated the proposed MSEO performs better than the original static algorithms.(3) Inspired by the basic ideas of MEO algorithms and BE-EO algorithm, we propose an optimization framework called EOSAT, which is based on the Bose-Eninstein distribution based initial solutions and extended evolutionary probability distributions. Under this framework, two novel modified EO algorithms are presented. From the experimental results on the Max-SAT instances near phase transition, we discover that the proposed algorithms can provide better performances than BE-EO.(4) Based on EOSAT framework, this thesis presents a novel method called backbone information guided extremal optimization (BGEO) by embeding the backbone information of combinatorial optimization problems into the search process. The superiority of BGEO algorithm to the EOSAT and other reported popular optimization algorithms is demonstrated by the experimental results on many hard Max-SAT instances. This work provides a novel idea and method for designing more effective combinatorial optimization algorithms.(5) Based on the above research work, the basic idea of MEO algorithms is extended to HP model-based protein folding problems. Moreover, the basic ideas of MEO and BGEO algorithms are also extended to SK spin glass problems. Their effectiveness in solving strongly-connected problems is demonstrated by a large number of experimental researches.Finally, conclusions and future research work on this newly developed extremal optimization are given.