Course AssignmentComputational Intelligence

问题简述

Given a set of n nodes and distances for each pair of nodes, find aroundtrip of minimal total length visiting each node exactly once. The distance from node i to node j is the same as from node j to node i.

Berlin52 – 52 locations in Berlin (Germany)

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <chrono>

using namespace std;

//Super-Parameters
const int ITERATION_TIMES = 200;
const int ANT_NUMBER = 100;
const int CITY_NUMBER = 50;    //DataSet: Berin52
const double ALPHA = 2.0;
const double BETA = 1.0;
const double ROW = 0.4;

const double information_init = 1.14;

typedef vector<vector<double>>  Matrix;   

struct Ant
{
    vector<int> route;           //(目前为止)路径
    double  TotalRouteLength;    //(目前为止)路径的总长度
};

class TSP{
    public:
        TSP(Matrix DistancesMatrix) : DistancesMatrix(DistancesMatrix){
            city_number = DistancesMatrix.size();   //城市数量：通过距离矩阵获取
            InformationMatrix = Matrix(city_number,vector<double>(city_number,information_init));   //初始化信息素矩阵
        }
        void solve();
        //获取最佳情况
        double GetBestRouteLength();
        vector<int> GetBestRoute();

    private:
        //存储最佳情况
        double BestRouteLength = numeric_limits<double>::max();    //初始值需要赋予一个很大的值
        vector<int> BestRoute;
        //一般参数
        int city_number;
        //距离矩阵，信息素矩阵
        Matrix DistancesMatrix;
        Matrix InformationMatrix;

        //三个核心方法
        int Select_NextCity(Ant& this_ant);           //传入Ant结构体的一个对象
        double Calculate_TotalLength(Ant& this_ant);
        void Update_Information(vector<Ant>& ants);
};

/*
    TSP的主要算法流程---------------------------------
*/
void TSP::solve()
{
    for(int iter=0; iter<ITERATION_TIMES; iter++){
        cout << "------第" << iter+1 << "次算法迭代" << "------" << endl;
        vector<Ant> ants(ANT_NUMBER);       //####创建存放Ant结构体变量的数组，开辟的空间数量为ANT_NUMBER
        for(int i = 0; i < ANT_NUMBER; i++){        //第i只蚂蚁
            ants[i].route.push_back(rand() % city_number);   //Step1:初始化蚂蚁所在节点（随机）
            cout << "|||第" << i+1 << "只蚂蚁：初始位置为" << ants[i].route.back() << "|||" << endl;

            for(int j = 0; j < city_number - 1; j++){   //第j步移动
                int nextCity = Select_NextCity(ants[i]);     //Step2:选择下一个前往的节点,结果push到route集合中去。重复直到走遍所有节点。#核心：Select_NextCity()方法
                ants[i].route.push_back(nextCity);
                cout << "!!!第" << j+1 << "步:移动到" << nextCity << endl;
            }
            ants[i].TotalRouteLength = Calculate_TotalLength(ants[i]);  //Step3:计算该蚂蚁(i)当前路径下的总距离，然后看看是不是最佳情况。#核心：Calculate_TotalLength()方法
            cout << "-->路径长：" << ants[i].TotalRouteLength << endl;
            if(ants[i].TotalRouteLength < BestRouteLength)
            {
                BestRouteLength = ants[i].TotalRouteLength;
                BestRoute = ants[i].route;
            }
            cout << "目前为止最佳的路径长：" << BestRouteLength << endl;
        }
        //Step4:所有蚂蚁的情况运行结束，现在开始根据ants所有成员存储的route信息，更新信息素矩阵。#核心：Update_Information()方法
        Update_Information(ants);
        //Step5:本次迭代结束，进入下一个迭代。
    }
}

