天天看點

基于禁忌搜尋算法求解TSP問題(JAVA)

一、TSP問題

TSP問題(Travelling Salesman Problem)即旅行商問題,又譯為旅行推銷員問題、貨郎擔問題,是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市,他必須選擇所要走的路徑,路徑的限制是每個城市隻能拜訪一次,而且最後要回到原來出發的城市。路徑的選擇目标是要求得的路徑路程為所有路徑之中的最小值。

TSP問題是一個組合優化問題。該問題可以被證明具有NPC計算複雜性。TSP問題可以分為兩類,一類是對稱TSP問題(Symmetric TSP),另一類是非對稱問題(Asymmetric TSP)。所有的TSP問題都可以用一個圖(Graph)來描述:

V={c1, c2, …, ci, …, cn},i = 1,2, …, n,是所有城市的集合.ci表示第i個城市, n為城市的數目;
E={(r, s): r,s∈ V}是所有城市之間連接配接的集合;
C = {crs: r,s∈ V}是所有城市之間連接配接的成本度量(一般為城市之間的距離);

如果crs = csr, 那麼該TSP問題為對稱的,否則為非對稱的。

一個TSP問題可以表達為:

求解周遊圖G = (V, E, C),所有的節點一次并且回到起始節點,使得連接配接這些節點的路徑成本最低。

二、禁忌搜尋算法

禁忌搜尋(Tabu Search或Taboo Search,簡稱TS)的思想最早由Glover(1986)提出,它是對局部領域搜尋的一種擴充,是一種全局逐漸尋優算法,是對人類智力過程的一種模拟。其特點是采用禁忌技術,即用一個禁忌表記錄下已經到達過的局部最優點,在下一次搜尋中,利用禁忌表中的資訊不再或有選擇地搜尋這些點,以此來跳出局部最優點。該算法可以克服爬山算法全局搜尋能力不強的弱點。

在禁忌搜尋算法中,首先按照随機方法産生一個初始解作為目前解,然後在目前解的鄰域中搜尋若幹個解,取其中的最好解作為新的目前解。為了避免陷入局部最優解,這種優化方法允許一定的下山操作(使解的品質變差)。另外,為了避免對已搜尋過的局部最優解的重複,禁忌搜尋算法使用禁忌表記錄已搜尋的局部最優解的曆史資訊,這可在一定程度上使搜尋過程避開局部極值點,進而開辟新的搜尋區域。

禁忌搜尋最重要的思想是标記對應已搜尋的局部最優解的一些對象,并在進一步的疊代搜尋中盡量避開這些對象(而不是絕對禁止循環),進而保證對不同的有效搜尋途徑的探索。禁忌搜尋涉及到臨域(neighborhood)、禁忌表(tabu list)、禁忌長度(tabu length)、候選解(candidate)、藐視準則(aspiration criterion)等概念。

禁忌搜尋算法實施步驟:

基于禁忌搜尋算法求解TSP問題(JAVA)

三、禁忌搜尋算法求解TSP問題

在該JAVA實作中我們選擇使用tsplib上的資料att48,這是一個對稱TSP問題,城市規模為48,其最優值為10628.其距離計算方法下圖所示:

基于禁忌搜尋算法求解TSP問題(JAVA)

具體代碼如下:

package noah;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

public class Tabu {

	private int MAX_GEN;// 疊代次數
	private int N;// 每次搜尋鄰居個數
	private int ll;// 禁忌長度
	private int cityNum; // 城市數量,編碼長度

	private int[][] distance; // 距離矩陣
	private int bestT;// 最佳出現代數

	private int[] Ghh;// 初始路徑編碼
	private int[] bestGh;// 最好的路徑編碼
	private int bestEvaluation;
	private int[] LocalGhh;// 當代最好編碼
	private int localEvaluation;
	private int[] tempGhh;// 存放臨時編碼
	private int tempEvaluation;

	private int[][] jinji;// 禁忌表

	private int t;// 目前代數

	private Random random;

