论文部分内容阅读
[摘要]背包问题其实就是一个优化问题，即在所有装包方案中选择一种最为有效精确的装包方案，使背包的体积最少，背包内所装物体价值最大。背包问题一直以来是研究的一个重点和难点，在总结国内外相关研究的基础上对背包问题及其算法进行研究，希望能够有助于提高我们对相关问题的认识。
[关键词]背包问题 算法 遗传算法 蚁群算法 博弈论 快速收敛算法
中图分类号：O29 文献标识码：A 文章编号：1671－7597(2008)0520023－02
背包问题是当前研究的一大热点和重点。背包问题的实质就是优化的问题，即如何在有效的空间内装载更多的物品，实现背包价值的最大化。对背包问题及其算法进行研究有助于提升应用的水平，加快效率社会的建设步伐。
一、背包问题
什么是背包问题呢，举个例子来说有10个重量不等，分别是1kg,2kg,3kg,4kg,5kg,6kg,7kg8kg,9kg,10kg的物品，现在要把他们装在一个背包里，背包只能装50kg的物品，如何从期间选择若干件商品使背包刚好装满。一只背包最多能装总重量为Mkg的物品,现共有n件物品,每件的重量均为正整数kg,它们是a1,a2,…,an(kg),而且a1+a2+…+an>M.试问:能否从n件标本中选出若干件,使得被选出的标本的总重量恰为Mkg？如果被选出的标本记为1,未被选中的记为0,也就相当于判定是否存在取值为0,1的二值数组(m1,m2,…,mn),m1a1+m2a2++mnan=M.因而可以建立数学模型：若n个正整数a1,a2,…,an和另一已知正整数M,满足a1+a2+…+an>M.问:是否存在一个二值数组(m1,m2,…,mn)(其中mi=0或1,i=1,2,…,n),使得恰有m1a1+m2a2+…+mnan=M？背包问题可能有解,也可能无解。选择正确的算法对背包问题进行解答，是解决背包问题的基础和关键。
二、背包问题的算法研究
（一）遗传算法
（二）蚁群算法
（1）蚁群算法的基本原理。蚁群算法是模仿真实的蚁群行为而提出的一种模拟进化算法，蚂蚁之间是通过一种称为信息素(Pheromone)的物质传递信息的，蚂蚁在运动过程中能够在经过的路径上留下该种物质，而且能够感知这种物质的存在及其强度，并以此指导自己的运动方向。因此，由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象：某一条路径上走过的蚂蚁越多,该路径上留下的信息素就越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息素的交流，搜索到一条从蚁巢到食物源的最短路径。
（2）蚁群算法已成功地解决了TSP问题，以求解平面上n个城市的TSP问题为例说明蚁群系统模型，TSP问题就是寻找通过n个城市各一次且最后回到出发点的最短封闭路径。TSP问题的目标函数为：
算法是问题求解过程的精确描述,一个算法由有限条可完全机械地执行的、有确定结果的指令组成，算法设计是一件非常困难的工作。除上面涉及的几种背包算法外，还有穷举搜索法（穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解）；递归法（递归法是设计和描述算法的一种有力的工具它在复杂算法的描述中经常被采用）；贪婪法（贪婪法是一种不要求最优解,只希望得到较为满意解的方法"贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间）；分治法（分治法是最广泛使用的算法设计方法）等。这些算法常常成为我们分析和解决背包问题的基础，和主要的指导性方法。
背包问题是当前研究的重点，利用多种算法对背包问题进行解答有助于加深对背包相关问题的理解，促进背包原理应用的提升。
参考文献：
[1]叶俊，刘贤德，韩露：《基于博弈论的背包问题优化算法》，载《华中科技大学学报(自然科学版)》2003年9月.
[2]刘华蓥，林玉娥，刘金月，《基于蚁群算法求解0/1背包问题》，载《大庆石油学院学报》2005年6月.
[3]刘西奎，李艳，许进，《背包问题的遗传算法求解》，载《华中科技大学学报(自然科学版)》2002年6月.
[4]周春荔，宁国然：，《背包问题与公开密钥》，载《中学数学》2000年第1期.
[5]李庆华、李肯立、蒋盛益、张薇，《背包问题的最优并行算法》，载《软件学报》2003年1月.
[6]何文明、朱起定：，《背包问题的循环及并行解》，载《湘潭师范学院学报》2000年5月.
[7]石晓龙，许进，《DNA计算与背包问题》，载《计算机工程与应用》2003年第27期.
[8]于秀霞，《求解背包问题的新型算法》，载《长春大学学报》2002年4月.
[9]于永新，张新荣，《基于蚁群系统的多选择背包问题优化算法》，载《计算机工程》2003年11月.
[10]李少芳，《连续背包问题贪婪算法最优解的实现》，载《福建电脑》2003年第11期.
[11]孙劲光，《“背包问题”算法设计及分析》，载《辽宁工程技术大学学报（自然科学版）》2002年4月.
[12]虞安波 、杨家本，《多背包问题的遗传算法求解》，载《计算机技术与自动化》2002年6月.
[关键词]背包问题 算法 遗传算法 蚁群算法 博弈论 快速收敛算法
中图分类号：O29 文献标识码：A 文章编号：1671－7597(2008)0520023－02
背包问题是当前研究的一大热点和重点。背包问题的实质就是优化的问题，即如何在有效的空间内装载更多的物品，实现背包价值的最大化。对背包问题及其算法进行研究有助于提升应用的水平，加快效率社会的建设步伐。
一、背包问题
什么是背包问题呢，举个例子来说有10个重量不等，分别是1kg,2kg,3kg,4kg,5kg,6kg,7kg8kg,9kg,10kg的物品，现在要把他们装在一个背包里，背包只能装50kg的物品，如何从期间选择若干件商品使背包刚好装满。一只背包最多能装总重量为Mkg的物品,现共有n件物品,每件的重量均为正整数kg,它们是a1,a2,…,an(kg),而且a1+a2+…+an>M.试问:能否从n件标本中选出若干件,使得被选出的标本的总重量恰为Mkg？如果被选出的标本记为1,未被选中的记为0,也就相当于判定是否存在取值为0,1的二值数组(m1,m2,…,mn),m1a1+m2a2++mnan=M.因而可以建立数学模型：若n个正整数a1,a2,…,an和另一已知正整数M,满足a1+a2+…+an>M.问:是否存在一个二值数组(m1,m2,…,mn)(其中mi=0或1,i=1,2,…,n),使得恰有m1a1+m2a2+…+mnan=M？背包问题可能有解,也可能无解。选择正确的算法对背包问题进行解答，是解决背包问题的基础和关键。
二、背包问题的算法研究
（一）遗传算法
（二）蚁群算法
（1）蚁群算法的基本原理。蚁群算法是模仿真实的蚁群行为而提出的一种模拟进化算法，蚂蚁之间是通过一种称为信息素(Pheromone)的物质传递信息的，蚂蚁在运动过程中能够在经过的路径上留下该种物质，而且能够感知这种物质的存在及其强度，并以此指导自己的运动方向。因此，由大量蚂蚁组成的集体行为便表现出一种信息正反馈现象：某一条路径上走过的蚂蚁越多,该路径上留下的信息素就越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息素的交流，搜索到一条从蚁巢到食物源的最短路径。
（2）蚁群算法已成功地解决了TSP问题，以求解平面上n个城市的TSP问题为例说明蚁群系统模型，TSP问题就是寻找通过n个城市各一次且最后回到出发点的最短封闭路径。TSP问题的目标函数为：
算法是问题求解过程的精确描述,一个算法由有限条可完全机械地执行的、有确定结果的指令组成，算法设计是一件非常困难的工作。除上面涉及的几种背包算法外，还有穷举搜索法（穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解）；递归法（递归法是设计和描述算法的一种有力的工具它在复杂算法的描述中经常被采用）；贪婪法（贪婪法是一种不要求最优解,只希望得到较为满意解的方法"贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间）；分治法（分治法是最广泛使用的算法设计方法）等。这些算法常常成为我们分析和解决背包问题的基础，和主要的指导性方法。
背包问题是当前研究的重点，利用多种算法对背包问题进行解答有助于加深对背包相关问题的理解，促进背包原理应用的提升。
参考文献：
[1]叶俊，刘贤德，韩露：《基于博弈论的背包问题优化算法》，载《华中科技大学学报(自然科学版)》2003年9月.
[2]刘华蓥，林玉娥，刘金月，《基于蚁群算法求解0/1背包问题》，载《大庆石油学院学报》2005年6月.
[3]刘西奎，李艳，许进，《背包问题的遗传算法求解》，载《华中科技大学学报(自然科学版)》2002年6月.
[4]周春荔，宁国然：，《背包问题与公开密钥》，载《中学数学》2000年第1期.
[5]李庆华、李肯立、蒋盛益、张薇，《背包问题的最优并行算法》，载《软件学报》2003年1月.
[6]何文明、朱起定：，《背包问题的循环及并行解》，载《湘潭师范学院学报》2000年5月.
[7]石晓龙，许进，《DNA计算与背包问题》，载《计算机工程与应用》2003年第27期.
[8]于秀霞，《求解背包问题的新型算法》，载《长春大学学报》2002年4月.
[9]于永新，张新荣，《基于蚁群系统的多选择背包问题优化算法》，载《计算机工程》2003年11月.
[10]李少芳，《连续背包问题贪婪算法最优解的实现》，载《福建电脑》2003年第11期.
[11]孙劲光，《“背包问题”算法设计及分析》，载《辽宁工程技术大学学报（自然科学版）》2002年4月.
[12]虞安波 、杨家本，《多背包问题的遗传算法求解》，载《计算机技术与自动化》2002年6月.