《背包问题课程设计说明书》由会员分享，可在线阅读，更多相关《背包问题课程设计说明书（23页珍藏版）》请在金锄头文库上搜索。
1、课程设计说明书(论文)用纸I摘摘 要要0-1 背包问题在实际中有广泛的应用，本课程设计采用遗传算法中 Prim 算法解决 0-1 背包问题，遗传算法主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。通过分析用遗传算法解决 0-1 背包问题能得到问题的最优解。根据算法的设计结果，采用 C 语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。关键词：关键词：0
2、-1 背包问题，遗传算法，Prim 算法课程设计说明书(论文)用纸II目目 录录1 问题描述.12 问题分析.23 建立数学模型.34 算法设计.45 算法实现.56 测试分析.6结 论.7参考文献.8课程设计说明书(论文)用纸第 1 页 共 21 页1 问题描述问题描述（1） 0-1 背包问题：给定 n 中物品和一个背包。物品 i 的重量是 Wi ，其价值为 Vi ，背包的容量为 C。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？在选择装入的背包的物品时，对每种物品 i 只有两种选择，即装入背包或不装入背包。不能将物品 i 装入背包多次，也不能只装入部分物品 i。因此，该
3、问题成为 0-1 背包问题。（2） 遗传算法：遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国 Michigan 大学 J.Holland教授于 1975 年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems ，GA 这个名称才逐渐为人所知，J.Holland教授所提出的 GA 通常为简单遗传算法（SGA） 。遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣
4、汰遗传机制）演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作
5、为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往课程设计说明书(论文)用纸第 2 页 共 21 页往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组
6、合交叉（crossover）和变异（mutation） ，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding） ，可以作为问题近似最优解。课程设计说明书(论文)用纸第 3 页 共 21 页2 问题分析对于背包问题遗传算法的基本运算过程如下：a)初始化:设置进化代数计数器t=0，设置最大进化代数 T，随机生成 M 个个体作为初始群体 P(0)。b)个体评价:计算群体 P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代
7、。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体 P(t)经过选择、交叉、变异运算之后得到下一代群体 P(t 1)。f)终止条件判断:若 tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。课程设计说明书(论文)用纸第 4 页 共 21 页3 算法设计据设计要求，该算法的基本运行流程为:第 1 步: 随机产生一组初始个体构成的初始群体;第 2 步
8、: 计算群体中每一个个体的适配值(fitness value) ;第 3 步: 应用复制、交叉、变异算子产生下一代群体;第 4 步: 把在任何一代中出现的最好的个体串指定为遗传算法的执行结果。课程设计说明书(论文)用纸第 5 页 共 21 页4 算法实现/遗传算法求解 0-1 背包问题#include#include#include#include#includeusing namespace std;/定义问题的最大规模#define max 100/为题规模，即共有多少个包int packageNum;/每个包的重量int packageWeightmax;/每个包的价值int packa
9、geValuemax;/约束，背包的最大容量int limitWeight;/群体的规模int colonySize;/*colonyStateik 表示一个染色体*/*colonyState1.conlonySize0|1 表示一个群体*/int colonyStatemax2max;/* currAge 表示当前代的编号*/* (currAge+1)%2 表示下一代的编号*/int currAge = 0;课程设计说明书(论文)用纸第 6 页 共 21 页/* 个体评价*/typedef struct tagIndivdualMsg int index;int value;Indivdua
10、lMsg;IndivdualMsg indivdualMsgmax;/*函数声明*/void printColonyState(int nextAge);/*初始化群体，初始种群产生,并计算每个适应度值和其对应的约束条件值(即为在染色体中选取的物品的重量) ,比较初始种群中各个个体的适应度。选择最大者所对应的个体作为第一代最优个体,并记录该个体以及它的适应度和约束条件值。*/void colonyInit() int i, j;int w;for(i=0; i limitWeight) w = 0;for(j=0; jvalue - x-value;void indivdualEstimate
11、() int i, j;for(i=0; i=0; i-)wheeli = (indivdualMsgi.value + wheeli+1) + colonySize*(colonySize-i);int seed = abs(wheel0-(rand()%(2*wheel0+1);choose = colonySize-1;while(seed wheelchoose)choose-;return choose;/*交叉，进行交叉运算,随即选择一对个体产生一对有效交叉位置进行交叉运算,并计算新产生的个体的适应度值和约束条件值。如果新产生的个体重量大于背包容量,则对新产生的个体进行修正,放弃在
12、一个个体中的一个物品,增加另一个个体的一个物品使其重量小于背包重量。*/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 limitWeight)w = limitWeight +1;while(w limitWeight)课程设计说明书(论文)用纸第 10 页 共 21 页w = 0;for(j=0; j= 0)for(j=0; jpackageNum;w = ne
13、w intpackageNum;v = new intpackageNum;coutvi;coutwi;for(i=0; ilimitWeight;colonySize = 100;delete w;delete v;void printProblem()int i;cout“;if(k = currAge)cout 时,算法需要 ( n* )的计算时间,这与22回溯法存在着一样的缺点计算速度慢; 本设计采用了遗传算法方法，并用实例进行了验证， 计算结果表明，在耗费上遗传算法虽然优于前者，但是并不一定到最优解。通过对背包问题的解决，我了解到了计算机算法设计与分析课程的重要性，使我对算法产生了兴趣；希望在以后的学习中，我们能够接触到更多有关算法的问题，并能够熟悉掌握各个算法的要点。课程设计说明书(论文)用纸第 21
