遗传算法解决多维背包问题（java代码）

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Random; public class Population implements GA_Param,Cloneable{ private List<Chromosome> chromosomeList; private int[] curObjValueArray; private int[] curFitnessArray; private int pop_size; private List<Integer> bestObjValueList; private Chromosome bestChromesome; /** * Constructor. * @param size: The size of the population. */ public Population(int size){ pop_size=size; chromosomeList=new ArrayList<Chromosome>(pop_size); curObjValueArray=new int[pop_size]; curFitnessArray=new int[pop_size]; bestObjValueList=new ArrayList<Integer>(MAX_ITER); bestChromesome=new Chromosome(CHROM_LENGTH); for(int i=0;i<CHROM_LENGTH;++i){ learnChance[i]=1.0; } for(int i=0;i<pop_size;++i){ chromosomeList.add(new Chromosome(CHROM_LENGTH)); } } /** * Population Deep clone!!! */ public Population clone(){ Population p = null; try{ p = (Population)super.clone(); List<Chromosome> list=new ArrayList<Chromosome>(pop_size); for(Chromosome elem:p.chromosomeList){ list.add((Chromosome) elem.clone()); } p.chromosomeList=list; p.curFitnessArray=p.curFitnessArray.clone(); p.curObjValueArray=p.curObjValueArray.clone(); }catch(CloneNotSupportedException e) { e.printStackTrace(); } return p; } /** * Randomly setting the chromosome of the population. */ public void randomPop(){ for(Chromosome elem:chromosomeList){ elem.randomSetGene(); } } /** * Set primary population. */ public void setPrimaryPop(){ int[] primaryGeneArray=new int[CHROM_LENGTH]; for(int col=0;col<CHROM_LENGTH;++col){ primaryGeneArray[col]=1; } for(Chromosome elem:chromosomeList){ elem.setPrimaryGene(primaryGeneArray); } } /** * Set primary population. * @param gene: Ready gene array. */ public void setPrimaryPop(int[] gene){ for(Chromosome elem:chromosomeList){ elem.setPrimaryGene(gene); } } /** * Repair the individual. * @param elem: Chromosome individual. */ public static void repair(Chromosome elem){ int row_weight=0; int[] gene=elem.getGene(); // Calculate each chromosome's attribute for(int row=0;row<ATTRIBUTE_ARRAY.length;++row){ for(int j=0;j<CHROM_LENGTH;++j){ if(gene[j]==1){ row_weight+=ATTRIBUTE_ARRAY[row][j]; } } // If the current total arrtribute is too large if(row_weight>LIMIT_ARRAY[row]){ double[] value_rate=new double[CHROM_LENGTH]; double minIndvalve_rate=1000000; int record=0; // Calculate cost performance. for(int j=0;j<ATTRIBUTE_ARRAY[row].length;++j){ if(gene[j]==1){ if(ATTRIBUTE_ARRAY[row][j]==0){ value_rate[j]=1000000; } else{ value_rate[j]=VALUE_ARRAY[j]/ATTRIBUTE_ARRAY[row][j]; } } else{ value_rate[j]=1000000; } } while(row_weight>LIMIT_ARRAY[row]){ for(int m=0;m<CHROM_LENGTH;++m){ if(value_rate[m]<minIndvalve_rate){ minIndvalve_rate=value_rate[m]; record=m; } } gene[record]=0; value_rate[record]=1000000; minIndvalve_rate=1000000; row_weight-=ATTRIBUTE_ARRAY[row][record]; } } row_weight=0; } } /** * Repair the unreasonable chromosome of the current population. */ public void repair(){ for(Chromosome elem:chromosomeList){ repair(elem); } } /** * Cross genes for the whole chromosome of list. * @param p: List of Chromosome. * @param rate: The probability of cross. * @throws Exception */ public static void cross(List<Chromosome> p,double rate) throws Exception{ Random random=new Random(); for(int i=0;i<p.size()/2;i+=1){ if(random.nextDouble()<rate){ Population.cross(p.get(2*i), p.get(2*i+1)); } } } /** * Swap two parts of two array in index of postion. * @param array1 * @param array2 * @param index1 * @param index2 * @throws Exception */ private static void swapArrays(int[] array1,int[]array2,int index1,int index2) throws Exception{ if(array1.length!=array2.length){ throw new Exception("Array length is inconsistent!"); } int start=Math.min(index1, index2); int end=index1+index2-start; int[] tempArray1=array1.clone(); for(int i=start;i<end;++i){ array1[i]=array2[i]; } for(int i=start;i<end;++i){ array2[i]=tempArray1[i]; } } /** * Exchange genes for a and b two chromosomes. * @param A: chromosome one * @param B: chromosome two * @throws Exception */ public static void cross(Chromosome a,Chromosome b) throws Exception{ int cPoint1=(int) (Math.random()*CHROM_LENGTH); int cPoint2=(int) (Math.random()*CHROM_LENGTH); swapArrays(a.getGene(),b.getGene(),cPoint1,cPoint2); } /** * Mutate chromosomes of the population. * @param p: list of Chromosome. * @param rate: The probability of mutation. */ public static void mutate(List<Chromosome> p,double rate){ for(Chromosome elem:p){ elem.mutate(rate); } } /** * Carrying out cross and mutation on the current population. * @param crossRate * @param mutateRate * @return The population after crossing and mutating. * @throws Exception */ public Population reproduce(double crossRate,double mutateRate) throws Exception{ // deep clone the current population. Population p=this.clone(); Random random=new Random(); // cross. for(int i=0;i<this.chromosomeList.size()/2;i+=1){ if(random.nextDouble()<crossRate){ Population.cross(chromosomeList.get(2*i), chromosomeList.get(2*i+1)); } } // mutate. for(Chromosome elem:this.chromosomeList){ elem.mutate(mutateRate); } return p; } /** * The two populations that current and param population p go on competing. * @param p: prePopulation. */ public List<Chromosome> popCompetition(Population p){ // Repair param population p. p.repair(); double totalFitness=0; // Respectively calculate fitness. p.calcFitness(); this.calcFitness(); // Superposition of total fitness. for(int elem:curFitnessArray){ totalFitness+=elem; } for(int elem:p.curFitnessArray){ totalFitness+=elem; } // Accumulate probability and build wheel. double[] rateAccArray=new double[pop_size*2]; rateAccArray[0]=curFitnessArray[0]/totalFitness; for(int i=1;i<pop_size;++i){ rateAccArray[i]=rateAccArray[i-1]+curFitnessArray[i]/totalFitness; } for(int i=pop_size;i<pop_size*2;++i){ rateAccArray[i]=rateAccArray[i-1]+p.curFitnessArray[i-pop_size]/totalFitness; } // Randomly generate 2*pop_size probabilities and sort. double[] randomRate=new double[pop_size]; for(int i=0;i<pop_size;++i){ randomRate[i]=Math.random(); } Arrays.sort(randomRate); // Start Select. List<Chromosome> newPopList=new ArrayList<>(); int newPopIndex=0,rateAccumulateIndex=0; while(newPopIndex<pop_size){ if(randomRate[newPopIndex]<rateAccArray[rateAccumulateIndex]){ Chromosome c=(Chromosome) p.chromosomeList.get(rateAccumulateIndex%pop_size).clone(); newPopList.add(c); newPopIndex++; } else{ rateAccumulateIndex++; } } return newPopList; } /** * Acquire the objective function value of the chromosome in all population. */ public void calcObjValue(){ for(int i=0;i<chromosomeList.size();++i){ Chromosome elem=chromosomeList.get(i); curObjValueArray[i]=elem.calcObjValue(); } } /** * Sort the whole population according to the each chromosome's fitness. */ private void sortPopulatin(){ Collections.sort(chromosomeList,new Comparator<Chromosome>(){ @Override public int compare(Chromosome o1, Chromosome o2)