gas.java

是一个用java做的遗传算法的实例

package yznu.algorithms.gas;
import java.util.Random;
public class GAS {

	static int generation;
	 static int best_index;
	 static int worst_index;
	 static Inidividual bestindividual =new Inidividual();
	 static Inidividual worstindividual=new Inidividual() ;
	 static Inidividual currentbest = new Inidividual();
	static Inidividual []population=new Inidividual[Constant.POPSIZE];
	public void generateInitialPopulation()
	{
		int i,j;
		//Random random = new Random(); 
		char[] chrom = new char[Constant.CHROMLENGTH];
		for(i=0;i<Constant.POPSIZE;i++)
		{
			population[i] = new Inidividual();
			for(j=0;j<Constant.CHROMLENGTH;j++)
			{
				population[i].chrom[j]=(Math.random()<0.5)?'0':'1';
			}
		}
		/*
		System.out.println("initial*************************");
		for(i=0;i<Constant.POPSIZE;i++)
		{
			for(j=0;j<Constant.CHROMLENGTH;j++)
		      System.out.print(population[i].chrom[j]);
			System.out.println();
		}*/
	}
	public void EvaluatePopulation()
	{
		CalculateObjectValue();
		CalculateFitnessValue();
		FindBestAndWorstIndividual();
	}
	void CalculateObjectValue()
	{
		int i;
		long temp1,temp2;
		double x1,x2;
		for(i=0;i<Constant.POPSIZE;i++)
		{
			temp1=DecodeChromosome(population[i].chrom,0,Constant.LENGTH1);
			temp2=DecodeChromosome(population[i].chrom,Constant.LENGTH1,Constant.LENGTH2);
			x1=4.096*temp1/1023.0-2.048;
			x2=4.096*temp2/1023.0-2.048;
			population[i].value=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);
			
		}
	}
	long DecodeChromosome(char []str,int point,int length)
	{
		long decimal=0L;
		for(int i=0;i<length;point++,i++)
			decimal+=(str[point]-'0')<<(length-1-i);
		return decimal;
	}
	void CalculateFitnessValue()
	{
		int i;
		double temp=0.0;
		for(i=0;i<Constant.POPSIZE;i++)
		{
			if(Constant.FunctionMode==Constant.MAXIMIZATION)
			{
				if((population[i].value+Constant.Cmin)>0.0)
				{
					temp=Constant.Cmin+population[i].value;
				}
				else
				{
					temp=0.0;
				}
			}
			else if(Constant.FunctionMode==Constant.MINIMIZATION)
			{
				if(population[i].value<Constant.Cmax)
				{
					temp=Constant.Cmax-population[i].value;
				}
				else
				{
					temp=0.0;
				}
			}
			population[i].fitness=temp;
		}
	}
	public void FindBestAndWorstIndividual()
	{
		int i;
		double sum=0.0;
		bestindividual = population[0];
		worstindividual = population[0];
		for(i=1;i<Constant.POPSIZE;i++)
		{
			if(population[i].fitness>bestindividual.fitness)
			{
				bestindividual = population[i];
				best_index = i;
			}
			else if(population[i].fitness<worstindividual.fitness)
			{
				worstindividual = population[i];
				worst_index = i;
			}
			//sum+=population[i].fitness;
		}
		//population[worst_index]=population[best_index];
		if(generation ==0)
		{
			//currentbest = bestindividual;
			copyIndividual(currentbest,bestindividual);
			System.out.println("generation="+generation);
		    System.out.println(currentbest.fitness+"------------------");
		}else
		{
			if(bestindividual.fitness>currentbest.fitness)
			{
				System.out.println("generation="+generation);
				System.out.println("compare currentbest.fitness to bestindividual.fitness");
			    System.out.println(currentbest.fitness+"------------------"+bestindividual.fitness);
				//currentbest = bestindividual;
			    copyIndividual(currentbest,bestindividual);
			}
		}
	}
	void copyIndividual(Inidividual c,Inidividual p)
	{
		for(int i=0;i<Constant.POPSIZE;i++)
		{
			for(int j=0;j<Constant.CHROMLENGTH;j++)
			{
		      c.chrom[j]=p.chrom[j];
			}
			c.value=p.value;
			c.fitness=p.fitness;
		}
	}
	public void GenerateNextPopulation()
	{
		SelectionOperator();
		CrossoverOperator();
		MutationOperator();
	}
	void SelectionOperator()
	{
		int i,index;
		double p=0.0,sum=0.0;
		double []cfitness=new double[Constant.POPSIZE];
		double max,min;
		int maxi=0,mini=0;
		double jc;
		//double 
		Random random = new Random();
		Inidividual []newpopulation = new Inidividual[Constant.POPSIZE];
		max=population[0].fitness;
		min=max;
		for(i=0;i<Constant.POPSIZE;i++)
		{
			sum+=population[i].fitness;
			//if(max<population[i].fitness) { max = population[i].fitness;maxi=i;}
			//if(min>population[i].fitness) { min = population[i].fitness;mini=i;}
		}
		
		jc = max - min;
		jc= jc/Constant.POPSIZE;
		
		for(i=0;i<Constant.POPSIZE;i++)
		{
			cfitness[i]=population[i].fitness/sum;
		}
		for(i=1;i<Constant.POPSIZE;i++)
		{
			cfitness[i]=cfitness[i-1]+cfitness[i];
		}
		//min=100000;
		for(i=0;i<Constant.POPSIZE;i++)
		{
			p=random.nextInt()%sum/sum;
			if(p<0) p=-p;
			//System.out.println("p="+p);
			//if(p>1){ i--;continue;}
			//p=random.nextDouble(cfitness[Constant.POPSIZE-1]);
			//System.out.println(p+"  "+cfitness[0]+"  "+cfitness[Constant.POPSIZE-1]+" "+i);
		    index = 0;
		    while(p>cfitness[index])
		    {
		    	index++;
		    }
		    newpopulation[i]=population[index];
		    //if(min<newpopulation[i].fitness) mini=i;
		}
		//System.out.println(newpopulation[mini].value+" ==========="+population[maxi].value);
		//newpopulation[mini]=population[maxi];
		for(i=0;i<Constant.POPSIZE;i++)
		{
			//System.out.println(population[i].value+"   "+newpopulation[i].value);
			population[i]=newpopulation[i];
		}
		System.out.println("after select***********************");
		for(i=0;i<Constant.POPSIZE;i++)
		{
			for(int j=0;j<Constant.CHROMLENGTH;j++)
			{
		      System.out.print(population[i].chrom[j]);
		      
			}
			System.out.println("  "+population[i].value);
			
		}
		
	}
	public void CrossoverOperator()
	{
		int i=0,j;
		int index[]=new int[Constant.POPSIZE];
		int point,temp;
		double p;
		char ch;
		
		Random random = new Random();
		for(i=0;i<Constant.POPSIZE;i++)
		{
			index[i]=i;
		}
		for(i=0;i<Constant.POPSIZE;i++)
		{
			point =random.nextInt()%(Constant.POPSIZE-i);
			if(point<0) point = - point;
			temp=index[i];
			index[i]=index[point+i];
			index[point+i]=temp;
		}

		for(i=0;i<Constant.POPSIZE-1;i+=2)
		{
			p=Math.random();
			//System.out.println(p);
			if(p<Constant.Pc)
			{
				point = random.nextInt(Constant.CHROMLENGTH-1)+1;
				/*
				for(j=0;j<Constant.CHROMLENGTH;j++)
				{
					System.out.print(population[index[i]].chrom[j]);
				}
				System.out.println("  ");
				for(j=0;j<Constant.CHROMLENGTH;j++)
				{
					System.out.print(population[index[i+1]].chrom[j]);
				}
				System.out.println("tttttttttt  ");
                */
				
				for(j=point;j<Constant.CHROMLENGTH;j++)
				{
					ch=population[index[i]].chrom[j];
					population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
					population[index[i+1]].chrom[j]=ch;
				}
				/*
				for(j=0;j<Constant.CHROMLENGTH;j++)
				{
					System.out.print(population[index[i]].chrom[j]);
				}
				System.out.println("  ");
				for(j=0;j<Constant.CHROMLENGTH;j++)
				{
					System.out.print(population[index[i+1]].chrom[j]);
				}

				System.out.println(point);
*/				
			}
		}
	}
	
	public void MutationOperator()
	{
		int i,j;
		double p;
		/*
		System.out.println("byq**************************************");
		for(i=0;i<Constant.POPSIZE;i++)
		{
			for(j=0;j<Constant.CHROMLENGTH;j++)
		      System.out.print(population[i].chrom[j]);
			System.out.println();
			
		}*/
		for(i=0;i<Constant.POPSIZE;i++)
		{
			for(j=0;j<Constant.CHROMLENGTH;j++)
			{
				p=Math.random();
//				p=random.nextInt((int)(max+1))/sum;
				if(p<Constant.Pm)
				{
					//System.out.println(i+"  "+j+"  "+p);
					population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
				}
			}
		}
		/*
		System.out.println("byh**************************************");
		for(i=0;i<Constant.POPSIZE;i++)
		{
			for(j=0;j<Constant.CHROMLENGTH;j++)
		      System.out.print(population[i].chrom[j]);
			System.out.println();
			
		}*/
	}
	public void PerformEvalution()
	{
		System.out.println(currentbest.fitness+ "  +++++++++++"+bestindividual.fitness+"-----"+worstindividual.fitness);
		if(bestindividual.fitness>currentbest.fitness)
		{
			//currentbest=population[best_index];
			copyIndividual(currentbest,population[best_index]);
		}else
		{
			//population[worst_index]=currentbest;
			copyIndividual(population[worst_index],currentbest);
		}
	}
	
	public void OutputTextReport()
	{
		int i;
		double sum;
		double average;
		sum =0.0;
		for(i=0;i<Constant.POPSIZE;i++)
		{
			sum+=population[i].value;
		}
		average = sum/Constant.POPSIZE;
		System.out.print("gen="+generation+",avg="+average+",best="+currentbest.value);
		System.out.print("chromosome=");
		for(i=0;i<Constant.CHROMLENGTH;i++)
		{
			System.out.print(currentbest.chrom[i]);
		}
		System.out.println();
	}
	public static void main(String args[])
	{

		//for(int i=0;i<100;i++)
	    //System.out.println(Math.random()+"  ");
		
		generation = 0;
		GAS gas = new GAS();
		gas.generateInitialPopulation();
		gas.EvaluatePopulation();
		
		while(generation<Constant.MaxGeneration)
		{
			generation++;
			gas.GenerateNextPopulation();
			gas.EvaluatePopulation();
			gas.PerformEvalution();
			gas.OutputTextReport();
		}
		/*
		for(int i=0;i<Constant.POPSIZE;i++)
		{
			for(int j=0;j<Constant.CHROMLENGTH;j++)
		      System.out.print(population[i].chrom[j]);
			System.out.println();
			System.out.println(gas.DecodeChromosome(population[i].chrom, 0, Constant.LENGTH1));
			System.out.println(gas.DecodeChromosome(population[i].chrom, Constant.LENGTH1,Constant.LENGTH2));
			System.out.println(population[i].value+"    "+population[i].fitness+"  ");
		}*/
		
		//System.out.println(currentbest.fitness);
		
		
	}
}