Last active
September 27, 2019 07:07
-
-
Save stmtk1/cb94f477c3f963d55513613886418527 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.io.*; | |
| import java.util.Random; | |
| import java.util.Date; | |
| import java.util.StringTokenizer; | |
| class Species { | |
| protected double max; // 最大適応度 | |
| protected double mean; // 平均適応度 | |
| protected double [] pi; // 適応度 | |
| protected double [] ro; // ルーレット板 | |
| protected int allele_u; // 対立遺伝子上限 | |
| protected int allele_l; // 対立遺伝子下限 | |
| protected int size; // 個体総数 | |
| protected int max_ch; // 子供の数の最大値 | |
| protected int max_len; // 最大遺伝子長 | |
| protected int min_len; // 最小遺伝子長（負の時は，最大遺伝子長で固定） | |
| protected int max_n; // 最大適応度の個体番号 | |
| protected int dup_a; // 遺伝子の重複 | |
| // =0 : 重複を許さない | |
| // =1 : 重複を許す | |
| protected int dup_s; // 個体の重複（同じ染色体の個体） | |
| // =0 : 重複を許さない | |
| // =1 : 重複を許す | |
| protected int [][] ind; // 集団（個体の集まり） | |
| protected int [] len; // 各個体の遺伝子長 | |
| protected int [] kou1; // 交叉・突然変異用作業場所１ | |
| protected int [] kou2; // 交叉・突然変異用作業場所２ | |
| protected int [] s_w; // 淘汰用指標（選択された回数） | |
| protected int [][] edge; // エッジ組み替え交叉用ワークエリア | |
| protected byte [] pi_w; // 適応度計算指標 | |
| // =0 : 未使用 | |
| // =1 : 適応度計算前（突然変異はこの個体だけに適用） | |
| // =2 : 適応度計算済み（交叉時に親とみなす） | |
| protected Random rn; // 乱数 | |
| /***********************************/ | |
| /* 正規分布変量の発生 */ | |
| /* m : 平均 */ | |
| /* s : 標準偏差 */ | |
| /* return : 正規分布変量 */ | |
| /***********************************/ | |
| double norm_d(double m, double s) | |
| { | |
| double x = 0.0; | |
| int i1; | |
| for (i1 = 0; i1 < 12; i1++) | |
| x += rn.nextDouble(); | |
| x = s * (x - 6.0) + m; | |
| return x; | |
| } | |
| /**************************************************/ | |
| /* 場所を探す */ | |
| /* n : >=0 : n番目の親を捜す */ | |
| /* -1 : 空いている場所を探す */ | |
| /* return : 親の場所，または，空いている場所 */ | |
| /* （存在しないときは負の値） */ | |
| /**************************************************/ | |
| int Position(int n) | |
| { | |
| int i1, k = -1, sw = 0; | |
| /* | |
| 空いている場所を探す | |
| */ | |
| if (n < 0) { | |
| for (i1 = 0; i1 < size+max_ch && k < 0; i1++) { | |
| if (pi_w[i1] == 0) | |
| k = i1; | |
| } | |
| if (k < 0) { | |
| System.out.print("***error 空いている場所がない --Position--\n"); | |
| System.exit(1); | |
| } | |
| } | |
| /* | |
| ｎ番目の親（pi_w[i]=2）を捜す | |
| */ | |
| else { | |
| for (i1 = 0; i1 < size+max_ch && sw == 0; i1++) { | |
| if (pi_w[i1] == 2) { | |
| k++; | |
| if (k == n) { | |
| sw = 1; | |
| k = i1; | |
| } | |
| } | |
| } | |
| } | |
| return k; | |
| } | |
| /*******************************************************************/ | |
| /* 個体の選択 */ | |
| /* method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* bias : α，または，method=2の場合は初期値 */ | |
| /* step : β */ | |
| /* return : 個体番号 */ | |
| /*******************************************************************/ | |
| int Select(int method, double bias, double step) | |
| { | |
| double sum = 0.0, x; | |
| int i1, k, min, n, sw; | |
| // ルーレット板の用意 | |
| switch (method) { | |
| // ランダム | |
| case -1: | |
| n = 0; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) | |
| n++; | |
| } | |
| sum = 1.0 / n; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) | |
| ro[i1] = sum; | |
| } | |
| break; | |
| // 評価値をそのまま利用 | |
| case 0: | |
| n = 0; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) { | |
| sum += pi[i1]; | |
| n++; | |
| } | |
| } | |
| if (Math.abs(sum) > 1.0e-10) { | |
| sum = 1.0 / Math.abs(sum); | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) | |
| ro[i1] = pi[i1] * sum; | |
| } | |
| } | |
| else { | |
| sum = 1.0 / n; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) | |
| ro[i1] = sum; | |
| } | |
| } | |
| break; | |
| // 最小値からの差 | |
| case 1: | |
| min = -1; | |
| n = 0; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) { | |
| n++; | |
| if (min < 0 || pi[i1] < pi[min]) | |
| min = i1; | |
| } | |
| } | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) { | |
| ro[i1] = pi[i1] - pi[min]; | |
| if (ro[i1] < bias) | |
| ro[i1] = bias; | |
| sum += ro[i1]; | |
| } | |
| } | |
| if (sum > 1.0e-10) { | |
| sum = 1.0 / sum; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) | |
| ro[i1] *= sum; | |
| } | |
| } | |
| else { | |
| sum = 1.0 / n; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) | |
| ro[i1] = sum; | |
| } | |
| } | |
| break; | |
| // 線形化 | |
| case 2: | |
| n = 0; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) { | |
| ro[i1] = -1.0; | |
| n++; | |
| } | |
| else | |
| ro[i1] = 1.0; | |
| } | |
| sw = 0; | |
| sum = bias; | |
| while (sw == 0) { | |
| min = -1; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (ro[i1] < 0.0 && (min < 0 || pi[i1] < pi[min])) | |
| min = i1; | |
| } | |
| if (min < 0) | |
| sw = 1; | |
| else { | |
| ro[min] = sum; | |
| sum += step; | |
| } | |
| } | |
| sum = 1.0 / (0.5 * (2.0 * bias + step * (n - 1)) * n); | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) | |
| ro[i1] *= sum; | |
| } | |
| break; | |
| } | |
| sum = 0.0; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) { | |
| sum += ro[i1]; | |
| ro[i1] = sum; | |
| } | |
| } | |
| // 選択 | |
| x = rn.nextDouble(); | |
| sw = 0; | |
| k = 0; | |
| for (i1 = 0; i1 < size+max_ch && sw == 0; i1++) { | |
| if (pi_w[i1] > 1) { | |
| if (x <= ro[i1]) { | |
| sw = 1; | |
| k = i1; | |
| } | |
| } | |
| } | |
| return k; | |
| } | |
| /****************************/ | |
| /* コンストラクタ */ | |
| /* name : ファイル名 */ | |
| /* seed : 乱数の初期値 */ | |
| /****************************/ | |
| Species (String name, int seed) throws IOException, FileNotFoundException | |
| { | |
| int kind, num; | |
| String line; | |
| StringTokenizer dt; | |
| BufferedReader in = new BufferedReader(new FileReader(name)); | |
| /* | |
| データの入力 | |
| */ | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| allele_u = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| allele_l = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| max_len = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| min_len = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| dup_a = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| dup_s = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| size = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| max_ch = Integer.parseInt(dt.nextToken()); | |
| /* | |
| データのチェック | |
| */ | |
| if (size <= 0) { | |
| System.out.print("***error 個体総数≦０ (Constructor)\n"); | |
| System.exit(1); | |
| } | |
| if (max_ch < 0) { | |
| System.out.print("***error 子供の数＜０ (Constructor)\n"); | |
| System.exit(1); | |
| } | |
| if (max_len <= 0 || min_len == 0) { | |
| System.out.print("***error 遺伝子長≦０ (Constructor)\n"); | |
| System.exit(1); | |
| } | |
| if (max_len < min_len) { | |
| System.out.print("***error 最大遺伝子長＜最小遺伝子長 (Constructor)\n"); | |
| System.exit(1); | |
| } | |
| if (allele_u <= allele_l) { | |
| System.out.print("***error 対立遺伝子上限≦対立遺伝子下限 (Constructor)\n"); | |
| System.exit(1); | |
| } | |
| kind = allele_u - allele_l + 1; | |
| if (dup_a == 0 && max_len > kind) { | |
| System.out.print("***error 遺伝子の重複を防ぐことはできない (Constructor)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 領域の確保 | |
| */ | |
| num = size + max_ch; | |
| ind = new int [num][max_len]; | |
| edge = new int [max_len][5]; | |
| pi = new double [num]; | |
| ro = new double [num]; | |
| len = new int [num]; | |
| kou1 = new int [max_len]; | |
| kou2 = new int [max_len]; | |
| s_w = new int [num]; | |
| pi_w = new byte [num]; | |
| /* | |
| 乱数の初期設定 | |
| */ | |
| rn = new Random (seed); | |
| } | |
| /********************/ | |
| /* 標準的な初期設定 */ | |
| /********************/ | |
| void Init_std() | |
| { | |
| int i1, i2, i3, length, lid, sw1, sw2; | |
| /* | |
| 初期設定 | |
| */ | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (i1 < size) | |
| pi_w[i1] = 1; // 適応度の計算前 | |
| else | |
| pi_w[i1] = 0; // 未使用 | |
| } | |
| /* | |
| 遺伝子の決定 | |
| */ | |
| for (i1 = 0; i1 < size; i1++) { | |
| sw1 = 0; | |
| while (sw1 == 0) { | |
| // 遺伝子長の決定 | |
| if (min_len < 0) | |
| length = max_len; | |
| else { | |
| length = (int)(rn.nextDouble() * (max_len - min_len + 1) + min_len); | |
| if (length > max_len) | |
| length = max_len; | |
| } | |
| len[i1] = length; | |
| // 遺伝子の決定 | |
| for (i2 = 0; i2 < length; i2++) { | |
| sw2 = 0; | |
| while (sw2 == 0) { | |
| lid = (int)(rn.nextDouble() * (allele_u - allele_l + 1) + allele_l); | |
| if (lid > allele_u) | |
| lid = allele_u; | |
| ind[i1][i2] = lid; | |
| // 重複遺伝子のチェック | |
| sw2 = 1; | |
| if (dup_a == 0) { | |
| for (i3 = 0; i3 < i2 && sw2 > 0; i3++) { | |
| if (lid == ind[i1][i3]) | |
| sw2 = 0; | |
| } | |
| } | |
| } | |
| } | |
| // 重複個体のチェック | |
| sw1 = 1; | |
| if (dup_s == 0) { | |
| for (i2 = 0; i2 < i1 && sw1 > 0; i2++) { | |
| if (len[i1] == len[i2]) { | |
| sw2 = 0; | |
| for (i3 = 0; i3 < len[i1] && sw2 == 0; i3++) { | |
| if (ind[i1][i3] != ind[i2][i3]) | |
| sw2 = 1; | |
| } | |
| if (sw2 == 0) | |
| sw1 = 0; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /****************************************************/ | |
| /* 標準的な出力 */ | |
| /* sw : 出力レベル */ | |
| /* =0 : 最終出力だけ */ | |
| /* n>0 : ｎ世代毎に出力（負はファイル） */ | |
| /* out_m : 出力方法 */ | |
| /* =0 : すべての個体を出力 */ | |
| /* =1 : 最大適応度の個体だけを出力 */ | |
| /* gen : 現在の世代番号 */ | |
| /* name : 出力ファイル名 */ | |
| /****************************************************/ | |
| void Out_std(int sw, int out_m, int gen, String name) throws IOException, FileNotFoundException | |
| { | |
| int i1, i2, k = 0, pr; | |
| String now; | |
| PrintStream out = null; | |
| BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); | |
| if (sw >= 0) { | |
| System.out.print(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ "); | |
| pr = Integer.parseInt(in.readLine()); | |
| } | |
| else | |
| pr = -1; | |
| if (pr != 0) { | |
| // 出力先の決定と評価値の出力 | |
| if (pr > 0) | |
| out = System.out; | |
| else { | |
| Date newtime = new Date(); // 現在時刻の獲得 | |
| now = newtime.toString(); // 文字列への変換 | |
| out = new PrintStream(new FileOutputStream(name, true)); | |
| out.println("***世代 " + gen + " 適応度 max " + max + | |
| " (" + max_n + ") mean " + mean + " 時間 " + now); | |
| } | |
| // 詳細出力 | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if ((pi_w[i1] > 1) && (out_m ==0 || out_m == 1 && i1 == max_n)) { | |
| out.print(i1 + " allele"); | |
| for (i2 = 0; i2 < len[i1]; i2++) | |
| out.print(" " + ind[i1][i2]); | |
| out.println(" value " + pi[i1]); | |
| if (pr > 0) { | |
| k++; | |
| if (k == pr) { | |
| in.readLine(); | |
| k = 0; | |
| } | |
| } | |
| } | |
| } | |
| if (pr < 0) | |
| out.close(); | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（親のコピー） */ | |
| /* method : =2 : 有性（２つの親から２つの子供） */ | |
| /* =1 : １つの親から１つの子供 */ | |
| /* pair : method=2 の時は親のペア数 */ | |
| /* method=1 の時は親の数（＝子供の数） */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_copy(int method, int pair, int k_method, double k_bias, | |
| double k_step) | |
| { | |
| int i1, i2, i3, k, p, p1, p2 = 0, sw; | |
| /* | |
| 初期設定とデータチェック | |
| */ | |
| if (method != 1) | |
| method = 2; | |
| if (pair <= 0) | |
| pair = (method==2) ? max_ch/2 : max_ch; | |
| else { | |
| if (method == 2 && 2*pair > max_ch || method == 1 && pair > max_ch) { | |
| System.out.print("***error 子供が多すぎる (C_copy)\n"); | |
| System.exit(1); | |
| } | |
| } | |
| /* | |
| 実行 | |
| */ | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // コピー | |
| for (i2 = 0; i2 < method; i2++) { | |
| p = (i2 == 0) ? p1 : p2; | |
| k = Position(-1); | |
| len[k] = len[p]; | |
| pi_w[k] = 1; | |
| for (i3 = 0; i3 < len[k]; i3++) | |
| ind[k][i3] = ind[p][i3]; | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（多点交叉） */ | |
| /* kosa : 交叉確率 */ | |
| /* k_point : 交叉点の数 */ | |
| /* （負の時は，1から-k_point間のランダム） */ | |
| /* k_vr : =0 : 両親とも同じ位置で交叉 */ | |
| /* =1 : 両親が異なる位置で交叉（遺伝子長は可変） */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_point(double kosa, int k_point, int k_vr, int k_method, | |
| double k_bias, double k_step) | |
| { | |
| int abs_p, c1, c2, i1, i2, i3, k1, k2, mn = 0, num, p1, p2 = 0, | |
| pair, sw, t11, t12, t21, t22; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| pair = max_ch / 2; | |
| if (dup_a == 0) { | |
| System.out.print("***error 交叉方法が不適当 (C_point)\n"); | |
| System.exit(1); | |
| } | |
| abs_p = Math.abs(k_point); | |
| if (abs_p == 0 || abs_p > max_len-1 || min_len > 0 && abs_p > min_len-1) { | |
| System.out.print("***error 交叉点の数が不適当 (C_point)\n"); | |
| System.exit(1); | |
| } | |
| if (k_vr > 0 && min_len < 0) { | |
| System.out.print("***error 遺伝子長は可変でなければならない (C_point)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| num = k_point; | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(2, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 交叉位置の数の決定 | |
| if (k_point < 0) { | |
| num = (int)(rn.nextDouble() * abs_p + 1); | |
| if (num > abs_p) | |
| num = abs_p; | |
| } | |
| // 交叉位置の決定（点の後ろで交叉） | |
| for (i2 = 0; i2 < num; i2++) { | |
| // 親１の交叉位置 | |
| sw = 0; | |
| while (sw == 0) { | |
| sw = 1; | |
| kou1[i2] = (int)(rn.nextDouble() * (len[p1] - 1)); | |
| if (kou1[i2] > len[p1]-2) | |
| kou1[i2] = len[p1] - 2; | |
| if (k_vr == 0 && kou1[i2] > len[p2]-2) | |
| kou1[i2] = len[p2] - 2; | |
| for (i3 = 0; i3 < i2 && sw > 0; i3++) { | |
| if (kou1[i3] == kou1[i2]) | |
| sw = 0; | |
| } | |
| } | |
| // 親２の交叉位置 | |
| if (k_vr > 0) { | |
| sw = 0; | |
| while (sw == 0) { | |
| sw = 1; | |
| kou2[i2] = (int)(rn.nextDouble() * (len[p2] - 1)); | |
| if (kou2[i2] > len[p2]-2) | |
| kou2[i2] = len[p2] - 2; | |
| for (i3 = 0; i3 < i2 && sw > 0; i3++) { | |
| if (kou2[i3] == kou2[i2]) | |
| sw = 0; | |
| } | |
| } | |
| } | |
| } | |
| // 交叉の実行 | |
| // 親１のt11からt12を子１のc1へコピー | |
| // 親２のt21からt22を子２のc2へコピー | |
| // 次は， | |
| // 親１のt11からt12を子２のc2へコピー | |
| // 親２のt21からt22を子１のc1へコピー | |
| // ・・・・・ | |
| c1 = 0; | |
| c2 = 0; | |
| t11 = 0; | |
| t21 = 0; | |
| // 遺伝子長 | |
| k1 = Position(-1); | |
| pi_w[k1] = 1; | |
| len[k1] = len[p1]; | |
| k2 = Position(-1); | |
| pi_w[k2] = 1; | |
| len[k2] = len[p2]; | |
| for (i2 = 0; i2 < num+1; i2++ ) { | |
| // 次の交叉位置を求める | |
| if (i2 == num) { // 最後 | |
| t12 = len[p1]; | |
| t22 = len[p2]; | |
| } | |
| else { | |
| // 親１ | |
| t12 = max_len; | |
| for (i3 = 0; i3 < num; i3++) { | |
| if (kou1[i3] >= 0 && kou1[i3] <= t12) { | |
| t12 = kou1[i3]; | |
| mn = i3; | |
| } | |
| } | |
| kou1[mn] = -1; | |
| t12++; | |
| // 親２ | |
| if (k_vr == 0) | |
| t22 = t12; | |
| else { | |
| t22 = max_len; | |
| for (i3 = 0; i3 < num; i3++) { | |
| if (kou2[i3] >= 0 && kou2[i3] <= t22) { | |
| t22 = kou2[i3]; | |
| mn = i3; | |
| } | |
| } | |
| kou2[mn] = -1; | |
| t22++; | |
| } | |
| } | |
| // 指定箇所のコピー | |
| for (i3 = t11; i3 < t12; i3++) { | |
| if (i2%2 == 0) { | |
| if (c1 < max_len) { | |
| ind[k1][c1] = ind[p1][i3]; | |
| c1++; | |
| } | |
| } | |
| else { | |
| if (c2 < max_len) { | |
| ind[k2][c2] = ind[p1][i3]; | |
| c2++; | |
| } | |
| } | |
| } | |
| for (i3 = t21; i3 < t22; i3++) { | |
| if (i2%2 == 0) { | |
| if (c2 < max_len) { | |
| ind[k2][c2] = ind[p2][i3]; | |
| c2++; | |
| } | |
| } | |
| else { | |
| if (c1 < max_len) { | |
| ind[k1][c1] = ind[p2][i3]; | |
| c1++; | |
| } | |
| } | |
| } | |
| // 交叉位置の移動 | |
| t11 = t12; | |
| t21 = t22; | |
| } | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（一様交叉．[0,1]を等確率で発生させ，1であれば， */ | |
| /* 親１，0であれば親２の遺伝子を子１が受け継ぐ） */ | |
| /* kosa : 交叉確率 */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_uniform(double kosa, int k_method, double k_bias, double k_step) | |
| { | |
| int i1, i2, k1, k2, p1, p2 = 0, pair, sw; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| pair = max_ch / 2; | |
| if (dup_a == 0) { | |
| System.out.print("***error 交叉方法が不適当 (C_uniform)\n"); | |
| System.exit(1); | |
| } | |
| if (min_len > 0) { | |
| System.out.print("***error 遺伝子長は固定長でなければならない (C_uniform)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(2, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 遺伝子長 | |
| k1 = Position(-1); | |
| pi_w[k1] = 1; | |
| len[k1] = len[p1]; | |
| k2 = Position(-1); | |
| pi_w[k2] = 1; | |
| len[k2] = len[p2]; | |
| // 交叉 | |
| for (i2 = 0; i2 < len[p1]; i2++) { | |
| if (rn.nextDouble() > 0.5) { | |
| ind[k1][i2] = ind[p1][i2]; | |
| ind[k2][i2] = ind[p2][i2]; | |
| } | |
| else { | |
| ind[k1][i2] = ind[p2][i2]; | |
| ind[k2][i2] = ind[p1][i2]; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（平均化交叉．２つの親の平均値を受け継ぐ） */ | |
| /* kosa : 交叉確率 */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_mean(double kosa, int k_method, double k_bias, double k_step) | |
| { | |
| int i1, i2, k, p1, p2 = 0, sw; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| if (min_len > 0) { | |
| System.out.print("***error 遺伝子長は固定長でなければならない (C_mean)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < max_ch; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(1, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 遺伝子長 | |
| k = Position(-1); | |
| len[k] = len[p1]; | |
| pi_w[k] = 1; | |
| // 交叉 | |
| for (i2 = 0; i2 < len[k]; i2++) | |
| ind[k][i2] = (ind[p1][i2] + ind[p2][i2]) / 2; | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（循環交叉．ランダムに１点を選択し，その位置にある遺伝子を */ | |
| /* そのまま各子供が選択する．その位置にある親２（１）の遺伝 */ | |
| /* 子を，その遺伝子の親１（２）の場所に，子１（２）が受け継 */ | |
| /* ぐ（ただし，doubleの場合は，この手続きをのぞく）．この手 */ | |
| /* 続きを，すでに受け継いだ遺伝子の位置が選択されるまで繰り */ | |
| /* 返し，残りの遺伝子については，子１（２）は，親２（１）の */ | |
| /* 遺伝子をその順番通りに受け継ぐ） */ | |
| /* 2 4 1 3 6 5 + + 1 + + 5 3 2 1 4 6 5 */ | |
| /* * → → */ | |
| /* 3 2 5 4 1 6 + + 5 + 1 + 2 4 5 3 1 6 */ | |
| /* kosa : 交叉確率 */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_cycle(double kosa, int k_method, double k_bias, double k_step) | |
| { | |
| int i1, i2, i3, k1, k2, p, pair, p1, p2 = 0, sw; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| pair = max_ch / 2; | |
| if (dup_a != 0) { | |
| System.out.print("***error 交叉方法が不適当 (C_cycle)\n"); | |
| System.exit(1); | |
| } | |
| if (min_len > 0) { | |
| System.out.print("***error 遺伝子長は固定長でなければならない (C_cycle)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(2, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 初期設定 | |
| for (i2 = 0; i2 < len[p1]; i2++) { | |
| kou1[i2] = 0; | |
| kou2[i2] = 0; | |
| } | |
| // 遺伝子長 | |
| k1 = Position(-1); | |
| pi_w[k1] = 1; | |
| len[k1] = len[p1]; | |
| k2 = Position(-1); | |
| pi_w[k2] = 1; | |
| len[k2] = len[p2]; | |
| // 交叉 | |
| sw = 0; | |
| while (sw == 0) { | |
| sw = 1; | |
| p = (int)(rn.nextDouble() * len[p1]); | |
| if (p >= len[p1]) | |
| p = len[p1] - 1; | |
| if (kou1[p] == 0 && kou2[p] == 0) { | |
| kou1[p] = 1; | |
| kou2[p] = 1; | |
| ind[k1][p] = ind[p1][p]; | |
| ind[k2][p] = ind[p2][p]; | |
| for (i2 = 0; i2 < len[p1] && sw > 0; i2++) { | |
| if (ind[p2][p] == ind[p1][i2]) { | |
| ind[k1][i2] = ind[p1][i2]; | |
| kou1[i2] = 1; | |
| sw = 0; | |
| } | |
| } | |
| sw = 1; | |
| for (i2 = 0; i2 < len[p2] && sw > 0; i2++) { | |
| if (ind[p1][p] == ind[p2][i2]) { | |
| ind[k2][i2] = ind[p2][i2]; | |
| kou2[i2] = 1; | |
| sw = 0; | |
| } | |
| } | |
| } | |
| } | |
| sw = 0; | |
| i2 = 0; | |
| i3 = 0; | |
| while (sw == 0) { | |
| while (sw == 0 && i2 < len[p1]) { | |
| if (kou1[i2] == 0) | |
| sw = 1; | |
| else | |
| i2++; | |
| } | |
| sw = 0; | |
| while (sw == 0 && i3 < len[p2]) { | |
| if (kou2[i3] == 0) | |
| sw = 1; | |
| else | |
| i3++; | |
| } | |
| if (i2 < len[p1] && i3 < len[p2]) { | |
| ind[k1][i2] = ind[p2][i3]; | |
| ind[k2][i3] = ind[p1][i2]; | |
| sw = 0; | |
| i2++; | |
| i3++; | |
| } | |
| else | |
| sw = 1; | |
| } | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（部分的交叉．ランダムに１点を選択し，その位置にある親１と */ | |
| /* 親２の遺伝子を取り出す．次に，親１と親２の染色体上で，こ */ | |
| /* の２つの遺伝子の位置を交換する．この操作を，選択した点よ */ | |
| /* り右にあるすべての遺伝子に対して実施する */ | |
| /* 2 4 1 3 6 5 2 4 5 3 6 1 */ | |
| /* * → → ･････ */ | |
| /* 3 2 5 4 1 6 3 2 1 4 5 6 */ | |
| /* kosa : 交叉確率 */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_part(double kosa, int k_method, double k_bias, double k_step) | |
| { | |
| int i1, i2, i3, k1, k2, lv, p, pair, p1, p2 = 0, sw; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| pair = max_ch / 2; | |
| if (dup_a != 0) { | |
| System.out.print("***error 交叉方法が不適当 (C_part)\n"); | |
| System.exit(1); | |
| } | |
| if (min_len > 0) { | |
| System.out.print("***error 遺伝子長は固定長でなければならない (C_part)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(2, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 遺伝子長 | |
| k1 = Position(-1); | |
| pi_w[k1] = 1; | |
| len[k1] = len[p1]; | |
| k2 = Position(-1); | |
| pi_w[k2] = 1; | |
| len[k2] = len[p2]; | |
| // 交叉 | |
| p = (int)(rn.nextDouble() * len[p1]); | |
| if (p >= len[p1]) | |
| p = len[p1] - 1; | |
| for (i2 = 0; i2 < len[p1]; i2++) { | |
| ind[k1][i2] = ind[p1][i2]; | |
| ind[k2][i2] = ind[p2][i2]; | |
| } | |
| for (i2 = p; i2 < len[p1]; i2++) { | |
| sw = 0; | |
| lv = ind[k1][i2]; | |
| for (i3 = 0; i3 < len[p1] && sw == 0; i3++) { | |
| if (ind[k2][i2] == ind[k1][i3]) { | |
| ind[k1][i2] = ind[k1][i3]; | |
| ind[k1][i3] = lv; | |
| sw = 1; | |
| } | |
| } | |
| sw = 0; | |
| for (i3 = 0; i3 < len[p1] && sw == 0; i3++) { | |
| if (lv == ind[k2][i3]) { | |
| ind[k2][i3] = ind[k2][i2]; | |
| ind[k2][i2] = lv; | |
| sw = 1; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（順序交叉．ランダムに切れ目を決定し，子１に対し，切れ目の */ | |
| /* 左側では，親１の遺伝子をそのまま受け継ぎ，右側では，親１ */ | |
| /* の遺伝子を親２の遺伝子の出現順序に並べ替える． */ | |
| /* 2 4 1 3 6 5 2 4 1 3 5 6 */ | |
| /* * → */ | |
| /* 3 2 5 4 1 6 3 2 5 4 1 6 */ | |
| /* kosa : 交叉確率 */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_seq(double kosa, int k_method, double k_bias, double k_step) | |
| { | |
| int i1, i2, i3, i4, k1, k2, p, pair, pp, p1, p2 = 0, sw; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| pair = max_ch / 2; | |
| if (dup_a != 0) { | |
| System.out.print("***error 交叉方法が不適当 (C_seq)\n"); | |
| System.exit(1); | |
| } | |
| if (min_len > 0) { | |
| System.out.print("***error 遺伝子長は固定長でなければならない (C_seq)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(2, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 遺伝子長 | |
| k1 = Position(-1); | |
| pi_w[k1] = 1; | |
| len[k1] = len[p1]; | |
| k2 = Position(-1); | |
| pi_w[k2] = 1; | |
| len[k2] = len[p2]; | |
| // 交叉 | |
| p = (int)(rn.nextDouble() * (len[p1] - 1)); | |
| if (p >= len[p1]-1) | |
| p = len[p1] - 2; | |
| for (i2 = 0; i2 <= p; i2++) { | |
| ind[k1][i2] = ind[p1][i2]; | |
| ind[k2][i2] = ind[p2][i2]; | |
| } | |
| pp = 0; | |
| for (i2 = p+1; i2 < len[p1]; i2++) { | |
| sw = 0; | |
| for (i3 = pp; i3 < len[p2] && sw == 0; i3++) { | |
| for (i4 = p+1; i4 < len[p1] && sw == 0; i4++) { | |
| if (ind[p2][i3] == ind[p1][i4]) { | |
| sw = 1; | |
| pp = i3 + 1; | |
| ind[k1][i2] = ind[p1][i4]; | |
| } | |
| } | |
| } | |
| } | |
| pp = 0; | |
| for (i2 = p+1; i2 < len[p2]; i2++) { | |
| sw = 0; | |
| for (i3 = pp; i3 < len[p1] && sw == 0; i3++) { | |
| for (i4 = p+1; i4 < len[p2] && sw == 0; i4++) { | |
| if (ind[p1][i3] == ind[p2][i4]) { | |
| sw = 1; | |
| pp = i3 + 1; | |
| ind[k2][i2] = ind[p2][i4]; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（一様順序交叉．位置の集合をランダムに選択し，一方の親の選 */ | |
| /* 択された位置における遺伝子の順序に従って，他の親の遺伝子 */ | |
| /* を並べ替える */ | |
| /* 2 4 1 3 6 5 2 4 1 3 6 5 */ | |
| /* * * → */ | |
| /* 3 2 5 4 1 6 4 2 5 3 1 6 */ | |
| /* kosa : 交叉確率 */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_useq(double kosa, int k_method, double k_bias, double k_step) | |
| { | |
| int i1, i2, i3, i4, k1, k2, p, pair, p1, p2 = 0, sw; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| pair = max_ch / 2; | |
| if (dup_a != 0) { | |
| System.out.print("***error 交叉方法が不適当 (C_useq)\n"); | |
| System.exit(1); | |
| } | |
| if (min_len > 0) { | |
| System.out.print("***error 遺伝子長は固定長でなければならない (C_useq)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(2, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 遺伝子長 | |
| k1 = Position(-1); | |
| pi_w[k1] = 1; | |
| len[k1] = len[p1]; | |
| k2 = Position(-1); | |
| pi_w[k2] = 1; | |
| len[k2] = len[p2]; | |
| // 交叉 | |
| for (i2 = 0; i2 < len[p1]; i2++) { | |
| ind[k1][i2] = ind[p1][i2]; | |
| ind[k2][i2] = ind[p2][i2]; | |
| kou1[i2] = (rn.nextDouble() < 0.5) ? 0 : 1; | |
| } | |
| p = 0; | |
| for (i2 = 0; i2 < len[p1]; i2++) { | |
| if (kou1[i2] > 0) { | |
| sw = 0; | |
| for (i3 = p; i3 < len[p2] && sw == 0; i3++) { | |
| for (i4 = 0; i4 < len[p1] && sw == 0; i4++) { | |
| if (ind[p2][i3] == ind[p1][i4] && kou1[i4] > 0) { | |
| sw = 1; | |
| p = i3 + 1; | |
| ind[k1][i2] = ind[p1][i4]; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| p = 0; | |
| for (i2 = 0; i2 < len[p2]; i2++) { | |
| if (kou1[i2] > 0) { | |
| sw = 0; | |
| for (i3 = p; i3 < len[p1] && sw == 0; i3++) { | |
| for (i4 = 0; i4 < len[p2] && sw == 0; i4++) { | |
| if (ind[p1][i3] == ind[p2][i4] && kou1[i4] > 0) { | |
| sw = 1; | |
| p = i3 + 1; | |
| ind[k2][i2] = ind[p2][i4]; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（一様位置交叉．位置の集合をランダムに選択し，一方の親の選 */ | |
| /* 択された位置における遺伝子の位置に，他の親の同じ遺伝子を */ | |
| /* 配置する．残りの遺伝子は，親と同じ順序に配置する． */ | |
| /* 2 4 1 3 6 5 + + 5 + 1 + 2 4 5 3 1 6 */ | |
| /* * * → → */ | |
| /* 3 2 5 4 1 6 + + 1 + 6 + 3 2 1 5 6 4 */ | |
| /* kosa : 交叉確率 */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_upos(double kosa, int k_method, double k_bias, double k_step) | |
| { | |
| int i1, i2, i3, k1, k2, p, pair, p1, p2 = 0, sw; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| pair = max_ch / 2; | |
| if (dup_a != 0) { | |
| System.out.print("***error 交叉方法が不適当 (C_upos)\n"); | |
| System.exit(1); | |
| } | |
| if (min_len > 0) { | |
| System.out.print("***error 遺伝子長は固定長でなければならない (C_upos)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(2, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 遺伝子長 | |
| k1 = Position(-1); | |
| pi_w[k1] = 1; | |
| len[k1] = len[p1]; | |
| k2 = Position(-1); | |
| pi_w[k2] = 1; | |
| len[k2] = len[p2]; | |
| // 交叉 | |
| for (i2 = 0; i2 < len[p1]; i2++) { | |
| kou1[i2] = (rn.nextDouble() < 0.5) ? 0 : 1; | |
| if (kou1[i2] > 0) { | |
| ind[k1][i2] = ind[p2][i2]; | |
| ind[k2][i2] = ind[p1][i2]; | |
| } | |
| } | |
| p = 0; | |
| for (i2 = 0; i2 < len[p1]; i2++) { | |
| sw = 0; | |
| for (i3 = 0; i3 < len[p1] && sw == 0; i3++) { | |
| if (kou1[i3] > 0 && ind[p1][i2] == ind[k1][i3]) | |
| sw = 1; | |
| } | |
| if (sw == 0) { | |
| for (i3 = p; i3 < len[p1] && sw == 0; i3++) { | |
| if (kou1[i3] == 0) { | |
| ind[k1][i3] = ind[p1][i2]; | |
| p = i3 + 1; | |
| sw = 1; | |
| } | |
| } | |
| } | |
| } | |
| p = 0; | |
| for (i2 = 0; i2 < len[p2]; i2++) { | |
| sw = 0; | |
| for (i3 = 0; i3 < len[p2] && sw == 0; i3++) { | |
| if (kou1[i3] > 0 && ind[p2][i2] == ind[k2][i3]) | |
| sw = 1; | |
| } | |
| if (sw == 0) { | |
| for (i3 = p; i3 < len[p2] && sw == 0; i3++) { | |
| if (kou1[i3] == 0) { | |
| ind[k2][i3] = ind[p2][i2]; | |
| p = i3 + 1; | |
| sw = 1; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /*******************************************************************/ | |
| /* 交叉（エッジ組み替え交叉．以下の手順に従って行う．対立遺伝子は */ | |
| /* 0～(max_len-1)である必要がある） */ | |
| /* (0) エッジマップを作成する．エッジマップとは，２つの親 */ | |
| /* を見て，ノードがどこに接続されているのかを表すもの */ | |
| /* であり，例えば，２つの親が， */ | |
| /* [A B C D E F] */ | |
| /* [B D C A E F] */ | |
| /* である場合は， */ | |
| /* A : B F C E */ | |
| /* B : A C D F */ | |
| /* C : B D A */ | |
| /* D : C E B */ | |
| /* E : D F A */ | |
| /* F : A E B */ | |
| /* となる． */ | |
| /* (1) 両親の２つの出発点の内１つで初期化する．ランダムま */ | |
| /* たはステップ(4)の基準に従って選ぶ（現在のノード） */ | |
| /* (2) エッジマップから，現在のノードを除く */ | |
| /* (3) 現在のノードが接続先のノードを持っていたら，(4)に */ | |
| /* 進む．さもなければ，(5)に進む */ | |
| /* (4) 現在のノードが持っている接続先ノードの内，最も少な */ | |
| /* い接続先ノードを持ったノードを選択し（同じ条件の場 */ | |
| /* 合は，ランダム），それを現在のノードとし，(2)に進む */ | |
| /* (5) 未接続のノードが残っていればランダムに選択し，(2)に */ | |
| /* 戻る．さもなければ，終了する */ | |
| /* kosa : 交叉確率 */ | |
| /* k_method : 選択方法 */ | |
| /* =-1 : ランダム */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* k_bias : α，または，method=2の場合は初期値 */ | |
| /* k_step : β */ | |
| /*******************************************************************/ | |
| void C_edge(double kosa, int k_method, double k_bias, double k_step) | |
| { | |
| int i1, i2, i3, i4, i5, k, kk, k0 = 0, k1, k2, min, num, | |
| p, pair, p1, p2 = 0, sw; | |
| int e[] = new int [2]; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| pair = max_ch; | |
| if (dup_a != 0) { | |
| System.out.print("***error 交叉方法が不適当 (C_edge)\n"); | |
| System.exit(1); | |
| } | |
| if (min_len > 0) { | |
| System.out.print("***error 遺伝子長は固定長でなければならない (C_edge)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < pair; i1++) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(1, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 親の選択 | |
| p1 = Select(k_method, k_bias, k_step); | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = Select(k_method, k_bias, k_step); | |
| if (p1 != p2) | |
| sw = 1; | |
| } | |
| // 遺伝子長 | |
| k = Position(-1); | |
| pi_w[k] = 1; | |
| len[k] = len[p1]; | |
| // エッジマップの初期化 | |
| for (i2 = 0; i2 < len[k]; i2++) { | |
| edge[i2][0] = 0; | |
| for (i3 = 1; i3 <= 4; i3++) | |
| edge[i2][i3] = -1; | |
| } | |
| // 交叉 | |
| // エッジマップの作成 | |
| for (i2 = 0; i2 < len[k]; i2++) { | |
| sw = 0; | |
| for (i3 = 0; i3 < len[k] && sw == 0; i3++) { | |
| if (i2 == ind[p1][i3]) { | |
| sw = 1; | |
| if (i3 == 0) { | |
| e[0] = ind[p1][len[k]-1]; | |
| e[1] = ind[p1][1]; | |
| } | |
| else { | |
| if (i3 == len[k]-1) { | |
| e[0] = ind[p1][i3-1]; | |
| e[1] = ind[p1][0]; | |
| } | |
| else { | |
| e[0] = ind[p1][i3-1]; | |
| e[1] = ind[p1][i3+1]; | |
| } | |
| } | |
| for (i4 = 0; i4 < 2; i4++) { | |
| edge[i2][0]++; | |
| edge[i2][edge[i2][0]] = e[i4]; | |
| } | |
| } | |
| } | |
| sw = 0; | |
| for (i3 = 0; i3 < len[k] && sw == 0; i3++) { | |
| if (i2 == ind[p2][i3]) { | |
| sw = 1; | |
| if (i3 == 0) { | |
| e[0] = ind[p2][len[k]-1]; | |
| e[1] = ind[p2][1]; | |
| } | |
| else { | |
| if (i3 == len[k]-1) { | |
| e[0] = ind[p2][i3-1]; | |
| e[1] = ind[p2][0]; | |
| } | |
| else { | |
| e[0] = ind[p2][i3-1]; | |
| e[1] = ind[p2][i3+1]; | |
| } | |
| } | |
| for (i4 = 0; i4 < 2; i4++) { | |
| sw = 1; | |
| for (i5 = 1; i5 <= edge[i2][0] && sw == 1; i5++) { | |
| if (edge[i2][i5] == e[i4]) | |
| sw = 2; | |
| } | |
| if (sw == 1) { | |
| edge[i2][0]++; | |
| edge[i2][edge[i2][0]] = e[i4]; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| // 交叉の実行 | |
| // 出発点の決定 | |
| k1 = ind[p1][0]; | |
| k2 = ind[p2][0]; | |
| if (edge[k1][0] == edge[k2][0]) | |
| kk = (rn.nextDouble() > 0.5) ? k2 : k1; | |
| else | |
| kk = (edge[k1][0] < edge[k2][0]) ? k1 : k2; | |
| ind[k][0] = kk; | |
| p = 1; | |
| while (p < len[k]) { | |
| // ノードの除去 | |
| for (i2 = 0; i2 < len[k]; i2++) { | |
| sw = 0; | |
| if (edge[i2][0] > 0) { | |
| for (i3 = 1; i3 <= 4 && sw == 0; i3++) { | |
| if (edge[i2][i3] == kk) { | |
| sw = 1; | |
| edge[i2][i3] = -1; | |
| edge[i2][0]--; | |
| } | |
| } | |
| } | |
| } | |
| // 次の現在ノードの選択 | |
| min = 10; | |
| num = 0; | |
| for (i2 = 1; i2 <= 4; i2++) { | |
| if (edge[kk][i2] >= 0) { | |
| k1 = edge[kk][i2]; | |
| if (edge[k1][0] >= 0 && edge[k1][0] < min) { | |
| num = 1; | |
| min = edge[k1][0]; | |
| k0 = k1; | |
| } | |
| else { | |
| if (edge[k1][0] == min) | |
| num++; | |
| } | |
| } | |
| } | |
| if (num > 1) { | |
| k1 = (int)(rn.nextDouble() * num) + 1; | |
| if (k1 > num) | |
| k1 = num; | |
| k2 = 0; | |
| k0 = -1; | |
| for (i2 = 1; i2 <= 4 && k0 < 0; i2++) { | |
| if (edge[kk][i2] >= 0) { | |
| if (edge[edge[kk][i2]][0] == min) { | |
| k2++; | |
| if (k1 == k2) | |
| k0 = edge[kk][i2]; | |
| } | |
| } | |
| } | |
| } | |
| else { | |
| if (num <= 0) { | |
| num = 0; | |
| for (i2 = 0; i2 < len[k]; i2++) { | |
| if (i2 != kk && edge[i2][0] >= 0) | |
| num++; | |
| } | |
| if (num <= 0) { | |
| System.out.print("***error invalid data (C_edge)\n"); | |
| System.exit(1); | |
| } | |
| else { | |
| k1 = (int)(rn.nextDouble() * num) + 1; | |
| if (k1 > num) | |
| k1 = num; | |
| k2 = 0; | |
| k0 = -1; | |
| for (i2 = 0; i2 < len[k] && k0 < 0; i2++) { | |
| if (i2 != kk && edge[i2][0] >= 0) { | |
| k2++; | |
| if (k1 == k2) | |
| k0 = i2; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| edge[kk][0] = -1; | |
| ind[k][p] = k0; | |
| kk = k0; | |
| p++; | |
| } | |
| } | |
| } | |
| } | |
| /*************************************************************/ | |
| /* 交叉（サブツアー交叉．２点交叉の拡張である．ただし，相手に*/ | |
| /* 同じ遺伝子のグループがない限り実行されない．たとえば*/ | |
| /* ***abcd** */ | |
| /* *cdab**** */ | |
| /* のような両親の時実行され，以下の４つの子供が生成され*/ | |
| /* る） */ | |
| /* ***cdab** */ | |
| /* *abcd**** */ | |
| /* ***badc** */ | |
| /* *dcba**** */ | |
| /* 最大，４＊交叉回数＊個体総数＊(個体総数－１) 個の子 */ | |
| /* 供が生成される可能性があるので，子供の数としてこの値*/ | |
| /* 以上のデータを入力しておく必要がある． */ | |
| /* kosa : 交叉確率 */ | |
| /* count : １つのペアーに対する交差回数 */ | |
| /*************************************************************/ | |
| void C_sub(double kosa, int count) | |
| { | |
| int i1, i2, i3, i4, i5, k1, k2, k3, k4, p1, p2, | |
| t11, t12 = 0, t21, t22 = 0, sw; | |
| /* | |
| 初期設定とデータのチェック | |
| */ | |
| if ((4*count*size*(size-1)) > max_ch) { | |
| System.out.print("***error 子供が多すぎる (C_sub)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 交叉 | |
| */ | |
| for (i1 = 0; i1 < size-1; i1++) { | |
| // 親１ | |
| p1 = Position(i1); | |
| if (p1 >= 0) { | |
| for (i2 = i1; i2 < size; i2++) { | |
| // 親２ | |
| p2 = Position(i2); | |
| if (p2 >= 0) { | |
| // 交叉しない場合 | |
| if (rn.nextDouble() > kosa) | |
| C_copy(2, 1, -1, 0.0, 0.0); | |
| // 交叉する場合 | |
| else { | |
| // 交叉回数の制御 | |
| for (i3 = 0; i3 < count; i3++) { | |
| // 交叉位置の決定（点の後ろで交叉） | |
| // 親１の交叉位置 | |
| t11 = (int)(rn.nextDouble() * len[p1]); | |
| if (t11 > (len[p1]-1)) | |
| t11 = len[p1] - 1; | |
| sw = 0; | |
| while (sw == 0) { | |
| t12 = (int)(rn.nextDouble() * len[p1]); | |
| if (t12 > (len[p1]-1)) | |
| t12 = len[p1] - 1; | |
| if (t12 != t11) | |
| sw = 1; | |
| } | |
| if (t11 > t12) { | |
| k1 = t11; | |
| t11 = t12; | |
| t12 = k1; | |
| } | |
| // 親２の交叉位置 | |
| sw = 0; | |
| t21 = -1; | |
| for (i4 = 0; i4 < len[p2] && t21 < 0; i4++) { | |
| for (i5 = t11; i5 <= t12 && t21 < 0; i5++) { | |
| if (ind[p2][i4] == ind[p1][i5]) | |
| t21 = i4; | |
| } | |
| } | |
| if (t21 >= 0) { | |
| t22 = t21 + t12 - t11; | |
| if (t22 < len[p2]) { | |
| sw = 1; | |
| for (i4 = t21+1; i4 <= t22 && sw > 0; i4++) { | |
| sw = 0; | |
| for (i5 = t11; i5 <= t12 && sw == 0; i5++) { | |
| if (ind[p2][i4] == ind[p1][i5]) | |
| sw = 1; | |
| } | |
| } | |
| } | |
| } | |
| // 交叉の実行 | |
| if (sw > 0) { | |
| k1 = Position(-1); | |
| pi_w[k1] = 1; | |
| len[k1] = len[p1]; | |
| k2 = Position(-1); | |
| pi_w[k2] = 1; | |
| len[k2] = len[p1]; | |
| k3 = Position(-1); | |
| pi_w[k3] = 1; | |
| len[k3] = len[p2]; | |
| k4 = Position(-1); | |
| pi_w[k4] = 1; | |
| len[k4] = len[p2]; | |
| for (i4 = 0; i4 < t11; i4++) { | |
| ind[k1][i4] = ind[p1][i4]; | |
| ind[k2][i4] = ind[p1][i4]; | |
| } | |
| for (i4 = t11; i4 <= t12; i4++) { | |
| ind[k1][i4] = ind[p2][t21+i4-t11]; | |
| ind[k2][i4] = ind[p2][t22-i4+t11]; | |
| } | |
| for (i4 = t12+1; i4 < len[p1]; i4++) { | |
| ind[k1][i4] = ind[p1][i4]; | |
| ind[k2][i4] = ind[p1][i4]; | |
| } | |
| for (i4 = 0; i4 < t21; i4++) { | |
| ind[k3][i4] = ind[p2][i4]; | |
| ind[k4][i4] = ind[p2][i4]; | |
| } | |
| for (i4 = t21; i4 <= t22; i4++) { | |
| ind[k3][i4] = ind[p1][t11+i4-t21]; | |
| ind[k4][i4] = ind[p1][t12-i4+t21]; | |
| } | |
| for (i4 = t22+1; i4 < len[p2]; i4++) { | |
| ind[k3][i4] = ind[p2][i4]; | |
| ind[k4][i4] = ind[p2][i4]; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /**************************************/ | |
| /* 突然変異（対立遺伝子との置き換え） */ | |
| /* pr : 突然変異率 */ | |
| /**************************************/ | |
| void M_alle(double pr) | |
| { | |
| int i1, i2, lid; | |
| /* | |
| データのチェックと初期設定 | |
| */ | |
| if (dup_a == 0) { | |
| System.out.print("***error 突然変異方法が不適当 (M_alle)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 実行 | |
| */ | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1) { | |
| for (i2 = 0; i2 < len[i1]; i2++) { | |
| if (rn.nextDouble() <= pr) { | |
| lid = (int)(rn.nextDouble() * (allele_u - allele_l + 1) + allele_l); | |
| if (lid > allele_u) | |
| lid = allele_u; | |
| if (lid != ind[i1][i2]) | |
| ind[i1][i2] = lid; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /**********************************************************************/ | |
| /* 突然変異（移動．２点を選択し，２番目の遺伝子を１番目の遺伝子の前に */ | |
| /* 移動する） */ | |
| /* pr : 突然変異率 */ | |
| /**********************************************************************/ | |
| void M_move(double pr) | |
| { | |
| int i1, i2, ld, p1, p2 = 0, sw; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1 && rn.nextDouble() <= pr) { | |
| /* | |
| 位置の決定 | |
| */ | |
| // p1 | |
| p1 = (int)(rn.nextDouble() * len[i1]); | |
| if (p1 >= len[i1]) | |
| p1 = len[i1] - 1; | |
| // p2 | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = (int)(rn.nextDouble() * len[i1]); | |
| if (p2 >= len[i1]) | |
| p2 = len[i1] - 1; | |
| if (p2 != p1) | |
| sw = 1; | |
| } | |
| /* | |
| 実行 | |
| */ | |
| if (p2 > p1) { | |
| ld = ind[i1][p2]; | |
| for (i2 = p2; i2 > p1; i2--) | |
| ind[i1][i2] = ind[i1][i2-1]; | |
| ind[i1][p1] = ld; | |
| } | |
| else { | |
| ld = ind[i1][p2]; | |
| for (i2 = p2; i2 < p1-1; i2++) | |
| ind[i1][i2] = ind[i1][i2+1]; | |
| ind[i1][p1-1] = ld; | |
| } | |
| } | |
| } | |
| } | |
| /********************************************************/ | |
| /* 突然変異（逆位．２点間の遺伝子順序を逆に並べ替える） */ | |
| /* pr : 突然変異率 */ | |
| /* wd : >0 : 幅を固定 */ | |
| /* =0 : 幅をランダム */ | |
| /********************************************************/ | |
| void M_inv(double pr, int wd) | |
| { | |
| int i1, lid, p, p1, p2 = 0, sw; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1 && rn.nextDouble() <= pr) { | |
| /* | |
| 区間の決定 | |
| */ | |
| if (wd == 0) { | |
| p1 = (int)(rn.nextDouble() * len[i1]); | |
| if (p1 >= len[i1]) | |
| p1 = len[i1] - 1; | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = (int)(rn.nextDouble() * len[i1]); | |
| if (p2 >= len[i1]) | |
| p2 = len[i1] - 1; | |
| if (p2 != p1) | |
| sw = 1; | |
| } | |
| if (p1 > p2) { | |
| p = p1; | |
| p1 = p2; | |
| p2 = p; | |
| } | |
| } | |
| else { | |
| p1 = len[i1]; | |
| while (p1 > len[i1]-2) | |
| p1 = (int)(rn.nextDouble() * len[i1]); | |
| p2 = p1 + wd - 1; | |
| if (p2 >= len[i1]) | |
| p2 = len[i1] - 1; | |
| } | |
| /* | |
| 実行 | |
| */ | |
| sw = 0; | |
| while (sw == 0) { | |
| lid = ind[i1][p1]; | |
| ind[i1][p1] = ind[i1][p2]; | |
| ind[i1][p2] = lid; | |
| p1++; | |
| p2--; | |
| if (p1 >= p2) | |
| sw = 1; | |
| } | |
| } | |
| } | |
| } | |
| /**********************************************************************/ | |
| /* 突然変異（スクランブル．２点間の遺伝子順序をランダムに並べ替える） */ | |
| /* pr : 突然変異率 */ | |
| /* wd : >0 : 幅を固定 */ | |
| /* =0 : 幅をランダム */ | |
| /**********************************************************************/ | |
| void M_scram(double pr, int wd) | |
| { | |
| int i1, i2, ld, p, p1, p2 = 0, sw; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1 && rn.nextDouble() <= pr) { | |
| /* | |
| 区間の決定 | |
| */ | |
| if (wd == 0) { | |
| p1 = (int)(rn.nextDouble() * len[i1]); | |
| if (p1 >= len[i1]) | |
| p1 = len[i1] - 1; | |
| sw = 0; | |
| while (sw == 0) { | |
| p2 = (int)(rn.nextDouble() * len[i1]); | |
| if (p2 >= len[i1]) | |
| p2 = len[i1] - 1; | |
| if (p2 != p1) | |
| sw = 1; | |
| } | |
| if (p1 > p2) { | |
| p = p1; | |
| p1 = p2; | |
| p2 = p; | |
| } | |
| } | |
| else { | |
| p1 = len[i1]; | |
| while (p1 > len[i1]-2) | |
| p1 = (int)(rn.nextDouble() * len[i1]); | |
| p2 = p1 + wd - 1; | |
| if (p2 >= len[i1]) | |
| p2 = len[i1] - 1; | |
| } | |
| /* | |
| 実行 | |
| */ | |
| for (i2 = p1; i2 <= p2; i2++) { | |
| p = (int)(rn.nextDouble() * (p2 - p1 + 1) + p1); | |
| if (p > p2) | |
| p = p2; | |
| ld = ind[i1][i2]; | |
| ind[i1][i2] = ind[i1][p]; | |
| ind[i1][p] = ld; | |
| } | |
| } | |
| } | |
| } | |
| /**********************************************************************/ | |
| /* 突然変異（転座．２点間の遺伝子を他の位置のものと置き換える．ただし */ | |
| /* 重複部分はそのままとする） */ | |
| /* pr : 突然変異率 */ | |
| /* wd : >0 : 幅を固定 */ | |
| /* =0 : 幅をランダム */ | |
| /**********************************************************************/ | |
| void M_chg(double pr, int wd) | |
| { | |
| int i1, i2, ld, p, p1, p2, p3 = 0, p4, sw; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1 && rn.nextDouble() <= pr) { | |
| /* | |
| 区間等の決定（[p1,p2]と[p3,p4]の入れ替え） | |
| */ | |
| // p1 | |
| p1 = (int)(rn.nextDouble() * len[i1]); | |
| if (p1 >= len[i1]) | |
| p1 = len[i1] - 1; | |
| // p3 | |
| sw = 0; | |
| while (sw == 0) { | |
| p3 = (int)(rn.nextDouble() * len[i1]); | |
| if (p3 >= len[i1]) | |
| p3 = len[i1] - 1; | |
| if (p3 != p1) | |
| sw = 1; | |
| } | |
| // 小さい方をp1,p2にする | |
| if (p1 > p3) { | |
| p = p1; | |
| p1 = p3; | |
| p3 = p; | |
| } | |
| // p4, p2 | |
| p4 = (wd == 0) ? (int)(rn.nextDouble() * (len[i1] - p3)) + p3 : | |
| p1 + wd - 1; | |
| if (p4 >= len[i1]) | |
| p4 = len[i1] - 1; | |
| p2 = p1 + (p4 - p3); | |
| // 重複部分のチェック | |
| if (p2 >= p3) { | |
| p = p3 - 1; | |
| p3 = p2 + 1; | |
| p2 = p; | |
| p4 = p3 + (p2 - p1); | |
| } | |
| /* | |
| 実行 | |
| */ | |
| p = p3; | |
| for (i2 = p1; i2 <= p2; i2++) { | |
| ld = ind[i1][i2]; | |
| ind[i1][i2] = ind[i1][p]; | |
| ind[i1][p] = ld; | |
| p++; | |
| } | |
| } | |
| } | |
| } | |
| /**********************************************************************/ | |
| /* 突然変異（重複．２点間の遺伝子を他の位置にコピーする */ | |
| /* pr : 突然変異率 */ | |
| /* wd : >0 : 幅を固定 */ | |
| /* =0 : 幅をランダム */ | |
| /**********************************************************************/ | |
| void M_dup(double pr, int wd) | |
| { | |
| int i1, i2, p, p1, p2, p3 = 0, p4, sw; | |
| /* | |
| データのチェック | |
| */ | |
| if (dup_a == 0) { | |
| System.out.print("***error 突然変異方法が不適当 (M_dup)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 実行 | |
| */ | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1 && rn.nextDouble() <= pr) { | |
| // 区間の決定（[p1,p2]を[p3,p4]にコピー） | |
| // p1 | |
| p1 = (int)(rn.nextDouble() * len[i1]); | |
| if (p1 >= len[i1]) | |
| p1 = len[i1] - 1; | |
| // p3 | |
| sw = 0; | |
| while (sw == 0) { | |
| p3 = (int)(rn.nextDouble() * len[i1]); | |
| if (p3 >= len[i1]) | |
| p3 = len[i1] - 1; | |
| if (p3 != p1) | |
| sw = 1; | |
| } | |
| // 区間を決める | |
| if (p3 > p1) { | |
| p4 = (wd == 0) ? (int)(rn.nextDouble() * (len[i1] - p3)) + p3 : | |
| p3 + wd - 1; | |
| if (p4 >= len[i1]) | |
| p4 = len[i1] - 1; | |
| p2 = p1 + (p4 - p3); | |
| } | |
| else { | |
| p2 = (wd == 0) ? (int)(rn.nextDouble() * (len[i1] - p1)) + p1 : | |
| p1 + wd - 1; | |
| if (p2 >= len[i1]) | |
| p2 = len[i1] - 1; | |
| p4 = p3 + (p2 - p1); | |
| } | |
| // 実行 | |
| p = p4; | |
| for (i2 = p2; i2 >= p1; i2--) { | |
| ind[i1][p] = ind[i1][i2]; | |
| p--; | |
| } | |
| } | |
| } | |
| } | |
| /******************************************************/ | |
| /* 突然変異（摂動．値をある量だけ変化させる） */ | |
| /* pr : 突然変異率 */ | |
| /* method : =0 : 正規分布 */ | |
| /* =1 : 一様分布 */ | |
| /* m : 平均または一様分布の下限 */ | |
| /* s : 標準偏差または一様分布の上限 */ | |
| /******************************************************/ | |
| void M_per(double pr, int method, double m, double s) | |
| { | |
| double w, wd = 0.0, x1; | |
| int i1, i2; | |
| /* | |
| データのチェックと初期設定 | |
| */ | |
| if (dup_a == 0) { | |
| System.out.print("***error 突然変異方法が不適当 (M_per)\n"); | |
| System.exit(1); | |
| } | |
| if (method > 0) | |
| wd = s - m; | |
| /* | |
| 実行 | |
| */ | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1) { | |
| for (i2 = 0; i2 < len[i1]; i2++) { | |
| if (rn.nextDouble() <= pr) { | |
| if (method == 0) | |
| w = norm_d(m, s); | |
| else { | |
| w = rn.nextDouble() * wd; | |
| if (rn.nextDouble() < 0.5) | |
| w = -w; | |
| } | |
| x1 = (double)ind[i1][i2] + w; | |
| if (x1 > allele_u) | |
| x1 = allele_u; | |
| else { | |
| if (x1 < allele_l) | |
| x1 = allele_l; | |
| } | |
| ind[i1][i2] = (int)x1; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| /**********************************************************************/ | |
| /* 突然変異（挿入．ある長さの遺伝子を挿入する） */ | |
| /* pr : 突然変異率 */ | |
| /* wd : >0 : 幅を固定 */ | |
| /* =0 : 幅をランダム */ | |
| /**********************************************************************/ | |
| void M_ins(double pr, int wd) | |
| { | |
| int i1, i2, l, ld, p; | |
| /* | |
| データのチェック | |
| */ | |
| if (dup_a == 0 || min_len < 0) { | |
| System.out.print("***error 突然変異方法が不適当 (M_ins)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 実行 | |
| */ | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1 && rn.nextDouble() <= pr) { | |
| // 挿入位置の決定 | |
| p = (int)(rn.nextDouble() * (len[i1]+1)); | |
| if (p > len[i1]) | |
| p = len[i1]; | |
| // 挿入する遺伝子長の決定 | |
| l = (wd == 0) ? (int)(rn.nextDouble() * (max_len - len[i1] + 1)) : wd; | |
| if (l > max_len-len[i1]) | |
| l = max_len - len[i1]; | |
| else { | |
| if (l <= 0) | |
| l = 1; | |
| } | |
| // 実行 | |
| // 挿入場所の確保 | |
| if (p < len[i1]) { | |
| for (i2 = len[i1]+l-1; i2 >= p; i2--) | |
| ind[i1][i2] = ind[i1][i2-l]; | |
| } | |
| // 挿入場所の遺伝子の決定 | |
| for (i2 = p; i2 < p+l; i2++) { | |
| ld = (int)(rn.nextDouble() * (allele_u - allele_l + 1) + allele_l); | |
| if (ld > allele_u) | |
| ld = allele_u; | |
| ind[i1][i2] = ld; | |
| } | |
| len[i1] += l; | |
| } | |
| } | |
| } | |
| /**********************************************************************/ | |
| /* 突然変異（削除．ある長さの遺伝子を削除する） */ | |
| /* pr : 突然変異率 */ | |
| /* wd : >0 : 幅を固定 */ | |
| /* =0 : 幅をランダム */ | |
| /**********************************************************************/ | |
| void M_del(double pr, int wd) | |
| { | |
| int i1, i2, l, max, p; | |
| /* | |
| データのチェック | |
| */ | |
| if (dup_a == 0 || min_len < 0) { | |
| System.out.print("***error 突然変異方法が不適当 (M_del)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 実行 | |
| */ | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1 && rn.nextDouble() <= pr) { | |
| // 削除位置の決定 | |
| p = (int)(rn.nextDouble() * len[i1]); | |
| if (p >= len[i1]) | |
| p = len[i1] - 1; | |
| // 削除する遺伝子長の決定 | |
| max = (len[i1]-min_len < len[i1]-p) ? len[i1] - min_len : len[i1] - p; | |
| l = (wd == 0) ? (int)(rn.nextDouble() * max + 1) : wd; | |
| if (l > max) | |
| l = max; | |
| // 実行 | |
| for (i2 = 0; i2 < len[i1]-p-l; i2++) | |
| ind[i1][p+i2] = ind[i1][p+i2+l]; | |
| len[i1] -= l; | |
| } | |
| } | |
| } | |
| /*********************************************************************/ | |
| /* 淘汰（エリート・ルーレット選択） */ | |
| /* elite : エリートで残す個体数(default=0) */ | |
| /* s_method : ルーレット板の作成方法(default=1) */ | |
| /* =0 : 適応度をそのまま使用 */ | |
| /* =1 : 最小値からの差（ただし，α以下の場合はα） */ | |
| /* =2 : 評価値に順位をつけ，減少率βで線形化 */ | |
| /* s_bias : α，または，method=2の場合は初期値(default=0) */ | |
| /* s_step : β(default=1) */ | |
| /*********************************************************************/ | |
| void S_roul(int elite, int s_method, double s_bias, double s_step) | |
| { | |
| int count = 0, i1, i2, i3, k = 0, max, n = 0, p, sw; | |
| /* | |
| 値のチェックと初期設定 | |
| */ | |
| if (s_method != 0 && s_method != 2) | |
| s_method = 1; | |
| if (elite > size) { | |
| System.out.print("***error エリートで残す数が多すぎる (S_roul)\n"); | |
| System.exit(1); | |
| } | |
| if (s_method == 2 && s_step <= 0.0) | |
| s_step = 1.0; | |
| for (i1 = 0; i1 < size+max_ch; i1++) | |
| s_w[i1] = 0; | |
| /* | |
| 重複個体を削除 | |
| */ | |
| if (dup_s == 0) { | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 0) { | |
| for (i2 = i1+1; i2 < size+max_ch; i2++) { | |
| if (pi_w[i2] > 0 && len[i1] == len[i2]) { | |
| sw = 0; | |
| for (i3 = 0; i3 < len[i1] && sw == 0; i3++) { | |
| if (ind[i1][i3] != ind[i2][i3]) | |
| sw = 1; | |
| } | |
| if (sw == 0) | |
| pi_w[i2] = 0; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1) | |
| n++; | |
| } | |
| if (n < 0 || dup_s == 0 && n < size) { | |
| System.out.print("***error 残す個体がない (S_roul)\n"); | |
| System.exit(1); | |
| } | |
| /* | |
| 淘汰して残す個体を選ぶ | |
| */ | |
| // エリートの選択 | |
| sw = 0; | |
| while (k < elite && k < n && sw == 0) { | |
| max = -1; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] > 1 && s_w[i1] == 0) { | |
| if (max < 0 || pi[i1] > pi[max]) | |
| max = i1; | |
| } | |
| } | |
| if (max < 0) | |
| sw = 1; | |
| else { | |
| s_w[max] = 1; | |
| k++; | |
| } | |
| } | |
| // ルーレット選択 | |
| while (count < size+max_ch && k < size) { | |
| p = Select(s_method, s_bias, s_step); | |
| if (dup_s == 0 && s_w[p] > 0) | |
| count++; | |
| else { | |
| count = 0; | |
| s_w[p]++; | |
| k++; | |
| } | |
| } | |
| // 選択に失敗した場合の処理 | |
| if (dup_s == 0 && k < size) { | |
| for (i1 = 0; i1 < size+max_ch && k < size; i1++) { | |
| if (pi_w[i1] > 1 && s_w[i1] == 0) { | |
| s_w[i1] = 1; | |
| k++; | |
| } | |
| } | |
| } | |
| // 複数回選択されたものの処理 | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (s_w[i1] == 0) | |
| pi_w[i1] = 0; | |
| } | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (s_w[i1] > 0) { | |
| if (s_w[i1] > 1) { | |
| for (i2 = 2; i2 <= s_w[i1]; i2++) { | |
| k = Position(-1); | |
| len[k] = len[i1]; | |
| pi_w[k] = 2; | |
| pi[k] = pi[i1]; | |
| for (i3 = 0; i3 < len[i1]; i3++) | |
| ind[k][i3] = ind[i1][i3]; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| ------------------------クラスTSP----------------- | |
| /*******************/ | |
| /* クラスTSPの定義 */ | |
| /*******************/ | |
| import java.io.*; | |
| import java.util.Date; | |
| import java.util.Random; | |
| import java.util.StringTokenizer; | |
| class TSP extends Species { | |
| private int max_gen; // 最大世代交代数 | |
| private int kosa_m; // 交叉方法 | |
| // =-1 : 交叉を使用しない | |
| // =0 : 親のコピー | |
| // =1 : 循環交叉 | |
| // =2 : 部分的交叉 | |
| // =3 : 順序交叉 | |
| // =4 : 一様順序交叉 | |
| // =5 : 一様位置交叉 | |
| // =6 : エッジ組み替え交叉 | |
| // =7 : サブツアー交叉 | |
| private double kosa; // 交叉確率 | |
| private int k_point; // 交差点の数（負の時は，1から-point間のランダム） | |
| private int k_vr; // =0 : 両親とも同じ位置で交叉 | |
| // =1 : 両親が異なる位置で交叉（遺伝子長は可変） | |
| private int k_method; // 交叉の時の親の選択方法 | |
| // =-1 : ランダム | |
| // =0 : 適応度をそのまま使用 | |
| // =1 : 最小値からの差（ただし，α以下の場合はα） | |
| // =2 : 評価値に順位をつけ，減少率βで線形化 | |
| private double k_bias; // α，または，method=2の場合は初期値 | |
| private double k_step; // β | |
| private int mute_m; // 突然変異方法 | |
| // =-1 : 突然変異を使用しない | |
| // =0 : 移動 | |
| // =1 : 逆位 | |
| // =2 : スクランブル | |
| // =3 : 転座 | |
| private double mute; // 突然変異率 | |
| private int wd; // 突然変異に使用する部分遺伝子長 | |
| private double m_mean; // 摂動の平均値 | |
| private double m_std; // 摂動の標準偏差 | |
| private int elite; // エリート選択で残す数 | |
| private int s_method; // ルーレット板の作成方法 | |
| // =0 : 適応度をそのまま使用 | |
| // =1 : 最小値からの差（ただし，α以下の場合はα） | |
| // =2 : 評価値に順位をつけ，減少率βで線形化 | |
| private double s_bias; // α，または，s_method=2の場合は初期値 | |
| private double s_step; // β | |
| private int out_d; // 表示間隔 | |
| private int out_lvl; // 出力レベル | |
| // =0 : 最終出力だけ | |
| // n>0 : ｎ世代毎に出力（負の時はファイル） | |
| private int out_m; // 出力方法 | |
| // =0 : すべてを出力 | |
| // =1 : 最大適応度の個体だけを出力 | |
| private String o_file; // 出力ファイル名 | |
| private int n_city; // 都市の数 | |
| private int [][] rg; // 都市間の距離 | |
| private int kinbo; // 近傍探索（０：行わない，１：行う） | |
| private int neib; // 近傍（2 or 3） | |
| private int sel; // エッジの選択方法 | |
| // =0 : 最良のものを選択 | |
| // =1 : 最初のものを選択 | |
| private Win wn; // Winオブジェクト | |
| int [][] city; //都市の位置データ | |
| int display; // 画面表示 | |
| // =0 : 画面表示を行わない | |
| // =1 : 結果だけを表示 | |
| // =2 : 初期状態と結果を表示 | |
| // =3 : out_lvlで指定された世代毎に表示 | |
| /***************************************/ | |
| /* コンストラクタ */ | |
| /* name1 : Species定義ファイル名 */ | |
| /* name2 : TSP定義ファイル名 */ | |
| /* seed : 乱数の初期値 */ | |
| /***************************************/ | |
| TSP (String name1, String name2, int seed) throws IOException, FileNotFoundException | |
| { | |
| super (name1, seed); | |
| double x, y; | |
| int i1, i2; | |
| String line; | |
| StringTokenizer dt; | |
| BufferedReader in = new BufferedReader(new FileReader(name2)); | |
| // 基本データの入力 | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| out_lvl = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| out_m = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| o_file = dt.nextToken(); | |
| dt.nextToken(); | |
| out_d = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| kosa_m = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| kosa = Double.parseDouble(dt.nextToken()); | |
| dt.nextToken(); | |
| k_point = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| k_vr = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| k_method = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| k_bias = Double.parseDouble(dt.nextToken()); | |
| dt.nextToken(); | |
| k_step = Double.parseDouble(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| mute_m = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| mute = Double.parseDouble(dt.nextToken()); | |
| dt.nextToken(); | |
| wd = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| m_mean = Double.parseDouble(dt.nextToken()); | |
| dt.nextToken(); | |
| m_std = Double.parseDouble(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| elite = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| s_method = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| s_bias = Double.parseDouble(dt.nextToken()); | |
| dt.nextToken(); | |
| s_step = Double.parseDouble(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| n_city = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| max_gen = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| kinbo = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| neib = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| sel = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| display = Integer.parseInt(dt.nextToken()); | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| dt.nextToken(); | |
| int font = Integer.parseInt(dt.nextToken()); | |
| dt.nextToken(); | |
| int width = Integer.parseInt(dt.nextToken()); | |
| int height = Integer.parseInt(dt.nextToken()); | |
| if (kinbo > 0 && neib != 2 && neib != 3) { | |
| System.out.print("***error 近傍の値が不適当 \n"); | |
| System.exit(1); | |
| } | |
| if (n_city != max_len) { | |
| System.out.print("***error 都市数が不適当 \n"); | |
| System.exit(1); | |
| } | |
| // 都市の位置データ | |
| city = new int [n_city][2]; | |
| for (i1 = 0; i1 < n_city; i1++) { | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| city[i1][0] = Integer.parseInt(dt.nextToken()); | |
| city[i1][1] = Integer.parseInt(dt.nextToken()); | |
| } | |
| // 距離テーブル | |
| rg = new int [n_city][n_city]; | |
| for (i1 = 0; i1 < n_city; i1++) { | |
| for (i2 = i1+1; i2 < n_city; i2++) { | |
| x = city[i2][0] - city[i1][0]; | |
| y = city[i2][1] - city[i1][1]; | |
| rg[i1][i2] = (int)(Math.sqrt(x * x + y * y) + 0.5); | |
| } | |
| } | |
| for (i1 = 1; i1 < n_city; i1++) { | |
| for (i2 = 0; i2 < i1; i2++) | |
| rg[i1][i2] = rg[i2][i1]; | |
| } | |
| in.close(); | |
| // Windowの生成 | |
| if (display > 0) | |
| wn = new Win (this, font, width, height, n_city); | |
| } | |
| /**************/ | |
| /* 全体の制御 */ | |
| /**************/ | |
| void Control() throws IOException, FileNotFoundException | |
| { | |
| int gen = 1, k1; | |
| BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); | |
| // 初期集団の発生 | |
| Init_std(); | |
| // 評価 | |
| if (kinbo > 0) | |
| Kinbo(); | |
| else | |
| Adap(); | |
| // 画面表示 | |
| System.out.println("***世代 " + gen + " 適応度 max " + max + | |
| " (" + max_n + ") mean " + mean); | |
| // 初期状態の出力（図） | |
| if (display >= 2) { | |
| wn.Draw(max, ind[max_n]); | |
| System.out.println(" 図を確認したらreturnキーを押してください"); | |
| in.readLine(); | |
| } | |
| // 出力 | |
| if (Math.abs(out_lvl) > 0) | |
| Output(gen); | |
| // 世代交代 | |
| for (gen = 2; gen <= max_gen; gen++) { | |
| // 交叉 | |
| switch (kosa_m) { | |
| case -1: | |
| break; | |
| case 0: | |
| C_copy(2, max_ch/2, k_method, k_bias, k_step); // 親のコピー | |
| break; | |
| case 1: | |
| C_cycle(kosa, k_method, k_bias, k_step); // 循環交叉 | |
| break; | |
| case 2: | |
| C_part(kosa, k_method, k_bias, k_step); // 部分的交叉 | |
| break; | |
| case 3: | |
| C_seq(kosa, k_method, k_bias, k_step); // 順序交叉 | |
| break; | |
| case 4: | |
| C_useq(kosa, k_method, k_bias, k_step); // 一様順序交叉 | |
| break; | |
| case 5: | |
| C_upos(kosa, k_method, k_bias, k_step); // 一様位置交叉 | |
| break; | |
| case 6: | |
| C_edge(kosa, k_method, k_bias, k_step); // エッジ組み替え交叉 | |
| break; | |
| case 7: | |
| C_sub(kosa, k_point); // サブツアー交叉 | |
| break; | |
| default: | |
| break; | |
| } | |
| // 突然変異 | |
| switch (mute_m) { | |
| case -1: | |
| break; | |
| case 0: | |
| M_move(mute); // 移動 | |
| break; | |
| case 1: | |
| M_inv(mute, wd); // 逆位 | |
| break; | |
| case 2: | |
| M_scram(mute, wd); // スクランブル | |
| break; | |
| case 3: | |
| M_chg(mute, wd); // 転座 | |
| break; | |
| default: | |
| break; | |
| } | |
| // 適応度 | |
| if (kinbo > 0) | |
| Kinbo(); | |
| else | |
| Adap(); | |
| // 淘汰 | |
| S_roul(elite, s_method, s_bias, s_step); | |
| // 画面表示 | |
| if (gen%out_d == 0) | |
| System.out.println("***世代 " + gen + " 適応度 max " + max + | |
| " (" + max_n + ") mean " + mean); | |
| // 文字出力と図示 | |
| if (Math.abs(out_lvl) > 0) { | |
| if (gen%Math.abs(out_lvl) == 0) { | |
| if (display == 3) { | |
| wn.Draw(max, ind[max_n]); | |
| System.out.println(" 図を確認したらreturnキーを押してください"); | |
| in.readLine(); | |
| } | |
| Output(gen); | |
| } | |
| } | |
| } | |
| gen--; | |
| k1 = out_m; | |
| out_m = 0; | |
| System.out.println("***世代 " + gen + " 適応度 max " + max + | |
| " (" + max_n + ") mean " + mean); | |
| if (display >= 1) { | |
| wn.Draw(max, ind[max_n]); | |
| System.out.println(" 図を確認したらreturnキーを押してください"); | |
| in.readLine(); | |
| } | |
| Output(gen); | |
| out_m = k1; | |
| } | |
| /*********************************/ | |
| /* 距離の計算 */ | |
| /* n_c : 都市の数 */ | |
| /* p : 都市番号 */ | |
| /* return : 距離（負） */ | |
| /*********************************/ | |
| int Kyori(int n_c, int [] p) | |
| { | |
| int i1, n1, n2, range = 0; | |
| n1 = p[0]; | |
| for (i1 = 1; i1 < n_c; i1++) { | |
| n2 = p[i1]; | |
| range -= rg[n1][n2]; | |
| n1 = n2; | |
| } | |
| n2 = p[0]; | |
| range -= rg[n1][n2]; | |
| return range; | |
| } | |
| /****************/ | |
| /* 適応度の計算 */ | |
| /****************/ | |
| void Adap() | |
| { | |
| int i1, k = 0; | |
| mean = 0.0; | |
| max = 0.0; | |
| max_n = -1; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1) { | |
| pi_w[i1] = 2; | |
| pi[i1] = Kyori(len[i1], ind[i1]); | |
| } | |
| if (pi_w[i1] > 0) { | |
| k++; | |
| mean += pi[i1]; | |
| if (max_n < 0 || pi[i1] > max) { | |
| max = pi[i1]; | |
| max_n = i1; | |
| } | |
| } | |
| } | |
| if (k > 0) | |
| mean /= k; | |
| } | |
| /**************************************/ | |
| /* エッジの入れ替え */ | |
| /* n_city : 都市の数 */ | |
| /* seq : 訪問する順番 */ | |
| /* r_m : 距離の負値 */ | |
| /* return : =0 : 改善がなかった */ | |
| /* =1 : 改善があった */ | |
| /**************************************/ | |
| int Change(int n_city, int [] seq, int [] r_m) | |
| { | |
| int ch = 0, i1, i2, i3, i4, k, k1, k2, max, n1, n2, n3, nn, r, sw = 0; | |
| max = r_m[0]; | |
| n3 = (int)(rn.nextDouble() * (n_city - 2)); | |
| if (n3 > n_city-3) | |
| n3 = n_city - 3; | |
| // ２近傍 | |
| for (i1 = 0; i1 <= n_city-3 && ch == 0; i1++) { | |
| if (n3 == 0) | |
| n1 = n_city - 2; | |
| else | |
| n1 = n_city - 1; | |
| for (i2 = n3+2; i2 <= n1 && ch == 0; i2++) { | |
| // 枝の場所（(n3,n3+1), (k1,k2)） | |
| k1 = i2; | |
| if (i2 == n_city-1) | |
| k2 = 0; | |
| else | |
| k2 = i2 + 1; | |
| // 枝の入れ替え | |
| kou1[0] = seq[n3]; | |
| k = 1; | |
| for (i3 = k1; i3 >= n3+1; i3--) { | |
| kou1[k] = seq[i3]; | |
| k++; | |
| } | |
| nn = k2; | |
| while (nn != n3) { | |
| kou1[k] = seq[nn]; | |
| k++; | |
| nn++; | |
| if (nn > n_city-1) | |
| nn = 0; | |
| } | |
| // 評価 | |
| r = Kyori(n_city, kou1); | |
| if (r > max) { | |
| max = r; | |
| sw = 1; | |
| for (i3 = 0; i3 < n_city; i3++) | |
| kou2[i3] = kou1[i3]; | |
| if (sel > 0) | |
| ch = 1; | |
| } | |
| } | |
| n3++; | |
| if (n3 > n_city-3) | |
| n3 = 0; | |
| } | |
| // ３近傍 | |
| if (neib == 3 && ch == 0) { | |
| for (i1 = 0; i1 <= n_city-3 && ch == 0; i1++) { | |
| n1 = n_city - 2; | |
| n2 = n_city - 1; | |
| for (i2 = n3+1; i2 <= n1 && ch == 0; i2++) { | |
| for (i3 = i2+1; i3 <= n2 && ch == 0; i3++) { | |
| // 枝の場所（(n3,n3+1), (i2,i2+1), (k1,k2)） | |
| k1 = i3; | |
| if (i3 == n_city-1) | |
| k2 = 0; | |
| else | |
| k2 = i3 + 1; | |
| // 枝の入れ替えと評価 | |
| // 入れ替え（その１） | |
| kou1[0] = seq[n3]; | |
| k = 1; | |
| for (i4 = i2; i4 >= n3+1; i4--) { | |
| kou1[k] = seq[i4]; | |
| k++; | |
| } | |
| for (i4 = k1; i4 >= i2+1; i4--) { | |
| kou1[k] = seq[i4]; | |
| k++; | |
| } | |
| nn = k2; | |
| while (nn != n3) { | |
| kou1[k] = seq[nn]; | |
| k++; | |
| nn++; | |
| if (nn > n_city-1) | |
| nn = 0; | |
| } | |
| // 評価（その１） | |
| r = Kyori(n_city, kou1); | |
| if (r > max) { | |
| max = r; | |
| sw = 1; | |
| for (i3 = 0; i3 < n_city; i3++) | |
| kou2[i3] = kou1[i3]; | |
| if (sel > 0) | |
| ch = 1; | |
| } | |
| // 入れ替え（その２） | |
| kou1[0] = seq[n3]; | |
| k = 1; | |
| for (i4 = k1; i4 >= i2+1; i4--) { | |
| kou1[k] = seq[i4]; | |
| k++; | |
| } | |
| for (i4 = n3+1; i4 <= i2; i4++) { | |
| kou1[k] = seq[i4]; | |
| k++; | |
| } | |
| nn = k2; | |
| while (nn != n3) { | |
| kou1[k] = seq[nn]; | |
| k++; | |
| nn++; | |
| if (nn > n_city-1) | |
| nn = 0; | |
| } | |
| // 評価（その２） | |
| r = Kyori(n_city, kou1); | |
| if (r > max) { | |
| max = r; | |
| sw = 1; | |
| for (i3 = 0; i3 < n_city; i3++) | |
| kou2[i3] = kou1[i3]; | |
| if (sel > 0) | |
| ch = 1; | |
| } | |
| // 入れ替え（その３） | |
| kou1[0] = seq[n3]; | |
| k = 1; | |
| for (i4 = i2+1; i4 <= k1; i4++) { | |
| kou1[k] = seq[i4]; | |
| k++; | |
| } | |
| for (i4 = i2; i4 >= n3+1; i4--) { | |
| kou1[k] = seq[i4]; | |
| k++; | |
| } | |
| nn = k2; | |
| while (nn != n3) { | |
| kou1[k] = seq[nn]; | |
| k++; | |
| nn++; | |
| if (nn > n_city-1) | |
| nn = 0; | |
| } | |
| // 評価（その３） | |
| r = Kyori(n_city, kou1); | |
| if (r > max) { | |
| max = r; | |
| sw = 1; | |
| for (i3 = 0; i3 < n_city; i3++) | |
| kou2[i3] = kou1[i3]; | |
| if (sel > 0) | |
| ch = 1; | |
| } | |
| // 入れ替え（その４） | |
| kou1[0] = seq[n3]; | |
| k = 1; | |
| for (i4 = i2+1; i4 <= k1; i4++) { | |
| kou1[k] = seq[i4]; | |
| k++; | |
| } | |
| for (i4 = n3+1; i4 <= i2; i4++) { | |
| kou1[k] = seq[i4]; | |
| k++; | |
| } | |
| nn = k2; | |
| while (nn != n3) { | |
| kou1[k] = seq[nn]; | |
| k++; | |
| nn++; | |
| if (nn > n_city-1) | |
| nn = 0; | |
| } | |
| // 評価（その４） | |
| r = Kyori(n_city, kou1); | |
| if (r > max) { | |
| max = r; | |
| sw = 1; | |
| for (i3 = 0; i3 < n_city; i3++) | |
| kou2[i3] = kou1[i3]; | |
| if (sel > 0) | |
| ch = 1; | |
| } | |
| } | |
| } | |
| n3++; | |
| if (n3 > n_city-3) | |
| n3 = 0; | |
| } | |
| } | |
| // 設定 | |
| if (sw > 0) { | |
| r_m[0] = max; | |
| for (i1 = 0; i1 < n_city; i1++) | |
| seq[i1] = kou2[i1]; | |
| } | |
| return sw; | |
| } | |
| /**************/ | |
| /* 近傍の探索 */ | |
| /**************/ | |
| void Kinbo() | |
| { | |
| int i1, k = 0, sw; | |
| int r [] = new int [1]; | |
| max = 0.0; | |
| max_n = -1; | |
| mean = 0.0; | |
| for (i1 = 0; i1 < size+max_ch; i1++) { | |
| if (pi_w[i1] == 1) { | |
| pi_w[i1] = 2; | |
| sw = 1; | |
| r[0] = Kyori(len[i1], ind[i1]); | |
| while (sw > 0) | |
| sw = Change(len[i1], ind[i1], r); | |
| pi[i1] = r[0]; | |
| } | |
| if (pi_w[i1] > 0) { | |
| k++; | |
| mean += pi[i1]; | |
| if (max_n < 0 || pi[i1] > max) { | |
| max = pi[i1]; | |
| max_n = i1; | |
| } | |
| } | |
| } | |
| if (k > 0) | |
| mean /= k; | |
| } | |
| /*****************************/ | |
| /* 結果の出力 */ | |
| /* gen : 現在の世代番号 */ | |
| /*****************************/ | |
| void Output(int gen) throws IOException, FileNotFoundException | |
| { | |
| double x, y; | |
| int i1, i2, k = 0, n, pr; | |
| String now; | |
| PrintStream out = null; | |
| BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); | |
| if (out_lvl >= 0) { | |
| System.out.print(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ "); | |
| pr = Integer.parseInt(in.readLine()); | |
| } | |
| else | |
| pr = -1; | |
| if (pr != 0) { | |
| // 出力先の決定と評価値の出力 | |
| if (pr > 0) | |
| out = System.out; | |
| else { | |
| Date newtime = new Date(); // 現在時刻の獲得 | |
| now = newtime.toString(); // 文字列への変換 | |
| out = new PrintStream(new FileOutputStream(o_file, true)); | |
| out.println("***世代 " + gen + " 適応度 max " + max + | |
| " (" + max_n + ") mean " + mean + " 時間 " + now); | |
| } | |
| // 巡回順序の出力 | |
| if (out_m == 0) { | |
| for (i1 = 0; i1 < len[max_n]; i1++) { | |
| n = ind[max_n][i1]; | |
| out.println(n + " " + city[n][0] + " " + city[n][1]); | |
| if (pr > 0) { | |
| k++; | |
| if (k == pr) { | |
| in.readLine(); | |
| k = 0; | |
| } | |
| } | |
| } | |
| } | |
| if (pr < 0) | |
| out.close(); | |
| } | |
| } | |
| } | |
| ------------------------クラスWin----------------- | |
| /*******************/ | |
| /* クラスWinの定義 */ | |
| /*******************/ | |
| import java.awt.*; | |
| import java.awt.event.*; | |
| class Win extends Frame { | |
| double ritu; // 表示倍率 | |
| private int font; // フォントサイズ | |
| private int min_x, max_x, min_y, max_y; // 都市の存在範囲 | |
| private int next, yoyu_x, yoyu_y; // 表示位置 | |
| private int n_city; // 都市の数 | |
| private int [] seq; // 都市を訪問する順番 | |
| private int range; // 距離 | |
| private TSP tsp; | |
| /*************************************/ | |
| /* コンストラクタ */ | |
| /* tsp_i : TSPのオブジェクト */ | |
| /* city_i : 都市の位置データ */ | |
| /* font_i : フォントサイズ */ | |
| /* width,height : 表示範囲 */ | |
| /* nc : 都市の数 */ | |
| /*************************************/ | |
| Win (TSP tsp_i, int font_i, int width, int height, int nc) | |
| { | |
| // Frameクラスのコンストラクタの呼び出し | |
| super("巡回セールスマン問題"); | |
| // 値の設定と領域の確保 | |
| double k1, k2; | |
| int i1; | |
| tsp = tsp_i; | |
| font = font_i; | |
| next = 70; | |
| yoyu_x = 30; | |
| yoyu_y = 80; | |
| n_city = nc; | |
| seq = new int [n_city]; | |
| // 描画領域の計算 | |
| min_x = tsp.city[0][0]; | |
| max_x = tsp.city[0][0]; | |
| min_y = tsp.city[0][1]; | |
| max_y = tsp.city[0][1]; | |
| for (i1 = 1; i1 < n_city; i1++) { | |
| if (tsp.city[i1][0] < min_x) | |
| min_x = tsp.city[i1][0]; | |
| else { | |
| if (tsp.city[i1][0] > max_x) | |
| max_x = tsp.city[i1][0]; | |
| } | |
| if (tsp.city[i1][1] < min_y) | |
| min_y = tsp.city[i1][1]; | |
| else { | |
| if (tsp.city[i1][1] > max_y) | |
| max_y = tsp.city[i1][1]; | |
| } | |
| } | |
| k1 = (double)(width - 2 * yoyu_x) / (max_x - min_x); | |
| k2 = (double)(height - yoyu_y - yoyu_x) / (max_y - min_y); | |
| ritu = (k1 < k2) ? k1 : k2; | |
| // ボタンの設定とWindowサイズ | |
| // 指定された大きさにWindowサイズを変更 | |
| width = 2 * yoyu_x + (int)(ritu * (max_x - min_x)); | |
| height = yoyu_y + yoyu_x + (int)(ritu * (max_y - min_y)); | |
| setSize(width, height); | |
| // ウィンドウを表示 | |
| setVisible(true); | |
| // イベントアダプタ | |
| addWindowListener(new WinEnd()); | |
| } | |
| /*****************************/ | |
| /* 描画指示 */ | |
| /* max : 距離の負値 */ | |
| /* seq_i : 訪問する順序 */ | |
| /*****************************/ | |
| void Draw(double max, int [] seq_i) | |
| { | |
| int i1; | |
| range = (int)(-max + 0.5); | |
| for (i1 = 0; i1 < n_city; i1++) | |
| seq[i1] = seq_i[i1]; | |
| repaint(); | |
| } | |
| /********/ | |
| /* 描画 */ | |
| /********/ | |
| public void paint (Graphics g) | |
| { | |
| int i1, k, n1, n2, size = 6, x1, x2, y1, y2; | |
| Font f; | |
| // 距離の表示 | |
| f = new Font("TimesRoman", Font.BOLD, 25); | |
| g.setFont(f); | |
| g.drawString("Length : "+Integer.toString(range), yoyu_x, yoyu_y-30); | |
| // 都市番号のフォントサイズ | |
| if (font > 0) { | |
| f = new Font("TimesRoman", Font.PLAIN, font); | |
| g.setFont(f); | |
| } | |
| // 点と直線のプロット | |
| k = size / 2; | |
| for (i1 = 0; i1 < n_city; i1++) { | |
| n2 = seq[i1]; | |
| x2 = yoyu_x + (int)(ritu * (tsp.city[n2][0] - min_x)); | |
| y2 = yoyu_y + (int)(ritu * (max_y - tsp.city[n2][1])); | |
| g.fillOval(x2, y2, size, size); | |
| if (font > 0) | |
| g.drawString(Integer.toString(n2), x2+k, y2-k); | |
| if (i1 > 0) { | |
| n1 = seq[i1-1]; | |
| x1 = yoyu_x + (int)(ritu * (tsp.city[n1][0] - min_x)); | |
| y1 = yoyu_y + (int)(ritu * (max_y - tsp.city[n1][1])); | |
| g.drawLine(x1+k, y1+k, x2+k, y2+k); | |
| if (i1 == n_city-1) { | |
| n1 = seq[0]; | |
| x1 = yoyu_x + (int)(ritu * (tsp.city[n1][0] - min_x)); | |
| y1 = yoyu_y + (int)(ritu * (max_y - tsp.city[n1][1])); | |
| g.drawLine(x1+k, y1+k, x2+k, y2+k); | |
| } | |
| } | |
| } | |
| } | |
| /************/ | |
| /* 終了処理 */ | |
| /************/ | |
| class WinEnd extends WindowAdapter | |
| { | |
| public void windowClosing(WindowEvent e) { | |
| System.exit(0); | |
| } | |
| } | |
| } | |
| ------------------------クラスTSP_r(main)--------- | |
| /***********************************/ | |
| /* 遺伝的アルゴリズムによるTSPの解 */ | |
| /* coded by Y.Suganuma */ | |
| /***********************************/ | |
| import java.io.*; | |
| import java.util.StringTokenizer; | |
| class TSP_r { | |
| /****************/ | |
| /* main program */ | |
| /****************/ | |
| public static void main(String args[]) throws IOException, FileNotFoundException | |
| { | |
| int i1, n, seed[]; | |
| String i_file1[], i_file2[], line; | |
| TSP tsp; | |
| StringTokenizer dt; | |
| BufferedReader in = new BufferedReader(new FileReader(args[0])); | |
| // 入力ミス | |
| if (args.length == 0) { | |
| System.out.print("***error ファイル名を入力して下さい\n"); | |
| System.exit(1); | |
| } | |
| // 入力ＯＫ | |
| else { | |
| // 乱数の初期値と入力データファイル名の入力 | |
| n = Integer.parseInt(in.readLine()); | |
| seed = new int [n]; | |
| i_file1 = new String [n]; | |
| i_file2 = new String [n]; | |
| for (i1 = 0; i1 < n; i1++) { | |
| line = in.readLine(); | |
| dt = new StringTokenizer(line, " "); | |
| seed[i1] = Integer.parseInt(dt.nextToken()); | |
| i_file1[i1] = dt.nextToken(); | |
| i_file2[i1] = dt.nextToken(); | |
| } | |
| in.close(); | |
| // 実行（乱数の初期値を変える） | |
| for (i1 = 0; i1 < n; i1++) { | |
| System.out.print("\n+++++ケース " + (i1+1) + "+++++\n"); | |
| // 入力と初期設定 | |
| tsp = new TSP (i_file1[i1], i_file2[i1], seed[i1]); | |
| // 最適化 | |
| tsp.Control(); | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment