卒論
参考サイト:MPI並列プログラミング
#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];
}
}
}
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
