STEP5 以一个较小的概率p，使得一个染色体的一个基因发生变异，形成 mutpop(t+1);t:=t+1,一个新的群体pop(t)= mutpop(t);返回STEP2。
例4.2 用遗传算法求 max f (x) 1 x2, x [0,1].
由于对连续变量求解，要解决的一个问题是如何编码。假设对解的误 差要求是1/16，则可以采用4位二进制编码。对应关系为
❖ 进化发生在解的编码上。这些编码按生物学的术语称为染色体。由于对 解进行了编码，优化问题的一切性质都通过编码来研究。编码和解码是 遗传算法的一个主题。
❖ 自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通 过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平 均数的后代。
❖ 当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。 ❖ 当染色体结合后，随机的变异会造成子代同父代的不同。
遗传算法
STEP1 选择问题的一个编码；给出一个有N个染色体的初始群体pop(1),t:=1
STEP2 对群体pop(t)中的每一个染色体popi(t)计算它的适应函数 fi fitness( popi (t))
STEP3 若停止规则满足，则算法停止；否则，计算概率
pi
fi
N
,
fi
j 1
i 1, 2 ,, N
若他们结合，采用如下的交配方式称为简单交配
x2 (11| 001)
y1 (11|111)
x3 (01|111)
y2 (01| 001)
x2 (11| 001)
y3 (11| 000)
x4 (01| 000)
y4 (01| 001)
即交换第二个位置以后的基因，得到 y1, y2, y3 和 y4 。若 y4 的第一个基因发生变异，则变成 y4 (11001 ) 。
遗传算法包含以下的主要处理步骤：
❖ 对优化问题的解进行编码，此处，我们称一个解的编码为一个染色体， 组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形 式和利于之后遗传算法中的计算。
❖ 适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。 当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率 分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体组成 种群，形成一个可以繁衍下一代的群体。
遗传算法中的作用 在算法停止时，最优目标值的解有最大的可能被留住 解 解的编码（字符串，向量等） 解中每一分量的特征（如各分量的值） 适应函数值 选定的一组解（其中解的个数为群体的规模） 根据适应函数值选取的一组解 通过交配原则产生一组新解的过程 编码的某一个分量发生变化的过程
最优化问题的求解过程是从众多的解中选出最优的解，生物进化的 适者生存的规律使得最具有生存能力的染色体以最大的可能生存。这样 的共同点使得遗传算法可以在优化问题中应用。
例4.1 用遗传算法求解 f (x) x2,0 x 31, x为整数的最大值。
一个简单的表示解的编码是二进制编码，即0，1字符串。由于变量的最大值是31，因此可以 采用5位数的二进制码。
如：10000 16 11111 31 01001 9 00010 2 以上的5个字符串成为染色体，每一个分量称为基因，每个基因有两种状态0或1。
并以此概率分布从pop（t）中随机选一些染色体构成一个种群 newpop(t+1)={popj(t)|j=1,2, …N} ；
(4.1)
【注】 newpop(t+1)集中可能重复pop（t）中的一个元素，如例4.1中的 就选取两次。
STEP4 通过交配，交配概率为Pc，得到一个有N个染色体的corsspop(t+1);
❖ 染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代 的产生。新一代的产生是一个生殖过程，它产生了一个新解。最后是变 异。新解产生的过程中可能发生基因变异，变异使某些解的编码发生变 化，使解有更大的遍历性。
生物遗传概念在遗传算法中的对应关系
生物遗传概念
适者生存
个体（individual） 染色体(chromosome) 基因(gene) 适应性(fitness) 群体(population) 种群(reproduction) 交配(crossover) 变异（mutation）
定义第i个个体入选种群的概率为
p(xi )
fitness(xi ) fitness(x j )
j
于是，适应函数值大的染色体个体的生存概率自然较大，若群体中4个个体成为种群则极有可能竞争
上的是 x2 (11001 ) , x2 (11001 ) , x3 (01111 ) , x4 (01000 )
第四章 遗传算法
遗传算法
遗传算法（genetic algorithms）是在70年代初期由美国执根 （Michigan）大学的Holland教授发展起来的。1975年， Holland发表了第 一本比较系统论述遗传算法的专著《Adptation in Natural and Artificial Systems》.本章先介绍遗传算法及一些基本性质，然后讨论遗传算法实现 的技术问题，最后通过在约束批量模型的应用了解算法实现过程。
❖ 4.1遗传算法 遗传算法的特征 遗传算法 遗传算法有待研究的主要因素 遗传算法优越性与不足
❖ 4.2模板理论 从模板理论的角度说明遗传算法的收敛性 针对遗传算法的三个算子独立考虑模板的变化给出三个引理 模板定理
4.1遗传算法
❖ 生物进化的基本过程
群体
种群
遗传算法主要借鉴了生物的一些特征，其主要特征体现为：
模拟生物进化，首先要产生一个群体，可以随机取4个染色体组成一个群体， x1 (00000 ) , x2 (11001 ) , x3 (01111 ) , x4 (01000 )
群体有4个个体，适应函数可以依据目标函数而定，如适应函数 fitness(x) f (x) x2
于是 fitness(x1) 0 fitness(x2 ) 252 fitness(x3 ) 152 fitness(x4 ) 82