下载文档原格式
数学建模遗传算法例题数学建模中，遗传算法是一种基于进化思想的优化算法，可以应用于复杂的优化问题中。
本文将介绍一些遗传算法的例题，帮助读者更好地理解遗传算法的应用。
例题一：背包问题有一个体积为V的背包和n个物品，第i个物品的体积为vi，价值为wi。
求这个背包最多能装多少价值的物品。
遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群。
2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。
3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。
4. 交叉：对被选中的个体进行交叉操作，生成新的个体。
5. 变异：对新的个体进行变异操作，引入新的基因。
6. 重复以上步骤，直到符合终止条件。
在背包问题中，适应度函数可以定义为：背包中物品的总价值。
交叉操作可以选择单点交叉或多点交叉，变异操作可以选择随机变异或非随机变异。
例题二：旅行商问题有n个城市，旅行商需要依次经过这些城市，每个城市之间的距离已知。
求旅行商经过所有城市的最短路径。
遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群，每个个体代表一种旅行路线。
2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。
3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。
4. 交叉：对被选中的个体进行交叉操作，生成新的个体。
5. 变异：对新的个体进行变异操作，引入新的基因。
6. 重复以上步骤，直到符合终止条件。
在旅行商问题中，适应度函数可以定义为：旅行商经过所有城市的总距离。
交叉操作可以选择顺序交叉或部分映射交叉，变异操作可以选择交换或反转基因序列。
总结：遗传算法是一种强大的优化算法，可以应用于多种复杂的优化问题中。
在数学建模中，遗传算法的应用也越来越广泛。
本文介绍了背包问题和旅行商问题的遗传算法解决步骤，希望对读者有所帮助。
遗传算法解决01背包问题2015 ～2016 学年第二学期学生姓名专业学号2016年 6 月目录一：问题描述 (3)二：遗传算法原理及特点 (3)三：背包问题的遗传算法求解 (3)1.文字描述 (3)2.遗传算法中的抽象概念在背包问题的具体化 (3)3.算法求解的基本步骤 (4)四：算法实现 (4)1.数据结构 (4)2.部分代码 (5)五：结论 (8)六：参考文献 (8)一、问题描述0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。
01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。
问应如何选择合适的物品装入背包，使得背包中装入的物品的总价值最大。
注意的一点是，背包内的物品的重量之和不能大于背包的容量C。
在选择装入背包的物品时，对每种物品i只有两种选择：即装入背包或者不装入背包，不能讲物品i装入背包多次，也不能只装入部分的物品，称此类问题为0/1背包问题。
二、遗传算法原理及特点遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
遗传算法有着鲜明的优点：(1)遗传算法的操作对象是一组可行解,而非单个可行解;搜索轨道有多条,而非单条,因而具有良好的并行性.(2)遗传算法只需利用目标的取值信息,而无需递度等高价值信息,因而适用于任何规模,高度非线形的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强的通用性.(3)遗传算法择优机制是一种“软”选择,加上良好的并行性,使它具有良好的全局优化性和稳健性.(4)遗传算法操作的可行解集是经过编码化的(通常采用二进制编码),目标函数解释为编码化个体(可行解)的适应值,因而具有良好的可操作性与简单性.三、背包问题的遗传算法求解1、文字描述0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。
遗传算法求解背包问题程序实现一、背包问题描述背包问题是著名的NP 完备类困难问题,对这个问题的求解前人已经研究出了不少的经典的方法,对该问题确实能得到很好的结果。
近年来蓬勃发展起来的遗传算法已被广泛地应用于优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用遗传算法克服了传统优化方法的缺点,借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制. 本程序将遗传算法应用于背包问题。
二、实验程序1、编程语言：C++2、开发环境：Microsoft Visual Studio 20053、程序整体流程：步1初始化过程1. 1确定种群规模scale、杂交概率pc、变异概率pm、染色体长度chN及最大进化代数maxgen。
1. 2取x1′(0) = u (0 ,1) , x2′(0) = u (0 ,1) , …, xchN′(0) = u (0 ,1) ,其中函数u (0 ,1) 表示随机地产生数0 或1 ,则x (0) = ( x1 (0) , x2 (0) ,⋯, xN (0) ) .若不满足约束条件,则拒绝接受. 由(1. 2) 重新产生一个新的染色体; 如果产生的染色体可行,则接受它作为种群的一名成员,经过有限次抽样后, 得到scale个可行的染色体xj (0) , j =1 ,2 , ⋯, M ,设xj (0) 的染色体编码为vj (0) ,并记为v (0) = ( v1 (0) , ⋯, vchN (0) ) .1. 3计算各个染色体的适值1. 4 置k = 0步2选择操作2. 1采用转轮法选择下一代。
.步3杂交变异操作3. 1 事先定义杂交操作的概率pc ,为确定杂交操作的父代,从j = 1 到M 重复以下过程:从[0 ,1 ] 中产生随机数r ,若r < pc ,则选择cj′( k)作为一个父代.3. 2 产生两个[1 , N ] 上的随机整数i 、j ,变异的结果为染色体vj′( k)的第i 位基因的值变为其第j 位基因的值,同样将染色体的vj′( k)第j 位基因的值变为其第i 位基因的值.3. 3 检验该染色体的可行性,若可行则作为变异的结果;如不可行,重复3. 2 直至该染色体可行.3. 4 事先定义变异概率pm ,对经过杂交操作的中间个体进行变异操作: ,如果r < pm ,则选择vi″( k) 作为变异的父代.3. 5 产生一个[1 , N ] 上的随机整数i ,及随机地产生数0 或1 , 记为b , 变异的结果为染色体vi″( k) 的第i 位基因的值变为b.3. 6 检验该染色体的可行性,若可行则作为变异的结果:如不可行,重复3. 5 直至该染色体可行.3. 7 计算新个体的适应值,并把它们同时放回,和步2 选择操作中剩余的个体一起构成新一代种群v ( k + 1) = { v1 ( k + 1) , v2 ( k + 1) , ⋯, vM ( k + 1) } .步4 终止检验如果达到最大进化代数maxgen 则终止演化,否则置k : = k + 1 ,转步2.4、程序流程图程序流程图5、程序代码1）主程序代码：KnapsacksProblem.cpp文件#include "GAonKP.h"#include <iostream>using namespace std;void main(){FILE* fp;CGAonKP gakp;int scale; //种群规模double MaxWeight; //背包允许最大财宝质量double pc; //杂交概率double pm; //变异概率int maxgen; //最大进化代数char filename[256];cout<<"遗传算法解决背包问题程序使用说明："<<endl;cout<<"1、该背包问题采用遗传算法"<<endl;cout<<"2、-1编码的方法，其中代表选中所对应的物品，代表不选中该物品"<<endl;cout<<"3、背包允许最带重量，种群规模（解空间大小），";cout<<"杂交概率，变异概率，最大进化代数需自己给";cout<<"定，程序会提示输入"<<endl;cout<<"4、程序提供一个输入示例"<<endl;cout<<"5、输入文件可加单行或多行注释"<<endl;cout<<"例如：#添加单行注释内容#"<<endl;cout<<"例如：#添加多行注释内容"<<endl;cout<<" 添加多行注释内容#"<<endl;cout<<"6、输入文件头位置需指定物品个数为int型数据。
遗传算法求解0-1背包问题一、问题描述给定n种物品和容量为C的背包。
物品i的重量是wi，其价值为vi。
问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?二、知识表示1、状态表示（1）个体或染色体：问题的一个解，表示为n个比特的字符串，比特值为0表示不选该物品，比特值为1表示选择该物品。
（2）基因：染色体的每一个比特。
（3）种群：解的集合。
（4）适应度：衡量个体优劣的函数值。
2、控制参数（1）种群规模：解的个数。
（2）最大遗传的代数（3）交叉率：参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为0.4～0.99。
（4）变异率：发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围一般为0.0001～0.1。
3、算法描述（1）在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；（2）随机产生U中的N个个体s1, s2, …, sN，组成初始种群S={s1, s2, …, sN}，置代数计数器t=1；（3）计算S中每个个体的适应度f() ；（4）若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。
（5）按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；（6）按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；（7）按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；（8）将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3。
三、算法实现1、主要的数据结构染色体：用一维数组表示，数组中下标为i的元素表示第（i+1）个物品的选中状态，元素值为1，表示物品被选中，元素值为0表示物品不被选中。
种群：用二维数组表示，每一行表示一个染色体。
遗传算法的过程：初始化：将计划装入背包的每个物品看成一个二进制串的一位，为1表示放入该物品，为0表示不放入该物品。
初始种群的产生：初始化前对放入背包物品数的一个预测（背包容积/物品最大体积），接下来只要在种群每条染色体中保证有（背包容积/物品最大体积）个为1的位初始化就完成了。
选择：选择进行杂交的父代染色体，被选中的父代染色体总是若干个染色体中最优（适应度最高）的，来保证向优化的方向发展。
详细的选择方法：随机产生2个数：Chrom_Cross_From, Chrom_Cross_To,当然得采用一定的手段来保证前者比后者小。
从Chrom_Cross_From到Chrom_Cross_To这Chrom_Cross_To-Chrom_Cross_From+1条染色体中选择最优（适应度最大）的染色体作为父代之一。
需要进行两次选择得到杂交的两条父代染色体。
这样做可以保证算法不会过早收敛。
函数实现：Individual Select(int ChromSize,Individual Pop[]){int Num_Selected,i,j,Chrom_Selected_From,Chrom_Selected_To,temp;Individual *Chrom_Selected;do{Chrom_Selected_From=rand()%PopSize;Chrom_Selected_To=rand()%PopSize;if(Chrom_Selected_From>Chrom_Selected_To){temp=Chrom_Selected_From;Chrom_Selected_From=Chrom_Selected_To;Chrom_Selected_To=temp;}Num_Selected=Chrom_Selected_To-Chrom_Selected_From+1;}while(Num_Selected<=0);Chrom_Selected=new Individual[Num_Selected];for(i=0;i<Num_Selected;i++)Chrom_Selected[i].chrom=new int[ChromSize];for(i=0,j=Chrom_Selected_From;i<Num_Selected,j<Chrom_Selected_To+1;i++,j++){Chrom_Selected[i]=Pop[j];}Order_Best_First(ChromSize,Num_Selected,Chrom_Selected);Chrom_Selected[0].fitness=Fitness(Chrom_Selected[0].chrom,ChromSize);return Chrom_Selected[0];}杂交：将两次选择得到的父代染色体进行杂交得到一条新的染色体，作为较新种群（并非新的种群）的一条染色体，杂交直到较新种群的染色体数等于原种群的染色体数。
遗传算法考试题目
题目1：使用遗传算法求解旅行商问题。
假设有一位旅行商需要拜访n个城市，每个城市只能访问一次，并且从一个城市回到起始城市。
每个城市之间都有距离，求解旅行商经过的最短路径。
题目2：使用遗传算法优化函数f(x)=x^2-4x+4，求解使得f(x)取得最小值的x。
题目3：使用遗传算法求解背包问题。
假设有一个背包的容量为C，同时有n个物品，每个物品有自己的重量和价值。
要求
选择一些物品放入背包中，使得背包内物品的总重量不超过C，并且物品的总价值最大。
题目4：使用遗传算法进行图像压缩。
假设有一张彩色图像，每个像素点都有RGB三个分量的值。
要求使用遗传算法对这
张图像进行压缩，使得图像的质量损失最小化的情况下，压缩比最大化。
题目5：使用遗传算法优化神经网络结构。
假设有一个神经网络，其层数和每层的节点数都是可调整的。
使用遗传算法搜索出最优的神经网络结构，使得在给定的数据集上，神经网络的预测性能最好。
一种有效求解多维背包问题的遗传算法摘要：就多维背包问题的求解，提出一个基于遗传算法的启发式算法（MKPGA）。
该算法中加入了一个利用问题特性知识的启发式修复算子以帮助求解。
测试实例使用270个不同特性的多维背包问题，实验结果表明，该算法对多维背包问题的求解十分有效，能获得不同特性问题的高质量解。
关键词：遗传算法;多维背包问题;贪婪算法遗传算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，对它的研究起源于20世纪70年代初，由美国Michigan 大学的J.Holland教授于1975年正式提出。
GA的主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。
它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。
2求解MKP的遗传算法设计MKPGA使用了一个基于简单贪婪算法的修复算子来修复交叉、变异操作后可能产生违反背包约束的不可行解。
虽然在标准遗传算法中并未提到修复算子的使用，但根据不同问题特性设计的修复算子被广泛应用在解决不同问题的遗传算法中。
MKPGA所采用的策略描述如下：①联赛选择方法；②一致交叉；③物品数小于500时变异概率取2／个体基因串长位，当物品数等于500时，变异概率取3/个体串长度；④不允许种群中有相同的个体；⑤每次迭代只产生一个不同于当前种群的新个体，如果新个体比当前种群中最差的个体好，则替换掉该最差个体。
3计算实验3.1实例本文使用的测试实例是由Beasley和Chu所提供的270个多维背包问题。
其中约束个数m包括5、10和30，物品数量n包括100、250和500，每一组m-n各有30个问题。
下面介绍这270个实例的生成方法。
物品j消耗资源i的量wij为一个均匀分布在区间（0，1 000）上的整数。
对于每一个m-n的组合，每个资源约束bi=α∑nj=1wij，α是问题的紧密比，前十个问题的α取0.25，接下来十个问题的α取0.50，最后十个问题的α取0.75。
智能所“暑期学校”科研实习报告题目：用遗传算法求解多维背包问题姓名：吴逊专业：智能科学与技术指导老师姓名、职务：尚荣华副教授日期：二零一一年八月摘要首先简单介绍了基本的遗传算法。
然后将贪婪算法与简单遗传法相结合构成一种混合遗传算法,用该混合遗传算法求解背包问题。
通过对标准测试集中的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 种资源取值c j ,j=1,2,...,m;另给定n 件物品，其中第i 件物品的价值为p i ，对应资源j 的占用量为a ij ,i=1,2...n 。
受背包条件限制，若只能挑选一部分物品装入背包，那么如何选择物品使背包装入物品的价值最大，数学描述为：⎪⎪⎪⎩⎪⎪⎪⎨⎧∈==≤==∑∑==}1,0{},,...,,{,...,2,1,..,...,2,1,)(max 2111i n n i j ij i n i i i x x x x x m j c a x t s ni p x x f 式中：f(x)表示装入背包物品的总价值；参数c j >0,p i >0,0<a ij <c j ；x=(x 1,x 2,...x n )表示一组物品的选择策略，x i =i 表示物品j 被选中放入背包，x i =0表示物品i 没有被选中。
当m 取值为1时，问题即变为简单0-1背包问题。
背包问题属典型的组合优化问题，并且是NP 难问题。
已有的求解方法可分为精确算法，如枚举法，动态规划法，分支定界法，图论法等指数级方法以及近似算法，如贪婪算法，遗传算法，免疫算法等两大类。
背包问题的研究对于解决复杂组合优化问题有重要的意义。
第三章 用遗传算法求解多维0-1背包问题4.1 算法描述本章将采用一种将贪婪算法与遗传算法相结合的混合遗传算法来求解多维背包问题，并将此算法与简单遗传算法和贪婪算法进行对比，以提供一种利用遗传算法求解问题的新思路。
传统的贪婪算法是基于价值密度的，例如物品单位体积价值或单位质量价值。
这在一维背包问题中很适合，但是对于多维背包问题就需要做一下修改，因为包的限制条件有多个（如体积、质量等），无法只用上述简单的价值密度来解决。
为此，我们提出了“综合价值密度”的概念，所谓“综合价值密度”就是对各种单一价值密度的综合，用ρ来表示，具体定义如下：ρi =p i /v i其中k j =c j /∑c j m 1 ，v i =∑a ij /k j n 1这种方法可以认为是将多种不同的资源整合为一种虚拟的“总资源”，v i表示第i 种物品占用“总资源”的加权量。
k j 的意义是包的对第j 种资源限制的相对大小，k j 越大说明包对对第j 种资源限制的越小，所以在该种资源在v i 中占的比例就越小。
用贪婪算法求解多维0-1背包问题的步骤如下： Step1：求解各物品的价值密度ρ；Step2:将物体按ρ由大到小的顺序排序。
不妨记新的排序为{1,2,…,n }； Step3:若对任意一种资源j,均有 ∑a ij x i k−1i=1+a kj ≤c j ,则x k =1,否则x k =0.k=k+1；Step4：IF k=n+1 stop;ELSE return step3.贪婪算法简单直观，易于理解，但并不能保证能得到全局最优解。
在简单遗传算法中加入适当的局部搜索方式，利用启发式信息或与领域相关的知识，使得算法既具有遗传算法的整体优化等特性，又能加快算法的收敛速度，从而在求解各类应用问题中具有更大的优越性，这样的算法称为混合遗传算法。
遗传算法的几个步骤（编码，初始化，选择，交叉，变异等）已经有许多很好的方法，例如轮盘赌选择法、单点交叉等，这些方法简单，效果好，而且有通用性，我们可以直接用来解决各种问题。
解决多维背包问题的关键在于包的限制条件的处理，遗传算法中经过交叉、变异的个体是随机的，很可能不满足包的限制条件，所以要用合理的修复算法修复每个个体使其满足限制条件。
基于对以上分析，可以利用在简单遗传算法中加入用基于上述贪婪算法的修复算法，这样既能将不可行解改造成可行解，又能使个体趋于较好的解。
