第
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
资源评论
weixin_38660058
- 粉丝: 5
- 资源: 920
最新资源
- 2022年江苏省高职组信息安全管理与评估竞赛2卷
- 基于UC3842芯片的AC-DC反激式开关电源 multisim仿真图源文件
- 小型博客系统的设计与实现
- 在线博客系统，个人学习整理，仅供参考
- 七自由度车辆动力学模型验证（Dugoff轮胎模型，B08-01基础上建模） 1.软件: MATLAB 2018以上；CarSim 2020.0 2.介绍: 基于Dugoff轮胎模型和车身动力学公式，搭
- 基于SSM的个人博客系统的设计与实现.zip
- Java源码springboot+vue二手图书交易平台-毕业设计论文-大作业.zip
- 【二维码识别】基于matlab GUI机器学习二维码生成与识别【含Matlab源码 635期】.mp4
- 数字信号处理期末复习基础知识
- 2022年江苏省高职组信息安全管理与评估竞赛3卷
- 批量一键取关公众号我们可以选择用最简单的方式 1.手机上按键精灵模拟实现 2.PC电脑上模拟
- PFC-LLC谐振开关电源设计方案整套学习资料 程序+仿真+硬件软件说明报告+原理图+计算书等等 注：该方案性价比很高，一套资料下来可以自己做个实物验证，要想看细节可以咨询我，我给你看资料的详细展示视
- 数字信号处理复习总结-最终版 --【60页】.doc
- ZenIdentityServer4 资源拥有者模式
- 利用pytorch搭建卷积神经网络（CNN）训练简单手写数字数据集（MNIST）
- jz2440衔接12期，uboot，文件系统，内核移植
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
