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

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

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

3、ed in management science and computer science. The most popular algorithms to solve the large scale problems are evolutionary algorithms, such as genetic algorithm and so. It is well known that the mutation operator is the key operator of the genetic algorithm. But there are few literatures dedicate

4、d to study the impact of mutation operator in genetic algorithm to solve the knapsack problem. In view of this, this paper aims to study the performance of the genetic algorithms with different mutation operator in solving the 0-1 knapsack problem. Firstly the mathematical model of 0-1 knapsack prob

5、lem and its significance are introduced. Then, the operator of genetic algorithm and its advantages and disadvan- tages are discussed. With different mutation operators designed, four genetic algorithms are presented accordingly. Finally, the numerical experiments were conducted to test the performa

6、nce of the different algorithm. Simulation results in solving the 0-1 knapsack problems indicate that different mutation operator will affect the performance of the genetic algorithm in its convergence speed and computational accuracy.Key words : genetic algorithm；mutation operator；knapsack problem；

7、matlab目录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背包问题中遗传算法变异算子研究1 背包问题1.1 背包问题的定义背包问题(Knapsack prob

8、lem)是一种NP困难组合优化的问题.可描述如下：决策者有一个背包,其承重能力为W,有m件可选择物品,每个物品的质量和价值分别为,而决策者的目的则是在允许的承重范围之内,选出合理的物品,以使背包中的物品总价值得到最大化.本文中仅考虑0-1背包问题,即每种物品仅有一件,若物品i选入背包的数量描述为,则0-1背包问题可用数学规划模型进行如下表示：1.2 背包问题的意义 背包问题在现代理科学中具有重要的应用 ,是运筹学中的一个典型的NP优化难题,在实际生活中也有着及其广泛的应用背景.许多关于工业和金融的问题,都可以建立背包问题的数学模型,例如资源分配、投资决策、货物装载、网络资源分配、线性材料切割等

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

10、胜劣带的机制,进行遗传操作,逐代演化,产生出更加适应环境的染色体.在每一代,根据问题可行域中个体的适应度大小选择优良个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出新的一代群体.这个过程将导致种群像自然进化一样使后生代种群比前代更加适应于环境,群体经过若干代,保留最适应环境的染色体,从而得到问题的最优解.2.2 遗传算法的优缺点由于遗传算法是基于整个群体进行智能的优化算法,故而其具有良好的全局搜索能力,可以快速地将解空间中的全体解搜索得出,不易陷入局部解中；且由于内在并行性,可以方便地进行分布式计算,加快求解速度.与此同时,由于遗传算法是进行的群体优化,导致其局部搜索能力比较差,在

11、算法执行后期的效率较低.在实际应用中,遗传算法容易产生局域收敛问题.而如何在选择出优良的个体的同时,还要维持群体的多样性,一直是遗传算法中较难解决的问题.2.3 遗传算法的步骤l 选定编码格式：编码需具有完备性、健全性和非冗余性此三大特性.本文根据0-1背包问题的特性采取二进制编码,即0-1编码格式.l 初始群体的确定：随机的产生数量为n的长度为m的初始染色体,其中m为物品数量,每个染色体代表一种潜在可行解,这些染色体就是初始群体.l 适应度函数和适应值的设计：为了确定染色体的优劣,必须拥有合适的适应值规范,目标函数为适应值函数,并计算个体的适应值.l 确定选择的标准：挑选合理的选择算子,主要

12、锦标赛选择、轮盘赌选择等算子,本文中根据背包问题的特性采用排序选择算子.l 产生新的群体：根据选择标准,当前群体淘汰劣质的染色体,并且同时复制优秀染色体补入群体,得到一个新的群体.l 交叉：将所有染色体进行两两不重复配对,进行交叉,得到新的染色体后形成新的群体,本文采用单点交叉.l 变异：变异是在小概率的情况下改变了染色体上的基因.l 终止条件：本文采用限制算法遗传代数为终止条件,当遗传代数达到限制遗传代数时,算法终止.2.4 遗传算法流程图开始Gen=1编码产生初始群体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子根据适应度复制淘汰个体选择两个交叉个体选择个体变异点执行变异执行

