蚁群算法及其在列车解体顺序编排的应用

##基本原理的了解##
首先我们来说一下蚁群算法。在看本文之前,大家需要先看一下百度百科关于蚁群算法的初步讲解。真正的蚁群算法和自然界的蚂蚁寻找食物是有很大差异的。但是了解大自然蚂蚁的寻找规律是很有必要的。

##蚁群算法和大自然蚂蚁寻找食物的区别##
大自然中,蚂蚁在寻找食物的时候,会留下自己的信息素。同时每个蚂蚁个体更倾向于朝着信息素更加浓的方向走(这是一个概率问题,越浓的方向被选择的概率越大)。同时由于两点之间,一定的时间内越短的道路通过的蚂蚁越多,所以越短的道路留下的信息素也越多。直到最后这个信息素浓度特别的浓,大家走有极大地概率往这个方向走。

上边这张图来自于百度百科。我想说明的一点是,蚂蚁并不知道自己走过的路程是短还是长(我了解这一点也是通过我的女票囧)。他们只需要按照信息素的浓度找吃的就可以了。因为如上图,最开始的时候,两边一样多的信息素浓度。但是A侧更短,所以A侧的会先到达目的地。因此一定时间内能够通过的蚂蚁更多。所以信息素浓度就大。
但是我们设计的蚁群算法不是这样的。我们是根据不同蚂蚁走过的道路的距离来决定信息素的多少的。这只蚂蚁走过的总路程最短,那么它释放的信息素就更多。我们只能通过距离的长短来设计信息素的多少,而不是通过蚂蚁先后到达来体现信息素。

##蚁群算法的基本流程##
总体来说每一轮蚁群算法的迭代有这么几步:

###放置蚂蚁###
以TSP(货郎担问题)为例,我们会在多个城市中随机放置蚂蚁。来作为整个程序的开始。

###选择概率的更新###
对于每一只蚂蚁的当前位置,我们需要根据信息素浓度来判定下一个城市的选择概率,然后根据概率进行下一个城市的选择。这里大有文章可做,我们可以结合信息素浓度,以及自己设计的各种启发函数,来确定下一个城市的选择概率。

###下一个城市的选择###
对于每一只蚂蚁,我们可以根据上一步的概率来选择下一个城市。同时进行操作,诸如已选城市标记,选择好的数据处理等等。

###信息素的更新###
这一步是在所有的蚂蚁完成该轮循环之后做的事情。我们对于每只旅行完毕的蚂蚁的每一段旅程进行信息素更新。更新的依据就是它走过的路程长短。这里把路程长短转化为信息素浓度也是需要设计。常用的有基于平均数的设计(短于平均长度的路程信息素加一些,长于平均长度的蚂蚁对应的路程信息素减一些)。对于经过的每一段旅程进行更新完毕之后,城市两两之间的选择信息素浓度就有了。

##货郎担问题的基本实现##
首先由几点要说一下:

###关于$\rho$这个元素###
我们知道,如果信息素不耗散,会有什么后果呢。理论一点的说就是算法收敛速度过快,陷入局部最优解中。为什么会出现这种现象呢。是因为为了让更多的蚂蚁去有更大的概率选择一些新的道路,或者说让最近的一次迭代起到的作用更大,我们需要削弱以前几次迭代的结果。这个在大自然中表现为蚂蚁留下的信息素会不断的被风吹走,我们在算法中呢,也就是代码中的rou,就是用来形容以前的信息素信息被吹走的。看看代码就可以了。

###关于代码中详细的表示###
本人不敢妄加修改代码,只好大体说一下各个函数以及变量的意义。
首先ant类是用来表示每只蚂蚁的行动的。函数名称对照我上边所说的几个过程就可以看懂了。
project类是用来描述整个的算法进程的。也是很容易明白。会点c++语言的基本都能看懂。
具体的Q啦,alpha啦,这些都是具体算法设计的内容。我没有作TSP的相关研究。这些都是可以自己设计的。我就暂且不说了。

###代码###
代码在最后边放着。我先说列车解体问题的具体应用了。

##列车解题顺序编排的应用##
这个问题大体来说是这样的。我们知道我们做的火车是由很多车节组成的。每个出发列车的车节都是由到达列车拆分然后组装出来的。所以我们要解决的问题就是,如果每个时间只能有一辆列车被拆分,在每个出发列车时间确定的情况下,怎样的拆分顺序是能够弄出更多的出发列车呢。

具体来说,每个到达列车有a,b,c,d四个方向不同的车节,每个出发列车也有四个方向车节的要求。同时每个到达列车有自己的解体时间,出发列车组装也需要时间。具体如下表:

