现代优化计算方法-模拟退火算法解决TSP问题

模拟退火算法(SA)解决TSP问题

题目的要求和数据和上一次一致，48个城市，对称性TSP问题，这次用的是SA算法，效果依旧不好。感觉课本上介绍的最基本的智能优化算法根本找不到最优解，需要对其中的算子进行富有创造性地改造（手动滑稽）。。。个人感觉优化就是一种玄学。

package simulated_annealing;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.*;

public class SA {
	private int CITYnum; //城市数量
	private double[][] Distance; //城市间距离矩阵
	private double Ts; //初始温度
	private int K; //降温次数
	private int N; //每次降温迭代的次数
	private double a; //降温系数（线性降温）
	private double Te; //最终温度
	private int[] Fcode; //初始解数组
	private int[] Bestcode; //最好解数组
	private double Bestsolution; //最佳路径
	private int[] temp; //临时存在编码的数组
	private double tempdistance; //临时存在编码所代表的距离
	private double distance; //邻居代表的距离
	
	//构造函数
	public SA(int cITYnum, double ts, int k, int n, double a) {
		CITYnum = cITYnum;
		Ts = ts;
		K = k;
		N = n;
		this.a = a;
	}
	
	//读取数据
	public void read_data(String filename) throws IOException{
		int[] x = new int[CITYnum]; //定义x坐标
		int[] y = new int[CITYnum]; //定义y坐标
		Distance = new double[CITYnum][CITYnum]; //定义距离矩阵
		String strbuff;
		@SuppressWarnings("resource")
		BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename))); //读取数据文件
		//获得每个城市的坐标
		for(int i=0;i<CITYnum;i++){
			strbuff = data.readLine();
			String[] s = strbuff.split(" "); //数据之间有空格
			x[i] = Integer.valueOf(s[1]); //读取x坐标
			y[i] = Integer.valueOf(s[2]); //读取y坐标
		}
		//计算距离获得距离矩阵
		for(int i=0;i<CITYnum;i++){
			for(int j=0;j<CITYnum;j++){
				double Dij = Math.sqrt(((Math.pow(x[i]-x[j], 2))+(Math.pow(y[i]-y[j], 2)))/10.0); //距离计算公式
				 Distance[i][j] = Dij;
			}
		}
	}
	
	//得到初始解
	public void init(){
		temp = new int[CITYnum];
		Bestcode = new int[CITYnum];
		Fcode = new int[CITYnum];
		int i,k;
		Fcode[0] = (int) (Math.random()*48);
		for(i=1;i<CITYnum;){
			Fcode[i] = (int) (Math.random()*48);
			for(k=0;k<i;k++){
				if(Fcode[i] == Fcode[k]){
					break;
				}
			}
			if(k==i){
				i++;
			}
		}
	}
	
	//得到距离
	public double getDistance(int[] code){
		double length = 0.0;
		for(int i=1;i<CITYnum;i++){
			length += Distance[code[i-1]][code[i]]; //得到中间城市的距离
		}
		length += Distance[code[CITYnum-1]][code[0]]; //首尾城市的距离
		return length;
	}
	
	//复制
	public void copy(int[] a,int[]b){
		for (int i=0;i<CITYnum;i++){
			a[i] = b[i];
		}
	}
	
	//邻居构造
	public void change(int[] code1, int[] code2){
		int rank1,rank2,temp1;
		for(int i=0;i<CITYnum;i++){
			code2[i] = code1[i];
		}
		rank1 = (int) (Math.random()*48);
		rank2 = (int) (Math.random()*48);
		//确保rank1 != rank2
		while(rank1 == rank2){
			rank2 = (int) (Math.random()*48);
		}
		temp1 = code2[rank2];
		code2[rank2] = code2[rank1];
		code2[rank1] = temp1;
	}
	
	//模拟退火
	public void sa(){
		init();
		copy(Bestcode,Fcode);
		Bestsolution = getDistance(Bestcode);
		tempdistance = Bestsolution;
		int k = 0; //降温的次数
		int n = 0; //每次降温迭代的次数
		double r = 0; 
		double t = Ts; //初始温度
		while(k<K){
			n = 0;
			while(n < N){
				change(Fcode,temp);
				distance = getDistance(temp);
				if(distance < Bestsolution){
					copy(Bestcode,temp);
					Bestsolution = distance;
				}
				r = Math.random(); //产生(0,1)之间的随机数
				if(distance < tempdistance || Math.exp((distance - tempdistance) / t) > r){
					copy(Fcode,temp);
				    tempdistance = distance;
					}
				n++;
				}
			t = t*a;
			k++;
		}
		Te = t;
		System.out.println("最终温度为:"+Te);
		System.out.println("最小长度为:"+Bestsolution);
		System.out.println("最优路径为:");
		for(int j=0;j<CITYnum;j++){
			System.out.print(Bestcode[j]+" ");
		}
	}

	public static void main(String[] args) throws IOException{
		SA s = new SA(48,250,500,40,0.98);
		s.read_data("/home/mouye/aat48.txt");
		s.sa();
	}
}

赏

谢谢老板

支付宝

微信