元启发式：概述和概论的比较

1、Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison组合优化中的元启发式：概述和概念比较1元启发式2基于人群的方法基于群体的方法是用一组解决方案（而不是一个解决方案）对算法进行一次完整的算法。 当他们处理大量的解决方案时，基于群体的算法为探索搜索空间提供了一种自然的，内在的方式。 然而，最终的表现强烈依赖于人口被操纵的方式。 研究最多的基于种群方法的最优化方法是进化计算（EC）和蚁群优化（ACO）。 在EC算法中，个体种群通过重组和变异算子进行修正，而在ACO中，人工蚂蚁群体被用来构建由

2、信息素路径和启发信息指导的解决方案。3蚁群优化算法（ACO）自然界蚂蚁群体在寻找食物的过程中，通过一种被称为信息素（Pheromone）的物质实现相互的间接通信，从而能够合作发现从蚁穴到食物源的最短路径。通过对这种群体智能行为的抽象建模，研究者提出了蚁群优化算法（Ant Colony Optimization, ACO），为最优化问题、尤其是组合优化问题的求解提供了一强有力的手段。4蚁群优化算法（ACO）在自然界中，蚂蚁通过在环境中释放信息素来交流信息，完成协同寻路任务。蚂蚁巢穴食物蚂蚁总以较大概率选择信息素浓度较高的路径；较短路径上的信息素积累速度较快；“正反馈”作用使蚁群最终聚集到较短路径

3、5蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。6算法流程路径构建每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城

4、市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。信息素更新当所有蚂蚁构建完路径后，算法将会对所有的路径进行全局信息素的更新。更新是在全部蚂蚁均完成了路径的构造后才进行的，信息素的浓度变化与蚂蚁在这一轮中构建的路径长度相关。7路径构建 伪随机比例选择规则（random proportional） 对于每只蚂蚁k，路径记忆向量Rk按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。Jk(i)表示从城市i可以直接到达的、且又不在蚂蚁访问过的城市序列Rk中的城市集合。h(i, j)是一个启发式信息，通常由h (i

5、, j)=1/dij直接计算。t(i, j)表示边(i, j)上的信息素量。8信息素更新（1）在算法初始化时，问题空间中所有的边上的信息素都被初始化为t0。（2）算法迭代每一轮，问题空间中的所有路径上的信息素都会发生蒸发，我们为所有边上的信息素乘上一个小于1的常数。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。（3）蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。（4）迭代（2），直至算法终止。9信息素更新m是蚂蚁个数；r是

6、信息素的蒸发率，规定0r1。 是第k只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的倒数。Ck表示路径长度，它是Rk中所有边的长度和。10最大最小蚂蚁系统（MMAS）最大最小蚂蚁系统（MAX-MIN Ant System，MMAS）在基本AS算法的基础上进行了四项改进：(1)只允许迭代最优蚂蚁（在本次迭代构建出最短路径的蚂蚁），或者至今最优蚂蚁释放信息素。(2)信息素量大小的取值范围被限制在一个区间内。(3)信息素初始值为信息素取值区间的上限，并伴随一个较小的信息素蒸发速率。(4)每当系统进入停滞状态，问题空间内所有边上的信息素量都会被重新初始化。11基于轨迹的方法1 模拟退

7、火2 禁忌搜索3 探索性本地搜索方法（1）变邻域搜索（VNS）（2）引导本地搜索（GLS）12模拟退火模拟退火算法(Simulated Annealing, SA)的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。模拟退火算法从某一较高的温度出发，这个温度称为初始温度，伴随着温度参数的不断下降，算法中的解趋于稳定，但是，可能这样的稳定解是一个局部最优解，此时，模拟退火算法中会以一定的概率跳出这

8、样的局部最优解，以寻找目标函数的全局最优解。13禁忌搜索标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的搜索区域。14变邻域搜索（VNS）变邻域搜索算法的主要思想是：采用多个不同的邻域进行系统搜索。首先采用最小的邻域搜索，当无法改进解时，则切换到稍大一点的邻域。如果能继续改进解，则退回到最小的邻域，否则继续切换到更大的邻域。15引导本地搜索（GLS）引导本地搜索在搜索过程中建立的惩罚。它利用点球帮助

9、局部搜索算法跳出局部极小和高原。当给定的局部搜索算法解决局部最优，GLS修改目标函数，采用特定的方法。然后，本地搜索将使用增广目标函数，其目的是使搜索跳出局部最优。关键是，目标函数是改性的方法。16元启发式算法是相对于最优化算法提出来的，一个问题的最优化算法可以求得该问题的最优解，而元启发式算法是一个基于直观或经验构造的算法，它可以在可接受的花费(指计算时间和空间)下给出问题的一个可行解，并且该可行解与最优解的偏离程度不一定可以事先预计。图为蚁群优化算法原理17 METAHEURISTICS的分类。自然启发与非自然启发 。基于人口与单点搜索。内存使用量与无内存方法图为ID框架然而不论它究竟属于

10、哪个分类，我们都可以从强化和多样化的角度去分析。18强化是要仔细和密集地搜索在过去的搜索中找到的良好解决方案。 相反，多样化则是将搜索引导至未访问区域。Yagiura和Ibaraki 2001每个元启发式方法的设计目的都是为了有效和高效地探索搜索空间。为了获得有效的元启发式，强化和多样化之间的正确平衡是必需的。而且，这种平衡不应该固定或只能向一个方向改变（例如不断增加的强度）。这种平衡应该是动态的。19作者在这里引入了ID框架来试图将拥有着不同的功效机理以及动态平衡的metaheuristics组件进行描述和分类，以便引出Metaheuristics杂交的概念。位于角落OG附近的AND组件的例子是本地搜索中最陡的下降选择规则NOG表示的角覆盖了除目标函数以外的一个或多个函数所引导的所有ID组件，由R表示的第三个角落包含完全随机的所有ID组件。20关于Metaheuristics杂交事实上很多的成功的应用程序都是杂交的结果，当然其混合形式也是多样的。两个元启发式的顺序链接，由一个到另一个不同的部分以某种方式交换信息以完成合作完全整合为一个统一系统杂交最常用的方法之一就是在基于群体的方法中使用轨迹方法。基于群体的方法的优势