CARP问题混代并行遗传算法的研究

陈未如， 马 超， 王翠青

(沈阳化工大学计算机科学与技术学院，辽宁沈阳 110142)

遗传算法(Genetic Algorithm，GA)最早由美国密歇根大学Holland教授在1975年提出［1］，是在达尔文进化论思想的基础上开发出的一种模拟自然界生物进化过程来求解优化问题的一类自适应技术.遗传算法具有应用广泛、适合于并行化处理等优点.遗传算法善于全局搜索所有解空间，但存在容易早熟且局部寻优能力不足等缺欠.针对这些缺欠，许多研究者从多个方面开始着手多遗传算法的改进.

吉根林［2］详细介绍了遗传算法的特点和基本原理，并讨论了并行遗传算法和混合遗传算法以及遗传算法的性能分析.Mariusz Nowostawski和Riccardo Poli［3］主要介绍了几种重要的并行算法的分类.沈洁陈和李开荣［4］讨论了遗传算法进行并行处理的主从式并行算法、粗粒度并行算法及细粒度并行算法，分析和比较各种方法的优缺点，介绍了并行遗传算法的适用范围和应用前景.

针对CARP问题，目前大多采用启发式非精确的解法.例如，Golden［5］在1981年提出的增量合并方法;1989年Pearn W L［6］提出的路径分割方法;2006年但正刚、蔡临宁、吕新福和郑力［7］运用小环路启发式方法求解CARP问题;2010年刘琳、朱征宇、许林和陈飞［8］提出混合随机搜索算法来求解CARP车场选址问题;Tang K，Mei Y and Yao X［9］等提出了改进的带有启发式候选解策略的文化基因算法，即MAENS算法来求解CARP问题等.

本文着重研究了遗传算法与并行计算，提出PCMGA和MGPGA的并行遗传算法.通过实验分析和比较，验证PCMGA算法和MGPGA算法在并行机中高效的并行计算性能，并把PCMGA算法和MGPGA算法运用到在目前广泛应用的CARP问题的求解中，取得了令人满意的求解效率.

1 遗传算法及其并行性分析

1.1 基本的遗传算法

生物的遗传和进化过程主要是通过染色体之间进行交叉和变异来完成，遗传算法是模拟自然界生物进化过程用于解决最佳化的搜索问题的计算模型，它是自然遗传学和计算机科学相互结合、相互渗透的新的计算方法［10］.

在遗传算法中，参与运算的对象是由多个个体组成的一个群体.与自然界中生物的进化过程相似，遗传算法的运算过程也是反复迭代的过程，首先，进行个体适应度的评价或者计算，从中选出优良个体作为初始种群，记为t，经过选择、交叉和变异运算后得到新一代种群t+1.这个群体经过不断的遗传和进化等操作，并且每次都按照优胜劣汰的原则将适应度值大(适应环境较好)的个体遗传到下一代，这样在最终群体中将会得到一个优良的个体X，它即是达到或接近问题的最优解［11］.

1.2 遗传算法的并行性分析

遗传算法是借鉴了生物界自然选择的原理发展起来的具有高度并行、随机和自适应的搜索算法.近几年来，对遗传算法的研究非常广泛，已被成功应用于经济管理、交通运输、工业等不同领域，解决了许多问题，是一种成熟的搜索算法［12］.

当用遗传算法解决较大规模的实际问题时，需要对大量的个体进行编码，对个体进行适应度值的计算、选择、交叉和变异运算，使得算法的进化运算过程进展缓慢，因此，遗传算法的并行计算问题受到重视，已成为广大研究者的一个重要研究领域.并行遗传算法可以从下列4个方面对其进行改进和发展［11］.

(1)适应度评价算法的并行性:由于对初始种群以及每一个新产生的个体都要进行适应度值的计算，并根据适应度的结果进行选择，因此，在整个遗传操作中，个体适应度值的计算占用时间较长，如能找到高效并行的适应度计算方法，将能够提高整个遗传算法的效率.

(2)个体间适应度评价的并行性:由初始种群生成新个体的过程中，每个个体适应度之间是独立、无相互依赖的，可将个体适应度的计算在不同处理器或者不同进程之间独立并行地进行，以加快求解速度.

(3)子代群体产生过程的并行性:父代产生子代的遗传运算中，与选择运算相关的是个体适应度值的大小，交叉和变异运算与个体的编码方式直接相关，因此，可将子代生成过程中的选择、交叉和变异并行地进行运算，以加快求解过程.

(4)群体分组的并行性:从整个遗传算法来看，遗传算法的操作对象是由多个个体所组成的一个群体.可将大的群体分成若干个组，运用遗传算法在多台处理器上将各个分组独立进行遗传操作，来提高整个进化过程的效率.

