基于粒子群算法的旅行商问题求解

基于粒子群算法的旅行商问题求解

从目前的各种psv解算方法来看，小型psv示例适合整体优化技术的解算方法，但考虑到面积较大的psv示例，需要采用启发式方法。对于复杂优化问题,单一机制的优化算法很难实现全局优化,且效率较低。多种优化机制和邻域搜索结构相混合,是能较大程度提高全局优化度的有力途径,并可一定程度上放松对单一算法参数选择的苛刻性。所以混合优化策略会是一种趋势。一、mtp的粒子群算法(一)tsp的步骤一般都是随机生成规模为N的初始路径。初始路径中的城市是按访问的顺序排列的,例如:对于一个10个城市的TSP:3-2-5-4-7-1-6-9-8-10,表示从城市3出发依次经过城市2,5,4,7,1,6,9,8,10然后返回城市3的一条路径。并且这种表达方式满足TSP问题的约束条件。保证了每个城市经过且只经过一次,并且保证任何一个城市子集中不形成回路。(二)交叉操作交叉的本质就是从种群中选择父代以生成新的母体群。交叉的方法很多,我在算法中采用了以下策略:1.交叉策略a在第2个串中随机选择一个交叉区域:将old2的交叉区域加到old1后面,删除old1中已在old2交叉区中出现过的城市。2.交叉策略b在第2个串中随机选择一个交叉区域;将old2的交叉区域加到old1对应的位置,删除old1中已在old2的交叉区中出现过的城市。3.交叉策略c在第2个串中随机选择一个交叉区域;将old2的交叉区域加到old1的随机位置,删除old1中在old2的交叉区中已出现的城市。4.更新传统的交叉区在第2个串中随机选择一个交叉区域,如交叉区域为:6,5,4,3:将old2的交叉区域加到old1的城市6的位置,删除old1中己在old2的交叉区中出现过的城市。(三)变异操作变异的目的是防止种群中的解跑到局部极值去。变异是对子代的随机的改变。我在算法中采用了以下变异策略:1.路径c0的交换在第1-n个访问的城市中随机地选取第J1次和第J2次访问的城市,在路径C0中交换第J1次和第J2次访问的城市,其余不变,此时的路径为C1。2.变异策略b在第1-n个访问的城市中随机地选取第J1次访问的城市,在路径C0中交换第J1次和第J1+1次访问的城市,其余不变,此时的路径为C1。3.城市之间路径组合也称逆转策略,在第1-n个访问的城市中随机地选取第J1次和第J2次访问的城市,在路径C0中第J1次和第J2次访问的城市之间的子路径以反方向插入,其余不变,此时的路径为C1。4.路径c0的城市在第1-n个访问的城市中随机地选取第J1次和第J2次访问的城市,假设J1<J2,在路径C0中将第J1次访问的城市安排到第J2次访问的城市之后,其余不变,此时的路径为C1。5.变异策略e在第1-n个访问的城市中随机地选取第J1次访问的城市,选取离J1距离最近的城市J2,在路径中将城市J2安排到城市J1之后,其余不变。6.城市j1和j2的选取计算路径中相邻城市之间距离最大的两个城市J1和J2,然后选取选取离J1距离最近的城市J3,在路径中将城市J3安排到城市J1和J2之间,其余不变。二、glbest和全局极值1.初始化,设定粒子数n,设定迭代次数m,随机排列城市顺序产生n条初始路径。2.根据当前位置计算适应值1tsp0,设置当前适应值为个体极值plbest,当前位置为个体极值位置pcbest,根据各个粒子的个体极值找出全局极值glbest和全局极值位置gcbest。while(迭代次数<规定迭代次数m)doForj=1:n3.第j个粒子的路径C(j)与个体极值作交叉操作,产生新的路径C’(j),若新的路径长度变短,则保存结果。C’(j)与全局极值作交叉操作,产生新的路径C”(j),若新的路径长度变短,则保存结果。C”(j)变异得到新的位置C”’(j),若新的路径长度变短,则保存结果。最后产生的路径为C1(j),若△E<0,则C1(j)覆盖原始路径C(j)Endfor根据各个粒子的个体极值找出全局极值glbest和全局极值位置gcbest。EndWhile4.输出全局极值glbest和全局极值位置gcbest。三、粒子群算法的优势本文在深入分析和研究了粒子群算法基本理论与方法的基础上,尝试用新的方法将粒子群概念应用到TSP这一离散领域优化的问题之中,取得了突破。同时针对PSO的弱点提出了交叉变异的方法,进一步提升了粒子群算法在寻找TSP最优解领域的能力,在求解旅行商问题上有较高的搜索效率,能在较短时间内获得较好解,而且简单有效。算法的分析和测试表明,该粒子群算法是有效的。虽然该算法没有专门针对TSP问题的经典算法那么高效,但是仍然是粒子群算法求解旅行商问题