浅谈几种智能优化算法

ISSN1009-3044

Computer与技术电脑知识与技术ComputerKnowledgeKnowledgeandandTechnologyTechnology电脑知识

Vol.7,No.19,July2011.第7卷第19期(2011年7月)http://www.dnzs.net.cnE-mail:[email protected]:+86-551-[1**********]964浅谈几种智能优化算法

海丽切木·阿布来提

（新疆教育学院数学与信息技术分院，新疆乌鲁木齐市830043）

摘要：该文首先介绍介绍了几种典型的群体智能算法，具体包括遗传算法、蚁群算法和粒子群算法，并对它们进行了详细的分析。关键词：智能算法；蚁群算法；遗传算法；粒子群算法

中图分类号：TP301文献标识码：A文章编号：1009-3044(2011)19-4628-03

EmpiricalStudyonSeveralTypicalIntelligenceAlgorithms·HalqamAblat

(SubInstituteofMathematicsandInformationTechnology,XinjiangEducationInstitute,Urumqi830043,China)

Abstract:Inthisessay,theauthorintroduceseveraltypicalswarmintelligencealgorithmsincludesgeneticalgorithm,antcolonyoptimiza-tionalgorithmandparticleswarmoptimizationalgorithm.

Keywords:intelligencealgorithm;geneticalgorithm;antcolonyalgorithm;particleswarmalgorithm

1概述

为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化在运筹学和管理科学中起着核心作用。最优化通常是极大或极小某个多变量的函数并满足一些等式或不等式约束。最优化技术对社会的影响日益增加，应用的种类和数量快速增加，丝毫没有减缓的趋势。近几年来，随着计算机的发展，一些过去无法解决的复杂优化问题已经能够通过计算机来求得近似解，所以，计算机求解优化问题的方法研究也就显得越来越重要了。

对于简单的函数优化问题，经典算法比较有效，且能获得函数的精确最优解。但是对于具有非线性、多极值等特点的复杂函数及组合优化问题而言，经典算法往往无能为力。基于系统动态演化的算法及基于此类算法而构成的混合型算法又可称为智能优化算法。

近年来，随着优化理论的发展，一些新的智能算法得到了迅速发展和广泛应用，成为解决传统优化问题的新方法，如遗传算法、蚁群算法、粒子群算法等。

2蚁群算法

蚁群算法是受到对真实蚁群行为的研究的启发而提出的。生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢穴之间的最短路径，而单只蚂蚁却不能。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种间接的通信机制达到协同搜索食物最短路径的目的。蚂蚁觅食协作方式的本质是：1）路径概率选择机制：信息素踪迹越浓的路径，被选中的概率越大；2）信息素更新机制：路径越短，在上面的信息素踪迹浓度增长越快；3）协同工作机制：蚂蚁之间通过信息素进行通信。

在蚁群优化算法中，作为分布智能体(Distributedgent)的人工蚁(ArtificialAnts)的行为可以如下描述：一群人工蚁相互协作在问题的解空间中搜索好的解，这些人工蚁按照人工信息素踪迹和基于问题的启发式信息的指引在问题空间移动以构造问题的解。在此，信息素(Pheromone)类似于一种分布式的长期记忆，这种记忆不是局部地存在于单个的人工蚁，而是全局地分布在整个问题空间。当人工蚁在问题空间中移动时，它们在其经过的路径上留下信息素踪迹，这些踪迹反映了人工蚁在问题空间觅食（即构造好的解）过程中的经历。换句话说，信息素在蚁群的协作和通信中起到一种间接媒介的作用。人工蚁在解空间中一步一步地移动从而构造问题的解，同时，它们根据解的质量在其路径上留下相应浓度的信息素，蚁群中其他蚂蚁倾向于沿着信息素浓的路径前进，同样这些蚂蚁也将在这段路径上留下自己的信息素，这就形成了一种自催化强化学习机制，也就是正反馈。这种正反馈机制将指引蚁群找到高质量的问题解。

3遗传算法

遗传算法(GeneticAgorithm)是模拟生物在自然环境中优胜劣汰、适者生存的遗传和进化过程而形成的一种具有自适应能力的、全局性的概率搜索算法。遗传算法是从代表待优化问题潜在解集的一个种群开始，而种群则由经过基因编码的一定数目的个体组成。基因编码成染色体，每个个体由染色体构成，每个个体实际上是带有染色体特征的实体。染色体作为遗传物质的主要载体，是多个基因的集合，其内部表现（即基因型）是多个基因的某种组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现收稿日期：2011-05-20

作者简介：海丽切木·阿布来提（1972-），女（维吾尔族），乌鲁木齐人，新疆教育学院数学与信息技术分院讲师，硕士，2005年在江南

大学研修，主要从事计算机应用技术研究。

4628人工智能及识别技术本栏目责任编辑：唐一东

