一、遗传算法简介
达尔文 (Darwin) 的进化论：自然选择原理
自然选择就是指生物由于环境中某些因素的影响而使得
有利于一些个体的生存，而不利于另外一些个体生存的
演化过程：物竞天择，适者生存 遗传：子代和父代具有相同或相似的性状，保证物种的 稳定性； 变异：子代与父代，子代不同个体之间总有差异，是生 命多样性的根源；
选择运算 个体评价 交叉运算
变异运算
群体p(t+1)
解
码
解集合
二、标准遗传算法
标准遗传算法的主要步骤
Step1 根据优化问题的特点对优化变量进行编码，随机产 生一组初始个体构成初始种群,并评价每一个个体的适配值; Step2 判断算法收敛准则是否满足。若满足则输出搜索结果； 否则执行以下步骤; Step3 根据适配值大小以一定方式进行复制(选择)操作; Step4 按交叉概率 pc 执行交叉操作; Step5 按变异概率 pm 执行变异操作; Step6 更新种群，返回Step2.
二、标准遗传算法
标准遗传算法算例---手工计算
max
s .t.
2 f x1 , x2 x12 x2
x1 0,1 7 x2 0,1 7
编码：二进制编码 基因型X= 1 0 1 1 1 0 对应的表现型是：X= 5, 6
二、标准遗传算法 ① ② 个体编号 初始群体 i P(0) 1 2 3 4 011101 101011 011100 111001 ③ x1 3 5 3 7 ④ x2 5 3 4 1 ⑤ f(x1,x2) 34 ∑fi=143 34 fmax=50 25 f=35.75 50 ⑥ f i/ ∑ f i 0.24 0.24 0.17 0.35
死后，20世纪初另外的科学家重新发现这个定律之后，
孟德尔的工作的重要性才被大家了解。
一、遗传算法简介 遗传学时间表 遗传学的发展 1859年 查尔斯· 达尔文发表了《物种起源》 1865年 格雷戈尔· 孟德尔发表文章《植物杂交试验》
1903年 发现染色体是遗传单位 1927年 基因的物理变化叫做基因突变 1931年 交叉互换导致了基因重组 1944年 分离出遗传物质DNA（那时叫做遗传要素） 1953年 提出DNA的双螺旋结构 1958年 试验证明DNA是半保留复制的 1961年 提出三联体遗传密码 ……
X:
5.80
6.90
3.05
3.80
5.00
T
x [5.08,6.90,3.50,3.80,5.00]
二、标准遗传算法 浮点数编码方法中，必须保证基因值在给定的区间限 制范围内，遗传算法中所使用的交叉、变异等算子也 必须保证产生的新个体也在区间限制范围内。 当用多个字节表示一个基因值时，交叉运算必须在两 个基因的分界字节处进行，而不能在某个基因的中间 字节分隔处进行。
l
U max U min l 2 1
二、标准遗传算法 参数编码时的对应关系
00000......000000 0 00000......000001 1 ................. 11111......111111 2l 1
设某一个体的编码是 则对应的解码公式为
个个体的适应程度被评价，通过自然选择和变异产 生新的生命群体，该群体就是下一代的个体。
一、遗传算法简介 遗传算法与自然进化的比较
自然界
染色体 基因 等位基因 染色体位置 基因型 表现型
遗传算法
字符串 字符，特征 特征值 字符串位置 结构 参数集，译码结构
进化过程三种运算：选择、交叉、变异
一、遗传算法简介 群体p(t) 遗传空间 解空间
二、标准遗传算法
二、标准遗传算法
标准遗传算法的5要素---初始种群
根据问题固有知识，设法把握最优解所占空间在整个 问题空间中的分布范围，然后，在此分布范围内设定 初始群体。 先随机生成一定数目的个体，然后从中挑出最好的个 体加到初始群体中。这个过程不断迭代，直到初始群 体中个体个数达到要求。 一般情况下，遗传算法在群体初始化阶段采用的是 随机数初始化方法。 群体的多准遗传算法
编码原则 有意义积木块编码原则：应使用能易于产生与所求 问题有关的且具有低阶、短定义长度模式的编码方 案。 最小字符集编码原则：应使用能使问题得到自然表 示或是描述的具有最小编码字符集合的编码方案。 编码规范
完备性：问题空间中的所有点都作为遗传空间中的 点表现。 健全性：遗传空间中的染色体对应所有问题空间中 的候选解。 非冗余性：染色体和候选解一一对应。
解码：从基因型到表现型的映射。
一、遗传算法简介 遗传算法的基本思想---借鉴
对于一个优化问题，一定数量的候选解（生命个体）
被表示为抽象的数字串（染色体），通过进化向更 好的解发展。 候选解一般为二进制数字串（即0和1），但也可能 有其他表示。一开始，生命个体完全随机产生，之
后一代一代的进化，在进化过程中的每一代，每一
二、标准遗传算法
标准遗传算法的5要素
编码：解空间 遗传空间 初始种群生成：随机生成 适应度函数设计：遗传空间 解空间 遗传操作设计：选择、交叉、变异
控制参数设定：交叉概率：0.4 - 0.99;
变异概率： 0.0001~0.1；终止代数： 100~500； 种群规模：20-100。
一
简介
二
遗 传 算 法
四
标准遗传算法
三
遗传算法理论
改进遗传算法
一、遗传算法简介 模拟自然界中生物进化的发展规律，借鉴生物界自然 选择原理和自然遗传机制而形成的一 种迭代式自适应 概率性全局优化搜索算法。 简单易懂、通用、鲁棒性强、适合并行处理，可用于 解决各种复杂优化问题。 70年代初期美国 密歇根(Michigan)大学John Holland教 授首先提出。 以《Adaptation in natural and Artificial systems》(1975)出版为标志。

