tour.java

遗传算法求解TSP问题

import java.awt.*;
import java.util.Random;

public class Tour {
	public Knoten [] knoten; 
	public int knoten_nr;
	
	private Map map1, map2;
	private Knoten [] knoten_new;
	private double dist [] [];
	private Random rand = new Random ();
	
	public Tour () {
		Random rand = new Random ();
		knoten = new Knoten [(2* World.points)];
		knoten_nr =  World.points;
		knoten_new = new Knoten [2*knoten_nr];
		dist = new double [2*knoten_nr] [2*knoten_nr];
		newTour (  World.points);
		makeDistMatrix();
	}
	public int change (int x, int y) {
		int i = 0; 
		boolean changed = false;
		/* first it is checked if a knot should be removed */
		while((!changed)&&(i < knoten_nr )) {
			if ( (knoten[i].x-World.minDist < x) && (x < knoten[i].x+World.minDist) &&
				(knoten[i].y-World.minDist < y) && (y < knoten[i].y+World.minDist) ) {
			  knoten[i] = knoten[knoten_nr-1];
			  knoten_nr--;
			  changed = true;
			} else i++;
		}		
		/* if not a new knot is added */
		if ( (!changed) && knoten_nr <= 2*World.points ) {
			knoten[knoten_nr] = new Knoten ( x, y, knoten_nr);
			knoten_nr++;
		} 

		for ( int j=0; j<knoten_nr; j++) knoten[j].nr = j; 
		makeDistMatrix();
		map2.setPoints ( knoten, knoten_nr);
		map1.setPoints ( knoten, knoten_nr);
		return knoten_nr;
	}
	public double length () {
		double t = 0;
		for ( int i = 0; i < knoten_nr; i ++ ) {
			t += dist[knoten[i].nr][knoten[(i+1)%knoten_nr].nr];
		}
		return t;
	}
	protected void makeDistMatrix () {
		  for ( int i = 0; i < knoten_nr; i ++ ) {
			for ( int j = i; j < knoten_nr; j ++ ) {
				dist [j][i] = 
				Math.sqrt (Math.pow( knoten[i].x - knoten[j].x, 2 ) +
				Math.pow ( knoten[i].y - knoten[j].y, 2 )); 
				dist [i][j] = dist [j][i];	
			}
		  }
	}
	public boolean nearest () {
		for ( int i = 0; i < knoten_nr-2; i++) {
		  for (int j = i+2; j < knoten_nr; j++) {
			if ( dist [knoten[i].nr] [knoten[i+1].nr] >
			dist [knoten[i].nr] [knoten[j].nr]){	
			  Knoten t = knoten [i+1];	
			  knoten[i+1] = knoten [j];
			  knoten[j] = t;
			}
		  }	
		}
		map1.setPoints ( knoten, knoten_nr);
		return false;
	}
	public void newTour ( int size ) {
		knoten = new Knoten[2*World.points];
		knoten_nr = size;
		
		for ( int i = 0; i < knoten_nr; i++) {
			knoten[i] = randomPoint ( 5, 5, World.width-10, World.height-10 );
			boolean test;
			do {
				test = true;
				for ( int j = 0; j < i; j++)
				if (( java.lang.Math.abs (knoten[j].x - knoten[i].x) < World.minDist ) &&
				    ( java.lang.Math.abs (knoten[j].y - knoten[i].y) < World.minDist )) test = false;
				if ( test == false ) knoten[i] = randomPoint ( 5, 5, World.width-10, World.height-10 );
				knoten[i].nr = i;
			}	while (	!test );
		}	
		makeDistMatrix();
		if ( map1 != null ) map1.setPoints ( knoten, knoten_nr );
		if ( map2 != null ) map2.setPoints ( knoten, knoten_nr );
		
	}
	public boolean orOpt () {
		boolean changed = false;
		for ( int i = 0; i < (knoten_nr-2); i ++ ) {
		  for ( int j = i+1; j < (knoten_nr-1); j ++ ) {
		    for ( int k = j+1; (k < j+4)&&(k < knoten_nr); k ++ ) {
			if (( dist[knoten[i].nr][knoten[(i+1)].nr] +
			     dist[knoten[j].nr][knoten[(j+1)].nr] +
			     dist[knoten[k].nr][knoten[(k+1)%knoten_nr].nr]) >
			    ( dist[knoten[i].nr][knoten[(j+1)].nr] +
			     dist[knoten[j].nr][knoten[(k+1)%knoten_nr].nr] + 
			     dist[knoten[k].nr][knoten[(i+1)].nr] )) {
				swap2 ( i, j, k);
				changed = true;
			}
		    }
		  }
		}
		if (changed) map1.setPoints ( knoten, knoten_nr );
		return changed;
	}
	private Knoten randomPoint ( int offX, int offY, int width, int height ) {
		return new Knoten( 	offX + Math.abs( rand.nextInt()) % width, 
							offY + Math.abs( rand.nextInt()) % height);
	}
	public boolean reset () {
		for ( int i = 0; i < knoten_nr-1; i++) {
		  if ( i != knoten[i].nr ) {
		    for ( int j = i+1; j < knoten_nr; j++)
			if ( i == knoten[j].nr ){	
			  Knoten t = knoten [i];	
			  knoten[i] = knoten[j];
			  knoten[j] = t;
		    }
		  }
		}
		map1.setPoints ( knoten, knoten_nr);
		return false;
	}
	public void setMap1 ( Map m ) {
        	map1 = m;
        	map1.setPoints ( knoten, knoten_nr );
	}
	public void setMap2 ( Map m ) {
        	map2 = m;
        	map2.setPoints ( knoten, knoten_nr );
	}
	protected void swap ( int x, int y ) {
		for ( int a = x+1; a < y+1; a++) {
		  knoten_new [a-x-1] = knoten[a];
		}
		for ( int a = x+1; a < y+1; a++) {		
		  knoten [a] = knoten_new[y-a];
		}
	}
	protected void swap2 ( int x, int y, int z ) {
		for ( int a = 0; a < z-x; a++) {
		  knoten_new [a] = knoten[a+x+1];
		}
		for ( int a = x+1; a < (x+1+z-y); a++) {		
		  knoten [a] = knoten_new[a-x-1+y-x];
		}
		for ( int a = (x+1+z-y); a < z+1; a++) {
		  knoten [a] = knoten_new[a-x-1-z+y];
		}
	}
	public boolean threeOpt () {
		boolean changed = false;
		for ( int i = 0; i < (knoten_nr-2); i ++ ) {
		  for ( int j = i+1; j < (knoten_nr-1); j ++ ) {
		    for ( int k = j+1; k < knoten_nr; k ++ ) {
			if (( dist[knoten[i].nr][knoten[(i+1)].nr] +
			     dist[knoten[j].nr][knoten[(j+1)].nr] +
			     dist[knoten[k].nr][knoten[(k+1)%knoten_nr].nr]) >
			    ( dist[knoten[i].nr][knoten[(j+1)].nr] +
			     dist[knoten[j].nr][knoten[(k+1)%knoten_nr].nr] + 
			     dist[knoten[k].nr][knoten[(i+1)].nr] )) {
				swap2 ( i, j, k);
				changed = true;
			}
		    }
		  }
		}
		if (changed) map1.setPoints ( knoten, knoten_nr);
		return changed;
	}
	public boolean twoOpt () {
		boolean changed = false;
		for ( int i = 0; i < (knoten_nr-2); i ++ ) {
		  for ( int j = i+2; j < knoten_nr; j ++ ) {
			if ( (dist[knoten[i].nr][knoten[(i+1)].nr] +
			     dist[knoten[j].nr][knoten[(j+1)%knoten_nr].nr] >
			     dist[knoten[i].nr][knoten[j].nr]  +
			     dist[knoten[(i+1)].nr][knoten[(j+1)%knoten_nr].nr] ) ) {
				swap ( i, j);
				changed = true;
			}
		  }
		}
		if (changed) map1.setPoints ( knoten, knoten_nr);
		return changed;
	}
	public int[] twoOptStep () {
		for ( int i = 0; i < (knoten_nr-2); i ++ ) {
		  for ( int j = i+2; j < knoten_nr; j ++ ) {
			if ( (dist[knoten[i].nr][knoten[(i+1)].nr] +
			     dist[knoten[j].nr][knoten[(j+1)%knoten_nr].nr] >
			     dist[knoten[i].nr][knoten[j].nr]  +
			     dist[knoten[(i+1)].nr][knoten[(j+1)%knoten_nr].nr] ) ) {
				return new int[] { i, j};
			}
		  }
		}
		return null;
	}
}