旅行商问题范文

旅行商问题范文（精选9篇）

旅行商问题 第1篇

旅行商问题 (TSP) 是一种典型的组合最优化问题, 可描述为某旅行商欲往n个城市推销货物, 从某个城市出发, 沿途经过各个城市一次后返回出发城市, 要确定一条行走的路线, 计算途径个城市的最短距离, 即给定n个城市和两两城市之间的距离, 确定一条经过每个城市并且仅经过一次的路线, 要求总路径最短。对于城市数目为n的地图, 共有n种不同的路径, 城市越多, 可能的路径也越多。而且路径的增加速度非常快且是非线形的。当n很大时, 去尝试每一种可能的路径是不可能的, 所以需要设计一个有效的算法去寻找最短的路径[1,2]。

1 蚁群算法原理

基于文献4中蚁群算法, 首先引入TSP中常用符号:m为蚁群中蚂蚁数量;bi (t) 为t时刻位于城市i的蚂蚁个数, 且为城市i和j之间的距离;nij为边 (i, j) 的能见度, 反映由城市i转移到城市j的启发程度;τij为边 (i, j) 上的信息素轨迹强度;△tij为蚂蚁k在边 (i, j) 上留下的单位长度轨迹信息素量;Pkij为蚂蚁k的转移概率;j是尚未访问的城市。

在初始时刻, 各条路径上的信息素量相等, 设τij (0) =C, (C为常数) , 蚂蚁k (k=1, 2, …, m) 被随机放到某个城市, 然后根据各条路径上的信息素量选择下一个城市。在t时刻,

式中:allowedk表示蚂蚁k下一步允许选择的城市;

α和β为2个参数, 分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。

为了阻止蚂蚁重复访问, 为每只蚂蚁都设计一个被称为禁忌表 (tabu list) 的数据结构。

经过n个时刻, 蚂蚁完成一次循环, 各路径上信息素“蒸发”和增加的量根据下式调整:

式中:ρ表示信息素蒸发后的剩余, 则 (1-ρ) 为衰减系数, 表示信息素的减少;表示信息素增加的量, 在式 (1) 中

表示第k只蚂蚁在时刻dij留在路径 (t, t+1) 上的信息素量;

, Q为常数, L (k) 为第k个蚂蚁爬过路径 (i, j) 的长度, 等于dij的值。

至此, 一个蚂蚁的循环过程结束, 由此反复迭代多次, 最终得出优化结果。

2 蚁群算法的MATLAB程序描述

2.1 MATLAB程序的主要步骤:

第一步变量初始化;第二步将m只蚂蚁放到n个城市上;第三步m只蚂蚁按概率函数选择下一座城市;第四步记录本次迭代最佳路线;第五步更新信息素;第六步输出结果[3]。

2.2 蚁群算法解决TSP的主要符号说明:

n为城市个数;C为n个城市的坐标, n×2的矩阵;m为蚁群中蚂蚁数量;NC＿max最大迭代次数;Alpha表征信息素重要程度的参数;Beta表征启发式因子重要程度的参数;Rho信息素蒸发系数;Q信息素增加强度系数;R＿best各代最佳路线;L＿best各代最佳路线的长度[4]。

2.3 MATLAB主要程序描述:

第三步m只蚂蚁选择下一座城市

(1) 待访问城市的选择概率分布:

visited=Tabu (i, 1: (j-1) ) ;%已访问的城市

J=zeros (1, (n-j+1) ) ;%待访问的城市

(2) 下面是计算待选城市的概率分布:

(3) 按概率原则选取下一个城市

第四步记录本次迭代最佳路线

第五步更新信息素

3 蚁群算法解决浙江旅行商问题

浙江旅行商问题初始参数设置如下:

蚁群中蚂蚁数量m=200;信息素重要程度的参数Alpha=1;启发式因子重要程度的参数Beta=5;信息素蒸发系数Rho=0.1;最大迭代次数NC＿max=200;信息素增加强度系数Q=100。

浙江省33个城市的坐标C (以33城市的经纬度作为城市的相对坐标) [5], 如表1:

运行蚁群算法程序后, 所得到的最短路线结果为:

即, 舟山-宁波-奉化-临海-台州-温岭-乐清-温州-瑞安-丽水-龙泉-江山-衢州-建德-兰溪-金华-义乌-东阳-诸暨-永康-富阳-湖州-余杭-杭州-萧山-绍兴-上虞-宁海-桐乡-嘉兴-平湖-慈溪-余姚

由于采用的是城市的经纬度作为初始条件, 因此不能算出具体最短路径是多长, 如果采用实际地理相对坐标, 则在运行后的MATLAB程序结果里可以看见所计算出的最短路径长度。

由结果可以看出, 蚁群算法运用于浙江旅行商问题, 在优化结果上是有效的, 表现出令人满意的性能。在进一步的研究中, 将继续探索它在其他优化问题上的应用, 以期取得更佳的效。

摘要：本文主要解决浙江旅行商问题, 应用蚁群算法, 通过MATLAB编写程序, 最终计算出浙江旅行商最短路径。最后画出最短路线图, 以直观方式展现在读者面前。

关键词：蚁群算法,MATLAB程序,浙江旅行商,经纬度

参考文献

[1]段海滨.蚁群算法原理及应用[M].北京:科学出版社.2005.

[2]谢宏.蚁群算法解决TSP问题的研究[J].农业网络信息, 2007, 第3期:22-24.

[3]李明海, 邢桂华.用MATLAB实现中国旅行商问题的求解[J].微计算机应用, 2004, 第25卷第2期:218-222.

[4]李如琦, 苏媛媛.用MAX_MIN蚂蚁算法解决中国旅行商问题[J].湖南工业大学学报, 2007, 第21卷第5期:48-50.

旅行商问题 第2篇

有时间约束旅行商问题的启发式遗传算法

