智能优化算法的比较与改进

开篇：润墨网以专业的文秘视角，为您筛选了一篇智能优化算法的比较与改进范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：本文阐述了几种常用智能优化算法的基本思想，概括了它们的本质特征，对智能优化算法进行了分类，并指出了智能优化算法的改进方向。

关键词：智能优化算法 个体行为 群体智能

智能优化算法概述

传统优化算法本质上是全局搜索算法，即通过搜索整个解空间来找到问题的最优解。为了加快算法的搜索速度或减少运行时计算空间的耗费，传统优化算法往往需要充分利用目标函数的解析性质以及约束空间的几何特征，逐步缩小搜索空间，最终完成整个解空间的搜索，从而找到最优解。但随着问题越来越复杂，规模越来越大，传统优化算法已经不能在可以接受的时间内找到最优解。这里求解时间与最优解是一对矛盾，为了解决这一矛盾，有些研究者提出了一类新的解决方法，它们不以寻找问题的最优解为目的，而是追求在有限的时间内找到满足需要的解即可。这类方法往往借鉴了人类解决复杂问题的技巧以及生物体的本能，能够将复杂的求解过程简单化，从而表现出“智能”的特征，因此被称为“智能算法”。常用的智能优化算法有：遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法、粒子群算法等。

智能优化算法按群体规模大小可以简单分为两类：基于个体行为的算法与基于群体智能的算法。其中，禁忌搜索算法、模拟退火算法等属于基于个体行为的智能算法；遗传算法、蚁群算法、粒子群算法、免疫算法、细菌觅食算法、人工鱼群算法、Memetic算法、捕食搜索算法等属于基于群体智能的算法。

1、禁忌搜索算法

人类的行为具有记忆性，即对过去行为的记忆往往对眼下及未来的行为具有指引性，所谓“吃一堑，长一智”，“一朝被蛇咬，三年怕井绳”讲的就是这个道理。禁忌就是禁止重复前面的工作，类似人类的记忆行为。禁忌搜索算法为了避免局部邻域搜索陷入局部最优解，引入禁忌表来记录已经搜索过的局部最优解，在下一次搜索中，不再有选择地搜索这些点，以此来跳出局部最优解。同时，禁忌搜索算法还引入“破禁”或特赦的思想，当被禁忌的解优于历史最优解，会被解禁。此外，禁忌表的长度类似人类的遗忘周期，当禁忌表填满禁忌对象时，新进的禁忌对象会挤出最早进入禁忌表中的对象，算法下一次搜索就可以重新选择被解禁的对象。

2、模拟退火算法

模拟退火算法本质上是一种概率搜索算法，算法每次迭代都以一定的概率选择搜索邻域外的解，即算法总能以一定的概率跳出局部最优解，如果这个解优于历史最优解，算法会集中在这个解的附近搜索，直到以一定的概率找到更好的解。模拟退火算法类似人类的随机漫步行为以及固体物体的退火过程。该算法将固体的退火过程与优化问题的求解过程有机的结合起来，因此被称为模拟退火算法。算法运行时从某一较高初温开始，结合具有概率突跳特性的Metropolis抽样策略在解空间中随机寻找目标函数的全局最优解，伴随温度参数的不断下复抽样过程，最终得到问题的近似最优解。模拟退火算法理论上属于全局最优算法，但实际中只需在一定的时间内找到近似解即可。

3、遗传算法

遗传算法模拟生物进化和生命遗传的过程，将问题的解编码成基因串，通过选择、交叉、变异三个遗传算子，完成种群的繁衍、进化。其本质是一种通过交换机制，重组基因串的概率搜索算法。由于遗传算法渗透了“优胜劣汰、适者生存”的遗传和进化思想，至今仍是应用最广泛也是最为成功的算法。

4、蚁群算法

