热力学遗传算法计算效率的改进
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

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 (湖北省自然科学基金)


Improving the Computational Efficiency of Thermodynamical Genetic Algorithms
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    热力学遗传算法(thermodynamical genetic algorithms,简称TDGA)借鉴固体退火过程中能量与熵的竞争模式来协调GA中"选择压力"和"种群多样性"之间的冲突.然而TDGA目前极高的计算代价限制了其应用.为了提高TDGA的计算效率,首先定义一种等级熵(rating-based entropy,简称RE)度量方法,它能以较小的计算成本度量种群中个体适应值的分散程度.然后引入分量热力学替换规则(component thermodynamical replacement,简称CTR),有效地降低了替换规则的复杂度.同时也证明了CTR规则具有驱动种群自由能近似最速下降的能力.在0-1背包问题上的实验结果表明,RE方法和CTR规则在保持TDGA良好的性能与稳定性的同时,极大地提高了其计算效率.

    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.

    参考文献
    相似文献
    引证文献
引用本文

应伟勤,李元香,SHEU Phillip C-Y.热力学遗传算法计算效率的改进.软件学报,2008,19(7):1613-1622

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2007-12-18
  • 最后修改日期:2008-03-14
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号