变异群体
二、遗传算法原理及实现技术(10)
3、遗传算法的基本实现技术
(1)编码方法 (2)种群初始化 (3)适应度函数 (4)遗传算子 (5)参数选择
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(11)
(1)编码方法
在遗传算法中如何描述问题的可行解，即将一个问 题的可行解从其解空间转换到遗传算法所能处理的搜 索空间的转换方法就称为编码。编码是应用遗传算法 时要解决的首要问题，也是设计遗传算法时的一个关 键步骤。
东北大学信息科学与工程学院
一、遗传算法概述(3)
2、遗传算法的基本思想
z 根据问题的目标函数构造适值函数 (Fitness Function)； z 产生一个初始种群(10-1000)； z 根据适值函数的好坏，不断选择繁殖； z 若干代后得到适值函数最好的个体即最优解。
东北大学信息科学与工程学院
选择 遗传运算 更新种群
东北大学信息科学与工程学院
向改进方向移动(在编码空间做)
二、遗传算法原理及实现技术(4)
(1)编码
解空间
编码
一个解的编码 染色体(chromosome)
东北大学信息科学与工程学院
其中的一个码和码所在的位置 基因(gene)/基因位
二、遗传算法原理及实现技术(5)
(2)初始化
编码方法可以分为三大类：二进制编码方法、实 数编码方法、符号编码方法。
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(12)
①二进制编码方法
二进制编码方法是遗传算法中最常用的一种编码方 法，它使用的编码符号集是由二进制符号0和1所组成的 二值符号集{0,1}，它所构成的个体基因型是一个二进 制编码符号串。
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(1)
1、算法框架 2、算法步骤 3、遗传算法的基本实现技术 4、计算实例
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(2)
1、算法框架 算法框架
东北大学信息科学与工程学院
开始
产生初始种群
Y
判断停止条件
N
计算适值函数
输出
停止
评估(在解空间做)
一、遗传算法概述(2)
1、 遗传算法起源
遗传算法是模拟生物在自然环境中的遗传和进化 过程而形成的一种自适应全局优化概率搜索算法。 ◆ 美国密执安大学的J. Holland教授于1975年在他的 专著《自然界和人工系统的适应性》中首先提出。 ◆上世纪80年代由Goldberg进行归纳总结，形成了遗 传算法的基本框架。
1 子代个体
2
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(8)
(5)变异操作
父代个体
变异位 Pmutate
变异概率
mutate 随机改变染色体某些基因位上的遗传信息
子代个体
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(9)
(6)选择操作
初始群体 进化群体
select
东北大学信息科学与工程学院
应于每个串的自变量的值：
xi
=
ai
+
decim al (1001L 0012 ) ×
bi − ai 2 Li − 1
其中decimal(string2)表示二进制串的十进制值。
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(15)
公式： 假设某一个体的编码是：bl bl −1 L b2b1
∑ 则对应的解码公式是： x
一、遗传算法概述(4)
3、遗传算法的构成要素
z 种群(Population), 种群大小(Pop-size) z 基因表达法——编码方法 z 遗传算子(Genetic Operator)：
交叉(Crossover)，变异(Mutation) z 选择策略:一般为正比选择 z 停止准则:一般是指定最大代数
=
a
+
⎛ ⎜⎝

l =1
bi
2i
−1
⎞ ⎟⎠
b−a 2l −1
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(16)
k
一个潜在解的染色体被长度为 L = ∑ Li 的二进制串 i =1
表达；前L1位对应区间[a1,b1]里的一个值，随后的L2位 对应区间[a2,b2]里的一个值，等等；最后的Lk位对应区 间[ak,bk]，里的一个值。
解的编号
解的编码
1
2
3
4
.
.
.
群体规模
.
.
.
POP
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(6)
(3)计算适应度
解码
计算适 应度
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(7)
(4)交叉操作
交叉位 Pcross
交叉概率
1 父代个体
2
cross 连续改变染色体多个基因位上的遗传信息
使用解编码后自变量序列的函数值f评价每代中的每 个染色体，按照适应值的概率分布选择新群体，通过变 异和杂交算子改变新群体中的染色体。经过若干代后， 如果观察不到更进一步的改进，则最好染色体就表示一 个可能是全局的最优解。通常根据速度和资源判据在一 固定数目的循环后停止算法。
二进制编码符号串的长度与问题所要求的求解精度有 关。设某一参数的取值范围是[a,b]，精度为ζ，则需 要的编码符号串的长度L如下所示：
2L−1 < b − a ≤ 2L −1
ξ
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(13)
设目标函数f(x1,…,xk>0，xi的定义域为Di,现以某个 要求的精度求f的最大值。
东北大学信息科学与工程学院
二、遗传算法原理及实现技术(14)
精度取自变量小数点后第6位。显然，要达到这样的
精度，每个域Di应该被分割成 (bi − ai )×106个等尺寸的
区间。这里用Li表示使
(bi − ai ) × 106 ≤ 2 Li − 1
成立的最小整数。这样，对每个变量xi，由串长位Li的 二进制编码表达显然能满足精度要求。下面的公式对
遗传算法原理与应用
2007 年 4 月
遗传算法原理与应用
一、遗传算法概述 二、遗传算法原理及实现技术 三、遗传算法的改进 四、遗传算法的应用
东北大学信息科学与工程学院
一、遗传算法概述(1)
1、遗传算法起源 2、遗传算法的基本思想 3、遗传算法的构成要素 4、遗传算法的特点
东北大学信息科学与工程学院
东北大学信息科学与工程学院
一、遗传算法概述(5)
4、遗传算法的特点
z遗传算法以决策变量的编码作为运算对象。可以很 方便地引入和应用遗传操作算子。 z遗传算法直接以目标函数值作为搜索信息，不需要 目标函数的导数等其它信息。 z遗传算法同时进行解空间的多点搜索，具有隐含并 行性。 z遗传算法属于一种自适应概率搜索技术，其选择、 交叉、变异等运算都是以概率的方式进行。实践和理 论都已证明了在一定条件下遗传算法总是以概率1 。