克隆选择免疫遗传算法对高维0/1背包问题应用

doi:10.3724/SP.J.1087.2013.00845

计算机应用 ›› 2013, Vol. 33 ›› Issue (03): 845-848.DOI: 10.3724/SP.J.1087.2013.00845

克隆选择免疫遗传算法对高维0/1背包问题应用

武慧虹^1*,钱淑渠¹,徐志丹²

1.安顺学院数学与计算机科学系,贵州安顺 561000;
2.哈尔滨商业大学基础科学学院, 哈尔滨 150028

收稿日期:2012-09-25 修回日期:2012-10-30 出版日期:2013-03-01 发布日期:2013-03-01
通讯作者: 武慧虹
作者简介:武慧虹(1980-), 女, 山西娄烦人, 讲师, 硕士, 主要研究方向: 智能优化算法、群与图; 钱淑渠(1978-),男, 安徽枞阳人, 讲师, 硕士, 主要研究方向: 智能优化算法、数学建模; 徐志丹(1980-), 女, 黑龙江哈尔滨人, 讲师, 博士研究生, 主要研究方向: 进化计算、智能控制。
基金资助:
贵州省科学技术基金资助项目(20122002); 贵州省教育厅自然科学基金资助项目(20090074); 贵州省教育厅人文社科青年辅导员基金资助项目(11FDY016)。

Immune genetic algorithm based on clonal selection and its application to 0/1 knapsack problem

WU Huihong^1*, QIAN Shuqu¹, XU Zhidan²

1.Department of Mathematics and Computer Science, Anshun University, Anshun Guizhou 561000, China;
2.Institute of Basic Science, Harbin University of Commerce, Harbin Heilongjiang 150028, China

Received:2012-09-25 Revised:2012-10-30 Online:2013-03-01 Published:2013-03-01
Contact: wu huihong

摘要/Abstract

摘要： 针对遗传算法求解高维背包问题收敛速度慢、易于陷入局部最优的缺点,基于生物免疫系统克隆选择原理,提出一种克隆选择免疫遗传算法。该算法中抗体采用二进制编码,通过抗体浓度设计抗体亲和力,进化群分离为可行群和非可行群,进化过程仅可行抗体动态克隆和突变,非可行抗体经修复算子获可行抗体。数值实验中,选取三种著名的算法用于四种高维的背包问题求解,结果表明:所提算法较其他算法具有更强的约束处理能力和快速收敛的效果。

关键词: 克隆选择, 免疫系统, 遗传算法, 高维, 背包问题

Abstract: There are some problems such as slow convergence and easy stagnation in local optima when using Genetic Algorithms (GA) to solve high-dimensional knapsack problem. To overcome those shortcomings, a bio-inspired clonal selection immune genetic algorithm was developed to solve knapsack problem with high dimension. In the algorithm, the antibody was binary coded and the affinity of antibody was designed based on its density; in addition, the population was divided into feasible and infeasible population, and the feasible antibodies were cloned dynamically and mutated to produce the offspring population, meanwhile the infeasible antibodies were repaired towards the feasibility. The simulation experiments on the four kinds of 0/1 knapsack problem with high dimension and comparison with ETGA, RIGA and ISGA demonstrate that the proposed algorithm has better ability in handling constraints and more rapid convergence.

Key words: clonal selection, immune system, Genetic Algorithm (GA), high dimension, Knapsack Problem (KP)

中图分类号:

TP301.6

武慧虹钱淑渠徐志丹. 克隆选择免疫遗传算法对高维0/1背包问题应用[J]. 计算机应用, 2013, 33(03): 845-848.

WU Huihong QIAN Shuqu XU Zhidan. Immune genetic algorithm based on clonal selection and its application to 0/1 knapsack problem[J]. Journal of Computer Applications, 2013, 33(03): 845-848.

参考文献

[1]LIU H Y, NIE S Z. Solving the 0-1 knapsack problem with polynomial-time quantum algorithm[C]// Proceedings of the Communications in Computer and Information Science. Berlin: Springer, 2012:377-384.
[2]王娜,向凤红,毛剑琳. 改进的自适应遗传算法求解0-1背包问题[J]. 计算机应用,2012, 32(6):1682-1684.
[3]马炫,刘庆.求解多背包问题的人工鱼群算法[J]. 计算机应用, 2010, 30(2):469-471,494.
[4]SINGH R P. Solving 0-1 knapsack problem using genetic algorithms[C]// Proceedings of the 3rd International Conference on Communication Solfware and Networks. Piscataway, NJ: IEEE Press, 2011:591-595.
[5]ZHONG Y H, NIE S Z. Polynomial-time quantum algorithms for the 0-1 knapsack problem[J]. Research Journal of Applied Sciences, Engineering and Technology, 2012, 4(5):510-512.
[6]田建立,晁学鹏.求解0-1背包问题的混沌遗传算法[J].计算机应用研究, 2012, 28(8): 2838-2839, 2879.
[7]WANG R, GUO N, XIANG F H, et al. An improved quantum genetic algorithm with mutation and its application to 0-1 knapsack problem[C]// Proceedings of 2012 International Conference on Measurement, Information and Control. Piscataway, NJ: IEEE Press, 2012:484-488.
[8]BASU S K, BHATIA A K. A naive genetic approach for non-stationary constrained problems[J]. Soft Computing, 2006, 10(2):152-162.
[9]SIMOES A, COSTA E. Improving the genetic algorithm's performance when using transformation [C]// Proceedings of the Sixth International Conference on Neural Networks and Genetic Algorithms. Piscataway, NJ: IEEE Press, 2003:175-181.
[10]SIMOES A, COSTA E. An immune system-based genetic algorithm to deal with dynamic environment: diversity and memory [C]// Proceedings of the Sixth International Conference on Neural Networks and Genetic Algorithms. Piscataway, NJ: IEEE Press, 2003: 168-174.
[11]王则林, 吴志健. 格雷码混合遗传算法求解0-1背包问题[J]. 计算机应用研究, 2012, 29(8):2906-2908.
[12]BORRADAILE G, HEERINGA B, WILFONG G. The knapsack problem with neighbour constraints[J]. Journal of Discrete Algorithms, 2012, 16:224-235.
[13]王晓东. 计算机算法设计与分析[M]. 北京:电子工业出版社, 2004.
[14]钱淑渠, 武慧虹, 涂歆. 动态免疫优化算法及其在背包问题中的应用[J]. 计算机工程, 2011, 37(20):216-218,222.

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[3]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[4]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[5]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[6]	程美英, 钱乾, 倪志伟, 朱旭辉. 信息筛选多任务优化自组织迁移算法[J]. 计算机应用, 2021, 41(6): 1748-1755.
[7]	王心, 朱浩华, 刘光灿. 卷积鲁棒主成分分析[J]. 计算机应用, 2021, 41(5): 1314-1318.
[8]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[9]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[10]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[11]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[12]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[13]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[14]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[15]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.

克隆选择免疫遗传算法对高维0/1背包问题应用

Immune genetic algorithm based on clonal selection and its application to 0/1 knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics