A hybrid genetic - Particle Swarm Optimization Algorithm for the vehicle routing problem

摘要

Usually in a genetic algorithm, individual solutions do not evolve during their lifetimes: they are created, evaluated, they may be selected as parents to new solutions and they are destroyed. However, research into memetic algorithms and genetic local search has shown that performance may be improved if solutions are allowed to evolve during their own lifetimes. We propose that this solution improvement phase can be assisted by knowledge stored within the parent solutions, effectively allowing parents to teach their offspring how to improve their fitness. In this paper, the evolution of each individual of the total population, which consists of the parents and the offspring, is realized with the use of a Particle Swarm Optimizer where each of them has to improve its physical movement following the basic principles of Particle Swarm Optimization until it will obtain the requirements to be selected as a parent. Thus, the knowledge of each of the parents, especially of a very fit parent, has the possibility to be transferred to its offspring and to the offspring of the whole population, and by this way the proposed algorithm has the possibility to explore more effectively the solution space. These ideas are applied in a classic combinatorial optimization problem, the vehicle routing problem, with very good results when applied to two classic benchmark sets of instances.