evolver.java

This program is using Genetic Algorithm to solve the Travlling Salesman Problem. It gives the bes

/* 
 * 
 * 
 * This program is using Genetic Algorithm to solve the Travlling 
 * Salesman Problem. It gives the best path route within a specified 
 * time.
 * 
 * usage: java Evolver <seconds> <city file> <config file>
 * 
 * Author:		Liu Yang 	
 * 
 *  			20/04/2006
 *  
 * */




import java.io.*;
import java.util.*;


public class Evolver{
	
    private static GATimer timer = new GATimer();
	
    private static int seconds;
    private static CityMap citymap = new CityMap();
    private static int[] best_result = null;    
    
    private static int chromosome_size;
    private static int population_size;
    private static int num_generations;
    private static boolean roulette;
    private static boolean single_crossover;
    private static int mutation_type;
    private static double crossover_probability;
    private static double mutation_probability;
    
    public static void main(String[] args){
    		timer.start();
    		if (args.length != 3) {
    			System.out.println("Usage: ");
    			System.out.println("java Evolver <seconds> <city file> <config file>");
    			return;
    		}
    		
    		try {
    			seconds = Integer.parseInt(args[0]);
    			if(seconds < 0)
    				throw new NumberFormatException();
    		}catch (NumberFormatException e) {
    			System.out.println("Invalid number of seconds: "+args[0]);
    			throw e;
    		}
    	
    		if (!load_city(args[1])) return;	
    		//if (!load_config(args[2])) return;


    		int num_cities = citymap.getNumCities();
    		best_result = new int[num_cities];
    	
    	//-------------------------------------------------------
        	//1, load file and cfg
    		load_city(args[1]);
    		boolean cfgExit = load_config(args[2]);

    		//2, use GA
    	    GenePool m_genePool = new GenePool(citymap);
    	    Population m_population;
    	    if ( cfgExit ) {
    	    	m_population = new Population(citymap.getNumCities(),population_size,crossover_probability,mutation_probability,m_genePool);
    	    	
    	    }else{
    	    	System.out.println(">>>>>>>> using default parameters <<<<<<<<<<");
    	    	System.out.println("POPULATION_SIZE = 100");
    	    	System.out.println("CROSSOVER_PROBABILITY = 0.90");
    	    	System.out.println("MUTATION_PROBABILITY = 0.10");
    	    	
    	    	m_population = new Population(citymap.getNumCities(), m_genePool);
    	    }
    		
    		while(true){
    			if ( (timer.getTime()/1000) < seconds){
    				
    				m_population.reproduce();
    			}
    			else
    				break;	
    		}
            

    		//3, pass city order of the top citymap to best_result
            Chromosome bestChromosome = m_population.getBestChromosome();
    		for(int i=0; i< citymap.getNumCities(); i++){
    			best_result[i] = java.lang.Integer.parseInt( bestChromosome.getGene(i).getDescription() );
    		}
    		
    	//-------------------------------------------------------


    		System.out.println("\nTILL NOW, THE BEST PATH IS:");
    		
    		for(int i=0;i<best_result.length-1;i++) {
    			System.out.print(best_result[i] +"-");
    		}
    		System.out.println(best_result[best_result.length-1]);
    		
    		System.out.println("DISTANCE: "+bestChromosome.getFitness());
    		
    		

    }//end main()
	
	
    private static boolean load_city(String fstr) {
			File city_file = new File(fstr);
			try {
				citymap.load(city_file);
			}catch (Exception e) {
				System.out.println("Corrupted or Missing city file: "+fstr);
				return false;
			}
			return true;	
    }//end load_city()
	

