基于云计算的混合并行遗传算法求解最短路径

张文金，许爱军

（广州铁路职业技术学院 教育技术中心，广东 广州510430）

基于云计算的混合并行遗传算法求解最短路径

张文金，许爱军

（广州铁路职业技术学院 教育技术中心，广东 广州510430）

为提高最短路径求解问题的效率，提出一种基于云计算的细粒度混合并行遗传算法求解最短路径的方法。方法采用云计算中Hadoop的MapReduce并行编程模型，提高编码效率，同时将细粒度并行遗传算法和禁忌搜索算法结合，提高了寻优算法的计算速度和局部寻优能力，进而提高最短路径的求解效率。仿真结果表明，该方法在计算速度和性能上优于经典遗传算法和并行遗传算法，是一种有效的最短路径求解方法。

云计算；遗传算法；禁忌搜索算法；最短路径

0 引言

近年来随着社会的发展和人们生活节奏的加快，高效率、快节奏需求使得最短路径求解成为一大新的研究课题。云计算是继网格计算、对等计算之后产生的新的计算模式[1]，其中 Apache开发的 Hadoop云计算平台被广泛应用，其核心 MapReduce能够进行并行编码，且编码效率高，为大规模的最短路径求解提供了有效的解决途径。遗传算法[2-3]（Genetic Algorithm，GA）由于具有潜在并行处理能力的特点，许多学者致力于并行遗传算法的研究，以提高搜索和寻优的速率，同时克服GA在进化初期超常个体引起的种群过早收敛到局部最优解的问题[4-5]。为提高GA的局部搜索能力，许多学者也将GA与其他算法结合，研究了混合遗传算法。其中禁忌搜索算法（Tabu Search Algorithm，TSA）的创始人将 GA与TSA结合提出了混合遗传算法 HGA（Hybrid Genetic Algorithm），HGA提高了算法的局部搜索能力和收敛速度，得到了广泛研究与应用[6-7]。同时混合遗传算法在并行遗传算法中也得到了一定研究，文献[3]将并行遗传算法和禁忌搜索算法结合，提出了混合并行遗传算法（Hybrid parallel genetic algorithm，HPGA），由于算法利用并行遗传算法的特征，提高了算法效率。

针对上述研究基础，本文在云计算中的 MapReduce并行编码模式基础上，提出一种基于细粒度混合并行遗传算法的最短路径求解方法。算法将细粒度并行遗传算法与禁忌搜索算法相结合，提高算法的局部寻优能力和收敛速度，进而应用到提高最短路径的求解效率的领域，具有重要意义。

1 背景知识

1.1 MapReduce模型

MapReduce是一种开源模型，适用于处理大规模数据，并对并行模型通信问题进行了很好的处理。其主要由Map函数和Reduce函数组成，其中Map函数将任务分割为多个小任务，通过相应的任务调度分配给分布在各地的计算机，再通过Reduce操作获得最终结果。其具体工作流程见文献[8]。

1.2 并行遗传算法

并行遗传算法分为主从式模型、粗粒度模型、细粒度模型等[9]。细粒度并行遗传算法是在群体中的每个个体分配一个处理单元，相互独立地采用GA执行进化，然后从进化后的个体中获得最优解。

GA的主要因素包括参数编码、初始种群设置、适应度函数、遗传操作设计和控制参数设置。其流程图如图1所示。

图1 遗传算法GA流程图

1.3 禁忌搜索算法

禁忌搜索算法TSA是由F. Glover在 1986年首次提出的，是一种全局寻优算法。从TSA过程可以看出，其主要因素包括禁忌列表、禁忌长度、候选集、藐视规则、终止规则。其中禁忌列表是影响TSA质量的主要因素之一。禁忌长度是被禁忌的解不能访问的步数。候选集由大量当前解的邻居组成。藐视规则是确保搜索过程可以释放特定的解，进而保证当所有候选解被禁忌或某一禁忌解比当前最优解要好时能够寻找到更好的全局最优解。终止规则规定算法进行一定步数后停止。TSA的流程图如图2所示。

图2 禁忌搜索算法TSA流程图

2 基于云计算的细粒度混合并行遗传算法

2.1 编码规则

传统的GA采用二进制编码的形式表述实际应用问题，但存在计算量大和精度受限的缺陷。为表述直观清晰且能克服上述缺陷，本文采用实数编码方式对最短路径求解问题进行编码，且此种方式不用解码。

