基于编码转换的离散演化算法设计与应用
作者:
作者单位:

作者简介:

贺毅朝(1969-),男,河北晋州人,教授,CCF高级会员,主要研究领域为演化计算,组合优化算法,近似算法,群测试理论;王熙照(1963-),男,博士,教授,博士生导师,主要研究领域为机器学习,进化计算,大数据分析;赵书良(1967-),男,博士,教授,博士生导师,CCF专业会员,主要研究领域为数据挖掘,大数据处理;张新禄(1968-),男,副教授,主要研究领域为智能计算,图论与组合优化,群测试理论.

通讯作者:

贺毅朝,E-mail:heyichao119@163.com

中图分类号:

基金项目:

国家自然科学基金(61503252,71371063,11471097);深圳知识创新项目基础研究项目(JCYJ20150324140036825);河北省高等学校科学研究计划(ZD2016005);河北省自然科学基金(F2016403055)


Design and Applications of Discrete Evolutionary Algorithm Based on Encoding Transformation
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61503252, 71371063, 11471097); Shenzhen Science and Technology Project (JCYJ20150324140036825); Scientific Research Plan of the Higher Education Institutions of Hebei Province, China (ZD2016005); Natural Science Foundation of Hebei Province of China (F2016403055)

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

    为了求解离散域上的组合优化问题,借鉴遗传算法(GA)、二进制粒子群优化(BPSO)和二进制差分演化(HBDE)中的映射方法,给出了一种基于映射变换思想设计离散演化算法(DisEA)的实用方法——编码转换法(ETM).为了说明ETM的实用性与有效性,首先,基于ETM给出了一个离散粒子群优化算法(DisPSO);然后,分别利用BPSO,HBDE和DisPSO等基于ETM构造的演化算法求解集合联盟背包问题和折扣{0-1}背包问题.通过与GA的计算结果比较指出,BPSO,HBDE和DisPSO的求解性能均优于GA,说明基于ETM提出的DisEA在求解背包问题方面具有良好的性能.由此表明,利用ETM方法设计DisEA是一种实用的有效方法.

    Abstract:

    In order to solve a combinatorial optimization problem in discrete domains by using evolutionary algorithms, this study draws lessons from the design concept of genetic algorithm (GA), binary particle swarm optimization (BPSO) and binary differential evolution with hybrid encoding (HBDE), to propose a simple and practical method for designing discrete evolution algorithm (DisEA) based on the idea of mapping transformation. This method is named encoding transformation method (ETM). For illustrating the practicability of ETM, a discrete particle swarm optimization (DisPSO) algorithm based on ETM is presented. For showing the feasibility and effectiveness of ETM, GA, BPSO, HBDE and DisPSO are used to solve the set union knapsack problem (SUKP) and the discounted {0-1} knapsack problem (D{0-1}KP), respectively. The results show that for SUKP and D{0-1}KP, the discrete evolutionary algorithms based on ETM, i.e. BPSO, HBDE and DisPSO have better performance than GA. This indicates that the design of DisEA based on ETM is not only a feasible method, but also a very practical and efficient method.

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

贺毅朝,王熙照,赵书良,张新禄.基于编码转换的离散演化算法设计与应用.软件学报,2018,29(9):2580-2594

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

京公网安备 11040202500063号