ComputationalIntelligence(2)幻灯片.ppt

Chapter 5: 计算智能（2）：进化计算、人工生命 Outline5.1 遗传算法5.2 进化策略5.3 进化编程5.4 人工生命5.5 小结2021/8/21Chapter 5: 计算智能（2）：进化计算、人工生命 进化计算（Evolutionary Computation）是通过模拟自然界中生物进化机制进行搜索的一种算法生物进化论 进化计算主要包括：遗传算法（Genetic Algorithm, GA）进化策略（Evolution Strategy）进化编程（Evolutionary Programming）或进化规划（ Evolutionary Planning ）2021/8/22Chapter 5: 计算智能（2）：进化计算、人工生命 进化计算的研究起源于20世纪50年代 1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中 1960年代，Rechenberg和Schwefel提出了进化策略; 同一时期，Fogel, Owens和Walsh提出了进化规划 1975年，Holland出版了他的著名专著自然系统和人工系统的适应性该书系统地阐述了遗传算法的基本理论和方法。

1990年，Koza提出了遗传规划（Genetic Programming）的概念，用于搜索解决特定问题的最适计算机程序2021/8/235.1 遗传算法 1960年代中期，美国Michigan大学的J. H. Holland教授提出借鉴生物自然遗传的基本原理用于自然 和人工系统的自适应行为研究和串编码技术； 1967年，他的学生J. D. Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词； 1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法的诞生 遗传算法（GA）思想来源于生物进化过程, 它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法 GA是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式，它为那些难以找到传统数学模型的难题提供了解决方法 特点：通用性鲁棒性（robustness）并行性次优解、满意解2021/8/245.1 遗传算法 GA先将搜索结构编码为字符串形式, 每个字符串结构被称为个体 然后对一组字符串结构(被称为一个群体)进行循环操作。

每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程 类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题2021/8/255.1 遗传算法 与自然界相似，GA对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会 在GA中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作 常用的遗传算子有复制、杂交、变异和反转2021/8/265.1 遗传算法GA与传统优化方法的不同GA不是直接作用在参变量集上, 而是利用参变量集的某种编码;GA不是从单个点, 而是在群体中从一个点开始搜索;GA利用适应值信息, 无需导数或其它辅助信息;GA利用概率转移规则, 而非确定性规则使用GA的几个关键确定表示方案;确定适应值的度量;确定控制该算法的参数和变量;确定程序运行结束的标准2021/8/275.1 遗传算法 GA的基本原理 以Holland的基本遗传算法(Simple Genetic Algorithm，SGA) 亦即简单遗传算法为例进行解释。

SGA只使用选择算子、交叉算和变异算子这三种基本的遗传算子其遗传操作简单、容易理解，是其它GA的雏形和基础2021/8/285.1 遗传算法SGA的基本要素染色体编码方法：首先必须对问题的解空间进行编码，使之能用遗传算法进行操作较常用的是二进制编码方法，现在使用非二进制编码的也逐渐增多适应度函数（fitness function，又称为适应值适值函数）用来评价一个染色体的好坏 遗传算子-选择算子(selection) ：又称为复制算子按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择交叉算子(crossover)：又称为杂交算子将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体如使用单点一致交叉变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值2021/8/295.1 遗传算法 SGA的参数设置 N：群体大小，即群体中包含的个体的数量 T：遗传算法终止的进化代数 Pc：交叉概率，一般取为 0.40.99 Pm：变异概率，一般取为 0.00010.1 2021/8/2105.1 遗传算法SGA的求解步骤 (1)初始化群体; (2)计算群体上每个个体的适应度值; (3)按由个体适应度值所决定的某个规则选择将进入下一代的个体; (4)按概率Pc进行交叉操作; (5)按概率Pm进行突变操作; (6)若没有满足某种停止条件，则转第(2)步，否则进入下一步。

(7)输出群体中适应度值最优的染色体作为问题的满意解或最优解2021/8/2115.1 遗传算法 SGA的框图初始化种群变异操作计算适应度值选择操作交叉操作适应值最优个体终止条件开始结束否是2021/8/2125.1 遗传算法一般遗传算法的步骤 (1)随机产生一个由确定长度的特征字符串组成的初始群体 (2)对该字符串群体迭代的执行下面的步和，直到满足停止标准：- 计算群体中每个个体字符串的适应值；- 应用复制、交叉和变异等遗传算子产生下一代群体 (3)把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解2021/8/213产生初始群体是否满足停止准则计算每个个体的适应值i=N?GEN:=GEN+1依概率选择遗传操作执行复制选择一个个体i:=i+1选择两个个体选择一个个体执行变异i:=0GEN:=0复制到新群体i:=i+1将两个后代插入新群体插入到新群体执行杂交指定结果结束是否是否变异复制交叉基本遗传算法框图2021/8/214遗传算法举例问题：求（1）编码： 此时取均长为5，每个染色体（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体： 编码： 01101，11000，01000，10011 解码： 13 24 8 19 适应度： 169 576 64 361（3）适应度评价：2021/8/215（4）选择：选择概率 个体： 01101，11000，01000，10011 适应度： 169 576 64 361 选择概率：0.14 0.49 0.06 0.31 选择结果：01101，11000，11000，10011（5）交叉操作：发生交叉的概率较大 哪两个个体配对交叉是随机的 交叉点位置的选取是随机的（单点交叉） 0110 1 01100 11 000 11 011 1100 0 11001 10 011 10 000遗传算法举例2021/8/216轮盘式选择 首先计算每个个体 i 被选中的概率 然后根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为 。

