beliefspace.cpp

文化算法的实际应用

#include <limits>
#include "culture.h"
namespace CAEP
{
	BeliefSpace::BeliefSpace(CARandom& rnd, Configer& cfg):mRandom(rnd), mConfiger(cfg), mLow(cfg.VariableCount),mHigh(cfg.VariableCount),mLowValue(cfg.VariableCount),mHighValue(cfg.VariableCount),mLowInit(cfg.VariableCount),mHighInit(cfg.VariableCount)
	{
		vector<float> low(mConfiger.VariableCount), high(mConfiger.VariableCount);
		Individual::Limit(low, high);
		for (int i = 0; i < mConfiger.VariableCount; i++) 
		{		
			mLowValue[i] = mHighValue[i] = numeric_limits<float>::max();;
			mLow[i] = mHighInit[i] = low[i];
			mHigh[i] = mHighInit[i] = high[i];
		}

		mRoot = new Cell(mConfiger);
		mRoot->mFather = NULL;
		mRoot->mSon[0] = NULL;
	}

	BeliefSpace::~BeliefSpace()
	{
		delete mRoot;
	}

	void BeliefSpace::Update(PopulationSpace *ps, int currentGeneration)
	{
		int i, j, dim, numSon, sumWalk, cell, k = 20;
		float max, min;
		Cell *nodeAct;

		// It decides whether to update the normative part
		if (currentGeneration % k == 0) 
		{
			Accept(ps);

			int idxMin, idxMax;
			for (i = 0; i < mConfiger.VariableCount; i++) 
			{
				idxMax = idxMin = 0;
				max = min = ps->mPopulation[0]->mVariables[i];

				//Cycle to find the high and low values of each Varialbes
				for (j = 1; j < mConfiger.TopCount; j++) 
				{
					if (ps->mPopulation[j]->mVariables[i] < min)  ///XZC:Whether to check thme feasible?
					{
						idxMin = j;
						min = ps->mPopulation[j]->mVariables[i];
					}
					if (ps->mPopulation[j]->mVariables[i] > max) 
					{
						idxMax = j;
						max = ps->mPopulation[j]->mVariables[i];
					}
				}

				//if min than expand,else if it has a good result and it is feasible than tight
				if ( (min < mLow[i]) || (ps->mPopulation[idxMin]->mValue < mLowValue[i] && ps->mPopulation[idxMin]->mIsFeasible) ) 
				{
					if (min < mHigh[i]) 
					{
						mLow[i] = min;
						mLowValue[i] = ps->mPopulation[idxMin]->mValue ;
					}
				}
				if ( (max > mHigh[i]) || (ps->mPopulation[idxMax]->mValue < mHighValue[i] && ps->mPopulation[idxMax]->mIsFeasible) ) 
				{
					if (max > mLow[i]) 
					{
						mHigh[i] = max;
						mHighValue[i] = ps->mPopulation[idxMax]->mValue ;
					}
				}
			}

			//creates new Cell for new intervals
			Expand(mRoot, ps);
		}

		//Update the part of restrictions  
		//  Associating to each individual one with node that contains it 
		for (i = 0; i < mConfiger.PopulationSize; i++) 
		{
			numSon = 0;
			// Cycle to verify that the individual one is within the intervals of the normative part
			for (j = 0; j < mConfiger.VariableCount; j++) {
				if (ps->mPopulation[i]->mVariables[j] < mLow[j] ||
					ps->mPopulation[i]->mVariables[j] > mHigh[j]) 
				{
					numSon = -1;
					break;
				}
			}
			if (numSon == -1) 
			{
				ps->mPopulation[i]->mCell = NULL;
				continue;
			}

			for (nodeAct = mRoot; nodeAct->mDimension[0] != -1; nodeAct = nodeAct->mSon[numSon]) 
			{
				numSon = 0;
				sumWalk = 1;
				for (j = 0; j < mConfiger.TreeDim; j++) 
				{
					dim = nodeAct->mDimension[j];
					if (ps->mPopulation[i]->mVariables[dim] > (nodeAct->mLowNode[dim] + nodeAct->mHighNode[dim])/2) 
					{
						numSon += sumWalk;
					}
					sumWalk += sumWalk;
				}
			}
			ps->mPopulation[i]->mCell =  nodeAct;

			if (ps->mPopulation[i]->mIsFeasible) 
			{
				ps->mPopulation[i]->mCell->mFeasibleCount++;
				if (ps->mPopulation[i]->mCell->mFeasibleCount == 1)
				{
					if (ps->mPopulation[i]->mCell->mUnFeasibleCount == 0)
					{
						ps->mPopulation[i]->mCell->mCellType = Feasible;
					}
					else 
					{
						ps->mPopulation[i]->mCell->mCellType = SemiFeasible;
						if (ps->mPopulation[i]->mCell->mDepth > 1) 
						{
							Expand(ps->mPopulation[i]->mCell, ps);
							i = -1;
							continue;
						}
					}
				}
			}
			else {
				ps->mPopulation[i]->mCell->mUnFeasibleCount++;
				if (ps->mPopulation[i]->mCell->mUnFeasibleCount == 1) 
				{
					if (ps->mPopulation[i]->mCell->mFeasibleCount == 0) 
					{
						ps->mPopulation[i]->mCell->mCellType = NotFeasible;
					}
					else {
						ps->mPopulation[i]->mCell->mCellType = SemiFeasible;
						if (ps->mPopulation[i]->mCell->mDepth > 1) 
						{
							Expand(ps->mPopulation[i]->mCell, ps);
							i = -1;
							continue;
						}
					}
				}
			}
		}
	}

