遗传算法的0~1背包问题(c语言).pdf

《遗传算法的0~1背包问题(c语言).pdf》由会员分享，可在线阅读，更多相关《遗传算法的0~1背包问题(c语言).pdf（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于遗传算法的 0-1 背包问题的求解摘要：一、前言一、前言组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。比如资源分配、投资决策、装载设计、公交车调度等一系列的问题都可以归结到组合优化问题中来。但是，往往由于问题的计算量远远超出了计算机在有效时间内的计算能力，使问题的求解变为异常的困难。尤其对于NP完全问题，如何求解其最优解或是近似最优解便成为科学的焦点之一。遗传算法已经成为组合优化问题的近似最优解的一把钥匙。它是一种模拟生物进化过程的计算模型，作为一种新的全局优化搜索算法，它以其简单、鲁棒性强、

2、适应并行处理以及应用范围广等特点，奠定了作为21世纪关键智能计算的地位。背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题，其nO(2)，传统上采用动态规划来求解。设wi是经营活动 i 所需要计算复杂度为的资源消耗，M是所能提供的资源总量，pi是人们经营活动i得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。二、问题描述背包问题(Knapsack Problem)的一般提法是：已知n个物品的重量（weight）及其价值（或收益profit）分别为wi 0和pi 0，背包的容量（contain）假设设为ci 0，如何选择哪些物品装入背包可以使得

3、在背包的容量约束限制之内所装物品的价值最大？该问题的模型可以表示为下述0/1整数规划模型：目标函数：maxf(x1,x2,xn)cixii1nnwixi pis.ti1（*）xi0,1(i 1,2,n)式中xi为 0-1 决策变量，xi1时表示将物品i装入背包中，xi 0时则表示不将其装入背包中。三、求解背包问题的一般方法解决背包问题一般是采取动态规划、递归回溯法和贪心方法。动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。对于背包问题可以对子过程用枚举法求解，而且约束条件越多，决策的搜索范围越小，求解也越容易。它的主要缺点是用数值方法求解时会随着状态变量的个数呈指数级的

4、增长，往往对于求解背包问题的实际问题是不现实的。使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解；但是由于此问题解的总组合数有2n个，因此，随着物件数 n 的增大，其解的空间将以2级增长，当 n 大到一定程度上，用此算法解决背包问题将是不现实的。使用贪心方法求解时计算的复杂度降低了很多，但是往往难以得到最优解，有时所得解与最优解相差甚远。因此，我们可以探索使用遗传算法解决物件数较大的背包问题。四、遗传算法简介遗传算法(Genetic Algorithms，GA)是在1975 年首次由美国密西根大学的D。J。Holland 教授和他的同事们借鉴

5、生物界达尔文的自然选择法则和孟德n尔的遗传进化机制基础之上提出的。经过近30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应值。算法将根据适应度值进行它的寻优过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的。它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的尽可能多的点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性

6、可由Holland提出的模式定理(Schema Therem)和隐式并行性得以解释。在遗传算法中，定义长度较短、低阶且适应值超过平均适应值的模式在群体中数目的期望值按指数递增，这个结论称为遗传算法的基本定理。遗传算法是通过定义长度短、确定位数少、适应度值高的模式的反复抽样、组合来寻找最佳点，称这些使遗传算法有效工作的模式为积木块，是遗传算法构造答案的基本材料。但归根到底，要使遗传算法有效工作必须按照遗传算法的模式定理(或积木块假设)根据具体问题设计合理的编码方案。在运行遗传算法程序时，需要对一些参数作事先选择，它们包括种群的大小、染色体长、交叉率、变异率、最大进化代数等，这些参数对 GA 的性

7、能都有很重要的影响。在试验中参数一般选取如下：种群大小N=20100，交叉概率pc=0.4 0.9，变异概率pm=0.0010.1，最大进化代数maxgen=100500。遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图 1 所示。编码初始化种群评估种群中个体适应度演选择化交叉变异图1、遗传算法的基本流程遗传算法的基本流程描述如下：（1）编码：将解空间的解数据进行二进制编码，表达为遗传空间的基因型串（即染色体）结构数据，如将数据9编码为“1001”；（2）初始化种群：定义整数pop_size 作为染色体的个数，并且随机产生pop_size 个染色体作为初始种群；（3）评