/*
    Select_NextCity:路径选择
*/
int TSP::Select_NextCity(Ant& this_ant)
{
    //this_ant.route存储了已经经过的结点，类型是vector<int>。在选择下一个目的节点时，需要跳过这些节点。
    //创建概率列表Probabilities：从当前节点i往其他节点走的概率p_k(i,j)
    vector<double> Probabilities(city_number,0.0);   

    int NowCity = this_ant.route.back();    //NowCity：当前所在的节点，即route列表的最后一项
    double totalProbabilities = 0.0;
    //Step1: 计算每个情况的概率(分子)
    for(int NextCity = 0; NextCity < city_number; NextCity++){
        //需要跳过已经访问的节点,前往他们的概率保持为0.0
        auto visited = find(this_ant.route.begin(), this_ant.route.end(), NextCity);  
        if(visited != this_ant.route.end())     
            continue;

        double information_goto_nextcity = InformationMatrix[NowCity][NextCity];
        double distance_goto_nextcity = DistancesMatrix[NowCity][NextCity];
        Probabilities[NextCity] = pow(information_goto_nextcity, ALPHA) * pow(1.0/distance_goto_nextcity, BETA);
        totalProbabilities += Probabilities[NextCity];
        //cout << "#Probabilities:[Before]" << Probabilities[NextCity] << endl;
    }
    //cout << "#totalProbabilities:" << totalProbabilities << endl;

    //Step2:计算每个情况的条件概率p_k(i,j)
    for(int NextCity = 0; NextCity < city_number; NextCity++){
        auto visited = find(this_ant.route.begin(), this_ant.route.end(), NextCity);  
        if(visited != this_ant.route.end())     
            continue;
        Probabilities[NextCity] = Probabilities[NextCity] / totalProbabilities;
        //cout << "#Probabilities:[After]" << Probabilities[NextCity] << endl;
    }

    //Step3:轮盘赌选择去往的下一个节点
    double  randVal = (double)rand() / RAND_MAX * totalProbabilities;
    //cout << "#randVal:" << randVal << endl;
    for(int NextCity = 0; NextCity < city_number; NextCity++){
        auto visited = find(this_ant.route.begin(), this_ant.route.end(), NextCity);  
        if(visited != this_ant.route.end())     
            continue;

        randVal -= Probabilities[NextCity] * totalProbabilities;
        if (randVal <= 0){
            return NextCity;
        }
    }

    return -1;    //ERROR
}

/*
    Calculate_TotalLength:计算路径总长
*/
double TSP::Calculate_TotalLength(Ant& this_ant)
{
    double totalLength = 0.0;
    for(int i = 0; i < this_ant.route.size()-1; i++){
        totalLength += DistancesMatrix[this_ant.route[i]][this_ant.route[i+1]];
    }
    totalLength += DistancesMatrix[this_ant.route.back()][this_ant.route[0]];  //终点回到起点
    return totalLength;
}

/*
    Update_Information:更新信息素矩阵
*/
void TSP::Update_Information(vector<Ant>& ants)
{
    //Step1: 信息素蒸发
    for(int i = 0; i < InformationMatrix[0].size(); i++){
        for(int j = 0; j < InformationMatrix[0].size(); j++){
            InformationMatrix[i][j] = InformationMatrix[i][j] * (1 - ROW);
        }
    }

    //Step2: 信息素释放：每只蚂蚁经过的路径上，都会留下一定的信息素。留下信息素的量规定为距离的倒数
    for(int i = 0; i < ants.size(); i++){
        for(int j = 0; j < ants[i].route.size() - 1; j++){
            int StartPoint = ants[i].route[j];
            int Destination = ants[i].route[j+1];
            InformationMatrix[StartPoint][Destination] += 1.0 / ants[i].TotalRouteLength;
        }
        InformationMatrix[ants[i].route.back()][ants[i].route[0]] += 1.0 / ants[i].TotalRouteLength;   //终点回到起点
    }
}

vector<int> TSP::GetBestRoute()
{
    return BestRoute;
}
double TSP::GetBestRouteLength()
{
    return BestRouteLength;
}