13、交叉执行复制复制个体替换淘汰个体交叉后添入新群体中变异后添入新群体中结果结果结果Gen=Gen+1输出结果终止YNYYYNNNPcPv图 2-1 遗传算法流程图3 问题假设及符号说明3.1 问题假设假设背包的空间足够大,可以装的下所有的物品,仅仅是重量承受有要求.假设所有的物品不重复,即没有相同的物品.每样物品数量仅有1个,即选入包中只能为0个或者1个.所有的染色体均为单倍体.3.2 符号说明表1 求解问题的符号说明符号说明Wmnk背包的承重能力可以选择的物品数量第i个物品的重量第i个物品的价值种族的染色体数量大小染色体的向量表示适应函数第i个染色体染色体发生交叉的概率染色体发生变异的概率染色

14、体交叉位点4 遗传算法的主要算子4.1 选择算子 选择,是将群体中的适应度低的染色体替换为适应度高的染色体的操作过程,它是遗传算法群体的整体优化的基础,可以使群体最优解越来越趋近于问题的理论最优解.目前,主要的选择算子包括适应值比例选择、Boltzmann选择、排序选择、联赛选择、精英选择、稳态选择.本文中采用的是排序选择,排列选择是将当代群体的染色体按照适应值排列,淘汰适应值低的染色体,并补入适应值高的染色体.对于一个确定好且数量为n的群体,是由多个染色体组成,可用向量描述,根据适应值函数可得到第i个染色体的适应值,适应值函数表达式可用如下表示：,其中为当前群体中染色体对应的方案价值的最小值

15、.适应值得出后,即可进行排序选择算子操作,最终得到新的群体,用图解表示则可用下图表示：选择100111101101011001100110100111101101011010011110适应值：4适应值：9适应值：10适应值：10适应值：9适应值：10图 4-1 排序选择算子示意图图4-1表示当前群体内有三条染色体,经过选择算子后选择后,淘汰适应值仅有4的染色体01100110,并将适应值最高为的染色体10011110补入至淘汰染色体的相应群体位置,最终得到一个新的群体.4.2 交叉算子交叉,是进化算法中的遗传算法所独有的原始性特征,它是模仿自然界的有性繁殖时的基因重组过程,将当代原有的优良基

16、因遗传给下一代个体,并生成包含更复杂基因结构体的新个体.一般,交叉操作会经过下列几个步骤：l 从交配池中随机选出不重复的交配个体l 根据交叉概率确定是否进行交叉操作,形成新的染色体l 进行交叉操作,将配对染色体上的对应基因进行交换,形成新的染色体. 交叉分为单点交叉,两点交叉,多点交叉和一致交叉等形式.单点交叉是最为基础的交叉方式.首先需要选出两条不同的染色体,检验交叉概率后,成功后随机在某一基因位点,染色体的对应基因片段进行互换,得到两条新的染色体.本文中采用的是单点交叉方法,可用图解表示：01001110101110010100100111101011r<0.8图4-2 单点交叉示意

17、图 图4-2表示染色体01001011与11101001在=0.8概率下,生成随机数r<0.8后,随机生成染色体交叉位点k为4,最终在此位基因发生单点交叉,形成两条新的染色体01001001与11101011. 由于交叉算子有效的增强了群体之间的染色体的相互联系,使基因的流动性得到提高,即群体的染色体保证了多样性,能够有效防止遗传算法的局域收敛,加强了遗传算法的全局搜索能力,在遗传算法中扮演一个十分重要的角色.4.3 变异算子 变异操作是模拟自然界生物体进化中的染色体上某位基因发生的突变,从而改变染色体的结构和物理性状的现象.一般遗传算法中,采用的是根据变异概率随机对某位基因进行变异.本

