import java.io.*;
import java.text.*;
import java.util.Locale;

abstract class f_xj extends Mathd
{
  // single function  multi independent variable
  // a single value is returned indiced to equation_ref
  // example f[0]=x[0]+sin(x[1])
  //         f[1]=x[0]*x[0]-x[1]
  // func(x,1) returns the value of f[1]
  // func(x,0) returns the value of f[0]

  abstract double func(double x[]);
}

class genotype3
{
// each genotype3 is member of the population
// Genotype is like a chromosone in real life genetic systems
// it can be thought as an evaluation point of a function with n variable
// f(xi)=f(x1,x2,x3,..,x_nvars)
public Gene3 G[]      ;  // string of variables makes a genotype3
public double Fitness;  // genotype3's fitness f(xi)
public double Upper[];  // gene's upper bound; xi_lower < xi < xi_upper
public double Lower[];  // Gene's lower bound; xi_lower < xi < xi_upper
public double RFitness; // the relative fitness
public double CFitness; // cumulative fitness
public int NVARS;       // Number of variables(Genes)
public int N;           // Number of bits defining each gene
public boolean Breeder;
  
  public genotype3(int iNVARS,double low[],double high[],int iN,f_xj fi)
  {setgenotype(iNVARS,low,high,iN,fi);}
  
  public void setgenotype(int iNVARS,double low[],double high[],int iN,f_xj fi)
  {
  setN(iN);  
  setNVARS(iNVARS);	  
  G=new Gene3[NVARS];
  Upper=new double[NVARS];
  Lower=new double[NVARS];
  setLower(low);
  setUpper(high);
  setGene(); 
  setFitness(fi);
  }
  
  public genotype3(genotype3 gi,f_xj fi)
  {setgenotype(gi,fi);}
   
  public void setgenotype(genotype3 gi,f_xj fi)
  {
  setN(gi.N);  
  setNVARS(gi.NVARS);	  
  G=new Gene3[NVARS];
  Upper=new double[NVARS];
  Lower=new double[NVARS];
  setLower(gi.Upper);
  setUpper(gi.Lower);
  for(int i=0;i<NVARS;i++)
    G[i]=gi.G[i].copyGene(); 
  setFitness(fi);
  }
  
  public genotype3 copygenotype(f_xj fi)
  {
  genotype3 g1=new genotype3(this,fi);
  return g1;
  }
  
  public void setN(int iN)    {N=iN;}
  public void setNVARS(int iNVARS)    {NVARS=iNVARS;}
  public void setLower(double lbound[]) {for(int i=0;i<NVARS;i++) Lower[i]=lbound[i];}
  public void setUpper(double ubound[]) {for(int i=0;i<NVARS;i++) Upper[i]=ubound[i];}
  public void setFitness(f_xj fi) 
  {	 Fitness=fi.func(getGene());}
  public void setRFitness(double isum)  {RFitness=Fitness/isum;}
  public void setCFitness(double ix)  {CFitness=ix;}
  public double getLower(int j) {return Lower[j];}
  public double getUpper(int j) {return Upper[j];}
  public double getFitness() {return Fitness;}
  public double getRFitness(){return RFitness;}
  public double getCFitness(){return CFitness;}
  public void breed() {Breeder=true;}
  public void not_breed() {Breeder=false;}
  public boolean isBreed() {return Breeder;}  
  
    
  public void setGene(int val)
  {  G[val]=new Gene3(Lower[val],Upper[val]);}
  
  public void setGene()
  {  for(int j=0;j<NVARS;j++)	  
	     setGene(j);
  }
  
  public double getGene(int val)
  { return G[val].getX();}  
  
  public double[] getGene()
  {   double x[]=new double[NVARS];
	  for(int j=0;j<NVARS;j++)	  
	     x[j]=getGene(j);
	  return x;     
  }

  public String toString()
  {
  //x values, Fitness,relative fitness and cumulative fitness	  
  String s="";
  for(int j=0;j<NVARS;j++)	  
	 s+=G[j].toString()+" F:";
  s+=getFitness();
  s+="RF:"+getRFitness();
  s+="CF:"+getCFitness();	      	  
  return s;
  }
}  //end of class genotype3

