智能科学与技术暑期学校科研实习报告：混合遗传算法在背包问题中的应用与优化
./智能所“暑期学堂”科研实习报告 标题：利用遗传算法解决多维背包问题 姓名：吴训 专业：智能科学与技术讲师，职位：尚荣华副教授 日期：2011年8月 摘要一、简单介绍了基本的遗传算法。然后将贪心算法与简单遗传法相结合，形成混合遗传算法，并利用混合遗传算法来求解背包问题。通过对标准测试集中的27个问题进行测试，发现使用该方法解决大规模背包问题，与简单的遗传算法和贪心算法相比，提高了解决质量和性能。关键词：遗传算法，多维背包问题 引言 遗传算法是一种模拟生物世界自然进化过程的计算模型。其思想主要来源于达尔文进化论、孟德尔遗传论以及现代生物学对生命遗传过程的研究。其研究起源于20世纪70年代，由密歇根大学的J. Holland教授于1975年正式提出。遗传算法的主要特点是群体搜索策略和群体中个体之间的信息交换。搜索不依赖于梯度信息。它特别适合处理传统搜索方法难以解决的复杂非线性问题，可广泛应用于组合优化、机器学习、自适应控制等领域。本文首先介绍遗传算法的思想渊源和基本思想，并提出遗传算法应用的五个要点。然后，分别采用简单遗传算法和混合遗传算法求解典型的组合优化问题——0-1背包问题，并将结果与贪心算法进行比较。
遗传算法概述 2.1 达尔文的进化论和孟德尔的理论 19世纪中叶，达尔文创立了生物进化论的科学理论。它第一次对整个生物世界的发生和发展给出了唯物主义的、规律性的解释，使生物学发生了革命性的变化。达尔文的进化论认为，生物不是静止的而是进化的。物种不断变异，旧物种消失，新物种出现。而且，生物进化是连续的、渐进的，没有突变。生物体之间存在一定的亲缘关系，有共同的祖先；另一方面，由于生物的过度繁殖，其生存空间和食物受到限制，因此面临着生存斗争，包括：物种、种间以及生物与环境的关系。斗争。可以概括为两部分：遗传变异和自然选择。自然选择是达尔文进化论的核心。 1857年，孟德尔对植物进行了一系列仔细的实验。揭示了遗传学的两个基本定律：分离定律和独立分布定律，统称为孟德尔遗传定律。分离法则指出，基因作为独特的独立单位代代相传。细胞中有成对的基本遗传单位。在杂交生殖细胞中，一种来自父本，另一种来自母本。独立分类法则指出，一对染色体上的基因对中的等位基因可以独立遗传。孟德尔遗传的两个基本定律是新遗传学的起点，孟德尔因此被称为现代遗传学的奠基人。达尔文进化论和孟德尔-摩根基因的结合成为现在被广泛接受的新达尔文主义。
新达尔文主义认为，生命的大部分历史可以通过种群和物种中的少数统计过程来充分解释。这些过程是繁殖、突变、竞争和选择。繁殖是所有生命的共同特征；突变确保任何生命系统都可以在正熵世界中不断地自我复制；对于限制在有限区域内的不断增长的人口来说，竞争和选择是不可避免的结果。 2.2 生物学中遗传的概念 在生物细胞中，控制和决定生物体遗传特征的物质是脱氧核糖核酸，简称DNA。染色体是其载体。 DNA是由四种碱基按一定规则排列组成的长链。四种碱基的不同排列方式决定了生物体不同的性能特征。例如，改变 DNA 长链（称为基因）的特定片段可以改变一个人的身高。当细胞分裂时，DNA被复制并转移到新产生的细胞中，新细胞继承了上一代细胞的基因。有性生殖生物繁殖下一代时，两条同源染色体通过交叉重新组合，即两条染色体的DNA在同一位置被切断，前后两串交叉，形成两条新的染色体。 。当细胞进行复制时，某些复制错误可能会以很小的概率发生，导致DNA发生某些突变并产生新的染色体。这些新染色体将决定新个体[后代]的新性状。在一个群体中，并非所有个体都有相同的繁殖机会。对生存环境适应性高的个体，将有更多的繁殖机会；对生存环境适应能力低的个体，其繁殖机会相对较少。 ，即所谓的自然选择。
幸存个体组成的群体质量不断提高，这就是进化。生物体的进化是无数有益进化的积累，不同的环境保留着不同的变异后代。遗传算法的基本思想是首先实现从性状到基因的映射，即编码工作，然后从代表问题的可能潜在解决方案集合的群体开始进化解决方案。第一代种群【编码集生成后，根据优胜劣汰的原则，根据个体适应度进行选择【选择个体，进行复制、交叉、变异，生成代表新解集的种群，并然后选择并执行一系列遗传操作]，如此往复，一代又一代的进化产生越来越好的近似解。选择是指通过适应度计算淘汰不合理的个体。类似于自然界的自然选择。复制是指代码的复制，类似于细胞分裂过程中染色体的复制。交叉是密码的交叉重组，类似于染色体的交叉重组。变异是指小概率的扰动引起的编码变化。与基因突变类似，这个过程将导致种群像自然进化一样进化。后代种群将比上一代更能适应环境。最后一代群体中的最优个体将被解码[从基因到性状]的映射，可以作为问题的近似最优解。遗传算法的基本框架如下： 遗传算法需要解决的5个问题。基本的遗传算法可以定义为一个八位组： GA=〔C,E,,M,Φ,Γ,Ψ,T 其中：C-个体编码方法； E——个体适应度函数；——初始种群； M——人口规模； Φ——选择算子； Г——交叉算子； Ψ——变异算子； T——算法终止条件。
基于以上认识，综上所述，认为完成一个遗传算法主要需要解决以下五个问题： 1、选择合适的编码方法，将原来的问题映射到基因空间。编码需要考虑染色体的可行性和合法性【解码是否是问题的解决方案以及映射的唯一性。有二进制编码、实数编码、整数排列编码等。 2 种群初始化通常有两种方法，一种是完全随机生成；另一种是完全随机生成。另一种是根据一定的先验知识生成一组必须满足的要求，并从满足这些要求的解决方案中随机选择样本。已经证明，在二进制编码的前提下，如果个体长度为L，则种群大小的最优值为[即完全解。但这个数字通常很大，所以通常是20-100。 3、个体评价适应度函数的选择直接影响遗传算法的收敛速度以及能否找到最优解。对于一般的优化问题，通常直接选择目标。函数作为适应度函数。在计算适应度时，常用的处理不可行解的方法有修正法和罚函数法。实验证明该修正方法优于罚函数法。 4 遗传算子[全局：选择； local：交叉、变异选择：其基础是适者生存理论，指导GA搜索向整个搜索空间中最有利的区域发展。确定适当的选择压力很重要。在进化初期保持低压可以保持种群多样性，而在进化后期选择高压可以加快收敛速度。常用的选择机制包括轮盘赌、确定性选择、混合选择等。
交叉和突变：分别模拟生物世界中的有性生殖过程和基因突变现象。常用的方法包括单点交叉、多点交叉、随机化、插入和交换突变。 5、参数选择；对于一般问题，通常需要确定的主要参数有：迭代次数；人口规模；交叉和变异概率。这些参数的变化对算法的性能有非常明显的影响，需要针对不同的问题具体分析。遗传算法的特点 遗传算法的主要特点是群体搜索策略和群体中个体之间的信息交换。具体来说，它具有与传统算法不同的优点：多点并行计算、计算速度快、避免收敛。它基于局部最优解；通过目标函数计算匹配度，对问题依赖性小；在解空间中执行高效的启发式搜索，而不是盲目穷举；具有广泛的应用范围；计算简单，功能强大，适合解决大规模问题。复杂的问题。 0-1背包问题问题描述：给定背包的m种资源，如尺寸、承载能力等，其中第j种资源的值为j=1,2,...,米；给出n项，其中第i项的值为，对应资源j的占用为，i=1,2...n。受背包条件的限制，如果只能选择一部分物品放入背包，那么如何选择物品才能最大化背包内物品的价值呢？数学描述为： 其中：f表示放入背包的物品的总价值；参数 > 0, > 0,0