求解动态TSP问题的化学反应算法研究

来源:用户上传      作者:

　　摘要：旅行商问题（TSP）是经典的NP难问题，节点可变的TSP问题被称为动态旅行商问题（DTSP）。通过研究化学反应算法（CRA），并对CRA算法并行化实现，能够解决DTSP问题。实验结果表明，CRA算法能够有效地处理快速变化的DTSP问题，且性能不亚于其它元启发式算法。
　　关键词：动态TSP问题;迁移算子;CRA并行实现
　　中图分类号：TP301 文献标识码：A 文章编号：1007-9416（2019）11-0115-02
　　0 引言
　　经典TSP问题的描述十分简单：给定一个城市列表以及每两个城市之间的距离，任务是找到一条最短路线，该路线要不重复地访问每个城市节点一次。TSP问题是人工智能的经典问题之一，CRA算法是用来解决TSP问题的启发式算法之一[1]。经典TSP问题在现实生活中的应用其实非常有限，因为在很大部分的TSP问题应用场景中，节点之间的距离是变化的。这种节点间距离会变化的TSP问题被称为动态TSP问题。动态TSP问题的解决远比静态TSP问题更复杂，CRA算法具备求解动态TSP问题的可行性。
　　1 DTSP-动态旅行商问题
　　TSP问题的描述虽然简单，但却是典型的NP难问题。暴力求解TSP问题的时间复杂度是O（n！），其中n是城市（节点）的数量。已知的精确算法可以将时间复杂度降为O（n22n）[2]，但對于更大的n而言，仍然需要更优的启发式算法。
　　1.1 DTSP的相关工作
　　Psaraftis提出了DTSP问题，在文献[3]中他论证了DTSP的一般属性和一些有用的性能指标，但未提出任何能够解决DTSP问题的具体方案。节点的变化会改变原有的距离，使得原有的搜索序列基本无效。因此，许多尝试解决DTSP问题的方法都使用了全局或者局部搜索重置策略[4]。全局重置策略只要检测到更改，就会激活全局重置，将所有搜索序列重置为默认值。局部重置策略仅更改节点群的动态变化区域的搜索序列，使得节点群至少有一部分之前收集的路线是可以利用的。节点发生变化的时间和地点是DTSP问题的已知条件，必不可少。
　　上述方法有一个主要的缺点是引入动态的方式。距离数组的更改仅由单个节点的删除、引入或一系列此类操作组成，并且以规律的间隔激活。因此，节点群可以保持其之前大部分的解决方案不变，因为节点间距离变化的影响是有限的。实际上，很多场景下节点的变化是比较大的。
　　因此，引入分子结构来替代不断变化的动态节点，通过CRA算法来测量最短路线，并对CRA算法在DTSP问题上的性能进行测试和评估。
　　1.2 分子结构
　　在CRA中，用分子结构来模拟每一个解，分子结构的势能就是一条路线，势能的最小值就是问题的最优函数解。
　　每次节点变化都会形成新的分子势能，也就是新的路线，该路线的距离求值操作由以下三个参数控制：
　　（1）总改变（ALL）：所有变化节点间距离的总和，是一个> 0的实数;（2）改变率（ROC）：变化节点的限制参数，是一个范围为[0，1]的实数;（3）改变频率（FOC）：每次变化之间的间隔，以毫秒为单位。
　　根据节点随机变化前的分子结构，和变化后的分子结构，容易得到距离公式1和距离公式2。
　　Dnew=Dold+（1-Dold）*rand（）*ROC                      （1）
　　Dnew=Dold-Dold*rand（）*ROC                         （2）
　　函数rand（）生成范围为[0，1]的随机数。节点变化后的距离与之前距离基本始终处在同一范围内，只要所有距离修改的总和不超过ALL，更新节点的过程就会继续。
　　2 CRA For TSP
　　化学反应算法的灵感来自于现实世界中分子与分子之间产生的化学反应，而将CRA用于TSP是元启发式算法的选择之一。
　　2.1 TSP CRA的基本版本
　　GA、CRA和其他相关的启发式算法的操作很简单：由实数构成的二维数组表示一个图，其中的距离代表两个城市/节点之间的距离，于是可以得到一个初始的分子结构。启发式算法的工作都采用迭代方式。经典GA算法是模拟自然界生物进化的演变而总结出来的算法，其主要过程由初始群体的逐代进化，即上一代进化成下一代，代代相传，最后得到最优一代的过程。GA的每代进化操作主要有三个，选择、交叉和变异：选择操作主要是选择当前区域里的较优解，即局部优化，慢慢向最优解靠近;交叉主要是产生最优解;变异主要是跳出局部最优，覆盖其它区域的解。CRA算法的迭代操作主要由4个反应组成：撞墙、分解、交换和合成。撞墙反应与GA算法中的变异操作类似，但是撞墙反应在CRA中的作用不一样，目的是继承原分子的优秀势能并向局部最优逼近;交换反应与GA算法中的交叉操作类似，目的是产生最优解;分解和合成的目的都是逃离局部最优，扩大解的覆盖面。CRA算法中有2个步骤进行了全局覆盖，因此CRA算法相对于GA算法应该具备更高的全局搜索能力，取得全局最优解的概率较GA算法高。提高CRA算法性能的关键因素在于提高四个基本反应的效率，优化发生化学反应的方法[5]。
　　选择CRA四个反应的算子参数并非易事。例如，在文献[6]中可以找到它们对CRA操作的影响分析。对于当前的研究，足以知道最大的改进可能会在早期迭代中发生。节点选择需要许多浮点计算，因此非常耗时。对于动态TSP，可用于交付解决方案的时间是至关重要的因素。因此，引入了并行的化学反应优化算法。 　　2.2 并行的CRA算法
　　将CRA算法改写成适用于多处理机的算法是非常直截了当的。大概有两种方法可以值得使用：
　　（1）让每个处理器独立地运行于分子集合的一个隔离子代上，通过迁移与其它处理器周期地共享它的那些最优分子。
　　每个处理器首先独立地生成它自己的初始分子集合。然后每个处理器對第k代分子集合进行适应性的评估，根据评估结果从它的第k代分子集合中选择优秀个体以用来生成第k+1代分子集合，在它的第k+1代分子集合上完成撞墙、分解、交换和合成计算。在经历上述k代后（k>=1），这些处理器就与其它的处理器通过迁移算子（migration operator）共享它们的最优分子。
　　当将迁移结合进来后，分子集合的变化就不再仅仅是由于继承其父代的基因造成的，偶尔也会有随机突变所造成的，以及引入新的品种所造成的。在CRA算法中，迁移算子要负责的任务是在分子集合间实现个体的交换。
　　在并行环境中，从每个分子集合中选择最优的分子进行迁移，并将已接收的分子融合到集合中以替代最差的分子将导致更快的收敛。所以通过从一个分子集合中拷贝一些较优的分子到另一分子集合以代替最差的分子将会达到更快的收敛。但是，以这种方式进行选择和融合最终将对分子集合施加太多的选择压力，从而可能阻碍最优解的生成。此外，如果选择压力过大的话，可能使结果的引进趋向局部优化而非全局优化。
　　（2）第二种方法让每个处理器在一个公共的分子集合上完成算法中的每一步的一部分——撞墙、分解、交换和合成。因此，至少需要一个4核CPU或者能提供4个同时进程的处理器才能实现该算法的并行化。
　　3 实验
　　在实验过程中，使用了两个城市节点群，一个节点群的节点在距离上发生了较大变化（CityBC），另一个节点群的节点发生了较小的变化（CitySC）。但是它们有一个共同点：具有相同的初始节点数50个，总改变（ALL）等于20，改变频率（FOC）等于2s。
　　唯一的区别是它们的改变率ROC。CitySC等于0.15，CityBC等于0.35。取距离变化修改的平均数，CitySC是380，CityBC是850。这意味着CityBC几乎改变了总距离的一半以上，节点变化比较频繁。CitySC的距离变化量较少，因为变化的节点较少。
　　表1显示了节点动态变化大的节点群（CityBC）和节点动态变化小的节点群（CitySC）的CRA算法的性能对比。CityBC的节点变化数从2到15，改变率10%到30%;CitySC的节点变化数从1到8，改变率1%到8%。迭代次数50或者100。从时间和结果来看，迭代50次的算法运行时间明显小于迭代100次的，但是差距不大。节点变化大的节点群，算法运行速度慢于节点变化小的节点群。
　　4 结论
　　近来，化学反应优化算法备受关注。本文用它来解决动态旅行商问题。实验结果有力地表明，化学反应算法能够有效地处理快速变化的城市节点群。它的性能不亚于标准GA。
　　还有很多方面需要进一步研究，例如：迭代次数、可变性与CRA算法的密切相关性;最优解的精度即结果的误差等。这些主题的研究工作目前正在进行中。
　　参考文献
　　[1] Albert Y.S.Lam，Victor O.K.Li.Chemical-Reaction-Inspired Metaheuristic for Optimization，Evolutionary-Computation[J].IEEE-Transactions-on Evolutionary Computation，2010，6（3）：381-399.
　　[2] Michael Held，Richard M.Karp.A dynamic programming approach to sequencing problems[J].Journal of the Society for Industrial and Applied Mathematics，1962，10（1）：196-210.
　　[3] Psarafits，H.N. Dynamic vehicle routing： status and prospects[J].Annals of Operations Research，1995，61（1）：143-164.
　　[4] Guntsch，M.，Middendorf，M.Pheromone modifcation strategies for ant algorithms applied to dynamic TSP[J].Applications of Evolutionary Computation，2001，2037（6）：213-222.
　　[5] 欧阳陈华.求解TSP问题的化学反应优化算法研究[D].湖南大学，2014.
　　[6] 黄丹青.基于混合化学反应优化算法的序列比对研究[D].湖南大学，2014.
转载注明来源:https://www.xzbu.com/8/view-15117062.htm