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

/////////////////////////////////////////////////////////////////////
//                                                                 //
//  Galaxy-based search algorithm  by Hamed Shah-Hosseini          //
//                                                                 //
//  Faculty of Electrical and Computer Engineering,                //
//  Shahid Beheshti University, G.C., Tehran, Iran                 //
//                                                                 //
//  Referance : Principal components analysis by the galaxy-based  //
//              search algorithm: a novel metaheuristic for        //
//              continuous optimisation                            //
//                                                                 //
/////////////////////////////////////////////////////////////////////

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[]);
}


public class galaxy_based_search
{

double a;
double chaosvar;
int ndim;
int discardcount;
double xmin[];
double xmax[];
double[] SG;
int maxiter;
double x[];
double sl[];
double su[];
f_xj ff;
boolean flag;
double[] snext;
double[] teta;
double[] ss;
double[] Snext;


      public galaxy_based_search(f_xj iff,int idiscardcount,double ixmin[],double ixmax[],int imaxiter)
      {
	  a=4.0;      
	  chaosvar=0.19;
	  ndim=ixmin.length;    
	  maxiter=imaxiter;
	  discardcount=idiscardcount; 
	  SG=new double[ndim];    
	  x=new double[maxiter];
	  xmin=ixmin;
	  xmax=ixmax;
	  sl=new double[ndim];
	  su=new double[ndim];
	  snext=new double[ndim];
	  teta=new double[ndim];
	  ss=new double[ndim];
	  Snext=new double[ndim];
	  ff=iff;
	  double drmax=1.0;
	  double dsmax=10.0;
	  double dr,ds;
	  double[][] LSdepo=new double[2][ndim];
	  double[][] SCMdepo=new double[3][ndim];
	  
	  SG=random(xmin,xmax); // initilaize  variables
	 
	  
	  x[0]=ff.func(SG); // first fitness value
	  
	  
	      for(int i=0;i<discardcount;i++)
	      {chaosvar=NextChaos(chaosvar);}
	    
		  LSdepo=LocalSearch(SG,chaosvar);
		  
		  for(int i=0;i<ndim;i++)
		  {
			  SG[i]=LSdepo[0][i];
		  }
		      chaosvar=LSdepo[1][0];
		 
		  flag=false;
		  
		    
		 for(int t=1;t<maxiter;t++) 
		 { 
			  
			  SCMdepo=SpiralChaosMove(SG,chaosvar);
			  
			  for(int i=0;i<ndim;i++)
			  {
				 SG[i]=SCMdepo[0][i];
			  }
			  chaosvar=SCMdepo[1][0];
			  flag=boolval(SCMdepo[2][0]);
			  
			  
			  chaosvar=NextChaos(chaosvar);
			  dr=drmax*chaosvar;
	          
			  if(dr<0.01)
			  {dr=0.01;}
			  
			  if(flag==true)
			  {LSdepo=LocalSearch(SG,chaosvar);
		  
		       for(int i=0;i<ndim;i++)
		       {
			     SG[i]=LSdepo[0][i];
		       }
		      chaosvar=LSdepo[1][0];
		      }
			  chaosvar=NextChaos(chaosvar);
			  
			  ds=dsmax*chaosvar;
			  if(ds<0.00000001)
			  {ds=0.00000001;}
			  
			  x[t]=ff.func(SG);
			  
			  if(Math.abs(x[t]-x[t-1])<=0.0001)
			  {
				ds = dsmax;
                dr = drmax;   
			  }
			  
	     }
		  
		  System.out.println(x[maxiter-1]);
		  System.out.println(Matrix.toString(SG));
		  
		  
		  
		  
		  
	  }

          public double NextChaos(double chaosvar)
          {
	      return a*chaosvar*(1-chaosvar);
	      }

          public double[] random(double xmin[],double xmax[])
          {
	        for(int i=0;i<ndim;i++)
	        {
		     SG[i]=xmin[i]+(xmax[i]-xmin[i])*Math.random();     
		    }  
	          
		   return SG; 
	      }

