/*-------------------------------------------------------------

Copyright (C) 2000 Peter Clote, Sebastian Will. 
All Rights Reserved.

written by Peter Clote
modified by Sebastian Will

Permission to use, copy, modify, and distribute this
software and its documentation for NON-COMMERCIAL purposes
and without fee is hereby granted provided that this
copyright notice appears in all copies.


THE AUTHOR AND PUBLISHER MAKE NO REPRESENTATIONS OR
WARRANTIES ABOUT THE SUITABILITY OF THE SOFTWARE, EITHER
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHORS
AND PUBLISHER SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED
BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
THIS SOFTWARE OR ITS DERIVATIVES.

-------------------------------------------------------------*/


/*-----------------------------------
   MonteCarlo
   P. Clote, Feb 1999

This class implements a MonteCarlo algorithm with
simulated annealing, in order
to determine the minimum of a function
   f : {0,1,2,...,2^n-1}  ---> Reals
where n = NumBits, a constant. 
-------------------------------------*/



class MonteCarlo {
   static final int NumBits = 7;
   static final int MAX = (int) Math.pow(2,NumBits);
             // equals 2^NumBits 

   /*--------------------------------
     F is the function, whose minimum we want
     to compute. This function can be changed.
   --------------------------------*/
   static double F(int x) { 
      return (Math.pow(x,4)*Math.sin(x)-10*Math.pow(x,3)-20);
   }   

   static void printFunctionValues() {
       System.out.println("\n\nFunction Values \n");
       for (int i=0;i<MAX;i++)
	   System.out.println("F("+i+") = "+F(i));
   }


   public static void main ( String argv[] ) {
   
      /*-----  variable declarations ------*/
      int i,j,k,m; 
      int x,y; // integers in {0,...,MAX-1}
      double z; // random in (0,1) for Boltzmann probability
      int M=0; 
            //  counter for Monte-Carlo moves in loop 
   

      /*-- command line argument inputs --**/
      if ( argv.length != 2 ) 
        {
        System.out.println("Parameters:  Temp NumIntervals");
        System.exit(1);
        }
      double T = (double) Integer.parseInt(argv[0]);
         // temperature
      int numSteps = Integer.parseInt(argv[1]);
      
      M = 0;
      x = (int) (Math.random()*MAX);
        // x is random initial value in {0,...,MAX-1}
      while ( T > 1 ) {
         for (i=0;i<numSteps;i++) {
            y = randomNhbor(x,NumBits);
            if (F(y) < F(x)) 
              x=y;  
                 // greedy step to find function min 
            else  {
              z=Math.random();
                 // random in (0,1) 
              if (z < Math.exp(-( F(y) - F(x) )/T ))
                  x=y;
              }   // Metropolis step 
            M++;  // increment step counter 
            } // end of for-loop
            T *= 0.9; // decrement temperature
         }  // end of while-loop


    System.out.println("Minimum found: F(" 
          + x + ") = " + F(x));
    System.out.println("Number of MonteCarlo steps: "
          + M);

    printFunctionValues(); 
          // can plot F(x) using gnuplot
    } // end of main 
  
      
    
    
    /*------------------------------------------------------
    Generate a random number y of Hamming distance 1 
    from input x, where |y| <= len.
    ------------------------------------------------------*/
    static int randomNhbor(int x,int len) {
       int k;
       k = (int)(Math.random()*len);
          // k is a random integer in range {0,...,len-1}
      
       return (x^(1<<k));
          //  x has its k-th bit toggled 
    }
    
    
    
} // end of class MonteCarlo



/*---------------------------------------
SAMPLE Output:
java MonteCarlo 10 10
Minimum found: F(43) = -3638762.3218733943
Number of MonteCarlo steps: 220

java MonteCarlo 10 1000
Minimum found: F(105) = -1.2954544029853348E8
Number of MonteCarlo steps: 22000

java MonteCarlo 100 1000
Minimum found: F(49) = -6674704.246380456
Number of MonteCarlo steps: 44000
---------------------------------------*/