有待研究的主要因素


解的编码和解码。 初始群体的选取和计算中群体的大小。 适应函数的确定。 三个算子。遗传算法的三个算子是：种群选取、交配和变异或称突变。
遗传算法的优越性可以简单地归结为

遗传算法适合数值求解那些多参数、多变量、多目标和在多区域但连通性较差的 NP—hard优化问题。 遗传算法在求解很多组合优化问题时，不需要有很强的技巧和对问题有非常深入 的了解。 遗传算法同求解问题的其他启发式算法有较好的兼容性。
其中t称为遗传的第t代。T（H,G（t））为模板H所包含 的G（t）中的所有染色体集合。
引理4.1 在生殖过程中，若每一个个体被选入种群newpop(t+1)的概率 为（4.1），且种群的规模与群体相同，则模板H所包含的染色体在t+1时刻 的期望数为
E1 ( H , t 1) f ( H , t ) N ( H , t ) ,
2 例4.2 用遗传算法求 max f ( x) 1 x , x [0,1].
由于对连续变量求解，要解决的一个问题是如何编码。假设对解的误 差要求是1/16，则可以采用4位二进制编码。对应关系为
a b c d (abcd ) 2 4 8 16
表4.2 遗传算法中的一步计算 new pop 0001 交配位 cross 是否 mut pop 00|01 0000 变异 pop N 0000 0 x值
pi ( H , t 1) 1 n 1 (1 p( H , t )) (4.5)
其中，p（H，t）表示t时刻模板H出现的概率。 证明 模板H发生变化的可能是由交配产生的。由于采用交配位后的基因 交换，因此选择第一个模板位到最后一个模板位中的任何一个位置为交配
位都可能产生模板变化，所以，模板发生改变的最大概率是 n 1 。假 设交配的双方有相同的模板，则交配后模板不变。一方不具有同H相同的概 率为 1 p( H , t ) 。于是使模板H改变的最大概率为 (H )
遗传算法包含以下的主要处理步骤：



对优化问题的解进行编码，此处，我们称一个解的编码为一个染色体， 组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形 式和利于之后遗传算法中的计算。 适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。 当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率 分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体组成 种群，形成一个可以繁衍下一代的群体。 染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代 的产生。新一代的产生是一个生殖过程，它产生了一个新解。最后是变 异。新解产生的过程中可能发生基因变异，变异使某些解的编码发生变 化，使解有更大的遍历性。
其中N(H,t)为t时刻T(H,pop(t))所包含的染色体数，
f (H , t)
Y :Y T ( H , pop ( t ))
(4.3)

Y :Y pop ( t )

fitn ess(Y ) T ( H , p op(t )) fitn ess(Y ) p op(t )
( 4.4)
证明 H模板的每一个染色体被选中的平均概率为
染色体称为向量 一个给定的向量结构，包括关心的分量位置和值， 称为该向量的一个模板。 如1010001和1111010 1＊1＊0＊＊ ＊表示基因不同或我们不关心这个位置的取值， 称H= 1＊1＊0＊＊为一个模板 0，1的位置称为模板位置，＊位置称为非模板位置。

