遗传算法求解01背包问题
更新时间:2023-09-19 07:33:01 阅读量: 小学教育 文档下载
遗传算法求解01背包问题
一、问题描述
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下:
给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择合适的物品装入背包,使得背包中装入的物品的总价值最大。注意的一点是,背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时,对每种物品i只有两种选择:装入背包或者不装入背包,即只能将物品i装入背包一次。称此类问题为0/1背包问题。 01背包问题是NP问题,传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决01背包问题。遗传算法(Genetic Algorithms)则是一种适合于在大量的可行解中搜索最优(或次优)解的有效算法。
二、遗传算法
1、遗传算法的基本思想 遗传算法的搜索从一个被称作种群的候选解集开始,新的种群由旧的种群中产生以期得到更好的种群。从旧种群中按照解的适应度来选择解以产生新的解;适应度越大,解被选择生成后代的机率也越大。这个从已有种群中选择双亲并产生后代的迭代过程持续到遗传算法的停止条件满足为止。 2、遗传算法的基本元素。 遗传算法由以下几个原素组成:由染色体组成的种群,根据适应度进行选择以及交叉产生后代。
三、用遗传算法求解01背包问题
1、01背包问题中染色体的表示。
用向量X来表示染色体,
X = {x1,x2,……,xn}。,xi∈{0,1},
xi=1表示物品i装入了背包,xi =0表示物品i未装入背包。 每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的适应度。
程序中定义了这样的一个结构来表示染色体: typedef struct{ int Weight; //染色体代表的物品的总重量 int Fitness; //染色体代表的物品的价值(适应度) int Gene[NUMG]; //用元素取值于定义域{0,1}的数组表示染色体。 }GENE;
2、遗传算法求解01背包问题时用到的参数。
POPSIZE:种群大小,即已知的可行解的个数。 NUMG:染色体中基因的个数,即物品的总数。 CAPACITY:背包的容量。
MAXB:二进制表示的染色体换算之后的最大十进制整数。用于随机产生一个整数,进而转换作染色体。
SIM:染色体之间的相似度阈值。当染色体之间的相似度达到阈值时,算法即停止运行。 PC=1.0 :交叉概率为100%。
PM=0.2 :变异概率为20%,变异可以保证种群的多样性,从而防止算法收敛于某个局部解。 3、选择操作。
选择操作采用了赌轮选择(Roulette-wheel selection)的方法。函数selectIndex()中包含了选择染色体的具体过程。其流程图如图1所示。
图1 赌轮选择流程图
程序中用一个Begin来代表当前赌轮上的指针的位置,End则用来使赌轮循环转动。
用summaryBE表示当前赌轮上的指针转过的染色体的总价值。 用summaryF表示当前全部染色体的价值总和。
用randProb作为染色体选择的阈值。randProb为介于[0,1]之间的随机数。
选择使summaryBE/summaryF 大于阈值randProb的染色体作为要选择的染色体。 4、交叉操作
程序中采用了单点交叉的策略。如下程序代码所示: for(int j=0; j for(;j partPos为随机产生的整数,代表交叉的位置。第一个for循环将partPos位置之前的基因遗传给一个后代,而第二个循环则将partPos位置之后的基因进行了交换。 calculateCapacity函数用于计算交叉操作后的染色体的容量。 calculateFitness函数用于计算交叉操作后的染色体的适应度。 checkCapacity函数则用于检查交叉后的染色体的合理性,容量超出背包的染色体是不合理的。这里没有使后代死亡,而是随机地调整了染色体中的基因。使得基因能够适应环境(背包的容量)而继续生存。 5、精英策略 精英策略为了不使最优解在交叉的过程中,不会丢失最优解而采取的策略。其思想是保存上一代中的适应性强的染色体。相应地取代下一代中适应性弱的染色体。 程序中精英策略由keepBestParents函数和sortFiness函数来实现。需要说明的是sortFitness仅仅对种群的索引进行了排序。然后用父代中20%的适应度较大的优秀染色体替换子代中20%的适应性弱的染色体。 6、变异操作 染色体的变异可以保持种群的多样性,防止最优解的丢失以及算法收敛到局部最优解。 变异操作由mutation函数实现。 首先产生一个介于0和1之间的随机数prob,若prob小于MP则进行变异操作:随机产生一个位置partPos,然后变异前染色体的partPos位置的基因为1,则变异为0,否则变异为1;相应地要进行适应度和染色体容量的变化。 7、代际更新 代际之间的更新,即用新生成的种群代替取代旧的种群。这个操作在updateGeneration函数中实现,同时这个操作使用了前面提及的精英策略。实际上,父代种群中优秀的染色体已被保留,updateGeneration中只是用新种群中的优秀染色体来代替父代中的染色体。 由于对父代和子代的染色体都进行了排序,因此程序中将子代的80%视作优秀,将父代中的前20%视作优秀。 8、算法的终止 程序中采用了一个HASH表来对子代种群的适应度进行HASH操作。HASH表中的头结点纪录了头结点所指向的单链表的信息。如下代码中的注释: typedef struct Head{ int maxFitness; //单链表中的最大的Fitness int Count; //HASH到该结点的染色体的数目 int Diff; //单链表中有多少不同的Fitness HASHNODE *Next; }HEAD; 用这样的一个HASH表结构可以只需遍历HASH表中的头结点,即可知当前的种群的适应度最大的染色体是否集中。 具体地,如checkFitness函数中的下面几行代码: index = maxFitness(hashTable); double CPount = hashTable[index].Count/(double)POPSIZE; double pDiff = hashTable[index].Diff/(double)POPSIZE; if(CPount>=0.9 && pDiff<=0.1){ sameFlag = false; } 如果当前maxFitness最大的头结点满足if语句中的判断条件,则sameFlag置为真,即算法停止迭代的条件得到了满足。 TraverseHashTable函数则用于遍历HASH表。 算法终止的另一个条件是迭代的次数。程序中设定了算法的最大迭代次数为1000。 四、实验结果。 试验中用到的物品的重量和价值分别存储于以下两个数组之中。 int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1}; int Value[NUMG]={2,20,5,4,19,14,18,8,11,6}; 父代种群存储于parentGenome[NUMG]中,子代种群存储于nextGenome[NUMG]中。程序的初始状 态和结束状态如下面的表格所示: 初始的种群 Weight 21 22 22 22 26 24 22 23 26 25 Value 52 23 40 53 45 53 53 25 48 29 染色体中的基因 0010110101 0011000101 0001100011 0100010110 1010011001 1100010011 0100010110 1011010000 1010110100 0111000000 初始的HASH表 头结点索引 maxFitness Count Diff 单链表中的结点内容 0 1 3 6 9 10 12 52 53 29 45 48 23 25 1 4 1 1 1 1 1 1 2 1 1 1 1 1 52: 53:40: 29: 45: 48: 23: 25: 程序在运行了16次后停止运行。 停止时的种群 Weight 29 29 29 29 29 29 29 28 29 29 Value 78 78 78 78 78 78 78 64 78 78 染色体中的基因 0100110111 0100110111 0100110111 0100110111 0100110111 0100110111 0100110111 0100100111 0100110111 0100110111 停止时的HASH表 头结点索引 maxFitness Count Diff 单链表中的结点内容 0 12 78 64 9 1 1 1 78: 64: 即可知当前01背包问题的最优解为 X ={0,1,0,0,1,1,0,1,1,1} 对应的最优值是78,即当前能够装入背包的最大价值。
正在阅读:
遗传算法求解01背包问题09-19
华为视频会议系统设计方案04-07
摘柿子作文600字06-21
诗歌朗诵会主持词01-08
最新广交会实习报告12-12
白糖项目可行性研究报告06-11
全国中学生英语能力竞赛(NEPCS)初赛高二年级组试题05-24
2018新人教蜘蛛开店教学设计01-25
- 通信原理实验报告
- 2016年上半年安徽省临床医学检验技术中级技师职称试题
- 传智播客刘意老师JAVA全面学习笔记
- 星级酒店客房部保洁服务标准与工作流程操作规范 - PA新员
- 算法竞赛入门经典授课教案第1章 算法概述
- 《微信公众平台架起家校互通桥》结题报告
- 2018年宁夏银川市高考数学三模试卷(理)Word版含解析
- 大学生创业基础 - 尔雅
- 2016年6月英语六级真题写作范文3套
- 中国磁性材料纸行业专项调查与发展策略分析报告(2015-2020)
- 云南省2018届高三普通高中学业水平考试化学仿真试卷二Word版缺答案
- 窗函数法设计低通滤波器
- 第三章 绩效考评方法与绩效管理模式
- 高等数学教案
- 个人独资合伙企业习题及答案
- 小学语文沪教版三年级上册第六单元第30课《想别人没想到的》公开课优质课教案比赛讲课获奖教案
- 曳引钢丝绳及其他曳引系统校核计算 - 图文
- 淮阴工学院管理学期末试卷7 - 图文
- 受力分析方法(1)
- 2013-2014学年陕西省西安市西工大附小五年级(上)期末数学试卷及解析
- 求解
- 遗传
- 算法
- 背包
- 问题
- 西班牙大流感
- 主持稿
- 品牌策划报价单
- 承钢2#高炉停炉放残铁实践
- 资产评估师考试《资产评估》企业价值评估(4)
- 2011年注会《财务管理》考试真题及答案
- 绝望的主妇第一季第六集剧本
- 2019年最新电大专科《建筑构造》机考网考题库及答案备考试资料
- 水工钢筋混凝土结构学(第四版)考试试题及答案
- 2015年注册监理工程师继续教育公路工程(试题)
- 装修秘籍之验房装修房技巧集锦
- 从一类单调性问题看算法的优化(汤泽)
- 一个好的用例的表述要点
- 学校安全管理问题案例
- 八下unit3Where would you like to visit SectionA
- 河南省名校2011届高考考前仿真模拟卷(四)--理综 - 图文
- 思辨协会新生辩论赛活动策划案
- 关于举办武汉科技大学第五届环保创意大赛的通知
- PLC课程设计(1)
- 职业健康管理制度及操作规程