基于云计算的城市路网最短路径遗传算法求解*

杨庆芳 梅朵 郑黎黎† 马明辉 王伟

(1.吉林大学汽车仿真与控制国家重点实验室，吉林长春130022;2.吉林大学吉林省道路交通重点实验室，吉林长春130022;3.吉林大学交通学院，吉林长春130022)

随着城市路网的日渐复杂，在处理最短路径问题时，数据的处理量也日趋庞大，已有的最短路径算法已经无法满足高效率、快节奏的时代要求.继2006年Google首席执行官Eric Schmidt提出云计算以后，越来越多的企业开发了自己的云计算平台，其中，Apache开发的Hadoop分布式计算平台尤为流行.MapReduce是Hadoop的核心之一，它编写的并行程序简单，仅用很短的代码就可以完成复杂的分布式计算任务，为解决求解最短路径过程中计算量大的问题提供了有效的途径.

遗传算法(GA)具有全局寻优和潜在并行的特点，已经成为求解城市路网最短路径的研究热点之一［1-3］.目前，大量学者致力于研究遗传算法的改进以及与其他算法的组合，而计算机技术的迅速发展使大量的并行遗传算法也不断涌现，但国内在这方面的研究还很少.胡小兵等［4］针对一类带有聚类特征的旅行商问题(TSP)提出了一种并行的遗传算法，该算法首先将问题进行聚类处理，再对小问题运用遗传算法，效果很好，有效地提高了收敛速度.韩中华等［5］提出一种并行遗传神经网络算法，并引入迁移算子，应用于大规模路网的交通诱导，但是该算法没有考虑并行之间的通信时长.姚锦宝等［6］提出了一种基于消息传递接口(MPI)的多种群并行遗传算法，加入模拟退火算法，求解应急系统中的最短路径问题;对比试验表明，该算法适应度高，寻优速度快.张晓波［7］提出了一种改进的遗传算法，引入两种策略，一是粗粒度并行，任务划分为子任务，多处理器并行处理提高算法的速度，二是主从式迁移，避免算法过早收敛;并通过实例证明了算法的有效性.目前，并行遗传算法在解决城市路网最短路径问题中还没有得到很好的研究和应用.文中基于已有并行遗传算法的理论基础，以粗粒度遗传算法为核心，将其MapReduce并行化处理，提出一种全新的并行遗传算法来求解城市路网最短路径问题.

1 并行遗传算法

遗传算法已经有30多年的历史了，并且一直处于研究领域中比较活跃的部分，其效率由很多因素决定，如迭代次数、种群规模以及遗传算法的多样性和时间复杂度等等.遗传算法有初始化种群、选择、交叉和变异4个重要的阶段，每1个阶段采取的方法会直接影响遗传算法的运行时间.但是，遗传算法有两个缺点:①由于它是一个全局式搜索算法，容易过早收敛，陷入局部最优;②在选择、交叉、变异等步骤耗时多，效率太低.

遗传算法是基于生物进化的自然规律提出来的，生物进化的过程本来就具有并行性，所以遗传算法自身就携带着并行的特征，并行遗传算法应运而生［7-8］.根据并行的粒度，将并行遗传算法分为4种结构:主从式结构、粗粒度结构、细粒度结构和混合式结构.无论是主从式结构还是细粒度结构，都需要很大的通信消耗［9］，从而使算法的效率降低，不能得到广泛的应用.粗粒度结构是将一个种群分成若干个子种群，可以很好地改善遗传算法局部收敛的问题［10］.文中在Hadoop平台上实现粗粒度并行遗传算法，避免遗传算法局部收敛的同时，又可以有效地解决遗传算法效率低的问题.

2 MapReduce模型算法

Hadoop实现了Google的MapReduce编程模型. MapReduce是开源的、简化的并行计算模型，任何人都可以使用这个框架进行并行编程，同时适用于处理和产生大型数据集，很好地解决了以往并行模式的通信问题［11-14］.MapReduce主要由映射(Map)函数和化简(Reduce)函数两部分组成，Map把任务分解为多个任务，Reduce把分解后的多个任务进行汇总，得到最终结果.具体实现过程见表1.

表1 Map和Reduce函数Table1 Map and Reduce functions

