populationspace.cpp

文化算法的实际应用

#include "culture.h"

namespace CAEP
{
	PopulationSpace::PopulationSpace(BeliefSpace *bs, CARandom& rnd, Configer& cfg, Result* result):
		mRandom(rnd), mConfiger(cfg),mConstraintMax(cfg.ConstraintCount),mPopulation(cfg.PopulationSize * 2)
	{
		mResult = result;
		int i, j;
		for (i = 0; i < mConfiger.PopulationSize * 2; i++) 
		{
			//do{
				mPopulation[i] = new Individual(mConfiger);
				for (j = 0; j < mConfiger.VariableCount; j++) 
				{
					mPopulation[i]->mVariables[j] = mRandom.NextFloat(bs->mLowInit[j], bs->mHighInit[j]);
				}
				//mPopulation[i]->Evaluate();
			//}while(!mPopulation[i]->mIsFeasible);
			//ShowInfo();
		}
	}

	void PopulationSpace::InitViolation()
	{
		for (int i = 0; i < mConfiger.ConstraintCount; i++) {
			mConstraintMax[i] = 0;
		}
	}

	void PopulationSpace::Evalute()
	{
		for (int i = 0; i < mConfiger.PopulationSize * 2; i++)
		{
			mPopulation[i]->Evaluate();
			mPopulation[i]->Violation(mConstraintMax);

			mResult->mEvalutionCount++;
		}
	}

	void PopulationSpace::Sort()
	{
		std::sort(mPopulation.begin(), mPopulation.begin() + mConfiger.PopulationSize);
	}

	void PopulationSpace::SortBig()
	{
		std::sort(mPopulation.begin(), mPopulation.begin() + mConfiger.PopulationSize * 2, CompareIndividualVictory());
	}

	void PopulationSpace::Select()
	{
		int c = mConfiger.PopulationSize/2;
		int i, j, idxCompare, idxMin;
		float min;
		char hasFeasible;

		//Test if there are feasibles 
//		for (i = 0; (!mPopulation[i]->mIsFeasible) || (i < 2 * mConfiger.PopulationSize); i++);
//		hasFeasible = (i < 2 * mConfiger.PopulationSize)? 1: 0;

		//compare with randomly selected c individuals and mark the victory count
		for (i = 0; i < 2 * mConfiger.PopulationSize; i++) 
		{
			mPopulation[i]->mVictoryCount = 0;
			for (j = 0; j < c; j++) {

				//Select the one to compare
				idxCompare = mRandom.NextInt(0, 2 * mConfiger.PopulationSize-2);
				idxCompare = (idxCompare == i)? idxCompare+1: idxCompare; //XZC: >= -> ==

				if ((mPopulation[i]->mIsFeasible && mPopulation[idxCompare]->mIsFeasible)) {
					if (mPopulation[i]->mValue < mPopulation[idxCompare]->mValue ) {
						mPopulation[i]->mVictoryCount++;
					}
				}
				else {
					if (!mPopulation[idxCompare]->mIsFeasible) 
					{
						if (mPopulation[i]->mIsFeasible) 
						{
							mPopulation[i]->mVictoryCount++;
						}
						else if (mPopulation[i]->mViolation < mPopulation[idxCompare]->mViolation) {
							mPopulation[i]->mVictoryCount++;
						}
						else if(mPopulation[i]->mValue < mPopulation[idxCompare]->mValue)  // XZC:
						{																   //add
							mPopulation[i]->mVictoryCount++;							   //
						}
					}
				}
			}
		}
			
		//Ensure the best one's victory count is the largest, as there may many ones' victory count == c
		for (i = 0; i < 2 * mConfiger.PopulationSize && !(mPopulation[i]->mIsFeasible); i++); ///XZC swap the place of the two tiaojian
		if (i < 2 * mConfiger.PopulationSize) 
		{
			min = mPopulation[i]->mValue ;
			idxMin = i;
			for (; i < 2 * mConfiger.PopulationSize; i++) 
			{
				if (mPopulation[i]->mIsFeasible && mPopulation[i]->mValue  < min) {
					idxMin = i;
					min = mPopulation[i]->mValue ;
				}
			}
			mPopulation[idxMin]->mVictoryCount = c + 1;
		}

		//To order descendent by count of victories
		SortBig();
	}

