3） 乘幂标 f’ = fK 4） 指数定标
f’ = exp(-bf)
4.1 遗传算法的基本描述
4.1.6 遗传算子
包括三个基本遗传算子（genetic operator）：选择，交叉和变 异。这三个遗传算子具有一些特点： （1）这三个算子的操作都是随机化操作，因此，群体中个体向最优 解迁移的规则是随机的。需要强调的是，这种随机化操作和传 统的随机搜索方法是有区别的。遗传操作进行的是高效有向的 搜索，而不是如一般随机搜索方法所进行的无向搜索。 （2）遗传操作的效果和所取的操作概率、编码方法、群体大小，以 及适应度函数的设定密切相关。 （3）三个基本算子的操作方法和操作策略随具体求解问题的不同而 异。或者说，是和个体的编码方式直接相关。
3）非冗余性（non-redundancy）：染色体和潜在解必须 一一对应。
4.1 遗传算法的基本描述
4.1.3 遗传编码
根据模式定理，De Jong进一步提出了较为客观明确的 编码评估准则，称之为编码原理。具体可以概括为两 条规则： 1）有意义积木块编码规则：编码应易于生成与所求问题 相关的短距和低阶的积木块。
4.1.6 遗传算子
一、选择（selection）算子 从群体中选择优胜个体，淘汰劣质个体的操作叫选择。 选择算子有时又称为再生算子（reproduction operator）。选择即从当前群体中选择适应度值高的个 体以生成配对池（mating pool）的过程。
4.1.6 遗传算子
i akl {0,1}
1 1 1 2 2 2 i i i n n n xk ak a a a a a a a a a a a 1 k2 kl1 k1 k 2 kl2 k1 k 2 kli k1 k 2 kln
对于给定的二进制编码位串sk,位段译码函数的形式为
li v u li j i i i i i i xi i (ak , a , , a ) u ( a 2 ) 1 k2 kli i kj li ， i = 1,2,…,n 2 1 j 1
4.1 遗传算法的基本描述
2．其他编码 1) 2) 大字符集编码（相对于二进制编码） 序列编码（TSP）
3)
4) 5)
实数编码
树编码 自适应编码
6)
乱序编码
4.1 遗传算法的基本描述
4.1.4 群体设定 1。初始群体的设定 一般来讲，初始群体的设定可以采用如下的策略： 1) 根据问题固有知识，设法把握最优解所占空间在整个 问题空间中的分布范围，然后，在此分布范围内设定 初始群体。
4.1.3 遗传编码
定义：由问题空间向GA编码空间的映射称为编码，而由 编码空间向问题空间的映射成为译码。
问题编码一般应满足以下三个原则：
1） 完备性（completeness）：问题空间中的所有点都能 能成为Gsoundness）：GA编码空间中的染色体位串 必须对应问题空间中的某一潜在解。
2）最小字符集编码规则：编码应采用最小字符集，以使 问题得到自然、简单的表示和描述。
4.1 遗传算法的基本描述
1．二进制编码 1）连续实函数的二进制编码 设一维连续实函数 f ( x), x [u, v] 采用长度维L的二进制字符串进 行定长编码，建立位串空间：
S L x1, x2 ,, xK
S {x1, x2 ,, xK } ，K=2L
L
i 1
该空间上的个体位串结构为 1 1 1 2 2 2 i i i n n n xk (ak , a , , a , a , a , , a , , a , a , , a , , a , a , , a 1 k2 kl1 k1 k2 kl2 k1 k2 kli k1 k2 kln ),
xk (ak1, ak 2 ,, akL )
akl 0,1
k=1,2,…,K; l=1,2,…,L; K=2L 表示精度为x (v u) /(2 L 1) 。 将个体又从位串空间转换到问题空间的译码函数 : {0,1}L [u, v] 的公式定义为：
vu L xk (ak1 , ak 2 , , akL ) u L ( akj 2 L j ) 2 1 j 1
4.1 遗传算法的基本描述
对于n维连续函数 f ( x), x ( x1 , x2 , , xn ), xi [ui , vi ](i 1,2, , n) ， 各维变量的二进制编码位串的长度为 li , 那么x 的编码从左到右依次构 n 成总长度为L li 的二进制编码位串。相应的GA编码空间为：
4.1 遗传算法的基本描述
4.1.1 标准遗传算法流程：
• • • • 1．编码 2．初始群体的生成 3．适应度评估检测 4．WHILE <未满足迭代终止条件> DO – 1. 选择 – 2. 交叉 – 3. 变异 – 4. 适应度评估检测 • 5．END DO
选择
交叉
当前代
中间代
下一代
4.1 遗传算法的基本描述
2) 先随机生成一定数目的个体，然后从中挑出最好的个 体加入到初始群体中。这一过程不断重复，直到初始 群体中个体数达到了预定的规模。
4.1 遗传算法的基本描述
4.1.4 群体设定 2。群体规模的设定 • 根据模式定理，若群体规模为 M ，则遗传操作可 从这M个个体中生成和检测O(M3)个模式，并在此 基础上不断形成和优化积木块，直到找到最优解。 群体规模 N ，模式阶 i ，被采样的模式数量的期望 Mi (i = 1, 2, …, )之间满足如下关系： M N
i
• •
2i
群体规模一般不随迭代而变化，但也不绝对。
4.1 遗传算法的基本描述
4.1.5 适应度函数（评价函数） 1。目标函数映射成适应度函数 2。适应度函数定标
1）线性定标（linear scaling）
f’ = af + b 2）截断（sigma truncation）
f ' f ( f c )