U min U min
U max
X:
l
bl bl 1 bl 2 ... b2 b1
U max U min x U min ( bi 2 ) l 2 1 i 1
i 1
二、标准遗传算法
二进制编码优点
编码、解码操作简单易行； 交叉、变异等遗传操作便于实现； 符合最小字符集编码原则； 便于利用模式定理对算法进行理论分析。
二进制编码缺点
二进制编码存在着连续函数离散化的映射误差。编码 串长度较短，达不到精度；而编码串较长，会使遗传 算法的搜索空间急剧扩大。 二进制编码不便于反映出所求问题的特定知识，不便 于开发出针对问题专门只是的遗传运算算子 不便于处理非平凡约束条件。
二、标准遗传算法
浮点数编码
浮点数编码方法，就是指每个基因值用某一范围内 的一个浮点数来表示，个体的编码长度等于其决策 变量的个数。因为这种编码方法使用的是决策变量 的真实值，所以浮点数编码也叫真值编码。 若某一个优化问题含有5个变量，且每个变量都有边界， 基因型 表现型
一、遗传算法简介 遗传学基本概念及术语 基因：染色体的一个片段，通常为单个参数的编码值。 基因座：遗传基因在染色体中所占据的位置，同一基 因座可能有的全部基因称为等位基因； 染色体：携带基因信息的数据结构，简称个体。 基因型：遗传因子组合的模型，染色体的内部表现； 表现型：由染色体决定性状的外部表现，基因型形成 的个体；
111111
111001 111010
7
7 7
7
1 2
98
50
fmax=98
f=58.75 53
0.42
0.21 0.23
二、标准遗传算法
标准遗传算法的5要素---编码
遗传算法不能直接 处理问题空间的参 数，必须把它们转 换成遗传空间的、 由基因按一定结构 组成的染色体或个 体。这一转换过程 实际上是将问题空 间转换为GA空间。
一、遗传算法简介 个体：指染色体带有特征的实体；
种群：个体的集合，该集合内个体数称为种群的大小；
种群大小：种群中个体的数量，也叫群体规模。 适应度：个体性能的数量值，度量某个物种对于生存环 境的适应程度。 选择：指决定以一定的概率从种群中选择若干个体的操 作； 复制：细胞在分裂时，遗传物质DNA通过复制而转移到 新产生的细胞中，新的细胞就继承了旧细胞的基因;
一、遗传算法简介 交叉：在两个染色体的某一相同位置处DNA被切断，其 前后两串分别交叉组合形成两个新的染色体。又称基因 重组，俗称“杂交”; 变异：在细胞进行复制时可能以很小的概率产生某些复 制差错，从而使DNA发生某种变异，产生出新的染色体， 这些新的染色体表现出新的性状; 编码：表现型到基因型的映射；
111011
1 1 1 1 0 1 0 1 1 0 0 1
6
交叉 变异
111010
0 1 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 1
0 1 1 1 0 1
二、标准遗传算法 ⒁ 子代群体P(1) 011101 ⒂ x1 3 ⒃ x2 5 34 ⒄ f(x1,x2) ∑fi =235 ⒅ fi/∑fi 0.14
二、标准遗传算法 ⑦ ⑧ ⑨ ⑩ 选择次 选择结 配对情 交叉点 数 果 况 位置 1 011101 ⑾ ⑿ 交叉结 变异 果 点 011001 4 ⒀ 变异结果 011101
1
1
111001
101011
1-2
3-4
1-2：2
3-4：4
111101
101001
5
2
111111
111001
2
111001
生存斗争和适者生存：具有适应性变异的个体被保留， 不具适应性变异的个体被淘汰。