基于编码转换的离散演化算法设计与应用

来源：软件学报杂志2018年第9期北京时间：

作者：贺毅朝,王熙照,赵书良,张新禄

单位：贺毅朝，河北地质大学 信息工程学院, 河北 石家庄 05003111,王熙照，深圳大学 计算机与软件学院, 广东 深圳 51806002,赵书良，河北师范大学 数学与信息科学学院, 河北 石家庄 05002403,张新禄，河北师范大学 数学与信息科学学院, 河北 石家庄 05002404

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

关键词：离散演化算法;编码转换;SUKP问题;D{0-1}KP问题

基金资助：国家自然科学基金（61503252，71371063，11471097）；深圳知识创新项目基础研究项目（JCYJ20150324140036825）；河北省高等学校科学研究计划（ZD2016005）；河北省自然科学基金（F2016403055）