单亲遗传算法最优群体规模的研究.pdfVIP

单亲遗传算法最优群体规模的研究1 李茂军，罗安，刘定国 长沙理工大学电气与信息工程学院，长沙（410076 ） 湖南大学电气与信息工程学院，长沙（410082 ） 摘 要：通过研究单亲遗传算法每一次遗传迭代所处理的有效图式的数量，建立研究单亲遗 传算法最优群体规模的数学模型，论证单亲遗传算法最优群体规模的存在性。在应用单亲遗 传算法解决实际问题时应该选择适当的群体规模才能使算法有较高的计算效率。 关键词：单亲遗传算法，图式，群体规模，最优 1 引言 在用遗传算法解决工程实际问题时，应该合理地选择群体规模N 的大小。如果N 太小, 不能产生充分多的采样点,容易导致算法收敛于局部最优解；反之，如果N 太大,每一代的适 值计算量太大,收敛速度慢。那么,对于N 的选择是否有一个最佳值或最佳取值范围呢？有学 者对此进行了研究，答案是肯定的[1] 。传统遗传算法主要采用交叉算子繁殖后代，但（1） [2,3] [4] 当遗传算法的染色体采取序号编码 ；（2 ）所求解的问题属有约束优化问题 时，遗传算法 的交叉算子的作用效率大为下降。因为在这两种情况下，常规交叉算子作用于表示可行解的 两个个体时，产生的新个体很可能不再表示可行解，此时必须使用特殊的交叉算子，如PMX 、 OX 、CX[5]等,而这些特殊的交叉算子遗传操作复杂,有哪些信誉好的足球投注网站效率不高。文献[6]针对传统遗传算 法的上述不足,提出了一种不使用交叉算子的新颖遗传算法——单亲遗传算法。单亲遗传算 法与传统遗传算法的区别主要在产生新个体的方法上，传统遗传算法模拟自然界大多数生物 的双亲繁殖方式，遗传操作主要在两个个体上进行；而单亲遗传算法模拟自然界少数生物的 [7] 单亲繁殖方式，遗传操作只在一个个体上进行 。 与传统遗传算法一样，单亲遗传算法群体规模N 的选择对计算效率有着很大的影响。 如果N 太小,每遗传迭代一次处理的图式数量太少,容易导致算法收敛于局部最优解；反之， 如果N 太大，每遗传迭代一次的适应度计算时间大幅度增加,计算效率低下。本文通过分析 单亲遗传算法在每一次遗传操作时处理的有效图式的数量，定义一个适当的目标函数，对单 亲遗传算法的最优群体规模进行研究。 2 单亲遗传算法群体中的有效图式 在由事物序号组成的长度为l 的字符串中，共有g j P j 种j 阶图式，且有Cj 种选择j c l l [6] 个位置的方式，其中g c 为同序基因数 ，且 P j l(l −1)(l −2) L(l −j +1) ， l （1） l l − l − l − Ll −j + Cj ( 1)( 1)( 2) ( 1) 。 l j (j −1)(j −2) L3 ×2 ×1