i-ant.cpp

采用了基本的蚁群算法来求解0-1背包问题

/*********** 蚁群算法-背包问题 ***********
 ***********        ***********
***********     Department of Automation,     ***********
 *****East China University of Science and Technology**********
***********     ***********/

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;

/*definition of user data */
#define M 20//蚂蚁数目
#define LENGTH 20//物品数目
int MaxGeneration=10;    //最大迭代次数
double rou=0.1; //蒸发系数
double Q=1000;
double tau[LENGTH];//每个物品对应的信息素
double enta[LENGTH];//每个物品的启发式因子
double a[LENGTH]={92, 4, 43, 83, 84, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58};
double c[LENGTH]={44, 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63};
int b=878;

/* definition of data structure */
struct individual//个体结构
{
int X[LENGTH];
int value;
int weight;
};

/* definition of global variables */
int generation;//代数
struct individual currentbest;
struct individual historybest;
struct individual Ant[M];

/* function prototype */
void Initial();
void Choosebag();
void Calculate();
void Refresh();
void FindBest();
void OutputResult();

int main()
{
	srand(static_cast<unsigned>(time(static_cast<time_t *>(NULL))));
	generation=0;
    Initial();
	while(generation<MaxGeneration)
	{
     generation++;
	 Choosebag();
	 Calculate();
     Refresh();
     FindBest();
     OutputResult();
	}
return 0;
}

void Initial()
{
    for(int j=0;j<LENGTH;j++)
	{tau[j]=0.2;}
	for(int h=0;h<LENGTH;h++)
	enta[h]=static_cast<double>(c[h]/a[h]);
}

void Choosebag()
{
	int i,j,index;
	for(i=0;i<M;i++)
	{
		Ant[i].weight=0;
		Ant[i].value=0;
		for(j=0;j<LENGTH;j++)
			Ant[i].X[j]=0;
	}

	double r;
	double sum=0.0;
    double P[LENGTH],Q[LENGTH];
	bool y=false;
    for(i=0;i<LENGTH;i++)
	{
    sum+=tau[i]*enta[i];	
	}
    for(i=0;i<LENGTH;i++)
	{
    P[i]=(tau[i]*enta[i])/sum;
	}
    Q[0]=P[0];
    for(i=1;i<LENGTH;i++)
	{
     Q[i]=Q[i-1]+P[i];
	}

for(i=0;i<M;i++)
{
for(j=0;j<LENGTH;j++)
{
    if(j==0)
	{
    r=static_cast<double>(rand()/double(RAND_MAX+1));
	index=0;	
	while(r>Q[index])
	{index++;}
	Ant[i].X[j]=index+1;
	Ant[i].weight+=a[index];
	}
	else 
	{  
		 while(y==false)
		 {     
			   r=rand()/double(RAND_MAX+1);
               index=0;
               while(r>Q[index])
			   {index++;}

               for(int m=j-1;m>=0;m--)
			   {  
				      if(index==(Ant[i].X[m]-1))
					  {       
                       m=-1;
					   y=false;
					  }
                      else
					   y=true;
			   }
		 }
           y=false;
		   if((Ant[i].weight+a[index])<=b)
		   {Ant[i].X[j]=index+1; Ant[i].weight+=a[index];}
		   else break;
		
	}
}
}

}

void Calculate()
{
	int i,j;
	for(i=0;i<M;i++)
	{
		Ant[i].value=0;
		for(j=0;j<LENGTH;j++)
		{
			if(Ant[i].X[j]!=0)
			Ant[i].value+=c[Ant[i].X[j]-1];
			else
			Ant[i].value+=0;
		}
	}
}

void Refresh()
{
	int i,j,h;
	double dtau[LENGTH];
    for(j=0;j<LENGTH;j++)
    dtau[j]=0;
	for(j=0;j<LENGTH;j++)
	{
		for(i=0;i<M;i++)
		{
			for(h=0;h<LENGTH;h++)
			{
				if(Ant[i].X[h]==j+1)
				dtau[j]+=Ant[i].value/Q;
			}
		}
		tau[j]=(1-rou)*tau[j]+dtau[j];
	}

}

void FindBest()
{
	int i;
currentbest=Ant[0];
for(i=1;i<M;i++)
{
	if(Ant[i].value>currentbest.value)
   {currentbest=Ant[i];}
}
if(generation==0)
{
	historybest=currentbest;
}
else
{
  if(currentbest.value>=historybest.value)
  {historybest=currentbest;}
}
}

void OutputResult()
{
int i;
cout<<"gen="<<generation<<"  "<<"BestValue="<<historybest.value<<endl;
cout<<"Best=[";
for(i=0;i<LENGTH;i++)
  {cout<<historybest.X[i]<<" ";}
cout<<"]"<<endl;
}