public class GA {
	final static int N=3;  // number of variables
	final static int M=1;  // number of objectives
	final static int TYPE=1; // 1=max;-1=min
	final static int GEN=400; // maximum generation number
	final static int POP_SIZE=30;
	final static double P_MUTATION=0.15 ;  //變異概率
	final static double P_CROSSOVER=0.7;  //交配概率，當隨機數(shù)小于該值時，該染色體被選中
	static double [][] CHROMOSOME=new double [POP_SIZE+1][N+1];
	static double [][]OBJECTIVE=new double [POP_SIZE+1][M+1];
	static double []q=new double[POP_SIZE+1];
	final static long RAND_MAX=1000000;
	/////////////////////////////////////
	public static double myu(double a, double b) // Uniform Distribution
	{
		  double y;
		  if(a>b) {
			System.out.print("\nThe first parameter should be less than the second!");
			//exit(1);
		  }
		  y = Math.random();
		  return (a+(b-a)*y); 
		}
	public static void objective_function()
	{
		double x1,x2,x3;
		int i;
		for(i = 1; i <= POP_SIZE; i++) 
		{
			x1 = CHROMOSOME[i][1];
			x2 = CHROMOSOME[i][2];
			x3 = CHROMOSOME[i][3];
			OBJECTIVE[i][1] = Math.sqrt(x1)+Math.sqrt(x2)+Math.sqrt(x3);
		}
		for(i=1;i<=POP_SIZE;i++)
		  OBJECTIVE[i][0] = OBJECTIVE[i][1];
	}
	///////////////////////////
	public static int constraint_check(double x[])
	{
		double a;
		int n; 
		for(n=1;n<=N;n++) 
			if(x[n]<0) 
				return 0;
		a = x[1]*x[1]+2*x[2]*x[2]+3*x[3]*x[3];
		if(a>1) 
			return 0;
		return 1;
	}

	/////////////////////////////////////////
	public static void initialization()
	{
	  double []x=new double [N+1]; // N is the number of variables
	  int i,j;
	  for(i=1; i<=POP_SIZE; i++)
	  {	  
	  	  do{
		  for(j=1; j<=N; j++) 
			  x[j]=myu(0,1);}
		  while (constraint_check(x) == 0); 
		  for(j=1; j<=N; j++) 
			  CHROMOSOME[i][j]=x[j];
	  
	  }
    }
	//////////////////////
	public static void main(String arc[])
	{
	  int i, j;
	  double a;

	  q[0]=0.05; 
	  a=0.05;
	  for(i=1; i<=POP_SIZE; i++) 
	  {
		  a=a*0.95; 
		  q[i]=q[i-1]+a;
	  } 
	  //q[]為seletion()函數(shù)中隨機選擇染色體做準備

	  initialization();
	  evaluation(0);
	  java.text.NumberFormat formater = java.text.DecimalFormat.getInstance(); 
	  formater.setMaximumFractionDigits(4); 

	  for(i=1; i<=GEN; i++) 
	    {
		  selection();
		  crossover();
		  mutation();
		  evaluation(i);
		  System.out.print("Generation NO.");
		  System.out.println(i);
		  //System.out.println("x=(");
		  for(j=1; j<=N; j++) 
		  {
			  if(j<N) 
				  System.out.println(formater.format(CHROMOSOME[0][j]));
			  
			  else
				  System.out.println(formater.format(CHROMOSOME[0][j]));
		  }
		  if(M==1) 
			  System.out.println(formater.format(OBJECTIVE[0][1]));
		  else 
		  {
			  System.out.println(")\nf=(");
		      for(j=1; j<=M; j++)
			  {
			     if(j<M) 
			    	 System.out.println(formater.format(OBJECTIVE[0][j]));
			     else 
			    	 System.out.println(formater.format(OBJECTIVE[0][j]));
			  }
		      System.out.println(")  Aggregating Value=%3.4f\n" + OBJECTIVE[0][0]);
		  }
	  }
	  System.out.println("\n");
	 // return 1;
	}
	//將染色體和目標函數(shù)按目標函數(shù)值由大到小進行排序
	public static void evaluation(int gen)  
	{
	  double a;
	  int   i, j, k, label;
	  objective_function();
	  if(gen==0)
	  {
		 for(k=0; k<=M; k++) 
			 OBJECTIVE[0][k]=OBJECTIVE[1][k];
		 for(j = 1; j <= N; j++) 
			 CHROMOSOME[0][j]=CHROMOSOME[1][j];
	  }
	  for(i=0; i<POP_SIZE; i++)
	  {
		  label=0;  
		  a=OBJECTIVE[i][0];
		  for(j=i+1; j<=POP_SIZE; j++)
			 if((TYPE*a)<(TYPE*OBJECTIVE[j][0])) 
			 {
				 a=OBJECTIVE[j][0];  
				 label=j;
			 }
		  if(label!=0) 
		  {
			 for(k=0; k<=M; k++) 
			 {
				 a=OBJECTIVE[i][k];
				 OBJECTIVE[i][k]=OBJECTIVE[label][k];
				 OBJECTIVE[label][k]=a;
			 }
			 for(j=1; j<=N; j++) 
			 {
				 a=CHROMOSOME[i][j];
				 CHROMOSOME[i][j]=CHROMOSOME[label][j];
				 CHROMOSOME[label][j]=a;
			 }
		  }
	  }
	}