8、估 种 群 中 个 体 适 应 度：评 价 函 数 对 种 群 中 的 每 个 染 色 体（chromosome）求得其个体适应度fi(fitness)；（4）选择：选择把当前群体中适应度较高的个体按某种规则或者模型遗传到下一代种群中，这里所用的规则是：染色体在种群中被选择的可能性与其个体的适应度的大小成正比；（5）交叉：定义参数pc作为交叉操作的概率，由（4）选择得到的两个个体以概率pc交换各自的部分染色体，得到新的两个个体；（6）变异：定义参数pm作为变异操作的概率，由（5）得到每个个体中的每个基因值都以概率pm进行变异；（7）演化：经过选择、交叉和变异操作，得到一个新的种群，对上述步骤经

9、过给定的循环次数（maxgen）的种群演化，遗传算法终止。五、背包问题的遗传算法求解描述基于背包问题的模型（*），我们设计了针对于背包问题的染色体编码方法：将待求解的各量X表示成长为n的二进制字符串xj，j=1，2，n。xj 0表示物体 j 不放入背包内，例如：111001100 xj 1表示物体 j 放入背包内。100111 代表一个解，它表示将第 1、2、3、6、7n-2,n-1,n 号物体放入背包中，其它的物体则不放入。根据遗传算法的基本流程，我们确定了求解背包问题的遗传算法：步骤步骤 1 1、初始化过程、初始化过程1.1确定种群规模 popsize、杂交概率pc、变异概率pm、染色体长

10、度 lchrom及最大进化代数 maxgen；1.2读入背包问题的相关信息，如每个物体的重量 weightj、每个物体的收益 profitj和背包的容量 contain，其中1.3取xj u(0,1)j 0,1,(lchrom 1)；j 0,1,(lchrom1)，其中u(0,1)表示 0-1 整数的均匀分布函数，即随机地生成数 0 或 1，生成的xj串即可看为一个染色体个体。若不满足模型（*）的约束条件，则拒绝接受，由 1.2 重新生成一个新的染色体个体 chrom；如果产生的染色体可行，则接受它作为种群的一名成员，经过有限次的 1.2 抽样后，得到 popsize 个可行的染色体 chro

11、m，形成新的种群。1.4置种群的代数 gen=0；步骤步骤 2 2、计算种群中个体适应度以及统计种群适应度情况、计算种群中个体适应度以及统计种群适应度情况2.1按照下列公式计算种群中个体适应度：lchrom 1weight weightj*chromjj 0(1)；lchrom1profitj*chromjj0fitnesslchrom1profitj*chromjalpha*(weightcontain)j0ifweight contain(2)ifweight contain公式（2）的下半部分即为适应度的惩罚函数，其中参数alpha 1.0。2.2按公式（3）计算种群的总体适应度，sum

12、fitnesspopsize1i0fitnessi(3)并且按照排序的方法统计出种群中的最大、最小适应度的染色体个体，分别标记为 maxpop、minpop；步骤步骤 3 3、选择操作、选择操作3.1生成一个随机数 rand_Number，要求0 rand _ Nuber 1；3.2按照赌轮法选择个体，赌轮法的算法描述如下：int selection()i=0;/个体的编号sum=0；/部分个体适应度的累加和/根据随机数和群体的总适应度确定赌轮的位置wheel-pos=rand_Number*sufitness;while sumwheel-pos&i=popsizei=i+1;sum=sum

13、+fitnessi;/fitness 为第 i 个个体的适应度return i-1;/选择了个体 i-13.3重复两次操作 3.1、3.2，生成两个个体作为交叉操作的父代；步骤四、交叉操作步骤四、交叉操作4.1根据事先定义好的交叉概率pc，为了确定是否进行交叉操作，则生成0，1的随机数 pp，若pp pc，则进行 4.2 交叉操作，否则将两个父代保留为下一代的两个个体；4.2随机生成0,lchrom 1的整数作为交叉点，对两个父代个体交叉生成新的两个个体；4.3重复 pop_size/2 次 4.1、4.2 便可生成 pop_size 个个体组成新的种群；步骤五、步骤五、变异操作变异操作5.1

