《计算机应用研究》|Application Research of Computers

利用遗传算法求解静态与动态背包问题的研究

Research on genetic algorithms for solving static and dynamic knapsack problems

免费全文下载 (已被下载 次)  
获取PDF全文
作者 贺毅朝,宋建民,张敬敏,苟海燕
机构 1.石家庄经济学院 a.信息工程学院;b.数理学院,石家庄 050031;2.石家庄经济学院 华信学院,河北 新乐 050000
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2015)04-1011-05
DOI 10.3969/j.issn.1001-3695.2015.04.012
摘要 为了有效处理遗传算法在求解静态与动态背包问题时产生非正常编码个体的问题,在分析已有处理方法不足的基础上,基于贪心策略提出了一种贪心修正算子与贪心优化算子相结合的新方法,并将该方法与遗传算法相融合给出了求解静态与动态背包问题的有效算法。仿真计算结果表明,在求解静态与动态背包问题时,利用所提出的新方法不仅可以解决非正常编码个体的问题,而且还能够显著提高个体所对应的可行解的质量,极大地改善了遗传算法的求解效果。
关键词 遗传算法;背包问题;时变背包问题;贪心策略
基金项目 河北省教育厅自然科学基金资助项目(Z2013110)
本文URL http://www.arocmag.com/article/01-2015-04-012.html
英文标题 Research on genetic algorithms for solving static and dynamic knapsack problems
作者英文名 HE Yi-chao, SONG Jian-min, ZHANG Jing-min, GOU Hai-yan
机构英文名 1. a. College of Information Engineering, b. College of Mathematics & Sciences, Shijiazhuang University of Economics, Shijiazhuang 050031, China; 2. Huaxin College, Shijiazhuang University of Economics, Xinle Hebei 050000, China
英文摘要 For solving the problem of non-normal coding individual by using genetic algorithms (GAs) for static and dynamic knapsack problems, this paper analyzed and pointed the pitfalls of existent methods, and proposed a new method for handling the problem of non-normal coding individual by greedy strategy, which included greedy modify operator and greedy optimize operator. Then, it gave out two efficient algorithms which combined the new method with GAs for static and dynamic knapsack problems. The numerical computation results show that the new method not only modify non-normal coding individual but also improve the quality of individual, and greatly improves the performance of GAs for static and dynamic knapsack problems.
英文关键词 genetic algorithms; knapsack problems(KP); time-varying knapsack problems(TVKP); greedy strategy
参考文献 查看稿件参考文献
  [1] 陈国良, 王熙法, 庄镇泉, 等. 遗传算法及其应用[M] . 北京:人民邮电出版社, 2003.
[2] YUEN S Y, CHOWC K. A genetic algorithm that adaptively mutates and never revisits[J] . IEEE Trans on Evolutionary Computation, 2009, 13(2):454-472.
[3] 徐宗本. 计算智能——模拟进化计算[M] . 北京:高等教育出版社, 2005.
[4] 汪定伟, 王俊伟, 王洪峰, 等. 智能优化方法[M] . 北京:高等教育出版社, 2007.
[5] 史岚, 张义宏, 吕建辉. 基于绝对贪心和预期效率的0-1背包问题优化[J] . 计算机应用研究, 2014, 31(3):684-687.
[6] 庄中文, 钱淑渠. 抗体修正免疫算法对高维0-1背包问题的应用[J] . 计算机应用研究, 2009, 26(8):2921-2923, 2930.
[7] 贺毅朝, 刘坤起, 张翠军, 等. 求解背包问题的贪心遗传算法及其应用[J] . 计算机工程与设计, 2007, 28(11):2655-2657, 2681.
[8] 贺毅朝, 田海燕, 张新禄, 等. 基于动态规划法求解动态0-1背包问题[J] . 计算机科学, 2012, 39(7):237-241.
[9] GOLDBERG D E, SMITH R E. Nonstationary function optimization using genetic algorithms with dominance and diploidy[C] //Proc of International Conference on Genetic Algorithms. Hillsdale:L. Erlbaum Associates Inc, 1987:59-68.
[10] 李宁, 贺毅朝, 田海燕. 混合编码和声搜索算法在动态优化中的应用[J] . 计算机工程, 2012, 38(12):149-151, 154.
[11] 周传华, 谢安世. 一种基于动态小生境的自组织学习算法[J] . 软件学报, 2011, 22(8):1738-1748.
[12] XU Z B, CHEN Z P, ZHANG X S. Recent development on theoretical research of genetic algorithms[J] . Advances in Mathematics, 2000, 29(2):97- 114.
[13] 堵丁柱, 葛可一, 胡晓东. 近似算法的设计与分析[M] . 北京:高等教育出版社, 2011.
[14] DAS S, SUGANTHAN P N. Differential evolution:a survey of the state-of-the-art[J] . IEEE Trans on Evolutionary Computation, 2011, 15(1):4-31.
[15] 贺毅朝, 王熙照, 寇应展. 一种具有混合编码的二进制差分演化算法[J] . 计算机研究与发展, 2007, 44(9):1476-1484.
[16] ENGELBRECHT A P. Fundamentals of computational swarm intelligence[M] . [S. l. ] :Wiley, 2005:145-330.
[17] LI Xiao-dong. Niching without niching parameters:particle swarm optimization using a ring topology[J] . IEEE Trans on Evolutionary Computation, 2010, 14(1):150-169.
收稿日期 2014/3/11
修回日期 2014/5/4
页码 1011-1015
中图分类号 TP301.6
文献标志码 A