	//////////////////////////////////////////
	public static void selection()
	{
	  double r;
	  double [][] temp=new double[POP_SIZE+1][N+1];
	  int   i, j, k;
	  for(i=1; i<=POP_SIZE; i++) 
	  {
		  r = myu(0,q[POP_SIZE]);
		  for(j=0; j<=POP_SIZE; j++) 
		  {
			  if(r<=q[j]) 
			  {
				  for(k=1; k<=N; k++) 
					  temp[i][k]=CHROMOSOME[j][k];
				  break;
			  }
		  }
	  }
	  for(i=1; i<=POP_SIZE; i++)
		 for(k=1; k<=N; k++)
			 CHROMOSOME[i][k]=temp[i][k];
	}

	/////////////////////   交配   //////////////////////
	public static void crossover()
	{
	  int   i, j, jj, k, pop;
	  double r;
	  double[] x = new double[N+1];
	  double[] y = new double[N+1];
	  pop=POP_SIZE/2;
	  for(i=1; i<=pop; i++)
	  {
		 if(myu(0,1)>P_CROSSOVER) 
			 continue;
		 j=(int)myu(1,POP_SIZE);
		 jj=(int)myu(1,POP_SIZE);
		 r=myu(0,1);
		 for(k=1; k<=N; k++)
		 {
			 x[k]=r*CHROMOSOME[j][k]+(1-r)*CHROMOSOME[jj][k];
			 y[k]=r*CHROMOSOME[jj][k]+(1-r)*CHROMOSOME[j][k];
		 }
		 if(constraint_check(x)==1)
		   for(k=1; k<=N; k++) 
			  CHROMOSOME[j][k]=x[k];
		 if(constraint_check(y)==1)
			 for(k=1; k<=N; k++) 
			 CHROMOSOME[jj][k]=y[k];
	  }
	}
	//////////////////////////////////////////
	public static void mutation()
	{
	  int i, j, k;
	  double infty;
	  double[] x = new double[N+1];
	  double[] y = new double[N+1];
	  double[] direction = new double[N+1];
	  double INFTY=10, precision=0.0001;
	  for(i=1; i<=POP_SIZE; i++)
	  {
		  if(myu(0,1)>P_MUTATION) 
			  continue;
		  for(k=1; k<=N; k++) 
			  x[k] = CHROMOSOME[i][k];
		  for(k=1; k<=N; k++)
			  if(myu(0,1)<0.5) 
				  direction[k]=myu(-1,1);
			  else 
				  direction[k]=0;
		  infty=myu(0,INFTY);
		  while(infty>precision) 
		  {
			  for(j=1; j<=N; j++) 
				  y[j]=x[j]+infty*direction[j];
			  if(constraint_check(y)==1) 
			  {
				 for(k=1; k<=N; k++) 
					 CHROMOSOME[i][k]=y[k];
				 break;
			  }
			  infty=myu(0,infty);
		  }
	  }
	}
}