import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.ArrayList;

//////////////////////////////////////////////////////
//Enginnering Optimisation by Cuckoo Search         //
//                                                  //
//            Xin-She Yang           Suash Deb      //
////////////////////////////////////////////////////// 

//REFERANCE
//Papers -- Citation Details:
// 1) X.-S. Yang, S. Deb, Cuckoo search via Levy flights,
// in: Proc. of World Congress on Nature & Biologically Inspired
// Computing (NaBIC 2009), December 2009, India,
// IEEE Publications, USA, pp. 210-214 (2009).
//http://arxiv.org/PS_cache/arxiv/pdf/1003/1003.1594v1.pdf
// 2) X.-S. Yang, S. Deb, Engineering optimization by cuckoo search,
//Int. J. Mathematical Modelling and Numerical Optimisation,
//Vol. 1, No. 4, 330-343 (2010).
//http://arxiv.org/PS_cache/arxiv/pdf/1005/1005.2908v2.pdf
abstract class f_xj
{
abstract double func(double x[]);
}

public class cuckoo_search1
{
int n;
int nd;
double pa;
double tol;
double nest[][];
double xmin[];
double xmax[];
f_xj ff;

      public cuckoo_search1(f_xj iff,int in,double ipa,double itol,double ixmin[],double ixmax[])
      {
	  n=in;    
	  nd=ixmin.length;    
	  pa=ipa;
	  tol=itol;
	  nest=new double[n][nd];
	  xmin=new double[nd];
	  xmax=new double[nd];
	  ff=iff;
	  double[] one=ones();
	  for(int i=0;i<nd;i++)
	  {xmin[i]=ixmin[i];xmax[i]=ixmax[i];}
	  }
	
	  double[] randn()
	  {
	  double a[]=new double[nd];
	  for(int i=0;i<nd;i++)
	  {a[i]=Math.random();}
	  return a;	  
	  }
	  
	  double[] ones()
      {
	  double v[]=new double[nd];     
	  for(int i=0;i<nd;i++)
	  {v[i]=1.0;}
	  return v;    
	  } 
	  	  
	  double [][][] initialize()
	  {
	  for(int i=0;i<n;i++)
	  {for(int j=0;j<nd;j++)
	      {nest[i][j]=xmin[j]+((xmax[j]-xmin[j])*Math.random());}
	  } 	  
	  double[] fitness=new double[n];
	  for(int i=0;i<n;i++)
	  {fitness[i]=Math.pow(10,7);}
	  double dp [][][]=new double [2][n][nd];
	  for(int i=0;i<n;i++)
	  {  for(int j=0;j<nd;j++)   
	     {dp[0][i][j]=nest[i][j];}  
	  }
	  for(int i=0;i<n;i++)
	  {dp[1][i][0]=fitness[i];}
	  return dp;
	  }
	
	  double logGamma(double x) 
	  {
      double tmp =(x-0.5)*Math.log(x+4.5)-(x+4.5);
      double ser = 1.0 + 76.18009173    / (x + 0)   - 86.50532033    / (x + 1)+ 24.01409822    / (x + 2)   -  1.231739516   / (x + 3)+  0.00120858003 / (x + 4)   -  0.00000536382 / (x + 5);
      return tmp + Math.log(ser * Math.sqrt(2 * Math.PI));
      }
      double gamma(double x) { return Math.exp(logGamma(x)); }
	
	
     double[] getminval_index(double[] a)
	 {
	 double m=0.0;	 
	 double b[]=new double[a.length];
	 for(int i=0;i<a.length;i++)
	 {b[i]=a[i];}  
	 double minval=a[0];
	 for(int i=0;i<a.length;i++)
	 {if(a[i]<minval){minval=a[i];}}
	 for(int i=0;i<a.length;i++)
	 {if(b[i]==minval){m=i;break;}};
	 double[] dep=new double[2];
	 dep[0]=minval;
	 dep[1]=m;
	 return dep;	 
	 } 
	 
