背包问题中的遗传算法变异算子研究(DOC)

1、JIANGXI AGRICULTURAL UNIVERSITY本科毕业论文（设计）题目：背包问题中遗传算法的变异算子研究学 院：_理学院_姓 名：_学号：_专 业：信息与计算科学_年 级：2009 级_指导教师： _职 称： _背包问题中遗传算法的变异算子研究I二一三年五月摘要背包问题是管理科学和计算机领域的NP 难题,对于大规模问题，目前的主流算法是遗传算法等进化算法.而变异算子是遗传算法能否找到全局最优解的关 键之一但是目前专门针对背包问题的变异算子研究并不多.鉴此，本文旨在研究,具有不同变异算子的遗传算法在解 0-1背包问题时的性能表现.本文首先介绍 了 0-1背包问题的数学模型及其求解

2、的意义.然后，介绍了遗传算法的主要算子及 其优缺点，并详细介绍了遗传算法的变异算子.本文通过对变异算子的不同改进，得到不同的遗传算法，并且将这些不同算法进行实验测试，以期得到具有最佳变异 算子的遗传算法.最后通过数值实验，比较了不同变异算子的优缺点.基于 0-1 背 包问题的仿真实验表明：不同变异算子会影响遗传算法的收敛速度和计算精度，在性能上各有优劣.关键词：遗传算法；变异算子；背包问题；MATLAB背包问题中遗传算法的变异算子研究iiAbstractKn apsack problem is a NP hard problem which is widely invo Ived in man

3、 ageme ntscie nee and computer scie nee. The most popular algorithms to solve the large scaleproblems are evolutionary algorithms, such as genetic algorithm and so. It is wellknown that the mutation operator is the key operator of the genetic algorithm. But thereare few literatures dedicated to stud

4、y the impact of mutatio n operator in gen eticalgorithm to solve the kn apsack problem .In view of this, this paper aims to study theperforma nee of the gen etic algorithms with differe nt mutatio n operator in solvi ng the0-1 kn apsack problem.Firstly the mathematical model of 0-1 knapsack problem

5、and its significanee are introduced. Then, the operator of gen etic algorithm and its adva ntages and disadva n-tages are discussed. With different mutation operators designed, four geneticalgorithms are prese nted accord in gly. Fin ally, the nu merical experime nts were conducted to test the perfo

6、rma nce of the differe nt algorithm. Simulatio n results in solvingthe 0-1 knapsack problems indicate that different mutation operator will affect theperformance of the genetic algorithm in it convergence speed and computati onalaccuracy.Key words :genetic algorithm；mutation operator； knapsack probl

7、em ；matlab背包问题中遗传算法的变异算子研究3目录1 背包问题. 11.1背包问题的定义. 11.2背包问题的意义. 12 遗传算法. 12.1遗传算法. 12.2遗传算法的优缺点 . 22.3遗传算法的步骤 . 22.4遗传算法流程图 . 33 问题假设及符号说明. 45.1问题假设. 45.2符号说明. 44 遗传算法的主要算子. 437,46,25,24,16,24,11,64,17,46,27,37,61,53,29,23,12,13,19,18,22,26,21,28,11,24,31,2选择算子437,46,25,24,16,24,11,64,17,46,27,37,61,

8、53,29,23,12,13,19,18,22,26,21,28,11,24,31,3交叉算子537,46,25,24,16,24,11,64,17,46,27,37,61,53,29,23,12,13,19,18,22,26,21,28,11,24,31,4变异算子65 数据测试. 81算法测试规范. 82测试目的及实例数据. 93参数设置. 104运行环境. 105运行结果图. 116结果分析. 146 结论. 15参考文献. 16附录. 17背包问题中遗传算法变异算子研究11背包问题7背包问题的定义背包问题(Knapsack problem 是一种 NP 困难组合优化的问题.可描述如下：

9、决 策者有一个背包，其承重能力为 W,有 m 件可选择物品，每个物品的质量和价值分 别为Wi和V,i =1,2. ,m),而决策者的目的则是在允许的承重范围之内，选出合理 的物品，以使背包中的物品总价值得到最大化.本文中仅考虑 0-1 背包问题，即每种 物品仅有一件，若物品 i 选入背包的数量描述为 Xi，则 0-1 背包问题可用数学规划 模型进行如下表示：mmax f (x)=送XiVii m览xi，wiWi壬Xi0,18背包问题的意义背包问题在现代理科学中具有重要的应用，是运筹学中的一个典型的 NP 优化难题,在实际生活中也有着及其广泛的应用背景.许多关于工业和金融的问题，都可以建立背包问

