tsp.java

用java实现的利用蚁群算法实现的tsp问题

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Point;

/**
 * 模拟退火算法
 * @author typot
 * 2007.12.26
 */
public class Tsp {
	private int CITY_COUNT = 50;
	private Point citys[];
	private int[] current_Road;
	private double initTemple;
	private double nowTemple;
	private int[] result_Road;
	private double[][] distance;
	private Panel p;
	
	public Point[] getCitys() {
		return citys;
	}

	public void setCitys(Point[] citys) {
		this.citys = citys;
	}

	public int[] getResult_Road() {
		return result_Road;
	}

	public void setResult_Road(int[] result_Road) {
		this.result_Road = result_Road;
	}

	public Tsp(Panel p)
	{
		initCity();
		init();
		this.p = p;
	}
	
	private void init() {
		// TODO Auto-generated method stub
		current_Road = new int[CITY_COUNT];
		result_Road = new int[CITY_COUNT];
		for(int i = 0; i < CITY_COUNT; i ++)
		{
			current_Road[i] = i;
			result_Road[i] = i;
		}
		double min = 10000;
		double max = 0;
		
		distance = new double[CITY_COUNT][CITY_COUNT];
		for(int i = 0; i < CITY_COUNT; i ++)
			for(int j = 0; j < CITY_COUNT; j ++)
			{
				int x = citys[i].x - citys[j].x;
				int y = citys[i].y - citys[j].y;
				distance[i][j] = Math.sqrt(x*x+y*y);
				if(distance[i][j] > max )
					max = distance[i][j];
				if(distance[i][j] < min)
					min = distance[i][j];
			}
		
		initTemple = CITY_COUNT*(CITY_COUNT*max - CITY_COUNT * min);
		nowTemple = initTemple;
	}

	private double getInstance(int[] road)
	{
		double result = 0;
		for(int i = 0; i < road.length - 1; i ++)
			result += distance[i][i+1];
		result += distance[road.length - 1][0];
		return result;
	}
	
	private void buildRandom()
	{
		int i = (int) (Math.random()*current_Road.length);
		int j = i;
		while(j == i)
		{
			j = (int) (Math.random()*current_Road.length);
		}
		
		int temp = current_Road[i];
		current_Road[i] = current_Road[j];
		current_Road[j] = temp;
	}
	
	public void tsp()
	{
		while(true)
		{
			int count = 0;
			while(true)
			{
				double total1 = getInstance(result_Road);
				buildRandom();
				double total2 = getInstance(current_Road);
				double del = total2 -total1;
				if(del < 0)
				{
					setResult();
				}
				else
				{
					double probability = Math.exp( -(del/nowTemple));
					if(probability > Math.random()*1)
					{
						setResult();
					}
				}
				if(count >= 20*20*20)
					break;
				else
					count ++;
			}
			if(nowTemple <= 0.01)
				break;
			else
				nowTemple = 0.95 * nowTemple;
		}
	}
	
	private void setResult()
	{
		for(int i = 0; i < current_Road.length; i ++)
		{
			result_Road[i] = current_Road[i];			
		}
		p.repaint();
	}
	private void initCity()
	{
		citys = new Point[CITY_COUNT];
		for(int i = 0; i < CITY_COUNT; i ++)
		{
			citys[i] = new Point();
			citys[i].x = (int) (Math.random() * 280 + 10);
			citys[i].y = (int) (Math.random() * 280 + 10);
		}
	}
	
	public void print()
	{
		System.out.println("result:");
		for(int i = 0; i < current_Road.length; i ++)
		{
			System.out.print(current_Road[i]+"\t");		
		}
	}
	
	public void draw(Graphics2D g2d)
	{
		for(int i = 0; i < result_Road.length - 1; i ++)
		{
			g2d.setPaint(Color.red);
			g2d.fillRect(citys[result_Road[i]].x*2 - 5, citys[result_Road[i]].y*2 - 5, 10, 10);
			Integer index = result_Road[i] + 1;
			g2d.drawString(index.toString(), citys[result_Road[i]].x*2 - 5, citys[result_Road[i]].y*2+15);
			g2d.setPaint(Color.white);
			g2d.drawLine(citys[result_Road[i]].x*2-5, citys[result_Road[i]].y*2-5, citys[result_Road[i+1]].x*2-5, citys[result_Road[i+1]].y*2-5);
		}
		g2d.setPaint(Color.red);
		g2d.fillRect(citys[result_Road[CITY_COUNT-1]].x*2-5, citys[result_Road[CITY_COUNT-1]].y*2-5, 10, 10);
		Integer index = result_Road[CITY_COUNT-1];
		g2d.drawString(index.toString(), citys[result_Road[CITY_COUNT-1]].x*2 - 5, citys[result_Road[CITY_COUNT-1]].y*2+15);
		g2d.setPaint(Color.white);
		g2d.drawLine(citys[result_Road[CITY_COUNT-1]].x*2-5, citys[result_Road[CITY_COUNT-1]].y*2-5, citys[result_Road[0]].x*2-5, citys[result_Road[0]].y*2-5);
	}
}