0-1背包问题在实际中有广泛的应用，本课程设计采用遗传算法中Prim算法解决0-1背包问题，遗传算法主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。通过分析用遗传算法解决0-1背包问题能得到问题的最优解。
根据算法的设计结果，采用C语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。
关键词：0-1背包问题，遗传算法，Prim算法
目 录
1 问题描述 1
2 问题分析 2
3 建立数学模型 3
4 算法设计 4
5 算法实现 5
6 测试分析 6
结 论 7
参考文献 8
1 问题描述
（1） 0-1背包问题：给定n中物品和一个背包。物品i的重量是Wi ，其价值为Vi ，背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？在选择装入的背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分物品i。因此，该问题成为0-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 算法设计
据设计要求，该算法的基本运行流程为:
第1 步: 随机产生一组初始个体构成的初始群体;
第2 步: 计算群体中每一个个体的适配值(fitness value) ;
第3 步: 应用复制、交叉、变异算子产生下一代群体;
第4 步: 把在任何一代中出现的最好的个体串指定为遗传算法的执行结果。
4算法实现
//遗传算法求解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< 5 测试分析 时间复杂度： 遗传算法解决所需的时间复杂度为O（2n） 测试数据如下： 物品个数：5 物品价值：6、3、5、4、6 物品重量：2、2、6、5、4 背包容量：10 程序运行结果如下: 结 论 从计算复杂性理论看,背包问题是一个经典NP难解问题。半个多世纪以来,该问题一直是算法与复杂性研究的热点问题之一。通过对0-1背包问题的算法分析可以看出,回溯法能够精确地得到问题的最优解,可是计算时间太慢;动态规划算法也可以得到最优解,但当m > 时,算法需要Ω ( n* )的计算时间,这与回溯法存在着一样的缺点——计算速度慢; 本设计采用了遗传算法方法，并用实例进行了验证， 计算结果表明，在耗费上遗传算法虽然优于前者，但是并不一定到最优解。 通过对背包问题的解决，我了解到了《计算机算法设计与分析》课程的重要性，使我对算法产生了兴趣；希望在以后的学习中，我们能够接触到更多有关算法的问题，并能够熟悉掌握各个算法的要点。 参考文献 [1] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007：102-121. [2] 严蔚敏 吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997：170-179. [3] 谭浩强.C程序设计(第三版) [M].北京：清华大学出版社，2005：1-378. [4]. 应莉.0-1背包问题及其算法分析[M].上海：金华职业技术学院，1999：1-157 [5]. 严太山.一种求解背包问题的改进遗传算法[M].北京：湖南理工学院， 2003：1-198 [6] 师从风.C语言结构化程序设计[M].湖南：机械工业出版社， 1977：1-351下载本文
