acs.cpp

实现通用的matlab蚁群算法的c++源码 重复使用度高

//--------编于2008年1月,裴曦-------------------------------------------------------
//--------由于只是测试算法的性能,故难免存在缺陷,望见谅!----------------------------



#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h> 
#include <math.h>
#include <stdio.h> 
#include <conio.h>

int n;  //变量个数
int nc_max;  //迭代次数
int m;  //蚂蚁个数
int d;  //同构到小数点后d位的0～1之间的小数
float rho;  //信息素挥发系数
const int tao=1;   //信息素增加量



void main()
{
	double f(double *x);
	FILE *fp;
	int l,i,j,k,r;
	int **tabu;  //[m][n*d]的矩阵，用来存放每次迭代的路径
	int nc=0;  //计数器，用来记录迭代次数
	double p[10],P,t,pcum[10];
	double **tau; //[10][n*(1+10*(d-1))]的矩阵，用来存放每条路径的信息素
	double **r_best; //[nc_max][n]的矩阵，用来存放每次迭代的最优解
	double *MinMax; //[2*n]的数组，里面依次是每个变量的最小值和最大值
	double **dest; //[m][n]的矩阵，用来存放每次迭代所有蚂蚁的路径值
	
//==========读入文件info.txt＝＝＝＝＝＝＝＝＝＝＝＝
	fp=fopen("info.txt","r");
	if(fp==NULL)
	{
    	cout<<"cannot open the file!"<<endl;
    	return;
	}
	fscanf(fp,"%d",&n);
	if(n<0||n==0)
	{
		cout<<"n can not be a minus or zero"<<endl;
		return;
	}
	MinMax=new double[2*n];
	fscanf(fp,"%d",&d);
	if(d<0||d==0)
	{
		cout<<"d can not be a minus or zero"<<endl;
		return;
	}
	fscanf(fp,"%d",&nc_max);
	fscanf(fp,"%d",&m);
	fscanf(fp,"%f",&rho);
	j=0;
	for(i=0;i<2*n;i++)
	{
		if(!feof(fp))
		{
			fscanf(fp,"%lf",&MinMax[i]);
			j++;
		}
	}
	if(j!=2*n)
	{	
		cout<<"the number of MinMax is error"<<endl;
		return;
	}
	fclose(fp);
//=================================================
	tau=new double*[10];
	for(i=0;i<10;i++)
		tau[i]=new double[n*(1+10*(d-1))];
	tabu=new int*[m];
	for(i=0;i<m;i++)
		tabu[i]=new int[n*d];
	r_best=new double*[nc_max];
	for(i=0;i<nc_max;i++)
		r_best[i]=new double[n];
	for(i=0;i<10;i++)
		for(j=0;j<n*(1+10*(d-1));j++)
			tau[i][j]=1;
	dest=new double*[m];
	for(i=0;i<m;i++)
		dest[i]=new double[n];	
//==================循环开始===================================
	while(nc<nc_max)
	{
		for(r=0;r<n*d;r++)
			for(j=0;j<m;j++)
			{
				if(r%d==0)
				{
					//======当起始点为原点时，按概率选择0~9中的一个数＝＝＝＝＝＝＝＝＝
					P=0;
					for(k=0;k<10;k++)
					{
						P=P+tau[k][r];
					}
					for(k=0;k<10;k++)
						p[k]=tau[k][r];
					for(k=0;k<10;k++)
						p[k]=p[k]/P;
					for(k=0;k<10;k++)
					{
						t=0.0;
						for(i=0;i<=k;i++)
						{
							t=t+p[i];
						}
						pcum[k]=t;
					}
					k=(rand()%9999);
					t=k/9999.0;//产生一个0~1的随机数
					for(k=0;k<10;k++)
					{
						if(t<pcum[k])
						{
							l=k;
							break;
						}
					}
					//===============================================================
					tabu[j][r]=l;//把走过的路径放到矩阵中
					tau[l][(10*(d-1)+1)*r/d]=tau[l][(10*(d-1)+1)*r/d]+tao;//局部更新
				}
				else
				{
					//==========当路径起始点不是原点时=========================
					l=tabu[j][r-1];
					P=0;
					for(k=0;k<10;k++)
					{
						P=P+tau[l][k+(r-r/d-1)*10+r/d+1];
					}
					for(k=0;k<10;k++)
						p[k]=tau[l][k+(r-r/d-1)*10+r/d+1];
					for(k=0;k<10;k++)
						p[k]=p[k]/P;
					for(k=0;k<10;k++)
					{
						t=0.0;
						for(i=0;i<=k;i++)
						{
							t=t+p[i];
						}
						pcum[k]=t;
					}
					k=(rand()%9999);
					t=k/9999.0;//产生一个0~1的随机数
					for(k=0;k<10;k++)
					{
						if(t<pcum[k])
						{
							l=k;
							break;
						}
					}
					tabu[j][r]=l;//把走过的路径放到矩阵中
					tau[tabu[j][r-1]][(r-r/d-1)*10+r/d+1+l]=tau[tabu[j][r-1]][(r-r/d-1)*10+r/d+1+l]+tao;//局部更新
				}
			}
			t=999999999;
			//==========找出本次迭代的最优路径==============
			for(k=0;k<m;k++)
			{
				for(j=0;j<n;j++)
				{
					P=0;
					for(i=j*d;i<(j+1)*d;i++)
					{
						if(j==0)
							P=P+tabu[k][i]*pow(10,-(i+1));
						else
							P=P+tabu[k][i]*pow(10,-(i%(j*d)+1));
					}
					dest[k][j]=P;
				}
				for(j=0;j<n;j++)
					dest[k][j]=MinMax[2*j]+(MinMax[2*j+1]-MinMax[2*j])*dest[k][j];
				//＝＝＝如果不是2维函数，这里是要改动的，因为参数变化了＝＝＝＝＝＝＝＝＝＝
				if(t>f(dest[k]))
				{
					t=f(dest[k]);
					l=k;//用l记录最佳路径，t记录最佳函数值
				}
			}
			//================================================
			for(k=0;k<10;k++)
				for(i=0;i<n*(1+10*(d-1));i++)
					tau[k][i]=(1-rho)*tau[k][i];
			for(k=0;k<n*d;k++)
			{//全局信息素更新
				if(k%d==0)
				{
					tau[tabu[l][k]][((d-1)*10+1)*(k/d)]=tau[tabu[l][k]][((d-1)*10+1)*(k/d)]+tao;
				}
				else
				{
					tau[tabu[l][k-1]][(r-r/d-1)*10+r/d+tabu[l][k]+1]=tau[tabu[l][k-1]][(r-r/d-1)*10+r/d+1+tabu[l][k]]+tao;
				}
			}
			if(nc!=0&&t<f(r_best[nc-1]))
			{//让r_best保留到当前为止最优解
				for(k=0;k<n;k++)
					r_best[nc][k]=dest[l][k];
			}
			else if(nc==0)
			{
				for(k=0;k<n;k++)
					r_best[nc][k]=dest[l][k];
			}				
			else
			{
				for(k=0;k<n;k++)
					r_best[nc][k]=r_best[nc-1][k];
			}
			nc++;
	}
//==================循环结束===============================================
//==================输出结果===============================================
    fp=fopen("result.txt","w+");
	fprintf(fp,"自变量取值：");
	for(i=0;i<n;i++)
	{
		fprintf(fp,"%lf  ",r_best[nc_max-1][i]);
	}
	fprintf(fp,"\n函数值：");
	fprintf(fp,"%lf",f(r_best[nc_max-1]));
}



//＝＝＝＝＝＝定义的优化函数＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
double f(double *x)
{
	return (4-2.1*pow(x[0],2)+pow(x[0],4)/3)*pow(x[0],2)+x[0]*x[1]+(-4+4*pow(x[1],2))*pow(x[1],2);	
}
//==========================================================================