sa_tsa.java

利用模拟退火算法解决旅行商问题的java原码

import java.lang.*;
import java.io.*;
import java.util.*;


/**
*class SA_TSA.java
* author: nt
* data: 2006-3-22
*51 city
* mini=result_______________: 11.180339887498949
*/
public class SA_TSA
{
	//the city 
	//String[][] map;
	private static double T=1000.0;				//init the T
	private static final double CONTROL_T=0.995; //change the T
	private static final double T_e=0.01; //control the T
	private static final int CYCLE_NUMBER=560;  //search length
	private static final int CITY_NUMBER=51;  //city number
	private static CityMap[] citymap=new CityMap[CITY_NUMBER]; //city position

	public static void main(String args[])
	{
		SA_TSA tsa=new SA_TSA();
		// tsa.init(); 
		
		CityMap[] _citymap=new CityMap[CITY_NUMBER];
		CityMap[] temp_citymap=new CityMap[CITY_NUMBER];
		for (int init=0;init< CITY_NUMBER;init++ )
		{
			_citymap[init]=new CityMap();
			temp_citymap[init]=new CityMap();
		}
		getTime();
		System.out.println("开始初始化路径：....");
		_citymap=copy(citymap);
		for (int cyc=0;cyc<50;cyc++)
		{
			_citymap=getRoute(_citymap);
		}
		_citymap=tsa.getFirstRoute(_citymap);
		//get time
		System.out.println("初始化路径结束!");
		setcitymap(_citymap);
		System.out.println("初始路径长度"+": "+getRouteValue(citymap));
		getTime();
		
		Date begin=new Date();
		//
		//setcitymap(_citymap);
		//showMap(citymap);

		temp_citymap=tsa.settempcitymap(citymap);
		
		
		
		boolean terminate=false;
		/*
		_citymap=tsa.getRoute(citymap);
		System.out.println("__________第一次变换______________");
		//showMap(citymap);
		double way_value=getRouteValue(_citymap);
		double delta_v=way_value-routeValue;
		System.out.println("delta_v:"+delta_v);
		System.out.println("old_Value:"+routeValue);
		System.out.println("new_value:"+way_value);
					//System.out.println("random_d:"+random_d);

		*/
		System.out.println("正在查找最优路径：....");
		double newvalue,oldValue,delta_v;
		
		while (T>T_e)
		{	
			int cycle=0;
			//System.out.println("_______ldfkgdlfkg_______: ");
			//_citymap=tsa.getRoute(_citymap);
			//showMap(_citymap);
			
			//System.out.println("routeValue____2: "+getRouteValue(_citymap));
			_citymap=tsa.getRoute(citymap);
			do
			{
				//_citymap=tsa.getRoute(citymap);
				//System.out.println("routeValue____"+cycle+"_: "+tsa.getRouteValue(citymap));
				//System.out.println("T ____"+T);
				//System.out.println("查找过程"+cycle+": "+getRouteValue(_citymap));
				oldValue=getRouteValue(citymap);
				newvalue=getRouteValue(_citymap);
				delta_v=newvalue-oldValue;
				//System.out.println("old____"+cycle+"_: "+routeValue);
				//System.out.println("new____"+cycle+"_: "+way_value);
				//System.out.println("delta_v____"+cycle+"_: "+delta_v);
				if (delta_v <0)
				{
					//System.out.println("T _______________"+T);
					setcitymap(_citymap);
					_citymap=tsa.getRoute(citymap);
					
				}
				else
				{
					double random_d=tsa.getRandomDouble();
					double delta_e=get_exp(-delta_v);
//					System.out.println("delta_v:"+delta_v);
////
//					System.out.println("delta_e:"+delta_e);
//					System.out.println("random_d:"+random_d);
					//if (delta_e>random_d)
					if (delta_e>random_d)
					{
						
						
						setcitymap(_citymap);
						//System.out.println("________^^^^^^^______________");
						
					}
					_citymap=tsa.getRoute(citymap);

				}//if (delta_v<0)
				cycle++;
//
			}
			while (cycle<CYCLE_NUMBER);
			double old_=tsa.getRouteValue(temp_citymap);
			double new_=getRouteValue(citymap);

			if (new_<old_)
			{
//				if (old_/new_ <1.00000001)
//				{
//					//terminate=true;
//					T=newT(T);
//				}
//				else
//				{
//					temp_citymap=settempcitymap(citymap);
//					T=newT(T);
//				}
				temp_citymap=settempcitymap(citymap);
				T=newT(T);
				System.out.println("change:"+new_);
				
			}
			else
			{
				T=newT(T);
			}
			

			

//			if (T<=T_e)
//			{
//				terminate=true;
//			}
		}/**/

		System.out.println("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^");
		//System.out.println("||||||||||||||||||||||||||||||");
		Date end=new Date();
		System.out.println("查找结果：");
		
		System.out.println("最优路径长度"+": "+getRouteValue(temp_citymap));
		//getTime();
		long waste=end.getTime() - begin.getTime();
		System.out.println("耗时： " +waste/1000+" 秒！");
		//showMap(temp_citymap);

		//showMap(citymap);



		


	}//main over
	/**
	*constrator: 
	*/
	public SA_TSA()
	{	
		try
		{
			init();	
		}
		catch (IOException e)
		{
			System.out.println(e.toString());
		}
		
	}
	
