Applied Research Of Genetic Algorithm In Combinatorial Optimization

Genetic algorithm is a new global optimization search algorithm, its basic idea is to simulate the biological evolution process. Genetic algorithm search space it has not restrictions, are not required to seek the solution in the continuity, providing a complex system optimization problems for solving a common framework, the problem does not depend on the specific areas of the problem types have a strong robustness, genetic algorithm has parallelism, these features will determine the genetic algorithm in many areas of extensive use. Practice has proved that genetic algorithms for combinatorial optimization of NP-complete problem solving is very effective.Combinatorial Optimization major studies are those containing a finite number of feasible solution of the problem, it has a wide range of engineering design applications. This is one of the important and very common applications is to consider how to effectively use scarce resources to improve their productivity. The typical engineering design problems include a knapsack problem, bin-packing problem, traveling salesman problem, vehicle routing problem, machine scheduling order and balance, create yuan design issues, equipment, location and layout. Although in theory, the optimal solution of these problems can be obtained by simple enumeration, but in practice usually can not be achieved under all circumstances. Because for such a practical design of the issue, they are the number of feasible solutions may be particularly great, so combinatorial optimization, one of the most challenging issues is how to effectively address these combinatorial explosion. The solution to this difficult problem a very effective method is to use genetic algorithm.This study is based on a combination of genetic algorithm optimization problem. Major study is the standard genetic algorithm to improve algorithms and genetic algorithms through these improved algorithm for solving combinatorial optimization problems. Especially given the two more classical combinatorial optimization problem-traveling salesman problem, vehicle routing problem solution. The main work of this article include the following aspects: (1) First, an overview of some of the basic principles of genetic algorithms, including the history of genetic algorithms, definition, application, characteristics and standard genetic algorithm genetic manipulation. Also concluded on the basis of our predecessors to study some of the common genetic algorithm improved algorithm. (2) In order to overcome the standard genetic algorithm crossover probability and mutation probability fixed by the limitations brought aboutSex, this paper to the standard genetic algorithm genetic operations are carried out each step is optimized, especially in the cross-operation in the "partial match" approach, the mutation operation, quoted a "polynomial mutation" approach, and This method is applied to solve the TSP problems, and 32 cities across the country the best path to solve the test results show that this improved genetic algorithm has good convergence and get the optimal solution.(3) In order to overcome the genetic algorithm in the lack of local search capabilities, this paper genetic algorithms, or each step of the genetic operations are optimized, in particular, is a strong local search ability of hill-climbing algorithm with the underlying genetic algorithm combined with each other to form the a hybrid genetic algorithm, and apply it to solve the vehicle routing problem (VRP). Experimental results show that the problem VRP hybrid genetic algorithm to improve search capability, so the population evolution are more likely to produce the optimal solution.