适应性》中首先提出的，它是一类借鉴生物界自然选择和
自然遗传机制的随机化搜索算法。GA来源于达尔文的进化 论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。其
基本思想是模拟自然界遗传机制和生物进化论而形成的一
种过程搜索全局最优解的算法。
一、遗传算法概述
2、生物进化理论和遗传学基本知识
(1) 达尔文的自然选择说
三、遗传算法的原理
标准遗传算法(Standard genetic algorithm, SGA)
Step1 在搜索空间U上定义一个适应度函 数f(x)，给定种群规模N，交叉率Pc和变异 率Pm，代数T； Step2 随机产生U中的N个个体s1, s2, …, sN，组成初始种群S={s1, s2, …, sN}，置代 数计数器t=1； Step3 计算S中每个个体的适应度f(x)； Step4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算 法结束。否则，转Step5；
四、遗传算法的应用
用遗传算法求解：
f ( x) x sin(10 x) 2.0
分析：由于区间长度为3，求解结果精确到6位小数，因此可将自变量
定义区间划分为3×106等份。又因为221 < 3×106 < 222 ，所以本例的 二进制编码长度至少需要22位，编码过程实质上是将区间[-1，2]内对 应的实数值转化为一个二进制串（b21b20…b0）。

循环交叉（Cycle Crossover）
交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换 组合，来产生新的优良品种！
二、遗传算法的基本操作
3 变异(mutation)
变异就是改变染色体某个(些)位上的基因 例如，设染色体s=11001101，将其第三位上的0变为1, 即
s=11001101 →11101101= s′。 s′也可以看做是原染色体s的子代染色体
算法中的一些控制参数：
种群规模： 最大换代数： 交叉率(crossover rate)： 参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc
取值范围一般为0.4～0.99
变异率(mutation rate)： 发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm
取值范围一般为0.0001～0.1
三、遗传算法的原理
标准遗传算法(Standard genetic algorithm, SGA)
Step5 按选择概率P(xi)所决定的选中机会， 每次从S中随机选定1个个体并将其复制， 共做N次，然后将复制所得的N个染色体组 成群体S1； Step6 按交叉率Pc所决定的参加交叉的染 色体数c，从S1中随机确定c个染色体，配对 进行交叉操作，并用产生的新染色体代替 原染色体，得群体S2； Step7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分 别进行变异操作，并用产生的新染色体代替原染色体，得群体S3； Step8 将群体S3作为新一代种群，即用S3代替S，t = t+1，转步Step3；
求解过程： (1)编码
表现型： x 基因型： 二进制编码，串长22位
几个术语
个体（染色体）
基因型：1000101110110101000111
基因
解码
编码
表现型：0.637197
四、遗传算法的应用
用遗传算法求解：
(2)生成初始种群
方式：随机生成长度为22的二进制制串 数量：种群的大小(规模)，如30，50，…
二、遗传算法的基本操作
1 选择-复制(selection-reproduction)
例：轮盘赌选择
8 8 5 2 10 7 12 5 19 10 14
解 (1)计算选择概率和累计概率
个体 1 2 3 4 5 6 7 8 9 10
染色体
0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011
得到的最佳个体： smax=<1111001100111011111100> xmax=1.8506 f(xmax)=3.8503
基因(gene)：染色体的一个片段
个体 9 ---染色体 1001
染色体(Chromosome)：问题中个体的某种字符串形式的编码表示 种群(Population)：个体的集合,该集合内的个体数称为种群的大小 基因型(genetype)：基因组合的模型，染色体的内部表现 表现型(phenotype)：染色体决定性状的外部表现
四、遗传算法的应用
用微分法求解：
f ( x) x sin(10 x) 2.0
f ( x) sin(10 x) 10 x cos(10 x) 0
即： tan( 10 x) 10 x 解有无穷多个
2i 1 i , i 1,2, 20 x0 0 xi xi 2i 1 i , i 1,2, 20
遗传（heredity）：
子代和父代具有相同或相似的性状，保证物种的稳定性
变异（variation）：
子代与父代,子代不同个体之间总有差异，是生命多样性的根源
生存斗争和适者生存：
具有适应性变异的个体被保留，不具适应性变异的个体被淘汰
一、遗传算法概述
2、生物进化理论和遗传学基本知识
(2) 遗传学基本概念和术语
(4)遗传操作 选择：轮盘赌选择法
交叉：单点交叉
变异：小概率变异
四、遗传算法的应用
用遗传算法求解：
(5)模拟结果
设置的参数： 种群大小50,交叉概率0.75 变异概率0.05,最大代数200
世代数 1 9 自变量 1.4495 1.8395 1.8512 适应度 3.4494 3.7412 3.8499
轮盘赌选择（roulette wheel selection） 随机遍历抽样（stochastic universal selection）������ 局部选择（local selection）������ 截断选择（truncation selection）������ 锦标赛选择（tournament selection）
变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素 引起的基因突变.若只有选择和交叉，而没有变异，则无法在初始基 因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进 入终止过程，从而影响解的质量!
三、遗传算法的原理
关键
适者生存 遗传算子
种群繁殖 标准遗传算法流程框图
三、遗传算法的原理
淘 汰
3 4 5 6 7 8 9 10
复制操作能从旧种群中选择出优秀者，但不能创造新的染色体！
二、遗传算法的基本操作
2 交叉(crossover)——基因重组
交叉就是互换两个染色体某些位上的基因 例：设染色体s1=01001011, s2=10010101,交换其后4位基因,即
单点交叉
s1′=01000101,
个体 1 2 染色体
0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011
适应度
8 5 2 10 7 12 5 19 10 14
选择概率
1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 ……
四、遗传算法的应用
是一个接近于0的实数递减序 列
i (i=1,2,…及i=-1,-2,…)
当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值 x19即为区间[-1,2]内的最大值点 37 x19 19 1.85 19 20 此时，函数最大值f(x19）比f(1.85)=3.85稍大
1 1 1 1 1 1 1 1 1 1 0 1 1 1
一、遗传算法概述
2、生物进化理论和遗传学基本知识
(2) 遗传学基本概念和术语
进化(evolution)：个体逐渐适应生存环境，不断改良品质的过程 适应度(fitness)：反映个体性能的一个数量值 适应度函数(fitness function): 问题中的全体个体与其适应度之间的一个对应关系,一般是一 个实值函数。该函数就是遗传算法中指导搜索的评价函数。 编码(coding)：从表现型到基因型的映射 解码(decoding)：从基因型到表现性的映射
s2′=10011011
可以看做是原染色体s1和s2的子代染色体
二、遗传算法的基本操作
2 交叉(crossover)——基因重组
其它常用的交叉方法：

多点交叉（multiple-point crossover）������


均匀交叉（uniform crossover）������
部分匹配交叉（Partially Matched Crossover ） 顺序交叉（Ordered Crossover）������
主要内容
一、遗传算法概述 二、遗传算法的基本操作
三、遗传算法原理
四、遗传算法的应用
现代智能优化算法
自 由 搜 索 算 法
FS
遗 传 算 法
GA
禁 忌 算 法
TS
蚁 群 算 法
ACO
粒 子 群 算 法
PSO
细 菌 算 法
BC
混 沌 算 法