采用基因表示路网节点，而染色体则表示路径。由于采用了实数编码方式，染色体会随基因变化而变化，所以做出如下规定来避免环路现象[10]：

（1）每个基因最多出现一次；

（2）染色体长度不能超过节点个数；

（3）从每个染色体O开始，D结束。

2.2 适应度函数

适应度函数是对染色体适应能力度量的函数，是对自然界中优胜劣汰原则的模仿，而适应度值体现了染色体的优劣程度。在城市路网最短路径求解问题中，路径长度最短的方法是最优解。设定义节点i与节点j之间路径长度为 L(i，j)，由某一节点m到节点 n的总路径长度可定义为：

其中N为所选路径的节点个数，π为所选路径节点的集合，l为所选路径的标签。根据最短路径求解问题，可定义适应度函数为：

由式(2)可以看出，路径长度越小，其适应度值就越大，故其最优解即为所要求的最短路径。

2.3 遗传算子

首先对个体选择策略进行阐述，个体选择对于算法的整体性能影响较大，个体选择得好，能够将优秀基因遗传下去；个体选择得不好，算法的寻优能力就会下降。本文采用种群进化常用的轮盘赌法选择优秀个体，按照适应度值计算对应的概率分布，然后将当前种群中的个体依概率复制到新的种群中，进而提高平均适应度。其概率分布的计算如下所示：

其中M为种群的大小。

遗传杂交算子方面，选择单点杂交，按照设定的概率Pc进行。同时变异方面按照设定的概率Pm进行。

2.4 藐视规则

对于被禁忌的个体，被搜索一次后其禁忌次数减去1；对于经常被搜索的个体，设定一定的数值，搜索一次加1，超过一定数值后该个体被禁忌。

2.5 方法的步骤和流程图

通过上面的描述，本文基于云计算的细粒度混合并行遗传算法求解最短路径方法的流程图如图3所示，其步骤可概括如下：

图3 云计算细粒度混合并行遗传算法流程图

(1)初始化，对每个个体分配一个处理单元，设置GA和TSA的各项参数；

(2)调用云计算平台中的MapReduce的Map函数定义每个个体的值，每个处理单元对个体进行适应度评估，并将结果存储HDFS文件；

(3)处理单元读取中间文件位置并传送给Reduce，然后 Reduce到相应位置的 DataNode上读取，完成个体的选择操作；

(4)进行交叉变异操作，同时将结果写入 HDFS文件系统；

(5)利用禁忌搜索算法TSA进行寻优，获取局部寻优更好的解；

(6)根据终止规则进行终止判定，当达到最大迭代步数或者得到某一稳定的解时算法停止，否则转至步骤(2)。

3 仿真实验与性能分析

为了验证本文所提出的基于云计算细粒度混合并行遗传算法的有效性，针对全国31个省会城市的旅行商(Traveling Salesman Problem，TSP)问题进行研究。仿真的环境为：Java语言编程，采用云计算平台的MapReduce编程模式，计算机处理器的主频为 2.80 GHz、内存为 4 GB，且采用操作系统Windows XP版本。

31个省会城市的仿真坐标为：[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556; 3238 1229;4196 1044;4312 790;4386 570;3007 1970; 2562 1756;2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578; 4029 2838;4263 2931;3429 1908;3507 2376;3394 2643;3439 3201;2935 3240;3140 3550;2545 2357; 2778 2826;2370 2975]。

初始种群设置为 20，禁忌长度取值 21，候选子集个数为200。交叉概率Pc=0.85，变异概率Pm=0.01。为了使得实验结果更加合理，进行50次仿真，取其平均值。

首先在最大迭代次数为500情况下进行仿真，对比算法分别为典型的GA算法和细粒度并行GA算法，各种算法的性能见表1。

从表1可以看出，在平均迭代次数方面，典型GA算法比细粒度并行GA算法和云计算细粒度混合并行GA算法要大，即后两者的寻优能力要优于前者，同时本文的寻优算法具有最好的寻优能力；在最大迭代次数500次的限制下，由于局部寻优能力等因素的影响，典型GA算法会有较多的次数得不到最优解，而细粒度并行GA算法的效果要好，本文所提出的云计算细粒度混合并行GA算法采用了TSA提高局部搜索能力，故每次都能得到最优解，其在收敛概率上要优于前两者；在计算时间方面，典型GA算法采用串行的方式进行寻优，其计算时间最大，而采用并行方式的GA算法，其平均耗时得到了显著提高。