int main(){

    srand(static_cast<unsigned>(time(0)));

    //测试集要求：主对角线全0，其他元素不能出现0（否则两点就重合了，必定报错）
    /* Test: 5-CITY
    Matrix distances = {
        {0, 2, 9, 10, 7},
        {1, 0, 6, 4, 3},
        {15, 7, 0, 8, 6},
        {6, 3, 12, 0, 5},
        {10, 4, 8, 7, 0}
    };
    */

    Matrix distances = {
        {0, 2, 9, 10, 7, 4, 8, 12, 5, 6, 3, 15, 14, 11, 13, 9, 8, 7, 5, 6, 4, 3, 2, 1, 8, 9, 7, 5, 6, 12, 10, 14, 16, 8, 11, 9, 15, 10, 14, 6, 7, 5, 3, 8, 9, 10, 12, 11, 13, 9},
        {2, 0, 6, 4, 3, 7, 5, 8, 9, 10, 11, 12, 13, 14, 15, 7, 8, 5, 6, 4, 3, 10, 12, 11, 9, 8, 6, 5, 7, 11, 12, 13, 14, 9, 8, 10, 11, 7, 5, 6, 4, 3, 9, 10, 8, 7, 6, 5, 4, 2},
        {9, 6, 0, 8, 5, 12, 14, 11, 10, 9, 15, 6, 8, 7, 9, 8, 10, 12, 14, 15, 6, 7, 9, 11, 12, 13, 14, 16, 15, 12, 10, 9, 7, 8, 6, 5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16},
        {10, 4, 8, 0, 7, 9, 10, 12, 14, 11, 8, 7, 6, 5, 4, 8, 9, 10, 12, 11, 14, 13, 12, 15, 14, 11, 10, 8, 9, 10, 11, 12, 13, 14, 15, 16, 11, 10, 9, 12, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7},
        {7, 3, 5, 7, 0, 8, 9, 10, 12, 14, 11, 10, 9, 8, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 11, 10, 9, 8, 7, 6, 5, 4, 3},
        {4, 7, 12, 9, 8, 0, 6, 10, 11, 13, 14, 15, 16, 12, 10, 9, 8, 7, 5, 4, 6, 5, 7, 9, 8, 10, 11, 12, 14, 15, 11, 10, 12, 13, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
        {8, 5, 14, 10, 9, 6, 0, 12, 11, 13, 14, 15, 16, 12, 11, 10, 9, 8, 7, 6, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4},
        {12, 8, 11, 12, 10, 10, 12, 0, 14, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 10, 9, 8, 6, 7, 8, 10, 11, 12, 14, 15, 16, 14, 12, 11, 10, 9, 8, 7, 6, 5},
        {5, 9, 10, 14, 12, 11, 11, 14, 0, 6, 5, 8, 9, 10, 11, 12, 14, 15, 16, 14, 12, 10, 8, 7, 6, 5, 4, 3, 2, 1, 10, 12, 13, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 8, 9, 10, 11, 12, 9},
        {6, 10, 9, 11, 14, 13, 12, 11, 6, 0, 5, 7, 8, 9, 10, 11, 12, 14, 15, 16, 14, 12, 10, 8, 7, 6, 5, 4, 3, 2, 1, 9, 10, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6},
        {3, 11, 15, 8, 11, 14, 14, 9, 5, 5, 0, 7, 8, 9, 10, 11, 12, 14, 15, 16, 14, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11, 12, 9, 8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4},
        {15, 12, 6, 7, 10, 15, 15, 8, 9, 7, 7, 0, 3, 4, 5, 6, 8, 10, 12, 14, 15, 11, 12, 10, 8, 7, 6, 5, 4, 3, 2, 1, 8, 9, 10, 11, 12, 13, 14, 15, 16, 14, 12, 11, 10, 9, 8, 7, 6, 5},
        {14, 13, 8, 5, 9, 16, 12, 11, 8, 11, 9, 3, 0, 6, 7, 8, 9, 10, 12, 11, 14, 15, 14, 12, 10, 8, 6, 4, 3, 2, 1, 9, 10, 11, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11, 12, 11, 10},
        {11, 14, 7, 8, 6, 12, 11, 9, 10, 9, 8, 4, 6, 0, 2, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 14, 12, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
        {13, 15, 9, 4, 6, 15, 14, 6, 8, 8, 7, 5, 7, 2, 0, 5, 6, 7, 8, 9, 10, 11, 12, 10, 9, 8, 6, 4, 3, 2, 1, 11, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 5},
        {9, 7, 8, 8, 5, 11, 14, 9, 12, 11, 5, 6, 9, 5, 5, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 8, 9, 10, 11, 12, 13, 14, 15, 16},
        {8, 8, 10, 9, 4, 8, 12, 8, 9, 10, 8, 7, 10, 7, 6, 3, 0, 2, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 5, 4, 3, 2},
        {7, 5, 12, 10, 1, 9, 10, 7, 10, 9, 8, 6, 8, 5, 6, 4, 2, 0, 4, 6, 8, 10, 11, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11, 12, 13, 14, 15, 16, 14, 12, 10, 9},
        {5, 6, 14, 15, 4, 10, 9, 6, 8, 10, 6, 5, 11, 9, 8, 5, 4, 4, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 8, 9, 10, 11, 12, 13},
        {6, 4, 15, 12, 6, 11, 12, 10, 11, 9, 5, 8, 12, 8, 9, 6, 6, 6, 2, 0, 2, 4, 6, 7, 8, 9, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11, 12, 13, 14, 15, 16},
        {4, 3, 6, 4, 10, 5, 10, 8, 7, 10, 7, 5, 8, 9, 10, 9, 8, 6, 3, 2, 0, 3, 4, 6, 7, 8, 9, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 9, 10, 11, 12, 13, 14},
        {3, 10, 7, 10, 9, 5, 9, 6, 8, 7, 3, 6, 10, 5, 5, 4, 3, 4, 4, 3, 3, 0, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11, 12, 13, 14},
        {2, 12, 9, 12, 8, 7, 8, 9, 10, 6, 7, 9, 12, 11, 10, 5, 6, 6, 4, 3, 2, 4, 0, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11, 12, 13, 14},
        {1, 11, 11, 15, 7, 6, 7, 10, 7, 11, 6, 5, 10, 8, 9, 6, 5, 10, 3, 2, 1, 5, 5, 0, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11},
        {8, 9, 12, 14, 6, 10, 11, 12, 6, 7, 8, 7, 9, 12, 10, 9, 8, 8, 6, 4, 3, 6, 7, 3, 0, 8, 9, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11, 12, 13, 14, 15},
        {9, 8, 12, 11, 5, 10, 10, 11, 8, 9, 9, 10, 11, 9, 8, 6, 5, 10, 2, 1, 10, 7, 8, 4, 8, 0, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10},
        {7, 6, 14, 15, 8, 9, 12, 11, 7, 10, 11, 9, 10, 8, 9, 8, 6, 9, 1, 1, 11, 10, 7, 7, 9, 3, 0, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2},
        {6, 5, 11, 12, 7, 6, 9, 8, 10, 8, 10, 10, 10, 7, 6, 6, 5, 10, 4, 3, 1, 5, 4, 5, 10, 2, 3, 0, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
        {5, 6, 12, 10, 4, 5, 9, 10, 11, 10, 10, 9, 10, 8, 8, 8, 7, 8, 3, 4, 2, 7, 7, 8, 10, 3, 4, 4, 0, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4},
        {4, 3, 10, 12, 7, 9, 11, 12, 9, 6, 7, 8, 8, 10, 9, 5, 4, 5, 2, 1, 10, 8, 6, 7, 8, 2, 3, 5, 2, 0, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4},
        {3, 2, 9, 14, 8, 11, 12, 10, 10, 9, 6, 8, 9, 7, 8, 5, 3, 6, 1, 1, 9, 7, 8, 5, 4, 2, 3, 6, 3, 3, 0, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4},
        {2, 1, 10, 16, 7, 8, 14, 12, 8, 10, 9, 6, 10, 8, 7, 4, 2, 5, 2, 1, 9, 6, 7, 6, 5, 3, 4, 5, 4, 5, 4, 0, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6},
        {1, 10, 11, 15, 8, 8, 11, 13, 9, 7, 5, 4, 5, 7, 5, 3, 2, 4, 1, 1, 10, 5, 8, 7, 9, 4, 5, 6, 5, 4, 3, 4, 0, 2, 4, 6, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5},
        {2, 1, 10, 15, 6, 8, 10, 8, 10, 10, 8, 5, 8, 5, 9, 4, 3, 3, 2, 2, 8, 5, 4, 5, 4, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 14, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
    };

    TSP tsp(distances);

    auto start = chrono::high_resolution_clock::now();
    tsp.solve();
    cout << "Running the algorithm...\n" << flush;
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;   //程序运行时间

    vector<int> BestRoute = tsp.GetBestRoute();
    double  BestRouteLength = tsp.GetBestRouteLength();
    
    
    //Test Ouput
    cout << "Algorithm completed!" << endl;
    cout << "\n\n==============最终结果==============\n";
    cout << "最佳路径：";
    for(int i = 0 ; i < BestRoute.size() - 1; i++)
    {
        cout << BestRoute[i] << " -> ";
    }
    cout << BestRoute.back();
    cout << "\n最佳(最短)路径长：";
    cout << BestRouteLength << endl;
    cout << "============================||END." << endl;
    cout << "(本次运行超参数：" << "--ITERATION_TIMES=" << ITERATION_TIMES 
                               << "--ANT_NUMBER" << ANT_NUMBER
                               << "--ALPHA=" << ALPHA
                               << "--BETA=" << BETA
                               << "--ROW=" << ROW
                               << ")" << endl;
    cout << "(程序运行时长：" << duration << " seconds)" << endl;

    return 0;
}

代码逻辑和解析—->2024.10.25更新完毕

算法载体“蚂蚁”的结构体表征

1
2
3
4
5
struct Ant
{
    vector<int> route;           //(目前为止)路径
    double  TotalRouteLength;    //(目前为止)路径的总长度
};
  • route: 路径，是一个存放int的一维vector。比如{3,2,1,4,5}，表示该蚂蚁的行走路径是3->2->1->4->5，蚂蚁当前正位于节点5。算法的运行过程中，在每只蚂蚁、每一次根据概率选择完毕下一个节点后，route需要在末尾实时存入(push_back)这个目的节点。
  • TotalRouteLength：每一次迭代完成后(即一只蚂蚁走遍了所有节点)，存放route路径的总长度。

距离矩阵和信息素矩阵

1
2
3
4
typedef vector<vector<double>>  Matrix;
//距离矩阵，信息素矩阵
Matrix DistancesMatrix;
Matrix InformationMatrix;
  • 矩阵的第i行第j列元素，表示从i节点到j节点“路径的距离”/“路径上信息素的含量”。
  • DistancesMatrix是算法的输入，他反映了当前TSP问题的城市个数和它们之间的位置关系(彼此间的距离)；
  • i->j与j->i路径相同只是方向相反，同一条路径上的距离和信息素都应该相同。因此，DistancesMatrix和InformationMatrix都是主对角线全0的对称矩阵。

算法主逻辑solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void TSP::solve()
{
    for(int iter=0; iter<ITERATION_TIMES; iter++){
        vector<Ant> ants(ANT_NUMBER);       //####创建存放Ant结构体变量的数组，开辟的空间数量为ANT_NUMBER
        for(int i = 0; i < ANT_NUMBER; i++){        //第i只蚂蚁
            ants[i].route.push_back(rand() % city_number);   //Step1:初始化蚂蚁所在节点（随机）
            for(int j = 0; j < city_number - 1; j++){   //第j步移动
                int nextCity = Select_NextCity(ants[i]);     //Step2:选择下一个前往的节点,结果push到route集合中去。重复直到走遍所有节点。#核心：Select_NextCity()方法
                ants[i].route.push_back(nextCity);
            }
            ants[i].TotalRouteLength = Calculate_TotalLength(ants[i]);  //Step3:计算该蚂蚁(i)当前路径下的总距离，然后看看是不是最佳情况。#核心：Calculate_TotalLength()方法
            if(ants[i].TotalRouteLength < BestRouteLength)
            {
                BestRouteLength = ants[i].TotalRouteLength;
                BestRoute = ants[i].route;
            }
        }
        //Step4:所有蚂蚁的情况运行结束，现在开始根据ants所有成员存储的route信息，更新信息素矩阵。#核心：Update_Information()方法
        Update_Information(ants);
        //Step5:本次迭代结束，进入下一个迭代。
    }
}
  • 三重循环：最外层循环控制算法总迭代次数；i循环遍历每只蚂蚁；j循环控制每只蚂蚁进行寻路。
  • 核心方法调用：
    • Select_NextCity：传入当前蚂蚁(结构体)。因为结构体中包含了蚂蚁现在的位置信息now(route的末尾元素)，因此可以遍历计算概率p(now,next)，并通过轮盘赌选择下一步的节点编号next。
    • Calculate_TotalLength：最内j循环运行完毕，即当前蚂蚁已经走遍所有节点，运算总路径长。随后确认是否是最佳情况。
    • Update_Information：所有蚂蚁寻路完毕，本次迭代完成，根据每只蚂蚁的路径route更新信息素矩阵。
  • 另外：ants为所有蚂蚁的集合，数据类型是存放结构体对象的一维vector。

*算法主逻辑手写版：

核心方法·其一：Select_NextCity路径选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int TSP::Select_NextCity(Ant& this_ant)
{
    //this_ant.route存储了已经经过的结点，类型是vector<int>。在选择下一个目的节点时，需要跳过这些节点。
    //创建概率列表Probabilities：从当前节点i往其他节点走的概率p_k(i,j)
    vector<double> Probabilities(city_number,0.0);   

    int NowCity = this_ant.route.back();    //NowCity：当前所在的节点，即route列表的最后一项
    double totalProbabilities = 0.0;
    //Step1: 计算每个情况的概率(分子)
    for(int NextCity = 0; NextCity < city_number; NextCity++){
        //需要跳过已经访问的节点,前往他们的概率保持为0.0
        auto visited = find(this_ant.route.begin(), this_ant.route.end(), NextCity);  
        if(visited != this_ant.route.end())     
            continue;

        double information_goto_nextcity = InformationMatrix[NowCity][NextCity];
        double distance_goto_nextcity = DistancesMatrix[NowCity][NextCity];
        Probabilities[NextCity] = pow(information_goto_nextcity, ALPHA) * pow(1.0/distance_goto_nextcity, BETA);
        totalProbabilities += Probabilities[NextCity];
    }

    //Step2:计算每个情况的条件概率p_k(i,j)
    for(int NextCity = 0; NextCity < city_number; NextCity++){
        auto visited = find(this_ant.route.begin(), this_ant.route.end(), NextCity);  
        if(visited != this_ant.route.end())     
            continue;
        Probabilities[NextCity] = Probabilities[NextCity] / totalProbabilities;
    }

    //Step3:轮盘赌选择去往的下一个节点
    double  randVal = (double)rand() / RAND_MAX * totalProbabilities;
    for(int NextCity = 0; NextCity < city_number; NextCity++){
        auto visited = find(this_ant.route.begin(), this_ant.route.end(), NextCity);  
        if(visited != this_ant.route.end())     
            continue;

        randVal -= Probabilities[NextCity] * totalProbabilities;
        if (randVal <= 0){
            return NextCity;
        }
    }

    return -1;    //ERROR
}
  • 计算每条路径的**概率p_k(i,j)**。注意需要事先排除已经走过的节点。
  • 轮盘赌选择去往的下一个节点。

核心方法·其二：Calculate_TotalLength计算总长

1
2
3
4
5
6
7
8
9
double TSP::Calculate_TotalLength(Ant& this_ant)
{
    double totalLength = 0.0;
    for(int i = 0; i < this_ant.route.size()-1; i++){
        totalLength += DistancesMatrix[this_ant.route[i]][this_ant.route[i+1]];
    }
    totalLength += DistancesMatrix[this_ant.route.back()][this_ant.route[0]];  //终点回到起点
    return totalLength;
}

为了简化代码，solve()在运行时不会让蚂蚁回到起点。但此处我们认为TSP问题仍需要走一个闭环，所以在运算路径总长时需要另外加上从终点(route最后一项)回到起点(route第一项)的距离。

核心方法·其三：Update_Information信息素更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void TSP::Update_Information(vector<Ant>& ants)
{
    //Step1: 信息素蒸发
    for(int i = 0; i < InformationMatrix[0].size(); i++){
        for(int j = 0; j < InformationMatrix[0].size(); j++){
            InformationMatrix[i][j] = InformationMatrix[i][j] * (1 - ROW);
        }
    }

    //Step2: 信息素释放：每只蚂蚁经过的路径上，都会留下一定的信息素。留下信息素的量规定为距离的倒数
    for(int i = 0; i < ants.size(); i++){
        for(int j = 0; j < ants[i].route.size() - 1; j++){
            int StartPoint = ants[i].route[j];
            int Destination = ants[i].route[j+1];
            InformationMatrix[StartPoint][Destination] += 1.0 / ants[i].TotalRouteLength;
        }
        InformationMatrix[ants[i].route.back()][ants[i].route[0]] += 1.0 / ants[i].TotalRouteLength;   //终点回到起点
    }
}
  • 信息素蒸发：根据超参数ROW，对上一次迭代后的信息素进行衰减操作。
  • 信息素释放：根据本轮迭代下每只蚂蚁的路径情况，为每条路径增加信息素。每次增加的信息素量是route总长的倒数(即1/TotalRouteLength)。

读取.tsp数据文件—->稍后更新

Berlin52数据集测试情况—->稍后更新

backtop