遗传算法小生境技术
计 算 机 工 程 第 34 卷 第11期
Vol.34 No.11 Computer Engineering · · 人工智能及识别技术
文章编号:1000—3428(2008)11—0186—03
文献标识码:A
2008年6月
June 2008
中图分类号:TP18
基于梯度优化的自适应小生境遗传算法
席红雷,行小帅,张清泉
(山西师范大学物理与信息工程学院,临汾 041004)
摘 要:针对基本遗传算法全局搜索能力差和收敛速度慢,且在求解多峰函数时仅能得到部分最优解的缺点,提出一种基于梯度优化的自适应小生境算法。该算法利用当前种群适应度和种群代数来设计交叉算子和变异算子,有效地保持了种群的多样性,改善全局搜索能力,加快了收敛速度,应用改进的梯度优化算子保证进化向最优解方向靠近,提高了计算峰值的精确度。对Shubert函数的仿真试验证明,该算法能改善全局搜索能力,加快算法收敛速度并提高计算精度。 关键词:小生境遗传算法;自适应;梯度优化;非均匀变异算子
Adaptive Niche Genetic Algorithm Based on Gradi-optimization
XI Hong-lei, XING Xiao-shuai, ZHANG Qing-quan
(College of Physics and Information Engineering, Shanxi Normal University, Linfen 041004)
【Abstract】To deal with low efficiency and low convergence speed in searching the global optimum, and only gaining several the optimum while itis used in multimodal-function-optimization, an adaptive Niche Genetic Algorithm(NGA) based on gradi-optimization is proposed in this paper. Theadaptive crossover operator and mutation operator are used to guarantee the population diversity, improve searching the global optimum andconvergence speed. The gradi-optimization is used to improve the precision of the optimum. Simulation results in the Shubert show that this methodis nice at improving on searching the global optimum, convergence speed and its superiority in precision.【Key words】Niche Genetic Algorithm(NGA); adaptive; gradi-optimization; non-uniform mutation eperator
1 概述
遗传算法(Genetic Algorithm, GA)[1]是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,它已经广泛应用于函数优化、任务调度、神经网络、机器学习等各个领域。基本遗传算法的全局搜索能力差,对于实际中需要求解多个峰值点问题,只能收敛于某个或部分峰值点[2],很难得到满意的结果。而小生境遗传算法(Niche Genetic Algorithm, NGA)[3]的引入很好地解决了有关多峰值的求解问题。
目前,对小生境遗传算法的改进都是在群体的多样性和
但这些改进方算法参数的确定等方面来提高算法的性能[4-5],
法都是单方面考虑算法的全局搜索能力、局部优化能力和收敛速度。提高算法的搜索能力就会使算法的收敛速度减慢,而收敛速度快又会出现早期收敛现象。对此,本文提出了一种基于梯度优化的自适应小生境遗传算法(GANGA)。
生境遗传算法。从各方面改善了算法的性能,有效地提高了算法的可行性。
3 GANGA的基本原理
3.1 编码及初始群体的生成
编码方法是算法的首要任务,既影响交叉算子、变异算子的设计方法,又与算法的收敛速度有很大关系。基于实数编码的遗传算法是对连续参数优化问题的实际描述,不存在二进制的编码和解码过程,能大大提高算法的效率。
为了能使初始种群均匀分布在整个解空间,本文采用小区间生成法,先把整个解空间划分为N个小区间,在每一个小区间内随机产生M个个体,这样就生成一个N×M大小的种群,该方法产生的初始种群均匀地分布在整个解空间,各个个体间有明显的差距,使每个个体都有较大概率参与算法。 3.2 交叉算子与变异算子
首先,为了提高算法的全局搜索能力,本文采用算术交叉算子。通过进化代数来控制交叉量,交叉后,一点落于进行交叉的父代之间,另一点落于靠近较好父代的一侧,使解向较好的方向发展,而自适应交叉量随进化代数的增大而减小,在算法中随机选取2个交叉个体,先比较2个个体Xi和Xj的适应度F(Xi)和F(Xj),假设F(Xi)>F(Xj),xik和xjk为交叉点,交叉结果为
基金项目:山西省青年科技研究基金资助项目(20031008)
作者简介:席红雷(1980-),男,硕士研究生,主研方向:人工神经网络,智能信息处理;行小帅,教授;张清泉,副教授、硕士收稿日期:2008-02-14 E-mail:xihonglei351@126.com
2 小生境遗传算法
在遗传算法中引入小生境的概念,产生了模拟生物小生境的遗传算法。该算法的基本目的是形成并维持稳定的多样化子种群,在搜索空间并行地进行搜索,常用于求解多峰函数、多目标优化和复杂系统的仿真。
本文采用基于排挤机制的小生境遗传算法,基本思想是:计算个体之间的海明距离,如果小于事先设定参数L,则对适应度低的个体处以罚函数,降低其适应度,保护种群的多样性,避免大量重复的解充斥整个解空间。基本的小生境遗传算法收敛速度慢、局部寻优能力差,并且容易出现进化停止现象。因此,在引入自适应交叉算子和变异算子,并与梯度算子相结合后,形成本文提出的基于梯度优化的自适应小 ——186
· 基于梯度优化的自适应小生境遗传算法席红雷,行小帅,张清泉 (山西师范大学物理与信息工程学院,临汾 041004) 摘要:针对基本遗传算法全局搜索能力差和收敛速度慢,且...
基于个体优化的自适应小生境遗传算法_专业资料。针对遗传算法在处理复杂多峰函数... 基于梯度优化的自适应小... 2人阅读 3页 2.00 基于自适应小生境遗传...
在自适应小生境的基础上,利用进化过程中相邻个体的信息产生的试探点标记的算法...基于梯度优化的自适应小生境遗传算 法[J]. 计算机工程, 2008, 34(11): 186...
基于小生境的自适应遗传算法_法学_高等教育_教育...环境中的遗传和进化过程而形成的一种全局优化概率...由于其不依赖于梯度信息或其它辅助知识,而只需要影响...
基于自适应小生境遗传算法的物流配送路径优化研究_专业资料。针对遗传算法具有早熟的缺点和小生境遗传算法比遗传算法更费时的问题,将自适应小生境技术引入遗传算法,...
F eb 2009 面向多模态函数优化的自适应小生境遗传算法陆 青 梁昌勇 杨善林 张俊岭 230009) * (合肥工 业大学 计算机网络系统研究所 合肥 摘 要 为了解决小生...
进化优化小生境遗传算法控... 1人阅读 3页 2.00元 基于小生境遗传算法的...利用进化梯度信息调整个体向更优解进化,并根据进化代数自适应调整实数编码个体的...
( 1982 -),女, 讲师, 硕士. 研究方向: 计算数学与最优化问题. 第5 期 薛凌霄等: 基于共轭梯度法的小生境混合遗传算法 · 557· s( x i , xj ) = ...
基于自适应小生境遗传算法的混合交通网络设计双层规划模型 在现有的交通网络设计...投资额以及CO的排放总量三方面因素,建立起以三者之和最小为目标的优化函数;下层...
提出了一种改进的小生境遗传算法Ζ 该算法基于自适应交叉概率算子和变异算子, ... 并在变异量的确定上引入了梯度的概念Ζ 通过在 Shubert 函数的全局最优化问题...
热门文档