现代优化计算方法结课作业—多维背包问题

现代优化计算方法结课作业—多维背包问题

现代优化计算方法终于结课了，分数差强人意(个人是不服气的！)。结课作业为多维背包问题，笔者用了基于贪婪算子的遗传算法，效果一般。数据百度云链接如下：
百度云链接 密码：oxwz
下附Java代码

---

package genetic_alogrithms_01;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class GA {
	private int POPsize;//种群大小
	private double Pc;//交叉概率
	private double Pm;//变异概率
	private int Iteration;//迭代次数
	public double Maxvalue;//最大的价值
	private int [] Bestsolution; //最优解数组
	private int[][] Fatherpop; //父代种群
	private int[][] Offspringpop; //子代种群
	private double[] Pa; //累计概率
	private int t; //当前的代数
	private int bestT; //最佳解出现的代数
	private double value[];//价值数组
	private double constraint[][];//约束数组
	private double Fitness[];//适应度
	private int Num;//物品总数目
	private int D;//约束数目
	private double cons[];//约束的数值
	private int[] tags;//背包的顺序数组
	
	//构造函数
	public GA(int POPsize, double Pc, double Pm, int Iteration,int Num, int D) {
		this.POPsize = POPsize;
		this.Pc = Pc;
		this.Pm = Pm;
		this.Iteration = Iteration;
		this.Num = Num;
		this.D = D;
	}
	
	//初始化种群
	public void init(){
		//初始化
		Fatherpop = new int[POPsize][Num];
		Offspringpop = new int[POPsize][Num];
		Bestsolution = new int[Num];
		Fitness = new double[POPsize];
		Pa = new double[POPsize];
		t = 0;
		Maxvalue = 0;
		value = new double[Num];
		constraint = new double[D][Num];
		cons = new double[D];
		bestT = 0;
		tags = new int[Num];
		//初始化最佳解数组，让其全部为1
		for (int i=0;i<Num;i++){
			Bestsolution[i] = 1;
		}
		//随机地对种群中的个体进行编码
		for(int i=0;i<POPsize;i++){
			for(int j=0;j<Num;j++){
				double r = Math.random();
				if(r<0.5){
					Fatherpop[i][j] = 0;
				}else{
					Fatherpop[i][j] = 1;
				}
			}
		}
	}
	
	//读取数据
		public void read_data(String filename) throws IOException{
			init();//初始化种群
			String strbuff;
			@SuppressWarnings("resource")
			BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename))); //读取数据文件
			strbuff = data.readLine();
			String[] s = strbuff.split(" "); //数据之间有空格
			//获取价值，并记录最初的顺序
			for(int j=0;j<Num;j++){
				value[j] = Double.valueOf(s[j]);
				tags[j] = j;
			}
			//获取每个维度的物体的数值
			for(int k=0;k<D;k++){
				strbuff = data.readLine();
				String[] a = strbuff.split(" "); //数据之间有空格
				for(int l=0;l<Num;l++){
				constraint[k][l] = Double.valueOf(a[l]);
			    }
			}
			strbuff = data.readLine();
			String[] b = strbuff.split(" "); //数据之间有空格
			//获取每个维度数值总和的最大值，即背包内的物体某个维度中的数值的总和不能超出的值
			for(int p=0;p<D;p++){
				cons[p] = Double.valueOf(b[p]);
			}
			//冒泡排序，得到价值由低到高的物体的顺序，以便后续修正时候，能基于贪婪的思想来进行修正，即先把价值小的物体丢弃
			double[] va = new double[Num];
			for(int i=0;i<Num;i++){
				va[i] = value[i];
			}
			for(int e=0;e<Num;e++){
				for(int r=e+1;r<Num;r++){
					if(value[e]>value[r]){
						double temp = value[r];
						value[r] = value[e];
						value[e] = temp;
						int tag = tags[e];
						tags[e] = tags[r];
						tags[r] = tag;
					}
				}
			}
			for(int i=0;i<Num;i++){
				value[i] = va[i];
			}
			
		}
		
	//得到一个染色体的各个维度限制的数值
	public double[] getConstraint(int[] chromosome){
		double[] cons = new double[D];
		for(int k=0;k<D;k++){
			cons[k] = 0;
		}
		for(int j=0;j<D;j++){
			for(int i=0;i<Num;i++){
				cons[j] +=  chromosome[i]*constraint[j][i];
			}	
		}
		return cons;
	}
	
	//得到一个染色体的价值
	public double getValue(int[] chromosome){
		double v = 0.0;
		for(int i=0;i<Num;i++){
			v += chromosome[i]*value[i];
		}
		return v;
	}
	
	//得到一个种群适应度数组
	public void getFitness(){
		for(int i=0;i<POPsize;i++){
			Fitness[i] = getValue(Fatherpop[i]);
		}
	}
	
	//得到累积概率
	public void getPa(){
		double Totalfitness = 0.0;
		//得到种群的总适应度
		for(int i=0;i<POPsize;i++){;
			Totalfitness += Fitness[i];
		}
		//得到累积概率
		Pa[0] = Fitness[0]/Totalfitness;
		for(int j=1;j<POPsize;j++){
			Pa[j] = (Fitness[j]/Totalfitness) + Pa[j-1];
		}
	}

	// 复制染色体
	public void copyChromosome(int a,int b){
		for(int i=0;i<Num;i++){
			Offspringpop[a][i] = Fatherpop[b][i];
		}
	}
	
	// 轮盘赌选择
	public void STW(){
		int selectID; //选中的父代染色体编号
		int i ,j;  //i为子代染色体编号
		//轮盘赌选择
		for(i=0;i<POPsize;i++){
			double p = Math.random();
			for(j=0;j<POPsize;j++){
				if(p <= Pa[j]){
					break;
				}
			}
			selectID = j;
			copyChromosome(i,selectID); //把父代选中的染色体复制给子代
		}
	}
	
	// 选择最好的个体
		public void selectBest(){
			Rectify();//修正种群
			double best;
			int bestID = 0;
			// 获得最好个体的适应度
			best = Fitness[0];
			for(int i=0;i<POPsize;i++){
				if(best<Fitness[i]){
					best = Fitness[i];
					bestID = i;
				}
			}
			// 获得出现最好的染色体出现的代数
			if(Maxvalue<best){
				Maxvalue = best;
				bestT = t; 
			}
			// 获得最佳的染色体
			for(int i=0;i<Num;i++){
				Bestsolution[i] = Fatherpop[bestID][i];
			}
		}
		
		//交叉算子
		public void crossover(int a,int b){
			int l, m, n,q;
			//随机得到两处交叉点
			int Rank1 = (int) (Math.random()*Num);
			int Rank2 = (int) (Math.random()*Num);
			//确保Rank2>=Rank1
			while(Rank2<Rank1){
				Rank2 = (int) (Math.random()*Num);
			}
			int[] chro1 = new int[Rank1];
			int[] chro2 = new int[Num-Rank2];
			//进行交叉互换
			for(int i=0;i<Rank1;i++){
				chro1[i] = Offspringpop[a][i];
			};
			for(int j=0;j<Rank1;j++){
				Offspringpop[a][j] = Offspringpop[b][j];
			}
			for(int k=0;k<Rank1;k++){
				Offspringpop[b][k] = chro1[k];
			}
			for(l=0,m=Rank2;l<(Num-Rank2);l++,m++){
				chro2[l] = Offspringpop[b][m];
			};
			for(int j=Rank2;j<Num;j++){
				Offspringpop[b][j] = Offspringpop[a][j];
			}
			for(q=0,n=Rank2;n<Num;n++){
				Offspringpop[a][n] = chro2[q];
			}
		}
		
		//变异
		public void mutation(int a){
			//随机产生变异地点
			int Rank2 = (int) (Math.random()*Num);
			//进行变异,0->1或1->0
			if(Offspringpop[a][Rank2]==0){
				Offspringpop[a][Rank2] = 1;
			}else{
				Offspringpop[a][Rank2] = 0;
			}
		}
		
		//校正种群
		public void Rectify(){
			double[] a;
			int k;
			//基于贪婪的修正，先把价值低的物品拿出
			for(int i=0;i<POPsize;i++){
				a = getConstraint(Fatherpop[i]);
				for(int j=0;j<D;j++){
					for(k=0;k<Num;){
						while(a[j]>cons[j]){
							k++;
							Fatherpop[i][tags[k]] = 0;
							a = getConstraint(Fatherpop[i]);
						}
						break;
			       }	
				}
				k=0;
			}	
			for(int i=0;i<POPsize;i++){
				a = getConstraint(Offspringpop[i]);
				for(int j=0;j<D;j++){
					for(k=0;k<Num;){
						while(a[j]>cons[j]){
							k++;
							Offspringpop[i][tags[k]] = 0;
							a = getConstraint(Offspringpop[i]);
						}
						break;
			       }	
				}
				k=0;
			}	
		}
		
		// 进化（遗传+交叉+变异）
		public void evolution(){
			int i;
			double p;
			selectBest(); //得到最好的路径、最好的长度、出现最好路径的代数
			STW(); //轮盘赌选择父代，获取子代
			for(i=0;i<POPsize;i++){
				p = Math.random();
				// 是否交叉
				if(i==POPsize-1){
					if(p<Pc){
						crossover(i-1,i);
						}
				}else{
				if(p<Pc){
					crossover(i,i+1);
					}
				p = Math.random();
				// 是否变异
				if(p<Pm){
				    mutation(i);
					}
			    p = Math.random();
				if(p<Pm){
					mutation(i+1);
				    }
		     	}
			}
			Rectify();//修正种群
			}
		
		// 遗传算法
		public void ga() throws IOException{
			System.out.println("Start...");
			Rectify();//修正种群
			getFitness(); //得到种群适应度
			getPa(); //得到累积概率
			for(t=0;t<Iteration;t++){
				evolution(); //进化 
				for(int i=0;i<POPsize;i++){
					for(int j=0;j<Num;j++){
						Fatherpop[i][j] = Offspringpop[i][j]; //将上一代子代的信息给下一代的父代，准备下一次进化
					}
				}
			    getFitness(); //得到新一代种群的适应度
			    getPa(); //得到新一代种群的累积概率
			    //迭代一定次数后，为了防止其掉入局部最优解，又在种群中新增随机产生的个体
			    if(t > (int) 0.8*Iteration){
				int rank1 = (int) (Math.random()*POPsize);
				for(int p=0;p<Num;p++){
					double r = Math.random();
					if(r<0.5){
					Fatherpop[rank1][p] = 0;
					}else{
					Fatherpop[rank1][p] = 1;
					}
				}
			 }
			}
			System.out.println("最大价值出现的代数："+bestT);
			System.out.println("最大价值："+Maxvalue);
			System.out.print("最优解：");
			// 打印最佳解
			for(int i=0;i<Num;i++){
				System.out.print(Bestsolution[i]+" "); 
			}
			System.out.println(" ");
			System.out.println(" ");
		}
	
		//主函数
	public static void main(String[] args) throws IOException {
		
		/*
		 * 
		 * 数据的格式要求为txt文件，txt文件里面的格式为：
		 * 第一行为物体的价值，每个物体的价值以一个空格相隔
		 * 第二行到第N-1行为每个物体每个维度的限制值，如第二行为每个物体体积的数值，每个数值以一个空格相隔；第三行为每个物体质量的数值，每个数值以一个空格相隔......
		 * 第N行为每个维度总量的最大值，每个数值以一个空格相隔
		 * 
		 */
		
		
		//构造GA类，并读取数据，调用ga算法
		for(int i=0;i<7;i++){
//			GA g1 = new GA(20,0.2,0.8,60,10,10);
//			g1.read_data("/home/mouye/1.txt");
//			g1.ga();
//			GA g2 = new GA(90,0.2,0.8,300,15,10);
//			g2.read_data("/home/mouye/2.txt");
//			g2.ga();
			GA g3 = new GA(500,0.2,0.8,500,50,5);
			g3.read_data("/home/mouye/3.txt");
			g3.ga();
		}
	}
}

赏

谢谢老板

支付宝

微信