main.java

遗传算法求解TSP问题

/*******************************************************************************
 * This is a simple JAVA-Applet to demonstrate algorithms solving the Traveling
 * Salesman problem. Feel free to use or modify it. If you do so, please send me
 * a copy.
 * Tim Stockheim ([e-mail])
 * 1995 (programmed) & 2001 (updated)
 * 
 * Please do not delete my name from this program.
 * The following files contain to the applet:
 * Knoten.java  Main.java  Map.java  Map1.java  Map2.java  Tour.java  World.java
 *******************************************************************************/

import java.applet.Applet;
import java.text.DecimalFormat;
import java.awt.*;

public class Main extends Applet implements Runnable {
	private Tour tour;
	public Map1 map1; // the left map
	public Map2 map2; // the right map
	protected Button button, button2, button3, button4, button5, button6, button7;
	protected Label box, box1, box2;
	protected int run_now = 0;
	public Thread myThread;
	private DecimalFormat df = new DecimalFormat();
	public boolean action(Event event, Object what) {
		if ( run_now == 0 ) {
			/* I would like to use a switch statement here but it wouldn't work 
			The manual says: The type of the Expression must be  byte, short , 
			int, or long, or a compilation error occurs. */

			if ( event.target == button) {
				run_now = 1;
				return true;
			} 
			if ( event.target == button2) {
				run_now = 2;
				return true;
			} 
			if ( event.target == button3) {
				run_now = 3;
				return true;
			} 
			if ( event.target == button4) {
				run_now = 4;
				return true;
			}
			if ( event.target == button5) {
				run_now = 5;
				return true;
			} 
			if ( event.target == button6) {
				run_now = 6;
				return true;
			}
			if ( event.target == button7) {
				run_now = 7;
				return true;
			}
		}
		return false;
	}
	public void init () {
		if ( map1 == null ) add ( map1 = new Map1 ( (int) (World.width*World.scaling), (int) (World.height*World.scaling) ) );
		if ( map2 == null ) add ( map2 = new Map2 ( (int) (World.width*World.scaling), (int) (World.height*World.scaling) ) );
                resize ( 25+(int)(2*World.width*World.scaling), 80+(int)(World.height*World.scaling) );
		tour = new Tour ();
		tour.setMap1 ( map1 );
		tour.setMap2 ( map2 );
		df.setMaximumFractionDigits(2);
		if ( box == null)      add( box     = new Label( "Waiting"));
		if ( button == null )  add( button  = new Button( " 2opt"));
		if ( button2 == null ) add( button2 = new Button( " 3opt"));
		if ( button3 == null ) add( button3 = new Button( "ORopt"));
		if ( button4 == null ) add( button4 = new Button( "Nearest"));
		if ( button5 == null ) add( button5 = new Button( "Reset"));
		if ( button6 == null ) add( button6 = new Button( "New"));
		if ( button7 == null ) add( button7 = new Button( "2opt (animated)"));
		if ( box1 == null)     add( box1 = new Label( "Points: "+World.points));
		if ( box2 == null)     add( box2 = new Label( "Length: "+df.format( tour.length())));
	}
	public boolean mouseDown( Event event, int x, int y ) {
		if ( run_now == 0 ) {
			y = (int)((y-5)/World.scaling);		
			x = (int)((x-World.width*World.scaling-15)/World.scaling);
			if ((0<x)&&(x<=World.width)&&(0<y)&&(y<=World.height)){
				box1.setText( "Punkte: " + tour.change( x, y ));
				box2.setText( "Length: " + df.format( tour.length()));
			}
		}
		return true;		
	}
	public void run () {
	  do {
		while (run_now == 0) {
 			try { myThread.sleep(100);
	 		} catch (InterruptedException e) {}
		}
	  switch (run_now) {
	  case 1:
		  button.setLabel( "OK");
		  box.setText( "Running");
		  while ( tour.twoOpt());
		  button.setLabel( "2opt");
		  break;
	  case 2:
		  button2.setLabel( "OK");
		  box.setText( "Running");
		  while ( tour.threeOpt () );
		  button2.setLabel( "3opt");
		  break;
	  case 3:
		  button3.setLabel( "OK");
		  box.setText( "Running");
		  while ( tour.orOpt ());
		  button3.setLabel( "ORopt");
		  break;
	  case 4:
		  button4.setLabel( "OK");
		  box.setText( "Running");
		  tour.nearest ();
		  button4.setLabel( "Nearest");
		  break;
	  case 5:
		  button5.setLabel( "OK");
		  box.setText( "Running");
		  tour.reset ();
		  try { myThread.sleep (50);
		  } catch (InterruptedException e){}
		  button5.setLabel( "Reset");
		  break;
	  case 6:
		  button6.setLabel( "OK");
		  box.setText( "Running");
		  tour.newTour( tour.knoten_nr );
		  try { myThread.sleep (50);
		  } catch ( InterruptedException e){}
		  box1.setText( "Punkte: "+ tour.knoten_nr );
		  button6.setLabel( "New");
		  break;
	   case 7:
		  button7.setLabel( "OK");
		  box.setText( "Running");
		  boolean running = true;
		  do {
			  int i[] = tour.twoOptStep();
			  map1.setColorPoints( i, Color.blue);
			  try { myThread.sleep (600);
		 	  } catch (InterruptedException e){}
		 	  if ( i!=null) tour.swap( i[0], i[1]);
		 	  else running = false;
		 	  map1.setColorPoints( Color.blue);
		 	  try { myThread.sleep (700);
		 	  } catch (InterruptedException e){}
		 	  map1.unsetColorPoints();
		 	  box2.setText( "Length: "+df.format( tour.length()));
			  try { myThread.sleep (500);
		 	  } catch (InterruptedException e){}
		  } while( running);
		  button7.setLabel( "2opt (animated)");
		  break;
	  default:;
	  }
	  box2.setText( "Length: "+df.format( tour.length()));
	  box.setText( "Waiting");
	  run_now = 0;
	  } while ( true );
	}
	public void start () {
		if (myThread == null) {
			myThread = new Thread( this, "opt");
			myThread.start();
		}
	}
}