模拟退火（Simulated Annealing)——C語言實作

概述

說退火之前，先來說一說爬山算法（Hill Climbing)，一種簡單的貪心搜尋算法，從臨近解中選擇一個較優解，循環一直到得到一個最優解，就像是爬山一樣，在左右山腰一直跳躍，直到達到山頂為止，但是這個算法有個主要的缺陷就是會陷入局部最優解，就像是爬山爬到一個山峰，但這個不是最高的山峰。那麼為了跳出局部最優解而得到整體最優解，就有了這種模拟退火的思想。

模拟退火思想

所謂模拟退火算法（SA算法），思想借鑒了實體中固體的退火過程，并結合組合優化問題之間的聯系，得到了這樣一種求整體最優解的優化算法。大緻分成了三個部分：加溫過程，等溫過程，冷卻過程。

通俗的講，就是在爬山算法的基礎上，設定一個可能性，這個可能性會讓它跳出目前的局部最優狀況，也就是從一個山頭，跳到另一個山頭或者是山腰上。這樣能夠跳出爬山算法的局部最優解的限制，調整溫度參數，可以很大程度上得到整體最優解。當然，模拟退火一定程度上是有一定機率接受惡化的解，這個是跳出局部最優的保證。

操作步驟

（1）初始化溫度T0，取一個合适的足夠大的數，T = T0， 确定每個T的疊代次數L，終止溫度T_end。

（2）得到一個初始解，可以随機給出一種路徑，或者采用貪心得到一個路徑L1。（後者較好，這樣優化的次數可以少一些，減少時間耗費）

（3）對目前的路徑随機産生一個擾動，（可以用2-opt擾動，參照筆者的另一篇文章）産生一個新的路徑L2。

（4）計算新路徑的增量D = f（L2） - f（L1），其中的f為一個代價函數，一般來說，對于路徑問題就是路徑長度。

（5）判斷D與0的關系，若f (L2） < f（L1），則更新解為L2，即另L1 = L2；否則一定的機率下，我們仍然更新解L2，這個機率滿足exp（-D/T），也就是随機産生一個（0，1）上的随機數n，若exp（-D/T） > n，則更新解為L2，否則不更新解。然後溫度T衰減，也就是T = T * q（q為一個（0，1）的函數，表示衰減函數）

（6）重複（3），（4），（5）對溫度T，和次數num = 1， 2，3…，L（疊代次數）

（7）滿足條件，停止循環，L1則為優化過的整體最優解。條件為：在連續N個疊代L次後新的解L2都沒有被接受，或者是溫度T達到終止溫度T_end。

代碼實作

int main() {
	game_state_t state;
	memset(&state, 0, sizeof(state));
	init(&state);
//       frome here X1
	int i, j;
	double T = T0;
	double minpath = 0;
	double minpath1 = 0;
	n = state.n;
	m = state.m;
	op.x = state.start_x, op.y = state.start_y;
	AdjGraph G;
	Init(state, &G);
	Floyd(G);
	int num_in = (state.start_x * m + state.start_y);
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (state.food[i][j] == 1) {
				n_food[count] = i * m + j;
				count++;
			}
		}
	}
	count1 = count;
	while (count > 0) {
		int nearest;
		double MIN = 9999.9;
		for (i = 0; i < m * n; i++) {
			int u = i / m;
			int v = i % m;
			if (state.food[u][v] == 1 && A[num_in][i] < MIN && num_in != i) {
				MIN = A[num_in][i];
				nearest = i;
			}
		}
		minpath += MIN;
		int num_out = nearest;
		num_in = num_out;
		state.food[num_out / m][num_out % m] = 0;
		pathway[count1 - count] = num_out;
		count--;
	}
	//to here X1這一部分貪心求一個解
	num_in = (state.start_x * m + state.start_y);
	srand((unsigned)time(NULL));
	while (T > T_end) {            //from here X2
		for (int k = 0;k < L; k++) {
			int n1, n2;
			n1 = rand() % count1;
			do {
				n2 = rand() % count1;
			} while (n1 == n2);
			if (n1 > n2) {
				swap(&n1, &n2);
			}
			int left = n1, right = n2;
			while (left < right) {
				swap(&pathway[left], &pathway[right]);
				left++; right--;
			}
			minpath1 = 0;
			for (i = 0; i < count1 - 1; i++) {
				minpath1 += A[pathway[i]][pathway[i + 1]];
			}
			minpath1 += A[num_in][pathway[0]];
			if (minpath1 < minpath) {
				minpath = minpath1;
			}
			else {
				double r = (rand() % 100000)*0.00001;
				if (exp((minpath - minpath1) / T <= r)) {
					left = n1, right = n2;
					while (left < right) {
						swap(&pathway[left], &pathway[right]);
						left++; right--;
					}
				}
			}
		}
		T *= q;
	}
	// to here X2 使用2-opt模拟退火優化貪心求出來的解
	// from here X3
	for (i = 0; i < count1; i++) {
		int num_out = pathway[i];
		BFS(G, num_in, num_out);
		transfor(num_out, &state);
		j = 0;
		while (path_BFS[j] != num_out) {
			printf("%c", p[j]);
			j++;
		}
		num_in = num_out;
	}
	// to here X3 輸出路徑
	destroy(&state);
	system("PAUSE");
	return 0;
}

           

關于裡面使用的宏定義，需要讀者自己去定義，并通過實驗的出一個最優的數字，如果需要筆者完整的資料結構，可自取

https://github.com/yiguang-hack/SA/tree/master