14、根据事先定义好的变异概率pm，为了确定新种群上的每个个体上的每个基因是否进行变异操作，则生成0，1的随机数 pp，若pp pm，则进行 5.2变异操作，否则基因不变异；5.2基因变异操作为原基因若为 1，则新基因则变异为0，若原基因为0，则新基因变异为 0；步骤步骤 6 6、演化演化6.1按步骤 2 的方法计算新种群的个体适应度和总体适应度情况，尤其是找出新种群中最大适应度的个体和最小适应度的个体；6.2若旧种群的最大个体适应度新种群的最大个体适应度，把旧种群的最大适应度的个体代替新种群中的最小适应度的个体，否则进行 6.3；6.3种群的代数 gen=genm+1，若 genMaxgen，则结

15、束种群的演化，否则转到步骤 2。六、遗传算法求解的实现1、遗传算法的主要参数#define popsize 80/种群的规模#define pc 0.7/杂交概率#define pm 0.1/变异概率#define lchrom 50/染色体长度#define maxgen 5000/最大进化代数double alpha;/计算适应度时使用的 惩罚函数系数2、数据结构（1）背包信息：/背包问题中物体重量、收益、背包容量int weightlchrom,profitlchrom,contain;（2）种群个体结构体struct populationunsigned int chromlchrom

16、;/染色体double fitness;/适应度unsigned int parent1,parent2,cross;/双亲、交叉点;（3）父代种群和新生代种群/父代种群、新生代种群struct population oldpoppopsize,newpoppopsize;/pop_size 为种群大小（4）适应度信息/种群的总适应度、最小、最大适应度doublesumfitness,minfitness,maxfitness;/一个种群中最大和最小适应度的个体编号intminpop,maxpop;3、主要函数说明（1）、int read_infor()功能：从文件 knapsack.txt

17、中读出背包信息（物体重量、收益、背包容量）；参数：无；返回值：返回读取文件信息是否正确；流程图：见图 2。打开文件否获取文件指针成功是读出物体重量信息读出物体收益信息读出背包容量信息返回图 2、read_infor()流程图（2）double cal_fit(unsigned int*chr)功能：种群中个体适应度计算；参数：unsigned int*chr 是染色体个体的指针，根据指针所指向的染色体计算个体的适应度；返回值：染色体个体适应度的大小；流程图：见图 3。适应度和总重量置 0累加计算个体适应度和背包的总重量总重量背包容量是使用惩罚函数对个体适应度进行处理返回个体适应度图 3、函数

18、cal_fit 的流程图（3）、void statistics(struct population*pop)功能：群体适应度的最大最小值以及其他信息；参数：struct population*pop 是种群指针，根据指针所指向的种群信息统计群体适应度的信息；返回值：无；流程图：见图 4。（4）、void report(struct population*pop,int gen)功能：报告种群的适应度信息，尤其是最大个体适应度、最大适应度个体的染色体信息；参数：struct population*pop 是种群指针，根据指针所指向的种群报告群体适应度的信息，gen 是表示此种群所在的演化代数返回

19、个体适应度返回值：无；流程图：见图 5。最大最小总适应度都置为首个体的适应度计数器 i=1ilchrom-1返回是总适应度=总适应度+个体 i 的适应度I 的适应度最大适应度I 的适应度最小适应度置最大适应度的编号为 i置最小适应度的编号为 ii=i+1图 4、函数 statistics 的流程图输出种群的代数 gen输出最大适应度个体的染色体信息 chrom输出最大个体适应度（5）、void initpop()功能：生成初始种群；参数：无；返回值：无；流程图：见图 6。maxfitness图 5、函数 report 的流程图个体计数器 i=0否ipop_size?返回是随机生成个体 i 染色