有时间约束的旅行商问题作为旅行商问题的拓展，是一个重要的`NP难题，深入研究这一问题具有重要的理论和实践意义。将时间窗约束转化为目标约束，采用序列编码设计了基于启发式规则的可同时处理软、硬时间约束的遗传算法――2-交换变异的遗传算法和3-交换变异的遗传算法。实验表明HGA1优于简单遗传算法(SGA)，HGA2优于HGA1。

作 者：谢秉磊 李军 刘建新 作者单位：西南交通大学经济管理学院， 四川 成都 610031刊 名：西南交通大学学报 ISTIC EI PKU英文刊名：JOURNAL OF SOUTHWEST JIAOTONG UNIVERSITY年，卷(期)：36(2)分类号：O224关键词：游路问题 组合规化 遗传算法 时间约束

基于最小调整法求解旅行商问题 第3篇

关键词 旅行商问题；最小调整法；算法有效性

中图分类号 O221.4 文献标识码 A

1 引 言

旅行商问题（Traveling Salesman Problem，简称TSP）是著名的组合优化问题[1].经典的TSP问题可描述为：设有n个城市1，…，n，由i城市到j城市的路程dij已知，一个旅行商为了推销货物，从某一城市出发，如何选择一条最优路线可以经过所有其他城市，且每个城市正好经过一次，然后回到出发点.容易看出，旅行商有（n-1）！种方案可供选择.即使n是较小的两位数，这类问题仍没有较好的有效算法，因此被称为NPcomplete问题.但是TSP问题在组合优化问题中具有广泛实际背景和深刻经济含义.例如，在计算机的集成电路设计中就出现了这一问题，还包括派车、排序、底板布线、考古学中的排号、自动钻井、工件加工顺序和邮局收发信件等其他许多方面，所有这些需要促使学者们不断地研究TSP问题的算法[2].目前国内外求解TSP问题的较好算法有遗传算法、神经网络算法、模拟退火算法、蚁群算法和粒子群算法等[3-7]，这些算法中遗传算法具有较好的全局搜索能力，但优化过程缓慢，结果准确度不高；粒子群算法局部搜索能力较弱；蚁群算法等存在计算速度较慢等缺点.因此，以这些算法为基础，较多学者相继提出了改进的算法以更好地求解TSP问题[8-13].

2 最小调整法求解TSP问题的思想和步骤

最小调整法[14]是以Dijkstra算法[15]为实现途径的一种多项式算法.本文根据最小调整法，给出了求解TSP问题的一种新的有效启发式算法.该算法较

之以往常用的启发式算法更加简单易行，计算量仅为O（n2），并且由此得到的近似解一般更接近最优解.

下面首先根据指派问题和TSP问题的异同点比较，然后提出将TSP问题先看做指派问题利用最小调整法求解[16]的具体步骤.

2.1 TSP问题与指派问题的异同

对比指派问题和TSP问题，它们有如下异同点：

第一，指派问题中，第i项任务可以由第i人去完成，因此其解可以在效率矩阵（成本）矩阵的主对角线上；但TSP问题中不存在从Ai城市到Ai城市的情况，其解显然不会出现在距离矩阵的主对角线上，即有i≠j的约束条件.

第二，对于有n个人的指派问题，其解由n项任务所组成，这些任务在效率矩阵中既不同行又不同列；对于有n个城市的TSP问题，其解由n段行程构成，这些行程在距离矩阵中既不同行又不同列.

第三，xij=1或0表示指派问题的解，则效率矩阵任一行、任一列的效率参数之和均为1，即∑ni=1xij=1且∑nj=1xij=1（i，j=1，…，n），即每个任务只有一个人承担，每个人只能承担一项任务.TSP问题中∑ni=1xij=1且∑nj=1xij=1（i，j=1，…，n），即在回路上仅由1个城市出发至第j个城市；从第i个城市出发仅通往1个城市，即所有中间城市仅通过一次.

第四，指派问题不存在回路问题，但TSP问题解的各段行程首尾相接，必然构成一个回路.

通过比较指派问题和TSP问题的特点，上述第一和第四点说明指派问题与TSP问题有区别，第二和第三点则是相同的.如果置TSP问题原始距离矩阵主对角线元素为一个相当大的正数M或记为“×”时，把TSP问题当作指派问题去求解，这种指派问题就具备了TSP问题的第一和第四点中某些特点了，然后再对该解检验其作为TSP问题的可行性.

2.2 最小调整法求解TSP问题的思想步骤

若把带权完全图G当前结点当成任务的承担者，另外结点当成任务，边的权（城市间距离）为完成任务所用时间，则寻求最优Hamilton回路[14，15]是把图中结点怎样与别的结点进行单一指派，使每个结点既是一个结点的任务承担者，又是另一个结点的任务，这种指派使完成任务时间最短以及满足这些指派所确定的路径（旅行商走过的路径即指派路径）构成一个回路的条件.指派路径构成一个回路是在一般指派问题中增加的条件.

设TSP问题的关系矩阵为C

其中元素cij表示由第i城市到第j城市的距离.

步骤1 取每列的一个最小值画圈，即得到一个最小方案.若这些画圈元素又分属于不同行，则得到相应指派问题的最优解，转步骤3；否则转步骤2.

步骤2 应把有两个或两个以上画圈元素行中的一个改画到同列别处，待到某一无圈行中有一元素画上圈，则算一次调整.如此进行，直到每行均有一个画圈元素时为止，然后转入步骤3即可.而每次调整均以目标函数（其值为各画圈元素之和）增值最小为原则.

步骤3 如果从步骤1或2得到的指派问题最优解元素的任一行指标i出发，先到其列指标j为下一行指标的元素出发，再到其列指标.如此进行下去，最后回到以i为列指标的元素，便形成一个圈.若圈中的元素恰为n个，则所得方案即为最优方案；否则便会形成两个或两个以上的子圈，它不是最优解，需进行再调整，转步骤4.

步骤4 以增值最小的原则实行对调调整.所谓对调调整，就是在任意两个子圈中各取一个元素，如cij与cst，交换它们的列标号，变成cit与csj，其结果是这两个子圈便合成一个圈，该变化如图1所示

由图1可知，这4个元素形成一个矩形，调整是把矩形原先对角线上的两个画圈元素cij与cst的圈转给了另一对角线上的两个画圈元素cit与csj.显然经过调整，目标函数将增加为Δf=（cit+csj）-（cij+cst）.考虑所有可能的对调调整，取其中增值最小的，加以调整，便破掉一圈.如此进行，直到无子圈为止.

nlc202309031959

破圈所说的“圈”指的是欧拉圈，它可以分为广义的和狭义的两种：在n个城市的TSP问题中，广义的圈可以由n个城市任选两个以上的城市任意排列构成；而狭义的圈则被严格规定为指派问题最优解即xij=1所在位置，也就是最优解中的画圈元素所构成的回路.狭义的圈在讨论TSP问题时被简称为“圈”.因此，此处可以将“圈”定义为用指派问题最优解所确定的，从一个城市到另一些城市，然后再返回到那个城市的一个闭合回路.对于大规模问题，求最短调整路线可用标号算法，

2.3 最小调整法求解TSP问题算例

先求出相应指派问题的最优解，具体过程为：

以此例的指派问题最优解为c13，c32，c21，c45，c54，转步骤3.检验结果此方案形成两个子圈：（c13，c32，c21）和（c45，c54）如图2（a）和（b）.

容易看出在两个子圈中任意各取一个元素，交换它们的列下标，则这两个圈便合成一个圈.例如将图2（a）的c13与（b）的c45的列下标对调或交换便成为：c15，c54，c43，c32，c21.于是便破掉一个圈，此例经处理便得到一个可行方案.上述处理相当于若把分属于不同圈中的两元素看成为矩形一对角线的二顶点，则其圈调换给了该矩形另外一条对角线的两个顶点对应的元素，即：

调整的结果将导致目标函数值的增加.若每次对调都选择增值最小的进行，当所有的子圈全被破掉后，即得原问题的一个更好的解.

此例中的最优解为：

因此，旅行商问题的最短路线为：1→4→5→3→2→1，最短路线长为f=20.

此例还有其他多种破圈方案在此不再累述.在最小调整最优方案的基础上实施对调调整可在图中直接完成，以上例两个圈进行说明：即以一个圈中的画圈元素与另一个圈的每个画圈元素连线，以该线为对角线的矩形的另两个顶点元素即交叉对角线的两个顶点元素，计算这两个元素之和与原画圈两个顶点元素之和的差，若为0则该对调调整就是最优调整；若不为0，继续将该圈中其他画圈元素仿此处理，最后取差值最小的进行对调调整.若最小调整法的最优方案形成两个以上的圈，也可按照上述两两圈分别进行对调调整差值计算比较，并进行对调调整，直至最终形成一个圈为止.

此问题的最优解并不唯一，另一最优解求解过程为：

此即另一最优解且无需对调调整：1→2→3→5→4→1.该最优解仅通过最小调整法就可解得.

3 最小调整法求解TSP问题的有效性分析

3.1 关于最小对调的分析

给定TSP问题的矩阵C，考虑以指派问题作为它的松弛问题.记指派问题的解为：itjt=1，t=1，…，n，其余ij=0（也可记：ci1j1，ci2j2，…，cinjn），相应最优值为

按下述行列衔接规则排列（1）中的元素：任取一元素citjt排在首位，若其行标为it列标为jt，则将以jt为行标的元素排在其后，使得每一元素的列标都是紧接其后元素的行标，直到以it为列标的元素排上为止.易见，如果上述排列所经历的元素恰为n个，则指派问题的解即为TSP的最优解，TSP的最优值也是式（1），而上述排列过程正好给出最优路线.若排列所经元素个数k

ci1i2，ci2i3，…，citit+1，…，ciki1

容易验证，当k

cj1j2，cj2j3，…，cjljl+1，…，cisi1，

设指派问题解中有h≥2个子圈，因此可以通过某种方法替换其中的元素，使子圈渐减直到无.经研究发现一种简单的破圈方法，具体如下定理.

定理1 交换分处于二子圈中任意二元素的行标（或列标）后简称为对调，这二子圈便合成一个高阶子圈，从而破掉一圈.

证明 设有二子圈（2）和（3），各任取一元素citjt+1及ciljl+1，交换它们的行标后式（2）和（3）分别变成： 按行列衔接规则重新排列，便有

这样它们便合成一个阶数为k+s的高阶子圈.

证毕.

推论1 若子圈（2）的阶数k≥4，则交换其中任意两个不相邻元素的行标（或列标），则它便一分为二个低阶子圈（注意ci1i2与ciki1也是相邻的）.

这样，对指派问题的解经（h-1）次对调便可得到TSP问题的一个可行解.可得定理1中所述的对调式（4）简记为

对调式（5）在破圈的同时，也引起目标函数值式（1）的增加，其增值为 为使由对调得到的可行解尽可能的好，自然希望增值（6）越小越好.于是每次破圈都选择使对调的增值（6）最小的进行当在首先考虑之中.这就是最小对调，由之得到的可行解称为最小对调解.

3.2 算法复杂性及近似程度分析

最小对调需要考虑所有可能的对调，因此应估算出对调总数.设式（2）的h个子圈所含元素的个数分别为x1，…，xh，则因子圈中任一元素均可与其余子圈中的任一元素实行对调，所以可知对调总数应为

说明对调总数不超过n22，且此上界与子圈个数h无关.

由于计算对调的增值（6）需3次加法运算，所以第一步最小对调的计算量不超过3n22次加法运算.虽说以后还要实行（h-2）步最小对调，但需要再计算的数量却比第一步的少得多.这是因为破掉一子圈后的变化仅在于由原二子圈合成的新子圈中换入了2个新元素，且新子圈所含元素至少为4.因此只需考虑这2个新元素所形成的对调，这时其余子圈的元素总数不超过（n-4），这样第二步需要计算的新对调不超过2（n-4），依此类推可知以后各步需要考虑的对调数之上

nlc202309031959

综上分析，对指派问题的解相继实行最小对调，直到得到最小对调解，所需考虑的对调总数按最坏情形计算则不超过n2，实行的加法运算次数不超过3n2，因此是十分有效的一种启发式算法.

再从与TSP问题最优解近似程度分析有如下定理2.

定理2 对于TSP的任意一个已知的可行解X，均可通过对指派问题的解实行若干次对调得到.

证明 取行标i=1，设对应列标j1，有x1j1=1.若1j1=1，则转而考查i=2.若1j1=0，则应有列标j2，使1j2=1，同时也有行标i1，使i1j1=1.若i1≠j2，则可实行对调（ci1j1，c1j2）→（c1j1，ci1j2），若对调后的方案仍记为，则已有1j1=x1j1=1.若i1=j2，则对调不能实行，由定理1说明c1j2与ci1j1属同一子圈，这时可于其他子圈中任取一元素ci2j3，先实行对调（ci1j1，ci2j3）→（ci2j1，ci1j3），然后再实行对调（ci2j1，c1j2）→（c1j1，ci2j2），结果仍有1j1=x1j1=1.再取i=2，重复以上过程，则知不超过2n次对调，便可由调整到可行解X.

证毕.

因此，由定理2，TSP问题的最优解也可通过若干次对调得到，它是使各步对调的增值（6）之累积总和最小者.最小对调虽说不能保证（6）之累积总和一定最小，但通常总是较小的，是最优解一个十分理想的上界.事实上，若设最优解为X*，指派问题的解仍为X-，最小对调解为X～，则有

f（）-f（X*）≤f（）-f（）

（10）

上式表明由最小对调解到最优解的改进不超过f（）-f（）.

3.3 算例分析

下面通过两个算例作进一步的对比分析.

例2 设旅行商问题的关系矩阵如下，求其最优解.

求解过程如下：

首先求相应指派问题最优解有

得到相应指派问题最优解：c14，c42，c21，c35，c56，c63.对调数为3×3=9，其中最小对调调整为（c42，c63）→（c62，c43），Δf=9.经过最小对调调整为于是得到：c14，c43，c35，c56，c62，c21；f（）=63，此即最优解.

若采用一般有效的启发式算法，因矩阵C是非对称的，所以无法求2—最优解，只能考虑3—最优解，取一初始路线，如X0：c12，c23，c34，c45，c56，c61，则f（X0）=124.其3—相邻路线共有6（6+1）（6-4）6=14条，其中最短的为X1：c14，c45，c56，c62，c23，c31，f（X1）=80；再求X1的3—相邻路线（除X0外计13条），其中最短的为X2：c14，c43，c35，c56，c62，c21，f（X2）=63；继续求X2的3—相邻路线（计13条），结果发现X2即3—最优解.它即是TSP问题的最优解.此类算法是否成功以及计算量的大小均依赖于初始路线X0，若选得好，既能得到满意解又减少迭代次数；若选得不好，则可能得不到最优解，迭代次数也会很多.例如，若选X0：c14，c45，c56，c63，c32，c21，f（X0）=64，则其3—最优解即TSP最优解；若选X0：c14，c42，c23，c36，c65，c51，f（X0）=65，则因其3—最优解即本身，所以得不到最优解.而所有这些差异事先无法预料，所以不得不随机地取许多初始路线，导致计算量大增，而且即使碰上最好的情形，其计算量也比最小对调大得多.由于指派问题的解的固有性质（f（）≤f（X*）），常使中的不少元素保留在TSP问题的最优解中，所以由→X*的对调调整一般都不太复杂，如果不是有意构造，其最小对调解大多与最优解很接近.因此下面通过一个最小对调解不是最优解的算例进一步进行分析说明.

例3 旅行商问题的关系矩阵如下所示

其对应的指派问题的解，经最小调整法求解得

实行第二步最小对调容易求得最小对调解为：累积增值Δf=12.而不是最优解，最优解为X*：c12，c24，c43，c36，c65，c51，Δf*=6.

如果由于的原因使f（）-f（）大到难以接受的程度（如将矩阵C中除1以外的元素均扩大10倍乃至更多），则应该考虑改进最小对调解.改进的途径有很多，其中容易想到和较为有效的是用二步、三步以至P步对调的增值和最小来代替一步增值最小，并分别记为2—最小对调，3—最小对调等等.如果不特别指出，通常所说最小对调的计算复杂度为O（n3），3—最小对调的计算复杂度是O（n4）等等.实算表明3—最小对调具有计算量不很大且效果好的优点.

若指派问题解的子圈个数h为偶数，则实行P—最小对调时，P取奇数为宜，所以据定理1及其推论，若取P为偶数，则永远不会得到可行解.同样，当h为奇数时，则P取偶数.因此考虑到破圈因素，各种对调混合使用效果可能更好，如果第一步用2—最小对调，然后3—最小对调，最后几步只用1—最小对调等等.甚至只需在累积用1—最小对调的同时，附带着多考虑几个对调，如次最小、三最小对调等等，然后加以比较，取其中最小者，就可能使得到的可行解有明显的改进，而每步的计算量仅有O（n）的增加.如对例3，若采用2—最小对调，便可得到最优解：第一步：（c21，c56）→（c51，c26），Δf1=14；第二步：（c26，c34）→（c36，c24），Δf2=-8.两步对调的增值累积和Δf=Δf1+Δf2=6.其实这里的第一步对调就是次增值最小者，实行1—最小对调时，若将它也附带考虑进去，便可更快得到最优解.因为TSP问题的最优解，虽然不能说一定是由每步增值最小的对调得到，但多半总是由每步增值较小之中的一个得到，所以对那些增值太大的对调一般可以不必考虑.最后根据定理2，对调也不应仅限于子圈之间，例如若h=2，且由P—最小对调得到最优解，则不能认为一定有P=1，因为P可能是其他奇数.这样一来，所考虑的对调数要增加，但数量仍不变，与前边分析的结果相同.任何一步对调都将引起子圈个数的变化，因此进一步研究P—最小对调对子圈变化的影响规律以及其他的破圈途径，以便更迅速有效地求得TSP问题的最优解，则是十分重要和有意义的.

nlc202309031959

4 结 论

本文基于最小调整法提出了求解TSP问题的一种新算法，给出了具体求解的步骤，并对算法的有效性进行了详细论证.通过对具体算例的求解及检验，说明最小调整法比常用的求解TSP问题近似解的算法更加简单易行.同时指出最小调整法求解该问题有时只能求出其近似解的不足和局限，对需要进一步改进和研究的工作进行了说明.

参考文献

[1] 牛燕影，王增富，王雷震.旅行商问题的一个新算法：堵子回路法＼[J＼].统计与决策，2008，24（13）：145-147.

[2] 吴振奎，王全文，刘振航.中国邮路问题的一个解法[J].运筹与管理，2004，13（3）：44-47.

[3] S LIN， B W KERNINGHAN. An effective heuristic algorithm for the traveling salesman problem[J]. Operation Research， 1971， 21（2）： 498-516.

[4] M DORIGO， L GAMBARDELLA. Ant colony system： a cooperative learning approach to the traveling salesman problem[J]. IEEE Transanctions on Evolutionary Computation， 1997，1（1）：53-66.

[5] G A JAYALAKSHMI， S SATHIAMOORTHY， R RAJARAM. A hybrid genetic algorithm： A new approach to solve traveling salesman problem[J]. International Journal of Computation Engineering Scinece， 2001，2（2） ： 339-355.

[6] Z WANG， X GENG， Z SHAO. An effective simulated annealing algorithm for solving the traveling salesman problem [J]. Journal of Computational and Theoretical Nanoscience， 2009， 6（7）： 1680-1686.

[7] Y MARINAKIS， M MARINAKI. A hybrid multiswarm particle swarm optimization algorithm for the probabilistic traveling salesman problem[J]. Computers and Operations Research， 2010， 37（3）： 432-442.

[8] 赵建明，姚念民.Hopfield网络求解旅行商问题有效性的研究[J].科学技术与工程，2009，9（2）：437-440.

[9] 吴新杰，黄国兴.利用粒子滤波求解旅行商问题[J].计算机应用，2012，32（8）：2219-2222.

[10] 柳寅，马良.模糊蚁群算法及其在TSP中的应用[J].数学的实践与认识，2011，41（6）：150-154.

[11] F LIU， G Z ZENG. Study of genetic algorithm with reinforcement learning to solve the TSP [J]. Expert System with Applications， 2009， 36（3）： 6995-7001.

[12] H WANG. Comparison of several intelligent algorithms for solving TSP problem in industrial engineering [J]. Systems Engineering Procedia， 2012， 4： 226-235.

[13] 李煜，马良.用量子蚁群算法求解大规模旅行商问题[J].上海理工大学学报，2012，34（3）：355-358.

[14] 夏少刚.运筹学—经济优化方法与模型[M].北京：清华大学出版社，2005.

[15] J J MODER， S E ELMAGHRABY. 运筹学手册： 基础和基本原理[M].上海：科学技术出版社，1987.

[16] 夏少刚，费威.基于最小调整法求解最短时限指派问题[J]. 数学的实践与认识，2009，39（17）：179-187.

使用遗传算法求解旅行商问题 第4篇

关键词：遗传算法,旅行商问题,选择算子,杂交算子,异变算子

1 引言

遗传算法是基于自然选择和自然遗传机制的一种随机搜索算法,具有良好的并行性和全局寻优能力,能够自适应地调整搜索方向。这是一种相对来说比较简单的算法,因为它不需要问题求解者具备非常完备的问题领域知识,它能够通过类似生物体繁殖后代的机制自动生成问题的解,不过这个解往往不是该问题的最优解,而是相对来说的次优解。正是由于遗传算法简单的算法思路以及强大的搜索能力,它在机器人寻路、函数优化以及组合优化等诸多领域都得到了相当广泛的应用。用遗传算法求解旅行商问题就是遗传算法应用到组合优化问题中的一个经典例子。

2 遗传算法求解旅行商问题

2.1 旅行商问题

所谓旅行商问题,即给定几个城市,旅行商从中选择一条最短的路线,使他能够访问到每个城市一次,然后返回起点。

2.2 一般步骤

要使用遗传算法,首先应该确定解的编码方式,然后使用这种编码方式随机地构造一定数目的可能解(即初始群体),每个解都称为一个染色体。接着循环执行如下步骤直到产生出需要的群体并从中选择一个最优的解:

(1)检查每一个染色,评估其解决问题的能力从而为其分配一个适应性分数。

(2)从当前群体中选择两个染色体按照预先设定的杂交率进行杂交。

(3)按照预先设定的变异率对产生的后代进行变异。

2.2.1 编码与适应性分数

由于旅行商问题的解是一条从起点经过所有城市后又回到起点的路径,而这条路径上存在的节点往往少则数十个多则成百上千个,因此,使用传统的二进制编码方式来对解进行编码是非常困难的。采用数字来标示每座城市,以数字序列来作为解的编码不仅在形式上比较简单而且有利于编程中的引用,因而是非常合适的。例如,城市A～F依次用数字1～6来标示,则一个可能的解可以表示为{1,3,4,6,5,2},即旅行商从城市A开始依次经过C、D、F、E、B最后回到A。因而一个染色体就对应了一个数字序列。

适应性分数是用来衡量一个可能解的好坏的度量标准,遗传算法参照这个适应性分数从父代中选择两个染色体来生成后代,这两个染色体也被称为父染色体和母染色体。在此问题中每一个解的适应性分数由该解的路径长短决定,具体为由当前世代中最长路径的长度减去当前解路径的长度。例如,当前世代中最长路径的长度为3000,而欲判断的解的路径长度为2300,则该解的适应性分数为700,而最长路径对应的解的适应性分数为0,这样就使得路径越长的解被选中的概率越小。

2.2.2 选择算子

在这个问题中,如果使用传统的轮盘选择,那么由于其中有相当一部分的解非常相似,算法的收敛会很快,从而使得求得最优解的机会变小。为了解决这个问题,可以采用淘汰机制。首先按适应性分数将解从低到高排列,然后将适应性分数非常接近的解按一定比例Pe淘汰,相对提高了保留下的解的多样性。适应性的接近程度可以用一个数值作为标准,例如当两个相邻染色体适应性分数之差小于50时,可以认为这两个染色体是应该被淘汰的。当所有非常接近的染色体都被淘汰后,在仍未达到淘汰比例Pe时,将适应性分数低的染色体也淘汰一部分,直到达到淘汰比例为止。然后在这些解中执行轮盘选择。而这种方法的主要问题就在于如何确定淘汰率Pe,Pe的确定往往需要算法设计人员经过反复试验得到,而且城市数目不同时原来的Pe也可能已经不适合,需要重新确定。在城市数目为20时,经验证7%可以得到不错的效果。

2.2.3 杂交算子

选择得到父染色体和母染色体后,需要按杂交率进行杂交。随机选择一个0到1之间的小数,当这个数小于杂交率时,就对这两个染色体进行杂交,得到两个子染色体。否则,直接复制这两个染色体为子染色体。杂交的方法采用顺序杂交。首先在父母染色体P1:a、b、c、f、e、d、g中选择n个位置,假设为1、2、3这3个位置。在P1中这3个位置对应了a、b、c,则另一个染色体P2中的a、b、c也应该按这个顺序排列,但没必要在相同位置。假设另一个父母染色体P2:c、e、f、g、a、b、d,则子染色体C1应该是a、e、f、g、b、c、d。同样的道理,在P2中1、2、3、3个位置为c、e、f,因而改变P1得到子染色体C2:a、b、c、e、f、d。

2.2.4 变异算子

采用简单的交换方法作为变异算子,在给定变异率下进行异变。随机选择一个0到1之间的小数,当此数小于变异率时对子染色体进行变异。例如,对于C1:a、e、f、g、b、c、d,随机选择两个城市,假设选择了e和b,交换两者的位置得到异变后的染色体C1’:a、b、f、g、e、c、d。

2.3 程序实现

使用C++语言和Win32SDK作为编程工具,在程序中城市被设计为一个类CCity,属性为它的坐标(x,y),这个坐标被人为地定义。两个城市的距离由勾股定理计算,根据这些距离可以确定某一个解的适应性分数。为了使得算法的效果更加直观,将所有城市排列成一个圆,那么可以肯定的是最短的路径必定将这些点连成一个圆形。如果路径并未完全分布在圆周上,那么说明这个解并不是最优的。在程序主界面上可以定义淘汰率、杂交率和变异率。最后的程序效果如图1所示。

3 结语

遗传算法的并行性和全局寻优能力使得其在许多问题领域都得到了应用。但是,由于遗传算法自身特点的限制,往往并不是总能求得最优解。经过国内外专家的研究与实验,得到了很多优化方法,使得遗传算法在求解时能够尽最大可能地求得最优解。遗传算法中的诸多参数也是决定算法性能的重要因素,为了使算法能够更好地适应所求解的问题,应该多测试一些参数以得到较为合适的解。

参考文献

[1]黎钧琪,石国桢.遗传算法交叉律与变异率关系的研究[J].武汉理工大学学报:交通科学与工程版,2003,27(1):97-99.

[2](美)Mat Buckland.游戏编程中的人工智能.北京:清华大学出版社,2006.

[3]Holland,J.H.(1975)Adatation in Natural and Artificial Sys-tems.University of Michigan Press,Ann Arbor,MI.

求解旅行商问题的改进混合蛙跳算法 第5篇

组合优化 (Combinatorial Optimization) 问题的目标是从可行解集中求出目标函数下的最优解[1]。旅行商问题 (Traveling Salesman Problem, TSP) 是组合优化中最典型的NP难问题, 它的含义可以简述为:求出一条遍历所要求的所有城市的最短路径。对TSP问题一般分为两大类的研究:一类着重于研究算法解决大规模实际问题, 侧重点在于算法能快速地有效求得可行解;另一类则是利用TSP问题来验证优化算法解决离散组合优化问题的有效性[2]。

混合蛙跳算法 (Shuffled Frog Leaping Algorithm, SFLA) 是一种新型的群体智能优化算法[3], 与其他群体智能优化算法相比, 具有涉及参数少和易于实现等优点。文献[4]尝试提出了运用混合蛙跳算法求解TSP问题。本文在此基础上把遗传算法 (Genetic Algorithm, GA) 中的交叉和变异的思想引入SFLA, 提出了一种改进的混合蛙跳算法 (Improved Shuffled Frog Leaping Algorithm, ISFLA) , 旨在提高SFLA的收敛速度, 提高克服局部最优的能力。

1 SFLA

SFLA是一种受自然生物模仿启示而产生的基于群体的协同搜索方法。通过模拟青蛙群体寻找食物时, 按种群分类进行思想传递的过程, 将全局的信息交换和局部搜索相结合, 使SFLA能跳出局部极值点, 向全局最优的方向进行[3]。

对于k维函数优化问题, 种群中的第i只青蛙可表示为Xi= (xi1, xi2, xik) , 根据每只青蛙适应度的大小从大到小排列。整个青蛙群体被分为m个子群体, 每个子群体包含n只青蛙, 即青蛙总数目为P=m*n。在进化计算过程中, 第一只青蛙进入第一个子群体, 第二只青蛙进入第二个子群体, 一直分配下去, 直到第m只青蛙进入到第m个子群体。然后, 第m+1只青蛙又进入到第一个子群体, 第m+2只青蛙进入到第二个子群体等, 这样循环分配下去, 直到所有青蛙分配完毕。

在每一个子群体中, 适应度最好的个体和最差的个体记为Xb和Xw, 整个青蛙群体适应度最优的个体记为Xg。在每次循环中, 只对每一个子群体的最差个体Xw进行更新, Xw的更新方法如下:

式 (1) 与式 (2) 中, rand () 是介于0和1的随机数, Dmax是青蛙允许跳动的最大距离。

如果通过式 (1) 与式 (2) 计算得到的新个体比原个体优, 则用其替代最差个体, 否则再次用式 (1) 与式 (2) 计算 (此时用Xg替代Xb) 。如果得到的新个体比原个体优, 则用其替代最差个体, 否则随机生成一个新解来取代最差个体。重复上述最差个体的更新过程, 直至每个子群都达到群内的更新代数Ite。

2 ISFLA

SFLA在进行元进化的时候, 采用两种跳跃方式分别只利用到局部最优和全局最优个体的信息, 忽略了个体之间和子群之间的信息交流, 失去了很多很宝贵的信息。当两次跳跃都无法产生比子种群中的最差个体Xw更好的个体, 算法就不加限制地随机产生一个新个体代替Xw, 这可能产生更差的个体, 也有可能导致群体中部分有用信息丢失。同时, 若将SFLA应用于解决TSP问题中, 再把元进化的策略应用到城市的组合中, 很有可能出现城市重复等无效解。ISFLA用交叉和变异和描述元进化。

2.1 交叉算子

次序交叉算子:在整个种群的最优个体Xg中随机选择两个维度并记录在两个维度之间的城市。然后在族群中最差的个体Xw中找到相对应的城市标记出来, 并把其余的城市按原来的顺序排好, 依次放入所选维度之间以外的空缺, 从而产生一个新个体。例如:Xg=ABCDEFGHIJK, Xw=GIKDCAEBFHJ, 选取维度2和维度7交叉后就可以得到新的最差个体IBCDEFGKAHJ。

引入交叉算子的目的是为了充分利用种群中最优个体的优良信息, 加快收敛速度, 交叉操作是否进行由事先设定的交叉概率pc决定。

2.2 变异算子

太快的收敛速度容易导致局部最优。为了保持ISFLA的种群多样性, 避免陷入局部最优, ISFLA中引入了变异算子, 变异操作是否进行由事先设定的变异概率pm确定。

ISFLA中的变异算子包含两种情况:自身反序变异和异体反序变异。在事先设定的自身反序变异概率pms下进行自身的反序变异, 否则进行异体的反序变异。

自身反序变异:在每个子群体的最差个体Xw上随机选择两个维度, 反转两个维度之间的城市。例如:对于GIKDCAEBFHJ, 随机选到的维度是3和10, 变异后得到GIKFBEACDHJ。

异体反序变异:在每个族群的Xw随上机选择一个城市, 在Xg上找到该城市的下一个城市, 在Xw中找到相应的城市, 将它与随机城市的下一个城市之间的城市进行反转。例如:Xg=ABCDEFGHIJK, Xw=GEIKDCAFBHJ, 随机选到的是E, 那么交叉后得到新的最差个体为GEFACDKIBHI。

ISFLA有六个关键参数, 分别是青蛙群体规模P, 每个子群的青蛙数n, 混合迭代次数G, 交叉概率pc, 变异概率pm, 自身反序变异概率pms。

2.3 ISFLA的实现过程

①初始化。

确定参数P, n, G, pc, pm, pms。随机产生P个青蛙个体, 计算所有青蛙的适应度。确定Xg, 迭代次数g=0。

②混合。

根据适应度对所有的青蛙进行排序, 把所有青蛙分配到各子种群, 每个子种群的青蛙数为n。确定每个种群的Xw。

③进化。

更新每一个子种群的最差个体Xw。

一是交叉。如果rand () >pc则跳至步骤二, 否则把Xw与Xg进行交叉操作, 产生新的Xw, 计算其适应度。重新确定Xg与子群体的Xw。

二是变异。如果rand () >pm, 则跳至步骤④, 否则对Xw进行变异:如果rand ()

④判断迭代是否终止。

g=g+1, 如果g

3 实验与讨论

为了验证ISFLA的收敛速度和克服局部最优的能力, 实验部分选用了国际上最通用的TSP测试库TSPLIB中的多个实例作为测试对象。把ISFL与SFLA、GA以及简单翻转 (Simple Inversion, SimInv) [5]进行比较。

为了比较, 这四种对照算法尽可能采用相同的参数设置。种群规模皆为200, 迭代次数皆为20000。在SFLA与ISFLA中, 子种群所包含的青蛙数目为10。ISFLA中交叉概率, 变异概率, 自身反序变异概率分别为0.9, 0.2, 0.9;GA中的交叉概率和变异概率分别为0.9与0.01。

图1是Eil51的最佳路径示意图, 4个对照算法作用于Eil51的30次独立运行平均收敛性能比较如图2所示。从图2可以看出, 自始至终ISFLA都具有明显较快的收敛速度。在算法的初始阶段 (前800代) , ISFLA的优势非常明显, 收敛速度最快, 收敛速度最慢的是SimInv;从800代之后的情况看, 收敛性能最好的还是ISFLA、此时收敛速度最差的是SFLA, 但是GA与SFLA的差别不大。ISFLA对子种群的最差个体与整个种群的最优个体实行交叉操作, 使得新个体很好地继承了最优个体的优良特性, 使得最差个体快速进化, 提高ISFLA的收敛速度。

表1是四种对照算法在每个测试实例上独立重复运行30次的统计平均结果, 从中可以看出:ISFLA在每一个测试实例上都具有较小的均值, 能够找到较短的路径, 而SFLA在每个测试实例上都是表现出最差的性能。相对SFLA, ISFLA更充分地利用了种群最佳个体所包含的信息, 从而表现出了较好的全局寻优性能和克服局部最优的能力。

4 结束语

本文把GA中的交叉和变异引入SFLA, 提出了一种改进的混合蛙跳算法 (ISFLA) , 旨在提高收敛速度和寻优性能。在TSPLIB的实验结果表明ISF-LA的测试结果达到了预期的效果:通过交叉操作, 充分利用最佳个体的优良信息, 提高了算法的收敛速度;同时, 通过两种变异操作, 保持了种群的多样性, 从而改善了局部最优现象。在搜索的过程中, 融入有效的局部搜索策略, 是提高ISFLA优化性能的有效途径。

参考文献

[1]钟伟才, 刘静, 刘芳, 等.组合优化多智能体进化算法[J].计算机学报, 2004, 27 (10) :1341-1353.

[2]王宇平, 李英华.求解TSP的量子遗传算法[J].计算机学报, 2007, 30 (5) :748-755.

[3]Eusuff M, Lansey K, Pasha F.Shuffled frog-leaping algorithm:A memetic meta-heuristic for discrete optimization[J].Engineering Optimization, 2006, 38 (2) :129-154.

[4]Xue-hui L, Ye Y, Xia L.Solving tsp with shuffled frog-leaping algorithm[C].8th International Conference on Intelligent Systems Design and Applications, ISDA 2008, Nov.26, 2008:228-232.

浅谈旅行商问题与粒子群优化算法 第6篇

引入交换算子和交换序是一种改进的粒子群算法去解决旅行商这种离散型问题的方法。这种方法也是粒子群算法应用到离散型问题的第一次尝试。此方法的问世,使得粒子群算法的应用领域发生巨大的改变。

1 基本的粒子群算法

粒子群优化算法首先初始化一群随机粒子,粒子们就追随当前的最优粒子在解空间中搜索。粒子通过跟踪两个极值来更新自己 ;第一个就是粒子本身所找到的最优解,这个解称为个体极值(pbest);另一个极值是整个种群目前找到的最优解,这个极值是全局极值(gbest)。

在找到这两个最优值时,粒子根据如下的公式来更新自己的速度和位置 :

其中ω为惯性权重, c1,c2为学习因子,r1,r2为0到1之间均匀分布的随机数。

2 TSP 问题

在生产生活中许多问题都可以转化为旅行商这类问题的模型,因此旅行商问题具有很高的实际应用价值,例如 :城市管道铺设优化、物流行业中的车辆调度优化等现实生活中的很多优化问题都可以归结为旅行商模型来求解。

TSP问题定义 :设n为城市数 目为n*n阶距离矩阵, 代表从城市i到城市j的距离,i=1,2,...,n , j=1,2,...,n。要找出访问每个城市且每个城市恰好只访问一次的一条Hamilton回路,且其路径的总长度是最短的。

这条Hamilton回路可以 表示为(1,2,...,n) 的所有循环排列的集合,即为 (1,2,...,n) 的排列, 表示访问第i个城市后访问第j个城市。

目标函数(在粒子群算法中也可以叫做适应值函数):城市Hamilton回路总长度为 :

引入决策变量 :

旅行商问题定义非常简单,使用穷举法可以让旅行商得到最优解,但随着需要访问城市数目的增加,会出现所谓的组合爆炸现象。所以,城市数目比较多的时候使用穷举搜索策略几乎是不可能做到的。

3 引入交换算子和交换序的粒子群算法求解 TSP 问题

3.1 引入交换算子和交换序的粒子群算法定义和流程

交换算子 :是用来交换一个有序序列中元素的位置,一个交换算子可以使这个有序序列中两个元素位置发生调换 ;交换序 :一个或多个交换子的有序队列就是交换序。

在上边两个概念基础上再定义几个概念 :

交换序的等价集 :不同的交换序作用于同一解上可能产生相同的新解 , 所有有相同效果的交换序的集合称为交换序的等价集 ;基本交换序 :在交换序等价集中 ,拥有最少交换子的交换序称为该等价集的基本交换序。

在引入交换序和交换序列后基本的粒子群算法的公式(1.1)需要改写,计算符号的含义也需要改变。

粒子速度更新公式改写为 :

粒子的位置更新公式保持原来的基本粒子群算法的公式(1.1),只是加法的含义发生改变,可以改写为 :

算法的步骤 :

(1)初始化粒子群 , 即给群体中的每个粒子赋一个随机的初始解和一个随机的交换序 ;

(2) 如果满足结束条件一般为最大迭代次数 ,

(3) 根据粒子当前位置 Xti, 计算其下一个位置t+1i ,即旅行商问题新的可行解 ;

3.2 实验结果与参数设置

设10个城市的 二维坐标 分布为 :city10=[0.4 0.4439;0.2439 0.1463;0.17070.2293;0.2293 0.761;0.5171 0.9414; 0.87320.6536;0.6878 0.5219;0.8488 0.3609;0.66830.2536;0.6195 0.2634]; 这十个城市的最短Hamilton回路为2.691

当粒子数为40,迭代次数取400, 和都取0.25时测试得到了最优解运行结果如下 :

4 结论

引入交换算子和交换序的改进粒子群算法,对于问题规模比较小的旅行商问题,其算法可以表现出很高的效率。

摘要：基本粒子群优化算法已经成功地应用于求解连续域问题,但是,对于离散域问题求解研究还很少。很不幸旅行商问题恰恰就属于离散问题,因此文章介绍了引入交换序和交换算子的改进粒子群算法,实现了对旅行商问题的求解。

旅行商问题 第7篇

关键词：蚁群算法,旅行商问题,MATLAB

1 意义和目标

旅行商问题是物流领域中的典型问题,它的求解具有十分重要的理论和现实意义。采用一定的物流配送方式,可以大大节省人力物力,完善整个物流系统。

已被广泛采用的遗传算法是旅行商问题的传统求解方法,但遗传算法收敛速度慢,具有一定的缺陷。本文采用蚁群算法,充分利用蚁群算法的智能性,求解旅行商问题,并进行实例仿真。进行仿真计算的目标是,该算法能够找到目前巳知的最好解。

2 国内外研究现状

仿生学出现于20世纪50年代中期,人们从生物进化机理中受到启发,提出了遗传算法、进化规划、进化策略等许多用以解决复杂优化问题的新方法。这些以生物特性为基础的演化算法的发展及对生物群落行为的发现引导研究人员进一步开展了对生物社会性的研究,从而出现了基于群智能理论的蚁群算法,并掀起了一股研究的热潮。

20世纪90年代Dorigo M[1]最早提出了蚁群优化算法蚂蚁系统(Ant system,AS),并将其应用于解决计算机算法学中经典的旅行商问题[2]。从蚂蚁系统开始,基本的蚁群算法得到了不断的发展和完善,并通过TSP以及许多实际优化问题的求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力,它们之间的差异仅在于搜索控制策略方面。而且,通过引入局部搜索算法的ACO取得了最佳结果,这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法,有利于提高蚁群各级系统在优化问题中的求解质量。

Ant density,Ant quantity和Ant cycle是AS的三个版本。在Ant density和Ant quantity中,更新信息素是蚂蚁在两个位置节点间每移动一次后,而在Ant cycle中,更新信息素是在所有蚂蚁都完成了自己的行程后,且每只蚂蚁所释放的信息素被表达为一个函数,该函数反映了相应的行程质量。通过与其他各种通用的启发式算法相比,在不大于75个城市的TSP中,这3种基本算法的求解能力还是比较理想的,但是当问题规模扩展时,AS的解题能力大幅度下降。因此,集中于AS性能的改进方面是其后的ACO研究工作的核心。精英策略(Elitist Strategy)是较早的一种改进方法,其思想是在算法开始后即对所有已发现的最好路径给与额外的增强,并将随后与之对应的行程记为Tgb(全局最优行程)。对这些行程予以加权来更新信息素,同时将经过这些行程的蚂蚁记为“精英”,从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解,但是该算法会较早的收敛于局部次优解,导致搜索的过早停滞。

针对AS中暴露出的问题,Gambardella L M,Dorigo M[3]提出了蚁群系统(Ant colony system,ACS)。该文作者较早提出的Ant Q[4]算法是该系统的基础。Ant Q将蚂蚁算法和一种增强型学习算法Q learning有机地结合了起来,ACS与AS差异主要有3个方面:首先,ACS选择规则的行为更为大胆;其次,只增强属于全局最优解的路径上的信息素,即:

其中Vtgbij(t)=1/Lgb0<ρ<1是信息素挥发参数,Lgb是从寻路开始到当前为止全局最优路径长度。另外,还引入了负反馈机制,每当一只蚂蚁由一个节点移动到另一个节点时,该路径上信息素都按照被相应地消除一部分,进行一种信息素的局部调整,从而减少已选择过的路径再次被选择的概率。

MAX-MIN Ant System[5]是对AS进行直接完善的方法中的一个典型代表。该算法改变了AS的信息素更新方式,每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解。为了避免搜索停滞,路径上的信息素浓度被限制在[τmin,τmax]范围内。另外,信息素的初始值被设为其取值上限,这样有助于增加算法初始阶段的搜索能力。

对AS改进的另一种算法是Rank based Version AS[6],与“精英策略”相似,在次算法中总是更新更好进程上的信息素,选择的标准是其行程长度L1(t)L2(t)...Lm(t)决定的排序,且每只蚂蚁放置信息素的强度通过

式中的排序加权处理确定,其中Vrij1/LrVijgb(t)1/Lgbm为每次迭代后放置信息素的蚂蚁总数。

将该算法求解TSP的能力与AS精英策略、AS遗传算法和模拟退火算法进行比较发现,在大型TSP问题中(最多包含132座城市),基于AS的算法都显示出来优于GA和SA的特性,而且在Rank based AS和精英策略AS均优于基本AS的同时,前者还获得了比精英策略AS更好的解。

吴庆洪[7]等人提出了具有变异特征的蚁群算法。也就是在基本蚁群算法中可引入变异机制,使得该蚁群算法具有较快的收敛速度,提高了算法的运行效率。该算法采用了逆转变异方式,随机地进行变异,以增大进化时所需的信息素。经过这种变异算子作用后,这一代解的性能有明显改善。

针对蚁群算法加速收敛和早熟停滞现象之间存在的矛盾,有研究者提出了一种自适应蚁群算法[8]。这种算法可以在加快收敛和避免早熟、停滞现象之间取得很好的平衡。该算法可以根据优化过程中解得分布平衡度,自适应地调整路径选择概率的确定策略和信息量更新策略。自适应蚁群算法主要有:基于调节信息素挥发度的自适应蚁群算法、具有分工的自适应蚁群算法以及基于协同学习机制的一群算法等[9]。

虽然,蚁群优化算法并不是旅行商问题的最佳解决方法,但是它却为解决组合优化问题提供了新思路,并很快被应用到其他组合优化问题中。本文只探究在经典旅行商问题中的解决方法。对蚁群算法理论的应用方法研究表明,虽然相对于各种比较成熟的计算智能方法来说蚁群算法的研究还处于初级阶段,并存在种种有待深入研究和解决的问题,但是可以预言,群智能[10]蚁群算法的研究将成为计算机研究发展的一个重要方向。

3 算法理论分析

旅行商问题定义:有n个城市和距离矩阵D={dij},其中dij表示城市i到城市j的距离(i,j=1,2,n),目标是要遍历每个城市恰好一次的一条的回路,且其路径长度之和最短。

设有m只蚂蚁,(i=1,,n)是在t时刻城市i的蚂蚁数,为全部蚂蚁数。每只简单蚂蚁有以下特征:

(1)它根据以城市距离和连接边上外激素的数量为变量的概率函数选择下一城市(设τij为t时刻边e(i,j)上外激素的强度)。

(2)规定蚂蚁走合法路线,除非周游完成,不允许转到已访问城市,由禁忌表控制(设tabuk表示第k只蚂蚁的禁忌表,tabuk(s)表示禁忌表中第S个元素)。

(3)它完成周游后,蚂蚁在它每一条访问的边上留下外激素。

初始时刻,各条路径上的信息量相等,设τij(0)=C(C为常数)。蚂蚁k(k=1,2,,m)在运动过程中,根据各条路径上信息量决定转移方向,pkij表示在t时刻蚂蚁k由位置i转移到位置j的概率,

其中,allowedk={0,1,,n-1}-tabuk表示蚂蚁k下一步允许选择的城市,与实际蚁群不同,人工蚁群系统具有记忆功能,tabuk(k=1,2,,m)用以记录蚂蚁k当前所走过的城市,集合tabuk随着进化过程做动态调整。ηij表示边弧(i,j)的能见度,用某种启发式算法算出,一般取ηij=1/dij,dij表示城市i与城市j之间的距离。α表示轨迹的相对重要性,β表示能见度的相对重要性,ρ表示轨迹的持久性,1-ρ理解为轨迹衰减度随着时间的推移,以前留下的信息逐渐消失,用参数1-ρ表示信息消逝程度,经过n个时刻,蚂蚁完成一次循环,各路径上信息量要根据以下公式做调整:

Vτkij表示第k只蚂蚁在本次循环中留在路径ij上的信息量,Vτij表示本次循环中路径ij上的信息量增量,Lk表示第k只蚂蚁环游一周的路径长度,Q为常数。

4 算法的技术路线

求解旅行商问题的蚁群算法的基本步骤如下:

(1)nc←0(nc为迭代步数或搜索次数);初始化τij和Vτij;将m只蚂蚁置于n个顶点上。

(2)将各蚂蚁的初始出发点置于当前解集中;对每只蚂蚁k(k=1,2,,m),按概率Pkij移至下一顶点j;将顶点j置于当前解集。

(3)计算各蚂蚁的路径长度(k=1,2,,m);记录当前的最好解。

(4)按更新方程修改轨迹强度。

(5)对各边弧(i,j),置Vτij←0,nc←nc+1。

(6)若nc<预定的迭代次数且无退化行为(即找到的都是相同解),则转步骤2。

(7)输出目前最好解。

算法的流程如下图:

该算法复杂度为:O(nc˙n3)

5 数据实验及结果

在MATLAB 7.9.0下,实现编码。选用Oliver30(最好解为423.7406)作为实验例子,来实现该算法。

算法的参数设置如下:α(a)=1,β(b)=5,m=6 0,(r)=0.99,Q(q)=1000,C=10,NC=50。对该算法循环调用20次,记录下每次的结果,并计算出平均值,输出这20次的最好解,最差解和平均解。实验记录的结果如下表:

从上面的实验数据看出,本文设计的算法可以达到目前已知的最好解(423.7406)。

6 分析与总结

本文设计了一种基于MATLAB实现的蚁群算法,用以求解组合优化难题中的典型代表旅行商问题。对Oliver30个城市旅行商问题进行了测试,所得结果能达到公布的最优解,实现了本文的研究目标。

经过对旅行商问题的深入理解,得到了能解决问题的基本数学模型,然后设计算法的基本思想,技术路线,最后编码。在多次调试,修改后,本算法成功运行,并实现了最初的设定目标。另外,MATLAB具有丰富的绘图函数,对于绘图十分方便,这是选择MATLAB解决TSP问题的算法编写、调试的原因。

蚁群算法研究处于初期,还有许多问题值得研究,如算法的参数选择、蚂蚁数的比例等只能通过仿真实验,无法给出理论指导。

参考文献

[1]Colorni A,Dorigo M,Maniezzo V.An investigation of some properties of an ant algorithm[A].Proc.Of the Parallel Problem Solving from Nature Conference(PPSN’92)[C].Brussels,Belgium:Elsevier Publishing,1992,509-520.

[2]马良,项培军.蚂蚁算法在组合优化中的应用[J].管理科学学报,2001,4(2):32-37.

[3]Gambardella L M,Dorigo M.Solving symmetric and asymmetric TSPs by ant colonies[A].Proceedings of the IEEE International Conference on Evolutionary Computation(ICEC’96)[C].Nagoya Japan,1996:622-627.

[4]Dorigo M,Gambardella L M.A study of some properties of Ant Q[A].Proceedings of PPSN IV Fourth International Conference on Parallel Problem Solving From Nature[C].Springer,Berlin,1996:656-665.

[5]Stutzle T,Hhoos H.The MAX MIN ant system and local search for the traveling salesman problem[A].In Proceedings of the IEEE International Conference on Evolutionary Computation(ICEC’97)[C].Indianapolis,USA,1997:309-314.

[6]Bernd Bullnheimer,Richard F Hartl,Christine Straub.Anew rank based version of th e a nt syste m a computational study[DB/OL].http://www.wu.wien.ac.at/am.

[7]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法,计算机研究与发展,1999,36(10):1240-1245.

[8]吴启迪,汪镭.智能蚁群算法及应用[M].上海:上海科技教育出版社,2004,3-129.

[9]李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004,1-21.

旅行商问题 第8篇

1 对应连通子图交叉

交叉算子是遗传算法中最重要的部分, 既可以使个体发生变化, 又能保留父体的优秀基因片段, 使种群向着理想的方向进化。对于旅行商问题通常采取自然编码, 即每个基因位对应一个城市的号码。例如1-2-3-4-5-6表示依次经过城市1到6最后回到1。这种编码容易理解, 效率高。但是在这种编码方式下普通的交叉算法就不再适用了, 因为可能产生没有意义的个体。图1中两条可用路径经过交叉操作以后, 产生的1-1-5-6-3-6路径是没有意义的。为了解决这个问题, 很多学者提出了适用于TSP的交叉算子, 像顺序插入法, 启发式交叉等, 但是这些算法会打乱交叉片段中的基因位置因而不能保存父体的优秀基因片段。

基于以上分析, 本文提出一种新的交叉算子:对应连通子图交叉 (CCSC) 。这种交叉方法可以做到严格的交叉, 即子代的基因都是从父代继承所得, 所有基因片段都可以在两个父体中找到。CCSC通过合并两条父体路径, 构造连通图G。对G中的对应连通子图进行搜索, 然后进行交叉, 交叉策略可以是:随机选择某个或若干个对应连通子图进行交换, 还可以采用贪婪选择对每个对应连通子图进行多次搜索, 找到最短个体, 这几种方法时间复杂度都在O (n) 之内, 本文权衡算法效率和求解效果, 决定采用随机选择若干个对应连通子图进行交换的交叉策略。明显可以看出若对应连通子图的个数大于等于1, CCSC就可以创造两个以上的后代个体。若有k个对应连通子图, 则可以产生2k+1-2个个体, 减2是因为有两个个体和父体是相同的。

对应连通子图:合并两条父体路径, 构造连通图G, 在G中, 删除两条父体路径的重合边后, 得到图G1, G1的某个连通子图中的节点在两条父体中均为连续的基因片段, 此连通子图称为对应连通子图。

图2-2中的a-b-c-d, a-c-b-d和g-h-j-i-k, g-i-h-j-k就是两对对应连通子图:

寻找对应连通子图的流程如下:

(1) 删除图G中两条路径重合的边。

(2) 建立队列Q, 把度为1的n个节点放在队头, 设定计数器K=n。

(3) 从队列的n+1个节点开始进行广度遍历, 找出所有连通子图, 把遍历过的点前移, 记录连通子图结点个数ti, 直至所有节点操作完成。

(4) 对结点个数ti大于等于3的连通子图i, 对其父体进行检查如果连通子图的节点在两父体中均为连续的基因片段, 则该连通子图为一个对应连通子图g, 记录g。

(5) 如果符合要求的连通子图都已经搜索就退出程序, 否则返回步骤4。

2 混合遗传算法CHGA的实现

2.1 选择算子

选择算子是算法中关键的一环, 可以选择优秀个体进入下一代进行交叉和变异操作, 本文采用的是轮盘赌法, 根据个体的适应度进行选择, 适应度越大个体被选择的概率就越大, 并且可以保留少量适应度较差的个体, 增加种群多样性。

2.2 变异和交叉算子

变异:本文采用两点随机交换的变异操作对种群进行扰动, 跳出某些局部最优解。

交叉:本文采用第一节提出的对应联通子图交叉作为交叉算子。

2.3 小生境操作

经过轮盘赌选择等操作后, 适应度大的个体更容易进入新种群, 种群里就会出现很多一样或者很相似的个体, 这样就会导致算法早熟, 结果陷入局部最优解, 所以本文引入小生境操作来保持物种多样性。

具体方法是:假设种群共有n个个体, 首先计算个体i (i=1, 2n) 和其他个体之间的小生境距离L (i, j) 。在对个体i与其他所有个体的小生境距离L (i, j) 求和, 计算出个体i的小生境排序值si, 。循环这个步骤直到计算出所有si。升序排列si后, 用随机产生的个体代替si最高的n个个体, 算法的时间复杂度是O (n2) 。

其中L (i, j) 的求法是, 假设TSP共有N个城市, 取个体i的第k (k=1, 2, 3N) 个基因位城市i (k) , 在个体j中找到城市i (k) 的位置t, 对i (k) 和j (t) 左右两边城市号做同或操作:L (i, j) =i (k+1) ⊙j (t+1) +i (k+1) ⊙j (t-1) +i (k-1) ⊙j (t+1) +i (k-1) ⊙j (t-1) 。因为0L (i, j) 2, 所以0si2n。小生境排序值si越大说明个体i周围的个体越多。对种群的非精英个体进行小生境操作, 起到了保留精英又增加种群多样性的作用。

2.4 局部搜索

在CHGA中局部搜索算法起着十分重要的作用。它可以使种群迅速向着希望的方向进化。它的另一个作用是使CHGA算法的第一代开始就能够找到更多的对应连通子图, 提高算法的效率, 本文采用LK算法[4]作为局部搜索。

在本文中局部搜索的另一个作用是使算法的第一代开始就能够找到等多的对应连通子图 (CCS) , 通过实验测试CCSC结合局部搜索算法可以产生的对应连通子图的大致个数, 实验采用TSPLIB中的att532, nrw1379和u1817三个算例, 用3-OPT, 3-OPT和MO-LK算法对50个随即路径进行测试, 平均实验结果如表1。通过实验发现2-OPT与CCSC结合在90%的情况下可以产生可用个体, 也就是至少有一对对应连通子图而, 结合3-OPT和LK算法的CCSC产生可用解的概率达到了将近100%。

3 算例实验

3.1 实验环境

为验证所设计算法的有效性, 基于如下实验环境进行相关实验:联想台式机, 其配置为:

(1)CPU：AMD 64 2X 4400+;

(2) 内存:2 G DDR2;

(3) 操作系统:Windows XP

程序以VC++2008编写及编译, 实验使用数据取自TSPLIB。算法各参数如表1所示。实验结果均为运行算法10次后计算得到的平均值、最优值以及最差值。

3.2 实验参数

3.3 实验结果

本文的算例采用TSPLIB数据库中的Att48、Eil51、Eil76、Kroa100、Ch130、Tsp225、Ch 150等6个测试对象, 每个算例进行20次计算, 结果取平均值, 并与文献[5, 6]进行了对比。具体数据如下:

实验结果表明, 本文所做改进效果明显。100以内规模的问题每次都可以计算出TSPLAB最优解, 而且速度上相比文献所述也有优势。100以上问题在20次实验中可以计算出TSPLAB最优解, 而且平均值的误差也在1%以内。在下一步工作中, 可以着力改善算法的计算速度, 并且向更大规模的问题发起挑战。

摘要：对混合遗传算法解决单目标旅行商问题进行研究, 提出了一种基于对应连通子图交叉的混合遗传算法。本算法还包括初始种群的生成、适应度函数的计算、选择、变异、LK局部搜索和小生境操作。最后通过具体算例的实验和对比表明算法是有效的, 在计算精度和速度上有较大提高。

关键词：混合遗传算法,旅行商问题,对应连通子图交叉

参考文献

[1]Holland John H.Adaptation in natural andartificial systems:anintroductory analysis with applications to biology, control, andartificial intelligence[J].USA:University of Michigan, 1975.

[2]马良.旅行推销员问题的算法综述[J].数学实践与认识, 2000, 32 (2) :156-165.

[3]葛继科, 丘玉辉, 等.遗传算法研究综述[J], 计算机应用研究, 2008, 25 (10) :2911-2917.

[4]Helsgaun K.General k-opt submoves for the Lin–KernighanTSP heuristic[J].Mathematical Programming Computation, 2009, 1 (2-3) :119-163.

[5]孙凯, 吴红星, 王浩, 丁家栋.蚁群与粒子混合算法求解TSP问题[J].计算机工程与应用, 2012, 48 (34) :60-63.

旅行商问题 第9篇

混合蛙跳算法(Shuffled Frog Leaping Algorithm,SF-LA)由Eusuff和Lansey在2003年第一次提出,是一种全新的启发式群体智能进化算法,最初用于解决管道网络扩充中管道尺寸的最小化问题[1]。随后,混合蛙跳算法以自身参数设置少、全局搜索寻优能力强、计算强度小、简单易于实现等优势被国内外学者所关注。目前主要用于解决组合优化问题,如水资源分布安排[2]、电力系统的调度[3]、云计算环境下资源分配问题[4]等。

组合优化问题是从组合问题的可行解中求出最优解。旅行商问题属于一种典型的组合优化问题,是NP难题。旅行商问题的具体描述是:以一个城市为出发点,在N个城市各经历一次,最后回到出发点,使得所经过的路程达到最短。如果不考虑方向性和周期性,则总共存在的闭合路径数目是当N选取的数目很大时,计算量将特别大,在求解最优路径时很困难,因为该问题算法在运行过程中,需要很长的运行时间和很大的存储空间,以至于根本不可能在计算机中得到实现,产生了所谓的“组合爆炸”问题。如果采用传统算法(如穷举搜索算法、贪心算法和动态规划算法等),就会遇到上述问题。现代智能算法的出现解决了上述问题,如遗传算法、蚁群算法、粒子群算法等。鉴于此,本文将采用混合蛙跳算法对旅行商问题进行求解。

本文对旅行商问题使用混合蛙跳算法进行求解并针对混合蛙跳算法存在容易陷入局部最优的问题,使用了贪婪倒位变异对当前的全局最优解进行变异,从而使得混合蛙跳算法跳出局部最优,从而向最优解逼近。使用改进前后的混合蛙跳算法分别对旅行商问题进行仿真实验,验证了改进后算法的有效性。

1 混合蛙跳算法

混合蛙跳算法是模拟青蛙觅食过程中群体信息共享和交流机制而产生的一种群智能算法。算法中每只青蛙被定义为问题的一个解。对所有青蛙进行模因分组,分为不同的子群体,青蛙在分组内共享自身的觅食经验和信息,当分组内信息交换到一定阶段后,再将所有分组混合进行分组间的信息交换。不断重复上述过程,一直向着食物源的位置逼近。混合蛙跳算法按照分组分类进行信息的传递,将这种局部进化和重新混合的过程相间进行,有效地将全局信息交互和局部进化搜索进行相互结合,具有高效的计算性能和优良的全局搜索性能。

混合蛙跳算法的具体描述[5]:

随机生成F只青蛙,当问题维度为d时,第i只青蛙表示为X(i)=(Xi1,Xi2,...,Xid),其评价函数为f(X(i))。按照评价函数的降序对青蛙进行排序,将青蛙分成m个组(子种群),每个组有n只青蛙,则F=m*n。将分组后的第一只青蛙放到第一组,第二只青蛙放到第二组,以此类推,直到放到第m组,如果有剩余青蛙,将第m+1只青蛙放到第m+1组,直到所有青蛙都放到分组中。

整个种群的最优解记作Gb,子种群中的最优解和最差解分别记作Pb、Pw。在子种群中的寻优过程是以对Pb和Gb作为参考,对Pw的位置进行更新,更新公式如下:青蛙的移动距离:

更新后青蛙位置:

其中,rand()为0~1的随机数,Dmax为允许青蛙移动的最大步长。如果更新后Pw(新)要好于Pw(旧),则用Pw(新)代替Pw(旧)。否则,用Gb代替式(1)中的Pb,重新执行对Pw的更新。如果还得不到更好的解,则随机生成一个个体来替代Pw。多次执行上述更新过程,直到更新结果满足约定条件(迭代次数)。当所有子种群更新完成后,再对所有青蛙进行全局混合、排序,继续进行子种群中的更新。反复执行上述过程,直到达到最大迭代次数或者找到最优解。

2 混合蛙跳算法改进

根据文中混合蛙跳算法所描述,在子种群的更新过程中,使用Pb和Gb作为Pw更新的参考。但是在子种群的更新过程中,Pb和Gb的状态是不会改变的,使得每次的更新范围不会超过Pb和Gb,这样算法就容易陷入局部最优。为了能跳出局部最优,可以在Pw得不到更好解的情况下对Pb和Gb进行变异,增加Pw取得更好解的可能性,并能够加速向全局最优解收敛。本文将贪婪倒位变异和模拟退火算法相结合对Gb进行变异。

2.1 更新陷入停滞的判断

由于算法的整个过程是在不断的迭代循环中进行,因而需要判断对Gb进行变异的位置节点,本文使用文献[6]中的群体适应度方差δ2,定义为:

其中,N为种群中青蛙个体的总量,fi是第i只青蛙适应度的大小,favg是所有青蛙适应度的平均值,f是用于限制δ2大小的归一化因子。如果δ2=0说明陷入局部最优,此时需要对Gb进行变异。

2.2 贪婪倒位变异

以个体X={5,8,2,1,3,7,4,6,9}为例,变异方式按照如下步骤执行:

步骤1:随机在X中选择一个坐标点1,选择1左右2和3中距离1远些的坐标2。

步骤2:除去这3个点,从其它点中选出距离1最近的点4。

步骤3:对2和6之间的左边坐标点进行倒位,得到变异之后的X={9,6,4,1,3,7,2,8,5}。

2.2 种群最优解接受准则

文中使用模拟退火算法[7]中的接收准则来判断是否接受通过贪婪倒位变异得到Gb(新)。如果变异后得到的Gb(新)要好于Gb(旧),则接受Gb(新)。否则按照概率s接受Gb(新),其中T是温度。

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

(1)初始解的生成。在旅行商问题中每一只青蛙代表问题的一条可能的访问路径。假设第i只青蛙表示为X(i)=(x1,x2,...,xn),其中x1,x2,...,xn表示需要访问的城市的序列。因此,在生成初始解时,随机生成F只青蛙,用于后续操作。

(2)局部最差解Pw的更新。根据式(1)和式(2),在混合蛙跳算法中对Pw的更新是基于实数的,显然这种方式不能解决旅行商问题,这里使用的是另一种方式对Pw进行更新。例如:局部最优解Pb=(2,3,5,1,4),Pw=(1,3,4,2,5)。则Pw向Pb靠近的过程中要经过两次变换,变换次数记为c=2,第一次由(1,3,4,2,5)变为(2,3,4,1,5),记为S0=(1,2),表示Pw中的1号城市变为2号城市,因为不能有相同的城市出现,相应地Pw后面的2号城市变为1号城市。第二次变换由(2,3,4,1,5)变为(2,3,5,1,4),记为S1=(4,5),变换方式同上。同时,对于式(1)中的随机值rand()的取值,使用r=rand()*c。假设rand()=0.6,此时的变换次数c=2,则r=1.2,对r进行向下取整得r=1,则在对Pw更新时,只使用S0=(1,2)的更新方式。如果得到的r=2,则同时使用S0=(1,2)和S1=(4,5)对Pw进行更新。

其它的求解过程根据混合蛙跳算法,每次执行全局混合、排序后,根据式(3)判断δ2的值,如果δ2=0,则使用贪婪倒位变异对排序后Gb进行变异,并根据2.2中所述的方法对Gb进行更新。

3 实验结果

本文使用TSPLIB中的burma14、bayg29、gr96和ch130作为测试数据,比较混合蛙跳算法改进前后的运行结果,对每组数据分别测试50次,利用平均值进行比较。相应的参数设置如下:蛙跳算法的种群数为200,子种群数为20,子种群的内循环为10次,全局最大进化迭代次数为300。模拟退火算法中的初始温度T0=100 000,终止温度Tf=10,退火系数为0.95。在同样实验条件下对TSP问题进行50次测试并且取平均值进行比较,实验结果如表1所示。

实验结果表明,改进后的混合蛙跳算法不论从最优解的值,还是找到最优解的迭代次数上都要优于改进前的混合蛙跳算法。随着坐标点数的增大,算法所需的迭代次数也在快速增加。当坐标点过大时,例如文中在测试gr96和ch130时,改进前后都在300次的全局最大迭代次数附近得到最优解,说明如果增加全局迭代次数,测试结果会更好。

4结语

本文针对混合蛙跳算法的种群最优解,使用贪婪倒位变异和模拟退火算法对其进行变异和概率接受。实验表明,改进后的算法比未改进的算法更加有效,并且该算法还有改进空间。

摘要：针对混合蛙跳算法在进化过程中容易陷入局部最优的问题,使用群体适应度值判断算法在进化过程中是否陷入局部最优,如果陷入局部最优,则对整个种群的当前最优解G_b进行贪婪倒位变异,如果变异后的G_b(新)要优于G_b(旧),则使用G_b(新);否则,使用模拟退火算法判断是否接受G_b(旧)。通过实验,将改进前后的混合蛙跳算法用于对旅行商问题的求解,并通过对比,验证了改进后的算法较未改进的算法更有效。

关键词：混合蛙跳算法,旅行商问题,组合优化问题

参考文献

[1]EUSUFF M M,LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].American Society of Civil Engineers,2003,129(3):210-225.

[2]EUSUFF M M,LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].American Society of Civil Engineers,2003,129(3):210-225.

[3]代永强,王联国,施秋红,等.改进的混合蛙跳算法性能分析及其在电力系统经济调度中的应用[J].电力系统保护与控制,2012,40(10):77-83.

[4]骆剑平,李霞,陈泯融.云计算环境中基于混合蛙跳算法的资源调度[J].计算机工程与应用,2012,48(29):67-72.

[5]杨淑莹.群体智能与仿生计算[M].北京:电子工业出版社,2012.

[6]吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3):416-420.