首页 | 本学科首页   官方微博 | 高级检索  
     

热力学遗传算法计算效率的改进
引用本文:应伟勤,李元香,SHEU Phillip C-Y.热力学遗传算法计算效率的改进[J].软件学报,2008,19(7):1613-1622.
作者姓名:应伟勤  李元香  SHEU Phillip C-Y
作者单位:武汉大学,软件工程国家重点实验室,湖北,武汉,430072;Department of Electrical Engineering and Computer Science, University of California, Irvine, CA 92697, USA
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60473014, 60773009 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z290 (国家高技术研究发展计划(863)); the China Scholarship Council under Grant No.2007101731 (国家留学基金); the Natural Science Foundation of Hubei Province of China under Grant No.2007ABA009 (湖北省自然科学基金)
摘    要:热力学遗传算法(thermodynamical genetic algorithms,简称TDGA)借鉴固体退火过程中能量与熵的竞争模式来协调GA中"选择压力"和"种群多样性"之间的冲突.然而TDGA目前极高的计算代价限制了其应用.为了提高TDGA的计算效率,首先定义一种等级熵(rating-based entropy,简称RE)度量方法,它能以较小的计算成本度量种群中个体适应值的分散程度.然后引入分量热力学替换规则(component thermodynamical replacement,简称CTR),有效地降低了替换规则的复杂度.同时也证明了CTR规则具有驱动种群自由能近似最速下降的能力.在0-1背包问题上的实验结果表明,RE方法和CTR规则在保持TDGA良好的性能与稳定性的同时,极大地提高了其计算效率.

关 键 词:遗传算法  热力学  计算效率  多样性度量  替换规则
收稿时间:2007/12/18 0:00:00
修稿时间:2008/3/14 0:00:00

Improving the Computational Efficiency of Thermodynamical Genetic Algorithms
YING Wei-Qin,LI Yuan-Xiang and SHEU Phillip C-Y.Improving the Computational Efficiency of Thermodynamical Genetic Algorithms[J].Journal of Software,2008,19(7):1613-1622.
Authors:YING Wei-Qin  LI Yuan-Xiang and SHEU Phillip C-Y
Abstract:Thermodynamical genetic algorithms(TDGA)simulate the competitive model between energy and entropy in annealing to harmonize the conflicts between selective pressure and population diversity in GA,But high computational cost restricts the applications of TDGA.In order to improve the computational efficiency,a measurement method of rating-based entropy(RE)is proposed.The RE method can measure the fitness dispersal with low computational cost.Then a component thermodynamical replacement(CTR)rule is introduced to reduce the complexity of the replacement,and it is proved that the CTR rule has the approximate steepest descent ability of the population free energy.Experimental results on 0-1 knapsack problems show that the RE method and the CTR rule not only maintain the excellent performance and stability of TDGA,but also remarkably improve the computational efficiency of TDGA.
Keywords:genetic algorithm  thermodynamics  computational efficiency  diversity measurement  replacement rule
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号