20、体计算生成个体的适应度否若背包不超重是接受个体，i=i+1图 6、函数 initpop 流程图（6）、int execise(double probability)功能：概率选择试验，以概率 probability 做随机试验，判断是否进行交叉或变异操作；参数：double probability 为交叉概率或变异概率返回值：试验是否成功，0 代表不试验成功，将不做交叉或者变异操作，1 代表试验成功，即进行交叉或者变异操作；流程图：见图 7。生成0，1之间的小数 pp是若 ppprobability否返回实验成功 1返回实验不成功 0图 7、函数 execise 的流程图（7）、int sel

21、ection(int pop)功能：在父代种群中选择个体，规则为适应度越大的个体被选择的概率越大；参数：int pop 为父代种群；返回值：父体中被选择的个体 i；流程图：见图 8。个体编号 i=0，部分适应度之和 partsum=0产生随机数rand_Number计算赌轮所在位置wheel_pospartsumwheel-pos&i=popsize?Partsum=partsum+个体 i的适应度个体计数器 i=i+1返回被选择的个体 i-1图 8、函数 selection的流程图（8）、int crossover(unsigned int*parent1,unsigned int*pare

22、nt2,int i)功能：两个父代个体在染色体的第 i个位置进行交叉，生成两个新个体；参数：unsigned int*parent1,unsigned int*parent2分别为两个父代染色体指针，指针指向父代个体的染色体，i为新种群的个体编号；返回值：交叉是否成功；流程图：见图 9。概率选择试验成功否是随机生成交叉位置cross_pos两个父代个体按照交叉位置进行交叉，生成新的两个个体保留两个父体成为新种群中的个体图 9、函数 crossover 的流程图（9）、int mutation(unsigned int alleles)功能：根据变异概率进行变异操作；参数：unsigned in

23、t alleles 是染色体上的基因型，在这里就是 0 或 1 的取值；返回值：变异后的基因型；流程图：见图 10。概率选择试验成功否是进行变异返回变异或者原值图 10、函数 mutation 的流程图（10）、void generation()功能：综合选择、交叉、变异等操作，生成新的种群；参数：无；返回值：无；流程图：见图 11。置个体编号 i=0ipop_size?是调用 selection 生成两个父体生成新的种群完毕调用 crossover，交叉生成两个新个体对每个个体的基因调用 mutation 进行变异置个体编号 i=i+2图 11、函数 generation 的流程图（11）、

24、void main()功能：遗传算法的主函数；参数：无；返回值：无；流程图：见图 11。调用 read_infor，读入背包信息置演化代数 gen=0调用 initpop()生成初始种群调用statistics()统计种群的适应度GenMaxgen?是调用 generation()生成新种群调用statistics()统计种群的适应度调用 report()，输出结果信息新种群的最大适应度旧种群的是复制旧种群的最大适应度个体到新种群中最小个体置演化代数 gen=gen+1图 12、主函数 main 的流程图七、成果说明七、成果说明1 1、程序开发程序开发环境环境开发环境：Visual C+6.0

25、(把 Fortran 程序改为 VC)操作系统：Windows 2003 Professional2 2、程序性能程序性能对比对比运行时间与加速比（如表 1 所示）进程数 p（个）运行时间 t（秒）加速比 s1129s278s1.65438s3.38表 1、运行时间与加速比3 3、程序运行结果：、程序运行结果：实例数据：假设物体的重量 Weight、物体的收益 Profit和背包的容量 Contain 分别为：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，50

26、，30，45，30，60，50，20，65，20，25，30，10，20，25，15，10，10，10，4，4，2，1Profit=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，1Contain=1000，如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大?传统的算法（动态规划、递归回溯

27、法和贪心算法所得结果传统的算法（动态规划、递归回溯法和贪心算法所得结果：总价值为 30773077,总重量为 999999。20012001 年张铃，张钹教授在计算机学报上发表的佳点集遗传算法所得结果年张铃，张钹教授在计算机学报上发表的佳点集遗传算法所得结果总价值为 31033103,总重量为 10001000。我们算法所得结果：我们算法所得结果：总价值为 31033103,总重量为 10001000。我们所求得最优解的个体分配情况为我们所求得最优解的个体分配情况为：11010101111011011011011111110100001010011000001000算法传统的算法佳点集算法遗传

