文摘
模拟退火(SA)算法是一种流行的智能优化算法已成功地应用于许多领域。参数的设置是其性能的关键因素,但它也是一个单调乏味的工作。为了简化参数设置,我们提出一个基于列表的模拟退火(LBSA)算法来解决旅行商问题(TSP)。LBSA算法使用一种新颖的基于列表的冷却时间来控制温度的降低。具体来说,首先创建一个列表的温度,然后使用的最高温度在列表大都市验收标准来决定是否接受一个候选的解决方案。温度列表迭代调整根据问题的解空间的拓扑结构。基于列表的冷却效果和参数灵敏度的时间表说明通过基准TSP问题。LBSA算法,性能强劲的大范围的参数值,显示了竞争与其他先进的算法性能。
1。介绍
模拟退火(SA)算法,首次独立作为一个组合优化问题的搜索算法(1,2),是一个受欢迎的迭代metaheuristic算法广泛用于解决离散和连续优化问题。SA算法的主要特点在于手段逃离当地的最适条件,允许爬山动作找到全局最优。SA的主要不足之一是,它有几个参数进行调优,性能及其对这些控制参数的值很敏感。有两个特殊的参数调优策略:在线参数调优和离线参数调优。在网络的方法,参数和动态更新或自适应控制在SA算法的执行(3- - - - - -7),而在离线方法,不同参数的值调整之前的执行SA算法和在执行过程中是固定的。微调参数值并不是微不足道的,这些参数通常很差由试验和错误。SA算法,参数或不太敏感的参数设置,在实际用户非常有吸引力。
最近,metaheuristic算法称为基于列表threshold-accepting (LBTA)算法被开发和显示显著的性能np完全组合优化问题。LBTA的优势超过大多数其他地区搜索metaheuristic方法是更少的控制参数,必须调整以产生令人满意的解决方案。LBTA自出现以来,已经成功地应用于许多组合优化问题(8- - - - - -14]。
在这个工作我们出于LBTA简化参数调优的成功研究基于列表的参数控制策略可以应用于SA算法。朝着这一目标,我们提出一种新颖的基于列表的冷却时间表SA算法解决旅行商问题(TSP),我们叫我们的算法基于列表的模拟退火算法(LBSA)。在基于列表的冷却时间,所有的温度都存储在一个列表被组织为一个优先队列。更高的温度更高的优先级。LBSA,温度首先创建的列表,然后,在每一代中,列表中的最大值作为当前温度计算接受概率候选方案。温度自适应更新列表根据问题的解空间的拓扑结构。使用基于列表的冷却时间,SA算法具有良好的性能在一个广泛的参数值;和它也有竞争和其他先进的算法相比性能。基于列表的参数鲁棒性冷却时间可以大大简化LBSA算法的设计和实现实际应用。
本文的其余部分组织如下:部分2提供了一个简短的描述TSP问题和SA算法。部分3礼物我们提出基于列表的SA算法。部分4给出了实验方法和实验结果进行基准TSP问题。最后,在节5我们总结我们的研究。
2。预赛
2.1。旅行商问题
TSP问题是一个最著名的困难的组合优化问题。它属于np难优化问题的类。这意味着没有多项式时间算法保证其全局最优解。考虑一个推销员拜访城市。TSP问题由通过的所有这样的城市找到最短的行程没有城市访问两次,推销员返回到开始的旅游城市。它可以定义如下。为提到的问题,我们可以使用一个距离矩阵存储所有的引用之间的距离,其中每个元素的矩阵代表了城市之间的距离和。我们用一组排列1的整数,其中包含所有可能的旅游的问题。我们的目标是找到一个排列,最大限度地减少
可能是对称或非对称TSP问题。在对称TSP,两个城市之间的距离都是一样的在每一个相反的方向,形成一个无向图。这种对称部分的数量可能的解决方案。不对称TSP,路径可能在两个方向上都不存在或可能不同的距离,形成一个有向图。城市交通碰撞、单行道、机票与不同的出发和到达费用这种对称如何分解的例子。
2.2。模拟退火算法
SA算法通常被认为是最古老的metaheuristics当然为数不多的算法,有明确的策略,以避免局部最小值。SA的起源是在统计力学中,首次提出了组合优化问题。基本思想是接受移动导致质量比当前解决方案的解决方案以逃离局部最小值。接受这一举动的概率是在搜索参数的温度有所下降。SA算法从最初的解决方案,候选的解决方案然后生成(随机或使用一些指定规则)附近的吗。大都市验收标准(15),模型如何热力学系统从一个状态转移到另一个状态的能量最小化,用于决定是否接受与否。候选解决方案被接受为当前的解决方案吗基于接受概率: 在哪里是温度的参数。SA算法可以描述图1。
为了SA算法应用到一个特定的问题,一个必须指定社区结构和冷却时间。这些选择和相应的参数设置可以对SA的性能产生重大影响。不幸的是,没有选择的这些策略将有利于所有的问题,也没有一般简单的方法来找到最优参数设置为给定的问题。冷却时间应该包含起始温度,温度衰减函数,马尔可夫链的长度,和终止条件。所描述的几何冷却时间,温度更新公式,可能是最常用的SA文学和作为基线进行比较与其他更复杂的方案(16]。的典型值适度的缓慢冷却率0.8到0.99。
实际应用,计算目标函数的复杂性很高,SA算法可能运行在恒定的马尔可夫链的长度和使用固定的迭代次数作为终止条件。因此,初始温度和制冷系数的两个关键参数影响SA算法的性能。甚至在这个简单的情况下,这不是一项容易的任务找到这两个参数的最优值,因为股价的表现对这些参数很敏感。一个方法解决SA算法的参数设置问题是使用自适应冷却策略3- - - - - -7]。自适应冷却策略无疑是高效和SA算法更敏感比规范SA用户定义的参数,但这也使得SA算法失去简单的特点。另一个解决这个问题的方法是寻找新的冷却时间也更少的参数或参数更健壮。
2.3。模拟退火算法在TSP问题
为了使用SA TSP问题的算法,我们可以代表的解决方案作为一个排列。一套大的运营商,如著名的2-Opt 3-Opt,逆,插入、交换操作,可用于生成候选方案。自出现以来,SA算法被广泛和深入研究了TSP问题(17- - - - - -21]。许多冷却进度表,如几何、指数、对数、和算术的及其变体,用于文学。
SA的理论收敛条件使它非常耗时在大多数情况下(22]。王等人。23)提出了一种两级SA算法测试23日基准TSP实例规模从51到783年。数值结果表明,SA算法很难解决TSP基准实例规模超过1000个城市基于时间复杂度。耿et al。24)提出了一种自适应模拟退火算法与贪婪搜索(ASA-GS),在贪婪的搜索技术用于加快收敛速度。ASA-GS达到一个合理的计算时间之间的权衡,解决质量和实现的复杂性。具有良好的可扩展性和良好的性能甚至为基准TSP实例规模超过1000个城市。王等人。25)提出了一个可替换主体SA算法与基于实例的抽样(MSA-IBS)利用基于实例的搜索算法的学习能力。上优于抽样可以有效改善SA的抽样效率。仿真结果表明,MSA-IBS的性能远比ASA-GS准确性和CPU时间的解决方案。摘要MSA-IBS作为基础使用基于列表的冷却时间。
3所示。基于列表的模拟退火算法
3.1。社区结构
在本文中,我们使用贪婪的混合运算符王等人提出的。25)产生候选方案。这是一种多个移动运营商,从三个邻居选择最好的一个。具体来说,在两个位置和被选中,它使用逆算子,插入操作和交换算子产生三个邻居解决方案。最好的一个作为候选方案。逆、插入、交换操作符可以定义如下。
定义1(逆算子)。意味着逆位置之间的城市和。的将生成一个新的解决方案吗这样,,,在那里;此外,如果,这意味着和,然后和。两条边将取而代之的是逆算子对称TSP问题。
定义2(插入操作符)。这意味着城市的位置定位。的操作符将生成一个新的解决方案这样,,在的情况下,或,,在的情况下。一般来说,三条边将被插入取代操作员。
定义3(交换算子)。这意味着交换位置的城市和城市的位置。的操作符将生成一个新的解决方案这样和。在一般情况下,四个边缘会被交换算子所取代。
使用上面的三个运营商,混合使用贪婪操作符可以定义如下: 在哪里回报最好的在它的参数。
3.2。产生初始温度列表
如LBTA算法(8- - - - - -14),基于列表的参数控制策略需要产生一个初始的参数列表。因为温度在SA是用来计算接受概率的候选方案,我们使用最初的接受概率生产温度如下。假设是当前解决方案和候选解决方案是随机选择的的邻居。他们的目标函数值和,分别。如果比,然后接受概率的可以计算使用公式(2)。相反,如果我们知道接受概率,然后我们可以计算相应的温度如下:
图2是生产的流程图初始温度列表。在图2之后,一个可行的解决方案生产,候选人解决方案吗是随机选择的的邻居。如果比,然后取而代之的是。并使用公式(4)的绝对值是用来计算一个初始温度的值。然后将插入到初始温度列表。温度是一个优先级列表,更高的温度更高的优先级。重复相同的步骤,直到温度的值列表。
3.3。温度控制程序
在每个迭代中,最高温度在列表用作当前温度。如果马尔可夫链长度,然后最多可以使用吗次接受概率的计算候选方案。假设有时报》表示,糟糕的解决方案被接受为当前的解决方案;我们使用和来表示目标函数值的差异和接受概率,分别和之间的关系和可以被描述为如下方程:
根据都市验收标准,每次坏候选解决方案是满足,一个随机数被创建。如果小于接受概率,那么坏的候选解决方案将被接受。因此,对于每一对和,有一个随机数和小于。我们使用和计算一个新的温度如以下公式描述:
我们使用的平均值更新温度列表。具体地说,会从列表删除,平均的将插入到列表。因为总是小于的平均小于也。通过这种方式,温度降低总是随着搜索的进行。
3.4。LBSA算法的描述
因为这篇文章的主要目的是研究基于列表的冷却进度表的有效性,我们使用一个简单的SA框架使用固定外层循环迭代时间和固定的马尔可夫链长度在每一个温度。详细的流程图的主要优化过程如图3。除了初始温度列表的创建,主要区别LBSA流程图,流程图规范SA的温度控制策略。规范SA,温度控制过程是独立于问题的解空间的拓扑结构。相反,LBSA的温度控制过程是自适应的拓扑问题的解空间。在图3,是外循环的最大迭代次数,LBSA的终止条件。马尔可夫链的长度,这是内循环的终止条件。计数器用于记录当前迭代的外循环,用于记录当前采样内循环,然后呢用于记录多少次糟糕的解决方案是在每个温度接受。变量用于存储的总温度计算公式(6),平均温度将用于更新温度列表。我们可以用一个最大堆来实现温度列表。的时间复杂度从堆对数,存储和检索的使用温度列表不会增加SA算法的时间复杂度。
4所示。仿真结果
为了观察和分析基于列表的冷却时间的影响和LBSA算法的性能,进行五种实验基准TSP问题。第一种实验被用来分析的有效性基于列表的冷却时间。第二种是LBSA算法的参数敏感性分析。第三类是比较不同方法的性能更新温度列表。第四类是比较不同的社区结构的性能。第五类是比较LBSA的性能和一些先进的算法。
4.1。基于列表的冷却进度表的有效性
为了说明基于列表的冷却进度表的有效性,我们比较的温度变化过程和搜索过程LBSA算法与基于经典几何冷却进度表的SA算法和算术冷却进度表。XQL662,这些实验在BCL380 XIT1083和XSC6880问题从超大规模集成数据集。最著名的整数解的问题是1621年,2513年,3558年和21537年,分别。外层循环的迭代时间是1000年,马尔可夫链的长度在每一个温度是城市的问题,这是380年,662年,1083年和6880年,分别。
图4比较不同的冷却时间的温度变化过程的四个基准问题。基于列表的冷却时间可以被视为一种几何与可变冷却冷却时间系数。与几何冷却的温度不同的计划相比,基于列表的冷却时间减少温度更快的早期阶段,但在后期慢。的艾布拉姆森et al。16),几何冷却时间总是使用常数冷却系数无论搜索阶段。然而,在高温下几乎所有的候选解决方案被接受,尽管他们中的许多人可能非生产性的。使用可变冷却系数,它取决于阶段,将允许SA算法少花点时间在高温阶段。因此,更多的时间是花在低温阶段,从而减少所需的总时间解决这个问题。
(一)
(b)
(c)
(d)
图5比较不同的冷却进度表的搜索过程的四个基准问题。与几何冷却进度表和算术冷却时间相比,基于列表的冷却时间有更快的收敛速度和良好的长期行为。这个良好的性能可能是由于变量基于列表的冷却进度表的制冷系数特性。温度自适应更新根据问题的解空间的拓扑结构。因此,LBSA算法可以花更多时间在前景看好的领域精细搜索。
(一)
(b)
(c)
(d)
4.2。温度敏感性分析列表长度和初始温度的值
我们在BCL380观察列表长度的敏感性,XQL662 XIT1083, XSC6880问题。对于每个问题,我们测试30种不同的列表长度从10到300年第10步。对于每个列表的长度,我们运行LBSA算法50倍,计算平均行程长度和百分比平均误差长度最著名的观光旅游。图6是百分比误差之间的关系和列表的长度。它显示了以下:)所有的问题,都有一个广泛的列表长度对LBSA相似的有前途的性能;()列表长度是更健壮的小问题,而不是大问题;()列表长度不应太大对于大型问题。大问题,使用马尔可夫链的长度,这是这个城市的问题,不够大LBSA在每个温度达到平衡。大列表长度意味着温度降低较慢,算法会花太多时间在高温和接受太多的非生产性的解决方案。因此,大列表长度将急剧恶化LBSA的性能对于大型问题。因为健壮的温度列表的长度,我们使用固定温度列表长度的模拟之后,也就是120的所有实例。
为了观察初始温度的灵敏度值,我们进行了实验与不同初始温度BCL380值,XQL662 XIT1083, XSC6880问题。因为初始温度的值是根据最初的接受概率,我们使用30个不同,范围从10−200.9、创建初始温度的值。具体来说,集合从10是等比数列的结合−20到10−2公比10和算术序列从0.1到0.9,0.1公差。对于每个初始接受概率,我们运行LBSA算法50倍,计算平均行程长度和百分比平均误差长度最著名的观光旅游。图7是百分比误差之间的关系和索引最初接受的概率。它显示了以下:)的性能LBSA初始温度不敏感值;()不同方向有不同的不同的问题。小问题,初始温度不应过低,但对于大问题,初始温度不应过高。这种差异是由于有限的计算资源使用和TSP问题的非线性计算的复杂性。LBSA算法可以有类似的承诺表现广泛的初始温度的值;这高鲁棒性的初始温度是由于自适应基于列表的冷却进度表的性质。
4.3。比较不同温度更新计划
在我们的算法中描述部分3.4,我们使用温度的平均值更新温度列表。有很多变种,如使用最大或最小值。使用平均的优势,我们比较结果和温度的降低过程使用这三个更新计划。表1仿真结果;很明显,使用平均温度来更新温度列表远远比其他方法更好的性能。BCL380温度降低过程中不同的策略,这是显示在图8使用平均温度,可以解释为什么是最好的选择。如果我们使用温度最高温度更新列表,温度会降低非常缓慢。结果,承认不好的解决方案总是高的概率,和SA算法将搜索解空间中随机。相反,如果我们使用最低温度更新温度列表,温度将急剧减少。结果,SA算法将很快被困到局部最小值和失去的优势逃离局部最小值通过使用大都市验收标准。
4.4。比较不同的社区结构
在我们的算法中,我们使用一个贪婪的混合的邻居王等人提出的运营商。25)产生候选方案。这个混合运算符使用产生的最好的一个逆,插入和交换运营商。显示其优势,我们比较结果产生的逆,插入、交换和混合操作符。和我们比较逆的百分比、插入、和交换运营商接受当我们使用杂交算子。表2仿真结果;很明显,杂交算子具有最好的性能。三个基本操作中,逆是最好的。如果我们比较不同的百分比基本运营商接受我们使用混合操作符时,我们发现,逆算子被接受。图9的比例是不同的运营商接受BCL380实例。逆的百分比、插入和交换运营商65%,31%,和4%,分别。三个运营商的相对百分比接受BCL380其他实例上是相似的。逆算子的良好的性能是由于它能够产生更多的细粒度的社区结构,因为它只改变两条边。混合操作符,它使用逆、插入和交换运营商同时,有一个更大的社区结构。所以它有更高的概率找到有前途的解决方案。
4.5。竞争力LBSA算法
我们比较LBSA与遗传模拟退火蚁群系统算法(GSAACS) [2624日)和MSA-IBS基准实例与城市从51到1655年。GSAACS是一种混合算法,利用蚁群系统(ACS)来生成初始解的遗传算法。然后,它使用遗传算法(GA),它使用SA作为变异算子,产生后代解决方案基于最初的解决方案。如果解决方案搜索遗传算法比最初的解决方案,GSAACS将使用这些更好的解决方案来更新信息素ACS。一个预定义的数代后,GSAACS使用粒子群优化(PSO)之间交换的信息素信息组织。
结果GSAACS来自[26]。GSAACS使用120只蚂蚁和1000代。在每一代GSAACS, GA 100代。MSA-IBS LBSA算法,我们将人口规模设置为30和1000年外循环迭代次数,和马尔可夫链的长度在每个温度的城市数量的两倍。最终的条件是,它发现最优解或外循环的迭代次数达到1000人。每个TSP问题的算法执行的25倍,和结果列在表3。
在表3列实例,选择最好的,意思是,和PEav表示的名称TSP问题,最优之旅从TSPLIB长度,长度最短旅行发现,25之间的平均行程长度试验和误差百分比意味着行程长度的选择,分别。我们可以看到在桌子上3,比GSAACS MSA-IBS和LBSA都有更好的性能在所有24实例。LBSA有点比MSA-IBS平均百分误差。
我们比较LBSA算法和GA-PSO-ACO (27)和MSA-IBS 35基准实例与城市从48到33810年。GA-PSO-ACO结合了遗传算法的进化思想,粒子群算法和蚁群优化。GA-PSO-ACO算法,整个过程分为两个阶段。在第一阶段,遗传算法和PSO用于获得一系列的次优方案调整信息素的初始分配算法。在第二阶段,算法用于搜索最优解。结果GA-PSO-ACO来自[27]。GA-PSO-ACO使用100人和1000代。LBSA MSA-IBS算法,我们人口规模的数量设置为10,外层循环的迭代时间至1000年,和马尔可夫链的长度在每一个温度是城市的数量。最终LBSA条件是找到最优解或外循环的迭代次数达到1000人。像GA-PSO-ACO和MSA-IBS LBSA在每个TSP实例执行20倍,和结果列在表4。
我们可以看到在桌子上4,比GA-PSO-ACO MSA-IBS和LBSA都有更好的性能在所有35实例。LBSA有点比MSA-IBS平均百分误差。
我们比较LBSA算法和ASA-GS (24)和MSA-IBS算法在40基准实例城市从151年到85900年。实验2.8 GHz PC上运行,ASA-GS是2.83 GHz PC上运行。对于所有实例,我们将外层循环的迭代时间设置为1000,在每个温度设定马尔可夫链长度的城市。如MSA-IBS算法,选择合适的人口规模为每个实例的CPU时间LBSA小于ASA-GS。LBSA的结束条件和MSA-IBS当它发现最优解或当外层循环的迭代次数达到1000人。算法执行25试验,每个实例和结果列在表5。
我们可以看到在桌子上5所有实例的平均PEav LBSA是0.75,比1.87 ASA-GS,所有实例和LBSA的平均CPU时间是282.49,远低于650.31的ASA-GS。LBSA有点比MSA-IBS PEav平均。
5。结论
本文提出一种基于列表的SA算法,TSP问题。LBSA算法使用新颖的基于列表的冷却时间来控制温度的降低参数。基于列表的冷却时间可以看作是一个特殊的几何与可变冷却冷却时间系数。冷却系数的方差自适应解的拓扑空间,这可能是更健壮的问题。模拟结果表明,该新型冷却时间表是对参数值和提出LBSA算法非常有效,简单,容易实现。不敏感参数的优点是很有吸引力的,允许LBSA算法应用在不同问题没有太多精力调优参数产生不错的效果。
利益冲突
作者宣称没有利益冲突有关的出版。
承认
这项工作是由中国福建省自然科学基金(没有。2014 j01219,没有。2013 j01216)。