用遗传算法求解多维背包问题.docx

智能所“暑期学校”科研实习报告智能所“暑期学校”科研实习报告题 目： 用遗传算法求解多维背包问题 姓 名： 吴逊 专 业：智能科学与技术指导老师姓名、职务：尚荣华 副教授日 期： 二零一一年八月 摘要首先简单介绍了基本的遗传算法。然后将贪婪算法与简单遗传法相结合构成一种混合遗传算法,用该混合遗传算法求解背包问题。通过对标准测试集中的27个问题进行测试，发现用这种方法求解大规模背包问题, 其解的质量和求解性能较简单遗传算法和贪婪算法都有所改善。关键词：遗传算法，多维背包问题绪论遗传算法是模拟生物界自然进化过程的一种计算模型，其思想主要来源于达尔文进化论、孟德尔遗传学说及现代生物学对生命遗传过程的研究。对它的研究起源于20世纪70年代，由美国Michigan大学的J.Holland教授于1975年正式提出。GA的主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制等领域。本文将先就遗传算法介绍其思想来源及基本思路，并提出GA应用的5个关键点。接着对一类典型的组合优化问题0-1背包问题分别进行简单遗传算法与混合遗传算法的求解，并将结果与贪婪算法进行对比。第一章 遗传算法概述 2.1达尔文进化论与孟德尔学说19世纪中叶，达尔文创立了科学的生物进化学说，它第一次对整个生物界的发生、发展，作出了唯物的、规律性的解释，使生物学发生了一次革命性的变革。达尔文进化论认为生物不是静止的，而是进化的。物种不断变异，旧物种消失，新物种产生。而且生物的进化是连续和逐渐，不会发生突变。生物之间存在一定的亲缘关系，他们具有共同的祖先；而另一方面，由于生物过渡繁殖，但是它们的生存空间和食物有限，从而面临生存斗争，包括:种内、种间以及生物与环境的斗争。总结起来为两部分内容：遗传变异与自然选择。其中自然选择是达尔文进化论的核心。1857年，孟德尔通过对植物进行一系列仔细的实验。揭示了遗传学的两条基本定律：分离定律和独立分配定律，统称为孟德尔遗传定律。分离定律是指基因作为独特的独立单位而代代相传。细胞中有成对的基本遗传单位，在杂交的生殖细胞中，一个来自雄性亲本，一个来自雌性亲本.独立分配定律则指出在一对染色体上的基因对中的等位基因能够独立遗传。孟德尔的这两条遗传基本定律就是新遗传学的起点，孟德尔也因此被后人称为现代遗传学的奠基人。将达尔文进化论和孟德尔-摩根基因相结合，成为现被广泛接受的新达尔文主义。新达尔文主义认为，只用种群上和物种内的少量统计过程就可以充分地解释大多数生命历史，这些过程就是繁殖、变异、竞争、选择。繁殖是所有生命的共同特性；变异保证了任何生命系统能在正熵世界中连续繁殖自己；对于限制在有限区域中的不断膨胀的种群来说，竞争和选择是不可避免的结论。2.2生物学中的遗传概念在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称DNA。染色体是其载体。DNA是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如，改变DNA长链中的特定一段（称为基因），即可改变人体的身高。细胞在分裂时，DNA通过复制而转移到新产生的细胞中，新的细胞就继承了上一代细胞的基因。有性生殖生物在繁殖下一代时，两个同元染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉形成两个新的染色体。在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生新的染色体。这些新的染色体将决定新的个体（后代）的新的性状。在一个群体中，并不是所有的个体都能得到相同的繁殖机会，对生存环境适应度高的个体将获得更多的繁殖机会；对生存环境适应度较低的个体，其繁殖机会相对较少，即所谓自然选择。而生存下来的个体组成的群体，其品质不断得以改良，称为进化。生物的进化是经过无数次有利的进化积累而成的，不同的环境保留了不同的变异后代。2.3 遗传算法的基本思想首先实现从性状到基因得映射，即编码工作，然后从代表问题可能潜在解集得一个种群开始进行进化求解。初代种群（编码集合）产生后，按照优胜劣汰的原则，根据个体适应度大小挑选（选择）个体，进行复制、交叉、变异，产生出代表新的解集的群体，再对其进行挑选以及一系列遗传操作，如此往复，逐代演化产生出越来越好的近似解。选择是指通过适应度的计算，淘汰不合理的个体。类似于自然界的物竞天择。复制指编码的拷贝，类似于细胞分裂中染色体的复制。交叉即编码的交叉重组，类似于染色体的交叉重组。变异是指编码按小概率扰动产生的变化，类似于基因的突变这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中得最优个体经过解码（从基因到性状的映射），可以作为问题近似最优解。遗传算法的基本框架如下：2.4 遗传算法需解决的5个问题基本的遗传算法可定义为一个八元组：GA=（C,E,P0,M,T）式中：C个体的编码方式；E个体的适应度函数；P0初始种群；M种群大小；选择算子；交叉算子；变异算子；T算法终止条件。基于以上认识,总结之，认为完成一个遗传算法主要需解决以下五个问题：1 编码选择合适的编码方式会使原问题映射到基因空间后变得简单明了、易于解决。编码需考虑染色体的可行性、合法性（通过解码是否为问题的一个解）以及映射的唯一性。有二进制编码、实数编码、整数排列编码等。 2群体初始化通常有两种方法，一种是完全随即产生；一种是根据某些先验知识产生一组必须满足的要求，在满足这些要求的解中随机选取样本。经证明，在二进制编码的前提下，若个体长度为L，则种群规模的最优值为2L/2（即全解）。但这个数字通常情况下都很大，所以一般取20-100。3个体评价适应度函数的选取直接影响遗传算法的收敛速度及能否找到最优解，对一般优化问题，通常直接选取其目标函数作为适应度函数。在计算适应度时，对不可行解的处理常用的方法有修正法和罚函数法，实验证明修正法要优于罚函数法。4遗传算子（全局:选择；局部：交叉、变异）选择：其基础是适者生存理论，指导GA搜索在整个搜索空间中朝最有利的区域发展。确定合适的选择压力对其很重要，在进化之初保持低压可以保留种群多样性，而在进化后期选择高压可以加快收敛速度。常用的选择机制有轮盘赌，确定性选择，混合选择等。交叉、变异:分别模拟生物界的有性生殖过程和基因突变现象，常用的有单点交叉，多点交叉，随机、插入及交换变异等方法。5 参数选择；对于一般的问题，通常需要确定的主要参数有：迭代次数；种群大小；交叉、变异概率。这几种参数的变化对算法性能的影响非常明显，需针对不同问题具体分析。2.5 遗传算法的特点遗传算法的主要特点是群体搜索策略和群体中个体之间的信息交换，具体而言，它有以下不同于传统算法的优点：从许多点开始并行计算，计算速度快，避免收敛于局部最优解；通过目标函数计算匹配度，对问题的依赖性小；在解空间进行高效的启发式搜索，而非盲目穷举；应用范围广；计算简单，功能强，适合解决大规模复杂问题。第二章 0-1背包问题问题描述：给定背包的m种资源，如大小、承重等，其中第j种资源取值cj,j=1,2,.,m;另给定n件物品，其中第i件物品的价值为pi，对应资源j的占用量为aij,i=1,2.n。受背包条件限制，若只能挑选一部分物品装入背包，那么如何选择物品使背包装入物品的价值最大，数学描述为：式中：f(x)表示装入背包物品的总价值；参数cj0,pi0,0aijcj；x=(x1,x2,.xn)表示一组物品的选择策略，xi=i表示物品j被选中放入背包，xi=0表示物品i没有被选中。当m取值为1时，问题即变为简单0-1背包问题。背包问题属典型的组合优化问题，并且是NP难问题。已有的求解方法可分为精确算法，如枚举法，动态规划法，分支定界法，图论法等指数级方法以及近似算法，如贪婪算法，遗传算法，免疫算法等两大类。背包问题的研究对于解决复杂组合优化问题有重要的意义。第三章 用遗传算法求解多维0-1背包问题4.1 算法描述本章将采用一种将贪婪算法与遗传算法相结合的混合遗传算法来求解多维背包问题，并将此算法与简单遗传算法和贪婪算法进行对比，以提供一种利用遗传算法求解问题的新思路。传统的贪婪算法是基于价值密度的，例如物品单位体积价值或单位质量价值。这在一维背包问题中很适合，但是对于多维背包问题就需要做一下修改，因为包的限制条件有多个（如体积、质量等），无法只用上述简单的价值密度来解决。为此，我们提出了“综合价值密度”的概念，所谓“综合价值密度”就是对各种单一价值密度的综合，用来表示，具体定义如下：i=pi/vi其中kj=cj/1mcj ，vi=1naij/kj这种方法可以认为是将多种不同的资源整合为一种虚拟的“总资源”，vi 表示第i种物品占用“总资源”的加权量。 kj的意义是包的对第j种资源限制的相对大小，kj越大说明包对对第j种资源限制的越小，所以在该种资源在vi中占的比例就越小。用贪婪算法求解多维0-1背包问题的步骤如下：Step1：求解各物品的价值密度；Step2:将物体按由大到小的顺序排序。不妨记新的排序为1,2,n；Step3:若对任意一种资源j,均有 i=1k-1aijxi+akjcj,则xk=1,否则xk=0.k=k+1；Step4：IF k=n+1 stop;ELSE return step3.贪婪算法简单直观，易于理解，但并不能保证能得到全局最优解。在简单遗传算法中加入适当的局部搜索方式，利用启发式信息或与领域相关的知识，使得算法既具有遗传算法的整体优化等特性，又能加快算法的收敛速度，从而在求解各类应用问题中具有更大的优越性，这样的算法称为混合遗传算法。遗传算法的几个步骤（编码，初始化，选择，交叉，变异等）已经有许多很好的方法，例如轮盘赌选择法、单点交叉等，这些方法简单，效果好，而且有通用性，我们可以直接用来解决各种问题。解决多维背包问题的关键在于包的限制条件的处理，遗传算法中经过交叉、变异的个体是随机的，很可能不满足包的限制条件，所以要用合理的修复算法修复每个个体使其满足限制条件。基于对以上分析，可以利用在简单遗传算法中加入用基于上述贪婪算法的修复算法，这样既能将不可行解改造成可行解，又能使个体趋于较好的解。具体步骤如下:Step1:依据上述贪婪算法将物品重新排序.Step2:依据上述贪婪选择机制依次修复每个个体。本实验中其它算子的选择如下： （1）编码：采用二进制编码，即直接使用原问题描述中的x表示个体。（2）评价函数：取目标函数f(x)。（3）初始化种群：随机产生，种群规模为100。（4）选择：轮盘赌算法。（5）交叉：单点交叉，交叉概率为pc=0.5.（6）变异：单点变异,变异概率为pm=0.01.（7）终止条件：设置一定的迭代次数。本实验中取100次。4.2实验与分析本实验共选取了标准测试集中的27个问题，对每个问题进行了5次实验，统计结果如下：问题mn简单遗传算法混合遗传算法贪婪算法已知最优解fmaxfmeanfmaxfmeanWeing2Weing1Weing3Weing7Weing8Weish01Weish02Weish06Weish07Weish10Weish11Weish14Weish15Weish18Weish19Weish22Weish24Weish26Weish27Weish30PB1PB2PB4PB5PB6sento1sento2222225555555555555554421030303028282810510530304040505060607070808090909027342920406060130314.0140115.895642.8994757.0479457.84504.84420.05336.45330.45882.45142.26168.46804.88688.26499.27563.08836.07669.28152.09306.82975.62975.891132.82090.6743.27327.48208.4102273.0117071.571296.3855858.1310523.33423.73424.34194.64089.14144.73484.74393.54452.26523.54561.15518.46871.05528.25764.67082.02454.52320.969256.81625.6447.55153.76854.9130687.0141227.895677.01011575.3616782.74554.04503.55351.65555.76304.75559.06875.07328.79349.07566.38837.39826.79348.39656.0108642977.03054.395168.02077.3776.07669.08646.3120317.8129795.990744.8858794.1555688.94228.04182.14959.55014.65585.74956.65969.06604.38232.56600.588368512.68207.48278.99376.92509.12620.584542.21776.9681.67117.97808.012188013927893278108836562006045344483550355676265555069027199922470518836981892789764108192792282590909192572376068709130883141278956771095445624319455445365557556763395643695474869580769889471022095849819111913090318695168213977677728722由以上实验数据可以看出：当m、n较小时，SGA的结果要优于贪婪算法，而当数据量增大时，SGA将次于gree