	 double[][][] get_best_nest(double[][] nest,double[][] newnest,double[] fitness)
	 {
	 double fnew=0.0; 	 
	   for(int j=0;j<n;j++)
	   {
	     fnew=ff.func(newnest[j]);
	     if(fnew<fitness[j])
	     {fitness[j]=fnew;nest[j]=newnest[j];}	   
	   }
	   double[] dep=getminval_index(fitness); 
	   double fmin=dep[0];
	   int index=(int)dep[1];
	   double[] best=new double[nd];	 
	   for(int i=0;i<nd;i++)
	   {best[i]=nest[index][i];}
	   double depp[][][]=new double[4][n][nd];	 
	   depp[0][0][0]=fmin;
	   for(int i=0;i<n;i++)
	   {depp[1][i][0]=fitness[i];}
	   for(int i=0;i<nd;i++)
	   {depp[2][0][i]=best[i];}
	   for(int i=0;i<n;i++)
	   {for(int j=0;j<nd;j++)
	       {depp[3][i][j]=nest[i][j];} 	   
	   }
	   return depp;	 
	 }
	 // Random permutation of matrix
	 double[][] randperm(double a[][])
	 {
	 double y[][]=new double[a.length][a[0].length];
	 double[] sw=new double[a[0].length];
	 for(int i=0;i<a.length;i++)
	 {y[i]=a[i];}
	 int m=a.length;
	 int rp=0;
	 for(int i=0;i<m-1;i++)
	 	 {rp=(int)((m-i)*Math.random()+i);sw=y[i];
		 y[i]=y[rp];y[rp]=sw;	 
		 }
	 return y;	 
	 }	 	 
	 double[][] get_cuckoos(double[][] nest,double best[])
	 {
	 double[] s=new double[nd];	 
	 double[] u=new double[nd];
	 double[] v=new double[nd];
	 double[] step=new double[nd];
	 double[] stepsize=new double[nd];	 
	 double beta=1.5; 	 
	 double sigma=Math.pow((gamma(1+beta)*Math.sin(3.1415*beta/2.0)/(gamma((1.0+beta)/2.0)*beta*Math.pow(2.0,(beta-1.0)/2.0))),(1.0/beta)); 
	 double[] sk=new double[nd];
	 Random rndm=new Random();
	 for(int j=0;j<n;j++)
	 {
	 s=nest[j]; 
	   for(int i=0;i<nd;i++)
	   {u[i]=(rndm.nextGaussian())*sigma;
		v[i]=(rndm.nextGaussian());
		step[i]=u[i]/Math.pow((Math.abs(v[i])),(1/beta) );
		stepsize[i]=0.01*step[i]*(s[i]-best[i]);
		} 	 
		for(int k=0;k<nd;k++)
		{sk[k]=stepsize[k]*rndm.nextGaussian();
		 s[k]=sk[k]+s[k];
		}
		nest[j]=simplebounds(s);		 
	 }
	 return nest;
	 }	 
	 double[] simplebounds(double s[])
	 {
	   for(int i=0;i<nd;i++)
	   {if(s[i]<xmin[i])
	    {s[i]=xmin[i];}
	    if(s[i]>xmax[i])
	    {s[i]=xmax[i];}
	   }	 
	   return s;	 
	 }
	 double[][] emptynests(double[][] nest)
	 {
		 double[][] K=new double[n][nd];
	     double[][] randmat=new double[n][nd];
		 double[] perm1=new double[n];
		 double[] perm2=new double[n];
		 double[][] nest1=new double[n][nd];
		 double[][] nest2=new double[n][nd];
		 double[][] nest3=new double[n][nd];
		 double[][] nest4=new double[n][nd];
		 double[][] stepsize=new double[n][nd];
	     double[][] randmat2=new double[n][nd];
		 double[][] newnest=new double[n][nd];
	     for(int i=0;i<n;i++)
	     {for(int j=0;j<nd;j++)
		    {randmat[i][j]=Math.random();
		    if(randmat[i][j]<pa){K[i][j]=0.0;}
		    if(randmat[i][j]>pa){K[i][j]=1.0;}
		    }    
		 }		
		 for(int i=0;i<n;i++)
		 {for(int j=0;j<nd;j++)
		    {nest1[i][j]=nest[i][j];nest2[i][j]=nest[i][j];}}
		 nest3=Matrix.substract(randperm(nest1),randperm(nest2));
		 for(int i=0;i<n;i++)
		 {for(int j=0;j<nd;j++)
		   {stepsize[i][j]=nest3[i][j]*Math.random();}}
		   nest4=Matrix.dotproduct(stepsize,K);
		   newnest=Matrix.add(nest,nest4);
		   return newnest;		 
	 }	 
	 void solution()
	 { 
	 double nestt[][]=new double[n][nd];	 
	 double fitness[]=new double[n];
	 double bestnest[]=new double[nd];
	 double best[]=new double[nd];
	 double newnest[][]=new double[n][nd];
	 double d1[][][]=initialize();
	 for(int i=0;i<n;i++)
	 {for(int j=0;j<nd;j++)
	    {nestt[i][j]=d1[0][i][j];}
	 }  	 
	 for(int i=0;i<n;i++)
	 {fitness[i]=d1[1][i][0];}
	 double d2[][][]=get_best_nest(nestt,nestt,fitness);	 
	 double fmin=d2[0][0][0]; 
	    for(int i=0;i<n;i++)
	    {fitness[i]=d2[1][i][0];}
	    for(int i=0;i<nd;i++)
	    {bestnest[i]=d2[2][0][i];}	 
		for(int i=0;i<n;i++)
		{   for(int j=0;j<nd;j++)
		   {nestt[i][j]=d2[3][i][j];}}
		int iter=0;
		double fnew=0.0;
		nestt=emptynests(nestt);
		//System.out.println(Matrix.toString(nestt));
		while(fmin>tol)
		{
			newnest=get_cuckoos(nest,bestnest);
			double d3[][][]=get_best_nest(nestt,newnest,fitness);	 
	        fnew=d3[0][0][0]; 
	        for(int i=0;i<n;i++)
	        {fitness[i]=d3[1][i][0];}
	        for(int i=0;i<nd;i++)
	        {best[i]=d3[2][0][i];}	 
		    for(int i=0;i<n;i++)
		    {for(int j=0;j<nd;j++)
		      {nestt[i][j]=d3[3][i][j];}
		    }
		    iter+=n;
			newnest=emptynests(nestt);
			//System.out.println(Matrix.toString(nestt));
			double d4[][][]=get_best_nest(nestt,newnest,fitness);	 
	         fnew=d4[0][0][0]; 
	        for(int i=0;i<n;i++)
	        {fitness[i]=d4[1][i][0];}
	        for(int i=0;i<nd;i++)
	        {best[i]=d4[2][0][i];}	 
		    for(int i=0;i<n;i++)
		    {for(int j=0;j<nd;j++)
		      {nestt[i][j]=d4[3][i][j];}
		    }
			iter+=n;
			if(fnew<fmin)
			{fmin=fnew;bestnest=best;}
		}		
		System.out.println("Optimum value of a function = "+fmin);		
		for(int i=0;i<bestnest.length;i++)
		{System.out.println("x["+i+"] = "+bestnest[i]);}		
	}
}