遗传算法解决背包问题（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 java.util.Random;
public class Chromosome {
public boolean[] gene;
private int fitness;
private int bag=1000;
public int getFitness() {
return fitness;
}
public void setFitness(int fitness) {
this.fitness = fitness;
}
/*
构造染色体
*/
public Chromosome(int n){
if (n<0){
return;
}
initSize(n);
for(int i=0;i<n;i++){
gene[i]=Math.random()>=0.5;
}
getFitness();
}
public Chromosome(){
}
public void initSize(int n){
if (n<0){
return;
}
this.gene=new boolean[n];
}
/*
染色体变异
*/
public void mutation(int size,double rate){
Random random=new Random();
for(int i=0;i<size;i++){
if(random.nextDouble()<rate){
boolean t=gene[i];
t=!t;
gene[i]=t;
}
}
}
}
遗传算法
import java.util.*;
public class GeneticAlgorith {
public List<Chromosome> population=new ArrayList<Chromosome>();//存放所有的种群基因
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) {
this.nowGenome = nowGenome;
}
public Chromosome getIterBestFit() {
return iterBestFit;
}
public void setIterBestFit(Chromosome iterBestFit) {
this.iterBestFit = iterBestFit;
}
public Chromosome getBestFit() {
return bestFit;
}
public void setBestFit(Chromosome bestFit) {
this.bestFit = bestFit;
}
public double getBestFitness() {
return bestFitness;
}
public void setBestFitness(double bestFitness) {
this.bestFitness = bestFitness;
}
public double getWorstFitness() {
return worstFitness;
}
public void setWorstFitness(double worstFitness) {
this.worstFitness = worstFitness;
}
public double getTotalFitness() {
return totalFitness;
}
public void setTotalFitness(double totalFitness) {
this.totalFitness = totalFitness;
}
private double totalFitness;//种群总适应度
private Random random=new Random();
public int sumCharge(){
int sumone=0;
for(int i=0;i<charge.length;i++){
sumone+=charge[i];
}
return sumone;
}
public int sumWeight(){
int sumtwo=0;
for(int i=0;i<weight.length;i++){
sumtwo+=weight[i];
}
return sumtwo;
}
//构造Getting方法
public GeneticAlgorith(int popSize){
this.popSize=popSize;
}
/*
初始化种群
*/
public void init(){
for(int i=0;i<charge.length;i++){
density[i]=charge[i]/weight[i];
}
for(int i=0;i<popSize;i++){
Chromosome g=new Chromosome(50);
changeGene(g);
population.add(g);
}
caculteFitness();
}
/*
计算种群适应度
*/
public void caculteFitness(){
bestFitness=population.get(0).getFitness();
worstFitness=population.get(0).getFitness();
totalFitness=0;
for (Chromosome g:population) {
//changeGene(g);
setNowGenome(g);
if(g.getFitness()>bestFitness){
setBestFitness(g.getFitness());
if(y<bestFitness){
y=g.getFitness();
}
setIterBestFit(g);
}
if(g.getFitness()<worstFitness){
worstFitness=g.getFitness();
}
totalFitness+=g.getFitness();
}
averageFitness = totalFitness / popSize;
//因为精度问题导致的平均值大于最好值，将平均值设置成最好值
averageFitness = averageFitness > bestFitness ? bestFitness : averageFitness;
}
/*
轮盘赌选择算法
*/
public Chromosome getChromoRoulette(){
double db=random.nextDouble();
double randomFitness=db*totalFitness;
Chromosome choseOne=null;
double sum=0.0;
for(int i=0;i<population.size();i++){
choseOne=population.get(i);
sum+=choseOne.getFitness();
if(sum>=randomFitness){
break;
}
}
return choseOne;
}
/*
clone
*/
public static Chromosome clone(Chromosome c){
if (c==null||c.gene==null){
return null;
}
Chromosome copy=new Chromosome();
copy.initSize(50);
for (int i=0;i<c.gene.length;i++){
copy.gene[i]=c.gene[i];
}
copy.setFitness(c.getFitness());
return copy;
}
/*
两点交叉
*/
public static List<Chromosome> genetic(Chromosome p1,Chromosome p2){
if(p1==null||p2==null){
return null;
}
if(p1.gene==null||p2.gene==null){
return null;
}
if(p1.gene.length!=p2.gene.length){
return null;
}
Chromosome c1=clone(p1);
Chromosome c2=clone(p2);
int size=c1.gene.length;
int a=(int)(Math.random()*size)%size;
int b=(int)(Math.random()*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<max;i++){
boolean temp=c1.gene[i];
c1.gene[i]=c2.gene[i];
c2.gene[i]=temp;
}
c1.setFitness(c1.getFitness());
c2.setFitness(c2.getFitness());
List<Chromosome> listNew=new ArrayList<Chromosome>();
listNew.add(c1);
listNew.add(c2);
return listNew;
}
/*
贪心变换算子
*/
public void changeGene(Chromosome c){
int flag=0;
int fitnessNow=0;
int weightNow=0;
Map<Integer,Double> map=new TreeMap<Integer, Double>();
for(int i=0;i<c.gene.length;i++){
if(c.gene[i]==true){
map.put(i,density[i]);
}
}
Comparator<Map.Entry<Integer, Double>> valueComparator = new Comparator<Map.Entry<Integer, Double>>() {
@Override
public int compare(Map.Entry<Integer, Double> o1, Map.Entry<Integer, Double> o2) {
return o2.getValue().compareTo(o1.getValue());
}
};
List<Map.Entry<Integer,Double>> list=new ArrayList<Map.Entry<Integer, Double>>(map.entrySet());
Collections.sort(list,valueComparator);
for (Map.Entry<Integer,Double> entry:list) {
if(weightNow+weight[entry.getKey()]<=bagMax){
//if(flag==0){
fitnessNow+=charge[entry.getKey()];
weightNow+=weight[entry.getKey()];
}
else{
//flag=1;
c.gene[entry.getKey()]=false;
}
/*
fitnessNow+=charge[entry.getKey()];
weightNow+=weight[entry.getKey()];
if(weightNow<=bagMax){
c.setFitness(fitnessNow);
}
else{
c.setFitness(0);
}
*/
c.setFitness(fitnessNow);
}
}
/*
进化算法
*/
public void evolve() {
List<Chromosome> childrenGenome = new ArrayList<Chromosome>();
for (int j = 0; j < popSize / 2; j++) {
Chromosome g1 = getChromoRoulette();
Chromosome g2 = getChromoRoulette();
double r = random.nextDouble();
if (r <= crossoverRate) {
List<Chromosome> children = genetic(g1, g2);
if (children != null) {
for (Chromosome g : children) {
changeGene(g);
childrenGenome.add(g);
g.mutation(50, mutationRate);
changeGene(g);
childrenGenome.add(g);
}
}
}
childrenGenome.add(g1);
childrenGenome.add(g2);
}
List<Chromosome> temGen = new ArrayList<Chromosome>();
population.clear();
for (int i = 0; i < popSize*0.2; i++) {
int max = 0;
for (Chromosome tempG : childrenGenome) {
if (tempG.getFitness() > max) {
max = tempG.getFitness();
setBestFit(tempG);
}
}
temGen.add(getBestFit());
childrenGenome.remove(getBestFit());
setBestFit(null);
}
population = childrenGenome;
caculteFitness();
while (temGen.size() < popSize) {
Chromosome tp1 = getChromoRoulette();
temGen.add(tp1);
}
/*
while (temGen.size()<popSize){
Chromosome tp1=new Chromosome(50);
temGen.add(tp1);
}
*/
population = temGen;
//重新计算种群适应度
caculteFitness();
}
/*
遗传算法GA流程
*/
public void geneticAlgorithProcess(){
generation=1;
init();
while(generation<iterNum){
evolve();
print();
generation++;
}
}
public void print(){
System.out.println("this is generation "+generation);
System.out.println("the best fitness is "+y);
System.out.println("-----------------------------------------------");
if(generation==iterNum-1){
for(int i=0;i<50;i++){
if(iterBestFit.gene[i]==true){
System.out.printf("1");
}
else{
System.out.printf("0");
}
System.out.printf(" ");
}
System.out.println("");
}
}
}
测试类
public class Test {
public static void main(String[] args) {
GeneticAlgorith g=new GeneticAlgorith(100);
g.geneticAlgorithProcess();
System.out.println(g.sumCharge());
System.out.println(g.sumWeight());
g=null;
}
}
结果
注意
本题存在两个局部最优解，分别为3103和3098，全局最优解为3103，但是当算法收敛到3098时很难再收敛到3103，这并不代表算法本身有问题，若要每次都求解到全局最优解，需要做进一步的改进，这个问题先留在此处。