📄 marklink.cpp
字号:
while (probability[j][n]<wheel_pos) n++;
// if (n!=n2)
// n=n2;
// else n=rand()%(num_sections+1);
}
path1[k][j][path[k][j]]=false;
path[k][j]=n; //第j个节点上，第k只蚂蚁选择第0.n处
path1[k][j][n] = true;
current.x = vertex[j+1][0].x + (vertex[j+1][1].x - vertex[j+1][0].x)*n/num_sections; //在当前路径点的调节中，蚂蚁选择的路径点
current.y = vertex[j+1][0].y + (vertex[j+1][1].y - vertex[j+1][0].y)*n/num_sections;
length_total[k] = length_total[k] + line_length(front,current); //计算第k只蚂蚁走过的总路径
front = current;
} //end of j（0～num 需要调整的节点数）
length_total[k] = length_total[k] + line_length(front,end); //计算第k只蚂蚁走过的总路径
/* w= rand()%(num_path_node-1); //2-opt
for(p =0;p<=num_sections;p++)
{
if (p!=y[w])
{
POINT before,now;
before.x=start.x;
before.y=start.y;
double length=0;
for (q=0;q<num_path_node-1;q++)
{
if (q == w)
{
now.x = vertex[q+1][0].x+(vertex[q+1][1].x-vertex[q+1][0].x)*p/num_sections;
now.y = vertex[q+1][0].y+(vertex[q+1][1].y-vertex[q+1][0].y)*p/num_sections;
}
else
{
now.x = vertex[q+1][0].x+(vertex[q+1][1].x-vertex[q+1][0].x)*y[q]/num_sections;
now.y = vertex[q+1][0].y+(vertex[q+1][1].y-vertex[q+1][0].y)*y[q]/num_sections;
}//end if
length = length+line_length(before,now);
before = now;
}// end for q
length = length+line_length(before,end);
if ( length < length_total[k])
{
path1[k][w][path[k][w]]=false;
path1[k][w][p]=true;
path[k][w]=p;
length_total[k] = length;
}//end if
}//end if
}//end for p
*/
if (length_best_path > length_total[k])//更新路径节点＋路径长度；
{
// flag = true;
for (j = 0; j< num_path_node-1 ; j++)
{
y[j]=path[k][j];
for (m = 0; m <= num_sections ; m++)
{
best_path[j][m] =path1[k][j][m];
}
}
length_best_path = length_total[k];
best_cycle=i;
}
mean[i]=mean[i]+length_total[k];
for( p =0;p<num_path_node-1;p++) //更新各点的信息数
for ( w =0;w<= num_sections;w++)
{
if (path1[k][p][w])
t[p][w]=t[p][w]*s+0.1*c;
}//end for k
// cout << "第"<<i<<"次循环 第"<<k<<"只蚂蚁所走的路径是"<<length_total[k]<<endl;
} //end of k（蚂蚁的数量）
mean[i]=mean[i]/num_ants;
for (k = 0; k < num_ants ; k++)
{
deviation[i]=deviation[i]+(length_total[k]-mean[i])*(length_total[k]-mean[i]);
}
deviation[i] = sqrt(deviation[i]/num_ants);
cout <<length_best_path<<" "<<mean[i]<<" "<<deviation[i]<<" "<<best_cycle<<endl;
// cout << length_best_path<<" ";
// cout << currentbest<<" ";
// cout << "第"<<i<<"次循环中的最短路径是 "<<length_best_path<<" "<<y[0]<<" "<<y[1]<<" "<<y[2]<<" "<<y[3]<<" "<<y[4]<<" "<<y[5]<<endl;
for(p =0;p<num_path_node-1;p++) //更新各点的信息数
{
for (w =0;w<= num_sections;w++)
{
t[p][w]=t[p][w]*s+0.1*c;
if (best_path[p][w]) //更新信息数语句1
// t[p][w]=t[p][w]+e*Q/length_best_path; //e是一常量
t[p][w]=t[p][w]+1/length_best_path; //e是一常量
}//end for w
}//end for p
/*
if(flag) //更新信息数语句3
{
for(p =0;p<num_path_node-1;p++) //更新各点的信息数
{
t[p][y[p]]=t[p][y[p]]+e*Q/currentbest; //e是一常量
}
}
*/
/* if ((i-best_cycle) > 7) //若超过7次循环还未找到更优解则将y[p]的值赋值为当前最短路径的y_best[]的值
{
for(p =0;p<num_path_node-1;p++)
{
y[p]=y_best[p];
}
}
*/
// finish_time = clock();
// duration[i] = (double)(finish_time - start_time) / CLOCKS_PER_SEC;
// cout <<length_best_path<<" "<<mean[i]<<" "<<deviation[i]<<" "<<currentbest<<" "<<duration[i]<<endl;
}//end of i (循环的次数)
return(length_best_path);
}
double ant_path()
{
double t[MAX][num_sections+1]; // 存储节点上的信息量
int path[num_ants][MAX]; //存储第k个蚂蚁在第n个节点的上的选择区域
bool path1[num_ants][MAX][num_sections+1]; //当第k个蚂蚁经过第n个节点的第m个区域时为true
double probability[MAX][num_sections+1]; //蚂蚁经过第n个节点的第m个区域的概率
double length_total[num_ants]; //存储每只蚂蚁所走相应路径的长度
bool best_path[MAX][num_sections+1];
double d[MAX][num_sections+1]; //能见度
int best=0; //表示最佳路径的蚂蚁
int best_cycle;
int p,q,w;
for( p =0;p< num_path_node-1;p++) //初始化各节点上的信息量
for ( w =0;w<= num_sections;w++) //num_path_node 用floyd算法求出的最短路径上的顶点数（包括起点和终点，且是从0开始计数）
{ //但是用蚁群算法只要调节除起点和终点以外的点，这些点的总数是num_path_node+1-2
t[p][w]=c; //在记录路径时，只考虑之间需要调节的路径点,他们在middle中相应的下标为此时的下标＋1
if (w ==5)
best_path[p][w] = true;
else
best_path[p][w] = false;
}
for( p =0;p<num_ants;p++)
for (q = 0; q< num_path_node-1;q++)
for ( w =0;w<=num_sections;w++)
path1[p][q][w]=false;
for( p =0;p<num_ants;p++) //初始化各蚂蚁的初始路径，均为0.5
for ( q =0;q< num_path_node-1;q++)
{
path[p][q] = 5;
path1[p][q][5]=true;
}
int y[MAX]; //初始t参数
for (p=0;p<num_path_node-1;p++)
{
y[p]=num_sections/2;
}
int i,j,k,m;
for (i = 0; i < num_cycle ; i++)
{
for(k = 0; k< num_ants ; k++)
{
length_total[k] = 0;
POINT front,current; //current定义当前调节的节点，front定义当前节点的前一节点
front = start;
int n ;
for (j = 0; j< num_path_node-1 ; j++ )
{
n=0;
for (m = 0; m <= num_sections ; m++) //计算各个区间的能见度
{
d[j][m] = ( num_sections+1- abs(m-y[j]) )/(num_sections+1.0); //能见度
probability[j][m]= pow(t[j][m],f)*pow(d[j][m],v); //各个顶点的信息量（信息激素＋能见度）
if (probability[j][n] < probability[j][m]) n=m; //n是最大值对应的num_section
if (m) probability[j][m]=probability[j][m]+probability[j][m-1];
} //end of m (0～11)
if (rand()%100 > 80)
{
double wheel_pos = probability[j][num_sections] * (rand()%100)/100;
n=0;
while (probability[j][n]<wheel_pos) n++;
}
path[k][j]=n; //第j个节点上，第k只蚂蚁选择第0.n处
path1[k][j][n] = true;
current.x = vertex[j+1][0].x + (vertex[j+1][1].x - vertex[j+1][0].x)*n/num_sections; //在当前路径点的调节中，蚂蚁选择的路径点
current.y = vertex[j+1][0].y + (vertex[j+1][1].y - vertex[j+1][0].y)*n/num_sections;
length_total[k] = length_total[k]+line_length(front,current); //计算第k只蚂蚁走过的总路径
front = current;
} //end of j（0～num 需要调整的节点数）
length_total[k] = length_total[k] + line_length(front,end); //计算第k只蚂蚁走过的总路径
if (length_total[k] < length_best_path)
{
//更新路径节点＋路径长度；
for (j = 0; j< num_path_node-1 ; j++)
for (m = 0; m <= num_sections ; m++)
{
best_path[j][m] =path1[k][j][m];
}
length_best_path = length_total[k];
best = k;
best_cycle = i;
}
/* for(int p =0;p<num_path_node-1;p++) //更新各点的信息数
for (int w =0;w<= num_sections;w++)
t[p][w]=t[p][w]*s+0.1*c;
*/
} //end of k（蚂蚁的数量）
for (j = 0; j< num_path_node-1 ; j++)
for (m = 0; m <= num_sections ; m++)
{
if (best_path[j][m]) y[j]=m;
}
for(int p =0;p<num_path_node-1;p++) //更新各点的信息数
{
for (int w =0;w<= num_sections;w++)
{
t[p][w]=t[p][w]*s+0.1*c;
if (best_path[p][w])
t[p][w]=t[p][w]+e*Q/length_best_path; //e是一常量
for (k = 0; k<num_ants; k++)
{
if (path1[k][p][w])
t[p][w]=t[p][w]+Q/length_total[k]; //Q是一常量
}//end for k
}//end for w
}//end for p
// cout << "第"<<i<<"次循环中最短路径的参数是"<<length_best_path<<endl<<endl;
cout << length_best_path<<" ";
}//end of i (循环的次数)
return(length_best_path);
}
double ant_path_improve()
{
double t[MAX][num_sections+1]; // 存储节点上的信息量
int path[num_ants][MAX]; //存储第k个蚂蚁在第n个节点的上的选择区域
bool path1[num_ants][MAX][num_sections+1]; //当第k个蚂蚁经过第n个节点的第m个区域时为true
double probability[MAX][num_sections+1]; //蚂蚁经过第n个节点的第m个区域的概率
double length_total[num_ants]; //存储每只蚂蚁所走相应路径的长度
bool best_path[MAX][num_sections+1];
double d[MAX][num_sections+1]; //能见度
int best; //表示最佳路径的蚂蚁
int best_cycle;
int p,q,w;
//////////////////////虚拟部分/////////////////////////////////////
num_path_node = 0;
vertex[num_path_node][0]=start;
vertex[num_path_node++][1]=start;
vertex[num_path_node][0]=barrier[2].vertex;
vertex[num_path_node++][1]=barrier[5].vertex;
vertex[num_path_node][0]=barrier[3].vertex;
vertex[num_path_node++][1]=barrier[6].vertex;
vertex[num_path_node][0]=barrier[3].vertex;
vertex[num_path_node++][1]=barrier[7].vertex;
vertex[num_path_node][0]=barrier[7].vertex;
vertex[num_path_node++][1]=barrier[12].vertex;
// vertex[num_path_node][0]=barrier[12].vertex;
// vertex[num_path_node++][1]=barrier[18].vertex;
// vertex[num_path_node][0]=barrier[11].vertex;
// vertex[num_path_node++][1]=barrier[19].vertex;
vertex[num_path_node][0]=end;
vertex[num_path_node][1]=end;
///////////////////////////////////////////////////////////////////
for( p =0;p< num_path_node-1;p++) //初始化各节点上的信息量
for ( w =0;w<= num_sections;w++) //num_path_node 用floyd算法求出的最短路径上的顶点数（包括起点和终点，且是从0开始计数）
{ //但是用蚁群算法只要调节除起点和终点以外的点，这些点的总数是num_path_node+1-2
t[p][w]=c; //在记录路径时，只考虑之间需要调节的路径点,他们在middle中相应的下标为此时的下标＋1
if (w ==5)
best_path[p][w] = true;
else
best_path[p][w] = false;
}
for( p =0;p<num_ants;p++)
for (q = 0; q< num_path_node-1;q++)
for ( w =0;w<=num_sections;w++)
path1[p][q][w]=false;
for( p =0;p<num_ants;p++) //初始化各蚂蚁的初始路径，均为0.5
for ( q =0;q< num_path_node-1;q++)
{
path[p][q] = 5;
path1[p][q][5]=true;
}
int i,j,k,m;
for (i = 0; i < num_cycle ; i++)
{
int y[4]; //初始t参数
y[0]=10;
y[1]=10;
y[2]=10;
y[3]=10;
// y[4]=5;
// y[5]=5;
// length_best_path = infinite;
for(k = 0; k< num_ants ; k++)
{
length_total[k] = 0;
POINT front,current; //current定义当前调节的节点，front定义当前节点的前一节点
front = start;
int n ;
for (j = 0; j< num_path_node-1 ; j++ )
{
n=0;
for (m = 0; m <= num_sections ; m++) //计算各个区间的能见度
{
d[j][m] = ( 21- abs(m-y[j]) )/21.0; //能见度
probability[j][m]= pow(t[j][m],f)*pow(d[j][m],v); //各个顶点的信息量（信息激素＋能见度）
// if (probability[j][n] < probability[j][m]) n=m; //n是最大值对应的num_section
if (m) probability[j][m]=probability[j][m]+probability[j][m-1];
} //end of m (0～11)
// if (rand()%100 > 80)
// {
double wheel_pos = probability[j][num_sections] * (rand()%100)/100;
n=0;
while (probability[j][n]<wheel_pos) n++;
// }
path[k][j]=n; //第j个节点上，第k只蚂蚁选择第0.n处
path1[k][j][n] = true;
current.x = vertex[j+1][0].x + (vertex[j+1][1].x - vertex[j+1][0].x)*n/num_sections; //在当前路径点的调节中，蚂蚁选择的路径点
current.y = vertex[j+1][0].y + (vertex[j+1][1].y - vertex[j+1][0].y)*n/num_sections;
length_total[k] = length_total[k] + line_length(front,current); //计算第k只蚂蚁走过的总路径
front = current;
} //end of j（0～num 需要调整的节点数）
length_total[k] = length_total[k] + line_length(front,end); //计算第k只蚂蚁走过的总路径
// cout << "第"<<i<<"次循环 第"<<k<<"只蚂蚁所走的路径是"<<length_total[k]<<endl;
if (length_total[k] < length_best_path)
{
//更新路径节点＋路径长度；
for (j = 0; j< num_path_node-1 ; j++)
for (m = 0; m <= num_sections ; m++)
{
best_path[j][m] =path1[k][j][m];
}
length_best_path = length_total[k];
best = k;
best_cycle = i;
}
/* for(int p =0;p<num_path_node-1;p++) //更新各点的信息数
for (int w =0;w<= num_sections;w++)
t[p][w]=t[p][w]*s+0.1*c;
*/
} //end of k（蚂蚁的数量）
for (j = 0; j< num_path_node-1 ; j++)
for (m = 0; m <= num_sections ; m++)
{
if (best_path[j][m]) y[j]=m;
}
for(int p =0;p<num_path_node-1;p++) //更新各点的信息数
{
for (int w =0;w<= num_sections;w++)
{
t[p][w]=t[p][w]*s+0.1*c;
if (best_path[p][w]=true)
t[p][w]=t[p][w]+e*Q/length_best_path; //e是一常量
for (k = 0; k<num_ants; k++)
{
if (path1[k][p][w]=true)
t[p][w]=t[p][w]+Q/length_total[k]; //Q是一常量
}//end for k
}//end for w
}//end for p
cout << "第"<<i<<"次循环中最短路径的参数是"<<length_best_path<<endl<<endl;
// cout <<length_best_path<<endl;
}//end of i (循环的次数)
return(length_best_path);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -