巡回セールスマン問題を焼きなまし法で解く

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
さざなみ

巡回セールスマン問題を焼きなまし法で解く

#1

投稿記事 by さざなみ » 7年前

巡回セールスマン問題を焼きなまし法を用いて解こうと考えています。

問題はこちらのサイトの
http://elib.zib.de/pub/Packages/mp-test ... index.html
a280.tspを使用しています。

実行してみた結果なのですが、

と最適解とは程遠い結果となってしまいます。
 ベストツアーを入れ替えた回数 94.000000
 確率遷移をした回数 13500000.000000
 20762.924838
ベストツアーを入れ替える回数を増やせば解決するように思うのですが
上手くいきません。

どうかお力をお貸しください。
よろしくお願いします。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define MAX_N 10000   // 点の数の最大値
#define INF 100000000 // 無限大の定義
#define EPSILON 0.00000001 //ε 小さい正の値
#define SWAP(a,b){int temp; temp=(a); (a)=(b); (b)=temp; }

//都市の座標を入れるための構造体
struct CELL{
  int data;
  struct CELL *next;
};

struct point {
  int x;
  int y;
};

// pとq の間の距離を計算
double dist(struct point p, struct point q) {  
  return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}

//順回路長を表示する関数
double tour_length(struct point p[MAX_N], int n, int tour[MAX_N]) {
  int i;
  double sum=0.0;
  for(i=0;i<n;i++) sum+=dist(p[tour[i]],p[tour[(i+1)%n]]);
  return sum;// 総距離が関数の戻り値
}

//問題ファイルを読み込む関数
void read_tsp_data(char *filename, struct point p[MAX_N],int *np) {
  FILE *fp;
  char buff[100];
  int i;

  if ((fp=fopen(filename,"rt")) == NULL) {// 指定ファイルを読み込み用に開く
    fprintf(stderr,"Error: File %s open failed.\n",filename);
    exit(0);
  }   

  while((fgets(buff,sizeof(buff),fp)!=NULL)   // DIMENSION で始まる行に出会う
	&&(strncmp("DIMENSION",buff,9)!=0)) ; // まで読み飛ばす. 
  sscanf(buff,"DIMENSION : %d",np);           // 点の数 *np を読み込む

  while((fgets(buff,sizeof(buff),fp)!=NULL)   // NODE_COORD_SECTIONで始まる
	&&(strncmp("NODE_COORD_SECTION",buff,18)!=0)) ; // 行に出会うまで, 
                                                        // 読み飛ばす. 
  for(i=0;i<*np;i++) {                       // i=0 から i=(*np)-1まで
    if(fgets(buff,sizeof(buff),fp)!=NULL) 
      sscanf(buff,"%*d %d %d",&(p[i].x),&(p[i].y)); // i番目の点の座標を読み込む
  }                                 

  fclose(fp);
}


//SA内の温度の関数
double temperature(double alpha, double s_t){
  int i;
  double t;
  
  s_t = alpha*s_t;
  
  return s_t;
}


//SA内の確率遷移に使う関数
double probability(double best_length, double n_length, double t){
  if(n_length < best_length){
    return 1;
  }else{
    return exp((best_length-n_length)/t);
  }
}