          public double[][] LocalSearch(double S[],double chaosvar)
          {
	        sl=S;  
	        su=S;
	        boolean endproc=false;
	        int i=ndim-1;
	        int direct=0;
	        int k=1;
	        int j;
	        double ds=0.0001;
	        double chaosvar2=chaosvar;     
	        
	        
	             while(i>=0)
	             {
		             j=1;
		             
		                while(true)
		                {
			               sl[i]=S[i]-(j*ds);    
			                
			               if(sl[i]>xmax[i])
			               {
				           sl[i]=xmax[i];    
				           } 
			               else if(sl[i]<xmin[i])
			               {
				           sl[i]=xmin[i];   
				           } 
			                
			               su[i]=S[i]+(j*ds); 
			                
			               if(su[i]>xmax[i])
			               {
				           su[i]=xmax[i];    
				           } 
			               else if(su[i]<xmin[i])
			               {
				           su[i]=xmin[i]; 
				           }
			               
			               if(ff.func(S)<ff.func(su) && ff.func(S)<ff.func(sl))
				           {
					       endproc=true;
					       break;    
					       }
				           
				              if(ff.func(su)<ff.func(S))
					          {
						       S[i]=su[i];    
						       sl[i]=S[i];
						        
						            if(direct==1)
						            {
							         j+=0.0001;    
							        }else{    
						            j=1; 
					                }
						         
						            k=1;
						            direct=1;
	                          }
					          else if(ff.func(sl)<ff.func(S))
					          {
						      S[i]=sl[i];    
						      su[i]=S[i];    
						             
                                     if(direct==-1)
                                     {
	                                     j+=0.0001;
	                                 }else{
		                             j=1;    
	                                 }    						      
						         k=1;
						         direct=-1; 
						      } 
					          else
					          {
						      j+=0.05;    
						      k++;
						      }
					          
					      if(k>=150)
						  {break;}    
						             
				        }
		             
		             su[i]=S[i];
		             sl[i]=S[i];
		             i--;
		          }
	             
	             double[][] depo=new double[2][ndim];
		         for(int ii=0;ii<ndim;ii++)
		         {
			     depo[0][ii]=S[ii];    
			     } 
		         depo[1][0]=chaosvar2;
		         
		         return depo; 
		          
	      }

 
	      public double[][] SpiralChaosMove(double S[],double chaosvar)
	      {
		   double r=0.0001;   
		   double  chaosvar2=chaosvar;
		   for(int i=0;i<ndim;i++)
		   {
			 chaosvar2=NextChaos(chaosvar2);
			 teta[i]=(2*chaosvar-1)*Math.PI;  
			 snext[i]=S[i];
		   }   
		      flag=false;
		      int k=1;
		        while(k<150 && flag==false)
		        {
			        for(int i=0;i<ndim;i++)
			        {
				    ss[i]=r*Math.cos(teta[i]);  
				    }
			        
			        for(int i=0;i<ndim;i++)
			        {
				     chaosvar2=NextChaos(chaosvar2);   
				     snext[i]=S[i]+ss[i]*chaosvar2; 
				      
				        if(snext[i]>xmax[i])
				        {
					    snext[i]=xmax[i];    
					    }
				        else if(snext[i]<xmin[i])
				        {
					    snext[i]=xmin[i];    
					    }  
		             
			        
			            if(ff.func(snext)<ff.func(S))
			            {
				        Snext=snext;   
				        flag=true;
				        break;   
				        }
			            
				        chaosvar2=NextChaos(chaosvar2);
			            snext[i]=S[i]-ss[i]*chaosvar2;
			            
			            if(snext[i]<xmin[i])
			            {
				          snext[i]=xmin[i];  
				        }
				        else if(snext[i]>xmax[i])
			            {
				          snext[i]=xmax[i];  
				        }
			    
				        if(ff.func(snext)<ff.func(S))
			            {
				        Snext=snext;   
				        flag=true;
				        break;   
				        }
				        
				         snext[i]=S[i];
				     }
		      
		        r+=1;//dr
		        for(int i=0;i<ndim;i++)
		        {
			    teta[i]+=0.001;//dt
			      if(teta[i]>Math.PI)  
			        {teta[i]=-Math.PI;}
			    }
		      k++;  
		  }
	      double[][] depo=new double[3][ndim];
		  for(int i=0;i<ndim;i++)
		  {depo[0][i]=snext[i];}
		  depo[1][0]=chaosvar2;
		  depo[2][0]=doubleval(flag);
	      
	      return depo;
	      
} 

           public double doubleval(boolean bool)
           {
	            if(bool==true)
	            {return 1.0;}
	            else
	            {return 0.0;}         
	       
	       }

           public boolean boolval(double doub)
           {
	              if(doub==1.0)
	              {return true;}
	              else
	              {return false;}    
	           
	       }
}