	/**
	*method: initialize city map
	*/
	private static void init()throws IOException
	{
		//init the citymap based on the array.txt
		int n;//the city number
		n=getCityNumber();
		//System.err.println("_____________"+n+"_____________");
		if (n!=CITY_NUMBER)
		{
			throw new NotEqulalException("city number shouder be equal the varial \"CITY_NUMBER\" you declare"+n);
		}
		String[] _city=getCityString();
		for (int i=0;i<n;i++)
		{
			citymap[i]=new CityMap(_city[i]);
		}

	}
	/**
	*method:getCityNumber
	*param: null
	*return: int the number of the citytxt file
	*/
	private static int getCityNumber() throws IOException
	{
		BufferedReader br=new BufferedReader(new FileReader("array.txt"));
		int n=0;
		String Str_="";
		while ((Str_=br.readLine()) != null) 
        {
			n++;
		}
		return n;
	}
	/**
	*method: getCityString
	*param: null
	*return String[]
	*/
	private static String[] getCityString()throws IOException
	{
		//
		BufferedReader br=new BufferedReader(new FileReader("array.txt"));
		String Str="";
		String Str_="";

		char regx=';';
		int n=0;
		while ((Str_=br.readLine()) != null) 
        {
			n++;
			Str+=Str_;
			Str+=regx;

		}
		Str=removeLastRegx(Str);
		
		//get the line to a array[]
		String[] _array=new String[n];
		_array=splitString(Str,(int)regx);
		return _array;
	}
	/**
	*method: splitString
	*param: args the string to split
	*param: c	the char you want to match
	*return:  a array 
	*/
	public static String[] splitString(String arg,int c)
	{	
		String[] _array=new String[CITY_NUMBER];
		int cc=0;
		//System.out.println(arg.indexOf(c));
		
		while(arg.indexOf(c)!=-1)
        {
			_array[cc]=arg.substring(0,arg.indexOf(c));
			arg=arg.substring(arg.indexOf(c)+1,arg.length());
			cc++;
        }
		_array[cc]=arg;

    	return _array;
	}
	/**
	*method: cut the last char form the String
	*/
	public static String removeLastRegx(String args)
	{
		//return args.substring(0,args.length()-1);
		if (args!=null)
		{
			return args.substring(0,args.length()-1);
		}
		else
		{
			return args;
		}
	}