10、题的数学模型，例如资源分配、投资决策、货物装载、网络资 源分配、线性材料切割等都可归结为背包问题.因此,研究背包问题无论是在理论 上还是在实际应用中都有着极其重大的意义.如今的社会，背包问题影响力愈来 愈大，是现在数学问题不可忽视的一部分.2遗传算法2.1 遗传算法在自然界中“物竞天择，适者生存”是一种永恒不变的规律，遗传算法就是 据此而提出来的一种随机搜索算法.遗传算法起源于对生物系统所进行的计算机 模拟.它是从问题的一组潜在解开始迭代寻优的算法.一个群体由一定数目的染 色体组成.染色体是由编码形成的基因组成，所以在遗传算法初始阶段需要进行 编码格式的确定遗传算法的编码主要有实数编码与二进制

11、编码两种类型，本文 中采用的即是二进制编码背包问题中遗传算法变异算子研究2生成初代群体之后，模拟生物解的适者生存、优胜劣带 的机制,进行遗传操作，逐代演化，产生出更加适应环境的染色体在每一代,根据 问题可行域中个体的适应度大小选择优良个体，并借助于自然遗传学的遗传算子 进行组合交叉和变异，产生出新的一代群体.这个过程将导致种群像自然进化一 样使后生代种群比前代更加适应于环境，群体经过若干代，保留最适应环境的染 色体,从而得到问题的最优解.1.8遗传算法的优缺点由于遗传算法是基于整个群体进行智能的优化算法，故而其具有良好的全局 搜索能力,可以快速地将解空间中的全体解搜索得出，不易陷入局部解中；且

12、由于 内在并行性，可以方便地进行分布式计算，加快求解速度.与此同时，由于遗传算法 是进行的群体优化，导致其局部搜索能力比较差，在算法执行后期的效率较低.在 实际应用中，遗传算法容易产生局域收敛问题.而如何在选择出优良的个体的同时 还要维持群体的多样性，一直是遗传算法中较难解决的问题.1.8遗传算法的步骤选定编码格式：编码需具有完备性、健全性和非冗余性此三大特性.本文根据 0-1 背包问题的特性采取二进制编码，即 0-1 编码格式.初始群体的确定：随机的产生数量为 n 的长度为 m 的初始染色体，其中 m 为物品数量，每个染色体代表一种潜在可行解，这些染色体就是初始群体. 适应度函数和适应值的设

13、计： 为了确定染色体的优劣，必须拥有合适的适 应值规范，目标函数为适应值函数，并计算个体的适应值.确定选择的标准：挑选合理的选择算子，主要锦标赛选择、轮盘赌选择等 算子,本文中根据背包问题的特性采用排序选择算子.产生新的群体：根据选择标准，当前群体淘汰劣质的染色体，并且同时复制 优秀染色体补入群体，得到一个新的群体.交叉：将所有染色体进行两两不重复配对，进行交叉,得到新的染色体后形 成新的群体，本文采用单点交叉.变异：变异是在小概率的情况下改变了染色体上的基因.终止条件：本文采用限制算法遗传代数为终止条件，当遗传代数达到限制遗 传代数时，算法终止.背包问题中遗传算法变异算子研究32.4遗传算法

14、流程图图 2-1 遗传算法流程图背包问题中遗传算法变异算子研究43问题假设及符号说明问题假设假设背包的空间足够大，可以装的下所有的物品，仅仅是重量承受有要求假 设所有的物品不重复，即没有相同的物品每样物品数量仅有 1 个,即选入包中只 能为 0 个或者 1个.所有的染色体均为单倍体.符号说明表 1 求解问题的符号说明符号说明W背包的承重能力m可以选择的物品数量wi第 i 个物品的重量Vi第 i 个物品的价值n种族的染色体数量大小T x染色体的向量表示g(x)适应函数Xi第 i 个染色体Pc染色体发生交叉的概率Pv染色体发生变异的概率k染色体交叉位点4遗传算法的主要算子选择算子选择,是将群体中的

15、适应度低的染色体替换为适应度高的染色体的操作过程 , 它是遗传算法群体的整体优化的基础，可以使群体最优解越来越趋近于问题的理 论最优解.目前,主要的选择算子包括适应值比例选择、Boltzmann 选择、排序选背包问题中遗传算法变异算子研究5择、联赛选择、精英选择、稳态选择.本文中采用的是排序选择，排列选择是将当 代群体的染色体按照适应值排列，淘汰适应值低的染色体，并补入适应值高的染 色体.对于一个确定好且数量为 n 的群体,是由多个染色体组成，可用向量描述 佝&,aj ,根据适应值函数g(x)可得到第 i 个染色体的适应值 rg(a),适应 值函数表达式可用如下表示：mf(a) -fm

