TSP-模拟退火算法求解

    package com.chb.Tabu;
    
    import java.io.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.util.Random;
    import java.util.Scanner;
    
    public class Data {
    	public static int cityNum=48;//城市数量，手动设置
    	public static final int N=40;//每个温度迭代的步长
    	public static final int T=400;//降温次数
    	public static final float a=0.98f;//降温系数
    	public static final float t0=250.0f;//初始温度
    	public static int bestT;//最佳的迭代次数
    	
    	public static int[]Ghh=new int[cityNum];//初始路径编码
    	public static int bestGh[]=new int[cityNum];//最好的路径编码
    	public static int[]tempGh=new int[cityNum];//存放临时编码
    	public static int bestEvaluation;
    	public static int GhhEvaluation;
    	public static int tempEvaluation;
    	
    	public static int point[][]=new int[cityNum][2];//每个城市的坐标
    	public static int dist[][]=new int[cityNum][cityNum];//距离矩阵
    	public static Random random;
    	
    
    	//读取数据并初始化
    	public static void read_data(String filepath) throws FileNotFoundException {
    		String line=null;
    		String substr[]=null;
    		Scanner cin=new Scanner(new BufferedReader(new FileReader(filepath)));
    		for (int i = 0; i < cityNum; i++) {
    			line=cin.nextLine();
    			line.trim();
    			substr=line.split(" ");
    			 point[i][0]=Integer.parseInt(substr[1]);//x坐标
    			 point[i][1]=Integer.parseInt(substr[2]);//y坐标
    		}
    		cin.close();
    		//计算距离矩阵，注意这里的计算方式，才用的是伪欧式距离
    		for (int i = 0; i < cityNum; i++) {
    			dist[i][i]=0;//对角线元素为0
    			for (int j = i+1; j < cityNum; j++) {
    				double rij=Math.sqrt((Math.pow(point[i][0]-point[j][0], 2)+
    						             Math.pow(point[i][1]-point[j][1], 2))/10.0);
    				//rij四舍五入取整
    				int tij=(int) Math.round(rij);
    				if(tij<rij) {
    					dist[i][j]=tij+1;
    					dist[j][i]=dist[i][j];
    				}else {
    					dist[i][j]=tij;
    					dist[j][i]=dist[i][j];
    				}
    			}
    		}
    		dist[cityNum-1][cityNum-1]=0;
    		
    		bestT=0;
    		bestEvaluation=Integer.MAX_VALUE;
    		GhhEvaluation=Integer.MAX_VALUE;
    		tempEvaluation=Integer.MAX_VALUE;
    		random=new Random(System.currentTimeMillis());
    	}
    }
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    

    package com.chb.Tabu;
    
    import java.io.FileNotFoundException;
    
    public class SA {
    	//初始化编码Ghh
    	public static void initGroup() {
    		Data.Ghh[0]=Data.random.nextInt(65535)%Data.cityNum;
    		int i,j;
    		//使得产生的每个基因都不一样
    		for (i = 1; i < Data.cityNum;) {
    			Data.Ghh[i]=Data.random.nextInt(65535)%Data.cityNum;
    			for (j = 0; j < i; j++) {
    				if(Data.Ghh[i]==Data.Ghh[j]) {
    					break;
    				}
    			}
    			if(j==i) {
    				i++;
    			}
    		}
    	}
    	//复制操作，将Gha复制到Ghb
    	public static void copyGh(int[]Gha,int[]Ghb) {
    		for (int i = 0; i < Data.cityNum; i++) {
    			Ghb[i]=Gha[i];
    		}
    	}
    	//评价函数
    	public static int evaluate(int[] chr) {
    		int len=0;
    		for (int i = 1; i < Data.cityNum; i++) {
    			len+=Data.dist[chr[i-1]][chr[i]];
    		}
    		len+=Data.dist[chr[Data.cityNum-1]][chr[0]];
    		return len;
    	}
    	//领域交换，得到邻居
    	public static void Linju(int[]Gh,int[]tempGh) {
    		int i,temp;
    		int rand1,rand2;
    		//将Gh复制到tempGh
    		for (i = 0; i < Data.cityNum; i++) {
    			tempGh[i]=Gh[i];
    		}
    		rand1=Data.random.nextInt(65535)%Data.cityNum;
    		rand2=Data.random.nextInt(65535)%Data.cityNum;
    		while(rand1==rand2) {
    			rand2=Data.random.nextInt(65535)%Data.cityNum;
    		}
    		//交换
    		temp=tempGh[rand1];
    		tempGh[rand1]=tempGh[rand2];
    		tempGh[rand2]=temp;
    	}
    	public static void solve() {
    		initGroup();
    		copyGh(Data.Ghh, Data.bestGh);
    		Data.bestEvaluation=evaluate(Data.Ghh);
    		Data.GhhEvaluation=Data.bestEvaluation;
    		int k = 0;// 降温次数
    		int n = 0;// 迭代步数
    		float t = Data.t0;
    		float r = 0.0f;
    		while(k<Data.T) {
    			n = 0;
    			while(n<Data.N) {
    				Linju(Data.Ghh,Data.tempGh);
    				Data.tempEvaluation=evaluate(Data.tempGh);
    				if(Data.tempEvaluation<Data.bestEvaluation) {
    					copyGh(Data.tempGh, Data.bestGh);
                    Data.bestT = k;
                    Data.bestEvaluation = Data.tempEvaluation;
    				}
    				r = Data.random.nextFloat();
    				if (Data.tempEvaluation < Data.GhhEvaluation
    						|| Math.exp((Data.GhhEvaluation - Data.tempEvaluation) / t) > r) {
    					copyGh(Data.tempGh,Data.Ghh);
    					Data.GhhEvaluation = Data.tempEvaluation;
    			    }
    				n++;
    		    }
    			t = Data.a * t;
            k++;
     	}
    		System.out.println("最佳迭代次数:"+Data.bestT);
    		System.out.println("最佳长度为:"+Data.bestEvaluation);
    		System.out.println("最佳路径为:");
    		for (int i = 0; i < Data.cityNum; i++) {
    			System.out.print(Data.bestGh[i]+"-->");
    		}
    	}
    	public static void main(String[] args) throws FileNotFoundException {
    		Data.read_data("data/att48.txt");
    		SA.solve();
    	}
    }