现代智能优化算法的研究综述

科技信息0、引言随着优化理论的发展，一些新的智能算法得到了迅速发展和广泛应用，成为解决传统优化问题的新方法，如遗传算法、蚁群算法、粒子群算法等。这些算法大大丰富了现代优化技术，也为具有非线性、多极值等特点的复杂函数及组合优化问题提供了切实可行的解决方案。现代智能优化算法主要包括：模拟退火算法、遗传算法、神经网络优化算法、蚁群算法、粒子群优化算法。这些优化算法都是通过模拟揭示自然现象和过程来实现，其优点和机制的独特，引起了国内外专家学者的高度重视。以下对几种常用的现代智能优化算法作简要的概述，并对智能计算方法的发展进行了展望。1、现代智能优化算法的发展历程及基本概念1.1模拟退火算法(SimulatedAnnealing，SA)模拟退火算法[1]的思想最早是由Metropolis(1953)提出的，1983年Kirkpatrick等人将其应用于组合优化。该算法来源于物理中固体退火过程与一般组合优化问题之间的相似性，是基于MentcCarlo迭代求解策略的一种随机优化算法。SA算法的基本思想是从一给定初始解开始,在邻域中随机产生另一个解，接受准则允许目标函数在有限范围内变差,以一定概率接受较差的解。目前，已经证明SA是一种在局部最优解中能概率性地跳出并最终趋于全局最优，是依概率1收敛于全局最优解的优化方法。1.2遗传算法(GeneticAlgorithm，GA)遗传算法[2]是一类模拟生物界自然选择、自然遗传机制和进化过程而形成的一种具有自适应能力的、全局性的随机化搜索算法,它是由美国Michigan大学的J.Holland教授于1975年首先提出的。遗传算法模拟生物进化的基本过程，通过选择、交叉、变异等遗传算子来仿真生物的基本进化过程，通过种群的不断“更新换代”，从而提高每代种群的平均适应度,通过适应度函数引导种群的进化方向，并在此基础上，使得最优个体所代表的问题解逼近问题的全局最优解。1.3神经网络优化算法(ArtificialNeuralNetwork，ANN)人工神经网络简称神经网络，神经网络[3]是模拟生物神经网络的组织结构和运行机制的一种工程系统。ANN是模拟人脑的思维，利用已知样本对网络进行训练，由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大，使得它具有很强的不确定性信息处理能力。ANN只有当神经元对所有输入信号的综合处理结果超过某一门限值后才输出一个信号，因此ANN是一种具有高度非线性的超大规模连续时间动力学系统，它突破了传统的以线性处理为基础的数字电子计算机的局限，标志着人们智能信息处理能力和模拟人脑智能行为能力的一大飞跃。1.4蚁群算法(AntColonyOptimization，ACO)人工蚁群算法[4]是受到对真实蚁群行为的研究的启发，由意大利学者M.Dorigo等人于1991年首先提出的，它是一种基于蚁群的模拟进化算法，属于随机搜索算法。研究学者在研究过程中发现，蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法正是模拟了这样的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解。1.5粒子群优化算法(ParticleSwarmoptimization，PSO)粒子群优化算法[5]是一种进化算法，最早是由Kenney与Eberhart于1995年提出的。最早的PSO是模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。PSO是模拟鸟群的捕食行为，让一群鸟在空间里自由飞翔觅食，每个鸟都能记住它曾经飞过最高的位置，然后就随机的靠近那个位置，不同的鸟之间可以互相交流，它们都尽量靠近整个鸟群中曾经飞过的最高点，这样，经过一段时间就可以找到近似的最高点。PSO后来经过多次的改进，去除了原来算法中一些无关的或冗余的变量，又加入了一些随机变化的量，使得鸟群的运动更像是空间微粒的运动，所以称之为微粒群算法。2、现代智能优化算法的工作原理和特点2.1模拟退火算法的工作原理和特点模拟退火算法的一般步骤描述如下：a)初始化。任选初始解，i∈S，给定初始温度T0，终止温度Tf，令迭代指标k=0,Tk=T0。b)随机产生一个领域解，j∈N（i）,(N(i)表示i的领域)，计算目标值增量△f=f(j)-f(i)。c)若△f0,令i=j转步骤4；否则产生ξ∈U（0，1），若exp(-△f/Tk)ξ,则令i=j。d)若达到热平衡（内循环次数大于n(Tk)）转步骤e)，否则转步骤b)。e)k=k+1降低Tk，若TkTf停止，否则转步骤b)。模拟退火算法的特点：SA的实验性能具有质量高，初值鲁棒性强，通用易实现的优点，编程最容易，理论最完善。但是，为了寻求最优解，算法通常要求较高的初温、较慢的降温速率、较低的终止温度以及各温度下足够多次的抽样，因此模拟退火算法往往优化过程较长，这也是SA算法最大的缺点。2.2遗传算法的工作原理和特点遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。c)选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。f)终止条件判断：若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。遗传算法除了具有实现简单、效果良好、通用性好、鲁棒性强等优点，还具有以下几方面的特点：1)遗传算法从问题解的串集开始搜索，而不是从单个解开始；2)遗传算法是对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险；3)遗传算法是用适应度函数值来评估个体，适应度函数不受连续可微的约束，而且其定义域可以任意设定，使得遗传算法的应用范围大大扩展；4)遗传算法是采用概率的变迁规则来指导搜索方向；5)具有自组织、自适应和自学习性。2.3神经网络优化算法的工作原理和特点ANN的特点和优越性，主要表现在三个方面：一是具有自学习功能。例如实现图像识别时，只要先把许多不同的图像样本和对应的应识别的结果输入人工神经网络，网络就会通过自学习功能，慢慢学会识别类似的图像。二是具有联想存储功能。三是具有高速寻找优化解的能力。寻找一个复杂问题的优化解，往往需要很大的计算量，利用一个针对某问题而设计的反馈型人工神经网络，发挥计算机的高速运算能力，可能很快找到优化解。2.4蚁群算法的工作原理和特点蚁群算法的主要工作原理可以如下描述：一群人工蚁相互协作在问题的解空间中搜索好的解，这些人工蚁按照人工信息素踪迹和基于问题的启发式信息的指引在问题空间移动以构造问题的解。信息素在蚁群的协作和通信中起到一种间接媒介的作用。人工蚁在解空间中一步一步地移动从而构造问题的解，同时，它们根据解的质量在其路径上留下相应浓度的信息素，蚁群中其他蚂蚁倾向于沿着信息素浓的路径前进，同样这些蚂蚁也将在这段路径上留下自己的现代智能优化算法的研究综述柳州师范高等专科学校数学与计算机科学系吴春梅［摘要］本文着重回顾了现代智能优化算法的发展历程，主要介绍了现代智能优化算法的基本概念，主要包括模拟退火算法、遗传算法、神经网络优化算法、蚁群算法、粒子群优化算法等，并阐述了其工作原理和特点，归纳了它们主要的应用方向，同时对智能计算方法的发展进行了展望。［关键词］现代智能优化算法遗传算法神经网络优化算法基金项目：本文系柳州师范高等专科学校基金项目（NO.LSZ2010C005）。作者简介：吴春梅（1970-），女，广西桂平人，副教授，主要研究方向：计算机应用及智能优化算法。（下转第33页）——31科技信息信息素，这就形成了一种自催化强化学习机制，也就是正反馈。这种正反馈机制将指引蚁群找到高质量的最优解。蚁群算法的特点是不仅能够智能搜索、全局优化，而且具有稳健性（鲁棒性）、正反馈、分布式计算、易与其它算法结合等特点。2.5粒子群优化算法的工作原理和特点PSO求解问题的基本操作流程如下:a)在整个设计域中以均匀随机分布形式初始化位置向量x和速度向量v。b)计算各个粒子的适应度，以及粒子的个体极值点pbest和全局极值点gbest。c)更新粒子的位置和速度：xij(t+1)=xij(t)+vij(t+1)(1)vij(t+1)=vij(t)+dir(c1r1(pbest(t)-xij(t)))+c2r2(pgbest(t)-xij(t))(2)d)检查是否满足迭代结束条件，若满足，则停止迭代，输出最优解；否则，重复b)~c)步。PSO算法与GA都属于进化算法，但PSO算法避免了二进制编码的麻烦，而且操作更加直观，PSO算法流程简单易实现，算法参数简洁，无需复杂的调整。PSO的缺点是：初始化过程是随机的，这虽然可保证初始解群分布均匀，但个体的质量不能保证。其次，粒子利用自身、个体及全局信息来更新自己的速度和位置，这是一个正反馈过程，当自身信息及个体信息占优势时，算法易陷入局部最优。3、现代智能最优化算法主要的应用方向模拟退火算法是一种通用的优化算法，目前已在工程中得到广泛的应用，在求解最大截问题(MaxCutProblem)、0-1背包问题(ZeroOneKnapsackProblem)、图着色问题(GraphColouringProblem)、调度问题(SchedulingProblem)等方面效率较高。遗传算法成功的应用主要有：函数优化、机器学习、组合优化、人工神经元网络训练、自动程序设计、专家系统、作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配等。ANN算法主要应用于自动控制、生物医学、质量检测、气象预报、信息处理、军事用途、公安用途、商业与金融业、通讯网、新一代计算机、工业用途及工程应用，其中已有很多商品化的应用。蚁群算法主要用于求解不同的组合优化问题，一类应用于静态组合优化问题，另一类用于动态组合优化问题。蚁群算法在静态组合中的优化应用包括：旅行商问题(TSP)、二次分配问题(QAP)、车间任务调度问题(JSP)、车辆路线问题(VRP)、图着色问题(GCP)、有序排列问题(SOP)；在动态组合中的优化应用包括：大规模集成电路中的综合布线以及电信网络中的路由等方面。目前，许多学者针对基本PSO提出了多种改进算法,这些改进的PSO已广泛应用于函数优化、系统识别、神经网络训练、信号处理和机器人等实际应用领域，并取得了丰富的成果。4、结束语智能优化算法是人工智能研究领域的一个重要分支，当前，智能计算正在蓬勃发展，研究智能计算的领域十分活跃。虽然智能算法研究水平暂时还很难使“智能机器”真正具备人类的智能，但智能计算将在21世纪蓬勃发展，人工脑将不仅是模仿生物脑的功能，而且两者具有相同的特性，这两者的结合将使人工智能的研究向着更广和更深的方向发展，将开辟一个全新的领域，开辟很多新的研究方向。智能计算将探索智能的新概念、新理论、新方法和新技术，而这些研究将在以后的发展中取得重大的成就。参考文献［1］康立山,谢云等.非数值并行算法——模拟退火算法［M］.北京:科学出版社,1998.［2］李敏强,寇纪淞等.遗传算法的基本理论与应用［M］.北京:科学出版社,2002.3.［3］张立明.人工神经网络的模型及其应用［M］.上海:复旦大学出版社,1993.7.［4］段海滨.蚁群算法原理及其应用［M］.北京:科学出版社,2005.［5］谢晓