求解随机时变背包问题的精确算法与进化算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(71371063,61170040)


Exact Algorithms and Evolutionary Algorithms for Randomized Time-Varying Knapsack Problem
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (71371063, 61170040)

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

    随机时变背包问题(randomized time-varying knapsack problem,简称RTVKP)是一种动态背包问题,也是一种动态组合优化问题,目前其求解算法主要是动态规划的精确算法、近似算法和遗传算法.首先,利用动态规划提出了一种求解RTVKP问题的精确算法,对算法时间复杂度的比较结果表明,它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两种进化算法.对5个RTVKP实例的数值计算结果比较表明,精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得一个极好的近似解.

    Abstract:

    The randomized time-varying knapsack problem (RTVKP) is both a kind of dynamic knapsack problem and a kind of dynamic combinational optimization problem. Currently, the leading algorithms for solving RTVKP include the exact algorithm base on dynamic programming, approximation algorithm base on greedy-choice strategy and evolutionary algorithm base on genetic algorithm. First, in this paper, an exact algorithm base on dynamic programming to solve RTVKP is presented, along with comparison of its time complexity with the existing exact algorithms. Results show that the proposed algorithm is more suitable to solve RTVKP whose profit is larger. Then, the greedy correction and optimization strategy is combined with differential evolution and particle swarm optimization respectively to solve RTVKP. The numerical results on 5 instances of RTVKP show that the evolutionary algorithms which combine the differential evolution, particle swarm optimization and genetic algorithm with Greedy correction and optimization strategy respectively are more suitable to solve the hard RTVKP whose scale and oscillation frequency are larger while having bigger data.

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

贺毅朝,王熙照,李文斌,赵书良.求解随机时变背包问题的精确算法与进化算法.软件学报,2017,28(2):185-202

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

京公网安备 11040202500063号