因为如果我们需要对每个到达列车进行顺序编排的话,就有n!种排序方式。这个很明显是NP完全问题了。用蚁群算法优化一下或许是一个不错的选择。

首先我们是需要把所有列车都解体的。只不过是顺序问题。所以我们就映射到了TSP问题当中,TSP需要走遍所有的城市,只不过是顺序问题罢了。
接下来我们可以用出发列车作为时间限制进行优化,比方说第一个出发列车,在这个列车出发前,我们有几辆列车已经到位了,所以这个时候在第一辆发车之前,我们只能选择已经到达的这几辆列车解体。凑够第一辆出发列车之后,我们在考虑第二辆列车。这样的话我们就缩小了搜索范围,提升了效率。
我们需要给每个蚂蚁设计一个时间戳,描述当前这只蚂蚁走到了什么时间。如果超过了当前列车出发时间还没有凑齐,那么这只蚂蚁就废了。success这个元素就标记成0.
每次添加城市(也就是具体问题中的选择新的列车),我们都要在这个蚂蚁的时间戳上更新时间。如果是很早以前就到了的列车,我们加上解体时间就好,如果是还没到的列车,我们需要等列车到了,再加上解体时间。然后在蚂蚁的列车库中先添加这个解体列车的列车节数,然后检查是不是凑够了当前出发列车需要的节数。如果凑够了就在蚂蚁车库中去除列车节数,否则就继续。
程序员都知道,当然这个列车问题有很多其他的设计细节,细节决定成败。详细说清楚的话很费力。有兴趣的看看代码,不懂再联系。

##代码部分##

