进化优化算法概述

第一章 进化优化算法概述

1．1 进化算法的一般框架

自1960年以来，进化算法已经发展出相当多的种类，但一般认为进化算法有5个基本组成部分[3]：

1．问题解的遗传表示。 2．种群的初始化方法。

3．根据个体适应度对其进行优劣判定的评价函数。 4．产生新的种群的进化算子 5．算法的参数取值

1.1.1进化优化算法解决对象的描述

进化算法主要是求解优化问题，其数学模型如下：

Maximize

(1.1)

Subject to g(x)=(g1(x),g2(x)，?，gm(x))?0 （1.2） 其中 x=（x1，x2，?，xn）?X，x是决策向量，X是决策向量形成的决策空间；

y=f(x)

y是决策目标。这是个最大化问题，对于最小化问题可以令y?=C-f(x)转化为最大化问题，因此，它们在本质上是一致的。

根据优化函数f(x)是否连续可以将最优化问题分为二大类：连续函数的最优化与离散函数的最优化。后者也可以称为组合优化问题。根据是否包含约束条件（1.2）可分为约束优化问题和无约束优化问题。此外，若y是一个决策向量，则是一个多目标的优化问题，我们将在第二章进一步讨论。

1.1.2进化优化算法结构

进化算法的一般结构如图1.1所示，进化算法维持由一群个体组成的种群

P(t)

(t为进化代数)。每个个体代表问题的一个潜在解。每个个体通过目标函数评价得到适应度并根据优胜劣汰的原则进行选择。被选择的个体经历遗传操作产生新的个体,主要有两种遗传操作：杂交是将多个个体的有关部分组合起来形成新的个体，变异是将一个个体改变而获得新的个体。新产生的个体（子代）继续被评

价优劣。从父代种群和子代种群中选择比较优秀的个体形成新的种群。在若干代后，算法收敛到一个最优个体，该个体很有可能代表问题的最优或次优解。 初始化种群P(t) 评价P(t) 是否满足停机条件 输出最优解 从P(t)和CR(t)中选择得新种群P(t+1) 评价CR(t) P(t)繁殖得R(t) 图1.1 进化算法流程图 1.1.3进化算法几个环节的解释

遗传编码：如何将问题的解编码成染色体是进化算法使用中的关键问题，目前的编码方式主要有二进制编码[4]、Gray编码、实数编码、字符编码等，对于更复杂的问题，用合适自然的数据结构来表示染色体的等位基因，可以有效抓住问题的本质，但总的来说，完整的遗传编码理论尚未建立，部分文献[5~7]的讨论都有都有一定的局限性。

繁殖算子：模拟生物物种的繁衍过程和遗传变异机制，主要有两种算子：交叉算子和变异算子，这主要考虑平衡算法的勘探(exploration)能力（勘探出新的解空间）和开发(exploitation)能力（积累所搜索的信息）[8~10]，在最早的进化策略和进化规划两类进化算法中，并没有交叉算子。已形成许多对包括各种交叉算子之间[11~18]（单点、两点、多点、均匀、算术等）、各种变异算子之间[18~19]（均匀、正态、非一致等）及交叉和变异算子之间[18~29]的选取原则，但这些原则主要还是基于经验或部分经验的，严格理论刻画还是较少。

选择算子：对生物的优胜劣汰的模拟，已有文献[2]对选择算子进行科学的归类并指出了各自的优缺点。

1．2 进化优化的研究动态

进化算法发展至今，已成为一门庞大的学科，一方面，进化算法在原来三个

并行的框架下，对各自的进化参数（包括交叉、变异、选择、种群规模、自适应、收敛性、复杂度、进化机制等）进行深入研究；另一方面，进化算法框架下的三类算法积极吸收对方的方法，相互渗透，有一种融合的趋势；进化计算还吸收其它高性能计算的新成果、新思想（如与文化进化、神经网络、群智能、模糊计算、免疫计算、分子计算、量子计算等相结合），从而拓展了进化算法的内容，有些新算法甚至跳出原来三类算法的标准内容而成为与其并行的算法群。但纵观这些进化算法的发展，可以发现它们在利用进化论思想和立足于主要解决优化问题这两个方面没有变，我们称之为进化优化算法，进化优化以遗传算法、进化策略、进化规划和优化理论为基础但不局限于此，积极吸收计算智能和仿生学的思想和理论成果，发展一系列高性能的优化算法。由于进化优化的迅猛发展，要对其进行综述是一件困难的事，一些好的综述都是大致在20世纪九十年代左右发表的

[8] [12] [21] [31~35]

。在最近的几年，据作者所知，很少出现进化优化的综述，有些资

深的研究者最近发表的综述性文章[36~38]，也仅仅是对自己感兴趣的几个热点进行评述。而国内期刊上发表的几篇的综述[39~41]则仅仅是对遗传算法或进化算法的简单介绍，基本上是国外20世纪90年代初的研究成果。

