第
36
卷第
3
期
2 0 0
9
年
3
月
湖南大学学报(自然科学版)
Journal
of
Hunan
University(Natural
Sc
ie
口
ces)
Vo
l. 36,No. 3
Mar.
2009
文章编号:
1674-2974 (2009 }03-0081-04
改进的克隆选择算法求解。
-1
背包问题带
王炼红，幸兢\龚固丰，何昭晖
(湖南大学电气与信息工程学院，湖南长沙
410082)
摘
要:提出了一种改进的克隆选择算法
(Improved
CSA)
，该算法采用贪婪策略与宽
限边界值相结合的方法，利用未成熟优良子群体提供的信息修改个体基因位来改善种群质
量;同时增加一个历史至当前代最佳个体记忆羊元防止种群退化.通过对
2
个
0-1
背包问题
的仿真实验表明:该算法比一般
CSA
算法和遗传算法能是快的找到最优解;其搜索效率更
高，性能更加稳定.
关键词:算法;克隆选择;贪婪策略;背包问题
中固分类号
:TP18
文献标识码
:A
Solution of 0 -1 Knapsack Problem Applying Improved CSA Algori thm
WANG
Lian-hong
,
ZHANG
Jing
t
,
GONG
Gu-feng
, HE
Zhao-hui
(Col!
ege
of
Electrical
and
Infonnation Engineering,
Hunan
Univ
,
Changsha
, Hunan 410082,
China)
Abstract:
This
paper
proposed
an
improved Clonal Selection
Algorithm
(CSA)
,
which
combined
greedy
strategy
with
an
extended
boundary
,
and
modified
individuality'
s
gene
bit
to
improve population
by
using
th
巳
good gene
bit
information
in
the
immaturate
subpopulation.
Meanwhile
an
additional
memory
cell
of
the
best
in-
dividuality
was
set
up
to
avoid population devolution.
The
simulation
test
of
two
0 -1
Knapsack
Problems
shows
that
the
algorithm
can
search
for
the
best
solution
more
quickly
than
the
current
CSA
,
and
its efficiency
is
higher
and
its
stability is
better
than
the
CSA
and
Genetic
Al
gorjthm(
GA)
.
Key
words:
algori
thm;
clonal selection;
greedy
strategy;
Knapsack
Problem
背包问题
(Knapsack
Problem)
实际上是一个典
型的非确定多项式
(Non-deterministic
Polynomial,
NP)
完全难题.它在
20
世纪
50
年代末期被
Dantzig
提出之后，在最近几年又被广泛研究.这主要是因为
它无论是在理论上，还是在实践中都具有重要的意
义.理论上很多整数规划问题的解决都依赖于一个
高效的背包问题解法;同时，在工业和金融等领域，
如资源分配、投资决策、材料切割、货物装载、网络资
源分配等均可建模为背包问题加以研究.穷举法、动
态规划法和递归回溯法等精确算法只适合于小规模
问题
[1-
3]
启发式算法是模拟自然现象和生物行为
过程而提出的新型算法，具有框架灵活，求解迅速、
解质量优良等一系列优点，因而获得了广泛应用.但
禁忌搜索算法和遗传算法等启发式式算法收敛速度
慢而且很容易陷入局部极小值
[4-6]
目前，免疫算法
帚收稿日期
:2008
-0
4
-22
能有效克服早熟现象，改善陷入局部最优的缺陷，使
算法比较快地收敛于全局最优解
[7]
本文在研究了
DE
Castro
提出的克隆选择算法
的基础上[剖，利用未成熟优良子群体提供的信息，结
合贪婪策略和宽限边界值来修改个体基因位，改善
了种群质量.因此，通过该引导机制可增强算法的智
能性，提高搜索效率和收敛速度.最后将算法用于背
包问题的解决，获得了比遗传算法和一般克隆选择
算法更满意的效果.
1
背包问题
假设我们要从多种物品中选择几件物品，装满
背包.若有
n
个不同的物品，对于物品
z
，其重量(或
容积)为叫，价值为
C
j
;
则
η
个物品的重量(容积)
基金项目:国家自然科学基金重点资助项目
(60634020)
;教育部高等学校博士学科点专项科研基金资助项目
(20060532026)
作者简介:王炼红(1
971-
)，女，湖南宁乡人，湖南大学搏士研究生
f
通讯联系人，
E-mail:zhan
回
@hnu.cn
资源评论
