genalg.cpp

与本人上次上传的类别一样

	int x[10];
	int y[10];

	for(int t = 0;t < 10;t++)
	{
		x[t] = baby1[t];
		y[t] = baby2[t];
	}
*/
	const int NumSelectCities = 10;
	
	//装载被选中的城市编号
	int SelectCities[NumSelectCities];
	
	//被选中的城市的位置
	int positions[NumSelectCities];
	
	//随机选出城市(并且排序)
	for(int i = 0;i < NumSelectCities;i++)
	{
		//记录所选城市在染色体的位置
		int pos = RandInt(0, g_numGen-1);
		
		//记录所选城市编号
		SelectCities[i] = mum[pos];
		
		//防止重复选择同一个城市,与及按照在染色体的顺序给城市排序
		if(i != 0)
		{
			for(int j = 0;j < i;j++)
			{	
				//如果所选择城市重复
				if(pos == positions[j])
				{
					i--;
					break;
				}
				//如果序数较小
				if(pos < positions[j])
				{
					for(int k = i;k > j;k--)
					{
						//调整以前确定的位置
						positions[k] = positions[k-1];
						//跟着调整所对应的编号
						SelectCities[k] = SelectCities[k-1];
					}

					positions[j] = pos;

					//记录所选城市编号
					SelectCities[j] = mum[pos];
					break;
				}
				//如果不重复而且序数最大,就摆在最后.
				positions[i] = pos;
			}
		}
		else
		{
			//如果是最先的城市,直接插入.
			positions[i] = pos;
		}
	}

	//装载在另外一条染色体里面对应城市排序
	int SelectCities2[NumSelectCities];

	//记录已经进行排序的城市个数
	int count = 0;
	
	//按照母方排序方法给baby2所选的几个城市排序
	for(i = 0;i < g_numGen;i++)
	{
		for(int j = 0;j < NumSelectCities;j++)
		{
			if(dad[i] == SelectCities[j])
			{
				//记录对应城市的排序
				SelectCities2[count] = dad[i];
				//按照母方的排序方法排序
				baby2[i] = SelectCities[count];
				count++;
				break;
			}
		}
	}

	//按照父方排序方法给baby1所选的几个城市排序
	for(i = 0;i < NumSelectCities;i++)
	{
		baby1[positions[i]] = SelectCities2[i];
	}
/*
	for(t = 0;t < 10;t++)
	{
		x[t] = baby1[t];
		y[t] = baby2[t];
	}
*/
}


	
//起到初始化的作用
void CGenAlg::Reset()
{
	m_dTotalFitness		= 0;
	m_dBestFitness		= 0;
	m_dWorstFitness		= 9999999;
	m_dAverageFitness	= 0;
}


void CGenAlg::CalculateBestWorstAvTot()
{
	m_dTotalFitness = 0;
	
	double HighestSoFar = 0;
	double LowestSoFar  = 9999999;
	
	for (int i=0; i<m_iPopSize; ++i)
	{
		//update fittest if necessary
		if (m_vecPop[i].dFitness > HighestSoFar)
		{
			HighestSoFar	 = m_vecPop[i].dFitness;

			m_dWorstFitness = HighestSoFar;
		}
		
		//update worst if necessary
		if (m_vecPop[i].dFitness < LowestSoFar)
		{
			LowestSoFar = m_vecPop[i].dFitness;

			m_iFittestGenome = i;
			
			 m_dBestFitness = LowestSoFar;
		}
		
		m_dTotalFitness	+= m_vecPop[i].dFitness;
				
	}//next chromo

	m_dAverageFitness = m_dTotalFitness / m_iPopSize;

	m_cGeneration++;
	m_arAverageFitness[m_cGeneration-1] = m_dAverageFitness;
	m_arBestFitness[m_cGeneration-1] = m_dBestFitness;
}



//以等级为基础的缩放比例函数
void CGenAlg::FitnessScaleRank()
{
	const int FitnessMultiplier = 1;
	
	//assign fitness according to the genome's position on
	//this new fitness 'ladder'
	for (int i=0; i<m_iPopSize; i++)
	{
		m_vecPop[i].dFitness = i * FitnessMultiplier;
	}

	//recalculate values used in selection
	CalculateBestWorstAvTot();
}


//-------------------------GrabNBest----------------------------------
//
//	This works like an advanced form of elitism by inserting NumCopies
//  copies of the NBest most fittest genomes into a population vector
//--------------------------------------------------------------------
void CGenAlg::GrabNBest(int NBest, vector<CGenome> &vecNewPop)
{
	//first we need to sort our genomes
	if (!m_ifSorted)
	{
		sort(m_vecPop.begin(), m_vecPop.end());

		m_ifSorted = 1;
	}

	//now add the required amount of copies of the n most fittest 
	//to the supplied vector
	while(NBest--)
	{
		vecNewPop.push_back(m_vecPop[(m_iPopSize - 1) - NBest]);
	}
}


