资源描述：
《一种基于模式替代的遗传算法解0_1背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第26卷第2期计算机应用研究Vol.26No.22009年2月ApplicationResearchofComputersFeb.20093一种基于模式替代的遗传算法解0/1背包问题1,212李康顺,贾玉珍,张文生(1.江西理工大学信息工程学院,江西赣州341000;2.中国科学院自动化研究所,北京100080)摘要:背包问题是一个典型的NP完全问题。提出一种基于模式替代的遗传算法解0/1背包问题思想,通过收集每代种群中最好的几个个体生成模式来引导种群的搜索方向,以提高遗传算法的搜索速度和寻找最优解的能力。通过仿真数值实验,将该方法与简单遗传算法、贪心算法计算结果比较分析,充分证
2、明了使用基于模式替代遗传算法来求解背包问题的有效性和实用性。关键词:背包问题;模式替代;遗传算法中图分类号:TP311文献标志码:A文章编号:100123695(2009)0220470202Geneticalgorithmwithschemareplacedforsolving0/1knapsackproblem1,212LIKang2shun,JIAYu2zhen,ZHANGWen2sheng(1.SchoolofInformationEngineering,JiangxiUniversityofScience&Technology,GanzhouJiangxi341000,
3、China;2.InstituteofAutoma2tion,ChineseAcademyofSciences,Beijing100080,China)Abstract:KnapsackproblemisatypicalNPcompleteproblem.Thispaperraisedgeneticalgorithmwithschemareplacedforsolving0/1knapsackproblem.Itleadedthesearchdirectionofthepopulationtoaschemabycollectingthebestseveralindi2vidual
4、sinpopulation.So,improvedthesearchingefficiencyandability.Atlast,gavethesimulationexperiment,andtheansweroftheknapsackproblemwhichwassolvedbysimplegeneticalgorithm,comparedgreedyalgorithmandgeneticalgorithmwithschemareplaced.Bythiscomparison,theadvantageswhichuseschemareplacedtosolveknapsackp
5、roblemisprovedtobeeffi2cientandpractical.Keywords:knapsackproblem(KP);schemareplaced;geneticalgorithm近年来,背包问题吸引了许多理论和实际工作者对此问题该问题的模型可以表示为下述0/1整数规划模型:的深入研究。在理论上尽管背包问题的结构简单,但它却具有nmaxf(x,x,⋯,x)=6px12niii=1组合爆炸的性质。在实际应用中,许多工业问题均可以用背包n6wx≤c问题来描述,如资金运算、货舱装载、存储分配等都是典型的应iiii=1目标函数:s.t[1]用例子。求解背包问题有许多
6、传统的算法,如贪心算法、动xi∈{0,1}(i=1,2,⋯,n)态规划算法、回溯法、分支限界法等,它们各自都存在一些其中:x为021决策变量,x=1时表示将物品i装入背包中,ii缺陷。x=0时则表示不将其装入背包中。i[2,3]遗传算法是Holland和他密西根大学的同事提出的以模式的基本理论自然选择和基因繁殖的思想为基础的一种高度并行、随机和自适应全局优化搜索算法。遗传算法一般在开始随机产生初始[5,6]1)模式(schema)它是基于三值字符集{0,1,3}所群体,然后不断地改进个体,以得到越来越好的结果。由于收产生的能描述具有某些结构相似性的0、1字符串集的字符串;敛速度和
7、寻找最优解往往是一对矛盾,基本遗传算法(SGA)常是一个描述字符串集的模板,该字符串中的某些位置上存在相表现为收敛速度慢,容易早熟、陷入局部最优解。本文提出了似性。以长度为5的串为例,模式31330描述了在位置2基于模式替代的思想,通过收集每代种群中最好的几个个体生为“1”及在位置5为“0”的字符串,即{01000,01010,01100,成模式来引导种群的搜索方向,提高了遗传算法的搜索速度和01110,11000,11010,11100,11110}。寻找最优解的能力。2)模式
