Research Of Cellular Genetic Algorithms Application On Combination Optimization

With the rapid development and progress of society,combinatorial optimization problems have very important application value in various fields.There are many feasible solutions to large-scale combinatorial optimization problems,and it takes a long time to solve them using traditional optimization methods.However,evolutionary algorithm can find a satisfactory solution in a short time.Cellular genetic algorithm(CGA)is a new algorithm formed by the combination of genetic algorithm(GA)and cellular automata(CA).CGA algorithm can better reflect the characteristics of biological evolution and heredity through neighborhood interaction,and has good optimization performance.Operation sequencing problem,0-1 knapsack problem(0-1KP)and traveling salesman problem(TSP)are classical combinatorial optimization problems.Aiming at these three kinds of problems,based on CGA algorithm,this thesis proposes greedy cellular genetic algorithm,evolutionary cellular genetic algorithm and hybrid cellular genetic algorithm based on simulated annealing algorithm,and verifies the accuracy,effectiveness and reliability of these three new algorithms through experiments.The main research contents of this thesis are as follows:1.Operation sequencing optimization is one of the important links and difficulties in process planning.In order to solve this problem quickly,a greedy cellular genetic algorithm(GCGA)is proposed.Firstly,GCGA algorithm uses topological sorting(TS)algorithm to generate the processing process of the initial population;At the same time,in order to reduce the total cost of the initial population,the processing resources of the initial population are selected combined with greedy algorithm;Finally,the crossover and mutation operators are designed to combine the elite individual retention strategy and ensure the feasibility of processing procedures in the evolution process.2.In order to find the optimal solution of 0-1KP problem,an evolutionary cellular genetic algorithm(ECGA)is proposed.Based on the CGA algorithm using Moore neighborhood,ECGA algorithm introduces three evolution rules corresponding to Moore neighborhood,and tests the optimization performance of ECGA algorithm using three evolution rules on 0-1KP instances through experiments;In order to ensure the feasibility of the initial population and the chromosome in the iterative process,the greedy repair operator is used to repair the infeasible solution.3.A hybrid cellular genetic algorithm(SCGA)based on simulated annealing(SA)algorithm is proposed to solve TSP problem.SCGA algorithm uses partial mapping crossover and inversion mutation to avoid repeated numbers after crossover and mutation;It introduces evolutionary rules;At the same time,the elite individual retention strategy is designed,combined with simulated annealing algorithm for local search.