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

Improved Clonal Selection Algorithm for Solving High- Dimensional Knapsack Problem

针对克隆选择算法(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及基因段基准长度σ)进行了敏感性分析,获得了合适的参数选择策略。

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 (CSAER) 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.