第7卷第19期(2011年7月)ComputerKnowledgeandTechnology电脑知识与技术型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出活应冷越来越好的个体。在每一代中，根据问题域中个体的适应度的优劣，选择一些适应度高的个体，基于这些选出的适应度高的个体，并借助于自然遗传学的交叉、变异算子，产生出代表新解集的下一代种群。这个过程将导致种群像自然进化一样，使后生代种群比前代种群具有更高的适应度，更加适应于环境。在优化过程结束后，末代种群中的最优个体经过解码，即可以作为问题的近似最优解。

遗传算法是将问题的每一个可能性解看作是群体中的一个个体（染色体），并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应值。算法将根据适应度值进行它的寻优过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的。

4PSO算法及其改进

4.1PSO简介

粒子群优化算法（PSO）是一种进化算法，经典粒子群算法的基本思想是模拟鸟类群体行为，并利用了生物学家的生物群体模型，因为鸟类的生活使用了简单的规则：1）飞离最近的个体；2）飞向目标；3）飞向群体的中心；来确定自己的飞行方向和飞行速度，并且成功的寻找到栖息地。

PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。如果我们把一个优化问题看作是在空中觅食的鸟群，那么在空中飞行的一只觅食的“鸟”就是PSO算法中在解空间中进行搜索的一个“粒子”（Particle），也是优化问题的一个解。“食物”就是优化问题的最优解。粒子的概念是一个折衷的选择，它只有速度和加速度用于本身状态的调整，没有质量和体积。

PSO算法中每个粒子即解空间中的一个解，它根据自己的飞行经验和同伴的飞行经验来调整自己的飞行。每个粒子在飞行过程所经历过的最好位置，就是粒子本身找到的最优解。整个群体所经历过的的最好位置，就是整个群体目前找到的最优解。前者叫做个体极值(pbest)，后者叫做全局极值(gbest)。每个粒子都通过上述两个极值小断更新自己，从而产生新一代群体。实际操作中通过由优化问题所决定的适应度函数值(fitness

解空间中搜索。

在PSO算法中每个粒子可以看作是解空间中的一个点。如果粒子的群体规模为N，则第i（i=1,2,…,N）个粒子的位置可表示为value)来评价粒子的“好坏”程度。显然，每个粒子的行为就是追随着当前的最优粒子在Xi,并在搜索空间中以一定的速度飞行，第i个粒子的飞行速度可表示为Vi。该飞行速度是根据个体的飞行经验和群体的飞行经验来进行动态地调整。

假设矢量：

Xi=(xi1,xi2,…,xim)表示微粒i的当前位置；

Vi=(vi1,vi2,…,vim)表示微粒i的当前飞行速度；

Pi=(pi1,pi2,…,pim)表示微粒i所经历过的具有最好适应度值的位置，称为个体i所经历的最佳位置（又称局部最优点）。设f(X)为需要最大化的目标函数，则微粒i目前的个体最好位置由下式确定

：

（1）

群体中的微粒数为N，群体中所有微粒所经历过的最佳位置Pg(t),称为全局最佳位置。则

：

（2）

Kennedy和Eberhart最早提出的PSO算法的进化方程如下

：

（3

）

（4）

其中：下标“i”表示第i个微粒，下标“j”表示的是微粒i的第j维分量，t表示第t代，学习因子c1,c2为非负常数，c1用来调节微粒向本身最好位置飞行的步长，c2用来调节微粒向群体最好位置飞行的步长，通常c1,c2在[0,2]间取值。r1j(t),r2j(t)是两个介于[0,1]之间的服从均匀分布的随机数，即：r1j(t)~U(0,1)，r2j(t)~U(0,1)。为了减少在优化过程中，微粒飞出搜索空间的可能性，vij(t)通常限定在一定的范围内，即vij∈[vmin,vmax]。vmin、vmax是根据具体问题而人为设定的，同时人们也会根据具体问题，限定搜索空间xij∈[xmin,xmax]。迭代终止条件根据具体问题一般选为最大迭代次数或粒子群搜索到的最优位置满足于预先设定的精度。为了方便起见，我们将经典微粒群算法的形式表述如下

：

（5

）

（6）

4.2改进的PSO算法

正如先前所述，公式(5)由三部分组成：第一部分是粒子先前的速度项，即Vi(t)，第二部分和第三部分是导致粒子速度变化的两项，即c1×r1×(Pi(t)-Xi(t))和c2×r2×(Pg(t)-Xi(t))。

一方面，如果没有后两项，粒子将保持在相同的方向上以当前的速度“飞翔”至下一个点，直至达到边界值。这样的PSO将不能找到一个可接受的解，除非这样的飞行轨迹是一种合理的方案，而这在现实中是非常少见的。

另一方面，如果没有第一项，那么“飞翔”粒子的速度仅仅取决于粒子的当前位置和它们最好的历史位置。速度自身是没有记忆性的。假设在开始的时候，粒子i正好是整体最好所在的点，那么粒子i将以速度为0“飞翔”，这将保持粒子此次的位置不变，直到出人工智能及识别技术本栏目责任编辑：唐一东4629

