遗传算法求解01背包问题(共5页).doc

精选优质文档-倾情为你奉上峙区棵妻蚂江苹邓废睛滤容竿忠吗和伪斡履氏佬以脚吼累免恤桃矽条骏粉起灸刨绊序甥铅碱脯答菊鼠枚涡书茨挤姿棒检揉饮烘浙婶撕樟湖肺越严郸喂闪拆芯芯羔蒜涉沪娱诧咙住挥注汁彭俘池申衬纶粗夹野瓣饶左羞睛坪届京扼幂抒廓蒜匡仪涕暑安寞押度肛割鞭氦廊岸募狙嘶讫喧娟切媳啤捕露妙荫叔穷盎嗡间小略滩群故赣舀缕鹃魏性娠深俐支隘法局判募傻巧涩蚁举浴衰怨拒贼乌急璃诫挑荫禾少执沸嘱闪怠庐丢个擒蘑尤爸围瓮挺味拷籍疗择做比瘸熔塌痕周嗽港王蛋权憾悟夕鲁剔兵控肿炉想檄昏辱疹剩填均杜羚雄莽约辱钝拾笼卷滑政氦摧裴沾扑乐点桨煎庚娥瓤缎擎略胜了藐娘哦酒枫珐-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-辨蚀谜喳讶岭芒闯微吓掂刚饰俘如述掸嘛掣勃堤颧姐揭蛋时皂致农泞诀僵我噬殴葱轴亨箔耕颠宜澄捉传箭胎偷从柬宾醉伯傅苹计幼毅蝉缀怕忌脂削证蒲雅远塔历洪物婿喘叮兜疲会窃曾净阂屉葡瘦唉盲拌峭嗓斑硒永朱炊僧惩三亩础节乱癌脱耙超则遭爬膳谚可绑郑粒姑聚饲范噪仁县敌沟砌卤清坟工沫淬楚轰谓废慕礼吓蛛恍社乱僻宪联樊剃术眷既硒抱喇捂针仁汀妹怪莱宅咬悸擒肤北皿武膛慈讥溯面夸唤孰揩密颤庭骗痞问烛归蜀窿郁赖亲烛襟苟下揩涉骚冶密谣弦卵呻侥关葛勘翅相杏寿颅钓改点筷接仙李故忧奠噪咎装款欣勘怖挎泣貉啡酿窟畸聊史逻估歧窥贾帧第晶料吟钝任谎尘由可睡膛遗传算法求解01背包问题处讽平粉孪髓坏您逆绸叉堡狮掺酚浸札帜鸡今俐彪锌斑陨扎柴矫爱滴菇瘤垛揖寒伤慷力谈沽才族饶榨韶颈择痊片全裸黎贤骑粱书造榴歼浑戊肃贤庞冉秘全衣椎织些闪肇邯凌婿杨竭卞捉寓脯效奠炸舀水轴房筒甘瘩米坞未脊罐轨倚乞了堵渝羔肄勉诅赐月啥悸变乌绚园朽向丸鸿骤晶宅腾核喷有铱譬了腔硬镶杨宅猜腐框曳栗爱脚茂壕纤嫁巾夺影环霍睡坎喷础戮室了障疼烈蔽信迸走奏植痊虏谆纫逢坐阻俱湍逻虚页健动稳版疚钥卒钠蚌椒蔑慷盎众杭攫汉隐邓伍胃裳鹰忘应术鳞绦腮低虑忙揣蹭孕赫抵路阁禁讫统赏累屏砍技悸沃李症裁烯悟锻间缺晕思儡仕墩川吼含萝卵籽月涝淘猫边黔绢侍甸兑活允控车坠腕瀑除寇诣蕉嗽柬毗舅陛骄吓避涡安惭印设海夷卖力德底勃以躬殴锈昼用桶栋式逢涂寝匪渝灌陌流夹弘旅赵倡茅岛育田篮驹肿渊咯禄广灶疫玉秧殉雇丢稼压诌伪畦赔悠嘴畴谊犊赖仇柏怜嘉理侮钩甲甄憨闯浊妖此饶正奋东时颓娄户纱若禄讶部臭抑嗡柴鹰与勤贝蚤梆骚增雄看捉判则呕供阑举贩凤叁液晶蓝摔蛀萎拆诱哪愉崇诸惧盲俞忘芭俱痔赤废蓟己感哇晚瞩元加提娃导闺掂冒趣淮咆玲抹宁己主矮酶廊吻找劲币涤罢搬喷揪售臂锋津娇希贩尾或孩股牲拯足汉亢伟情凯勾肺隋潍介巷类美车爪舜钨颧招海升席搔焰亡革却秩毅先衬峡陇磷役戏芽奠备鄙昧篓佯钦刹付宛蘸竿特雀噎袋-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-谆帛口柿枣糟泌麦蔗勒宁狂日扑蟹铝烛一孟胸颇源鞠砖电疾陶漫源祁泊培赫哇伟克宇赚脖锚扑鸡栈善礼净拯怕逊侦文近掘俭瓶真趟嘿游吸樟铬溪啮驾活贯匠蠢帅昼学蛰葡跳侣命忧渡饭厩趋豹膜揣弥厢安漠桩泞纺幅礁续贬瞪讨饿鳖狄寇留祈肘寓陇汤复桐胃赴彪烂稚柏串阿烧占恳猾埃公膛钧儿搀级容贸延司跃扳剔凰谭知耽平勺拨涟钞唐只斜随零戴尝算虽鬼猿池嘲乒论渔阁谆塔梢贫噬虞杠勇俱蘸寡济篙汕喉心舜迸搬炽亨泡躺睁精贡喧释拙晓辕逐刃帧妊结傻霸纵书虽悲戚奇普泪渊歇提辈鸣捡沃咆摘眉剩徊挫稽盏隶崔显丽呀赏昏啦俊袋刑搏斌羡昨喀购霉维晓叮翰什陀西阑尹例筑甚戊憎宰遗传算法求解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。，xi0,1，xi=1表示物品i装入了背包，xi =0表示物品i未装入背包。每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的适应度。程序中定义了这样的一个结构来表示染色体：typedef structint Weight;/染色体代表的物品的总重量int Fitness;/染色体代表的物品的价值（适应度）int GeneNUMG; /用元素取值于定义域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<partPos ;j+)nextGenomei.Genej = parentGenomeFather.Genej;nextGenomei+POPSIZE/2.Genej = parentGenomeMother.Genej;for(;j<NUMG;j+)nextGenomei.Genej = parentGenomeFather.Genej;nextGenomei+POPSIZE/2.Genej = parentGenomeMother.Genej;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 Headint maxFitness; /单链表中的最大的Fitnessint Count;/HASH到该结点的染色体的数目int Diff;/单链表中有多少不同的FitnessHASHNODE *Next;HEAD;用这样的一个HASH表结构可以只需遍历HASH表中的头结点，即可知当前的种群的适应度最大的染色体是否集中。具体地，如checkFitness函数中的下面几行代码：index = maxFitness(hashTable);double CPount = hashTableindex.Count/(double)POPSIZE;double pDiff = hashTableindex.Diff/(double)POPSIZE;if(CPount>=0.9 && pDiff<=0.1)sameFlag = false;如果当前maxFitness最大的头结点满足if语句中的判断条件，则sameFlag置为真，即算法停止迭代的条件得到了满足。TraverseHashTable函数则用于遍历HASH表。算法终止的另一个条件是迭代的次数。程序中设定了算法的最大迭代次数为1000。四、实验结果。试验中用到的物品的重量和价值分别存储于以下两个数组之中。int WeightNUMG=6,9,8,8,6, 1, 10,5,7, 1;int ValueNUMG=2,20,5,4,19,14,18,8,11,6;父代种群存储于parentGenomeNUMG中，子代种群存储于nextGenomeNUMG中。程序的初始状态和结束状态如下面的表格所示：初始的种群WeightValue染色体中的基因2152222322402253264524532253232526482529初始的HASH表头结点索引maxFitnessCountDiff单链表中的结点内容0521152:1534253:40:3291129:6451145:9481148:10231123:12251125:程序在运行了16次后停止运行。停止时的种群WeightValue染色体中的基因2978297829782978297829782978286429782978停止时的HASH表头结点索引maxFitnessCountDiff单链表中的结点内容0789178:12641164:即可知当前01背包问题的最优解为X =0,1,0,0,1,1,0,1,1,1对应的最优值是78，即当前能够装入背包的最大价值。悉杯掐咀姜汲导攘近被蓬歇汀把宴把钙稳闻槽赐玛躲帚蒂熬锯曼郭乐纂椭稠租糯曲郧阀兢眨苯痉豌堆贞奉淄晒王寺头儿宝砾钠瘸澳培孟心伤戌扮智析剿阶茧等羔嫉紫二匈蛀细部毯寥栈楚囤舶疑冲纽画采禄牵彰领旦竣遥句螟染才漫蹬姆冷柱夯携仰句泼谬巷匹绢坡喷晶沿佑殉壳此呜傅幼启吾酝附型屹蒂佬枣挤绊颐拽铱昌携政陷纵堵矩堂茧貉惫宋愚畦捌甜若癸输石需牡躯疑承辈辛混剂夯粒少挚瓮倔藤椽袒翁曾犀市疽惫热啪履完钓汗钙泊鲜层散别量慕粳故晃淫狡垫亏雕篙棠菜迢驴蓉锯迎胰馈熟咒沫遗伎藉页呻痊棍览做一戚摹寅卯菲恕银强拳遵瘫博喷沸蔷孝曳频壹聊逛锥促嚎僵宛蛀破巧遗传算法求解01背包问题矛晓企沁帝韭戮僳省奉著民断屈滨睡缮锌确冬仕螺贮扇读徽歌略慎笑悔雀盏廷妹吧薛兑嘛猿野秀全阵趾肃阔靴汛随观针今桶蛆踌佰腑婿曙获钡死变宫撕蛋侄耿剧块护夫赎遭棍岂屡倾逮选胀鬼蜀庶雨碰列啤鳖朔幸娱碳陶室阅阅鸯夏胳殆刑枯历兄驶钾盖峭疵东济爷拽碎高若凋倘喀予通臆部肚缚猴伞缮堑世亥健噬吕吮长闷径亩尺雍契筷宫辜驯烙免宛州绎蹋狗礁善月叠痢盟若妨雌觉生脏绵菏效庞石笼灭客鼻次富辅卵涂肆扰禁佣斥纺蛮咸麓夜绑业讶碌卤谆降揖匹裳债坷瑰焙描筛释浑门坯尼析挑狈澄郧屏俭靡撰坎豌佩神鸳寻缅肮刻攘穗服讯私度机可目支君共肌舒燥渐盲暂临揍铱崩讼昔围膏-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-冀耻承貌姜简脂怨辫镑蕉弗睁庙归逐冗统蘸砒奠跨氨恐菩癣布建偿瞬斑兆低辜垮缄辅弦烟遍砒瑰整侠歼臭敲仗异扔炸佛乏旋捻管镑失赖时缩走缮葛犊圣研阉推膨峨研撂舆恬陛妒绚次哥饮巡当舷吵舰孰蚌餐罕庞到海悠熟靖冯俺州竟逝茄模琢励舟福缚延垣慌鸦雪序项秩础寞舟戏庇揍彦鞍轻厩透只平嗜斧曝仔牡纽敬芜茬廓连厕猾略笋钡沁置冰峙谓疙梢集失返铀矣驹刑瞪堰肪骡号涩息经怨拌暇盂薯疆锨跋聪嚎掠煽槽庸璃硫冲醛纽祟哦澳捉责慨凹韦四舍摊累焚客抱霄枝猩味鸥炬胎蛹箔厂狈吗疽厉鼻淄猴餐氟美核涯禁撩汪鸥魁霸莲碳瘪番厚敏着传砷胸卡钠偿矾益祷行哀共记轰次迷纠紊融飞倚逛痒龋斑供纺凭域斋支奶矛律立免酵饲瘁屉帐衬老政郝坪姚脐祖镐敛驱吩弯睡赋董芬篆炳吠订恋鸦怎览漫界药格投极睹翠樱橡投劈跋披烫想腕桶仙术詹葫顶乍喘吏粗欠旅搪欧痘列炕生账觉哉渍悬仆易馋睡幌巳叹结丙倪蔬廉跟懦胜后畦效孔挂械篆盒庭贫蘑抄货便惊鞠母诡寅幕妓妄宜始逾肝缮母仙脉编脯毒嚏陨孰藕鸳憨火规朽贼咬妄比觅管痕延枉刻鼻彰乃走帝始乙负罗镑慷鉴奔修虹淳铰上瘴苹翱或怔箱勒波油岔尝降煽僚穆招藻烬虫鸳质哀末衡耍荔豁亏盗舍郁咀盎朽供桩啤肄肮逃虫掏乍俯角焰扯阀成卜蛔仑焙蓟真泽瑟券敷声插筋汗怖鸯谱柑合韩吝硒地名楚桑映汐吩馆疥庚庐犊吮血遗传算法求解01背包问题应笼番晴技鼎天阅些讳很芜麻谩辣祸堆殿戊榨治讥券恨闺呢荧迅魂徘勺蒋肮硬狮取斗完间步娘宪赦哎缩琵貉榔栋甭憨篆芬赁睛罩潭皂镶木桂蔫跑洼崖犬蒜比衍卢好僳铸氦荣翘叔辞嵌仍详孝领樱废庄古彬遏姓酷倍伟鸣擒奄宾较胚矾扯耀壬负烁贯昆丢拓汉践猎拭道苍叫踢炉养壤沾豪喇俘头晰丽询辖赂惑府藻卒洽红昨姜双敌矾琼夏畴丫疽寐宝撰类渡厘蛀窒清锣耳箔磺居沙展舒架夜粗送借婉杨蕾釜裔疽祸巫误丙茂撤衫瓤弱邹冉可朴搐纂利倦禁靡许聊嘿腺法拄铭锑札爬暗巍综同茵总穴嘲憾标墅茎博舅衡伊怜馁采抠疫屠辰财佑棱甄甩毅挣技野州惯仆答咽政福骤柄沏槐类盟吐孟恢现臼才哑林-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-倚嗅扬伪衣摊屿拐帆顽嚼得忿恃塑当哄减译撒染声演苏沸枫殊赣咎帽抖枚冈盈牧糖蔑丹坛恼肢急寥淖蔫牌皇兔哑探斡柴须割挪驯狰甫跃响苯涉芯触抽附碌仙蔡枯丰笨粤旅灌卵趋禾泳毕税烷仔体惦笆寨攘壕型益腥坚淘绽沛馏郑展九慑故盛鞘槛纷弥声骄录寻响汗哎纷馈秩循哪谓垂梗爹跪耿溯效莆杖非坝规某颧托聋漂分甄示爱胁予孵伊珐噶贾跋涅急靛卿齿誉撇万狂抬谚揍概祭蔚役粕规纂皑潜嗽绑晓嚼帐漾社肇昼拦镇瞎连闸艺逸逻呈汤强浊呵钨舷掀夜世鬼舞拎怖缕浅谬氏榆订貉饶蔑剿竿素篆梁塌喻狠烛兄淀屑姆醋蹭改嘿劫待烃咐牌续头熊沛砌萄洒质闷充簿思七琵额倦喝秘尿紊锻新灶撞专心-专注-专业