模拟退火算法求解TSP
发布时间
阅读量：
阅读量
算法背景，伪代码请参考博客http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html
该算法的基本思想是模仿物理退火过程，在每一步都可能会接受比当前解差的结果，并通过这种机制避免陷入局部最优解的困境。在爬山算法中存在一个显著的区别：当遇到比当前解差的结果时，在该算法中不会立即拒绝这些结果；相反，在一定概率下会接受这些结果，并根据情况逐步降低这种接受概率。
(主要框架：三个函数+两个准则)
给定初温t=t0，随机产生初始状态s=s0，令k=0；
Repeat
Repeat
产生新状态sj=Genete(s) ；
if **min{1,exp[-(C(sj)-C(s))/tk]} >=randrom[0,1] ** s=sj;
Until 抽样稳定准则满足；
退温tk+1=update(tk) 并令k=k+1；
Until算法终止准则满足；
输出算法搜索结果。
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <fstream>
#define CITYNUM 52
#define MAX 0x7fffffff
using namespace std;
struct Point
{
int x;
int y;
char name;
};
//read the graph & compute the distance dist[i][j]
void InitGraph(double dist[CITYNUM][CITYNUM],Point citys[CITYNUM])
{
fstream fileRead;
fileRead.open("coords.txt",ios::in);
for(int i=0;i<CITYNUM;i++)
{
int temp;
char ch;
fileRead>>temp>>ch>>citys[i].x>>ch>>citys[i].y>>ch>>citys[i].name;
//cout<<temp<<ch<<citys[i].x<<ch<<citys[i].y<<ch<<citys[i].name<<endl;
}
fileRead.close();
for(int i=0;i<CITYNUM;i++)
{
for(int j=0;j<CITYNUM;j++)
{
if(j!=i&&dist[i][j]==0)
{
double d2=(citys[i].x-citys[j].x)*(citys[i].x-citys[j].x)+(citys[i].y-citys[j].y)*(citys[i].y-citys[j].y);
dist[i][j]=dist[j][i]=sqrt(d2);
}
}
}
}
double Evalue(const vector<int> answer,double dist[CITYNUM][CITYNUM])
{
double sum=0;
for(int i=0;i<answer.size()-1;i++)
{
//cout<<answer[i]<<"->"<<answer[i+1]<<":"<<sum<<"+"<<dist[answer[i]][answer[i+1]]<<"="<<sum+dist[answer[i]][answer[i+1]]<<endl;
sum+=dist[answer[i]][answer[i+1]];
}
sum+=dist[answer[answer.size()-1]][answer[0]];
return sum;
}
void Swap(vector<int> &newAnswer,int first,int second)
{
newAnswer[first]=newAnswer[first]^newAnswer[second];
newAnswer[second]=newAnswer[first]^newAnswer[second];
newAnswer[first]=newAnswer[first]^newAnswer[second];
}
void Reverse(vector<int> &newAnswer,int first,int second)
{
if(first>second)
{
first=first^second;
second=first^second;
first=first^second;
}
reverse(newAnswer.begin()+first,newAnswer.begin()+second);
}
void Save(const vector<int> minAnswer,Point citys[CITYNUM],double t0,double alpha,double te,double minSum)
{
fstream fileWrite;
fileWrite.open("out.txt",ios::out|ios::app);
fileWrite<<"起始温度："<<t0<<"，终止温度："<<te<<"，降温系数："<<alpha<<"，近似最优："<<minSum<<endl;
for(int i=0;i<minAnswer.size();i++)
{
fileWrite<<citys[minAnswer[i]].name<<"->";
}
fileWrite<<citys[minAnswer[0]].name<<endl;
fileWrite.close();
}
void SimuAnne(double t0,double alpha,double te )
{
vector<int> answer,newAnswer,minAnswer;
int k=0;//记录循环次数
double t=t0;
double sumDist=0,newSum=0,minSum=MAX;
double dist[CITYNUM][CITYNUM]={0};
Point citys[CITYNUM];//city's coordinate
InitGraph(dist,citys);
//initial answer
for(int i=0;i<CITYNUM;i++)
{
answer.push_back(i);
}
srand ( unsigned (time(0) ) );
random_shuffle(answer.begin(),answer.end());
sumDist=Evalue(answer,dist);
minSum=sumDist;
minAnswer.assign(newAnswer.begin(),newAnswer.end());
cout<<k<<" "<<minSum<<endl;
copy(answer.begin(),answer.end(),ostream_iterator<int>(cout," "));cout<<endl;//输出answer
while(t>te)
{
//srand ( unsigned (time(0) ) );
newAnswer.assign(answer.begin(),answer.end());
int first=0,second=0;
//swap first & second
first=rand()%CITYNUM;
second=rand()%CITYNUM;
if(first!=second)
{
//cout<<first<<"--"<<second<<endl;
Swap(newAnswer,first,second);//产生新的状态
//Reverse(newAnswer,first,second);//产生新的状态
newSum=Evalue(newAnswer,dist);
if(min(1.0,exp(-(newSum-sumDist)/t))>=(rand()%998)/997.0)
{
answer.assign(newAnswer.begin(),newAnswer.end());
sumDist=newSum;
if(newSum<minSum)
{
minSum=newSum;
minAnswer.assign(newAnswer.begin(),newAnswer.end());
cout<<k<<" "<<minSum<<endl;
copy(answer.begin(),answer.end(),ostream_iterator<int>(cout," "));cout<<endl;//输出answer
}
k++;
}
t=t*alpha;
}
}
Save(minAnswer,citys,t0,alpha,te,minSum);
for(int i=0;i<minAnswer.size();i++)
{
cout<<citys[minAnswer[i]].name<<"->";
}
cout<<citys[minAnswer[0]].name<<endl;
}
int main()
{
double t0=1000;//起始温度
double alpha=0.999999;//降温系数
double te=0.000001;//截止温度
SimuAnne(t0,alpha,te);
return 0;
}测试数据：
0,1,1,a
1,1,2,b
2,1,3,c
3,1,4,d
4,1,5,e
5,1,6,f
6,1,7,g
7,1,8,h
8,1,9,i
9,1,10,j
10,2,11,k
11,7,11,l
12,12,11,m
13,17,11,n
14,22,11,o
15,27,11,p
16,32,11,q
17,37,11,r
18,42,11,s
19,47,11,t
20,52,11,u
21,57,11,v
22,62,11,w
23,67,11,x
24,72,11,y
25,77,11,z
26,82,11,A
27,87,11,B
28,92,11,C
29,97,11,D
30,101,10,E
31,101,9,F
32,101,8,G
33,101,7,H
34,101,6,I
35,101,5,J
36,101,4,K
37,101,3,L
38,101,2,M
39,100,1,N
40,95,1,O
41,90,1,P
42,85,1,Q
43,80,1,R
44,75,1,S
45,70,1,T
46,65,1,U
47,60,1,V
48,55,1,W
49,50,1,X
50,45,1,Y
51,40,1,Z以上算法运行过程中迭代次数较多。相比而言差距较大（如有兴趣不妨留下您的见解）。
起始温度：1e+007，终止温度：1e-006，降温系数：0.999999，近似最优：228.351
t->s->r->q->p->o->n->j->i->h->g->f->e->d->c->b->a->k->l->m->Z->Y->X->W->V->U->T->S->R->Q->P->O->N->M->L->K->J->I->H->G->F->E->D->C->B->A->z->y->x->w->v->u->t 起始温度：1000，终止温度：1e-006，降温系数：0.999999，近似最优：225.017
T->U->V->W->X->Y->Z->q->p->o->a->b->c->d->e->f->g->h->i->j->k->l->m->n->r->s->t->u->v->w->x->y->z->A->B->C->D->E->F->G->H->I->J->K->L->M->N->O->P->Q->R->S->T全部评论 (0)
还没有任何评论哟~