一、 问题介绍
中国邮递员问题tsp
输入：中国144个城市数据
输出：最短路径序列及路径长度
1. 采用局部搜索算法实现
2. 采用模拟退化算法实现
二、 程序设计与算法分析
1. 待解决的问题实际上是优化与组合优化问题。很多问题属于优化问题,或者可以转化为优化问题，如TSP问题,皇后问题等。
2. 用一个城市的序列表示一个可能的解，通过交换两个城市的位置获取S的邻居。
逆序交换方法设xi、xj是选取的两个城市,所谓的逆序交换方式是指,通过逆转xi、xj两个城市之间的城市次序来得到S的邻居。
3. local search：
基本思想:在搜索过程中,始终向着离目标最接近的方向搜索。
目标可以是最大值,也可以是最小值。
本题中目标为最小值。
算法步奏：
1．随机的选择一个初始的可能解x0∈D,xb=x0,P=N(xb);
2. 如果不满足结束条件,则
3. Begin
4. 选择P的一个子集P',xn为P'中的最优解
5. 如果f(xn)<f(xb),则xb=xn,P=N(xb),
转2;f(x)为指标函数。
6. 否则P=P–P',转2。
7. End
8. 输出计算结果
9. 结束
4. localsearch中存在的问题：
得到的答案往往是局部最优，而不是全局最优解。
5. 解决local search中问题的方法：
1) 每次并不一定选择邻域内最优的点,而是依据一定的概率,从 邻域内选择一个点,指标数优的点,被选中的概率比较大, 而指标函数差的点,被选中的概率比较小。
2) 函数的递增递减可能不均匀，在最优值附近可能变化极快，最好采用变步长的方式，越接近最优解时步长越小。
3) 起始点的选择可能会影响最终的解：随机的生成一些初始点,从每个初始点出发进行搜索,找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。
6. 以上决方法可以结合在一起使用,比如第一、第二种方 法的结合,就产生了模拟退火方法。
7. 模拟退火思想综述：
在高温下,系统基本处于无序的状态,基本以等概率落入各个状态在给定的温度下,系统 落入低能量状态的概率大于系统落入高能量状态的概率,这样在同一温度下,如果系统交换的 足够充分,则系统会趋向于落入较低能量的状态。随着温度的 缓慢下降,系统落入低能量状态的概率逐步增加,而落入高能量状态的概率逐步减少,使得系统各状态能量的期望值随温度的下降单调下降,而只有那些能量小于期望值的状态,其概率 才随温度下降增加,其他状态均随温度下降而下降。因此,随着能量期望值的逐步下降,能量低于期望值的状态逐步减少, 当温度趋于0时,只剩下那些具有最小能量的状态,系统处于其他状态的概率趋近于0。因此最终系统将以概率1处于具有最小能量的一个状态。
8. 达到最小能量状态三个条件：
1) 初始温度必须足够高;
2) 在每个温度下,状态的交换必须足够充分;
1. 3) 温度T的下降必须足够缓慢
9. 算法流程：
1) 随机选择一个解i,k=0,t0=Tmax(初始温度),计算指标函数f(i)
2) 如果满足结束条件,则转(15)。
3) Begin
4) 如果在该温度内达到了平衡条件,则转(13)。
5) Begin
6) 从i的邻域N(i)中随机选择一个解j。
7) 计算指标函数f(j)。
8) 如果f(j)<f(i),则i=j,f(i)=f(j),转(4)。
9) 计算P (i->j) =exp{ -( f(j)-f(i) )/t };
10) 如果Pt(i=>j)>Random(0,1),则i=j,f(i)=f(j)。
11) 转(4)
12) End
13) tk+1=Drop(tk),k=k+1。
14) End
15) 输出结果。
16) 结束。
10. 算法中的问题：
1) 初始温度的选取：
一个合适的初始温度,应保证平稳分布中每一个状态的概率基本相等,也就是接受概率P近似等于1。可选初始温度为1，每次温度上升5%，直到接受概率为0.9为止。
2) 内循环的结束条件,即每个温度状态交换何时结束：
固定长度方法：在每一个温度下,都使用相同的Lk。Lk的选取与具体的问题相关,一般与邻域的大小直接关联,通常选择为问题规模n的一个多项式函数。
3) 外循环的结束条件,即温度下降到什么时候结束：
无变化控制法：如果在相邻的n个温度中,得到的解的指标函数值无任何变化,则说明算法已经收敛。
4) 温度的下降方法：
等比例的下降温度：如每次温度下降5%。
三、 实验结果
1. local_search实验结果：
2. 模拟退火实验结果：
四 local_search实现：
// 实验4：中国邮递员问题
// 输入：中国144个城市数据
// 输出：最短路径序列及路径长度
// 4.1 采用局部搜索算法实现
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=144;
double len=0;
struct Point{
int num,x,y;
double dist(Point &r){
return sqrt((x-r.x)*(x-r.x)+(y-r.y)*(y-r.y));
}
}point[144];
// 生成一个随机路径开始搜索
void init(){
len=0;
// 生成全排列
for(int i=0;i<MAXN;++i){
int pos=rand()%MAXN;
swap(point[pos],point[i]);
}
for(int i=0;i<MAXN-1;++i)
len+=point[i].dist(point[i+1]);
len+=point[0].dist(point[MAXN-1]);
}
void readData(){
freopen("Cities(144).txt","r",stdin);
for(int i=0;i<144;++i)
scanf("%d%d%d",&point[i].num,&point[i].x,&point[i].y);
double ans=0;
}
void localSearch1(){
int times=20000000;
while(times--){
int pos1=rand()%MAXN,pos2=rand()%MAXN;
if(pos1>pos2) swap(pos1,pos2);
if(pos1==pos2 || (pos1==0 && pos2==MAXN-1)) continue;
double offset=point[pos1].dist(point[(pos2+1)%MAXN])+point[pos2].dist(point[(pos1-1+MAXN)%MAXN])-point[pos1].dist(point[(pos1-1+MAXN)%MAXN])-point[pos2].dist(point[(pos2+1)%MAXN]);
if(offset<0){
len+=offset;
while(pos1<pos2) swap(point[pos1++],point[pos2--]);
}
}
}
int main(){
srand((unsigned int)time(NULL));
readData();
init();
localSearch1();
printf("len:\n%f\npath:\n",len);
for(int i=0;i<MAXN;++i)
printf("%d ",point[i].num);
printf("\n");
return 0;
}
五. 模拟退火实现：
// 实验4：中国邮递员问题
// 输入：中国144个城市数据
// 输出：最短路径序列及路径长度
// 4.1 采用局部搜索算法实现
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=144;
const double E=2.718281828459;
double len=0,temperature=1,recent_len[2]={1e12,1e12};
struct Point{
int num,x,y;
double dist(Point &r){
return sqrt((x-r.x)*(x-r.x)+(y-r.y)*(y-r.y));
}
}point[144];
inline double rand0_1(){
return 1.0*rand()/RAND_MAX;
}
double get_receive_rate(){
int receive=0,times=300,t=300;
while(t--){
int pos1=rand()%MAXN,pos2=rand()%MAXN;
if(pos1>pos2) swap(pos1,pos2);
if(pos1==pos2 || (pos1==0 && pos2==MAXN-1)){
++receive;
continue;
}
double offset=point[pos1].dist(point[(pos2+1)%MAXN])+point[pos2].dist(point[(pos1-1+MAXN)%MAXN])-point[pos1].dist(point[(pos1-1+MAXN)%MAXN])-point[pos2].dist(point[(pos2+1)%MAXN]);
if(offset<=0 || pow(E,-offset*1.0/temperature)>=rand0_1())
++receive;
}
return 1.0*receive/times;
}
// 生成一个随机解作为初始解,并计算一个合适的初始温度（使得接受概率大于0.9）
void init(){
len=0;
// 生成全排列
for(int i=0;i<MAXN;++i){
int pos=rand()%MAXN;
swap(point[pos],point[i]);
}
for(int i=0;i<MAXN-1;++i)
len+=point[i].dist(point[i+1]);
len+=point[0].dist(point[MAXN-1]);
while(get_receive_rate()<0.9) temperature*=1.05;
}
void readData(){
freopen("Cities(144).txt","r",stdin);
for(int i=0;i<144;++i)
scanf("%d%d%d",&point[i].num,&point[i].x,&point[i].y);
double ans=0;
}
void anneal(){
int times=1e4;
while(temperature>0.001){
times*=1.01;
int t=times;
// printf("temperature=%f\ttimes=%d\tlen=%f\n",temperature,t,len);
while(t--){
int pos1=rand()%MAXN,pos2=rand()%MAXN;
if(pos1>pos2) swap(pos1,pos2);
if(pos1==pos2 || (pos1==0 && pos2==MAXN-1)) continue;
double offset=point[pos1].dist(point[(pos2+1)%MAXN])+point[pos2].dist(point[(pos1-1+MAXN)%MAXN])-point[pos1].dist(point[(pos1-1+MAXN)%MAXN])-point[pos2].dist(point[(pos2+1)%MAXN]);
if(offset<=0 || pow(E,-offset*1.0/temperature)>=rand0_1()){
len+=offset;
while(pos1<pos2) swap(point[pos1++],point[pos2--]);
}
}
if(len==recent_len[0] && len==recent_len[1]) break;
temperature*=0.98;
recent_len[0]=recent_len[1];
recent_len[1]=len;
}
}
void debug(){
}
int main(){
srand((unsigned int)time(NULL));
readData();
init();
debug();
anneal();
printf("len:\n%f\npath:\n",len);
for(int i=0;i<MAXN;++i)
printf("%d ",point[i].num);
printf("\n");
return 0;
}
