基于改进算子的遗传算法

《基于改进算子的遗传算法 》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于改进算子的遗传算法孙秀娟潍坊科技学院山东寿光262700【文章】为提高算法收敛速度，本文提出一种改进算法来解决遗传算法存在的问题。在选择运算中引入一种抗早熟机制，防止算法陷入局部最优解；在交叉运算中，通过动态调整交叉算子保证父代的优良模式遗传到下一代，加快算法的收敛速度。实验证明，两种改进算子的有效结合保证算法能以较快速度收敛于全局最优解。【关键词】遗传算法；交叉算子：TP301.6：A0引言遗传算法是一种全局随机搜索算法，它有三种基本遗传算子：选择算子、交叉算子和变异算子，这些参数将直接影响算法的性能和收敛速度。基本遗传算法存在收敛速度慢、运行时间长、过早陷入局部最

2、优解等问题。本文针对传统遗传算法存在的问题，提出一种改进算法。在选择运算中引入一种抗早熟机制来防止算法陷入局部最优解；在交叉运算中引入一种自识别交叉算子以加快算法收敛速度，减少运行时间。1改进的遗传算法1.1选择操作选择运算是根据个体的适应度，按照一定的规则，从第t代群体中选择一些优良个体保留到下一代群体中。本文引入一种抗早熟机制，即个体被选中的概率与适应度大小存在一种函数关系。个体被中的概率与适应度的关系如下：（1）（2）其中，为常数，。式（1）的概率需经过归一化后再进行轮盘赌选择。用式（2）进行归一化，m为群体规模。当个体的适应度值大于1时，根据式（1），概率大于个体

3、的适应度，当参数越小，这种关系越明显。该方法可有效地预防算法提早陷于局部最优解。1.2交叉算子交叉算子对遗传算法的收敛速度有着重要影响。根据两个个体的相似性，遗传算法采用固定的交叉率对两个个体进行交叉操作，导致父个体中的优良模式不能被遗传到下一代，进而降低了算法收敛速度。为提高父个体的优良模式遗传到下一代机率，本文提出一种自识别交叉算子，该算子根据个体间的相似度大小确定是否进行交叉操作。定义两个串A和B的相似度如下：（3）其中l是A和B的最长公共子串的长度，n为染色体串长度。下面定义一阈值p:其中大Z为进化代数，小z为当前进化代数。只有当两个个体相似度小s小于大S时，两个

4、个体才可以进行单点交叉。2实验为了评估新算法的性能，使用1个Benchmark函数进行测试：本文分别采用传统遗传算法和改进算法对上述函数进行测试，种群规模取200，独立运行50次，并记录函数的最优平均值和标准差。将本文算法运行的结果和传统的遗传算法进行比较，结果如表1示。由表1以看出，对于测试函数f1，本文算法得到的标准差虽然大于传统算法，即本文算法得到的最优解的波动性比传统算法大，说明本文算法的收敛速度和搜索精度明显优于传统算法。测试函数f1存在多个局部极值点，搜索过程易陷入局部最优。因此，本文算法具有较强的多峰搜索能力。3结论本文提出一种改进遗传算法，该算法在加快算法

5、收敛速度的同时，防止算法陷入局部最优解。【