cacs4fun.cpp

该压缩包有文档和代码

////////////////////////////////////////////////////////////////////////
//  Class Name: Ant Colony System for Function Optimization           //
//  Version:    0.1                                                   //
//  Author:     Chen Ye (Sichuan University)                          //
//  E-mail:     [e-mail], [e-mail]                   //
//  Blog:       http://www.mscenter.edu.cn/blog/chenye                //
//  Date:       2006-07-01                                            //
////////////////////////////////////////////////////////////////////////

#include "CACS4Fun.h"
#include <cstdlib>
#include <cmath>
#include <iostream.h>

CAcs4Fun::CAcs4Fun()
{
	need_release=false;			//indicate that memory hasn't been allocated
								//and needs release operation
}

CAcs4Fun::~CAcs4Fun()
{
	if(need_release)
		release_vars();
}

void CAcs4Fun::release_vars()
{
	int i,j;

	for (i=0; i<num_layers; i++)
	{
		for (j=0; j<10; j++)
			delete[] tau[i][j];
		delete[] tau[i];
	}
	delete[] tau;

	for (i=0; i<num_ants; i++)
		delete[] ant[i];
	delete[] ant;

	for (i=0; i<num_ants; i++)
		delete[] x[i];
	delete[] x;
	delete[] gbx;

	delete[] fit;
	delete[] y;
	delete[] gbant;
	delete[] ibant;

	need_release=false;
}

void CAcs4Fun::allocate_vars()
{
	int i, j;

	if(need_release==true)
		release_vars();
	//allocate memory for variables
	//float ***tau;
	tau=new float**[num_layers];
	for (i=0; i<num_layers; i++)
	{
		tau[i]=new float*[10];
		for (j=0; j<10; j++)		
			tau[i][j]=new float[10 +1];	//the last element is used to store the accumulate value of the foregoing 10 numbers
	}

	//int **ant;
	ant=new int*[num_ants];
	for (i=0; i<num_ants; i++)
		ant[i]=new int[num_layers];

	//float *fit;
	fit=new float[num_ants];

	//float *y;
	y=new float[num_ants];

	//int *gbant;
	gbant=new int[num_layers];

	//int *ibant;
	ibant=new int[num_layers];

	//float **x;
	x=new float*[num_ants];
	for (i=0; i<num_ants; i++)
		x[i]=new float[dimension];

	//float *gbx;
	gbx=new float[dimension];

	need_release=true;
	layers_per_dimension=num_layers/dimension;
}

void CAcs4Fun::init_vars()
{
	int i, j, k;
	//init variables for global best ant
	gbfit=100000;
	gby=0;

	//init tau
	for (i=0; i<num_layers; i++)
	{
		for (j=0; j<10; j++)
		{
			for (k=0; k<10; k++)
				tau[i][j][k]=tau0;
			tau[i][j][10]=tau0*10;
		}
	}
}

void CAcs4Fun::ant_move(int ant_no, int layer)
{
	int last_pos, next_pos;
	int i;
	float t;

	//last_pos stands for the node number of the ant chooses in the last move
	//and it will be 0 for the first move of each dimension of variable
	if(layer%layers_per_dimension==0)   //即当前如果是最后一层
		last_pos=0;						//蚂蚁在最后一步选择中的结点为0
	else								//last_pos为当前所选择的最后一步
		last_pos=ant[ant_no][layer-1];  //当前蚂蚁在前一层中所选择的数
	t=(float)rand()/RAND_MAX;
	if ( t<p0 )   //小于某一个概率则用信息素浓度作为移动的标准
	{
		//select a path with maximum pheromone
		next_pos=0;
		for (i=1; i<10; i++)
			if (tau[layer][last_pos][i]>tau[layer][last_pos][next_pos])//当前层中前一个位置为last_pos的蚂蚁在当前层寻找信息素浓度最大的路径
				next_pos=i;//next_pos为一个值，该值为本次移动中蚂蚁根据信息素浓度最大值所找到的移动位置
		ant[ant_no][layer]=next_pos;//将蚂蚁移动到本次所选择的位置
	}
	else//当概率大于一定值时，根据各个结点的移动概率来选择将要移动到的位置
	{
		//select a path randomly according to pseudo-random-proportional rule，根据pseudo的随机概率规则随机选择一个路径
		next_pos=0;
		t=(float)rand()/RAND_MAX*tau[layer][last_pos][10];
		for (i=0; i<10 -1; i++)		//the for statement just need to run till i==8, as i==9 is the last choise
			if(tau[layer][last_pos][i]>t)
				break;
			else
				t-=tau[layer][last_pos][i];//根据罗盘原则选择将要移动到的下一层中的位置
		ant[ant_no][layer]=i;//移动蚂蚁至当前层
	}
}

