moni.h

用模拟退火算法求解旅行商问题

//****************模拟退火算法求解旅行商问题************
//***			 
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <fstream>
using namespace std;
const double e=2.71828;
ofstream outfile("wokankan.txt");
int ttt;
//一些全局量
int num; //城市数量
int ** dis;//距离矩阵，dis[0..N-1][0..N-1].我的程序的规模不会超过100。
void input();//输入N,产生距离矩阵，随机化
class candidate   //解的结构，或称状态
{
public:
	int N;			//城市数
	vector<int> citys;//citys[0]-->citys[1]-->....citys[N-1]-->citys[0]的路线
	int cost;//花的总时间;
	double T;   //当前温度
	int k; //在当前温度下的已迭代步数
	int itera;  //在某一温度下的迭代步数
	int precost; //前一温度下的最小值
	double a;//温度衰减系数
	candidate(double T,double a,int itera_num,int N)  //创建初始状态
	{
		//一般量的初始化
		this->precost=-1;
		this->k=0;
		this->itera=itera_num*N;
		this->N=N;
		this->a=a;
		this->T=T;



		//初始状态的生成
		vector<int> temp;
		int i;
		for(i=0;i<N;i++)
		{
			temp.push_back(i);
		}



		for(i=0;i<N;i++)
		{
			ttt=rand();
			int t=ttt%(N-i);
			citys.push_back(temp[t]);
			temp.erase(temp.begin()+t);
		}


		//计算刚生成的状态的值
		calculateCost();

	}

	//*****改变温度******
	void changeT(double a) //a 是温度衰减系数
	{
		T=T*a;
	}


	//**得到当前温度******
	double getT()
	{
		return T;
	}

	//*******一开始的时候计算行走路径*******
	void calculateCost()  
	{
		cost=0;
		int i;
		for(i=0;i<N-1;i++)
		{
			cost=cost+dis[citys[i]][citys[i+1]];
		}
		cost+=dis[citys[N-1]][citys[0]];
	}


	//模拟退火全过程
	void anneal()
	{
		//外层循环，控制温度的下降
		while(!isfinish())
		{
			precost=cost;

			int i;
			int dt;

			//内层循环，在某一温度下迭代指定步数，以达到平衡
			for(i=0;i<itera;i++)
			{
				int u,v;
				dt=generate(u,v);
				updateCost(dt,u,v);
			}

			changeT(a);k++;
		}
	}

	//**********终止条件看是否 T 已经足够低 *************
	bool isfinish()   
	{
		return T<0.01;
	}


	//************如果接受了领域的点，就更新cost *******************
	void updateCost(int dt,int u,int v) 
	{
		double possible=pow(e,-(abs(dt)/T));
		ttt=rand();
		if(dt<=0||double(double(ttt%300)/double(300))<possible) //accept the new 
		{
			cost=cost+dt;

			// 将随机生成的u,v在先前的旅游路线中调换一下位置，
			//得到一条新的路线。
			int i;
			for(i=u+1;i<(u+v+1)/2;i++)
			{
				int te=citys[i];
				citys[i]=citys[u+v-i];
				citys[u+v-i]=te;
			}


		}

	}



	//**********生成领域,逆向交换城市法，即随机产生城市u,v(u<v)******************
	int generate(int &u,int& v)
	{ 
		ttt=rand(); 
		u=ttt%N;
		if(u==N-1)
		{
			v=u;
			ttt=rand();
			u=ttt%(N-1);                                     
		}
		else
		{
			ttt=rand();
			v=(ttt%(N-1-u))+u+1;
		}


		if(u+1!=v)
		{
			int re=dis[citys[u]][citys[v-1]]+dis[citys[u+1]][citys[v]]
			-dis[citys[u]][citys[u+1]]-dis[citys[v-1]][citys[v]];
			return re;
		}
		return 0;

	}



	//********输出最优解******************
	void output()
	{
		cout<<"after "<<k<<" steps we get a nice solution as below"<<endl;
		int i;
		for (i=0;i<N;i++)
		{
			cout<<citys[i]<<" ";
		}

		cout<<"the total dis they spend is: "<<cost<<endl;

	}





};

void input()
{
	int number[5]={5,10,30,60,100};
	string ss[5]={"data_5.txt","data_10.txt","data_30.txt","data_60.txt","data_100.txt"
	};
	int sel;
	cout<<"what you will select N"<<endl;
	cout<<"0. 5  1. 10  2. 30  3. 60  4. 100"<<endl;
	cin>>sel;
	num=number[sel];
	int i,j;
	dis=new int *[num];
	for (i=0;i<num;i++) {
		dis[i]=new int[num];
	}

	ifstream into(ss[sel].c_str());
	for(i=0;i<num;i++)
	{	
		for (j=0;j<num;j++) 
		{
			into>>dis[i][j];	
		}

	}
}