文摘
我们提出一个新颖的启发式算法基于先进和谐的方法搜索和蚁群优化(AHS-ACO)有效地解决旅行商问题(TSP)。TSP,总的来说,是众所周知的一个np完全问题,其计算复杂度增加的数量呈指数增长的城市。在我们的算法中,蚁群优化(ACO)是用来搜索解空间中的局部最优,其次是和谐的使用搜索逃离局部最优由ACO,走向全球最佳。实验来验证我们的算法的效率,通过与其他算法进行比较和TSPLIB中提出最佳解决方案。结果表明,我们的算法可以生成最优解TSPLIB中大多数情况下;此外,我们的算法在两种情况下,找到更好的解决方案(kroB100和pr144)相比,最优解TSPLIB中。
1。介绍
旅行商问题(TSP)是一个典型的例子一个np完全问题的计算复杂性理论,可以理解为“用最小成本最大利益”,搜索最短闭之旅,访问每个城市一次,只有一次。众所周知,TSP属于np完全问题的家庭。一般来说,当解决这种类型的问题与整数规划(IP),确定最优解是不可能的,因为计算时间搜索解空间随着问题规模呈指数增长。因此,一般方法包括确定算法的解决方案在一个合理的时间内通过应用metaheuristics。在过去的十年中,TSP已经被许多metaheuristic研究方法,如遗传算法(GA)、模拟退火(SA)、禁忌搜索(TS),蚁群优化(ACO),粒子群优化(PSO),和谐搜索(HS),布谷鸟搜索(CS)和萤火虫算法(FA)。在这些方法中,遗传算法的一般程序,SA和TS已经介绍了很多文章1- - - - - -3]。算法是一种metaheuristic方法所启发的蚂蚁的行为寻找他们的食物来源4- - - - - -7]。进行算法最初是归因于肯尼迪和埃伯哈特(8),最初是用于模拟运动的社会行为作为一个程式化表示生物的鸟群或鱼的学校。商品,提出Geem et al。9,10),是一种即兴创作的灵感来自于metaheuristic音乐家的过程。CS是仿照的专性育寄生产卵布谷鸟物种在其他鸟类的巢(其他物种)11]。FA metaheuristic算法是模仿萤火虫的闪光行为(12]。Freisleben和梅尔兹(13意识到GA通过使用一个新的变异算子的Lin-Kernighan-Opt寻找高质量的解决方案在合理的时间内不对称TSP。王,田14]介绍了改进的模拟退火(ISA),这是基本的集成模拟退火(BSA)四个顶点和三行不平等来搜索最优哈密顿回路(OHC)或near-OHC。Fiechter [15)提出了大型茶匙的TS获取算法的解决方案。卓越的想法他的研究是,虽然TS寻求解决方案的全球质量高,几个独立执行的本地搜索在TS搜索没有多少质量的损失。Stuzle和呼!16]提出最小不等式蚂蚁系统,证明了他们的算法可以显著提高性能的一般蚂蚁系统在大多数情况下讨论了TSP的例子。王等人。17)设计一个先进的算法与交换算子和交换序列的概念,表现出良好的结果在一个小型TSP有14个节点。Geem et al。920个城市TSP)海关申请解决。他们结合两个运营商(邻近的城市去和city-inverting运营商)内HS迅速到达全局最优。两家运营商之一是能够找到最近的城市,参观了当前城市之后。另一种是用于生产一个新的路径通过交换两个节点随机选择的顺序在一个可行的路径。欧阳et al。18]介绍了先进的CS“search-new-nest”和“研究”运营商,来源于“inver-over”算子的概念解决球面TSP。他们的实验表明,CS / GA HA30从TSPLIB提供更好的解决方案。Kumbharana和Pandey19实现FA和证明了它比算法提供了更好的解决方案,GA和SA在大多数情况下TSP的例子。许多文章前面提到的例子的应用只有单一metaheuristics或metaheuristic本地搜索。
然而最近,来补充单一metaheuristics的弱点,少数研究涉及两个或两个以上的杂交引入了启发式。彭日成等人提出的组合算法与模糊理论解决TSP。在他们的研究中,模糊矩阵被用来代表粒子的位置和速度的算法,和原来的算法公式符号和运营商重新定义了转换成模糊矩阵的形式(21]。护送和Balasubramanie22]介绍了遗传禁忌搜索算法,结合启发式遗传算法的动态切换和TS。实验结果表明,该组合在各自的个人更好的解决方案使用GA和TS。燕等。23]介绍了混合启发式算法解决TSP。在他们的算法,SA和ACO涨跌互现,获得改进的性能。TSPLIB相比之下,他们认为混合形式比(a)原算法在收敛速度和极大极小蚂蚁系统和(b) SA收敛于最优解的概率。陈和简24]介绍了并行遗传算法求解TSP。他们证明了改进的解决方案在三个案例TSPLIB的楚et al。25与原算法。陈和简26]提出的结合四个metaheuristics (GA、SA、算法和PSO)获得一个更好的解决方案在TSP。他们的实验测试相结合的四个metaheuristics用25 TSPLIB的数据集和证明,它提供了更好的解决方案通过一个比较与先前发表四篇文章。根据回顾许多文章关注的组合两个或两个以上的启发式发表自2006年以来,海关和其他启发式求解TSP的组合很少研究。因此,在本文中,我们提出了杂化HS和算法解决TSP。节4,我们的算法将详细介绍。本文的其余部分组织如下;节2介绍配电网和HS的简单概述。节3,我们描述了先进的HS求解TSP,和我们解释整个过程的算法部分4。节5,实验描述TSPLIB的20个数据集执行,结果我们的算法和别人比较的情况下参与TSPLIB 11实例。最后,结论部分提供6。
2。蚁群搜索优化和和谐的概述
2.1。蚁群优化
蚁群优化(ACO),最初提出的民宿,(4)是一种stochastic-based metaheuristic技术,使用人工蚂蚁找到解决组合优化问题。算法的概念是找到更短的路径从巢穴到食物来源。蚂蚁存款一种叫做信息素的化学物质使其它蚂蚁之间的沟通。一只蚂蚁的旅行,存款一个常数其他蚂蚁的信息素量可以遵循。每只蚂蚁有些随机的方式移动,但是当一只蚂蚁遇到一个追踪信息素,它必须决定是否跟随它。如果蚂蚁沿着小径,蚂蚁的信息素增强现有的轨迹,和增加信息素的增加的概率下蚂蚁选择路径。因此,蚂蚁,旅行路径越多,后来的蚂蚁的路径变得更具吸引力。此外,蚂蚁使用短路线食物来源将回到鸟巢。随着时间的推移,随着越来越多的蚂蚁能够完成短路线,短路径上信息素积累更快和更长的路径不强化。信息素的蒸发也让不理想的路线更难以检测和进一步降低其使用。 However, the continued random selection of paths by individual ants helps the colony discover alternate routes and ensures successful navigation around obstacles that interrupt a route. ACO, thus, is an algorithm that reflects the stochastic travels of ants by the probability, the evaporation, and the update of pheromone over time. ACO is composed of the state transition rule, the local updating rule, and the global updating rule. Based on the state transition rule as expressed in (1),蚂蚁之间移动节点。考虑 在状态转换规则,节点之间距离的倒数吗和。蚂蚁意味着节点的集合在节点可以在下次访问。,参数确定的相对重要性信息素和距离的节点,分别。
当蚂蚁访问他们的节点通过状态转换规则,更新信息素的局部更新规则。它可以表达的
信息素的蒸发系数是一个十进制数在0到1的范围。是初始信息素的量。在这里,意味着城市的数量是由最近邻启发式成本。毕竟蚂蚁访问了所有城市,全局更新规则执行 在哪里是恒定的,是全球最好的旅游。ACO算法的总体结构可以描述如下,和图1显示了ACO算法的流程图。
步骤1。初始化信息素表和ACO参数。
步骤2。蚂蚁随机分配到每一个节点。每个蚂蚁都必须移动到下一个城市,根据概率分布。
步骤3。局部信息素更新执行。
步骤4。如果所有蚂蚁没有通过所有的城市参观,去一步2。
第5步。计算最优路径和全球信息素的更新。
步骤6。如果停止标准不满意,去一步2。
2.2。和谐搜索
和谐搜索(HS)是一个metaheuristic算法,模拟即兴创作的音乐播放器和过程非常成功在各种各样的优化问题9,10]。在HS算法,奇妙的和谐,审美标准,音高的仪器,和每个实践在全球最佳表现商品的过程表明,目标函数,变量的值,分别在每个迭代优化过程。HS是由优化运营商,如和谐内存(HM)和谐内存大小(HMS)和谐内存考虑率(HMCR)和音高调整率(PAR)。
商品是由以下步骤,HS算法的总体流程图如图2。
步骤1。初始化HM和算法参数。
步骤2。从HM即兴创作一个新的和谐。嗯,产生的新的和谐向量基于内存的考虑,音高调整,随机化。和分别生成随机在0和1之间,每个运营商根据下列条件选择。(我)条件1:和;选择记忆的考虑。(2)条件2:和;选择调整。(3)条件三:;选择随机化。
步骤3。如果一个新的和谐比最坏的HM的和谐,更新嗯。
步骤4。如果停止标准不满意,去一步2。
3所示。先进和谐寻找旅行推销员问题
HS算法表现出良好的性能在解决各种问题;然而,它也有一些缺点的顺序问题,如TSP和车辆路径问题。之间的顺序问题,仔细定位节点意味着很强的相关性。商品,然而,使用统一的概率无论节点之间的相关性在选择新值在一个新的和谐的历史值存储在现有HM的相同的索引。内存运营商甚至不考虑函数在以下情况:在生成下一个新的和谐的价值th价值指数是1,如果所有的值()th现有HM城市1,如果所有的值在现有HM城市1。为了弥补这些缺点,我们提出先进的HS (AHS),其中包括健身、精英策略和遗传算法的变异算子。
3.1。修改内存考虑和音高调整
原商品的内存考虑运营商运行随机从HM的历史价值。然而,在先进的HS算法,考虑运营商实现的内存使用轮盘赌,所以HM的适者指数比弱的更大的生存机会。健身和距离成反比。与此同时,虽然内存考虑运营商运行一定次数,如果价值和候选人th价值所选择的记忆考虑运营商都是一样的,th新的和谐的价值是由随机化算子。在满足条件的情况下的第1部分2。2,距调整生成th索引值最接近的一个新的和谐价值值的可能的范围值。
3.2。精英保留规则和变异
HS算法更新的方式,一种新的和谐包含在HM和现有的最糟糕的一个是排除在英国当一个新的和谐比现有最和谐的嗯。这种机制部队的所有元素的融合,在HM相同的值,可能是局部最优,在无限重复。为了躲避这样的情况下,我们认为反演算子,GA的所有突变之一。这对HM执行满足以下方程:,在那里意味着注意率精英策略的性能。反转变异算子同时选择几个随机节点在所有节点,节点选择以逆顺序重新排列。所示图的例子3,前面的节点(1,2,3,4,5,6,7,8)转化为新节点(1、7、3、5、4、6、2、8)通过反转突变。
4所示。TSP的算法
整个过程的算法结合了观众和ACO算法如图4。首先,我们随机产生初始解。更新信息素轨迹。通过使用内存的考虑,音高调整,随机在每个小节中提到的条件2。2,我们创建一个新的和谐,检查是否出现一个更新。当变异算子实现在一定的概率,反转突变进行休息,除了HM视为精英,然后更新信息素。之后,蚂蚁生成解决方案与HMS的大小用ACO算法,基于信息素轨迹由HS算法。结合蚁解决方案和HM存储在临时内存HMS的两倍大,它们总距离按升序排序,定义为目标函数。前50%和更高价值的临时内存作为新HM决定。这些程序是重复直到满足停止条件。伪代码1描述了该算法的伪代码。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
5。实验结果
表1列出了该算法的参数设置。表明该算法的性能,我们进行实验使用电脑英特尔core i5处理器、2 GB内存和使用c#编程语言实现该算法。我们测试了该算法使用TSPLIB 20的数据集(例如,berlin52, st70, eil76, kroA100, kroB100, kroC100, kroD100, kroE100, eil101, lin105, ch130, pr144, ch150, pr152, d198, tsp225, pr226, pr264, a280,和pr299)。与其他算法的比较和已知的最好的解决方案从TSPLIB中获得,任意两个城市之间的距离计算欧式距离和四舍五入小数点后1。每个实验都使用1000次迭代和10分,最好的,最糟糕的情况下,意思是,和标准偏差为每个运行记录。见表220个数据集测试中,我们发现在19个数据集的最优解,除了pr299 TSPLIB的表示。对于kroB100 pr144,特别是,我们的算法优于TSPLIB的已知的最佳解决方案(见表的星号2详情)。
来验证我们的算法的优越性,我们比较兰德尔和蒙哥马利(27和陈和简24,26]。兰德尔和蒙哥马利27]提出了蚁群所积累的经验(AEAC)使用前殖民地的经验来指导选择的元素,和陈一个简24,26]解决TSP的组合四metaheuristics GA, SA算法,算法。表3和4分别显示比较结果与前两个研究。
6。结论
在本文中,我们提出了AHS-ACO算法,这是一个高级和谐搜索和蚁群优化算法,来解决TSP。我们修改了通用HS算法产生一个新的HS算法包括健身、精英策略和变异算子的遗传算法,我们结合ACO算法在HS算法来克服的缺点HS算法求解顺序问题。我们进行了实验使用AHS-ACO算法TSPLIB的20日的数据集。所示的实验结果,我们发现从TSPLIB在几乎所有情况下获得最优解TSPLIB;此外,我们的算法提供了一个更好的解决方案在kroB100和pr144 TSPLIB的解决方案。本文的结果表明,HS算法可以是一个很好的方法,与其他启发式相结合,解决TSP等顺序问题,以及许多其他问题。
确认
这项研究受到了基础科学研究项目通过韩国国家研究基金会(NRF)由教育部、科技部(2010 - 0023236)。