__2017-12-11 如一模式识别研究

如一模式识别研究

基本数学知识>>c++ 使用蚁群算法解决TSP问题。

转自:http://blog.csdn.net/luo_xianming/article/details/24474281

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

显然,第一种的效果更好,当蚂蚁的总路程越短,使其留下来的信息素量越高。

代码如下:

[cpp] view plaincopy

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

for(j = 0;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]<

return 0;

}

写好后对测试用例进行测试,只有10个城市的最佳路径求解,发现一开始的代码执行后得到的结果偏差较大而且次次不同。然后对其中的一些常量进行了更改。但是发现这些常量是息息相关的,更改一个则会导致其他的常数效果变差。如当我将蚂蚁数量增加时,每次循环后增加的信息素量会变大,而使每一次的新的信息素增加占信息素量的比例变得极大,而是其对之前可能有的较好路径的敏感度降低。

决定这些常量的值是一件困难的事,测试了半天后,发现太难去寻找一个较好的搭配,而且在我选取的常量的搭配中,最多尝试了100000次循环依旧没有求的最佳解。完。

评论留言区

:
  

作者: 游客 ; *
评论内容: *
带*号为必填项目

如一模式识别更新提示

matlab在图像处理方面的应用有更新

如一模式识别 友情链接

关于本站作者     chinaw3c     mozilla