题目：蚁群优化算法的连续空间函数求解
实验目的：加深了解蚁群优化算法的原理，深入认识智能优化算法的重要性，拓展算法的应用领域与空间
实验内容与算法详细设计介绍：
1．先熟悉基本蚁群优化算法的设计思想：
蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己
的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。
2．基本蚁群优化算法的实现
初始化过程
设t:=0; {t时间计数器}
Nc:=0; {Nc为循环次数计数器}
τij(t):=C; {为每条路径(i, j)设一个轨迹强度的初始值}
∆τij=0; {轨迹强度增量的初值设为0}
ηij由某种启发式算法确定； {在TSP中，
ηij=1/dij}
tabuk= Φ; {在初始阶段，禁忌表为空}
将m只蚂蚁随机置于n个节点（城市）上；
设置s:=1; {s为禁忌表索引，将各只蚂蚁的初始城市置于
当前禁忌表中}
for i:=1 to n do
for k:=1 to bi(t) do
tabuk(s)=i
重复直到禁忌表满为止{这一步要重复(n-1)次}
设置s:= s +1;
for i:=1 to n do
for k:=1 to bi(t) do
• 以概率选择城市j;
• 将蚂蚁k移到j;
将刚刚选择的城市j加到tabuk中；
信息素调整：
记录到目前为止的最短路径
if Nc < N_max
then
清空所有的禁忌表
设置s:= 1;
for i:=1 to n do
for k:=1 to bi(t) do
tabuk(s)=i {一次循环后蚂蚁又重新回到初始位置}
设t:= t +1;
对于每一个路径(i, j)，设置∆ τij(t, t+1):=0;
返回步骤（2）;
else
输出最短路径；
3．本程序遵循基本蚁群优化算法的思想，但在某些细节和形式方面有所变形：
程序求F（X,Y,Z）=X^3+ Y^3+Z^3的最小值，因此取fit最小时候的X，Y，Z作为解向量，其它维可做相应扩展，扩展[3]那一维，当求一维时候，删去此维，算法采用c++语言编写，细节如下：
cacs4fun.h分析：
alpha, rho, p0，tau0，dimension，num_layers，num_ants，num_iters均为常数参数，视具体目标函数而定，在main.cpp中， alpha=0.2;num_ants=50;
num_iters=2000;num_layers=200;dimension=10;p0=0.1;rho=0.2;tau0=0.01;
根据设计后测试所得，基本为最适合的常数参数。 dimension，num_layers，num_ants，num_iters的值越大程序执行速度越慢。
具体测试数值如下：(每个常数参数的测试都选择四个数，即最后输出的 fit[i],测试时其它常数都相同，仅待测常数变化)
AverageFit AverageFit
Alpha=0.05 1.268 num_ants=20 0.02
Alpha=0.1 0.526 num_ants=50 0.02
Alpha=0.2 0.018 num_ants=100 0.0144
Alpha=0.3 0.019 num_ants越大执行速度越慢，精确
Alpha=0.5 0.027
Alpha=0.8 0.007
AverageFit AverageFit
num_iters=3000 0.018 layers=500 0.0144
num_iters=2000 0.02 layers=100 0.027
num_iters=1000 0.08 layers=10 太大
num_iters=800 0.66
num_iters越大执行速度越慢，精确
dimension,p0,rh0略。
double ****tau 定义tau[60][3][10][11]数组，tau[num_layers][3][lastpos][curpos]
代表进行第num_layers层次（精度时），在X，Y，Z坐标上，两个位置间的信息素
double *gbx , *gby,*gbz 表示最好的位置坐标
int ***ant ant[num_ants][ layer][3]表示第num_ants个蚂蚁行进到layer时X，Y，Z坐标，最后的[3]代表X，Y，Z坐标
double **x, **y, **z 数组记录各个X，Y，Z坐标上的译码x[num_ants][ dimension]
main.cpp分析：
srand(time(NULL)); time(NULL)利用系统时间设置种子，srand(time(NULL))产生随机数，用scrand()设置种子数，可以用系统时钟time()来设置，rand()得到随机数。在使用rand()之前，必须用srand()来设置种子数，否则的话，rand（）得到的是伪随机数（有一定规律性）
初始化常数参数；
acs.allocate_vars();为变量分配内存空间；
acs.start();开始搜索过程；
start()过程如下：
void CAcs4Fun::init_vars()：：
gbfit=100000;全局最好适应度设置成大值
为tau[60][3][10][11]每一个元素赋值（赋值为tau0=0.01）
for (cur_iter=0; cur_iter< num_iters; cur_iter++)
{for (cur_layer=0; cur_layer<num_layers; cur_layer++)
{for (cur_ant=0; cur_ant<num_ants; cur_ant++)
{ant_move ( cur_ant, cur_layer );
蚂蚁从当前位置爬向下一个结点；
local_update ( cur_ant, cur_layer );
局部变量更新；
}
}
译码；
评价适应度；
找到全局最好的蚂蚁；
更新全局变量；
输出本代最好的适应度；
}结束循环
输出最好适应度，输出最好的X，Y，Z方向的坐标；
4．具体细节：
void CAcs4Fun::release_vars()释放变量内存，逐维释放内存，delete[]函数为释放数组的；
void CAcs4Fun::allocate_vars()分配变量内存，其中tau[num_layers][3][pssition] [10]存放最后一维中前九个元素的值
void CAcs4Fun::init_vars()初始化禁忌表；
void CAcs4Fun::ant_move(int ant_no, int layer)蚂蚁选择移动位置，选择具有最大信息素浓度的路径（在X，Y，Z方向上）
{////以在X方向上寻找为例子解析：
int last_pos[3], next_pos[3];///定义位置向量
double tx///记录信息素浓度
if处于第0layer, last_pos[0]=0;
else pseudo-random-proportional法则：ACO的路径选择规则，也称为随机机率法则，选择路径由随机机率决定
}
void CAcs4Fun::local_update(int ant_no, int layer)///局部更新
void CAcs4Fun::get_best_ant()///找到最好的蚂蚁
void CAcs4Fun::global_update()///全局更新
void CAcs4Fun::decode()///译码，将路径上的1~10转换成double型
void CAcs4Fun::evaluate()///适应度评估
5.程序评价
收敛时仍有误差，每次跟每次运行时都不一样结果，运行后输出每一代最好适度最后一个适应度为全局最好，还将输出蚂蚁最好位置的坐标向量；
程序缺点：没有X，Y，Z的定义域限制区间，怎么办？
或许在void CAcs4Fun::decode()中增加限制性语句：
If(x[i][j]>=b) x[i][j]=b; If(x[i][j]<=a) x[i][j]=a;
If(y[i][j]>=b) x[i][j]=b; If(y[i][j]<=a) y[i][j]=a;
If(z[i][j]>=b) x[i][j]=b; If(z[i][j]<=a) z[i][j]=a;
6.程序代码
#include "CACS4Fun.h"
#include <stdlib.h>
#include <math.h>
#include <iostream.h>
///设计三维空间连续函数蚁群优化问题
CAcs4Fun::CAcs4Fun()//定义CAcs4Fun类的构造函数
{
need_release=false; //表明内存没有被分配给变量
//需要释放变量内存
}
CAcs4Fun::~CAcs4Fun()//定义CAcs4Fun类的析构函数
{
if(need_release)
release_vars();//调用
}
void CAcs4Fun::release_vars()///释放变量内存
{
int i,j,k;
for (i=0; i<num_layers; i++)
{
for (j=0; j<3; j++)
{for (k=0; k<10; k++)
{delete[] tau[i][j][k];}///delete[]函数释放数组内存
delete[] tau[i][j];}
delete[] tau[i];}///tau[60][3][10][11]
delete[] tau;
for (i=0; i<num_ants; i++)///int **ant
delete[] ant[i];
delete[] ant;
for (i=0; i<num_ants; i++)///double **x
delete[] x[i];
delete[] x;
for (i=0; i<num_ants; i++)///double **y
delete[] y[i];
delete[] y;
for (i=0; i<num_ants; i++)///double **z
delete[] z[i];
delete[] z;
delete[] gbx;///double *gbx
delete[] gby;///double *gbx
delete[] gbz;///double *gbx
delete[] fit;
for (i=0; i<num_layers; i++)
delete[] gbant[i];
delete[] gbant;///int **gbant
for (i=0; i<num_layers; i++)///int **ibant
delete[] ibant[i];
delete[] ibant;
need_release=false;///变值
}
void CAcs4Fun::allocate_vars()///分配变量内存
{
int i, j,k;
if(need_release==true)
release_vars();
///double ****tau
tau=new double***[num_layers];
for (i=0; i<num_layers; i++)
{
tau[i]=new double**[3];
for (j=0; j<3; j++)
{tau[i][j]=new double*[10];
for (k=0; k<10; k++)
{tau[i][j][k]=new double[10+1];///最后一维的第10个空间存放前面九个的和
}
}///tau[60][3][10][11]
}
//int **ant;
ant=new int**[num_ants];
for (i=0; i<num_ants; i++)
{ant[i]=new int*[num_layers];
{for (j=0; j<num_layers; j++)
ant[i][j]=new int[3];}}
//double *fit;
fit=new double[num_ants];
//int *gbant;
gbant=new int*[num_layers];
for (i=0; i<num_layers; i++)
{gbant[i]=new int[3];}
//int *ibant;
ibant=new int*[num_layers];
for (i=0; i<num_layers; i++)
{ibant[i]=new int[3];}
//double **x;
x=new double*[num_ants];
for (i=0; i<num_ants; i++)
x[i]=new double[dimension];
//double **y;
y=new double*[num_ants];
for (i=0; i<num_ants; i++)
y[i]=new double[dimension];
//double **z;
z=new double*[num_ants];
for (i=0; i<num_ants; i++)
z[i]=new double[dimension];
//double *gbx;
gbx=new double[dimension];
//double *gby;
gby=new double[dimension];
//double *gbz;
gbz=new double[dimension];
need_release=true;
layers_per_dimension=num_layers/dimension;///每段精度
}
void CAcs4Fun::init_vars()
{
int i, j, k,m;
gbfit=100000;//全局最好适应度设置成大值
for (i=0; i<num_layers; i++)
{ for (j=0; j<3; j++)
{ for (k=0; k<10; k++)
{for (m=0; m<11; m++)
tau[i][j][k][m]=tau0;
tau[i][j][k][10]=tau0*10;
}
}
}
}
void CAcs4Fun::ant_move(int ant_no, int layer)///蚂蚁选择移动位置
{
int last_pos[3], next_pos[3];
int i;
double tx,ty,tz;
///last_pos[3]表示在上次移动中最后一个结点
///next_pos[3]表示将要移动的下一个结点
if(layer%layers_per_dimension==0)
{last_pos[0]=0;///x方向
last_pos[1]=0;//////y方向
last_pos[2]=0;}///z方向
else
{ last_pos[0]=ant[ant_no][layer-1][0];///x方向
last_pos[1]=ant[ant_no][layer-1][1];//////y方向
last_pos[2]=ant[ant_no][layer-1][2];}///z方向
tx=(float)rand()/RAND_MAX;///各自产生随机数
ty=(float)rand()/RAND_MAX;
tz=(float)rand()/RAND_MAX;
if ( tx<p0 )///比较随机数，确定如何移动
{
//选择具有最大信息素浓度的路径（在X方向上）
next_pos[0]=0;
for (i=1; i<10; i++)
{if (tau[layer][0][last_pos[0]][i]>tau[layer][0][last_pos[0]][next_pos[0]])
///禁忌表中第i个元素的浓度大于要选择的下一个目标i的浓度时
next_pos[0]=i;}///找到下一个目标结点
ant[ant_no][layer][0]=next_pos[0];
}
else
{
//根据pseudo-random-proportional法则随机选择一条路径
next_pos[0]=0;
tx=(float)rand()/RAND_MAX*tau[layer][0][last_pos[0]][10];
for (i=0; i<10 -1; i++) //运行到i==8,如果不满足条件则选择i==9
if(tau[layer][0][last_pos[0]][i]>tx)
break;
else
tx-=tau[layer][0][last_pos[0]][i];
ant[ant_no][layer][0]=i;
}
if ( ty<p0 )///比较随机数，确定如何移动
{ next_pos[1]=0;
for (i=1; i<10; i++) //选择具有最大信息素浓度的路径（在y方向上）
{if (tau[layer][1][last_pos[1]][i]>tau[layer][1][last_pos[1]][next_pos[1]])
next_pos[1]=i;}
ant[ant_no][layer][1]=next_pos[1];
}
else
{
next_pos[1]=0;
ty=(float)rand()/RAND_MAX*tau[layer][1][last_pos[1]][10];
for (i=0; i<10 -1; i++)
if(tau[layer][1][last_pos[1]][i]>ty)
break;
else
ty-=tau[layer][1][last_pos[1]][i];
ant[ant_no][layer][1]=i;
}
if ( tz<p0 )
{ next_pos[2]=0;
for (i=1; i<10; i++) //选择具有最大信息素浓度的路径（在z方向上）
{if (tau[layer][2][last_pos[2]][i]>tau[layer][2][last_pos[2]][next_pos[2]])
next_pos[2]=i;}
ant[ant_no][layer][2]=next_pos[2];
}
else
{
next_pos[2]=0;
tz=(float)rand()/RAND_MAX*tau[layer][2][last_pos[2]][10];
for (i=0; i<10 -1; i++)
if(tau[layer][2][last_pos[2]][i]>tz)
break;
else
tz-=tau[layer][2][last_pos[2]][i];
ant[ant_no][layer][2]=i;
}
}
void CAcs4Fun::local_update(int ant_no, int layer)///局部更新
{
double tx,ty,tz, ttx,tty,ttz;///分别在X，Y，Z三个方向上更新禁忌表
int last_pos[3], cur_pos[3];
if(layer%layers_per_dimension==0)
{ last_pos[0]=0;
last_pos[1]=0;
last_pos[2]=0;
}
else
{ last_pos[0] = ant[ant_no][layer-1][0];
last_pos[1] = ant[ant_no][layer-1][1];
last_pos[2] = ant[ant_no][layer-1][2];}
cur_pos[0] = ant[ant_no][layer][0];
cur_pos[1] = ant[ant_no][layer][1];
cur_pos[2] = ant[ant_no][layer][2];
tx = tau[layer][0][last_pos[0]][cur_pos[0]];
ty = tau[layer][1][last_pos[1]][cur_pos[1]];
tz = tau[layer][2][last_pos[2]][cur_pos[2]];
ttx=(1-rho)*tx + rho*tau0;
tty=(1-rho)*ty + rho*tau0;
ttz=(1-rho)*tz + rho*tau0;
tau[layer][0][last_pos[0]][cur_pos[0]]=ttx;
tau[layer][1][last_pos[1]][cur_pos[1]]=tty;
tau[layer][2][last_pos[2]][cur_pos[2]]=ttz;
tau[layer][0][last_pos[0]][10] += (ttx-tx);///ttx-tx现在的减去原来的等于第10个元素上的增量
tau[layer][1][last_pos[1]][10] += (tty-ty);
tau[layer][2][last_pos[2]][10] += (ttz-tz);
}
void CAcs4Fun::get_best_ant()///找到最好的蚂蚁
{
int i;
ibfit=fit[0];///ibfit暂时fit[0]
ibant_no=0;
for (i=1; i<num_ants; i++)
{
if (fit[i]<ibfit)///比ibfit小就交换，找到最小值
{
ibant_no=i;
ibfit=fit[i];
}
}
if(ibfit<gbfit)
{
for (i=0; i<num_layers; i++)///求得最好蚂蚁的X，Y，Z坐标
{gbant[i][0]=ant[ibant_no][i][0];
gbant[i][1]=ant[ibant_no][i][1];
gbant[i][2]=ant[ibant_no][i][2];}
for (i=0; i<dimension; i++)
{ gbx[i]=x[ibant_no][i];///求得全局最好的X，Y，Z坐标
gby[i]=y[ibant_no][i];
gbz[i]=z[ibant_no][i];}
gbfit=ibfit;
}
}
void CAcs4Fun::global_update()///全局更新
{
double tx,ty,tz, ttx,tty,ttz;///分别在X，Y，Z三个方向上更新禁忌表
int last_pos[3], cur_pos[3];
int i;
for (i=0; i<num_layers; i++)
{
if(i%layers_per_dimension==0)
last_pos[0]=0;
last_pos[1]=0;
last_pos[2]=0;
cur_pos[0]=gbant[i][0];
cur_pos[1]=gbant[i][1];
cur_pos[2]=gbant[i][2];
tx = tau[i][0][last_pos[0]][cur_pos[0]];
ty = tau[i][1][last_pos[1]][cur_pos[1]];
tz = tau[i][2][last_pos[2]][cur_pos[2]];
ttx=(1-alpha)*tx + alpha/gbfit;
tty=(1-alpha)*ty + alpha/gbfit;
ttz=(1-alpha)*tz + alpha/gbfit;
tau[i][0][last_pos[0]][cur_pos[0]]=ttx;
tau[i][1][last_pos[1]][cur_pos[1]]=tty;
tau[i][2][last_pos[2]][cur_pos[2]]=ttz;
tau[i][0][last_pos[0]][10] += (ttx-tx);
tau[i][1][last_pos[1]][10] += (tty-ty);
tau[i][2][last_pos[2]][10] += (ttz-tz);
last_pos[0]=cur_pos[0];
last_pos[1]=cur_pos[1];
last_pos[2]=cur_pos[2];
}
}
void CAcs4Fun::decode()///译码，将路径上的1~10转换成double型
{
int i, j, k;
for (i=0; i<num_ants; i++)
{
fit[i]=0;
for (j=0; j<dimension; j++)
{
x[i][j]=0;
y[i][j]=0;
z[i][j]=0;
for (k=0; k<layers_per_dimension; k++)
{
x[i][j]+=ant[i][j*layers_per_dimension+k][0]*pow(10,-k-1);///pow(10,-k-1)=10^(-k-1),各位位权
///if(x[i][j]>=5) x[i][j]=5;
/// if(x[i][j]<=0) x[i][j]=0;
y[i][j]+=ant[i][j*layers_per_dimension+k][1]*pow(10,-k-1);
// if(y[i][j]>=0.1) y[i][j]=5;
// if(y[i][j]<=0) y[i][j]=0;
z[i][j]+=ant[i][j*layers_per_dimension+k][2]*pow(10,-k-1);
// if(z[i][j]>=0.1) z[i][j]=5;
// if(z[i][j]<=0) z[i][j]=0;
}
}
}
}
void CAcs4Fun::evaluate()///适应度评估
{
int i, j;
for (i=0; i<num_ants; i++)
{
for (j=0; j<dimension; j++)
fit[i]=x[i][j]*x[i][j]*x[i][j]+y[i][j]*y[i][j]*y[i][j]+z[i][j]*z[i][j]*z[i][j];
}///可以变换目标函数
}
void CAcs4Fun::start()
{
int cur_layer, cur_ant;
init_vars();
for (cur_iter=0; cur_iter< num_iters; cur_iter++)
{
for (cur_layer=0; cur_layer<num_layers; cur_layer++)
{
for (cur_ant=0; cur_ant<num_ants; cur_ant++)
{
ant_move ( cur_ant, cur_layer );
local_update ( cur_ant, cur_layer );
}
}
decode();
evaluate();
get_best_ant();
global_update();
cout<<cur_iter<<" "<<gbfit<<endl;
}
}
*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。
发布文章
