选择算子
轮盘赌选择算法
指针 转动方向 21% 43% 6%
/* once of roulette wheel selection * 输出参数： * 选中的染色体 */
30%
pi
fi
f
j 1
N


i
fi f sum
procedure RWS 1 m←0; 2 r←Random(0,1); //0至1的随机数 3 for i=1 to N 4 m←m+Pi; 5 if r ＜= m 6 return i; 7 end if 8 end for end procedure
k 1
i
交配算子
在染色体交配阶段，每个染色体能否进行交配由交配概 率Pc（一般取值为0.4到0.99之间）决定，其具体过程为： 对于每个染色体，如果Random(0, 1)小于Pc则表示该染色 体可进行交配操作（其中Random(0, 1)为[0, 1]间均匀分布 的随机数），否则染色体不参与交配直接复制到新种群 中。 每两个按照Pc交配概率选择出来的染色体进行交配，经 过交换各自的部分基因，产生两个新的子代染色体。具 体操作是随机产生一个有效的交配位臵，染色体交换位 于该交配位臵后的所有基因。
流程结构



染色体编码 群体初始化 适应值评价 选择算子 交配算子 变异算子 算法流程图和伪代码
应用举例

函数优化问题 算法的执行步骤示意图
基本遗传算法的构成要素
基本遗传算法(Simple Genetic Algorithm:SGA)又 称为简单遗传算法，只使用选择算子、交叉算子和 变异算子这三种基本的遗传算子。
y
max
min fitness
x
search space
爬山的模拟
不断地通过交叉变 异以及选择来达到 爬山的效果
y
max
min fitness
x
search space
爬山的模拟
不断地通过交叉变 异以及选择来达到 爬山的效果
y
max
min fitness
染色体编码方法：首先必须对问题的解空间进行编 码，使之能用遗传算法进行操作。较常用的是二进 制编码方法，现在使用非二进制编码的也逐渐增多。
染色体编码
二进制编码方法（Binary Representation）
U min
U max
U max U min X j 2 j 1
U min
4.1.1 基本原理
生物模拟技术
遗传算法
达尔文进化论
现代遗传学
4.1.1 基本原理
生物进化

生命自从在地球上诞生以来，就开始了漫长的生物 演化历程，低级、简单的生物类型逐渐发展为高级、 复杂的生物类型。这一过程已经由古生物学、胚胎 学和比较解剖学等方面的研究工作所证实。生物进 化的原因自古至今有着各种不同的解释，其中被人 们广泛接受的是达尔文的自然选择学说。
适应值评价，保存最优染色体
选择
交配
变异 重新评价适应值，更新最优染色体
否
满足终止条件 是 结束
*/ Procedure GA begin t←0; initialize(P(t)); //初始化群体 evaluate(P(t)); //适应值评价 keep_best(P(t)); //保存最优染色体 while (不满足终止条件) do begin P(t)← selection(P(t)); //选择算子 P(t)← crossover(P(t)); //交配算子 P(t)← mutation(P(t)); //变异算子 t←t+1; P(t)←P(t-1); evaluate(P(t)); if(P(t)的最优适应值大于Best的适应值) //以P(t)的最优染色体替代Best replace(Best); end if end end
第4章 遗传算法
Contents
1 2
算法简介
基本流程 改进研究 相关应用
3
4
4.1 遗传算法简介
遗传算法是什么？ 遗传算法的思想来源是怎样的？ 它由谁提出的？
遗传算法 GA思想源于自然界“自然选择”和“优 （Genetic Algorithm ，GA） 胜劣汰”的进化规律， 是进化计算的一个分支， 通过模拟生物进化中的自然选择和交配 变异寻找问题的全局最优解。 是一种模拟自然界生物进化过程的随机搜 索算法。 它最早由美国密歇根大学教授John H. Holland提出， 现在已经广泛应用于各种工程领域的优 化问题之中。
遗传算法的实质是通过选择、交叉、变异对模式进行搜索， 低阶、定义长度较小且平均适应值高于群体平均适应值的 模式在群体中的比例将呈指数级增长，即随着进化的不断 进行，较优染色体的个数将快速增加。
模式定理证明了遗传算法寻求最优解的可能性。但不能保 证算法一定找到全局最优。
4.1.1 基本原理
2、积木块假设：指低阶、定义长度较小且平均 适应度值高于群体平均适应值的模式。 积木块假设认为在遗传算法运行过程中，积木块 在遗传算子的影响下能相互结合，产生新的更加 优秀的积木块，最终接近全局最优解。 积木块假设对模式定理作了补充，说明遗传算法具 有能够找到全局最优解的能力。 目前的研究还不能对积木块假设是否成立给出一个 严整的论断和证明，但大量的实验和应用为积木块 假设提供了支持。
j 1 L
0000…0000 1111…1111
2 L 1
X L X L1 ...X 2 X1
浮点数编码方法（Float Point Representation）
群体初始化
一般情况下，遗传算法在群体初始化阶段采用的 是随机数初始化方法。采用生成随机数的方法， 对染色体的每一维变量进行初始化赋值。初始化 染色体时必须注意染色体是否满足优化问题对有 效解的定义。 如果在进化开始时保证初始群体已经是一定程度 上的优良群体的话，将能够有效提高算法找到全 局最优解的能力。
4.1.3 基本思想
潜在解集内选择一组可能解集
一定数目的经过基因编码的个体所组成 产生初代种群 优胜劣汰、适者生存 经过解码得到近似最优解
4.1.4 基本流程
编码和生成初始群体 对群体中的个体适应度进行评价 满足终止条件？
N Y
选择 交叉 变异 终止进化进程， 输出最终结果
4.2 遗传算法的流程
交配算子
单点交叉
父代染色体1 父代染色体2 交配位置 X1 X2 … Xk Xk+1 Xk+2 … XD Y1 Y2 … Yk Yk+1 Yk+2 … YD 交配 子代染色体1 子代染色体2 X1 X2 … Xk Yk+1 Yk+2 … YD Y1 Y2 … Yk Xk+1 Xk+2 … XD




International Conference on Genetic Algorithm ACM Genetic and Evolutionary Computation Conference Workshop on Foundations of Genetic Algorithms and Classifier Systems Genetic Programming Conference International Workshop on Artificial Life ……
fi为个体的适应度；fsum为种群的总适应度；pi为个体i的选 择概率。
轮盘选择的详细描述过程 ① 顺序累计群体内各个体的适应度，得相应的
累计值 Si pk ，设群体有n个个体，最后一
个累计值为Sn。 ② 在[0，Sn] 区间内产生均匀分布的随机数r。 ③ 依次用 Si 与 r比较，第一个出现大于或等于r 的Si所对应的个体i被选为复制对象。 ④ 重复第二步和第三步，直到满足所需要的复 制个体数目。
问题的求解-群体爬山 进化算法的求解问题过程 是一个不断爬山的过程
爬山的模拟
随机地生成初始解
y
max
min fitness
x
search space
爬山的模拟
不断地通过交叉变 异以及选择来达到 爬山的效果
y
max
min fitness
x
search space
爬山的模拟
不断地通过交叉变 异以及选择来达到 爬山的效果
4.1.2 研究进展
GA 研究内容与方向
算法性能 研究
混合算法 研究
并行算法 研究
算法应用 研究
与GA相关的重要学术期刊与国际会议
重要学术期刊



Evolutionary Computation IEEE Transactions on Evolutionary Computation ……
重要国际会议
•
算法结束
遗传算法
4.1.1 基本原理
群体 淘汰
遗传基因重组过程
淘汰的 个体
变异
选择
新种群 交配
种群
父代染色体1 父代染色体2
生物进化过程
子代染色体1
子代染色体2
4.1.1 基本原理
模式定理
1、模式的定义 模式也称积木块（building block），是描述位串子 集的相似性模板，表示基因串中某些特征位相同的 结构。 [定义1] 模式：群体中编码的某些位置具有相似结构 的染色体集合。 如：染色体的编码是由0或者1组成的二进制序列， 模式01***0表示以01开头且以0结尾的编码串对应的 染色体的集合。
双点交叉
父代1： 01| 101| 00110 父代2： 11| 000| 10100 交叉点1 交叉点2
双点交叉
子代1： 01| 000| 00110 子代2： 11| 101| 10100