巡回セールスマン問題を焼きなまし法で解く
Posted: 2016年6月27日(月) 23:45
巡回セールスマン問題を焼きなまし法を用いて解こうと考えています。
問題はこちらのサイトの
http://elib.zib.de/pub/Packages/mp-test ... index.html
a280.tspを使用しています。
実行してみた結果なのですが、
と最適解とは程遠い結果となってしまいます。
ベストツアーを入れ替えた回数 94.000000
確率遷移をした回数 13500000.000000
20762.924838
ベストツアーを入れ替える回数を増やせば解決するように思うのですが
上手くいきません。
どうかお力をお貸しください。
よろしくお願いします。
問題はこちらのサイトの
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);
}