	public Tabu() {

	}

	/**
	 * constructor of GA
	 * 
	 * @param n
	 *            城市數量
	 * @param g
	 *            運作代數
	 * @param c
	 *            每次搜尋鄰居個數
	 * @param m
	 *            禁忌長度
	 * 
	 **/
	public Tabu(int n, int g, int c, int m) {
		cityNum = n;
		MAX_GEN = g;
		N = c;
		ll = m;
	}

	// 給編譯器一條指令,告訴它對被批注的代碼元素内部的某些警告保持靜默
	@SuppressWarnings("resource")
	/**
	 * 初始化Tabu算法類
	 * @param filename 資料檔案名,該檔案存儲所有城市節點坐标資料
	 * @throws IOException
	 */
	private void init(String filename) throws IOException {
		// 讀取資料
		int[] x;
		int[] y;
		String strbuff;
		BufferedReader data = new BufferedReader(new InputStreamReader(
				new FileInputStream(filename)));
		distance = new int[cityNum][cityNum];
		x = new int[cityNum];
		y = new int[cityNum];
		for (int i = 0; i < cityNum; i++) {
			// 讀取一行資料,資料格式1 6734 1453
			strbuff = data.readLine();
			// 字元分割
			String[] strcol = strbuff.split(" ");
			x[i] = Integer.valueOf(strcol[1]);// x坐标
			y[i] = Integer.valueOf(strcol[2]);// y坐标
		}
		// 計算距離矩陣
		// ,針對具體問題,距離計算方法也不一樣,此處用的是att48作為案例,它有48個城市,距離計算方法為僞歐氏距離,最優值為10628
		for (int i = 0; i < cityNum - 1; i++) {
			distance[i][i] = 0; // 對角線為0
			for (int j = i + 1; j < cityNum; j++) {
				double rij = Math
						.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
								* (y[i] - y[j])) / 10.0);
				// 四舍五入,取整
				int tij = (int) Math.round(rij);
				if (tij < rij) {
					distance[i][j] = tij + 1;
					distance[j][i] = distance[i][j];
				} else {
					distance[i][j] = tij;
					distance[j][i] = distance[i][j];
				}
			}
		}
		distance[cityNum - 1][cityNum - 1] = 0;

		Ghh = new int[cityNum];
		bestGh = new int[cityNum];
		bestEvaluation = Integer.MAX_VALUE;
		LocalGhh = new int[cityNum];
		localEvaluation = Integer.MAX_VALUE;
		tempGhh = new int[cityNum];
		tempEvaluation = Integer.MAX_VALUE;

		jinji = new int[ll][cityNum];
		bestT = 0;
		t = 0;

		random = new Random(System.currentTimeMillis());
		/*
		 * for(int i=0;i<cityNum;i++) { for(int j=0;j<cityNum;j++) {
		 * System.out.print(distance[i][j]+","); } System.out.println(); }
		 */

	}

	// 初始化編碼Ghh
	void initGroup() {
		int i, j;
		Ghh[0] = random.nextInt(65535) % cityNum;
		for (i = 1; i < cityNum;)// 編碼長度
		{
			Ghh[i] = random.nextInt(65535) % cityNum;
			for (j = 0; j < i; j++) {
				if (Ghh[i] == Ghh[j]) {
					break;
				}
			}
			if (j == i) {
				i++;
			}
		}
	}

	// 複制編碼體,複制編碼Gha到Ghb
	public void copyGh(int[] Gha, int[] Ghb) {
		for (int i = 0; i < cityNum; i++) {
			Ghb[i] = Gha[i];
		}
	}

	public int evaluate(int[] chr) {
		// 0123
		int len = 0;
		// 編碼,起始城市,城市1,城市2...城市n
		for (int i = 1; i < cityNum; i++) {
			len += distance[chr[i - 1]][chr[i]];
		}
		// 城市n,起始城市
		len += distance[chr[cityNum - 1]][chr[0]];
		return len;
	}

	// 鄰域交換,得到鄰居
	public void Linju(int[] Gh, int[] tempGh) {
		int i, temp;
		int ran1, ran2;

		for (i = 0; i < cityNum; i++) {
			tempGh[i] = Gh[i];
		}
		ran1 = random.nextInt(65535) % cityNum;
		ran2 = random.nextInt(65535) % cityNum;
		while (ran1 == ran2) {
			ran2 = random.nextInt(65535) % cityNum;
		}
		temp = tempGh[ran1];
		tempGh[ran1] = tempGh[ran2];
		tempGh[ran2] = temp;
	}

	// 判斷編碼是否在禁忌表中
	public int panduan(int[] tempGh) {
		int i, j;
		int flag = 0;
		for (i = 0; i < ll; i++) {
			flag = 0;
			for (j = 0; j < cityNum; j++) {
				if (tempGh[j] != jinji[i][j]) {
					flag = 1;// 不相同
					break;
				}
			}
			if (flag == 0)// 相同,傳回存在相同
			{
				// return 1;
				break;
			}
		}
		if (i == ll)// 不等
		{
			return 0;// 不存在
		} else {
			return 1;// 存在
		}
	}

	// 解禁忌與加入禁忌
	public void jiejinji(int[] tempGh) {
		int i, j, k;
		// 删除禁忌表第一個編碼,後面編碼往前挪動
		for (i = 0; i < ll - 1; i++) {
			for (j = 0; j < cityNum; j++) {
				jinji[i][j] = jinji[i + 1][j];
			}
		}

		// 新的編碼加入禁忌表
		for (k = 0; k < cityNum; k++) {
			jinji[ll - 1][k] = tempGh[k];
		}

	}

	public void solve() {
		int nn;
		// 初始化編碼Ghh
		initGroup();
		copyGh(Ghh, bestGh);// 複制目前編碼Ghh到最好編碼bestGh
		bestEvaluation = evaluate(Ghh);

		while (t < MAX_GEN) {
			nn = 0;
			localEvaluation = Integer.MAX_VALUE;
			while (nn < N) {
				Linju(Ghh, tempGhh);// 得到目前編碼Ghh的鄰域編碼tempGhh
				if (panduan(tempGhh) == 0)// 判斷編碼是否在禁忌表中
				{
					// 不在
					tempEvaluation = evaluate(tempGhh);
					if (tempEvaluation < localEvaluation) {
						copyGh(tempGhh, LocalGhh);
						localEvaluation = tempEvaluation;
					}
					nn++;
				}
			}
			if (localEvaluation < bestEvaluation) {
				bestT = t;
				copyGh(LocalGhh, bestGh);
				bestEvaluation = localEvaluation;
			}
			copyGh(LocalGhh, Ghh);

			// 解禁忌表,LocalGhh加入禁忌表
			jiejinji(LocalGhh);
			t++;
		}

		System.out.println("最佳長度出現代數:");
		System.out.println(bestT);
		System.out.println("最佳長度");
		System.out.println(bestEvaluation);
		System.out.println("最佳路徑:");
		for (int i = 0; i < cityNum; i++) {
			System.out.print(bestGh[i] + ",");
		}
	}

	/**
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		System.out.println("Start....");
		Tabu tabu = new Tabu(48, 1000, 200, 20);
		tabu.init("c://data.txt");
		tabu.solve();
	}
}
           

運作結果截圖:

基于禁忌搜尋算法求解TSP問題(JAVA)

四、總結

禁忌算法其主要特點是在搜尋開始階段,解的品質提高很快,随着搜尋過程的繼續,解的品質的提高速度逐漸放緩,甚至在很長的搜尋階段内解的品質沒有太大提高,适合中小規模的NP問題求解,整體效率比較均衡。

(接上一篇爬山算法,個人計劃TSP問題系列大概會有四五種算法來求解,敬請各位期待!)

注:本文部分内容來源于網絡,但程式以及分析結果屬于本人成果,轉載請注明!