29背包问题中的遗传算法变异算子研究

JIANGXIAGRICULTURALUNIVERSITY本科毕业论文（设计）题目：背包问题中遗传算法的变异算子研究学院：理学院姓名：学号：专业：信息与计算科学年级：2009级指导教师：职称：二〇一三年五月背包问题中遗传算法的变异算子研究I摘要背包问题是管理科学和计算机领域的NP难题,对于大规模问题,目前的主流算法是遗传算法等进化算法.而变异算子是遗传算法能否找到全局最优解的关键之一.但是目前专门针对背包问题的变异算子研究并不多.鉴此,本文旨在研究,具有不同变异算子的遗传算法在解0-1背包问题时的性能表现.本文首先介绍了0-1背包问题的数学模型及其求解的意义.然后,介绍了遗传算法的主要算子及其优缺点,并详细介绍了遗传算法的变异算子.本文通过对变异算子的不同改进,得到不同的遗传算法,并且将这些不同算法进行实验测试,以期得到具有最佳变异算子的遗传算法.最后通过数值实验,比较了不同变异算子的优缺点.基于0-1背包问题的仿真实验表明：不同变异算子会影响遗传算法的收敛速度和计算精度,在性能上各有优劣.关键词：遗传算法；变异算子；背包问题；MATLAB背包问题中遗传算法的变异算子研究IIAbstractKnapsackproblemisaNPhardproblemwhichiswidelyinvolvedinmanagementscienceandcomputerscience.Themostpopularalgorithmstosolvethelargescaleproblemsareevolutionaryalgorithms,suchasgeneticalgorithmandso.Itiswellknownthatthemutationoperatoristhekeyoperatorofthegeneticalgorithm.Buttherearefewliteraturesdedicatedtostudytheimpactofmutationoperatoringeneticalgorithmtosolvetheknapsackproblem.Inviewofthis,thispaperaimstostudytheperformanceofthegeneticalgorithmswithdifferentmutationoperatorinsolvingthe0-1knapsackproblem.Firstlythemathematicalmodelof0-1knapsackproblemanditssignificanceareintroduced.Then,theoperatorofgeneticalgorithmanditsadvantagesanddisadvan-tagesarediscussed.Withdifferentmutationoperatorsdesigned,fourgeneticalgorithmsarepresentedaccordingly.Finally,thenumericalexperimentswereconductedtotesttheperformanceofthedifferentalgorithm.Simulationresultsinsolvingthe0-1knapsackproblemsindicatethatdifferentmutationoperatorwillaffecttheperformanceofthegeneticalgorithminit’sconvergencespeedandcomputationalaccuracy.Keywords:geneticalgorithm；mutationoperator；knapsackproblem；matlab背包问题中遗传算法的变异算子研究III目录1背包问题.........................................................11.1背包问题的定义...............................................11.2背包问题的意义...............................................12遗传算法.........................................................12.1遗传算法.....................................................12.2遗传算法的优缺点.............................................22.3遗传算法的步骤...............................................22.4遗传算法流程图...............................................33问题假设及符号说明...............................................43.1问题假设.....................................................43.2符号说明.....................................................44遗传算法的主要算子...............................................44.1选择算子.....................................................44.2交叉算子.....................................................54.3变异算子.....................................................65数据测试.........................................................85.1算法测试规范.................................................85.2测试目的及实例数据...........................................95.3参数设置....................................................105.4运行环境....................................................105.5运行结果图..................................................115.6结果分析....................................................146结论............................................................15参考文献...........................................................16附录...............................................................17背包问题中遗传算法变异算子研究11背包问题1.1背包问题的定义背包问题(Knapsackproblem)是一种NP困难组合优化的问题.可描述如下：决策者有一个背包,其承重能力为W,有m件可选择物品,每个物品的质量和价值分别为iiVW和)m,,2,1i(,而决策者的目的则是在允许的承重范围之内,选出合理的物品,以使背包中的物品总价值得到最大化.本文中仅考虑0-1背包问题,即每种物品仅有一件,若物品i选入背包的数量描述为ix,则0-1背包问题可用数学规划模型进行如下表示：}1,0{xWwxvx)x(fmaxim1iiim1iii1.2背包问题的意义背包问题在现代理科学中具有重要的应用,是运筹学中的一个典型的NP优化难题,在实际生活中也有着及其广泛的应用背景.许多关于工业和金融的问题,都可以建立背包问题的数学模型,例如资源分配、投资决策、货物装载、网络资源分配、线性材料切割等都可归结为背包问题.因此,研究背包问题无论是在理论上还是在实际应用中都有着极其重大的意义.如今的社会,背包问题影响力愈来愈大,是现在数学问题不可忽视的一部分.2遗传算法2.1遗传算法在自然界中“物竞天择,适者生存”是一种永恒不变的规律,遗传算法就是据此而提出来的一种随机搜索算法.遗传算法起源于对生物系统所进行的计算机模拟.它是从问题的一组潜在解开始迭代寻优的算法.一个群体由一定数目的染色体组成.染色体是由编码形成的基因组成,所以在遗传算法初始阶段需要进行背包问题中遗传算法变异算子研究2编码格式的确定.遗传算法的编码主要有实数编码与二进制编码两种类型,本文中采用的即是二进制编码.生成初代群体之后,模拟生物解的适者生存、优胜劣带的机制,进行遗传操作,逐代演化,产生出更加适应环境的染色体.在每一代,根据问题可行域中个体的适应度大小选择优良个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出新的一代群体.这个过程将导致种群像自然进化一样使后生代种群比前代更加适应于环境,群体经过若干代,保留最适应环境的染色体,从而得到问题的最优解.2.2遗传算法的优缺点由于遗传算法是基于整个群体进行智能的优化算法,故而其具有良好的全局搜索能力,可以快速地将解空间中的全体解搜索得出,不易陷入局部解中；且由于内在并行性,可以方便地进行分布式计算,加快求解速度.与此同时,由于遗传算法是进行的群体优化,导致其局部搜索能力比较差,在算法执行后期的效率较低.在实际应用中,遗传算法容易产生局域收敛问题.而如何在选择出优良的个体的同时,还要维持群体的多样性,一直是遗传算法中较难解决的问题.2.3遗传算法的步骤选定编码格式：编码需具有完备性、健全性和非冗余性此三大特性.本文根据0-1背包问题的特性采取二进制编码,即0-1编码格式.初始群体的确定：随机的产生数量为n的长度为m的初始染色体,其中m为物品数量,每个染色体代表一种潜在可行解,这些染色体就是初始群体.适应度函数和适应值的设计：为了确定染色体的优劣,必须拥有合适的适应值规范,目标函数为适应值函数,并计算个体的适应值.确定选择的标准：挑选合理的选择算子,主要锦标赛选择、轮盘赌选择等算子,本文中根据背包问题的特性采用排序选择算子.产生新的群体：根据选择标准,当前群体淘汰劣质的染色体,并且同时复制优秀染色体补入群体,得到一个新的群体.交叉：将所有染色体进行两两不重复配对,进行交叉,得到新的染色体后形成新的群体,本文采用单点交叉.变异：变异是在小概率的情况下改变了染色体上的基因.终止条件：本文采用限制算法遗传代数为终止条件,当遗传代数达到限制遗传代数时,算法终止.背包问题中遗传算法变异算子研究32.4遗传算法流程图图2-1遗传算法流程图开始Gen=1编码产生初始群体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子根据适应度复制淘汰个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制复制个体替换淘汰个体交叉后添入新群体中变异后添入新群体中结果结果结果Gen=Gen+1输出结果终止YNYYYNNNPcPv背包问题中遗传算法变异算子研究43问题假设及符号说明3.1问题假设假设背包的空间足够大,可以装的下所有的物品,仅仅是重量承受有要求.假设所有的物品不重复,即没有相同的物品.每样物品数量仅有1个,即选入包中只能为0个或者1个.所有的染色体均为单倍体.3.2符号说明表1求解问题的符号说明符号说明Wmiwivnx)x(gixcpvpk背包的承