《差分演化算法求解旅行商问题》由会员分享，可在线阅读，更多相关《差分演化算法求解旅行商问题（3页珍藏版）》请在金锄头文库上搜索。
1、 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 第25卷第7期 计算机应用与软件Vol125 No. 7 2008年7月 ComputerApplications and SoftwareJul . 2008 差分演化算法求解旅行商问题 胡中波 1 熊盛武 2 1 (孝感学院数学系 湖北 孝感432100) 2 (武汉理工大学计算机科学与技术学院 湖北 武汉430070) 收稿日期: 2006 - 10 - 20。国家973重大基础研究前期研究专项 (2004CCA02500
2、) ;国家自然科学基金(60572015) ;湖北省教育厅优秀中 青年人才项目(Q200726003)。胡中波,讲师,主研领域:演化计算和统 计计算。 摘 要 设计了基于差分演化算法的新算法来求解旅行商问题。在新算法中,旅行商问题的城市的个数作为向量的维数,每个向 量的元素的大小顺序作为旅行商问题的一个可行解。实验表明,该算法能够成功求解小规模的旅行商问题,而且算法稳健性好;再 与同类算法的优化结果相比较,表明了该算法计算量小、 收敛速度快的优点。 关键词 差分演化算法 旅行商问题 组合优化 D IFFERENTIAL EVOLUTI ON ALGORITHM FOR TRAVELL ING
3、SALESMAN PROBLEM S Hu Zhongbo 1 Xiong Shengwu 2 1 (Department of M athematics, Xiaogan University, Xiaogan 432100, Hubei, China) 2 (School of Computer Science and Technology,Wuhan University of Technology,W uhan 430070, Hubei, China) AbstractA new strategy based on differential evolution algorithm i
4、s designed to solve travelling sales man problems(TSP).In the strate2 gy, the number of TSPs cities is the dimension of vectors, and the precedence order of all the members of each vector is a feasible solution of the problems . The experimental results show that the robust strategy can succeed in s
5、olving s mall2scale travelling sales man problems . Com2 pared with particle s warm optimization algorithm and ant algorithms, the proposed method is of s maller computation complexity and faster con2 vergence speed. KeywordsDifferential evolution algorithmTravelling sales man problemCombinational o
6、ptimization 0 引 言 差分演化算法DE ( differential evolution algorithm)是由R. Storn和K .Price于1995年提出来的一类演化算法 1, 2。其基 本思想是应用当时种群中个体的差来重组得到中间种群,然后 通过父子之间的锦标赛制的竞争获得新一代种群。目前,该算 法已经在多峰函数优化、 数据滤波等众多大方向上得到了较好 的仿真结果。 这些成功的仿真结果主要集中在连续优化领域,在离散优 化领域的研究和应用相对较少,而应用DE算法求解NP难题更 是一个新的研究方向。旅行商问题TSP( traveling sales man prob2 l
7、em) 又是著名的NP难题,因此,尝试用DE算法来求解TSP问 题。试验结果表明,设计的基于DE算法的新策略是求解小规 模TSP问题的有效方案;且与同类的微粒群算法优化TSP问题 的结果相比较,该算法还显示出计算量小、 稳健性强等优点。 1 旅行商问题简介 TSP问题 3是组合优化中的 NP难题,常被用来验证智能 启发式算法的有效性。TSP问题可以简单的描述为:给定n个 城市及两两城市之间的距离,求一条经过各城市一次且仅一次 的最短回路。建立数学模型如下: 已知图G = (V, A),其中V为顶点集,A为边集,并已知各 边的长度,要求确定一条长度最短的Hamilton回路。设dij为城 市i与
8、城市j之间的距离,即边( i, j)的长度。引入决策变量 xij: xij= 1若访问城市i后访问城市j 0否则 则TSP的目标函数为: min n i, j=1 xijdij。 2 求解旅行商问题的差分演化算法 DE算法是一种实数编码的演化算法,算法的基本思想及整 体构架与遗传算法相类似,从一代种群到下一代种群都要经过 变异、 交叉、 选择等操作,有三个经验参数,分别是种群规模N (一般设置为向量维数的5到10倍)、 变异因子F、 交叉概率 CR,其中F和CR的取值范围被建议在(0,1内。发展至今, DE算法已经有了很多不同的版本,较有影响力的有三个版 本 1,2 ,它们的主要区别是变异操作
9、的公式不同。鉴于文献2 所示的版本兼顾了算法的收敛速度和稳健性,本文将以该版本 为基础设计求解TSP问题的方案。 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 258 计算机应用与软件2008年 在新方案中,把TSP问题的城市的个数作为向量的维数, 每个向量的元素的大小顺序作为旅行商问题一个可行解,再计 算这条路径的长度作为该个体(向量)的适应值。 另外,与函数优化问题不同的是,向量每一维的元素的上界 high和下界low没有已知,必须自己设置。 从而无形中增加了两 个参量,
10、但幸运的是实验结果表明,解的好坏和收敛的稳定性对 于这两个参数的变化都不敏感。 求解TSP问题的差分演化算法步骤如下(不同于原DE算 法的步骤加了下划线 ) : Step1 给变异因子F、 交叉概率CR和最大迭代次数MaxGens赋初值; Step2 设置种群中向量每一维元素的上界high和下界low; Step3 初始化种群X1 (N D) ,其中,种群中向量的每一维的元 素在low和high之间随机取值,设置迭代次数g =1 ; Step4 当g =MaxGens,输出适应值最大(即路径最短)的个体中元 素排序后的序号(就是求得的最短路径 ) , 终止程序。否则,继续; Step5 对X1
11、中的每个向量 ?xi执行如下操作: (1)把向量 ?xi的D个元素从小到大排序,并把大小顺序作为问题的 一个可行解,求出相应的路径长度作为 ?xi的适应值。 (2)在X1中随机的选取一个适应值不小于 ?xi的适应值的个体 ?xr3; (3)在0,N- 1的整数中随机的选取两个不等于i和r3的数r1、r2; (4)随机的产生一个不小于0,且不大于D -1的整数Z; (5)对 ?xi的每一维j执行如下操作: a.产生一个0,1上服从均匀分布的随机数r; b.如果r = CR或者j = = Z,则: vij= xr3 j+ xij 2 + F xr3 j- xij+ xr1, j- xr2, j 否
12、则,vij= xij; (6)让 ?xi与 ?vi竞争,把胜出的个体赋予 ?xi; Step6 当搜索到了已知的最短路径时,退出循环,输出结果,终止 程序;否则,继续。(注:在求解一些已知了最短路径的标准TSP问题时 加上此步;否则,删去。) Step7g +,返回Step4。 3 数值实验 为了验证算法的有效性,用该方案分别优化了14个和10 个城市的标准TSP问题 46 ,并把计算的结果与文献 5 提出 的微粒群算法优化TSP问题及文献6 提出的蚁群搜索算法的 计算结果相比较。 (1) 14点的TSP标准问题如表 1所示。 表114点TSP问题 点xiyi点xiyi 116. 4796.
13、10216. 4794. 44 320. 0992. 54422. 3993. 37 525. 2397. 24622. 0096. 05 720. 4797. 02817. 2096. 29 916. 3097. 381014. 0598. 12 1116. 5397. 381221. 5295. 59 1319. 4197. 131420. 0994. 55 算法实现时,参数设计如下: high =500. 0, low = - 500. 0,N =120 ,D =14 ,F =0.6 ,CR =0.2。实现环境:AMD2200 + , 1. 5GHz, 256MB,VC +6. 0。 在
14、上述参数设置下,连续运行10次,每次都能较快的搜索 到最短路径。表征算法性能的各项相关指标如表2所示。 表2 算法性能分析指标 解空间规模(14 - 1) !/2 =3113510400 最少| |最多| |平均迭代次数974 | | 3714 | | 2351. 6 平均搜索到的个体总数2351. 6120 = 282192 平均搜索到的个体总数 /解空间规模 282192 / 3113510400 = 0. 00906% 最短| |最长| |平均时耗(秒)1. 125 | | 4. 062 | | 2. 5968 最优路径 43142110911 813712654 最短距离30. 878
15、504 (等于已知的最好结果) (2) 10点的TSP标准问题如表 3所示。 表310点TSP问题 点xiyi点xiyi 10. 40000. 443920. 24390. 1463 30. 17070. 229340. 22930. 7610 50. 51710. 941460. 87320. 6536 70. 68780. 521980. 84880. 3609 90. 66830. 2536100. 61590. 2623 算法实现时,参数设计如下: high =500. 0, low = - 500. 0,N =80 ,D =10 ,F =0.6 ,CR =0.2。实现环境与上相同。
16、在上述参数设置下,连续运行10次,每次都能较快的搜索 到最短路径。表征算法性能的各项相关指标如表4所示。 表4 算法性能分析指标 解空间规模(10 - 1) !/2 =188440 最少| |最多| |平均迭代次数24 | | 62 | | 41. 9 平均搜索到的个体总数41. 980 = 3352 平均搜索到的个体总数 /解空间规模 3352 /188440 =1. 78% 最短| |最长| |平均时耗(秒)0. 015 | | 0. 031| | 0. 021 最优路径 413210 987654 最短距离2. 690249(等于已知的最好结果) 从试验结果可见,本算法具有如下的几个优点: 1) 算法的收敛速度快,耗时短。文献6 用蚁群算法优化 10个城 市TSP问 题 耗 时013秒(实 验 环境: P4, 115GHz, 256MB) ,而本算法的最长时耗才01031秒,平均时耗只有01021 秒。可见在同等实验环境下,本算法的时耗只是蚁群算法的 0107倍。 2) 算法稳健性好。对于试验的两个TSP问题连续运行10 次无一次失败
