实现遗传算法的0-1背包问题 求解及其改进
姓名：
学号：
班级：
提交日期：
实现遗传算法的0-1背包问题求解
摘要：研究了遗传算法解决0-1背包问题中的几个问题：
1） 对于过程中不满足重量限制条件的个体的处理, 通过代换上代最优解保持种群的进化性 2） 对于交换率和变异率的理解和处理方法, 采用逐个体和逐位判断的处理方法
3） 对于早熟性问题, 引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。 4） 一种最优解只向更好进化方法的尝试。
通过实际计算比较表明, 本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。
关键词：遗传算法；背包问题 ；优化
1. 基本实现原理： 一、问题描述 0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：
给定n 个物品和一个背包，物品i 的重量为Wi ，其价值为Vi ，背包的容量为C 。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C 。在选择装入背包的物品时，对每种物品i 只有两种选择：装入背包或者不装入背包，即只能将物品i 装入背包一次。称此类问题为0/1背包问题。 其数学模型为：
0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。 二、遗传算法特点介绍:
遗传算法(Genetic Algorithm, GA)是1962年Holland 教授首次提出了GA 算法的思想是近年来随着信息数据量激增，发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。 基本遗传算法求解步骤：
Step 1 参数设置：在论域空间U 上定义一个适应度函数f (x ) ，给定种群规模N ，交叉率P c 和变异率P m ，代数T ；
Step 2 初始种群：随机产生U 中的N 个染色体s 1, s 2, …, s N ，组成初始种群S ={s 1, s 2, …, s N }，置代数计数器t =1；
Step 3 计算适应度：S 中每个染色体的适应度f() ；
Step 4 判断：若终止条件满足，则取S 中适应度最大的染色体作为所求结果，算法结束。 Step 5 选择-复制：按选择概率P (x i ) 所决定的选中机会，每次从S 中随机选定1个染色体并将其复制，共做N 次，然后将复制所得的N 个染色体组成群体S 1；
Step 6 交叉：按交叉率P c 所决定的参加交叉的染色体数c ，从S 1中随机确定c 个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S 2；
Step 7 变异：按变异率P m 所决定的变异次数m ，从S 2中随机确定m 个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S 3；
Step 8 更新：将群体S 3作为新一代种群，即用S 3代替S ，t =t +1，转步3； 遗传算法是一种仿生算法, 即模拟生命演化的算法，它从一个代表问题初始解的初始种群出发, 不断重复执行选择, 杂交和变异的过程, 使种群进化越来越接近某一目标既最优解，如果视种群为超空间的一组点, 选择、杂交和变异的过程即是在超空间中进行点集之间的某种变换, 通过信息交换使种群不断变化， 遗传算法通过模拟达尔文“优胜劣汰, 适者生存”的原理激励好的结构, 同时寻找更好的结构, 作为一种随机的优化与搜索方法, 遗传算法有着其鲜明的特点。
—遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解(如果搜索成功的话) 。
—遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。
—遗传算法总是在寻找优解(最优解或次优解), 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解(当然包括优解), 所以遗传算法又是一种优化搜索算法。
—遗传算法的搜索过程是从空间的一个点集(种群) 到另一个点集(种群) 的搜索, 而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算, 而且这种种群到种群的搜索有能力跳出局部最优解。
—遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。
—遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束, 不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。 3. 程序步骤：
一、 使用基本遗传算法解决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背包问题存在的不足： 1. 对于过程中不满足重量限制条件的个体的处理 在用基本遗传算法解决0- 1背包问题的时候，在初始化或者交叉变异后可能会产生不满足重量约束条件的伪解，而对于这些伪解，基本遗传算法没有给出一个很好的处理方法，而
只是又随机生成了一个满足约束条件的解作为新的个体从而替换掉原来的个体。根据遗传算法的根本思想“优胜劣汰，适者生存”的原则，可以将不满足条件的个体用已有的最优个体来进行替换，这样，既使得种群中所有的个体均满足重量的约束条件，又保留了较优解，符合遗传算法的思想。 具体做法为： 在程序中加入一个变量保存每代的最优解，当前代在进行选择、复制、交叉、变异后如果有不满足约束条件的个体，则在种群更新时采用这个最优值作为替代。
具体做法为：在每代遗传后通过函数FindBestandWorstIndividual()找到当前最优值并保存bestindividual 中，在计算适应度函数CalculateFitnessValue()中加入：
if(w>KW) X[i]=bestindividual; //如果不是解，找最好的一个解代之
其中w 为当前个体的总重量，KW 为背包最大承重量，X[i]表示种群中第i 个个体，bestindividual 为保存的个体最优解。
2. 对于交换率和变异率的理解和处理方法 根据遗传算法的基本步骤的交叉和变异操作
Step 6 交叉：按交叉率P c 所决定的参加交叉的染色体数c ，从S 1中随机确定c 个染色体，配对进行交叉操作， 并用产生的新染色体代替原染色体，得群体S 2；
Step 7 变异：按变异率P m 所决定的变异次数m ，从S 2中随机确定m 个染色体，分别进行变异操作，并用产生的 新染色体代替原染色体，得群体S 3； 可以有两种处理方法：
其一，采用先确定数目在随机选取的方法，步骤如下：
对于交叉操作： 对于变异操作：
1, 根据交叉率确定应该交叉的个体数目1, 根据变异率确定应该变异的染色体数n 目n 2, 在种群中进行n 次循环 2, 在种群中进行n 次循环 2-1随机选中种群中的一个个体a 2-1随机选中种群中的一个个体的染2-2随机选中种群中异于a 的一个个色体a 体b
2-2随机选中染色体a 的某位基因
2-3随机确定交叉位数 2-4进行交叉
2-3对进行0-1互换变异
其二，采用对每个操作单元分别进行特定概率下处理的方法，步骤如下：
对于交叉操作：
1, 在种群中进行S 次循环, 其中S 代表种群中个体的数量
2, 对于每一个个体X[i]（X 为种群数组）做如下操作
2-1生成随机数p [0,1],判断p 与的大小关系 2-2如果p
说明X[i]需要交换
3-1生成随机数q [0,1],判断q 与
的大小关系
说明需要进行0-1互换
对于变异操作：
1, 在种群中进行S 次循环, 其中S 代表种群中个体的数量
2, 对每一个个体X[i]做N 次循环，其中N 为染色体位数
2-1对染色体的每一位
2-2-1 随机在种群中找到异于X[i]的另一个体进行交换 2-3如果p
说明X[i]不需要交换 3-2如果q
变异2-3如果q 说明不需要变
分析这两种处理方法可知：方法一没有很好地体现随机机会均等的思想，因为在步骤1中确定的需要操作的数目n 后，总体上是保证了交叉或者变异的数目，但不是对于每一个个体而言的，因而会出现有的个体被选择交叉或者变异多次而有的没有机会交叉或者变异的情况，而如果采用方法二，就体现了机会的均等性，即要求对每一个单元操作目标进行概率的验证，以确定是否变异或者交叉。在程序中具体的实现方法体现在交叉和变异函数中：
void CrossoverOperator(void)//交叉操作 for(i=0; i
do{p=rand()%S;//两个[0，S]的随机数 q=rand()%S; }while(p==q);
void MutationOperator(void)//变异操作 for (i=0; i
q=(rand()%1001)/1000.0;//产生q [0,1] if (q
if(X[i].chromsome[j]==1)X[i].chromsome[j]=0; else X[i].chromsome[j]=1;
int w=1+rand()%N;//[1,N]交换的位数
double p=(rand()%1001)/1000.0; if(p
2. 对于算法早熟性的分析及解决方法 遗传算法中种群中的个体由初始化时的具有多样性，可能会由于在进化过程中一些超常个体限制其它个体的进化——这个个体的适应度大大优于种群内的其它值，由于适者生存原则这个个体被不断复制从而充满了整个种群，使得种群的多样应大大降低，进化停滞，从而出现算法收敛于局部最优解的现象，称为早熟现象。 早熟现象的可能解法：
1） 通过提高变异率来增加种群的多样性，以期更优解的出现，这也是最简单基本遗传算法中不添加相关操作的情况下唯一的一种方法，然而这种方法有明显的弊端：在提高变异率获得多样性种群的同时，个体变异的机会增加，使得较优解发生变异，从而遗传算法丧失了其优于其它算法的优越性，所以这种方法不是很好地解决方法。 2） 引入多样性衡量和处理
基本思路：在出现进化停滞现象时要引入新的个体来增强种群的多样性。 做法：1, 判断是否达到早熟现象 对于种群中S 个个体，判断等位基因的相等程度，即引入一个参数值same, 如果same 达到一定的 理论值大小就可以认为达到了早熟现象。 2, 早熟现象的处理，即引入新的个体。 处理过程中应该不违反适者生存的原则，所以应该保留较好的个体，所以首先选中适应度最小的 个体执行删除操作，然后随机生成一个新的符合重量限制且打破早熟现象的新个体。
具体实现见函数：void checkalike(void)
if(same>N*0.5)//大于50%作为判定为早熟
//相似度校验 for( i=0;i
//确定最小 int minindex=0; for(intn=0;n
if(X[n].fitness
//重新生成 for (j=0; j
X[minindex].weight+=m*weight[j]; //个体的总重量
X[minindex].fitness+=m*value[j];
//个体的总价值
3. 一种最优解只向更好进化方法的尝试 基本思路为：每一组的最优解是一个独特的个体，我们求解的问题最终的最优解或者近似解都产生于这个特殊的个体，最优解只向更好进化方法中规定：每代中选出一个最优解并做好相应的记录或者标记，最优解参与交叉和变异，只是在交叉或者变异时对最优解进行前后适应度的比较，如果发现交叉或者变异后适应度大于操作前适应度，则保存操作后的结果，如果发现交叉或者变异后适应度小于操作前适应度，则禁止最优解的操作，而不禁止与最优解进行交叉的个体的变化。这样，每一代中的最优解的特性可以通过交叉传递给同代中的其它个体，而保证种群一定会向更好的方向进化。 做法在交叉后和变异后调用以下函数判断：
int comp(individual bestindividual,individual temp)//比较函数 { int fit=0,w=0;//第一种不变:操作后不满足重量函数，第二种:操作后适应度小于操作前 for(int i=0;iKW)return -1; return (bestindividual.fitness>fit?-1:1);//如果小于原来值或者不满足重量函数，则返回-1 }
三、 改进的遗传算法解决0- 1背包问题： 1、参数设置：
#define S 500 #define Pc 0.8 #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 每一组编码即为某一个个体的基因表示, 称其为染色体, 染色体长度取决于待分配的物件的个数n. 在编码形式的表示方法中, 形如二进制编码 10010101 表示为一个待分配的物件的个数为8（编码长度）的一个背包问题的一个解, 则该个体对应于选择了物件1, 4, 6, 8，即第1, 4, 6, 8个物品被放入了背包。用数据格式表示为：
struct individual { bool chromsome[N]; double fitness; double weight; };
//个体结构体
//染色体编码
//适应度//即本问题中的个体所得价值 //总重量
2产生初始种群
n 个待分配的物件随机产生S 个长度为n 的二进制串, 即种群中个体的染色体编码的每一位按等概率在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)
上述适应度函数基于一个考虑违背约束条件的惩罚处理，根据上述具体问题适应度函数值不可能为零, 所以当随机产生的某个个体违背约束条件时, 通过把其适应度函数值罚为0而达到淘汰该个体的目的。 4选择-复制操作
参照适应度函数值和约束条件用赌轮选择法进行模拟，具体为: ( 1)根据适应度函数值和约束条件, 罚掉部分个体（前述不满足容量条件的个体） (2)对于满足约束条件的个体, 根据适应度函数值计算个体被选中的概率, 称为选择概率： 公式为: P
=
p() 称为染色体x i (i =1, 2, …, n ) 的选择概率
(3)根据轮盘赌累计公式为： i
q =P (x j )
i ∑
j =1
称为染色体x i (i =1, 2, …, n ) 的积累概率
( 4) 对已得到的累计概率作如下处理，完成选择操作： 1）在［0, 1］区间内产生一个均匀分布的伪随机数r 。 2）若r≤q1,则染色体x1被选中。 3）若qk-1
对于每一个个体，根据交叉率P c 做如下操作： ( 1)随机产生一个交叉点的位置 ( 2)随机选取当前代中的两个个体作为父个体 ( 3)根据交叉点的位置, 做单点交叉 6变异操作: 根据变异率P m
( 1)随机产生变异点的位置 ( 2)在变异点位置作0- 1翻转 8、算法终止
程序中定义了一个最优值，stop=
一般情况下这个最优值达不到，一旦程序在执行过
程中达到此最优值，也就没有必要在执行下去，因为这必定是最好的解，所以保存最优值和最优解，结束。
如果程序的最优值达不到理想情况下的stop ，那么根据最大换代次数来结束程序，在结束后
的种群中找到一个最好的解作为本问题的最优解，程序结束。
4算例(可以使用参考文献[2]中的典型算例) ：
1. 小规模问题的算例：
算例1-1：设定物品价值value={50,30,60,80,20}重量weight{35,40,40,20,15}背包的最大承重量为100
遗传算法中参数：群体大小S=5，交叉率Pc=0.8,变异率Pm=0.05,最大换代次数T=20, 通过多次试验比较本文改进后遗传算法和其他得到结果如下表所示：
（右图中输出第一行数为最优价值；第二行数为重量；第三行为最优解）
本文改进的遗传算法： 实验总次数：30
达到全局最优解次数：27
未达到全局最优解：3 效果截图 由实验结果可知在小规模算例中，本文改进的遗传算法优于前两者。 2．较大规模问题求解算例： 遗传算法中参数：
群体大小S=5，交叉率Pc=0.8,变异率Pm=0.05,最大换代次数T=800，相似度取5% 实例1：
价值value ：{ 92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58} 重量weight ：{ {44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63}} 背包的最大承重量：878 实例2： 价值value ： {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}; 重量weight: {80,82,85,70,72,70,66,50,55,25,50,55,40,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}; 背包最大承重量：1000
实例3：
(说明：参考论文中的实例3价值数组中缺少一个值，这里以0补上，使价值和重量一一对应)
价值value ： {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,451,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,192,184,183,176,171,169,165,165,154,153,150, 149,147,143,140,138,134,132,127,124,123,114,111,104,89,74,63,62,58,55,48,27,22,12,6,0}; 重量
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,140,31,24,197,101,73,16,73,2,159,71,102,144,151,27,131,209,164,177,177,129,146,17,53,64,146,43,170, 180,171,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};
各运行30次后比较30次中的最好值, 比较结果如下本文改进的遗传算法和先前算法结果如下：
本文改进遗传算法实验结果：
实例1：（输出第一行数为最优价值；第二行数为重量；第三行为最优解）
实例2：
实例3：
根据得到最优解的情况本文改进的遗传算法所得最好值均好于先前两种算法，特别是实例3中，在缺少一个价值值补0的情况下得到的结果仍然优于前两种算法。 由此得出结论：本文改进的遗传算法优于前两种。
4. 心得体会：
遗传算法是一种模拟生物进化在解中求解最优值的方法，实现起来方便，适于处理大宗数据，然而基于简单基本遗传算法在求解不同问题时应该具体问题具体分析，找的结合所解问题的优化方法，例如本文分析的遗传算法解决0-1背包问题，虽然简单基本遗传算法可以求出一个比较好的解出来，但是分析可知，结果并不令人满意，在对问题进行细致的分析、查阅相关资料和深入思考后，我提出了自己认为比较好的4点改进方法并通过实践结合具体的算例把改进后的遗传算法和与原来的简单遗传算法和参考文献中的一种改进方法进行了比较，结果显示本文改进的遗传算法无论在小规模数据处理还是较大规模数据处理方面均优于前两者，这一点很令人高兴。 另外，通过本次实践，我也深刻体会到对于算法分析和改进的重要性，往往一个算法经过认真地分析和合理的改进后会获得性能上的提高——时间复杂度或者空间复杂度的降低，而且能够获得更好的解，本文就是一个很好的例证。
6. 参考文献：
[1]M.H.Alsuwaiyel著，方世昌等译《算法设计技巧与分析》电子工业出版社，北京，2009
[2]闫丽《用基本遗传算法解决0- 1背包问题》通化师范学院学报第26卷第4期，2005,7
[3]赵新超, 韩宇, 艾文宝《求解背包问题的一种改进遗传算法》 计算机工程与应用2011，47(24)
7. [附]实现程序：
已通过vc6.0编译后运行 #include #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 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 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 //最大换代数
#define 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,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; //初始化函数中初始化为所有价值之和
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,451,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,192,184,183,176,171,169,165,165,154,153,150,149,147,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,140,31,24,197,101,73,16,73,2,159,71,102,144,151,27,131,209,164,177,177,129,146,17,53,64,146,43,170,180,171,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 chromsome[N]; //染色体编码
double fitness; //适应度//即本问题中的个体所得价值
double weight; //总重量
};
int best=0;
int same=0;
individual X[S],Y[S],bestindividual;//
/************************************************************************/
int comp(individual bestindividual,individual temp); //比较函数
void checkalike(void); //检查相似度函数
void GenerateInitialPopulation(void); //初始种群
void CalculateFitnessValue(void); //适应度
void SelectionOperator(void); //选择
void CrossoverOperator(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;i
if(w>KW)return -1;
return (bestindividual.fitness>fit?-1:1);//如果小于原来值或者不满足重量函数，则返回-1
}
/************************************************************************/
void Checkalike(void)
{
int i=0,j=0;
for( i=0;i
{
for(j=0;j
} { bool temp=X[i].chromsome[j]; for(int k=1;k
if(same>N*ALIKE)//大于ALIKE 作为判定为早熟
{
int minindex=0;
for(int n=0;n
if(X[n].fitness
for (j=0; j
{
bool m=(rand()%10
X[minindex].chromsome[j]=m;
X[minindex].weight+=m*weight[j];//个体的总重量
X[minindex].fitness+=m*value[j]; //个体的总价值
}
}
}
/************************************************************************/ void GenerateInitialPopulation(void)//初始种群, 保证每个值都在符合条件的解
{
int i=0,j=0; bool k;
for(i=0;i
for (i=0; i
{
int w=0,v=0;
for (j=0; j
{
k=(rand()%10
X[i].chromsome[j]=k;
w+=k*weight[j];//个体的总重量
v+=k*value[j]; //个体的总价值
}
if(w>KW) i--; //如果不是解，重新生成
else
{
X[i].fitness=v;
X[i].weight=w;
if(v==stop){bestindividual=X[i];return;}//这种情况一般不会发生
}
}
}
/************************************************************************/ void CalculateFitnessValue()
{
int i=0,j=0;
for (i=0; i
{
int w=0,v=0;
for (j=0; j
{
w+=X[i].chromsome[j]*weight[j];//个体的总重量
v+=X[i].chromsome[j]*value[j]; //个体的总价值
}
X[i].fitness=v;
X[i].weight=w;
if(v==stop){bestindividual=X[i];return;}//符合条件情况下最优解这种情况一般不会发生 if(w>KW) X[i]=bestindividual; //如果不是解，找最好的一个解代之
}
}
/************************************************************************/ void SelectionOperator(void)
{
int i, index;
double p, sum=0.0;
double cfitness[S];//选择、累积概率
individual newX[S];
for (i=0;i
for (i=0;i
for (i=1;i
for (i=0;i
{
p=(rand()%1001)/1000.0;//产生一个[0,1]之间的随机数
index=0;
} while(p>cfitness[index])//轮盘赌进行选择 { index++; } newX[i]=X[index];
for (i=0; i
}
/************************************************************************/ void CrossoverOperator(void)//交叉操作
{
int i=0, j=0,k=0;individual temp; for(i=0; i
int w=1+rand()%N;//[1,N]表示交换的位数
double r=(rand()%1001)/1000.0;//[0,1]
if(r
{
for(j=0;j
{
temp.chromsome[j]=X[p].chromsome[j];//将要交换的位先放入临时空间 X[p].chromsome[j]=X[q].chromsome[j];
X[q].chromsome[j]=temp.chromsome[j];
}
}
if(p==best)
if(-1==comp(bestindividual,X[p]))//如果变异后适应度变小
X[p]=bestindividual;
if(q==best)
if(-1==comp(bestindividual,X[q]))//如果变异后适应度变小
X[q]=bestindividual;
}
}
/************************************************************************/ void MutationOperator(void)
{
int i=0, j=0,k=0,q=0;
double p=0;
for (i=0; i
{
for (j=0; j
{
p=(rand()%1001)/1000.0;
if (p
{
if(X[i].chromsome[j]==1)X[i].chromsome[j]=0;
else X[i].chromsome[j]=1;
}
}
if(i==best)
if(-1==comp(bestindividual,X[i]))//如果变异后适应度变小
X[i]=bestindividual;
}
}
/************************************************************************/ void FindBestandWorstIndividual(void)
{
int i;
bestindividual=X[0];
for (i=1;i
{
if (X[i].fitness>bestindividual.fitness)
{
bestindividual=X[i];
best=i;
}
}
}
/*主函数*****************************************************************/ void main(void)
{
srand((unsigned)time(0));
t=0;
GenerateInitialPopulation(); //初始群体包括产生个体和计算个体的初始值
while (t
{
FindBestandWorstIndividual(); //保存当前最优解
SelectionOperator(); //选择
CrossoverOperator(); //交叉
MutationOperator(); //变异
Checkalike(); //检查相似度
CalculateFitnessValue(); //计算新种群适应度
t++;
}
FindBestandWorstIndividual(); //找到最优解
cout
for(int k=0;k
cout
}
/*结束***********************************************************************/
实现遗传算法的0-1背包问题 求解及其改进
姓名：
学号：
班级：
提交日期：
实现遗传算法的0-1背包问题求解
摘要：研究了遗传算法解决0-1背包问题中的几个问题：
1） 对于过程中不满足重量限制条件的个体的处理, 通过代换上代最优解保持种群的进化性 2） 对于交换率和变异率的理解和处理方法, 采用逐个体和逐位判断的处理方法
3） 对于早熟性问题, 引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。 4） 一种最优解只向更好进化方法的尝试。
通过实际计算比较表明, 本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。
关键词：遗传算法；背包问题 ；优化
1. 基本实现原理： 一、问题描述 0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：
给定n 个物品和一个背包，物品i 的重量为Wi ，其价值为Vi ，背包的容量为C 。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C 。在选择装入背包的物品时，对每种物品i 只有两种选择：装入背包或者不装入背包，即只能将物品i 装入背包一次。称此类问题为0/1背包问题。 其数学模型为：
0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。 二、遗传算法特点介绍:
遗传算法(Genetic Algorithm, GA)是1962年Holland 教授首次提出了GA 算法的思想是近年来随着信息数据量激增，发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。 基本遗传算法求解步骤：
Step 1 参数设置：在论域空间U 上定义一个适应度函数f (x ) ，给定种群规模N ，交叉率P c 和变异率P m ，代数T ；
Step 2 初始种群：随机产生U 中的N 个染色体s 1, s 2, …, s N ，组成初始种群S ={s 1, s 2, …, s N }，置代数计数器t =1；
Step 3 计算适应度：S 中每个染色体的适应度f() ；
Step 4 判断：若终止条件满足，则取S 中适应度最大的染色体作为所求结果，算法结束。 Step 5 选择-复制：按选择概率P (x i ) 所决定的选中机会，每次从S 中随机选定1个染色体并将其复制，共做N 次，然后将复制所得的N 个染色体组成群体S 1；
Step 6 交叉：按交叉率P c 所决定的参加交叉的染色体数c ，从S 1中随机确定c 个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S 2；
Step 7 变异：按变异率P m 所决定的变异次数m ，从S 2中随机确定m 个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S 3；
Step 8 更新：将群体S 3作为新一代种群，即用S 3代替S ，t =t +1，转步3； 遗传算法是一种仿生算法, 即模拟生命演化的算法，它从一个代表问题初始解的初始种群出发, 不断重复执行选择, 杂交和变异的过程, 使种群进化越来越接近某一目标既最优解，如果视种群为超空间的一组点, 选择、杂交和变异的过程即是在超空间中进行点集之间的某种变换, 通过信息交换使种群不断变化， 遗传算法通过模拟达尔文“优胜劣汰, 适者生存”的原理激励好的结构, 同时寻找更好的结构, 作为一种随机的优化与搜索方法, 遗传算法有着其鲜明的特点。
—遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解(如果搜索成功的话) 。
—遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。
—遗传算法总是在寻找优解(最优解或次优解), 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解(当然包括优解), 所以遗传算法又是一种优化搜索算法。
—遗传算法的搜索过程是从空间的一个点集(种群) 到另一个点集(种群) 的搜索, 而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算, 而且这种种群到种群的搜索有能力跳出局部最优解。
—遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。
—遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束, 不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。 3. 程序步骤：
一、 使用基本遗传算法解决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背包问题存在的不足： 1. 对于过程中不满足重量限制条件的个体的处理 在用基本遗传算法解决0- 1背包问题的时候，在初始化或者交叉变异后可能会产生不满足重量约束条件的伪解，而对于这些伪解，基本遗传算法没有给出一个很好的处理方法，而
只是又随机生成了一个满足约束条件的解作为新的个体从而替换掉原来的个体。根据遗传算法的根本思想“优胜劣汰，适者生存”的原则，可以将不满足条件的个体用已有的最优个体来进行替换，这样，既使得种群中所有的个体均满足重量的约束条件，又保留了较优解，符合遗传算法的思想。 具体做法为： 在程序中加入一个变量保存每代的最优解，当前代在进行选择、复制、交叉、变异后如果有不满足约束条件的个体，则在种群更新时采用这个最优值作为替代。
具体做法为：在每代遗传后通过函数FindBestandWorstIndividual()找到当前最优值并保存bestindividual 中，在计算适应度函数CalculateFitnessValue()中加入：
if(w>KW) X[i]=bestindividual; //如果不是解，找最好的一个解代之
其中w 为当前个体的总重量，KW 为背包最大承重量，X[i]表示种群中第i 个个体，bestindividual 为保存的个体最优解。
2. 对于交换率和变异率的理解和处理方法 根据遗传算法的基本步骤的交叉和变异操作
Step 6 交叉：按交叉率P c 所决定的参加交叉的染色体数c ，从S 1中随机确定c 个染色体，配对进行交叉操作， 并用产生的新染色体代替原染色体，得群体S 2；
Step 7 变异：按变异率P m 所决定的变异次数m ，从S 2中随机确定m 个染色体，分别进行变异操作，并用产生的 新染色体代替原染色体，得群体S 3； 可以有两种处理方法：
其一，采用先确定数目在随机选取的方法，步骤如下：
对于交叉操作： 对于变异操作：
1, 根据交叉率确定应该交叉的个体数目1, 根据变异率确定应该变异的染色体数n 目n 2, 在种群中进行n 次循环 2, 在种群中进行n 次循环 2-1随机选中种群中的一个个体a 2-1随机选中种群中的一个个体的染2-2随机选中种群中异于a 的一个个色体a 体b
2-2随机选中染色体a 的某位基因
2-3随机确定交叉位数 2-4进行交叉
2-3对进行0-1互换变异
其二，采用对每个操作单元分别进行特定概率下处理的方法，步骤如下：
对于交叉操作：
1, 在种群中进行S 次循环, 其中S 代表种群中个体的数量
2, 对于每一个个体X[i]（X 为种群数组）做如下操作
2-1生成随机数p [0,1],判断p 与的大小关系 2-2如果p
说明X[i]需要交换
3-1生成随机数q [0,1],判断q 与
的大小关系
说明需要进行0-1互换
对于变异操作：
1, 在种群中进行S 次循环, 其中S 代表种群中个体的数量
2, 对每一个个体X[i]做N 次循环，其中N 为染色体位数
2-1对染色体的每一位
2-2-1 随机在种群中找到异于X[i]的另一个体进行交换 2-3如果p
说明X[i]不需要交换 3-2如果q
变异2-3如果q 说明不需要变
分析这两种处理方法可知：方法一没有很好地体现随机机会均等的思想，因为在步骤1中确定的需要操作的数目n 后，总体上是保证了交叉或者变异的数目，但不是对于每一个个体而言的，因而会出现有的个体被选择交叉或者变异多次而有的没有机会交叉或者变异的情况，而如果采用方法二，就体现了机会的均等性，即要求对每一个单元操作目标进行概率的验证，以确定是否变异或者交叉。在程序中具体的实现方法体现在交叉和变异函数中：
void CrossoverOperator(void)//交叉操作 for(i=0; i
do{p=rand()%S;//两个[0，S]的随机数 q=rand()%S; }while(p==q);
void MutationOperator(void)//变异操作 for (i=0; i
q=(rand()%1001)/1000.0;//产生q [0,1] if (q
if(X[i].chromsome[j]==1)X[i].chromsome[j]=0; else X[i].chromsome[j]=1;
int w=1+rand()%N;//[1,N]交换的位数
double p=(rand()%1001)/1000.0; if(p
2. 对于算法早熟性的分析及解决方法 遗传算法中种群中的个体由初始化时的具有多样性，可能会由于在进化过程中一些超常个体限制其它个体的进化——这个个体的适应度大大优于种群内的其它值，由于适者生存原则这个个体被不断复制从而充满了整个种群，使得种群的多样应大大降低，进化停滞，从而出现算法收敛于局部最优解的现象，称为早熟现象。 早熟现象的可能解法：
1） 通过提高变异率来增加种群的多样性，以期更优解的出现，这也是最简单基本遗传算法中不添加相关操作的情况下唯一的一种方法，然而这种方法有明显的弊端：在提高变异率获得多样性种群的同时，个体变异的机会增加，使得较优解发生变异，从而遗传算法丧失了其优于其它算法的优越性，所以这种方法不是很好地解决方法。 2） 引入多样性衡量和处理
基本思路：在出现进化停滞现象时要引入新的个体来增强种群的多样性。 做法：1, 判断是否达到早熟现象 对于种群中S 个个体，判断等位基因的相等程度，即引入一个参数值same, 如果same 达到一定的 理论值大小就可以认为达到了早熟现象。 2, 早熟现象的处理，即引入新的个体。 处理过程中应该不违反适者生存的原则，所以应该保留较好的个体，所以首先选中适应度最小的 个体执行删除操作，然后随机生成一个新的符合重量限制且打破早熟现象的新个体。
具体实现见函数：void checkalike(void)
if(same>N*0.5)//大于50%作为判定为早熟
//相似度校验 for( i=0;i
//确定最小 int minindex=0; for(intn=0;n
if(X[n].fitness
//重新生成 for (j=0; j
X[minindex].weight+=m*weight[j]; //个体的总重量
X[minindex].fitness+=m*value[j];
//个体的总价值
3. 一种最优解只向更好进化方法的尝试 基本思路为：每一组的最优解是一个独特的个体，我们求解的问题最终的最优解或者近似解都产生于这个特殊的个体，最优解只向更好进化方法中规定：每代中选出一个最优解并做好相应的记录或者标记，最优解参与交叉和变异，只是在交叉或者变异时对最优解进行前后适应度的比较，如果发现交叉或者变异后适应度大于操作前适应度，则保存操作后的结果，如果发现交叉或者变异后适应度小于操作前适应度，则禁止最优解的操作，而不禁止与最优解进行交叉的个体的变化。这样，每一代中的最优解的特性可以通过交叉传递给同代中的其它个体，而保证种群一定会向更好的方向进化。 做法在交叉后和变异后调用以下函数判断：
int comp(individual bestindividual,individual temp)//比较函数 { int fit=0,w=0;//第一种不变:操作后不满足重量函数，第二种:操作后适应度小于操作前 for(int i=0;iKW)return -1; return (bestindividual.fitness>fit?-1:1);//如果小于原来值或者不满足重量函数，则返回-1 }
三、 改进的遗传算法解决0- 1背包问题： 1、参数设置：
#define S 500 #define Pc 0.8 #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 每一组编码即为某一个个体的基因表示, 称其为染色体, 染色体长度取决于待分配的物件的个数n. 在编码形式的表示方法中, 形如二进制编码 10010101 表示为一个待分配的物件的个数为8（编码长度）的一个背包问题的一个解, 则该个体对应于选择了物件1, 4, 6, 8，即第1, 4, 6, 8个物品被放入了背包。用数据格式表示为：
struct individual { bool chromsome[N]; double fitness; double weight; };
//个体结构体
//染色体编码
//适应度//即本问题中的个体所得价值 //总重量
2产生初始种群
n 个待分配的物件随机产生S 个长度为n 的二进制串, 即种群中个体的染色体编码的每一位按等概率在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)
上述适应度函数基于一个考虑违背约束条件的惩罚处理，根据上述具体问题适应度函数值不可能为零, 所以当随机产生的某个个体违背约束条件时, 通过把其适应度函数值罚为0而达到淘汰该个体的目的。 4选择-复制操作
参照适应度函数值和约束条件用赌轮选择法进行模拟，具体为: ( 1)根据适应度函数值和约束条件, 罚掉部分个体（前述不满足容量条件的个体） (2)对于满足约束条件的个体, 根据适应度函数值计算个体被选中的概率, 称为选择概率： 公式为: P
=
p() 称为染色体x i (i =1, 2, …, n ) 的选择概率
(3)根据轮盘赌累计公式为： i
q =P (x j )
i ∑
j =1
称为染色体x i (i =1, 2, …, n ) 的积累概率
( 4) 对已得到的累计概率作如下处理，完成选择操作： 1）在［0, 1］区间内产生一个均匀分布的伪随机数r 。 2）若r≤q1,则染色体x1被选中。 3）若qk-1
对于每一个个体，根据交叉率P c 做如下操作： ( 1)随机产生一个交叉点的位置 ( 2)随机选取当前代中的两个个体作为父个体 ( 3)根据交叉点的位置, 做单点交叉 6变异操作: 根据变异率P m
( 1)随机产生变异点的位置 ( 2)在变异点位置作0- 1翻转 8、算法终止
程序中定义了一个最优值，stop=
一般情况下这个最优值达不到，一旦程序在执行过
程中达到此最优值，也就没有必要在执行下去，因为这必定是最好的解，所以保存最优值和最优解，结束。
如果程序的最优值达不到理想情况下的stop ，那么根据最大换代次数来结束程序，在结束后
的种群中找到一个最好的解作为本问题的最优解，程序结束。
4算例(可以使用参考文献[2]中的典型算例) ：
1. 小规模问题的算例：
算例1-1：设定物品价值value={50,30,60,80,20}重量weight{35,40,40,20,15}背包的最大承重量为100
遗传算法中参数：群体大小S=5，交叉率Pc=0.8,变异率Pm=0.05,最大换代次数T=20, 通过多次试验比较本文改进后遗传算法和其他得到结果如下表所示：
（右图中输出第一行数为最优价值；第二行数为重量；第三行为最优解）
本文改进的遗传算法： 实验总次数：30
达到全局最优解次数：27
未达到全局最优解：3 效果截图 由实验结果可知在小规模算例中，本文改进的遗传算法优于前两者。 2．较大规模问题求解算例： 遗传算法中参数：
群体大小S=5，交叉率Pc=0.8,变异率Pm=0.05,最大换代次数T=800，相似度取5% 实例1：
价值value ：{ 92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58} 重量weight ：{ {44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63}} 背包的最大承重量：878 实例2： 价值value ： {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}; 重量weight: {80,82,85,70,72,70,66,50,55,25,50,55,40,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}; 背包最大承重量：1000
实例3：
(说明：参考论文中的实例3价值数组中缺少一个值，这里以0补上，使价值和重量一一对应)
价值value ： {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,451,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,192,184,183,176,171,169,165,165,154,153,150, 149,147,143,140,138,134,132,127,124,123,114,111,104,89,74,63,62,58,55,48,27,22,12,6,0}; 重量
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,140,31,24,197,101,73,16,73,2,159,71,102,144,151,27,131,209,164,177,177,129,146,17,53,64,146,43,170, 180,171,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};
各运行30次后比较30次中的最好值, 比较结果如下本文改进的遗传算法和先前算法结果如下：
本文改进遗传算法实验结果：
实例1：（输出第一行数为最优价值；第二行数为重量；第三行为最优解）
实例2：
实例3：
根据得到最优解的情况本文改进的遗传算法所得最好值均好于先前两种算法，特别是实例3中，在缺少一个价值值补0的情况下得到的结果仍然优于前两种算法。 由此得出结论：本文改进的遗传算法优于前两种。
4. 心得体会：
遗传算法是一种模拟生物进化在解中求解最优值的方法，实现起来方便，适于处理大宗数据，然而基于简单基本遗传算法在求解不同问题时应该具体问题具体分析，找的结合所解问题的优化方法，例如本文分析的遗传算法解决0-1背包问题，虽然简单基本遗传算法可以求出一个比较好的解出来，但是分析可知，结果并不令人满意，在对问题进行细致的分析、查阅相关资料和深入思考后，我提出了自己认为比较好的4点改进方法并通过实践结合具体的算例把改进后的遗传算法和与原来的简单遗传算法和参考文献中的一种改进方法进行了比较，结果显示本文改进的遗传算法无论在小规模数据处理还是较大规模数据处理方面均优于前两者，这一点很令人高兴。 另外，通过本次实践，我也深刻体会到对于算法分析和改进的重要性，往往一个算法经过认真地分析和合理的改进后会获得性能上的提高——时间复杂度或者空间复杂度的降低，而且能够获得更好的解，本文就是一个很好的例证。
6. 参考文献：
[1]M.H.Alsuwaiyel著，方世昌等译《算法设计技巧与分析》电子工业出版社，北京，2009
[2]闫丽《用基本遗传算法解决0- 1背包问题》通化师范学院学报第26卷第4期，2005,7
[3]赵新超, 韩宇, 艾文宝《求解背包问题的一种改进遗传算法》 计算机工程与应用2011，47(24)
7. [附]实现程序：
已通过vc6.0编译后运行 #include #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 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 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 //最大换代数
#define 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,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; //初始化函数中初始化为所有价值之和
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,451,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,192,184,183,176,171,169,165,165,154,153,150,149,147,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,140,31,24,197,101,73,16,73,2,159,71,102,144,151,27,131,209,164,177,177,129,146,17,53,64,146,43,170,180,171,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 chromsome[N]; //染色体编码
double fitness; //适应度//即本问题中的个体所得价值
double weight; //总重量
};
int best=0;
int same=0;
individual X[S],Y[S],bestindividual;//
/************************************************************************/
int comp(individual bestindividual,individual temp); //比较函数
void checkalike(void); //检查相似度函数
void GenerateInitialPopulation(void); //初始种群
void CalculateFitnessValue(void); //适应度
void SelectionOperator(void); //选择
void CrossoverOperator(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;i
if(w>KW)return -1;
return (bestindividual.fitness>fit?-1:1);//如果小于原来值或者不满足重量函数，则返回-1
}
/************************************************************************/
void Checkalike(void)
{
int i=0,j=0;
for( i=0;i
{
for(j=0;j
} { bool temp=X[i].chromsome[j]; for(int k=1;k
if(same>N*ALIKE)//大于ALIKE 作为判定为早熟
{
int minindex=0;
for(int n=0;n
if(X[n].fitness
for (j=0; j
{
bool m=(rand()%10
X[minindex].chromsome[j]=m;
X[minindex].weight+=m*weight[j];//个体的总重量
X[minindex].fitness+=m*value[j]; //个体的总价值
}
}
}
/************************************************************************/ void GenerateInitialPopulation(void)//初始种群, 保证每个值都在符合条件的解
{
int i=0,j=0; bool k;
for(i=0;i
for (i=0; i
{
int w=0,v=0;
for (j=0; j
{
k=(rand()%10
X[i].chromsome[j]=k;
w+=k*weight[j];//个体的总重量
v+=k*value[j]; //个体的总价值
}
if(w>KW) i--; //如果不是解，重新生成
else
{
X[i].fitness=v;
X[i].weight=w;
if(v==stop){bestindividual=X[i];return;}//这种情况一般不会发生
}
}
}
/************************************************************************/ void CalculateFitnessValue()
{
int i=0,j=0;
for (i=0; i
{
int w=0,v=0;
for (j=0; j
{
w+=X[i].chromsome[j]*weight[j];//个体的总重量
v+=X[i].chromsome[j]*value[j]; //个体的总价值
}
X[i].fitness=v;
X[i].weight=w;
if(v==stop){bestindividual=X[i];return;}//符合条件情况下最优解这种情况一般不会发生 if(w>KW) X[i]=bestindividual; //如果不是解，找最好的一个解代之
}
}
/************************************************************************/ void SelectionOperator(void)
{
int i, index;
double p, sum=0.0;
double cfitness[S];//选择、累积概率
individual newX[S];
for (i=0;i
for (i=0;i
for (i=1;i
for (i=0;i
{
p=(rand()%1001)/1000.0;//产生一个[0,1]之间的随机数
index=0;
} while(p>cfitness[index])//轮盘赌进行选择 { index++; } newX[i]=X[index];
for (i=0; i
}
/************************************************************************/ void CrossoverOperator(void)//交叉操作
{
int i=0, j=0,k=0;individual temp; for(i=0; i
int w=1+rand()%N;//[1,N]表示交换的位数
double r=(rand()%1001)/1000.0;//[0,1]
if(r
{
for(j=0;j
{
temp.chromsome[j]=X[p].chromsome[j];//将要交换的位先放入临时空间 X[p].chromsome[j]=X[q].chromsome[j];
X[q].chromsome[j]=temp.chromsome[j];
}
}
if(p==best)
if(-1==comp(bestindividual,X[p]))//如果变异后适应度变小
X[p]=bestindividual;
if(q==best)
if(-1==comp(bestindividual,X[q]))//如果变异后适应度变小
X[q]=bestindividual;
}
}
/************************************************************************/ void MutationOperator(void)
{
int i=0, j=0,k=0,q=0;
double p=0;
for (i=0; i
{
for (j=0; j
{
p=(rand()%1001)/1000.0;
if (p
{
if(X[i].chromsome[j]==1)X[i].chromsome[j]=0;
else X[i].chromsome[j]=1;
}
}
if(i==best)
if(-1==comp(bestindividual,X[i]))//如果变异后适应度变小
X[i]=bestindividual;
}
}
/************************************************************************/ void FindBestandWorstIndividual(void)
{
int i;
bestindividual=X[0];
for (i=1;i
{
if (X[i].fitness>bestindividual.fitness)
{
bestindividual=X[i];
best=i;
}
}
}
/*主函数*****************************************************************/ void main(void)
{
srand((unsigned)time(0));
t=0;
GenerateInitialPopulation(); //初始群体包括产生个体和计算个体的初始值
while (t
{
FindBestandWorstIndividual(); //保存当前最优解
SelectionOperator(); //选择
CrossoverOperator(); //交叉
MutationOperator(); //变异
Checkalike(); //检查相似度
CalculateFitnessValue(); //计算新种群适应度
t++;
}
FindBestandWorstIndividual(); //找到最优解
cout
for(int k=0;k
cout
}
/*结束***********************************************************************/