china45dlg.cpp

遗传算法解中国旅行商问题

		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CChina45Dlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CChina45Dlg::OnMenuGaset() 
{
	// TODO: Add your command handler code here
	CGASetDlg dlg;
	if(dlg.DoModal()==IDOK)
	{
		m_nGroupSize=dlg.m_nGroupSize;
		m_GACrossProb=dlg.m_GACrossProb;
		m_GAVariProb=dlg.m_GAVariProb;
		m_GANum=dlg.m_GANum;
		UpdateData(false);
	}
}

void CChina45Dlg::OnMenuSoft() 
{
	// TODO: Add your command handler code here
	CAboutDlg dlg;
	dlg.DoModal();
	
}

void CChina45Dlg::OnMenuExit() 
{
	// TODO: Add your command handler code here
	CDialog::OnOK();
}

void CChina45Dlg::OnButtonGa() 
{
	PopNode *oldpop;
	oldpop=new PopNode[m_nGroupSize];
	for(int k=0;k<1;k++)
	{
		ExecGA(k, oldpop);
	}

	//ExecGA(101,oldpop);
}

// 产生随机整数
int CChina45Dlg::RandomInt(int low, int high)
{
	int result;
	result=rand();
    return result%(high-low+1)+low;
}

//屏幕显示函数
void CChina45Dlg::DrawNetwork()
{
	CPen Pen;
	CDC* pDC=GetDC();
	CRect RectClient,Workarea;

    GetClientRect(RectClient);
    Workarea.left=RectClient.left+140;
    Workarea.bottom=RectClient.bottom-30;
	Workarea.right=Workarea.left+290;
    Workarea.top=Workarea.bottom-270;
    pDC->Rectangle(Workarea);
    pDC->SetBkColor(0x00FFFFFF);

	int px=Workarea.left;
	int py=Workarea.bottom+20;
	
	pDC->SetTextColor(0x00F08080);
	for(int i=0;i<MAXCHROM;i++)
	{
		CRect city;
		city.left=px+m_point[i].x-2;
		city.right=px+m_point[i].x+2;
		city.top=py-m_point[i].y-2;
		city.bottom=py-m_point[i].y+2;
		pDC->Ellipse(city);
	}

	//char xn[4];wsprintf(xn,"%d",m_GeneLen);
	//AfxMessageBox(xn);

	pDC->SetTextColor(0x000000FF);
	for(int k=0;k<m_GALen-1;k++)
	{	
		int x1=px+m_point[m_pop.path[k]].x;
		int y1=py-m_point[m_pop.path[k]].y;
		
		int x2=px+m_point[m_pop.path[k+1]].x;
		int y2=py-m_point[m_pop.path[k+1]].y;

		pDC->MoveTo(x1,y1);
		pDC->LineTo(x2,y2);	
	}
	
	int x1=px+m_point[m_pop.path[m_GALen-1]].x;
	int y1=py-m_point[m_pop.path[m_GALen-1]].y;
	int x2=px+m_point[m_pop.path[0]].x;
	int y2=py-m_point[m_pop.path[0]].y;

	pDC->MoveTo(x1,y1);
	pDC->LineTo(x2,y2);	

}


void CChina45Dlg::OnMenuResult() 
{
	// TODO: Add your command handler code here
	/*CString txt;
	
	for(int i=0;i<MAXCHROM;i++)
	{
		char xn[4]; wsprintf(xn,"%d",m_pop.path[i]);
		txt= txt+ xn + "--";
	}
	
	//AfxMessageBox(txt);

	CResultDlg dlg;
	dlg.SetResult(txt);
	dlg.DoModal();*/
}

