遗传算法地0-1背包问题(c语言)

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

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

3、 ci0 ，如何选择哪些物品装入背包可以使得在背包的容量约束限制之内所装物品的价值最大？该问题的模型可以表示为下述0/1整数规划模型：n目标函数： maxf ( x1, x2 , xn )ci xii 1ns.twi xipi* i 1专业资料整理WORD格式xi 0,1(i1,2,n)专业资料整理WORD格式式中 xi为 0-1 决策变量， xi1时表示将物品i装入背包中， xi0 时那么表示不将其装入背包中。三、求解背包问题的一般方法解决背包问题一般是采取动态规划、 递归回溯法和贪心方法。 动态规划可以把困难得多阶段决策变换为一系列相互联系比较容易的单阶段问题。 对于背包问题可以对子过程用

4、枚举法求解， 而且约束条件越多， 决策的搜索X围越小， 求解也越容易。它的主要缺点是用数值方法求解时会随着状态变量的个数呈指数级的增长，往往对于求解背包问题的实际问题是不现实的。使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解；但是由于此问题解的总组合数有2n个，因此，随着物件数n 的增大，其解的空间将以2n级增长，当n 大到一定程度上，用此算法解决背包问题将是不现实的。使用贪心方法求解时计算的复杂度降低了很多，但是往往难以得到最优解，有时所得解与最优解相差甚远。因此，我们可以探索使用遗传算法解决物件数较大的背包问题。四、遗传算法简介遗传算法

5、 ( Genetic Algorithms， GA) 是在 1975 年首次由美国密西根大学的D。J。Holland 教授和他的同事们借鉴生物界达尔文的自然选择法那么和孟德尔的遗传进化机制根底之上提出的。 经过近 30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。遗传算法是将问题的每一个可能性解看作是群体中的一个个体 (染色体 )，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进展评价，给出一个适应值。 算法将根据适应度值进展它的寻优过程， 遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的

6、。 它的搜索能力由选择算子和杂交算子决定，变异算子那么保证了算法能够搜索到问题空间的尽可能多的点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由 Holland提出的模式定理 ( Schema Therem) 和隐式并行性得以解释。 在遗传算法中， 定义长专业资料整理WORD格式度较短、低阶且适应值超过平均适应值的模式在群体中数目的期望值按指数递增，这个结论称为遗传算法的根本定理。 遗传算法是通过定义长度短、 确定位数少、适应度值高的模式的反复抽样、 组合来寻找最正确点， 称这些使遗传算法有效工作的模式为积木块， 是遗传算法构造答案的根本材料。 但归根到底， 要使遗传算法有效工作

7、必须按照遗传算法的模式定理 (或积木块假设 ) 根据具体问题设计合理的编码方案。在运行遗传算法程序时， 需要对一些参数作事先选择， 它们包括种群的大小、染色体长、穿插率、变异率、最大进化代数等，这些参数对 GA 的性能都有很重要的影响。在试验中参数一般选取如下： 种群大小 N= 20100 ，穿插概率 pc = 0.40.9 ，变异概率 pm= 0.0010.1 ，最大进化代数 maxgen = 100500。遗传算法是具有“生成 +检测的迭代过程的搜索算法。它的根本处理流程如图 1 所示。编码初始化种群评估种群中个体适应度演选择化交叉变异图1、遗传算法的根本流程遗传算法的根本流程描述如下：专

8、业资料整理WORD格式1编码：将解空间的解数据进展二进制编码，表达为遗传空间的基因型串即染色体构造数据，如将数据9编码为“ 1001；2初始化种群：定义整数 pop_size作为染色体的个数，并且随机产生 pop_size 个染色体作为初始种群；3评估种群中个体适应度： 评价函数对种群中的每个染色体chromosome求得其个体适应度 f i ( fitness) ；4选择：选择把当前群体中适应度较高的个体按某种规那么或者模型遗传到下一代种群中， 这里所用的规那么是： 染色体在种群中被选择的可能性与其个体的适应度的大小成正比；5穿插：定义参数pc作为穿插操作的概率，由4选择得到的两个个体以概率

9、 pc交换各自的局部染色体，得到新的两个个体；6变异：定义参数 p m作为变异操作的概率，由5得到每个个体中的每个基因值都以概率 p m进展变异；7演化：经过选择、穿插和变异操作，得到一个新的种群，对上述步骤经过给定的循环次数 maxgen的种群演化，遗传算法终止。五、背包问题的遗传算法求解描述基于背包问题的模型 * ，我们设计了针对于背包问题的染色体编码方法：将待求解的各量 X 表示成长为n的二进制字符串 x j ，j=1，2，,，n。x j0表示物体 j 不放入背包内，x j1 表示物体j放入背包内。 例如：111001100,100111 代表一个解，它表示将第1、 2、3、6、7,n-

10、2,n-1,n号物体放入背包中，其它的物体那么不放入。根据遗传算法的根本流程，我们确定了求解背包问题的遗传算法：步骤 1、初始化过程1.1确定种群规模 popsize、杂交概率 pc 、变异概率 pm、染色体长度 lchrom及最大进化代数maxgen；1.2读入背包问题的相关信息，如每个物体的重量weightj 、每个物体的收专业资料整理WORD格式益profitj和背包的容量contain，其中j0,1,(lchrom1) ；专业资料整理WORD格式1.3取 x ju(0,1)j0,1,(lchrom1) ，其中u(0,1)表示0-1整数的均匀专业资料整理WORD格式分布函数，即随机地生成

11、数0 或1，生成的x j串即可看为一个染色体个体。专业资料整理WORD格式假设不满足模型 * 的约束条件，那么拒绝承受，由1.2 重新生成一个新的染色体个体 chrom；如果产生的染色体可行，那么承受它作为种群的一名成员，经过有限次的1.2 抽样后，得到 popsize 个可行的染色体chrom，形成新的种群。1.4置种群的代数 gen=0；步骤 2、计算种群中个体适应度以及统计种群适应度情况2.1按照以下公式计算种群中个体适应度：l c h r o m1(1) ；w e i g h tw e i ghjt* c h r o jmj0lchrom 1profit j * chrom jifwe

12、ightcontainj 0(2)fitness lchrom 1profit j * chrom j alpha* (weight contain) ifweightcontainj 0公式 2的下半局部即为适应度的惩罚函数，其中参数alpha 1.0。2.2按公式 3计算种群的总体适应度，p o p s i1 z es u m f i t n e s s f i t n ei s s(3)i 0并且按照排序的方法统计出种群中的最大、最小适应度的染色体个体， 分别标记为 maxpop、minpop；步骤 3、选择操作3.1 生成一个随机数 rand_Number，要求0 rand _ Nub

13、er1 ；3.2按照赌轮法选择个体，赌轮法的算法描述如下：int selection( )i=0;/个体的编号sum=0；/局部个体适应度的累加和专业资料整理WORD格式/根据随机数和群体的总适应度确定赌轮的位置wheel-pos=rand_Number*sufitness;while sum<wheel-pos && i<=popsize i=i+1;sum=sum+fitnessi; /fitness 为第 i 个个体的适应度return i-1;/ 选择了个体 i-13.3重复两次操作 3.1、 3.2，生成两个个体作为穿插操作的父代；步骤四、穿插操作4.1根

14、据事先定义好的穿插概率pc，为了确定是否进展穿插操作，那么生成0，1的随机数 pp，假设 pppc，那么进展 4.2 穿插操作，否那么将两个父代保存为下一代的两个个体；4.2随机生成 0 , lchrom1 的整数作为穿插点， 对两个父代个体穿插生成新的两个个体；4.3重复 pop_size/2次 4.1、4.2 便可生成 pop_size个个体组成新的种群；步骤五、变异操作5.1根据事先定义好的变异概率p m，为了确定新种群上的每个个体上的每个基因是否进展变异操作，那么生成0， 1的随机数pp，假设 pppm，那么进展5.2变异操作，否那么基因不变异；5.2基因变异操作为原基因假设为1，那么

15、新基因那么变异为0，假设原基因为 0，那么新基因变异为 0；步骤 6、 演化6.1按步骤 2 的方法计算新种群的个体适应度和总体适应度情况，尤其是找出新种群中最大适应度的个体和最小适应度的个体；6.2假设旧种群的最大个体适应度新种群的最大个体适应度，把旧种群的最大适应度的个体代替新种群中的最小适应度的个体，否那么进展6.3；6.3种群的代数 gen=genm+1，假设genMaxgen，那么完毕种群的演化，否那么转专业资料整理WORD格式到步骤 2。六、遗传算法求解的实现1、遗传算法的主要参数专业资料整理WORD格式#define popsize 80/ 种群的规模专业资料整理WORD格式#d

