simulated annealing.cpp

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

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<math.h>
#include<cstdlib>
#include<ctime>
using namespace std;
struct city
{
	string name;
	double x;
	double y;
};

int city_num=0;
double current_t=280;
vector<city> city_vec;
struct state
{
	vector<int> queue;
	double f;
	void assign_f()
	{
		double dx=0;
		double dy=0;
		double dis=0;
		f=0;
		for(int i=0;i<city_num-1;i++){
			dx=city_vec[queue[i+1]].x-city_vec[queue[i]].x;
			dy=city_vec[queue[i+1]].y-city_vec[queue[i]].y;
			dis=sqrt(pow(dx,2)+pow(dy,2));
			f=f+dis;
		}		
		dx=city_vec[queue[city_num-1]].x-city_vec[queue[0]].x;
		dy=city_vec[queue[city_num-1]].y-city_vec[queue[0]].y;
		dis=sqrt(pow(dx,2)+pow(dy,2));
		f=f+dis;
	}
	state operator =(const state&right)
	{
		queue.clear();
		for(int i=0;i<city_num;i++){			
			queue.push_back(right.queue[i]);		
		}
		f=right.f;
		return *this;
	}
};

state last_final;//表示每种温度下的最后解
state current_final;

int random()
{
	int fanhui=0;
	while(true){
	double temp=(double)rand()/RAND_MAX;
	fanhui=(int)(city_num*temp);
	if(fanhui<city_num){break;}	
	}
	return fanhui;
}
state make_near(state s)
{
	int i=random();
	int j=random();
	state ss;
	ss.queue.clear();
	for(int ii=0;ii<city_num;ii++){
		ss.queue.push_back(ii);
	}
	for(int ii=0;ii<i;ii++){
		ss.queue[ii]=s.queue[ii];
	}
	int ii=i;
	int jj=j;
	while(ii<=jj){
		ss.queue[ii]=s.queue[jj];
		ss.queue[jj]=s.queue[ii];
		ii++;
		jj--;
	}
	for(int jj=j+1;jj<city_num;jj++)
	{
		ss.queue[jj]=s.queue[jj];
	}
	ss.assign_f();
	return ss;
}

bool judge(state current,state state_near)
{
	double df=state_near.f-current.f;
	double standard=(double)rand()/RAND_MAX;
	double probability=0;
	if(df<0){probability=1;}
	else{probability=exp(-df/current_t);}

	if(probability>standard){return true;}
	else{return false;}

}
int main(int argv,char*args[])
{
	srand((unsigned int)time(NULL));
	ifstream in(args[1]);
	if(!in){cout<<"fail"<<endl;}
	in>>city_num;	
	for(int i=1;i<=city_num;i++)
	{
		city c;
		in>>c.name;
		in>>c.x;
		in>>c.y;
		city_vec.push_back(c);
	}


	state current;
	for(int i=city_num-1;i>=0;i--){
		current.queue.push_back(i);
	}
	current.assign_f();
	make_near(current);

	last_final=current;
	current_final=current;
	state state_near;
	while(true){
	
	last_final=current_final;
	for(int i=1;i<=100*city_num;i++)
	{
		
		state_near=make_near(current);
		if(state_near.f<current.f){
			current=state_near;
		}else if(judge(current,state_near)){
			current=state_near;
		}
	}
	current_final=current;
	current_t=current_t*0.92;
	//输出结果
	cout<<"f="<<current_final.f<<":  ";
	for(int i=0;i<city_num;i++)
	{
		cout<<city_vec[current.queue[i]].name<<"  ";
	}
	cout<<endl;
	if(current_final.f==last_final.f){break;}
	}

	return 0;
}