其次，在最大迭代次数变化条件下对3个算法的适应度值进行分析。其他参数设置不变，最大迭代次数从100～1 000取值，步长为100。

从图4可以看出，细粒度并行遗传算法的适应度值要高于典型GA算法，而本文的云计算细粒度混合并行遗传算法的适应度值要优于前两者。

表1 各算法的性能

图4 各种算法的适应度值

以上仿真可以看出，在云计算编程模型下，采用并行计算的方式可以有效提高遗传算法的计算速度，而将遗传算法与禁忌搜索算法TSA混合，可进一步提高寻优算法的局部搜索能力，进而提高整体的寻优效率。该实验验证了本文的云计算环境下的细粒度混合并行遗传算法的有效性和正确性。

4 结束语

本文针对最短路径求解问题，采用了云计算中的MapReduce模型，同时对细粒度并行遗传算法和 TSA进行了分析，提出了一种基于云计算的细粒度混合并行遗传算法，并将其应用于分布式旅行商问题。寻优算法结合了并行遗传算法和禁忌搜索算法的优点，提高了全局和局部寻优能力，同时采用 MapReduce模型提高了编程的效率。仿真实验结果验证了方法的有效性，证明该方法是一种较好的最短路径求解方法。

[1]林闯，苏文博，孟坤，等.云计算安全：架构、机制与模型评估[J].计算机学报，2013，36(9)：1765-1784.

[2]MA P，TIAN M，YANG M.An improved genetic algorithm[C]. 2010 First International Conference on Pervasive Computing，Signal Processing and Applications，2010：977-980.

[3]焦翠珍，戴文华.基于混合并行遗传算法的多目标约束优化技术研究[J].沈阳农业大学学报，2006，37(1)：125-127.

[4]严晓明.粗粒度并行遗传算法迁移算子的一种改进[J].福建师范大学学报：自然科学版，2013，29(1)：42-47.

[5]李想，魏加华，傅旭东.粗粒度并行遗传算法在水库调度问题中的应用[J].水力发电学报，2012，31(4)：28-33.

[6]AZZOUZ A，ENNIGROU M，JLIFI B，et al.Combining tabu search and genetic algorithm in a multi-agent system for solving flexible job shop problem[C].Eleventh Mexican International Conference on Artificial Intelligence：Advances in Artificial Intelligence and Applications，2012：83-88.

[7]TONGPANG J，TANTATSANAWONG P.An application of tabu search algorithms and genetic algorithms in collaborative logistucs optimization[C].2011 Annual SRII Global Conference，2011：699-706.

[8]邬开俊，鲁怀伟.云环境下基于DPSO的任务调度算法[J].计算机工程，2014，40(1)：59-62.

[9]BRUNETTI A.A fast fine-grained genetic algorithm for spectrum fitting:An application to X-ray spectra[J].Computer Physics Communications，2013，184(2013)：573-578.

[10]杨庆芳，梅朵，郑黎黎，等.基于云计算的城市路网最短路径遗传算法求解[J].华南理工大学学报(自然科学版)，2014，42(3)：47-51，58.

Cloud computing-based hybrid parallel genetic algorithm for solving shortest path problem

Zhang Wenjin，Xu Aijun
(Education Technology Center,Guangzhou Institute of Railway Technology，Guangzhou 510430，China)

The shortest path problem plays an important role in many application research areas.In order to improve the efficiency of solving shortest path problem,a cloud computing-based hybrid parallel genetic algorithm was proposed in this paper.The MapReduce parallel programming model of Hadoop distributed computing platform in cloud computing was used to improve the coding efficiency.Based on the combination of fine grained parallel genetic algorithm and tabu search algorithm,the computing speed and search ability of the optimal algorithm were also improved,and thus the efficiency of solving shortest path problem was enhanced.The simulation results show that the computation speed and performance of the proposed algorithm were better than classical genetic algorithm and parallel genetic algorithm,and presented method is an effective shortest path solving method.

cloud computing；genetic algorithm；tabu search algorithm；shortest path

TP181

：A

：0258-7998(2015)03-0123-03

10.16157/j.issn.0258-7998.2015.03.032

2014-11-29)

张文金(1972－)，男，硕士，讲师，工程师，主要研究方向：计算机网络、智能计算。

许爱军(1978－)，男，硕士，副教授，主要研究方向：计算机网络应用、数据挖掘。