void CChina45Dlg::ExecGA(int k, PopNode *pop)
{
	double TotalF=0;

	// 取得基因算法所需参数  
	UpdateData(TRUE);

	//根据群体规模和交叉概率计算出交叉个体个数
	m_CrossNum=(int)m_nGroupSize*m_GACrossProb/2;
	m_VariNum=(int)m_nGroupSize*m_GAVariProb;

	PopNode *oldpop, *newpop;
	oldpop=new PopNode[m_nGroupSize];
	newpop=new PopNode[m_nGroupSize+m_CrossNum*2+m_VariNum];
	
	//已进行过基因算法标志
	m_bIsGA=true;

	if(m_nGroupSize<m_CrossNum*2+m_VariNum)
	{
		AfxMessageBox("群体规模交叉变异设置有误!",MB_OK|MB_ICONINFORMATION,NULL);
        return; 
	}
	
	if(k<=100)
	{
		//形成初始基因序列   
		for(int i=0;i<m_nGroupSize;i++) for(int j=0;j<MAXCHROM-1;j++)
		{
			int r1=RandomInt(1, MAXCHROM-1);
			int r2=RandomInt(1, MAXCHROM-1);
			if(r1!=r2) oldpop[i].Varite(r1, r2);
		}
	}
	else
		for(int i=0;i<m_nGroupSize;i++) oldpop[i].CopyNode(&pop[i]);


	// 基因算法具体实现
    for(int gen=0;gen<m_GANum;gen++)
    {   
		// 计算当前一代群体中个体的适应度数值F
		for(int i=0;i<m_nGroupSize;i++)
			TotalF+=1/oldpop[i].CalcCost(m_distance);

        // 归一化F值
		for(i=0;i<m_nGroupSize;i++) 
			oldpop[i].fit=1/oldpop[i].cost/TotalF*100;

        // 将当前一代群体中的个体按F值从大到小排序
		for(i=0;i<m_nGroupSize-1;i++) 
		{
			double max=0.0;
			int maxpos;

			for(int j=i;j<m_nGroupSize;j++) if(oldpop[j].fit>max)
			{
				max=oldpop[j].fit; maxpos=j;
			}

			if(i!=maxpos) oldpop[i].SwapNode(&oldpop[maxpos]);
		}

		m_CurGANum=gen;

    	// 查找当前一代中的最小费用个体
		m_MiniCost=oldpop[0].cost;

		m_pop.CopyNode(&oldpop[0]);

		m_GAFitness=m_pop.fit;

		//AfxMessageBox("显示数据");

		UpdateData(false);

		UpdateWindow();

		// 绘制图形
		DrawNetwork();

		//继承所有父代基因
		for(i=0;i<m_nGroupSize;i++) newpop[i].CopyNode(&oldpop[i]);

        // 交叉操作
		for(i=0;i<m_CrossNum;i++)
        {  
			int nPos, temp=0;
            int parent1=0;     //父代基因1
			int parent2=0;     //父代基因2
             
			parent1=RandomInt(0,m_nGroupSize-1);   
			temp=RandomInt(0,m_nGroupSize-1);
			if(parent1>temp) parent1=temp;

            parent2=RandomInt(0,m_nGroupSize-1);
            temp=RandomInt(0,m_nGroupSize-1);
            if(parent2>temp) parent2=temp; 
			
			//复制用于交叉的基因对
			PopNode pop1;
			PopNode pop2;

			pop1.CopyNode(&oldpop[parent1]);
			pop2.CopyNode(&oldpop[parent2]);
			 
            // 基因序列中用于交叉的基因位
			nPos=RandomInt(3,MAXCHROM-3); 
			pop1.CrossTwo(&pop2, nPos);  
			
			//交叉完成,保存结果
			newpop[m_nGroupSize+2*i].CopyNode(&pop1);
			newpop[m_nGroupSize+2*i+1].CopyNode(&pop2);

        } 

		//变异操作
		for(i=0;i<m_VariNum;i++)
		{
			int nPos1,nPos2,parent=0;     //变异父代基因

			parent=RandomInt(0,m_nGroupSize-1);
			nPos1=RandomInt(3,MAXCHROM-3);
			nPos2=RandomInt(3,MAXCHROM-3);

			PopNode pop;
			pop.CopyNode(&oldpop[0]);

			//double mincost=40000;
			//int n1=0,n2=0;
			
			//for(nPos1=0;nPos1<MAXCHROM;nPos1++) for(nPos2=nPos1+1;nPos2<MAXCHROM;nPos2++)
			
			//{
				//执行变异
				//PopNode tmppop; 
				//tmppop.CopyNode(&pop);
				//tmppop.Varite(nPos1,nPos2); 
				pop.Varite(nPos1,nPos2); 
				//double tmpcost=pop.CalcCost(m_distance);
				//if(mincost>tmpcost){n1=nPos1;n2=nPos2;mincost=tmpcost;}
			//}
			
			//保存变异结果
			//pop.Varite(n1,n2);
			newpop[m_nGroupSize+m_CrossNum*2+i].CopyNode(&pop);
		}

        //按适应度降序排列子代群体
		for(i=0;i<m_nGroupSize+m_CrossNum*2+m_VariNum;i++)
        {
			double max=0.0;
			int maxpos;

			for(int j=i;j<m_nGroupSize+m_CrossNum*2+m_VariNum;j++) 
				if(newpop[j].fit>max)
					{
						max=newpop[j].fit;maxpos=j;
					}

			if(i!=maxpos) newpop[i].SwapNode(&newpop[maxpos]);
		}
		
		//产生新一代群体
		for(i=0;i<m_nGroupSize;i++) oldpop[i].CopyNode(&newpop[i]);
		
		//睡眠0以便于观察
		Sleep(0);
	}

	m_pop.CopyNode(&oldpop[0]);

	if(k<=100) 
		for(int i=0; i<m_nGroupSize;i++)
			pop[i+m_nGroupSize*k].CopyNode(&oldpop[i]);
		

}