题目6-基于遗传算法求解0-1背包问题
课程设计要求及任务描述：
1.明确任务的目的
2.对相应题目进行算法分析
3.编写源代码
4.上机调试
5.显示调试结果
6.写出实验总结
工作计划及安排：
1.选题与搜集资料:选择相应题目,进行课程设计课题的资料搜集
2.分析与设计:根据搜集的资料,进行程序功能与数据结构分析,并选择合适的数据结构,并在此基础上进行实现程序功能的算法设计
3.程序设计:运用掌握C语言编写程序,实现所程序的各个模块功能
4.调试与测试:自行调试程序,成员交叉测试程序,并记录测试情况
5.课程设计报告:编写课程设计报告
一、题目分析
（1）遗传算法：遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
（2）遗传算法的基本运算过程如下：a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价:计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
（遗传算法流程图）
（3）0-1背包：给定n中物品和一个背包。物品i的重量是Wi ，其价值为Vi ，背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？在选择装入的背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分物品i。因此，该问题成为0-1背包问题。
二、总体设计
本学期中，我们学习了多种算法求解背包问题，本次课程设计中，我们通过自学探究方法用遗传算法求解背包问题。首先，运用遗传算法步骤，产生初始群体、评价个体、复制交叉变异等中心步骤求解，为背包问题的进一步学习拓宽了思路。
三、详细设计
根据设计要求，该算法的基本运行流程为:
第1 步: 随机产生一组初始个体构成的初始群体;
第2 步: 对串群体迭代的执行下面的步骤(3) , (4) , 直到满足停止准则后转(5) ;
第3 步: 计算群体中每一个个体的适配值(fitness value) ;
第4 步: 应用复制、交叉、变异算子产生下一代群体;
第5 步: 把在任何一代中出现的最好的个体串指定为遗传算法的执行结果, 这个结果可以表示问题的一个解(或近似解)。由此可设计所需结构和函数如下:
1.定义数据类型
个体评价的结构类型
typedef struct tagIndivdualMsg
{
int index;
int value;
} IndivdualMsg;
IndivdualMsg indivdualMsg[max];
2.实现算法的各函数说明：
（1）初始化群体：void colonyInit()
（2）对个体进行评价:
int cmp(const void *a, const void *b), void indivdualEstimate()
（3）终止循环的条件，给定一个最大进化步数
bool stopFlag()
（4）赌轮选择,计算适应度
int gambleChoose()
（5）交叉，进行交叉运算,随即选择一对个体产生一对有效交叉位置进行交叉运算,并计算新产生的个体的适应度值和约束条件值。如果新产生的个体重量大于背包容量,则对新产生的个体进行修正,放弃在一个个体中的一个物品,增加另一个个体的一个物品使其重量小于背包重量。
void across(int male, int female, int index)
（6）变异进行变异操作,如果一个个体的一个基因为1,则变为0;如果是0则变为1,重新计算该个体的适应度值和约束条件值
void aberrance(int index)
（7）处理死亡个体
void dealDeath()
（8）最优个体保护
void saveBest()
（9）输出函数void setProblem()
void printProblem();
void printColonyState(int k) ;
void printIndividualMsg();
（10）主函数:
void main()
{
调用函数；
解出问题的解；
}
3.函数调用关系如图：
四、调试分析
错误1
--------------------Configuration: bag - Win32 Debug--------------------
Compiling...
bag.cpp
c:\\documents and settings\\administrator\桌面\算法\\bag\\bag.cpp(41) : error C2018: unknown character '0xa3'
c:\\documents and settings\\administrator\桌面\算法\\bag\\bag.cpp(41) : error C2018: unknown character '0xac'
c:\\documents and settings\\administrator\桌面\算法\\bag\\bag.cpp(41) : error C2146: syntax error : missing ';' before identifier 'j'
c:\\documents and settings\\administrator\桌面\算法\\bag\\bag.cpp(41) : error C2065: 'j' : undeclared identifier
Error executing cl.exe.
bag.exe - 4 error(s), 0 warning(s)
分析：在代码编写过程中，由于中英文输入法之间的转换，错将英文输入法下的“,”输入为中文输入法下的“，”以至于出现错误。这类错误是在程序设计中经常出现的错误，是由于长时间的程序编写造成的粗心大意造成的。
解决：将中文输入法下的“，”改为英文输入法下的“,”即可 。
错误2
--------------------Configuration: bag - Win32 Debug--------------------
Compiling...
bag.cpp
C:\\Documents and Settings\\Administrator\桌面\算法\\bag\\bag.cpp(285) : error C2065: 'saveBest' : undeclared identifier
Error executing cl.exe.
bag.exe - 1 error(s), 0 warning(s)
分析：函数调用过程输错。
解决：重新书写出错的函数名即可。
五、测试结果
测试数据如下：
物品个数：5
物品价值：6、3、5、4、6
物品重量：2、2、6、5、4
背包容量：10
程序运行结果如下:
六、程序代码
//遗传算法求解0-1背包问题
#include #include #include #include #include using namespace std; //定义问题的最大规模 #define max 100 //为题规模，即共有多少个包 int packageNum; //每个包的重量 int packageWeight[max]; //每个包的价值 int packageValue[max]; //约束，背包的最大容量 int limitWeight; //群体的规模 int colonySize; /*colonyState[i][k] 表示一个染色体*/ /*colonyState[1...conlonySize][0|1] 表示一个群体*/ int colonyState[max][2][max]; /* currAge 表示当前代的编号*/ /* (currAge+1)%2 表示下一代的编号*/ int currAge = 0; /* 个体评价*/ typedef struct tagIndivdualMsg { int index; int value; }IndivdualMsg; IndivdualMsg indivdualMsg[max]; /*函数声明*/ void printColonyState(int nextAge); /*初始化群体，初始种群产生,并计算每个适应度值和其对应的约束条件值(即为在染色体中选取的物品的重量) ,比较初始种群中各个个体的适应度。选择最大者所对应的个体作为第一代最优个体,并记录该个体以及它的适应度和约束条件值。*/ void colonyInit() { int i, j; int w; for(i=0; i //保证找到一个符合约束的染色体 w = limitWeight +1; while(w > limitWeight) { w = 0; for(j=0; j colonyState[i][currAge][j] = rand()%2; w += packageWeight[j] * colonyState[i][currAge][j]; } } } } /*对个体进行评价*/ int cmp(const void *a, const void *b) { IndivdualMsg *x = (IndivdualMsg *)a; IndivdualMsg *y = (IndivdualMsg *)b; return y->value - x->value; } void indivdualEstimate() { int i, j; for(i=0; i indivdualMsg[i].index = i; indivdualMsg[i].value = 0; for(j=0; j } qsort(indivdualMsg, colonySize, sizeof(IndivdualMsg), cmp); } /*终止循环的条件，给定一个最大进化步数*/ bool stopFlag() { //进行n代进行后停止 static int n = 50; if(n-- <= 0) return false; else return true; } /*赌轮选择*/ int gambleChoose() { int wheel[max] = {0}; int i = colonySize-1; int choose; wheel[i] = indivdualMsg[i].value; for(i--; i>=0; i--) wheel[i] = (indivdualMsg[i].value + wheel[i+1]) + colonySize*(colonySize-i); int seed = abs(wheel[0]-(rand()%(2*wheel[0]+1))); choose = colonySize-1; while(seed > wheel[choose]) choose--; return choose; } /*交叉，进行交叉运算,随即选择一对个体产生一对有效交叉位置进行交叉运算,并计算新产生的个体的适应度值和约束条 件值。如果新产生的个体重量大于背包容量,则对新产生的个体进行修正,放弃在一个个体中的一个物品,增加另一个个体的 一个物品使其重量小于背包重量。*/ void across(int male, int female, int index) { int nextAge = (currAge+1) %2; int i, j, t; int acrossBit = rand() % (packageNum-1) + 1; for(j=0; j colonyState[index][nextAge][j] = colonyState[indivdualMsg[male].index][currAge][j]; colonyState[index+1][nextAge][j] = colonyState[indivdualMsg[female].index][currAge][j]; } for(i=0; i t = colonyState[index][nextAge][i]; colonyState[index][nextAge][i] = colonyState[index+1][nextAge][i]; colonyState[index+1][nextAge][j] = t; } } /*变异:进行变异操作,如果一个个体的一个基因为1,则变为0;如果是0则变为1,重新计算该个体的适应度值和约束条件值*/ void aberrance(int index) { int seed, nextAge; nextAge = (currAge+1) %2; //只有1/3的概率发生异变 seed = rand() %(packageNum*3); if(seed < packageNum) colonyState[index][nextAge][seed] = (colonyState[index][nextAge][seed] + 1) %2; } /*处理死亡个体*/ void dealDeath() { int i, j; int weight, w; int nextAge = (currAge+1) %2; for(i=0; i weight = 0; for(j=0; j if(weight > limitWeight) { w = limitWeight +1; while(w > limitWeight) { w = 0; for(j=0; j colonyState[i][nextAge][j] = rand() %2; w += packageWeight[j] * colonyState[i][nextAge][j]; } } } } } /*最优个体保护*/ void saveBest() { int i, j; int min, minp, value; int nextAge = (currAge+1) %2; min = indivdualMsg[0].value; minp = -1; for(i=0; i value = 0; for(j=0; j if(value <= min) { min = value; minp = i; } } if(minp >= 0) { for(j=0; j colonyState[minp][nextAge][j] = colonyState[indivdualMsg[0].index][currAge][j]; } } } /*输出函数*/ void setProblem() { int i; int *w; int *v; cout<<"请输入物品的个数: "< w = new int[packageNum]; v = new int[packageNum]; cout<<"请输入价值:"< cout<<"请输入重量:"< for(i=0; i packageWeight[i] = w[i]; packageValue[i] = v[i]; } cout<<"请输入背包的容量:"< colonySize = 100; delete []w; delete []v; } void printProblem() { int i; cout<<"---------------------------------------------------"< for(i=0; i for(i=0; i void printColonyState(int k) { cout<<"----------------------------------------------------"< if(k == currAge) cout<<"currAge:"< cout<<"next age:"< for(i=0; i for(j=0; j } void printIndividualMsg() { int i; cout<<"---------------------------------------------------"< void main() { srand((unsigned int)time(NULL)); setProblem(); printProblem(); //初始化群体 colonyInit(); printColonyState(currAge); while(! stopFlag()) { //评价当前群体 indivdualEstimate(); //生成下一代 for(int i=0; i int male = gambleChoose(); int female = gambleChoose(); across(male, female, i); aberrance(i); aberrance(i+1); } //处理死亡个体 dealDeath(); //保护最优个体 saveBest(); //现在的下一代变成下一轮的当前代 currAge = (currAge+1) %2; } //输出问题解 indivdualEstimate(); cout<<"近似解:"< cout< w += packageWeight[j] *colonyState[indivdualMsg[0].index][currAge][j]; cout< cout< 七、算法比较 求解背包问题的算法比较 八、遗传算法解决0-1背包问题的进一步探究 8.1 改进遗传算法的基本思想 人类的繁殖方式与其他动物有着根本的区别。首先，为了提高人口素质，法律对婚配年龄作了明确的规定， 也就是说人类的繁殖要受到法定年龄的制约。当然，在达到一定的年龄之后，个体的生育能力也就自然消失了；其次，人类的繁殖方式是严格的远缘繁殖，而在动物界，“乱伦”现象经常发生。人类为了避免近亲繁殖，制定了相应的法律来进行约束，法律规定直系血亲和三代以内的旁系血亲禁止通婚，因为研究表明，双亲的亲缘关系越近，他们的基因特性雷同的机会就越大，并存于双亲的基因就越容易显现出消极的一面， 致使近亲繁殖产生的后代往往都体弱多病，甚至不能存活。 为了提高遗传算法的收敛性能，本文将人类繁殖方式引入到遗传算法中来，得到一种改进的遗传算法(IGA)。该算法的遗传个体具有雄性和雌性两种性别，同时融合了个体的年龄和个体间的亲缘关系两种特征，在允许的年龄范围内，异性个体进行严格的远缘繁殖，遗传算子包括选择算子、助长算子、交叉算子和变异算子。这种改进的遗传算法流程如图1 所示。 8.2 编码方法 采用二进制编码方法对个体进行编码，每一个个体编码是由两部分组成的，第一部分是个体表现型对应的二进制编码；第二部分是个体性别对应的二进制编码，如表1 所示。 其中，个体性别编码部分为0 或1，可用0 表示雌性个体，用1 表示雄性个体。个体表现型编码是将n 个xi的值顺序排列， 就可构成背包问题的遗传编码。具体地说，个体表现型编码X=（x1，x2，…，xn），xi=0或1，如果xi=1，则表示将第i 件物品放入背包中；如果xi=0， 则表示第i 件物品不放入背包中。例如“110001100000000……0000000011” 就代表一个解，它表示将第1，2，6，7，……n-1，n 号物品放入背包中，其他的物品则不放入。 8.3 适应度函数 由于适应度值是群体中个体生存机会选择的唯一确定性指标，所以适应度函数的形式直接决定着群体的行为进化。为了直接将适应度函数与群体中的个体优劣度量相联系， 在遗传算法中规定适应度为非负，并且在任何情况下总是越大越好。本文在进行个体适应度评价时， 直接使用目标函数作为适应度函数，即： 式中，vi表示第i 个物品的价值。 8.4遗传算子 （1）选择算子 采用两代竞争排序的选择方法来对个体进行优选，即把父代与子代的所有雄性个体与雌性个体分别进行重新排序，再在允许的年龄范围内按群体规模N分别从排序后的雄性个体集与雌性个体集中截取前N/2 个优秀的个体进入匹配池， 作为交叉操作的对象。这样不仅保证了交叉操作的个体能进行有效的配对，同时也可以使每一代的优秀个体得以保留，而淘汰那些不良的个体， 从而使好的基因和模式不会丢失，有利于尽快找到全局最优解。 （2）助长算子 为了加强算法跳出局部最优的能力，加速算法的收敛，IGA 使用一个助长算子来对种群中的个体进行一定概率下的助长。助长操作在选择操作之后及配对操作之前进行，其具体步骤如下： Step1：令i=1； Step2：随机产生一个实数r，使0≤r≤1，如果r≤ph ，则执行Step3；否则，跳转到Step6； Step3：令j=1； Step4：如果=0，令 =1；但如果此时si 的适应度值降低，则维持 =0； Step5：j=j+1，如果j>n-1，则执行Step6；否则，跳转到Step4； Step6：i=i+1，如果i>N，则执行Step7；否则，跳转到Step2； Step7：结束。 其中，ph表示助长概率，si 表示种群中第i 个个体，sij表示第i 个个体编码的第j 位，n 表示编码长度，N 表示种群大小。 （3）交叉与变异算子 二进制编码方式下的交叉操作采用单点交叉方式非常有效，单点交叉操作的重要特点是：它可以产生与原配对个体完全不同的子代个体，如果邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度，那么单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。 经过杂交产生的所有新个体，要在一定概率下随机发生变异，形成新一代种群，这样增加了群体中个体的多样性，有助于跳出局部最优，达到全局最优。在二进制编码方式下，变异操作就是以很小的变异概率从群体中随机选取若干个体，对于选中的个体又随机选取表现型编码中的某一位或多位进行数码翻转，即将1 变为0 或0 变为1。 （4）个体年龄判断 个体的繁殖能力与年龄有着十分密切的关系，随着年龄的增长，个体的成活率和繁育率均成下降的趋势，个体的繁殖能力也会随之衰减。在基本遗传算法中， 对个体基因年龄的忽略是不符合自然规律的，这样有可能会导致搜索范围缩小及局部最优，从而出现早熟收敛。为此，本文改进算法在选择操作之后首先要对进入匹配池中的个体进行年龄判断，不符合年龄要求的个体予以剔除，重新选择相同性别的优秀个体来替换。 个体年龄判断方法：设个体配对的最大允许年龄为N，初始种群P（0）中个体的年龄记为ni（0）=1，每进化一次，个体年龄加1，记录每次进化后新种群P（t）个体的年龄ni（t）。如果ni（t） 在本文改进的遗传算法中，同性别个体之间是不能进行配对的， 雄性个体只能同雌性个体进行配对。配对是按个体优劣顺序进行的，即对按优劣顺序排队的雄性个体与按优劣顺序排队的雌性个体进行一一配对， 这有利于提高遗传算法寻找全局最优解的速度，增强遗传算法的全局收敛能力。 为了避免近亲繁殖，两个异性个体在配对之后还要进行个体间亲缘关系的检测。个体间亲缘关系直接用两个个体表现型编码对应的二进制数的差值来衡量，如果两个个体表现型编码所对应的二进制数相等或者仅相差1，则视为近亲，不能进行杂交，需对它们进行修正。修正的方法是：把适应度小的个体表现型编码的高位修改为与适应度大的个体表现型编码的高位不同的值。这样，保证个体之间的繁殖属于远缘繁殖，从而提高遗传算法的效率。 九、参考文献 [1].《算法设计与分析》，清华大学出版社，王晓东编著 [2].《0-1背包问题的遗传算法求解》，鄂州大学，曾国清 [3].《0-1背包问题及其算法分析》，金华职业技术学院，应莉 [4].《一种求解背包问题的改进遗传算法》，湖南理工学院，严太山、陈专红、陈群 [5].遗传算法，百度百科，baike.baidu.com下载本文
从计算复杂性理论看,背包问题是一个经典NP难解问题。半个多世纪以来,该问题一直是算法与复杂性研究的热点问题之一。通过对0-1背包问题的算法分析可以看出,回溯法能够精确地得到问题的最优解,可是计算时间太慢;动态规划算法也可以得到最优解,但当m > 时,算法需要Ω ( n* )的计算时间,这与回溯法存在着一样的缺点——计算速度慢;采用贪心算法和遗传算法,虽然耗费上优于前者,但不一定能得到最优解。目前,以上四种方法都广泛地应用到不同的实际问题中,并在应用中不断改进和完善。算法名称 时间复杂度 优点 缺点 改进 回溯法 0( n* ) 最优解 速度慢 剪枝 动态规划 O ( n*m) 最优解 速度慢 递归方程求解 贪心算法 O ( n* logn) 速度快 不一定是最优解 启发式方法 遗传算法 O ( T* ) 近似最优解 速度较慢，肯那个造成局部最优解 惩罚方法和译码方法
