论文研究-求解TSP 问题的离散粒子群优化算法.pdf

所需积分/C币:5 2019-09-20 22:51:20 335KB .PDF
收藏 收藏
举报

论文研究-求解TSP 问题的离散粒子群优化算法.pdf,
90 系统工程理论与实践 2006年6月 粒子的移动:位置与速度相加得到个新位置 如果对上述对象(或运算)作了定乂,则可以根据PS算法的基本思想构建υSO算法去求解离散优 化问题作为一个具体例子,erc针对TSP间题实现了一个具体的DPSO算法,它把位置定义为N个城 市的排列,而定乂速度为交换的列表,每个交换表示交换排列中的两个城市,在此基础上,对其它量及运算 法则进行了定义,由于缺少对离散量与连续量运算规律不同的考虑,仿真结果与其它算法相比仍有较人的 差距.但其算法已经表现出了很强的计化特征,展示了PSO在求解离散优化问题时的一个可行的方向 3离散粒子群优化算法 与PS∞算法类似,D門SO算法的关键就是要根据间题领域定义粒子的位置和速度的表示,同时,根据 离散量的特点,定义这些量的运算规律和粒子的运动方程,下面对求解ISP问题的DPSO算法的基本量及 其运算法则进行挂述 3.1粒子的位置 与文献/87不同,粒子的位置X用一个由边组成的表来表示,它是一个N维向量,在X中,维表示边 的起始城市的编号.每一维的数椐表示相应边的终点城市的编号,同时它还作为指针与维一起构成一个循 环单链表,表示了一次周游的路径,可以用公式()来表示粒子的位置X .t1, d x ),1≤i≤N,1 式中N是城市数,对第冫维的数据x;,表示了条边(i,x),即在访问完城市i后将访问城市x,而访问完 x;后将访问城市x,依此类推,整个访问序列构成了一个循环单链表 3.2粒子的速度 速度V的作用是改变粒子的位置,与粒子的位置ⅹ的定义类似速度V是一个N维向量,表示为 V=(w,2,…,v,…,w),1≤i≤N,0 N 14) 式中N是城市数.同样,速度V的维表示边的起始城市,但是每一维上的数据有二种含义:如果v等于0 表示空操作,即如果用该速度作用某一个位置,它将不影响位置上相应维的数据:而如果不等于0.表示把 此位置的相应维上的数据修改为,而山于修改后的位置必须是一条有效的周游路径,所以它不可能仅是 简单的替换操作,必然还会影响位置上其它维的数据 3.3位置与速度的加法运算 位置与速度的加法运算实现了粒子位置的移动,使粒子进入了一个新的位置,表示为 X=X+V 新位置的每一维数据的产生依次由公式(6)确定 if Oor v = x Prev(u)y, 式中pe(以是ⅹ路径中城市η的前趋城市,公式(6)说明,如果速度等于0,或者等于位置上相应维的数 据,则速度是一个空操作,否则,它将影响位置的三个维上的数据,相当于单链表上的一个结点插入到一个 新的位置,并对结点的值进行相应的修改.图1描述了速度对位置的作用过程,图中实线是作用前的路径, 虚线是作用后的路径. 34位置的减法 prev(以 两个位置X2和X1相减的结果是一个速度V,表示为公式 它表示如果把V作用在Ⅺ1上将得到位置X2,它可以通过下述过 程来计算:比较Ⅺ1和ⅹ在每一维i上的值,如果相同,则使v等 于0,如果不同,则使v等于x2,,即V中的任意一个元素可表示 图1速度的操作示意图 C1994-2009ChinaAcademicjOurnalElectronicPublishingHouse.alLrightsreservedhttp://www.cnki.net 第6期 求解TSP问题的离散粒子群优化算法 为 35速度的数乘 速度的数乘具有概率意义,它可以表示为: c. V 式中c是一个常数,它具有概率的意义,在实际计算V2时,对V1中的每一维的速度v.,生成一个0到1 之间的随机数mnd,如果rund小于c,则使v2等于v,,否则,n,笔于0,即V2中的任意一个元素可表示 为 if rand< 10) 0 3.6速度的加法 两个速度相加,得到的新速度表示为 其中每一个速度分量w定义为 0 根据上面的定义,一般V1+V2V2+V1,即不满足交换律,只有当V1-V2,才有V1+V2-V2+V1 3.7粒子的运动方程 由于离散量运算的特殊性,对粒子的运动方程作了修改,取消了原有的惯性项,即公式(1中右边的第 一项,因为速度的定义使位置的运动是一步到位的,所以它已经意义不大,粒子的运动方程具体描述如下 13) X=X+V 14) 由于惯性的主要作用是产生扰动.维持粒子群的多样性.没有它的作用.DPSO算法将迅速陷入早熟 为解决这一问题,本文后面定义了排斥算子来维持粒子群的多样性,使算沄在迭代的后期能依然保持进化 能力 4优化算子 PSO算法应用于优化问题求解,可以看作是一种随机化搜索过程,在该搜索过程中,PSO不仅要尽量 保证探索解空间的全局性( exploration),而且应当充分利用已经获得的解空间信息逼近当前局部最优解 ( exploitation),在使用PSO算法的过程中发现,尽管PO具有通用性的一面,但却忽视了问题特征信息的辅 助作用,使得算法的局部求精能力不强;PO的另一个引起广泛关注的问题是早熟牧敛,硏究表明,早熟收 敛总是与粒子群中粒子趋同、粒子样多样性的迅速下降有密切关系.同样,DPSO算法也存在类似的问题, 为了使DPSO算法在空间探索和局部求精间取得更好的平衡,本文定义了排斥算子来保持粒子群的多样 性,使用个体学习算子来提高局部求精能力 41基本概念 1)粒子位置相似性s,:是指任意两个位置X和ⅹ的相似程序,定义为: 15) N 式中N是位置的维数如果s,等于1,则两者完全相同.如果等于0.则完全不同,也就是说s;,∈/0,17 2)粒子个体多样性d:是指粒子X和其历史最佳及全局最佳间的相似程度,定义为 L i, pbes spbest, gbest 16) 201994-2009ChinaAcademicJournalElectronicpUblishingHouse.Allrightsreservedhttp:/www.cnki.net 92 系统工程理论与实践 2006年6月 如果d1=0,则三者完全相同.如果d=1,则三者两两完全不同,也就是说dh∈/0,1 3)粒孑群微观多样性爾:粒子群微观多样性是指个体多样性的平均值 S 17) 式中Sze是粒子群的大小.在后面的仿真实验中将使用珻来描述粒子群的多样性 4.2排斥算子 当粒子的个体多样性下降到一定程度后,个体的进化能力就受到了很大的限制,只有在其它粒子找到 新的全局最佳位置后粒子才恢复进化能力所以,在个体多样性下降到一定程度后,必须有相应的算子去 增加其多样性,以保持个体的进化能力,为此,定义一个排斥算子( repulsion operator),对位置中的每一维数 据,如果它与历史最佳值(或全局最佳值相同,则以一定的概率为其随机生成一个新的速度,再按公式f6) 把此速度作用到位置上 4.3学习算子 对TP问题,在最佳路径里必然包括而且在很大程度上包括了相邻城市间距离最短(或者较短)的边 所以,可以用一个n×m矩阵K米行储各个城市的近邻城市排序表,里面的每一个元素k,的值表示对城 市i而言,第j近的城市是k,,即最近的城市是k1,次近的城市是k,2,依此类推,K作为问题域的公共知 识库能被所有的粒子所感知. 在公共知识库K的基础上,定义了一个学习算子 (learning operator,粒子学习时,对每一个城市(位置 上的每一维)如果它接下大要访问城市(位置上相应维的偵)不是最近城市,则以此最近城市为速度,作用 到此粒子上(操作如图1,看能不能减小路径长度,如果能,则粒子进入新的位置,对所有维重复这个过 程因为不可能在所有的城市岀发时都能访问其最近邻城市.所以也可以考虑每个城市的次近城市等等 定义学习宽度( width这个参数来控制在学习过程中所考虑的城市数,如果wdh=1,则只考虑每个城市 的最近城市,如果 width=2,则除考虑最近城市外,还需考虑次近城市,依此类推. 5仿真实验及结果 为了检验DPSO算法的性能,从通用TSPB中选用典型的 Benchmark问题进行了仿真实验,对称 ISP选用的是ei51问题,最佳值是426,而非对称TP选用的是r48,最佳值是1442.)别对排斥算子的作 用和算法的总体性能进行了仿真实验 排斥算子的作用 为了观察排斥算」对粒」样多样性的作用效果,比较∫不带排斥算」与带排斥算子的情况下粒」群 徵观多样性的变化情况,仿真中c和的值分别设为0.2和0.3,在个体多样性低于0.2时启用排斥算 子图2是在cil51问题上的仿真结果,图3是在ry48问题上的仿真结果,从图中可以看出,如果不使用排 斥算子,则粒子群很快趋同,失去了进化能力,排斥算子能有效地维持粒子群的多样性,具体数值可通过启 用时机和排斥概率来设定,于有效地避免了早熟收敛,仿真发现,使用排斥算子后的结果也更好. 0.5 0.5 不带排斥算子 ■不带排斥算子 带排斥算子 带排斥算子 0.4 0.4 非0.3 03 02 。······。。a· 0.2 0. 0.0 0.0 日画口口口■■ 200400 00 2004006008001000 代次数 迭代次数 图2在el51问题上粒子彩微观多样性的变化曲线 图3在ny48问翘上粒子群微观多样性的变亿出线 o1994-2009ChinaAcademicJournalElectronicPublishingHouseALlrightsreservedhttp://www.cnki.net 第6期 求解TSP问题的离散粒子群优化算法 52算法的总体效果 付DP∞O算法的性能进行了刈比实验,在实验中,算法的迭代次数为1000次,粒子群的大小等于城市 数,使用学习宽度为6的学习算子,c1和c2分别为0.2和0.3,DPSO的数据都是25次实验的统计值.从文 献中选用了几种典型的ACO算法进行对比,其中ACSm(Ant( Colony System)算法和MMAs2( MAX-MIN Ant System)算法被认为是最好的A∝O算法,由于文献[13]中没有对ei5l问题和r48问题进行仿真, Aselite l( Ant System with elitist strategy)的数据来源于本文所作的仿真实验,而ACS算法的数据来源于文 献[11]MMAS的数括来涼于文献[12],其中SM表示信息素平滑札制JS表示近邻搜索 表1是在ei51问题上的仿真结果 ASclitc ACS和MMAS+SM相当于51只蚂蚁迭代10000次MMAS+ LS是10只蚂蚁迭代1000次.从表中可以看出,不管是平均值,还是标准差,DPS∞O算法都具有最佳的性能. 表2是在ry48问题上的仿真结果 ASelite ACS和MMAS+SMⅥ相当于51只蚂蚁迭代20000次MMAS LS是10只蚂蚁迭代1000次.从表中可以看出,不管是平均值,还是标准差,DPSO算法都具有最佳的性能. 表1在cil51问题上的仿真结果 表2在ry48问题上的仿真结果 算法 最佳值 平均值 标准差 算法 最佳值 平均值 标准差 DPSO 426 426.22 0.37 DPSO 14422 14438.56 29.22 432.8 l4509 14704.2 l31.99 AcS 426 42 28.06 2.48 ACs 14422 14565.45 115.23 MMAS + SM 426 427.2 1.13 MMAS +SM 14422 1461.64 39.27 MMAS+LS 426 426.3 0.48 MMAS+LS 1421444 43.75 620 20000 600 最佳值 19500 最佳值 580 平均值 19000 平均值 560 18500 18000 坐540 17500 520 N 500 盖16500 480 60144"如,时机的你 15000 440 14500 420 14000 200 400 600 800 8001000 迭代次数 迭代次数 图4在eil51问题上最佳值和平均值的收敛过程 图5在ny48问题上最佳值和平均值的收敛过程 图4和图5分别是DPSO算法在cil5l和r48问题上所获取的最佳值和平均值随迭代次数变化的情 况,从图屮可以看出,算法的收敛性能比较理想,从平均值的变化曲线可以看出,即使在迭代的后期,也不 会出现所有粒子趋同的现象,使粒子群在达代后期依然存在继续进化的能力,这乜进一步说明了排斥算子 对维持DPO算法进化能力的作用 6结论 以求解TSP问题为例,提出∫一个DPSO算法的具体实现,算法中使用了排斥算子来保持粒」群的多 样性,采用了学习算子来提高算法的局部求精能力,使算法在空间探索和局詺求精间取得了很好的平衡 仿真实验表眀DPSO算法具有良好的性能,说明如果能够针对冋趑的特点,重新定义DPSO算法的位萓、速 度等量及其运算规则,DPSO算法能够很好地应用到NP困难的组合优化间题的求解屮,经过适当的修改 本算法也可以用于解决其它置换类问题. o1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net 系统工程理论与实践 2006年6月 参考文献 [1 Kennedy J, Eberhart R. Particle swarm optimization [A]. IEEE Intl Conf on Neural Networks[ C]. Perth, Australia, 1995, 1942 [2 Eberhart R, Kennedy J. A new optimizer using particle swarm theory LA. Proc of the Sixth Intemational Symposium on Micro Machine and Human Science[C]. Nagoya, Japan, 1995, 39-43 [31 Kennedy J, Eberhart R. a discrete binary version of the particle swarm algorithm[A]. Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics[C]. Piscataway, N: IEFE Service Center, 1997, 4104-4109 [4 Cagnina L, Esquivel S, Gallard R. Particle swarm optimization for sequencing problems: A case study Ia]. proceeding of the 2004 Congress on Evolutionary Computation[C]. USA [5] Tasgctiren MF, Sevkli M, liang YC, ct al. Particle swarm optimization algorithm for permutation flowshop sequencing pmblem [A]. Lecture Notes in Coputer Science, Vol. 3172, Ant Colony Optimization and Swarm Intelligence: the 4th International Workshop lC. Springer Verlag, 2004. 382-390 [6] Tasgetiren M F, Sevkli M, Liang Y C, et al. Particle swarm optimization algorithm for single machine total weighted tardiness problem[A]. In: Proceedings of the 2004 Congress on Evolutionary Computation[ C]. Portland, Oregon, 2004. 1412-1419 [7]李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[].系统工程理沦与实,2004,24(4):130-135 Li Ning, Zou Tong, Sun Debao. Particle ization for vehicle outing poblem with time windows [J. Systems Engineering- Theory and Practice, 2004, 24(4): 130-135 [8 Clerc, M. Discrete particle swarm optimization[A]. Orwubolu CC, Babu bv. New Optimization Techniques in Engineering[CI Springer- Verlag, 2004, 219-240 Lυ」高尚,韩斌,吴小俊,等.珓解旅行崗叵题的混合粒子群优化算法U」.控制与决策,2004,19(11):1286-1289 Goo Shang, Han Bin, Wu Xiaojun, et al. Solving traveling salesman problem by hybrid particle swarm optimization algorithm [J] ContIol and Decision, 2004, 19(11):1286-1289 [10]http://ww.iwr.uni-heidelberg.de!gmupscomopt/software/tsp.B95 [Il Gambardella L M, M Dorigo. Solving symmetric and asymmetric ISPs by ant colonies[A. Proceedings of IEEE Intenational Conference on Evolutionary Computation[ C]. Nagoya, Japan, 1996, 622-627 [ 12] Stutzle T, Hbos H. MAX MN ant system[J ]. Future Generation Computer Systems, 2000, 16(8): 889-914 [13 Bullnheimer B, HartI R F, Strauss C. a new rank based version of the ant system: A computational study[]. Central Furopean Journal for Operations Research and Economics, 1999,7 (1): 25-38 C1994-2009ChinaAcademicjOurnalElectronicPublishingHouse.alLrightsreservedhttp://www.cnki.net

...展开详情
试读 7P 论文研究-求解TSP 问题的离散粒子群优化算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744207 欢迎大家使用并留下宝贵意见
    2019-09-20
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-求解TSP 问题的离散粒子群优化算法.pdf 5积分/C币 立即下载
    1/7
    论文研究-求解TSP 问题的离散粒子群优化算法.pdf第1页
    论文研究-求解TSP 问题的离散粒子群优化算法.pdf第2页
    论文研究-求解TSP 问题的离散粒子群优化算法.pdf第3页

    试读已结束,剩余4页未读...

    5积分/C币 立即下载 >