用多种群遗传算法求解车辆路径问题

摘要

车辆路径问题（Vehicle Routing Problems,VRP），即如何利用有限的运输资源来完成1定量的运输任务，并且使得运输成本最低的问题。车辆路径问题由于其巨大的经济效益，在过去的40多年间得到了突飞猛进的发展。本文在已有方法研究的基础上，针对标准遗传算法在解决车辆路径问题上容易出现早熟，容易陷入局部最优解的缺点，对传统的遗传算法进行改进，提出了多种群遗传算法（Multiple_population Genetic Algorithms）。即在求解过程中将初始化两个种群，分别选取不同的交叉变异概率，在每1次迭代完后将第1个种群之中的适应度较低的个体与第2个种群中适应度较高的个体进行交换，并且保存每个种群的最优解到精英种群，以解决传统遗传算法容易出现早熟，容易陷入局部最优解的问题。实验结果表明，经过改进的遗传算法比1般算法收敛速度更快，求解质量更为优良。

关键字：遗传算法；物流调度；多种群；遗传算子

Multi- Populations Genetic Algorithms for Vehicle Routing Problems

Abstract

Vehicle Routing Problems, how namely use the limited transportation resources to complete the ration the transportation duty, and causes the transportation cost lowest question. Vehicle Routing Problems as a result of its huge economic efficiency, obtained the development during more than 40 years in the past which progresses by leaps and bounds. This article in by has in the foundation which the method studies, is easy in view of the standard genetic algorithms in the solution Vehicle Routing Problems to appear precociously, is easy to fall into the partial optimal solution shortcoming, makes the improvement to the traditional genetic algorithms, proposed the multi- populations genetic algorithms. In the solution process the initialization two populations, separately will select the different overlapping variation probability, after each time will iterate the sufficiency high individual carries on the first populations in sufficiency low individual with the second population in the exchange, and will preserve each center group the optimal solution to the outstanding person population, by will solve the tradition genetic algorithms to be easy to appear precociously, will be easy to fall into the partial optimal solution question. The experimental result indicated that, after improvement genetic algorithms compared to general algorithm convergence rate quicker, the solution quality is finer.

Key word: Genetic Algorithms, Vehicle Routing Problems, Good Population and Bad Population, Elite Population

（转载自http://zw.NSEAC.com科教作文网）