遗传算法求解背包问题.doc

开始初始化调用保证放入背包物品体积和不超过背包容量函数达到算法终止条件？结束是选择算子否达到种群大小？将选择得到的两条染色体，进行杂交得到一条新的染色体，调用保证放入背包物品体积和不超过背包容量函数杂交从原种群中选择连续的几个染色体（随机），在选出来的染色体中选择适应度最大的一条染色体，如此进行两次得到两条父代染色体，调用保证放入背包物品体积和不超过背包容量函数否变异变异逐条考察染色体，判断是否要进行变异是得到新种群并赋值给旧种群是遗传算法的过程：初始化：将计划装入背包的每个物品看成一个二进制串的一位，为1表示放入该物品，为0表示不放入该物品。初始种群的产生：初始化前对放入背包物品数的一个预测（背包容积/物品最大体积），接下来只要在种群每条染色体中保证有（背包容积/物品最大体积）个为1的位初始化就完成了。选择：选择进行杂交的父代染色体，被选中的父代染色体总是若干个染色体中最优（适应度最高）的，来保证向优化的方向发展。详细的选择方法：随机产生2个数：Chrom_Cross_From,Chrom_Cross_To,当然得采用一定的手段来保证前者比后者小。从Chrom_Cross_From到Chrom_Cross_To这Chrom_Cross_To-Chrom_Cross_From+1条染色体中选择最优（适应度最大）的染色体作为父代之一。需要进行两次选择得到杂交的两条父代染色体。这样做可以保证算法不会过早收敛。函数实现：IndividualSelect(intChromSize,IndividualPop[]){intNum_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=newIndividual[Num_Selected];for(i=0;i<Num_Selected;i++)Chrom_Selected[i].chrom=newint[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);returnChrom_Selected[0];}杂交：将两次选择得到的父代染色体进行杂交得到一条新的染色体，作为较新种群（并非新的种群）的一条染色体，杂交直到较新种群的染色体数等于原种群的染色体数。杂交的详细方法：假设选择得到的两条染色体分别为：Pop_Cross1，Pop_Cross2。假设染色体的基因数为ChromSize，从0—ChromSize-1逐个考察染色体的基因如果rand()%2=0新染色体的当前基因来自父代的第二条染色体，否则来自第一条染色体函数实现：IndividualCross(intchrom1[],intchrom2[],intChromSize){//;;;;;;;;杂交,接受的参数是两条染色体和染色体中基因的数目;;;;;;;//;;;;;;;;返回一条染色体,及该染色体的适应度;;;;;;;;;;;;;;;;;;;;;inti;IndividualChrom_Return;Chrom_Return.chrom=newint[ChromSize];//;;;;;随机数为基数,当前基因来自第二条染色体,偶数则来自第一条染色体;;;;;;for(i=0;i<ChromSize;i++){if(rand()%2==1)Chrom_Return.chrom[i]=chrom2[i];elseChrom_Return.chrom[i]=chrom1[i];}Chrom_Return.fitness=Fitness(Chr