drive.java

模拟退火算法解决旅行商问题

	import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
/*
 * 初始温度选取为280
 * 同一温度内,固定迭代次数为100*number次
 * 同一温度内，若fj<fi,则接受;若fj>fi,exp(-(fj-fi)/tmp)>random(),则也接受
 * 降温算法为t(K+1)=t(K)*0.92
 * 算法结束条件为当连续结果2次相差很小时，即相差小于0.00001倍时结束
 */
public class Drive {
	ArrayList<City> cityList;
	ArrayList<City> list1;
	ArrayList<City> list2;
	int number;//记录城市个数
	double result1;//记录fi
	double result2;//记录fj
	double lastResult=0;
	int last1=0;
	int last2=0;
	public static void main(String[] args){
		Drive drive=new Drive();
		ArrayList<String> str=new ArrayList<String>();
		try{
			File fis=new File("TSP10.txt");
			BufferedReader buf=new BufferedReader(new FileReader(fis)); 
			String r;
			while((r=buf.readLine())!=null){
				str.add(r);
			}
		}catch(FileNotFoundException f){
			System.out.println("file not found");
		}catch(IOException e){
			System.out.println("IOException");
		}	
		drive.input(str);
        drive.init();
		drive.go();	
	}
	public void input(ArrayList<String> strVector){//按文件格式读入数据
		cityList=new ArrayList<City>();
		list1=new ArrayList<City>();
		list2=new ArrayList<City>();
		ArrayList<ArrayList<String>> strArray=new ArrayList<ArrayList<String>>();
		for(int i=0;i<strVector.size();i++){
			String s=strVector.get(i);
			String[] sa=new String[5];
			ArrayList<String> sb=new ArrayList<String>();
			sa=s.split(" |\t");
			for(int j=0;j<sa.length;j++){
				if(sa[j].length()==0) continue;
				sb.add(sa[j]);
			}
			strArray.add(sb);
		}
		number=Integer.parseInt(strArray.get(0).get(0));
		for(int i=1;i<strArray.size();i++){
			if(strArray.get(i).size()==3){
				String name=strArray.get(i).get(0);
				double xCoo=Double.parseDouble(strArray.get(i).get(1));
				double yCoo=Double.parseDouble(strArray.get(i).get(2));
				City c=new City(name,xCoo,yCoo);
				cityList.add(c);
			}
		}
		
	}
	public void init(){//随机选择一个初始解
		for(int i=0;i<5;i++){
			changeState();
			receive();
		}
	}
	public void go(){
		double tmp=280.0;
		int stay=0;
		int outer=0;//		
		while(true){//外层循环
			int inner=0;//内层循环次数
			while(true){//内层循环
				if(inner>100*number)//若连续5次未接受新状态，则结束内循环
					break;	
				inner++;
				changeState();
				if(result2<result1){//若fj<fi,则接受
					receive();
				}
				else{//否则，则若exp(-(fj-fi)/tmp)>random()，则也接受（random()为0至1中的一个随机数）
					double delta=result2-result1;
					double p=Math.exp(-delta/tmp);
					double r=Math.random();
					if(p>r){
						receive();
					}
				}
			}
			System.out.println("第"+outer+"次降温温度为"+tmp+"     结果为    :");//输出此次结果
			System.out.print(result1+"   ");
			System.out.print(cityList.get(0).name);
			for(int i=1;i<number;i++)
				System.out.print("--"+cityList.get(i).name);
			System.out.println("");
			tmp=tmp*0.92;
			outer++;
			double Result=0.0;
			for(int i=0;i<number-1;i++)
				Result+=dis(cityList.get(i),cityList.get(i+1));
			Result+=dis(cityList.get(0),cityList.get(number-1));
			if(Math.abs(Result-lastResult)<Result*0.00001)
				stay++;
			else 
				stay=0;			
			lastResult=Result;
			if(stay>2)			
				break;						
		}
	}
	public void changeState(){//随机生成一个邻域内的解
		result1=result2=0.0;
		if(list1.size()==number&&list2.size()==number){
			for(int i=0;i<number;i++){
				list1.set(i,cityList.get(i));
				list2.set(i,cityList.get(i));
			}
		}		
		else if(list1.size()==0&&list2.size()==0){
			list1.addAll(cityList);
			list2.addAll(cityList);
		}
		for(int i=0;i<number-1;i++){
			result1+=dis(list1.get(i),list1.get(i+1));
		}
		result1+=dis(list1.get(number-1),list1.get(0));
		//list2中保存交换某两个城市顺序后的序列
		int k1=0;
		int k2=0;
		while(k1==last1&&k2==last2){//若生成的k1与k2与上次恰好相等，则重新生成
			k1=(int)(Math.random()*number);//k1和k2为从0到number-1当中的随机数
			k2=(int)(Math.random()*number);
		}			
		last1=k1;
		last2=k2;
		if(k1==k2){//若k1=k2，则置k2=(k1+3)%number，以保证两数不等
			k2=(k1+3)%number;
		}
		int temp=Math.max(k1,k2);
		k1=Math.min(k1,k2);
		k2=temp;
		while(k1<k2){
			City tempCity=new City(list2.get(k1));//交换两城市，
			list2.set(k1, list2.get(k2));
			list2.set(k2, tempCity);
			k1++;k2--;
		}
		for(int i=0;i<number-1;i++){
			result2+=dis(list2.get(i),list2.get(i+1));
		}
		result2+=dis(list2.get(number-1),list2.get(0));
	}
	public double dis(City c1,City c2){//求两个城市之间的距离
		return Math.sqrt(Math.pow(c1.x-c2.x,2)+Math.pow(c1.y-c2.y, 2));
	}
	public void receive(){//接受转移
		for(int i=0;i<number;i++)
			cityList.set(i, list2.get(i));
	}
}