18、文中,主要研究变异算子的性质,在整个遗传算法框架内嵌入不同的变异算子,从而得到不同的遗传算法.然后通过背包问题实例测试各个具有不同变异算子的遗传算法,得到每种变异算子的优缺点,故重点进行介绍变异算子的性能优劣.关于二进制的变异算子,本文中列举了四种变异算子形式,四种变异算子进行变异的流程图解可用如下图表示：l 第一种变异算子,是对群体中的每一条染色体的每一位基因进行变异,此变异算子广泛应用于各个遗传算法的变异算子之中,是最基本最常用的变异算子.例如图4-3,当物品数m=8时,染色体10110101进行变异概率=0.02的变异,生成m个服从0,1的均匀分布的随机数,最终得到一个随机数集合r,r=

19、0.01,0.5,0.15,0.06,0.5,0.4,0.9,0.8,判断其每个元素是否小于,若小于,则表明此元素对应的基因发生了变异,进行基因取反操作,如上述集合r可知染色体第1位基因发生变异,得到新的染色体00110101.r<0.021011010100110101r=0.01,0.5,0.15,0.06,0.5,0.4,0.9,0.8图 4-3 第一种变异算子示意图l 第二种变异算子,此变异算子是基于第一种变异算子的计算量过高而进行改良得到.它首先需要得到一条染色体的整体变异概率P,然后对每条染色体进行如下操作：生成一个满足0,1均匀分布的随机数r,若r<P,则表明此染色体

20、可能发生变异,然后对每位基因进行如下操作：生成一个满足0,1均匀分布的随机数s,当s<时,表明此位基因会发生变异,进行取反操作.此变异算子最终使得原本需要次的计算量改良降为的计算量.如：图4-4,当物品数m=8,=0.02时,对染色体10110101进行变异操作,生成随机数为r,当r<P后,生成一组随机数集合S=0.5,0.3,0.6,0.015,0.7,0.8,0.4,0.9,表明第4位基因发生变异,最终得到新的染色体10100101.101101011010010110110101r<P图 4-4 第二种变异算子示意图l 第三种变异算子.与第一、二种变异算子相比,此算子更

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

22、色体发生变异后,随机生成两个基因位点a=3,b=4,确定出变异基因片段为3至4位基因,最后进行基因取反操作,得到新的染色体1000010111.10110101111000010111a=3,b=41011010111r<P图 4-5 第三种变异算子示意图l 第四种变异算子,它是基于第三种变异算子进行改良,首先需要求出一条染色体的变异概率P,然后对每条染色体进行如下操作：生成一个满足0,1均匀分布的随机数r,若r<P,则表明此染色体发生变异：,进行变异操作：确定基因变异位,为了计算量的减少,此变异算子采用连续变异基因位的方法,即将k个连续的基因进行变异,为避免一条染色体变异的基因个

23、数不会过多,导致算法易陷入局部解之中,所以在算子中添加了一个约束条件,使每条染色体基因变异个数不能超过一条染色体基因变异的期望值,确定出变异基因片段后,选出当前群体的最优染色体,将此基因片段的基因变异为最优染色体相应基因片段信息,最终形成一条新的染色体. 图4-6,染色体1011010111在的概率下,通过随机数r判断染色体发生变异后,随机生成两个基因位点a=5,b=6,确定出变异基因片段为5至6位基因,当代群体的最优染色体为1100011001,变异后得到新的染色体1011110111.10110101111011110111a=5,b=61011010111r<P1100111001

24、最优染色体:图4-6 第四种变异算子示意图5 数据测试5.1 算法测试规范l 编码规范,遗传算法中,编码一般需要具备三大特性：完备性、健全性、非冗余性.完备性：问题空间中的所有可行解均可成为一条染色体的表现型.健全性：每一种染色体必须对应问题空间中的某一个潜在可能解.非冗余性：染色体与问题空间中的可能潜在解必须一一对应.由于每种物品数量仅有一个,且只分为选入背包与不选入背包两种情况,故可用二进制进行编码.例如对m=10的情形,染色体1011010111表示第1,3,4,6,8,9,10个物品放入背包之中,其它物品则不放入背包之中.l 初始群体,初始群体的产生一般通过随机生成足够数量且合格的染色

