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

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

作　　者：尚荣华[1] 焦李成[1] 马文萍[1] 张伟[1] 

机构地区：[1]西安电子科技大学智能信息处理研究所,西安710071

出　　处：《西安交通大学学报》2008年第2期156-160,共5页Journal of Xi'an Jiaotong University

基　　金：国家重点基础研究发展规划资助项目(2001CB309403;2006CB705700);国家自然科学基金重点资助项目(60133010;60372045).`

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

关 键 词：多目标0/1背包问题 支配抗体 克隆选择 抗体修正 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]