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

来源：计算机科学与探索杂志2016年第12期北京时间：

作者：钱淑渠，武慧虹

单位：1. 南京航空航天大学 自动化学院，南京 2100162. 安顺学院 数理学院，贵州 安顺 561000

摘要：针对克隆选择算法（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）,受体编辑机制,修补策略