NSGA2 QMEA java源代码

package algo.QMEA; import util.Knapsack; import util.Qubit; import util.WriteFile; import java.util.ArrayList; import java.util.Random; /** * 算法实现类 */ public class QMEA { final static boolean DEBUG = false;// debug模式 private int popSize;// 种群规模 private int numItem;// 物件数量 private int maxGen;// 最大进化代数 private int numKnapsack;// 背包数 private ArrayList<Knapsack> knapsackList;// 背包列表 private int gen;// 当前进化代数 private ArrayList<Chromsome> popList;// 当代种群 private ArrayList<Chromsome> prePopList;// 上一代种群 /* 构造函数 */ public QMEA(int popSize, int numItem, int numKnapsack, int maxGen, ArrayList<Knapsack> knapsackList) { this.popSize = popSize; this.numItem = numItem; this.numKnapsack = numKnapsack; this.maxGen = maxGen; this.gen = 0; this.knapsackList = knapsackList; this.popList = new ArrayList<Chromsome>(); for (int i = 0; i < this.popSize; i++) { Chromsome chromsome = new Chromsome(numItem, numKnapsack); popList.add(chromsome); } this.prePopList = new ArrayList<Chromsome>(); for (int i = 0; i < this.popSize; i++) { Chromsome chromsome = new Chromsome(numItem, numKnapsack); prePopList.add(chromsome); } } /* * 初始化个体中的量子染色体 */ public void initPopulation() { for (int i = 0; i < popSize; i++) { for (int j = 0; j < numItem; j++) { popList.get(i).quantumChrom[j] = new Qubit(1 / Math.sqrt(2), 1 / Math.sqrt(2)); prePopList.get(i).quantumChrom[j] = new Qubit(); } } } /* * 观察染色体得到状态 */ public void observPopulation() { Random random = new Random(); for (int i = 0; i < popSize; i++) { for (int j = 0; j < numItem; j++) { // 产生一个[0,1]范围内的随机数，如果该随机数大于相应qubit的|0>状态的概率幅的平方，则观察结果为1，否则为0 if (random.nextDouble() > Math.pow( popList.get(i).quantumChrom[j].getZeroAmplitude(), 2)) { popList.get(i).binChrom[j] = 1; } else { popList.get(i).binChrom[j] = 0; } } } } /* * 计算目前背包的重量，每个背包一个重量 */ public void calWeight() { for (int i = 0; i < popSize; i++) { // 对种群中的所有个体依次计算其权重数组 double[] weight = new double[numKnapsack];// 用于暂时保存背包的重量 for (int j = 0; j < numKnapsack; j++) { double tempWeight = 0.0; for (int k = 0; k < numItem; k++) { // 计算一个目标对应的权重值 tempWeight += popList.get(i).binChrom[k] * knapsackList.get(j).weight[k]; } weight[j] = tempWeight; } popList.get(i).setWeight(weight);// 将权重数组保存 } } /* * 计算目前每个背包的适应度 */ public void calFitness() { for (int i = 0; i < popSize; i++) { // 对种群中的所有个体依次计算其适应度值数组 double[] fitness = new double[numKnapsack];// 零时变量，用于暂时保存个体的适应度值数组 for (int j = 0; j < numKnapsack; j++) { // 同一个个体，一个目标（背包）一个适应度值，依目标逐次计算 double tempFitness = 0.0; for (int k = 0; k < numItem; k++) { // 计算一个目标对应的适应度值 tempFitness += popList.get(i).binChrom[k] * knapsackList.get(j).profit[k]; } fitness[j] = tempFitness; } popList.get(i).setFitness(fitness);// 将适应度值数组保存 } } /* * 将当代种群的相关数据复制到prePopList中，供下次迭代时使用 */ public void copyPopListToPrePopList() { for (int i = 0; i < popSize; i++) { prePopList.set(i, popList.get(i)); } } /* * 对违反背包约束条件的个体进行处理 随机修复 */ public void randomRepair() { Random random = new Random(); boolean knapsack_overfilled = false;// @knapsack_overfilled // false表示个体的权重和没有超过背包容量 Chromsome repair = new Chromsome(numItem, numKnapsack);// 用于保存修复过程中的个体 int temp = 0;// 要修复的物件对应的下标 // 对种群进行修复，并按照概率pr决定是否要用修复的个体代替原个体 for (int i = 0; i < popSize; i++) { repair = popList.get(i); //判断是否有权重超出某个背包的容量 for (int j = 0; j < numKnapsack; j++) { if (repair.weight[j] > knapsackList.get(j).capacity) { knapsack_overfilled = true; } } if (knapsack_overfilled) { while (knapsack_overfilled) {// 如果有权重超出某个背包的容量，随机拿走一个物件，直到满足所有背包的容量约束为止 temp = random.nextInt(numItem); boolean loopCondition = true; while (loopCondition) {// 随机生成一个随机数作为下标，如果对应的物件原本就不在背包中，则重新生成一个，否则将对应的物件从背包中移走，退出循环 if (repair.binChrom[temp] == 0) { temp = random.nextInt(numItem); } else { repair.binChrom[temp] = 0; loopCondition = false; } } repair.binChrom[temp] = 0;// 随机拿走一个物件 double[] weight = new double[numKnapsack]; double[] fitness = new double[numKnapsack]; for (int h = 0; h < numKnapsack; h++) {// 拿走物件后修改个体对应的权重数组和适应度值数组 double tempWeight = 0.0; double tempProfit = 0.0; for (int k = 0; k < numItem; k++) { tempWeight += knapsackList.get(h).weight[k] * repair.binChrom[k]; tempProfit += knapsackList.get(h).profit[k] * repair.binChrom[k]; } weight[h] = tempWeight; fitness[h] = tempProfit; } repair.setWeight(weight); repair.setFitness(fitness); int index = 0; for (int h = 0; h < numKnapsack; h++) {// 再次判断是否有权重超出某个背包的容量，若没有，则将knapsack_overfilled赋值为false退出循环 if (repair.weight[h] > knapsackList.get(h).capacity) { index += 1; } } if (index == 0) { knapsack_overfilled = false; } } //通过上面拿走一些物件满足各个背包的容量约束后，可能会存在将一个权重比较小的物件再次加入背包也不会超过所有背包容量的情况，针对这种可能性随机选取一个物件对其进行尝试以提高解的质量 while (knapsack_overfilled == false) { temp = random.nextInt(numItem); boolean loopCondition = true; while (loopCondition) {// 随机生成一个随机数作为下标，如果对应的物件已经在背包中，则重新生成一个，否则将对应的物件加入背包中，退出循环 if (repair.binChrom[temp] == 1) { temp = random.nextInt(numItem); } else { repair.binChrom[temp] = 1; loopCondition = false; } } repair.binChrom[temp] = 1; double[] weight = new double[numKnapsack]; double[] fitness = new double[numKnapsack]; for (int h = 0; h < numKnapsack; h++) {// 加入物件后修改个体对应的权重数组和适应度值数组 double tempWeight = 0.0; double tempProfit = 0.0; for (int k = 0; k < numItem; k++) { tempWeight += knapsackList.get(h).weight[k] * repair.binChrom[k]; tempProfit += knapsackList.get(h).profit[k] * repair.binChrom[k]; } weight[h] = tempWeight; fitness[h] = tempProfit; } repair.setWeight(weight); repair.setFitness(fitness); for (int h = 0; h < numKnapsack; h++) {// 再次判断是否有权重超出某个背包的容量，若超出则将knapsack_overfilled赋值为true退出循环 if (repair.weight[h] > knapsackList.get(h).capacity) { knapsack_overfilled = true; } } } repair.binChrom[temp] = 0;// 把最后一个加入的物件从背包中拿走 double[] weight = new double[numKnapsack]; double[] fitness = new double[numKnapsack]; for (int h = 0; h < numKnapsack; h++) {// 拿走物件后修改个体对应的权重数组和适应度值数组 double tempWeight = 0.0; double tempProfit = 0.0; for (int k = 0; k < numItem; k++) { tempWeight += knapsackList.get(h).weight[k] * repair.binChrom[k]; tempProfit += knapsackList.get(h).profit[k] * repair.binChrom[k]; } weight[h] = tempWeight; fitness[h] = tempProfit; } repair.setWeight(weight); repair.setFitness(fitness); popList.set(i, repair); } } } /*