//頭文件:		GenMSrch.hpp
//目的:			為遺傳算法提供基類,該基類將評價函數值直接作為適合度,采用
//				新個體直接替換老個體的整體再生法,在搜索過程中,采用多目標法
//語言:			VC++ 6.0
//時間:			1999年11月~2000年1月
//作者:			劉康
//環境:			Win32
//注意:			EvalVal(INDIVIDUAL&)應由用戶類覆蓋,以提供正確的評價函數.
////////////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include "GenMSrch.hpp"

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

GenMSrch::GenMSrch(int n, int gl):Genetic(n,gl)
{
	VRProb = .2;
	SProb = .5;
}

GenMSrch::~GenMSrch()
{

}

//交叉再生方法
void GenMSrch::GenCross()
{
	if(CurrentChild>=ChildrenNum-1) return;
	int parent1 = ParentSelect();		//選擇雙親1
	int *indSort = new int[IndNumber];
	int *indDis = new int[IndNumber];
	for(int st=0; st<IndNumber; st++)	//計算其它個體與雙親1的距離
	{
		indDis[st] = VisualDis(parent1,st);
		indSort[st] = st;
	}
	for(st=0; st<IndNumber-1; st++)		//將其他個體按距離排序
	{
		int mDis = st;
		for(int sst=st+1; sst<IndNumber; sst++)
			if(indDis[sst]<indDis[mDis]) mDis = sst;
		int tmp = indSort[st];
		indSort[st] = indSort[mDis];
		indSort[mDis] = tmp;
		tmp = indDis[st];
		indDis[st] = indDis[mDis];
		indDis[mDis] = tmp;
	}
	double *index = new double[IndNumber];//個體總適合度數組
	index[0] = Individual[indSort[0]].Fit;
	for(st=1; st<IndNumber; st++)		//按與雙親1距離計算個體總適合度
		index[st] = Individual[indSort[st]].Fit+index[st-1];
	int len = (int)((rand()/(double)RAND_MAX)*IndNumber*VRProb);
	if(len<1) len = 1;					//計算距離內個體個數
	int parent2;
	if(rand()/(double)RAND_MAX<=SProb)	//近親結婚
	{
		parent2 = Wheel(index+1,len);	//滾輪選擇,排除雙親1
		parent2 = indSort[parent2];
	}
	else								//遠親結婚
	{
		parent2 = Wheel(index+len,IndNumber-len);//滾輪選擇
		parent2 = indSort[parent2];
	}
	delete []indSort;
	delete []indDis;
	delete []index;
	if((rand()/(double)RAND_MAX)<CrossProb)
	{
		if(Cross == ONE_POINT)
			Individual[parent1].Chrom.OneCross(Individual[parent2].Chrom,
											   Children[CurrentChild].Chrom,
											   Children[CurrentChild+1].Chrom);
		else if(Cross == TWO_POINT)
			Individual[parent1].Chrom.TwoCross(Individual[parent2].Chrom,
											   Children[CurrentChild].Chrom,
											   Children[CurrentChild+1].Chrom);
		else
			Individual[parent1].Chrom.UniCross(Individual[parent2].Chrom,
											   Children[CurrentChild].Chrom,
											   Children[CurrentChild+1].Chrom);
	}
	else
	{
		Children[CurrentChild].Chrom = Individual[parent1].Chrom;
		Children[CurrentChild+1].Chrom = Individual[parent2].Chrom;
	}
	CurrentChild += 2;
}

//可視距離函數
int GenMSrch::VisualDis(int P1,int P2)
{
	int sLong = 0;
	for(int i=1; i<=Individual[P1].Chrom.GetLen(); i++)
		if(Individual[P1].Chrom.GetInt(i,i)!=Individual[P2].Chrom.GetInt(i,i))
			sLong++;
	return sLong;
}