Journal of Frontiers of Computer Science and Technology ›› 2016, Vol. 10 ›› Issue (12): 1711-1719.DOI: 10.3778/j.issn.1673-9418.1511066

Previous Articles     Next Articles

Improved Clonal Selection Algorithm for Solving High-Dimensional Knapsack Problem

QIAN Shuqu1,2+, WU Huihong2   

  1. 1. College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
    2. School of Sciences, Anshun University, Anshun, Guizhou 561000, China
  • Online:2016-12-01 Published:2016-12-07

改进的克隆选择算法求解高维背包问题

钱淑渠1,2+,武慧虹2   

  1. 1. 南京航空航天大学 自动化学院,南京 210016
    2. 安顺学院 数理学院,贵州 安顺 561000

Abstract: Since clonal selection algorithm (CSA) on high-dimensional knapsack problems (KPs) can only obtain a low feasible rate, and falls easily into local search, this paper proposes an improved clonal selection algorithm (CSA-ER) to solve high-dimensional KPs. In CSA-ER, a receptor editing mechanism is developed based on antibodies diversity function in immune system. Also, a repeat repair strategy is introduced to enhance the ability of handling constraints. CSA-ER is compared with several variants of CSA (CSA-M, CSA-E, CSA-MR) and two other intelligent algorithms on KPs in simulation experiments. The results show that CSA-ER has strong exploitation and convergence capability. Meanwhile, the sensitivities of three parameters (selection rate α, editing rate Tr, and basic gene segment length σ) in CSA-ER are also analyzed, and the appropriate parameter settings are obtained in the last.

Key words: high-dimensional knapsack problem, clonal selection algorithm (CSA), receptor editing mechanism, repair strategy

摘要: 针对克隆选择算法(clonal selection algorithm,CSA)求解高维背包问题(knapsack problem,KP)时可行抗体比率低且易于陷入局部搜索的问题,充分挖掘免疫系统的抗体多样性机理,提出了受体编辑机制,并设计了二次修补策略增强约束处理能力,获得了改进的克隆选择算法CSA-ER(clonal selection algorithm with receptor editing and repair)。数值实验将CSA-ER与CSA的一系列变体(CSA-M、CSA-E、CSA-MR)及两类其他群智能算法应用于两类KP进行了仿真比较,结果表明CSA-ER具有较强的开采和收敛能力。同时对CSA-ER的3个参数(克隆选择率α、编辑率Tr及基因段基准长度σ)进行了敏感性分析,获得了合适的参数选择策略。

关键词: 高维背包问题, 克隆选择算法(CSA), 受体编辑机制, 修补策略