遗传算法解决背包问题(java)

网站建设840 更新时间：2025-06-08 11:36:21

2023年8月1日发(作者：)

遗传算法解决背包问题（java）遗传算法解决背包问题（java）遗传算法作为当今⼀个⽐较热门的研究⽅向，在解决最优化问题上有着良好的作⽤。遗传算法利⽤基因编码，对其进⾏⽣成、杂交、变异、选择等操作，产⽣不同的基因序列，使解⼀步⼀步向最优解逼近。背包问题(Knapsack problem)是⼀种组合优化的NP完全问题。问题可以描述为：给定⼀组物品，每种物品都有⾃⼰的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最⾼。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应⽤数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V。已知n个物体的容积及其价值分别为w_i 和c_i （i=1,2, …,n），背包的总容量为v。问：选择哪些物品装⼊背包可以使背包在满⾜容量限制的前提下总价值最⼤？问题可选择的物品有50件，其价值c和重量v分别为c={220,208,198,192,180,180,165,162,160,158,155,130,125122,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,1}w={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,4,4,2,1}背包的总量不能超过1000，求解背包所能装下的最⼤的价值是多少遗传算法解决思路利⽤遗传算法时，可以随机⽣成⼀个长度为50的0-1序列，其中1表⽰对应位置的物品装进背包，0表⽰对应物品不装进背包，需要注意的是，⽣成的序列有可能超过背包的总重量，不满⾜约束条件，此时需要对序列进⾏操作。可⾏的操作有两种，第⼀种是对于不满⾜约束条件的序列进⾏抛弃，第⼆种是对其进⾏贪⼼算⼦变换，具体操作如下：对所有 x_1=1 的物品，按它们的价值密度排序，形成队列b(i)；依次放⼊价值密度最⼤的物品，并判断是否有超出背包限定的范围；如果超出，则将价值密度序列中从这个位置之后的所有商品置0；代码染⾊体类import ;public class Chromosome { public boolean[] gene; private int fitness; private int bag=1000; public int getFitness() { return fitness; } public void setFitness(int fitness) { s = fitness; } /*

构造染⾊体 */ public Chromosome(int n){ if (n<0){ return; } initSize(n); for(int i=0;i=0.5; } getFitness(); } public Chromosome(){ } public void initSize(int n){ if (n<0){ return; } =new boolean[n]; } /*

染⾊体变异 */ public void mutation(int size,double rate){ Random random=new Random(); for(int i=0;i population=new ArrayList();//存放所有的种群基因 private int popSize; //种群规模N private int chromoLength;//每条染⾊体数⽬m； private double mutationRate=0.01;//基因突变概率pm private double crossoverRate=0.6;//交叉概率pc private int bagMax=1000; private int generation;//种群代数t private int iterNum=10000;//最⼤迭代次数 // private int stepmax=3;//最长步长 private int [] charge={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,1}; private int [] 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,4,4,2,1}; private double[] density=new double[50]; private Chromosome nowGenome; private Chromosome bestFit; //最好适应度对应的染⾊体 private Chromosome iterBestFit;//全局最优染⾊体 private double bestFitness;//种群最⼤适应度 private double worstFitness;//种群最坏适应度 private double averageFitness; private double x1; private double x2; private double y=0; public Chromosome getNowGenome() { return nowGenome; } public void setNowGenome(Chromosome nowGenome) { ome = nowGenome; } public Chromosome getIterBestFit() { return iterBestFit; } public void setIterBestFit(Chromosome iterBestFit) { stFit = iterBestFit; } public Chromosome getBestFit() { return bestFit; } public void setBestFit(Chromosome bestFit) { t = bestFit; } public double getBestFitness() { return bestFitness; } public void setBestFitness(double bestFitness) { tness = bestFitness; tness = bestFitness; } public double getWorstFitness() { return worstFitness; } public void setWorstFitness(double worstFitness) { itness = worstFitness; } public double getTotalFitness() { return totalFitness; } public void setTotalFitness(double totalFitness) { itness = totalFitness; } private double totalFitness;//种群总适应度 private Random random=new Random(); public int sumCharge(){ int sumone=0; for(int i=0;i<;i++){ sumone+=charge[i]; } return sumone; } public int sumWeight(){ int sumtwo=0; for(int i=0;i<;i++){ sumtwo+=weight[i]; } return sumtwo; } //构造Getting⽅法 public GeneticAlgorith(int popSize){ e=popSize; } /*

初始化种群 */ public void init(){ for(int i=0;i<;i++){ density[i]=charge[i]/weight[i]; } for(int i=0;i

计算种群适应度 */ */ public void caculteFitness(){ bestFitness=(0).getFitness(); worstFitness=(0).getFitness(); totalFitness=0; for (Chromosome g:population) { //changeGene(g); setNowGenome(g); if(ness()>bestFitness){ setBestFitness(ness()); if(y bestFitness ? bestFitness : averageFitness; } /*

轮盘赌选择算法 */ public Chromosome getChromoRoulette(){ double db=uble(); double randomFitness=db*totalFitness; Chromosome choseOne=null; double sum=0.0; for(int i=0;i<();i++){ choseOne=(i); sum+=ness(); if(sum>=randomFitness){ break; } } return choseOne; } /* clone */ public static Chromosome clone(Chromosome c){ if (c==null||==null){ return null; } Chromosome copy=new Chromosome(); ze(50); for (int i=0;i<;i++){ [i]=[i]; } ness(ness()); return copy; } /*

两点交叉 */ public static List genetic(Chromosome p1,Chromosome p2){ if(p1==null||p2==null){ return null; } if(==null||==null){ return null; } if(!=){ return null; } Chromosome c1=clone(p1); Chromosome c2=clone(p2); int size=; int a=(int)(()*size)%size; int b=(int)(()*size)%size; int min=a>b?b:a; int max=a>b?a:b; if(max-min>15){ max=min+15; }//最⼤步长为10 for(int i=min;i listNew=new ArrayList(); (c1); (c2); return listNew; } /*

贪⼼变换算⼦ */ public void changeGene(Chromosome c){ int flag=0; int fitnessNow=0; int weightNow=0; Map map=new TreeMap(); for(int i=0;i<;i++){ if([i]==true){ (i,density[i]); } } Comparator<> valueComparator = new Comparator<>() { @Override public int compare( o1, o2) { return ue().compareTo(ue()); } }; List<> list=new ArrayList<>(et()); (list,valueComparator); for ( entry:list) { if(weightNow+weight[()]<=bagMax){ //if(flag==0){ fitnessNow+=charge[()]; weightNow+=weight[()]; weightNow+=weight[()]; } else{ //flag=1; [()]=false; } /* fitnessNow+=charge[()]; weightNow+=weight[()]; if(weightNow<=bagMax){ ness(fitnessNow); } else{ ness(0); } */ ness(fitnessNow);

} } /*

进化算法 */ public void evolve() { List childrenGenome = new ArrayList(); for (int j = 0; j < popSize / 2; j++) { Chromosome g1 = getChromoRoulette(); Chromosome g2 = getChromoRoulette(); double r = uble(); if (r <= crossoverRate) { List children = genetic(g1, g2); if (children != null) { for (Chromosome g : children) { changeGene(g); (g); on(50, mutationRate); changeGene(g); (g); } } } (g1); (g2); } List temGen = new ArrayList(); (); for (int i = 0; i < popSize*0.2; i++) { int max = 0; for (Chromosome tempG : childrenGenome) { if (ness() > max) { max = ness(); setBestFit(tempG); } } (getBestFit()); (getBestFit()); setBestFit(null); } population = childrenGenome; caculteFitness(); while (() < popSize) { Chromosome tp1 = getChromoRoulette(); (tp1); } /* while (()

遗传算法GA流程 */ public void geneticAlgorithProcess(){ generation=1; init(); while(generation