25、体.随机生成一条染色体后,检验重量是否合格,失败后则重新随机生成一条染色体,直到生成了一条合格的染色体并补入进初始群体中.一直到初始群体的大小达到了指定的数量为止,否则继续生成染色体.l 终止条件,遗传算法作为一种迭代式算法,必须要确立一个明确的终止条件,用以终止算法,输出最终结果.一般而言,遗传算法有两种判断算法是否终止的方法：设定最大遗传代数,此方法简单,但结果不够精确；通过群体的收敛程度判断,通过计算群体中的基因位相似度进行判断.本文中采用设定遗传代数作为算法终止条件,当遗传代数达到设定数值时,算法终止,输出最优解.相似度计算方法：首先计算群体中所有染色体第一位基因两种基因的个数,取其最

26、大值,将其除以群体染色体个数,得到第一位基因相似度,类似,求取接下来的每一位基因的相似度,将所有的相似度累加,除以染色体的基因总位数,得到的就是基因相似度,最终通过确定此值是否满足条件而确定该如何执行下一步操作.基因相似度=,其中m为基因的总位数,表示所有染色体中第i位基因为0的染色体个数,表示所有染色体中第i位基因为1的染色体个数,n表示群体中的染色体个数.例如染色体1010、1110、0111的相似度为.5.2 测试目的及实例数据本文旨在通过不同的实例测试使用不同变异算子的遗传算法求解背包问题时性能的差异,最终确定选择何种变异算子的遗传算法解决背包问题的效果达到最佳.例1物品数量为m=20

27、,质量价值分别如下：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,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,

28、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物品总质量为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,10Value=16,24,11,64,17,46

29、,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, 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,

30、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,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, 37

31、,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,16,24,11,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,理论最优解为22675.3 参数设置表2 本文算法参数选择参数值变异概率交叉概率群体大小n算法执行次数终止遗传代数物品数量0.020.81502510020-1005.4 运行环境l 操作系统：64位 Windows7

32、旗舰版l 处理器：Intel Core is-2350M CPU 2.30GHzl 内存：4Gb,3.82Gb可用5.5 运行结果图例1结果图表以及分析：表3 例1算法平均所用时间、背包内最高价值、平均价值、最低价值变异算子编号算法平均时间(s)最高价值平均价值最低价值2.0286 1.8801 1.8402 1.9157262262262262261.32261.20259.96258.36258258255254 图5-1 例1最优解背包价值箱图图5-2 例1最优解背包价值标准差图在求解算例一时,根据表3中的算法平均时间,在四种变异算子中,第二、三种变异算子的算法平均耗时较短,使用第一、四

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

34、,则应当使用第二种变异算子,可快速获得问题最优解的同时能保证足够的精确度以及稳定性.例2结果图表以及分析：表4 例2算法平均所用时间、背包内最高价值、平均价值、最低价值变异算子编号算法平均时间(s)最高价值平均价值最低价值2.3474 2.1409 1.9850 2.1040 729729729729724.80725.72723.04714.92719718715695 图5-3 例2最优解背包价值箱图图5-4 例2最优解背包价值标准差图在求解算例二时,根据表4中的算法平均时间,在四种变异算子中,使用第三种变异算子的遗传算法平均耗时最短,所以使用此变异算子的遗传算法可最快速的获得算法的结果值

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

36、解的同时能保证足够的精确度以及稳定性.例3结果图表以及分析：表5 例3算法平均所用时间、背包内最高价值、平均价值、最低价值变异算子编号算法平均时间(s)最高价值平均价值最低价值2.5665 2.3638 2.0604 2.1790 10881087108710741076.21077.11057.31060.61051106210321027 图5-5 例3最优解背包价值箱图图5-6 例3最优解背包价值标准差图在求解算例三时,根据表5中的算法平均时间,在四种变异算子中,使用第三、四种变异算子的遗传算法平均耗时较短,可较为快速的获得算法的结果值.使用第一变异算子的遗传算法耗时最长,其中使用第三种

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

