gaapopulation.java

Java实现的遗传算法工具集：GA Playground

import java.text.*;
import java.util.*;

public class GaaPopulation {
	
	GaaSelection selection;
	
	boolean exitFlag;
	boolean debugFlag;
	int stagnationCounter;
	int degradeCounter;
	int totalShuffles;
	int totalInversions;
	double bestVal;
	double lastVal;
	String bestChrom;
	String lastChrom;
	int currentId;
	
	int popSize;
	int genesNumber;
	int generation;
	int survivorsPercent;
	int gaType;
	int crossType;
	int stagnationLimit;
	int degradeLimit;
	double sumFitness;
	double exitValue;
	
	String chroms[];
	String kids[];
	String memory[];
	double vals[];
	double kidVals[];
	double fits[];
	double kidFits[];
	double tempVals[];
	
	DecimalFormat dFormat;
	DecimalFormat f0;
	DecimalFormat f000;

	
	GaaProblem problem;
	

	public GaaPopulation(GaaProblem pr) {
		
		int i;
		
		debugFlag = false;
		dFormat = new DecimalFormat("0.000");
		f000 = new DecimalFormat("000");
		problem = pr;
	  selection = new GaaSelection(problem,this);
		
		updateParams();
		initPopulation();
		
	}


	public void updateParams() {
		
		popSize = problem.popSize;
		genesNumber = problem.genesNumber;
		gaType = problem.gaType;
		exitValue = problem.exitValue;
		stagnationLimit = problem.stagnationLimit;
		degradeLimit = problem.degradeLimit;
		survivorsPercent = problem.survivorsPercent;
		generation = 0;
		
		chroms = new String[popSize];
		kids = new String[popSize];
		memory = new String[popSize];
		vals = new double[popSize];
		kidVals = new double[popSize];
		fits = new double[popSize];
		kidFits = new double[popSize];
		tempVals = new double[popSize];
		
		for (int i=0;i<popSize;i++) {
			memory[i] = "2222222222";
		}

	}
	
	
	public void initPopulation () {
		
		int i;
		
		stagnationCounter = 0;
		degradeCounter = 0;
		exitFlag = false;
		bestVal = 0;
		lastVal = 0;
		bestChrom = "";
		lastChrom = "";
		generation = 0;
		totalShuffles = 0;
		totalInversions = 0;
		problem.functionCalls = 0;
		
		boolean b = GaaApplet.keepOldPop;
		if (!GaaApplet.keepOldPop) {
			updateParams();
			for (i=0;i<popSize;i++) {
				chroms[i] = problem.alleleSet.encodeRandomChrom(gaType);
			}
		}
		
		problem.function.setPop(this);
		problem.function.preBreed();
		
		for (i=0;i<popSize;i++) {
			currentId = i;
			vals[i] = problem.function.getValue(chroms[i]);
			fits[i] = vals[i];
			double a = vals[i];
			a = a;
		}
		
		problem.function.postBreed();
		
		processFitness();
		
		bestVal = vals[0];
		bestChrom = chroms[0];
		lastVal = vals[0];
		lastChrom = chroms[0];
		
		problem.currentBestVal = vals[0];
		problem.currentBestChrom = chroms[0];
		problem.currentGeneration = 0;
		
		//GaaApplet.statusLabel.setText("Start. Best = \t"+GaaMisc.formatDouble(bestVal,3));
		//deb.debug("Start. Best = \t"+GaaMisc.formatDouble(bestVal,3));
		
	}
	
	
		
	
	public void runEvolution(int num) {
		
		int i;
		long t = 0,t1 = 0,t2 = 0, t1a,t1b,t1c;
		
		if (num == 0) {
			double winner = vals[0];
			while (winner < exitValue) {
				newGeneration();
				winner = vals[0];
			}
		}
		else {
			debugFlag = true;
			
			t = 0;
			for (i=0;i<num;i++) {
				//GaaMisc.dbg("Before New Generation\n" + poplistTableString(),problem.withLogging);
				t1 = System.currentTimeMillis();
				newGeneration();
				t2 = System.currentTimeMillis();
				t += (t2-t1);
				//GaaMisc.dbg("After New Generation\n" + poplistTableString(),problem.withLogging);
			}
			debugFlag = false;
			
			GaaMisc.dbg("\nTime for one generation = "+(double)(t/num)+" millisecs");
			//GaaApplet.statusLabel.setText("Time for one generation = "+(t/num)+" millisecs");
		}
		
	}		

	public void newGeneration() {

		generation++;
		problem.currentGeneration = generation;
				
		if ((!problem.inputString1.equals("")) && (problem.udfDouble > 0)) {
			for (int i=0;i<popSize;i++) {
				if (GaaMisc.flip(problem.udfDouble/100))
					chroms[i] = problem.inputString1;
			}
		}
		
		breed();
		processFitness();
		processValue();
		
		if (stagnationCounter > stagnationLimit) {
				kick();
				processFitness();
		}
		
		lastVal = vals[0];
		lastChrom = chroms[0];
		double a;
		if (lastVal > 0)
			a = 0;
		
		if (problem.withStatusText)
			GaaApplet.statusLabel.setText("Current Chromosome: "+lastChrom);
		
		if (((problem.minmaxType == 1) && (vals[0] >= bestVal)) ||
			((problem.minmaxType == 2) && (vals[0] <= bestVal))) {
			if (lastVal > bestVal)
				a = 1;	
			if (bestVal != 0.0)
				a=2;
			if (bestVal != vals[0])
				a=3;
			bestVal = vals[0];
			bestChrom = chroms[0];
			problem.currentBestVal = vals[0];
			problem.currentBestChrom = chroms[0];
		}
		
		if (((problem.minmaxType == 1) && (vals[0] >= (problem.exitValue-problem.exitTolerance))) ||
			((problem.minmaxType == 2) && (vals[0] <= (problem.exitValue+problem.exitTolerance)))) {
			exitFlag = true;
			GaaMisc.dbg("Generation #"+f000.format(generation) + ": " + chroms[0] + "   Value:  " + dFormat.format(vals[0]) + "   Best:  " + dFormat.format(bestVal),problem.withLogging);
		}
		else {
			GaaMisc.dbg("Generation #"+f000.format(generation) + ": " + chroms[0] + "   Value:  " + dFormat.format(vals[0]) + "   Best:  " + dFormat.format(bestVal),problem.withLogging);
			String s = chroms[0];
			double d = vals[0];
			double dd = bestVal;
			dd=dd;
		}
	
	}

	/*
	private double getSumFitness() {

		int i;
		double sum;
		
		sum = 0;
		for (i=0;i < popSize;i++) {
			sum += fits[i];
		}

		return sum;
	}

		
	private String getParent() {

		int i;
		double rand, partsum;
		String chrom = "";
		String txt;

		partsum = 0;
		rand =(double) (Math.random()*sumFitness);

		for (i=0;i<popSize;i++) {
			partsum += fits[i];
			
			if (partsum >= rand) {
				chrom = chroms[i];
				break;
			}
		}

		return chrom;	

	}
	*/


	private String mate() {

		String mom, dad, kid, temp, txt;
		
		mom = selection.getParent();
		dad = selection.getParent();
		kid = problem.crossover.crossover(mom,dad);
		temp = kid;
		kid = problem.mutation.mutation(kid);
		kid = problem.inversion.inversion(kid);
		
		if (debugFlag) {
			double x = problem.function.getValue(mom);
			double y = problem.function.getValue(dad);
			double z = problem.function.getValue(temp);
			double u = problem.function.getValue(kid);
			txt = "\nGeneration #"+generation+"  Mating #"+currentId+" : \n";
			txt += "Best: "+chroms[0]+" / "+vals[0]+"\n";
						txt += "Best: "+chroms[0]+" / "+problem.function.getValue(chroms[0])+"\n";
			txt += "Mom: "+mom+" / "+problem.function.getValue(mom)+"\n";
			txt += "Dad: "+dad+" / "+problem.function.getValue(dad)+"\n";
			txt += "Kid: "+temp+" / "+problem.function.getValue(temp)+"\n";
			txt += "Mutated Kid: "+kid+" / "+problem.function.getValue(kid)+"\n";
			GaaMisc.dbg(txt,true);
			
		}

		return kid;

	}



	private void breed() {

		int i, j, k, n;
		int best = 0;

		sumFitness = selection.getSumFitness();
		problem.function.preBreed();
		
		for (i=0;i<popSize;i++) {
			currentId = i;
			kids[i] = mate();
			kidVals[i] = problem.function.getValue(kids[i]);
			kidFits[i] = kidVals[i];
		}
		
		debugFlag = false;
		problem.function.postBreed();
		
		sortKidsByVals();
		
		if (survivorsPercent > 0) {
			n = (int) (popSize*survivorsPercent/100);
			for (i=n;i<popSize;i++) {
				if (i > (n-1)) {
					chroms[i] = kids[i-n];
					vals[i] = kidVals[i-n];
					fits[i] = kidFits[i-n];
				}
			}
		}
		else {
			for (i=0;i<popSize;i++) {
					chroms[i] = kids[i];
					vals[i] = kidVals[i];
					fits[i] = kidFits[i];
			}
		}
		
	}


	public void processFitness() {
		
		int i;
		double max;
		
		if (problem.minmaxType == 2) {
			sortChroms(chroms,fits,vals,false);
			System.arraycopy(vals,0,tempVals,0,vals.length);
			max = Math.abs(getDoublesMax(tempVals))*1.1;
			for (i=0;i<popSize;i++) {
				fits[i] = max - vals[i];
				if ((i > 0) && (chroms[i].equals(chroms[i-1])))
					fits[i] = fits[i-1]*problem.kinFactor;
				//if ((i > 0) && (fits[i] == (fits[i-1])))
				//	fits[i] = fits[i-1]*problem.kinFactor;
			}
		}
		else {
			sortChroms(chroms,fits,vals,true);
			for (i=0;i<popSize;i++) {
				if ((i > 0) && (chroms[i].equals(chroms[i-1])))
					fits[i] = fits[i-1]*problem.kinFactor;
				//if ((i > 0) && (fits[i] == (fits[i-1])))
				//	fits[i] = fits[i-1]*problem.kinFactor;
			}
		}
		
		preScale();
			
	}	


	public void processValue() {
		
		int i;
		double max;
		
		if (problem.minmaxType == 2) {