tsp.java.svn-base

Traveling Salesman Problem Java Genetic Algorithm Solution, Hope all enjoy it.

/*
 * $Source: f:/cvs/prgm/tsp/src/org/saiko/ai/genetics/tsp/TSP.java,v $
 * $Id: TSP.java,v 1.11 2005/08/24 12:33:13 dsaiko Exp $
 * $Date: 2005/08/24 12:33:13 $
 * $Revision: 1.11 $
 * $Author: dsaiko $
 *
 * Traveling Salesman Problem genetic algorithm.
 * This source is released under GNU public licence agreement.
 * [e-mail]
 * http://www.saiko.cz/ai/tsp/
 * 
 * Change log:
 * $Log: TSP.java,v $
 * Revision 1.11  2005/08/24 12:33:13  dsaiko
 * Documentation finished
 *
 * Revision 1.10  2005/08/23 23:18:05  dsaiko
 * Finished.
 *
 * Revision 1.9  2005/08/23 10:01:31  dsaiko
 * Gui and main program divided
 *
 * Revision 1.8  2005/08/22 22:25:11  dsaiko
 * Packages rearanged
 *
 * Revision 1.7  2005/08/22 22:13:53  dsaiko
 * Packages rearanged
 *
 * Revision 1.6  2005/08/22 22:08:51  dsaiko
 * Created engines with heuristics
 *
 * Revision 1.5  2005/08/13 15:02:49  dsaiko
 * build task
 *
 * Revision 1.4  2005/08/13 15:02:09  dsaiko
 * build task
 *
 * Revision 1.3  2005/08/13 14:41:35  dsaiko
 * *** empty log message ***
 *
 * Revision 1.2  2005/08/13 12:53:02  dsaiko
 * XML2PDF report finished
 *
 * Revision 1.1  2005/08/12 23:52:17  dsaiko
 * Initial revision created
 *
 */

package org.saiko.ai.genetics.tsp;

import java.awt.event.ActionEvent;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.saiko.ai.genetics.tsp.engines.crossover.GreedyCrossoverEngine;
import org.saiko.ai.genetics.tsp.engines.crossover.GreedyCrossoverEngineTests;
import org.saiko.ai.genetics.tsp.engines.crossoverHibrid2opt.GreedyCrossoverHibrid2OptEngine;
import org.saiko.ai.genetics.tsp.engines.jgapCrossover.JGapGreedyCrossoverEngine;
import org.saiko.ai.genetics.tsp.engines.jgapCrossover.JGapGreedyCrossoverEngineTests;
import org.saiko.ai.genetics.tsp.engines.simpleUnisexMutator.SimpleUnisexMutatorEngine;
import org.saiko.ai.genetics.tsp.engines.simpleUnisexMutator.SimpleUnisexMutatorEngineTests;
import org.saiko.ai.genetics.tsp.engines.simpleUnisexMutatorHibrid2Opt.SimpleUnisexMutatorHibrid2OptEngine;

/**
 * @author Dusan Saiko ([e-mail])
 * Last change $Date: 2005/08/24 12:33:13 $
 *
 * Main class for representation of the traveling salesman problem.
 */
public class TSP  {

   /** String containing the CVS revision. **/
   public final static String CVS_REVISION = "$Revision: 1.11 $";

   /**
    * Application configuration
    */
   public final TSPConfiguration configuration=new TSPConfiguration();

   /**
    * Thread of running computations
    */
   protected Thread runingThread;
   
   /**
    * TPS engines which are able to solve the problem
    */
   protected static final Class engineClasses[] = new Class[] {
      SimpleUnisexMutatorEngine.class,
      JGapGreedyCrossoverEngine.class,
      GreedyCrossoverEngine.class,
      GreedyCrossoverHibrid2OptEngine.class,
      SimpleUnisexMutatorHibrid2OptEngine.class,
   };
   
   
   /**
    * available map files
    */
   protected final static String mapFiles[]={
         "cities_020",    
         "cities_050",    
         "cities_100",    
         "cities_150",    
         "cities_192", 
         null,
         "square_15x15",
         "triangle_15x15",
         "circle_150",
         "circle_120",
         "full_circle_305",
         "spiral_263",
         "line_100",
   };
   
   /**
    * selected map file
    */
   protected String mapFile=mapFiles[2];
   
   /**
    * synchronization mutex
    */
   protected final static Object mutex=new Object();
   
   /**
    * generated serialVersionUID
    */
   protected static final long serialVersionUID =8917595268427032741L;
 
   /**
    * Cities definition.
    * cities are loaded from definition file which coordinates
    * are writen in S-JTSK format
    */
   protected City cities[]=null;
   
