TSP问题,旅行商问题:假如一个旅行商人要拜访n个城市,他必须选择所有要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。选择全部路径中的最小值。TSP具有NP计算复杂度(NP是指在非确定性图灵机上有多项式时间算法的问题)。TSP问题是数图论中重要的一个问题,即“已给一个n个点的完全图,每条边都有一个长度,求总长度最短的经过每个顶点正好一次的封闭回路”。
蚁群算法:蚁群算法是一种基于种群,通过模拟蚁群采集食物的过程的启发式搜索算法。蚂蚁通过释放信息素来记录路径,并趋向于走信息素量较多的路径来寻找最佳路径。其中一些限制的参数。
1.信息素的总量:蚂蚁拥有的信息素是有一定总量的,则在出发出信息素量较多,在一定距离后信息素会用尽,以防止其越走越远。
2.观测范围:蚂蚁有一定的观测范围,会选择信息素较多的路径。
3.出错概率:蚂蚁有一定的出错概率,会不往信息素最多的区域走。这使算法不过早的收敛。
4.信息素的消减速度:信息素以一定的速度消减,使一些不合适的路径上的信息素能消失,以减少对蚂蚁的干扰。
5.记忆能力:蚂蚁应该记住之前总过的路径,以防止回头,但是这个值较大时,会较低效率。
结合TSP问题,应做的一些改进:
蚂蚁数量为m,城市数量为n,城市间的距离为D[ i ] [ j ]。蚂蚁行走的过程不应该是以一定速度行走,而是以 一个时间段进行行走,在这个时间段内,每个蚂蚁都能完整的从一个城市走到另一个城市。则在n个时间段后,蚂蚁完成了一次回路,则n个时间段合起来为一次循环,计循环次数为K。每只蚂蚁在一个循环中走过的城市编号,保存在 Path [m] [n];中,对于Path[m][0]]默认为出发点,则蚂蚁无法走路径中的点,则最后一个点不是初始点,但之后要回到初始点,要注意一下。
对于这个系统,应该选择标记的是点还是边,即蚂蚁留下信息素的地方是边还是点。暂时使用边,以方便之后的信息素消散的操作。虽然对于一个点去选取其下一个路径来说,下一个点上的信息素浓度与下一条边上的浓度效果是相同的,但由于这是完全图,对于其他点在选取边时,会被其他点的最佳选取所增加的信息素所干扰。
对于信息素,在蚁群算法中有两种信息素,一种是找到食物的蚂蚁留下的信息素,一种是找到家的蚂蚁留下的信息素。而在TSP中,蚂蚁肯定会找到家,则只有一种信息素。则每完成一次循环后,进行信息素的更新。信息素的更新公式:
Phe [ i ][ j ] = Dis* Phe[i][j] + DPhe[i][j]
Phe 表示 每条边上的信息素浓度,Dis为信息素消逝的速率,DPhe为本次循环内的边ij的信息素增加量。DPhe的值为 每个蚂蚁在本次循环留在路径ij上的信息素量KDPhe的总和,对于KDPhe有三种模型,Ant-Circle System , Ant-Quantity System 和 Ant-Density System.效果最好的为第一种。具体为
Ant-Circle System : KDPhe = Q / LK 或0(当蚂蚁未经过此路径时。Q为一个常量,LK为这个循环中,此蚂蚁的总路程)
Ant-Quantity System : KDPhe = Q / D[i][j] 或0
Ant-Density System .: KDPhe = Q 或 0
显然,第一种的效果更好,当蚂蚁的总路程越短,使其留下来的信息素量越高。
代码如下:
using namespace std; //使用10个蚂蚁,进行10个城市的TSP问题求解。 const int MMax = 9999;//蚂蚁数量,蚂蚁数量根据城市数量决定。 const int NMax = 500;//城市数量最大数量,超过出错 int m,n;//蚂蚁数量与城市数量 const double Q = 999 ;//常量 const int K = 1000;//循环总次数 int D[NMax][NMax];//路径长度 double Phe[NMax][NMax];//边对应的信息素浓度 int LK;//蚂蚁此循环中的总路径长度 int Path[MMax][NMax];//记录蚂蚁的路径,用于防止走重复的路。记录的是点 int ant;//蚂蚁当前所在点 int i,j,k,p;//循环使用 double Dis = 0.1;//每次信息素 消失的速率 int sameNum,samePhe[NMax];//每次去寻找信息素最多的边,如初始情况,信息素量都相同时,要 //随机的去从中选取边。 int bugNum,bugTry[NMax];//出错情况下进行的选择 double bugP = 0.90;//每一次操作的出错概率 //后来发现,出错概率要结合蚂蚁数与城市数进行判断,而定值Q为估计距离 int start;//出发点,城市编号从0 - n-1. double Max;//用来选取最多信息素的边 bool Passed[NMax];//用来判断城市是否已经经过,是否可以选取 int main() { //载入数据 fstream f("data.txt",ios::in); f >> n; if( n > NMax)//本来想直接赋值,后来又决定从文件中读入。 return 0; for(i = 0;i<n;i++) for(j = 0;j<n ;j++) if(j != i) f>>D[i][j]; for(i = 0;i < n;i++) D[i][i] = 0; f >> start; if(start > n-1)return 0;//没必要的检测,如果文件未正确书写,发生意外的错误,概不负责。 f.close(); for(i = 0;i < n;i++) for(j = 0; j < n;j++) Phe[i][j] = 1;//初始化每条边上的信息素浓度 for(i = 0;i< m;i++) Path[i][0] = start;//每只蚂蚁的出发点都固定 m = 999;//蚂蚁数为城市数的2倍,后来发现不够 for(k = 0;k < K;k++){ for(i = 0;i < n;i++) for(j = 0; j < n;j++) Phe[i][j] *= Dis ;//每次循环后,进行信息素的消逝 srand((unsigned)time(NULL)); for(i = 0;i < m;i++){//对于每只蚂蚁,进行一次循环 ant = start; for(j = 0;j < n;j++) Passed[j] = false; Passed[ant] = true; for(j = 1;j < n;j++){//每只蚂蚁选n-1次边 Max = 0; sameNum = 0 ; bugNum = 0; for(p = 0;p < n;p++) if(!Passed[p]) Max = Max > Phe[ant][p] ? Max : Phe[ant][p] ;//寻找周围边上信息素的最大值 for(p = 0;p < n;p++) if(Max == Phe[ant][p]) if(!Passed[p]) samePhe[sameNum++] = p;//记录信息素取最大值时,对应的city编号和数量 for(p = 0;p < n;p++) if(!Passed[p]) bugTry[bugNum++] = p; if( (double)rand() /32765 < bugP) ant = samePhe[ rand() % sameNum ] ;//用随机数,从中选中一条边 else ant = bugTry [ rand() % bugNum ] ;//出错情况下,随机选一条边 Passed[ant] = true;//路径经过 Path[i][j] = ant;//保存路径 } } //完成对每一个蚂蚁的操作后,进行增加信息素的操作,使用Ant-Circle System for(i = 0; i < m;i++){ LK = 0 ; for(j = 0; j < n-1;j++) LK += D[Path[i][j]][Path[i][j+1]];//计算一次循环中蚂蚁的总路程 LK += D[Path[i][j]][Path[i][0]];//回到初始点 for(j = 0; j < n-1;j++) Phe[Path[i][j]][Path[i][j+1]] += Q/LK ; Phe[Path[i][j]][Path[i][0]] += Q/LK ;//初始点 } } p = 0xfffff;//虽然已经完成操作,但我们要直观的从所有现有路径中找出最短的路径。 for(i = 0;i < m;i++){ LK = 0; for(j = 0;j < n-1;j++) LK += D[Path[i][j]][Path[i][j+1]];//计算一次循环中蚂蚁的总路程 LK += D[Path[i][j]][Path[i][0]];//回到初始点 if(LK < p){ p = LK; start = i; } } for(i = 0;i < n; i++) cout << Path[start][i]<<"->"; cout << Path[start][0]<<endl; return 0; }
写好后对测试用例进行测试,只有10个城市的最佳路径求解,发现一开始的代码执行后得到的结果偏差较大而且次次不同。然后对其中的一些常量进行了更改。但是发现这些常量是息息相关的,更改一个则会导致其他的常数效果变差。如当我将蚂蚁数量增加时,每次循环后增加的信息素量会变大,而使每一次的新的信息素增加占信息素量的比例变得极大,而是其对之前可能有的较好路径的敏感度降低。
决定这些常量的值是一件困难的事,测试了半天后,发现太难去寻找一个较好的搭配,而且在我选取的常量的搭配中,最多尝试了100000次循环依旧没有求的最佳解。完。