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）, 受体编辑机制, 修补策略