在Map阶段，MapReduce框架将输入的数据分割为M个片断，对应M个Map任务［10］.每一个Map操作的输入是数据片断中的键值对〈k1，v1〉集合，Map操作调用用户定义的Map函数，输出一个中间态的键值对〈k2，v2〉集合［15］.接着，按照中间态的k2将输出的数据集进行排序，并生成一个新的〈k2，List(v2)〉元组，这样可以使得对应同一个键的所有值的数据在一起.然后按照k2的范围将这些元组分割为R个片断，对应Reduce任务的数目.

3 基于云计算的城市路网最短路径并行遗传算法

3.1 染色体编码

染色体编码是为了方便计算，将所求问题的解的形式转化为遗传算法能够识别的编码串形式的过程.在城市交通网络中，路网节点对应基因，路径对应染色体.因为多个节点连接起来就形成路径，随着节点的增多，路径会变长，所以文中采用不等长可变的实数编码方式，简单直观地表达实际问题，又无需解码.

采用不等长可变的实数编码方式，染色体随着基因数的变化而变化，为避免出现环路现象，要满足3个条件:①染色体不能超过最大长度N(N是节点个数);②每个染色体不存在重复基因，即每个节点最多访问一次;③每个染色体对应的OD，必须起自O终至D，从O出发，随机搜索下一个相连节点，直到D.如图1所示，节点1→6的OD，随机表示成染色体如下:

路径1:1→2→3→6

路径2:1→2→4→5→6

路径3:1→4→3→6

图1 网络示范图Fig.1 Network model figure

3.2 适应度函数

遗传算法在搜索过程中，不利用其他信息，通过定义一个适应度函数，利用这个函数计算每个个体的适应度值，不断指导下一代的选择进化，求得问题的最优解.因此，一个精确的适应度函数可以提高算法的速度和最优解的质量.在求解城市路网最短路径问题时，其目的是找到两点之间的最短路径，对于节点数为 N的路网，定义节点(si，sj)的路阻为d(si，sj)，则由节点1到节点N的总路阻为

式中，r表示节点.

求解最短路径就是求一条总路阻最小的路径，但是在算法初期，会出现大量的断路，用总路阻来判断染色体的优劣是不合理的，这时采用有效基因片段数l(i)来定义适应度函数:

式中，l(i)为染色体i的有效基因片段数，l(i)max为所有染色体中的最大有效基因片段数.

当算法进入一定代数时，再利用式(1)定义适应度函数，并将其转化为

由此可见，总路阻值越小，适应度值就越大，所对应的解就越好，即越接近于要求的最短路径.

3.3 迁移操作

完成适应度评价之后，Map操作结束，这时候进行迁移操作，目的是保持子种群的多样性，并且实现充分的信息交互，在避免串行遗传算法过早收敛的同时，提高解的质量.文中在云计算环境下实现迁移操作，主要采用异步随机迁移策略，即当每个子种群达到收敛之后，执行每个子种群中最佳个体的迁移操作，以保持种群多样性，避免过早收敛.

3.4 遗传操作

3.4.1 个体选择

个体选择的目的是将适应度值较高的优秀个体通过复制遗传给下一代，使优秀的个体不断进化.文中的个体选择方法选择轮盘赌选择法进行，则适应度为f(i)的个体被选择的概率为

3.4.2 交叉与变异

交叉操作是为了尽量将父代个体的优秀基因保留下来，形成一个全新的个体.变异的目的是避免算法陷入局部最优解，保持种群的多样性.因为自然界中的变异是为了适应环境，所以选择自适应的交叉和变异，交叉率和变异率是可以自适应调整的，从而避免遗传算法早熟的现象.概率函数［7］为

式中，fmax为当前代的最大适应度值，f^为当前代平均适应度值，fi为当前代第i个个体的适应度值，f'为当前代两个交叉个体中适应度值较大的，N是染为两个交叉个体中较大的那个在当前代中的优劣程度为第i个个体在当前代中的优劣程度，K1和K2为调整系数.

3.5 算法流程

整个算法的流程如图2所示.

图2 并行遗传算法流程图Fig.2 Flow chart of parallel genetic algorithm

(1)初始化种群.由主机器完成初始化种群，并将所有个体均分为多个子种群.设置遗传算法的参数，将参数和子种群一并分配到从机器上去.