	void BeliefSpace::Expand(Cell* nodeAct, PopulationSpace *ps)
	{
		int i, j, numTree, numSon, sumWalk, dim, min;
		C2DVector<int> sumMin(mConfiger.TestTreeCount, mConfiger.TreeDim + 1);
		float tmp;

		//create and init the children
		if (nodeAct->mSon[0] == NULL) 
		{
			for (i = 0; i < mConfiger.TreeNodeCount; i++) 
			{
				nodeAct->mSon[i] = new Cell(mConfiger);
				nodeAct->mSon[i]->mFather = nodeAct;
				nodeAct->mSon[i]->mSon[0] = NULL;
			}
		}
		for (i = 0; i < mConfiger.TreeNodeCount; i++) 
		{
			nodeAct->mSon[i]->mDimension[0] = -1;
		}

			
		//If mFather is NULL, their intervals are those of the normative part 	
		if (nodeAct->mFather == NULL) {
			for (i = 0; i < mConfiger.VariableCount; i++) 
			{
				nodeAct->mLowNode[i] = mLow[i];
				nodeAct->mHighNode[i] = mHigh[i];
			}
		}

		if (mConfiger.VariableCount > mConfiger.TreeDim) 
		{
			for (numTree = 0; numTree < mConfiger.TestTreeCount; numTree++) 
			{
				//Reinitiation of the counts of feasibles individuals of the children 
				for (i = 0; i < mConfiger.TreeNodeCount; i++) 
				{
					nodeAct->mSon[i]->mFeasibleCount = 0;
					nodeAct->mSon[i]->mUnFeasibleCount = 0;
				}

				// Election of the dimensions to particionar at random
				sumMin[numTree][1] = mRandom.NextInt(3, mConfiger.VariableCount-1);  //XZC: 0 -> 3 as 3 seems the best
				sumMin[numTree][2] = mRandom.NextInt(3, mConfiger.VariableCount-2);
				sumMin[numTree][3] = mRandom.NextInt(3, mConfiger.VariableCount-3);

				//printf("%d %d %d\n",sumMin[numTree][1],sumMin[numTree][2],sumMin[numTree][3]);
				
				if (sumMin[numTree][2] == sumMin[numTree][1]) 
				{   ///XZC: >= -> ==  ??
					sumMin[numTree][2]++;
					if (sumMin[numTree][3] == sumMin[numTree][1]) 
					{
						sumMin[numTree][3]++;
					}
					if (sumMin[numTree][3] == sumMin[numTree][2]) 
					{
						sumMin[numTree][3]++;
					}
				}
				else {
					if (sumMin[numTree][3] == sumMin[numTree][2]) 
					{
						sumMin[numTree][3]++;
					}
					if (sumMin[numTree][3] == sumMin[numTree][1]) 
					{
						sumMin[numTree][3]++;
					}
				}
				//printf("%d %d %d\n\n",sumMin[numTree][1],sumMin[numTree][2],sumMin[numTree][3]);

				for (i = 0; i < mConfiger.PopulationSize; i++) 
				{
					numSon = 0;
					for (j = 0; j < mConfiger.VariableCount; j++) 
					{
						if (ps->mPopulation[i]->mVariables[j] < nodeAct->mLowNode[j] ||
							ps->mPopulation[i]->mVariables[j] > nodeAct->mHighNode[j]) 
						{
							numSon = -1;
							break;
						}
					}
					if (numSon == -1) 
					{
						continue;
					}

					sumWalk = 1;
					for (j = 0; j < mConfiger.TreeDim; j++) 
					{
						dim = sumMin[numTree][j + 1];
						if (ps->mPopulation[i]->mVariables[dim] > (nodeAct->mLowNode[dim] + nodeAct->mHighNode[dim])/2) 
						{
							numSon += sumWalk;
						}
						sumWalk += sumWalk;
					}
					if (ps->mPopulation[i]->mIsFeasible) 
					{
						nodeAct->mSon[numSon]->mFeasibleCount++;
					}
					else 
					{
						nodeAct->mSon[numSon]->mUnFeasibleCount++;
					}
				}

				sumMin[numTree][0] = 0;
				for (i = 0; i < mConfiger.TreeNodeCount; i++)
				{
					sumMin[numTree][0] += (nodeAct->mSon[i]->mFeasibleCount < nodeAct->mSon[i]->mUnFeasibleCount)? nodeAct->mSon[i]->mFeasibleCount: nodeAct->mSon[i]->mUnFeasibleCount;
				}
			}
			min = sumMin[0][0];
			numTree = 0;
			for (i = 1; i < mConfiger.TestTreeCount; i++)
			{
				if (sumMin[i][0] < min)
				{
					min = sumMin[i][0];
					numTree = i;
				}
			}
			
			for (i = 0; i < mConfiger.TreeDim; i++)
			{
				nodeAct->mDimension[i] = sumMin[numTree][i + 1];
			}
		}

		else {
			for (i = 0; i < mConfiger.VariableCount; i++)
			{
				nodeAct->mDimension[i] = i;
			}
		}

		for (i = 0; i < mConfiger.PopulationSize; i++) 
		{
			numSon = 0;
			for (j = 0; j < mConfiger.VariableCount; j++) 
			{
				if (ps->mPopulation[i]->mVariables[j] < nodeAct->mLowNode[j] ||
					ps->mPopulation[i]->mVariables[j] > nodeAct->mHighNode[j])
				{
					numSon = -1;
					break;
				}
			}
			if (numSon == -1) 
			{
				continue;
			}
			sumWalk = 1;
			for (j = 0; j < mConfiger.TreeDim; j++) 
			{
				dim = nodeAct->mDimension[j];
				if (ps->mPopulation[i]->mVariables[dim] > (nodeAct->mLowNode[dim] + nodeAct->mHighNode[dim])/2) {
					numSon += sumWalk;
				}
				sumWalk += sumWalk;
			}
			if (ps->mPopulation[i]->mIsFeasible)
			{
				nodeAct->mSon[numSon]->mFeasibleCount++;
			}
			else {
				nodeAct->mSon[numSon]->mUnFeasibleCount++;
			}
		}

		/* Allocation of the intervals to each cell  */
		for (i = 0; i < mConfiger.TreeNodeCount; i++) 
		{
			for (j = 0; j < mConfiger.VariableCount; j++) 
			{
				nodeAct->mSon[i]->mLowNode[j] = nodeAct->mLowNode[j];
				nodeAct->mSon[i]->mHighNode[j] = nodeAct->mHighNode[j];
			}
			numSon = i;
			sumWalk = 1;
			for (j = 0; j < mConfiger.TreeDim; j++) 
			{
				tmp = (nodeAct->mLowNode[nodeAct->mDimension[j]] + nodeAct->mHighNode[nodeAct->mDimension[j]]) / 2;
				if (numSon % (2*sumWalk)) 
				{
					nodeAct->mSon[i]->mLowNode[nodeAct->mDimension[j]] = tmp;
					numSon -= sumWalk;
				}
				else
				{
					nodeAct->mSon[i]->mHighNode[nodeAct->mDimension[j]] = tmp;
				}
				sumWalk += sumWalk;
			}
		}

		/* Allocation of mCellType to cell  */
		for (i = 0; i < mConfiger.TreeNodeCount; i++) 
		{
			if (nodeAct->mSon[i]->mFeasibleCount > 0)
			{
				if (nodeAct->mSon[i]->mUnFeasibleCount > 0) 
				{
					nodeAct->mSon[i]->mCellType = SemiFeasible;
				}
				else 
				{
					nodeAct->mSon[i]->mCellType = Feasible;
				}
			}
			else {
				if (nodeAct->mSon[i]->mUnFeasibleCount > 0) 
				{
					nodeAct->mSon[i]->mCellType = NotFeasible;
				}
				else {
					nodeAct->mSon[i]->mCellType = Stranger;
				}
			}
		}

		/*Recursiva call to expands  */
		if (nodeAct->mDepth > 1) {
			for (i = 0; i < mConfiger.TreeNodeCount; i++)
			{
				if (nodeAct->mSon[i]->mCellType == SemiFeasible) 
				{
					Expand(nodeAct->mSon[i], ps);
				}
			}
		}
	}

	void BeliefSpace::Accept(PopulationSpace *ps)
	{
		ps->Sort();
	}
}