智能优化算法的综述教学研究

科技创新导报２００８　　ＮＯ．１３

高　新　技　术

智能优化算法的综述教学研究

莫愿斌１　　刘贺同２　　王勤２

（１．广西民族大学数学与计算机科学学院　　广西南宁　　５３０００６；　２．中国计量学院理学院　　浙江杭州　　３１００１８）

摘　要：本文就优化算法问题的综述与教学做了几方面的研究，以提高对该问题的教学质量、增强初学者对智能算法的认识，也促进对该问题的进一步研究。

关键词：智能优化算法　　模拟退火算法　　禁忌搜索算法　　遗传算法　　蚁群算法　　粒子群算法　　教学研究中图分类号：Ｏ１３文献标识码：Ａ文章编号：１６７４－０９８Ｘ（２００８）０５（ａ）－０００２－０２

１　引言

优化是科学研究，工程技术和经济管理领域的重要研究对象。例如，工程设计中怎样选择参数，使设计方案既满足要求又能降低成本；资源分配中，怎样分配有限资源，使分配方案既满足各方面的基本要求，又能获得好的经济效益；在人类活动的各个领域中，诸如此类，不胜枚举。

优化问题广泛存在于各领域，对该问题的求解研究从未停止。自从优化问题提出以来，人们提出了各种各样的优化算法，特别是近几年以模拟生物的群体智能而设计的算法出现了兴起。然而对各种智能算法综述教学研究却很少有人涉及。优化问题是个古老的课题。目前对优化问题的求解研究有两个发展方向；一个是以分析与泛函为基础的，对优化问题进行严格的理论证明，提出确切的求解算法，这些算法只要求解的问题满足一定的条件，保证能求出问题的最优解；另一个方向就是以自然界生物群体所表现出的智能现象为基础而设计的智能算法，这些算法虽然不能够保证一定能得到问题的最优解，但这些算法的特点是，算法机理简单，易于理解，而且算法设计简洁，对目标函数没有特殊的要求，易于编程计算，能在可接受的时间范围内给出问题的一个满意的解；因此对智能优化算法的研究是当今的热点。

一方面是各种纷繁的智能算法的提出，另一方面是对智能优化算法的综述教学研究没有得到广泛的重视，让许多初学者对这些算法感到迷惑，也给智能算法的进一步研究造成了阻碍。基于这样的情况，对智能算法的综述教学研究显得尤为重要。本文就优化问题的定义、优化问题的求解算法发展演变、智能、智能优化算法、智能优化算法的发展前景作了阐述与分析研究，以使初学者对优化问题的整个发展与求解算法的演变有一个整体的认识，加深了对智能算法的理解，促进了智能算法的进一步研究与发展。

３　优化问题的求解算法及其发展演变

求优化问题（１）的解就是寻找一（称为可行域，就是满足（１）中所有约束条件的点组成的集合），使得每一

个，恒成立

，则就称为（１）的解。自从优化问

题提出以来，人们对优化问题的求解提出了各种求解算法。

３．１　经典精确优化算法

主要用来处理目标函数以及约束条件有具体的解析表达式且存在导数的情况。它是先利用求导或者变分法得到极值点存在的必要条件，通常是一组方程或不等式，然后再求解此方程或不等式［１］。３．２　经典近似优化算法

利用经典精确算法求解最优解的主要不足是，（１）在目标函数比较复杂时，这时求导将很困难；（２）求解通过求导以后所建立的方程组，有时也非常的不易。为此，人们通过各种

最优解的性质（如梯度的性质）建立迭代公式求最优解。

如：对无约束优化问题，牛顿法［２］的基本迭代式为：

确的定义是不现实的。知识的阈值理论认为：智能就是在巨大的搜索空间中迅速找到一个满意解的能力［３］。麻省理工学院的布鲁克又提出［３］，智能是在任意给定的环境和目标的条件下，正确制定决策和实现目标的能力。

５　智能优化算法

从上世纪９０年代以来，一些学者开始注意到某些生物诸如蚂蚁、蜜蜂、鸟群和鱼群等群居生物依靠整个集体的行为能够完成觅食、清扫、搬运、御敌等高效的协同工作，能够建立起坚固、漂亮和精确的巢穴，能够在高速运动过程中保持和变换优美有序的队形等许多令人匪夷所思的事情。按以上对智能的理解，这就是一种智能行为。而人们正是由于受到这些生物行为的启发，将得到的这些方法和计算机科学相结合来解决一些传统问题和实际应用中出现的新问题；这就是智能算法。智能优化算法发展至今，提出了各种不同的智能优化算法，但主要的有下面几种。５．１　模拟退火算法

模拟退火算法［４］（ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ，ＳＡ）是基于Ｍｏｎｔｅ　Ｃａｒｌｏ迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性（即：退火过程中，固体最终达到能量最小的状态，对应于优化算法最终找到了最优解）而设计的一种智能优化算法，该算法将固体的退火过程与优化问题的求解过程有机的结合起来，因此该算法被称为模拟退火算法。算法主要包括：新状态产生函数、新状态接受函数、退温函数、抽样稳定准则和退火结束准则（简称三函数两准则）。算法开始时设计一个所谓的初始温度。初始温度和上面的三函数两准则将是直接影响算法优化结果的主要环节。算法运行时是从某一较高初温开始，结合具有概率突跳特性的Ｍｅｔｒｏｐｏｌｉｓ抽样策略在解空间中随机寻找目标函数的全局最优解，伴随温度参数的不断下降重复抽样过程，最终得到问题的全局最优解。５．２　禁忌搜索算法

所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不足，禁忌搜索算法（ＴＳ）用一个禁忌表来记录已经达到过的局部最优点，在下一次的搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。禁忌对象、禁

其中

３．３　优化算法的近期发展趋势

上面的经典精确算法与近似算法，都必须建立在目标函数存在导数的性质条件下进行，而在实际中碰到的很多优化问题的目标函数并不都存在导数。因此，近年来以模拟物质变化过程或模拟生命体而设计的搜索方式为基础提出各种算法，此类算法有人称之为智能算法，有人称之为仿生算法、也有人称之为演化算法或进化算法，这类算法的本质都属于随机性算法。此类算法最大的优点就是不需要目标函数具有可导性，甚至不需要目标函数有明确的表达形式，只要知道输入输出即可，所以这类算法适应了科技发展的要求，而且随着其在优化领域取得的成功，日益引起了人们的关注。越来越多的人加入到此类算法的研究之中，并对之作出诸多改进，使其更适合优化问题，所以对此类算法的研究将给求解优化问题带来新的活力。

２　优化问题的定义

所谓优化问题，就是在满足一定的约束条件下，寻找一组参数值，使系统的某些性能指标达到最大或最小。而求一个函数f的最大，

总可以转换为求－f的最小，因此优化问题的数学模型一般可表示为

４　智能

什么是智能？智能的本质是什么？这是科学家一直在探索和研究的问题，但至今仍然没有完全解决。要从本质上给智能下一个精

　　（１）

２

科技创新导报　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｎｏｖａｔｉｏｎ　Ｈｅｒａｌｄ