一种求解TSP的智能水滴改进算法
2016-04-12张峰
张 峰
(安徽交通职业技术学院 水运工程系，合肥 230051)
一种求解TSP的智能水滴改进算法
张峰
(安徽交通职业技术学院水运工程系，合肥230051)
摘要:智能水滴算法是模拟自然界中水滴群体和它附近环境相互作用，最终形成河道的过程而被研究者提出的一种新兴的智能优化算法。旅行商问题(TSP)是数学当中组合优化问题之一，也是一Non-deterministic Polynomial(NP)完全问题。针对智能水滴算法的缺陷提出了改进的智能水滴算法——具有变异特征的智能水滴算法，并用TSP问题来验证改进算法的可行性和有效性。经过分析发现该改进的算法对比之前的基本智能水滴算法具有很强的全局搜索能力，对顺利找到最短路径解决实际问题具有非常大的意义的。
关键词:TSP问题；智能水滴算法；组合优化；变异特征
1知识准备
随着经济的快速发展，道路负荷日益加重，交通拥挤。人们生产经济利润的提高以及消费者生活水平的提高，都对生鲜农产品的流通提出更高要求，进而就会要求旅行商在众多路线当中选择一条最短路径进行送货，达到消费者的满意度。因此，在很多学科(如计算机科学、运筹学等)中，最短路径问题渐渐成为一个研究热点。
旅行商问题(Traveling Saleman Problem, TSP)是数学当中组合优化问题之一，也属于一完全NP难题(非多项式算法问题)，被广泛的应用在很多领域里，是一种优化问题的集中概括和简化形式[1]。并且还经常用来作为许多种启发式算法的间接性的比较标准，所以我们一般在TSP上来验证某种算法的性能，假如能够得到比较好的性能，则在别的相似的优化组合问题上往往也能取得到很好的结果。
1932年K.Menger提出TSP问题，该问题是求解最小路径成本问题，可以描述为一旅行商从起始点出发，遍历所有已知给定的需求点之后，最终再回到起始点的最小路径成本[2-3]。许多数学家对其产生了兴趣，但是到目前为止，还未找到最好的求解方法，一直还处在研究当中。Shah-Hosseini于2007年第一次使用智能水滴算法解决TSP问题，接着于2008年提出针对TSP问题改进的智能水滴算法，并利用因特网上的TSP库TSPLIB95进行验证，结果说明智能水滴算法能够较好地接近最优解[4]。2009年Hamed Shah Hosseini阐述了一种自然群智能算法——智能水滴算法；Iman Kamkar等人在2010年使用智能水滴算法解决VRP问题[5]；2012年，我国学者张宏滨用智能水滴算法解决了在通信中的问题；2013年，周季华,叶春明研究了智能水滴算法置换流水线调度问题[6]；2014年，马竹根对智能水滴算法做了研究综述。然而在国内还没有学者用智能水滴算法解决TSP问题[6]。
早期的研究者在求解TSP问题时经常使用经典算法，但是随着问题规模(走访的城市增多)的增大，用经典算法解决此类问题就会变得很棘手，求解此类问题所需要的时间相应的就会很长。所以，在随后的研究中，学者重点研究近似算法或启发式算法在TSP问题中的应用。由于群智能算法(遗传算法、蚁群算法等)的群体搜索能力很强，但是此类算法可能会陷入搜索局部最优解得问题，有可能不能找到全局的最优解。鉴于以上原因，许多学者为了克服这个缺陷，常常将局部搜索算法和群智能算法结合研究出更高效的混合算法，克服以上算法的缺陷，采用相结合的算法求解TSP问题。本文介绍了组合优化算法的一种新的求解法——智能水滴算法。因智能水滴算法存在的缺陷以致在解决大规模旅行商问题时会使其处理的速度下降，本研究针对智能水滴算法在求解实际问题方面的缺陷进行修正，用TSP问题来验证改进算法的可行性和有效性。对顺利找到最短路径解决实际问题具有非常大的意义的。
(1)
一般地，TSP的数学模型可以描述为
(2)
(3)
(4)
式 (1)表示的是距离之和，式(2)约束旅行者恰好从城市i走出来，式(3)约束旅行者恰好进入城市j一次，式(2)、(3)结合一起代表任何一个城市仅被访问一次，式(4)中的决策变量xij=1表示旅行者走访的路线包括城市i到城市j的路径, xij=0表示旅行者没有选择走访从城市i到城市j的路径。
2一种改进的TSP问题智能水滴算法
2.1智能水滴算法的基本模型
智能水滴(IWD)具备两个重要的属性：我们一般用soil(IWD)表示水滴本身携带的泥土量，用velocity(IWD)表示水滴向前流动行进时本身具有的速度。在工程问题中，我们亟待解决的问题可以用智能水滴流动时周围的环境替代，而我们解决工程问题找到的最优路径可以用相互作用智能水滴寻找的最短路径替代，在寻找最优路径的过程中，智能水滴具有的两项重要属性即soil(IWD)和velocity(IWD)是不断变化的[9]。
以TSP为例说明Shah-Hosseini等人提出的水滴群系统(Intelligent Water Drop)模型，在TSP中，目标是极小化
(5)
其中，d(Cx,Cy)代表两城市x、y之间的路程。设bi(t)代表t时刻处在城市i的水滴数量，soilij(t)代表t时刻路径(i,j)上的泥土量浓度，n为TSP规模，m为水滴群中水滴的总数目，即
在初始时刻各条路径上泥土量浓度相等，设soilij(0)=C，C为常量。水滴k(k=1,2,…m)在行进过程中，其转移方向依据各条路径上的泥土量浓度来决定。而水滴k当前所走过的城市用禁忌表tabuk(k=1,2,…,m)来记录，集合随着tabuk进化过程不断地作出调整。在搜索过程中用每条路径上的泥土量浓度来计算状态转移概率。为了避免残留泥土量过多引起残留泥土量所启发的信息被淹没。由此，城市t+n时刻在路径(i,j)上泥土量可按照如下规则进行调整[9]。
soilij(t+n)=ρ0*soilij(t)+ρn*Δsoilij(t)
(6)
式中：ρ0代表信息素挥发系数，则ρn=1-ρ0代表信息素残留因子，为了防止信息的无限积累，规定：ρ0⊂[0,1]。
2.2改进智能水滴算法的提出
2011年，M.E、L.ThangaMariappan M.E和D.ArunShunmugam M.E提出一种改进的智能水滴算法用来解决TSP问题，它与先前的智能水滴算法的不同之处在于改进的算法在水滴移动搜索最短路径时，不仅局部对路径之间的泥土量进行了更新，而且对所有水滴遍历整个节点后，所有节点之间泥土量都进行了全局的更新变化，其表达式如下：
(1)智能水滴算法改进的思想。
提出了一种改进的算法——具有变异特征的智能水滴算法。
设某滴水滴所走线路可以表示为：
如果满足：
与智能水滴算法中的迭代过程相比，变异的这个过程用到的运算量更为简便，因此在运算量上减少了时间，并且目前的最优解的性能在这种变异算子作用后，便得到明显的改善，进而使整个群体的性能得以提高，节省了时间，提高了算法的收敛速度。此部分的算法可以用伪代码表示为begin，初始化;
ncycle=0;
bestcycle=0;
soil(i,j)=C;
Δsoil(i,j)=0;
tabuk={};
while(not termination condition)
{
ncycle=ncycle+1;
for(index=0:index /* index 表示已走城市的个数*/ 选择城市j; 将最好的路径和最好的结果输出 把以上两种改进算法的核心思想相结合，可知改进的算法不仅可以将基本智能算法的收敛速度得以提高，而且还能搜索到全局最优解，提高解的质量。 (2)改进智能水滴算法求解TSP步骤。 第一步：静态参数的初始化。可定义水滴的数量NIWD是一个正整数，并且一般情况下，与城市的个数Nc相等。对于速度变化的参数av,bv,cv，可定义av=1，bv=0.01，cv=1。对于泥土量的更新参数as,bs,cs，可定义as=1，bs=0.01，cs=1。局部泥土量更新参数ρn=0.9，全局泥土量更新参数ρIWD，一般在[-1,0]区间内取值，令ρIWD=-0.9.另外，初始状态下得每两个城市之间的泥土量初始化为InitSoil=1000，初始状态下的水滴本身具有的速度初始化为InitVel=4。这个最优解TTB被定义为q(TTB)=-∞，最大迭代次数用itmax表示[10-12]。 第二步：动态参数的初始化。对于每一个水滴，一个被访问过的节点Vc(IWD)被放在一个空的矩阵中的，用Vc(IWD)={},每一个水滴的初始速度定义为InitVel和每一个水滴本身携带的泥土量定义为0. 第三步：对于每一个水滴，它们都是自由选择下一个节点。 第四步：对被访问过的节点，我们要更新禁忌表tabulist={}，被访问过的节点要依次加进这个表格中。 对任一水滴而言，从节点i走到节点j，其更新水滴具有的速度，其表达式为： 这里velIWD(t+1)是水滴更新过的速度。计算此时两个节点之间减少的泥土量Δsoil(i,j) 此式中的 第六步：找出最优解(即最短路径) 第七步:设某滴水滴所走线路可以表示为 然后引入变异机制，并运用2-opt简便高效的特点，来代替水滴群的多次迭代循环来寻找最优解，这样的变换可以节省时间，加快收敛速度。如果满足： 进行的主要的操作为：Inversion(S1,S2,Inversion)。 3仿真实验 为了说明此改进的算法具有实用性和可操作性，选用一组城市，它们的坐标见表1。为了方便，在此选用简单的TSP模型，应用10个点之间坐标。先创建一个二维坐标轴。在坐标轴上恰当的选择10个点，描绘10个城市。将这10个点所在坐标轴的坐标分别给出。以备主函数调用文本文件中点得坐标的坐标轴位置进行计算两个之间的路径距离建立个表格，如表1所示。 表1 城市坐标 运用MATLAB编程，参数选用av=1，bv=0.01，cv=1。对于泥土量的更新参数as,bs,cs，定义as=1，bs=0.01，cs=1。InitVel=4，InitSoil=1 000。通过计算机仿真，得出实验结果如下所示： tabu_list = 8 910 1 3 2 4 5 6 7 3 210 9 8 7 6 5 4 1 2 3 110 9 8 7 6 5 4 10 9 8 7 6 5 4 1 3 2 910 7 8 6 5 4 1 3 2 6 7 8 910 1 3 2 4 5 7 8 910 1 3 2 4 5 6 5 4 1 3 210 9 8 7 6 4 5 6 7 8 910 1 3 2 1 3 210 9 8 7 6 5 4 2 3 110 9 8 7 6 5 4 10 9 8 7 6 5 4 1 3 2 5 4 1 3 210 9 8 7 6 4 5 6 7 8 910 1 3 2 1 3 210 9 8 7 6 5 4 8 910 1 3 2 7 6 5 4 6 7 8 910 1 3 2 4 5 910 1 3 2 4 5 6 7 8 3 210 9 8 7 6 5 4 1 7 8 910 1 3 2 4 5 6 4 8 910 7 6 5 1 3 2 7 8 910 1 3 2 4 5 6 910 1 3 2 4 5 6 7 8 8 7 6 5 4 1 3 210 9 2 3 110 9 8 7 6 5 4 10 9 8 7 6 5 4 1 3 2 3 2 110 9 8 7 6 5 4 6 7 8 910 1 3 2 4 5 5 4 1 3 210 9 8 7 6 110 9 8 7 6 5 4 3 2 5 6 7 8 910 1 3 2 4 shortest_path = 10 9 8 7 6 5 4 1 3 2(见图1) shortest_length = 270.273 2(见图2) 从上面的结果可以看出，这几个城市的最短路径为270.273 2，依次遍历的城市为 J→I→H→G→F→E→D→A→C→B 图1 表示改进水滴算法迭代3次遍历10个城市的轨迹 图2 表示改进水滴算法迭代3次搜索10个城市最短路径的收敛性 仿真实验表明：改进的算法相比基本算法而言，它总是可以找到可以实现并最优化的路径，但基本的智能算法无法实现这一点；改进的算法在收敛速度以及求最优解方面比基本的智能水滴算法更有效，并且该算法使求最优解的能力进一步加强，防止算法陷入局部最优。 当城市的规模问题小的时候，改进的算法较最初算法的收敛快的优势表现的并不明显，即最原始的算法就可以解决城市规模较小的最短路径问题。但当城市的规模相当大时，改进的算法的优势就会展现出来。 4研究结论 智能水滴算法是模拟自然界中水滴群体和它附近环境相互作用最终形成河道的过程而被研究者提出的一种新兴的智能优化算法。在工业、农业、科研等领域都有该算法的广泛应用。本文针对智能水滴算法的缺陷提出了改进的智能水滴算法——具有变异特征的智能水滴算法。为了证实该改进的智能水滴算法的有效性和可行性，本文将改进的智能水滴算法在实际问题中加以运用，用TSP问题来验证改进算法的可行性和有效性。选用了一个10个城市规模的问题，用水滴算法和改进的水滴算法进行求解[12]，得出在问题规模较小时，两种算法寻找的最优解一样，所需要的时间几乎没有差异，改进的水滴算法没有发现出很大的优势。经过分析，该改进的算法对比之前的基本智能水滴算法具有很强的全局搜索能力，对顺利找到最短路径解决实际问题具有非常大的意义的，大大地提高了算法的收敛速度。 参考文献： [1]孙亦冰. 基于实时路况的城市道路动态路由研究[D].武汉: 华中科技大学控制科学与工程系,2009. [2]刘云翔.最短路径分析及GIS/GPS集成技术研究[D].长沙: 国防科学技术大学信息系统与管理学院,2002,1. [3]Hamed Shah-Hosseoni.Intelligent Water Drops Algorithm: A New Optimization Method for Solving the Multiple Knapsack Problem[J].International,2008,1(2): 193-212. [4]劳眷.TSP问题中的蚁群优化算法研究[D].长沙: 湖南大学计算机与通信学院,2007. [5]李洪海.基于移动机器人的双目立体视觉技术研究[D].南京: 南京航空航天大学自动化学院,2011. [6]马竹根.智能水滴算法研究[J].怀化学院计算机工程系,2014(6): 964-968. [7]胡中功,李静.群智能算法的研究进展[J].控制理论与应用,2008(2): 13-15. [8]Kamkar I,Akbarzadeh-T M R,Yaghoobi M.Intelligent Water Drops a New Optimization Algorithm for Solving the Vehicle Routing Problem[C]//Systems Man Cybernetics(SMC),2010 IEEE International Conference on IEEE,2010: 4142-4146. [9]周季华,叶春明,盛晓华.基于智能水滴算法置换流水线调度问题的研究[J].计算机科学,2013,40 (9): 250-253. [10] 李至立.船舶制造车间作业管理系统设计与实现[D].黑龙江: 哈尔滨工业大学计算机与科学技术学院,2011. [11] 李翼.物流中心选址问题的分支定界法研究[D].山东: 山东科技大学数学与系统科学学院,2012. [12] YANG Fan.A Study on the Intelligent Water Drop Based Routing Technique for Mannet[D].Beijing: Beijing University of Posts and Telecommunications，School of Information and Communication Engineering,2011. [责任编辑：张永军] An Improved Algorithm to Solve TSP Problem of Intelligent Water Droplets ZHANG Feng (Department of Water Engineering, Anhui Communications Vocational & Technical College,Hefei 230051,China) Abstract:the intelligent water drop algorithm is a new kind of intelligent optimization algorithm, which put forward by researchers.It is because that this algorithm simulates the interaction between water droplets in nature and its environment,and eventually forms the river. Traveling salesman problem (TSP) is one of the combination optimization problems in mathematics, and it is also a complete problem of NP. In this paper, an improved intelligent water drop algorithm, which has the characteristic of variation, is proposed to improve the intelligent water drop. The feasibility and effectiveness of the improved algorithm is verified by using TSP. Through the analysis, it is found that the improved algorithm has a strong global search ability, and it has a very large significance to the smooth path to solve the actual problem. Key words:TSP problem; intelligent drop algorithm; combination optimization; variation characteristic 中图分类号：TP301.6 文献标识码：A 文章编号：1673-162X(2016)01-0023-07 作者简介：张峰(1981—)，男，安徽萧县人，安徽交通职业技术学院水运工程系讲师，硕士；研究方向：基础数学、计算数学。 基金项目：：2016年高校优秀青年人才支持计划重点项目(编号gxyqZD2016484)阶段性成果。 收稿日期：2015-10-05修回日期：2015-12-20
