《一种基于模式替代的遗传算法解０／１背包问题.doc》由会员分享，可在线阅读，更多相关《一种基于模式替代的遗传算法解０／１背包问题.doc（8页珍藏版）》请在三一文库上搜索。
1、一种基于模式替代的遗传算法解背包问题 (1.江西理工大学 信息工程学院， 江西 赣州 341000；2.中国科学院 自动化研究所， 北京 100080) Genetic algorithm with schema replaced for solving 0/1 knapsack problem LI Kangshun1,2,JIA Yuzhen1,ZHANG Wensheng2 (1.School of Information Engineering, Jiangxi University of Science & Technology, Ganzhou Jiangxi 341000, Ch
2、ina;2.Institute of Automation, Chinese Academy of Sciences, Beijing 100080, China) Abstract:Knapsack problem is a typical NP complete problemThis paper raised genetic algorithm with schema replaced for solving 0/1 knapsack problemIt leaded the search direction of the population to a schema by collec
3、ting the best several individuals in population.So,improved the searching efficiency and ability. At last，gave the simulation experiment，and the answer of the knapsack problem which was solved by simple genetic algorithm,compared greedy algorithm and genetic algorithm with schema replacedBy this com
4、parison，the advantages which use schema replaced to solve knapsack problem is proved to be efficient and practical Key words:knapsack problem(KP); schema replaced; genetic algorithm ? 近年来，背包问题吸引了许多理论和实际工作者对此问题的深入研究。在理论上尽管背包问题的结构简单，但它却具有组合爆炸的性质。在实际应用中，许多工业问题均可以用背包问题来描述，如资金运算、货舱装载、存储分配等都是典型的应用例子1。求解背包
5、问题有许多传统的算法，如贪心算法、动态规划算法、回溯法、分支限界法等，它们各自都存在一些缺陷。 遗传算法2，3是Holland和他密西根大学的同事提出的以自然选择和基因繁殖的思想为基础的一种高度并行、随机和自适应全局优化搜索算法。遗传算法一般在开始随机产生初始群体，然后不断地改进个体，以得到越来越好的结果。由于收敛速度和寻找最优解往往是一对矛盾，基本遗传算法(SGA)常表现为收敛速度慢，容易早熟、陷入局部最优解。本文提出了基于模式替代的思想，通过收集每代种群中最好的几个个体生成模式来引导种群的搜索方向，提高了遗传算法的搜索速度和寻找最优解的能力。 1 背包问题 背包问题4(KP)的一般提法是：
6、已知n个物品的重量（weight）及其价值（或收益profit）分别为wi0和pi0，背包的容量（contain）假设设为ci0，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内所装物品的价值最大？ 该问题的模型可以表示为下述0/1整数规划模型： max f(x1,x2,xn)=ni=1pixi 目标函数：s.tni=1wixici xi0,1(i=1,2,n) 其中：xi为01决策变量，xi=1时表示将物品i装入背包中，xi=0时则表示不将其装入背包中。 2 模式的基本理论 1)模式5,6(schema) 它是基于三值字符集 0，1，*所产生的能描述具有某些结构相似性的0、1字符串集
7、的字符串；是一个描述字符串集的模板，该字符串中的某些位置上存在相似性。以长度为 5的串为例，模式*1*0 描述了在位置 2为“1”及在位置5为“0”的字符串，即01000，01010，01100，01110，11000，11010，11100，11110。 2)模式阶 它是指模式中确定位置的个数，用来反映模式之间所匹配的字符串的个数不同。比如模式011*1与模式1*相比，前者的模式阶为4，后者的模式阶为1，前者的确定性高，能匹配的串的个数比后者少。 3)模式的定义距 它是指模式中的第一个确定位置和最后一个确定位置之间的距离。比如模式 011*1的定义距为4，而模式0*为0。 4)Holland
8、的模式定理 在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以指数级增长。模式定理是遗传算法的理论基础。 5)积木块假设 低阶、短距、高平均适应度的模式 (积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，可最终生成全局最优解。 模式定理和积木块假设保证了遗传算法寻找到全局最优解的能力。 3 基于模式替代的遗传算法 遗传算法通过选择算子将当前群体中的优良模式遗传到下一代群体中；通过交叉算子进行模式重组；通过变异算子进行模式突变；通过这些遗传运算，一些较差的模式被淘汰，而一些较好的模式逐步被进化，最终得到问题的最优解
9、。从实际计算中可以发现，最优解和次优解或者表现比较好的个体存在相对程度的相似，也可以说表现良好的个体中含有最优解的基因基本遗传算法在进化到一定的代数后，次优解和次优解相似的个体占了大部分，那么交叉和变异操作往往可能只是在最优解的基因块内部发生，所以导致遗传速度很慢。 采用保存最优个体的策略能确保遗传算法找到最优解，但是其收敛过程往往是缓慢的。仅仅简单采取将最好结果保存不能很好地发挥好的模式对群体的影响，因此，本文对此进行了改进。 3.1 改进策略 3.1.1 模式生成方法 根据模式定理，个体中的部分基因在遗传操作作用下随着进化的迭代，将在种群中迅速增加。收集每一代中最好的一个或者几个个体，将其
10、记录下来，构成生成模式的采样空间，对每一位上的1(或0)的个数进行统计。如果某一位上1(或0)的个数比例超过了某一比例数pPar(本文中称之为模式固定率)，则此位值为1(或0)，否则为*(设置为2)，由此得到模式。那么这些确定的1或0，可以认为它是染色体中的优良基因。还可以对模式进行评估和校正，如果模式中确定的位数太多，即模式的阶数太大，可以提高比例数pPar，让确定的位数减少。如果模式中确定的位数太少，即模式的阶数太小，则降低比例数pPar，让确定的位数增加。 例如，模式的采样空间为1010110110111110，设在某位上1(或0)的个数超过或等于0.75(比例数pPar取0.75)，可
11、以认为此位置为定值1(或0)，则以上采样空间产生的模式为1*1*。 3.1.2 模式替换 选择算子是优良模式增加快慢的关键，选择算子不会产生新的模式却会造成一些模式的丢失。弱的选择算子虽然可以保留更多的模式，但会造成高适应度的模式得不到有效保留，算法收敛效率不高，而强的选择算子虽然加快整体算法的收敛速度但同时加快了一些模式的丢失，算法易陷入局部最优，即早熟变异算子对早熟有抑制作用，但总体上交叉和变异算子将破坏模式的遗传。 本文采用将模式中不确定的“*”进行随机取值产生新个体，比如若模式是 1*1*，那么可能的随机产生的新个体包括1111，1110，1010，1011。这些产生的新个体将取代原群
12、体中的最坏的个体，以便好的模式即使在经过交叉和变异后也有比较大的概率存活下来，保证了好的基因不丢失，同时减少了过多的模式，在提高寻优能力的同时防止早熟。 3.2 算法步骤 a)初始化种群。随机产生初始染色体，采用二进制编码，适应值函数即是背包物品的价值。 b)对种群进行统计，记录最好的几个个体。 c)根据记录的最好个体形成模式的采样空间，根据3.1.1节的策略产生模式。 d)进行模式替换。根据模式产生新的个体，如果比最差的个体好则替换群体中的最差个体。 e)进行选择、交叉、变异等操作。对产生的每个新的个体进行适应值判断：若产生的个体较本代最差的个体好，则替换掉最差个体，否则保留原个体。 f)是
13、否到最大的遗传代数，如果达到则输出结果，结束算法；否则转b)继续执行。 4 数据实验 本文就以上算法设计思想，对所需要实现的背包问题，用上述方法进行了实验，并取得了良好的结果。在实验中，所用的参数定义为演化代数1 000，种群规模200，杂交率0.618，变异率0.06，产生模式的个体数50，模式位固定率0.7。问题实例来自文献7。 各算法重复运行10次，比较算法所能够求得的最好的结果(总价值总重量)，并给出其对应的染色体，则贪心算法、基本遗传算法与基于模式替代的遗传算法对实例13的计算结果如表1所示。 表1 实验结果 上述实验结果表明，用模式替代方法确实能够有效解决0/1背包问题，而且得到的解比较好、收敛速度快，利用模式替代的方法是一种可行和有效的方法。 5 结束语 本文为了求解0/1背包问题，在基本遗传算法的基础上，根据模式的一些基本理论，通过好个体的生成来引导种群的搜索方向，形成了基于模式替换的遗传算法。通过大量的数值模拟实验证明了基于模式替换的遗传算法在求解0/1背包问题时是很有效的，尤其在物品较多时效果更明显，而且具有很好的稳定性。