16、in， f (a) -fmin0 且 2 4 Wj= Wg(a) Ty，9 其他其中 fmin为当前群体中染色体对应的方案价值的最小值适应值得出后，即可进行排序选择算子操作，最终得到新的群体，用图解表示则 可用下图表示：图 4-1 排序选择算子示意图图 4-1 表示当前群体内有三条染色体，经过选择算子后选择后，淘汰适应值仅 有 4的染色体 01100110，并将适应值最高为的染色体 10011110 补入至淘汰染色 体的相应群体位置，最终得到一个新的群体交叉算子交叉，是进化算法中的遗传算法所独有的原始性特征，它是模仿自然界的有性 繁殖时的基因重组过程，将当代原有的优良基因遗传给下一代个体，并生

17、成包含更 复杂基因结构体的新个体一般，交叉操作会经过下列几个步骤：从交配池中随机选出不重复的交配个体根据交叉概率 Pc确定是否进行交叉操作，形成新的染色体进行交叉操作，将配对染色体上的对应基因进行交换，形成新的染色体.交叉分为单点交叉，两点交叉,多点交叉和一致交叉等形式单点交叉是最为 基础的交叉方式.首先需要选出两条不同的染色体，检验交叉概率后，成功后随机 在某一基因位点，染色体的对应基因片段进行互换，得到两条新的染色体.本文中 采用的是单点交叉方法，可用图解表示：适应值：4适应值：9适应值：10选择1101011011010110适应值：10适应值：9适应值：1010011110 10011

18、11001100110 10011110背包问题中遗传算法变异算子研究6图 4-2 单点交叉示意图图 4-2 表示染色体 01001011 与 11101001 在 Pc=0.8 概率下 住成随机数 r0.8 后,随机生成染色体交叉位点 k 为 4,最终在此位基因发生单点交叉，形成两条新的染色体 01001001 与 11101011.由于交叉算子有效的增强了群体之间的染色体的相互联系，使基因的流动性 得到提高,即群体的染色体保证了多样性，能够有效防止遗传算法的局域收敛，加 强了遗传算法的全局搜索能力，在遗传算法中扮演一个十分重要的角色.变异算子变异操作是模拟自然界生物体进化中的染色体上某位基

19、因发生的突变，从而改变染色体的结构和物理性状的现象.一般遗传算法中，采用的是根据变异概率 Pv随机对某位基因进行变异.本文中,主要研究变异算子的性质，在整个遗传算 法框架内嵌入不同的变异算子，从而得到不同的遗传算法.然后通过背包问题实 例测试各个具有不同变异算子的遗传算法，得到每种变异算子的优缺点，故重点 进行介绍变异算子的性能优劣.关于二进制的变异算子，本文中列举了四种变异 算子形式，四种变异算子进行变异的流程图解可用如下图表示：第一种变异算子，是对群体中的每一条染色体的每一位基因进行变异，此变 异算子广泛应用于各个遗传算法的变异算子之中，是最基本最常用的变异算子.例如图 4-3，当物品数

20、m=8 时,染色体 10110101 进行变异概率 pv=0.02的变 异，生成 m 个服从0,1的均匀分布的随机数，最终得到一个随机数集合r,r=0.01,0.5,0.15,0.06,0.5,0.4,0.9,0.8判断其每个元素是否小于 Pv,若小于，则 表明此元素对应的基因发生了变异，进行基因取反操作，如上述集合 r 可知染 色体第 1位基因发生变异，得到新的染色体 00110101.0100100111101011r0.8图 4-3 第一种变异算子示意图背包问题中遗传算法变异算子研究7第二种变异算子，此变异算子是基于第一种变异算子的计算量过高而进行改 良得到.它首先需要得到一条染色体的整

21、体变异概率p, P 胡_(1 _pv)m,然后对每条染色体进行如下操作：生成一个满足0,1均匀分布的随机数 r,若 rP, 则表明此染色体可能发生变异，然后对每位基因进行如下操作：生成一个满足 0,1均匀分布的随机数 s 当 spv时,表明此位基因会发生变异,进行取反操作. 此变异算子最终使得原本需要 m n 次的计算量改良降为P m n的计算量. 如：图 4-4,当物品数 m=8,pv=0.02 时,对染色体 10110101 进行变异操作，生成 随机数为 r,当 rP 后,生成一组随机数集合 S=0.5,0.3,0.6,0.015,0.7,0.8,0.4,0.9, 表明第 4 位基因发生变

22、异，最终得到新的染色体 10100101.图 4-4 第二种变异算子示意图第三种变异算子与第一、二种变异算子相比，此算子更加简化了算法量此 算子第一步与上述第二种变异算子相同，首先需要求出一条染色体的变异概 率 P,然后对每条染色体进行如下操作：生成一个满足0,1均匀分布的随机数 r,若 rP 则表明此染色体发生变异：确定基因变异位，为了计算量的减少，此 变异算子采用连续变异基因位的方法，即将 k 个连续的基因进行变异，为避免 一条染色体变异的基因个数不会过多，导致算法易陷入局部解之中，所以在 算子中添加了一个约束条件，使每条染色体基因变异个数不能超过一条染色 体基因变异的期望值，即 X m,

