fire.cpp

使用模拟退火算法求解10城市和20城市的旅行商问题

/*模拟退火算法中
  初始温度的选取：t0=280；
  状态被接收的条件：设新状态的f值为f2，原来的为f1，则满足以下任意一条时接收新状态(t为当前温度,random(0,1)为0,1之间的随机数)：
					(1)f2<f1
					(2)e^(-(f2-f1)/t)>random(0,1)
  同一温度下计算结束的条件：计算次数count达到100*n（其中n为城市总数）
  降温：t(k+1)=t(k)*0.92
  算法结束条件：相邻两个温度下得到的结果完全相同
*/



#include<iostream>
#include<fstream>
#include<string>
#include<math.h>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;


struct City{																//城市结构
	string name;															//城市名
	double x;																//城市x坐标值
	double y;																//城市y坐标值
	bool accept;															//标记，在生成初始状态时判断该城市是否已经加入到状态中
};
vector<City> start;															//初始状态数组
vector<City> last;															//最终状态数组
int num;																	//城市数

double calculate_f(vector<City> c){											//计算某一状态的f值
	int size=(int)c.size();
	double distance=0.0;
	for(int i=0;i<size-1;i++){												//循环求得相邻城市之间的距离，并加到最终距离上
		double delta_x=c[i].x-c[i+1].x;
		double delta_y=c[i].y-c[i+1].y;
		distance=distance+sqrt(pow(delta_x,2.0)+pow(delta_y,2.0));
	}
	double delta_x=c[size-1].x-c[0].x;										//将最后一城市与第一个城市的距离加到最终距离上
	double delta_y=c[size-1].y-c[0].y;
	distance=distance+sqrt(pow(delta_x,2.0)+pow(delta_y,2.0));
	return distance;														//返回最终距离值
}

void search(){																//模拟退火算法搜索最优路径
	double t=280.0;															//初始温度t为280度
	vector<City> temp=start;												//暂存当前状态
	vector<City> next;														//存放当前状态的邻接状态
	vector<City> temp2;														//保存上一温度计算结束后的状态
	bool flag=false;														//判断是否跳出最外层循环的标记
	srand((unsigned int) time(NULL));										//设置种子
	while(true){															//外层循环，在当前温度下进行搜索
		flag=true;															//先将跳出循环标记置true
		double f=0.0;														//保存每个温度下得到的最后状态的f值
		int count=100*(int)start.size();									//每个温度下的计算次数为100*n，其中n为城市数
		while(count>0){														//未达到温度平衡条件时（即未计算满100*n次）
			int a=rand()%num;												//生成两个不同的随机数，在0——n-1之间（n为城市数）	
			int b=rand()%num;
			while(a==b){
				b=rand()%num;
			}
			if(a>b){														//将生成的两个数中小的存放在a中，大的存放在b中
				int temp=a;
				a=b;
				b=temp;
			}
			for(int i=0;i<a;i++){											//逆序交换第a个到第b个城市之间的所有城市，包括两者本身，此处即将a到b直接的城市逆序压入下一状态数组中，其余按原顺序压入
				next.push_back(temp[i]);
			}
			for(int i=b;i>=a;i--){
				next.push_back(temp[i]);
			}
			for(int i=b+1;i<num;i++){
				next.push_back(temp[i]);
			}
			double f1=calculate_f(temp);									//计算当前状态和下一状态的f值,分别存放在f1和f2中
			double f2=calculate_f(next);
			f=f1;
			if(f2<f1){														//f2<f1时，进入到下一状态
				temp=next;
				f=f2;
				next.clear();
			}
			else{															//否则
				double random=rand()/RAND_MAX;								//生成一随机数（在0到1之间）
				double pt=exp(-(f2-f1)/t);									//计算接收概率
				if(pt>random){												//接收概率比随机小数大时，进入到下一状态
					temp=next;
					f=f2;
					next.clear();
				}
				else{														//否则停留在原状态
					next.clear();
				}
			}
			
			count--;														//当前温度剩余计算次数减1
		}
		for(int i=0;i<(int)temp.size();i++){								//每一温度计算完毕，输出得到的状态及f值
			cout<<temp[i].name<<" ";
		}
		cout<<f<<endl;
		if(temp2.size()!=temp.size()){										//判断与上一个温度计算结束时的状态是否相同，若不同，则将跳出循环的标记置false
			flag=false;
		}
		else{
			for(int i=0;i<(int)temp.size();i++){
				if(temp[i].name!=temp2[i].name){
					flag=false;
					break;
				}
			}
		}
		if(flag){															//判断是否需要跳出循环，若要，则跳出
			break;
		}
		else{																//否则，保存当前温度下的最后状态，并降温
			temp2=temp;
			t=t*0.92;														
		}
	}
	last=temp;																//将最终得到的结果存在last数组中
}

int main(int argv, char *args[]){
	num=0;
	vector<City> cv;
	ifstream in(args[1]);													//从命令行读入文件名
	if(!in){
		cout<<"fail"<<endl;
		return -1;
	}
	in>>num;																//第一行为城市数
	for(int i=1;i<=num;i++){												//之后每一行均为城市名，x坐标和y坐标
		City c;
		in>>c.name;															
		in>>c.x;
		in>>c.y;
		c.accept=false;
		cv.push_back(c);
	}
	srand((unsigned int) time(NULL));										//设置种子
	for(int i=0;i<num;i++){							
		int j=rand()%num;													//生成0——n-1的随机数（n为城市数）
		if(cv[j].accept==false){											//若该城市未被加入到初始状态中，则加入之
			start.push_back(cv[j]);
			cv[j].accept=true;
		}
		else{																//否则重新生成随机数
			i--;
			continue;
		}
	}
	search();																//模拟退火搜索最优路径
	double f=calculate_f(last);												//计算最终状态的f值
	cout<<f<<endl;															//输出最优解
	return 0;
}