//SA法の関数
void sa(struct point p[MAX_N], int n, int tour[MAX_N]){

  double s_t=100, e_t=0.1;
  int i,j,t,k,x,ransuu1,ransuu2;
  double kakuritsu;
  double alpha = 0.95, max_step = 100000, step;

  double kaunt=0,kaunt2=0;

  int best_tour[MAX_N], n_tour[MAX_N], t_tour[MAX_N],c_tour[MAX_N],visited[MAX_N];
  double best_length, n_length, t_length, c_length;
    
    
  srand((unsigned int)time(NULL));
  
  //ランダムに順回路を作る
  for(i=0; i<n; i++){
    visited[i] = 0;
  }
  i = 0;
  do{
    j = rand()%n;
    if(visited[j] == 0){
      tour[i] = j;
      visited[j] = 1;
      i++;
    }
  }while(i != n);
  
  //現時点で最も短いツアーとして保存
  for(i=0; i<n; i++){
    best_tour[i] = tour[i];
  }
  best_length = tour_length(p,n,best_tour);
  
  //都市入れ替え用にもうひとつツアーを作る
  for(i=0; i<n; i++){
    n_tour[i] = best_tour[i];
  }
   
  
  do{
    for(step=0; step<max_step; step++){
     
      //このループ内で作ったツアーの中で最も短い順回路長を保存する  
      c_length = INF;
    
      //都市をランダムに入れ替える
      for(x=0; x<10; x++){
        //乱数作る
        ransuu1 = rand()%(n-1);
        do{
          ransuu2 = rand()%(n-1);
        }while(ransuu1 == ransuu2);
    
        //適当な2箇所の2-opt
        if(ransuu1 < ransuu2){
          while(ransuu1 < ransuu2){
            SWAP(n_tour[ransuu1], n_tour[ransuu2]);
            ransuu1++; ransuu2--;
          } 
        }else{
          while(ransuu2 < ransuu2){
            SWAP(n_tour[ransuu2], n_tour[ransuu1]);
            ransuu2++; ransuu1--;
          }
        }
      
        //このループ内での最短のツアーを保存する
        if(c_length > tour_length(p,n,n_tour)){  
          for(i=0; i<n; i++){
            c_tour[i] = n_tour[i];
          }
          c_length = tour_length(p,n,n_tour);
        }   
      } 
      
      //順回路の比較
      if(c_length < best_length){
        best_length = c_length;
        for(i=0; i<n; i++){
          best_tour[i] = c_tour[i];
          n_tour[i] = c_tour[i];
        }
        kaunt++;
      }  
  
      //確率遷移
      kakuritsu = probability(best_length, c_length, s_t);
      if(rand()/RAND_MAX <= kakuritsu){
        for(i=0; i<n; i++){
          n_tour[i] = c_tour[i];
        }
        kaunt2++;
      } 
    
    }
  
    //温度変更
    s_t = temperature(alpha,s_t);
  }while(s_t>e_t);

  printf("ベストツアーを入れ替えた回数 ");
  printf("%f\n",kaunt);
  printf("確率遷移した回数 ");
  printf("%f\n",kaunt2);

  for(i=0; i<n; i++){
    tour[i] = best_tour[i];
  }
}


//順回路をファイルに書き出す関数
void write_tour_data(char *filename, int n, int tour[MAX_N]){
  FILE *fp; 
  int i;
 
 // 構築した巡回路をfilenameという名前のファイルに書き出すためにopen
  if((fp=fopen(filename,"wt"))==NULL){ 
    fprintf(stderr,"Error: File %s open failed.\n",filename);
    exit(EXIT_FAILURE);
  }
  fprintf(fp,"%d\n",n);
  for(i=0;i<n; i++){
   fprintf(fp,"%d ",tour[i]);
  }
  fprintf(fp,"\n");
  fclose(fp);
}


main(int argc, char *argv[]) {
  int  n;                   // 点の数 
  struct point  p[MAX_N];   // 各点の座標を表す配列 
  int tour[MAX_N];   // 巡回路を表現する配列

  if(argc != 2) {
    fprintf(stderr,"Usage: %s <tsp_filename>\n",argv[0]);
    exit(EXIT_FAILURE);
  }

  // 点の数と各点の座標を1番目のコマンドライン引数で指定されたファイルから読み込む
  read_tsp_data(argv[1],p, &n);

  //Simulated Annealing法
  sa(p,n,tour);
  //順回路長表示
  printf("%lf\n",tour_length(p,n,tour));
  // 巡回路をテキストファイルとして出力
  write_tour_data("tour.dat",n,tour);

  exit(EXIT_SUCCESS);
}

“C言語何でも質問掲示板” へ戻る