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

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

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

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.