Algorithm Alley
by Girish Keshav Palshikar 

Listing One
// max. no. of neighboring states for a given state
#define MAX_NEIGHBOUR   100     

// external functions assumed (specific to each problem domain)
extern double Cost(STATE *pS);  // returns the cost of given state
extern int Solution(STATE *pS);  // 1 if given state is a solution; else 0 
// generate neighbor states of given state; return no. of neighbor states
extern int GetNeighbours(STATE *pS, STATE Next[MAX_NEIGHBOUR]); 

// hopefully find and return the lowest cost state
// STATE is a problem-specific representation of the structure of a state 
// pS0 and pS are pointers to given initial state and low cost state found. 
int HillClimbing(STATE *pS0, STATE *pS)
{
   STATE Next[MAX_NEIGHBOUR];
   int i, n, index;
   double c0, c, c1;

   if ( Solution(pS0) ) // found
   {
       CopyState(pS,pS0);
       return(1);
   }
   CopyState(pS, pS0); // initialize
   c0 = Cost(pS0);     // cost of initial state
   while ( (n = GetNeighbours(pS,Next)) > 0 ) // get neighbours of s
   {
       index = 0; // index (in Next) of lowest cost neighbour
       c = Cost(&Next[0]);
       for(i = 0; i < n; i++) // do for each neighbour state
       {
       if ( Solution(&Next[i]) ) // found
       {
           CopyState(pS,&Next[i]);
           return(1);
       }
       if ( (c1 = Cost(&Next[i])) < c )
       {
           index = i;
           c = c1;
       }
       } // end for 
       if ( c < c0 ) // found a lower cost neighbour
       {
       CopyState(pS, &Next[index]);
       c0 = c;
       }
       else // reached local maximum
       break;
   } // end while
   return(0); // global solution not found; S contains low cost state found 
}

Listing Two 
/* Module: Simulated Annealing
 * Programmer: Girish Keshav Palshikar
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "simann.h"
#include "sim_app.h"    // problem-specific information needed by SA

// function prototypes 
int NextTemp(TEMP *pt);       
BOOL Boltzmann(ENERGY e1, ENERGY e2, TEMP t);
BOOL CoolEnough(TEMP t); 

// problem-specific functions assumed
extern BOOL NeighbourState(STATE *pS, STATE *pNew);
extern BOOL IsSolution(STATE *pS); // TRUE if state is an acceptable solution
extern ENERGY Energy(STATE *pS); // compute & return cost/energy of state
extern int CopyState(STATE *pDest, STATE *pSrc);

// s0 is the initial state and t0 is the initial temperature
// Limit is the no. of attempts to explore neighbourhoods at a given temp. 
BOOL SimAnneal(STATE *pInit, TEMP t0, int Limit, STATE *pDest)
{
   STATE s;  // current state
   TEMP t;   // current temp.
   ENERGY e, e_new; // energy of current and new state
   BOOL success = FALSE;
   int i;

   CopyState(&s, pInit);  // make current state = initial state
   e = Energy(&s); // compute current energy
   t = t0;
   CopyState(pDest, pInit);  // copy initial state into pDest
   
   while ( !CoolEnough(t) ) 
   {
       if ( IsSolution(&s) ) // done
       {
       success = TRUE;
       break;
       }
       for ( i = 0, success = FALSE; i < Limit; i++ ) 
       {
       if ( !NeighbourState(&s, pDest) ) // generate new state in pDest
           break;   // no more states in the neighbourhood 
       if ( IsSolution(pDest) ) // done
       {
           success = TRUE;
           break;
       }
       e_new = Energy(pDest);
       printf("temp = %lf i = %d e = %lf e_new = %lf\n", t, i, e, e_new); 
       if ( Boltzmann(e, e_new, t) ) // make pDest new current state?
       {    
           CopyState(&s, pDest);
           e = e_new;
       }
       }  // end for
       NextTemp(&t);  // get the next lower temperature
   } // end while          
   CopyState(pDest, &s); // copy last state into pDest
   return(success);
}
BOOL Boltzmann(ENERGY e1, ENERGY e2, TEMP t)
{
   double x;
   if ( e2 < e1 ) return(TRUE);
   x = exp( (-(e2 - e1)) / t );
   if ( x <= 1.0 && rand() < x ) return(TRUE);
   if ( rand() < (x - floor(x)) ) // x > 1, so check decimal fraction of x
       return(TRUE); 
   return(FALSE);
}
// implement cooling schedule; return the next lower temp
int NextTemp(TEMP *pt)       
{
    TEMP t1 = (*pt);
    (*pt) = t1 * TEMP_FACTOR;
    return(0);
}
// true if given temp < a fixed threshold; stop condition for SA 
BOOL CoolEnough(TEMP t) 
{ 
   if ( t < MIN_TEMP ) return(TRUE);
   return(FALSE);
}

Listing Three
/* Module: Simulated Annealing
 * File: simann.h
 * Programmer: Girish Keshav Palshikar
*/
#ifndef SIMANN_H
#define SIMANN_H

typedef double TEMP;
typedef double ENERGY;
typedef enum { FALSE = 0, TRUE = 1 } BOOL;

#define MAX_TEMP           5000.0
#define MIN_TEMP           1.0
#define BOLTZMANN_CONSTANT 1.0
#define TEMP_FACTOR        0.5

#endif



3