Biological Heuristic Algorithms And Improvement Research

Nature has always been a rich source of human creativity, human's ability to understand things come from the interactions of human and natural. Many phenomena in nature give people inspirations:Organisms and natural ecosystems can solve many complex optimization problems by their evolutions. In recent years, some biological heuristic algorithms which different from some classical mathematical programming principles have emerged, such as evolutionary algorithm, particle swarm optimization, ant colony algorithm and artificial immune algorithm, etc. They have greatly enriched the modern optimization techniques and provided a practical solution for the NP-hard problem in which those of traditional optimization techniques are difficult to solve. With the advantage of efficient optimization performance and no need of problem's specific information, they have been widely used in engineering optimal design, computer science, combinatorial optimization, optimal scheduling and other fields. This thesis mainly studies the evolutionary algorithm, ant colony optimization, particle swarm algorithm and artificial immune algorithm.This thesis is divided into six chapters. Chapter 1 is an introduction, which introduces the historical development of biological heuristic algorithm and the current development status, especially presents the background and development status of the evolutionary algorithm, ant colony optimization, particle swarm algorithm and immune algorithm. Finally, gives a brief introduction of the research contents and methods of the thesis.Chapter 2 studies the different aspects of genetic algorithm, evolutionary programming, evolution strategies and genetic programming after introducing the basic principles of evolutionary algorithm, then makes a compare study from the coding strategy, selection method and genetic operators. The two main operators in evolutionary algorithm: mutation and crossover are discussed.Chapter 3 introduces the basic principles of ant colony algorithm and the travelling salesman problem which is a typical combinatorial optimization problem. Evolution strategies converge fast but it has the problem of premature convergence. The max-min ant system has better solving ability but it converges slowly. To this problem, we combine max-min ant system with evolution strategies. Using max-min ant system to calculate the optimal solution of every iteration and make a mutate operation on the iterative optimal solution to speed up the convergence rate of solutions. The combination algorithm is applied into the Chinese Traveling Salesman Problem (CTSP) to verify the superiority of the algorithm proposed.Chapter 4 introduces the basic principles of particle swarm optimization and the steps of solving traveling salesman problem. For the shortcomings of particle swarm optimization (PSO) algorithm easily trapping into the local minimum value, we propose a hybrid algorithm which introduces the mutation factors of evolutionary algorithm and simulated annealing algorithm into the PSO. Finally, the hybrid algorithm is applied to solve the Chinese traveling salesman problem. Experimental results of basic simulated annealing algorithm, basic particle swarm algorithm and the particle swarm algorithm with mutation factor are compared.The origin of artificial immune algorithm, basic principles and steps of solving practical optimization problems are introduced in chapter 5. The emphasis is focus on the information entropy based and Euclidean based immune algorithms. In response to the shortcomings of two algorithms mentioned above, an improved immune algorithm is presented. The algorithm redefines the method of calculating the density of antibody, thus a new strategy to maintain the diversity of the antibody group is proposed. The algorithm proposed is applied into the Chinese traveling salesman problem (CTSP), in which we propose a new vaccine extraction and injection method. The simulation experiments show that the new algorithm can converge to the optimal solution faster and the solution obtained is more efficient. The algorithm proposed is an ideal improved one for solving complex optimization problems.In chapter 6, we summary some research results, and point out some problems existed in the research of biotechnology heuristic algorithm. The directions of future research are reviewed. The further research contents and directions of the biotechnology heuristic algorithm are prospected.