资源描述：
《旅行商问题的改进粒子群算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、旅行商问题的改进粒子群算法第27卷2007年12月计算机应用ComputerApplicationsVol,27Dec.2007文章编号:1001—9081(2007)s2—0185—03旅行商问题的改进粒子群算法刘勤明.吕文元(上海理工大学管理学院,上海200093)(1qm0531@163.tom)摘要:旅行商问题是组合优化中最典型的困难问题之一,为解决这个问题,采用粒子群算法,取得了良好的效果.进一步在传统的基础上引入了记忆机制,并进行改进,从而加快了算法的收敛速度,提高了解的精度.最后通过两个实例说明了该算法的有效性,同时也说明
2、了用该算法来分析和求解旅行商问题的可行性.关键词:旅行商问题;粒子群算法;记忆机制中图分类号:TP301.6文献标志码:A0引言旅行商问题(TravelingSalesmanProblem,TSP),亦称邮递员路径问题,是典型的组合优化问题.也就是有一个售货员从城市Ⅳ0出发,遍访城市Ⅳ,,v2,…Ⅳ各一次,最后返回Ⅳ0的过程.可以分为如下两类…:1)对称旅行商问题(d=,Vi,,=1,2,…,n);2)非对称旅行商问题(d≠比,ji√=1,2,…,n).TSP问题在实际应用具有典型意义,比如可以用于车辆调度,分配问题和网络问题等,因而自
3、从该问题被提出以来,一直被各个领域的研究人员所关注,从计算复杂性理论来看,TSP一直是组合优化中极富活力的研究课题之一,也是个NP完全问题,是否存在多项式时间有效算法尚不可知.该问题的求解方法主要是启发式算法,如贪心算法,遗传算法及模拟退火算法,蚂蚁算法等.lTSP数学规划在研究TSP时应该综合考虑多种因素,而且涉及到的变量比较多,在这里采用0—1整数规划进行建模].(i=0,1,…n,=0,1…,n,r=1,2…,n+1,i≠J.)表示i一段路线作为某巡回路线中第r段行程的决策变量,当=1时,表示该段行程在巡回路线上,当=0时,表示该
4、段行程不在巡回路线上.其中i表示每段线路的起点,表示每段线路的终点,r表示每段线路.所以这个问题的数学模型为:n4-lnnminF=∑∑∑C(1)…1i0J=0f∑=∑.fi=0k^=0s.t.{(2)l∑∑=1一l,00*=0,1其中:r=1,2,…,n;=1,2,…,n;i=1,2,…,n.假设C为各点之间的最短距离(假定各点之间均有直达路线),约束条件(1)说明以J为起点的路段如果作为巡回路段中的r+z段行程而存在,那么必有以为终点的路段作为r段行程存在于巡回路线中,从而保证了各路段依次衔接而不间断.约束条件(2)说明以i为起点的
5、路段在巡回路线中必须而且只能出现一次,从而保证了离开点i只能到另外一个点,,而不重复走相同的路段.2TSP与粒子群算法2,1基本粒子群算法粒子群算法'采用群体进化适应度函数来评价优化结果,算法中的每个粒子都有一个适应度函数所决定的适应值,都具有位置和速度两个属性,分别用来表示当前粒子在解空间中的位置和移动速度,且以粒子位置坐标所对应的适应度函数值来确定粒子的好坏,在每一次迭代中粒子通过跟踪粒子本身的最优解(t)和整个群体到目前找到的最优解P(t)来更新自己,并且每个粒子的飞行速度根据粒子本身的历史经验以及同伴的历史经验来进行动态调整,用
6、式(3)和(4)来更新速度和位置:(t+1)=×(t)+Cl×rand()×[p二6(t)一P(t)]+C2×rand()×[P(t)一P(t)](3)P'(t+1)=P(t)+(t+1)(4)其中:.(t)为第i个粒子在第t次迭代的速度向量,P(t)为第i个粒子在第t次迭代的位置,C.和C为学习因子,取(0,2)之间的随机数,rand()为在[0,1]范围内变化的随机函数,为惯性权重,用来控制粒子的搜索能力,当取值较大时,粒子具有较好的全局搜索能力,取值较小时,具有较强的局部搜索能力,并且每个粒子的每一维速度都被限制在一个最大速度一.
7、和一个最小速度.d之间,当.>～.d时,=d,当<d时,,d=…-d,每个粒子的每一维位置也都被限制在一个最大位置p～.和最小位置p之间.2.2改进的粒子群算法虽然粒子群算法可以用来求解大量非线性,不可微等复杂优化问题,需要调整的参数也少,但是该算法在收敛过程中也容易存在早熟收敛现象,因此在本文中引入了进化速度因子和聚集度因子来增强粒子的搜索能力,由文献[7]可得:收稿日期:2007—07—04;修回日期:2007—10—08.作者简介:刘勤明(1984一),男,山东日照人,硕士研究生,主要研究方向:工业工程,设备管理;吕文
8、元(1970一),男,浙江人,副教授,博士,主要研究方向:工业工程,设备管理.186计算机应用2007盘h=min[F(p(t一1)),F(p(t))/maxF(p(t一1)),F(Ps(t))](5)h为
