基于改进算子的遗传算法

孙秀娟 潍坊科技学院 山东寿光 262700

【文章摘要】

为提高算法收敛速度，本文提出一种改进算法来解决遗传算法存在的问题。在选择运算中引入一种抗早熟机制，防止算法陷入局部最优解；在交叉运算中，通过动态调整交叉算子保证父代的优良模式遗传到下一代，加快算法的收敛速度。实验证明，两种改进算子的有效结合保证算法能以较快速度收敛于全局最优解。【关键词】

遗传算法；交叉算子

中图分类号：TP301.6 文献标识码：A

0 引言

遗传算法是一种全局随机搜索算法，它有三种基本遗传算子：选择算子、交叉算子和变异算子，这些参数将直接影响算法的性能和收敛速度。基本遗传算法存在收敛速度慢、运行时间长、过早陷入局部最优解等问题。

本文针对传统遗传算法存在的问题，提出一种改进算法。在选择运算中引入一种抗早熟机制来防止算法陷入局部最优解；在交叉运算中引入一种自识别交叉算子以加快算法收敛速度，减少运行时间。

1 改进的遗传算法

1.1 选择操作

选择运算是根据个体的适应度，按照一定的规则，从第t 代群体中选择一些优良个体保留到下一代群体中。本文引入一种抗早熟机制，即个体被选中的概率与适应度大小存在一种函数关系。个体被中的概率与适应度的关系如下：

（ 1）

（ 2）

其中， 为常数， 。式（1）的概率需经过归一化后再进行轮盘赌选择。用式（2）进行归一化，m 为群体规模。当个体的适应度值大于1 时，根据式（1），概率大于个体的适应度，当参数越小，这种关系越明显。该方法可有效地预防算法提早陷于局部最优解。

1.2 交叉算子交叉算子对遗传算法的收敛速度有着重要影响。根据两个个体的相似性，遗传算法采用固定的交叉率对两个个体进行交叉操作，导致父个体中的优良模式不能被遗传到下一代，进而降低了算法收敛速度。

为提高父个体的优良模式遗传到下一代机率，本文提出一种自识别交叉算子，该算子根据个体间的相似度大小确定是否进行交叉操作。定义两个串A 和B 的相似度如下：

（ 3）

其中l 是A 和B 的最长公共子串的长度，n 为染色体串长度。下面定义一阈值p:其中大Z 为进化代数，小z 为当前进化代数。只有当两个个体相似度小s 小于大S 时，两个个体才可以进行单点交叉。

2 实验

为了评估新算法的性能，使用1 个Benchmark 函数进行测试：本文分别采用传统遗传算法和改进算法对上述函数进行测试，种群规模取200，独立运行50 次，并记录函数的最优平均值和标准差。将本文算法运行的结果和传统的遗传算法进行比较，结果如表1示。

由表1 以看出，对于测试函数f1，本文算法得到的标准差虽然大于传统算法，即本文算法得到的最优解的波动性比传统算法大，说明本文算法的收敛速度和搜索精度明显优于传统算法。测试函数f1 存在多个局部极值点，搜索过程易陷入局部最优。因此，本文算法具有较强的多峰搜索能力。

3 结论

本文提出一种改进遗传算法，该算法在加快算法收敛速度的同时，防止算法陷入局部最优解。

【参考文献】

[1]J H Holland. Adaptation in natural andartificial systems[M]. Ann Arbor: TheUniversity of Michigan Press, 1975.