选择时转动轮盘，参考点r落到扇形i则选择个体i p1p2pir2021/8/217（6）变异：发生变异的概率很小（7）新群体的产生： 保留上一代最优个体，一般为10%左右，至少1个 用新个体取代旧个体，随机取代或择优取代 11000，11011，11001，10011（8）重复上述操作，直至满足某个条件而终止程序运行 说明：GA的终止条件一般人为设置； 此外，GA通常只能求次优解或满意解遗传算法举例2021/8/2185.2 进化策略20世纪60年代，德国柏林工业大学的I.Rechenberg和H.P.Schwefel等在进行风洞实验时，由于设计中描述物体形状的参数难以用传统方法进行优化，因而利用生物变异的思想来随机改变参数值，获得了较好的结果随后，他们对这种方法进行了深入的研究和发展，形成了一种新的进化计算方法进化策略(Evolution Strategy, 简称ES) 2021/8/2195.2 进化策略早期的进化策略可以被看成使用浮点数表达，只使用变异作为其重组算子的一种进化计算方法它主要用于各种带连续可变参数的优化问题其基本思想为：随机产生一个适用于所给问题环境的初始种群，即搜索空间，种群中的每个个体为实数编码，计算每个个体的适应值；依据达尔文的进化原则，选择遗传算子(重组、突变等)对种群不断进行迭代优化，直到在某一代上找到最优解或近似最优解。

2021/8/2205.2 进化策略最早的进化策略只是基于单个个体组成的种群而进化的，且在进化过程中只使用变异算子独特之处在于，个体被表达成一对浮点数组成的向量，其中x表示搜索空间的一个点，而表示标准偏差向量变异是通过如下的方式实现的：变异之后的个体（后代）当且仅当有较好的适应值且满足所有的约束（如果有的话）时，才会被接收为种群的新成员 2021/8/2215.2 进化策略虽然种群是由经历变异的单个个体组成，但是后代和父代进行竞争，而且在竞争阶段种群中临时地包含两个个体，因此，上述的进化策略被称为“两成员进化策略”，即“1+1-ES”1973年，Rechenberg进行了多父代方法的早期工作，但还是采用单子代1981年，Schwefel在Rechenberg工作的基础上迈进一步，研究了多父代和多子代的进化策略2021/8/2225.2 进化策略(+)ES和(,)ES这两种进化策略都采用含有个个体的父代群体，并通过重组和突变产生个新个体它们的差别仅仅在于下一代群体的组成上)ES是在原有个个体及新产生的个新个体中共（+）个个体，再择优选择个个体作为下一代群体)ES则是只在新产生的个新个体中择优选择个个体作为下一代群体，这时要求。

总之，在选择子代新个体时若需要根据父代个体的优劣进行取舍，则使用“+”记号，如(1+1)、(+1)及(+)；否则，改用逗号分隔，如(,)近年来，(,)ES得到广泛的应用，这是由于这种进化策略使每个个体的寿命只有一代，更新进化很快，特别适合于目标函数有噪声干扰或优化程度明显受迭代次数影响的课题 2021/8/2235.2 进化策略进化策略执行过程 1）确定问题的表达方式 -个体由目标变量X和标准差两部分组成，每部分又可以有n个分量，即 2021/8/2245.2 进化策略进化策略执行过程 2）随机生成初始群体，并计算其适应度进化策略中的初始群体由个个体组成，每个个体的内又可以包含n个X i、 i分量产生初始个体的方法是随机生成为便于和传统的方法比较，可以从某个初始点出发，通过多次突变产生个初始个体，该初始点可从可行域中用随机方法选取初始个体的标准差(0)=3.0 3）计算初始个体的适应度，如若满足条件，终止；否则，往下进行 2021/8/2255.2 进化策略进化策略执行过程 4）根据进化策略，用下述操作产生新群体：-4.1)重组：将两个父代个体交换目标变量和标准差，产生新个体一般目标变量采用离散重组，标准差采用中值重组。

离散重组：对父代中两个个体实行随机交叉组合中值重组：从个父代个体中用随机的方法任选两个个体，然后将父代个体各分量的平均值作为子代新个体的分量，构成的新个体4.2)突变：对重组后的个体添加随机量，按照前述变异算子产生新个体4.3)计算新个体适应度4.4)选择：实行(+)或(,)选择策略，挑选一部分个体组成下一代群体5）反复执行第4步，直到达到终止条件，选择最佳个体作为进化策略的结果 2021/8/2265.2 进化策略进化策略与遗。