模板长度：从第一个模板位置到最后一个模板位置的
j 1
(4.1)
并以此概率分布从pop（t）中随机选一些染色体构成一个种群 newpop(t+1)={popj(t)|j=1,2, …N} ；
【注】 newpop(t+1)集中可能重复pop（t）中的一个元素，如例4.1中的 就选取两次。
STEP4 通过交配，交配概率为Pc，得到一个有N个染色体的corsspop(t+1); STEP5 以一个较小的概率p，使得一个染色体的一个基因发生变异，形成 mutpop(t+1);t:=t+1,一个新的群体pop(t)= mutpop(t);返回STEP2。
定义第i个个体入选种群的概率为
p( xi )
fitness( xi ) fitness( x j )
j
于是，适应函数值大的染色体个体的生存概率自然较大，若群体中4个个体成为种群则极有可能竞争 ) , x2 (11001 ) , x3 (01111 ) , x4 (01000 ) 上的是 x2 (11001 若他们结合，采用如下的交配方式称为简单交配
pc
pc
(H )
在交配的过程中，会出现交配的双方不具有H模板，但交配后却具有H模 板，故有
p1 ( H , t 1) 1 pc
n 1
(1 p ( H , t )) ,
(H )
n 1
(1 p ( H , t )) .
引理4.3 假设模板H在t时刻存在的概率为p(H,t)，经过简单变异，则
第四章
遗传算法
遗传算法
遗传算法（genetic algorithms）是在70年代初期由美国执根 （Michigan）大学的Holland教授发展起来的。1975年， Holland发表了第 一本比较系统论述遗传算法的专著《Adptation in Natural and Artificial Systems》.本章先介绍遗传算法及一些基本性质，然后讨论遗传算法实现 的技术问题，最后通过在约束批量模型的应用了解算法实现过程。



进化发生在解的编码上。这些编码按生物学的术语称为染色体。由于对 解进行了编码，优化问题的一切性质都通过编码来研究。编码和解码是 遗传算法的一个主题。 自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通 过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平 均数的后代。 当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。 当染色体结合后，随机的变异会造成子代同父代的不同。
有
p2 ( H , t 1) 1 pm ( H ) ,
(4.6)
pm 为每个基因变异概率， ( H ) 为H的阶 其中，
定理4.1 （模板定理）假设群体在t时刻有相同模板H的染色体个数为 N(H,t),经过满足引理4.1的种群选取、满足引理4.2的以概率 pc 的交配和满足 引理4.3以概率 pm 的变异，则在t+1时刻，群体中具有H模板的染色体数的期 望值为
遗传算法的不足
（1）编码不规范及编码存在表示的不准确性。 （2）单一的遗传算法编码不能全面地将优化问题的约束表示 出来。
（3）是否能保证收敛到最优解
4.2模板理论
简单遗传算法的主要特征有：



群体和种群的维数相等，且不随代数的变化而变化； 适应函数直接选用目标函数； 种群中的个体通过轮盘赌的方式选取； 种群中的一对个体采用随机交配位的方式产生一对子代； 每一个基因有相同的变异概率。
x2 (11| 001) x3 (01| 111) x2 (11| 001) x4 (01| 000)
y1 (11| 111) y2 (01| 001) y3 (11| 000) y4 (01| 001)
) 。 即交换第二个位置以后的基因，得到 y1 , y2 , y3 和 y4 。若 y4 的第一个基因发生变异，则变成 y4 (11001
所有分量个数减1。 如H= 1＊1＊0＊＊的长度为4，记为 ( H ) 。
模板的阶数：模板位置对应的确定分量个数。
如H= 1＊1＊0＊＊的阶数为3，记为 ( H ) 。 若染色体Y在H的模板位置上对应的分量相同，则称Y 具有H模板。 记G（t）是第t代群体，即第t代染色体集合
T ( H , G(t )) {Y G(t ) | Y具有模板H}, (4.2)
遗传算法
STEP1 选择问题的一个编码；给出一个有N个染色体的初始群体pop(1),t:=1 STEP2 对群体pop(t)中的每一个染色体popi(t)计算它的适应函数 fi fitness( popi (t )) STEP3 若停止规则满足，则算法停止；否则，计算概率 f pi N i , i 1, 2 , , N fi
生物遗传概念在遗传算法中的对应关系
生物遗传概念 适者生存 个体（individual） 染色体(chromosome) 基因(gene) 适应性(fitness) 群体(population) 种群(reproduction) 交配(crossover) 变异（mutation） 遗传算法中的作用 在算法停止时，最优目标值的解有最大的可能被留住 解 解的编码（字符串，向量等） 解中每一分量的特征（如各分量的值） 适应函数值 选定的一组解（其中解的个数为群体的规模） 根据适应函数值选取的一组解 通过交配原则产生一组新解的过程 编码的某一个分量发生变化的过程
Y
N N
1101 13/16
0001 1/16 0011 3/16
平均值=0.7833，交配概率p=1，变异概率pm=0.02
简单遗传算法可以理解为：


求解的问题是极大目标函数的优化问题； 采用0—1二进制编码； pop（t）中的染色体个数是一个常数； 初始群体随机选取 适应函数为目标函数； 按轮盘赌方法选取染色体个数同pop（t）相同的种群； 常规交配方法：一对染色体按随机位交换后的基因； 染色体中的每一个基因都以相同的概率变异。
Y :Y T ( H , pop ( t ))

fitness(Y ) T ( H , pop(t ))
fitness(Y ) pop(t )