ga1.cpp

这是一个利用遗传算法求解函数极值

// GA1.cpp: implementation of the CGA class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "GA.h"
#include "GA1.h"

#include "Chromosome.h"
#include <afxtempl.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include "Random.h"
#include "QuickSelect.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#define LENGHTARRAY 600

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CGA::CGA()
{
}

CGA::CGA(float pcross,float pmutation,int popsize,int percision,int funcType,int maxgen)
{
	m_popsize=popsize;
	m_maxgen=maxgen;
	m_pcross=pcross;
	m_pmutation=pmutation;
	m_maxFitness=0;
	m_maxgenImprove=8;
	m_genImprove=0;
	m_pBestChrom=NULL;

	CChromosome::SetChromParam(percision,funcType);
	
}


CGA::~CGA()
{
}

bool CGA::isSatisfyCon()
{
	double dFitness[LENGHTARRAY];
	CChromosome *pChrom;
	int newArraySize=m_newPtrArray.GetSize();
	while(newArraySize--)
	{
		m_oldPtrArray.Add(m_newPtrArray.GetAt(newArraySize));
		m_newPtrArray.RemoveAt(newArraySize);
	}
	int oldArraySize=m_oldPtrArray.GetSize();
	for(int i=0;i<oldArraySize;i++)
	{
		dFitness[i]=((CChromosome*)m_oldPtrArray.GetAt(i))->GetFitness();
	}

	double fitness=QuickSelect(dFitness,0,oldArraySize-1,m_popsize+1);

	while(oldArraySize--)
	{
		pChrom=(CChromosome*)m_oldPtrArray.GetAt(oldArraySize);
		if(fitness>=pChrom->GetFitness())
		{
			if(fitness==pChrom->GetFitness())
			{
				m_oldPtrArray.Add(pChrom);
			}
			else
			{
				delete pChrom;
			}
			m_oldPtrArray.RemoveAt(oldArraySize);
		}
	}
	oldArraySize=m_oldPtrArray.GetSize(); 
	while(oldArraySize-- > m_popsize)
	{
		delete (CChromosome*)m_oldPtrArray.GetAt(oldArraySize);
		m_oldPtrArray.RemoveAt(oldArraySize);		                                                   
	}
	
	bool isSatC=0;
    CChromosome *pBestChrom=(CChromosome*)m_oldPtrArray.GetAt(0);
	double maxFitness=pBestChrom->GetFitness();
	for(int i=1;i<m_popsize;i++)
	{
		pChrom=(CChromosome*)m_oldPtrArray.GetAt(i);
		if(maxFitness<pChrom->GetFitness())
		{
			maxFitness=pChrom->GetFitness();
			pBestChrom=pChrom;
		}
	}
	if(maxFitness>m_maxFitness)
	{
		m_maxFitness=maxFitness;
		if(m_pBestChrom!=NULL)
			delete m_pBestChrom;
		m_pBestChrom=pBestChrom->CopyChrom();
		m_genImprove=0;
	}
	else
	{
		if(m_genImprove>=m_maxgenImprove) //种群中的最优个体在连续若干代没有改进时停止
		{
			isSatC=1;
			m_genImprove=0;
		}
		else
		{
			m_genImprove++;
		}
	}

	///////////////////
/*	int ddd=m_newPtrArray.GetSize();
	ddd=m_oldPtrArray.GetSize();
	CString str1,str2;
	for(int kk=0;kk<m_oldPtrArray.GetSize();kk++)
	{
		str1.Format("%s,%f,\n",((CChromosome*)m_oldPtrArray.GetAt(kk))->GetStrCode(),((CChromosome*)m_oldPtrArray.GetAt(kk))->GetFitness());
		str2+=str1;
	}
	AfxMessageBox(str2);*/
	///////////////////////


/*	for( kk=0;kk<m_oldPtrArray.GetSize();kk++)
	{
		str1.Format("%f,",((CChromosome*)m_oldPtrArray.GetAt(kk))->GetFitness());
		str2+=str1;
	}
	AfxMessageBox(str2);*/

	return isSatC;
}