28、算法最大迭代次数4007075总价值为307731033103总重量为99910001000八、收获、体会和课题展望八、收获、体会和课题展望在本课题中，我们研究了如何用遗传算法求解组合优化问题中的背包问题。我们可以看出在求解背包问题上显示了超出想象、良好的搜索能力，它具有收敛快、搜索速度快的特点，在试验中取得了比动态规划、递归回溯法和贪心法等更好的求解效果。然而在一般情况下，使用基本遗传算法解决背包问题时，得到问题的近似解也不能满足逼近最优解的要求。如何改进基本遗传算法使它所求得的解逼近最优解，成为我们当前亟待解决的问题，也是我们将来的课题中所要研究的重要问题。/knapsack.cpp:De

29、fines the entry point for the console application./#include stdafx.h#include#include#include#include#include#include/重要常量参数#define popsize 200/种群的规模#define pc 0.618/杂交概率#define pm 0.03/变异概率#define lchrom 50/染色体长度#define maxgen 1000/最大进化代数struct populationunsigned int chromlchrom;/染色体double weight;/背

30、包重量double fitness;/适应度unsigned int parent1,parent2,cross;/双亲、交叉点;/新生代种群、父代种群struct population oldpoppopsize,newpoppopsize;/背包问题中物体重量、收益、背包容量int weightlchrom,profitlchrom,contain;/种群的总适应度、最小、最大、平均适应度double sumfitness,minfitness,maxfitness,avgfitness;/计算适应度时使用的 惩罚函数系数double alpha;/一个种群中最大和最小适应度的个体intm

31、inpop,maxpop;/*读入背包信息,并且计算惩罚函数系数*/void read_infor()FILE*fp;int j;/获取背包问题信息文件if(fp=fopen(knapsack.txt,r)=NULL)/读取文件失败AfxMessageBox(The file is not found,MB_OK,NULL);return;/读入物体收益信息for(j=0;jlchrom;j+)fscanf(fp,%d,&profitj);/读入物体重量信息for(j=0;jlchrom;j+)/读入背包容量fscanf(fp,%d,&weightj);fscanf(fp,%d,&contai

32、n);fclose(fp);/根据计算的个体重量,判断此个体是否该留在群体中double cal_weight(unsigned int*chr)int j;double pop_weight;/背包重量pop_weight=0;for(j=0;jlchrom;j+)pop_weight=pop_weight+(*chr)*weightj;chr+;return pop_weight;/*种群中个体适应度计算*/double cal_fit(unsigned int*chr)int j;double pop_profit;/适应度pop_profit=0;/pop_weight=0;for(j

33、=0;jlchrom;j+)pop_profit=pop_profit+(*chr)*profitj;/pop_weight=pop_weight+(*chr)*weightj;return pop_profit;chr+;/*群体适应度的最大最小值以及其他信息*/void statistics(struct population*pop)sumfitness=pop0.fitness;minfitness=pop0.fitness;int i;double tmp_fit;minpop=0;maxfitness=pop0.fitness;maxpop=0;for(i=1;imaxfitnes

34、s)&(int)(tmp_fit*10)%10=0)maxfitness=popi.fitness;maxpop=i;/选择种群中最小适应度的个体if(tmp_fitminfitness)/计算平均适应度avgfitness=sumfitness/(float)popsize;minfitness=popi.fitness;minpop=i;/printf(nthe max pop=%d;,maxpop);/printf(nthe min pop=%d;,minpop);/printf(nthe sumfitness=%fn,sumfitness);/报告种群信息void report(str

35、uct population*pop,int gen)int j;printf(the generation is%d.n,gen);/输出种群的代数/输出种群中最大适应度个体的染色体信息printf(The populations chrom is:n);for(j=0;jlchrom;j+)/输出群体中最大适应度if(j%5=0)printf();printf(%1d,popmaxpop.chromj);int pop_weight=0;printf(nThe populations max fitness is%d.,(int)popmaxpop.fitness);printf(nThe

36、 knapsack weight is%d.nn,(int)popmaxpop.weight);/*生成初始种群*/void initpop()int i,j,ispop;double tmpWeight;/变量用于判断是否为满足条件的个体ispop=false;/生成 popsize 个种群个体for(i=0;ipopsize;i+)while(!ispop)/选择重量小于背包容量的个体,即满足条件for(j=0;jlchrom;j+)oldpopi.chromj=rand()%2;/随机生成个体的染色体oldpopi.parent1=0;/双亲oldpopi.parent2=0;oldpo