16、efine pc 0.7/杂交概率专业资料整理WORD格式#define pm 0.1/变异概率专业资料整理WORD格式#define lchrom 50/染色体长度专业资料整理WORD格式#define maxgen 5000/最大进化代数专业资料整理WORD格式double alpha;/计算适应度时使用的惩罚函数系数专业资料整理WORD格式2、数据构造专业资料整理WORD格式（ 1背包信息：/背包问题中物体重量、收益、背包容量int weightlchrom,profitlchrom,contain; 2种群个体构造体struct populationunsigned int chrom

17、lchrom;/染色体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( )专业资料整理WORD格式功能

18、：从文件 knapsack.txt 中读出背包信息物体重量、收益、背包容量 ；参数：无；返回值：返回读取文件信息是否正确；流程图：见图 2。翻开文件否获取文件指针成功是读出物体重量信息读出物体收益信息读出背包容量信息返回图 2、 read_infor( )流程图（ 2 double cal_fit(unsigned int *chr)功能：种群中个体适应度计算；参数： unsigned int *chr 是染色体个体的指针，根据指针所指向的染色体计算个体的适应度；返回值：染色体个体适应度的大小；流程图：见图 3。专业资料整理WORD格式适应度和总重量置0累加计算个体适应度和背包的总重量总重量背

19、包容量是使用惩罚函数对个体适应度进展处理返回个体适应度图 3、函数 cal_fit 的流程图（ 3、void statistics(struct population *pop)功能：群体适应度的最大最小值以及其他信息；参数： struct population *pop 是种群指针，根据指针所指向的种群信息统计群体适应度的信息；返回值：无；流程图：见图 4。（ 4、void report(struct population *pop,int gen)功能：报告种群的适应度信息， 尤其是最大个体适应度、 最大适应度个体的染色体信息；参数： struct population *pop 是种群指

20、针，根据指针所指向的种群报告群体适应度的信息， gen 是表示此种群所在的演化代数返回值：无；流程图：见图 5。专业资料整理WORD格式最大最小总适应度都置为首个体的适应度计数器 i=1i<lchrom-1返回是总适应度 =总适应度 +个体 i 的适应度I 的适应度I 的适应度 <最大适应度最小适应度专业资料整理WORD格式置最大适应度的编号为 i置最小适应度的编号为 i专业资料整理WORD格式i=i+1图 4、函数 statistics 的流程图输出种群的代数 gen输出最大适应度个体的染色体信息 chrom输出最大个体适应度maxfitness图 5、函数 report 的流程

21、图专业资料整理WORD格式（ 5、void initpop( )功能：生成初始种群；参数：无；返回值：无；流程图：见图 6。个体计数器 i=0否i<pop_size"返回是随机生成个体i 染色体计算生成个体的适应度否假设背包不超重是承受个体， i=i+1图 6、函数 initpop 流程图（ 6、int execise(double probability)功能：概率选择试验，以概率probability 做随机试验，判断是否进展穿插或变异操作；参数： double probability 为穿插概率或变异概率返回值：试验是否成功，0 代表不试验成功，将不做穿插或者变异操作，1

22、 代表试验成功，即进展穿插或者变异操作；流程图：见图 7。专业资料整理WORD格式生成 0，1之间的小数 pp是否若 pp< probability返回实验成功 1返回实验不成功 0图 7、函数 execise的流程图（ 7、int selection(int pop)功能：在父代种群中选择个体，规那么为适应度越大的个体被选择的概率越大；参数： int pop 为父代种群；返回值：父体中被选择的个体i；流程图：见图 8。专业资料整理WORD格式i 个位置进展穿插，生成两个新个体；个体编号 i=0，局部适应度之和 partsum=0产生随机数 rand_Number计算赌轮所在位置whee

23、l_pospartsum<wheel-pos&& i<=popsize""Partsum=partsum+个体 i 的适应度个体计数器 i=i+1返回被选择的个体i-1图 8、函数 selection 的流程图（ 8、int crossover(unsigned int *parent1,unsigned int *parent2,int i)功能：两个父代个体在染色体的第参数： unsigned int *parent1,unsigned int *parent2分别为两个父代染色体指针，指针指向父代个体的染色体，i 为新种群的个体编号；返回值