(2)适应度评价.这一步骤在Map操作中进行.调用Map函数，定义子种群编号为键，个体为值，每个从机器对各自的子种群进行适应度评价，得到每个个体的适应度值，并将相同的键对应的值归约起来，进行迁移操作，存储到本地HDFS文件系统.

(3)选择操作.这一步骤开始进行Reduce操作，调用Reduce函数.主机器读取中间结果文件的位置，传达给Reduce，Reduce接到指令后再到某个DataNode上去读取，然后完成子种群的选择操作，每个子种群选择2个个体.

(4)交叉与变异操作.采用插入基因的方法对子种群中选取的2个个体进行交叉操作，产生2个全新的个体.然后采用自适应变异的方法进行变异操作，并将新产生的个体构成子代种群，按照〈k，v〉形式写入HDFS文件系统.

(5)终止条件.当进化代数达到最大并行进化代数，或者当个体适应度值达到稳定值时算法终止，输出最终结果;否则进行步骤(6).

(6)更新进化代数，转到步骤(2).

4 实验结果与分析

文中联合Java语言、MapReduce编程模式和遗传算法开发了基于云计算的城市路网最短路径并行遗传算法，并以节点数为2067、弧段数为6838的长春市路网(见图3)数据为基础，对该算法进行了实验测试.通过求解长春市路网中某一个OD的最短路径，验证了文中提出的并行遗传算法的有效性和可行性，并与串行遗传算法的性能进行了比较.硬件环境为8台双核PC机，软件环境为Redhat Enterprise Linux 5.0虚拟机+Hadoop 0.17.1和JRE1.5+JAVA.在实验中，将8台机器的名称分别命名为JobTracker1、TaskTracker1、TaskTracker2、TaskTracker3、TaskTracker4、TaskTracker5、TaskTracker6、TaskTracker7.其中，Job-Tracker1作为主节点，同时也作为从节点，其余7台机器只作为从节点.在JobTracker1上安装和配置好Hadoop 0.17.1和JRE1.5，并通过scp命令将其部署到其余7台机器上去.

图3 长春市路网图Fig.3 Road network diagram of Changchun

实验设计:设置种群规模为1000，最大进化代数取50、100、150、200、250、300、350、400，在节点数为1、2、4、8的4种情况下进行实验，其中节点数为1时即为串行算法，节点数为2、4、8时为并行算法.由于遗传算法是一个启发式算法，受各种随机因素的影响比较严重，每组实验的子实验进行50次取平均值，得到的平均适应度值和平均运行时间结果如图4和图5所示，图中1、2、4、8代表节点数.

图4 适应度值对比图Fig.4 Contrast figure of fitness value

图5 平均运行时间对比图Fig.5 Contrast figure of average running time

从图4中可以看出，并行算法的适应度值大于串行算法，节点数为4的时候适应度值最大，即结果最优，这表明基于云计算的并行遗传算法具有较好的稳定性.但是，当节点数增加到8时，适应度值变小，这是因为节点数越多，子种群中的个体数量越少，过少的个体数量无法保证种群的多样性，从而导致搜索区域比较集中，算法陷入过早收敛.当节点数为2时，由于子种群的数目太少，无法满足充分的信息交换，从而直接影响算法进程，也不利于提高解的质量.

对算法进行并行的主要目的就是减少算法的运行时间，从图5可以看出，并行算法的运行时间要比串行算法的少，节点数为4的时候运行时间最短.当节点数为8时，运行时间反而增大了，因为随着节点数的增加，节点间的迁移操作越来越频繁，通信负荷越来越大，消耗了大量的时间，所以算法的运行时间增大.

并行加速比(Sn)是衡量并行算法运行效率的重要指标，并行加速比越大，并行算法的效率越高.并行加速比的公式是Sn=Ts/Tp，其中Ts为串行算法运行时间，Tp为并行算法运行时间.取进化代数为400，当节点数为1时，串行算法的运行时间为Ts=32.2s，当节点数为4时，并行算法达到最高性能，运行时间为Tp=7.8 s，所求得的加速比为Sn= Ts/Tp=32.2/7.8=4.1.由此可见，并行算法与串行算法相比，算法的运行效率有了显著的提高，最佳运行时间7.8s，满足交通诱导的需求.

