santafeants.java

aco algorithm for santafe trail

// Author: Linda MacPhee-Cobb 2008
// http://www.herselfsai.com/2008/06/santafe-ant-trail.html


//  Simple demo of SantaFe Ant problem in genetic life
//  Creative Commons Non Commercial Share Alike 3.0

//  89 bits of food are laid out in a trail for the ants.
//  See webpage for more details
//  best score so far for me is 69

import java.awt.*; 
import java.awt.event.*; 
import java.util.*;


//Main sets up simulation window and jump starts program
public class SantaFeAnts extends Frame implements Runnable, WindowListener 
{ 

    int dim = 670;												// window size
	int max = 670;												// allow for title bars and margins
	int max_ants = 300;											// constant population
	int max_days = 400;											// steps to take per ant per generation
	int max_generations = 500;									// how many generations
	int max_scores = max_ants/10;								// top scorers
	int current_generation = 0;
	int current_average_score = 0;
	int state_machine_length = 12;								// amount of instructions ants store
							
    Thread animThread;											// to continuously call repaint();
    long delay = 0L;											// speed up or slow down animation here - larger is slower but may miss updates so critters jump
	boolean world_created = false;								// don't start drawing loop till we get ourselves setup
	int number_ants_to_view = max_ants;							// how many ants show we view in animation all or just a few
	
	int SantaFeTrail[][] = new int[32][32];						// SantaFe food trail
	Ant ants[] = new Ant[max_ants];								// Ants
	Ant top_scorers[] = new Ant[max_ants/10];
	
	Random random = new Random ( System.currentTimeMillis() );	// jump start random number generator
	

	
    public static void main(String[] args) 
    { 
		new SantaFeAnts(); 
    } 
    
    
    // initialize things then tell the animation to start 
    public SantaFeAnts() 
    { 	
		//create a window ----------------------------------------------------------------------------
		super ( "  SantaFeAnts  " );							//title
		setBounds ( 0, 0, dim, dim );							//window size
		setVisible ( true );									//window interaction stuff....
		addWindowListener ( this );								// allows user to close window and stop program in gui
		
		
		//  Set up Santa Fe Trail --------------------------------------------------------------------
		for ( int i=0; i<32; i++){
			for ( int j=0; j<32; j++){
				SantaFeTrail[i][j] = 0;
			}
		}
		
		SantaFeTrail[1][0] = 1;
		SantaFeTrail[2][0] = 1;
		SantaFeTrail[3][0] = 1;

		SantaFeTrail[3][1] = 1;
		SantaFeTrail[3][2] = 1;
		SantaFeTrail[3][3] = 1;
		SantaFeTrail[3][4] = 1;
		SantaFeTrail[3][5] = 1;
		
		SantaFeTrail[4][5] = 1;
		SantaFeTrail[5][5] = 1;
		SantaFeTrail[6][5] = 1;
		
		SantaFeTrail[8][5] = 1;
		SantaFeTrail[9][5] = 1;
		SantaFeTrail[10][5] = 1;
		SantaFeTrail[11][5] = 1;
		SantaFeTrail[12][5] = 1;
		
		SantaFeTrail[12][6] = 1;
		SantaFeTrail[12][7] = 1;
		SantaFeTrail[12][8] = 1;
		SantaFeTrail[12][9] = 1;
		
		SantaFeTrail[12][11] = 1;
		SantaFeTrail[12][12] = 1;
		SantaFeTrail[12][13] = 1;
		SantaFeTrail[12][14] = 1;
		
		SantaFeTrail[12][17] = 1;
		SantaFeTrail[12][18] = 1;
		SantaFeTrail[12][19] = 1;
		SantaFeTrail[12][20] = 1;
		SantaFeTrail[12][21] = 1;
		SantaFeTrail[12][22] = 1;
		SantaFeTrail[12][23] = 1;
		
		SantaFeTrail[11][24] = 1;
		SantaFeTrail[10][24] = 1;
		SantaFeTrail[9][24] = 1;
		SantaFeTrail[8][24] = 1;
		SantaFeTrail[7][24] = 1;
		
		SantaFeTrail[4][24] = 1;
		SantaFeTrail[3][24] = 1;
		
		SantaFeTrail[1][25] = 1;
		SantaFeTrail[1][26] = 1;
		SantaFeTrail[1][27] = 1;
		SantaFeTrail[1][28] = 1;
		
		SantaFeTrail[2][30] = 1;
		SantaFeTrail[3][30] = 1;
		SantaFeTrail[4][30] = 1;
		SantaFeTrail[5][30] = 1;
		
		SantaFeTrail[7][29] = 1;
		SantaFeTrail[7][28] = 1;
		
		SantaFeTrail[8][27] = 1;
		SantaFeTrail[9][27] = 1;
		SantaFeTrail[10][27] = 1;
		SantaFeTrail[11][27] = 1;
		SantaFeTrail[12][27] = 1;
		SantaFeTrail[13][27] = 1;
		SantaFeTrail[14][27] = 1;
		
		SantaFeTrail[16][26] = 1;
		SantaFeTrail[16][25] = 1;
		SantaFeTrail[16][24] = 1;
		
		SantaFeTrail[16][21] = 1;
		SantaFeTrail[16][20] = 1;
		SantaFeTrail[16][19] = 1;
		SantaFeTrail[16][18] = 1;
		
		SantaFeTrail[17][15] = 1;
		
		SantaFeTrail[20][14] = 1;
		SantaFeTrail[20][13] = 1;
		
		SantaFeTrail[20][10] = 1;
		SantaFeTrail[20][9] = 1;
		SantaFeTrail[20][8] = 1;
		SantaFeTrail[20][7] = 1;
		
		SantaFeTrail[21][5] = 1;
		SantaFeTrail[22][5] = 1;
		
		SantaFeTrail[24][4] = 1;
		SantaFeTrail[24][3] = 1;
		
		SantaFeTrail[25][2] = 1;
		SantaFeTrail[26][2] = 1;
		SantaFeTrail[27][2] = 1;
		
		SantaFeTrail[29][3] = 1;
		SantaFeTrail[29][4] = 1;
		
		SantaFeTrail[29][6] = 1;
		
		SantaFeTrail[29][9] = 1;
		
		SantaFeTrail[29][12] = 1;

		SantaFeTrail[28][14] = 1;
		SantaFeTrail[27][14] = 1;
		SantaFeTrail[26][14] = 1;
		
		SantaFeTrail[23][15] = 1;
		
		SantaFeTrail[24][18] = 1;
		
		SantaFeTrail[27][19] = 1;
		
		SantaFeTrail[26][22] = 1;

		SantaFeTrail[23][23] = 1;


		// create ants  ----------------------------------------------------------------
		for ( int i=0; i<max_ants; i++){
			ants[i] = new Ant( SantaFeTrail, random );
		}

		//  load up init values in top scorers  ----------------------------------------
		for ( int i=0; i<max_scores; i++){
			top_scorers[i] = new Ant ( SantaFeTrail, random );
		}
		
		// start animation loop --------------- ----------------------------------------		
		animThread = new Thread ( this );						// main program thread.
		animThread.start();


	
    } 
    


