桂洪照 东北大学CCF会员



几种具有代表性的启发式算法研究

桂洪照 东北大学CCF会员

【文章摘要】

启发式算法（Heuristic Algorithm）来自人类对地球生物圈的感悟。人类从生物圈的运行规律中摸索出很多方法与理论。本文介绍了五种重要的启发式算法，退火模拟算法，蚁群算法，遗传算法与人工神经网络算法。

0 引言

启发式算法 （Heuristic Algorithm )相对于最优化算法提出。随机概率群体寻优过程当中，个体能够利用自身或者全局的经验来制定各自的搜索策略，就像算法拥有智能一样。启发式算法最初的概念在上世纪40年代提出，有了人工网络的概念，50年代退火模拟算法，70年代遗传算法，80年代禁忌搜索，90年代蚁群算法。随着发展更多的启发式算法被人们所知，粒子群算法，人工蜂群算法，甚至还有情感算法等，它们每个拥有自己的特点，在其相对的特定问题上为人类做出了巨大的贡献。

1 具体算法

（Traveling Salesman Problem,TSP）旅行商问题是测验算法能力的一个很好的试验场，本篇论文将以TSP问题为例对每个算法做出解释。

1.1退火模拟算法

模拟退火算法（Simulated Annealing，SA）是一种启发式算法，最早的思想是由N. Metropolis等人于1953年提出，SA的核心为模拟物理中材料先加热再缓慢冷却以改善其结构的工艺过程，温度由高变低时，由无序活动变为有序稳定，下图。用热力学系统来模拟求解优化问题。把系统的能量看作目标函数，把物理系统降温的过程模拟成算法在执行中的优化过程。它从一个给定初始解开始（较高），随机在邻域产生另一个解，它按照一定概率接受比当前解更差的邻域。

算法步骤

1) 首先,需要设置初始温度和创建随机的初始解

2) 然后开始循环,直到满足停止条件

3) 把当前的解决方案做一些小的改变，选择新的相邻的方案

4) 决定是否移动到相邻的解决方案

5) 降低温度,继续循环，得到结果

模拟退火算法有不错的全局收敛性和鲁棒性, 可以方便的并行计算, 有较大概率求得全局最优解, 然而 SA 算法运算效率较低, 优化时间较长。

1.2蚁群算法

蚁群优化(Ant Colony Optimization ACO)由M.Dorigo等人在1992年发布。蚂蚁在移动时候会释放一些信息素，这些信息素使得蚂蚁会跟着前面的同伴走，高的信息素浓度能够吸引更多的蚂蚁。蚂蚁走过的路径越短，信息素积累得越快，浓度越高，最终所有蚂蚁都选择了短路径。在蚂蚁选择信息素浓度较高的路径时，蚂蚁有一定概率寻找新的路径（explore），如果新路径更短，那么蚂蚁将被吸引过来，经过一定次数的重复蚂蚁最终就能找到巢穴和食物间的最短路径。

算法步骤（以最短路径问题为例）

1）给每条路径上的信息素浓度赋予初值，把a只模拟蚂蚁放在b个点上

2）依照概率函数，让每只蚂蚁找出可行路径，计算路径长度,选出最优路径

3）根据路线情况,更新本次最短路径上的信息素浓度，返回前面循环直到得到最优路径。

ACO有正反馈与并行性、智能适应的特点。但计算量大，消耗时间久, 常常由于过程中得到较好解影响，陷入局部最优解, 使算法结束。

1.3遗传算法

遗传算法（Genetic Algorithm）GA[16]通过模拟生物学的自然选择和自然遗传机制来解决问题，它由J.Holland教授于1975年提出,GA模拟自然界生物进化过程，它将问题域中的可能解看作是群体的一个个体或染色体。依照遗传选择，自然淘汰的生物进化过程，对群体反复进行操作。用适应度函数进行评价，保留适应的种群，淘汰不适应的种群。并将最优种群进行变异杂交，通过繁殖得到更好的后代。同时使用全局并行搜索来寻找群体的最优个体来得到最优解。GA有三个基本操作：变异：即按一定概率随机改变某个体的基因值。交叉：将父本个体按照一定的概率随机地交换基因形成新的个体。选择：体现了适者生存，优胜劣汰的进化规则。

算法步骤

1）制定搜寻策略与R(控制参数)，随机产生初始种群A，进化代数 i= 1.

2）对A进行评价, 若进化代数无法累加或达到终止条件则终止算法，输出最佳个体解.

3）操作种群（交叉变异），处理边界条件，得到临时种群B并对其评价，计算每个个体的适应度值

4）操作种群（选择）得到新种群.i=i+1，跳到步骤2.

遗传算法使用范围广，能够处理大多数组合优化问题，处理简单不需要有很高的数学水平, 能够并行处理，具有较优秀的全局搜索能力，然而常有早熟收敛的现象。

1.4人工神经网络算法

人工神经网络 ( Artificial Neural Network , ANN) 模仿人类的大脑思维及运行方式，它起源于脑神经元学说，在构成原理和功能特点等方面更加接近人脑，不是按给定的程序一步一步地执行运算，而是能够自身适应环境、总结规律、完成某种运算。它的研究应追溯至本世纪40年代。1982年，Hopfield等人将Hopfield网用于TSP问题的求解，给神经网络在计算机领域的应用打下基石。这种网络由神经元连接成非线性动态系统，通过引入能量函数概念，通过网络状态的变化让能量不断减少，最后达到平衡时即达到最优解。

算法步骤：

1）初始化各层连接权值，把问题映射为换位矩阵E。

2） 将E与 神经网络对应, 每条路径对应E的元素。

3） 设定能量函数BP, BP的min值点对应问题的解。

4）计算神经网络的E和偏置电流,。

5）运行网络直至局部最优解。

Hopfield神经网络快速且简单，记忆性强，能够存储大量的数据，但是其优化性较差。实验表明, 神经网络算法只有局部搜索能力, 若是要提高解有效性概率，那么解的优化能力降低, ,需要恰当的网络运行参数的设置。

2 结束语

在人类对启发式算法研究长达半个世纪中，涌现出了很多有思想有新意的优秀算法。但是启发式算法目前仍有不足，它缺乏统一、完整的理论体系，并且面对局部最优的问题上略有不足。启发式算法需要进行大量的计算，通常遇到大型问题，其计算量更是呈现指数型增长。由于近年来技术的勃发，启发式算法的前景相当广大。蚁群算法结合了mapreduce并行计算，有效的减少了其计算的时间。一类被称为超启发式算法（Hyper-Heuristic Algorithm）的新算法类型在智能计算领域的著名国际会议上出现。研究者们结合他们的灵活思维将不同的算法结合取得到了非常好的成果。随着人类的不断进步，启发式算法在智能计算领域的地位越来越重要，应用的领域越来越广。