23、然后进行基因片段取反，得到一条新的染色 体.通过此算子，可使得算法量将降低为P m k.图 4-5,染色体1011010111 在 Pv=0.2 的概率下,通过随机数 r 判断染色体发生变异后，随机生成两个基 因位点 a=3,b=4,确定出变异基因片段为 3 至 4 位基因,最后进行基因取反操作 得到新的染色体 1000010111.10110101111011010111a=3,b=41C00Q1O111rP图 4-5 第三种变异算子示意图第四种变异算子，它是基于第三种变异算子进行改良，首先需要求出一条染色体的变异概率 P,然后对每条染色体进行如下操作：生成一个满足0,1均匀 分布的随机数

24、r,若 rP 则表明此染色体发生变异：，进行变异操作：确定基因变异位,为了计算量的减少，此变异算子采用连续变异基因位的方法，即将 k 个连续的基因进行变异，为避免一条染色体变异的基因个数不会过多，导致 算法易陷入背包问题中遗传算法变异算子研究8局部解之中，所以在算子中添加了一个约束条件，使每条染色体 基因变异个数不能超过一条染色体基因变异的期望值Pvm ,确定出变异基因片段后,选出当前群体的最优染色体，将此基因片段的基因变异为最优染 色体相应基因片段信息，最终形成一条新的染色体图 4-6,染色体 1011010111 在 Pv=0.2 的概率下,通过随机数 r 判断染色体发生变异后,随机 生成

25、两个基因位点 a=5,b=6,确定出变异基因片段为 5 至 6 位基因，当代群体的 最优染色体为 1100011001 变异后得到新的染色体 1011110111.最优染色体：110011100110110101111011010111a=5,b=61011110111rP图 4-6 第四种变异算子示意图5数据测试算法测试规范编码规范，遗传算法中，编码一般需要具备三大特性：完备性、健全性、非冗 余性.完备性：问题空间中的所有可行解均可成为一条染色体的表现型.健全性：每一种染色体必须对应问题空间中的某一个潜在可能解非冗余性：染色体与问题空间中的可能潜在解必须一一对应.由于每种物品数量仅有一个，且

26、 只分为选入背包与不选入背包两种情况，故可用二进制进行编码例如对 m=10 的情形，染色体 1011010111 表示第 1,3,4,6,8,9,10 个物品放入背包之中，其它物品则不放入背包之中初始群体,初始群体的产生一般通过随机生成足够数量且合格的染色体随机生成一条染色体后，检验重量是否合格，失败后则重新随机生成一条染色 体,直到生成了一条合格的染色体并补入进初始群体中.一直到初始群体的 大小达到了指定的数量为止，否则继续生成染色体.终止条件,遗传算法作为一种迭代式算法，必须要确立一个明确的终止条件，用以终止算法，输出最终结果.一般而言，遗传算法有两种判断算法是否终止 的方法：设定最大遗传

27、代数，此方法简单，但结果不够精确；通过群体的收敛 程度判断,通过计算群体中的基因位相似度进行判断本文中采用设定遗传 代数作为算法终止条件，当遗传代数达到设定数值时，算法终止,输出最优 解.背包问题中遗传算法变异算子研究9相似度计算方法：首先计算群体中所有染色体第一位基因两种基因的个数，取其最大值，将其除以群体染色体个数，得到第一位基因相似度，类似,求取接下来的每一位 基因的相似度，将所有的相似度累加，除以染色体的基因总位数，得到的就是 基因相似度，最终通过确定此值是否满足条件而确定该如何执行下一步操作.1m基因相似度maxCio，5/n,其中 m 为基因的总位数,cl0表示所有染色mi仝体中第

28、 i 位基因为 0 的染色体个数,ci1表示所有染色体中第 i 位基因为 1 的染色体个数,n 表示群体中的染色体个数.例如染色体 1010、1110 0111 的相似 度为(2 23 2)/(4 3) =0.75.测试目的及实例数据本文旨在通过不同的实例测试使用不同变异算子的遗传算法求解背包问题 时性能的差异，最终确定选择何种变异算子的遗传算法解决背包问题的效果达到 最佳.例 1物品数量为 m=20,质量价值分别如下：Weight=3,12,5,4,7,2,1,4,15,9,5,11,3,10,8,9,2,6,5,4Value=24,17,11,8,15,25,33,29,18,20,15,

29、31,10,21,18,19,17,22,14,11物品总重量为 125,背包最大承重为 60,理论最优解为 262例 2物品数量为 m=35,质量价值分别如下：Weight=15,10,11,17,10,9,15,15,14,18,21,17,6,15,7,9,4,15,17,11,10,9,15,14,18,21,17,10,11,17,7,9,14,11,4Value=37,61,53,33,43,36,37,46,25,24,16,24,11,64,17,46,27,37,61,53,29,23,12,13,19,18,22,26,21,28,11,24,31,25,24物品总质量为

