tsp.java.svn-base

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

         //status refreshing thread
         Thread statusThread=new Thread() { 
            @Override
            public void run() {
               while(!stopRequestFlag) {
                  runTime=System.currentTimeMillis()-startTime;
                  setStatus(engine);
                  try { Thread.sleep(configuration.console ? 15000 : 1000); } catch (Exception e) {/**nop**/}
               }
            }
         };
         statusThread.start();
         
         //repeat the evolotion until stop is required 
         while(!stopRequestFlag) {
            //if pause, then wait
            if(generation%3==0) {
               if(!configuration.console && pauseRequestFlag) {
                  gui.statusBar.setText("Pause; "+gui.statusBar.getText());
                 while(pauseRequestFlag) {
                    try {
                        Thread.sleep(1000);
                     } catch(InterruptedException foo) { /* none */ }
                 }
               } //pause
            } // check for pause

            //get best chromosome
            bestChromosome=engine.getBestChromosome();
            bestCost=bestChromosome.getTotalDistance();
            if(previewCost==bestCost) {
               bestCostAge++;
            } else {
               bestCostAge=0;
            }
            if(bestCostAge>=configuration.maxBestCostAge) {
               stopRequestFlag=true;
            }
            previewCost=bestCost;
            
            long currentTime=System.currentTimeMillis();
            //once in 5 seconds repaint map graphics
            if(previewDrawTime<currentTime-1000 || pauseRequestFlag) {
               previewDrawTime=currentTime;
               if(previewDrawCost!=bestCost && !configuration.console) {
                  gui.cityMap.repaint();
                  previewDrawCost=bestCost;
               } 
            }
   
            engine.nextGeneration();
   
            generation++;
         } //while ! stop
         
         //stop actions
         runTime=System.currentTimeMillis()-startTime;
         statusThread.interrupt();
         //wait a second 
         try { Thread.sleep(500); } catch(Throwable e) { /*nop*/ }

         //refresh status line
         setStatus(engine);
         if(!configuration.console) {
        	 gui.statusBar.setText("Finished; "+gui.statusBar.getText());
         }
         
         stopRequestFlag=false;
         startedFlag=false;
         pauseRequestFlag=false;
         
         //reenable menu items
         if(!configuration.console) {
	         gui.menu.resetMenu();
	         gui.menu.menuItemPDFReport.setEnabled(true);
	         gui.menu.menuItemXMLReport.setEnabled(true);
	         gui.menu.menuItemXML2PDFReport.setEnabled(true);
	
	         gui.repaint();
         }
      } catch(Throwable e) {
         e.printStackTrace();
         System.exit(-1);
      }
   }

   /**
    * set information at status bar
    * @param engine
    */
   void setStatus(TSPEngine engine) {
      String statusText=String.format(
            "%s: cities: %s; time: %s; generation: %s; population: %s; best distance: %s; best age: %s;",
            engineName,
            cities.length,
            runTime/1000,
            generation,
            engine.getPopulationSize(),
            (int)bestCost,
            bestCostAge
      );
      if(configuration.console) {
    	  System.out.println(statusText);
      } else {
    	  gui.statusBar.setText(statusText);
      }
   }
   
   /**
    * computes application version from CVS revisions of classes
    * @return application version String
   */
   public static String getAppVersion() {
	   String projectClasses[]=new String[] {
			   City.CVS_REVISION,
			   CityTests.CVS_REVISION,
			   Report.CVS_REVISION,
			   TSP.CVS_REVISION,
			   TSPChromosome.CVS_REVISION,
			   TSPChromosomeTests.CVS_REVISION,
			   TSPConfiguration.CVS_REVISION,
			   TSPEngine.CVS_REVISION,
			   TSPMenu.CVS_REVISION,
			   TSPMenuTests.CVS_REVISION,
			   JGapGreedyCrossoverEngine.CVS_REVISION,
			   JGapGreedyCrossoverEngineTests.CVS_REVISION,
			   SimpleUnisexMutatorHibrid2OptEngine.CVS_REVISION,
			   SimpleUnisexMutatorEngineTests.CVS_REVISION,
			   GreedyCrossoverEngine.CVS_REVISION,
			   GreedyCrossoverEngineTests.CVS_REVISION,
			   GreedyCrossoverHibrid2OptEngine.CVS_REVISION,
			   SimpleUnisexMutatorHibrid2OptEngine.CVS_REVISION,
			   TSPGui.CVS_REVISION,
	   };
	   
	   //take care that version 1.30 is not the same like 1.3
	   double major=0;
	   double minor=0;
	   Pattern revision=Pattern.compile("(\\d+)\\.*(\\d+)");
	   for(String v:projectClasses) {
		   Matcher matcher=revision.matcher(v);
		   matcher.find();
		   major+=Double.parseDouble(matcher.group(1));
		   minor+=Double.parseDouble(matcher.group(2));
	   }
	   major=major/projectClasses.length;
	   minor=minor/projectClasses.length;
	   return ((int)major)+"."+((int)(minor*100));
   }
   
   /**
    * Main - starts the application ig text or graphics mode
    * for all the parameters, run this application with /? 
    * Possible command line parameters are
    * --console     mandatory to set the output to console, no graphics displayed
	* --map=NAME    where name is name of resource with .csv format
    *               you can use only number part (020, 050...) as map name for build in maps
    * --priority=N  where N in <1..10>; DEFAULT 5
	* --engine=N    where N is the index of engine to use; DEFAULT engine is GreedyCrossoverHibrid2OptEngine
  	* --rms=T       where T in <true,false> - computes RMS cost from distance; DEFAULT false
  	* --population=N where N is the initial population size. DEFAULT 1000
    * --max=N       where N is the max number of the same best result; DEFAULT 100
    * --growth=N    where N is population growth. DEFAULT 0.0075
  	* --mutation=N  where N is mutation ratio. DEFAULT 0.5
  	* --xml=FILE.xml where FILE is output name for XML report file.
  	*				DEFAULT tsp_report_yyyy_MM_dd_HH_mm.xml
	* See the gui interface help, documentation or http://www.saiko.cz/ai/tsp/ for detailed information.
	* Example:       --console --map=192 --priority=1 --engine=3 --rms=false --population=200 --growth=0.01 --max=200 --mutation=0.5
    *                --console
	*			     --help 
    * @param args - command line arguments
    * @throws Exception 
    */
   public static void main(String args[]) throws Exception {
	   
	   //process command line
	   if(args!=null && args.length>0) {
		   //display ussage ?
		   boolean error=false;
		   String errorMessage="";
		   
		   int paramPriority=Thread.NORM_PRIORITY;
		   String paramMap="/org/saiko/ai/genetics/tsp/etc/cities_050.csv";
		   Class paramEngine=engineClasses[3];
		   boolean paramRms=false;
		   int paramPopulation=1000;
		   int paramMax=100;
		   double paramMutation=0.5;
		   double paramGrowth=0.0075;
		   String paramXMLFileName="tsp_report_"+new SimpleDateFormat("yyyy_MM_dd_HH_mm").format(Calendar.getInstance().getTime())+".xml";
		   
		   try {
			   for(int i=0; i<args.length; i++) {
				   String param=args[i].toLowerCase();
				   while(param.startsWith("-")) {
					   param=param.substring(1);
				   }
				   if(param.startsWith("priority=")) {
					   param=param.substring(param.lastIndexOf('=')+1);
					   paramPriority=Integer.parseInt(param);
				   } else
				   if(param.equals("console")) {
					   //nothing
				   }
				   else if(param.startsWith("map=")) {
					   param=param.substring(param.lastIndexOf('=')+1);
					   
					   String[] possiblePaths=new String[] {
							   param,
							   "/org/saiko/ai/genetics/tsp/etc/"+param,
							   "/org/saiko/ai/genetics/tsp/etc/"+param+".csv",
							   "/org/saiko/ai/genetics/tsp/etc/cities_"+param+".csv",
							   "/org/saiko/ai/genetics/tsp/etc/cities_"+param,
							   "/org/saiko/ai/genetics/tsp/etc/cities_0"+param+".csv",
							   "/org/saiko/ai/genetics/tsp/etc/cities_0"+param,
					   };
					   for(String resName:possiblePaths) {
						   if(TSP.class.getResourceAsStream(resName)!=null) {
							   paramMap=resName;
							   break;
						   } 
					   }
					   
					   if(paramMap==null) {
						   error=true;
					   }
					   
				   }
				   else if(param.startsWith("engine=")) {
					   int engineIndex=Integer.parseInt(param.substring(param.lastIndexOf('=')+1));
					   paramEngine=engineClasses[engineIndex];
					   @SuppressWarnings("unused") TSPEngine engineInterface=(TSPEngine)paramEngine.newInstance();
				   }
				   else if(param.startsWith("population=")) {
					   paramPopulation=Integer.parseInt(param.substring(param.lastIndexOf('=')+1));
				   }
				   else if(param.startsWith("max=")) {
					   paramMax=Integer.parseInt(param.substring(param.lastIndexOf('=')+1));
				   }
				   else if(param.startsWith("growth=")) {
					   paramGrowth=Double.parseDouble(param.substring(param.lastIndexOf('=')+1));
				   }
				   else if(param.startsWith("mutation=")) {
					   paramMutation=Double.parseDouble(param.substring(param.lastIndexOf('=')+1));
				   }
				   else if(param.startsWith("rms=")) {
					   paramRms=Boolean.parseBoolean(param.substring(param.lastIndexOf('=')+1));
				   }
				   else if(param.startsWith("xml=")) {
					   paramXMLFileName=param.substring(param.lastIndexOf('=')+1);
				   }
				   else {
					   error=true;
					   break;
				   }
			   }
		   } catch(Throwable e) {
			   error=true;
		   }
		   
		   if(error) {
			   String ussage=
				   "Error in command line parameters.\n"+errorMessage+"\nOptions: \n" +
			   			"--console     mandatory, sets the output to console, no graphics displayed.\n" +
			   			"--map=NAME    where name is name of resource with .csv format.\n" +
				   		"                build in maps:\n" +
				   		"                  /org/saiko/ai/genetics/tsp/etc/cities_020.csv\n" +    
				   		"                  /org/saiko/ai/genetics/tsp/etc/cities_050.csv <- DEFAULT\n" +    
				   		"                  /org/saiko/ai/genetics/tsp/etc/cities_100.csv\n" +
				   		"                  /org/saiko/ai/genetics/tsp/etc/cities_150.csv\n" +
				   		"                  /org/saiko/ai/genetics/tsp/etc/cities_192.csv\n" +
				   		"                you can use only number part (020, 050...) as map name for build in maps.\n" +
				   		"--priority=N  where N in <1..10>; DEFAULT 5\n" +
				   		"--engine=N    where N is the index of engine to use; DEFAULT engine is GreedyCrossoverHibrid2OptEngine\n" +
				   		"                build in engines:\n"
			   ;
			   int i=0;
			   for(Class engineClass:engineClasses) {
			   		ussage+=
			   			"                  "+i+": "+engineClass.getSimpleName()+"\n";
			   		i++;
			   }
			   ussage+=
  		   		   "--rms=T       where T in <true,false> - computes RMS cost from distance; DEFAULT false\n" +
  		   		   "--population=N where N is the initial population size. DEFAULT 1000.\n" +
  		   		   "--max=N       where N is the max number of the same best result; DEFAULT 100\n" +
  		   		   "--growth=N    where N is population growth. DEFAULT 0.0075\n" +
  		   		   "--mutation=N  where N is mutation ratio. DEFAULT 0.5\n" +
  		   		   "--xml=FILE.xml where FILE is output name for XML report file. \n" +
  		   		   "              DEFAULT tsp_report_yyyy_MM_dd_HH_mm.xml\n" +
				   "\n" +
				   "See the gui interface help, documentation or http://www.saiko.cz/ai/tsp/ for detailed information.\n"+
				   "Example:       --console --map=192 --priority=1 --engine=3 --rms=false --population=200 --growth=0.01 --max=200 --mutation=0.5 \n" +
				   "               --console\n" +
				   "               --help\n" 
			   ;
			   System.err.println(ussage);
			   System.exit(-1);
		   }
		   
		   //display used parameters
		   System.out.println("Priority: "+paramPriority);
		   System.out.println("Map: "+paramMap);
		   System.out.println("Engine: "+paramEngine);
		   System.out.println("RMS: "+paramRms);
		   System.out.println("Population: "+paramPopulation);
		   System.out.println("Mutation: "+paramMutation);
		   System.out.println("Growth: "+paramGrowth);
		   System.out.println("Max best age: "+paramMax);
		   System.out.println("XML report file: "+paramXMLFileName);
		   System.out.println("Initializing ...");
		   
		   //set the parameters
		   TSP tsp=new TSP(false);
		   tsp.configuration.console=true;
		   tsp.configuration.initialPopulationSize=paramPopulation;
		   tsp.configuration.maxBestCostAge=paramMax;
		   tsp.configuration.rmsCost=paramRms;
		   tsp.configuration.mutationRatio=paramMutation;
		   tsp.configuration.populationGrow=paramGrowth;
		   tsp.configuration.threadPriority=paramPriority;
		   tsp.engineClass=paramEngine;
		   tsp.engine=(TSPEngine)paramEngine.newInstance();
		   tsp.mapFile=paramMap;

		   //load the map
		   tsp.loadCities(null,true);

		   System.out.println("Running ...");
		   tsp.start();

		   System.out.println("Writing the report ...");
		   new TSPMenu(tsp).actionXMLReport(paramXMLFileName);
		  
		   System.out.println("Finished.");
		   System.exit(0);
	   } //end command line processing
	   else {
		   //run the program in GUI
		   new TSP().start();
	   }
   }
}