//此函数产生新的一代,见证着整个进化的全过程.
//以父代种群的基因组容器作为参数传进去,该函数将往该容器里放入新一代的基因组(当然是经过了优胜劣汰的)
void CGenAlg::Epoch(vector<CGenome> &vecNewPop)
{
	//用类的成员变量来储存父代的基因组(在此之前m_vecPop储存的是不带估值的所有基因组)
	m_vecPop = vecNewPop;

	//初始化相关变量
	Reset();

	m_ifSorted = 0;

	vecNewPop.clear();

	vecNewPop.reserve(m_iPopSize);

	GrabNBest(2,vecNewPop);

	CalculateBestWorstAvTot();
	
	//产生新一代的所有基因组
	while (vecNewPop.size() < m_iPopSize)
	{
		//转盘随机抽出两个基因
		//CGenome mum = GetChromoRoulette();
		//CGenome dad = GetChromoRoulette();
		
		CGenome mum = TournamentSelection(4);
	    CGenome dad = TournamentSelection(4);

		//创建两个子代基因组
		vector<int> baby1, baby2;
		
		//交叉父方的基因和母方的基因
		CrossoverOBX(mum.Cities, dad.Cities, baby1, baby2);

		//使子代基因发生基因突变
		MutateIM(baby1);
		MutateIM(baby2);
		
		//把两个子代基因组放到新的基因组容器里面
		vecNewPop.push_back( CGenome(baby1, 0) );
		vecNewPop.push_back( CGenome(baby2, 0) );
	}//子代产生完毕
	
	//如果你设置的人口总数非单数的话,就会出现错误
	if(vecNewPop.size() != m_iPopSize)
	{
		AfxMessageBox("你的人口数目不是单数!!!");
		return;
	}
}



void CGenAlg::outputTheData(CDC* pDC)
{
	//显示统计图表
	if(ifShowDiagram)
	{
		CPen pen,pen2,*p_pen;
		pen.CreatePen(PS_SOLID,2,RGB(0,0,0));
		p_pen = pDC->SelectObject(&pen);
		
		int x1 = g_WindowsWidth / 8;
		int y1 = g_WindowsHeight / 2 - g_WindowsHeight / 16;
		
		int x2 = g_WindowsWidth / 8; 
		int y2 = g_WindowsHeight - g_WindowsHeight / 16;
		
		pDC->MoveTo(x1,y1);
		pDC->LineTo(x1,y1 - g_WindowsHeight * 3 / 8);
		pDC->MoveTo(x1,y1);
		pDC->LineTo(x1 + g_WindowsWidth * 3 / 4,y1);
		
		pDC->MoveTo(x2,y2);
		pDC->LineTo(x2,y2 - g_WindowsHeight * 3 / 8);
		pDC->MoveTo(x2,y2);
		pDC->LineTo(x2 + g_WindowsWidth * 3 / 4,y2);
		
		
		double max1 = m_arBestFitness[0];
		double max2 = m_arAverageFitness[0];
		for(int i = 0; i < m_cGeneration;i++)
		{
			if(max1 < m_arBestFitness[i])
				max1 = m_arBestFitness[i];
			if(max2 < m_arAverageFitness[i])
				max2 = m_arAverageFitness[i];
		}
		
		double interval;
		if(m_cGeneration == 1)
		{
			interval = 0;
		}
		else
		{
			interval = 1.0 * g_WindowsWidth * 3 / 4 / (m_cGeneration-1);
		}
		
		pen2.CreatePen(PS_SOLID,1,RGB(0,0,0));
		p_pen = pDC->SelectObject(&pen2);
		
		int showInterval = floor(m_cGeneration/g_NumDiagramline) + 1;

		if(m_cGeneration == 690)
		{
			int a  = 10;
		}

		pDC->MoveTo(x1,y1 - m_arBestFitness[0] / max1 * g_WindowsHeight * 3 / 8);
		
		for(i = 0;i < m_cGeneration;i+=showInterval)
		{
			int x = x1 + i * interval;
			int y = y1 - m_arBestFitness[i] / max1 * g_WindowsHeight * 3 / 8;
			pDC->LineTo(x, y);
			pDC->LineTo(x, y1);
			pDC->MoveTo(x, y);
		}
		
		
		//int interval2 = g_WindowsWidth * 3 / 4 / (m_cGeneration-1);
		pDC->MoveTo(x2,y2 - m_arAverageFitness[0] / max2 * g_WindowsHeight * 3 / 8);
		for(i = 0;i < m_cGeneration;i+=showInterval)
		{
			int x = x2 + i * interval;
			int y = y2 - m_arAverageFitness[i] / max2 * g_WindowsHeight * 3 / 8;
			pDC->LineTo(x, y);
			pDC->LineTo(x, y2);
			pDC->MoveTo(x, y);
		}
	}
	

	

	CFont *pOldfont,*newfont=new CFont;
	TEXTMETRIC tm;
	newfont->CreateFont(15,0,0,0,FW_NORMAL,0,0,0,GB2312_CHARSET,OUT_DEFAULT_PRECIS,CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,DEFAULT_PITCH,"宋体");
	pOldfont=pDC->SelectObject(newfont);
	pDC->GetTextMetrics(&tm);
	pDC->SetTextColor(RGB(0,0,0));
	pDC->SetBkMode(TRANSPARENT);

	char buf[20];
	sprintf(buf,"基因的世代: %d", m_cGeneration);
	pDC->TextOut(20,20,buf);

	sprintf(buf,"最优基因的得分: %Lf", m_dBestFitness);
	pDC->TextOut(20,35,buf);

	sprintf(buf,"基因的平均得分: %Lf", m_dAverageFitness);
	pDC->TextOut(20,50,buf);

	pDC->SelectObject(pOldfont);
	newfont->DeleteObject();
}