下载文档原格式
遗传算法求解背包问题程序实现一、背包问题描述背包问题是著名的NP 完备类困难问题,对这个问题的求解前人已经研究出了不少的经典的方法,对该问题确实能得到很好的结果。
近年来蓬勃发展起来的遗传算法已被广泛地应用于优化领域,其全局最优性、可并行性、高效性在函数优化中得到了广泛地应用遗传算法克服了传统优化方法的缺点,借助了大自然的演化过程,是多线索而非单线索的全局优化方法,采用的是种群和随机搜索机制. 本程序将遗传算法应用于背包问题。
二、实验程序1、编程语言：C++2、开发环境：Microsoft Visual Studio 20053、程序整体流程：步1初始化过程1. 1确定种群规模scale、杂交概率pc、变异概率pm、染色体长度chN及最大进化代数maxgen。
1. 2取x1′(0) = u (0 ,1) , x2′(0) = u (0 ,1) , …, xchN′(0) = u (0 ,1) ,其中函数u (0 ,1) 表示随机地产生数0 或1 ,则x (0) = ( x1 (0) , x2 (0) ,⋯, xN (0) ) .若不满足约束条件,则拒绝接受. 由(1. 2) 重新产生一个新的染色体; 如果产生的染色体可行,则接受它作为种群的一名成员,经过有限次抽样后, 得到scale个可行的染色体xj (0) , j =1 ,2 , ⋯, M ,设xj (0) 的染色体编码为vj (0) ,并记为v (0) = ( v1 (0) , ⋯, vchN (0) ) .1. 3计算各个染色体的适值1. 4 置k = 0步2选择操作2. 1采用转轮法选择下一代。
.步3杂交变异操作3. 1 事先定义杂交操作的概率pc ,为确定杂交操作的父代,从j = 1 到M 重复以下过程:从[0 ,1 ] 中产生随机数r ,若r < pc ,则选择cj′( k)作为一个父代.3. 2 产生两个[1 , N ] 上的随机整数i 、j ,变异的结果为染色体vj′( k)的第i 位基因的值变为其第j 位基因的值,同样将染色体的vj′( k)第j 位基因的值变为其第i 位基因的值.3. 3 检验该染色体的可行性,若可行则作为变异的结果;如不可行,重复3. 2 直至该染色体可行.3. 4 事先定义变异概率pm ,对经过杂交操作的中间个体进行变异操作: ,如果r < pm ,则选择vi″( k) 作为变异的父代.3. 5 产生一个[1 , N ] 上的随机整数i ,及随机地产生数0 或1 , 记为b , 变异的结果为染色体vi″( k) 的第i 位基因的值变为b.3. 6 检验该染色体的可行性,若可行则作为变异的结果:如不可行,重复3. 5 直至该染色体可行.3. 7 计算新个体的适应值,并把它们同时放回,和步2 选择操作中剩余的个体一起构成新一代种群v ( k + 1) = { v1 ( k + 1) , v2 ( k + 1) , ⋯, vM ( k + 1) } .步4 终止检验如果达到最大进化代数maxgen 则终止演化,否则置k : = k + 1 ,转步2.4、程序流程图程序流程图5、程序代码1）主程序代码：KnapsacksProblem.cpp文件#include "GAonKP.h"#include <iostream>using namespace std;void main(){FILE* fp;CGAonKP gakp;int scale; //种群规模double MaxWeight; //背包允许最大财宝质量double pc; //杂交概率double pm; //变异概率int maxgen; //最大进化代数char filename[256];cout<<"遗传算法解决背包问题程序使用说明："<<endl;cout<<"1、该背包问题采用遗传算法"<<endl;cout<<"2、-1编码的方法，其中代表选中所对应的物品，代表不选中该物品"<<endl;cout<<"3、背包允许最带重量，种群规模（解空间大小），";cout<<"杂交概率，变异概率，最大进化代数需自己给";cout<<"定，程序会提示输入"<<endl;cout<<"4、程序提供一个输入示例"<<endl;cout<<"5、输入文件可加单行或多行注释"<<endl;cout<<"例如：#添加单行注释内容#"<<endl;cout<<"例如：#添加多行注释内容"<<endl;cout<<" 添加多行注释内容#"<<endl;cout<<"6、输入文件头位置需指定物品个数为int型数据。
遗传算法求解0-1背包问题一、问题描述给定n种物品和容量为C的背包。
物品i的重量是wi，其价值为vi。
问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?二、知识表示1、状态表示（1）个体或染色体：问题的一个解，表示为n个比特的字符串，比特值为0表示不选该物品，比特值为1表示选择该物品。
（2）基因：染色体的每一个比特。
（3）种群：解的集合。
（4）适应度：衡量个体优劣的函数值。
2、控制参数（1）种群规模：解的个数。
（2）最大遗传的代数（3）交叉率：参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为0.4～0.99。
（4）变异率：发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围一般为0.0001～0.1。
3、算法描述（1）在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；（2）随机产生U中的N个个体s1, s2, …, sN，组成初始种群S={s1, s2, …, sN}，置代数计数器t=1；（3）计算S中每个个体的适应度f() ；（4）若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。
（5）按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；（6）按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；（7）按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；（8）将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3。
三、算法实现1、主要的数据结构染色体：用一维数组表示，数组中下标为i的元素表示第（i+1）个物品的选中状态，元素值为1，表示物品被选中，元素值为0表示物品不被选中。
种群：用二维数组表示，每一行表示一个染色体。
遗传算法的过程：初始化：将计划装入背包的每个物品看成一个二进制串的一位，为1表示放入该物品，为0表示不放入该物品。
初始种群的产生：初始化前对放入背包物品数的一个预测（背包容积/物品最大体积），接下来只要在种群每条染色体中保证有（背包容积/物品最大体积）个为1的位初始化就完成了。
选择：选择进行杂交的父代染色体，被选中的父代染色体总是若干个染色体中最优（适应度最高）的，来保证向优化的方向发展。
详细的选择方法：随机产生2个数：Chrom_Cross_From, Chrom_Cross_To,当然得采用一定的手段来保证前者比后者小。
从Chrom_Cross_From到Chrom_Cross_To这Chrom_Cross_To-Chrom_Cross_From+1条染色体中选择最优（适应度最大）的染色体作为父代之一。
需要进行两次选择得到杂交的两条父代染色体。
这样做可以保证算法不会过早收敛。
函数实现：Individual Select(int ChromSize,Individual Pop[]){int Num_Selected,i,j,Chrom_Selected_From,Chrom_Selected_To,temp;Individual *Chrom_Selected;do{Chrom_Selected_From=rand()%PopSize;Chrom_Selected_To=rand()%PopSize;if(Chrom_Selected_From>Chrom_Selected_To){temp=Chrom_Selected_From;Chrom_Selected_From=Chrom_Selected_To;Chrom_Selected_To=temp;}Num_Selected=Chrom_Selected_To-Chrom_Selected_From+1;}while(Num_Selected<=0);Chrom_Selected=new Individual[Num_Selected];for(i=0;i<Num_Selected;i++)Chrom_Selected[i].chrom=new int[ChromSize];for(i=0,j=Chrom_Selected_From;i<Num_Selected,j<Chrom_Selected_To+1;i++,j++){Chrom_Selected[i]=Pop[j];}Order_Best_First(ChromSize,Num_Selected,Chrom_Selected);Chrom_Selected[0].fitness=Fitness(Chrom_Selected[0].chrom,ChromSize);return Chrom_Selected[0];}杂交：将两次选择得到的父代染色体进行杂交得到一条新的染色体，作为较新种群（并非新的种群）的一条染色体，杂交直到较新种群的染色体数等于原种群的染色体数。
基于遗传算法得0-1背包问题得求解摘要:一、前言组合优化问题得求解方法研究已经成为了当前众多科学关注得焦点,这不仅在于其内在得复杂性有着重要得理论价值,同时也在于它们能在现实生活中广泛得应用。
比如资源分配、投资决策、装载设计、公交车调度等一系列得问题都可以归结到组合优化问题中来。
但就是,往往由于问题得计算量远远超出了计算机在有效时间内得计算能力,使问题得求解变为异常得困难。
尤其对于NP 完全问题,如何求解其最优解或就是近似最优解便成为科学得焦点之一。
遗传算法已经成为组合优化问题得近似最优解得一把钥匙。
它就是一种模拟生物进化过程得计算模型,作为一种新得全局优化搜索算法,它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点,奠定了作为21世纪关键智能计算得地位。
背包问题就是一个典型得组合优化问题,在计算理论中属于NP-完全问题,其计算复杂度为)2(O n ,传统上采用动态规划来求解。
设w[i]就是经营活动 i 所需要得资源消耗,M 就是所能提供得资源总量,p[i]就是人们经营活动i 得到得利润或收益,则背包问题就就是在资源有限得条件下, 追求总得最大收益得资源有效分配问题。
二、问题描述背包问题( Knapsack Problem)得一般提法就是:已知n 个物品得重量(weight)及其价值(或收益profit)分别为0>i w 与0>i p ,背包得容量(contain)假设设为0>i c ,如何选择哪些物品装入背包可以使得在背包得容量约束限制之内所装物品得价值最大？该问题得模型可以表示为下述0/1整数规划模型:目标函数:∑==ni i i n x c x x x f 121),,(max⎪⎩⎪⎨⎧=∈≤∑=),2,1(}1,0{t .s 1n i x p x w i n i i i i (*) 式中i x 为0-1决策变量,1=i x 时表示将物品i 装入背包中,0=i x 时则表示不将其装入背包中。
遗传算法的01背包问题(c语言)基于遗传算法的0-1背包问题的求解摘要：一、前言组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。
比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。
但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。
尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。
遗传算法已经成为组合优化问题的近似最优解的一把钥匙。
它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。
背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题，其n O(2)，传统上采用动态规划来求解。
设w[i]是经营活动 i 所需计算复杂度为要的资源消耗，M是所能提供的资源总量，p[i]是人们经营活动i得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。
二、问题描述背包问题( Knapsack Problem)的一般提法是：已知n个物品的重量（weight）p?00w?，背包的容量（及其价值（或收益profit）分别为contain）假和i i c?0，如何选择哪些物品装入背包可以使得在背包的容量约束限制之设设为i内所装物品的价值最大？该问题的模型可以表示为下述0/1整数规划模型：n?x)x?c,?,xf max(x目标函数：ii12n1?i遗传算法的01背包问题(c语言)?p?wx?s.t iii?（*）1?i?x?{0,1}(i?1,2,?n)?i xx?1x?0时n?则表示不将为0-1决策变量，时表示将物品装入背包中，式中i iii其装入背包中。
三、求解背包问题的一般方法解决背包问题一般是采取动态规划、递归回溯法和贪心方法。
解决0-1背包问题的遗传分布估计算法余娟;贺昱曜【期刊名称】《计算机工程与应用》【年(卷),期】2014(000)009【摘要】0-1背包问题是典型的NP难问题，针对0-1背包问题提出分布估计算法（EDA）与遗传算法（GA）相结合的算法（E-GA）。
该算法在每一次迭代中由二者共同产生种群，并行搜索，两种方法产生的个体数目动态变化，将EDA的全局搜索与GA的局部搜索能力、EDA的快速收敛性与GA的种群多样性结合，实现优势互补。
通过三个背包问题算例进行算法验证，与以往文献相比，结果显示该算法所获最优值优于文献最优值，运行时间短且收敛速度快。
%0-1 knapsack problem is a classic NP-hard problem. For the 0-1 knapsack problem, a combined parallel search algorithm(E-GA)is proposed. The population is generated by Genetic Algorithm(GA)and Estimation of Distribution Algorithm(EDA)together. The population proportion caused by two algorithms is changed dynamically, which combines the global statical information and location information and overcomes the shortcoming of GA and EDA. The algorithm is applied to three widely used knapsack samples, and the results show that proposed E-GA algorithm has better search ability and convergence speed than the other algorithms.【总页数】6页(P12-16,31)【作者】余娟;贺昱曜【作者单位】西北工业大学航海学院，西安 710072;西北工业大学航海学院，西安 710072【正文语种】中文【中图分类】TP18【相关文献】1.用基本遗传算法解决0-1背包问题 [J], 闫丽2.一种结合贪婪因子求解0-1背包问题的分布估计算法 [J], 谭阳;周虹3.基于佳点集遗传算法的0-1背包问题解决方法 [J], 徐宗杨;唐耀庚;王晓霞4.求解折扣{0-1}背包问题的新遗传算法 [J], 吴聪聪; 贺毅朝; 赵建立5.求解0-1背包问题的混合贪婪遗传算法 [J], 陈桢;钟一文;林娟因版权原因，仅展示原文概要，查看原文内容请购买。
0-1背包问题是一种常见的动态规划问题，其目标是在给定背包容量和物品集合的情况下，选择某些物品放入背包，使得背包内物品的总价值最大。
以下是求解0-1背包问题的算法综述：
1. 定义变量和参数：
* 物品集合：包括每个物品的重量和价值。
* 背包容量：表示背包能够容纳的最大重量。
* dp数组：用于存储每个状态下的最大价值，dp[i][j]表示前i个物品、背包承重为j时的最大价值。
2. 初始化dp数组：
* 对于每个物品i和背包容量j，如果物品i能够装入背包，则令dp[i][j]为0；否则，令dp[i][j]为负无穷。
3. 递推计算dp数组：
* 对于每个物品i和背包容量j，如果物品i能够装入背包，则令dp[i][j]为当前物品的价值加上前i-1个物品、背包容量为j-w[i]时的最大价值，即dp[i][j] = dp[i-1][j-w[i]] + p[i]；否则，
令dp[i][j]为前i-1个物品、背包容量为j时的最大价值，即dp[i][j] = dp[i-1][j]。
4. 返回dp数组的最后一个元素，即为所求的最大价值。
以上是求解0-1背包问题的算法综述，实际实现时可以根据具体情况进行优化，以提高算法的效率和性能。
课程设计题目6-基于遗传算法求解0-1背包问题一、题目分析（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），产生出代表新的解集的种群。
一种改进的免疫遗传算法求解0—1背包问题作者：杜彦华靳宗信来源：《创新科技》2013年第02期在现代科技高速发展的过程中，随着交叉学科的发展，从生物体各个信息处理系统中抽取相应的人工模型已成为研究的热点。
人工免疫模型正在为科学贡献力量，以其为基础的各种模型已经应用于科学的各个领域。
传统的遗传算法存在缺陷，例如在迭代后期容易出现退化现象，算法的收敛速度慢等。
但传统遗传算法的改进算法较多，已被成功用于科学的不同领域。
生物作为计算问题的思想源泉，已经为科学工作者提供了许多解决问题的思路。
生物免疫系统自身的许多机制，如适应性、记忆性和多样性等机制能被用来解决各种计算任务，在此基础上发展起来的计算方法已经成为一门学科，已经引起不同领域学者的关注。
根据生物免疫系统与传统遗传算法结合而产生的免疫算法已经表现出良好的性能，本文将生物免疫系统产生多样性抗体的产生机制加入到传统的遗传算法中，提出了一种新型的免疫遗传算法。
为了检测此算法的特性，使用经典的0-1背包问题进行检验，仿真实验结果表明此算法能够很快找到全局最优解，克服遗传算法的缺点，表现出较高的效率。
NIGA在传统的遗传算法中加入生物体产生抗体的多样性机制，即加入免疫算子，不仅保留了原算法本身的优良特性，还可以抑制算法在迭代过程中出现的退化现象，提高算法的收敛速度。
免疫算子对应于待求解问题的解的一些特征信息。
NIGA的执行效率在很大程度上取决于免疫算子的选取。
免疫算子的好坏，即生成抗体的优劣不会影响算法的收敛性，只会影响算法的收敛速度和免疫算子在整个算法中的作用。
所以免疫算子的优劣直接影响了算法的好坏。
本文改进了提取免疫算子的方法，并把这种方法加入到免疫遗产算法中去，得到了一种新型的免疫遗产算法（NIGA）。
使用经典的NP难问题对其进行检验后，表明此算法能够很快找到当前最优解。
根据生物学的相关知识，生物染色体上的固定位置上的基因位可以决定生物的性状。
也就是说，基因通过两个方面影响生物的性状，第一个是基因本身碱基的顺序，第二个是基因本身在染色体上的位置，由此可知，虽然两个基因的碱基顺序相同，但把它们放在染色体的不同位置，生物体就会表现出不同的性状。
基于遗传算法的0-1背包问题的求解摘要：一、前言组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。
比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。
但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。
尤其对于NP 完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。
遗传算法已经成为组合优化问题的近似最优解的一把钥匙。
它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。
背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题， 其计算复杂度为)2(O n ，传统上采用动态规划来求解。
设w[i]是经营活动 i 所需要的资源消耗，M 是所能提供的资源总量，p[i]是人们经营活动i 得到的利润或收益，则背包问题就是在资源有限的条件下， 追求总的最大收益的资源有效分配问题。
二、问题描述背包问题( Knapsack Problem)的一般提法是：已知n 个物品的重量（weight ）及其价值（或收益profit ）分别为0>i w 和0>i p ，背包的容量（contain ）假设设为0>i c ，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内所装物品的价值最大？该问题的模型可以表示为下述0/1整数规划模型：目标函数：∑==ni i i n x c x x x f 121),,(max Λ⎪⎩⎪⎨⎧=∈≤∑=),2,1(}1,0{t .s 1n i x p x w i n i i i i Λ （*） 式中i x 为0-1决策变量，1=i x 时表示将物品i 装入背包中，0=i x 时则表示不将其装入背包中。
遗传算法求解0-1背包问题。
（步骤）#include "iostream.h"#include "iomanip.h"#include "stdlib.h"#include "math.h"#include "time.h"//定义问题的最大规模#define max 100//问题规模，即共有多少个包int packageNum;//每个包的重量int packageWeight[max];//每个包的价值int packageValue[max];//约束，背包的最大容量int limitWeight;//群体的规模int colonySize;//colonyState[i][k] 表示一个染色体//colonyState[1...colonySize][ 0|1 ] 表示一代群体int colonyState[max][2][max];// currAge 表示当前代的编号// (currAge+1)%2 表示下一代的编号int currAge = 0;//个体评价信息表typedef struct tagIndividualMsg{int index;int value;} IndividualMsg;IndividualMsg individualMsg[max];//////////////////////////////////////////////////////////// // 函数声明void printColonyState( int nextAge );//////////////////////////////////////////////////////////// //初始化群体void colonyInit(){int i , j;int w;for( i = 0 ; i < colonySize ; i++ ){//保证找到一个符合约束的染色体w = limitWeight + 1;while( w > limitWeight ){w = 0;for( j = 0 ; j < packageNum && w <= limitWeight ; j++ ){colonyState[i][currAge][j] = rand() % 2;w += packageWeight[j] * colonyState[i][currAge][j];}}}}//对个体进行评价int cmp( const void *a , const void *b ){IndividualMsg *x = (IndividualMsg *)a;IndividualMsg *y = (IndividualMsg *)b;return y->value - x->value;}void individualEstimate(){int i , j;for( i = 0 ; i < colonySize ; i++ ){individualMsg[i].index = i;individualMsg[i].value = 0;for( j = 0 ; j < packageNum ; j++ )individualMsg[i].value += packageValue[j] * colonyState[i][currAge][j]; }qsort( individualMsg , colonySize , sizeof(IndividualMsg) , cmp );}//终止循环的条件bool stopFlag(){//进行n 代进行后停止static int n = 50;if( n-- <= 0 )return true;elsereturn false;}//赌轮选择int gambleChoose(){int wheel[max] = { 0 };int i = colonySize - 1;int choose;wheel[i] = individualMsg[i].value;for( i-- ; i >= 0 ; i-- )wheel[i] = ( individualMsg[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--;// cout<<"----------------------------------------"<<endl;// cout<<"wheel :"<<endl;// for( i = 0 ; i < colonySize ; i++ )// cout<<setw(5)<<wheel[i];// cout<<endl;// cout<<"seed = "<<seed<<endl;// cout<<"choose "<<choose<<endl;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 < packageNum ; j++ ){colonyState[index][nextAge][j] =colonyState[individualMsg[male].index][currAge][j];colonyState[index+1][nextAge][j] =colonyState[individualMsg[female].index][currAge][j];}for( i = 0 ; i < acrossBit ; i++ ){t = colonyState[index][nextAge][i];colonyState[index][nextAge][i] = colonyState[index+1][nextAge][i];colonyState[index+1][nextAge][j] = t;}}//变异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 < colonySize ; i++ ){weight = 0;for( j = 0 ; j < packageNum ; j++ )weight += packageWeight[j] * colonyState[i][nextAge][j];if( weight > limitWeight ){//随机生成新的个体w = limitWeight + 1;while( w > limitWeight ){w = 0;for( j = 0 ; j < packageNum && w <= limitWeight ; j++ ){colonyState[i][nextAge][j] = rand() % 2;w += packageWeight[j] * colonyState[i][nextAge][j];}}}}printColonyState( nextAge );}//最优个体保护void saveBest(){int i , j;int min , minp , value;int nextAge = ( currAge+1)%2;min = individualMsg[0].value;minp = -1;for( i = 0 ; i < colonySize ; i++ ){value = 0;for( j = 0 ; j < packageNum ; j++ )value += packageValue[j] * colonyState[i][nextAge][j]; if( value <= min ){min = value;minp = i;}}if( minp >= 0 ){for( j = 0 ; j < packageNum ; j++ ){colonyState[minp][nextAge][j] =colonyState[individualMsg[0].index][currAge][j];}}}//////////////////////////////////////////////////////////// void setProblem(){int i;packageNum = 5;int w[] = { 5 , 4 , 3 , 2 , 1 };int v[] = { 8 , 9 , 3 , 1 , 2 };for( i = 0 ; i < packageNum ; i++ ){packageWeight[i] = w[i];packageValue[i] = v[i];}limitWeight = 13;colonySize = 5;}void printProblem(){int i;cout<<"----------------------------------------"<<endl;cout<<"problem state:"<<endl;cout<<"packageNum = "<<packageNum<<endl;cout<<"limitWeight = "<<limitWeight<<endl;cout<<"Weight: ";for( i = 0 ; i < packageNum ; i++ )cout<<setw(3)<<packageWeight[i];cout<<endl;cout<<"Value: ";for( i = 0 ; i < packageNum ; i++ )cout<<setw(3)<<packageValue[i];cout<<endl;}void printColonyState( int k ){cout<<"----------------------------------------"<<endl;cout<<"colonyState-->";if( k == currAge )cout<<"currAge:"<<endl;elsecout<<"next age:"<<endl;int i , j;for( i = 0 ; i < colonySize ; i++ ){for( j = 0 ; j < packageNum ; j++ )cout<<setw(2)<<colonyState[i][k][j];cout<<endl;}}void printIndividualMsg(){int i;cout<<"----------------------------------------"<<endl;cout<<"Individual Msg:"<<endl;for( i = 0 ; i < colonySize ; i++ ){cout<<individualMsg[i].index<<"\t"<<individualMsg[i].value<<endl; }}////////////////////////////////////////////////////////////void main(){srand( (unsigned int)time(NULL) );setProblem();printProblem();//初始群体colonyInit();printColonyState( currAge );while( !stopFlag() ){//评价当前群体individualEstimate();//生成下一代for( int i = 0 ; i < colonySize ; i += 2 ){int male = gambleChoose();int female = gambleChoose();across( male , female , i );aberrance( i );aberrance( i + 1 );}//处理死亡个体dealDeath();//最优个体保护saveBest();//现在的下一代变成下一轮的当前代currAge = ( currAge + 1 ) % 2;//printColonyState( currAge );}//输出问题解individualEstimate();cout<<"近似解:"<<endl;int j , w = 0;cout<<setw(10)<<"Value:";for( j = 0 ; j < packageNum ; j++ )cout<<setw(5)<<packageValue[j];cout<<endl;cout<<setw(10)<<"Weight:";for( j = 0 ; j < packageNum ; j++ ){w += packageWeight[j] * colonyState[individualMsg[0].index][currAge][j]; cout<<setw(5)<<packageWeight[j];}cout<<endl;cout<<setw(10)<<"Choose:";for( j = 0 ; j < packageNum ; j++ )cout<<setw(5)<<colonyState[individualMsg[0].index][currAge][j];cout<<endl;cout<<"limitWeight: "<<limitWeight<<endl;cout<<"总重量: "<<w<<endl;cout<<"总价值: "<<individualMsg[0].value<<endl; }////////////////////////////////////////////////////////////。