基于此，本节对最近特别是21世纪这几年进化优化的发展做一个述评，有时为了保持完整性会追溯到上世纪80，90年代的论文。做这个评述的目的有二：充分了解进化优化的发展情况；对进化优化的新思想和发展趋势做一个总结，形成改进进化优化算法的若干见解，以此来指导进化优化算法的创新。

1.2.1进化优化的新算法

基于进化算法在优化方面的强大优势和20世纪八九十年代良好的发展基础所形成的广阔交流学习研究平台（每年数十个关于进化计算的学术会议和包括《进化计算》和《IEEE进化计算学报》等有影响力的期刊，全球数十个有名的进化计算研究小组的网络共联并有公开的网络讨论社区和提供最新软件和研究成果），更重要的是进化现象和其它计算思想给我们提供无限的启发创新空间，近年来，新的进化优化算法层出不穷并受到不同程度的关注迅速成长起来。在这里我们主要介绍有影响力的新算法，关于遗传算法、进化策略、进化规划和遗传编程的介绍,在一般的专著[2~3] [19] [26] [31] [42~43]和综述文章[8] [12] [21] [31~41]中都能找到。

生物一个独特的性质就是它的智能性，而作为一种智能算法，向生物学习和

模拟就成为很自然的方法，主要的仿生算法有：

人工免疫算法（artificial immune algorithms）：生物免疫系统是识别体内所有细胞，区分某一细胞是自身还是外界的，并对非自身细胞进一步分类以加强抵御

图1.2 生物免疫系统示意图

的机制。图1.2 是Satoshi Endoh 给出的示意图，当抗原入侵时，部分T细胞识别出是外来物，于是通知相应B细胞，B细胞开始分化、增殖，用B细胞表面的抗体与抗原结合，使抗原无害化，完成一次抵抗抗原入侵过程，最后免疫系统保留（记忆）一部分B细胞作为下一次抵抗同样抗原入侵的基础。而人工免疫系统就是对生物免疫系统的模拟，有免疫记忆、自我识别、免疫多样性和并行分布式等特点。目前的人工免疫优化算法主要有三类：免疫遗传算法（immune genetic algorithm）[44~46],可看成是遗传算法的改进。免疫网络算法（immune network algorithm）[48~49]将免疫系统看成网络结构，通过节点间的信息传递达到识别、响应、记忆等功能。反向选择算法（negative selection algorithm），该算法最初模拟生物免疫系统的T细胞用于计算机安全检测[50~52]，Gonzalez将其修改

[53]

，用于函数优化取得很好的效果。

微粒群算法（particle swarm optimization algorithms）：微粒群算法是

由J.Kennedy和R. C. Eberhart提出的新仿生算法[54~55]，它模拟鸟群觅食场景：鸟不知食物在哪，但知道食物离它有多远，所以最好的策略就是跟随离食物最近

的那只鸟。在微粒群算法中，决策向量对应觅食的鸟，也叫微粒，每个微粒都有适应度和飞行速度，微粒群就在最好微粒的带领下搜索问题空间找到最好的解。因此，微粒群算法就是在下两个公式下的迭代：

Vid(t?1)?w?Vid(t)?c1?rand1()?[pid?xid(t)]?c2?rand2()?[pnd?xid(t)]

（1.3）

xid(t?1)?xid(t)?Vid(t?1)（1.4）

其中pid表示该微粒迄今为止找到的最好的解，pnd表示包括该微粒及其邻居

迄今为止找到的最好的解，所以（1.3）式的第二项代表该个体的自学成分，第三项则表示个体向社会学习的成分。微粒群算法中，有五个重要的参数：pid，

pnd，w，c1，c2.对这些参数的选取，许多学者做过这方面的研究[56~59]，但并没有定论，而且选取的原则与问题的类型（约束问题、多目标问题、动态优化问题等）会有所不同。标准的微粒群算法主要用于连续函数优化，对于离散函数的优化，算法要作适当的修改[60~61]，主要要考虑微粒的速度的定义及离散变量的相邻原则。微粒群算法已成功应用于约束优化、多目标优化、动态优化等许多领域，目前主要有以下问题急需解决：理论分析微粒群算法的收敛性，更好离散化方案，微粒与智能体结合等。

蚂蚁算法（ant optimization algorithms）：蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”（其多少与食物的数量和质量有关）作为蚁群前往食物所在地的标记，信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。受到蚂蚁觅食时的通信机制的启发，1991年，Dorigo在解决TSP问题时提出了蚂蚁算法[62]，主要是下两个过程的迭代：根据信息素模型产生新解（根据概率分布有偏好的抽样解空间），根据解的质量修改信息素（影响下一次抽样）。根据解的产生和信息素的更新的方式不同，蚂蚁算法已衍生出许多新的算法：蚁群算法[63]、最大最小蚁群系统[64]、排序蚁群系统[65]、最好最坏蚁群系统[66]等。目前对蚁群算法的研究主要集中在[67~68]：在算法中更好的加入

本文来源：https://www.bwwdw.com/article/mntf.html