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

abstract class f_xj
{
  // 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 genotype
{
// each genotype is member of the population
public double Gene[];   // string of variables makes a genotype
public double Fitness;  // Genotype's fitness
public double Upper[];    // gene's upper bound
public double Lower[];    // Gene's lower bound
public double RFitness; //the relative fitness
public double CFitness; //cumulative fitness
public int NVARS;
public boolean Survivor;
  genotype(int iNVARS)
  {
  NVARS=iNVARS;	  
  Gene=new double[NVARS];
  Upper=new double[NVARS];
  Lower=new double[NVARS];
  }
  
  public genotype(int iNVARS,double low[],double high[])
  {
  setGenotype(iNVARS,low,high);
  }
  
  public void setGenotype(int iNVARS,double low[],double high[])
  {
  setNVARS(iNVARS);	  
  Gene=new double[NVARS];
  Upper=new double[NVARS];
  Lower=new double[NVARS];
  setLower(low);
  setUpper(high);
  setGene(); 
  }
  
  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 double getLower(int j) {return Lower[j];}
  public double getUpper(int j) {return Upper[j];}
  public double getFitness() {return Fitness;}
  public void setRFitness(double isum)  {RFitness=Fitness/isum;}
  public void setCFitness(double ix)  {CFitness=ix;}
  public double getRFitness(){return RFitness;}
  public double getCFitness(){return CFitness;}
  public double RandVal(double low,double high)
         {return Math.random()*(high-low)+low;}
  public void survive() {Survivor=true;}
  public void die() {Survivor=false;}
  public boolean isSurvive() {return Survivor;}
  
  public void setGene()
  {for(int j=0;j<NVARS;j++)
      setGene(j);
  }
  
  public void setGene(int val)
  {
      Gene[val]=RandVal(Lower[val],Upper[val]);
  }
  
  public double getGene(int val)
  { return Gene[val];}
  
}//end of class genotype

public class Genetic
{
	// Maximizing a function
	int POPSIZE; //population size
	int MAXGENS; //maximum number of generations;
	int NVARS;   //number of independent variables of function
    double PXOVER; //probability of crossover;
    double PMUTATION; //proportion of mutated variables
    int Generation; //Current generation number
    int NSurvivors; //Number of survivors in a generation
    int Best; //The best genotype in the population
    genotype Population[];
    //f_xj f;  // function to be avaluated by genetic algorithm
    
    public Genetic(int iPOPSIZE,int iMAXGENS,int iNVARS,double iPXOVER,double iPMUTATION)
    {
    POPSIZE=iPOPSIZE;
    MAXGENS=iMAXGENS;
    NVARS=iNVARS;
    PXOVER=iPXOVER;
    PMUTATION=iPMUTATION;
    NSurvivors=0;
    Population=new genotype[POPSIZE+1];
	}
	
	public void setPopulation(double low[],double up[])
	{
	for(int i=0;i<POPSIZE+1;i++)
	  { Population[i]=new genotype(NVARS,low,up);}
	}
	
	public void evaluate(f_xj fi)
	{
	  int mem;
	  int j;
	  double x[]=new double[NVARS];
	  for(mem=0;mem<POPSIZE;mem++)
	  {
	  for(j=0;j<NVARS;j++)	  
	     x[j]=Population[mem].Gene[j];
	  //System.out.println("Fitness value="+Population[mem].Fitness);   
	  Population[mem].Fitness=fi.func(x);
	  //System.out.println("Fitness value1="+Population[mem].Fitness);
	  if(Population[mem].Fitness > Population[POPSIZE].Fitness)
	     {
		 Best=mem;
		 Population[POPSIZE].Fitness=Population[mem].Fitness;    
	     for(j=0;j<NVARS;j++)
	        {
	        Population[POPSIZE].Gene[j]=Population[mem].Gene[j];
		    }//end of for(j=0..
		 }//end of if
	  }//end of for(mem=0;..
	}
	
	public void select()
	{
	int mem;
	double sum=0.0;
	//total fitness of population
	for(mem=0;mem<POPSIZE+1;mem++)
	  {sum+=Population[mem].Fitness;}
	//calculate relative fitness of each genotype
	for(mem=0;mem<POPSIZE+1;mem++)
	  {Population[mem].setRFitness(sum);}
	//calculate cumulative fitness
	  Population[0].setCFitness(Population[0].getRFitness());  
	for(mem=1;mem<POPSIZE+1;mem++)
	  {Population[mem].setCFitness(Population[mem-1].getCFitness()+Population[mem].getRFitness());}
	// select the survivors using cumulative fitness
	for(mem=0;mem<POPSIZE;mem++)
	  {
	  if(Math.random()<=PXOVER)
	     {
	     Population[mem].survive();
		 NSurvivors++;
	     }
	  else
	     Population[mem].die();	 
	  }
	  Population[Best].survive();
	  Population[POPSIZE].survive();    
	}
		
   public void crossover()
   {
   int i,count;
   int mem;
   int POne,a;
   int PTwo,b;
   int point;
   //loop through the population replacing non surviving
   //genotypes using crossover between pairs of survivors
    for(mem=0;mem<POPSIZE;mem++)
        {
        //does this member need to be replaced?
        if(!Population[mem].isSurvive())
           {
           //select two survivors
           a=(int)(Math.random()*NSurvivors)+1;
           b=(int)(Math.random()*NSurvivors)+1;
           count=0;
           POne=0;
           PTwo=0;
           for(i=0;i<POPSIZE+1;i++)
             {
             if(Population[i].isSurvive())
                {
                count++;
                if(count==a) POne=count;
                if(count==b) PTwo=count;
	            }
	         }
	       //Select the crossover point
	       point=(int)(Math.random()* NVARS );
	       //perform a crossover; coppy everything up to the 
	       // crossover point from the first parent
	       for(i=0;i<point;i++)
	         {
	         Population[mem].Gene[i]=Population[POne].Gene[i];
		     }
		   //copy everything after the crossover point from the second parent
	       for(i=point;i<NVARS;i++)
	         {
	         Population[mem].Gene[i]=Population[PTwo].Gene[i];
		     }
		           
	       } 
	    }
   }
   public void mutate()
   {
   int i;
   double lbound,hbound;
   int nmutations;
   int member;
   int var;
   nmutations=(int)((double)(POPSIZE*NVARS*PMUTATION));
   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].setGene(var);
	  }      
   }
   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();
   s="Generation = "+Generation+"best value = "+best_value+"Average = "+avg+"Standart Deviation = "+stdev;   
   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++;
     NSurvivors=1;
     select();
     crossover();
     mutate();
     evaluate(fi);
     if(report)
        System.out.println(report());
     }	 
   return getBest();
   }      
}