###传统TSP###
这个代码是直接从网上粘过来的。来自于fashionxu.blogchina.com
这个代码是我自己调试通过了的。有什么疑问留言就好。

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
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int iAntCount=10;//ant numbers
const int iCityCount=48;
const int iItCount=5000;
const double Q=100;
const double alpha=3.0;
const double beta=5.0;
const double rou=0.9;
const double rain=0.022;
const double q0=0.3;
int besttour[iCityCount+1];
double rnd(int low,int uper)
{
double p=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);1;
return (p);
};
int rnd(int uper)
{
return (rand()%uper);
};
struct GInfo
{
double m_dDeltTrial[iCityCount][iCityCount];
double m_dTrial[iCityCount][iCityCount];
double distance[iCityCount][iCityCount];
}Map;
class ant
{
private:
double prob[iCityCount];
int m_iTopCity;
int allowed[iCityCount];
int ChooseNextCity();
void UpdateProb();
public:
double m_dLength;
int visited[iCityCount+1];
ant();
void addcity(int city);
void Clear();
void UpdateLength();
void move();
//void move2last();
};
ant::ant()
{
m_dLength=0;
m_iTopCity=0;
int i;
for(i=0;i<iCityCount;i++)
{
prob[i]=0.5;
allowed[i]=1;
}
}
void ant::addcity(int city)
{//add city to tabu;
visited[m_iTopCity]=city;
m_iTopCity++;
allowed[city]=0;
}
void ant::UpdateProb()
{
int i;
double temp=0;
int curCity=visited[m_iTopCity-1];
int c=0;
for (i=0;i<iCityCount;i++)
{
if(allowed[i])
{
double p=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);
temp+=p;
c++;
}
}
for (i=0;i<iCityCount;i++)
{
if(allowed[i])
{
if (temp==0)
prob[i]=(double)1.0/(double)c;
else
prob[i]=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)/temp;
}
else
prob[i]=0;
}
}
int ant::ChooseNextCity()
{//Update the probability of path selection
//select a path from tabu[m_iCityCount-1] to next
int i,j;
double temp;
double mRate=rnd(0,1);
int curCity=visited[m_iTopCity-1];
UpdateProb();
if (mRate>q0)
{
temp=-1;
for (i=0;i<iCityCount;i++)
{
//temp<prob[i];
if(allowed[i])
{
double p=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);
if (temp<p)
{
temp=p;
j=i;
}
}
}
}
else
{
double mSelect=0;
for (int i=0;i<iCityCount;i++)
{
mSelect+=prob[i] ;
if (mSelect>=mRate) {j=i;break;}
}
}
return j;
}
void ant::UpdateLength()
{// Update the length of tour
int i;
for(i=0;i<iCityCount;i++)
m_dLength+=Map.distance[visited[i]][visited[i+1]];
}
void ant::move()
{//the ant move to next town and add town ID to tabu.
int j;
j=ChooseNextCity();
addcity(j);
}
void ant::Clear()
{
m_dLength=0;
int i;
for(i=0;i<iCityCount;i++)
{
prob[i]=0.5;
allowed[i]=1;
}
i=visited[0];
m_iTopCity=0;
addcity(i);
}
class project
{
void initmap();
public:
double m_dShortest;
ant ants[iAntCount];
void UpdateTrial();
void GetAnt();
void StartSearch();
project();
};
project::project()
{//initial map,read map infomation from file . et.
struct city
{
int x;
int y;
}cc[iCityCount];
int num;
int i;
initmap();
m_dShortest=10e9;
ifstream in("48.txt");
for (i=0;i<iCityCount;i++)
{
in>>num>>cc[i].x>>cc[i].y;
besttour[i]=0;
}
int j;
for(i=0;i<iCityCount;i++)
for (j=0;j<iCityCount;j++)
Map.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2));
}
void project::initmap()
{
int i;
int j;
for(i=0;i<iCityCount;i++)
for (j=0;j<iCityCount;j++)
{
Map.m_dTrial[i][j]=1.0/(double)iCityCount;
Map.m_dDeltTrial[i][j]=0;
}
}
void project::GetAnt()
{//randomly put ant into map
int i=0;
int city;
srand( (unsigned)time( NULL ) +rand());
for (i=0;i<iAntCount;i++)
{
city=rnd(iCityCount);
ants[i].addcity(city);
}
}
void project::StartSearch()
{//begin to find best solution
int max=0;//every ant tours times
int i;
int j;
double temp;
int temptour[iCityCount+1];
while (max<iItCount)
{
for (i=0;i<iCityCount-1;i++)
for(j=0;j<iAntCount;j++)
ants[j].move();
for(j=0;j<iAntCount;j++)
{
ants[j].visited[iCityCount]=ants[j].visited[0];
ants[j].UpdateLength ();
}
//find out the best solution of the step and put it into temp
int t;
temp=ants[0].m_dLength ;
for (t=0;t<iCityCount+1;t++)
temptour[t]=ants[0].visited[t];
for(j=0;j<iAntCount;j++)
{
if (temp>ants[j].m_dLength) {
temp=ants[j].m_dLength;
for ( t=0;t<iCityCount+1;t++)
temptour[t]=ants[j].visited[t];
}
}
if(temp<m_dShortest){
m_dShortest=temp;
printf("%d : %f\n",max,m_dShortest);
for ( t=0;t<iCityCount+1;t++)
besttour[t]=temptour[t];
}
if (max %100==0)printf(" %d ",max);
UpdateTrial();
for(j=0;j<iAntCount;j++)
ants[j].Clear();
max++;
//char c;
//scanf("%c",&c);
}
printf("The shortest toure is : %f\n",m_dShortest);
for ( int t=0;t<=iCityCount;t++)
printf(" %d ",besttour[t]);
}
void project::UpdateTrial()
{//calculate the changes of trial information
int i;
int j;
for (i=0;i<iCityCount;i++)
{
for (j=0;j<iCityCount;j++)
{
//printf("trail is : %1.10f deltatrial is: %1.10f\n",Map.m_dTrial[i][j],Map.m_dDeltTrial[i][j]);
Map.m_dTrial[i][j]*=(1-rou);//*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j] );
//Map.m_dProb[i][j]=
//Map.m_dDeltTrial[i][j]=0;
}
}
for(i=0;i<iAntCount;i++)
{
for (j=0;j<iCityCount;j++)
{
Map.m_dDeltTrial[ants[i].visited[j]][ants[i].visited[j+1]]+=Q/ants[i].m_dLength ;
Map.m_dDeltTrial[ants[i].visited[j+1]][ants[i].visited[j]]+=Q/ants[i].m_dLength;
}
}
for (i=0;i<iCityCount;i++)
{
for (j=0;j<iCityCount;j++)
{
//printf("trail is : %1.10f deltatrial is: %1.10f\n",Map.m_dTrial[i][j],Map.m_dDeltTrial[i][j]);
Map.m_dTrial[i][j]=rou*(Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j] );
//Map.m_dProb[i][j]=
Map.m_dDeltTrial[i][j]=0;
}
}
}
int main()
{
project TSP;
TSP.GetAnt();
TSP.StartSearch();
char c;
scanf("%c",&c);
return 0;}

输入文件叫做“48.txt”,格式如下
48.txt

###列车解体问题###
输入文件格式如下:
首先是到达列车的数量,然后分别写出每个列车的信息
然后是出发列车的数量,然后写出每个列车的信息
aco_input.txt

Contents
,