1．1 进化算法的一般框架
进化标记自1960年以来，进化算法已经发展出相当多的种类，但一般认为进化算法有5个基本组成部分[3]：
2． 种的初始化方法。
4． 产生新的种的进化算子
5． 算法的参数取值
1.1.1进化优化算法解决对象的描述
进化算法主要是求解优化问题，其数学模型如下：
Maximize y=f(x) (1.1)
Subject to g(x)=(,，…，)0 （1.2）
其中 x=（，，…，）X，x是决策向量，X是决策向量形成的决策空间；y是决策目标。这是个最大化问题，对于最小化问题可以令=C-f(x)转化为最大化问题，因此，它们在本质上是一致的。
根据优化函数f(x)是否连续可以将最优化问题分为二大类：连续函数的最优化与离散函数的最优化。后者也可以称为组合优化问题。根据是否包含约束条件（1.2）可分为约束优化问题和无约束优化问题。此外，若y是一个决策向量，则是一个多目标的优化问题，我们将在第二章进一步讨论。
1.1.2进化优化算法结构
进化算法的一般结构如图1.1所示，进化算法维持由一个体组成的种P(t)
(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]，它模拟鸟觅食场景：鸟不知食物在哪，但知道食物离它有多远，所以最好的策略就是跟随离食物最近的那只鸟。在微粒算法中，决策向量对应觅食的鸟，也叫微粒，每个微粒都有适应度和飞行速度，微粒就在最好微粒的带领下搜索问题空间到最好的解。因此，微粒算法就是在下两个公式下的迭代：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议