模拟退火算法解决旅行商问题_SA

模拟退火算法解决旅行商问题_SA_TSP

关于模拟退火算法，这篇博文写的通俗易懂，戳http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html

自己也是看了这篇才看懂这个SimulatedAnnealing.

然后自己参考着别人的代码也实现了一番，数据仍然是前面遗传算法里的city.txt.

代码如下：

 1 #ifndef SA_TSP_H_
 2 #define SA_TSP_H_ 
 3 #include <iostream>
 4 #include <vector>
 5 #include <string>
 6 #define CITIES 99
 7 #define INITAL_TEMP 1000
 8 #define MIN_TEMP 10
 9 
10 struct city{
11     int id;
12     int x;
13     int y;
14 };
15 
16 struct unit{
17     double length;
18     std::vector<int> path;
19     bool operator<(const struct unit &other) const
20     {
21         return length < other.length;
22     }
23 };
24 
25 class SA_TSP
26 {
27     public:
28         SA_TSP();
29         void initMatrix(const std::string &filename);
30         void initBestUnit();
31         double lenOfUnit(unit &);
32         void genNewUnit(unit &u);
33         void simulateAnnealing();
34         bool isAccept(unit &, unit &);
35         void printBestUnit();
36         ~SA_TSP() {}
37     private:
38         unit bestUnit_;
39         double speed_;
40         int markov_;
41         double currentTemp_;
42 };
43 
44 #endif  /*SA_TSP_H_*/

