2.8　人工智能的典型算法

如今，人工智能的算法多种多样，并应用于各领域中。下面对几种常用的典型智能算法进行简要介绍。

1．差分进化算法

差分进化算法（Differential Evolution，DE）是一种新兴的进化计算技术。它由Storn等于1995年提出，其最初的设想是用于解决切比雪夫多项式问题，但后来发现差分进化算法也是解决复杂优化问题的有效技术。

差分进化算法是基于种群智能理论的优化算法，是通过种群内个体间的合作与竞争产生的智能优化搜索。但相比于进化计算，差分进化算法保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了进化计算的复杂性。同时，差分进化算法特有的记忆能力使它可以动态跟踪当前的搜索情况，以调整其搜索策略。它具有较强的全局收敛能力和稳健性，并且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法很难求解，甚至无法求解的复杂优化问题。

2．免疫算法

最早的免疫系统模型是由Jerne于1973年提出的，他基于Burnet的克隆选择学说开创了独特型网络理论，给出了免疫系统的数学框架，并采用微分方程建模仿真淋巴细胞的动态变化。Farmal等于1986年基于免疫网络学说理论构造出了免疫系统的动态模型，展示了免疫系统与其他人工智能方法组合的可能性，开创了免疫系统研究的先河。

免疫算法（Immune Algorithm，IA）是模拟生物免疫机制并结合基因的进化机理，人工构造出的一种新型智能搜索算法。免疫算法具有一般免疫系统的特征，采用种群搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解。相比于其他算法，免疫算法利用自身产生多样性和维持机制，保证了种群的多样性，克服了一般寻优过程（特别是多峰值的寻优过程）中不可避免的“早熟”问题，可求得全局最优解。免疫算法具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点。

3．模拟退火算法

模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热时，粒子间的布朗运动增强，到达一定强度后，固体物质会转化为液态，此时再进行退火，粒子热运动减弱，并逐渐趋于有序，最后达到稳定。

模拟退火的解不再像局部搜索那样依赖初始点。模拟退火算法引入了一个接受概率p。如果新的点（设为pn）的目标函数f(pn)更好，则p=1，表示选取新点；否则，接受概率p是当前点（设为pc）的目标函数f(pc)。也就是说，模拟退火不像局部搜索那样每次都贪婪地寻找比现在好的点，目标函数差一点的点也有可能接受进来。随着算法的执行，系统温度T逐渐降低，最后终止于某个温度，在该温度下，系统不再接受变化。

模拟退火的典型特征是除了接受目标函数的改进，还接受一个衰减极限，当T较大时，接受较大的衰减；当T逐渐变小时，接受较小的衰减；当T为0时，不再接受衰减。这一特征意味着模拟退火与局部搜索相反，它能避开局部极小，并保持局部搜索的通用性和简单性。

在物理上，首先加热，让分子互相碰撞，变成无序状态，内能加大；然后降温；最后的分子次序反而会更有序，内能比没有加热前更小。

值得注意的是，当T为0时，模拟退火就成了局部搜索的一个特例。

4．遗传算法

“物竞天择，适者生存”是进化论的基本思想。遗传算法就是模拟自然界想做的事。遗传算法可以很好地用于优化问题，若把它看作对自然过程高度理想化的模拟，则更能显示出它本身的优雅（虽然生存竞争是残酷的）。

遗传算法以一种群中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始种群的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优化搜索算法，遗传算法以其简单通用、健壮性强、适于并行处理，以及高效、实用等显著特点，在各个领域得到了广泛的应用，取得了良好的效果，并逐渐成为重要的智能算法之一。

5．禁忌搜索算法

为了找到全局最优解，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域及其邻域进行搜索，导致一叶障目、不见泰山。禁忌搜索就是有意识地避开局部最优解（但不是完全隔绝），从而获得更多的搜索区间。如同兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰就脱颖而出了。

