主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
贺毅朝,王熙照,李文斌,赵书良.求解随机时变背包问题的精确算法与进化算法.软件学报,2017,28(2):185-202
求解随机时变背包问题的精确算法与进化算法
Exact Algorithms and Evolutionary Algorithms for Randomized Time-Varying Knapsack Problem
投稿时间:2014-08-04  修订日期:2015-01-21
DOI:10.13328/j.cnki.jos.004937
中文关键词:  动态规划  时间复杂度  差分演化  粒子群优化  修复方法
英文关键词:dynamic programming  time complexity  differential evolution  particle swarm optimization  repair approach
基金项目:国家自然科学基金(71371063,61170040)
作者单位E-mail
贺毅朝 河北地质大学 信息工程学院, 河北 石家庄 050031
河北师范大学 软件学院, 河北 石家庄 050024 
heyichao@sjzue.edu.cn 
王熙照 深圳大学 计算机与软件学院, 广东 深圳 518060  
李文斌 河北地质大学 信息工程学院, 河北 石家庄 050031  
赵书良 河北师范大学 数学与信息科学学院, 河北 石家庄 050024
河北师范大学 软件学院, 河北 石家庄 050024 
 
摘要点击次数: 1383
全文下载次数: 1156
中文摘要:
      随机时变背包问题(randomized time-varying knapsack problem,简称RTVKP)是一种动态背包问题,也是一种动态组合优化问题,目前其求解算法主要是动态规划的精确算法、近似算法和遗传算法.首先,利用动态规划提出了一种求解RTVKP问题的精确算法,对算法时间复杂度的比较结果表明,它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两种进化算法.对5个RTVKP实例的数值计算结果比较表明,精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得一个极好的近似解.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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