什么?我的计算机跑不动了?精确式VS启发式

简介: 什么?我的计算机跑不动了?精确式VS启发式


现在失去的,在未来会以另一种方式归来。

——短短的路走走停停


微信图片_20220422153512.jpg

大家,好·久·不·见·啦~!

在为期两个月的C++速成班结束后,魔鬼的老师布置了大作业,幸运的是这次的大作业可以选择自己找题目。正好小编最近在学一些启发式算法,所以心地善良的小编就想呀,如果能把作业和推文和学习结合在一起,“learning+working+sharing”的形式岂不是很好吗~所以这次给大家带来了大作业的分享——启发式算法和精确式算法的时间消耗比较


差不多就开始吧!


启发式算法及TSP问题介绍



开始这次小实验之前我们起码要知道什么是启发式算法。


在一些寻找最优解问题中,传统的能够求出最优解的精确式算法(如分支界定、动态规划等)花费的时空过大。启发式算法(heuristic algorithm)是一种能以更快速度找出问题近似最优解的方法。启发式算法通过牺牲一些精度来换取较小的时空消耗,可以看作是解决问题的捷径。


其次,这次小实验问题的载体是老熟人TSP问题。这里再简单介绍一下。

TSP问题(Traveling Salesman Problem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下:


有若干个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次,最后回到出发的城市,问如何事先确定一条最短的线路已保证其旅行的费用最少?


如下图所示:

微信图片_20220422153517.jpg

当然,这次我并不打算用讨厌的美国为例。我们的算例采用柏林52城。

测试数据如下:

微信图片_20220422153519.jpg


算法及代码



在之前关于回溯法的推文中我们曾提到TSP问题,所以这次我们选用的精确式算法依旧是回溯法(我爱ctrl+c)。在启发式算法的选择上,因为小编才刚开始学习,所以把可用的都拿出来比较一下,分别是模拟退火法迭代局部搜索算法

可以点击链接学习这三种算法:

【算法学习】再谈回溯法

【算法进阶】用模拟退火(SA, Simulated Annealing)算法解决旅行商问题

【优化算法】迭代局部搜索算法(Iterated local search)探幽(附C++代码及注释)

(前排怒赞老板的推文,真的是一看就懂,亲测)

代码略微分享一下,因为和老板写的不完全相同(偷偷所一句,老板原先的两段代码都有一丢丢小问题)。可以暂时跳过这一部分,在文末下载代码细看。中间会有些许优化处理并没那么好懂。

代码确实很多,三大段,推荐先跳过。


using namespace std;
int const N=14;  // 城市数量
int Y[N],Ybest[N];
double f1,f2;
int dis[N][N];
int count=0;
// 中国31个城市坐标
double city_pos[N][2] =
    {
{ 565,575 },{ 25,185 },{ 345,750 },{ 945,685 },{ 845,655 },
{ 880,660 },{ 25,230 },{ 525,1000 },{ 580,1175 },{ 650,1130 },
{ 1605,620 },{ 1220,580 },{ 1465,200 },{ 1530,5 },/*
{ 845,680 },{ 725,370 },{ 145,665 },
{ 415,635 },{ 510,875 },{ 560,365 },{ 300,465 },{ 520,585 },{ 480,415 },
{ 835,625 },{ 975,580 },{ 1215,245 },{ 1320,315 },{ 1250,400 },{ 660,180 },
{ 410,250 },{ 420,555 },{ 575,665 },{ 1150,1160 },{ 700,580 },{ 685,595 },
{ 685,610 },{ 770,610 },{ 795,645 },{ 720,635 },{ 760,650 },{ 475,960 },
{ 95,260 },{ 875,920 },{ 700,500 },{ 555,815 },{ 830,485 },{ 1170,65 },
{ 830,610 },{ 605,625 },{ 595,360 },{ 1340,725 },{ 1740,245 }*/
  };
//函数声明
double distance(double *,double *); // 计算两个城市距离
void swap(int&,int&); //交换函数 
double testtime();
void setdis();
void backtrack(int);   
double distance(double *p1,double *p2)  //计算两点间距离 
{
  double dist=0;
  dist=sqrt(pow(p1[0]-p2[0],2)+pow(p1[1]-p2[1],2));
  return dist;
}
void setdis()
{
  for(int i=0;i<N;i++)
     for (int j=0;j<i;j++)
         dis[i][j]=dis[j][i]=distance(city_pos[i],city_pos[j]);
}
 void swap(int&a,int&b)  //交换 函数
{
   int temp;
   temp=a;
   a=b;
   b=temp;
 }
 void backtrack(int t)   
{
   if (t==N)
     { //判断边界。
       if (f2>f1+dis[Y[t-1]][Y[0]]||f2==0) 
       {
         memcpy(Ybest,Y,N*sizeof(int));
         f2=f1+dis[Y[t-1]][Y[0]];
         return;
    }
     }
  else
     {
    for (int j=t;j<N;j++)//从t开始,相当于第一轮没有交换 
       {
         if(f2>f1 || f2==0)
         {
             swap(Y[t],Y[j]);
             f1+=dis[Y[t]][Y[t-1]];
             backtrack(t+1);
             f1-=dis[Y[t]][Y[t-1]];
             swap(Y[t],Y[j]);
      }
       }
     }
     count++;
 }
 double testtime()
{
    time_t start,finish;
    start = clock(); // 程序运行开始计时
    setdis();
    for (int i=0;i<N;i++)
      Y[i]=i;
   backtrack(0);
    cout<<"回溯算法。测试点数"<<N<<"共迭代"<<count<<"次,得到的TSP最优距离为"<<f2<<"路径为"<<endl;
   for(int j=0;j<N;j++)  // 输出最优路径
   {
     if (j==0) 
      cout<<Ybest[j];
     else
       cout<<"--->"<<Ybest[j];
   }
    finish = clock(); // 程序结束
    double duration = ((double)(finish-start))/CLOCKS_PER_SEC; // 计算时间
    cout<<endl;
    cout<<"程序运行耗时:"<<duration<<"秒"<<endl;
    return duration;
 }
 int main()
{   
    srand((unsigned)time(NULL)); //初始化随机数种子
    double time=testtime();
   cout<<"test:  time:"<<time<<";  result:"<<f2<<endl;
   int a;
   cin>>a;
   return 0;
 }


//使用模拟退火算法(SA)求解TSP问题 By ZLL.HUST
//参考自短短的路走走停停 模拟退火代码 参见微信公众号程序猿声 
#include <iostream> 
#include <string>
#include <time.h>
#include <cmath>
#include <stdlib.h>
using namespace std;
double const T0=50000.0; // 初始温度
double const T_min=1e-8;
double const q=0.98;   // 退火系数
double const K=1;  //公式中的常数K 
int const L=1000;  // 每个温度时的迭代次数,即链长
int const N=52;  // 城市数量
// 中国31个城市坐标
double city_pos[N][2] =
    {
    { 565,575 },{ 25,185 },{ 345,750 },{ 945,685 },{ 845,655 },
{ 880,660 },{ 25,230 },{ 525,1000 },{ 580,1175 },{ 650,1130 },{ 1605,620 },
{ 1220,580 },{ 1465,200 },{ 1530,5 },{ 845,680 },{ 725,370 },{ 145,665 },
{ 415,635 },{ 510,875 },{ 560,365 },{ 300,465 },{ 520,585 },{ 480,415 },
{ 835,625 },{ 975,580 },{ 1215,245 },{ 1320,315 },{ 1250,400 },{ 660,180 },
{ 410,250 },{ 420,555 },{ 575,665 },{ 1150,1160 },{ 700,580 },{ 685,595 },
{ 685,610 },{ 770,610 },{ 795,645 },{ 720,635 },{ 760,650 },{ 475,960 },
{ 95,260 },{ 875,920 },{ 700,500 },{ 555,815 },{ 830,485 },{ 1170,65 },
{ 830,610 },{ 605,625 },{ 595,360 },{ 1340,725 },{ 1740,245 }
  };
//函数声明
double distance(double *,double *); // 计算两个城市距离
double path_len(int *);  // 计算路径长度
double SA(); //Simulated Annealing模拟退火 
void swap(int&,int&); //交换函数 
void create_new(int *);  // 产生新解
void testtime(double *,double *,int,int *);
double distance(double *p1,double *p2)  //计算两点间距离 
{
  double dis=0;
  dis=sqrt(pow(p1[0]-p2[0],2)+pow(p1[1]-p2[1],2));
  return dis;
}
double path_len(int *city_list) //计算路径长度 
{
  double path=0;
  for (int i=0;i<(N-1);i++)
    path+=distance(city_pos[city_list[i]],city_pos[city_list[i+1]]);
  //学长的代码少了下面一行,没有回到原城市,所以写错了哦~! 
  path+=distance(city_pos[city_list[0]],city_pos[city_list[N-1]]) ;
  return path;
}
 void swap(int&a,int&b)  //交换 函数
{
   int temp;
   temp=a;
   a=b;
   b=temp;
 }
void create_new(int *city_list)   //产生新解
{
   int i=rand()%N;
   int j=rand()%N;
  while(j==i)
    j=rand()%N;
  swap(city_list[i],city_list[j]);
 }
double SA(int *bestpath)
{
   int count=0;
   int Ynew[N]; // 用于存放一个解
   int Ybest[N];
   for (int i=0;i<N;i++)
      Ybest[i]=i;
   memcpy(Ynew,Ybest,N*sizeof(int));
   double f1;
  double f2=path_len(Ybest); 
  double T=T0;
   while(T>T_min)
   {
     for (int i=0;i<L;i++)
    {
    create_new(Ynew);
     f1=path_len(Ynew);
     double de=f1-f2;
     if (de<0)
     {
        memcpy(Ybest,Ynew,N*sizeof(int));
       f2=f1;
       }
     else 
     {
       double r = ((double)rand())/(RAND_MAX);
       if(exp(de/(K*T))<r)
       {
           memcpy(Ybest,Ynew,N*sizeof(int));
           f2=f1;
         }
         else
            memcpy(Ynew,Ybest,N*sizeof(int));
     }
     }
     T*=q;
       count++;
   }
   cout<<"模拟退火算法,初始温度T0="<<T0<<",降温系数q="<<q<<",每个温度迭代"<<L<<"次,共降温"<<count<<"次,得到的TSP最优距离为"<<f2<<"路径为"<<endl;
   for(int j=0;j<N;j++)  // 输出最优路径
   {
     if (j==0) 
      cout<<Ybest[j];
     else
       cout<<"--->"<<Ybest[j];
   }
   int bestpathlong=path_len(bestpath);
   if (f2<bestpathlong)
      for (int i=0;i<N;i++)
         bestpath[i]=Ybest[i];
   return f2;
 }
 void testtime(double *time,double *result,int num,int *bestpath)
{
    time_t start,finish;
    start = clock(); // 程序运行开始计时
    result[num]=SA(bestpath);
    finish = clock(); // 退火过程结束
    double duration = ((double)(finish-start))/CLOCKS_PER_SEC; // 计算时间
    cout<<endl;
    cout<<"程序运行耗时:"<<duration<<"秒."<<endl;
    time[num]=duration;
 }
 int main()
{   
    srand((unsigned)time(NULL)); //初始化随机数种子
   double time[10],result[10];
   int bestpath[N];
   for(int i=0;i<N;i++)  // 初始化总最优路径
     bestpath[i]=i;
   for (int i=0;i<10;i++)
   {
      cout<<"test"<<i+1<<":"<<endl;
      testtime(time,result,i,bestpath);
     }
   for (int i=0;i<10;i++)
      cout<<"test"<<i+1<<"\t"<<":  time:"<<time[i]<<"\t"<<";  result:"<<result[i]<<endl;
   cout<<endl<<"最优路径为:"<<endl;
  for(int i=0;i<N;i++)  // 输出最优路径
   {
     if (i==0) 
      cout<<bestpath[i];
     else
       cout<<"--->"<<bestpath[i];
   }
  int a;
  cin>>a; 
   return 0;
 }
////////////////////////
//TSP问题 迭代局部搜索求解代码
//代码基于老板代码的框架,并大规模参考 
//作者:ZLL.HUST
//时间:2019-11-28
////////////////////////
#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <windows.h>
#include <memory.h>
#include <string.h>
#include <iomanip>
using namespace std;
int const CITY_SIZE=52; //城市数量
//城市坐标
typedef class candidate
{
  public:
    int x;
    int y;
}city, CITIES;
//优化值
int Delta[CITY_SIZE][CITY_SIZE]; 
//解决方案
typedef class Solution
{
  public:
    int permutation[CITY_SIZE]; //城市排列
    int cost;                        //该排列对应的总路线长度
}SOLUTION;
// 计算邻域操作优化值 
int calc_delta(int i, int k, int *tmp, CITIES * cities);
//计算两个城市间距离
int distance_2city(city c1, city c2);
//根据产生的城市序列,计算旅游总距离
int cost_total(int * cities_permutation, CITIES * cities);
//获取随机城市排列, 用于产生初始解
void random_permutation(vector <int> &cities_permutation); //(int * cities_permutation)
//颠倒数组中下标begin到end的元素位置, 用于two_opt邻域动作
void swap_element(int *p, int begin, int end);
//邻域动作 反转index_i <-> index_j 间的元素
void two_opt_swap(int *cities_permutation, int *new_cities_permutation, int index_i, int index_j);
//本地局部搜索,边界条件 max_no_improve
void local_search(SOLUTION & best_solution, CITIES * cities, int max_no_improve);
//判断接受准则
bool AcceptanceCriterion(int *cities_permutation, int *old_cities_permutation, CITIES * cities);
//将城市序列分成4块,然后按块重新打乱顺序。
//用于扰动函数
void double_bridge_move(int *cities_permutation, int * new_cities_permutation,CITIES * cities);
//扰动
void perturbation(CITIES * cities, SOLUTION &best_solution, SOLUTION &current_solution);
//迭代搜索
void iterated_local_search(SOLUTION & best_solution, CITIES * cities, int max_iterations, int max_no_improve);
// 更新Delta 
void Update(int i, int k,  int *tmp, CITIES * cities);
//Debug
void test(); 
//berlin52城市坐标,最优解7542好像(这貌似是精确的最优解,我得出的结论是7526) 
CITIES berlin52[CITY_SIZE] = { 
{ 565,575 },{ 25,185 },{ 345,750 },{ 945,685 },{ 845,655 },
{ 880,660 },{ 25,230 },{ 525,1000 },{ 580,1175 },{ 650,1130 },
{ 1605,620 },{ 1220,580 },{ 1465,200 },{ 1530,5 },
{ 845,680 },{ 725,370 },{ 145,665 },
{ 415,635 },{ 510,875 },{ 560,365 },{ 300,465 },{ 520,585 },{ 480,415 },
{ 835,625 },{ 975,580 },{ 1215,245 },{ 1320,315 },{ 1250,400 },{ 660,180 },
{ 410,250 },{ 420,555 },{ 575,665 },{ 1150,1160 },{ 700,580 },{ 685,595 },
{ 685,610 },{ 770,610 },{ 795,645 },{ 720,635 },{ 760,650 },{ 475,960 },
{ 95,260 },{ 875,920 },{ 700,500 },{ 555,815 },{ 830,485 },{ 1170,65 },
{ 830,610 },{ 605,625 },{ 595,360 },{ 1340,725 },{ 1740,245 }
};
int main()
{
  srand((unsigned)time(NULL)); //初始化随机数种子
  time_t start,finish;
    start = clock(); // 程序运行开始计时
    int max_iterations = 600;
    int max_no_improve = 50;
    SOLUTION best_solution;
    iterated_local_search(best_solution, berlin52, max_iterations, max_no_improve);
    cout << endl<<endl<<"搜索完成! 最优路线总长度 = " << best_solution.cost << endl;
    cout << "最优访问城市序列如下:" << endl;
    for (int i = 0; i < CITY_SIZE;i++)
        cout << best_solution.permutation[i]<<"\t";
  finish = clock(); // 退火过程结束
    double duration = ((double)(finish-start))/CLOCKS_PER_SEC; // 计算时间
    cout<<endl;
    cout<<"程序运行耗时:"<<duration<<"秒."<<endl;
    return 0;
}
void test()
{
  int jinque[10]={0,4,5,3,9,8,7,2,6,1};
  cout<<cost_total(jinque,berlin52)<<endl;
  int moni[10]={9,3,5,4,0,1,6,2,7,8};
  cout<<cost_total(moni,berlin52)<<endl;
}
//迭代搜索
void iterated_local_search(SOLUTION & best_solution, CITIES * cities, int max_iterations, int max_no_improve)
{
  SOLUTION current_solution;
  vector <int> cities_permutation;
  random_permutation(cities_permutation);
  for (int i=0;i<CITY_SIZE;i++)
     best_solution.permutation[i]=cities_permutation[i];
  best_solution.cost=cost_total(best_solution.permutation, cities);
  local_search(best_solution, cities, max_no_improve);
  //cout<<"best_solution.cost"<<best_solution.cost<<endl;
  for(int i=0;i<max_iterations;i++)
  {
    perturbation(cities, best_solution, current_solution);
    local_search(current_solution, cities, max_no_improve);
    if(current_solution.cost<best_solution.cost)
       best_solution=current_solution;
    cout << setw(13) << setiosflags(ios::left) <<"迭代搜索 " << i << " 次\t" << "最优解 = " << best_solution.cost << " 当前解 = " << current_solution.cost << endl;
  }
}
//计算两个城市间距离
int distance_2city(city c1, city c2)
{
  double dis=0;
  dis=sqrt(pow(c1.x-c2.x,2)+pow(c1.y-c2.y,2));
  return dis;
}
//根据产生的城市序列,计算旅游总距离
int cost_total(int * cities_permutation, CITIES * cities)
{
  double path=0;
  for (int i=0;i<(CITY_SIZE-1);i++)
    path+=distance_2city(cities[cities_permutation[i]],cities[cities_permutation[i+1]]);
  path+=distance_2city(cities[cities_permutation[0]],cities[cities_permutation[CITY_SIZE-1]]);
  return path;
}
//获取随机城市排列, 用于产生初始解(learning form CSDN)
void random_permutation(vector <int> &cities_permutation) //(int * cities_permutation)   
{
  vector <int> cities_permutation0(CITY_SIZE);
    for (int i = 0; i < CITY_SIZE; i++)
        cities_permutation0[i]=i;
   for (int i=CITY_SIZE;i>0;i--) 
   {
        // 选中的随机下标
        int index = rand()%i;
        // 根据选中的下标将原数组选中的元素push到新数组
        cities_permutation.push_back(cities_permutation0[index]);
        // 将原数组中选中的元素剔除
        cities_permutation0.erase(cities_permutation0.begin()+index);
    }
}
//颠倒数组中下标begin到end的元素位置
void swap_element(int *p, int begin, int end)
{
    int temp;
    while (begin < end)
    {
        temp = p[begin];
        p[begin] = p[end];
        p[end] = temp;
        begin++;
        end--;
    }
}
//邻域动作 反转index_i <-> index_j 间的元素
void two_opt_swap(int *cities_permutation, int *new_cities_permutation, int index_i, int index_j)
{
    for (int i = 0; i < CITY_SIZE; i++)
        new_cities_permutation[i] = cities_permutation[i];
    swap_element(new_cities_permutation, index_i, index_j);
}
//本地局部搜索,找出局部最优解,边界条件 max_no_improve
void local_search(SOLUTION & best_solution, CITIES * cities, int max_no_improve)
{
    int count = 0;
    int inital_cost = best_solution.cost; //初始花费
    int now_cost = 0;
    SOLUTION new_solution; 
  for (int i = 0; i < CITY_SIZE - 1; i++)
       for (int k = i + 1; k < CITY_SIZE; k++) //注意Delta数组中行的数字必定大于列的数字 
      Delta[i][k] = calc_delta(i, k, best_solution.permutation, cities); 
  int deadprotect=0;
    do
    {
        //枚举排列
        for (int i = 0; i < CITY_SIZE - 1; i++)
        {
            for (int k = i + 1; k < CITY_SIZE; k++)
            {
                //邻域动作
                two_opt_swap(best_solution.permutation, new_solution.permutation, i, k);
        now_cost = inital_cost + Delta[i][k];
                new_solution.cost = now_cost;
                if (new_solution.cost < best_solution.cost)
                {
                    count = 0; //better cost found, so reset.we need to found a best solution in an area(邻域)
                    best_solution = new_solution;
                    inital_cost = best_solution.cost;
                    Update(i, k, best_solution.permutation, cities);
                }
            }
        }
        count++;
        deadprotect++;
        if (deadprotect==4*max_no_improve) break;
    //cout<<count<<endl;
    } while (count <= max_no_improve);
}
// 计算邻域操作优化值 
int calc_delta(int i, int k, int *tmp, CITIES * cities)
{
  /*
                以下计算说明:
                对于每个方案,翻转以后没必要再次重新计算总距离
                只需要在翻转的头尾做个小小处理
                比如:
                有城市序列   1-2-3-4-5 总距离 = d12 + d23 + d34 + d45 + d51 = A
                翻转后的序列 1-4-3-2-5 总距离 = d14 + d43 + d32 + d25 + d51 = B
                由于 dij 与 dji是一样的,所以B也可以表示成 B = A - d12 - d45 + d14 + d25
                下面的优化就是基于这种原理
    */
    //学长这里疯狂分类凑行数吗2333 
    int delta=0;
    if((i==0)&&(k==CITY_SIZE-1))
       delta=0;
    else
  {
    int i2=(i-1+CITY_SIZE)%CITY_SIZE;
        int k2=(k+1)%CITY_SIZE; 
        delta = 0
                - distance_2city(cities[tmp[i2]], cities[tmp[i]])
                + distance_2city(cities[tmp[i2]], cities[tmp[k]])
                - distance_2city(cities[tmp[k]], cities[tmp[k2]])
                + distance_2city(cities[tmp[i]], cities[tmp[k2]]);
  }
    return delta;
}
// 更新Delta 
void Update(int i, int k,  int *tmp, CITIES * cities)
{
  /*小编注:这是一个计算每次领域动作后路径长度改变值的小优化,在测试中我们暂时忽略这个优化。 
  去重处理,对于Delta数组来说,对于城市序列1-2-3-4-5-6-7-8-9-10,如果对3-5应用了邻域操作2-opt , 事实上对于
  7-10之间的距离是不需要重复计算的,即后半部分是不变的。 所以用Delta提前预处理一下。
  当然由于这里的计算本身是O(1) 的,事实上并没有带来时间复杂度的减少(更新操作反而增加了复杂度) 
  如果delta计算 是O(n)的,这种去重操作效果是明显的。 
  if (i && (k != (CITY_SIZE - 1)))
  {   // 如果不是边界,更新(i-1, k + 1)之间的 
    i --; k ++;
    for (int j = i; j <= k; j ++)
      for (int l = j + 1; l < CITY_SIZE; l ++)
        Delta[j][l] = calc_delta(j, l, tmp, cities);
    for (int j = 0; j < k; j ++)
    {
      for (int l = i; l <= k; l ++)
      {
        if (j >= l) continue;
        Delta[j][l] = calc_delta(j, l, tmp, cities);
      }
    }
  }
  // else if ((!i)&&(k!=(CITY_SIZE-1))){} 
  // else if (i&&(k==(CITY_SIZE-1))){} 
  //本想在这里加入两个elseif,把两种情况都优化一下,后来想想没必要,其实这都是很小的一部分  
  else*/
  {
    for (i = 0; i < CITY_SIZE - 1; i++)
          for (k = i + 1; k < CITY_SIZE; k++)
        Delta[i][k] = calc_delta(i, k, tmp, cities);
  }
}
//判断接受准则
bool AcceptanceCriterion(int *cities_permutation, int *new_cities_permutation, CITIES * cities)
{
  int AcceptLimite=500;
  int c1=cost_total(cities_permutation, cities);
  int c2=cost_total(new_cities_permutation, cities)-500;
  if (c1<c2)
    return false;
  else
    return true;
}
//将城市序列分成4块,然后按块重新打乱顺序。
//用于扰动函数
void double_bridge_move(int *cities_permutation, int * new_cities_permutation,CITIES * cities)
{
  int pos1=rand()%(CITY_SIZE/3);
  int pos2=rand()%(CITY_SIZE/3)+CITY_SIZE/3;
  int pos3=rand()%(CITY_SIZE/3)+(CITY_SIZE/3)*2;
  int deadprotect=0;
  do
  {
    int i=0;
      //写完才发现老板也是反向,哈哈,英雄所见略同啊! 
      for (int j=pos3;j<CITY_SIZE;j++)
      {
        new_cities_permutation[i]=cities_permutation[j];
        i++;
      }
      for (int j=pos2;j<pos3;j++)
      {
        new_cities_permutation[i]=cities_permutation[j];
        i++;
      }
      for (int j=pos1;j<pos2;j++)
       {
        new_cities_permutation[i]=cities_permutation[j];
        i++;
      }
      for (int j=0;j<pos1;j++)
      {
        new_cities_permutation[i]=cities_permutation[j];
        i++;
      }
      deadprotect++;
      //cout<<deadprotect;
      //cout<<endl;
      if (deadprotect==5) break;
  //学长的代码在这里如果没有accept就直接用原数据,所以不需要deadprotect。 
    }while(AcceptanceCriterion(cities_permutation, new_cities_permutation, cities));
}
//扰动
void perturbation(CITIES * cities, SOLUTION &best_solution, SOLUTION &current_solution)
{
  double_bridge_move(best_solution.permutation, current_solution.permutation,cities);
  current_solution.cost=cost_total(current_solution.permutation, cities);
}

(小错误见注释)

霍霍,万事俱备只欠东风啦!马上开始我们的测试!

微信图片_20220422153523.jpg


测试



先用回溯法跑一跑中国31城的算例:

微信图片_20220422153527.jpg

发现没有输出。为什么呢?

微信图片_20220422153530.jpg

咳咳,并不是程序错了。而是因为回溯法的时间复杂度是指数级的,当n=31时已经是很大的数字了,所以程序一直在跑呀跑呀却出不来。

 

调整城市的数量,砍到13城左右。

微信图片_20220422153533.jpg

这回总算是跑动啦。

 

接下来看启发式算法的表现:

微信图片_20220422153536.jpg

(迭代局部搜索,柏林52城问题)

微信图片_20220422153539.jpg

(模拟退火,柏林52问题)

31城、52城都能轻松跑出来。并且耗时都不长,最长不过21秒。

经过小编的多次试验,我们给出三种方法的比较折线图:

微信图片_20220422153541.jpg

(纵坐标单位为秒)

微信图片_20220422153544.jpg

(横坐标表结点数)

微信图片_20220422153546.jpg


从数据中我们可以看出,回溯法的耗时是指数级的,两种启发式算法则是线性增长的。这与理论是吻合的。


从柏林52城的已知解为7542以及迭代局部搜索得出的解7526(应该是由于精度问题导致的差异,我是用整数型表示距离),以及以上的比较结果看来,启发式算法还是比较精确的。

 

当然我们会发现两种启发式算法所用的时间和精度仍有差别。

时间上的差异是因为人为制定的搜索次数不同,比如模拟退火的退火系数,迭代局部搜索的迭代次数,这些是人为设置的,自然在速度上有差别。比方说我这里设置的模拟退火法明显次数较少,4秒、7秒内就跑完一次搜索(我一次测试了10组);而迭代局部用了7秒、21秒。


至于精度,我认为是算法和代码的差异导致的。在模拟退火中每次都在同一邻域的周围搜索,代码中跳跃的幅度也不大,所以在数据较大时(52城)搜索多次也没有太大的差别,而13城以内比较精确;而迭代局部搜索有一个邻域间跳跃的过程,在此之后进行邻域内搜索最优解,找到整体最优的可能性就大大提高了。


总结来说,在稍微深入一些的学习中,启发式算法带来巨大的收益相信这也是老板们要求小编学习的原因啦。


第一次跑回溯法跑不出的时候小编也以为是程序错了。第一次认识到,原来强大无比的计算机也有算不出来的时候。之前可一直不敢相信呢。所以凡事还是都需要一点脑子,不能一昧地穷举。
引用老板的一句话结尾:从上面的过程我们可以看出,模拟退火算法是一种随机算法,它有一定的概率能求得全局最优解,但不一定用模拟退火算法可以较快速地找出问题的近似最优解。不过,在小编不成熟的眼光看来,人生亦有相似之处。有时候可能放弃眼前短浅的利益,最终才可能获得更好的未来。现在失去的,在未来会以另一种方式归来。
代码链接: https://pan.baidu.com/s/154PynBJHbfB63eAPl8viaA 提取码: au1f

相关文章
|
7月前
|
SQL 开发框架 算法
【MFAC】基于偏格式动态线性化的无模型自适应控制
【MFAC】基于偏格式动态线性化的无模型自适应控制
|
26天前
|
算法
基于改进自适应分段线性近似(IAPLA)的微分方程数值解法研究: 从简单动力系统到混沌系统的应用分析
IAPLA方法为复杂动力系统的数值模拟提供了一个灵活、高效且易于实现的框架,在众多实际应用中可以作为现有数值求解器的有效替代方案。
33 2
基于改进自适应分段线性近似(IAPLA)的微分方程数值解法研究: 从简单动力系统到混沌系统的应用分析
|
机器学习/深度学习 数据采集 算法
序列模型算法在上网行为管理中的应用:精度提升的新途径
当我们谈论如何通过序列模型算法来提升上网行为管理的精度时,其实是一种超级有用的工具,可以帮助我们更轻松地识别和管理用户的行为,让网络管理员更加高效地监管网络活动。下面是一些有趣的方法,可以通过序列模型算法来提高上网行为管理的准确性——
181 1
|
数据采集 监控 算法
【状态估计】基于二进制粒子群优化 (BPSO) 求解最佳 PMU优化配置研究【IEEE30、39、57、118节点】(Matlab代码实现)
【状态估计】基于二进制粒子群优化 (BPSO) 求解最佳 PMU优化配置研究【IEEE30、39、57、118节点】(Matlab代码实现)
【状态估计】基于二进制粒子群优化 (BPSO) 求解最佳 PMU优化配置研究【IEEE30、39、57、118节点】(Matlab代码实现)
|
机器学习/深度学习 算法
Bandit算法,UCB算法与β分布的关系,以及强化学习策略选择随机性研究
Bandit算法,UCB算法与β分布的关系,以及强化学习策略选择随机性研究
120 0
|
安全 调度
多源动态最优潮流的分布鲁棒优化方法(IEEE118节点)(Matlab代码实现)
多源动态最优潮流的分布鲁棒优化方法(IEEE118节点)(Matlab代码实现)
149 0
|
机器学习/深度学习 存储 网络架构
比量子化学方法快六个数量级,一种基于绝热状态的绝热人工神经网络方法,可加速对偶氮苯衍生物及此类分子的模拟
比量子化学方法快六个数量级,一种基于绝热状态的绝热人工神经网络方法,可加速对偶氮苯衍生物及此类分子的模拟
121 0
|
机器学习/深度学习 传感器 算法
【蝴蝶算法】基于随机惯性权重策略+最优邻域扰动策略+动态转换概率策略的蝴蝶算法求解单目标优化问题附matlab代码IBOA
【蝴蝶算法】基于随机惯性权重策略+最优邻域扰动策略+动态转换概率策略的蝴蝶算法求解单目标优化问题附matlab代码IBOA
|
决策智能
运筹优化学习02:Lingo求解带容量约束的车辆路径问题(CVRP)(下)
运筹优化学习02:Lingo求解带容量约束的车辆路径问题(CVRP)
|
决策智能
运筹优化学习02:Lingo求解带容量约束的车辆路径问题(CVRP)(上)
运筹优化学习02:Lingo求解带容量约束的车辆路径问题(CVRP)
运筹优化学习02:Lingo求解带容量约束的车辆路径问题(CVRP)(上)