ComputerKnowledgeandTechnology电脑知识与技术第7卷第19期(2011年7月)现新的一个最好点替代粒子i。同时，每一个粒子将向自身最好点和整体最好点的质心方向“飞翔”。因此可以想像在没有第一项情况下的PSO搜索过程，其搜索空间将在迭代中逐渐衰退，这类似于局部搜索算法。只有当全局最好点包含在初始搜索空间内的时候，才有可能找到满意解。这样，最终解在很大程度上要依赖于初始化种群。这也说明了在没有第一项内容的情况下，PSO算法更多的显现的是局部搜索能力。从另一层意思来说，第一项内容使得粒子有一种扩展搜索空间的能力，即开拓能力（exploreability），是一种全局搜索能力的表现。

在各类问题的解决中，局部搜索和全局搜索都起着重要作用。对于某一类优化问题的具体解决中，我们应该权衡局部搜索和全局搜索的贡献。Y.Shi和Eberhart在1998年对微粒群算法引入了惯性权重w(t)，并提出了在进化过程中线性调整惯性权重的方法，以起到权衡全局搜索和局部搜索能力。惯性权重因子W可以是个整数，也可以是以时间为变量的线性或非线性正整数。该方程已被学者们称为标准PSO算法，这样公式就变为

：

（7

）

（8）

当惯性权重w(t)=1时，式（3）与式（7）相同，从而表明代惯性权重的微粒群算法是基本微粒群算法的扩展，建议w(t)的取值范围为[0,1.4]，但实验结果表明当w(t)取[0.8,1.2]时，算法收敛速度更快，而当w(t)＞1.2时，算法则较多的陷入局部极值。惯性权重w(t)表明微粒的原先的速度能在多大的程度上得到保留，较大的w(t)值有较好的全局搜索能力，而较小的w(t)则由较强的局部搜索能力。因此，随着迭代次数的增加，线性的减小惯性权重w(t)，就可以使得微粒群算法在初期具有较强的全局收敛能力，而在晚期具有较强的局部收敛能力。当惯性权重w(t)满足

：

（9）

即w(t)随着迭代线性地从m递减到n（通常m=1.2,n=0.4）时，从几个测试函数的测试结果来看，效果很好。等式(9)中的max_circletimes为最大截止代数，对于惯性权重w(t)来说，由于不同的问题，其每一代所需的比例关系并不相同，这样，线性的递减关系并不是对所有的问题都会最佳。又有学者提出了基于模糊系统的惯性权重的动态调整。

5结束语

本论文介绍了几种典型的智能算法：蚁群算法、遗传算法和粒子群算法，并进行了较深入的阐述。

参考文献：

[1]

[2]

[3]

[4]

[5]

[6]徐成贤,陈志平,李乃成.近代优化方法[M].北京:科学出版社,2002:24-27.丁建立,陈增强,袁著祉.基于自适应蚂蚁算法的动态最优路由选择[J].控制与决策,2003,18(6):751-753.张纪会,高齐圣,徐心和.自适应蚁群算法[J].控制理论与应用,2000,17(1):1-3.魏平,熊伟清.一种求解函数优化的蚁群算法[J].计算机科学,2002,29(9):227-229.潘峰,陈杰,甘明刚,等.粒子群优化算法模型分析[J].自动化学报,2006(3):368-377.KennedyJ,EberhartRC.Particleswarmoptimization[C].ProceedingsofIEEEInternationalConferenceonNeuralNetworks,1995:1942-1948.

[7]DorigoM,Gambardella.Antcolonysystem:acooperativelearningapproachtothetravelingsalesmanproblem[J].IEEETransactionsonEvolutionaryCompu6hg,1997,1(1):53-56.（上接第4627页）

通过对显示函数的反复调用来实现在一帧时间内完成旋转变换和显示，直到消息循环接收到WM_QUIT消息为止。

3实验结果及结论

使用基于DierectX编程的旋转算法很好的节约了CPU资源，旋转平滑自然，没有出现图像失真的问题，达到了较高的旋转质量。

参考文献：

[1]

[2]

[3]

[4]

[5]

[6]吴恩华,柳有权.基于图形处理器(GPU)的通用计算口[J].计算机辅助设计与图形学学报,2004,16(5):601-612.王丽萍.立体视觉检测及弱视治疗系统研究[D].杭州：浙江大学,2005.DanielssonPE.HammerinMHigh-AccuracyRotationofImages[J].CVGIP,1992,54(4):340-344.LunaFD.Introductionto3DGameProgrammingwithDirectX9.0[M].TexasPiano：WordwarePublishingInc,2003.尚晶晶.Direct3D游戏开发技术详解[M].北京：人民邮电出版社,2006.Microsoft.MicrosoftDirectXSDKDocuments[EB/OL].[2000-04-15].http://www.microsoft.COITL.

4630人工智能及识别技术本栏目责任编辑：唐一东