	void PopulationSpace::GenerateChildren(BeliefSpace* bs)
	{
		int i, j;
		float x;

		for (i = 0; i < mConfiger.PopulationSize; i++) 
		{
			for (j = 0; j < mConfiger.VariableCount; j++) 
			{
				mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = mPopulation[i]->mVariables[j];

				x = mRandom.RandomNormalDeviate();

				if (mPopulation[i]->mVariables[j] < bs->mLow[j])   //smaller than the left bander than move towards right
				{
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] += fabs(x*(bs->mHigh[j] - bs->mLow[j]));
				}
				else if (mPopulation[i]->mVariables[j] > bs->mHigh[j]) //greater than the right bander than move towards left
				{
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] -= fabs(x*(bs->mHigh[j] - bs->mLow[j]));
				}
				else if (mPopulation[i]->mCell == NULL) //mutation
				{
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] += x*(bs->mHigh[j]-bs->mLow[j]);
				}
				else if (mPopulation[i]->mCell->mCellType == NotFeasible)   //move to the area that are feasible
				{
					Move(i, j, x, bs);
				}
				else //perturb the feasible one
				{
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] += x*(mPopulation[i]->mCell->mHighNode[j] - mPopulation[i]->mCell->mLowNode[j]);
				}

				if (mPopulation[i+mConfiger.PopulationSize]->mVariables[j] > bs->mHighInit[j]) {
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = bs->mHighInit[j];
					//mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = mRandom.NextFloat(bs->mLow[j], bs->mHigh[j]);
				}
				else if (mPopulation[i+mConfiger.PopulationSize]->mVariables[j] < bs->mLowInit[j]) {
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = bs->mLowInit[j];
					//mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = mRandom.NextFloat(bs->mLow[j], bs->mHigh[j]);
				}
			}
		}
	}

	void PopulationSpace::GenerateChildren(BeliefSpace* bs,  ostream& o)
	{
		int i, j;
		float x;

		for (i = 0; i < mConfiger.PopulationSize; i++) 
		{
			for (j = 0; j < mConfiger.VariableCount; j++) 
			{
				mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = mPopulation[i]->mVariables[j];
				x = mRandom.RandomNormalDeviate();
				if (mPopulation[i]->mVariables[j] < bs->mLow[j]) {
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] += fabs(x*(bs->mHigh[j] - bs->mLow[j]));

					o<<1<<"\t"<<i<<"\t"<<j<<"\t"<<mPopulation[i+mConfiger.PopulationSize]->mVariables[j]<<endl;
				}
				else if (mPopulation[i]->mVariables[j] > bs->mHigh[j]) {
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] -= fabs(x*(bs->mHigh[j] - bs->mLow[j]));
					o<<2<<"\t"<<i<<"\t"<<j<<"\t"<<mPopulation[i+mConfiger.PopulationSize]->mVariables[j]<<endl;
				}
				else if (mPopulation[i]->mCell == NULL) {
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] += x*(bs->mHigh[j]-bs->mLow[j]);
					o<<3<<"\t"<<i<<"\t"<<"\t"<<j<<mPopulation[i+mConfiger.PopulationSize]->mVariables[j]<<endl;
				}
				else if (mPopulation[i]->mCell->mCellType == NotFeasible) {
					Move(i, j, x, bs);
					o<<4<<"\t"<<i<<"\t"<<j<<"\t"<<mPopulation[i+mConfiger.PopulationSize]->mVariables[j]<<endl;
				}
				else {
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] += x*(mPopulation[i]->mCell->mHighNode[j] - mPopulation[i]->mCell->mLowNode[j]);
					o<<5<<"\t"<<i<<"\t"<<j<<"\t"<<mPopulation[i+mConfiger.PopulationSize]->mVariables[j]<<endl;
				}

				if (mPopulation[i+mConfiger.PopulationSize]->mVariables[j] > bs->mHighInit[j]) {
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = bs->mHighInit[j];
					//mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = mRandom.NextFloat(bs->mLowInit[j], bs->mHighInit[j]);
				}
				else if (mPopulation[i+mConfiger.PopulationSize]->mVariables[j] < bs->mLowInit[j]) {
					mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = bs->mLowInit[j];
					//mPopulation[i+mConfiger.PopulationSize]->mVariables[j] = mRandom.NextFloat(bs->mLowInit[j], bs->mHighInit[j]);
				}
			}
		}
	}

	void PopulationSpace::Move(int indiv, int dim, float x, BeliefSpace* bs)
	{
		Cell *cellNear;

		cellNear = Cell::Near(SemiFeasible, mPopulation[indiv]->mCell);
		if (cellNear == NULL) 
		{
			cellNear = Cell::Near(Stranger, mPopulation[indiv]->mCell);
		}

		if (cellNear == NULL) 
		{
			mPopulation[indiv+mConfiger.PopulationSize]->mVariables[dim] += x*(bs->mHigh[dim] - bs->mLow[dim]);
		}
		else 
		{
			mPopulation[indiv+mConfiger.PopulationSize]->mVariables[dim] = x*(cellNear->mHighNode[dim] - cellNear->mLowNode[dim]) + (cellNear->mHighNode[dim] + cellNear->mLowNode[dim])/2;
		}
	}

	void PopulationSpace::FetchValue()
	{
		int i, idxMin, idxMax, count = 0;
		float min, max, sum = 0.0;

		//Feasibles solutions are preferred 
		for (i = 0; !mPopulation[i]->mIsFeasible && i < mConfiger.PopulationSize; i++);
		if (i < mConfiger.PopulationSize) 
		{
			max = min = mPopulation[i]->mValue ;
			idxMin = idxMax = i;
			for (; i < mConfiger.PopulationSize; i++) 
			{
				if (mPopulation[i]->mIsFeasible) 
				{
					if (mPopulation[i]->mValue  < min) 
					{
						idxMin = i;
						min = mPopulation[i]->mValue ;
					}

					if (mPopulation[i]->mValue  > max) 
					{
						idxMax = i;
						max = mPopulation[i]->mValue ;
					}

					sum += mPopulation[i]->mValue ;
					count++;
				}
			}
		}
		else 
		{
			max = min = mPopulation[0]->mViolation;
			idxMin = idxMax = 0;
			for (i = 0; i < mConfiger.PopulationSize; i++) {
				if (mPopulation[i]->mViolation < min) {
					idxMin = i;
					min = mPopulation[i]->mViolation;
				}
				if (mPopulation[i]->mViolation > max) {
					idxMax = i;
					max = mPopulation[i]->mViolation;
				}
				sum += mPopulation[i]->mValue ;
				count++;
			}
		}

		for(int i = 0; i < mConfiger.VariableCount; i++)
		{
			mResult->mVariables[i] = mPopulation[idxMin]->mVariables[i];
		}
		
		mResult->mBestValue = mPopulation[idxMin]->mValue;
		mResult->mIndexMax = idxMax;
		mResult->mIndexMin = idxMin;
		mResult->mAverage = sum/count;
	}

	void PopulationSpace::ShowInfo()
	{
		for(int i = 0; i < mConfiger.PopulationSize * 2; i++)
		{
			//mPopulation[i]->mIsFeasible =1;
			cout<<i<<"\tValue:\t"<<mPopulation[i]->mValue<<"\tIsFeasible:\t"<<mPopulation[i]->mIsFeasible<<"\tVCount:\t"<<mPopulation[i]->mVictoryCount<<endl;
		}
	}
	void PopulationSpace::ShowInfo(ostream &o)
	{
		for(int i = 0; i < mConfiger.PopulationSize * 2; i++)
		{
			//mPopulation[i]->mIsFeasible =1;
			o<<i<<"\tValue:\t"<<mPopulation[i]->mValue<<"\tIsFeasible:\t"<<mPopulation[i]->mIsFeasible<<"\tVCount:\t"<<mPopulation[i]->mVictoryCount<<endl;
			
			o<<"Variables:\t";
			for(int j = 0; j < mConfiger.VariableCount; j++)
			{
				o<<mPopulation[i]->mVariables[j]<<"\t";
			}
			o<<endl;

			//o<<"Comnstraints:\t";
			for(int j = 0; j < mConfiger.ConstraintCount; j++)
			{
				//o<<mPopulation[i]->mConstraints[j]<<"\t";
			}
			//o<<endl<<endl;
		}
	}
}