genetic.java

A Genetic Algorithm finding Strings. Enter any Word it will search this string using fitness functio

/*****************************************************************
 * Program:   Genetic Algorithm for finding Strings
 * Author:    Mark Rich, [e-mail]
 * Date:      3/30/2000
 ****************************************************************/
//import javabook.*;

/**
 * 
 */
class Genetic {

    public static void main(String[] args) {

		System.out.println("What is the goal word?");
	//Scanner sc = new Scanner(System.in);
	String goal = "Pakistan";

	// Make sure they enter a positive even integer for size
	int size = 100;
	

	final double MUTATION_RATE = .05;

	// Create and initialize the Fitness object with the goal word
	Fitness fit = new Fitness(goal);

	// Randomly initialization of population and make
	// a counter for the generations
	int generation = 0;
	String[] population = new String[size]; 
	for (int i = 0; i < size; i++) {
	    population[i] = fit.getRandomString();
	}

	// Find current best individual in the population
	int bestIndex = fit.findBestIndex(population);
	
	// Pretty formatting for the user so they see what's happening
	System.out.println("Gen\t: " + goal + " : Score");
	System.out.println("------------------------------");

	// Search until you find the goal word
	while (fit.score(population[bestIndex]) != 0) {
	    
	    // Display the best of this generation to screen
	    System.out.print(generation + "\t: " );
	    System.out.println(population[bestIndex] + " : " +
			  fit.score(population[bestIndex]));

	    // Create space for the next generation
	    String[] children = new String[size];

	    // Selection Step: 
	    // choose two members of the current population at random
	    // choose the one with better score to reproduce in the 
	    // next generation.
	    for (int i = 0; i < size; i++) {
		int parent1 = (int)(Math.random() * size);
		int parent2 = (int)(Math.random() * size);
		children[i] = fit.select(population[parent1], 
					 population[parent2]);
	    }

	    // Mutation Step:
	    // mutate a percentage of the children found by selection
	    // based on the MUTATION_RATE
	    for (int i = 0; i < size; i++) {
		if (Math.random() < MUTATION_RATE) {
		    StringBuffer mutant = new StringBuffer(children[i]);
		    fit.mutate(mutant);
		    children[i] = mutant.toString();
		}
	    }

	    // Crossover Step:
	    // take each pair of children and swap some DNA using
	    // the crossover function
	    for (int i = 0; i < size; i+=2) {
		StringBuffer child1 = new StringBuffer(children[i]);
		StringBuffer child2 = new StringBuffer(children[i+1]);
		fit.crossover(child1, child2);
		children[i] = child1.toString();
		children[i+1] = child2.toString();
	    }
	    
	    // The new replace the old, we find the best member of this 
	    // new generation, and increment our generation counter
	    System.arraycopy(children, 0, population, 0, size);
	    bestIndex = fit.findBestIndex(population);
	    generation++;
	}

	// Wrap up the simulation by printing out the goal string
	System.out.println("------------------------------");
	System.out.println(generation + "\t: " + population[bestIndex] +
		      " : Goal Found!");
    }
}