传统遗传算法的并行性主要从个体适应度评价并行性、整个种群中各个体适应度评价并行性、子代群体产生过程并行性及基于群体分组并行性进行考虑.

2 并行遗传算法的改进

遗传算法是计算机科学与进化论相结合的产物，它不仅有包括自组织、自适应和自学习性在内的智能特性，而且还有内在本质的并行特性，这些特性使它具有非常广泛的应用范围.在第1.2节所述的遗传算法并行性研究的基础上，本文主要研究并提出了PCMGA和MGPGA并行遗传算法.

2.1 并行交变遗传算法—PCMGA算法

基于上述子代群体产生过程的并行性，对传统的并行遗传算法做了一定的改进:即主进程负责对种群适应度的计算、排序和选择操作;将遗传操作中的交叉操作和变异操作分配给各子进程并行计算.子进程将交叉和变异操作后得到的新个体再返给主进程，直到得到满足要求的最优解或者达到预先设定的最大迭代次数.将此子代种群并行产生过程的遗传算法称为并行交变遗传算法(Parallel Crossover and Mutation Genetic Algorithm)，简称PCMGA算法.

PCMGA算法是在传统遗传算法的基础上，将父代群体产生下一代群体所需进行的遗传运算分解，选择操作由主进程完成，交叉操作和变异操作由从进程完成.这样，产生子代群体的选择、交叉、变异等遗传操作就可以相互独立地并行进行，提高了处理器资源的利用率，以达到高速求解CARP问题的目的.

2.2 混代并行遗传算法—MGPGA算法

在第1.2节所述的4种并行处理方式中，都保留了原始遗传算法分代的概念.然而在现实世界中，生物在长期的遗传繁衍过程中，有的进化速度快，有的慢，代与代之间已经没有明确的界限.本文提出一个新的思路，充分利用遗传过程的并行性，将该过程交由多个进程同时处理，并将每次遗传变异所产生的新个体直接插入到已经概率有序的种群中参与遗传，以加速求解过程，而不是等到整个新生代产生后再形成新的种群.这个思路打破了代与代之间的界限，称为混代并行遗传算法MGPGA(Mixed Generation Parallel Genetic Algorithm).

与PCMGA类似，MGPGA算法分主进程和从进程两部分.从进程的工作与PCMGA算法相同，主进程的工作也与PCMGA类似，所不同的是MGPGA算法中没有明确的新种群排序、选择、淘汰过程，每当有新的个体产生，立即将之以适当的适应度关系插入到原种群中并参与新的遗传，淘汰一个较差的个体.目前常见的并行遗传算法基本上都是基于1.2节所述的4种并行机制或其组合来实现的.而混代并行遗传算法MGPGA则是一种新的探索和研究，也是本文研究的重点.MGPGA算法的主进程流程如图1所示，MGPGA算法的从进程流程如图2所示.

图1 MGPGA算法主进程流程Fig.1 The Flow of Main Process in MGPGA

图2 MGPGA算法从进程流程Fig.2 The Flow of Secondary Process in MGPGA

从性能上看，算法具体解题时间计算如下:

式中，ti，初始化时间;tc，每个子代个体产生的平均时间，包括相应的通信时间和进程同步等待时间;tm，每个新个体插入到种群中的平均时间;p，从进程个数;m，算法过程产生的新个体总数.

从式(1)中可以看出:如果对于给定问题，算法不变，则m基本确定(等于PCMGA算法的n·g)，决定运算时间T的关键因素是tc、tm和p.

与PCMGA算法相比较，MGPGA有以下几个优点:

(1)tm·m 等于 ts·g，但是不能简单这么计算，因为MGPGA将tm分配每个新个体的产生过程当中，可以充分利用主进程的空闲等待时间，使MGPGA算法CPU利用率提高，从而提高了运算速度;

(2)由于没有明显的代划分，不需要代间同步等待时间，从而减少部分运算时间;

(3)MGPGA使新个体加入遗传的时间提前.如果按代计算，平均提前n/2个子个体产生时间.而如果不考虑代的划分，该时间还会提前更多.新个体提前参与遗传，意味着遗传速度的提高.虽然有可能产生种群早熟问题，但如果能避免这个问题，将会对遗传算法的改进和应用起到重要作用.

3 仿真实例

3.1 问题描述

CARP(Capacitated Arc Routing Problem)是车辆带有容量限制的弧的路径选择问题，是Golden等最早提出的，并由他们证明该问题是NP难问题［13］.在我们的日常生活中，CARP 的应用范围非常广泛，凡是针对道路进行服务的问题都可以纳入其研究范围，例如:邮件快递、城市垃圾回收、输电线检查、班车路线安排问题等.