void CAcs4Fun::local_update(int ant_no, int layer)//每移动完一次，就要进行一次信息素的调整
{
	float t, tt;
	int last_pos, cur_pos;
	//last_pos为蚂蚁上一次移动中所选择的结点，当它为变量每维的第一次移动时值为0
	//last_pos stands for the node number of the ant chooses in the last move
	//and it will be 0 for the first move of each dimension of variable
	if(layer%layers_per_dimension==0)
		last_pos=0;
	else
		last_pos = ant[ant_no][layer-1];
	cur_pos = ant[ant_no][layer];

	t = tau[layer][last_pos][cur_pos];//t赋值为当前层中刚选择到的路径的信息素的浓度
	tt=(1-rho)*t + rho*tau0;//tt为更新的信息素的浓度值
	tau[layer][last_pos][cur_pos]=tt;//将当前层所选路径的信息素浓度调整为更新值
	tau[layer][last_pos][10] += (tt-t);//当前层的最后一个元素位置存放的是当前层的信息素浓度总和
}

void CAcs4Fun::get_best_ant()//寻求最优蚂蚁
{
	int i;

	ibfit=fit[0];//设置个体最优适应度初值为fit[0]
	ibant_no=0;
	for (i=1; i<num_ants; i++)
	{   
		//求适应读最小的蚂蚁
		if (fit[i]<ibfit)
		{
			ibant_no=i;//将适应度小原记录的蚂蚁记为当前最优蚂蚁
			ibfit=fit[i];//个体最优适应度取适应度值最小的
		}
	}
	//本次局部适应度如果小于全局适应度，则改写全局最小适应度
	if(ibfit<gbfit)//如果局部最优适应度小于全局最优适应度，则将全局的各个值用当前局部最优值替代
	{
		for (i=0; i<num_layers; i++)
			gbant[i]=ant[ibant_no][i];//全局最优蚁的各个层的值为当前最优蚁的各个层值
		for (i=0; i<dimension; i++)
			gbx[i]=x[ibant_no][i];//全局最优蚂蚁的变量值为当前最优蚂蚁的变量值
		gbfit=ibfit;//设置全局最优蚂蚁的适应度为当前最优蚂蚁的适应度
	}
}

void CAcs4Fun::global_update()//全局优化
{
	float t, tt;
	int i;
	int last_pos, cur_pos;

	for (i=0; i<num_layers; i++)
	{
		//last_pos stands for the node number of the ant chooses in the last move
		//and it will be 0 for the first move of each dimension of variable
		if(i%layers_per_dimension==0)//当每个变量结束时，设置蚂蚁所在的最后位置
			last_pos=0;
		cur_pos=gbant[i];
		t  = tau[i][last_pos][cur_pos];//t为蚂蚁i当前的信息素浓度
		tt=(1-alpha)*t + alpha/gbfit;//计算信息度的更新值
		tau[i][last_pos][cur_pos]=tt;//将信息素浓度设置为更新后的信息素浓度
		tau[i][last_pos][10] += (tt-t);//在当前层的最后一个位置记录当前层的信息素浓度总和
		last_pos=cur_pos;//位置向后移一位
	}
}

void CAcs4Fun::decode()
{
	int i, j, k;
	//float x[300];

	for (i=0; i<num_ants; i++)
	{
		//fit[i]=0;？？？？？？？？？？
		for (j=0; j<dimension; j++)
		{
			x[i][j]=0;
			for (k=0; k<layers_per_dimension; k++)
			{
				x[i][j]+=ant[i][j*layers_per_dimension+k]*pow(10,-k-1);//x[i][j]表示第i只蚂蚁的第j个变量的值
																		//这里ant[i][j*layers_per_dimension+k]*pow(10,-k-1)
																		//是计算蚂蚁i的变量j的各个小数点位的值
																		//总体通过双层循环得到蚂蚁i的各个变量的值
			}
			//fit[i]+=x[j]*x[j]*100;
		}
	}
}

void CAcs4Fun::evaluate()
{
	int i, j;
	for (i=0; i<num_ants; i++)
	{
		//fit[i]=1-fabs((1-x[i][0])*x[i][0]*x[i][0]*sin(200*3.14159265*x[i][0]));
		for (j=0; j<dimension; j++)	//SphereModel, x belongs to (-5, 5]
			fit[i]+=(0.5-x[i][j])*(0.5-x[i][j])*100;//？？？？？？？？？？？/
		
	}
}

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;//打印当前的迭代数和全局最佳适应值
	}
}