文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 基于遗传算法求解0_1背包问题的算法探讨
侵权投诉

基于遗传算法求解0_1背包问题的算法探讨

介绍贪婪算法和基本遗传算法求解背包问题

第17卷 第4期

  

2008年10月云南民族大学学报(自然科学版)

JournalofYunnanNationalitiesUniversity(NaturalSciencesEdition)Vol.17 No.4Oct.2008

基于遗传算法求解0-1背包问题的算法探讨

刘 锐 张金波 刘蕊洁 李积宪

(兰州交通大学数理与软件工程学院,甘肃兰州730070)

摘 要 0-1背包问题是一类典型的组合优化问题,并且是NP完全问题,具有重要的研究意义.介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,提出了基于贪婪算法的混合遗传算法求解0-1背包问题.有更好的近似解.

关键词 遗传算法;贪婪算法;0-1背包问题【中图分类号】TP30116

【文献标识码】A

【()--03

OntheAlgorithmofSolvingthe-1mBasedontheGeneticAlgorithm

iuJinbo LiuRuijie LiJixian

(PhysicsandSoftwareEngineering,LanzhouJiaotongUniversity,

Lanzhou730070,China)

Abstract:The0-1knapsackproblemisatypicalkindofcombinatorialoptimizationproblemsandisrelatedtoNP-complete,whoseresearchhasgreatsignificance.Thegreedyalgorithmandthebasicgeneticalgorithmforsolvingthe0-1knapsackproblemareintroduced,andanimprovedgeneticalgorithmbasedonthegreedyalgo2rithmwhichisusefulforsolvingthe0-1knapsackproblemisproposed.Theexperimentshowstheresultthattheimprovedgeneticalgorithmcanprovidebetterapproximatesolutions.

Keywords:geneticalgorithm;greedyalgorithm;0-1knapsackproblem

0 引言

0-1背包问题

[1-3]

1 问题描述及基本算法介绍

是一个经典的NP完全问

111 0-1背包问题的描述

题,人们认为这类难解的组合最优化问题不存在求解最优解的多项式时间算法.0-1背包问题在现实生活中具有广泛的应用,如物流公司的货物发配问题,集装箱的装运问题等.解决0-1背包问题的方法可以分为最优算法和启发式算法,最优算法包括穷举法、动态规划法、递归算法等,可以找到最优解,但是只适用于小规模问题;启发式算法包括贪婪算法、遗传算法等,一般用于求解较大规模问题.本文简单介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,并提出基于贪婪算法的混合遗传算法求解0-1背包问题.实验结果表明改进的遗传算法有更好的近似解.

3 收稿日期:2008-04-11.

背包问题的一般提法是:设U={u1,u2,…,un}是一个准备放入容量为C的背包中的n项物品的集合.对于1ΦjΦn,令sj和yj分别为第j项物品的体积和价值,这里,C,sj,vj和j都是整数.要解决的问题是用U中的物品来装满包,这些物品的总体积不超过C,然而,要使得它的总价值最大.不失一般性,假定每项物品的体积不大于C.更形式地,给出有n项物品的集合,要找出一个子集合SΑU,使得f(x1,

x2,…,xn)=

6

n

vixi在最大约束条件

i=1

6

n

i=1

sixiΦC下

最大,其中xi∈{0,1},当xi=1时,表示第i项物品

ui被选中装入背包中,当xi=0时,表示第项物品没

作者简介:刘锐(1979~),男,硕士研究生,主要研究方向:数据挖掘.通讯作者:李积宪(1962~),男,副教授,主要研究方向:自动控制.

377

第1页

你可能喜欢

  • 量子遗传算法
  • 小生境遗传算法
  • 神经网络遗传算法
  • matlab遗传算法工具箱
  • 算法研究

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email