《用遗传算法解决0-1背包问题要点.pdf》由会员分享，可在线阅读，更多相关《用遗传算法解决0-1背包问题要点.pdf（15页珍藏版）》请在三一文库上搜索。
1、实现遗传算法的0-1 背包问题 求解及其改进 姓名： 学号： 班级： 提交日期： 2012 年 6 月 27 日 实现遗传算法的0-1 背包问题求解 摘要：研究了遗传算法解决0-1 背包问题中的几个问题： 1） 对于过程中不满足重量限制条件的个体的处理, 通过代换上代最优解保持种群的进化性 2） 对于交换率和变异率的理解和处理方法, 采用逐个体和逐位判断的处理方法 3） 对于早熟性问题 , 引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。 4） 一种最优解只向更好进化方法的尝试。 通过实际计算比较表明, 本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算 效率。通
2、过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。 关键词：遗传算法；背包问题；优化 1. 基本实现原理： 一、问题描述 0-1 背包问题属于组合优化问题的一个例子，求解0-1 背包问题的过程可以被视作在很 多可行解当中求解一个最优解。01 背包问题的一般描述如下： 给定 n 个物品和一个背包，物品i 的重量为 Wi，其价值为 Vi，背包的容量为C。选择合适 的物品装入背包， 使得背包中装入的物品的总价值最大。注意的一点是， 背包内的物品的重 量之和不能大于背包的容量C 。在选择装入背包的物品时，对每种物品i 只有两种选择：装 入背包或者不装入背包，即只能将物品i 装入背包
3、一次。称此类问题为0/1 背包问题。 其数学模型为： 0-1 背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有 效地解决 0-1 背包问题。遗传算法（ Genetic Algorithms）则是一种适合于在大量的可行解中 搜索最优（或次优）解的有效算法。 二、遗传算法特点介绍 : 遗传算法 (Genetic Algorithm, GA) 是 1962 年 Holland 教授首次提出了GA算法的思想是近 年来随着信息数据量激增， 发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观 点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。 基本遗传算
4、法求解步骤： Step 1 参数设置： 在论域空间 U 上定义一个适应度函数f(x)，给定种群规模N，交叉率 Pc 和变异率 Pm，代数 T； Step 2 初始种群： 随机产生 U 中的 N 个染色体 s1, s2, , sN，组成初始种群 S=s1, s2, , sN， 置代数计数器 t=1； Step 3计算适应度：S中每个染色体的适应度f() ； Step 4 判断： 若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。 Step 5 选择-复制： 按选择概率 P(xi)所决定的选中机会，每次从S中随机选定 1 个染色体并 将其复制，共做 N 次，然后将复制所得的N 个染
5、色体组成群体S1； Step 6 交叉： 按交叉率 Pc所决定的参加交叉的染色体数c，从 S1中随机确定 c 个染色体， 配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2； Step 7 变异： 按变异率 Pm所决定的变异次数m，从 S2中随机确定 m 个染色体，分别进行 变异操作，并用产生的新染色体代替原染色体，得群体S 3； Step 8 更新： 将群体 S3作为新一代种群，即用S3代替 S ，t=t+1，转步 3； 遗传算法是一种仿生算法 , 即模拟生命演化的算法，它从一个代表问题初始解的初始种 群出发 , 不断重复执行选择, 杂交和变异的过程, 使种群进化越来越接近某一目标
6、既最优 解，如果视种群为超空间的一组点, 选择、杂交和变异的过程即是在超空间中进行点集之间 的某种变换 , 通过信息交换使种群不断变化，遗传算法通过模拟达尔文 “优胜劣汰 , 适者生 存”的原理激励好的结构, 同时寻找更好的结构 , 作为一种随机的优化与搜索方法, 遗传算 法有着其鲜明的特点。 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后 才找到解 (如果搜索成功的话 )。 遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜 索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。 遗传算法总是在寻找优解(最优解或次优解 ), 而
7、不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解 (当然包括优解 ), 所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集 (种群)的搜索 ,而不像图 搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索, 适合大 规模并行计算 , 而且这种种群到种群的搜索有能力跳出局部最优解。 遗传算法的适应性强 , 除需知适应度函数外 , 几乎不需要其他的先验知识。 遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性 , 能以 很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。 3.程序步骤： 一、 使
8、用基本遗传算法解决0- 1背包问题： 1: 打开数据文件 2: 设置程序运行主界面 3: 调用初始化种群模块 3- 1: 按照一定的种群规模和染色体长度以基因为单位用随机产生的0- 1对个体赋值 3- 2: 调用计算适应度函数 4: 以最大进化代数为循环终止条件开始进行循环 4- 1: 调用产生新一代个体的函数 4- 1- 1: 调用选择函数 4- 1- 2: 调用交叉函数 4- 1- 3: 调用变异函数 4- 1- 4: 调用计算适应度函数 5: 调用计算新一代种群统计数据函数 6: 调用输出新一代统计数据函数 7: 返回到第四步 , 直至循环结束 二、 基本遗传算法解决0- 1背包问题存在
9、的不足： 1.对于过程中不满足重量限制条件的个体的处理 在用基本遗传算法解决0- 1 背包问题的时候， 在初始化或者交叉变异后可能会产生不满 足重量约束条件的伪解， 而对于这些伪解， 基本遗传算法没有给出一个很好的处理方法，而 只是又随机生成了一个满足约束条件的解作为新的个体从而替换掉原来的个体。根据遗传算 法的根本思想“优胜劣汰，适者生存”的原则，可以将不满足条件的个体用已有的最优个体 来进行替换，这样，既使得种群中所有的个体均满足重量的约束条件，又保留了较优解， 符 合遗传算法的思想。 具体做法为： 在程序中加入一个变量保存每代的最优解，当前代在进行选择、复制、交叉、变异后如 果有不满足约
10、束条件的个体，则在种群更新时采用这个最优值作为替代。 具体做法为：在每代遗传后通过函数FindBestandWorstIndividual()找到当前最优值并保存 bestindividual 中，在计算适应度函数CalculateFitnessValue() 中加入： if(wKW) Xi=bestindividual; / 如果不是解，找最好的一个解代之 其中 w 为当前个体的总重量，KW为背包最大承重量，Xi表示种群中第 i个个体， bestindividual 为保存的个体最优解。 2.对于交换率和变异率的理解和处理方法 根据遗传算法的基本步骤的交叉和变异操作 Step 6 交叉： 按
11、交叉率 Pc所决定的参加交叉的染色体数c，从 S1中随机确定 c 个染色体， 配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S 2； Step 7 变异： 按变异率 Pm所决定的变异次数m，从 S2中随机确定 m 个染色体，分别进行 变异操作，并用产生的新染色体代替原染色体，得群体S3； 可以有两种处理方法： 其一，采用先确定数目在随机选取的方法，步骤如下： 对于交叉操作： 1,根据交叉率确定应该交叉的个体数目 n 2,在种群中进行 n 次循环 2-1 随机选中种群中的一个个体a 2-2 随机选中种群中异于a 的一个个 体 b 2-3 随机确定交叉位数 2-4 进行交叉 对于变异操作
12、： 1,根据变异率确定应该变异的染色体数 目 n 2,在种群中进行 n 次循环 2-1 随机选中种群中的一个个体的染 色体 a 2-2 随机选中染色体 a 的某位基因 2-3 对进行 0-1 互换变异 其二，采用对每个操作单元分别进行特定概率下处理的方法，步骤如下： 对于交叉操作： 1,在种群中进行S次循环 ,其中 S代表种群中个体的 数量 2,对于每一个个体Xi（X 为种群数组）做如下操 作 2-1 生成随机数p 0,1,判断 p 与的大小关系 2-2 如果 p说明 Xi需要交换 2-2-1 随机在种群中找到异于Xi的另一 个体进行交换 2-3 如果 p说明 Xi不需要交换 对于变异操作：
13、1,在种群中进行S次循环 ,其中 S代表种群中个体的 数量 2,对每一个个体Xi做 N 次循环，其中N 为染色体 位数 2-1 对染色体的每一位 3-1 生成随机数q0,1,判断 q 与 的大小关系 3-2 如果 q说明需要进行0-1 互换 变异 2-3 如果 q说明不需要变 分析这两种处理方法可知： 方法一没有很好地体现随机机会均等的思想，因为在步骤 1 中确 定的需要操作的数目n 后，总体上是保证了交叉或者变异的数目，但不是对于每一个个体 而言的，因而会出现有的个体被选择交叉或者变异多次而有的没有机会交叉或者变异的情 况，而如果采用方法二， 就体现了机会的均等性， 即要求对每一个单元操作目
14、标进行概率的 验证，以确定是否变异或者交叉。在程序中具体的实现方法体现在交叉和变异函数中： void CrossoverOperator(void)/ 交叉操作 for(i=0; iN*0.5)/ 大于 50%作为判定为早熟 / 确定最小 int minindex=0; for(intn=0;nKW)return -1; return (bestindividual.fitnessfit?-1:1);/如果小于原来值或者不满足重量函数，则返回-1 三、 改进的遗传算法解决0- 1 背包问题： 1、参数设置： #define S 500 / 种群的规模 #define Pc 0.8 / 交叉概率
15、 #define Pm 0.01 / 突变概率 #define KW 878 / 背包最大载重 #define N 20 / 物体总数 #define T 1000 / 最大换代数 2 个体的表示和染色体编码 用变量 i 代表物件 , i = 1, 2, ,n 定义变量 xi，其含义为：xi= 1表示：第 i 个物件被选入背 包, xi = 0表示第 i 个物件没有被选入背包。考虑n 个物件的选择与否 , 就可以得到一个长度 为 n 的 0, 1 序列。 由此可见遗传算法应用于上述背包问题时,采用简单二进制编码较为适宜 1 每一组编码即为某一个个体的基因表示, 称其为染色体 , 染色体长度取决
16、于待分配的物件 的个数 n.在编码形式的表示方法中,形如二进制编码10010101 表示为一个待分配的物件的 个数为 8（编码长度）的一个背包问题的一个解, 则该个体对应于选择了物件1, 4, 6, 8，即 第 1, 4, 6, 8个物品被放入了背包。用数据格式表示为： struct individual / 个体结构体 bool chromsomeN; / 染色体编码 double fitness; / 适应度 / 即本问题中的个体所得价值 double weight; / 总重量 ; 2 产生初始种群 n 个待分配的物件随机产生S个长度为 n 的二进制串 , 即种群中个体的染色体编码的每一
17、位 按等概率在 0 与 1 中选择 S 指的是种群规模 , 即种群中的个体数目 . void GenerateInitialPopulation(void); / 初始种群 3 适应度函数 背包内物件的总重量为a1x1 + a2x2 + ,anxn, 物件的总价值为 c1x1 + c2x2 + , + cn xn 0-1 背包问题中采用每个个体的总价值作为适应度，在满足背包容量的条件下，价值越大， 适应度越高。所以适应度求解方法为： f i = c1x1 + c2x2 + , + cnxn ( 当 t a1x1 + a2x 2 + , + anxn c ，xj = 0, 1) 上述适应度函数基
18、于一个考虑违背约束条件的惩罚处理，根据上述具体问题适应度函数值不 可能为零 , 所以当随机产生的某个个体违背约束条件时, 通过把其适应度函数值罚为0 而达 到淘汰该个体的目的。 4 选择-复制操作 参照适应度函数值和约束条件用赌轮选择法进行模拟，具体为 ( 1)根据适应度函数值和约束条件, 罚掉部分个体（前述不满足容量条件的个体） (2)对于满足约束条件的个体, 根据适应度函数值计算个体被选中的概率,称为选择概 率： 公式为 : P= p()称为染色体 xi(i=1, 2, , n)的选择概率 (3)根据轮盘赌累计公式为： 称为染色体 xi(i=1, 2, , n)的积累概率 ( 4) 对已得
19、到的累计概率作如下处理，完成选择操作： 1）在 0, 1区间内产生一个均匀分布的伪随机数r。 2）若 rq1, 则染色体 x1 3） 若 qk-1 #include #include #include /* 小规模 * #define S 5 / 种群的规模 #define N 5 / 物体总数 #define Pc 0.8 / 交叉概率 #define Pm 0.05 / 突变概率 #define KW 100 / 背包最大载重 #define T 20 / 最大换代数 #define ALIKE 0.05 / 判定相似度 int stop=0; / 初始化函数中初始化为所有价值之和 int
20、 t=0; / 目前的代数 int weight=35,40,40,20,15; / 物体重量 int value=50,30,60,80,20; / 物体价值 /* 实例 1* #define S 5 / 种群的规模 #define N 20 / 物体总数 #define Pc 0.8 / 交叉概率 #define Pm 0.05 / 突变概率 #define KW 878 / 背包最大载重 #define T 800 / 最大换代数 #define ALIKE 0.05 / 判定相似度 int stop=0; / 初始化函数中初始化为所有价值之和 int t=0; / 目前的代数 int
21、weight=44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63; / 物体重量 int value=92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58; / 物体价值 /* 实例 2* #define S 5 / 种群的规模 #define Pc 0.8 / 交叉概率 #define Pm 0.05 / 突变概率 #define KW 1000 / 背包最大载重1000 #define N 50 / 物体总数 #define T 800 / 最大换代数 #defi
22、ne ALIKE 0.05 / 判定相似度 int stop=0; / 初始化函数中初始化为所有价值之和 int t=0; / 目前的代数 int vaue= 220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88 ,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1; int weight= 80,82,85,70,72,70,66,50,55,25,50,55,40
23、,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,25,30,45,30,60,50,20,65 ,20,25,30,10,20,25,15,10,10,10,4,4,2,1; /* 实例 3*/ #define S 5 / 种群的规模 #define Pc 0.8 / 交叉概率 #define Pm 0.05 / 突变概率 #define KW 6718 / 背包最大载重1000 #define N 100 / 物体总数 #define T 800 / 最大换代数 #define ALIKE 0.05 / 判定相似度 int stop=0; / 初始
24、化函数中初始化为所有价值之和 int t=0; / 目前的代数 int vaue= 597,596,593,586,581,568,567,560,549,548,547,529,529,527,520,491,482,478,475,475,466,462,459,458,454,45 1,449,443,442,421,410,409,395,394,390,377,375,366,361,347,334,322,315,313,311,309,296,295,294,289,285, 279,277,276,272,248,246,245,238,237,232,231,230,225,
25、192,184,183,176,171,169,165,165,154,153,150,149,14 7,143,140,138,134,132,127,124,123,114,111,104,89,74,63,62,58,55,48,27,22,12,6,250; Int weight= 54,183,106,82,30,58,71,166,117,190,90,191,205,128,110,89,63,6,140,86,30,91,156,31,70,199,142,98,178,16,1 40,31,24,197,101,73,16,73,2,159,71,102,144,151,27
26、,131,209,164,177,177,129,146,17,53,64,146,43,170,180,17 1,130,183,5,113,207,57,13,163,20,63,12,24,9,42,6,109,170,108,46,69,43,175,81,5,34,146,148,114,160,174,156 ,82,47,126,102,83,58,34,21,14; /*/ struct individual / 个体结构体 bool chromsomeN; / 染色体编码 double fitness; / 适应度 / 即本问题中的个体所得价值 double weight;
27、/ 总重量 ; int best=0; int same=0; individual XS,YS,bestindividual;/ /*/ int comp(individual bestindividual,individual temp); / 比较函数 void checkalike(void); / 检查相似度函数 void GenerateInitialPopulation(void); / 初始种群 void CalculateFitnessValue(void); / 适应度 void SelectionOperator(void); / 选择 void CrossoverOpe
28、rator(void); / 交叉 void MutationOperator(void); / 变异 void FindBestandWorstIndividual(void); / 寻找最优解 void srand(unsigned int seed); / 随机生成 /*/ int comp(individual bestindividual,individual temp)/比较函数 int fit=0,w=0;/ 第一种不变 :操作后不满足重量函数，第二种:操作后适应度小于操作前 for(int i=0;iKW)return -1; return (bestindividual.fi
29、tnessfit?-1:1);/如果小于原来值或者不满足重量函数，则返回-1 /*/ void Checkalike(void) int i=0,j=0; for( i=0;iN*ALIKE)/ 大于 ALIKE作为判定为早熟 int minindex=0; for(int n=0;nKW) i-; / 如果不是解，重新生成 else Xi.fitness=v; Xi.weight=w; if(v=stop)bestindividual=Xi;return;/这种情况一般不会发生 /*/ void CalculateFitnessValue() int i=0,j=0; for (i=0; i
30、KW) Xi=bestindividual; / 如果不是解，找最好的一个解代之 /*/ void SelectionOperator(void) int i, index; double p, sum=0.0; double cfitnessS;/ 选择、累积概率 individual newXS; for (i=0;icfitnessindex)/轮盘赌进行选择 index+; newXi=Xindex; for (i=0; ibestindividual.fitness) bestindividual=Xi; best=i; /* 主函数 */ void main(void) srand
31、(unsigned)time(0); t=0; GenerateInitialPopulation(); /初始群体包括产生个体和计算个体的初始值 while (t=T) FindBestandWorstIndividual(); / 保存当前最优解 SelectionOperator(); / 选择 CrossoverOperator(); / 交叉 MutationOperator(); / 变异 Checkalike(); / 检查相似度 CalculateFitnessValue(); / 计算新种群适应度 t+; FindBestandWorstIndividual(); / 找到最优解 coutbestindividual.fitnessendl / 输出最优值 bestindividual.weightendl; / 对应重量 for(int k=0;kN;k+)coutbestindividual.chromsomek;/输出最优解 coutendl; /* 结束 */