    private static boolean load_config(String fstr) {

	File config_file = new File(fstr);
	FileReader freader = null;
	BufferedReader breader = null;
	String str;

	try {
	    freader = new FileReader(config_file);
	    breader = new BufferedReader(freader);
	}
	catch (Exception e) {
	    System.out.println("Missing config file: "+fstr);
	    return false;
	}

	try {
	    str = breader.readLine();
	    
	    //line1: read chromosome_size
	    try {
			chromosome_size = Integer.parseInt(str);
			if (chromosome_size <= 0) throw new Exception();
	    }
	    catch (Exception e) {
			System.out.println("Invalid chromosome size: "+str);
			throw e;
	    }
	    
	    //line2: read population_size
	    str = breader.readLine();
	    try {
			population_size = Integer.parseInt(str);
			if (population_size <= 0) throw new Exception();
	    }
	    catch (Exception e) {
			System.out.println("Invalid population size: "+str);
			throw e;
	    }
	    
	    //line3: read num_generations
	    str = breader.readLine();
	    try {
			num_generations = Integer.parseInt(str);
			if (num_generations <= 0) throw new Exception();
	    }
	    catch (Exception e) {
			System.out.println("Invalid number of generations: "+str);
			throw e;
	    }
	    
	    //line4: read if it is roulette selection
	    str = breader.readLine();
	    try {
			if (str.toLowerCase().trim().equals("roulette")) 
		    	roulette = true;
			else if (str.toLowerCase().trim().equals("tournament")) 
		    	roulette = false;
			else throw new Exception();
	    }
	    catch (Exception e) {
			System.out.println("Invalid selection type: "+str);
			throw e;
	    }
	    
	    //line5: read crossover type
	    str = breader.readLine();
	    try {
			if (str.toLowerCase().trim().equals("double"))
		    	single_crossover = false;
			else if (str.toLowerCase().trim().equals("single"))
		    	single_crossover = true;
			else throw new Exception();
	    }
	    catch (Exception e) {
			System.out.println("Invalid crossover type: "+str);
			throw e;
	    }
	    
	    //line6: read mutation type
	    str = breader.readLine();
	    try {
			mutation_type = Integer.parseInt(str);
			if (mutation_type < 0) throw new Exception();
	    }
	    catch (Exception e) {
			System.out.println("Invalid muation type: "+str);
			throw e;
	    }
	    
	    
	    //line7: read crossover_probability
	    str = breader.readLine();
	    try {
			crossover_probability = Double.parseDouble(str);
			if (crossover_probability < 0.0 ||
		    	crossover_probability > 1.0) throw new Exception();
	    }
	    catch (Exception e) {
			System.out.println("Invalid crossover probability: "+str);
			throw e;
	    }
	    
	    //line8: read mutation_probability
	    str = breader.readLine();
	    try {
			mutation_probability = Double.parseDouble(str);
			if (mutation_probability < 0.0 ||
		    	mutation_probability > 1.0) throw new Exception();
	    }
	    catch (Exception e) {
			System.out.println("Invalid mutation probability: "+str);
			throw e;
	    }
	    
	    
	}
	catch (Exception e) {
	    System.out.println("Error reading from config file: "+fstr);
	    return false;
	}
	return true;
       
    }	//end load_config()


}


class Gene{   
    private String m_description;	//cityNo
    private double m_x;
	private double m_y;
	
	// Constructors
	public Gene() {}
	public Gene(CityMap citymap, int i_index) { init(citymap, i_index); }
	public Gene(String i_description, double i_x, double i_y)
	{
	    this.m_description = i_description;
	    this.m_x = i_x;
	    this.m_y = i_y;
	}
	
	/** Method to initialize a gene from a citymap */
	public void init(CityMap citymap,int index){
		setDescription( ""+(index+1) );
		setX( citymap.getLocationX(index) );
		setY( citymap.getLocationY(index) );
	}

	
	// Accessor/Settor methods
    public String getDescription() { return m_description; }
	public void setDescription(String i_description) { m_description = i_description; }
	public double getX() { return m_x; }
	public void setX(double i_x) { m_x = i_x; }
	public double getY() { return m_y; }
	public void setY(double i_y) { m_y = i_y; }
	
