一种求解TSP问题的并行遗传算法
第22卷 第2期
文章编号:1006-9348(2005) 02-0082-04
计 算 机 仿 真
2005年2月
一种求解TSP 问题的并行遗传算法
侯建花, 杨长青
(成都理工大学, 四川成都610059)
摘要:遗传算法(G A ) 是一种基于自然群体遗传机制的有效搜索算法, 由于它在搜索空间中同时考虑许多点, 这样就减少了收敛于局部极小的可能, 也增加了处理的并行性。因此可以利用并行遗传算法(PG A ) 研究典型的组合优化实例-TSP 问题的求解问题。该文提出一种有效的并行算法求解旅行商(TSP ) 问题, 实验结果表明, 该方法在解的精度上优于以前的算法。关键词:并行遗传算法; 旅行商问题; 收敛性; 组合优化中图分类号:O224 文献标识码:A
A P arallel G enetic Algorithm for Solving Traveling HOU Jian -hua , Y (Chengdu University of T , )
ABSTRACT :G enetic Alg orithm (G A ) is effective on genetic mechanism of natural colony , consulting simultaneously , A can reduce the possibility of converging on local minimum and enhance the , parallel genetic alg orithm (PG A ) can be used in studying the s olution of —TSP problem. In this paper , we introduce the principles of PG A and make to TSP. The results of experiments show that the new parallel genetic alg orithm is practical and efficient. KE :genetic alg orithm ;T raveling salesman problem ;C onvergence ;C ombinatorial optimization
1 引言
遗传算法是一种模拟自然界生物进化的搜索算法, 由于它的简单易行、鲁棒性强, 尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程, 从而使它的应用范围极为广泛, 并且已在众多领域得到了实际应用, 取得了令人瞩目的成果, 引起了广大学者和工程人员的关注。
旅行商问题(T raveling Salesman Problem , TSP ) 是一个典型的、易于描述却难于处理的NP 完全问题, 是许多领域内出现的多种复杂问题的集中概括和简化形式。对于TSP 问题, 没有确定的算法能够在多项式时间内得到问题的解。目前针对这一问题已有许多种解法, 如穷举搜索法、贪心法、动态规划法、分支界定法等。这些方法都存在着一个共同问题, 就是当城市数目N 较大时, 会产生所谓的“组合爆炸”问题。因此, 有效地解决TSP 问题, 在可计算理论上具有重要的理论意义, 同时也具有重要的实际应用价值。
近十几年来, 模拟自然进化的过程用以求解TSP 问题的研究十分活跃, 这方面的工作有基于遗传算法的研究, 有基于进化规划的研究, 其中以前者居多。TSP 问题因其典型已成为许多启发式的搜索、优化算法的间接比较标准。遗传算
收稿日期:2003-07-21
法就其本质来说, 主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。遗传算法在TSP 问题求解方面的应用研究, 对于构造适当的遗传算法框架, 建立有效的遗传操作, 以及有效地解决TSP 问题等具有多方面的重要意义。
2 遗传算法简介
传统的优化搜索算法通常采用梯度技术, 使搜索朝着梯度下降最快的方向进行。但是对于多峰优化等问题
, 通常只
能得到极值, 而不能求得全局最优解。遗传算法(G A ) 是J.
H olland 教授等人通过模拟自然进化规律, 提出的一种与传统
优化不同的优化搜索算法。该算法是从一个种群开始, 利用选择、交叉、变异等遗传算子对种群进行不断优化, 最后得到全局最优解。理论已证明:对于每代中保留当代最优解的
G A 是收敛的算法, 即随着G A 中遗传代数不断增加, 目前保
留的最好解将逐渐接近全局最优解。从二十世纪八十年代开始,G A 开始成为应用领域的一个热门话题, G A 的应用涉及到控制、规划、设计、组合优化、图像处理、信号处理、机器人、人工生命等诸多领域。
G A 通常包括五个基本因素:参数编码、初始群体的设
定、适应度函数的设计、遗传操作设计、控制参数设定。在实际应用中主要从五个基本因素考虑G A 的设计。
—82—
同时G A 也存在不足, 如G A 的搜索效率通常比传统的优化搜索算法低, 一般采用如下几种方法提高搜索效率:
1) 与其它搜索方法相结合。例如可以与局部搜索方法
程;
3) 当主进程收到比它的最短路径值更小的值时, 把它发
送给所有子进程, 若主进程调用广播函数, 则子进程必须停下来等待接收最短路径的消息。为了让子进程不用等待一个可能不出现的最新消息, 这里应用MPI 的非阻塞通讯, 让通讯与计算重叠。
主进程使用通配符可接收任何子进程的消息; 消息标志:
1) 当W ORK T AG 及w ork . len 为负数时, 表示该子进程空
相结合, 也可以与模拟退火方法结合。
2) 优化G A 的五个基本因素。3) 采用并行遗传算法(PG A ) 。
由于G A 是从群体出发,G A 在本质上具有很好的并行处理特性, 特别是G A 中各个体适应值的计算可独立进行而彼此之间无需任何通信, 所以并行效率很高。PG A 正成为G A 的一个重要研究方向。
闲。
2) 当W ORK T AG 及w ork . len 为正数时, 表示该子进程有
3 并行求解TSP 算法
我们用松弛算法, 找出问题的所有解。每个城市都编上号, 代表相应城市, 主进程把城市编号分配给子进程计算, 余下的城市以先来先服务原则, 分配给空闲的子进程计算。各子进程并行计算, 并把当前最短的解发送给主进程。当所有城市完成计算后, 主进程显示所有最短路径的解, 主进程和子进程结束。
旅行商问题是一个组合查找问题, 子进程从指定的城市出发, 从不同的城市出发最后返回到原处, 合。每种组合, 都要计算一次。
为0。:
1) , 把当前城市与它的距离累加
一个解。
子进程接收的消息当标志:
1) 为W ORK T AG 及w ork . len 为正数时, 表示有一个工
作。为主进程当前最短路径值。
2) 为W 及w ork. len , , 子
。
3) 。
MPI 的并行解
1 1) 主进程向各子进程分配一个城市编号, 更新发送工作
件数。
F or (rank =1; rank
到总路径值中。若该城市为组合中最后的城市, 则把它与首个出发城市的距离累加到总路径值中。
2) 在每次累加后, 比较总路径值与它的最短路径值。
∶
w ork . thiscity =rank ; MPI Send (&w ork , 1,w ork C OM M W OR LD ) ;
type , rank , W ORK T AG, MPI
计算这个组合的约束条件有:
1) 当总路径值比最短路径值大, 表示这个组合不是一个
/3新工作, 子进程, 工作信号, 通讯子3/
++Sendctn/3记录分配了工作件数3/++lastcity /3记录当前城市编号3/}}
2) 主进程等待接收子进程的消息, 消息标志使用通配
解。
2) 当经过所有城市后返回原处, 表示这个组合是一个
解。子进程会:
①更新它的最短路径值;
②向主进程发送这个组合的路径值及经过城市的次序。主进程也有变量最短路径值, 表示当前最优的最短路值。当收到一个解时, 主进程会把这个解的路径值和它的最短路径值比较。若这个解的路径值比较短, 表示找到一个更优的解, 主进程会:
1) 更新它的最短路径值;
2) 发送最新的最短路径值给所有子进程; 3) 记录这个解的路径值及经过城市的次序。
符, 表示接收任何子进程的消息; 发出消息的子进程序号从
status . MPI S OURCE 取得。
MPI Recv (&w ork ,1,w ork type , /3工作结束3/
MPI ANY S OURCE , /3任何子进程3/MPI ANY T AG, /3任何标志3/MPI C OM
M W OR LD , /3通讯子3/&status ) ; /3返回状态3/
在整个计算过程中, 主进程和子进程的最短路径值有一个同步问题:
1) 主进程向子进程分配工作时, 向子进程发送它的最短
消息有两种:
①当w ork. len 大于0时, 表示已经找出一个的解。主进程把解的路径值与它的最短路径值比较, 若解的路径值比较大, 重复二) ; 否则, 主进程会更新它的最短路径值; 并把这个值通知所有子进程。
路径值;
2) 子进程若找到更短的路径值时, 就将它发送给主进
—83—
M inpath =w ork. len ;
F or (rank =1;rank
MPI C OM M W OR LD , /3通讯子3/ &update req ) ; /3更新请求3/
/3执行接收请求3/MPI S tart (&update req ) ;
3) 子进程提交接收请求及等待接收主进程的标志为W ORK T AG 的消息。
/3提交接收请求3/MPI S tart (&search req ) ; MPI Wait (&search req , &status ) ;
MPI Send (&minpath ,1,MPI I NT , /3最短路径3/ Rank , /3发送给子进程3/ UPDT AG, /3更新标志3/
MPI C OM M W OR LD ) ; /3通讯子3/及记录这个解的路径值及经过城市的次序, 重复二) 。
②当w ork. len 为负数时, 表示子进程空闲, 发送工作件数减一。
3) 主进程结束条件。若lastcity 大于N 及发送工作件数
收到消息后, 有两种情况:
①当w ork. len 为负数时, 表示结束信号, 子进程便结束。
I f (w ork. len ==ST OPT AG )
为0, 表示完成所有城市查检, 主进程显示所有与它的最短路径相同的解, 并在结束前, 以结束信号通知各子进程结束。
W ork . len =ST OP ; /3ST OP 为负整数3/F or (rank =1;rank
MPI Send (&w ork ,1,w ork type , /3工作3/Rank , /3子进程3/W ORK T AG, /3结束信号3/
MPI C OM M W OR LD ) ; /3通信子*/}
4) 若lastcity 大于N 及发送工作件数大于0, Break ;
②当w ork. len 为正数时, 表示有新工作。子进程把它的最短路径值设为w ork. len 。
4) , 并计算所
, , 到, :
, 累加到变量总路径, 这个组合的计算便结束, 并开始另一个组合的计算; 否则, 在成功完成这个组合计算之后, 子进程把这个解发送给主进程。
MPI Send (&w ork ,1,w ork type , /3工作结束3/
作在处理中。重复
5) 加一。) I f (lastcity N W ork . =;
MPI Send (&w ork ,1,w ork type , /3新工作3/ S tatus ,MPI S OURCE , /3空闲子进程3/ W ORK T AG, /3工作标志3/
MPI C OM M W OR LD ) ; /3通讯子3/ ++sendctn ; ++lastcity ;
}
4. 2 子进程的工作流程
1) 子进程用持久等待接收主进程的标志为W ORK T AG
0, /3发送给主进程3/ W ORK T AG, /3工作标志3/ MPI C OM M W OR LD ) /3通讯子3/
②调用MPI T est 来检测是否有新的最短路径值消息。若flag 为1, 表示接收到新消息, 每次完成最短路径的处理后, 要再提交接收请求。
MPI T est (&update req , &flag ,MPI ST AT US I ONORE ) ; I f (flag =1) {
/3接收最短路径值的处理3/
∶
/3提交接收请求3/MPI S tart (&update req ) ; }
的消息, 建立持久通讯请求。/3建立持久通讯请求3/
MPI Recv init (&w ork ,1,w orktype , /3新工作3/
0, /3从主进程接收3/W ORK T AG, /3工作标志3/MPI C OM M W OR LD , /3通讯子3/&search req ) ; /3搜索请求3/
2) 子进程用持久等待接收主进程标志为UPDT AG 的消
∶
5) 完成计算整个组合后, 子进程向主进程发送信号, 重
复四) 。
W ork . action =I D LE /3I D LE 为负整数3/MPI Send (&w ork ,1,w ork type , /3工作结果3/
息, 建立并提交持久通讯请求。
/3建立保持通讯请求*/MPI Recv init (&minpath ,1,MPI
I NT , /3最短路径值
0, /3发送给主进程3/ W ORK T AG, /3工作标志3/ MPI C OM M W OR LD ) /3通讯子3/
3/
0, /3从主进程接收3/ UPDT AG, /3更新标志3/
5 实验结果
—8
4—
为了便于比较和分析, 我们选择了文献[1]中城市数目分别为30、50和75的三个TSP 问题进行了实验, 优化后的最佳路径长度如表1所示。表1还列出了D. T. Whitley 采用遗传算法得到的最佳结果[4],D. B. F ogel 采用进化规划方法得到的最佳结果[5]。从表1中的对比结果可知, 对于30城市的TSP 问题, 本算法找到了由O. liver 等人(1987) 确认的最佳路径[7], 对于75城市TSP 问题, 本算法找到了新的比表1中其它结果更好的路径。
表1 三个TSP 问题的优化结果
城市数文献[4]的优化结果文献[5]的优化结果本文的优化结果
30
423. 7406423. 7406423. 7406
50430427. 855427. 5168
75553549. 180540. 6718
参考文献:
[1] 陈国良, 等. 遗传算法及其应用[M].北京:人民邮电出版社,
1996.
[2] 周明, 孙树栋. 遗传算法原理及应用[M].北京:国防工业出版
社,1997.
[3] 李晓梅, 莫则尧. 面向结构的并行算法-设计与分析[M].长沙:
国防科技大学出版社,1996.
[4] D Whitley etal. Scheduling problems and traveling salesman :the ge 2
netic edge recombination operator[C].proc. of 3rd Int. con f on genetic Alg orithms , 1989. 133-140.
[5] D B F ogel. Applying ev olutionary programm ing to selected traveling
salesman problems[J].Cybem tics and systems ,1993
, (24) :27-36. [6] L Olive , D J Msm ith &J R C H olland. A study of permutation
Cross over operators on the traveling salesman problem[C].G enetic Al 2g orithm and their application :Proceedings of the Second International C on ference on G enetic Alg orithms. 1987. 350.
6 结论
实验结果表明, 本文提出的算法提高了的全局和局部搜索能力, 并改善了未成熟收敛缺陷。今后任务是更加深入地研究并行算法, 改善算法的性能, 使算法速度有所提高。
(-) () , 山西太原市人, 在读硕
, :网络并行计算;
(1973-) , 男(汉族
) , 山西太原市人, 在读硕
士, 主要研究方向:数值计算。
(上接第81[4] 韩军, 熊璋, 孙文彦1自动分割及跟踪视频运动对象的一种实
、分类统计提供了基础。
现方法[J]1中国图象图形学报,2001-6(A ) :7321
[5] Y aakov Bar -Shalom , X R ong Li , Thiagalingam K irubarajan Estima 2
tion with Applications to T racking and Navigation :Theory Alg orithms and S oftware[M]1John W iley &Sons , Inc 1IS BNs :0-471-41655-X (Hardback ) -471-22127-9(E lectronic ) , C opyright 20011[6] D Y oshida , K T erada , S Oe and J Y amaguchi 1A method of counting
the passing people by using the stereo images[C]1in Proc 1IEEE Int 1C on f 1on Image Processing , 19991338-3421
[作者简介]
李 曦(1977110-) , 男(汉族) , 湖北人, 现为上海交
通大学电信学院自控系博士研究生, 研究方向为燃料电池等非线性系统的建模与智能控制;
曹广益(1941110-) , 男(汉族) , 上海人, 上海交通大
图2 该组动态图像多目标质心位置图
学电信学院自控系教授、博士生导师, 研究方向为燃
料电池、机器人等非线性系统的建模与控制。
参考文献:
[1] 李智勇, 沈振康, 杨卫平1动态图象分析[M]1北京:国防工业
朱新坚(195814-) , 男(汉族) , 上海人, 上海交通大学电信学院自控
系教授、博士生导师, 国家863后续能源专家组成员。研究方向为燃料电池、机器人等非线性系统的建模与控制;
出版社,1999年
[2] 徐毓, 金以慧1基于聚类融合的多目标跟踪算法[J]1传感器技
付晓薇(197714-) 女(汉族) , 湖北人, 武汉科技大学计算机学院, 助
教。研究方向为模式识别与智能控制。
术,2002, 21(7) :311
[3] 刘亚, 艾海舟1一种基于背景模型的运动目标检测与跟踪算法
[J]1信息与控制,2002,31(4) 1
—85—