dlg.cpp

刚根据蚁群算法文档编写的蚁群算法的程序

// Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "Project.h"
#include "Dlg.h"
#include "stdio.h"
#include "Global.h"
#include "Ant.h"
#include "City.h"
#include "stdlib.h"
#include "time.h"

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

/////////////////////////////////////////////////////////////////////////////
// Dlg dialog


Dlg::Dlg(CWnd* pParent /*=NULL*/)
	: CDialog(Dlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(Dlg)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
}


void Dlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(Dlg)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(Dlg, CDialog)
	//{{AFX_MSG_MAP(Dlg)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// Dlg message handlers

void Dlg::OnOK() 
{
//	long ltime;
//	int stime;

	int Numoftabu = 0;
	int temp_po;
	double temp_pro = 0;
	int time = 0;  
	int NC = 0;   
	double length[NumOfCity][NumOfCity];
	double shortest_path_distant = 0;
	int shortest_path_ant;
	int shortest_path[NumOfCity];
	double derta_t[NumOfCity - 1][NumOfCity - 1];
	double tao[NumOfCity][NumOfCity];

	FILE *fp1;
	FILE *fp;
	FILE *fp2;
	fp = fopen("path.txt", "w+");
	fp1 = fopen("length.txt", "r+");
	fp2 = fopen("result.txt", "w+");


	// read the length of each path and set them in length[][]
	for(int i = 0; i <= NumOfCity - 1; i++)
	{
		for(int j = 0; j <= NumOfCity - 1; j++)
		{
			fscanf(fp1, "%lf ", &length[i][j]);
		}
	}


	Ant ant[NumOfAnt];  // define object of Ant
	CCity city[NumOfCity];   // define object of City
	

	// The First step
	// set tao as a constant
	for(int c = 0; c <= NumOfCity - 1; c++)
	{
		for(int v = 0; v <= NumOfCity - 1; v++)
		{
			tao[c][v] = tao_0;
		}
	}

	// initial the derta_t
	for(int uu = 0; uu <= NumOfCity - 2; uu ++)
	{
		for(int pp = 0; pp <= NumOfCity - 2; pp ++)
		{
			derta_t[uu][pp] = 0;
		}
	}

	for(int a = 0; a <= NumOfAnt - 1; a++)  // place the ants in the random town
	{
		ant[a].current_position = rand() % NumOfCity;
	}

	for(int ant_num = 0; ant_num <= NumOfAnt - 1; ant_num ++)
	{
		for(int city_num = 0; city_num <= NumOfCity - 1; city_num ++)
		{
			ant[ant_num].tabu[city_num] = -1;   // clear the tabu
		}
	}

Re:	do
	{
//		Numoftabu = 0;
		for(int i = 0; i <= NumOfAnt - 1; i++)
		{
			// The Second step
//			Numoftabu = 0; // Numoftabu is "s" in document
			ant[i].tabu[Numoftabu] = ant[i].current_position;  // set the current position in tabu
//			Numoftabu ++;

			// The Third step
			for(int j = 0; j <= NumOfCity - 1; j++)
			{
				ant[i].prob[ant[i].current_position][j] = ant[i].getProbability(ant[i].current_position, j);
			}
			temp_pro = 0;
			for(int m = 0; m <= NumOfCity - 1; m++)
			{				
				if(ant[i].prob[ant[i].current_position][m] >= temp_pro)
				{
					temp_pro = ant[i].prob[ant[i].current_position][m];
					temp_po = m;
					ant[i].next_Position = temp_po;
				}
			}
	
			ant[i].current_position = ant[i].next_Position;   // move to next town
//			Numoftabu ++;
//			ant[i].tabu[Numoftabu] = ant[i].current_position;	// insert next town into tabu
		}
		Numoftabu ++;
	}while(Numoftabu <= NumOfCity - 1);


	// The Fourth step
	for(int u = 0; u <= NumOfAnt - 1; u++)
	{ 
		// set the ants to the first place
		ant[u].current_position = ant[u].tabu[0];
		// compute the length of each ants
		for(int r = 0; r <= NumOfCity - 2; r++)
		{
			ant[u].length = ant[u].length + length[ant[u].tabu[r]][ant[u].tabu[r + 1]];
		}
	}

	// search the shortest path
	for(int g = 0; g <= NumOfAnt - 2; g++)
	{
		if (ant[g].length <= ant[g + 1].length)
		{
			// record the distant of shortest path
			shortest_path_distant = ant[g].length;
			shortest_path_ant = g;

		}
	}
	for(int l = 0; l <= NumOfCity - 1; l++)
	{ 
		// record the shortest path
		shortest_path[l] = ant[shortest_path_ant].tabu[l];
	}

	// set the information of each ant
	for(int num = 0; num <= NumOfAnt - 1; num ++)
	{
		for(int num_city = 0; num_city <= NumOfCity - 2; num_city ++)
		{
			ant[num].derta_t[ant[num].tabu[num_city]][ant[num].tabu[num_city + 1]];
		}
	}

	// set the total information of each path
	for(int nu = 0; nu <= NumOfCity - 2; nu ++)
	{
		for(int nu1 = 0; nu1 <= NumOfCity - 2; nu1 ++)
		{
			for(int nu_ant = 0; nu_ant <= NumOfAnt - 1; nu_ant ++)
			{
				derta_t[nu][nu1] = ant[nu_ant].derta_t[nu][nu1];
			}
		}
	}

	// The Fifth step
	time = time + NumOfCity - 1;
	NC ++;
	// set the derta_t of each edge as "0"
	for(int n = 0; n <= NumOfCity - 2; n ++)
	{
		for(int m = 0; m <= NumOfCity - 2; m ++)
		{
			derta_t[n][m] = 0;
		}
	}

	// The Sixth step
	if( NC <= NC_Max )
	{
		for(int x = 0; x <= NumOfAnt - 1; x ++)
		{
			for(int w = 0; w <= NumOfCity - 1; w ++)
			{
				ant[x].tabu[w] = -1;
			}
		}
		goto Re;
	}
	else 
	{
		for(int b = 0; b <= NumOfCity; b ++)
		{
			fprintf(fp2, "%d   ", shortest_path[b]);
		}		
	}

	fclose(fp);
	fclose(fp1);
	fclose(fp2);
}