求解多目标0/1背包问题的克隆选择算法

提出一种用于求解多目标 0/1 背包问题的新算法.新算法将抗体群中的抗体分为支配抗体和非支配抗体代替传统算法中对所有个体分配适应度值,解决了多目标优化问题中解的多样性的问题.先通过克隆操作实现全局择优,得到分布较广的Pareto-前端,接着采用免疫基因操作提高算法的局部搜索能力,同时采用抗体修正操作对由免疫基因等操作产生的不可行解进行修正,保证抗体在可行解范围内,并实现局部搜索.该算法与已有算法相比能更好地保持解的多样性、均匀性以及收敛性.仿真实验表明,新算法所得的 Pareto-前端分布最广,所得的解能较好地收敛到 Pareto-前端,并且将均匀性评价指标降低到1%以下.

Clonal Selection Algorithm for Multi-Objective 0/1 Knapsack Problems

A new algorithm for multi-objective 0/1 knapsack problems is proposed.The antibodies in the antibody population are divided into dominated ones and non-dominated ones,which solves the diversity problem in the multi-objective optimization problems.In the algorithm,the clonal operation is adopted to implement the searching for optimal solutions in the global region and getting a widely spread Pareto-front.Then,adopting the immune gene operation the searching for optimal solutions is improved in the local region.In the last,the antibody repair operator is introduced for repairing the infeasible solutions produced by the immune gene operation,which guarantees the antibodies in the feasible region and implements the local research.Compared with the existed algorithms,the algorithm can obtain high quality solutions with good diversity,uniformity and convergence.Simulation results show that the Pareto-front obtained by the new algorithm has the most widely spread; the solutions obtained by the algorithm can converge to the Pareto-front and the spacing metric is depressed under 1%.