智能优化算法概述

.本栏目责任编辑:李桂瑾.....人工智能及识别技术。智能优化算法概述蒋腾旭(九江职业大学计算机系,江西九江332000)摘要:本文简要介绍了几种常见的智能优化算法,并给出了不同智能优化算法的优缺点及在优化应用领域的使用情況,指出了不同智能优化算法的发展趋势。关键词:人工智能;软计算;智能优化算法;优化技术中图分类号:TP18文献标识码:A文章编号:1009 -3044(200)08 -20507-02A Summary of Inelligence Optimum AlgorithmJIANG Teng- xu .(Computer Department, Jiujiang Vocational university, jiujiang 332000,China)Abstract:Some kinds of familiar itelligence optimum algorithm is introduced briely in this paper. The author introduces advantages anddisadvantages of different intelligence optimum algorithm, as well as applications in some optimization fields. Meanwhile, the development trendof each intelligence optimum algorithm is pointed in the paper too.Key wordsartificial itelligence; soft computation; itelligence optimum algorithm; optimization techniques1引言3遗传算法智能计算也称之为“软计算”,是人们受自然界或生物界规律遗传算法[2] (Genetie Algorithm,GA)是一 类 借鉴生物界自然的启发,根据自然界或生物界的原理,模仿其规律而设计的求解选择和自然遗传机制的随机化搜索算法,它是由美国Michigan大问题的算法。自然界-直是人类创造力的丰富源泉,人类认识事学的J.Holland教授于1975年首先提出的。遗传算法模拟生物进物的能力来源于自然界的相互作用之中，自然界的许多自适应优化的基本过程,用数码串来类比生物中的染色个体，通过选择.交化现象不断给人类以启示。近几十年来,.-些与经典的数学规划叉、变异等遗传算子来仿真生物的基本进化过程,利用适应度函原理截然不同的、试图通过模拟自然生态系统机制以求解复杂优数来表示染色体所蕴涵问题解的质量的优劣，通过种群的不断化问题的仿生智能优化算法相继被提出和研究,这方面的内容很“更新换代",从而提高每代种群的平均适应度,通过适应度函数多,如模拟退火算法、遗传算法、人工神经网络技术、人工免疫算引导种群的进化方向,并在此基础上,使得最优个体所代表的问法和群智能算法等。这些算法大大丰富了现代优化技术,也为那题解逼近问题的全局最优解。GA求解问题的基本思想是维持由些传统优化技术难以处理的组合优化问题提供了切实可行的解一群个体组成的种群p() (t代表遗传代数),每一个体均代表问题决方案。以下对几种常用的智能优化算法作简要的概述。的一个潜在解,每-个体都被评价优劣并得到其适应值。个体通2模拟退火算法过遗传算子产生新的个体,新产生的个体继续被评价优劣,从父模拟退火算法[](Simulated Annealing ,SA)是1983 年由代种群和子代种群中选择比较优秀的个体形成新的种群。在若干Kirkpatrick首次提出的一种组合优化算法。该算法来源于固体退代以后.算法收敛到一个最优个体,该个体很可能代表着问题的火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内最优解或次优解。部粒子随温度上升变为无序状态,内能增大。而徐徐冷却时粒子GA是具有“生成+检测"(generate- -and- test)的迭代过程的搜索渐趋有序,在每个温度都达到平衡态，最后在常温时达到基态,内算法，遗传操作算子使GA具有了与传统的其他搜索算法如爬山能减为最小。SA算法借鉴热力学中的能量方程,同时又引入了法、分支界定法、禁忌搜索算法等不同的工作机理,当遇到较大规Metroplis准则,粒子在温度T时趋于平衡的概率为e-OE(KT),其模的问题时,GA有着不可替代的优异性:如GA并不是对问题的中E为温度T时的内能,AE为其改变量,k为Boltzmann常数。算待优化参数本身进行操作，而是通过由这些参数所编码形成的染法的基本思想是从一给定解开始,从邻域中随机产生另一个解,色体进行交叉、变异和选择等操作。GA操作的对象不限于一个,而接受准则允许目标函数在有限范围内变坏,以-定概率接受较差是对由大量对象形成的种群进行操作，这种做法使得参与操作的的解。用固体退火模拟组合优化问题,将内能E模拟为目标函数信息量大,速度快,效果好,使得整个优化过程容易跳出局部最优。值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退GA不依赖于问题领域的信息来指导搜索,GA实现简单，效果良火算法:由初始解i和控制参数初值t开始,对当前解重复“产生好,通用性好,鲁棒性强等。虽然CA具有上述优点，但由于CA本新解-→计算目标函数差-→接受或舍弃”的迭代， 并逐步衰减t值,质上是一种基于概率的启发式随机搜索方法,GA也有自身的缺算法终止时的当前解即为所得近似最优解,SA已经被证明是-陷:如GA是对种群进行概率性操作,所以,在全局寻优上效果良种依概率1收敛于全局最优解的优化方法。好，而在局部寻优上存在不足;在算法进行的前期搜索效果良好,SA的迭代搜索过程以Boltzmann分布概率接受目标函数的而在算法进行的后期搜索速度缓慢;GA虽然实现简单，但实现的“劣化解”，所以SA具有脱离局部最优陷阱的能力，而且具有高效果很大程度上取决于问题的多种参数,如果这些参数设置不好,效鲁棒、通用、灵活的优点。但其参数难以控制，如初始温度T的此时的GA类似随机搜索算法，甚至会出现“早熟收敛"现象。设置太大,算法要花费大量的时间,设置太小,则全局搜索性能可与传统方法相比,遗传算法具有隐式并行性和全局搜索性两能受到影响。还有退火速度问题,也要做合理的设置。大主要特点，作为强有力且应用广泛的随机搜索和优化方法,遗模拟退火算法的应用很广泛，在求解最大截问题(Max Cut传算法可能是当今影响最广泛的进化计算方法之一。近十几年Problem) .0-1背包问题(Zero One Knapsack Problem)、 图着色问题来，遗传算法主要在复杂优化问题求解和工业工程领域应用方(Graph Colouring Problem)、调度问题(Scheduling Problem)等方面效面,取得了一些令十的应用包括:函数率较高。优化、机器学习、当中国煤化工、简切程序设、YHCNMH G收稿日期:2007-02-23作者简介:蒋腾旭(1970-),男,江西九江人,讲师,硕士,研究方向:软件技术、数据挖掘、智能优化算法。507●人工智能及识别技术......本栏目责任编辑:李桂瑾专家系统、作业调度与排序、可靠性设计、车辆路径选择与调度、性,通过计算抗体期望生存率来促进较优抗体的遗传和变异,用成组技术、设备布置与分配等等。记忆细胞单元保存择优后的可行解来抑制相似可行解的继续产4人工神经网络生并加速搜索到全局最优解,同时,当相似问题再次出现时,能较人工神经网络[3] (Artificial Neural Network, ANN)是在对人脑快产生适应该问题的较优解甚至最优解。组织结构和运行机制的认识理解基础之上模拟其结构和智能行与GA类似,标准AIA也使用交叉和变异来对抗体解进行进为的一种工程系统。早在二十世纪四十年代初期，心理学家Mc-化操作,并且采用信息熵的形式来保证抗体的多样性。其求解问Culloch、数学家Pitts就提出了人工神经网络的第-个数学模型,题基本步思想是首先进行问题识别并产生抗体群,初始抗体群通从此开创了神经科学理论的研究时代。常是在解空间用随机的方法产生的。然后计算抗体适应值,生成ANN是生物神经网络的-种模拟和近似,它从结构、实现机免疫记忆细胞,将适应值较大的抗体作为记忆细胞加以保留。再理和功能上模拟生物神经网络。ANN是由大量与自然神经细胞类进行抗体的选择，计算当前抗体群中适应值相近的抗体浓度,浓似的人工神经元互联而成的网络,这种由许多神经元组成的信息度高的则减小该个体的选择概率(抑制);反之,则增加该个体的处理网络具有并行分布结构。每个神经元具有单一输出,并且能选择概率(促进),以此保持群体中个体的多样性。然后进行交叉够与其它神经元连接。网络中存在多重输出连接方法，每种连接.和变异操作,产生新抗体群。最后是抗体群更新,用记忆细胞中适方法对应一个连接权系数。我们可以把ANN看成是以处理单元应值高的个体代替抗体群中适应值低的个体，形成下一代抗体PE(processing elemen)为节点.用加权有向弧(链)相互连接而成的群。在若干代以后,算法收敛到一个最优个体。有向图。ANN以加权值控制结点参与工作的程度,正权值相当于由于生物免疫系统的复杂性使得人工免疫系统的研究不像神经元突触受到刺激而兴奋，负权值相当于受到抑制而使神经元遗传算法、人工神经网络等其他智能方法那样得到足够的发展,麻痹直到完全不工作。但AIA结合了先验知识和生物免疫系统的自适应能力两大特点,ANN解决问题的方式与传统统计方法完全不同,它是模拟人因而鲁棒性较强,具有较强的信息处理能力,并且在对问题进行脑的思维,把大量的神经元连成-个复杂的网络,利用已知样本求解时不要求目标函数具有可导等高附加信息,在搜索过程中更对网络进行训练,由于人工神经网络中神经元个数众多以及整个能收敛到全局最优解，被人们认为是具有强大潜力的搜索算法,网络存储信息容量的巨大,使得它具有很强的不确定性信息处理目前AIA已经用于函数优化、异常和故障诊断机器学习、机器人能力。即使输入信息不完全、不准确或模糊不清,只要输入的模式行为仿真网络入侵检测等领域,表现出较卓越的性能和效率。接近于训练样本,系统就能给出正确的推理结论。ANN只有当神6群智能算法经元对所有输入信号的综合处理结果超过某一门限值后才输出.随着人类对生物启发式计算的研究, -些社会性动物(如蚁一个信号，因此ANN是一种具有高度非线性的超大规模连续时群、蜂群、鸟群)的自组织行为引起了科学家的广泛关注。这些社间动力学系统,它突破了传统的以线性处理为基础的数字电子计会性动物在漫长的进化过程中形成了-个共同的特点:个体的行算机的局限,标志着人们智能信息处理能力和模拟人脑智能行为为都很简单,但当它们一起协同工作时,却能够“突现"出非常复能力的一大飞跃杂的行为特征。目前，群智能理论研究领域主要有两种算法:蚁群ANN的特点和优越性，主要表现在三个方面:一是具有自学算法(Ant Colony Optimization, ACO)和粒子群优化算法(Particle :习功能。例如实现图像识别时，只要先把许多不同的图像样本和Swarm Optimization, PSO)对应的应识别的结果输入人工神经网络,网络就会通过自学习功6.1蚁群算法能,慢慢学会识别类似的图像。二是具有联想存储功能。三是具有人工蚁群算法[6]是受到人们对自然界中真实的蚁群集体行高速寻找优化解的能力。寻找一个复杂问题的优化解,往往需要为研究成果的启发而提出的一种基于蚁群的模拟进化算法,属于很大的计算量,利用一个针对某问题而设计的反馈型人工神经网随机搜索算法，由意大利学者M. Dorigo等人于 1991年首先提络,发挥计算机的高速运算能力,可能很快找到优化解。出。仿生学家经过大量细致观察研究发现,蚂蚁个体之间是通过常见的几种典型人工神经网络有多层感知网络(误差逆传播一种称之为外激素(pheromone)的物质进行信息传递,从而能相互神经网络)、竞争型(KOHONEN)神经网络.Hopfield 神经网络等。其协作，完成复杂的任务。蚁群之所以表现出复杂有序的行为,个体中Hopfield神经网络应用得较广，基本的Hopfield神经网络是-之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程个由非线性元件构成的全连接型单层反馈系统,Hopfeld神经网中,能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过络的能量函数是朝着梯度减小的方向变化,它的缺点是一旦能量程中能够感知这种物质的存在及其强度,并以此指导自己的运动函数陷入到局部极小值,它将不能自动跳出局部极小点而到达全方向,蚂蚁倾向于朝着该物质强度高的方向移动。因此由大量蚂局最小点，因而无法求得网络最优解。蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路目前,随着各种神经网络理论模型和学习算法的提出,神经径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁网络理论已日趋成熟,其应用已渗透到了生物学、物理学、地质学个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算等诸多领域，并在智能控制模式识别、非线性优化等方面取得了法正是模拟了这样的优化机制,即通过个体之间的信息交流与相令人鼓舞的进展。互协作最终找到最优解。5人工免疫算法以TSP问题为例，设有n个城市,m只蚂蚁,ii.=.,-,n.生物的信息处理系统可分为:脑神经系统.遗传系统和免疫表示城市i和j间的距离,ij()表示在t时刻城市i和j之间的信系统。人们在实践过程中通过对生物三大信息系统的模拟研究得息量,则:在t时刻蚂蚁k在i节点选择j节点的转移概率为:到了基于三大信息处理系统的三种智能算法,即基于模拟脑神经罚onf ()系统的人工神经网络,基于模拟遗传系统的遗传算法以及基于模Je allowedp吟()=2北llowd.唱()g0(1)拟免疫系统的人工免疫算法[4] [5](Artificial Immune Algorithm,otheriseAIA)。AIA的研究始于20世纪90年代后期,AIA模仿生物免疫系统的自适应机制和排除机体的抗原性异物机制,从而使AIA具下一步允许选有学习,记忆和自适应调节能力,AIA将抗原和抗体分别对应于优择的城市,tabuk(中国煤化工前所走过的城市，化问题的目标函数和可行解。把抗体和抗原的亲和力视为可行解集合tabuk随着进THCNMHG.(下转第530页)与目标函数的匹配程度:用抗体之间的亲和力保证可行解的多样508●人工智能及识别技术......本栏目责任编辑:李桂瑾乐理知识算法改进的多方面作大量工作。参考文献:[1] Alpen A.Techniques for algorithmic composition of musicEB0Ttp://alum.hampshire.edu/-adaF92/algocomp/algocomp95.html.1995.图2二+次进化结果[2]冯寅周昌乐.算法作曲的研究进展].软件学报.2006,17(2):5结束语209-215.通过本文的介绍，可以看到遗传算法能够很好地应用于辅助[3] Wiggins G Papadopoulos,S Phon-Amnuaisuk,A Tuson.作曲方面,但是,目前国内外所研究的各种系统都有很多不足的Evolutionary. .Methods for Musical Composition[EB/0O:.ttp://ww.地方,由于作曲是一种融合作家曲理论水平和思想的工作,人为soicity ac.ukl/-geraintpapers/CASYS98a.pdf,1999.因素很重要,而遗传算法的作曲却只能先设定再进行，这就势必[4]张英俐,刘弘,马金刚遗传算法作曲系统研究[].信息技术造成乐曲的思想性和创新性存在不足，生成乐曲的质量判断也是与信息化.2005,5: 106-108.一个比较难以回避的问题,要解决好这些问题,就要在音乐识别、(上接第508页)提出的人工鱼群算法,该算法通过模拟鱼群的觅食和生存活动来经过n个时刻蚂蚁完成一次循环,每只蚂蚁所走过的路径实现在空间中寻求全局最优解。整个算法没有高层指挥者,也不就是一个解。此时,要根据下面公式对各路径上的信息量作更新:需要关于命题的先验知识，每条人工鱼按照自己的规则游动,算ri(+)=:.ij()+Qrij ρ∈ (0,1)法整体表现出快速向极值区域收敛的特性,随机移动行为的存在由上述可知,蚁群算法优化过程的本质在于:(1)选择机制。使得寻优活动更加全面展开，多个人工鱼个体并行进行搜索,具信息量越大的路径,被选择的概率越大。(2) 更新机制。路径上面有较高的寻优速率。的信息量会随蚂蚁的经过而增长,同时也随着时间的推移逐渐减以微粒群优化算法和蚁群优化算法为代表的群智能优化算小。(3) 协调机制。蚂蚁之间实际上是通过信息量来互相通信、协法,经过近十几年的发展,已成为-种新兴的演化计算技术,并受同工作的,这样的机制使得蚁群算法具有很强的发现较好解的能到各学科领域越来越多研究者的关注。与传统的计算方法相比,力。但是,蚁群算法也有一些缺陷。例如,由于蚁群中多个个体的群智能优化算法比较突出的优点是:无集中控制、多代理机制、算运动是随机的,当群体规模较大时,要找出-条较好的路径需要法结构简单、隐含并行性、易理解和易实现,这些优点有效地促进较长的搜索时间等。了其在应用优化技术中的发展。意大利学者M.Dorigo等人充分利用蚁群搜索食物的过程与由于群智能理论依据来源于对生物群落社会性的模拟，因此旅行商问题(ISP)之间的相似性,解决了TSP问题,取得了很好的其相关数学分析还比较薄弱，群智能算法的数学理论基础相对薄结果。随后,蚁群算法被用来求解分配问题、网络路由问题、指派弱,缺乏具备普遍意义的理论性分析。算法中涉及的各种参数设问题,车间作业调度问题，电力系统故障诊断等NP完全问题,显置一直没有确切的理论依据，通常都是按照经验型方法确定,对示出蚁群算法在求解复杂优化问题方面的优越性。具体问题和应用环境的依赖性比较大,还缺乏用于性能评估的标6.2粒子群优化算法算法准测试集。将来的研究工作,应加强群智能算法理论的分析,进-粒子群优化算法[7] (PSO)最早是由Kenney与Eberhart 于步明确与算法原理相关的重要定义,另外，还应扩展群智能与其1995年提出的。PSO是模拟鸟群的捕食行为,让一群鸟在空间里它各种先进技术的融合，以改善其自身或相应技术方法的性能。自由飞翔觅食,每个鸟都能记住它曾经飞过最高的位置,然后就群智能理论的应用方法研究证明,虽然相对于各种比较成熟的计随机的靠近那个位置,不同的鸟之间可以互相交流,它们都尽量算智能方法来说，群智能的研究还处于初级阶段,并存在种种有靠近整个鸟群中曾经飞过的最高点,这样,经过一段时间就可以待深入研究和解决的问题,但是可以预言群智能的研究代表了以找到近似的最高点。PSO 后来经过多次的改进,去除了原来算法后计算机研究发展的一个重要方向。中-些无关的或冗余的变量,又加入了-些随机变化的量,使得7结束语鸟群的运动更象是空间微粒的运动,所以称之为微粒群算法。PSC智能优化算法是人工智能研究领域的一个重要分支,当前,求解问题的基本思想是随机产生一粒子群作为初始解，用粒子的智能计算正在蓬勃发展,研究智能计算的领域十分活跃。虽然智位置表示待优化问题的解,每个粒子性能的优劣程度取决于待优能算法研究水平暂时还很难使“智能机器'真正具备人类的智能，化问题目标函数确定的适应值,微粒尽量靠近最优点并且有随机但人工脑将不仅是模仿生物脑的功能，而且两者具有相同的特的变化发生,使得微粒不会停留在最优点不动,而是尽量靠近,同性,这两者的结合将使人工智能的研究向着更广和更深的方向发时保持创新性。每个微粒记录它自己的最优位置(pbes), 还要记展 ,智能计算将探索智能的新概念、新理论.新方法和新技术,而.录所有微粒的最优位置(gbest),然后通过比较当前位置和两个这些研究将在以后的发展中取得重大的成就。最优位置的差别来调整速度以确定下一步的位置。每个粒子由一个速度矢量决定其飞行方向和速率大小，通过改变速度的大小和[1]康立山，谢云等.非数值并行算法一-模拟退 火算法[M].方向使随机的初始解“飞向”最优解。北京:科学出版社, 1998.PSO算法与GA都属于进化算法,但PSO算法避免了二进制编[2]李敏强,寇纪淞等.遗传算法的基本理论与应用[M].北京:码的麻烦,而且操作更加直观,PSO算法流程简单易实现,算法参数科学出版社,2002.3.[3]张立明.人工神经网络的模型及其应用[M].上海:复旦大简洁,无需复杂的调整。PSO的缺点是:初始化过程是随机的,这虽学出版社, 1993.7.然可保证初始解群分布均匀.但个体的质量不能保证。其次粒子利_[4]王 磊,潘进焦李成.免疫算法[]电子学报,2000 ,28 (7):用自身、个体及全局信息来更新自己的速度和位置,这是一个正反.馈过程,当自身信息及个体信息占优势时算法易陷入局部最优[5] TimmisJ，Neal M，Hunt J . Arificial immune systems for目前,许多学者针对基本PSO提出了多种改进算法,这些改data analysis中国煤化工京科学出版社,[6]段海滨.进的PSO已广泛应用于函数优化、系统识别、神经网络训练信号2005.YHCNMHG.处理和机器人等实际应用领域,取得了丰富的成果。[7]谢晓峰,张文，是以工计开么一心[].控制与决策,除了上述ACO及PSO以外,还有我国李晓磊博士于2002年2003,18(2):129-134.530