30、443,背包最大承重为 200,理论最优解为 729例 3物品数量为 m=50,质量价值分别如下：Weight=5,13,14,15,7,9,4,15,17,11,10,9,15,14,18,21,17,6,7,10,7,9,14,11,4,16,15,10,11,17,7,9,14,11,4,16,15,10,11,17,10,9,15,14,18,21,17,6,7,10背包问题中遗传算法变异算子研究10Value=16,24,11,64,17,46,27,37,61,53,29,23,12,13,19,18,22,26,21,28,11,24,31,33,43,36,37,46,25,2

31、4,16,24,11,64,17,46,27,37,61,53,33,43,36, 37,46,25,24,16,24,11 物品总重量为 592,背包最大承重为 300 理论最优解为 1088.例 4物品数量为 m=100，质量价值分别如下：Weight=5,7,9,4,15,17,11,10,9,15,14,18,21,17,6,7,10,7,9,14,11,4,16,15,10,11,17,7,9,14,11,4,16,15,10,11,17,10,9,15,15,14,18,21,17,6,15,7,9,4,15,17,11,10,9,15,14,18,21,17 ,10,11,17,

32、7,9,14,11,4,16,15,11,4,9,14,11,4,16,15,10,11,10,9,15,14,18,21,17,10,11,17,7 ,9,14,11,4,16,15,11,4,9Value=16,24,11,64,17,46,27,37,61,53,29,23,12,13,19,18,22,26,21,28,11,24,31,33,43,36,37,46,25,24,16,24,11,64,17,46,27,37,61,53,33,43,36,3ed-a706-a729cfb06169-Numbered_9aa8d093-e259-4164-9c5,24,16,24,11,

33、64,17,46,27,61,46,27,37,61,53,33,43,36,37,46,25,24,11,64,17,46,27,37,61,53物品总重量为 1191，背包最大承重为 600,理论最优解为 2267参数设置表 2 本文算法参数选择参数值变异概率 Pv0.02交叉概率 Pc0.8群体大小 n150算法执行次数25终止遗传代数100物品数量20-100运行环境操作系统：64 位 Windows7 旗舰版处理器：In tel? Core? is-2350M CPU 2.30GHz内存：4Gb,3.82Gb 可用背包问题中遗传算法变异算子研究11运行结果图例 1 结果图表以及分析：

34、表 3 例 1 算法平均所用时间、背包内最高价值、平均价值、最低价值变异算子编号算法平均时间（s）最高价值平均价值图 5-1 例 1 最优解背包价值箱图图 5-2 例 1 最优解背包价值标准差图在求解算例一时，根据表 3 中的算法平均时间，在四种变异算子中，第二、三种 变异算子的算法平均耗时较短，使用第一、四种变异算子的算法耗时较长，其中使 用第三种变异算子的遗传算法耗时最短，可最快得到遗传算法结果使用第一种变 异算子的遗传算法耗时最长结合图 5-1、5-2 以及表 3,四种变异算子中使用第一、二种变异算子的遗传 算法精确度较高，使用第三、四种变异算子的遗传算法精确度较低其中使用第一种变异算子

35、的遗传算法的精确度最高，可最精确的得到背包问题的理论最优值使 用第四种变异算子的遗传算法精确度最低，不利于精确获得问题理论最优解因此,从遗传算法的计算速度上看，使用第三种变异算子的遗传算法更好获取 到算法结果；从算法的精确度和稳定性看，则应当选取第一种变异算子，可更加精 确稳定的获得算法结果；综合考虑计算速度和精度，则应当使用第二种变异算子, 可快速获得问题最优解的同时能保证足够的精确度以及稳定性最低价值5In出I2.0286262261.322581.8801262261.202581.8402262259.962551.9157262258.36254丄1234变异尊子编号娈异崖子编号2背

36、包问题中遗传算法变异算子研究12例 2 结果图表以及分析:表 4 例 2 算法平均所用时间、背包内最高价值、平均价值、最低价值变异算子编号算法平均时间（s）最高价值平均价值7QQ -1234变异算子编号图 5-3 例 2 最优解背包价值箱图图 5-4 例 2 最优解背包价值标准差图在求解算例二时，根据表 4 中的算法平均时间，在四种变异算子中，使用第三种变异算子的遗传算法平均耗时最短，所以使用此变异算子的遗传算法可最快速的 获得算法的结果值使用第一变异算子的算法耗时最长，使用二、三种变异算子的 遗传算法则耗时较短结合图 5-3、5-4 以及表 4,四种变异算子中使用第一、二种变异算子的遗传 算

