dpso.cpp

蚁群算法解决车辆最优路径问题

// DPSO.cpp: implementation of the DPSO class.
//
//////////////////////////////////////////////////////////////////////

#include "DPSO.h"
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "DCONVERSE.h"
#include "DPARTICLE.h"


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

DPSO::DPSO()
{
	dParticle = 0;
	PNum = 0;
	GBestIndex = 0;

	W = 1;
	C1 = 0.5;//预设值
	C2 = 0.5;

}
DPSO::DPSO(int dim, int num,int *city_root)
{
	PNum = num;
	dParticle = new DPARTICLE[PNum];
	for(int i=0; i<PNum; i++) 
		dParticle[i].SetDim(dim);
	
	GBestIndex = 0;
	W = 1;
	C1 = 0.5;
	C2 = 0.5;

	CalCity_car(city_root, dim);
}

DPSO::~DPSO()
{	
	delete []dParticle;
	dParticle = NULL;
}


void DPSO::CalCity_car(int* city_root,int dim)
{
	for (int m=0; m<dim; m++)
	{
		city_car[m] = city_root[m];
	}
}



//初始化群体
void DPSO::Initialize()
{
	if(dParticle==NULL) 
		return;
    
	int PARTICLE_NUMBER,j,k,l;
	srand((unsigned)time(NULL));
	GBestIndex = 0;
	for(PARTICLE_NUMBER=0; PARTICLE_NUMBER<PNum; PARTICLE_NUMBER++)
	{
		int max = dParticle[PARTICLE_NUMBER].Dim;
		int minmember = 1;

		for(j=0; j<dParticle[PARTICLE_NUMBER].Dim; j++)

		{
zhang:      dParticle[PARTICLE_NUMBER].X[j] =((rand() % (int)(((max) + 1) - (minmember))) + (minmember));

			for(int t=0; t<j; t++)
				if(dParticle[PARTICLE_NUMBER].X[j]==dParticle[PARTICLE_NUMBER].X[t])
					goto zhang;
				
		}
		
		for (k = 0; k<dParticle[PARTICLE_NUMBER].Dim; k++)
		{
			for (int sortnumber = 1; sortnumber <= dParticle[PARTICLE_NUMBER].Dim; sortnumber++)
			{
				if (dParticle[PARTICLE_NUMBER].X[k] == sortnumber)
				{
					dParticle[PARTICLE_NUMBER].X[k] = city_car[sortnumber - 1];
					break;
				}
			}
		}


		for (l=0; l<dParticle[PARTICLE_NUMBER].Dim; l++)
		{
			dParticle[PARTICLE_NUMBER].XBest[l] = dParticle[PARTICLE_NUMBER].X[l];
		}

		//速度初始化
		for(j=0; j<dParticle[PARTICLE_NUMBER].Dim; j++)        
		{		
			int *index = new int[dParticle[PARTICLE_NUMBER].Dim];
			for(int m=0; m<dParticle[PARTICLE_NUMBER].Dim; m++)
			{
zhang1:         index[m] = ((rand() % (int)(((dParticle[PARTICLE_NUMBER].Dim - 1) + 1) - (0))) + (0));
				for(int n=0; n<m; n++)
					if(index[m]==index[n])
						goto zhang1;
			}

			for(int p=0; p<dParticle[PARTICLE_NUMBER].Dim; p++)
				for(int q=0; q<dParticle[PARTICLE_NUMBER].Dim; q++)
				{
					if(q==index[p])
						dParticle[PARTICLE_NUMBER].V[p*dParticle[PARTICLE_NUMBER].Dim + q] = 1;
					else
						dParticle[PARTICLE_NUMBER].V[p*dParticle[PARTICLE_NUMBER].Dim + q] = 0;
				}
		    
			//6.2 zhangliyan
			delete []index;
			index = NULL;
		}

		dParticle[PARTICLE_NUMBER].Fit = GetFit(dParticle[PARTICLE_NUMBER]); //计算该微粒适合度
		dParticle[PARTICLE_NUMBER].FitBest = dParticle[PARTICLE_NUMBER].Fit; //设最优适合度初值

		if(dParticle[PARTICLE_NUMBER].Fit < dParticle[GBestIndex].Fit)
			GBestIndex = PARTICLE_NUMBER;//查找群体最优微粒
	}
}

void DPSO::CalFit()
{
	if(dParticle==NULL) 
		return;

	for(int i=0; i<PNum; i++)
		dParticle[i].Fit = GetFit(dParticle[i]);
}

