改进混合蛙跳算法求解旅行商问题

1、改进混合蛙跳算法求解旅行商问题罗雪晖,杨烨,李霞(深圳大学信息工程学院,广东深圳 518060摘 要:以旅行商问题(TSP为例,引入调整序思想设计了局部搜索策略,同时在全局信息交换过程中加入变异操作,提出一种改进混合蛙跳算法求解TSP问题。实验结果表明,与遗传算法和粒子群优化算法相比较,改进混合蛙跳算法在求解TSP问题上具有更好的搜索性能和顽健性。关键词:混合蛙跳算法;旅行商问题;局部搜索;全局信息交换中图分类号:TP18 文献标识码:A 文章编号:1000-436X(200907-0130-06Modified shuffled frog-leaping algorithm tosolve

2、traveling salesman problemLUO Xue-hui, YANG Ye, LI Xia(College of Information Engineering, Shenzhen University, Shenzhen 518060,ChinaAbstract: Modified shuffled frog-leaping algorithm to solve TSP was proposed, which presented the concept of adjustment sequence to design the strategy of local search

3、ing, and added the mutation operation in the global exchange of information. Experimental results indicate that, compared with genetic algorithm and particle swarm optimization algorithm, the proposed algorithm has more powerful search capability and more strong robustness in solving TSP.Key words:

4、shuffled frog-leaping algorithm; traveling salesman problem; local search; global information exchange1引言混合蛙跳算法是2000年由Muzaffar Eusuff和Kevin Lansey提出的一种基于群智能的亚启发式计算优化算法,用于解决离散组合优化问题1。作为一种新型的仿生物学智能优化算法,SFLA结合了基于模因(meme进化的模因演算法(MA,memetic algorithm和基于群体行为的粒子群算法(PSO, particle swarm optimization2种群智能优化算法

5、的优点。该算法具有概念简单,调整的参数少,计算速度快,全局搜索寻优能力强,易于实现的特点2。混合蛙跳算法主要应用于解决多目标优化问题,例如水资源分配、桥墩维修、车间作业流程安排等工程实际应用问题35。著名的旅行商问题6(TSP, traveling salesman problem是一类典型组合优化问题,求得一条遍历所有城市的最短回路,属于NP难问题。对TSP问题一般分为两大类的研究:一类着重于研究算法解决大规模实际问题7,如文献7中解决的TSP问题城市规模最大达到316 228个,侧重点在于算法能快速地有效求得可行解;另一类则是利用TSP问题来验证优化算法解决离散组合优化问题的有效性。几十年

6、来,出现了很多近似优化算法用于求解TSP 问题,基本分为2类:与问题本身特征相关的局部启发式搜索算法,如2-Opt、3-Opt和Lin-Kernighan(LK8等。这类优化算法多数充分收稿日期:2008-08-02;修回日期:2008-11-20基金项目:国家自然科学基金资助项目(60772148Foundation Item: The National Natural Science Foundation of China (600772148第7期 罗雪晖等:改进混合蛙跳算法求解旅行商问题 ·131·利用问题本身特征的相关信息有效寻找问题的局部最优解,但是这些算法过分

7、依赖于问题本身特征,当问题的规模扩大后,问题本身特征的相关信息更复杂,大大增加算法计算量,使得算法搜索时间过长。独立于问题的经典智能优化算法,如蚁群算法、遗传算法、模拟退火法、粒子群算法、免疫算法等。此类算法大多数是模拟生物进化算法,不依赖于问题本身特征,具有较强的全局搜索能力。近年来,许多学者将局部启发式搜索算法和智能优化算法相结合产生新型混合算法应用于求解TSP 问题。文献8提出了一种求解TSP 问题的混合遗传算法,该算法结合了基于领域的LK 算法和采用了交叉逆转算子;文献9介绍了求解TSP 问题的蚁群算法,在算法中引入局部信息激素、信息激素更新策略与变参数策略等;文献10提出了基于改进粒

8、子群优化算法求解旅行商问题,文中引入了速度变异机制和粒子自探索机制。这些研究成果表明把智能优化算法与局部启发式搜索相结合能有效提高算法搜索到最优解的能力。混合蛙跳算法提出时间不长,无论在理论还是在实践方面都处于起步阶段。文献11 尝试提出了运用混合蛙跳算法求解TSP 问题,本文在此基础上引入调整序思想设计了局部搜索策略,同时在全局信息交换过程中加入变异操作,从而提出一种改进的混合蛙跳算法求解TSP 问题。实验结果表明,与遗传算法和粒子群优化算法相比较,改进的混合蛙跳算法在求解TSP 问题上具有更好的搜索性能和顽健性。2 混合蛙跳算法的数学模型1混合蛙跳算法(SFLA是一种受自然生物模仿启示而产

9、生的基于群体的协同搜索方法。这种算法模拟青蛙群体寻找食物时,按族群分类进行模因信息传递的过程。混合蛙跳算法主要包括2个部分:局部搜索和全局信息交换。各族群局部搜索使模因信息在局部个体间传递优化局部个体,混合全部青蛙,然后排序再分族群的过程使局部间的模因信息得到全局信息交换。局部搜索和全局信息交换一直持续交替进行到满足收敛条件结束为止。以下简要介绍混合蛙跳算法的数学模型。 2.1 基本概念随机生成F 只青蛙组成初始群体,每个青蛙个体表示问题的一个可行解为12(,d U U U U =",计算青蛙个体适应度(i f ,其中d 表示解空间的维数。在随机生成初始群体之后,将青蛙个体按适应度(

10、i f 降序排列存储于(,(,1,X U i f i i F =",然后按照特定的划分原则将整个青蛙群体分成m 个族群Y 1,Y 2,Y m ,每个族群中包含n 只青蛙,满足下列关系:k k k k k i f i m k U i U i f i U Y (,1(|(,(+=(1, 1, 1,; f k m i i n k m F mn =+="" (1 若设定m =3,F 只青蛙按适应度由高到低排列,位置位于第1的青蛙分入第1族群,第2的青蛙分入第2族群,第3的青蛙分入第3族群,第4的青蛙分入第1族群,依次类推,将所有青蛙个体划分到3个族群中。 2.2 局部搜索

11、青蛙种群中各族群执行局部搜索策略的目的是在不同的搜索方向上搜索局部最优,搜索迭代一定次数后使得族群中局部最优个体逐步趋向于全局最优个体。首先将青蛙种群划分成多个族群,对每个族群进行局部搜索,但是为了避免青蛙个体过早陷入局部最优,同时加快收敛速度,在每个族群中按照特定的原则选择一定数目的青蛙构成该族群的子族群。对于青蛙群体,具有全局最好适应度的解表示为g U ;对于每一个子族群,具有最好适应度的解表示为B U ,最差适应度的解表示为W U 。首先对每个子族群进行局部搜索,即对子族群中最差适应度的青蛙个体进行更新操作,更新策略为B W max B W B W max B W min int(, ,

12、 0max int(, , 0 rand U U s U U S rand U U s U U =< (2q W U U S =+ (3其中,S 表示青蛙个体的调整矢量,max s 表示青蛙个体允许改变的最大步长。如设W U =1 3 5 4 2, U B =2 1 5 3 4,允许改变的最大步长max s =3,若rand=0.5,则q (1U =1+minint0.5×(21,3=1; q (2U =3+maxint0.5×(13, 3=2;依此相同的操作完成更新策略后可得到一个新解q U =1 2 5 4 3。 2.3 全局信息交换全局信息交换有助于收集各族群搜

13、索的局部·132· 通 信 学 报 第30卷信息,通过模因在全局中的传递,获得新的搜索全局最优解的方向。当所有族群经过一定次数的局部搜索后,将各族群中青蛙个体混合在一起,按适应度(i f 降序排列后,重新划分族群,这样使得青蛙个体间的模因信息得到充分的传递,然后继续进行局部搜索,如此反复直到满足收敛条件算法停止。3 混合蛙跳算法求解TSP 问题TSP 问题描述如下:给定d 个城市及各个城市的坐标,求一条经过各城市一次且仅一次,起始城市和终止城市相同的最短闭合路径。 3.1 青蛙个体位置向量表示每个青蛙个体的位置向量表示TSP 问题的一个可行解。设青蛙12(,d U U U

14、U =",其中d U U U ,21"代表d 个城市的编号,U 表示从城市1U 出发依次经过城市d U U ,2"最后回到城市1U 的路径。另外,青蛙个体适应度函数(i f 定义为闭合路径长度的倒数。3.2 子族群的构造和青蛙个体的更新策略 子族群中青蛙个体的选择策略是青蛙个体的选择权重大小与适应度的大小成正比,即适应度越大的青蛙个体,选择权重越大,越容易被选入子族群;反之亦然。族群中的青蛙依概率选取构造成子族群,其概率公式为2(1/(1i P n i n n =+,1,2,i n =" (4其中,i P 表示在当前族群中第i 青蛙被选入子族群的概率,n

15、 表示每个族群中青蛙个数,族群中每个青蛙被选择的概率之和满足关系式11=ni i P 。2.1节中有关混合蛙跳算法的青蛙个体更新策略有可能会出现不可行解,所以针对TSP 问题,混合蛙跳算法中的青蛙个体更新策略为任意截取B U 中的一段路径序列,替换W U 与之相对应的位置,W U 其余位置的城市序号若出现在这段路径序列中,则将其去除掉,反之保持不变,最后将没有出现的城市序号随机插入路径序列中,从而生成一个新的可行解q U 。若q U 优于W U ,用q U 更新W U ,否则,用全局最优的g U 代替B U ,然后进行上述相同操作,生成一个新的可行解q U 。若q U 优于W U ,用q U

16、更新W U ,否则,随机产生一个新的可行解更新U w 。 4 改进的混合蛙跳算法求解TSP 问题虽然文献11中混合蛙跳算法采用的局部搜索能保证更新解的可行性,但是随机截取一段的操作存在盲目性,使得局部搜索容易早熟。为此,本文在文献11的基础上,引入调整因子和调整序思想设计了局部搜索策略,同时在全局信息交换过程中加入变异操作,从而提出了一种改进的混合蛙跳算法求解TSP 问题。4.1 基于调整序的局部搜索策略调整序12是一个可行解向另一个可行解转换的一个调整序列。局部搜索中子族群的最差解利用调整序思想优化,比简单的随机截取一段替换更有指导性,所以在局部搜索中引入这种思想更新子族群的最差解。1 调整

17、因子设d 个城市的TSP 问题的解为(,i U U = 1,2,i d ="定义调整因子,(21i i TO 为将U 中的1i U 插入到2i U 位置之前,则,(21'i i TO U U +=为U 经调整因子,(21i i TO 操作后的新解。例如,当U =(1 3 5 2 4,调整因子为2,4(TO ,则2,4('TO U U +=(1 2 3 5 42 调整序一个或多个调整因子的有序排列就是调整序,记作ST ,(21N TO TO TO ST "=,其中N TO TO TO ,21"是调整因子,它们之间的顺序是有意义的。A U 、B U 分

18、别为2个不同解,调整序B A (ST U U 表示将A U 调整为B U 的调整序,即B A B A A 12(,N U U ST U U U TO TO TO =+=+"A 12(N U TO TO TO =+" (5 构造一个调整序。设定A U =(1 3 5 2 4,B U =(31 42 5,需要构造一个调整序B A (ST U U ,使得A B A B (U ST U U U +=。可见12B A 3U U =,所以第一个调整因子1,2(1TO ,A1A 1U U TO =+,得到A1U =(3 1 52 4;35B A14U U =,所以第二个调整因子是3,5(

19、2TO ,A2A12(5,3U U TO =+,由此类推,可得B A 123(2,1,(5,3,(5,4ST U U TO TO TO =文献12中求解2个TSP 解序列之间的调整序之前,需要将两个TSP 解序列转化为均以1为起点,预处理的目的是求解出两个TSP 解序列之间的最简短的调整序列(即调整因子个数最少。因为在第7期 罗雪晖等:改进混合蛙跳算法求解旅行商问题 ·133·求解过程中,大多数所得的调整序是将局部最差解调整为局部最优解的情况,为了尽可能使得调整序中调整因子个数较多,增加青蛙个体更新的多样性,从而增加了算法搜索能力,避免过早陷入局部最优,本文在求解调整序列时

20、,不需要进行解序列预处理。青蛙个体之间的差异是青蛙个体之间的调整序,调整序的数目为非负数,所以青蛙个体的更新策略为B W max minint(,l rand length ST U U l = (6B W (|(,1,2,i i S TO TO ST U U i l =" (7q W U U S =+ (8 其中,B W (length ST U U 表示调整序B W (ST U U 中全部调整因子个数,l 表示更新W U 所选用的B W (ST U U 部分调整因子个数,max l 表示允许选用的最大调整因子个数,S 表示更新W U 的调整序。图1所示为青蛙个体更新的一个例子B

21、W (5length ST U U =,3l =,12(,S TO TO = 3TO 。 图1 改进的混合蛙跳算法中局部搜索的青蛙个体更新策略4.2 全局信息交换策略 求解TSP 问题的混合蛙跳算法并未考虑到TSP问题所具有的特点,即边与边之间的邻接关系,不能很好地保留原有边的邻接关系,所以不能将可行解中的优良性能很好地保留在青蛙群体中,不能提高算法的收敛速度。因此在改进的算法中,各个族群的青蛙进行过局部搜索之后,将全体青蛙重新混合在一起,按照一定的概率对每一个青蛙个体进行贪婪倒位变异操作。改进的混合蛙跳算法在全局信息交换过程中加入青蛙个体变异操作,保证了青蛙个体的多样性,缩短算法搜索到全局最

22、优解的时间。贪婪倒位变异算子13利用了贪婪法的基本思想,其主要思想是:对某一青蛙个体U ,随机选择一个城市i U ,与城市i U 左、右连接的城市分别表示为1i U ,1+i U ,然后选取除了i U 、1i U 、1+i U 以外的距离i U 最近的城市j U ,若在U 中j U 与1+i U 之间间隔的城市数少于j U 与1i U 之间间隔的城市数,则对1+i U 到j U 之间的城市进行倒位;反之,则对j U 与1i U 之间的城市进行倒位。例如:对青蛙个体U (1 3 5 2 6 4 8 7 9,随机选择一个城市i U =5,则1+i U =2,1i U =3,离城市5最近的城市j U

23、 =8,则倒位后产生新的青蛙个体1U (1 3 5 8 4 62 7 9,如果新的青蛙个体1U 优于青蛙个体U ,则用1U 取代U 放入青蛙群体中。 4.3 算法实现不失一般性,假设算法收敛的准则为连续多次迭代所得TSP 路径的总长度未有改善。以下给出改进的混合蛙跳算法求解TSP 问题的基本步骤。 1 初始化参数(青蛙族群数m ,族群中青蛙数n (总青蛙数F =(mn ,子族群中青蛙数q ,还有族群中青蛙更新迭代次数IT 的设置; 2 随机产生F 个初始可行解,并计算青蛙个体的适应度;3 青蛙个体按适应度降序排列划分成m 个族群,构造子族群;4 局部搜索。对每个族群中的子族群按4.1节的方式进

24、行青蛙个体的更新;5 所有族群混合,每个青蛙个体进行4.2节青蛙个体变异操作,如产生的新个体优于原来个体则取代原来青蛙个体放入青蛙种群中,重新计算适应度;6 判断是否满足算法收敛条件,若满足,输出最优路径序列;否则,更新全局最优解,返回到步骤3。 5 实验仿真本文采用TSPLIB 14中的Burma14、Bays29、Eil51和Eil101对算法进行测试。实验环境:PC 机PIV-2.8GHz CPU ,512M RAM ,Window XP ,Matlab 6.5。参数设置:青蛙群体总数10F N =,族群数10m =,子族群中青蛙个数2/3q N =,族群中青蛙更新迭代次数IT =q ,

25、青蛙个体允许选择的最大调整因子个数max /2l N =(其中N 表示城市数。采用平均距离对算法的性能进行客观评价,收敛时所需的平均时间对算法运算量进行评价;算法稳定性的评·134· 通 信 学 报 第30卷价是基于相对误差。实验仿真是以同样实验条件下对每个TSP 问题进行50次计算机仿真的统计平均,结果如表1所示,其中针对不同规模TSP 问题,第一行表示混合蛙跳算法的实验结果,第二行是改进混合蛙跳算法的实验结果。表1 混合蛙跳算法和改进混合蛙跳算法在不同规模TSP 问题上的测试结果TSP 实例已知 最优值 算法 最优值平均 距离相对 误差/%平均运行时间/s30.88 3

26、0.88 0.00 1.84 Burma1430.8830.88 30.88 0.00 2.352 020 2 044 1.20 6.75 Bays292020 2 0202 0200.008.21428.87 436.76 1.84 17.42 Eil51428.8711428.87 430.66 0.42 22.36655 673 6.99 28.38Eil101 629629 649 3.18 42.74注:相对误差%100×=OptOptAvg Err 由表1可知,与混合蛙跳算法相比较,改进算法在求解Burma14、Bays29和 Eil51问题能够搜索到最优路径,而且寻找到

27、最优路径的成功率有显著改善。值得注意的是,混合蛙跳算法在求解Eil101问题搜索不到最优解,而改进算法可以搜索到最优解。以51点Eil51为例,运行10次每次迭代50代。将改进混合蛙跳算法与混合蛙跳算法在搜索最优值时,随迭代次数变化的平均情况如图2所示。由图中可见,虽然改进混合蛙跳算法每一次迭代需要操作的步骤增多了,但是它所需的收敛次数明显比混合蛙跳算法少,而且搜索的平均结果也有改善,所以所耗费的运行时间虽然较长,但综合考虑还是可接受范围。 图2 混合蛙跳算法和改进混合蛙跳算法求解Eil51问题的搜索收敛速度对比表2给出了改进混合蛙跳算法,改进粒子群优化算法15,遗传局部搜索算法16在运行环境大致相同的情况下求解Eil51问题所得到的算法最优值、平均距离、相对误差和平均运行时间的数据结果。表2 混合蛙跳算法与其他改进算法在求解Eil51问题上的测