37、法的算法精确度较高，使用第四种变异算子的遗传算法的算法精确度最低其中使用第二种变异算子的遗传算法的精确度最高，可最精确的得到背包问题的理论最优值.使用第四种变异算子的遗传算法精确度最低，不利于精确获得问题理论最 优解.因此,从遗传算法的计算速度上看，使用第三种变异算子的遗传算法更好获取 到算法结果；从算法的精确度和稳定性看，则应当选取第二种变异算子，可更加精 确稳定的获得算法结果；综合考虑计算速度和精度，则应当使用第二种变异算子, 可快速获得问题最优解的同时能保证足够的精确度以及稳定性.最低价值7In出I2.3474729724.807192.1409729725.727181.9850729

38、723.047152.1040729714.926953背包问题中遗传算法变异算子研究13例 3 结果图表以及分析:表 5 例 3 算法平均所用时间、背包内最高价值、平均价值、最低价值变异算子编号算法平均时间（s）最高价值平均价值最低价值背包问题中遗传算法变异算子研究14In出I2.566510881076.210512.363810871077.110622.060410871057.310322.179010741060.610274 2 O 8- C1.522.53娈异算子编号1234寰畀算子编号图 5-5 例 3 最优解背包价值箱图图 5-6 例 3 最优解背包价值标准差图在求解算例三

39、时，根据表 5 中的算法平均时间，在四种变异算子中，使用第三、四种变异算子的遗传算法平均耗时较短，可较为快速的获得算法的结果值使用第 一变异算子的遗传算法耗时最长，其中使用第三种变异算子的遗传算法耗时最短结合图 5-5、5-6 以及表 5,四种变异算子中使用第一、二种变异算子的遗传 算法的算法精确度较高，使用第三、四种变异算子的遗传算法的算法精确度较低 . 其中使用第二种变异算子的遗传算法的精确度最高，可最精确的得到背包问题的理论最优值使用第三种变异算子的遗传算法精确度最低，不利于精确获得问题理 论最优解因此,从遗传算法的计算速度上看，使用第三种变异算子的遗传算法更好获取 到算法结果；从算法的

40、精确度和稳定性看，则应当选取第二种变异算子，可更加精 确稳定的获得算法结果；综合考虑计算速度和精度，则应当使用第二种变异算子, 可快速获得问题最优解的同时能保证足够的精确度以及稳定性J .1 JI J3.5背包问题中遗传算法变异算子研究15例 4 结果图表以及分析:表 6 例 4 算法平均所用时间、背包内最高价值、平均价值、最低价值变异算子编号算法平均时间（s）最高价值平均价值图 5-7 例 4 最优解背包价值箱图图 5-8 例 4 最优解背包价值标准差图在求解算例四时，根据表 6 中的算法平均时间，在四种变异算子中，使用第三、四种变异算子的遗传算法平均耗时较短，可较为快速的获得算法的结果值使

41、用第 一、二变异算子的遗传算法耗时较长，其中使用第三种变异算子的遗传算法耗时 最短,使用第一种变异算子的遗传算法耗时最长结合图 5-7、5-8 以及表 5,四种变异算子中使用第二种变异算子的遗传算法 的算法精确度最高，可最为精确的获得问题的理论最优解，使用第三、四种变异算 子的遗传算法的算法精确度较低使用第四种变异算子的遗传算法精确度最低，不 利于精确获得问题理论最优解因此,从遗传算法的计算速度上看，使用第三种变异算子的遗传算法更好获取 到算法结果；从算法的精确度和稳定性看，则应当选取第二种变异算子，可更加精 确稳定的获得算法结果；综合考虑计算速度和精度，则应当使用第二种变异算子, 可快速获得

42、问题最优解的同时能保证足够的精确度以及稳定性结果分析最低价值In出I3.283422232187.421443.149422642207.721572.236722442165.120812.375022092148.0205842Q-1JJL11.522.533.54变异夏子编号205 CO2O&J2背包问题中遗传算法变异算子研究16通过上述的四则算例的结果分析，使用第一、二种变异算子的遗传算法在算法结果的精确度以及稳定性上有着较为良好的优势；而使用第三、四种变异算子的遗传算法在算法的运行速度上有着较为良好的优势 总体说来，当从算法的计 算速度上考虑，应当使用第三种变异算子最优，可更

43、快的获得算法的结果；从算法 的结果精确度及稳定性上考虑，使用第一种变异算子可使遗传算法效果达到最 优；综合算法的速度与精确度，则应当选取第二种变异算子，可使算法的效益比率 最高,可较快得到结果的同时获得较为精确的结果6结论遗传算法是一种具有定向制导的随机搜索技术，其定向制导的原则是：导向 以高适应度模式为祖先的“家族”方向,为了保证群体的多样性，防止算法陷入举 步最优解，引入了变异算子.采用二进制编码的遗传算法，其变异算子比较单调，且没有相关文献系统地分析各类变异算子对遗传算法影响，故本文设计了四种的 变异算子，并通过 0-1 背包问题实例的仿真实验结，比较了个变异算子的优劣基 于第一、二种变