5 结语

文中运用云计算中的MapReduce编程模式将遗传算法并行化处理，有效地改善了遗传算法在求解城市路网最短路径问题时存在的缺陷，同时提高了遗传算法处理庞大数据集的能力.实验结果表明:文中提出的基于云计算的遗传算法在处理城市路网最短路径问题时具有高效性、有效性和可行性.下一步的研究内容有两点:一是对遗传算法自身进行优化，进一步提高算法的性能;二是基于MapReduce的遗传算法和基于MPI的遗传算法的比较研究.

［1］ 安竹林.基于MPI的并行遗传算法研究［D］.合肥:合肥工业大学计算机与信息学院，2006:3-6.

［2］ 刘晓平，安竹林，郑利平.基于MPI的主从式并行遗传算法框架［J］.系统仿真学报，2004，16(9):1938-1940. Lu Xiao-ping，An Zhu-lin，Zheng Li-ping.Master-slave parallel genetic algorithm framework on MPI［J］.Journal of System Simulation，2004，16(9):1938-1940.

［3］ 郑锋，李名世，蔡佳佳.基于OpenMP的并行遗传算法探讨［J］.心智与计算，2007，1(4):396-402. Zheng Feng，Li Ming-shi，Cai Jia-jia.Parallel genetic algorithms based on OpenMP［J］.Mind and Computing，2007，1(4):396-402.

［4］ 胡小兵，黄席樾.对一类带聚类特征TSP问题的并行遗传算法求解［J］.计算机工程与应用，2004，34(4): 66-74. Hu Xiao-bing，Huang Xi-yue.Solving traveling salesman problem with characteristic of clustering by parallel genetic algorithm［J］.Computer Engineering and Applications，2004，34(4):66-74.

［5］ 韩中华，吴成东，杨丽英，等.基于并行遗传神经网络算法的动态路径选择方法［J］.微计算机信息，2005，12(12-2):166-169. Han Zhong-hua，Wu Cheng-dong，Yang Li-ying，et al.The method of dynamic route choice based on parallel genetic and neural network algorithm［J］.Microcomputer Information，2005，12(12-2):166-169.

［6］ 姚锦宝，夏禾，姚宝珍.基于并行遗传算法的车辆路径问题［J］.物流技术，2010(5):65-66. Yao Jin-bao，Xia He，Yao Bao-zhen.Solution to vehicle routing problem based on parallel genetic algorithm［J］. Logistics Technology，2010(5):65-66.

［7］ 张晓波.并行遗传算法求解应急系统最短路径的研究［D］.太原:太原理工大学计算机与软件学院，2005: 25-59.

［8］ 吴莲.基于城市道路网的遗传最短路径算法研究［D］.南京:南京理工大学理学院，2010:4-5.

［9］ Verma A，Llora X，Goldberg D E，et al.Scaling simple and compact genetic algorithms using MapReduce［R］.Urbana:Illinois Genetic Algorithms Laboratory，University of Illinois，2009:1-16.

［10］ Verma A，Llorà X，Goldberg D E，et al.Scaling genetic algorithms using MapReduce［C］∥Proceedings of the Ninth International Conference on Intelligent Systems Design and Applications.Pisa:ISDA2009，2009:13-18.

［11］ Vijayalakahmi V，Akila A，Nagadivya S.The survey on MapReduce［J］.International Journal of Engineering Science and Technology，2012，4(7):3335-3342.

［12］ Poka Laxmi，Jayant Umale，Sunita Mahajan.MoHPBGA: multi-objective hierarchical population balanced genetic algorithm using MapReduce［J］.International Journal of Computer Applications，2012，40(2):1-7.

［13］ Zhan Shao-bin，Huo Hong-ying.Improved PSO-based task scheduling algorithm in cloud computing［J］.Journal of Information＆Computational Science，2012，13(9):3821-3829.

［14］ McCubbin Christopher，Perozzi Bryan，Levine Andrew，et al.Finding the‘needle’:locating interesting nodes using the K-shortest paths algorithm in MapReduce［C］∥Proceedings of the 11th IEEE International Conference on Data Mining Workshops.Vancouver:ICDMW，2011:180-187.

［15］ 刘鹏.云计算［M］.北京:电子工业出版社，2011: 189-226.