Research And Application Based On Double Population Hybrid Genetic Algorithm

GA is an adaptive global search algorithm, which takes the individual as the basic units to search for the best solution, and the search process of which is simulate to the evolution process of species. Through the coding technique, it converts the problem space to individual encoding, the fitness function takes the place of the objective function as the measure of individual strengths and weaknesses, so the problem solving process is converted into optimal fitness of the individual search process. The optimal algorithm does not rely on the characteristics of the problem itself, by selecting operation, populations have been evolving towards the optimal solution, and it reflects the high adaptability, which makes the genetic algorithm widely used in many fields.GA takes the individual as the basic units of its searching, the independence of the individual evolution is very high, each individual evolution is an independent search process to the solution of the problem, and it can be said that GA is a kind of hidden parallel algorithm which takes population size as the parallel scale, which gives the genetic algorithm a stronger global searching ability, however, when solving practical problems it does not have enough strength of convergence because of the lack of local search ability, so it always cannot accurately converge to the optimal solution after evolving many generations. Another reason for this phenomenon is when the evolution comes to the later period, the degree of similarity between individuals will continue to improve, in the evolution process, there would be a large number of inbreeding phenomenon, and population diversity would be destroyed, so as to make the algorithm converges to local optimal solution or near the optimal solution.In this paper, based on the defects of genetic algorithm itself, double population hybrid genetic algorithm, DPHGA is proposed, by constructing the double parallel evolutionary population, it ensures the population diversity and can avoid inbreeding population, so to what it can improve the efficiency of algorithm. Hybrid genetic algorithm, by adding the local optimization algorithm to genetic algorithm, in ensuring the global search ability of genetic algorithm, at the same time, can of course strengthen the local search ability. DPHGA algorithm is based on genetic algorithm and takes the hybrid algorithm as the framework, it can be applied to solving the different practical problems by using different ways of encoding.In this paper, the content of research includes two parts:1. Unconstrained function optimization, for the convenience of research, the unconstrained function optimization problem with only two decision variables and multimoding is chosen in this part. Encoding by binary encoding which has strong extensibility and maneuverability, and constructing double populations by random matching principle replication, with the improved random selection operator, it can ensure the population diversity, at the same time, it can also improve the efficiency of crossover operator effectively, crossover operation and mutation operation are designed according to the features of the problem, to improving the local search ability, the simulated annealing algorithm is added into DPHGA. At last, the test results of three international examples and literature comparison, confirmed DPHGA algorithm has strong ability of convergence and accuracy.2. VRPTW problem, for the problem of the vehicle routing problem with time Windows, first to deal with constraints, constraints on load, this part adds greedy algorithm to the decoding part for processing, and the time window constraints, by penalty function method for processing, the DPHGA is still used in optimization. First of all, every customer was given a number, it uses the natural number coding method to encode all of the customers who must be distributed, in view of the different codes, different crossover operator and mutation operator are designed, instead of simulated annealing algorithm, mutation operator, to which adds2-opt algorithm thought to be a local search algorithms, enhancing the local search ability of algorithm. At last, in order to further ensure the diversity of population, the regeneration strategy, by who the same individuals in the population will be reborn is used in DPHGA. Through the test of two commonly VRPTW instances, results of which shows it is better than the algorithm in the literature.