[科普中国]-元启发式算法

定义

元启发式算法是相对于最优化算法提出来的，一个问题的最优化算法可以求得该问题的最优解，而元启发式算法是一个基于直观或经验构造的算法，它可以在可接受的花费(指计算时间和空间)下给出问题的一个可行解，并且该可行解与最优解的偏离程度不一定可以事先预计。

元启发式算法包括禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、粒子群优化算法、人工鱼群算法、人工蜂群算法、人工神经网络算法等。1

算法禁忌搜索算法禁忌搜索(tabu search)算法是一种全局性邻域搜索算法，它模拟了人类具有记忆功能的特征。禁忌搜索算法最早是由Glover在1986年提出的，随后很多学者对这个算法进行了完善，形成了一套完整的算法。

禁忌搜索算法主要针对一般的下降算法的缺点而提出来的，一般的下降算法在搜索到某个局部最优解时，算法很容易自动停止，而禁忌搜索算法采用禁忌策略尽量避免已搜索过的对象，从而保证了对不同的搜索路径的探索。禁忌搜索算法不是搜索到局部最优解就停止搜索，而是引导算法跳出局部最优解，进而转向全局最优解。禁忌搜索算法是人工智能的一种体现，该算法最重要的思想是记住以往已搜索过的局部最优解，并在进一步迭代搜索中尽量避开这些局部最优解(而不是绝对禁止循环)，进而使得搜索途径多样化，以此跳出局部最优解。

在禁忌搜索算法中会涉及到邻域、候选集、禁忌对象、禁忌表、禁忌表规模、评价函数等内容，禁忌表特别指禁忌对象及其被禁的长度;禁忌对象多选择造成解变换的状态;候选集中的元素依评价函数而确定，根据评价函数的优劣选择一个可能替代被禁对象的元素，是否替代取决于禁忌的规则和其他一些特殊规则，如特赦规则;计算中的一些信息，如被禁对象对应的评价值、被禁的频率等，将对禁忌的长度和停止规则提供帮助。1

模拟退火算法模拟退火(simulated annealing)算法属于一种通用的随机探索算法，最初是由Metropolis在1953年提出的，其基本思想是把某类优化问题的求解过程与统计热力学中的热平衡问题进行对比，试图通过模拟高温物体退火过程来找到优化问题的全局最优解或者近似最优解。1983年Kirkpartrick成功地将模拟退火算法应用在了组合优化问题。

模拟退火算法是受到了物体退火过程的启发。一个物体的退火过程大体如下:首先对该物体高温加热(融化)，显然物体内原了处于高速运行的高能状态，然而作为一个实际的物理系统，原子的运动又总是趋于最低的能量状态。在退火的初始状态，温度较高，物体处于高能状态，随着温度的逐渐降低，物体内部原了的运动趋于低能状态，这种有高能向低能逐渐降温的过程称为退火。当温度降至结晶温度后，物体由原了运动变成围绕晶体格点的微小振动，液体凝固成固体，退火过程结束。在求解组合优化问题时，将物体的内能E模拟为目标函数值f，温度T看成控制参数，就得到了我们所说的模拟退火算法。

遗传算法遗传算法(Genetic Algorithm)是由美国Michigan大学的John Holland教授于1975年首次提出的，它的基本思想是基于Darwin的进化论和Mendel的遗传学，即生物的遗传和变异在生物的进化过程中起着重要的作用，它使得生物不仅能够保持自身固有的特性，同时还能够不断地改变白身以适应新的生存环境。遗传算法是一种基于群体进化的计算模型，它通过群体的个体之问繁殖、变异、竞争等方法进行的信息交换优胜劣汰，从而一步步地逼近问题的最优解。对个体的遗传操作主要通过选择(繁殖)、交叉和变异这三个基本的遗传算了来实现。

生物的进化是以群体的形式进行的，而群体的进化是通过个体的信息遗传与交义叉来完成的，与之相对应，遗传算法的运算对象也是群体，它由n个个体组成一个集合，通过对该集合进行遗传操作来模拟生物的进化过程，遗传算法中的个体就是模拟生物的染色体，称为人工染色体。为了完成对个体的遗传操作，需要将个体的表现型转换成基因型，这一个过程称为编码，反之，将基因型转换成表现型的过程称为解码。

蚁群算法蚁群算法(ant colony optimization, ACO)是由意大利学者Marco Dorig于1992年在他的博士论文中提出来的一种仿生进化算法。它产生于对蚁群行为的研究:蚁群中的蚂蚁以“信息素”为媒介，问接异步地相互联系，蚂蚁在寻找食物或巢穴的路径过程中，会在它们经过的地方留下一些化学物质，称之为“信息素”，这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号使后到的蚂蚁选择有这些物质的路径的可能性比选择没有这些物资的路径的可能性大得多，后到的蚂蚁也会留下信息素对原有的信息素进行加强。这样，寻找最优选址变现为一种正反馈过程，蚂蚁到过次数多的地点，后来的蚂蚁选择到此处的可能性就越大。

蚁群算法的设计利用了蚂蚁个体的运动规则:

1)搜索范围:可具体设定蚁群个体的搜索参数半径，这样就限定了其运动过程中的观察能力和移动能力。

