模拟退火遗传算法
112
湖 南 城 市 学 院 学 报(自然科学) 2003年第3期
为对应的目标函数值,并且不再对它作其它变换处理,即F(X)= f (x1,x2).
(5)设计遗传算子.选择运算使用比例选择算子;交叉运算使用单点交叉算子;变异运算使用均匀变异算子.
(6)确定遗传算法运行参数.具体到本论文的程序设计,所选的参数如下:群体大小M=80;终止代数T=180;交叉概率Pc=0.6;变异概率Pm=0.001.
(7)确定模拟退火算法的运行参数.笔者对模拟退火算法运行参数的确定是在以基本理论依据为前提的条件下,通过实验的方式来确定的,即按有利于提高整个算法的进化速度的方向.经过多次尝试,以此来决定模拟退火算法运行所需的各个参数值.
1)对控制参数初值To的选取基于“Tk只要选的充分的大,就会立即达到准平衡”的论证.实际上,为使算法进程一开始就达到准平衡,应让初始接受率r接近于1,由Metropolis准则exp(-△f/To)≈1,可推知To值很大.通过实验选取的经验法则是:要求算法进程在合理的时间里搜索尽可能大的解空间,只有足够大的To才能满足这个要求.笔者选To= 9 000.0.
2)控制参数终值Tf的选取:由于算法收敛于最优解集是随控制参数T值的缓慢减小逐渐地进行的,只有在控制参数终值Tf充分小时,才有可能得出高质量最终解.在本论文中,是每进行一轮后,用T(t)=k*T(t-1),k为一略小于1的系数,来实现T的缓慢减小过程,用循环参数t来控制算法的停止.本论文中,k=0.95,t<200.
3)程序中对群体中的个体,执行个体演变操作的思想之一是基于遗传算法的“变异”操作思想.这里的变异是对个体中的随机基因座及其之前的基因座进行置反操作过程.还有一步操作则是把个体基因串按较小的概率p(p<0.01)进行前后等长倒位操作.这里的演变操作对维持群体中个体的多样性,防止算法陷入局部最优同样有着不可忽略的贡献.
(8)实验结果:为了全面地评价模拟退火遗传算法的性能,本文设计了4个算法程序:不带保留策略基本遗传算法程序(GA_b.c)、带保留策略基本遗传算法程序(GA.c)、不带保留策略模拟退火遗传算法程序(GASA_b.c)、带保留策略模拟退火遗传算法程序(GASA.c).每一个程序数据的采集采用算法程序连续运行25次(为一组),记录搜索到最优解所需的进化代数,在到终止代数(180代)还不能搜索到最优解的以180计.对4个被测算法程序随机进行7组采样.先对实验的采集数据每组分别求进化代数平均值,然后再把前后实验所得的7组数据总体求平均值,再连同所有单个数据一起作为算法评价的依据.分析的角度是:算法在所测过程中陷入局部最
优解的次数和进化平均代数.
表1无最优解率是指在规定的进化代数(180)内没有搜索到全局最优解的比例,即算法在所测过程中陷入局部最优解的次数同算法运行总次数之比.
表1 实验结果表
平均进化代数 总体无最优解率
GA_b 148 77%
GA 99 46%
GASA_b 55 6%
GASA 21 0%
2.1 实验数据分析
首先指出,对于不使用保留最佳解策略的基本遗传算法GA_b实际上在很多时候会出现早熟收敛,陷于次优解后难于再搜索到最优解的情况,既不收敛现象.
另外,在算法GASA_b的实验记录数据中也出现了180的统计.需要指出的是,虽然到第180代也没有搜索到最优解,但该算法并非就是一定收敛于次优解中了,通过增加基因群体的遗传变异代数(比如T=200)再进行实验,统计数据表明,该算法不能收敛到最优解的现象明显减少.即使是陷入了次优解中,也会在算法运行中出现从次优解中“跳变”出来的情况,而这种“跳变”,在算法GA_b的运行过程中几乎不会出现,即使是在使用了保留最佳解策略的基本遗传算法程序GA的运行过程中也是非常少见的.
从以上表1中可以明显看出,两个引入模拟退火机制的遗传算法较之基本遗传算法不仅在进化速度上有非常大的提高,而且在局部搜索能力方面也有非常明显的改进.模拟退火遗传算法还在从当前局部最优状态向其它未被搜索空间转移的能力上有了较大的实质性突破.
2.2 算法运行过程的图象分析
以上的算法运行过程图象是从大量的实验采集中抽取的较为典型的样本,它们基本能反应各个算法的运行特征.分析结果如下:过程图中,最为明显的是基本遗传算法GA运行过程的曲线较为平滑(见图2),基因群体对应的目标函数平均值越来越向最优(次优)基因个体对应的目标函数值靠拢,甚至重合.这说明基本遗u传算法在执行过程中维持群体的多样性方面存在着较大的缺陷,并且体现出在程序执行的后期,基本遗传算法对最优解的搜索效率极其低下.所以从实验图1和图2的结果来看,它们均未搜索到最优解也就不足为怪了.图1尚未搜索到次优解,正如前面所述,大量的实验表明,不使用保留最佳解策略的基本遗传算法比较难于收敛到最优解,甚至出现不收敛的情况.而图2过早地就收敛于了次优解的“陷阱”中.联系统计表和运行过程图,大量实验表明这种现象出现的几率不低于45%.这说明即使使用了保留最佳解策略,基本遗
我要评价 贡献者等级:融会贯通 五级 格式:pdf 关键词:遗传算法模拟退火算法TSP...的性能分析汪松泉1 ,程家兴2 ( 1. 安徽大学 计算机科学与技术学院 ,安徽 ...
暂无评价0人阅读0次下载举报文档 模拟退火与遗传算法。在工程实践中,经常会...初始群体也应该选取适当,如果选取的-过小则杂交优势不明显,算法性能很差(数量上...
暂无评价0人阅读0次下载举报文档 遗传模拟退火算法_工学_高等教育_教育专区...不但增强了算法的全局收敛性,并且使算法在优化 后期有较强的爬山性能,加快了...
遗传算法和模拟退火算法求解TSP的性能分析 隐藏>> 第9卷200 9 月 第 年1 11...评价 函数 ea(i:vlV) 用来对 种群 中的每个 染 色体 设定一个概率 , 以...
暂无评价0人阅读0次下载举报文档 遗传模拟退火算法及其应用_环境科学/食品科学...得到F 2 x 的结果 与此同时,我们多次独立地运行每个算法和测试其平均求性能。...
2003 引入模拟退火机制的新型遗传算法张 晖* 吴 斌 余张国 (西南科技大学...2 实验方法为评价新型遗传算法的性能,考虑Rosenbrock函数的全局最大值计算问题 f...
0.0分 (0人评价)暂无用户评价 我要评价相关...构建相应的朴素贝叶斯分类器,采用模拟退火遗传算法进行...与传统的朴素贝叶斯方法相比,该方法具有更好的性能。...
基于模拟退火遗传算法的模糊PID控制规则优化_机械/仪表_工程科技_专业资料 暂无评价
暂无评价0人阅读0次下载举报文档 基于模拟退火遗传算法的贝叶斯分类_自然科学...但如果将遗传算法和模拟退火算法相结合,互相取 长补短,则有可能开发出性能优良...
暂无评价 4页 2.00 遗传与模拟退火算法 8页 1下载券 一种混合遗传模拟退火...对算法的性能和求解精度进行了 测试.GSA 算法不仅比传统的算法效率有很大的提高...
热门文档