	/**
	*method: getFirstRoute
	*param: CityMap
	*return: CityMap
	*/
	private static CityMap[] getFirstRoute(CityMap[] cm)
	{
		//

		return getRoute(cm); 
	}

	
	/**
	*method: newT
	*param: double T
	*return: double a lower T
	*/
	private static double newT(double t)
	{
		return t*CONTROL_T;
	}
	/**
	*method: get_exp
	*param: double_________________________________________________________________________-
	*return: double
	*/
	private static double get_exp(double del)
	{
		//
		//System.out.println("Math.E"+Math.E);
		//System.out.println("del/T"+del/T);
		return Math.pow(Math.E,100*del/T);

	}
	/**
	*method: showMap(citymap)
	*param: CityMap[]
	*return: void
	*/
	private static void showMap(CityMap[] cm)
	{
		System.out.println("the city map is:\n______start________");
		int n=CITY_NUMBER;
		int count=0;
		for (int i=0;i<n;i++)
		{	
			if (count % 18==0)
			{
				System.out.print("\n");
			}
			count++;
			//System.out.print("--"+cm[i].getcity()+"("+cm[i].getxpos()+", "+cm[i].getypos()+")");
			System.out.print("--"+cm[i].getcity());
		}
		System.out.println("\n_______end_________");

	}
	/**
	*method:getRandomInt
	*/
	private static int getRandomInt()
	{
		Random random1 = new Random();
		return 1+(int)(Math.abs(random1.nextDouble())*(CITY_NUMBER-1))%(CITY_NUMBER-1);
	}
	/**
	*method: getRandomDouble()
	*/
	private static double getRandomDouble()
	{
		Random random1 = new Random();
		return Math.abs(random1.nextDouble());
	}
	/**
	*method:getRouteValue()
	*param:
	*return: double
	*/
	private static double getRouteValue()
	{
		CityMap[] cm=new CityMap[CITY_NUMBER];
		cm=copy(citymap);
		double routevalue=0.0;
		double px,py,qx,qy;
		for (int i=0;i<CITY_NUMBER-1;i++)
		{
			px=cm[i].getxpos();
			py=cm[i].getypos();
			qx=cm[i+1].getxpos();
			qy=cm[i+1].getypos();
			routevalue+=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);

		}
		double first_end;
		px=cm[0].getxpos();
		py=cm[0].getypos();
		qx=cm[CITY_NUMBER-1].getxpos();
		qy=cm[CITY_NUMBER-1].getypos();
		first_end=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
		return routevalue+first_end;

	}
	/**
	*method:getRouteValue()
	*param:
	*return: double
	*/
	private static double getRouteValue(CityMap[] cm)
	{
		//CityMap[] cm=new CityMap[CITY_NUMBER];
		//cm=citymap;
		double routevalue=0.0;
		double px,py,qx,qy;
		for (int i=0;i<CITY_NUMBER-1;i++)
		{
			px=cm[i].getxpos();
			py=cm[i].getypos();
			qx=cm[i+1].getxpos();
			qy=cm[i+1].getypos();
			routevalue+=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
//			System.out.print("city_"+cm[i].getcity()+"   city_"+cm[i+1].getcity());
//			System.out.println("    "+(Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5)));
//			

		}
		double first_end;
		px=cm[0].getxpos();
		py=cm[0].getypos();
		qx=cm[CITY_NUMBER-1].getxpos();
		qy=cm[CITY_NUMBER-1].getypos();
		first_end=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
//		System.out.print("city_"+cm[0].getcity()+"   city_"+cm[CITY_NUMBER-1].getcity());
//		System.out.println("    "+(Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5)));
//		System.out.println("_____________");
		return routevalue+first_end;

	}
	/**
	*method: setcitymap(CityMap[])
	*param:
	*return: void
	*/
	private static void setcitymap(CityMap[] cm)
	{
		for (int i=0;i<CITY_NUMBER;i++)
		{
			citymap[i].setcity(cm[i].getcity());
			citymap[i].setxpos(cm[i].getxpos());
			citymap[i].setypos(cm[i].getypos());
		}
	}
	
	/**
	*method: settempcitymap(_citymap)
	*param:
	*return: void
	*/
	
	private static CityMap[] settempcitymap(CityMap[] cm)
	{   

		CityMap[] c_m=new CityMap[CITY_NUMBER];
		for (int i=0;i<CITY_NUMBER;i++)
		{	
			c_m[i]=new CityMap();
			c_m[i].setcity(cm[i].getcity());
			c_m[i].setxpos(cm[i].getxpos());
			c_m[i].setypos(cm[i].getypos());
		}
		return c_m;
	}
	/**
	*method: get time
	*param:
	*return: void
	*/
	private static void getTime()
	{
		Date date = new Date(System.currentTimeMillis());
		String strdat="";
		strdat = date.toLocaleString();
		System.out.println("系统时间:"+strdat);

	}
	/**
	*method: copy a array
	*/
	private static CityMap[] copy(CityMap[] cm)
	{
		CityMap[] c_m=new CityMap[CITY_NUMBER];
		for (int i=0;i<CITY_NUMBER;i++)
		{	
			c_m[i]=new CityMap();
			c_m[i].setcity(cm[i].getcity());
			c_m[i].setxpos(cm[i].getxpos());
			c_m[i].setypos(cm[i].getypos());
		}
		return c_m;

	}

	/**
	*method: get another citymap from now citymap
	*param:  CityMap[]
	*return:  CityMap[]
	*change: 2006-3-27
	*/
	private static CityMap[] getRoute(CityMap[] cmap)
	{
		CityMap[] cm=new CityMap[CITY_NUMBER];
		cm=copy(cmap);
		int n,m;
		n=getRandomInt();
		m=getRandomInt();
		//System.out.println("m=:"+m);
		//System.out.println("n=:"+n);
		while(m==n)
		{
			n=getRandomInt();
			m=getRandomInt();
		}
		//System.out.print("m=:"+m);
		//System.out.println("  n=:"+n);
		//CityMap[] _cm=new CityMap[CITY_NUMBER];
		//_cm=swap(cm);
		//System.out.print("m:"+m+" n:"+n);
		String TEMP_pc=cm[m].getcity();
		double TEMP_px=cm[m].getxpos();
		double TEMP_py=cm[m].getypos();
		cm[m].setcity(cm[n].getcity());
		cm[m].setxpos(cm[n].getxpos());
		cm[m].setypos(cm[n].getypos());
		cm[n].setcity(TEMP_pc);
		cm[n].setxpos(TEMP_px);
		cm[n].setypos(TEMP_py);
		
		return cm;
		
	}


	/**
	*method: get another citymap from now citymap
	*param:  CityMap[]
	*return:  CityMap[]
	*change: 2006-3-27 add
	*/
	private static CityMap[] getRoute_(CityMap[] cmap)
	{
		CityMap[] cm=new CityMap[CITY_NUMBER];
		cm=copy(cmap);
		int a,b,c;
		a=getRandomInt();
		b=getRandomInt();
		c=getRandomInt();
		System.out.println("a=:"+a);
		System.out.println("b=:"+b);
		System.out.println("c=:"+c);
		while(a==b||a==c||b==c)
		{
			a=getRandomInt();
			b=getRandomInt();
			c=getRandomInt();
		}
		//System.out.print("m=:"+m);
		//System.out.println("  n=:"+n);
		//CityMap[] _cm=new CityMap[CITY_NUMBER];
		//_cm=swap(cm);
		//System.out.print("m:"+m+" n:"+n);
		String TEMP_pc=cm[a].getcity();
		double TEMP_px=cm[a].getxpos();
		double TEMP_py=cm[a].getypos();
		cm[a].setcity(cm[b].getcity());
		cm[a].setxpos(cm[b].getxpos());
		cm[a].setypos(cm[b].getypos());
		cm[b].setcity(cm[c].getcity());
		cm[b].setxpos(cm[c].getxpos());
		cm[b].setypos(cm[c].getypos());
		cm[c].setcity(TEMP_pc);
		cm[c].setxpos(TEMP_px);
		cm[c].setypos(TEMP_py);
		
		return cm;
		
	}



};