📄 marklink.cpp
字号:
if (rand()%100 > 20)
{
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)
{
//更新路径节点＋路径长度；
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];
}
w= rand()%(num_path_node-1);
// p= rand()%(num_sections+1);
// for (w=0; w<num_path_node-1;w++)
// {
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_best_path)
{
y[w]=p;
length_best_path = length;
length_total[k] = length;
}//end if
}//end if
}//end for p
// }//end for w
if(currentbest > length_total[k])
{
currentbest = length_total[k];
}
/* 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;
*/
mean[i]=mean[i]+length_total[k];
} //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;
}
*/
mean[i]=mean[i]/num_ants;
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;
}
}
/*
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
*/
if(flag)
{
for(p =0;p<num_path_node-1;p++) //更新各点的信息数
{
t[p][y[p]]=t[p][y[p]]+e*Q/length_best_path; //e是一常量
}
}
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]<<endl;
// cout <<mean[i]<<" ";
// cout << "第"<<i<<"次循环中的最短路径是 "<<length_best_path<<" "<<y[0]<<" "<<y[1]<<" "<<y[2]<<" "<<y[3]<<" "<<y[4]<<" "<<y[5]<<endl<<endl;
}//end of i (循环的次数)
/*
cout <<endl;
for(i=0; i<=num_cycle; i++)
{
cout << deviation[i] <<" ";
}
*/ return(length_best_path);
}
double acs_1()
{
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]; //能见度
bool flag; //标记此次循环中是否找到了更优解
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 ( q =0;q< num_path_node-1;q++)
y[q]=num_sections/2;
int i,j,k,m;
for (i = 0; i < num_cycle ; i++)
{
flag= false;
// length_best_path = infinite;
for(k = 0; k< num_ants ; k++)
{
length_total[k] = 0;
POINT front,current; //current定义当前调节的节点，front定义当前节点的前一节点
front = start;
int n;
// double high=0;
for (j = 0; j< num_path_node-1 ; j++ )
{
// n=0;
for (m = 0; m <= num_sections ; m++) //计算各个区间的能见度
{
d[j][m] = ( num_sections- abs(m-y[j]) )/(num_sections+1.0); //能见度
probability[j][m]= pow(t[j][m],f)*pow(d[j][m],v); //各个顶点的信息量（信息激素＋能见度）
// if (high < probability[j][m])
// {
// high = 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)
{
//更新路径节点＋路径长度；
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];
}
w= rand()%(num_path_node-1);
// p= rand()%(num_sections+1);
// for (w=0; w<num_path_node-1;w++)
// {
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;
now.y = vertex[q+1][0].y+(vertex[q+1][1].y-vertex[q+1][0].y)*p;
}
else
{
now.x = vertex[q+1][0].x+(vertex[q+1][1].x-vertex[q+1][0].x)*y[q];
now.y = vertex[q+1][0].y+(vertex[q+1][1].y-vertex[q+1][0].y)*y[q];
}//end if
length = length+line_length(before,now);
before = now;
}// end for q
length = length+line_length(before,end);
if ( length < length_best_path)
{
y[w]=p;
length_best_path = length;
}//end if
}//end if
}//end for p
// }//end for w
/* 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;
*/
} //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(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;
}
}
/* 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
*/
if(flag)
{
for(p =0;p<num_path_node-1;p++) //更新各点的信息数
{
t[p][y[p]]=t[p][y[p]]+e*Q/length_best_path; //e是一常量
}
}
cout << "第"<<i<<"次循环中的最短路径是 "<<length_best_path<<" "<<y[0]<<" "<<y[1]<<" "<<y[2]<<" "<<y[3]<<" "<<y[4]<<" "<<y[5]<<endl<<endl;
}//end of i (循环的次数)
return(length_best_path);
}
double acs_2()
{
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]; //能见度
bool flag; //标记此次循环中是否找到了更优解
// double currentbest; //记录每次循环中的路径最优值
double deviation[num_cycle]; //标准偏差
double mean[num_cycle]; //记录每次循环平均值
// clock_t start_time, finish_time; //记录每次循环起止的时间
// double duration[num_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[6],y_best[6]; //初始t参数
for ( q =0;q< num_path_node-1;q++)
{
y[q]=num_sections/2;
y_best[q]=num_sections/2;
}
int best_cycle=0; //标识在第i次循环中寻找到最短路径
int i,j,k,m;
for (i = 0; i < num_cycle ; i++)
{
// start_time = clock();
flag= false;
// length_best_path = infinite;
mean[i]=0;
deviation[i]=0;
for(k = 0; k< num_ants ; k++)
{
length_total[k] = 0;
POINT front,current; //current定义当前调节的节点，front定义当前节点的前一节点
front = start;
int n;
double high ;
for (j = 0; j< num_path_node-1 ; j++ )
{
n=0;
high=0;
for (m = 0; m <= num_sections ; m++) //计算各个区间的能见度
{
d[j][m] = ( num_sections- abs(m-y[j]) )/(num_sections+1.0); //能见度
probability[j][m]= pow(t[j][m],f)*pow(d[j][m],v); //各个顶点的信息量（信息激素＋能见度）
if (high < probability[j][m])
{
high = 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 > 90 )
{
double wheel_pos = probability[j][num_sections] * (rand()%100)/100;
n=0;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -