Optimization Research Based On Genetic Algorithm

Researchers have been highly interested in heuristic algorithms since the 1960s. And these algorithms used to solve complicated optimization problems are inspired from natural evolution. Genetic algorithms, which have strong abilities of optimization and stochastic searching, are widely used in industry and engineering and have great impact on these practical fields.Traveling salesman problem(TSP) which is a tipical combinatorial optimization is very hard to solve. And for years, people have been making efforts to test a genetic algorithm on TSP. However, most of the existed research is focused on static TSPs and not suit for the dynamic environment. Recently, researchers are more and more interested in TSP of dynamic environment (DTSP), and it is significant to design an effective algorithm for a real world DTSP. There is another type of optimization problem called Multi-objective optimization. It deals with a number of conflict objectives and aims to find a set of optimal solutions. It is obvious that to design an effective algorithm to solve these problems is significant, for simply deal with these objectives by a weighted function will not be satisfied by decision maker. Genetic algorithm has shown it's advantages and is widely used in multi-objective optimizasion.The research work in this paper focused on two aspects of optimization problem. One is TSP solving and the other is multi-objective optimization. For TSP solving, our main work is as following:First, we improved the inver-over operator with a remember scheme which can preserve the good gene in the recombination procedure. And experiment data shown that the improved algorithm has faster convergence and stronger ability of search. Second, inspired from traffic jam of the busy people going on work and off work, we build the math model of TSP in dynamic environment where there is a Gauss peak of block paths in the metaphase of the genetion. And we designed respond algorithm for the emergent situation with good edges of the existed path. Meanwhile, to make the algorithm more effective, we improved the inver-over operator and make it work in our optimization.The experiment makes us believe that our dynamic model and algorithm is effective for this kind of DTSP.And the main research on genetic algorithm of multi-objective optimization problem includes the following two aspects.Firstly, we proposed an efficient algorithm to construct the non-dominated set called the deal's principle with no backtracking. The deal's principle can reduce the compare times of individuals, thus improve the efficiency of the algorithm. Secondly, we proposed a method called density based genetic algorithm of multi-objective optimization. From the analysis of a number of MOGAs, we can see that the density is really important in distribution maintenance. So, in our DMOGA we take the density of the population into account, and calculated the sum influence function of other individuals to the considering individual thus can reflect the distribution correctly. Our distribution maintenance method of DMOGA only has a complexity of O(n2). To make DMOGA more efficient, we use deal's principle to construct the non-dominated set. The abundant experimental results and analysis shown DMOGA can maintain a good distribution, and at the same time with high efficiency.