2)局部环境:蚂蚁个体仅需要感知它周围的局部环境信息，并且该局部环境中点的信息素是按一定速度消失的。

3)觅食规则:每只蚂蚁只是在其能感知的范围内进行信息探索和留存，在局部环境中，哪一点的信息素最多，就以较大的概率决定了它的运动方向。这样，虽然在其运动过程中，会出现小概率的搜索错误，但从总体上说，其搜寻的效率和正确性会通过其他蚂蚁的行为反馈加以调整。

4)移动规则:每只蚂蚁都朝着信息素最多的方向移动，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性地运动下去，并且，在运动的方向上有一个随机的小的运动，以保留原来的运动记忆。如果发现有其已经经过的地点，则以较大概率进行避让。

5)避障规则:如果在蚂蚁即将移动的方向上存在障碍物，则它会随机选择一个方向，或者按照信息素的指引继续其觅食行为。

6)通信规则:实际上，每只蚂蚁是通过其信息素的播撒和感知来进行通信的。其具体规则是多元化的，它可以在找到相对最优解的时候散发最多的信息素，并且随着它走的距离越来越远，播撒的信息素也越来越少。1

粒子群优化粒子群优化(particle swarm optimization, PSO )是美国心理学家Kennedy和电气工程师Eberhart受鸟类觅食行为的启发，于1995年提出了粒子群优化算法。PSO是一种基于群体智能的全局随机寻优算法，它模仿鸟类的觅食行为，将问题的搜索空间类比于鸟类的飞行空间，将每只鸟抽象成为一个微粒，用以表征问题的一个候选解，所需要寻找的最优解等同于要寻找的食物。算法为每个微粒给定位置和速度，每个微粒通过更新速度来更新其自身的位置。通过迭代搜索，种群可以不断地找到更好的微粒位置，从而得到优化问题的较优解。

提出PSO之后，Kennedy和Eberhart又在基本PSO算法基础上做了扩展，提出了一种离散二进制PSO算法，应用于函数优化问题，验证了其有效性，但该算法难以有效地跳出局部最优。Clerc推广了这一工作，研究了离散PSO算法，并将其应用于旅行商问题的求解。近年来涌现了很多PSO应用于调度问题的研究。Tasgentirenetal.最先对于flow shop问题提出了一种基于变邻域搜索(variable neighborhood search, VNS )的混合PSO算法，采用基于随机键的SPV ( smallest position value)规则将标准PSO算法推广到排序问题，并利用VNS来改进PSO环节所得到的解。Lianetal.针对相同的问题，提出了一种新型的PSO算法，直接利用GA的交叉和变异操作作为PSO算法中微粒速度和位置的更新操作。

迭代贪婪迭代贪婪(iterated greedy, IG)是Ruiz和Stutzle在2007年提出的一种简单而有效的求解调度问题的元启发式算法。迭代贪婪算法始终记录两个解:算法找到的最好解以及算法使用的当前解。算法初始化这两个解之后(通常由启发式规则实现)，从当前解出发，考虑针对所解决问题设计的局部搜索方法，若局部搜索中有更好的解则贪婪地移动到那个解，局部搜索结束之后算法会采用类似模拟退火的接受准则以一定的概率接受比最好解更差的解，然后更新最好解，再对当前解采用破坏重建过程以跳出局部最优并准备下一次的迭代过程。该算法结构非常简单，参数较少，且求解效果非常好。Ruiz和Stutzle随后又将该算法用于具有顺序相关准备时间的flow shop问题，取得了较好的效果。Panetal.提出了改进的IG算法用于零等待的flow shop问题。Framinan和Leisten提出了一种多目标IG算法用于flow shop调度。

差分进化差分进化(differential evolution, DE )是由Storn和Price于1997年提出的一种智能优化算法。它是一种针对实变函数优化的随机搜索算法，也可看作是遗传算法的进一步扩展。差分进化算法利用选择、交叉和变异三个操作来更新种群个体。首先，利用父代个体间的差分矢量进行变异得到变异个体;然后，该变异个体以一定的概率与父代个体进行交叉得到一个试验个体;最后，采用一对一的竞争机制贪婪地选择试验个体和父代个体之间的较优者作为子代对种群进行更新。DE具有原理简单、易于实现、全局寻优能力较好、鲁棒性强等特点，因此在科学研究和工程应用领域都得到了广泛应用。

人工蜂群人工蜂群跟粒子群算法类似，人工蜂群算法也是通过模拟生物界群体智能行为而提出一种群智能算法。蜂群算法的关键在于:群体中的蜜蜂跟它的邻居蜜蜂之间的信息交流和传播能力使得蜜蜂可以利用其他蜜蜂的信息去寻找最好的食物源。ABC算法最早是由土耳其的Karaboga在2005年提出来的。之后，其研究团队又对系统地研究了该算法的性能。在基本的ABC算法中，用食物源表示问题的解，蜂群中的个体分成三种:雇佣蜂、旁观蜂和侦察蜂。去探索其对应的食物源的蜜蜂称为雇佣蜂，在蜂房中等待并决定选择哪个食物源的蜜蜂称为旁观蜂，而侦察蜂负责进行随机搜索。2