24、：穿插是否成功；流程图：见图 9。专业资料整理WORD格式概率选择试验否成功是随机生成穿插位置cross_pos两个父代个体按照交叉位置进展穿插，生成新的两个个体保存两个父体成为新种群中的个体图 9、函数 crossover的流程图（ 9、int mutation(unsigned int alleles)功能：根据变异概率进展变异操作；参数： unsigned int alleles是染色体上的基因型，在这里就是0 或 1 的取值；返回值：变异后的基因型；流程图：见图 10。否概率选择试验成功是进展变异返回变异或者原值专业资料整理WORD格式图 10、函数 mutation 的流程图专业资料

25、整理WORD格式（ 10、void generation()功能：综合选择、穿插、变异等操作，生成新的种群；参数：无；返回值：无；流程图：见图 11。置个体编号 i=0i<pop_size"是调用 selection 生成两生成新的种群完毕个父体调用 crossover，穿插生成两个新个体对每个个体的基因调用 mutation 进展变异置个体编号 i=i+2图 11、函数 generation的流程图（ 11、void main( )功能：遗传算法的主函数；参数：无；返回值：无；流程图：见图 11。专业资料整理WORD格式调用 read_infor，读入背包信息置演化代数 ge

26、n=0调用 initpop( ) 生成初始种群调用 statistics ( )统计种群的适应度Gen<Maxgen"是调用 generation()调用 report( )，生成新种群输出结果信息调用 statistics ( )统计种群的适应度新种群的最大适应度 <旧种群的是复制旧种群的最大适应度个体到新种群中最小个体置演化代数 gen=gen+1专业资料整理WORD格式图 12、主函数 main 的流程图专业资料整理WORD格式七、成果说明1、程序开发环境开发环境： Visual C+6.0 (把 Fortran 程序改为 VC)操作系统： Windows 2003

27、 Professional2、程序性能比照运行时间与加速比如表1 所示进程数 p个124运行时间 t秒129s78s38s加速比 s1.653.38表 1、运行时间与加速比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，30，45，30，60，50，20 ，65， 20，25，30，10，20，25，15，10，10 ，10

28、，4， 4， 2， 1 Profit=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，如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大 "传统的算法动态规划、递归回溯法和贪心算法所得结果：总价值为 3077

29、 ,总重量为 999。2001 年X铃，X钹教授在计算机学报上发表的"佳点集遗传算法"所得结果总价值为 3103,总重量为 1000。我们算法所得结果：总价值为 3103,总重量为 1000。专业资料整理WORD格式我们所求得最优解的个体分配情况为：11010101111011011011011111110100001010011000001000算法最大迭代次数总价值为总重量为传统的算法4003077999佳点集算法7031031000遗传算法7531031000八、收获、体会和课题展望在本课题中，我们研究了如何用遗传算法求解组合优化问题中的背包问题。我们可以看出在求解背

30、包问题上显示了超出想象、良好的搜索能力， 它具有收敛快、搜索速度快的特点， 在试验中取得了比动态规划、递归回溯法和贪心法等更好的求解效果。然而在一般情况下， 使用根本遗传算法解决背包问题时，得到问题的近似解也不能满足逼近最优解的要求。 如何改进根本遗传算法使它所求得的解逼近最优解，成为我们当前亟待解决的问题， 也是我们将来的课题中所要研究的重要问题。/ knapsack.cpp : Defines the entry point for the console application./#include "stdafx.h"#include <AfxWin.h>

31、#include <stdlib.h>#include <math.h>#include <time.h>#include <conio.h>#include <stdio.h>/ 重要常量参数#define popsize 200/ 种群的规模#define pc 0.618/杂交概率#define pm 0.03/ 变异概率#define lchrom 50/ 染色体长度#define maxgen 1000/最大进化代数专业资料整理WORD格式struct population专业资料整理WORD格式unsigned int c

32、hromlchrom; double weight;/染色体/背包重量专业资料整理WORD格式double fitness;/ 适应度专业资料整理WORD格式unsigned int parent1,parent2,cross;/双亲、穿插点;/新生代种群、父代种群struct population oldpoppopsize,newpoppopsize;/背包问题中物体重量、收益、背包容量int weightlchrom,profitlchrom,contain;/种群的总适应度、最小、最大、平均适应度double sumfitness,minfitness,maxfitness,avgfi