SA_TSP.h

  1 #include "SA_TSP.h"
  2 #include <iostream>
  3 #include <string>
  4 #include <vector>
  5 #include <time.h>
  6 #include <math.h>
  7 #include <algorithm>
  8 #include <fstream>
  9 using namespace std;
 10 
 11 city cities[CITIES];
 12 double cityMatrix[CITIES][CITIES];
 13 
 14 SA_TSP::SA_TSP()
 15     :markov_(10000), speed_(0.98), currentTemp_(INITAL_TEMP)
 16 {
 17 }
 18 
 19 void SA_TSP::initBestUnit()
 20 {
 21     for(int i = 1; i < CITIES + 1; ++i)
 22     {
 23         bestUnit_.path.push_back(i);
 24     }
 25     random_shuffle(bestUnit_.path.begin(), bestUnit_.path.end());
 26     /* 虽然调用了random_shuffle，
 27      * 但是每次程序开始时第一次shuffle出来的序列都是一样的
 28      */
 29 
 30     /* for(auto &item: bestUnit_.path){
 31             cout << item << " ";
 32     }
 33     cout << endl;
 34 
 35     bestUnit_.length = lenOfUnit(bestUnit_);
 36     cout << bestUnit_.length << endl;
 37     */
 38 }
 39 
 40 
 41 void SA_TSP::initMatrix(const string &filename)
 42 {
 43     int i, j;
 44     ifstream in(filename);
 45     for(i = 0; i < CITIES; ++i)
 46     {
 47         in >> cities[i].id >> cities[i].x >> cities[j].y;
 48     }
 49     for(i = 0; i < CITIES; ++i)
 50     {
 51         cityMatrix[i][i] = 0;
 52         for(j = i + 1; j < CITIES; ++j)
 53         {
 54             cityMatrix[i][j] = sqrt((cities[i].x - cities[j].x) * (cities[i].x - cities[j].x) + (cities[i].y - cities[j].y) * (cities[i].y - cities[j].y));
 55             cityMatrix[j][i] = cityMatrix[i][j];
 56         }
 57     }
 58 }
 59 
 60 
 61 double SA_TSP::lenOfUnit(unit &u)
 62 {
 63     u.length = 0;
 64     for(int j = 0; j < CITIES-1; ++j)
 65     {
 66         u.length += cityMatrix[u.path[j]][u.path[j+1]];
 67     }
 68     u.length += cityMatrix[u.path[CITIES-1]][u.path[0]];
 69 
 70     return u.length;
 71 }
 72 
 73 
 74 bool SA_TSP::isAccept(unit &best_unit, unit &tmp_unit)
 75 {
 76     if(best_unit.length > tmp_unit.length)
 77         return true;
 78     else
 79     {
 80         /*产生0-1之间的随机数用 double(RAND_MAX) */
 81         double temper = exp((best_unit.length - tmp_unit.length) / (double)currentTemp_);
 82         double randtemper = rand()/double(RAND_MAX);
 83         if(temper > randtemper)//必须是'>', 因为temper会越来越小,导致条件越来越不满足，从而趋于稳定
 84             return true;
 85     }
 86     return false;
 87 }
 88 
 89 void SA_TSP::genNewUnit(unit &u)
 90 {
 91 /* srand(time(NULL)); 在调用genNewUnit()的外部使用，
 92  * 否则每次调用都会初始化一次，这样每次都相同了，包括下面的choice也是一样
 93  * 这与前面的shuffle同理
 94  */
 95     int pos1 = rand() % CITIES;
 96     int pos2 = rand() % CITIES;
 97 
 98     auto ptr = u.path.begin();
 99     //ensure pos1 != pos2
100     while(pos1 == pos2)
101         pos2 = rand() % CITIES;
102     if(pos1 > pos2)
103             swap(pos1, pos2);
104 
105     int choice = rand() % 3;
106     if(choice == 0) //swap
107     {
108         //ensure pos1 < pos2
109         swap(u.path[pos1], u.path[pos2]);
110     }else if(choice == 1) //reverse
111     {
112         reverse(ptr + pos1, ptr + pos2);
113     }else{//rightrotate
114         rotate(ptr + pos1, ptr + pos2, ptr + pos2 + 1);
115     }
116 
117     u.length = lenOfUnit(u);
118 }
119 
120 void copy(unit &u1, unit &u2)
121 {
122     u1.path = u2.path;
123     u1.length = u2.length;
124 }
125 
126 void SA_TSP::simulateAnnealing()
127 {
128     unit tmp_unit;
129     copy(tmp_unit, bestUnit_);
130     srand(time(NULL)); 
131     while(currentTemp_ > MIN_TEMP)
132     {
133         for(int i = 0; i < markov_; ++i)
134         {
135             genNewUnit(tmp_unit);
136             if(isAccept(bestUnit_, tmp_unit))
137             {
138                 copy(bestUnit_, tmp_unit);
139             }
140         }
141         currentTemp_ *= speed_;
142     }
143 }
144 
145 void SA_TSP::printBestUnit()
146 {
147     cout << "best path: ";
148     for(vector<int>::iterator it = bestUnit_.path.begin(); it != bestUnit_.path.end(); ++it){
149         cout << *it << " ";    
150     }
151     cout << endl << "best_length: " << bestUnit_.length << endl;;
152 }

SA_TSP.cpp

 1 #include "SA_TSP.h"
 2 #include <iostream>
 3 #include <string>
 4 #include <vector>
 5 using namespace std;
 6 int main(int argc, const char *argv[])
 7 {
 8     SA_TSP saTsp;
 9     saTsp.initMatrix("city.txt");
10     saTsp.initBestUnit();
11     saTsp.simulateAnnealing();
12     saTsp.printBestUnit();
13     return 0;
14 }

testmain.cpp

之前说了这组数据最小的代价是1100+，而我实现的代码怎么搞，最小代价都是2200+。这些应该跟参数的设定和产生新路径的方法有关。

Tips:

虽然我在程序初始化时候用了random_shuffle()来打乱顺序，可是我每次开始执行的时候，path都会被shuffle成同样的序列，只有在程序中再次调用的时候shuffle才会随机改变path。

同理，还有srand(),rand()，第一次调用时候的值都是一样的，只有在程序中多次rand()才会不停的产生随机数。还有时间种子srand()只要调用一次就好，或者你下次给定的种子与之前不同也行。但是不要放在循环体，或者一个会被多次调用的函数里，否则每次调用都被初始化为相同的值了，那么接下来的rand()又会重复上一次的老路了！

这代码肯定还有待优化的地方！