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，贝0 1 1 10 . 1 1 1
0 1 11 0 1 0
对种群要确定交叉概率；•。随机选择NX：个个体进行交叉，其余不变。
显然，利用选择、交叉算子可以产生具有更高平均适应值和更好个体的群体。但仅仅如 此，容易导致局部最优解。
变异算子
变异算子能使个体发生突然变异，导入新的遗传信息，使寻优有可能指向未探知区域， 是提高全局最优搜索能力的有效步骤，也是保持群体差异，防止过早出现收敛现象的重要手
段。以一个很小的变异概率己，随机的改变染色体上的某个基因（二）,具有增加群体多 样性的效果。例如：010—000

（1） 选择问题解的一个编码，给出一个有N个染色体的初始群体pop（1），t=1。
（2） 对群体中的每一个染色体i，计算它的适应函数值f（"）。
（3） 若停止规则满足，则算法停止，否则计算概率=^，并以此概率分布，从 pop（t）中随机选取N个染色体构成一个新的种群newpop（t）。
（4） 通过交叉（交叉概率为<），得到N个染色体的crosspop（t+1）。
（5）