	//****************************************************************************************************
	// main program loop    
	public synchronized void run() 
    { 
		current_generation = 0;

		try{
			
			while ( current_generation < max_generations){	// for each generation

				int j=0;
				while ( j<max_days ){						// for each day

					for ( int k=0; k<max_ants; k++){		// move each ant one state
						ants[k].move(j);
					}

					repaint( delay );						// request redraw 
					wait();									// wait for redraw 
					j++;									// next day
				}
				
				sort();										// sort ants high score to low score
				print();									// print info to command line
				generation();								// mate and reset trail and food scores
				current_generation++;						// next generation
			}
		
		} catch( Exception ex ) { System.err.println( "Error: " + ex ); } 
		
    } 
	//****************************************************************************************************


	// generational stuff to do at end of each generation
	void generation()
	{
		
		// mate fittest half of population  1&2, 2&3, 3&4 ....
		int array_middle = max_ants/2;
		for ( int j=0; j< array_middle; j++){
			Ant a = ants[j];
			Ant b = ants[j+1];
			ants[array_middle + j] = a.mate( a, b, SantaFeTrail, random );	// add new beings to bottom of array, overwriting lesser creatures
		}
		
		
		// mix things up a bit
		int mix = 10;
		for ( int q=mix; q<max_ants; q+=mix )
		{	
			ants[q] = ants[q].adjust_dna( ants[q], random );
		}					
					
									
																							
		// re-set food to zero for all ants and reset SantaFeTrail for all ants, and start everyone facing east
		for ( int j=0; j<max_ants; j++){
			ants[j].food = 0;
			ants[j].d = 1;	
			ants[j].x = 0;
			ants[j].y = 0;	
								
			for ( int k=0; k<32; k++){				// lay out the food trail
				for ( int l=0; l<32; l++){
					for ( int m=0; m<32; m++){
						ants[j].santa_fe[l][m] = SantaFeTrail[l][m];
					}
				}
			}
				
		}
	}
	
	
	
	
	
	
	//    ***********    helper functions ****************************************************************
	

	
	
	

    //print results to screen
	void print()
	{
	
		System.out.println  ( " New Generation " + current_generation + " ###  food ahead   ##########  Average = " + current_average_score + "  ###   no food ahead   ###########"  );

		int fitness = 0;
		
		for ( int i=0; i<max_scores; i++){       //just print top scorers
		
			System.out.print ( " Ant " + i +  ":  " );
			Ant a = ants[i];
			for ( int j=0; j<state_machine_length; j++){
				System.out.print ( "  " + a.if_food_ahead[j] );
			}
			System.out.print ( "   ***   " );
			for ( int j=0; j<state_machine_length; j++){