用遗传算法解决0-1背包问题.

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) 考虑到会有不不满足容量条件的个体则： f i = 0 (当a1x1 + a2x2 + , + anxn > c，xj = 0, 1)

上述适应度函数基于一个考虑违背约束条件的惩罚处理，根据上述具体问题适应度函数值不可能为零, 所以当随机产生的某个个体违背约束条件时, 通过把其适应度函数值罚为0而达到淘汰该个体的目的。 4选择-复制操作

参照适应度函数值和约束条件用赌轮选择法进行模拟，具体为 ( 1)根据适应度函数值和约束条件, 罚掉部分个体（前述不满足容量条件的个体） (2)对于满足约束条件的个体, 根据适应度函数值计算个体被选中的概率,称为选择概率：

公式为:

=

p()称为染色体xi(i=1, 2, …, n)的选择概率

P

(3)根据轮盘赌累计公式为： iq?P(xj) i ? j?1

称为染色体xi(i=1, 2, …, n)的积累概率

( 4) 对已得到的累计概率作如下处理，完成选择操作： 1）在［0, 1］区间内产生一个均匀分布的伪随机数r。 2）若r≤q1,则染色体x1 3）若qk-1

对于每一个个体，根据交叉率Pc 做如下操作： ( 1)随机产生一个交叉点的位置 ( 2)随机选取当前代中的两个个体作为父个体 ( 3)根据交叉点的位置, 做单点交叉 6变异操作: 根据变异率Pm

( 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[]={