主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
王熙照,贺毅朝.求解背包问题的演化算法.软件学报,2017,28(1):1-16
求解背包问题的演化算法
Evolutionary Algorithms for Knapsack Problems
投稿时间:2016-09-22  修订日期:2016-10-24
DOI:10.13328/j.cnki.jos.005139
中文关键词:  背包问题  数学模型  演化算法  个体编码  不可行解
英文关键词:knapsack problem  mathematical model  evolutionary algorithm  individual coding  infeasible solution
基金项目:国家自然科学基金(71371063);深圳市知识创新计划基础研究项目(JCYJ20150324140036825);河北省自然科学基金(F2016403055);河北省高等学校科学研究计划(ZD2016005)
作者单位E-mail
王熙照 深圳大学 计算机与软件学院, 广东 深圳 518060 xizhaowang@ieee.org 
贺毅朝 河北地质大学 信息工程学院, 河北 石家庄 050031  
摘要点击次数: 7201
全文下载次数: 2837
中文摘要:
      背包问题(knapsack problem,简称KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.对近10余年来利用EAs求解KP的研究情况进行了较为详细的总结,一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面,为今后进一步利用最新提出的EAs求解KP问题提供了一条可借鉴的思路.
英文摘要:
      Knapsack problem (KP) is a well-known combinatorial optimization problem which includes 0-1 KP, bounded KP, multi-constraint KP, multiple KP, multiple-choice KP, quadratic KP, dynamic knapsack KP, discounted KP and other types of KPs. KP can be considered as a mathematical model extracted from variety of real fields and therefore has wide applications. Evolutionary algorithms (EAs) are universally considered as an efficient tool to solve KP approximately and quickly. This paper presents a survey on solving KP by EAs over the past ten years. It not only discusses various KP encoding mechanism and the individual infeasible solution processing but also provides useful guidelines for designing new EAs to solve KPs.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利