44、异算子的算法精度高，更稳定,而基于第三、四种变异算子的算法 收敛速度更快参考文献17参考文献d5-bfb8-06a74fa916dc-Numbered_39365a4d-fe56-4491-b3fb-bfDuane Hanselman、Bruce Littlefield 著,朱仁峰译制版精通 Matlab7,清华大学出版社2006年出版,p27-29 p317-321d5-bfb8-06a74fa916dc-Numbered_39365a4d-fe56-4491-b3fb-bf 李敏强、寇纪淞等遗传算法的基本理论与应用科学出版社 2002 版,p27-45、p47-48d5-bfb8-06a7

45、4fa916dc-Numbered_39365a4d-fe56-4491-b3fb-bf 万福永、戴浩晖等著，数学实验教程(Matlab 版)科学出版社 2006 版,p169-176d5-bfb8-06a74fa916dc-Numbered_39365a4d-fe56-4491-b3fb-bf 遗传学编写组遗传学北京：中国大百科全书出版社，1983张文修，梁怡遗传算法的数学基础 M 1 西安：西安交通大学出版社，2001.王小平，曹立明遗传算法一一理论、应用与软件实现M 西安：西安交通大学出版社,2002. 攀 戀 挀戀昀昀 一甀洀戀攀爀攀搀开搀攀愀攀愀戀 戀 昀挀攀搀 一甀洀戀攀爀攀搀开搀

46、昀攀搀 戀 34079233569 愀愀 戀攀昀搀昀攀 一甀洀戀攀爀攀搀开搀攀攀昀 昀昀愀 戀 愀攀国良，王煦法，庄镇泉，王东生遗传算法及其应用M 人民邮电出版社，2001. 攀 戀 挀戀昀昀 一甀洀戀攀爀攀搀开搀攀愀攀愀戀 戀 昀挀攀搀 一甀洀戀攀爀攀搀开搀昀攀搀 戀 34079243569 愀愀 戀攀昀搀昀攀 一甀洀戀攀爀攀搀开搀攀攀昀 昀昀愀 戀 愀攀永兵，王斌，张永飞等基于遗传算法的背包问题求解.大理学院学报，2005,4(5):2426 攀 戀 挀戀昀昀 一甀洀戀攀爀攀搀开搀攀愀攀愀戀 戀 昀挀攀搀 一甀洀戀攀爀攀搀开搀昀攀搀 戀 34079253569 愀愀 戀攀昀搀昀攀 一甀洀戀

47、攀爀攀搀开搀攀攀昀 昀昀愀 戀络资源：http:/ ; http:/ nNu mber=150; %群体大小n=25; %每种问题执行次数 nfor i=1:ny1(i,1),z1(i,1)=Mai n( lssueMatrix,MaxValue,pc,pv,Populatio nNu mber,1); % 算法终止时的遗传代数以及最优解y2(i,1),z2(i,1)=Ma in (lssueMatrix,MaxValue,pc,pv,Populatio nNu mber,2);y3(i,1),z3(i,1)=Ma in (lssueMatrix,MaxValue,pc,pv,Populati

48、o nNu mber,3);y4(i,1),z4(i,1)=Ma in (lssueMatrix,MaxValue,pc,pv,Populatio nNu mber,4); end figure;var1(1)=mea n( y1);var1(2)=mea n(y2);var1(3)=mea n(y3);var1(4)=mea n(y 4);plot(1:1:4,var1,o);%绘制平均算法终止所用时间图title(平均算法终止所用时间图);xlabel(变异算子编号);ylabel(时间);figure;boxplot(z1,z2,z3,z4); %绘制最优结果值的箱图title(遗传算法

49、最终结果价值箱图);xlabel(变异算子编号);ylabel(结果值);附录1 主程序测试程序clear all; %清除缓存lssueMatrix=; %MaxValue=600; %pc=0.8;%pv=0.02;%重量价值关系矩阵背包容量交叉概率单个基因变异概率获取附录19figure;var2(1)=std(z1,1);var2(2)=std(z2,1);var2(3)=std(z3,1);var2(4)=std(z4,1);plot(1:4,var2,o);%绘制最优结果值的标准差图title(遗传算法最终结果价值标准差图);xlabel(变异算子编号);ylabel(标准差);执

50、行主程序function y,z=Main(lssueMatrix,MaxValue,pc,pv,PopulationNumber,action)global Gen; % 遗传代数,初始为 0global Variatio nCou nt %染色体发生变异的次数global CrossCou nt %染色体发生交叉的次数Gen=0; %初始化计数器global Variatio nCountglobal CrossCo untglobal Codi ngLe ngth %定义编码长度global Population %定义种群Variati onCoun t=0;CrossCo un t=