38、果图表以及分析：表6 例4算法平均所用时间、背包内最高价值、平均价值、最低价值变异算子编号算法平均时间(s)最高价值平均价值最低价值3.2834 3.1494 2.2367 2.3750 22232264224422092187.42207.72165.12148.02144215720812058 图5-7 例4最优解背包价值箱图图5-8 例4最优解背包价值标准差图在求解算例四时,根据表6中的算法平均时间,在四种变异算子中,使用第三、四种变异算子的遗传算法平均耗时较短,可较为快速的获得算法的结果值.使用第一、二变异算子的遗传算法耗时较长,其中使用第三种变异算子的遗传算法耗时最短,使用第一种变

39、异算子的遗传算法耗时最长.结合图5-7、5-8以及表5,四种变异算子中.使用第二种变异算子的遗传算法的算法精确度最高,可最为精确的获得问题的理论最优解,使用第三、四种变异算子的遗传算法的算法精确度较低.使用第四种变异算子的遗传算法精确度最低,不利于精确获得问题理论最优解.因此,从遗传算法的计算速度上看,使用第三种变异算子的遗传算法更好获取到算法结果;从算法的精确度和稳定性看,则应当选取第二种变异算子,可更加精确稳定的获得算法结果;综合考虑计算速度和精度,则应当使用第二种变异算子,可快速获得问题最优解的同时能保证足够的精确度以及稳定性.5.6 结果分析 通过上述的四则算例的结果分析,使用第一、二

40、种变异算子的遗传算法在算法结果的精确度以及稳定性上有着较为良好的优势；而使用第三、四种变异算子的遗传算法在算法的运行速度上有着较为良好的优势.总体说来,当从算法的计算速度上考虑,应当使用第三种变异算子最优,可更快的获得算法的结果；从算法的结果精确度及稳定性上考虑,使用第一种变异算子可使遗传算法效果达到最优；综合算法的速度与精确度,则应当选取第二种变异算子,可使算法的效益比率最高,可较快得到结果的同时获得较为精确的结果.6 结论 遗传算法是一种具有定向制导的随机搜索技术,其定向制导的原则是：导向以高适应度模式为祖先的“家族”方向,为了保证群体的多样性,防止算法陷入举步最优解,引入了变异算子.采用

41、二进制编码的遗传算法,其变异算子比较单调,且没有相关文献系统地分析各类变异算子对遗传算法影响,故本文设计了四种的变异算子,并通过0-1背包问题实例的仿真实验结,比较了个变异算子的优劣.基于第一、二种变异算子的算法精度高,更稳定,而基于第三、四种变异算子的算法收敛速度更快.参考文献参考文献1Duane Hanselman、Bruce Littlefield著,朱仁峰译制版 精通Matlab7,清华大学出版社 2006年出版,p27-29 p317-3212李敏强、寇纪淞等 遗传算法的基本理论与应用 科学出版社2002版,p27-45、p47-483万福永、戴浩晖等著,数学实验教程(Matlab版

42、) ,科学出版社 2006版,p169-1764遗传学编写组·遗传学·北京:中国大百科全书出版社,19835张文修, 梁怡·遗传算法的数学基础 M 1西安: 西安交通大学出版社, 2001.6王小平,曹立明·遗传算法 理论、应用与软件实现 M·西安: 西安交通大学出版社, 2002.7陈国良, 王煦法, 庄镇泉, 王东生·遗传算法及其应用M ·人民邮电出版社, 2001.8张永兵,王斌,张永飞等·基于遗传算法的背包问题求解.大理学院学报,2005,4(5):24269网络资源：28附录附录1 主程序1.1 测试程序

43、 clear all; %清除缓存IssueMatrix=; %重量价值关系矩阵 MaxValue=600; %背包容量 pc=0.8; %交叉概率 pv=0.02; %单个基因变异概率 PopulationNumber=150; %群体大小 n=25; %每种问题执行次数n for i=1:n y1(i,1),z1(i,1)=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumber,1); %获取算法终止时的遗传代数以及最优解 y2(i,1),z2(i,1)=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumbe

