互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

基于混合编码的差异演化算法解0-1背包问题


  摘 要:针对典型的一类NP完全问题——背包问题,提出一种混合编码的差异演化求解方法。该方法基于差异演化算法框架,采用混合编码机制,每个决策变量均由一个实数和一个二进制数的组合表示。利用新定义的映射算子,构建混合编码的种群;增加边界约束处理算子,确保变异算子计算结果满足边界约束条件;利用新定义的丢弃算子对于不可行的装包策略进行修正。通过数值仿真实验,将该方法与遗传算法、二进制差异算法的计算结果比较分析,表明该算法求解背包问题的有效性与适用性。

  关键词:0-1背包问题; 混合编码; 差异演化算法; 丢弃算子

  中图分类号:TP18文献标志码:A

  文章编号:1001-3695(2010)06-2031-03

  doi:10.3969/j.issn.1001-3695.2010.06.009

  Mixed-coding-based differential evolution algorithm for 0-1 knapsack problem

  DENG Chang-shou1,2, ZHAO Bing-yan1, LIANG Chang-yong2

  (1. School of Information Science & Technology, Jiujiang University, Jiujiang Jiangxi 332005, China; 2. Institute of Computer Network System, Hefei University of Technology, Hefei 230009, China)

  Abstract:This paper proposed mixed-coding-based differential evolution algorithm for 0-1 knapsack problem which was NP complete. This algorithm was based on the original differential evolution using mix-coding mechanism in which each decision variable was represented by the combination of one float number and a binary number. Firstly, proposed a new mapping operator to construct mixed-coding population, and then defined a new operator which dealt with the boundary constraint. Lastly used a discarding operator to adapt the infeasible solution. Simulation numerical results compared with that of genetic algorithm and binary differential evolution show that this algorithm is efficient and practical for 0-1 knapsack problem.

......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017