	// Utility methods
	public Gene copy() { return new Gene(getDescription(), getX(), getY()); }
	public boolean equals(Gene i_gene) { return (i_gene.getDescription().equals(m_description)); }
    public String toString() { return m_description; }
}



class GenePool{
    protected static ArrayList m_genes;
    protected static int m_numberGenes;

    // Constructor
    public GenePool(CityMap citymap) { init(citymap); }
    
    /** Method to initialize gene pool from citymap */
    public void init(CityMap citymap)
    {
        m_numberGenes = citymap.getNumCities();
        m_genes = new ArrayList(m_numberGenes);
        
        for (int i = 0; i < m_numberGenes; i++)
        {
            Gene i_gene = new Gene(citymap, i);
            m_genes.add(i, i_gene);						
        }
    }
    
    /** Returns a chromosome with the genes in random order */
    public Chromosome createRandomChromosome(int i_size)
    {
    	java.util.Collections.shuffle(m_genes);
        
        ArrayList i_genes = new ArrayList(i_size);
        
        for (int i = 0; i < i_size; i++)
        {
            i_genes.add(i, m_genes.get(i));		 
        }
        
        return new Chromosome(i_genes);
    }
}


class Chromosome{
	
	static final double DEFAULT_CROSSOVER_RATE = 0.90;
	static final double DEFAULT_MUTATION_RATE = 0.05;
	
    protected ArrayList m_genes = new ArrayList();
    protected double m_fitness;
    
    // Constructors
    public Chromosome(ArrayList i_genes) { m_genes = i_genes; }
    public Chromosome(Gene[] i_genes) { setGenes(i_genes); }
    public Chromosome(Gene[] i_beginGenes, Gene[] i_endGenes) { setGenes(i_beginGenes, i_endGenes); }
    
    /** Performs a crossover with this chromosome and the one specified in the argument.
        Returns two children chromosomes while preserving the uniqueness of genes in the chromosomes,
        meaning that all genes will be represented once and only once in the chromosome. */
    public Chromosome[] crossover(Chromosome dad) { return crossover(dad, Chromosome.DEFAULT_CROSSOVER_RATE); }
    public Chromosome[] crossover(Chromosome i_chromosome, double i_crossoverRate)
    {
        int size = this.getSize();
        Chromosome mom = this.copy();
        Chromosome dad = i_chromosome.copy();
        
        Chromosome[] children = new Chromosome[2];
        
        double random = GAUtils.getRandomDouble(1.0);
        
        if (random < i_crossoverRate){
            int crossoverPoint = GAUtils.getRandomInt(1, size - 1);//crossoverPoint is random
                        
            Gene[] child1begin = mom.getGenes(0, crossoverPoint - 1);
            Gene[] child1end = getEndGenes(child1begin, dad.getGenes(0, size -1));
            
            Gene[] child2begin = dad.getGenes(0, crossoverPoint - 1);
            Gene[] child2end = getEndGenes(child2begin, mom.getGenes(0, size -1));
            
            children[0] = new Chromosome(child1begin, child1end);
            children[1] = new Chromosome(child2begin, child2end);
            
            return children;
        }
        
        // if no crossover, children are same as parents
        children[0] = mom;
        children[1] = dad;
        
        return children;	
    }	
    
    
    
    /** Utility method to preserve uniqueness of genes in a chromosome.  Given the genes that are
        selected to begin a child chromosome, get the remaining unique genes from the other parent. */
    private Gene[] getEndGenes(Gene[] i_childBegin, Gene[] i_parentGenes)
    {
        Vector temp = new Vector();
            
            for (int i = 0; i < i_parentGenes.length; i++)
            {
            	Gene g = i_parentGenes[i];
                boolean inChild = false;
                
                for (int j = 0; j < i_childBegin.length; j++)
                {
                	Gene gchild = i_childBegin[j];
                    if (gchild.equals(g))
                    {
                        inChild = true;
                        break;