37、pi.cross=0;/交叉点tmpWeight=cal_weight(oldpopi.chrom);if(tmpWeight=contain)oldpopi.fitness=cal_fit(oldpopi.chrom);oldpopi.weight=tmpWeight;oldpopi.parent1=0;oldpopi.parent2=0;oldpopi.cross=0;ispop=true;/此个体可以加入到种群中ispop=false;/*遗传操作*/概率选择试验int execise(double probability)double pp;/如果生成随机数大于相应的概率则返回真，否则

38、试验不成功pp=(double)(rand()%20001/20000.0);if(pp=probability)return 1;return 0;/选择进行交叉操作的个体int selection(int pop)double wheel_pos,rand_Number,partsum;int parent;/赌轮法选择rand_Number=(rand()%2001)/2000.0;wheel_pos=rand_Number*sumfitness;/赌轮大小partsum=0;parent=0;dopartsum=partsum+oldpopparent.fitness;parent=p

39、arent+1;while(partsumwheel_pos&parentpopsize);return parent-1;/*交叉操作*/int crossover(unsigned int*parent1,unsigned int*parent2,int i)int j,cross_pos;if(execise(pc)else cross_pos=lchrom-1;/生成交叉位置 0,1,.(lchrom-2)cross_pos=rand()%(lchrom-1);for(j=0;j=cross_pos;j+)/保留复制；for(j=cross_pos+1;j=(lchrom-1);j+)

40、/从交叉点开始交叉newpopi.chromj=parent2j;/包括在概率选择不成功时，父体完全保留newpopi.chromj=parent1j;/记录交叉位置newpopi.cross=cross_pos;return 1;/*变异操作*/int mutation(unsigned int alleles)if(execise(pm)if(alleles)alleles=0;else alleles=1;/返回变异值，或者返回原值return alleles;/*群体更新*/void generation()unsigned int i,j,mate1,mate2;double tmp

41、Weight;int ispop;/记录是否是符合条件的个体i=0;while(ipopsize)ispop=false;while(!ispop)/选择mate1=selection(i);mate2=selection(i+1);/交叉crossover(oldpopmate1.chrom,oldpopmate2.chrom,i);/变异for(j=0;jlchrom;j+)newpopi.chromj=mutation(newpopi.chromj);/选择重量小于背包容量的个体,即满足条件tmpWeight=cal_weight(newpopi.chrom);if(tmpWeight=

42、contain)/此个体可以加入到种群中newpopi.fitness=cal_fit(newpopi.chrom);newpopi.weight=tmpWeight;newpopi.parent1=mate1;newpopi.parent2=mate2;ispop=true;i=i+1;void main(int argc,char*argv)int gen,oldmaxpop,k;double oldmax;read_infor();/读入背包信息gen=0;srand(unsigned)time(NULL);/置随机种子initpop();memcpy(&newpop,&oldpop,p

43、opsize*sizeof(struct population);statistics(newpop);/统计新生种群的信息report(newpop,gen);while(genmaxgen)gen=gen+1;if(gen%100=0)srand(unsigned)time(NULL);/置随机种子oldmax=maxfitness;oldmaxpop=maxpop;generation();statistics(newpop);/统计新生代种群信息/如果新生代种群中个体的最大适应度小于老一代种群/个体的最大适应度，则保存老一代种群个体的最大适应度/否则报告新生代的最大适应度if(maxfitnessoldmax)for(k=0;koldmax)report(newpop,gen);newpopminpop.cross=oldpopoldmaxpop.cross;statistics(newpop);printf(It is over.);getch();