CARP问题定义如下［14］:给定带权强连通有向图G=(V，A)，其中V和A分别代表图的顶点集和弧集.顶点集V可以分为两个集合，Vd={v1，v2，…，vq}和 Vc={vq+1，…，vq+n}，分别代表了q个车场顶点和n个非车场顶点;A={τi|i=1，2，…，m}代表弧集，是由 m 条有向弧构成的集合，其中包含ε条服务弧，τi弧的花费(长度)值为ω(τi)，其中ε条服务弧组成了子集R⊆A，对于任意弧 τi∈R，其系数 λ 为1，对于任意非服务弧，τi∈A-R，λ的值为0.先假设一个有N车辆的车队，问题的目标是寻找到K条路径，每辆车辆从车场 v(x=1，2，…，q)出发，服务完该路径后再回到原车场，要求需服务弧有且只能属于一条路径，且每条路径服务弧需求的总和部超过服务该路径的车辆容量C，每条弧只能被一辆车服务，但一辆车可以服务多条路径，最终使得所有车总花费最小.

3.2 数学模型

对CARP问题的描述可建立数学模型如下:

以上计算公式中，式(2)为目标函数，即使得总的花费最小，式(3)～式(6)为约束条件.其中Ti表示第i条路径，|Ti|表示该路径中服务的弧数量.一个可行解包含了K条路径，分别表示为 T1，T2，…，Tk，K 为所有的路径总数，Tij表示第i条路径中第j条服务弧，L(Tij)表示Tij的路径长度.(3)式表示每一条路径Ti中的总需求不大于服务该路径的车辆容量C.(4)式为花费函数，其中路径Ti的花费为:从停车场σ出发，到第一条服务弧的最短路径，加上第二条弧的长度，加上第二条弧到第三条弧的最短路径，一直累加到最后一条弧，然后再加上最后一条弧到车场 σ 的最短路径.d(Tij，Ti，j+1)表示 Tij的终点到Ti，j+1的起点之间的最短距离，σ表示行驶路径Ti车辆的停车场.(5)式保证了每条服务弧都被服务，ε为服务弧的总数.(6)式定义了集合Rk，Rk中的元素有第k条路径中的服务弧组成.任意两条路径中不能有重复的服务弧，保证了任意一条服务弧只能被服务一次.

3.3 仿真实验

CARP问题是一个具有广泛应用背景与重要理论价值的组合优化难题.实验采用CARP问题是一个城市垃圾回收问题.在车辆的数量N和容量C有限制的前提下，寻找一个最短路径使得花费最小，并且能够把所有垃圾的道路进行清扫.

实验是在Inter Core i5四核处理器，8.00 GB内存，采用C语言，编译环境为VS2010，MPI并行环境下实现的.实验数据来源于Eglese［15］中的3组基于CARP的实例，在表1所示的实验环境下，在进程数 P 分别为 1、2、3、4、5、6、7、8、9、10的条件下，对3组实验数据独立运行30次，实验的参数设定如表1所示，实验的数据说明如表2所示，将所得的最优解取30次中的平均值，与文献［16］中的求解结果进行对比，来验证PCMGA和MGPGA算法效率.由于篇幅有限，在表3中仅例举了进程数P为1、4和9时对应的最优解的实验结果.

其中，表 2中的 vertexNum、ReqEdgeNum、NonReqEdgeNum、vehicle、capacity、best 和MAENS分别代表CARP问题在实验中的顶点数、有需求的边、没有需求的边、车辆数、车的容量、已知理论上的最优解和运用MAENS算法［9］求得的最优解.

表3中P代表试验中的进程数，PCMGA、MGPGA和A_TIME分别表示当用P个进程数计算时所求得的最优解以及所求的最优解30次所用的平均时间.

表1 初始化参数设定Table 1 Setting of Initialization parameter

表2 实验数据Table 2 Experimental Data

表3 针对表2实验数据用PCMGA和MGPGA算法进程数P为1、4和9的实验结果Table 3 Experimental Results of Table 2 with process number 1，4 and 9 in PCMGA and MGPGA

以下图3～图5为当P等于1～10时针对E1、E2和 E3中的 CARP问题，用 PCMGA和MGPGA算法求得最优解所用的平均时间.

图3 E1组数据用MGPGA和PCMGA平均时间Fig.3 E1:The average time with MGPGA and PCMGA

PCMGA和MGPGA算法都是基于MPI的主从式并行算法，理论分析可以得出:当系统中进程数为2时，当主进程初始化操作结束后，就将交叉和变异的遗传操作交给子进程，此时主进程闲置;当子进程遗传操作结束后，主进程负责处理提交的新个体的排序和选择操作，此时从进程闲置.因此，P=2时的并行遗传算法实际上同一时刻还是只有一个进程在单独操作，并改变原有传统遗传算法的基本特点，却在传统遗传算法的基础上增加了并行程序所需的MPI初始化、进程之间的通信和MPI结束等操作，因此P=2的并行遗传算法的运行效率明显会低于P=1的传统遗传算法.