当兔子们再去寻找时，一般会有意识地避开泰山，因为它们知道，这里已经找过，并且有一只兔子留守在这里。这就是禁忌搜索中“禁忌表”的含义。那只留守在泰山的兔子一般不会在这里安家，它会在一段时间后重新回到找最高峰的队伍中，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑。这个归队时间，在禁忌搜索里面叫作“禁忌长度”；如果在搜索的过程中，留守在泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，那么兔子们就不得不再次考虑选中泰山。也就是说，当一个有兔子留守的地方的优越性太突出时，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就是“特赦准则”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法优化的关键也在这里。

6．蚁群算法

蚁群算法（Ant Colony Optimization，ACO）是由意大利学者M.Dorigo、V.Maniezzo和A.Colorni等于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法，是群智能理论研究领域的一种主要算法。

蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径，并且能随环境的变化自适应地搜索新的路径。其根本原因是蚂蚁在寻找食物时，能在其走过的路径上释放一种特殊的分泌物——信息素。随着时间的推移，该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，后来的蚂蚁选择该路径的概率也就越大，从而进一步增大了该路径上的信息素强度。强度大的信息素会吸引更多的蚂蚁，从而形成一种反馈机制。通过这种反馈机制，蚂蚁最终可以发现最短路径。蚁群算法具有分布式计算、无中心控制和分布式个体之间间接通信等特征，易与其他优化算法相结合。它通过简单个体之间的协作，表现出了求解复杂问题的能力，已经广泛应用于优化问题的求解中。

7．粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是一种进化计算技术，于1995 年由Eberhart 博士和kennedy博士提出。该算法最初是受到飞鸟集群活动的规律性的启发，进而利用种群智能建立的一个简化模型。粒子群算法在对动物集群活动行为进行观察的基础上，利用种群中的个体对信息的共享使整个种群的运动在问题求解空间中产生从无序到有序的演化，从而获得最优解。

PSO与遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。但是它没有遗传算法中的交叉及变异，而是粒子在解空间追随最优的粒子进行搜索。与遗传算法相比较，PSO的优势在于简单、容易实现，并且没有许多参数需要调整。目前，PSO已广泛应用于函数优化、神经网络训练、模糊推理系统控制及其他遗传算法的应用领域。

PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物，而在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？最简单、有效的方法就是搜寻目前离食物最近的鸟的周围区域。

PSO从这种模型中得到启示并用于解决优化问题。在PSO中，每个优化问题的解都是搜索空间中的一只鸟，我们称之为粒子。所有的粒子都有一个由被优化的函数决定的适应度值，每个粒子都还有一个速度，决定它们飞翔的方向和距离。然后，粒子们就追随当前的最优粒子在解空间中进行搜索。

PSO初始化为一群随机粒子（随机解），然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个极值来更新自己：一个极值就是粒子本身找到的最优解，这个解叫作个体极值pbest；另一个极值是整个种群目前找到的最优解，这个极值是全局极值gbest。另外，也可以不用整个种群而只是用其中一部分作为粒子的“邻居”，那么所有“邻居”中的极值就是局部极值。

8．神经网络算法

人工神经网络（Artificial Neural Network，ANN）简称神经网络或连接模型。早在1943年，心理学家McCulloch和数学家Pitts就合作提出了形式神经元的数学模型，从此开创了神经科学理论研究的时代；1957年，Rosenblatt提出的感知器模型由阈值性神经元组成，试图模拟动物和人脑的感知与学习能力；1982年，H.Hofield提出了具有联想记忆功能的Hopfield神经网络，引入了能量函数的原理，给出了网络的稳定性判据，这一成果标志着神经网络的研究取得了突破性的进展。

神经网络具有一些显著的特点：具有非线性映射能力；不需要精确的数学模型；擅长从输入/输出数据中学习有用知识；容易实现并行计算；由大量的简单计算单元组成，易于用软/硬件实现；等等。因为神经网络是一种模仿生物神经系统的新的信息处理模型，并具有独特的结构，所以人们期望它能够解决一些用传统方法难以解决，甚至无法解决的问题。迄今为止，已经出现了许多神经网络模型及相应的学习算法。其中，Rumelhart和McClelland于1985年提出的BP网络的误差反向传播学习算法是一种较常用的神经网络算法。