####################################
# 遺伝的アルゴリズムによるTSPの解
# coded by Y.Suganuma
####################################
######################
# クラスSpeciesの定義
######################
class Species
#########################
# コンストラクタ
# name : ファイル名
#########################
def initialize(name)
# データの入力
inn = open(name, "r")
s = inn.gets().split(" ")
@_allele_u = Integer(s[1]) # 対立遺伝子上限
@_allele_l = Integer(s[3]) # 対立遺伝子下限
s = inn.gets().split(" ")
@_max_len = Integer(s[1]) # 最大遺伝子長
@_min_len = Integer(s[3]) # 最小遺伝子長（負の時は，最大遺伝子長で固定）
s = inn.gets().split(" ")
@_dup_a = Integer(s[1]) # 遺伝子の重複
# =0 重複を許さない
# =1 重複を許す
@_dup_s = Integer(s[3]) # 個体の重複（同じ染色体の個体）
# =0 重複を許さない
# =1 重複を許す
s = inn.gets().split(" ")
@_size = Integer(s[1]) # 個体総数
@_max_ch = Integer(s[3]) # 子供の数の最大値
# データのチェック
if @_size <= 0
print("***error 個体総数≦０ (Constructor)\n")
end
if @_max_ch < 0
print("***error 子供の数＜０ (Constructor)\n")
end
if @_max_len <= 0 or @_min_len == 0
print("***error 遺伝子長≦０ (Constructor)\n")
end
if @_max_len < @_min_len
print("***error 最大遺伝子長＜最小遺伝子長 (Constructor)\n")
end
if @_allele_u <= @_allele_l
print("***error 対立遺伝子上限≦対立遺伝子下限 (Constructor)\n")
end
kind = @_allele_u - @_allele_l + 1
if @_dup_a == 0 and @_max_len > kind
print("***error 遺伝子の重複を防ぐことはできない (Constructor)\n")
end
# 領域の確保
num = @_size + @_max_ch
@_ind = Array.new(num) # 集団（個体の集まり）
for i1 in 0 ... num
@_ind[i1] = Array.new(@_max_len)
end
@_edge = Array.new(@_max_len) # エッジ組み替え交叉用ワークエリア
for i1 in 0 ... @_max_len
@_edge[i1] = Array.new(5)
end
@_pi = Array.new(@_max_len) # 適応度
for i1 in 0 ... @_max_len
@_pi[i1] = Array.new(5)
end
@_pi = Array.new(num) # 適応度
@_ro = Array.new(num) # ルーレット板
@_len = Array.new(num) # 各個体の遺伝子長
@_kou1 = Array.new(@_max_len) # 交叉・突然変異用作業場所１
@_kou2 = Array.new(@_max_len) # 交叉・突然変異用作業場所２
@_s_w = Array.new(num) # 淘汰用指標（選択された回数）
@_pi_w = Array.new(num) # 適応度計算指標
# =0 未使用
# =1 適応度計算前（突然変異はこの個体だけに適用）
# =2 適応度計算済み（交叉時に親とみなす）
@_max = -999999999 # 最大適応度
@_mean = 0.0 # 平均適応度
@_max_n = -1 # 最大適応度の個体番号
end
##################################################
# 場所を探す
# n >=0 : n番目の親を捜す
# -1 : 空いている場所を探す
# return : 親の場所，または，空いている場所
# （存在しないときは負の値）
##################################################
def Position(n)
k = -1
sw = 0
# 空いている場所を探す
if n < 0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 0
k = i1
break
end
end
if k < 0
print("***error 空いている場所がない --Position--\n")
end
# ｎ番目の親（pi_w[i]=2）を捜す
else
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 2
k += 1
if k == n
sw = 1
k = i1
break
end
end
end
end
return k
end
###################################################################
# 個体の選択
# method : 選択方法
# =-1 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# bias : α，または，method=2の場合は初期値(default=0)
# step : β(default=1)
# return : 個体番号
###################################################################
def Select(method, bias, step)
sum = 0.0
# ルーレット板の用意
# ランダム
if method == -1
n = 0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
n += 1
end
end
sum = 1.0 / n
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
@_ro[i1] = sum
end
end
# 評価値をそのまま利用
elsif method == 0
n = 0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
sum += @_pi[i1]
n += 1
end
end
if sum.abs() > 1.0e-10
sum = 1.0 / sum.abs()
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
@_ro[i1] = @_pi[i1] * sum
end
end
else
sum = 1.0 / n
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
@_ro[i1] = sum
end
end
end
# 最小値からの差
elsif method == 1
min = -1
n = 0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
n += 1
if min < 0 or @_pi[i1] < @_pi[min]
min = i1
end
end
end
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
@_ro[i1] = @_pi[i1] - @_pi[min]
if @_ro[i1] < bias
@_ro[i1] = bias
end
sum += @_ro[i1]
end
end
if sum > 1.0e-10
sum = 1.0 / sum
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
@_ro[i1] *= sum
end
end
else
sum = 1.0 / n
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
@_ro[i1] = sum
end
end
end
# 線形化
elsif method == 2
n = 0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
@_ro[i1] = -1.0
n += 1
else
@_ro[i1] = 1.0
end
end
sw = 0
sum = bias
while sw == 0
min = -1
for i1 in 0 ... @_size+@_max_ch
if @_ro[i1] < 0.0 and (min < 0 or @_pi[i1] < @_pi[min])
min = i1
end
end
if min < 0
sw = 1
else
@_ro[min] = sum
sum += @_step
end
end
sum = 1.0 / (0.5 * (2.0 * bias + step * (n - 1)) * n)
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
@_ro[i1] *= sum
end
end
end
sum = 0.0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
sum += @_ro[i1]
@_ro[i1] = sum
end
end
# 選択
x = rand(0)
sw = 0
k = 0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
if x <= @_ro[i1]
sw = 1
k = i1
break
end
end
end
return k
end
###################
# 標準的な初期設定
###################
def Init_std()
# 初期設定
for i1 in 0 ... @_size+@_max_ch
if i1 < @_size
@_pi_w[i1] = 1 # 適応度の計算前
else
@_pi_w[i1] = 0 # 未使用
end
end
# 遺伝子の決定
for i1 in 0 ... @_size
sw1 = 0
length = 0
while sw1 == 0
# 遺伝子長の決定
if @_min_len < 0
length = @_max_len
else
length = Integer(rand(0) * (@_max_len - @_min_len + 1) + @_min_len)
if length > @_max_len
length = @_max_len
end
end
@_len[i1] = length
# 遺伝子の決定
for i2 in 0 ... length
sw2 = 0
while sw2 == 0
lid = Integer(rand(0) * (@_allele_u - @_allele_l + 1) + @_allele_l)
if lid > @_allele_u
lid = @_allele_u
end
@_ind[i1][i2] = lid
# 重複遺伝子のチェック
sw2 = 1
if @_dup_a == 0
for i3 in 0 ... i2
if lid == @_ind[i1][i3]
sw2 = 0
break
end
end
end
end
end
# 重複個体のチェック
sw1 = 1
if @_dup_s == 0
for i2 in 0 ... i1
if @_len[i1] == @_len[i2]
sw2 = 0
for i3 in 0 ... @_len[i1]
if @_ind[i1][i3] != @_ind[i2][i3]
sw2 = 1
break
end
end
if sw2 == 0
sw1 = 0
break
end
end
end
end
end
end
end
####################################################
# 標準的な出力
# sw : 出力レベル
# =0 : 最終出力だけ
# n>0 : ｎ世代毎に出力（負はファイル）
# out_m : 出力方法
# =0 : すべての個体を出力
# =1 : 最大適応度の個体だけを出力
# gen : 現在の世代番号
# name : 出力ファイル名
####################################################
def Out_std(sw, out_m, gen, name)
k = 0
pr = -1
if sw >= 0
print(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ ")
pr = Integer($stdin.gets())
end
if pr != 0
# 出力先の決定と評価値の出力
if pr > 0
out = $stdout
$stdin.gets()
else
now = String(Time.now)
out = open(name, "a")
out.print("***世代 " + String(gen) + " 適応度 max " + String(@_max) + " (" + String(@_max_n) + ") mean " + String(@_mean) + " 時間 " + now + "\n")
# 詳細出力
end
for i1 in 0 ... @_size+@_max_ch
if (@_pi_w[i1] > 1) and (out_m == 0 or (out_m == 1 and i1 == @_max_n))
out.print(String(i1) + " allele")
for i2 in 0 ... @_len[i1]
out.print(" " + String(@_ind[i1][i2]))
end
out.print(" value " + String(@_pi[i1]) + "\n")
if pr > 0
k += 1
if k == pr
$stdin.gets()
k = 0
end
end
end
end
if pr < 0
out.close()
end
end
end
###################################################################
# 交叉（親のコピー）
# method : =2 有性（２つの親から２つの子供）(default)
# =1 １つの親から１つの子供
# pair : method=2 の時は親のペア数(default=max_ch/2)
# method=1 の時は親の数（＝子供の数）
# k_method : 選択方法
# =-1 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_copy(method = 2, pair = 0, k_method = -1, k_bias = 0.0, k_step = 1.0)
# 初期設定とデータチェック
if method != 1
method = 2
end
if pair <= 0
if method == 2
pair = Integer(@_max_ch / 2)
else
pair = @_max_ch
end
else
if method == 2 and 2*pair > @_max_ch or method == 1 and pair > @_max_ch
print("***error 子供が多すぎる (C_copy)\n")
end
end
# 実行
for i1 in 0 ... pair
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# コピー
for i2 in 0 ... method
p = p2
if i2 == 0
p = p1
end
k = Position(-1)
@_len[k] = @_len[p]
@_pi_w[k] = 1
for i3 in 0 ... @_len[k]
@_ind[k][i3] = @_ind[p][i3]
end
end
end
end
###################################################################
# 交叉（多点交叉）
# kosa : 交叉確率
# k_point : 交叉点の数(default=1)
# （負の時は，1から-k_point間のランダム）
# k_vr : =0 両親とも同じ位置で交叉(default)
# =1 両親が異なる位置で交叉（遺伝子長は可変）
# k_method : 選択方法
# =-1 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_point(kosa, k_point = 1, k_vr = 0, k_method = -1, k_bias = 0.0, k_step = 1.0)
mn = 0
# 初期設定とデータのチェック
pair = Integer(@_max_ch / 2)
if @_dup_a == 0
print("***error 交叉方法が不適当 (C_point)\n")
end
abs_p = k_point.abs()
if abs_p == 0 or abs_p > @_max_len-1 or (@_min_len > 0 and abs_p > @_min_len-1)
print("***error 交叉点の数が不適当 (C_point)\n")
end
if k_vr > 0 and @_min_len < 0
print("***error 遺伝子長は可変でなければならない (C_point)\n")
end
# 交叉
num = k_point
for i1 in 0 ... pair
# 交叉しない場合
if rand(0) > kosa
C_copy(2, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 交叉位置の数の決定
if k_point < 0
num = Integer(rand(0) * abs_p + 1)
if num > abs_p
num = abs_p
end
end
# 交叉位置の決定（点の後ろで交叉）
for i2 in 0 ... num
# 親１の交叉位置
sw = 0
while sw == 0
sw = 1
@_kou1[i2] = Integer(rand(0) * (@_len[p1] - 1))
if @_kou1[i2] > @_len[p1]-2
@_kou1[i2] = @_len[p1] - 2
end
if k_vr == 0 and @_kou1[i2] > @_len[p2]-2
@_kou1[i2] = @_len[p2] - 2
end
for i3 in 0 ... i2
if @_kou1[i3] == @_kou1[i2]
sw = 0
break
end
end
end
# 親２の交叉位置
if k_vr > 0
sw = 0
while sw == 0
sw = 1
@_kou2[i2] = Integer(rand(0) * (@_len[p2] - 1))
if @_kou2[i2] > @_len[p2]-2
@_kou2[i2] = @_len[p2] - 2
end
for i3 in 0 ... i2
if @_kou2[i3] == @_kou2[i2]
sw = 0
break
end
end
end
end
end
# 交叉の実行
# 親１の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 in 0 ... num+1
# 次の交叉位置を求める
if i2 == num # 最後
t12 = @_len[p1]
t22 = @_len[p2]
else
# 親１
t12 = @_max_len
for i3 in 0 ... num
if @_kou1[i3] >= 0 and @_kou1[i3] <= t12
t12 = @_kou1[i3]
mn = i3
end
end
@_kou1[mn] = -1
t12 += 1
# 親２
if k_vr == 0
t22 = t12
else
t22 = @_max_len
for i3 in 0 ... num
if @_kou2[i3] >= 0 and @_kou2[i3] <= t22
t22 = @_kou2[i3]
mn = i3
end
end
@_kou2[mn] = -1
t22 += 1
end
end
# 指定箇所のコピー
for i3 in t11 ... t12
if i2%2 == 0
if c1 < @_max_len
@_ind[k1][c1] = @_ind[p1][i3]
c1 += 1
end
else
if c2 < @_max_len
@_ind[k2][c2] = @_ind[p1][i3]
c2 += 1
end
end
end
for i3 in t21 ... t22
if i2%2 == 0
if c2 < @_max_len
@_ind[k2][c2] = @_ind[p2][i3]
c2 += 1
end
else
if c1 < @_max_len
@_ind[k1][c1] = @_ind[p2][i3]
c1 += 1
end
end
end
# 交叉位置の移動
t11 = t12
t21 = t22
end
end
end
end
###################################################################
# 交叉（一様交叉．[0,1]を等確率で発生させ，1であれば，
# 親１，0であれば親２の遺伝子を子１が受け継ぐ）
# kosa : 交叉確率
# k_method : 選択方法
# =-1 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_uniform(kosa, k_method = -1, k_bias = 0.0, k_step = 1.0)
# 初期設定とデータのチェック
pair = Integer(@_max_ch / 2)
if @_dup_a == 0
print("***error 交叉方法が不適当 (C_uniform)\n")
end
if @_min_len > 0
print("***error 遺伝子長は固定長でなければならない (C_uniform)\n")
end
# 交叉
for i1 in 0 ... pair
# 交叉しない場合
if rand(0) > kosa
C_copy(2, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 遺伝子長
k1 = Position(-1)
@_pi_w[k1] = 1
@_len[k1] = @_len[p1]
k2 = Position(-1)
@_pi_w[k2] = 1
@_len[k2] = @_len[p2]
# 交叉
for i2 in 0 ... @_len[p1]
if rand(0) > 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]
end
end
end
end
end
###################################################################
# 交叉（平均化交叉．２つの親の平均値を受け継ぐ）
# kosa : 交叉確率
# k_method : 選択方法
# =-1 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_mean(kosa, k_method = -1, k_bias = 0.0, k_step = 1.0)
# 初期設定とデータのチェック
if @_min_len > 0
print("***error 遺伝子長は固定長でなければならない (C_mean)\n")
end
# 交叉
for i1 in 0 ... @_max_ch
# 交叉しない場合
if rand(0) > kosa
C_copy(1, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 遺伝子長
k = Position(-1)
@_len[k] = @_len[p1]
@_pi_w[k] = 1
# 交叉
for i2 in 0 ... @_len[k]
@_ind[k][i2] = Integer((@_ind[p1][i2] + @_ind[p2][i2]) / 2)
end
end
end
end
###################################################################
# 交叉（循環交叉．ランダムに１点を選択し，その位置にある遺伝子を
# そのまま各子供が選択する．その位置にある親２（１）の遺伝
# 子を，その遺伝子の親１（２）の場所に，子１（２）が受け継
# ぐ（ただし，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 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_cycle(kosa, k_method = -1, k_bias = 0.0, k_step = 1.0)
# 初期設定とデータのチェック
pair = Integer(@_max_ch / 2)
if @_dup_a != 0
print("***error 交叉方法が不適当 (C_cycle)\n")
end
if @_min_len > 0
print("***error 遺伝子長は固定長でなければならない (C_cycle)\n")
end
# 交叉
for i1 in 0 ... pair
# 交叉しない場合
if rand(0) > kosa
C_copy(2, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 初期設定
for i2 in 0 ... @_len[p1]
@_kou1[i2] = 0
@_kou2[i2] = 0
end
# 遺伝子長
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 = Integer(rand(0) * @_len[p1])
if p >= @_len[p1]
p = @_len[p1] - 1
end
if @_kou1[p] == 0 and @_kou2[p] == 0
@_kou1[p] = 1
@_kou2[p] = 1
@_ind[k1][p] = @_ind[p1][p]
@_ind[k2][p] = @_ind[p2][p]
for i2 in 0 ... @_len[p1]
if @_ind[p2][p] == @_ind[p1][i2]
@_ind[k1][i2] = @_ind[p1][i2]
@_kou1[i2] = 1
sw = 0
break
end
end
sw = 1
for i2 in 0 ... @_len[p2]
if @_ind[p1][p] == @_ind[p2][i2]
@_ind[k2][i2] = @_ind[p2][i2]
@_kou2[i2] = 1
sw = 0
break
end
end
end
end
sw = 0
i2 = 0
i3 = 0
while sw == 0
while sw == 0 and i2 < @_len[p1]
if @_kou1[i2] == 0
sw = 1
else
i2 += 1
end
end
sw = 0
while sw == 0 and i3 < @_len[p2]
if @_kou2[i3] == 0
sw = 1
else
i3 += 1
end
end
if i2 < @_len[p1] and i3 < @_len[p2]
@_ind[k1][i2] = @_ind[p2][i3]
@_ind[k2][i3] = @_ind[p1][i2]
sw = 0
i2 += 1
i3 += 1
else
sw = 1
end
end
end
end
end
###################################################################
# 交叉（部分的交叉．ランダムに１点を選択し，その位置にある親１と
# 親２の遺伝子を取り出す．次に，親１と親２の染色体上で，こ
# の２つの遺伝子の位置を交換する．この操作を，選択した点よ
# り右にあるすべての遺伝子に対して実施する
# 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 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
#******************************************************************/
def C_part(kosa, k_method = -1, k_bias = 0.0, k_step = 1.0)
# 初期設定とデータのチェック
pair = Integer(@_max_ch / 2)
if @_dup_a != 0
print("***error 交叉方法が不適当 (C_part)\n")
end
if @_min_len > 0
print("***error 遺伝子長は固定長でなければならない (C_part)\n")
end
# 交叉
for i1 in 0 ... pair
# 交叉しない場合
if rand(0) > kosa
C_copy(2, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 遺伝子長
k1 = Position(-1)
@_pi_w[k1] = 1
@_len[k1] = @_len[p1]
k2 = Position(-1)
@_pi_w[k2] = 1
@_len[k2] = @_len[p2]
# 交叉
p = Integer(rand(0) * @_len[p1])
if p >= @_len[p1]
p = @_len[p1] - 1
end
for i2 in 0 ... @_len[p1]
@_ind[k1][i2] = @_ind[p1][i2]
@_ind[k2][i2] = @_ind[p2][i2]
end
for i2 in p ... @_len[p1]
sw = 0
lv = @_ind[k1][i2]
for i3 in 0 ... @_len[p1]
if @_ind[k2][i2] == @_ind[k1][i3]
@_ind[k1][i2] = @_ind[k1][i3]
@_ind[k1][i3] = lv
sw = 1
break
end
end
sw = 0
for i3 in 0 ... @_len[p1]
if lv == @_ind[k2][i3]
@_ind[k2][i3] = @_ind[k2][i2]
@_ind[k2][i2] = lv
sw = 1
break
end
end
end
end
end
end
###################################################################
# 交叉（順序交叉．ランダムに切れ目を決定し，子１に対し，切れ目の
# 左側では，親１の遺伝子をそのまま受け継ぎ，右側では，親１
# の遺伝子を親２の遺伝子の出現順序に並べ替える．
# 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 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_seq(kosa, k_method = -1, k_bias = 0.0, k_step = 1.0)
# 初期設定とデータのチェック
pair = Integer(@_max_ch / 2)
if @_dup_a != 0
print("***error 交叉方法が不適当 (C_seq)")
end
if @_min_len > 0
print("***error 遺伝子長は固定長でなければならない (C_seq)")
end
# 交叉
for i1 in 0 ... pair
# 交叉しない場合
if rand(0) > kosa
C_copy(2, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 遺伝子長
k1 = Position(-1)
@_pi_w[k1] = 1
@_len[k1] = @_len[p1]
k2 = Position(-1)
@_pi_w[k2] = 1
@_len[k2] = @_len[p2]
# 交叉
p = Integer(rand(0) * (@_len[p1] - 1))
if p >= @_len[p1]-1
p = @_len[p1] - 2
end
for i2 in 0 ... p+1
@_ind[k1][i2] = @_ind[p1][i2]
@_ind[k2][i2] = @_ind[p2][i2]
end
pp = 0
for i2 in p+1 ... @_len[p1]
sw = 0
i3 = pp
while i3 < @_len[p2] and sw == 0
i4 = p + 1
while i4 < @_len[p1] and sw == 0
if @_ind[p2][i3] == @_ind[p1][i4]
sw = 1
pp = i3 + 1
@_ind[k1][i2] = @_ind[p1][i4]
end
i4 += 1
end
i3 += 1
end
end
pp = 0
for i2 in p+1 ... @_len[p2]
sw = 0
i3 = pp
while i3 < @_len[p1] and sw == 0
i4 = p + 1
while i4 < @_len[p2] and sw == 0
if @_ind[p1][i3] == @_ind[p2][i4]
sw = 1
pp = i3 + 1
@_ind[k2][i2] = @_ind[p2][i4]
end
i4 += 1
end
i3 += 1
end
end
end
end
end
###################################################################
# 交叉（一様順序交叉．位置の集合をランダムに選択し，一方の親の選
# 択された位置における遺伝子の順序に従って，他の親の遺伝子
# を並べ替える
# 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 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_useq(kosa, k_method = -1, k_bias = 0.0, k_step = 1.0)
# 初期設定とデータのチェック
pair =Integer(@_max_ch / 2)
if @_dup_a != 0
print("***error 交叉方法が不適当 (C_useq)\n")
end
if @_min_len > 0
print("***error 遺伝子長は固定長でなければならない (C_useq)\n")
end
# 交叉
for i1 in 0 ... pair
# 交叉しない場合
if rand(0) > kosa
C_copy(2, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 遺伝子長
k1 = Position(-1)
@_pi_w[k1] = 1
@_len[k1] = @_len[p1]
k2 = Position(-1)
@_pi_w[k2] = 1
@_len[k2] = @_len[p2]
# 交叉
for i2 in 0 ... @_len[p1]
@_ind[k1][i2] = @_ind[p1][i2]
@_ind[k2][i2] = @_ind[p2][i2]
if rand(0) < 0.5
@_kou1[i2] = 0
else
@_kou1[i2] = 1
end
end
p = 0
for i2 in 0 ... @_len[p1]
if @_kou1[i2] > 0
sw = 0
i3 = p
while i3 < @_len[p2] and sw == 0
i4 = 0
while i4 < @_len[p1] and sw == 0
if @_ind[p2][i3] == @_ind[p1][i4] and @_kou1[i4] > 0
sw = 1
p = i3 + 1
@_ind[k1][i2] = @_ind[p1][i4]
end
i4 += 1
end
i3 += 1
end
end
end
p = 0
for i2 in 0 ... @_len[p3]
if @_kou1[i2] > 0
sw = 0
i3 = p
while i3 < @_len[p1] and sw == 0
i4 = 0
while i4 < @_len[p2] and sw == 0
if @_ind[p1][i3] == @_ind[p2][i4] and @_kou1[i4] > 0
sw = 1
p = i3 + 1
@_ind[k2][i2] = @_ind[p2][i4]
end
i4 += 1
end
i3 += 1
end
end
end
end
end
end
###################################################################
# 交叉（一様位置交叉．位置の集合をランダムに選択し，一方の親の選
# 択された位置における遺伝子の位置に，他の親の同じ遺伝子を
# 配置する．残りの遺伝子は，親と同じ順序に配置する．
# 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 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_upos(kosa, k_method = -1, k_bias = 0.0, k_step = 1.0)
# 初期設定とデータのチェック
pair = Integer(@_max_ch / 2)
if @_dup_a != 0
print("***error 交叉方法が不適当 (C_upos)\n")
end
if @_min_len > 0
print("***error 遺伝子長は固定長でなければならない (C_upos)\n")
end
# 交叉
for i1 in 0 ... pair
# 交叉しない場合
if rand(0) > kosa
C_copy(2, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 遺伝子長
k1 = Position(-1)
@_pi_w[k1] = 1
@_len[k1] = @_len[p1]
k2 = Position(-1)
@_pi_w[k2] = 1
@_len[k2] = @_len[p2]
# 交叉
for i2 in 0 ... @_len[p1]
@_kou1[i2] = 1
if rand(0) < 0.5
@_kou1[i2] = 1
end
if @_kou1[i2] > 0
@_ind[k1][i2] = @_ind[p2][i2]
@_ind[k2][i2] = @_ind[p1][i2]
end
end
p = 0
for i2 in 0 ... @_len[p1]
sw = 0
for i3 in 0 ... @_len[p1]
if @_kou1[i3] > 0 and @_ind[p1][i2] == @_ind[k1][i3]
sw = 1
break
end
end
if sw == 0
for i3 in p ... @_len[p1]
if @_kou1[i3] == 0
@_ind[k1][i3] = @_ind[p1][i2]
p = i3 + 1
sw = 1
break
end
end
end
end
p = 0
for i2 in 0 ... @_len[p2]
sw = 0
for i3 in 0 ... @_len[p2]
if @_kou1[i3] > 0 and @_ind[p2][i2] == @_ind[k2][i3]
sw = 1
break
end
end
if sw == 0
for i3 in p ... @_len[p2]
if @_kou1[i3] == 0
@_ind[k2][i3] = @_ind[p2][i2]
p = i3 + 1
sw = 1
break
end
end
end
end
end
end
end
###################################################################
# 交叉（エッジ組み替え交叉．以下の手順に従って行う．対立遺伝子は
# 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 ランダム(default)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# k_bias : α，または，method=2の場合は初期値(default=0)
# k_step : β(default=1)
###################################################################
def C_edge(kosa, k_method = -1, k_bias = 0.0, k_step = 1.0)
e = Array.new(2)
k0 = 0
# 初期設定とデータのチェック
pair = @_max_ch
if @_dup_a != 0
print("***error 交叉方法が不適当 (C_edge)\n")
end
if @_min_len > 0
print("***error 遺伝子長は固定長でなければならない (C_edge)\n")
end
# 交叉
for i1 in 0 ... pair
# 交叉しない場合
if rand(0) > kosa
C_copy(1, 1)
# 交叉する場合
else
# 親の選択
p1 = Select(k_method, k_bias, k_step)
p2 = p1
sw = 0
while sw == 0
p2 = Select(k_method, k_bias, k_step)
if p1 != p2
sw = 1
end
end
# 遺伝子長
k = Position(-1)
@_pi_w[k] = 1
@_len[k] = @_len[p1]
# エッジマップの初期化
for i2 in 0 ... @_len[k]
@_edge[i2][0] = 0
for i3 in 1 ... 5
@_edge[i2][i3] = -1
end
end
# 交叉
# エッジマップの作成
for i2 in 0 ... @_len[k]
sw = 0
for i3 in 0 ... @_len[k]
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]
end
end
for i4 in 0 ... 2
@_edge[i2][0] += 1
@_edge[i2][@_edge[i2][0]] = e[i4]
end
break
end
end
sw = 0
for i3 in 0 ... @_len[k]
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]
end
end
for i4 in 0 ... 2
sw = 1
for i5 in 1 ... @_edge[i2][0]+1
if @_edge[i2][i5] == e[i4]
sw = 2
break
end
end
if sw == 1
@_edge[i2][0] += 1
@_edge[i2][@_edge[i2][0]] = e[i4]
end
end
break
end
end
end
# 交叉の実行
# 出発点の決定
k1 = @_ind[p1][0]
k2 = @_ind[p2][0]
if @_edge[k1][0] == @_edge[k2][0]
kk = k1
if rand(0) > 0.5
kk = k2
end
else
kk = k2
if @_edge[k1][0] < @_edge[k2][0]
kk = k2
end
end
@_ind[k][0] = kk
p = 1
while p < @_len[k]
# ノードの除去
for i2 in 0 ... @_len[k]
sw = 0
if @_edge[i2][0] > 0
for i3 in 1 ... 5
if @_edge[i2][i3] == kk
sw = 1
@_edge[i2][i3] = -1
@_edge[i2][0] -= 1
break
end
end
end
end
# 次の現在ノードの選択
min = 10
num = 0
for i2 in 1 ... 5
if @_edge[kk][i2] >= 0
k1 = @_edge[kk][i2]
if @_edge[k1][0] >= 0 and @_edge[k1][0] < min
num = 1
min = @_edge[k1][0]
k0 = k1
else
if @_edge[k1][0] == min
num += 1
end
end
end
end
if num > 1
k1 = Integer(rand(0) * num) + 1
if k1 > num
k1 = num
end
k2 = 0
k0 = -1
i2 = 1
while i2 <= 4 and k0 < 0
if @_edge[kk][i2] >= 0
if @_edge[@_edge[kk][i2]][0] == min
k2 += 1
if k1 == k2
k0 = @_edge[kk][i2]
end
end
end
i2 += 1
end
else
if num <= 0
num = 0
for i2 in 0 ... @_len[k]
if i2 != kk and @_edge[i2][0] >= 0
num += 1
end
end
if num <= 0
print("***error invalid data (C_edge)\n")
else
k1 = Integer(rand(0) * num) + 1
if k1 > num
k1 = num
end
k2 = 0
k0 = -1
i2 = 0
while i2 < @_len[k] and k0 < 0
if i2 != kk and @_edge[i2][0] >= 0
k2 += 1
if k1 == k2
k0 = i2
end
end
i2 += 1
end
end
end
end
@_edge[kk][0] = -1
@_ind[k][p] = k0
kk = k0
p += 1
end
end
end
end
##############################################################
# 交叉（サブツアー交叉．２点交叉の拡張である．ただし，相手に
# 同じ遺伝子のグループがない限り実行されない．たとえば
# ***abcd**
# *cdab****
# のような両親の時実行され，以下の４つの子供が生成され
# る）
# ***cdab**
# *abcd****
# ***badc**
# *dcba****
# 最大，４＊交叉回数＊個体総数＊(個体総数－１) 個の子
# 供が生成される可能性があるので，子供の数としてこの値
# 以上のデータを入力しておく必要がある．
# kosa : 交叉確率
# count : １つのペアーに対する交差回数(default=10)
##############################################################
def C_sub(kosa, count = 10)
t22 = 0
# 初期設定とデータのチェック
if (4*count*@_size*(@_size-1)) > @_max_ch
print("***error 子供が多すぎる (C_sub)\n")
end
# 交叉
for i1 in 0 ... @_size-1
# 親１
p1 = Position(i1)
if p1 >= 0
for i2 in i1 ... @_size
# 親２
p2 = Position(i2)
if p2 >= 0
# 交叉しない場合
if rand(0) > kosa
C_copy(2, 1)
# 交叉する場合
else
# 交叉回数の制御
for i3 in 0 ... count
# 交叉位置の決定（点の後ろで交叉）
# 親１の交叉位置
t11 = Integer(rand(0) * @_len[p1])
if t11 > (@_len[p1]-1)
t11 = @_len[p1] - 1
end
sw = 0
while sw == 0
t12 = Integer(rand(0) * @_len[p1])
if t12 > (@_len[p1]-1)
t12 = @_len[p1] - 1
end
if t12 != t11
sw = 1
end
end
if t11 > t12
k1 = t11
t11 = t12
t12 = k1
end
# 親２の交叉位置
sw = 0
t21 = -1
i4 = 0
while i4 < @_len[p2] and t21 < 0
i5 = t11
while i5 <= t12 and t21 < 0
if @_ind[p2][i4] == @_ind[p1][i5]
t21 = i4
end
i5 += 1
end
i4 += 1
end
if t21 >= 0
t22 = t21 + t12 - t11
if t22 < @_len[p2]
sw = 1
i4 = t21 + 1
while i4 <= t22 and sw > 0
sw = 0
i5 = t11
while i5 <= t12 and sw == 0
if @_ind[p2][i4] == @_ind[p1][i5]
sw = 1
end
i5 += 1
end
i4 += 1
end
end
end
# 交叉の実行
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 in 0 ... t11
@_ind[k1][i4] = @_ind[p1][i4]
@_ind[k2][i4] = @_ind[p1][i4]
end
for i4 in t11 ... t12+1
@_ind[k1][i4] = @_ind[p2][t21+i4-t11]
@_ind[k2][i4] = @_ind[p2][t22-i4+t11]
end
for i4 in t12+1 ... @_len[p1]
@_ind[k1][i4] = @_ind[p1][i4]
@_ind[k2][i4] = @_ind[p1][i4]
end
for i4 in 0 ... t21
@_ind[k3][i4] = @_ind[p2][i4]
@_ind[k4][i4] = @_ind[p2][i4]
end
for i4 in t21 ... t22+1
@_ind[k3][i4] = @_ind[p1][t11+i4-t21]
@_ind[k4][i4] = @_ind[p1][t12-i4+t21]
end
for i4 in t22+1 ... @_len[p2]
@_ind[k3][i4] = @_ind[p2][i4]
@_ind[k4][i4] = @_ind[p2][i4]
end
end
end
end
end
end
end
end
end
#######################################
# 突然変異（対立遺伝子との置き換え）
# pr : 突然変異率
#######################################
def M_alle(pr)
# データのチェックと初期設定
if @_dup_a == 0
print("***error 突然変異方法が不適当 (M_alle)\n")
end
# 実行
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1
for i2 in 0 ... @_len[i1]
if rand(0) <= pr
lid = Integer(rand(0) * (@_allele_u - @_allele_l + 1) + @_allele_l)
if lid > @_allele_u
lid = @_allele_u
end
if lid != @_ind[i1][i2]
@_ind[i1][i2] = lid
end
end
end
end
end
end
######################################################################
# 突然変異（移動．２点を選択し，２番目の遺伝子を１番目の遺伝子の前に
# 移動する）
# pr : 突然変異率
######################################################################
def M_move(pr)
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1 and rand(0) <= pr
# 位置の決定
# p1
p1 = Integer(rand(0) * @_len[i1])
if p1 >= @_len[i1]
p1 = @_len[i1] - 1
end
# p2
p2 = p1
sw = 0
while sw == 0
p2 = Integer(rand(0) * @_len[i1])
if p2 >= @_len[i1]
p2 = @_len[i1] - 1
end
if p2 != p1
sw = 1
end
end
# 実行
if p2 > p1
ld = @_ind[i1][p2]
i2 = p2
while i2 > p1
@_ind[i1][i2] = @_ind[i1][i2-1]
i2 -= -1
end
@_ind[i1][p1] = ld
else
ld = @_ind[i1][p2]
for i2 in p2 ... p1-1
@_ind[i1][i2] = @_ind[i1][i2+1]
end
@_ind[i1][p1-1] = ld
end
end
end
end
########################################################
# 突然変異（逆位．２点間の遺伝子順序を逆に並べ替える）
# pr : 突然変異率
# wd : >0 : 幅を固定
# =0 : 幅をランダム(default)
########################################################
def M_inv(pr, wd = 0)
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1 and rand(0) <= pr
# 区間の決定
if wd == 0
p1 = Integer(rand(0) * @_len[i1])
if p1 >= @_len[i1]
p1 = @_len[i1] - 1
end
sw = 0
p2 = p1
while sw == 0
p2 = Integer(rand(0) * @_len[i1])
if p2 >= @_len[i1]
p2 = @_len[i1] - 1
end
if p2 != p1
sw = 1
end
end
if p1 > p2
p = p1
p1 = p2
p2 = p
end
else
p1 = @_len[i1]
while p1 > @_len[i1]-2
p1 = Integer(rand(0) * @_len[i1])
end
p2 = p1 + wd - 1
if p2 >= @_len[i1]
p2 = @_len[i1] - 1
end
end
# 実行
sw = 0
while sw == 0
lid = @_ind[i1][p1]
@_ind[i1][p1] = @_ind[i1][p2]
@_ind[i1][p2] = lid
p1 += 1
p2 -= 1
if p1 >= p2
sw = 1
end
end
end
end
end
######################################################################
# 突然変異（スクランブル．２点間の遺伝子順序をランダムに並べ替える）
# pr : 突然変異率
# wd : >0 : 幅を固定
# =0 : 幅をランダム(default)
######################################################################
def M_scram(pr, wd = 0)
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1 and rand(0) <= pr
# 区間の決定
if wd == 0
p1 = Integer(rand(0) * @_len[i1])
if p1 >= @_len[i1]
p1 = @_len[i1] - 1
end
sw = 0
p2 = p1
while sw == 0
p2 = Integer(rand(0) * @_len[i1])
if p2 >= @_len[i1]
p2 = @_len[i1] - 1
end
if p2 != p1
sw = 1
end
end
if p1 > p2
p = p1
p1 = p2
p2 = p
end
else
p1 = @_len[i1]
while p1 > @_len[i1]-2
p1 = Integer(rand(0) * @_len[i1])
end
p2 = p1 + wd - 1
if p2 >= @_len[i1]
p2 = @_len[i1] - 1
end
end
# 実行
for i2 in p1 ... p2+1
p = Integer(rand(0) * (p2 - p1 + 1) + p1)
if p > p2
p = p2
end
ld = @_ind[i1][i2]
@_ind[i1][i2] = @_ind[i1][p]
@_ind[i1][p] = ld
end
end
end
end
######################################################################
# 突然変異（転座．２点間の遺伝子を他の位置のものと置き換える．ただし
# 重複部分はそのままとする）
# pr : 突然変異率
# wd : >0 : 幅を固定
# =0 : 幅をランダム(default)
######################################################################
def M_chg(pr, wd = 0)
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1 and rand(0) <= pr
# 区間等の決定（[p1,p2]と[p3,p4]の入れ替え）
# p1
p1 = Integer(rand(0) * @_len[i1])
if p1 >= @_len[i1]
p1 = @_len[i1] - 1
end
# p3
sw = 0
p3 = p1
while sw == 0
p3 = Integer(rand(0) * @_len[i1])
if p3 >= @_len[i1]
p3 = @_len[i1] - 1
end
if p3 != p1
sw = 1
end
end
# 小さい方をp1,p2にする
if p1 > p3
p = p1
p1 = p3
p3 = p
end
# p4, p2
p4 = p1 + wd - 1
if wd == 0
p4 = Integer(rand(0) * (@_len[i1] - p3)) + p3
end
if p4 >= @_len[i1]
p4 = @_len[i1] - 1
end
p2 = p1 + (p4 - p3)
# 重複部分のチェック
if p2 >= p3
p = p3 - 1
p3 = p2 + 1
p2 = p
p4 = p3 + (p2 - p1)
end
# 実行
p = p3
for i2 in p1 ... p2+1
ld = @_ind[i1][i2]
@_ind[i1][i2] = @_ind[i1][p]
@_ind[i1][p] = ld
p += 1
end
end
end
end
######################################################################
# 突然変異（重複．２点間の遺伝子を他の位置にコピーする
# pr : 突然変異率
# wd : >0 : 幅を固定
# =0 : 幅をランダム(deafult)
######################################################################
def M_dup(pr, wd = 0)
# データのチェック
if @_dup_a == 0
print("***error 突然変異方法が不適当 (M_dup)\n")
end
# 実行
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1 and rand(0) <= pr
# 区間の決定（[p1,p2]を[p3,p4]にコピー）
# p1
p1 = Integer(rand(0) * @_len[i1])
if p1 >= @_len[i1]
p1 = @_len[i1] - 1
end
# p3
sw = 0
p3 = p1
while sw == 0
p3 = Integer(rand(0) * @_len[i1])
if p3 >= @_len[i1]
p3 = @_len[i1] - 1
end
if p3 != p1
sw = 1
end
end
# 区間を決める
p2 = p1
p4 = p1
if p3 > p1
p4 = p3 + wd - 1
if wd == 0
p4 = Integer(rand(0) * (@_len[i1] - p3)) + p3
end
if p4 >= @_len[i1]
p4 = @_len[i1] - 1
end
p2 = p1 + (p4 - p3)
else
p2 = p1 + wd - 1
if wd == 0
p2 = Integer(rand(0) * (@_len[i1] - p1)) + p1
end
if p2 >= @_len[i1]
p2 = @_len[i1] - 1
end
p4 = p3 + (p2 - p1)
# 実行
end
p = p4
i2 = p2
while i2 > p1-1
@_ind[i1][p] = @_ind[i1][i2]
p -= 1
i2 -= 1
end
end
end
end
######################################################
# 突然変異（摂動．値をある量だけ変化させる）
# pr : 突然変異率
# method : =0 正規分布(default)
# =1 一様分布
# m : 平均または一様分布の下限(default=0.0)
# s : 標準偏差または一様分布の上限(default=1.0)
######################################################
def M_per(pr, method = 0, m = 0.0, s = 1.0)
wd = 0.0
# データのチェックと初期設定
if @_dup_a == 0
print("***error 突然変異方法が不適当 (M_per)\n")
end
if method > 0
wd = s - m
end
# 実行
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1
for i2 in 0 ... @_len[i1]
if rand(0) <= pr
if method == 0
w = normalvariate(m, s)
else
w = rand(0) * wd
if rand(0) < 0.5
w = -w
end
end
x1 = float(@_ind[i1][i2]) + w
if x1 > @_allele_u
x1 = @_allele_u
else
if x1 < @_allele_l
x1 = @_allele_l
end
end
@_ind[i1][i2] = Integer(x1)
end
end
end
end
end
##############################################
# 突然変異（挿入．ある長さの遺伝子を挿入する）
# pr : 突然変異率
# wd : >0 幅を固定
# =0 幅をランダム(default)
##############################################
def M_ins(pr, wd = 0)
# データのチェック
if @_dup_a == 0 or @_min_len < 0
print("***error 突然変異方法が不適当 (M_ins)\n")
end
# 実行
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1 and rand(0) <= pr
# 挿入位置の決定
p = Integer(rand(0) * (@_len[i1] + 1))
if p > @_len[i1]
p = @_len[i1]
end
# 挿入する遺伝子長の決定
l = wd
if wd == 0
l = Integer(rand(0) * (@_max_len - @_len[i1] + 1))
end
if l > @_max_len-@_len[i1]
l = @_max_len - @_len[i1]
else
if l <= 0
l = 1
end
end
# 実行
# 挿入場所の確保
if p < @_len[i1]
i2 = @_len[i1] + l - 1
while i2 > p-1
@_ind[i1][i2] = @_ind[i1][i2-l]
i2 -= 1
end
end
# 挿入場所の遺伝子の決定
for i2 in p ... p+l
ld = Integer(rand(0) * (@_allele_u - @_allele_l + 1) + @_allele_l)
if ld > @_allele_u
ld = @_allele_u
end
@_ind[i1][i2] = ld
end
@_len[i1] += l
end
end
end
##############################################
# 突然変異（削除．ある長さの遺伝子を削除する）
# pr : 突然変異率
# wd : >0 幅を固定
# =0 幅をランダム(default)
##############################################
def M_del(pr, wd = 0)
# データのチェック
if @_dup_a == 0 or @_min_len < 0
print("***error 突然変異方法が不適当 (M_del)\n")
end
# 実行
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1 and rand(0) <= pr
# 削除位置の決定
p = Integer(rand(0) * @_len[i1])
if p >= @_len[i1]
p = @_len[i1] - 1
end
# 削除する遺伝子長の決定
max = @_len[i1] - p
if @_len[i1]-@_min_len < @_len[i1]-p
max = @_len[i1] - @_min_len
end
l = wd
if wd == 0
l = Integer(rand(0) * max + 1)
end
if l > max
l = max
end
# 実行
for i2 in 0 ... @_len[i1]-p-l
@_ind[i1][p+i2] = @_ind[i1][p+i2+l]
end
@_len[i1] -= l
end
end
end
######################################################################
# 淘汰（エリート・ルーレット選択）
# elite : エリートで残す個体数(default=0)
# s_method : ルーレット板の作成方法(default=1)
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
# s_bias : α，または，method=2の場合は初期値(default=0)
# s_step : β(default=1)
######################################################################
def S_roul(elite = 0, s_method = 1, s_bias = 0.0, s_step = 1.0)
count = 0
k = 0
n = 0
# 値のチェックと初期設定
if s_method != 0 and s_method != 2
s_method = 1
end
if elite > @_size
print("***error エリートで残す数が多すぎる (S_roul)\n")
end
if s_method == 2 and s_step <= 0.0
s_step = 1.0
end
for i1 in 0 ... @_size+@_max_ch
@_s_w[i1] = 0
end
# 重複個体を削除
if @_dup_s == 0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 0
for i2 in i1+1 ... @_size+@_max_ch
if @_pi_w[i2] > 0 and @_len[i1] == @_len[i2]
sw = 0
for i3 in 0 ... @_len[i1]
if @_ind[i1][i3] != @_ind[i2][i3]
sw = 1
break
end
end
if sw == 0
@_pi_w[i2] = 0
end
end
end
end
end
end
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1
n += 1
end
end
if n < 0 or @_dup_s == 0 and n < @_size
print("***error 残す個体がない (S_roul)\n")
end
# 淘汰して残す個体を選ぶ
# エリートの選択
sw = 0
while k < elite and k < n and sw == 0
max = -1
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] > 1 and @_s_w[i1] == 0
if max < 0 or @_pi[i1] > @_pi[max]
max = i1
end
end
end
if max < 0
sw = 1
else
@_s_w[max] = 1
k += 1
end
end
# ルーレット選択
while count < @_size+@_max_ch and k < @_size
p = Select(s_method, s_bias, s_step)
if @_dup_s == 0 and @_s_w[p] > 0
count += 1
else
count = 0
@_s_w[p] += 1
k += 1
end
end
# 選択に失敗した場合の処理
if @_dup_s == 0 and k < @_size
i1 = 0
while i1 < @_size+@_max_ch and k < @_size
if @_pi_w[i1] > 1 and @_s_w[i1] == 0
@_s_w[i1] = 1
k += 1
end
i1 += 1
end
end
# 複数回選択されたものの処理
for i1 in 0 ... @_size+@_max_ch
if @_s_w[i1] == 0
@_pi_w[i1] = 0
end
end
for i1 in 0 ... @_size+@_max_ch
if @_s_w[i1] > 0
if @_s_w[i1] > 1
for i2 in 2 ... @_s_w[i1]+1
k = Position(-1)
@_len[k] = @_len[i1]
@_pi_w[k] = 2
@_pi[k] = @_pi[i1]
for i3 in 0 ... @_len[i1]
@_ind[k][i3] = @_ind[i1][i3]
end
end
end
end
end
end
end
####################
# クラスTSPの定義
####################
class TSP < Species
######################################
# コンストラクタ
# name1 : Species定義ファイル名
# name2 : TSP定義ファイル名
######################################
def initialize(name1, name2)
super(name1) # 親のコンストラクタ
# 基本データの入力
inn = open(name2, "r")
s = inn.gets().split(" ")
@_out_lvl = Integer(s[1]) # 出力レベル
# =0 最終出力だけ
# n>0 ｎ世代毎に出力（負の時はファイル）
@_out_m = Integer(s[3]) # 出力方法
# =0 すべてを出力
# =1 最大適応度の個体だけを出力
s = inn.gets().split(" ")
@_o_file = s[1] # 出力ファイル名
@_out_d = Integer(s[3]) # 表示間隔
s = inn.gets().split(" ")
@_kosa_m = Integer(s[1]) # 交叉方法
# =-1 交叉を使用しない
# =0 親のコピー
# =1 循環交叉
# =2 部分的交叉
# =3 順序交叉
# =4 一様順序交叉
# =5 一様位置交叉
# =6 エッジ組み替え交叉
# =7 サブツアー交叉
@_kosa = Float(s[3]) # 交叉確率
@_k_point = Integer(s[5]) # 交差点の数（負の時は，1から-k_point間のランダム）
@_k_vr = Integer(s[7]) # =0 両親とも同じ位置で交叉
# =1 両親が異なる位置で交叉（遺伝子長は可変）
@_k_method = Integer(s[9]) # 交叉の時の親の選択方法
# =-1 ランダム
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
@_k_bias = Float(s[11]) # α，または，method=2の場合は初期値
@_k_step = Float(s[13]) # β
s = inn.gets().split(" ")
@_mute_m = Integer(s[1]) # 突然変異方法
# =-1 突然変異を使用しない
# =0 移動
# =1 逆位
# =2 スクランブル
# =3 転座
@_mute = Float(s[3]) # 突然変異率
@_wd = Integer(s[5]) # 突然変異に使用する部分遺伝子長
@_m_mean = Float(s[7]) # 摂動の平均値
@_m_std = Float(s[9]) # 摂動の標準偏差
s = inn.gets().split(" ")
@_elite = Integer(s[1]) # エリート選択で残す数
@_s_method = Integer(s[3]) # ルーレット板の作成方法
# =0 適応度をそのまま使用
# =1 最小値からの差（ただし，α以下の場合はα）
# =2 評価値に順位をつけ，減少率βで線形化
@_s_bias = Float(s[5]) # α，または，s_method=2の場合は初期値
@_s_step = Float(s[7]) # β
s = inn.gets().split(" ")
@_n_city = Integer(s[1]) # 都市の数
@_max_gen = Integer(s[3]) # 最大世代交代数
s = inn.gets().split(" ")
@_kinbo = Integer(s[1]) # 近傍探索（０：行わない，１：行う）
@_neib = Integer(s[3]) # 近傍（2 or 3）
s = inn.gets().split(" ")
@_sel = Integer(s[1]) # エッジの選択方法
# =0 最良のものを選択
# =1 最初のものを選択
if @_kinbo > 0 and @_neib != 2 and @_neib != 3
print("***error 近傍の値が不適当\n")
end
if @_n_city != @_max_len
print("***error 都市数が不適当\n")
end
# 都市の位置データ
@_city = Array.new(@_n_city)
for i1 in 0 ... @_n_city
@_city[i1] = Array.new(2)
s = inn.gets().split(" ")
@_city[i1][0] = Integer(s[0])
@_city[i1][1] = Integer(s[1])
end
# 距離テーブル
@_rg = Array.new(@_n_city)
for i1 in 0 ... @_max_len
@_rg[i1] = Array.new(@_n_city)
end
for i1 in 0 ... @_n_city
for i2 in i1+1 ... @_n_city
x = @_city[i2][0] - @_city[i1][0]
y = @_city[i2][1] - @_city[i1][1]
@_rg[i1][i2] = Math.sqrt(x * x + y * y).round()
end
end
for i1 in 1 ... @_n_city
for i2 in 0 ... i1
@_rg[i1][i2] = @_rg[i2][i1]
end
end
inn.close()
end
###############
# 全体の制御
###############
def Control()
gen = 1
# 初期集団の発生
Init_std()
# 評価
if @_kinbo > 0
Kinbo()
else
Adap()
end
# 出力
print("***世代 " + String(gen) + " 適応度 max " + String(@_max) + " (" + String(@_max_n) + ") mean " + String(@_mean) + "\n")
if @_out_lvl.abs() > 0
Output(gen)
end
# 世代交代
for gen in 2 ... @_max_gen+1
# 交叉
if @_kosa_m == 0
C_copy() # 親のコピー
elsif @_kosa_m == 1
C_cycle(@_kosa) # 循環交叉
elsif @_kosa_m == 2
C_part(@_kosa) # 部分的交叉
elsif @_kosa_m == 3
C_seq(@_kosa) # 順序交叉
elsif @_kosa_m == 4
C_useq(@_kosa) # 一様順序交叉
elsif @_kosa_m == 5
C_upos(@_kosa) # 一様位置交叉
elsif @_kosa_m == 6
C_edge(@_kosa) # エッジ組み替え交叉
elsif @_kosa_m == 7
C_sub(@_kosa, @_k_point) # サブツアー交叉
end
# 突然変異
if @_mute_m == 0
M_move(@_mute) # 移動
elsif @_mute_m == 1
M_inv(@_mute) # 逆位
elsif @_mute_m == 2
M_scram(@_mute) # スクランブル
elsif @_mute_m == 3
M_chg(@_mute) # 転座
end
# 適応度
if @_kinbo > 0
Kinbo()
else
Adap()
end
# 淘汰
S_roul(@_elite)
# 出力
if gen%@_out_d == 0
print("***世代 " + String(gen) + " 適応度 max " + String(@_max) + " (" + String(@_max_n) + ") mean " + String(@_mean) + "\n")
end
if @_out_lvl.abs() > 0
if gen%@_out_lvl.abs() == 0
Output(gen)
end
end
end
gen -= 1
k1 = @_out_m
@_out_m = 0
print("***世代 " + String(gen) + " 適応度 max " + String(@_max) + " (" + String(@_max_n) + ") mean " + String(@_mean) + "\n")
Output(gen)
@_out_m = k1
end
##########################
# 距離の計算
# n_c : 都市の数
# p : 都市番号
# return : 距離（負）
##########################
def Kyori(n_c, p)
r = 0
n1 = p[0]
for i1 in 1 ... n_c
n2 = p[i1]
r -= @_rg[n1][n2]
n1 = n2
end
n2 = p[0]
r -= @_rg[n1][n2]
return r
end
################
# 適応度の計算
################
def Adap()
k = 0
@_mean = 0.0
@_max = 0.0
@_max_n = -1
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1
@_pi_w[i1] = 2
@_pi[i1] = Kyori(@_len[i1], @_ind[i1])
end
if @_pi_w[i1] > 0
k += 1
@_mean += @_pi[i1]
if @_max_n < 0 or @_pi[i1] > @_max
@_max = @_pi[i1]
@_max_n = i1
end
end
end
if k > 0
@_mean /= k
end
end
######################################
# エッジの入れ替え
# n_city : 都市の数
# seq : 訪問する順番
# r_m : 距離の負値
# return : =0 改善がなかった
# =1 改善があった
######################################
def Change(n_city, seq, r_m)
ch = 0
sw = 0
max = r_m[0]
n3 = Integer(rand(0) * (n_city - 2))
if n3 > n_city-3
n3 = n_city - 3
end
# ２近傍
i1 = 0
while i1 <= n_city-3 and ch == 0
if n3 == 0
n1 = n_city - 2
else
n1 = n_city - 1
end
i2 = n3 + 2
while i2 <= n1 and ch == 0
# 枝の場所（(n3,n3+1), (k1,k2)）
k1 = i2
if i2 == n_city-1
k2 = 0
else
k2 = i2 + 1
end
# 枝の入れ替え
@_kou1[0] = seq[n3]
k = 1
i3 = k1
while i3 > n3
@_kou1[k] = seq[i3]
k += 1
i3 -= 1
end
nn = k2
while nn != n3
@_kou1[k] = seq[nn]
k += 1
nn += 1
if nn > n_city-1
nn = 0
end
end
# 評価
r = Kyori(n_city, @_kou1)
if r > max
max = r
sw = 1
for i3 in 0 ... n_city
@_kou2[i3] = @_kou1[i3]
end
if @_sel > 0
ch = 1
end
end
i2 += 1
end
n3 += 1
if n3 > n_city-3
n3 = 0
end
i1 += 1
end
# ３近傍
if @_neib == 3 and ch == 0
i1 = 0
while i1 <= n_city-3 and ch == 0
n1 = n_city - 2
n2 = n_city - 1
i2 = n3 + 1
while i2 <= n1 and ch == 0
i3 = i2 + 1
while i3 <= n2 and ch == 0
# 枝の場所（(n3,n3+1), (i2,i2+1), (k1,k2)）
k1 = i3
k2 = k1
if i3 == n_city-1
k2 = 0
else
k2 = i3 + 1
end
# 枝の入れ替えと評価
# 入れ替え（その１）
@_kou1[0] = seq[n3]
k = 1
i4 = i2
while i4 > n3
@_kou1[k] = seq[i4]
k += 1
i4 -= 1
end
i4 = k1
while i4 > i2
@_kou1[k] = seq[i4]
k += 1
i4 -= 1
end
nn = k2
while nn != n3
@_kou1[k] = seq[nn]
k += 1
nn += 1
if nn > n_city-1
nn = 0
end
end
# 評価（その１）
r = Kyori(n_city, @_kou1)
if r > max
max = r
sw = 1
for i3 in 0 ... n_city
@_kou2[i3] = @_kou1[i3]
end
if @_sel > 0
ch = 1
end
end
# 入れ替え（その２）
@_kou1[0] = seq[n3]
k = 1
i4 = k1
while i4 > i2
@_kou1[k] = seq[i4]
k += 1
i4 -= 1
end
for i4 in n3+1 ... i2+1
@_kou1[k] = seq[i4]
k += 1
end
nn = k2
while nn != n3
@_kou1[k] = seq[nn]
k += 1
nn += 1
if nn > n_city-1
nn = 0
end
end
# 評価（その２）
r = Kyori(n_city, @_kou1)
if r > max
max = r
sw = 1
for i3 in 0 ... n_city
@_kou2[i3] = @_kou1[i3]
end
if @_sel > 0
ch = 1
end
end
# 入れ替え（その３）
@_kou1[0] = seq[n3]
k = 1
for i4 in i2+1 ... k1+1
@_kou1[k] = seq[i4]
k += 1
end
i4 = i2
while i4 > n3
@_kou1[k] = seq[i4]
k += 1
i4 -= 1
end
nn = k2
while nn != n3
@_kou1[k] = seq[nn]
k += 1
nn += 1
if nn > n_city-1
nn = 0
end
end
# 評価（その３）
r = Kyori(n_city, @_kou1)
if r > max
max = r
sw = 1
for i3 in 0 ... n_city
@_kou2[i3] = @_kou1[i3]
end
if @_sel > 0
ch = 1
end
end
# 入れ替え（その４）
@_kou1[0] = seq[n3]
k = 1
for i4 in i2+1 ... k1+1
@_kou1[k] = seq[i4]
k += 1
end
for i4 in n3+1 ... i2+1
@_kou1[k] = seq[i4]
k += 1
end
nn = k2
while nn != n3
@_kou1[k] = seq[nn]
k += 1
nn += 1
if nn > n_city-1
nn = 0
end
end
# 評価（その４）
r = Kyori(n_city, @_kou1)
if r > max
max = r
sw = 1
for i3 in 0 ... n_city
@_kou2[i3] = @_kou1[i3]
end
if @_sel > 0
ch = 1
end
end
i3 += 1
end
i2 += 1
end
n3 += 1
if n3 > n_city-3
n3 = 0
end
i1 += 1
end
end
# 設定
if sw > 0
r_m[0] = max
for i1 in 0 ... n_city
seq[i1] = @_kou2[i1]
end
end
return sw
end
##############
# 近傍の探索
##############
def Kinbo()
k = 0
@_max = 0.0
@_max_n = -1
@_mean = 0.0
for i1 in 0 ... @_size+@_max_ch
if @_pi_w[i1] == 1
@_pi_w[i1] = 2
sw = 1
r = Kyori(@_len[i1], @_ind[i1])
while sw > 0
r = Array.new(1)
sw = Change(@_len[i1], @_ind[i1], r)
end
@_pi[i1] = r[0]
end
if @_pi_w[i1] > 0
k += 1
@_mean += @_pi[i1]
if @_max_n < 0 or @_pi[i1] > @_max
@_max = @_pi[i1]
@_max_n = i1
end
end
end
if k > 0
@_mean /= k
end
end
#############################
# 結果の出力
# gen : 現在の世代番号
#############################
def Output(gen)
k = 0
pr = -1
if @_out_lvl >= 0
print(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ ")
pr = Integer($stdin.gets())
end
if pr != 0
# 出力先の決定と評価値の出力
if pr > 0
out = $stdout
$stdin.gets()
else
now = String(Time.now)
out = open(@_o_file, "a")
out.print("***世代 " + String(gen) + " 適応度 max " + String(@_max) + " (" + String(@_max_n) + ") mean " + String(@_mean) + " 時間 " + now + "\n")
end
# 巡回順序の出力
if @_out_m == 0
for i1 in 0 ... @_len[@_max_n]
n = @_ind[@_max_n][i1]
out.print(String(n) + " " + String(@_city[n][0]) + " " + String(@_city[n][1]) + "\n")
if pr > 0
k += 1
if k == pr
$stdin.gets()
k = 0
end
end
end
end
if pr < 0
out.close()
end
end
end
end
# 入力ミス
if ARGV[0] == nil
print("***error ファイル名を入力して下さい\n")
# 入力ＯＫ
else
# データの数と入力データファイル名の入力
line = gets()
n = Integer(line) # データの数
i_file1 = Array.new(n)
i_file2 = Array.new(n)
for i1 in 0 ... n
line = gets()
a = line.split(" ")
i_file1[i1] = a[0]
i_file2[i1] = a[1]
end
# 実行（乱数の初期値を変える）
for i1 in 0 ... n
print("\n+++++ケース " + String(i1+1) + "+++++\n")
srand(1000 * i1 + 1234567);
tsp = TSP.new(i_file1[i1], i_file2[i1])
tsp.Control()
end
end
=begin
----------------ケーススタディデータ(data_ct.txt)------
3
data1_t.txt data2_t.txt
data1_t.txt data2_t.txt
data1_t.txt data2_t.txt
---------------Species記述データ(data1_t.txt)---------
対立遺伝子上限 9 対立遺伝子下限 0
最大遺伝子長 10 最小遺伝子長（負の時は，最大遺伝子長で固定） -1
遺伝子の重複 0 個体の重複（同じ染色体の個体） 0
集団サイズ 10 子供 10
---------------TSP記述データ(data2_t.txt)--------
出力レベル(負はファイル) 10 出力方法(0:適応度＋順番，1:適応度) 0
出力ファイル名 out1.txt 表示間隔 10
交叉方法 1 交叉確率 1.0 点 5 位置 0 方法 1 バイアス 0 ステップ 1
突然変異方法 1 突然変異率 0.03 幅 1 平均 0.0 標準偏差 1.0
エリート 2 方法 1 バイアス 0 ステップ 1
都市数 10 最大世代交代数 2000
近傍探索(0:行わない，1:行う) 0 近傍（2or3） 2
選択方法(0:最良，1:最初) 1
-58 37
55 -19
6 -79
27 -30
44 -94
33 -58
-94 87
-9 3
33 69
43 -57
=end