当P=4或8时求解CARP问题的平均时间较小.因为实验环境为四核处理器，当P=4时，为1个主进程3个从进程，资源利用率较高，但是当P=5时，就要有某一个CPU要分给主从两个进行参与运算，其它从进程运算结束后，与主进程通信的等待时间交叉，因而出现计算时间的高峰.

图4 E2组数据用MGPGA和PCMGA平均时间Fig.4 E2:The average time with MGPGA and PCMGA

图5 E3组数据用MGPGA和PCMGA平均时间Fig.5 E3:The average time with MGPGA and PCMG

从以上图中分析，PCMGA和MGPGA算法都将群体中的个体分布在各个处理器的存储器中，独立地对子群体进行遗传进化操作，所以，能够有近似线性的加速度比，能够有效地提高遗传算法的运行速度.尤为明显的是MGPGA并行遗传算法，从进行的实验可以看到:当MGPGA算法正在运行时，系统CPU的使用率一直都是100%，直到算法结束;而PCMGA算法运行时CPU使用率最高为96% ～99%.以上实验结果的比较可以看出;PCMGA和MGPGA的并行遗传方法都有效地提高了遗传算法的运行速度，MGPGA并行遗传算法是一种效率极高的并行遗传算法.

4 结语

主要研究了目前遗传算法的4种不同并行性，比较它们的适用场合;根据CARP问题的目标函数、适应度计算时间以及遗传操作中的交叉和变异计算时间长等特点，构建了主从并行模型改进处理后的遗传算法，提出了 PCMGA和MGPGA算法，提高了遗传算法求解速度;在MAENS算法基础上实现了PCMGA和MGPGA算法，并将其运用到CARP问题求解中.实验证明:PCMGA和MGPGA算法在整体算法运行的平均时间以及最优解上，取得满意的结果:在求解精度上与改进前算法相当，求解速度随处理器个数的增加而有所提高，并行效率令人满意.另外，本文所提出的混代并行遗传算法MGPGA在提高收敛速度上有很好的效果，较未采用混代技术的并行算法PCMGA的收敛速度有成倍的提高.

［1］ Holland J H.Adaptation in Natural and Artificial Systems［M］.Michigan:University of Michigan press，1975:5-6.

［2］ 吉根林.遗传算法研究综述［J］.计算机应用与软件，2004，21(2):69-73.

［3］ Nowostawski M，Poli R.Parallel Genetic Algorithm Taxonomy［R］.Adelaide，SA:KES’99，1999:88-92.

［4］ 沈洁陈，李开荣.遗传算法的并行实现［J］.扬州大学学报(自然科学版)，2000，3(2):1-6.

［5］ Golden B L，DeArmon J S，Baker E K.Computational Experiments with Algorithms for a Class of Routing Problems［J］.Computers and Operation Research，1983(10):47-59.

［6］ Pearn W L.Approximate Solutions for the Capacitated Arc Routing Problem［J］.Computers and Operations Research，1989(6):589-600.

［7］ 但正刚，蔡临宁，吕新福，等.CARP问题的小环路启发式求解方法［J］.系统工程学报，2006，21(5):502-507.

［8］ 刘琳，朱征宇，许林，等.求解CARP车场选址问题的混合随机搜索算法［J］.计算机应用，2010，30(6):1508-1512.

［9］ Tang K，Mei Y，Yao X.Memetic Algorithm with Extended Neighborhood Search(MAENS)for Capacitated Arc Routing Problem［J］.IEEE Trans.On Evol.Comput，2009，13(5):1151-1166.

［10］陈国良，王煦法，庄镇泉，等.遗传算法及应用［M］.北京:人民邮电出版社，1996:25-30.

［11］周明，孙树栋.遗传算法原理及应用［M］.北京:国防工业出版社，1999:65-68.

［12］ Erick Cantu-Paz.A Summary of Research on Parallel Genetic Algorithms［R］.Illinois:IlliGAL，1995.

［13］ Golden B L，Wong R T.Capacitated Arc Routing Problems［J］.Networks，1981，11(3):305-316.

［14］李小花，朱征宇，夏梦霜.多车场CARP问题的改进遗传算法求解［J］.计算机工程与应用，2009，45(11):230-234.

［15］ Eglese R W.Routing Winter Gritting Vehicles［J］.Discrete Applied Mathematics，1994，48(3):231-244.

［16］ Fu Haobo，Mei Yi，Tang Ke，et al.Evolutionary Computation(CEC)［C］.Barcelona:IEEE，2010:3229-3236.