33、tness;/计算适应度时使用的惩罚函数系数double alpha;/一个种群中最大和最小适应度的个体intminpop,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;j<lchrom;j+)f

34、scanf(fp,"%d",&profitj);/读入物体重量信息for (j=0;j<lchrom;j+)专业资料整理WORD格式fscanf(fp,"%d",&weightj);/读入背包容量fscanf(fp,"%d",&contain);fclose(fp);/根据计算的个体重量,判断此个体是否该留在群体中double cal_weight(unsigned int *chr)int j;double pop_weight;/ 背包重量pop_weight=0;for (j=0;j<lchr

35、om;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=0;j<lchrom;j+)pop_profit=pop_profit+(*chr)*profitj;/ pop_weight=pop_weight+(*chr)*weightj; chr+;return pop_profit;专业资料整理

36、WORD格式/*群体适应度的最大最小值以及其他信息*/void statistics(struct population *pop)int i;double tmp_fit;sumfitness=pop0.fitness;minfitness=pop0.fitness;minpop=0;maxfitness=pop0.fitness;maxpop=0;for (i=1;i<popsize;i+)/计算种群的总适应度sumfitness=sumfitness+popi.fitness;tmp_fit=popi.fitness;/选择种群中最大适应度的个体if (tmp_fit>max

37、fitness)&&(int)(tmp_fit*10)%10=0)maxfitness=popi.fitness;maxpop=i;/选择种群中最小适应度的个体if (tmp_fit<minfitness)minfitness=popi.fitness;minpop=i;/计算平均适应度avgfitness=sumfitness/(float)popsize;/ printf("nthe max pop = %d;",maxpop);/ printf("nthe min pop = %d;",minpop);/ printf(&qu

38、ot;nthe sumfitness = %fn",sumfitness);/报告种群信息void report(struct population *pop,int gen)int j;int pop_weight=0;专业资料整理WORD格式printf("the generation is %d.n",gen); /输出种群的代数/输出种群中最大适应度个体的染色体信息printf("The population's chrom is:n");for (j=0;j<lchrom;j+)if (j%5=0) printf(&qu

39、ot; "); printf("%1d",popmaxpop.chromj);/输出群体中最大适应度printf("nThe population's max fitness is %d.",(int)popmaxpop.fitness); printf("nThe knapsack weight is %d.nn",(int)popmaxpop.weight);/*生成初始种群*/void initpop()int i,j,ispop;double tmpWeight;/ 变量用于判断是否为满足条件的个体ispop

40、=false;/ 生成 popsize 个种群个体for(i=0;i<popsize;i+)while (!ispop)for(j=0;j<lchrom;j+)oldpopi.chromj=rand()%2;/随机生成个体的染色体oldpopi.parent1=0;/双亲oldpopi.parent2=0;oldpopi.cross=0;/穿插点/选择重量小于背包容量的个体,即满足条件tmpWeight=cal_weight(oldpopi.chrom);if (tmpWeight<=contain)oldpopi.fitness=cal_fit(oldpopi.chrom)

41、;oldpopi.weight=tmpWeight;oldpopi.parent1=0;专业资料整理WORD格式oldpopi.parent2=0;oldpopi.cross=0;ispop=true;/ 此个体可以参加到种群中ispop=false;/*遗传操作*/概率选择试验int execise(double probability)double pp;/如果生成随机数大于相应的概率那么返回真，否那么试验不成功pp=(double)(rand()%20001/20000.0);if (pp<=probability) return 1;return 0;/ 选择进展穿插操作的个体i

42、nt 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=parent+1; while (partsum<wheel_pos && parent<popsize); return parent-1;/*

43、穿插操作*/int crossover(unsigned int *parent1,unsigned int *parent2,int i)专业资料整理WORD格式int j,cross_pos;if (execise(pc)/生成穿插位置0,1,.(lchrom-2)cross_pos=rand()%(lchrom-1);else cross_pos=lchrom-1;for (j=0;j<=cross_pos;j+)/保存复制；/包括在概率选择不成功时，父体完全保存 newpopi.chromj=parent1j;for(j=cross_pos+1;j<=(lchrom-1);j+)/从穿插点开场穿插newpopi.chromj=parent2j;/记录穿插位置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