Improvement Of Genetic Algorithm And Its Application In Combinatorial Optimization

Genetic Algorithm [1.3] is a searching method using probability and its basic theorem is to simulate the biology evolution. For its few limitation on the presumption of the solution space, GA do not require the solution space to be continuous and derivable, and built-in parallelism make it a useful method in many area extensively.Combinatorial optimization [14] focuses on the problems, which have finite feasible solution, or exist largely in life, especially in the designing project. The classic combinatorial optimal problem includes the Traveling Sales Problem and Flow Shop Scheduling problem, and so on. This article focuses on the research of improving the genetic algorithm, and its application in the combinatorial optimization.This article has some research and analyses about the theory, optimization, and application ofgenetic algorithm. Firstly, we introduced the basic principle of genetic algorithm------schematatheorem, and analyzed its applicability to the coded scheme of one dimensional chromosome; This article briefly summarizes the rationales of Genetic Algorithm and gives an intensive discussion about such as the premature convergence, genetic drifting, how to keep society diversity, and so on. At same time the article introduces some improved methods, such as: Hybrid Genetic Algorithm, Improved Genetic Algorithm basing on the gene bank, Adaptive Genetic Algorithm, Niche and Sharing Function, and so on. Considering the randomicity which the basic genetic algorithm produces the original population, we designed a Simulated Annealing Hybrid Genetic Algorithm based on the gene bank[7.14] and applied this algorithm to solve the classical TSP problem. The improved genetic algorithm has following advantages:1. The initial population produced by the gene bank and partheno-genetic algorithm. For the parfheno-genetic operator produce the initial population by the excellence gene in gene bank, the individual of the initial population has more the excellence gene than the individual which was produced randomly. Everyone of the population is so close to the whole optimal solution, so they can produce the optimal solution during the population evolving quickly.2. It speed the convergence of algorithm by the strong local searching of the Simulated Annealing Algorithm, and also increase the reliability of finding the whole optimal solution.At same time, we applied this algorithm to solve the classic combinatorial optimization problem, Traveling Sales Problem. The results showed that the improved algorithm had better convergent property; and convergent speed is more quickly; and convergent stability is better. The algorithm also found the best solution now.For the limitation brought by the invariability of crossover probability and mutation probability during the evolutional process[10.13], we brought forward an improved Adaptive Genetic Algorithm based on the gene bank. It makes the genetic operator to change with concentrated degree of population adaptively. The improved genetic algorithm has following advantages:1. The initial population produced by the gene bank and partheno-genetic algorithm. Everyone of the population is so close to the whole optimal solution. The individual of the population has more the excellence gene than the individual which was produced randomly. So they can produce the optimal solution during the population evolving quickly.2. During the genetic process, it changed adaptive the genetic operator basing on theconcentrated degree of fitness. It insured the population evolved in the direction of evolvinginto the individual with better property. So it increased the convergent speed of improvedalgorithm.At same time, we applied this algorithm to solve the Flow Shop Scheduling problem. The results showed that convergent speed of the improved algorithm is more quickly; and convergent stability is better. The running efficiency of the improved algorithm is much better than it of the original algorithm. In the end of this article, we analyzed respectively the astringency of two improved algorithms b...