// Genetic Ant Algorithm
// Carl E. Bredlau

// from Koza, _Genetic Programming_,  MIT Press
// programmed modeled after sga.  Thanks to the author.


//02-02-01 Added generation() since Solaris Netscape was acting up

// A Collection of Ants

package geneticAnt;

import java.util.Random;
public class Ants {


   int size;     // of population
   int generation = 0;
   Ant[] pop;	// population

   static float mutate = (float) 0.05;	 
   static float cross  = (float) 0.25;


	public Ants(int size, int states) {

		this.size = size;
		pop = new Ant[size];
		for (int i = 0; i < this.size; i++)
			pop[i] = new Ant(states);
	}



	public void generate(Board b, int moves) {
		 Random r = new Random();
		 IntRandom s = new IntRandom(size);

		 Board test_board;

		int sum_fit = 0;
		int new_size = 0;

		int max_index = 0;

		// this.show();

		Ant[] sample = new Ant[size*3];

     // Copy ants. Calculate fitness.
		for (int i = 0; i < size; i++) {
			sample[i] = pop[i];
			test_board = (Board) b.clone();
			sample[i].walk(test_board,moves);
			sum_fit += sample[i].fitness;
			// System.out.println("*** " + i + 
			//	" Fitness " + sample[i].fitness 
			//	+ " Sum is now " + sum_fit);
			if (sample[i].fitness > sample[max_index].fitness)
				max_index = i;
		}
	// Now mutate
		new_size = size;
		for (int i = 0; i < size; i++) 
			if (r.nextFloat() < mutate) {
				sample[new_size] = pop[i].mutate();
				test_board = (Board) b.clone();
				sample[new_size].walk(test_board,moves);
				sum_fit += sample[new_size].fitness;
				if (sample[new_size].fitness > sample[max_index].fitness)
					max_index = new_size;
				// System.out.println("Mutated..." + i + " to " + new_size
				//	+ "  Sum  " + sum_fit);
				// sample[new_size].show();
				new_size++;
			}
		
	// Now crossover
		for (int i = 0; i < size; i++) 
			if (r.nextFloat() < cross) {
			    int j;
				do {
					j = s.nextInt();
				} while (j == i);
				Ant[] temp = new Ant[2];
				temp = pop[i].crossover(pop[j]);
				sample[new_size] = temp[0];	
				test_board = (Board) b.clone();
				sample[new_size].walk(test_board,moves);	
				sum_fit += sample[new_size].fitness;  
				if (sample[new_size].fitness > sample[max_index].fitness)
					max_index = new_size;
				// System.out.println("Crossed..." + i + " and " + j 
				//	+ "  new size " + new_size + "  Sum  " + sum_fit);
				// sample[new_size].show();

				new_size++;	 
				

				sample[new_size] = temp[1];
				test_board = (Board) b.clone();
				sample[new_size].walk(test_board,moves);	
				sum_fit += sample[new_size].fitness;
				if (sample[new_size].fitness > sample[max_index].fitness)
					max_index = new_size;  
				// System.out.println(" new size " + new_size + "  Sum  " + sum_fit);
 				// sample[new_size].show();

			 	new_size++;
			}

		// Now determine the best
		pop[0] = sample[max_index];
		pop[0].age++;
		// remove this one from consideration
		sum_fit -= sample[max_index].fitness;
		sample[max_index] = null; 

	   // System.out.println(" Best is " + max_index);
	   // Pick the rest using probability fit
		for (int i = 1; i < size; i++) {
			int x = (int) (r.nextFloat()*sum_fit);
			// System.out.println("Sum fit now " + sum_fit + 
			//	" Select num is " + x);

			int j = -1;
			int part_sum = 0;

			do 	{
				j++;
				// System.out.println("*** " + j);	
				if (sample[j] != null) {
				  part_sum += sample[j].fitness;
				 // System.out.println("s  " + sample[j].fitness +"   f " + part_sum);
				}
			}  while( (part_sum <= x) && (j < new_size - 1));

			pop[i] = sample[j];
			pop[i].age++;   // age the ant
			sum_fit -= sample[j].fitness;
	     	sample[j] = null;
			// System.out.println("Selected " + j);
		}
		generation++;
	}

        public int generation() { return generation; }
        // Solaris netscape is acting up....

	 public void show() {
		System.out.println("***** Generation " + generation + " *********");
		for (int i = 0; i < size; i++)
			pop[i].show();
		System.out.println("--------------------");
	 }

	/*  public void show(boolean mem) {
		for (int i = 0; i < size; i++)
			pop[i].show(mem);
	 }

	*/

	public static void main(String args[]) {
		// Paramteters...
		int num_ANTS    = 50;
		int num_STATES  = 8;
		int num_BOARD   = 28;
		int num_MOVES   = 400;

   	
 		Ants pop = new Ants(num_ANTS,num_STATES);
		// pop.show();

		do {
			Board b = new Board(num_BOARD);
			pop.generate(b,num_MOVES);
			pop.show();
			pop.pop[0].show(true);
			pop.pop[0].walk(b,num_MOVES);
			b.show();
		} while (true);
	}					   

					
}