淘 汰
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
选择概率
适应性》中首先提出的，它是一类借鉴生物界自然选择和
自然遗传机制的随机化搜索算法。GA来源于达尔文的进化 论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。其
基本思想是模拟自然界遗传机制和生物进化论而形成的一
种过程搜索全局最优解的算法。
一、遗传算法概述
2、生物进化理论和遗传学基本知识
(1) 达尔文的自然选择说
轮盘赌选择（roulette wheel selection） 随机遍历抽样（stochastic universal selection）������ 局部选择（local selection）������ 截断选择（truncation selection）������ 锦标赛选择（tournament selection）
二、遗传算法的基本操作
1 选择-复制(selection-reproduction)
(2)在0-1之间产生一个随机数 0.507893 6 0.070221 1 0.545929 8 0.784567 9 0.446930 6 0.291198 5 0.716340 8 0.271901 4 0.371435 6 0.854641 10
二、遗传算法的基本操作
1 选择-复制(selection-reproduction)
选择概率P(xi)的计算公式为: P( xi )
f ( xi )
按比例的适应 选择-复制指的就是以一定的概率从种群中选择若干个体并进行 度分配方法 复制的操作
f (x
j 1
N
j
)
常用选择-复制方法：
������
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
基因(gene)：染色体的一个片段
个体 9 ---染色体 1001
染色体(Chromosome)：问题中个体的某种字符串形式的编码表示 种群(Population)：个体的集合,该集合内的个体数称为种群的大小 基因型(genetype)：基因组合的模型，染色体的内部表现 表现型(phenotype)：染色体决定性状的外部表现
适应度
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 1 1 1 1 1 1 1 1 1 0 1 1 1
一、遗传算法概述
2、生物进化理论和遗传学基本知识
(2) 遗传学基本概念和术语
进化(evolution)：个体逐渐适应生存环境，不断改良品质的过程 适应度(fitness)：反映个体性能的一个数量值 适应度函数(fitness function): 问题中的全体个体与其适应度之间的一个对应关系,一般是一 个实值函数。该函数就是遗传算法中指导搜索的评价函数。 编码(coding)：从表现型到基因型的映射 解码(decoding)：从基因型到表现性的映射
Hale Waihona Puke 二、遗传算法的基本操作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
s2′=10011011
可以看做是原染色体s1和s2的子代染色体
二、遗传算法的基本操作
2 交叉(crossover)——基因重组
其它常用的交叉方法：

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


均匀交叉（uniform crossover）������
遗传（heredity）：
子代和父代具有相同或相似的性状，保证物种的稳定性
变异（variation）：
子代与父代,子代不同个体之间总有差异，是生命多样性的根源
生存斗争和适者生存：
具有适应性变异的个体被保留，不具适应性变异的个体被淘汰
一、遗传算法概述
2、生物进化理论和遗传学基本知识
(2) 遗传学基本概念和术语
主要内容
一、遗传算法概述 二、遗传算法的基本操作
三、遗传算法原理
四、遗传算法的应用
现代智能优化算法
自 由 搜 索 算 法
FS
遗 传 算 法
GA
禁 忌 算 法
TS
蚁 群 算 法
ACO
粒 子 群 算 法
PSO
细 菌 算 法
BC
混 沌 算 法
COA
一、遗传算法概述
1、遗传算法起源
遗传算法(Genetic Algorithm, GA)是由美国的J. Holland教授于1975年在他的专著《自然界和人工系统的