public class Genetic3
{
	// Maximizing a function
	int    POPSIZE; //population size
	int    MAXGENS; //maximum number of generations;
	int    NVARS;   //number of independent variables of function
    int    N;        //number of genes in each variable
	double PXOVER; //probability of crossover;
    double PMUTATION; //proportion of mutated variables
    int Generation; //Current generation number
    int NBreeder; //Number of survivors in a generation
    int Best; //The best genotype3 in the population
    genotype3 Population[];
    //f_xj f;  // function to be avaluated by genetic algorithm
    
    public Genetic3(int iPOPSIZE,int iMAXGENS,int iNVARS,int iN, 
    double iPXOVER,double iPMUTATION)
    {
    POPSIZE=iPOPSIZE;
    MAXGENS=iMAXGENS;
    NVARS=iNVARS;
    N=iN;
    PXOVER=iPXOVER;
    PMUTATION=iPMUTATION;
    NBreeder=0;
    Population=new genotype3[POPSIZE+1];        
	}	
	public void setPopulation(double low[],double up[],f_xj fi)
	{
	for(int i=0;i<POPSIZE+1;i++)
	  { Population[i]=new genotype3(NVARS,low,up,N,fi);}
	}
	
	public genotype3[] copyPopulation(f_xj fi)
	{
	genotype3 Po[]=new genotype3[POPSIZE+1]; 	
	for(int i=0;i<POPSIZE+1;i++)
	  { Po[i]=new genotype3(Population[i],fi);
	    Po[i].Fitness=Population[i].Fitness;
	  	Po[i].RFitness=Population[i].RFitness;	    
	    Po[i].CFitness=Population[i].CFitness;	
	  }
	return Po;  
	}
		
	public void evaluate(f_xj fi)
	{
	  int mem;
	  int j;
	  double x[]=new double[NVARS];
	  for(mem=0;mem<POPSIZE;mem++)
	  {
	  //System.out.println(Population[mem].toString());	  
	  Population[mem].setFitness(fi);
	  if(Population[mem].getFitness() > Population[POPSIZE].getFitness())
	     {
		 Best=mem;
		 Population[POPSIZE]=Population[mem];    
	     for(j=0;j<NVARS;j++)
	        {
	        Population[POPSIZE].G[j].copyGene(Population[mem].G[j]);
		    }//end of for(j=0..
		 }//end of if
	  }//end of for(mem=0;..
	}
	
	
	public void setRFCF(genotype3 Pi[])
	{
	//calculates relative and cumulative fitness functions	
	int mem;
	int PN=Pi.length;	
	double sum=0.0;
	//total fitness of population
	for(mem=0;mem<PN;mem++)
	  {sum+=Pi[mem].Fitness;} 
	//System.out.println("sum="+sum);   
	//calculate relative fitness of each genotype3
	for(mem=0;mem<PN;mem++)
	  {Pi[mem].setRFitness(sum);}
	//calculate cumulative fitness
	Pi[0].setCFitness(Pi[0].getRFitness());  
    for(mem=1;mem<PN;mem++)
	  {Pi[mem].setCFitness(Pi[mem-1].getCFitness()+Pi[mem].getRFitness());
	  }
	}
	
	public void toString(genotype3 Pi[])
	{
	int mem;
	int PN=Pi.length;	
	for(mem=0;mem<PN;mem++)
	{
	//list them	
	System.out.println("Population["+mem+"]="+Pi[mem].toString());
	} 	
	}
	
	public void select(f_xj fi)
	{
	//select the new generation members of population	
	double r;
	int mem;
	setRFCF(Population);
	//create a new population;
	genotype3 Po[]=copyPopulation(fi);
    setRFCF(Po);	
    for(int i=0;i<POPSIZE;i++)
    {   mem=0;
        r=Math.random();
        double gf1=Population[i].getCFitness();
	    double gf2;
        if (gf1 > r) Po[i]=Population[mem].copygenotype(fi);     
	    for(mem=1;mem<POPSIZE;mem++)
           {
	       gf2=Population[mem].getCFitness();
	       if( gf2>=r && gf1< r ) {Po[i]=Population[mem].copygenotype(fi);break;}
           } 
    }
    setRFCF(Po);    
	Population=Po;
	evaluate(fi);
    //toString(Population); 
    }
		