44、r,2); y3(i,1),z3(i,1)=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumber,3); y4(i,1),z4(i,1)=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumber,4); end figure; var1(1)=mean(y1); var1(2)=mean(y2); var1(3)=mean(y3); var1(4)=mean(y4); plot(1:1:4,var1,'o'); %绘制平均算法终止所用时间图 title('平均算法终止所用时间图'

45、); xlabel('变异算子编号'); ylabel('时间'); figure; boxplot(z1,z2,z3,z4); %绘制最优结果值的箱图 title('遗传算法最终结果价值箱图'); xlabel('变异算子编号'); ylabel('结果值'); figure; 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'); %绘制最优结果值的标准差图 t

46、itle('遗传算法最终结果价值标准差图'); xlabel('变异算子编号'); ylabel('标准差');1.2 执行主程序function y,z=Main(IssueMatrix,MaxValue,pc,pv,PopulationNumber,action)global Gen; %遗传代数,初始为0global VariationCount %染色体发生变异的次数global CrossCount %染色体发生交叉的次数Gen=0; %初始化计数器global VariationCountglobal CrossCountglobal

47、 CodingLength %定义编码长度global Population %定义种群VariationCount=0;CrossCount=0;a=size(IssueMatrix);CodingLength=a(1,2);InitPopulation(IssueMatrix,MaxValue,CodingLength,PopulationNumber); %初始化种群Gen=1;time=0;tic;%计时开始while (Gen<100) %检测是否已经达到100代,若已经达到,则结束循环,否则继续迭代SelectFunction(IssueMatrix,MaxValue,Cod

48、ingLength,PopulationNumber); %进行选择算子 Array=GetArray(PopulationNumber); %获取交叉序列 CrossFunction(Array,CodingLength,pc,PopulationNumber); %进行交叉 for Number=1:PopulationNumber %Number代表当前群体中染色体的标号 if action=1 VariationFunction1(Number,pv,CodingLength); end if action=2 VariationFunction2(Number,pv,CodingLe

49、ngth); end if action=3 VariationFunction3(Number,pv,CodingLength); end if action=4 VariationFunction4(IssueMatrix,Number,pv,CodingLength,MaxValue,PopulationNumber); end end Gen=Gen+1;endtime=toc;%计时结束 BestValue=GetBestValue(IssueMatrix,MaxValue,Population,CodingLength,PopulationNumber); %获取最优解HighVa

50、lue=CountValue(IssueMatrix,BestValue,CodingLength);y=time;%时间z=HighValue;2 初始化群体2.1 初始化：function InitPopulation(IssueMatrix,MaxValue,CodingLength,PopulationNumber) global Population; for i=1:PopulationNumber Population(i,:)=GetCoding(IssueMatrix,MaxValue,CodingLength); %生成编码end2.2 获取一个合格的染色体编码functi

51、on y=GetCoding(IssueMatrix,MaxValue,CodingLength) for i=1:CodingLength y(1,i)=round(rand(1); %随机生成一个基因编码 end if CountWeight(IssueMatrix,y,CodingLength)>MaxValue %判别是否合格 y=GetCoding(IssueMatrix,MaxValue,CodingLength); %不合格重新获取end3 数据统计程序3.1 计算重量function y=CountWeight(IssueMatrix,CodingMatrix,Codin

52、gLength) y=0; for i=1:CodingLength y=y+IssueMatrix(1,i)*CodingMatrix(1,i); %累加重量 end3.2 计算价值function y=CountValue(IssueMatrix,CodingMatrix,CodingLength) y=0; for i=1:CodingLength y=y+IssueMatrix(2,i)*CodingMatrix(1,i); %累加价值 end3.3 相似度计算function y=Detection(Population,CodingLength,PopulationNumber) %计算相似度 s=0; for i=1:CodingLength a=sum(Population(1:PopulationNumber,i); %每位基因的相似个数 if a<PopulationNumber/2; a=PopulationNumber-a; end s=s+a; %相似数累加 end y=s/CodingLength/PopulationNumber; %除去