psomatch.h

用匈牙利算法解决二部图的最优匹配问题,可用于多任务的指派问题的解决.

#ifndef __PSOMATCH_H__
#define	__PSOMATCH_H__

#include <list>
#include "Common.h"
class PSOIndividual
{
public:
	int number[10];
	int pBest[10];
	double pBestfitness;
	double fitness;
};
class PSOMatch
{
public:
	PSOMatch(int dimen = 3, int size = 10) {Dimension = dimen; POPSize = size;}
	int POPSize;
	int Dimension;
	double Cost[100][100];

	PSOIndividual Particulate[100];
	int gBest[10];
	double gBestfitness;

	void initiate();
	void cross();
	void calculate(int ID);
	void localbest(int ID);
	void globalbest(bool HaveGBest = true);
	void match();
};
void PSOMatch::calculate(int ID)
{
	Particulate[ID].fitness = 0;
	for(int i = 0; i < Dimension; i++)
	{
		Particulate[ID].fitness += Cost[i][Particulate[ID].number[i]];
	}
}
void PSOMatch::localbest(int ID)
{
	int i = 0;
	calculate(ID);
	if(Particulate[ID].pBestfitness > Particulate[ID].fitness)
	{
		for(i = 0; i < Dimension; i++)
		{
			Particulate[ID].pBest[i] = Particulate[ID].number[i];
		}
		Particulate[ID].pBestfitness = Particulate[ID].fitness;
	}
}
void PSOMatch::globalbest(bool HaveGBest /* = TRUE */)
{
	int i;
	double s = 0;
	int gBestID = 0;
	if(!HaveGBest)
	{
		s = Particulate[0].fitness;
		gBestID = 0;
		for(i = 0; i < POPSize; i++)
		{
			if(Particulate[i].fitness < s)
			{
				s = Particulate[i].fitness;
				gBestID = i;
			}
		}

		for(i = 0; i < Dimension; i++)
		{
			gBest[i] = Particulate[gBestID].number[i];
		}
		gBestfitness = Particulate[gBestID].fitness;
	}
	else
	{
		s = gBestfitness;
		gBestID = -1;
		for (i = 0; i < POPSize; i++)
		{
			if(Particulate[i].pBestfitness <= s)
			{
				s = Particulate[i].pBestfitness;
				gBestID = i;
			}
		}
		if(gBestID >= 0)
		{
			gBestfitness = s;
			for(i = 0; i < Dimension; i++)
			{
				gBest[i] = Particulate[gBestID].pBest[i];
			}
		}
	}
}
void PSOMatch::initiate()
{
	int i, j;
	for(i = 0; i < POPSize; i++)
	{
		Particulate[i].number[0] = i%Dimension;
		Particulate[i].pBest[0] = Particulate[i].number[0];
		int key = 1;
		for(j = 1; j < Dimension; j++)
		{
			Particulate[i].number[j] = Particulate[i].number[j-1] + key;
			if(Particulate[i].number[j] >= Dimension)
			{
				Particulate[i].number[j] -= Dimension;
			}
			Particulate[i].pBest[j] = Particulate[i].number[j];
		}
		calculate(i);
		Particulate[i].pBestfitness = Particulate[i].fitness;
	}

	globalbest(false);
}
void PSOMatch::cross()
{
	int MaxSteps = 30;
	int step = 0;
	PSOIndividual indi;
	while(step <= MaxSteps)
	{
		for(int i = 0; i < POPSize; i++)
		{
			indi = Particulate[i];
			//1、每个粒子与全局极值交叉
			//1.1 计算交叉位置
			int min = (int)AverageRandom(0, Dimension-1);
			int max = (int)AverageRandom(0, Dimension-1);
			CompareTwoNumber(min, max);
			while(max - min <= (int)Dimension/2 -1)
			{
				max = max + 1;
				if(max >= Dimension) max = max - Dimension;
				CompareTwoNumber(min, max);
			}
			//1.2 交叉
			int k = 0;
			for(int j = min; j <= max; j++)
			{
				indi.number[k] = gBest[j];
				k++;
			}
			int kk = k;
			for(j = 0; j < Dimension; j++)
			{
				bool HaveSameNum = false;
				for(int p = 0; p < k; p++)
				{
					if(Particulate[i].number[j] == indi.number[p])
					{
						HaveSameNum = true;
						break;
					}
				}
				if(!HaveSameNum)
				{
					indi.number[kk] = Particulate[i].number[j];
					kk++;
				}
			}
			//1.3 保存
			Particulate[i] = indi;

			//2、再与个体极值交叉
			//2.1 计算交叉位置
			min = (int)AverageRandom(0, Dimension-1);
			max = (int)AverageRandom(0, Dimension-1);
			CompareTwoNumber(min, max);
			while(max - min <= (int)Dimension/2 -1)
			{
				max = max + 1;
				if(max >= Dimension) max = max - Dimension;
				CompareTwoNumber(min, max);
			}
			//2.2 交叉
			k = 0;
			for(j = min; j <= max; j++)
			{
				indi.number[k] = Particulate[i].pBest[j];
				k++;
			}
			kk = k;
			for(j = 0; j < Dimension; j++)
			{
				bool HaveSameNum = false;
				for(int p = 0; p < k; p++)
				{
					if(Particulate[i].number[j] == indi.number[p])
					{
						HaveSameNum = true;
						break;
					}
				}
				if(!HaveSameNum)
				{
					indi.number[kk] = Particulate[i].number[j];
					kk++;
				}
			}
			//2.3 保存
			Particulate[i] = indi;

			//3、变异
			double per = AverageRandom(0, 1);
			if(per > 0.618/*0.9*/)
			{
				for(j = 0; j < Dimension-1; j++)
				{
					int key = (int)AverageRandom(j,Dimension - 0.5);
					Exchange(Particulate[i].number[j], Particulate[i].number[key]);
				}
			}
			calculate(i);
			localbest(i);
		}
		globalbest(true);
		step++;
	}
}
void PSOMatch::match()
{
	initiate();
	cross();
}
#endif