产生初 始种群
计算 适应度 满足优化准则？
最佳 个体
选择 开始 交叉
结果
变异
基本遗传操作(SGA)可以定义为一个 元组 基本遗传操作 可以定义为一个8元组 可以定义为一个 SGA=(C, E , P0 , M , Φ , Г , Ψ, Τ ) C－个体的编码方法，SGA使用固定长度二进制符号串 －个体的编码方法， 使用固定长度二进制符号串 的编码方法； 的编码方法； E－个体的适应度评价函数； －个体的适应度评价函数； P0－初始群体； －初始群体； M－群体大小，一般取20～100； －群体大小，一般取 ～ ； Φ－选择算子，SGA使用比例选择算子； －选择算子， 使用比例选择算子； 使用比例选择算子 Г－交叉算子，SGA使用单点交叉算子； －交叉算子， 使用单点交叉算子； 使用单点交叉算子 Ψ－变异算子，SGA使用基本位变异算子； －变异算子， 使用基本位变异算子； 使用基本位变异算子 Τ－算法终止条件，一般终止进化代数为100～500。 －算法终止条件，一般终止进化代数为 ～ 。
பைடு நூலகம்
适应度 8 5 2 10 7 12 5 19 10 14
选择概率 0.086957 0.054348 0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174
累积概率 0.086957 0.141304 0.163043 0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000
初代种群选择之后，按照适者生存，优胜劣汰原理， 初代种群选择之后，按照适者生存，优胜劣汰原理， 适者生存 原理 逐代演化产生越来越好的近似解。 逐代演化产生越来越好的近似解。 在每一代，根据问题域中个体的适应度大小挑选个体，并 在每一代，根据问题域中个体的适应度大小挑选个体， 个体的适应度大小挑选个体 借助组合交叉和变异产生新的解集的种群。 借助组合交叉和变异产生新的解集的种群。 末代种群中的个体经过解码，可以作为问题的近似最优解 末代种群中的个体经过解码， 解码
如果只考虑交叉操作实现进化机制， 如果只考虑交叉操作实现进化机制，在多数情况下是不行 的，这与生物界近亲繁殖影响进化历程是类似的。 这与生物界近亲繁殖影响进化历程是类似的。 因为种群的个体数是有限的，经过若干代交叉操作， 因为种群的个体数是有限的，经过若干代交叉操作，出 源于一个较好祖先的子个体逐渐充斥整个种群的现象， 现源于一个较好祖先的子个体逐渐充斥整个种群的现象，问 过早收敛， 题会过早收敛 当然得到的解也不能代表最优解。 题会过早收敛，当然得到的解也不能代表最优解。为避免过 早收敛，有必要在进化过程中加入具有新遗传基因的个体。 早收敛，有必要在进化过程中加入具有新遗传基因的个体。 解决办法之一是效法自然界的生物变异。 解决办法之一是效法自然界的生物变异。
1 10 9 2 3 4 5 8 7 6
1 2 3 4 5 6 7 8 9 10
个体 1 2 3 4 5 6 7 8 9 10
染色体编码 0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011
(3)遗传算子 遗传算子
SGA的遗传算子 的遗传算子: 的遗传算子 选择算子 选择算子 交叉算子 交叉算子 变异算子 变异算子
(4)SGA的运行参数 的运行参数
N:群体大小 群体中所含个体的数量 群体大小,群体中所含个体的数量 群体大小 群体中所含个体的数量,20—100 T:遗传算法的终止进化代数 遗传算法的终止进化代数,100—500 遗传算法的终止进化代数 Pc:交叉概率 0.4—0.99 交叉概率 Pm:变异概率 0.0001-0.1 变异概率: 变异概率
选择算法： 选择算法： （1）轮盘赌选择 ） （2）随机遍历抽样 ） （3）局部选择 ） （4）截断选择 ） （5）锦标赛选择 ）
轮盘赌选择方法类似于博彩游戏中的轮盘 赌。如图所示，个体适应度按比例转化为选中 如图所示， 概率，将轮盘分成 个扇区 因为要进行10次 个扇区， 概率，将轮盘分成10个扇区，因为要进行 次 选择，所以产生 个 ， 之间的随机数 之间的随机数， 选择，所以产生10个[0，1]之间的随机数，相 当于转动10次轮盘，获得10次转盘停止时指针 当于转动 次轮盘，获得 次转盘停止时指针 次轮盘 位置，指针停止在某一扇区， 位置，指针停止在某一扇区，该扇区代表的个 体即被选中。 体即被选中。
进化计算（Computational intelligence)
遗传算法（GA） 进化规划（EP） 进化策略（ES） 遗传程序设计（GP）
遗传算法的主要应用领域
应用领域 控制 规划 设计 组合优化 图像处理 信号处理 机器人 人工生命 说明 煤气管道控制,防避导弹控制,机器人控制 生产规划,并行机任务分配 VLSI布局,通信网络设计,喷气发动机设计 TSP问题,背包问题,图划分问题 模式识别,特征提取 滤波器设计 路径规划 生命的遗传进化
选择，再生
0001100000, 1110010010, 1100000001, 1001110100,1010101010 1110010110, 1001011011, 1001110100, 1001110100, 0001010011
交叉
0001010110, 111101101, 1100000100, 1001110100,1010101011 1110100000, 1000010010, 1001110001, 1001110100, 0001010010
遗传算法简介
第一节 概述 一、发展 70年代，美国Michigan大学的John Holland 遗传算法（Genetic Algorithms---GA) 从试图解释自然系统中生物的复杂适应过程入手，模拟生物进 化的机制来构造人工系统的模型。 1975 “Adaptation in Natural and Artificial System”
四、遗传算法的基本思想
遗传算法是从代表问题可能潜在解集的 种群开始的 一个种群开始的，而一个种群则由经过基因编 一个种群开始的，而一个种群则由经过基因编 码的一定数目的个体组成。每个个体实际上是 码的一定数目的个体组成。 组成 染色体带有特征的实体。 染色体带有特征的实体。 因此，在一开始，需要实现从表现型到基 因此，在一开始，需要实现从表现型到基 因型的映射即编码工作 因型的映射即编码工作。 工作
6、复制 细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细 胞继承旧细胞的基因 7、交叉 有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，也 即在两个染色体之间的某一相同位置处DNA被切断，其前后两串分别交 叉组合形成两个新的染色体。（基因重组） 8、变异 在细胞进行复制时可能以很小的概率产生某些差错，从而使DNA发生 某种变异，产生出新的染色体 9、编码 DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码
二、生物进化理论的有关概念
1、遗传 亲代把生物信息交给子代，子代按照所得信息而发育、分 化，因而子代总是和亲代具有相同或相似的性状。 2、变异 亲代和子代之间以及子代的不同个体之间的差异 3、生存斗争和适者生存
三、遗传学的有关概念 1、染色体 遗传物质的主要载体，由多个遗传基因组成 2、个体 染色体带有特征的实体 3、进化 生物在其延续过程中，逐渐适应其生存环境，使得其 品质不断得到改良的现象 4、适应度 5、选择 以一定的概率从种群中选择若干个体的操作。一般基 于适应度的优胜劣汰的过程
1000110100
初始种群
0001100000, 0101111001, 0000000101, 1001110100,1010101010 （8） （5） （2） （10） （7） 1110010110, 1001011011, 1100000001, 1001110100, 0001010011 （12） （5） （19） （10） （14）
①二进制编码 真值编码) ②浮点数编码方案(真值编码) 浮点数编码方案(真值编码 ③ 符号编码方法
(2)适应度函数 适应度函数
评估函数(evaluation function) 评估函数 ---评估染色体优劣的绝对值 评估染色体优劣的绝对值 适应度函数(fitness function) 适应度函数 ---评估染色体相对于整个群体的优劣的相对值 评估染色体相对于整个群体的优劣的相对值
变异
0001010110, 111101101, 1100000100, 1001110100,1010101011 1110100000, 1000010010, 1000110001, 1001110100, 0001010010
遗传算法的进化过程
二、遗传算法描述 1、随机产生一定数目初始种群，个体表示为染色体的基因编码 、随机产生一定数目初始种群， 2、计算个体适应度，判断是否符合优化标准，若符合，输出最佳 、计算个体适应度，判断是否符合优化标准，若符合， 个体及其代表的最优解，结束计算；否则转向 个体及其代表的最优解，结束计算；否则转向3 3、依据适应度选择再生个体 、 4、按照一定的交叉概率和交叉方法，生成新个体 、按照一定的交叉概率和交叉方法， 5、按照一定的变异概率和变异方法，生成新个体 、按照一定的变异概率和变异方法， 6、由交叉和变异产生新一代的种群，返回 2 、由交叉和变异产生新一代的种群，
显然，适应度高的个体被选中的概率大， 显然，适应度高的个体被选中的概率大，而 且可能被选中， 且可能被选中，而适应度低的个体则很有可能被淘 和个体3被淘汰 汰。在第一次生存竞争考验中个体2和个体 被淘汰， 在第一次生存竞争考验中个体 和个体 被淘汰， 再生。 代之以个体8和个体 。这个过程被称为再生 代之以个体 和个体6。这个过程被称为再生 和个体