   /**
    * pause flag - pause is required
    */
   protected volatile boolean pauseRequestFlag=false;
   
   /**
    * stop flag - stop is required
    */
   protected volatile boolean stopRequestFlag=false;

   /**
    * started flag - the computation is running
    */
   protected volatile boolean startedFlag=false;
   
   /**
    * best chromosome of population (to draw ...)
    */
   protected TSPChromosome bestChromosome;
   
 
   /**
    * Computation start time
    */
   protected long startTime=0;

   /**
    * Total running time (ms)
    */
   protected long runTime=0;
   
   /**
    * Selected engine class
    */
   protected Class engineClass=engineClasses[3];

   /**
    * Engine instance from engineClass
    */
   TSPEngine engine; 

   /**
    * Engine class name (short form) 
    */
   String engineName;
   
   /**
    * The count of generation which give the same best cost result
    */
   int bestCostAge;
   
   
   /**
    * generation counter
    */
   int generation=0;

   /**
    * cost of best chromosome
    */
   double bestCost=0;
   
   /**
    * loads cities from selected map 
    * @param citiesToLoad - not null if we just want to set some exact cities
    * @param initDiscanceCache - true if we want to initialize the distance cache of cities
    * @see City#initDistanceCache(int)
    */
   protected void loadCities(City[] citiesToLoad, boolean initDiscanceCache) {
         try {
        	 cities=citiesToLoad;
        	 if(cities==null) {
	            List<City> c=new ArrayList<City>();
	
	            //get the stream
	            //first try with only file name in mapFile
	            BufferedReader reader=null;
	            try {
	            	reader=new BufferedReader(
	                  new InputStreamReader(
	                          TSP.class.getClassLoader().getResourceAsStream("org/saiko/ai/genetics/tsp/etc/"+mapFile+".csv"),
	                          "UTF-8"
	                  )
	            	);
	            } catch(NullPointerException e) {
		            //first try with full path in mapFile
	            	reader=new BufferedReader(
	  	                  new InputStreamReader(
	  	                          new Object().getClass().getResourceAsStream(mapFile),
	  	                          "UTF-8"
	  	                  )
	  	            	);
	            }
	            
	            //read the data
	            String line;
	            Pattern patternLine=Pattern.compile("\"(.*?)\",(.*?),(.*)"); //$NON-NLS-1$
	            int count=0;
	            int id=0;
	            while((line=reader.readLine())!=null) {
	               count++;
	               if(count==1) continue;
	               Matcher regex=patternLine.matcher(line);
	               if(regex.find()) {
	                  String name=regex.group(1).trim();
	                  Integer x=new Integer(regex.group(2));
	                  Integer y=new Integer(regex.group(3));
	                  //city.id is the unique index of city starting from 0 
	                  City city=new City(id,configuration,name,x,y);
	                  id++;
	                  c.add(city);
	               }
	            }
	            reader.close();
	            cities=c.toArray(new City[]{});
        	 }

            //set the first city from file as start city
            cities[0].startCity=true;
            
            //find the bigist X
            int x1=0;
            for(City city:cities) {
               if(city.x>x1) x1=city.x;
            }
            //rotate around y access (characteristics of coordinates)
            //initialize
            for(City city:cities) {
               city.x=Math.abs(x1-city.x);
               //init the distance cache of the city for known number of cities
            }
            if(initDiscanceCache) {
            	City.initDistanceCache(cities.length);
            }
            
         } catch(Throwable e) {
            e.printStackTrace();
            System.exit(-1);
         }       
      }

   /**
    *  class constructor
    */
   public TSP() {
      this(true);
   }

   /**
    *  class constructor
    * @param loadCities - should the cities be loaded at initialization ? 
    */
   public TSP(boolean loadCities) {
	   if(loadCities) {
	      //load cities - the selected map has default value 
	      loadCities(null,true);
	   }
   }

   /**
    * Gui for TSP
    */
   TSPGui gui;
   
   /**
    * show the window
    */
   public void start() {
	   if(!configuration.console) {
		   gui=new TSPGui(this);
		   gui.init();
	   } else { 
		   run();
	   }
   }
   
   
   /**
    * runs the genetic computation of selected engine
    * starts in new thread
    * @see TSPMenu#actionStart(ActionEvent)
    */
   protected void run() {
      try {
         //initialize variables
         generation=0;

         startTime=System.currentTimeMillis();
         engine=(TSPEngine)engineClass.newInstance();
         engine.initialize(configuration,cities);
         engineName=engine.getClass().getSimpleName();
         
         bestCostAge=0;
         
         double previewCost=0;
         double previewDrawCost=0;
         long previewDrawTime=0;
         bestCost=0;