GA遗传算法概述.docx

遗传算法及其应用
摘要：遗传算法是一种基于生物自然选择和遗传机理的随机搜索与优化方法。近年来,由于遗传算法在求解复杂问题中的巨大潜力及其在工业工程领域的成功应用,受到了国内外学者的广泛关注。本文详细介绍了遗传算法的基本原理、主要特征以及主下两个方法：（1）用随机方法产生，只有这样选取才能达到所有状态的遍历，使最优解在遗传算法的进化中最终得以生存。（2）使用其他优化方法或启发式方法选取使初始群体更优良。


把当前群体中的个体按与适应值成比例的概率^复制到新的群体中，遗传算法中最
常用的选择方式是轮盘赌选择方式。轮盘赌选择步骤如下：
（1）求群体中所有个体的适应值总和S；
（2）产生一个0到S之间的随机数M；
（3）从群体中编号为1的个体开始，将其适应值与后续个体的适应值相加，直到累加和大于等于M,则停止。其中，那个最后加进去的个体即为新选择的个体。
选择算子作用的效果是提高了群体的平均适应值及最差的适应值，低适应值的个体趋于被淘汰，高适应值的个体趋于被复制，但是是以损失群体的多样性为代价，选择算子并没有产生新的个体，当然群体中最好个体的适应值不会改进。
交叉算子交叉算子（又称杂交算子）每次作用在种群随机选取的两个个体上产生两个不同的子个
体，它们一般与父个体不同，但又包含父个体的遗传物质，交叉运算是遗传算法区别于其它进化算法的重要特征。
交叉规则内容包括两个方面：（1）从种群中对个体随即配对，并按预定的交叉概率来决定是否进行交叉操作。（2）设定个体的交叉点，并对这些点前后的配对个体的基因相互交换。
例如：首先产生一个1到h（其中h为染色体分量的个数）的随机数i（称为交叉点），然后配对的两个个体相互交换从（i+1）到h的位子，如对以下两个数进行交叉且交叉点选择在2,即i=2，贝I」1110—111
0111010
对种群要确定交叉概率=。随机选择NXM个个体进行交叉，其余不变。显然，利用选择、交叉算子可以产生具有更高平均适应值和更好个体的群体。但仅仅如此，容易导致局部最优解。
变异算子变异算子能使个体发生突然变异，导入新的遗传信息，使寻优有可能指向未探知区域，
是提高全局最优搜索能力的有效步骤，也是保持群体差异，防止过早出现收敛现象的重要手
段。以一个很小的变异概率入，随机的改变染色体上的某个基因C二)，具有增加群体多
样性的效果。例如：010—000

选择问题解的一个编码，给出一个有N个染色体的初始群体pop(1),t=1。
对群体中的每一个染色体?■?：-，计算它的适应函数值f「)。
若停止规则满足，则算法停止，否则计算概率=^—，并以此概率分布，从
pop(t)中随机选取N个染色体构成一个新的种群newpop(t)。
通过交叉(交叉概率为Pc),得到N个染色体的crosspop(t+1)。
以较小的变异概率凡，使得某染色体的一个基因发生变异，形成新的群体
mutpop(t+1)。令t=t+1，pop(t)=mutpop(t)，重复第(2)步。流程如图一所示。

遗传算法的优越性：(1)作为数值求解方法具有普适性，对目标函数几乎没有要求，总能以极大概率找到全局最优解。(2)遗传算法在求解很多组合优化问题时，不需