tsp.cpp

基于VC开发的神经网络工具箱

/* 
 * Travelling Salesman Problem using Kohonen Map.
 * Author: Asim Shankar
 * http://annie.sourceforge.net
 *
 * This program demonstrates the solving of a travelling salesman problem
 * using a self-organizing Kohonen map.
 *
 * There are 20 cities through which the salesman must cycle through.
 * The coordinates of the cities are normalized to lie between [0,1).
 *
 * The Kohonen Map used is a 1 dimensional map with 40 neurons.
 *
 * Training is done as follows:
 *	1. Map neurons initialized to random values.
 *  2. Randomly select a city, and generate a random point in it's neighbourhood
 *  3. Update the weights of the neurons using the Kohonen update rule and the point
 *     generated above.
 *  4. Goto step 2. Repeat until the map seems to stabalize.
 *
 * The tour is generated from the map as follows:
 *	1. Feed each city (Ci) to the map and find out the winner neuron (Wi).
 *  2. Order the cities C1...Cn according to the winners (W1...Wn).
 *  3. The order above gives the order of visiting.
 */
#include <annie.h>
#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

using namespace annie;

#define NEAR 0.05		// Random points are generated around the given cities with this radius
#define NCITIES 20		// Total number of cities

real Cities[NCITIES][2] =	//The normalized coordinates of the cities
{
	{0.25, 0.09},
	{0.60, 0.90},
	{0.19, 0.46},
	{0.93, 0.12},
	{0.41, 0.53},
	{0.10, 0.39},
	{0.65, 0.03},
	{0.07, 0.07},
	{0.85, 0.63},
	{0.57, 0.90},
	{0.88, 0.37},
	{0.34, 0.20},
	{0.56, 0.36},
	{0.39, 0.36},
	{0.43, 0.15},
	{0.62, 0.74},
	{0.34, 0.83},
	{0.26, 0.96},
	{0.24, 0.64},
	{0.91, 0.37},
};

//returns the Euclidean distance between city i and city j
real getCityDistance(int i, int j) 
{
	real dx = Cities[i][0]-Cities[j][0];
	real dy = Cities[i][1]-Cities[j][1];
	return sqrt(dx*dx+dy*dy);
}

void makePlotFiles(KohonenMap &map,const char *citiesFile, const char *tspFile, int path[], const char *weightsFile)
{
	FILE *cf,*tspf,*mapof;
	cf = fopen(citiesFile,"w");
	tspf = fopen(tspFile,"w");
	mapof = fopen(weightsFile,"w");

	for (int i=0; i<NCITIES; i++)
		fprintf(cf,"%f\t%f\n",Cities[i][0],Cities[i][1]);
	for (int i=0; i<NCITIES; i++)
		fprintf(tspf,"%f\t%f\n",Cities[path[i]][0],Cities[path[i]][1]);
	fprintf(tspf,"%f\t%f\n",Cities[path[0]][0],Cities[path[0]][1]);
	for (int i=0; i<NCITIES*2; i++)
		fprintf(mapof,"%f\t%f\n",map.getWeight(i,0),map.getWeight(i,1));
	fprintf(mapof,"%f\t%f\n",map.getWeight(0,0),map.getWeight(0,1));
	fclose(cf);
	fclose(tspf);
	fclose(mapof);
}

int main()
{
	int seed,timeout,i; //888 and 10000 is good with the wierd r function
	cout<<"Enter random seed : "; cin>>seed;
	cout<<"Time to train     : "; cin>>timeout;
	srand(seed);

	KohonenMap1D map(NCITIES*2,2);
	map.init(0.8,0.995,0.8,0.995);
	int ctr=0;
	while (map.getTime() < timeout)
	{
		int city = randomInt(0,NCITIES);
		//int city = ctr%NCITIES;
		ctr++;
		real p[2];
		p[0] = Cities[city][0]+annie::random()*NEAR;
		p[1] = Cities[city][1]+annie::random()*NEAR;
		map.updateWeights(p);
	}
	cout<<map.getCurrEpsilon()<<" "<<map.getCurrSigma()<<endl;

	// We've now trained the map
	int winners[NCITIES]; 
	int order[NCITIES];
	for (i=0;i<NCITIES;i++)
		order[i]=i;
    for (i=0;i<NCITIES;i++)
	{
		map.setInput(Cities[i]);
		winners[i] = map.getWinner();
		cout<<winners[i]<<endl;
	}

	for (i=NCITIES-1;i>=0;i--)
		for (int j=0;j<i;j++)
		{
			if (winners[j]>winners[j+1])
			{
				int t=winners[j];
				winners[j]=winners[j+1];
				winners[j+1]=t;

				t=order[j];
				order[j]=order[j+1];
				order[j+1]=t;
			}
		}

	real totalLength = 0.0;
	for (int i=0;i<NCITIES;i++)
	{
		printf("(%d,%d)\n",order[i],order[(i+1)%NCITIES]);
		totalLength+= getCityDistance(order[i],order[(i+1)%NCITIES]);
	}
	cout<<endl<<"TOTAL LENGTH = "<<totalLength<<endl;

	//map.save("test");
	makePlotFiles(map,"cities.dat","tsp.dat",order,"weights.dat");
	return 0;
}

//int main()
//{
//	real p[6][1] = {0.1,0.2,0.5,0.6,0.8,0.9};
//	int seed;
//	int timeout;
//	cout<<"Enter seed : "; cin>>seed;
//	cout<<"Tmax       : "; cin>>timeout;
//	KohonenMap1D map(3,1);
//	map.init(0.5,0.995,0.5,0.995);
//	while (map.getTime() < timeout)
//	{
//		int k = randomInt(0,6);
//		map.updateWeights(p[k]);
//	}
//	
//	for (int i=0; i<6 ;i++)
//	{
//		map.setInput(p[i]);
//		printf("%d --> %d\n",i,map.getWinner());
//	}
//}
//