一.模擬退火演算法概述
模擬退火演算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis準則，粒子在溫度T時趨於平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變數，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函式值f，溫度T演化成控制引數t，即得到解組合優化問題的模擬退火演算法：由初始解i和控制引數初值t開始，對當前解重複“產生新解→計算目標函式差→接受或捨棄”的迭代，並逐步衰減t值，演算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啟發式隨機搜尋過程。退火過程由冷卻進度表(Cooling
Schedule)控制，包括控制引數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。
二.流程圖
Java程式碼 
- 偽碼描述:
- Simulated-Annealing()
- Create initial solution S
- repeat
- for i=1 to iteration-length do
- Generate a random transition from S to Si
- If ( C(S) <= C(Si) ) then
- S=Si
- else if( exp(C(S)-C(Si))/kt > random[0,1) ) then
- S=Si
- Reduce Temperature t
- until ( no change in C(S) )
- C(S): Cost or Loss function of Solution S
三.旅行商問題上的應用
旅行商問題就是指旅行商按一定的順序訪問N個城市的每個城市,使得每個城市都能被訪問且僅能被訪問一次,最後回到起點,而使花費的代價最小。本例中從第0個城市開始然後回到原點.
示例程式碼:
Java程式碼
- /**
- *
- */
- package anneal.tsp;
- import java.io.BufferedReader;
- import java.io.File;
- import java.io.FileReader;
- import java.io.IOException;
- import java.util.Arrays;
- import java.util.Random;
- /**
- * @author Dukie 下午02:22:13 2010
- *
- */
- public class Anneal {
- private static double[][] city;
- private static int[] currPath;
- private static int[] bestPath;
- private static double shortesDistance;
- private static int numOfCity = 20;
- //trace item
- private static int iterator = 0;
- public void printInfo() {
- System.out.println(“bestPath: ” Arrays.toString(bestPath));
- System.out.println(“shortest distance: ” shortesDistance);
- System.out.println(“iterator times: ” iterator);
- }
- private void init() throws IOException {
- city = new double[numOfCity][numOfCity];
- currPath = new int[numOfCity];
- bestPath = new int[numOfCity];
- shortesDistance = 0;
- loadCity();
- int lenth = currPath.length;
- for (int i = 0; i < lenth; i ) {
- currPath[i] = i;
- }
- }
- private void loadCity() throws IOException {
- //DistanceMatrix.csv” a file stores the distance info.
- File file = new File(“E:\\TSP\\DistanceMatrix.csv”);
- inputGraph(file, city);
- }
- private void inputGraph(File file, double[][] city) throws IOException {
- BufferedReader in = new BufferedReader(new FileReader(file));
- String str = “”;
- int length = 0;
- while ((str = in.readLine()) != null) {
- str = str.replaceAll(“, “, “,”);
- String[] line = str.split(“,”);
- for (int j = 0; j < numOfCity; j )
- // ten cities
- city[length][j] = Double.parseDouble(line[j]);
- length ;
- }
- }
- /**
- * key function
- * @throws IOException
- */
- public void anneal() throws IOException {
- double temperature = 10000.0D;
- double deltaDistance = 0.0D;
- double coolingRate = 0.9999;
- double absoluteTemperature = 0.00001;
- init();
- double distance = getToatalDistance(currPath);
- int[] nextPath;
- Random random = new Random();
- while (temperature > absoluteTemperature) {
- nextPath = generateNextPath();
- deltaDistance = getToatalDistance(nextPath) – distance;
- if ((deltaDistance < 0)
- || (distance > 0 &&
- Math.exp(-deltaDistance / temperature) > random.nextDouble())) {
- currPath = Arrays.copyOf(nextPath, nextPath.length);
- distance = deltaDistance distance;
- }
- temperature *= coolingRate;
- iterator ;
- System.out.println(“iterator: ” iterator ” path: ” Arrays.toString(currPath));
- }
- shortesDistance = distance;
- System.arraycopy(currPath, 0, bestPath, 0, currPath.length);
- }
- /**
- * calculate total distance
- * @param currPath
- * @return
- */
- private double getToatalDistance(int[] currPath) {
- int length = currPath.length;
- double totalDistance = 0.0D;
- for (int i = 0; i < length – 1; i ) {
- totalDistance = city[currPath[i]][currPath[i 1]];
- }
- totalDistance = city[currPath[length – 1]][0];
- return totalDistance;
- }
- /**
- * swap two elements in the old array to genreate new array
- * @return
- */
- private int[] generateNextPath() {
- int[] nextPath = Arrays.copyOf(currPath, currPath.length);
- Random random = new Random();
- int length = nextPath.length;
- int fistIndex = random.nextInt(length – 1) 1;
- int secIndex = random.nextInt(length – 1) 1;
- while (fistIndex == secIndex) {
- secIndex = random.nextInt(length – 1) 1;
- }
- int tmp = nextPath[fistIndex];
- nextPath[fistIndex] = currPath[secIndex];
- nextPath[secIndex] = tmp;
- return nextPath;
- }
- }
20個城市測試資料:
Java程式碼
- 0, 11893, 14633, 10172, 8078, 12843, 10079, 14395, 8056, 14232, 11714, 9309, 12517, 11574, 9720, 13727, 13852, 14330, 10660, 8138
- 11893, 0, 10568, 9031, 11050, 9039, 10622, 14138, 8738, 9122, 8817, 13099, 9984, 13063, 11546, 11379, 8850, 14111, 13775, 8073
- 14633, 10568, 0, 14174, 13338, 12629, 14418, 10391, 14444, 12956, 14040, 12835, 13486, 14249, 14039, 8186, 14730, 8886, 12862, 12365
- 10172, 9031, 14174, 0, 9422, 11814, 14133, 11645, 10495, 13099, 14712, 14988, 11662, 14561, 13350, 10781, 14886, 11549, 13044, 11194
- 8078, 11050, 13338, 9422, 0, 9868, 11492, 12416, 14672, 12894, 11181, 14310, 9231, 12697, 12617, 8856, 11850, 13302, 12558, 11165
- 12843, 9039, 12629, 11814, 9868, 0, 10069, 10605, 8799, 9295, 14078, 12349, 14367, 9501, 11379, 13431, 10723, 8845, 10427, 14821
- 10079, 10622, 14418, 14133, 11492, 10069, 0, 12734, 8656, 13830, 12681, 13165, 11583, 8610, 9202, 9838, 10755, 10674, 13881, 13024
- 14395, 14138, 10391, 11645, 12416, 10605, 12734, 0, 11980, 13753, 11174, 14603, 13478, 12543, 12974, 11059, 8799, 11781, 13797, 9287
- 8056, 8738, 14444, 10495, 14672, 8799, 8656, 11980, 0, 11108, 8725, 11253, 12277, 13086, 9476, 12513, 9597, 11850, 13866, 8605
- 14232, 9122, 12956, 13099, 12894, 9295, 13830, 13753, 11108, 0, 14301, 8065, 13706, 9212, 8301, 8258, 14817, 9277, 12742, 14550
- 11714, 8817, 14040, 14712, 11181, 14078, 12681, 11174, 8725, 14301, 0, 8133, 13841, 9062, 10704, 13366, 13779, 13710, 12832, 12812
- 9309, 13099, 12835, 14988, 14310, 12349, 13165, 14603, 11253, 8065, 8133, 0, 8079, 9554, 9760, 11617, 10566, 9382, 12105, 11755
- 12517, 9984, 13486, 11662, 9231, 14367, 11583, 13478, 12277, 13706, 13841, 8079, 0, 9991, 14717, 13082, 11787, 14614, 11698, 10970
- 11574, 13063, 14249, 14561, 12697, 9501, 8610, 12543, 13086, 9212, 9062, 9554, 9991, 0, 14363, 8175, 12309, 9042, 11251, 9250
- 9720, 11546, 14039, 13350, 12617, 11379, 9202, 12974, 9476, 8301, 10704, 9760, 14717, 14363, 0, 12291, 12173, 10971, 9000, 9868
- 13727, 11379, 8186, 10781, 8856, 13431, 9838, 11059, 12513, 8258, 13366, 11617, 13082, 8175, 12291, 0, 14291, 12915, 9583, 9671
- 13852, 8850, 14730, 14886, 11850, 10723, 10755, 8799, 9597, 14817, 13779, 10566, 11787, 12309, 12173, 14291, 0, 13657, 8621, 9089
- 14330, 14111, 8886, 11549, 13302, 8845, 10674, 11781, 11850, 9277, 13710, 9382, 14614, 9042, 10971, 12915, 13657, 0, 9709, 10960
- 10660, 13775, 12862, 13044, 12558, 10427, 13881, 13797, 13866, 12742, 12832, 12105, 11698, 11251, 9000, 9583, 8621, 9709, 0, 13131
- 8138, 8073, 12365, 11194, 11165, 14821, 13024, 9287, 8605, 14550, 12812, 11755, 10970, 9250, 9868, 9671, 9089, 10960, 13131, 0
在我機上對20個頇城市進行測試後,效果比較好. 對10城市時,在幾秒鐘來就達到全域性最優解.
注意:模擬退火演算法與初始值無關，演算法求得的解與初始解狀態S(是演算法迭代的起點)無關；模擬退火演算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂於全域性最優解的全域性優化演算法；模擬退火演算法具有並行性。