tsp.cpp

这是一个用遗传算法来求解旅行商问题（TSP问题：Travelling Salesman Problem）的源代码

// TSP.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include ".\TSPSGA.h"

int Run = 0;
int OpCnt = 0;
int ChromLen = 9;
int  CrossOver(const char *Parent1, const char *Parent2, char *Child1, char *Child2);
int  Produce(const char *Parent2, char *Child1, int Pos1, int Pos2);
int _tmain(int argc, _TCHAR* argv[])
{

	CTSPSGA *sga;

	FILE *File = fopen("tt.txt", "w+");
	fclose(File);

	for (Run=0; Run<500; Run++)
	{
		sga = new CTSPSGA();

		sga->StartRun();

		delete sga;
		sga = NULL;
	}
	/*char p1[20] = "ABCDEFGHI";
	char p2[20] = "CBAGEIDHF";
	char c1[20] = "";
	char c2[20] = "";
	CrossOver(p1, p2, c1, c2);
	*/

	printf("%d", OpCnt);

	getchar();

	return 0;
}

int  CrossOver(const char *Parent1, const char *Parent2, char *Child1, char *Child2)
{	
	int  Len = strlen(Parent1);
	int  Pos1 = 1 + rand() % (ChromLen - 2);
	int  Pos2 = 0;
	do
	{
		Pos2 = 1 + rand() % (ChromLen - 2);
	}while (Pos1 == Pos2);

	double pick = Crand((unsigned)time( NULL ));

	if (pick > 1.0)
	{
		memcpy(Child1, Parent1, Len);
		memcpy(Child2, Parent2, Len);
		return 0;
	}
	

	Pos1  = 3;
	Pos2  = 7;

	if (Pos1 > Pos2)
	{
		int tem = Pos1;
		Pos1 = Pos2;
		Pos2 = tem;
	}

	//中间部分保存不变
	memcpy(Child1+Pos1, Parent1+Pos1, Pos2 - Pos1);
	memcpy(Child2+Pos1, Parent2+Pos1, Pos2 - Pos1);

	Produce(Parent2, Child1, Pos1, Pos2);
	Produce(Parent1, Child2, Pos1, Pos2);

	return Pos1*1000+Pos2;
}

int Produce(const char *Parent2, char *Child1, int Pos1, int Pos2)
{
	char *pCh = new char[ChromLen];
	memset(pCh, 0, ChromLen);

	//
	memcpy(pCh, Parent2+Pos2, ChromLen - Pos2);
	memcpy(pCh + ChromLen - Pos2, Parent2, Pos2);
	
	for (int i=0; i<ChromLen; i++)
	{
		for(int j=0; j<Pos2 - Pos1; j++)
		{
			if (pCh[i] == Child1[Pos1+j])
			{
				pCh[i] = '0';
			}
		}
	}

	int k = Pos2;
	for (int i=0; i<ChromLen; i++)
	{
		if (pCh[i] != '0')
		{
			Child1[k] = pCh[i];
			k = (k + 1) % ChromLen;
		}
	}

	delete []pCh;
	pCh = NULL;

	return 0;
}