1 #ifndef GENTIC_TSP_H_ 2 #define GENTIC_TSP_H_ 3 #include <iostream> 4 #include <vector> 5 #include <string> 6 #define CITIES 99 7 #define UNITS 50 8 #define MAX_GEN 15 9 10 11 struct city{12     int id;13     int x;14     int y;15 };16 17 struct unit{18     double length;19     std::vector<int> path;20     bool operator<(const struct unit &other) const21     {22         return length < other.length;23     }24 };25 26 27 class GenticTSP{28     public:29         GenticTSP();30         void initMatrix(const std::string &filename);//file to matrix31         void initGroup();//shuffle a group32         double lenOfUnit(unit &p);//33         int searchCity(unit &, int id);//search a city‘s id for cross34         void selectGroup();35         void crossUnits(unit &p, unit &q, unit &r);36         void mutateGroup();37         void evoluteGroup();38         void printBestUnit();39         ~GenticTSP();40     private:41         unit bestUnit_;42         double pm_;// mutate probability43         double ps_;//save probability44 45 };46 47 #endif  /*GENTIC_TSP_H_*/

  1 #include "GenticTSP.h"  2 #include <iostream>  3 #include <fstream>  4 #include <string>  5 #include <vector>  6 #include <list>  7 #include <algorithm>  8 #include <math.h>  9 #include <time.h> 10 #include <string.h> 11  12 using namespace std; 13  14 city cities[CITIES]; 15 unit group[UNITS]; 16 double cityMatrix[CITIES][CITIES]; 17  18 GenticTSP::GenticTSP() 19     :pm_(0.2), ps_(0.8) 20 { 21  22 } 23  24 GenticTSP::~GenticTSP() 25 { 26  27 } 28  29 void GenticTSP::initMatrix(const string &filename) 30 { 31     int i, j; 32     ifstream in(filename); 33     for(i = 0; i < CITIES; ++i) 34     { 35  36         in >> cities[i].id >> cities[i].x >> cities[i].y; 37     } 38  39     for(i = 0; i < CITIES; ++i) 40     { 41         cityMatrix[i][i] = 0; 42         for(j = i + 1; j < CITIES; ++j) 43         { 44             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)); 45             cityMatrix[j][i] = cityMatrix[i][j]; 46         } 47  48     } 49 } 50  51  52 //calculate the path-lenght of each path 53 double GenticTSP::lenOfUnit(unit &unit) 54 { 55     unit.length = 0; 56     for(int j = 0; j < CITIES - 1; ++j) 57     { 58         unit.length += cityMatrix[unit.path[j]][unit.path[j + 1]]; 59     } 60  61     //回到起始城市 62     unit.length += cityMatrix[unit.path[0] ][unit.path[CITIES - 1] ]; 63  64     return unit.length; 65 } 66  67  68 //init group of various paths 69 void GenticTSP::initGroup() 70 { 71     vector<int> tmp; 72     for(int i = 0; i < CITIES; ++i) 73         tmp.push_back(i); 74  75     for(int i = 0; i < UNITS; ++i) 76     { 77         random_shuffle(tmp.begin(),tmp.end()); 78         group[i].path = tmp; 79         group[i].length = lenOfUnit(group[i]); 80     } 81 } 82  83 //for test 84 void printlist(list<int> &path) 85 { 86     for(list<int>::iterator it = path.begin(); it != path.end(); ++it){ 87         cout << *it << " ";     88     } 89     cout << endl; 90 } 91  92 void rightRotateList(list<int> &path, list<int>::iterator ptr, list<int>::iterator res) 93 { 94     path.insert(ptr, res, path.end()); 95     path.erase(res, path.end()); 96 } 97  98  99 void GenticTSP::selectGroup()100 {101     int selected = UNITS * ps_;102     int non_selected = UNITS - selected; //防止取整丢失，所以直接采用减去selected103     for(int i = 0; i < UNITS; ++i)104     {105         group[i].length = lenOfUnit(group[i]);106     }107     sort(group, group + UNITS);108 109     /*群体规模保持不变110      *被淘汰的个体数目为non_selected111      *用被选择的前non_seleted个个体替代之112      */113     for(int i = 0; i < non_selected; ++i)114     {115         group[UNITS-1-i].path =  group[i].path;116         group[UNITS-1-i].length =  group[i].length;117 118        /* WARNING:119         * error:memcpy(&group[UNITS-1-i], &group[i], sizeof(unit)); 120         * 不能用memcpy121         * 因为unit是自定义的结构体122         * 其中的vector类型也不是原生的数据类型123         * 如若使用，需要自定义构造函数124         */125     }126 }127 128 129 void GenticTSP::evoluteGroup()130 {131     for(int i = 0; i < MAX_GEN; ++i)132     {133         selectGroup();134 135         for(int j = 0; j < UNITS-2;)136         {137             crossUnits(group[j], group[j+1], group[j+2]);138             j += 2;139         }140 141         mutateGroup();142     }143 144 }145 146 147 void GenticTSP::mutateGroup()148 {149     srand(time(NULL));150     int num;151     int pos1, pos2;152     int tmp;153     int sum = UNITS * pm_; //变异的总数= 群体数 * 变异概率154     while(sum--)155     {156         //随机选取一个发生变异的unit157         num = rand() % UNITS;158         //随机选取两个path上变异的城市，采用交换两个城市的方法进行变异159         pos1 = rand() % CITIES;160         pos2 = rand() % CITIES;161 162         //如果相同则不能算是变异，这里用while确保变异163         while(pos1 == pos2)164             pos2 = rand() % CITIES;165 166         tmp = group[num].path[pos1];167         group[num].path[pos1] = group[num].path[pos2];168         group[num].path[pos2] = tmp;169 170         //更新该变异后path的长度171         lenOfUnit(group[num]);      172     }173 }174 175 176 177 178 void GenticTSP::crossUnits(unit &u1, unit &u2, unit &u3)179 {180     //将路径存储在list类型的容器中便于后面的插入操作181     list<int> path1(u1.path.begin(), u1.path.end());182     list<int> path2(u2.path.begin(), u2.path.end());183     list<int> path3(u3.path.begin(), u3.path.end());184     //随机产生起始城市的id， 并将位置默认为第一个位置185     srand((int)time(0));186     int cityID = rand() % CITIES;187     list<int>::iterator res1, res2, res3;188     res1 = find(path1.begin(), path1.end(), cityID);189     res2 = find(path2.begin(), path2.end(), cityID);190     res3 = find(path3.begin(), path3.end(), cityID);191     if(res1 == path1.end() || res2 == path2.end() || res3 == path3.end())192     {193         cout << "city not found" << endl;194     }195     196     //将以随机选取的城市及其后面的城市右旋到序列首部197     rightRotateList(path1, path1.begin(), res1);198     rightRotateList(path2, path2.begin(), res2);199     rightRotateList(path3, path3.begin(), res3);200 201     list<int>::iterator ptr1, ptr2, ptr3;202     ptr1 = path1.begin();203     ptr2 = path2.begin();204     ptr3 = path3.begin();205 206     /*CITIES个城市207      *第一个城市在循环体外已经确定208      *循环体内只要再执行CITIES - 2 次即可209      *因为当执行倒数第二次后，最后一个也就是仅剩的一个也无需再循环了210      */211     for(int k = 1; k < CITIES-1; ++k)212     {213       //  cout << "______" << k<< "______" << endl;214         int h1 = *ptr1;215         double len1 = cityMatrix[h1][*(++ptr1)];216         int h2 = *ptr2;217         double len2 = cityMatrix[h2][*(++ptr2)];218         int h3 = *ptr3;219         double len3 = cityMatrix[h3][*(++ptr3)];220 221         //找出前两个城市距离最小的那个path中得第一个城市的编号222         double len = (len1 <= len2) ? len1 : len2;223         len = (len < len3) ? len : len3;224         if(len == len1){225             cityID = *ptr1;226         }else if(len == len2){227             cityID = *ptr2;228         }else{229             cityID = *ptr3;230         }231 232         //与当前城市距离最小的下一个城市编号为cityID233         res1 = find(ptr1, path1.end(), cityID);234         res2 = find(ptr2, path2.end(), cityID);235         res3 = find(ptr3, path3.end(), cityID);236         if(res1 == path1.end() || res2 == path2.end() || res3 == path3.end())237         {238             cout << "city not found in loop" << endl;239         }240         rightRotateList(path1, ptr1, res1);241         rightRotateList(path2, ptr2, res2);242         rightRotateList(path3, ptr3, res3);243 244         //指针失效，需要重新定位245         ptr1 = find(path1.begin(), path1.end(), cityID);246         ptr2 = find(path2.begin(), path2.end(), cityID);247         ptr3 = find(path3.begin(), path3.end(), cityID);248     }249 250 251     /*为了避免三个路径相同，所以这里在不改变路径的情况下替换起点城市，有利于接下来的交叉*/252     cityID = (rand() % CITIES);253     res2 = find(path2.begin(), path2.end(), cityID);254     rightRotateList(path2, path2.begin(), res2);255 256     cityID = (rand() % CITIES);257     res3 = find(path3.begin(), path3.end(), cityID);258     rightRotateList(path3, path3.begin(), res3);259 260     //交叉完之后再赋值给vector类型261     u1.path.assign(path1.begin(), path1.end());262     u2.path.assign(path2.begin(), path2.end());263     u3.path.assign(path3.begin(), path3.end());264 }265     266     267 //print top5 paths with length268 void GenticTSP::printBestUnit()269 {270     for(int i = 0; i < 5; ++i)271     {272         cout << "Path" << i << ": ";273         for(vector<int>::iterator it = group[i].path.begin(); it != group[i].path.end(); ++it){274             cout << *it << " ";    275         }276         cout << endl << "length: " << group[i].length << endl; 277     }278 }

 1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <fstream> 5 #include "GenticTSP.h" 6 using namespace std; 7  8  9 int main(int argc, const char *argv[])10 {11     GenticTSP genticTsp;12     genticTsp.initMatrix("city.txt");13     genticTsp.initGroup();14     genticTsp.evoluteGroup();15     genticTsp.selectGroup(); //进化后需要再一次选择，从而排序出最优序列16     genticTsp.printBestUnit ();17 18     return 0;19 }