蚁群算法是通过模仿蚂蚁觅食行为而设计出来的一种智能优化算法。单个蚂蚁的行为极其简单，谈不上智能，但由蚂蚁个体组成的蚁群能够协助合作，总能找到一条从蚁巢到食物源的最短路，其行为表现出高度的智能。研究发现，蚂蚁个体之间通过一种称之为信息素的物质进行信息传递，即蚂蚁个体之间能够共享信息，从而能够相互协作，完成复杂的任务。蚂蚁在觅食过程中，能够在它所经过的路径上留下信息素，而且能够感知信息素的存在及其强度，从而指导自己朝着信息素强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大。蚁群个体之间就是通过这种信息的交流、共享机制，从而达到寻找食物的目的。人类野外寻找路径以及在陌生领域内探索研究，与蚁群个体之间通过信息的交流、共享，完成食物的搜索一样，具有相同的本质特征。后来者总是沿着前人开辟的道路前进，只有某条路不能再前行了，人们才会去开辟新的道路。所谓“世上本没有路，走的人多了，也就成了路”，讲的就是信息共享的道理。但正反馈机制既是蚁群算法的优点，也是其缺点，蚁群算法很容易出现停滞现象。当局部最优解路径上的信息素强度较强时，正反馈机制会继续放大这条路径上的信息素强度，从而使得算法很快陷入局部最优解。这时，正反馈机制就不再是“正反馈”，而是“负反馈”了，这与“羊群效应”或“盲从现象”是类似的了。

5、粒子群算法

粒子群优化算法是模拟鸟类迁徙行为而设计出来的一种智能算法，最早由Kenney与Eberhart于1995年提出。鸟类在迁徙途中总能根据自身的位置以及周围同伴的位置调整飞行方向，因此整个鸟群能够保持完美的飞行阵型，这种充满美学的行为背后是鸟类个体之间相互学习的机制发挥了作用的结果。粒子群优化算法正是借鉴这种学习机制，微粒个体通过记住自身历史最好解以及群体的历史最优解，并结合自身的位置随时调整飞行方向，从而经过一段时间就能飞向最优解。PSO后来经过多次的改进，去除了原来算法中一些无关的或冗余的变量，又加入了一些随机变化的量，使得鸟群的运动更象是空间微粒的运动，所以称之为微粒群算法。

智能优化算法的本质与比较

禁忌搜索算法和模拟退火算法都是基于个体行为的智能优化算法。禁忌搜索算法通过禁忌表记录局部历史最优解，本质上类似人类的记忆行为，而模拟退火算法通过随机选择来跳出局部最优解，本质上类似人类的随机漫步行为。人类行为兼具记忆性与随机性两种特征，即对过去行为的记忆往往对眼下及未来的行为具有指引性，这往往是确定性的，而人类行为还具有随机性的特征，即人类行为往往还是偶发的、不可琢磨的、随机的。

遗传算法、蚁群算法、粒子群算法等属于基于群体智能的算法，这些算法通过模拟群体生物之间信息交换、信息共享以及学习机制，通过迭代逐步选出优质解。基于群体智能的算法又分为两类，一类是基于个体编码结构的智能算法，另一类是基于个体与群体行为特征的智能算法。遗传算法、蚂蚁算法等属于基于个体编码结构的智能算法，这类算法以选优解的编码结构为基础，通过交换、变异与信息素标记即共享来重组个体编码，换言之，这类算法假定选优解的部分编码结构必优，通过重组优质解的部分编码结构能够找到群体优质解。粒子群算法属于基于个体与群体行为特征的智能算法，粒子群算法以个体与群体行为特征向量即飞行方向向量来调整个体行为，最终达到个体行为与群体行为的协调统一，从而得到优质解。

智能优化算法的改进

智能优化算法的改进主要从以下两个方面来改进：

一是算法融合，即在一种算法中通过融合其他算法的优点来改进。算法融合主要有两种方式，一种是在基于群体智能的算法中通过融合个体行为的随机或记忆特征来改进，另一种是在基于个体行为特征的智能算法中引入群体特征如并行机制来改进。二是模仿自然界生物的行为特征创立新型智能优化算法，如捕食搜索算法、人工鱼群算法、细菌觅食算法、免疫算法、Memetic算法等。

总结

本文通过几种常用的智能优化算法的基本思想的介绍，概括了智能优化算法的本质特征与区别，并提出了改进的方向，角度独特，观点新颖，对智能优化算法的研究具有一定的启发性。

（作者单位： 国防信息学院）