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