1  6  4   2 15 15   3 24 18   4 33 12   5 48 12   6 57 14   7 67 10   8 77 10   9 86 15  10  6 21  11 17 26  12 23 25  13 32 35  14 43 23  15 55 35  16 65 36  17 78 39  18 87 35  19  3 53  20 12 44  21 28 53  22 33 49  23 47 46  24 55 52  25 64 50  26 71 57  27 87 57  28  4 72  29 15 78  30 22 70  31 34 71  32 42 79  33 54 77  34 66 79  35 78 67  36 87 73  37  7 81  38 17 95  39 26 98  40 32 97  41 43 88  42 57 89  43 64 85  44 78 83  45 83 98  46  5 109  47 13 111  48 25 102  49 38 119  50 46 107  51 58 110  52 67 110  53 74 113  54 88 110  55  2 124  56 17 134  57 23 129  58 36 131  59 42 137  60 53 123  61 63 135  62 72 134  63 87 129  64  2 146  65 16 147  66 25 153  67 38 155  68 42 158  69 57 154  70 66 151  71 73 151  72 86 149  73  5 177  74 13 162  75 25 169  76 35 177  77 46 172  78 54 166  79 65 174  80 73 161  81 86 162  82  2 195  83 14 196  84 28 189  85 38 187  86 46 195  87 57 194  88 63 188  89 77 193  90 85 194  91  8 211  92 12 217  93 22 210  94 34 216  95 47 203  96 58 213  97 66 206  98 78 210  99 85 204