stimulation_final.cpp

采用的是康力山等人确定的实验参数。 对于n个城市的旅行商问题

#include<iostream.h>
#include<math.h>
#include <stdlib.h>
#include<time.h>
#define amount 10
class citys{

private:
	int city_number;
	double citycoordinate[amount][2];

public:
	citys(void){    //构造函数
		city_number = 10;
		double temp[amount][2] = {0.4000,0.4439,
							  0.2439,0.1463,
							  0.1707,0.2293,
							  0.2293,0.7610,
							  0.5171,0.9414,
							  0.8732,0.6536,
							  0.6878,0.5219,
							  0.8488,0.3609,
							  0.6683,0.2536,
							  0.6195,0.2634};
								/*	{5.294,1.558,
									4.286,3.622,
									4.719,2.774,
									4.185,2.230,
									0.915,3.821,
									4.771,6.041,
									1.524,2.871,
									3.447,2.111,
									3.718,3.665,
									2.649,2.556,
									4.399,1.194,
									4.660,2.949,
									1.232,6.440,
									5.036,0.244,
									2.710,3.140,
									1.072,3.454,
									5.855,6.203,
									0.194,1.862,
									1.762,2.693,
									2.682,6.097};*/
	
		for(int i=0;i<amount;i++)
			for(int j=0;j<2;j++)
				citycoordinate[i][j] = temp[i][j];
	}
	double distance(int x,int y)       //计算两个城市之间的距离
	{
		double result = 0;
		result = sqrt( (citycoordinate[x][0] - citycoordinate[y][0]) * (citycoordinate[x][0] - citycoordinate[y][0]) + 
						(citycoordinate[x][1] - citycoordinate[y][1]) * (citycoordinate[x][1] - citycoordinate[y][1]) );
		return result;
	}
	double evaluate(int *x)         //计算某一个序列中城市之间的距离总和
	{
		double result = 0;
	
		for(int counter=0;counter<amount-1;counter++)
		{
			result += distance(x[counter],x[counter+1]);
		}
		result += distance(x[amount-1],x[0]);

		return result;
	}
	
	double P(int *i,int *j,double t)    //t代表当前温度,i,j分别代表不同的两个序列,返回对应的转移发生概率
	{
		double fi = 0,fj = 0;
		double result = 0;
		fi = evaluate(i);
		fj = evaluate(j);
	
		if(fj < fi)
			result = 1.0;
		else 
			result = exp( (fi - fj)/t );
		return result;
	}
	double random0_1(void)
	{        //产生随机数,范围在0-1之间
		return (double)rand() / (double)RAND_MAX;
	}

	//设计函数能够从一个父序列中找出一个随机的子序列，使得两个城市位置互换
	void Neighbour(int *i,int *result)   //i代表父序列，result代表子序列。将交换结果存储在result中
	{
		int n = 0,m = 0,temp = 0;
		for(int k=0;k<amount;k++)
			result[k] = i[k];
		do
		{
			n = rand() % amount;
			m = rand() % amount;
		}while(n == m);
		temp = result[n];
		result[n] = result[m];
		result[m] = temp;	
	}
	
	void out(int *x){
		int *temp = x;
		for(int s=0;s<amount;s++)
		{
			cout << temp[s] << " ";
		}
			cout << evaluate(temp) << endl;
	}

	int *stimulation(int *x)    
	{
		int *result = NULL,*temp = NULL;
		double random = 0;
		int *j = new int[amount];
		int *i = new int[amount];
		for(int m=0;m<amount;m++)
		{	i[m] = x[m];j[m] = 0; }
		double t = 280,alpha = 0.92;   //初始温度，降温系数
		int k = 0;        //降温次数
		const int L = 1000;    //每个温度的迭代次数,也就是每一个温度上的平衡条件
		int time = 0;   //记录某一温度下的迭代次数
		double f1 = 101,f2 = 100;  //f1记录上一个温度中达到的最后指标函数值,f2记录当前温度下达到的指标函数值
		do
		{
			f1 = f2;
			time = 0;
			do
			{
				Neighbour(i,j);
				random = P(i,j,t);
				if ( (random == 1.0) || (random > random0_1()) )
				{
					temp = i;
					i = j;
					j = temp;
				}
				time++;
			}while(time < L);

			f2 = evaluate(i);
			t = alpha * t;
			k++;
		}while( fabs(f2 - f1) > 1e-5);
	
		result = i;
		return result;
	}
};

int * random(void)
{
	int temp = 0,signal = 1,k=0;
	int *save =NULL;
	save =  new int[amount];
	for(int j=0;j<amount;j++)
		save[j] = -1;
	do
	{
		signal = 1;
		temp = rand() % amount;
		for(int i=0;i<amount;i++)
			if(save[i] == temp)
			{signal = 0;break;}
		if(signal != 0)
		{
			save[k] = temp;
			k++;
		}
	}while(signal == 0 || k != amount);
	return save;
}

void main()
{
	citys city;
	srand( (unsigned)time( NULL ) );   //设置种子	
	int *sequence;   //初始序列
	sequence = random();
	for(int i=0;i<100;i++)city.out(city.stimulation(sequence));
}