#author("2018-11-21T11:17:30+09:00","","")
#author("2018-11-21T11:17:50+09:00","","")
[[卒論]]

[[参考サイト:MPI並列プログラミング:http://www.matlab.nitech.ac.jp/~kazu-k/mpi.html]]

プログラムの説明(並列GA)
#ref(mpi.ppt)

 #include <stdio.h>
 #include <stdlib.h>             /* rand() */
 #include <time.h>               /* srand() */
 #include "mpi.h"

 #define NODE      50            /* 都市の数 */
 #define MAX_DIST  30            /* 都市間の距離の最大値 */
 #define GENOM     200           /* 遺伝子数 */
 #define LIMIT     100000        /* 計算回数 */
 #define EVOLUTION 1             /* 突然変異発生確率[%] */

 #define MIG_INTERVAL 1000       /* 移住間隔[世代] */
 #define MIG_RATE     15         /* 移住率[%] */

 #define DEBUG1    0             /* 関数確認用 */
 #define DEBUG2    0             /* 経路が正しいかどうか確認 */
 #define WRITEFILE 1             /* ファイルへの書き込み用の出力 */

 typedef struct {
   double dist[NODE];            /* town[now].dist[go] */
   int    flag;                  /* 訪問確認用旗 */
 }  TOWN;
 TOWN town[NODE];

 typedef struct {
   double distance;              /* 距離 */
   int    route[NODE+1];         /* 経路 */
   int    flag;                  /* 旗 */
 }  RESULT;
 RESULT result[GENOM];


 int    champ = 0;
 double fast = NODE * MAX_DIST;

 void func(void);                /* 母集団生成 */
 void makelist(void);            /* 都市間の距離リスト作成 */
 void tournament(int rank);      /* 淘汰 */
 void calc_dist(RESULT *res);    /* 距離計算 */
 void cross(void);               /* 交叉 */
 void variation(int np);         /* 突然変異 */
 void migrate(int rank, int np,
              MPI_Status *status);       /* 移住 */


 /* main **************************************************************/
 int main(int argc, char **argv) {
  int    i, j, k, min, sec;
  int    start, end;
  time_t t1,t2;

  int rank, np;                 /* ランク、端末数 */
  MPI_Status status;
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &np);

  double fast_rank[np], fast_all;
  makelist();
  int distribution[GENOM][NODE+1];

 /* --- 親 (rank=0) --- */
  if (rank == 0)
    {
      start = time(&t1);        /* 開始時間取得 */
      srand((unsigned)time(NULL));
      func();  /* 母集団初期化 */
      /* 母集団の配分 */
        for (i = 1; i < np; i++) {         //i: 端末(rank)
          for (j = 0; j < GENOM; j++) {    //j: 遺伝子数
            for (k = 0; k < NODE+1; k++) { //k: 経路
              distribution[j][k] = result[j].route[k];
            }
          }
          MPI_Send(distribution, GENOM*(NODE+1), MPI_INT,
                   i, 99, MPI_COMM_WORLD);
        }
    }

 /* --- 子 (rank!=0) --- */
  else
    {
      /* 母集団の受け取り */
      MPI_Recv(distribution, GENOM*(NODE+1), MPI_INT,
               0, 99, MPI_COMM_WORLD, &status);
      for (i = 0; i < GENOM; i++) { //i: 遺伝子数
        for (j = 0; j < NODE+1; j++) { //j: 経路
          result[i].route[j] = distribution[i][j];
        }
        calc_dist(&result[i]);  //距離計算
      }
      srand((unsigned)time(NULL));
    }

 /* ループ */
  i = 0;
  while (i < LIMIT) {
    cross();                    /* 交叉 */
    tournament(rank);
    if ((rand() % 100) < EVOLUTION) {
      variation(np);            /* 突然変異 */
      tournament(rank);         /* 淘汰 */
    }
    i++;

    if (i % MIG_INTERVAL == 0){
      /* 結果表示 */
      if (rank == 0)
        {
          fast_all = fast;
            for (j = 1; j < np; j++) {
              MPI_Recv(&fast_rank[j], 1, MPI_DOUBLE, j,
                       50, MPI_COMM_WORLD, &status);
              if (fast_all > fast_rank[j])
                fast_all = fast_rank[j];
            }
 #if WRITEFILE
            printf("%d\t%6.2f\n", i, fast_all);
            //printf("%6.2f\n", fast_all);
 #endif
        }

      else
        {
          MPI_Send(&fast, 1, MPI_DOUBLE, 0,
                   50, MPI_COMM_WORLD);
        }
      if (np-1)
        migrate(rank, np, &status); /* 移住 */
    }
  } //loop end

 #if WRITEFILE
   usleep(1000*rank*100);
   printf("%2d> %6.2f: ", rank, result[champ].distance);
   for (i = 0; i < NODE+1; i++) {
     printf("%2d ", result[champ].route[i]);
  }
   puts("");
 #endif

   if (rank == 0)
    {
      fast_all = fast;
        for (i = 1; i < np; i++) {
          MPI_Recv(&fast_rank[i], 1, MPI_INT, i,
                   50, MPI_COMM_WORLD, &status);
          if (fast_all > fast_rank[i])
            fast_all = fast_rank[i];
        }

      printf("the shortest distance: %.2f\n", fast_all);
      end = time(&t2);          /* 終了時間取得 */
      min = end - start;
      sec = min / 60;
      min -= sec * 60;
 #if WRITEFILE
      usleep(1000*np*100);
      printf("exec time;;; %d:%02d\n", sec, min);
 #endif
    }

  else
    {
      MPI_Send(&fast, 1, MPI_INT, 0,
               50, MPI_COMM_WORLD);
    }

  MPI_Finalize();               /* MPI終了 */
 }

 /* func **************************************************************/
 void func() {
 #if DEBUG1
  puts("--func");
 #endif
  int i, j, go;

  for (i = 0; i < GENOM; i++)
    {
      result[i].distance = 0;
      result[i].route[0] = 0;
      result[i].route[NODE] = 0;

      for (j = 1; j < NODE; j++) {
        town[j].flag = 0;
      }
      town[0].flag = 1;

      for (j = 1; j < NODE; j++) {
        do {
          go = rand() % (NODE-1) + 1;
        } while (town[go].flag); //do-while end
        result[i].route[j] = go;
        town[go].flag++;
      } //for(j) end
      calc_dist(&result[i]);    /* 距離計算 */
    } //for(i) end

 #if DEBUG1
  puts("--func end");
 #endif

 /* calc_dist *********************************************************/
 void calc_dist(RESULT *res) {
  int     i, now, go;

  /* 経路が正しいかどうか確認 */
 #if DEBUG2
  double  judge = 0, dist_judge = 0;
  for (i = 1; i < NODE; i++) {
    judge += res->route[i];
    dist_judge += i;
  }
  if (judge != dist_judge) {
    puts("route error!");
    exit(1);
  }
 #endif  

  res->distance = 0;
  now = 0;
  for (i = 1; i < NODE+1; i++) {
    go = res->route[i];
    res->distance += town[now].dist[go];
    now = go;
  }
 }

 /* tournament ********************************************************/
 void tournament(int rank) {
 #if DEBUG1
  printf("--tournament %d\n", rank);
 #endif
  int        i, n, x;
 
  for (i = 0; i < GENOM/2; i++)
    {
      n = i;
      x = GENOM-1-i;
      if (result[n].distance > result[x].distance) {
        n = x;
        result[i] = result[n];  /* 代入 */
      }
      if (result[n].distance < result[champ].distance)
        champ = n;
    }

  if (fast > result[champ].distance){
    fast = result[champ].distance;
 #if WRITEFILE==0
    /* 記録表示 */
    printf("%2d> %6.2f: ", rank, result[champ].distance);
    for (i = 0; i < NODE+1; i++) {
      printf("%2d ", result[champ].route[i]);
    }
    putchar('\n');
 #endif
  }

 #if DEBUG1
  printf("--tournament %d end\n", rank);
 #endif
 }
 
 /* cross *************************************************************/
 /* 部分交叉 */
 void cross() {
 #if DEBUG1
  puts("--cross");
 #endif
  int    i, j, k, l, a, b, x;
  int    tmp1, tmp2;
  int    flag1[NODE], flag2[NODE];  /* parent1,parent2用旗 */
  RESULT parent1, parent2;

  for (i = 0; i < GENOM/2; i+=2)
    {
      /* 交叉するペアを選択 */
      a = rand() % (GENOM/2);
      do {
        b = rand() % (GENOM/2);
      } while (a == b);
      parent1 = result[a];
      parent2 = result[b];

      /* 旗初期化 */
      for (j = 0; j < NODE; j+=2) {
        flag1[j] = 1;  flag1[j+1] = 1;
        flag2[j] = 1;  flag2[j+1] = 1;
      }

      /* 距離の短いルートは交叉しないようにする */
      for (j = 0; j < NODE; j++) {
        if (town[parent1.route[j]].dist[parent1.route[j+1]] < 2) {
          flag1[j] = 0;  flag1[j+1] = 0;
        }
        if (town[parent2.route[j]].dist[parent2.route[j+1]] < 2) {
          flag2[j] = 0;  flag2[j+1] = 0;
        }
      }

      /* 交叉 */
      x = rand() % (NODE-1) + 1;        /* 切れ目 */
      for (j = x; j < NODE; j++) {
        tmp1 = parent1.route[j];
        tmp2 = parent2.route[j];
        if (flag1[j] && flag2[j]) {
          for (k = 1; k < NODE; k++) {
            if ((parent1.route[k] == tmp2) && k!=j && flag1[k]) {
              parent1.route[j] = tmp2;  flag1[j] = 0;
              parent1.route[k] = tmp1;  flag1[k] = 0;
            }
            if ((parent2.route[k] == tmp1) && k!=j && flag2[k]) {
              parent2.route[j] = tmp1;  flag2[j] = 0;
              parent2.route[k] = tmp2;  flag2[k] = 0;
            }
          } //for(k) end
        } //if(j) end
      } //for(j) end

        /* 距離計算 */
      calc_dist(&parent1);
      calc_dist(&parent2);

      l = GENOM/2+i;
      result[l] = parent1;
      result[l+1] = parent2;
    } //for(i) end

 #if DEBUG1
    puts("--cross end");
 #endif
 }
 
 /* variation *********************************************************/
 /* 突然変異 --位置移動 */
 void variation(int np) {
 #if DEBUG1
  puts("--variation");
 #endif
  int    i, j, k, l;
  int    x, y, z, tmp;
  RESULT parent;

  /* 旗初期化 */
  for (i = 0; i < GENOM; i++) {
    result[i].flag = 0;
  }

  k = rand()%10+1;
  for (i = 0; i < GENOM*k/100; i++)
    {
      do {
        j = rand() % GENOM;
      } while (result[j].flag);
      result[j].flag = 1;
      parent = result[j];

      //l = rand()%15+1;
      l = 1;
      for (j = 0; j < l; j++) {
        do {
      x = rand() % (NODE-1) + 1;
        } while (town[x-1].dist[x] < 2);
      do {
        y = rand() % (NODE-1) + 1;
      } while (x == y || town[y].dist[y+1] < 2);
          
      if (x > y) {              /* x < y の関係にする */
        tmp = x;
        x = y;
        y = tmp;
      }
      /* 位置移動 */
      tmp = parent.route[y];
      for (z = y; z > x; z--) {
        parent.route[z] = parent.route[z-1];
      }
      parent.route[x] = tmp;

      }

      calc_dist(&parent);       /* 距離計算 */
      result[GENOM-i] = parent;
    } //for(i) end
  
 #if DEBUG1
  puts("--variaion end");
 #endif
 }

 /* migrate ***********************************************************/
 /* 移住 */
 void migrate(int rank, int np, MPI_Status *status) {
 #if DEBUG1
  printf("%d  migrate\n", rank);
 #endif
  int i, j, b, x;
  int flag[GENOM] = {0};
  int a;                        /* 遺伝子数 x MIG_RATE[%] */
  int immigrant[a][NODE+1];

  a = GENOM*MIG_RATE/100;
  /* 移住者を決める */
  for (i = 0; i < a; i++) {
    do {
      x = rand() % GENOM;
    } while (flag[x]);
    flag[x] = 1;
    for (j = 0; j < NODE+1; j++) {
      immigrant[i][j] = result[x].route[j];
    }
  }

  b = a * (NODE+1);             /* 送信するデータの数 */
  /* 偶数rank 送信->受信 */
  if (rank%2 == 0)
    {
      /* 送信 */
      MPI_Send(immigrant, b, MPI_INT, rank+1,
               10, MPI_COMM_WORLD);
      /* 受信 */
      if (rank == 0) {
        MPI_Recv(immigrant, b, MPI_INT, np-1,
                 20, MPI_COMM_WORLD, status);
      }
      else {
        MPI_Recv(immigrant, b, MPI_INT, rank-1,
                 20, MPI_COMM_WORLD, status);
      }
      /* 受信データ格納 */
      for (i = 0; i < a; i++) {
        do {
          x = rand()%(GENOM/2)+(GENOM/2);
        } while (flag[x]);
        flag[x] = 1;

        for (j = 0; j < NODE+1; j++) {
          result[x].route[j] = immigrant[i][j];
        }
        calc_dist(&result[x]);
      }

    }

  /* 奇数rank 受信->送信 */
    else
      {
        /* 受信 */
        MPI_Recv(immigrant, b, MPI_INT, rank-1,
                 10, MPI_COMM_WORLD, status);
        /* 受信データ格納 */
        for (i = 0; i < a; i++) {
          do {
            x = rand()%(GENOM/2)+(GENOM/2);
          } while (flag[x]);
          flag[x] = 1;

          for (j = 0; j < NODE+1; j++) {
            result[x].route[j] = immigrant[i][j];
          }
          calc_dist(&result[x]);
        }
        /* 送信 */
        if (rank == np-1) {
          MPI_Send(immigrant, b, MPI_INT, 0,
                   20, MPI_COMM_WORLD);
        }
        else {
          MPI_Send(immigrant, b, MPI_INT, rank+1,
                   20, MPI_COMM_WORLD);
        }
      }


  /* 移住者を決める */
  for (i = 0; i < a; i++) {
    do {
      x = rand() % GENOM;
    } while (flag[x]);
    flag[x] = 1;
    for (j = 0; j < NODE+1; j++) {
      immigrant[i][j] = result[x].route[j];
    }
  }


  /* 偶数rank 受信->送信 */
  if (rank%2 == 0)
    {
      /* 受信 */
      MPI_Recv(immigrant, b, MPI_INT, rank+1,
               30, MPI_COMM_WORLD, status);
      /* 受信データ格納 */
      for (i = 0; i < a; i++) {
        do {
          x = rand()%(GENOM/2)+(GENOM/2);
        } while (flag[x]);
        flag[x] = 1;

        for (j = 0; j < NODE+1; j++) {
          result[x].route[j] = immigrant[i][j];
        }
        calc_dist(&result[x]);
      }

      /* 送信 */
      if (rank == 0) {
        MPI_Send(immigrant, b, MPI_INT, np-1,
                 40, MPI_COMM_WORLD);
      }
      else {
        MPI_Send(immigrant, b, MPI_INT, rank-1,
                 40, MPI_COMM_WORLD);
      }
    }

  /* 奇数rank 送信->受信 */
  else
    {
      /* 送信 */
      MPI_Send(immigrant, b, MPI_INT, rank-1,
               30, MPI_COMM_WORLD);

      /* 受信 */
      if (rank == np-1) {
        MPI_Recv(immigrant, b, MPI_INT, 0,
                 40, MPI_COMM_WORLD, status);
      }
      else {
        MPI_Recv(immigrant, b, MPI_INT, rank+1,
                 40, MPI_COMM_WORLD, status);
      }
      /* 受信データ格納 */
      for (i = 0; i < a; i++) {
        do {
          x = rand()%(GENOM/2)+(GENOM/2);
        } while (flag[x]);
        flag[x] = 1;

        for (j = 0; j < NODE+1; j++) {
          result[x].route[j] = immigrant[i][j];
        }
        calc_dist(&result[x]);
      }
    }

  tournament(rank);
 }

 /* makelist **********************************************************/
 リストは別(参考サイト参照)

 for (i = 0; i < NODE; i++) {
    for (j = 0; j < NODE; j++) {
      town[i].dist[j] = list[i][j];
    }
  }
 }
トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS