人工智能并行算法-并行禁忌算法

**

人工智能：智能优化算法

优化问题是指在满足一定条件下，在众多方案或参数值中寻找最优方案或参数值，以使得某个或多个功能指标达到最优，或使系统的某些性能指标达到最大值或最小值。优化问题广泛地存在于信号处理、图像处理、生产调度、任务分配、模式识别、自动控制和机械设计等众多领域。优化方法是一种以数学为基础，用于求解各种优化问题的应用技术。各种优化方法在上述领域得到了广泛应用，并且已经产生了巨大的经济效益和社会效益。实践证明，通过优化方法，能够提高系统效率，降低能耗，合理地利用资源，并且随着处理对象规模的增加，这种效果也会更加明显。

在电子、通信、计算机、自动化、机器人、经济学和管理学等众多学科中，不断地出现了许多复杂的组合优化问题。面对这些大型的优化问题，传统的优化方法（如牛顿法、单纯形法等）需要遍历整个搜索空间，无法在短时间内完成搜索，且容易产生搜索的“组合爆炸”。例如，许多工程优化问题，往往需要在复杂而庞大的搜索空间中寻找最优解或者准最优解。鉴于实际工程问题的复杂性、非线性、约束性以及建模困难等诸多特点，寻求高效的优化算法已成为相关学科的主要研究内容之一。

受到人类智能、生物群体社会性或自然现象规律的启发，人们发明了很多智能优化算法来解决上述复杂优化问题，主要包括：模仿自然界生物进化机制的遗传算法；通过群体内个体间的合作与竞争来优化搜索的差分进化算法；模拟生物免疫系统学习和认知功能的免疫算法；模拟蚂蚁集体寻径行为的蚁群算法；模拟鸟群和鱼群群体行为的粒子群算法；源于固体物质退火过程的模拟退火算法；模拟人类智力记忆过程的禁忌搜索算法；模拟动物神经网络行为特征的神经网络算法；等等。这些算法有个共同点，即都是通过模拟或揭示某些自然界的现象和过程或生物群体的智能行为而得到发展；在优化领域称它们为智能优化算法人工智能并行算法，它们具有简单、通用、便于并行处理等特点。

**

1 进化类算法**

**

自然界的生物体在遗传、选择和变异等一系列作用下，优胜劣汰，不断地由低级向高级进化和发展，人们将这种“适者生存”的进化规律的实质加以模式化而构成一种优化算法，即进化计算。进化计算是一系列的搜索技术，包括遗传算法、进化规划、进化策略等，它们在函数优化、模式识别、机器学习、神经网络训练、智能控制等众多领域都有着广泛的应用。其中，遗传算法是进化计算中具有普遍影响的模拟进化优化算法。 为了求解切比雪夫多项式问题，Rainer Storn和Kenneth Price根据这种进化思想提出了差分进化算法。它是一种采用实数编码、在连续空间中进行随机搜索、基于群体迭代的新兴进化算法，具有结构简单、性能高效的特点。而免疫算法是模仿生物免疫机制，结合基因的进化机理，人工地构造出的一种新型智能搜索算法。该算法具有一般免疫系统的特征，它采用群体搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解，相当于属于进化算法的变种算法。

1.1 遗传算法

遗传算法（Genetic Algorithm，GA）是模拟生物在自然环境中的遗传和进化过程而形成的自适应全局优化搜索算法。它最早由美国的J. H. Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究；70年代，K. A. De Jong基于遗传算法的思想，在计算机上进行了大量的纯数值函数优化计算试验；80年代，遗传算法由D. J. Goldberg在一系列研究工作的基础上归纳总结而成。

遗传算法是 通过模仿自然界生物进化机制而发展起来的随机全局搜索和优化方法。它借鉴了达尔文的进化论和孟德尔的遗传学说，本质上是一种并行、高效、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作：使用“适者生存”的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境。

1.2 差分进化算法

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

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

1.3 免疫算法

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

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

**

2 群智能算法

**

群智能指的是“无智能的主体通过合作表现出智能行为的特性”，是一种基于生物群体行为规律的计算技术。它受社会昆虫（如蚂蚁、蜜蜂）和群居脊椎动物（如鸟群、鱼群和兽群）的启发，用来解决分布式问题。它在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了一种新的思路。

群智能方法易于实现，其算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需要目标函数的输出值，而不需要其梯度信息。已完成的群智能理论和应用方法研究证明：群智能方法是一种能够有效解决大多数全局优化问题的新方法。近年来群智能理论研究领域出现众多算法，如：蚁群算法、粒子群算法、鱼群算法、蜂群算法、猫群算法、狼群算法、鸡群算法、鸟群算、文化算法、杂草算法、蝙蝠算法、布谷鸟算法、果蝇算法、蛙跳算法、细菌觅食算法、萤火虫算法和烟花算法，等等。其中蚁群算法和粒子群算法是最主要的两种群智能算法。群智能理论研究领域有两种主要的算法：蚁群算法和粒子群算法。前者是对蚂蚁群体食物采集过程的模拟，已成功应用于许多离散优化问题；后者起源于对简单社会系统的模拟人工智能并行算法，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化算法。

2.1 蚁群算法

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

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

2.2 粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是Kennedy和Eberhart受人工生命研究结果的启发，通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法；1995年IEEE国际神经网络学术会议上发表了题为“Particle Swarm Optimization”的论文，标志着粒子群算法的诞生。粒子群算法一经提出，由于它算法简单，容易实现，立刻引起了进化计算领域学者们的广泛关注，成为一个研究热点。

粒子群算法与其他进化算法一样，也是基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索。同时，它又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体中的个体看成是在D维搜索空间中没有质量和体积的粒子，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbestpbest和邻域历史最佳位置gbestgbest聚集，实现对候选解的进化。粒子群算法因具有很好的生物社会背景而易于理解，由于参数少而容易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注。

**

3 模拟退火算法

**

模拟退火算法（Simulated Annealing，SA）的思想最早由Metropolis等人于1953年提出。Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题。模拟退火算法是一种基于Monte Carlo迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其目的在于：为具有NP（Non-deterministic Polynomial）复杂性的问题提供有效的近似求解算法，它克服了传统算法优化过程容易陷入局部极值的缺陷和对初值的依赖性。

模拟退火算法是一种通用的优化算法，是局部搜索算法的扩展。它与局部搜索算法的不同之处，是以一定的概率选择邻域中目标值大的状态。从理论上来说，它是一种全局最优算法。模拟退火算法具有十分强大的全局搜索性能，这是因为它采用了许多独特的方法和技术：基本不用搜索空间的知识或者其他的辅助信息，而只是定义邻域结构，在邻域结构内选取相邻解，再利用目标函数进行评估；采用概率的变迁来指导它的搜索方向，它所采用的概率仅仅是作为一种工具来引导其搜索过程朝着更优化解的区域移动。因此，虽然看起来它是一种盲目的搜索方法，但实际上有着明确的搜索方向。

**

4 禁忌搜索算法

**

搜索是人工智能的一个基本问题，一个问题的求解过程就是搜索。人工智能在各应用领域中，被广泛地使用。现在，搜索技术渗透在各种人工智能系统中，可以说没有哪一种人工智能的应用不用搜索技术。

禁忌搜索算法（Tabu Search or Taboo Search，TS）的思想最早由美国工程院院士Glover教授在1986年提出，并在1989年和1990年对该方法做出了进一步的定义和发展。在自然计算的研究领域中，禁忌搜索算法以其灵活的存储结构和相应的禁忌准则来避免迂回搜索，在智能算法中独树一帜，成为一个研究热点，受到了国内外学者的广泛关注。禁忌搜索算法是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。它通过禁忌准则来避免重复搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效搜索，以最终实现全局优化。

**

5 神经网络算法

**

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

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

**

参考文献

**

《智能优化算法及其MATLAB实例（第2版）》，包子阳，电子工业出版社。