ga.java

遗传算法 JAVA SQL2000

package com;

public class GA {
	public GA(int popSize, int maxGen){
		this.popSize = popSize;
		this.maxGen = maxGen;
		oldpop = new Chrom[popSize];
		newpop = new Chrom[popSize];
		minChrom = new Chrom(lchrom, qNum);
	}
	//统计初始群体的最大(max)、最小(min)、平均(avg)适应度，最佳个体(minChrom)；计算群体总适应度(sumFitness)
	public void initStatistic(){
		oldpop[0] = new Chrom(lchrom, qNum);
		newpop[0] = new Chrom(lchrom, qNum);
		oldpop[0].setFitness(objfunc(oldpop[0]));
		sumFitness = max = min = oldpop[0].getFitness();
		//minChrom = oldpop[0];
		for(int t=0; t<3; t++){
			minChrom.setElement(t, oldpop[0].getElement(t));
		}
		minChrom.setFitness(oldpop[0].getFitness());
		double tempFit;
		for(int n=1; n<popSize; n++){
			oldpop[n]= new Chrom(lchrom, qNum);
			newpop[n] = new Chrom(lchrom, qNum);
			tempFit = objfunc(oldpop[n]);
			oldpop[n].setFitness(tempFit);
			sumFitness += tempFit;
			if(tempFit >= max){
				max = tempFit;
			}
			if(tempFit <= min){
				min = tempFit;
				//minChrom = oldpop[n];
				for(int t=0; t<3; t++){
					minChrom.setElement(t, oldpop[n].getElement(t));
				}
				minChrom.setFitness(oldpop[n].getFitness());
			}
		}
		avg = sumFitness/popSize;
		//newpop = oldpop;
		for(int n=0; n<popSize; n++){
			for(int t=0; t<3; t++){
				newpop[n].setElement(t, oldpop[n].getElement(t));
			}
			newpop[n].setFitness(oldpop[n].getFitness());
		}
	}
	//
	public void initReport(){
		System.out.println("种群大小：" + popSize);
		System.out.println("设定的最大遗传代数：" + maxGen);
		System.out.println("-----------------------------------------");
		System.out.printf("交叉概率：%.4f\n", pcross);
		System.out.printf("编译概率：%.4f\n", pmutation);
		System.out.printf("初始群体中的最大适应度：%.4f\n", max);
		System.out.printf("初始群体的平均适应度：%.4f\n", avg);
		System.out.printf("初始群体中的最小适应度：%.4f\n", min);
		System.out.printf("Initial Population Sum of Fitness = %.4f\n\n", sumFitness);
	}
	//
	public void operate(){
		int gen = 1;
		while(sumFitness>100 && gen<=maxGen){
			generation();
			statistics();
			report(gen);
			gen ++;
			//oldpop = newpop;
			for(int n=0; n<popSize; n++){
				for(int t=0; t<3; t++){
					oldpop[n].setElement(t, newpop[n].getElement(t));
				}
				oldpop[n].setFitness(newpop[n].getFitness());
			}
		}
	}
	//进化函数  选择，交叉，变异
	private void generation(){
		int j = 0;
		do{//挑选交叉配对
			int mate1 = select(), mate2 = select();
			while(mate1 == mate2){
				mate2 = select();
			}
			//两点顺序交叉（OX）
			if(flip(pcross)){
				for(int t=0; t<typeNum; t++){
					//调用用于交叉操作的函数
					crossover(oldpop[mate1].getElement(t), oldpop[mate2].getElement(t), t);
					newpop[j].setElement(t, child1);
					newpop[j+1].setElement(t, child2);
				}
			}
			//变异
			if(flip(pmutation)){
				for(int t=0; t<typeNum; t++){
					newpop[j].setElement(t, mutation(newpop[j].getElement(t), t));
				}
			}
			//子体2
			if(flip(pmutation)){
				for(int t=0; t<typeNum; t++){
					newpop[j+1].setElement(t, mutation(newpop[j+1].getElement(t), t));
				}
			}
			//计算适应度
			double tempFit1 = objfunc(newpop[j]); //计算变异后子个体1的适应度函数值
			double tempFit2 = objfunc(newpop[j+1]); //计算变异后子个体2的适应度函数值
			if(tempFit1 > max){
				//newpop[j] = minChrom;
				for(int t=0; t<3; t++){
					newpop[j].setElement(t, minChrom.getElement(t));
				}
				newpop[j].setFitness(minChrom.getFitness());
			}else{
				newpop[j].setFitness(tempFit1);
			}
			if(tempFit2 > max){
				//newpop[j+1] = minChrom;
				for(int t=0; t<3; t++){
					newpop[j+1].setElement(t, minChrom.getElement(t));
				}
				newpop[j+1].setFitness(minChrom.getFitness());
			}else{
				newpop[j+1].setFitness(tempFit2);
			}
			j += 2;
		}while(j < (popSize-1));
		//newpop[popSize-1] = minChrom;
		for(int t=0; t<3; t++){
			newpop[popSize-1].setElement(t, minChrom.getElement(t));
		}
		newpop[popSize-1].setFitness(minChrom.getFitness());
	}
	//统计最大、最小和累计适应度
	private void statistics(){
		sumFitness = max = min = newpop[0].getFitness();
		if(minChrom.getFitness() >= min){
			//minChrom = newpop[0];
			for(int t=0; t<3; t++){
				minChrom.setElement(t, newpop[0].getElement(t));
			}
			minChrom.setFitness(newpop[0].getFitness());
		}
		double tempFit;
		for(int j=1; j<popSize; j++){
			tempFit = newpop[j].getFitness();
			sumFitness += tempFit;
			if(tempFit >= max){
				max = tempFit;
			}
			if(tempFit <= min){
				min = tempFit;
				if(minChrom.getFitness() >= min){
					//minChrom = newpop[j];
					for(int t=0; t<3; t++){
						minChrom.setElement(t, newpop[j].getElement(t));
					}
					minChrom.setFitness(newpop[j].getFitness());
				}
			}
		}
		avg = sumFitness/popSize; //计算平均适应度
	}
	//
	private void report(int gen){
		System.out.println("目前遗传代数：" + gen);
		System.out.println("-----------------------------------------");
		System.out.printf("交叉概率：%.4f\n", pcross);
		System.out.printf("变异概率：%.4f\n", pmutation);
		System.out.printf("最大适应度：%.4f\n", max);
		System.out.printf("平均适应度：%.4f\n", avg);
		System.out.printf("最小适应度：%.4f\n", min);
		System.out.printf("Sum of Fitness = %.4f\n\n", sumFitness);
	}
	//轮盘赌选择
	private int select(){
		double pick = Math.random()*sumFitness;
		double sum = 0;
		int i = 0;
		for(; sum<pick && i<popSize; i++){
			sum += oldpop[i].getFitness();
		}
		if(i>0) return i-1;
		else return i;
	}
	//交叉
	private void crossover(int[][] parent1, int[][] parent2, int t){
		int[][] temp = new int[180][];
		//判断是否发生交叉操作，pcross为交叉概率
		int jcross1, jcross2;
		child1 = new int[180][2];
		child2 = new int[180][2];
		if(flip(pcross)){
			jcross1 = (int)(Math.random() * 179); //随机产生两个交叉点的位置
			do{
				jcross2 = (int)(Math.random() * 179);
			}while(jcross1 == jcross2);
			if(jcross1 > jcross2){
				int work = jcross1;
				jcross1 = jcross2;
				jcross2 = work;
			}
			//保持交叉点之间附加码不变
			for(int i=0; i<lchrom[t]; i++){//lchrom[qType]为每种题型对应染色体的长度
				if(i>=jcross1 && i<jcross2){
					child1[i] = parent1[i];
					child2[i] = parent2[i];
				}
			}
			//下面设置child1交叉点两边位置的值
			for(int i=0; i<lchrom[t]-jcross2; i++){
				temp[i] = parent2[jcross2+i];
			}
			for(int i=lchrom[t]-jcross2; i<lchrom[t]; i++){
				temp[i] = parent2[i-(lchrom[t]-jcross2)];
			}
			int sub = 0; //sub保存temp中当前已被除去的附加码个数
			for(int k=jcross1; k<jcross2; k++){
				//lchrom[QTYPR]为题型qType对应的染色体长度
				for(int j=0; j<lchrom[t]-sub; j++){
					if(parent1[k][0] == temp[j][0]){
						//将交叉点之间的附加码从temp中去掉
						for(int j1=j; j1<lchrom[t]-sub-1; j1++){
							temp[j1] = temp[j1+1];
						}
					}
				}
				sub++;
			}
			//将temp顺序码中的值依次赋给parent1交叉点两边的位置
			for(int i=0; i<jcross1; i++){ //为jcross1左边赋值
				child1[i] = temp[i];
			}
			int k = 0;
			for(int i=jcross2; i<lchrom[t]; i++){ //为jcross2右边赋值
				child1[i] = temp[jcross1+k];
				k++;
			}
			//下面设置child2交叉点两边位置的值
			for(int i=0; i<lchrom[t]-jcross2; i++){
				temp[i] = parent1[i+jcross2];
			}
			for(int i=lchrom[t]-jcross2; i<lchrom[t]; i++){
				temp[i] = parent1[i-(lchrom[t]-jcross2)];
			}
			sub = 0;
			for(k=jcross1; k<jcross2; k++){
				//lchrom[qType]为题型qType对应的染色体长度
				for(int j=0; j<lchrom[t]-sub; j++){
					if(parent2[k] == temp[j]){
						//将交叉点之间附加码从temp中去掉
						for(int j1=j; j1<lchrom[t]-sub-1; j1++){
							temp[j1] = temp[j1+1];
						}
					}
				}
				sub++;
			}
			//将temp顺序码中的值依次赋给parent1交叉点两边的位置
			for(int i=0; i<jcross1; i++){ //为jcross1左边赋值
				child2[i] = temp[i];
			}
			k=0;
			for(int i=jcross2; i<lchrom[t]; i++){ //为jcross2右边赋值
				child2[i] = temp[jcross1+k];
				k++;
			}
		}
	}
	//变异操作
	private int[][] mutation(int[][] child, int t){
		//child指向要变异的染色体的附加码，qType表示题型
		for(int i=0; i<lchrom[t]; i++){//依洗牌方式重排appCode数组
			//lchrom[qType]表示qType题型对应染色体的编码长度
			int temp = (int)(Math.random() * (lchrom[t]-1));//产生0到lchrom[qType]-1范围内的随机数
			int exchange = child[i][1];//交换appendCode[i]和appendCode[temp]中的值
			child[i][1] = child[temp][1];
			child[temp][1] = exchange;
		}
		return child;
	}
	//适应度计算
	private double objfunc(Chrom p){
		int[] chapter = new int[12];
		int[] difficulty = new int[5];
		DBConn rs = new DBConn();
		int[] temp;
		try {
			for(int i=0; i<3; i++){
				for(int j=0; j<lchrom[i]; j++){
					if(p.getElement(i)[j][1] == 1){
						temp = rs.search(j+1, qType[i]);
						chapter[temp[0]-1] += temp[2];
						difficulty[temp[1]-1] += temp[2];
					}
				}
			}
			rs.db_close();
		} catch (Exception e) {
			e.printStackTrace();
		}
		double temp1 = 0;
		for(int i=0; i<12; i++){
			temp1 += Math.abs(chapterPara[i] - chapter[i]);
		}
		double f = temp1/12*0.2;
		temp1 = 0;
		for(int i=0; i<5; i++){
			temp1 += Math.abs(difficultyPara[i] - difficulty[i]);
		}
		f += temp1/5*0.8;
		//System.out.println("f  " + f);
		return f;
	}
	//贝努利试验
	private boolean flip(double probability){
		double ppp = Math.random();
		if(ppp <= probability) return true;
		return false;
	}
	
	private int[] lchrom = {180, 180, 180};	//题库中选择题，填空题，解答题各自的数量及试题总量
	private int[] qNum = {15, 10, 8};
	private int[] chapterPara = {5, 8, 8, 5, 8, 20, 8, 5, 12, 8, 8, 5};
	private int[] difficultyPara = {15, 20, 30, 25, 10};
	private int[][] child1;
	private int[][] child2;
	private String[] qType = {"qSelect", "qFilling", "qAnswer"};
	private Chrom[] oldpop, newpop;
	private Chrom minChrom;
	private int popSize;
	private int maxGen;  	//最大世代数
	private int typeNum = 3;		//题型种类数量
	private double pcross = 0.9;
	private double pmutation = 0.05;
	private double sumFitness;
	private double max;
	private double min;
	private double avg;
}