   public void crossover(f_xj fi)
   {
   int i,count;
   int mem;
   int POne,a;
   int PTwo,b;
   int point;
   //select members for breeding
   int iselect[]=new int[POPSIZE];
   int counter=0;
   double r;
    for(mem=0;mem<POPSIZE;mem++)
	{
	  r=Math.random();	  
	  if(r < PXOVER)
	     {
		 iselect[counter++]=mem;    
	     Population[mem].breed();
		 NBreeder++;
	     }
	  else
	     Population[mem].not_breed();	 
	}
	//System.out.println("iselect="+Matrix.toString(iselect));
	//let also best of the population to breed
	Population[Best].breed();
	   
   //loop through the population select breeding pairs
    for(mem=0;mem<POPSIZE;mem++)
        {
           //select two in popolation in random
           a=(int)(Math.random()*NBreeder)+1;
           b=(int)(Math.random()*NBreeder)+1;          
           count=0;
           POne=0;
           PTwo=0;
           //select two individuals for breeding
           for(i=0;i<POPSIZE;i++)
             {
             if(Population[i].isBreed())
                {
                count++;
                if(count==a) POne=count;
                if(count==b) PTwo=count;
	            }
	         }
	       //perform a crossover; 
	         genotype3 Po[]=new genotype3[2];
		     Po[0]=Population[POne].copygenotype(fi);
		     Po[1]=Population[PTwo].copygenotype(fi);
	         for(i=0;i<NVARS;i++)
	         {
		     Population[POne].G[i].cross(Math.random(),Po[0].G[i],Po[1].G[i]);
		     Population[PTwo].G[i].cross(Math.random(),Po[0].G[i],Po[1].G[i]);
		     }
		     Population[POne].setFitness(fi);
		     Population[PTwo].setFitness(fi);		                
	       } 
	    }
   
   public void mutate(f_xj fi)
   {
   int i;
   double lbound,hbound;
   int nmutations;
   int member;
   int var;
   nmutations=(int)((double)(POPSIZE*NVARS*PMUTATION*N));
   for(i=0;i<nmutations;i++)
      {
      member=(int)(Math.random()*POPSIZE);
      var=(int)(Math.random()*NVARS);
      //replace the old value with a new mutated one
      Population[member].G[var].mutate();
	  //after mutation recalculate the function value
      Population[member].setFitness(fi); 
      }   	     	        
   }
   
   public String report()
   {
   String s;	   
   int i;
   double best_value;
   double avg;
   double stdev;
   double sum_square;
   double square_sum;
   double sum;
   double xx;
   sum=0;
   sum_square=0.0;
   for(i=0;i<POPSIZE;i++)
      {
	  xx= Population[i].getFitness();   
      sum+=xx;
      sum_square=xx*xx;
	  }
   avg=sum/(double)POPSIZE;
   square_sum=sum*sum/(double)POPSIZE;
   stdev=Math.sqrt(square_sum);
   best_value=Population[POPSIZE].getFitness();
   double aa[]=new double[NVARS+1]; 
   for(i=0;i < NVARS;i++)
     {
     aa[i]=Population[POPSIZE].getGene(i);
	 }
	 aa[NVARS]=Population[POPSIZE].getFitness();
    
   //s="Generation = "+Generation+"best value = "+Matrix.toString(aa)+"Average = "+avg+"Standart Deviation = "+stdev;   
   s="Generation = "+Generation+"best value = "+Matrix.toString(aa);
   return s;
   }
   
   public double[] getBest()
   {
   double aa[]=new double[NVARS+1];  
   for(int i=0;i < NVARS;i++)
     {
     aa[i]=Population[POPSIZE].getGene(i);
	 }
	 aa[NVARS]=Population[POPSIZE].getFitness();
   return aa;	      
   }
   
   public double[] calculate(f_xj fi,boolean report)
   {
   evaluate(fi);
   Generation=0;
   while(Generation<MAXGENS)
     {
     Generation++;
     NBreeder=(int)(0.8*POPSIZE);
     select(fi);
     crossover(fi);
     mutate(fi);
     evaluate(fi);
     //if(report)
        //System.out.println(report());
     }	 
   return getBest();
   }      
}
