/*
 * SimAnnealing.java
 * Created on Mar 28, 2005
 */
package search;

import java.util.Random;

/**
 * Simulated annealing of a spin glass.
 */
public final class SimAnnealing {
    
    private static final Random rand = new Random();
    private static final int NUM_SPINS = 100;
    private static final int MAX_ITERATIONS = 10000;
    private static final double[] COOLING_RATES = {0.1, 0.01, 0.001};

    private SimAnnealing() {}
    
    private static void simAnnealing(SpinGlass spinGlass, double coolingRate) {
        double currentEnergy = spinGlass.energy();
        
        for (int t = 1; t <= MAX_ITERATIONS ; t++) {
            int randSpin = rand.nextInt(spinGlass.size());
            spinGlass.flip(randSpin);
            double newEnergy = spinGlass.energy();
            double deltaEnergy = newEnergy - currentEnergy;
            
            // energy decreases, accept
            if (deltaEnergy < 0) {
                // if energy doesn't decrease too much, stop
                if (deltaEnergy > -.0001) return;
                currentEnergy = newEnergy;
            }
            // otherwise, accept with probability p
            else {
                double p = Math.exp(-coolingRate * t * deltaEnergy);
                if (rand.nextDouble() < p) {
                    currentEnergy = newEnergy;
                } else {
                    spinGlass.flip(randSpin);
                }
            }
            
        }
    }
    
    public static void main(String[] args) {
        
        boolean[] spins = new boolean[NUM_SPINS];
        double[] energies = new double[NUM_SPINS];
        double minEnergy = 0;
        
        for (int i = 0; i < NUM_SPINS; i++) {
            spins[i] = rand.nextBoolean();
            energies[i] = rand.nextGaussian();
            minEnergy -= Math.abs(energies[i]);
        }
        
        System.out.println("min energy: " + minEnergy);
        
        for(int i = 0; i < COOLING_RATES.length; i++) {
            System.out.println();
            System.out.println("cooling rate:" + COOLING_RATES[i]);
            SpinGlass spinGlass = new SpinGlass(spins, energies);
            System.out.println("start energy: " + spinGlass.energy());
            simAnnealing(spinGlass, COOLING_RATES[i]);
            System.out.println("final energy: " + spinGlass.energy());
        }
    }

}