void CGA::Select()
{ 
	CString strCode;
	int nCount=0;
	double sumFitness=0;

	CArray <int, int> kind;
	CArray <int, int> sameNext;
	CArray <int, int> serialNum;
	kind.SetSize(m_popsize);
	serialNum.SetSize(m_popsize);
	for(int i=0;i<m_popsize;i++)
	{
		kind[i]=1;
		serialNum[i]=0;
	}
	for(int j=0;j<m_popsize;j++)
	{
		if(kind[j]!=0)
		{
			nCount++;
			strCode=((CChromosome*)m_oldPtrArray.GetAt(j))->GetStrCode();
			for(int i=j;i<m_popsize;i++)
			{
				if(strCode==((CChromosome*)m_oldPtrArray.GetAt(i))->GetStrCode())
				{
					kind[i]=0;
					kind[j]+=1;
					serialNum[i]=nCount;
				}
			}
		}
	}

	CArray <double, double> fitness;
	CArray <double, double> percent;
	CArray <int, int> count;
	fitness.SetSize(nCount);
	percent.SetSize(nCount);
	count.SetSize(nCount);
	for(int i=0;i<nCount;i++)
		fitness[i]=0;

	for(int i=0;i<m_popsize;i++)
	{
		fitness[serialNum[i]-1]+=((CChromosome*)m_oldPtrArray.GetAt(i))->GetFitness();
		sumFitness+=((CChromosome*)m_oldPtrArray.GetAt(i))->GetFitness();
	}
	int remnant=m_popsize;
	for(int i=0;i<nCount;i++)
	{
		percent[i]=fitness[i]/sumFitness;         
		count[i]=int(percent[i]*m_popsize);
		percent[i]-=count[i];
		remnant-=count[i];
	}

	int numRem,imaxper;
	float maxper;
	for(numRem=0;numRem<remnant;numRem++)
	{
		maxper=float(percent[0]); imaxper=0;
		for(int i=0;i<nCount;i++)
		{
			if(maxper<percent[i])
				imaxper=i;
		}
		percent[imaxper]=0.0f;
		count[imaxper]+=1;
	}

	CChromosome *pChrom;    
	int num,sum=0,iCount; 
	int j=0;
	for(int i=0;i<m_popsize;i++)
	{
		if(kind[i]!=0)
		{
			for(iCount=0;iCount<count[j];iCount++)
			{
				sum++;
				pChrom=((CChromosome*)m_oldPtrArray.GetAt(i))->CopyChrom();
				if(sum==1 || sum==2)
					num=sum-1;
				else
					num=int((sum-2)*fRandom());
				m_newPtrArray.InsertAt(num,pChrom);           
			}
			j++;
		}
	}
//	newPtrArray.RemoveAll();
	kind.RemoveAll();
	sameNext.RemoveAll();
	serialNum.RemoveAll();
	fitness.RemoveAll();
	percent.RemoveAll();
	count.RemoveAll();
}

void CGA::CrossOver()
{
	CChromosome *pChrom1,*pChrom2;

//	int xSite;
	int lenChrom=((CChromosome*)m_newPtrArray.GetAt(0))->GetLenChrom();//=Random(((CChromosome*)m_newPtrArray.GetAt(0))->GetLenChrom());
	int numPair=(int)(m_popsize*m_pcross/2+0.5);
	int num;//,j;
	for(int i=0;i<numPair;i++)
	{	
//		for(j=0;j<3;j++)
		{
//			xSite=int((lenChrom-1)*fRandom());
			num=int((m_popsize/2-1)*fRandom());
			pChrom1=(CChromosome*)m_newPtrArray.GetAt(2*num);
			pChrom2=(CChromosome*)m_newPtrArray.GetAt(2*num+1);
			pChrom1->CrossOver(pChrom2);
		}
	}
}

void CGA::Mutation()
{
	CChromosome *pChrom;
	int numMutation=(int)(m_popsize*m_pmutation+0.5);
	int mSite;
	int lenChrom=((CChromosome*)m_newPtrArray.GetAt(0))->GetLenChrom();
		
	int i=0,j,num;
	CString strCode;
	while(i<numMutation)
	{
		for(j=0;j<3;j++)
		{
			num=int((m_popsize-1)*fRandom());
			mSite=int((lenChrom-1)*fRandom());
			pChrom=(CChromosome*)m_newPtrArray.GetAt(num);
			pChrom->Mutation(mSite);
			i++;
		}
	}
}


void CGA::GA()
{
	m_gen=1;
	CString strResult;
	BOOL isSatC=0;
	CFile file("GARe.txt",CFile::modeCreate | CFile::modeWrite);
	RandomNumber();
	CChromosome::InitChromPop(m_oldPtrArray,m_popsize);

	do	{
		Select();
		CrossOver();
		Mutation();
		isSatC = isSatisfyCon();
		m_gen++;

		strResult.Format("\r\n第%d代, 最优值:%.10f\r\n自变量值为:",m_gen,m_pBestChrom->GetFitness());
		const double *pVarible=m_pBestChrom->GetVarible();
		int num=m_pBestChrom->GetVaribleNum();
		for(int i=0;i<num;i++)
		{
			CString str;
			str.Format("%f  ",pVarible[i]);
			strResult+=str;
		}
		file.Write(strResult.GetBuffer(),strResult.GetLength());
		strResult = "";
	}while( m_gen<m_maxgen && !isSatC);

	file.Close();
	int num=m_pBestChrom->GetVaribleNum();
	const double *pVarible=m_pBestChrom->GetVarible();
	m_strResult.Format("最优值为%.10f\n\n自变量值为:",m_pBestChrom->GetFitness());
	for(int i=0;i<num;i++)
	{
		CString str;
		str.Format("%f  ",pVarible[i]);
		m_strResult+=str;
	}
	CString str;
	str.Format("\n\n总共计算了%d代",m_gen);
	m_strResult+=str;
	CChromosome::DestroyChromPop(m_newPtrArray);
	delete m_pBestChrom;
}