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

尚荣华; 焦李成; 马文萍; 张伟

您当前的位置：

首页 >

文章列表页 >

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

专题研究 | 更新时间：2025-12-08

- 求解多目标0/1背包问题的克隆选择算法
- Clonal Selection Algorithm for Multi-Objective 0/1 Knapsack Problems
- 西安交通大学学报 2008年42卷第2期页码：156-160
- 作者机构：
  
  西安电子科技大学智能信息处理研究所,西安,710071
- 作者简介：
- 基金信息：
  
  : 2007-04-28. 作者简介: 尚荣华(1979-),女,博士生;焦李成(联系人),男,教授,博士生导师. 基金项目: 国家重点基础研究发展规划资助项目(2001CB309403,2006CB705700);国家自然科学基金重点资助项目(60133010,60372045).
- DOI：
  中图分类号： TP18
- 网络首发：2008-02-10，
  
  纸质出版：2008
- 稿件说明：
移动端阅览
尚荣华, 焦李成, 马文萍, 等. 求解多目标0/1背包问题的克隆选择算法[J]. 西安交通大学学报, 2008,42(2):156-160.

尚荣华, 焦李成, 马文萍, et al. Clonal Selection Algorithm for Multi-Objective 0/1 Knapsack Problems[J]. 2008, 42(2): 156-160.
尚荣华, 焦李成, 马文萍, 等. 求解多目标0/1背包问题的克隆选择算法[J]. 西安交通大学学报, 2008,42(2):156-160. DOI：

尚荣华, 焦李成, 马文萍, et al. Clonal Selection Algorithm for Multi-Objective 0/1 Knapsack Problems[J]. 2008, 42(2): 156-160. DOI：

摘要

提出一种用于求解多目标0/1背包问题的新算法.新算法将抗体群中的抗体分为支配抗体和非支配抗体代替传统算法中对所有个体分配适应度值

解决了多目标优化问题中解的多样性的问题.先通过克隆操作实现全局择优

得到分布较广的Pareto-前端

接着采用免疫基因操作提高算法的局部搜索能力

同时采用抗体修正操作对由免疫基因等操作产生的不可行解进行修正

保证抗体在可行解范围内

并实现局部搜索.该算法与已有算法相比能更好地保持解的多样性、均匀性以及收敛性.仿真实验表明

新算法所得的Pareto-前端分布最广

所得的解能较好地收敛到Pareto-前端

并且将均匀性评价指标降低到1%以下.

Abstract

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%.

关键词

Keywords

references

ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach [J]. IEEE Trans Evol Computer,1999,3(4):257-271.

SCHAFFER J D. Multiple objective optimization with vector evaluated genetic algorithms [D]. Nashville, USA: Vanderbilt University,1984.

HORN J, NAFPLIOTIS N. Multiobjective optimization using the niched pareto genetic algorithm, IlliGAL Report 93005 [R]. Urbana, USA: Illinois Genetic Algorithms Laboratory, University of Illinois, 1993.

NAND S, DEB K. Multiobjective optimization using nondominated sorting in genetic algorithms [J]. IEEE Trans Evol Computer,1994, 2(3): 221-248.

de CASTRO L N, von ZUBEN F J. Learning and optimization using the clonal selection principle [J]. IEEE Trans Evol Computer, 2002, 6(3):239-251.

焦李成,杜海峰,刘芳,等.免疫优化计算、学习与识别[M].北京:科学出版社, 2006.

ISHIBUCHI H, MURATA T. A multiobjective genetic local search algorithm and its application to flowshop scheduling [J]. IEEE Trans System, Man and Cyber,1998, 28(3): 392-403.

潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.

郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007.

ZITZLER E, DEB K, THIELE L. Comparison of multiobjective evolutionary algorithms: empirical results [J]. IEEE Trans Evol Computer, 2000, 8(2):173-195.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种用于非线性系统参数辨识的耦合算法研究

水蒸气掺混对氨裂解气旋流燃烧与排放特性的影响研究

采用试验设计方法的第三代CO2气体箔轴承箔片几何参数敏感性分析

融合物理信息与深度算子网络的变压器绕组热-流场快速计算方法

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究