51、0;a=size(IssueMatrix);Codi ngLe ngth=a(1,2);In itPopulatio n( lssueMatrix,MaxValue,Codi ngLe ngth,Populatio nNu mber); %初始化种群Gen=1;time=0;tic;%计时开始while (GenMaxValue %判别是否合格y=GetCodi ng(lssueMatrix,MaxValue,Codi ngLe ngth); %不合格重新获取end3 数据统计程序计算重量function y=Co un tWeight(lssueMatrix,Codi ngMatrix,Co

52、d in gLe ngth)y=0;for i=1:Cod in gLe ngthy=y+lssueMatrix(1,i)*Codi ngMatrix(1,i); %累加重量end计算价值function y=CountValue(lssueMatrix,CodingMatrix,CodingLength)y=0;for i=1:Codi ngLe ngthy=y+lssueMatrix(2,i)*Codi ngMatrix(1,i); %累加价值end相似度计算function y=Detectio n( Populatio n,Codi ngLe ngth,Populatio nNu mb

53、er) %计算相似度s=0;生成编附录22for i=1:Cod in gLe ngtha=sum(Populatio n(1:Populatio nNu mber,i); %每位基因的相似个数if amaxvalue )&(b=MaxValue) %当满足重量条件时才选入最大值之中maxvalue=a;maxnumber=i; %保存最大值的染色体代号,方便复制endendy=Populati on( max nu mber,:);选择算子程序function SelectF un ctio n(lssueMatrix,MaxValue,Codi ngLe ngth,Populati

54、o nNu mber)global Populati on;maxnumber=0; %设定数据，保存当前群体最优解信息for i=1:Populatio nNu mber %得到最最优染色体信息v=Co un tValue(IssueMatrix,Populati on (i,:),Codi ngLe ngth);w=Co un tWeight(lssueMatrix,Populatio n(i,:),Cod in gLe ngth);if w0); %获取三个合格的最低价值min value2=min( y(fi nd(y min valuel);min value3=min( y(fi

55、nd(y min value2);x=0;for i=1:Populatio nNumber %复制淘汰相应染色体if y(i)=0|y(i)=min value1|y(i)=min value2|y(i)=min value3Populati on (i,:)=Populati on( max nu mber,:);x=x+1;endend附录 5:交叉算子程序程序 1 :交叉程序function CrossF un cti on( Array,Codi ngLe ngth,pc,Populatio nNu mber)global CrossCo unt;global Populati on

56、;for i=1:2:Populatio nNu mberif ran d(1)=pc %交叉概率CrossPoi nt=fix(Codi ngLe ngth*ra nd(1)+1; %随机生成交叉位点a=Populatio n(Array(i),CrossPoi nt:Codi ngLe ngth);%保存染色体片段信息，便于交换片段Populati on( Array(i),CrossPo in t:Codi ngLe ngth)=Populati on( Array(i+1),CrossPo in t:Codi ngLe ngth);Populati on( Array(i+1),Cro

57、ssPo in t:Codi ngLe ngth)=a;CrossCou nt=CrossCou nt+1;endend程序 2:交叉染色体序列生成附录24function y=GetArray(N) %随机生成一组序列，用于交叉ya=zeros(1,N);xa=zeros(1,N);for i=1:Nya(i)=i; %记录数组的原始位置endfor i=1:Nm=ra ndi nt(1,1,1,N-i+1);xa(i)=ya(m);for j=m:N-iya(j)=ya(j+1);endendy=xa;附录 6:变异算子程序经典变异算子：function Variatio nFunctio

58、n 1(Number,pv,Codi ngLe ngth)global Variati onCount;global Populati on;x=0;for i=1:Cod in gLe ngthif ra nd(1)pvVariatio nPo in t=i; %变异点if Populatio n(Number,Variatio nPoi nt)=O %进行基因变异Populatio n(N umber,Variatio nPoi nt)=1;elsePopulati on(N umber,Variati onPoin t)=0;附录25endx=x+1;endendVariati onCo

59、un t=Variati onCount+x;改良变异算子 1:function Variatio nFunction 2(Number,pv,Codi ngLength)global VariationCount;global Populati on;p=1-(1-pv)ACodi ngLe ngth; %色体的概率来判断是否执行变异条件为减少计算量，进行改进变异概率，通过整个染,用此方法计算整个染色体的变异概率x=0;if ra ndpfor i=1:Codi ngLe ngthif ra nd(1)=pvVariationPoint=i; %变异点if Population(Number,VariationPoint)=0 %进行基因变异Populatio n(Number,Variatio nPoint)=1; elsePopulati