void DPSO::ParticleFly()
{

	int PARTICLE_NUMBER_1,j,k;
	if(dParticle==NULL) 
		return;

	//整个群体飞向新的位置
	for(PARTICLE_NUMBER_1=0; PARTICLE_NUMBER_1<PNum; PARTICLE_NUMBER_1++)
	{
		double rc1,rc2,rw;

		srand( (unsigned)time( NULL ) );
		rc1 = rand()/(double)RAND_MAX;
		rc2 = rand()/(double)RAND_MAX;
		rw  = rand()/(double)RAND_MAX;

		int *Mp = new int[dParticle[PARTICLE_NUMBER_1].Dim*dParticle[PARTICLE_NUMBER_1].Dim]; //放pbest的矩阵；
		int *Mg = new int[dParticle[PARTICLE_NUMBER_1].Dim*dParticle[PARTICLE_NUMBER_1].Dim]; //放gbest的矩阵；

		DCONVERSE dconverse(dParticle[PARTICLE_NUMBER_1].Dim);

		dconverse.VtoM(dParticle[PARTICLE_NUMBER_1].X,dParticle[PARTICLE_NUMBER_1].XBest,dParticle[PARTICLE_NUMBER_1].Dim);
		for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)  
			for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
				Mp[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = dconverse.t[j*dParticle[PARTICLE_NUMBER_1].Dim + k];

		dconverse.VtoM(dParticle[PARTICLE_NUMBER_1].X,dParticle[GBestIndex].XBest,dParticle[PARTICLE_NUMBER_1].Dim);
		for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
			for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
				Mg[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = dconverse.t[j*dParticle[PARTICLE_NUMBER_1].Dim + k];

/*		if (rw<W)
		{
			if(rc1<C1)
			{
				dconverse.Multi(dParticle[PARTICLE_NUMBER_1].V,Mp,dParticle[PARTICLE_NUMBER_1].Dim);
				for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
					for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
						dParticle[PARTICLE_NUMBER_1].V[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = dconverse.m[j*dParticle[PARTICLE_NUMBER_1].Dim + k];
			}

			if(rc2<C2)
			{
				dconverse.Multi(dParticle[PARTICLE_NUMBER_1].V,Mg,dParticle[PARTICLE_NUMBER_1].Dim);
				for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
					for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
						dParticle[PARTICLE_NUMBER_1].V[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = dconverse.m[j*dParticle[PARTICLE_NUMBER_1].Dim + k];//公式V(i+1)=wV(i)+C1{X(pbest)-X(i)}+C2{X(gbest)-X(i)}的实现
			}
		}
		else
		{
			if (rc1<C1)
			{
				if (rc2<C2)
				{
					dconverse.Multi(Mp,Mg,dParticle[PARTICLE_NUMBER_1].Dim);
					for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
						for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
							dParticle[PARTICLE_NUMBER_1].V[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = dconverse.m[j*dParticle[PARTICLE_NUMBER_1].Dim + k];
				}
				else
				{
					for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
						for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
							dParticle[PARTICLE_NUMBER_1].V[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = Mp[j*dParticle[PARTICLE_NUMBER_1].Dim + k];

				}
			}
			else
			{
				if (rc2<C2)
				{
					for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
						for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
							dParticle[PARTICLE_NUMBER_1].V[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = Mg[j*dParticle[PARTICLE_NUMBER_1].Dim + k];
				}
			}
		}
*/
		//验证过了,进去的和出去的是一样的;
		if(rc1<C1)
		{
			dconverse.Multi(dParticle[PARTICLE_NUMBER_1].V,Mp,dParticle[PARTICLE_NUMBER_1].Dim);
			for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
				for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
					dParticle[PARTICLE_NUMBER_1].V[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = dconverse.m[j*dParticle[PARTICLE_NUMBER_1].Dim + k];
		}

		if(rc2<C2)
		{
			dconverse.Multi(dParticle[PARTICLE_NUMBER_1].V,Mg,dParticle[PARTICLE_NUMBER_1].Dim);
			for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
				for(k=0; k<dParticle[PARTICLE_NUMBER_1].Dim; k++)
					dParticle[PARTICLE_NUMBER_1].V[j*dParticle[PARTICLE_NUMBER_1].Dim + k] = dconverse.m[j*dParticle[PARTICLE_NUMBER_1].Dim + k];//公式V(i+1)=wV(i)+C1{X(pbest)-X(i)}+C2{X(gbest)-X(i)}的实现
		}

		dconverse.XandV(dParticle[PARTICLE_NUMBER_1].X,dParticle[PARTICLE_NUMBER_1].V,dParticle[PARTICLE_NUMBER_1].Dim);
		for(j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
			dParticle[PARTICLE_NUMBER_1].X[j] = dconverse.x[j]; 
	//6.2 zhangliyan
	delete []Mp;
	Mp = NULL;
	delete []Mg;
	Mg = NULL;
	}

	//计算各微粒适合度
	CalFit();

	for(PARTICLE_NUMBER_1=0; PARTICLE_NUMBER_1<PNum; PARTICLE_NUMBER_1++)
		if(dParticle[PARTICLE_NUMBER_1].Fit<=dParticle[PARTICLE_NUMBER_1].FitBest)
		{
			dParticle[PARTICLE_NUMBER_1].FitBest = dParticle[PARTICLE_NUMBER_1].Fit;
			for(int j=0; j<dParticle[PARTICLE_NUMBER_1].Dim; j++)
				dParticle[PARTICLE_NUMBER_1].XBest[j] = dParticle[PARTICLE_NUMBER_1].X[j];
		}

	//设置新的最优个体
	for(PARTICLE_NUMBER_1=0; PARTICLE_NUMBER_1<PNum; PARTICLE_NUMBER_1++)
		if(dParticle[PARTICLE_NUMBER_1].FitBest<=dParticle[GBestIndex].FitBest && PARTICLE_NUMBER_1!=GBestIndex) 
			GBestIndex = PARTICLE_NUMBER_1;
			
}

DPSO::Run(int n)
{
	Initialize();

	for(int RUN_TIME=0; RUN_TIME<n; RUN_TIME++)
	{
		ParticleFly();
	}
}

double DPSO::GetBest()
{
	return dParticle[GBestIndex].FitBest;
}

int DPSO::GetGBestIndex()
{
	return GBestIndex;
}

int DPSO::GetGXBest(int k)
{
	return dParticle[GBestIndex].XBest[k];
}