模拟退火遗传算法
第24卷 第3期 湖 南 城 市 学 院 学 报 (自然科学) Vol.24 No.3 2003年5月 JOURNAL OF HUNAN CITY UNIVERSITY (Natural Science) May 2003
模拟退火遗传算法的性能评价
李红军
(西南科技大学,四川 绵阳 621002)
摘 要:遗传算法和模拟退火算法的结合对遗传算法的性能有很大的改进.将遗传算法与模拟退火算法相结合,提出了模拟退火遗传算法.研究结果表明,该算法能较好地克服传统遗传算法存在的不足,并在进化速度和全局寻优能力方面有较大的突破.
关键词:遗传算法;模拟退火算法;模拟退火遗传算法
中图分类号:TP301.6 文献标识码:A 文章编号:1672–1942(2003)03–0111–03
虽然理论上已经证明,遗传算法能从概率意义上以随机的方式寻求到最优解,但大量的应用实践表明,在遗传算法的应用中也会出现一些问题.这些问题中最主要的是它容易产生早熟现象、局部寻优能力较差等.并且对许多问题而言,基本遗传算法往往不是解决这些问题的最有效的方法;另一方面,遗传算法的局部搜索能力较差,但把握搜索过程的能力较强;而模拟退火算法具有较强的局部搜索能力,并能使搜索过程避免陷入局部最优解,但模拟退火算法把握搜索过程的能力不强,从而使得模拟退火算法的运行效率不高.如果在遗传算法的搜索过程中融合退火算法的思想,构成模拟退火遗传算法,将是提高遗传算法运行效率和求解质量的有效手段.
Crossover[P(t)];个体变异操作:P(t)←Mutation[P(t)];个体模拟退火操作:P4(t)←Simulated Annealing [P3(t)];评价群体P4 (t)的适应度;下一轮遗传过程:P(t+1)←Reproduction [P(t)∪P4(t)].终止条件判断.若不满足终止条件,则t←t+1,转到第四步继续遗传进化过程,否则,输出当前最优个体,算法结束.
21
3
2 模拟退火遗传算法的设计事例
为评价本论文提出的模拟退火遗传算法的性能,考虑如下函数的全局最大值计算.
Rosenbrock函数f (x1,x2)=100(x12-x2)+ (1-x1) s.t. -2.048≤xi≤2.048(i=1,2)
该函数有2个局部极大点,分别是 f (2.048,-2.048)=3 897.734 2和f(-2.048,-2.048)= 3 905.926 2,其中后者为全局最大点.解决该问题的构造步骤如下:
(1)确定决策变量和约束条件,即前面所提到的-2.048≤xi≤2.048(i=1,2).
(2)依据所给的数学模型确定编码方法.用长度为10位的二进制编码串来分别表示两个决策变量x1,x2.将x1,x2的定义域离散化为1 023个均等的区域,包括两个端点在内共1 024个不同的离散点.从离散点-2.048到离散点2.048,依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码,再将分别表示x1,x2两个10位长的二进制编码串连接起来,组成一个20位的二进制编码串,就构成了此函数优化问题的染色体编码.
(3)确定解码方法.解码时需要先将20位长的二进制编码串切断为两个10位长的二进制编码串,分别记为y1,y2.将代码yi转化成所对应的变量xi的解码公式为:xi=4.096*yi/1 023-2.048(i=1,2).
(4)确定个体适应度评价方法.个体的适应度取
2
2
1 模拟退火遗传算法的思想及设计
1.1 模拟退火遗传算法的思想
本文提出的模拟退火遗传算法,是以遗传算法运算流程为主体流程,把模拟退火机制融入其中,用以进一步调整优化群体.整个算法的执行过程由两部分组成:首先通过遗传算法部分的进化操作(侧重全局搜索)产生出较优良的一个群体,再利用模拟退火算法部分的退火操作(侧重局部搜索)来进行进一步基因个体的优化调整.其中模拟退火操作设计是针对一定规模的群体中的每个基因个体的,对每个基因个体实施一定演变而产生恶化解的设计引用了遗传算法中的变异和倒位的思想.这种算法思想策略,从对全局最优解的搜索角度和算法的进化速度上来提高模拟退火遗传算法的性能.运行过程反复迭代,直到满足某个终止条件为止. 1.2 模拟退火遗传算法算法设计
进化代数计数器初始化:t←0;随机产生初始群体P(t);评价群体P(t)的适应度;群体复制操作:P(t)←Selection[P(t)];个体交叉操作:P(t)←
1
2
收稿日期:2003-03-04
基金项目:西南科技大学青年预研基金资助项目(05ZK023080) 作者简介:李红军(1977-),男,助教,硕士,主要从事计算机算法研究.
我要评价 贡献者等级:融会贯通 五级 格式: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 算法不仅比传统的算法效率有很大的提高...
热门文档