NO IMAGE

一.模擬退火演算法概述

  模擬退火演算法來源於固體退火原理,將固體加溫至充分高,再讓其徐徐冷卻,加溫時,固體內部粒子隨溫升變為無序狀,內能增大,而徐徐冷卻時粒子漸趨有序,在每個溫度都達到平衡態,最後在常溫時達到基態,內能減為最小。根據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程式碼  收藏程式碼
  1. 偽碼描述:    
  2. Simulated-Annealing()    
  3. Create initial solution S    
  4. repeat    
  5.     for i=1 to iteration-length do    
  6.         Generate a random transition from S to Si    
  7.         If ( C(S) <= C(Si) ) then    
  8.             S=Si    
  9.         else if( exp(C(S)-C(Si))/kt > random[0,1) ) then    
  10.             S=Si    
  11.     Reduce Temperature t    
  12. until ( no change in C(S) )    
  13.     
  14. C(S): Cost or Loss function of Solution S    

 三.旅行商問題上的應用

    旅行商問題就是指旅行商按一定的順序訪問N個城市的每個城市,使得每個城市都能被訪問且僅能被訪問一次,最後回到起點,而使花費的代價最小。本例中從第0個城市開始然後回到原點.

示例程式碼:

Java程式碼  收藏程式碼
  1. /**  
  2.  *   
  3.  */    
  4. package anneal.tsp;    
  5.     
  6. import java.io.BufferedReader;    
  7. import java.io.File;    
  8. import java.io.FileReader;    
  9. import java.io.IOException;    
  10. import java.util.Arrays;    
  11. import java.util.Random;    
  12.     
  13. /**  
  14.  * @author Dukie 下午02:22:13 2010  
  15.  *   
  16.  */    
  17. public class Anneal {    
  18.     
  19.     private  static double[][] city;    
  20.     private  static int[] currPath;    
  21.     private  static int[] bestPath;    
  22.     private  static double shortesDistance;    
  23.     private  static int numOfCity = 20;    
  24.     //trace item    
  25.     private static int iterator = 0;    
  26.     
  27.     public void printInfo() {    
  28.         System.out.println(“bestPath: ”   Arrays.toString(bestPath));    
  29.         System.out.println(“shortest distance: ”   shortesDistance);    
  30.         System.out.println(“iterator times: ”   iterator);    
  31.     }    
  32.     
  33.     private void init() throws IOException {    
  34.         city = new double[numOfCity][numOfCity];    
  35.         currPath = new int[numOfCity];    
  36.         bestPath = new int[numOfCity];    
  37.         shortesDistance = 0;    
  38.         loadCity();    
  39.         int lenth = currPath.length;    
  40.         for (int i = 0; i < lenth; i ) {    
  41.             currPath[i] = i;    
  42.         }    
  43.     }    
  44.     
  45.     private void loadCity() throws IOException {    
  46.         //DistanceMatrix.csv” a file stores the distance info.    
  47.         File file = new File(“E:\\TSP\\DistanceMatrix.csv”);    
  48.         inputGraph(file, city);    
  49.     }    
  50.     
  51.     private void inputGraph(File file, double[][] city) throws IOException {    
  52.         BufferedReader in = new BufferedReader(new FileReader(file));    
  53.         String str = “”;    
  54.         int length = 0;    
  55.         while ((str = in.readLine()) != null) {    
  56.             str = str.replaceAll(“, “, “,”);    
  57.             String[] line = str.split(“,”);    
  58.             for (int j = 0; j < numOfCity; j )    
  59.                 // ten cities    
  60.                 city[length][j] = Double.parseDouble(line[j]);    
  61.             length ;    
  62.         }    
  63.     }    
  64.     
  65.     /**  
  66.      * key function  
  67.      * @throws IOException  
  68.      */    
  69.     public void anneal() throws IOException {    
  70.     
  71.         double temperature = 10000.0D;    
  72.         double deltaDistance = 0.0D;    
  73.         double coolingRate = 0.9999;    
  74.         double absoluteTemperature = 0.00001;    
  75.     
  76.         init();    
  77.     
  78.         double distance = getToatalDistance(currPath);    
  79.     
  80.         int[] nextPath;     
  81.         Random random = new Random();    
  82.         while (temperature > absoluteTemperature) {    
  83.             nextPath = generateNextPath();    
  84.             deltaDistance = getToatalDistance(nextPath) – distance;    
  85.     
  86.             if ((deltaDistance < 0)    
  87.                     || (distance > 0 &&     
  88.                           Math.exp(-deltaDistance / temperature) > random.nextDouble())) {    
  89.                 currPath = Arrays.copyOf(nextPath, nextPath.length);    
  90.                 distance = deltaDistance   distance;    
  91.             }    
  92.     
  93.             temperature *= coolingRate;    
  94.             iterator ;    
  95.             System.out.println(“iterator: ”   iterator   ” path: ”   Arrays.toString(currPath));    
  96.         }    
  97.         shortesDistance = distance;    
  98.         System.arraycopy(currPath, 0, bestPath, 0, currPath.length);    
  99.     
  100.     }    
  101.     
  102.     /**  
  103.      * calculate total distance  
  104.      * @param currPath  
  105.      * @return  
  106.      */    
  107.     private double getToatalDistance(int[] currPath) {    
  108.         int length = currPath.length;    
  109.         double totalDistance = 0.0D;    
  110.         for (int i = 0; i < length – 1; i ) {    
  111.             totalDistance  = city[currPath[i]][currPath[i   1]];    
  112.         }    
  113.         totalDistance  = city[currPath[length – 1]][0];    
  114.     
  115.         return totalDistance;    
  116.     }    
  117.     
  118.     /**  
  119.      * swap two elements in the old array to genreate new array  
  120.      * @return  
  121.      */    
  122.     private int[] generateNextPath() {    
  123.         int[] nextPath = Arrays.copyOf(currPath, currPath.length);    
  124.         Random random = new Random();    
  125.         int length = nextPath.length;    
  126.         int fistIndex = random.nextInt(length – 1)   1;    
  127.         int secIndex = random.nextInt(length – 1)   1;    
  128.         while (fistIndex == secIndex) {    
  129.             secIndex = random.nextInt(length – 1)   1;    
  130.         }    
  131.         int tmp = nextPath[fistIndex];    
  132.         nextPath[fistIndex] = currPath[secIndex];    
  133.         nextPath[secIndex] = tmp;    
  134.     
  135.         return nextPath;    
  136.     }    
  137.     
  138. }    

 20個城市測試資料:

Java程式碼  收藏程式碼
  1. 0, 11893, 14633, 10172, 8078, 12843, 10079, 14395, 8056, 14232, 11714, 9309, 12517, 11574, 9720, 13727, 13852, 14330, 10660, 8138    
  2. 11893, 0, 10568, 9031, 11050, 9039, 10622, 14138, 8738, 9122, 8817, 13099, 9984, 13063, 11546, 11379, 8850, 14111, 13775, 8073    
  3. 14633, 10568, 0, 14174, 13338, 12629, 14418, 10391, 14444, 12956, 14040, 12835, 13486, 14249, 14039, 8186, 14730, 8886, 12862, 12365    
  4. 10172, 9031, 14174, 0, 9422, 11814, 14133, 11645, 10495, 13099, 14712, 14988, 11662, 14561, 13350, 10781, 14886, 11549, 13044, 11194    
  5. 8078, 11050, 13338, 9422, 0, 9868, 11492, 12416, 14672, 12894, 11181, 14310, 9231, 12697, 12617, 8856, 11850, 13302, 12558, 11165    
  6. 12843, 9039, 12629, 11814, 9868, 0, 10069, 10605, 8799, 9295, 14078, 12349, 14367, 9501, 11379, 13431, 10723, 8845, 10427, 14821    
  7. 10079, 10622, 14418, 14133, 11492, 10069, 0, 12734, 8656, 13830, 12681, 13165, 11583, 8610, 9202, 9838, 10755, 10674, 13881, 13024    
  8. 14395, 14138, 10391, 11645, 12416, 10605, 12734, 0, 11980, 13753, 11174, 14603, 13478, 12543, 12974, 11059, 8799, 11781, 13797, 9287    
  9. 8056, 8738, 14444, 10495, 14672, 8799, 8656, 11980, 0, 11108, 8725, 11253, 12277, 13086, 9476, 12513, 9597, 11850, 13866, 8605    
  10. 14232, 9122, 12956, 13099, 12894, 9295, 13830, 13753, 11108, 0, 14301, 8065, 13706, 9212, 8301, 8258, 14817, 9277, 12742, 14550    
  11. 11714, 8817, 14040, 14712, 11181, 14078, 12681, 11174, 8725, 14301, 0, 8133, 13841, 9062, 10704, 13366, 13779, 13710, 12832, 12812    
  12. 9309, 13099, 12835, 14988, 14310, 12349, 13165, 14603, 11253, 8065, 8133, 0, 8079, 9554, 9760, 11617, 10566, 9382, 12105, 11755    
  13. 12517, 9984, 13486, 11662, 9231, 14367, 11583, 13478, 12277, 13706, 13841, 8079, 0, 9991, 14717, 13082, 11787, 14614, 11698, 10970    
  14. 11574, 13063, 14249, 14561, 12697, 9501, 8610, 12543, 13086, 9212, 9062, 9554, 9991, 0, 14363, 8175, 12309, 9042, 11251, 9250    
  15. 9720, 11546, 14039, 13350, 12617, 11379, 9202, 12974, 9476, 8301, 10704, 9760, 14717, 14363, 0, 12291, 12173, 10971, 9000, 9868    
  16. 13727, 11379, 8186, 10781, 8856, 13431, 9838, 11059, 12513, 8258, 13366, 11617, 13082, 8175, 12291, 0, 14291, 12915, 9583, 9671    
  17. 13852, 8850, 14730, 14886, 11850, 10723, 10755, 8799, 9597, 14817, 13779, 10566, 11787, 12309, 12173, 14291, 0, 13657, 8621, 9089    
  18. 14330, 14111, 8886, 11549, 13302, 8845, 10674, 11781, 11850, 9277, 13710, 9382, 14614, 9042, 10971, 12915, 13657, 0, 9709, 10960    
  19. 10660, 13775, 12862, 13044, 12558, 10427, 13881, 13797, 13866, 12742, 12832, 12105, 11698, 11251, 9000, 9583, 8621, 9709, 0, 13131    
  20. 8138, 8073, 12365, 11194, 11165, 14821, 13024, 9287, 8605, 14550, 12812, 11755, 10970, 9250, 9868, 9671, 9089, 10960, 13131, 0    

 在我機上對20個頇城市進行測試後,效果比較好. 對10城市時,在幾秒鐘來就達到全域性最優解.

注意:模擬退火演算法與初始值無關,演算法求得的解與初始解狀態S(是演算法迭代的起點)無關;模擬退火演算法具有漸近收斂性,已在理論上被證明是一種以概率l 收斂於全域性最優解的全域性優化演算法;模擬退火演算法具有並行性。