你的位置:论文发表 >> 论文下载 >> 理学论文 >> 机械制造 >> 详细内容 在线投稿

基于改进算子的遗传算法

浏览223次 时间:2014年3月14日 13:17

孙秀娟 潍坊科技学院 山东寿光 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.

[ 2 ] K I V I J A R Y I J , F R A N T I P ,NEVALAINEN O. Self-adaptive geneticalgorithm for clustering[J].Journal ofHeuristics,2003,9(2):113-129.
上一篇 下一篇

论文发表与咨询

论文发表 写作指导 职称论文 毕业论文 客服联系方式:
投稿信箱:lunww@126.com
在线咨询客服QQ:站点合作85782530
在线咨询客服QQ:站点合作82534308
联系电话:18262951856
点击进入支付宝支付(支付宝认可网络诚信商家)
点击进入财付通支付(财付通认可网络诚信商家)
点击进入支付方式---->>>>

论文发表 诚信说明

论文发表 论文投稿 热点图片