最適化アルゴリズム
集合知プログラミングの第５章最適化の一部を自分なりにまとめます。
ヒルクライム法（傾斜上り法）
ヒルクライム法は、ある地点から少し値を変更し、
変更後の値が変更前の値より低ければ採用する。
これを繰り返して行けば、最小値へ近づくことが出来る。
ヒルクライム法には致命的な弱点がある。
例えば、下図のようなグラフを考える。
このように、局所的最小解があるようなグラフでは、
大局的最小解を発見することはできない。
ヒルクライム法は非常に単純な方法で一般的に使われることは無いが、
この後の手法の比較のために説明する。
アルゴリズム
＜初期化処理＞- ランダムな値で変数を初期化。カウントを初期化。
＜反復処理＞
- 変更する変数を一つ選ぶ。
- 変数の値を増加させるか、減少させるかを決定する。
- 変数の値を変更後、新たな変数でコストを算出する。
- 変更前と変更後のコストの大小を比較する。
- 変更後のコストが小さければ採用する。
- カウンタを進める。
＜終了条件＞
- 反復回数。
具体例
の最小値を求めてみる。
グラフは既に掲載済みである。
このグラフの特徴として、
0.864付近に大局的最小解があるが、
0付近に局所的最小解がある。
作成したプログラムは以下。
# -+- coding: utf-8 -*- import random #ランダムモジュール import math def hillclimboptimize(maxcount=5000, cool=0.95, step=0.001): # ランダムな値で初期化 vec = random.randint(-2,2) print "start =",vec count = 0 while count < maxcount: # 変更する変数を一つ選ぶ。 # 今回の場合は1次元なので選ぶ必要がない。 # i = random.randint(0, dimmension-1) # 変数の値を増加させるか、減少させるかを決定する。 dir = random.randint(0,1) if dir == 0: dir = -step else: dir = step # 変数の値を変更する。 newvec = vec + dir # 変更前と変更後のコストを計算する。 newcost = costf(newvec) cost = costf(vec) # 変更後のコストが小さければ採用する。 if(newcost < cost): vec = newvec # カウンタを進める。 count += 1 return vec def costf(x): return (3*(x**4)) - (5*(x**3)) + (2*(x**2)) if __name__ == '__main__': print hillclimboptimize()
何回か動かした結果です。
% python hillclimb.py 27 木 15:06:34 start = -2 -1.09252884517e-13||< % python hillclimb.py 27 木 15:08:06 start = -1 8.81239525796e-16 % python hillclimb.py 27 木 15:06:00 start = 0 0 % python hillclimb.py 27 木 15:06:01 start = 1 0.864 % python hillclimb.py 27 木 15:07:25 start = 2 0.864
このプログラムの初期値は、
-2,-1,0,1,2のいずれかに設定されていますが、
グラフを見て解る通り、
-2,-1,0では0付近に収束し、
1,2では0.864付近に収束していることがわかる。
これらのことから、局所的最小解に収束する可能性が高いという
ヒルクライム法の問題点がわかったのではないでしょうか。
焼きなまし法（アニーリング法）
焼きなまし法は、大域的最適化問題を解くヒューリスティックな汎用的アルゴリズムの一つである。
焼きなまし法という名前は、物理現象の焼きなましからヒントを得て、
作成されたことに起因する。
焼きなまし法では温度を表す変数を使う。
この変数は当初は非常に高い値を設定し、アルゴリズムが進むに連れて、
次第に低くなっていくように変化させていく。
各反復では解の中の数字をランダムに選び、いずれかの方向にずらす。
そして、変更前と変更後でコストを計算し、両者を比較する。
もし、新しいコストの方が小さければ、新しい解が現在解となる。
しかし、コストが大きくなるときも、一定の確率で新しい解が現在解となる。
これにより、局所最小解を回避可能な点が焼きなまし法の大きな特徴である。
この一定の確率を決定するのが、初めに説明した温度の変数に当たる。
すなわち、初めは温度が高いため、変更前後でコストが大きくなろうとも、
新しい解として採用されやすくなるが、
アルゴリズムが進むに連れて、だんだんと温度が低くなり、
変更前後でコストが大きくなると、新しい解として採用されにくくなる。
アルゴリズム
＜初期化処理＞- ランダムな値で変数を初期化。
＜反復処理＞
- 変更する変数を一つ選ぶ。
- 変数の値を増加させるか、減少させるかを決定する。
- 変数の値を変更後、新たら変数でコストを算出する。
- 変更前と変更後のコストの大小を比較する。
- 変更後のコストが小さければ採用する。コストが大きければ、確率的に採用する。
- 温度を下げる。
＜終了条件＞
- 反復回数または温度指定。
具体例
の最小値を求めてみる。
ヒルクライム法の時と同様の問題を解いてみる。
作成したプログラムは以下。
# -+- coding: utf-8 -*- import random #ランダムモジュール import math def annealingoptimize(T=10000, cool=0.99, step=1): # ランダムな値で初期化 vec = random.randint(-2,2) while T > 0.0001: # 変更する変数を一つ選ぶ。 # 今回の場合は1次元なので選ぶ必要がない。 # i = random.randint(0, dimmension-1) # 変数の値を増加させるか、減少させるかを決定する。 dir = random.random() dir = (dir - 0.5) * step # 変数の値を変更する。 newvec = vec + dir # 変更前と変更後のコストを計算する。 newcost = costf(newvec) cost = costf(vec) # 温度から確率を定義する。 p = pow(math.e, -abs(newcost - cost) / T) print p # 変更後のコストが小さければ採用する。 # コストが大きい場合は確率的に採用する。 if(newcost < cost or random.random() < p): vec = newvec # 温度を下げる T = T * cool return vec def costf(x): return (3*(x**4)) - (5*(x**3)) + (2*(x**2)) if __name__ == '__main__': print annealingoptimize()
以上がメインの焼きなまし法による解法です。
実際に正しいのかどうかのテストコードを作成しました。
if __name__ == '__main__': success, failure = 0,0 for i in range(0, 1000): ans = annealingoptimize() if (ans >= -0.05 and ans <= 0.05): failure += 1 if (ans > 0.8 and ans <= 0.9): success += 1 print success,failure
メインの中身をこのように変えてみましょう。
1,000回試行して、大局的最小解に行き着けたか
あるいは、行き着けなかったかを出力します。
結果は以下の通りです。
% python simulated_annealing_simu.py 27 木 18:57:48 924 76
成功した回数が924件
失敗した回数が76件
となりました。
単に結果が良い方だけを選択し続けた場合、
局所的最小解にしか収束しない。
しかし、焼きなまし法では、結果が悪い場合も確率的に採用することによって、
局所的最小解から抜け出すことが出来、大局的最小解に収束する。
その結果、ヒルクライム法よりも良い結果を導くことができる。
遺伝的アルゴリズム
遺伝的アルゴリズムは、生物の進化からヒントを得た最適化アルゴリズムである。
まず、個体群と呼ばれる無作為解の集団を生成する。
そして、最適化のステップごとに個体群の全メンバーに対して
コストが計算されて、解のリスト内で順位を付ける。
解に順位がついたら、新しい個体群（次の世代）を生成する。
まずは、最良の解をいくつかそのまま新しい個体群に入れる。
これをエリート主義という。
残りは最良の解を改変して作られたまったく新しい解で構成する。
こうした解の改変には２種類ある。
- 突然変異
- 交叉または交配
突然変異
突然変異は、優れた解に対してランダムに値を変化させることで、新しい解を生成する。交叉または交配
交配は、優れた解同士の一部を何らかの方法で組み合わせることで、新しい解を生成する。アルゴリズム
＜初期化処理＞- ランダムな値で個体群を生成。
＜反復処理＞
- 個体群のコストを計算する。
- 個体群のソートを行い、結果が良かったものをエリートとする。
- エリートから突然変異や交配を行ったものを作成し、新しい個体群（次の世代）を生
成する。
＜終了条件＞
- 世代数（反復数）。
具体例
の最小値を求めてみる。
ヒルクライム法の時と同様の問題を解いてみる。
作成したプログラムは以下。
# -+- coding: utf-8 -*- import random #ランダムモジュール import math def geneticoptimize(popnum = 6,popsize=10, step=1,mutprob=0.2,elite=0.2,maxiter=500): # 突然変異の操作 def mutate(vec): i = random.randint(0,popnum-1) return vec[0:i] + [random.randint(0,9)] + vec[i+1:] # 交叉の操作 def crossover(r1, r2): i = random.randint(1, popsize-2) return r1[0:i] + r2[i:] # 初期化個体群の構築 pop = [] for i in range(popsize): vec = [random.randint(0,9) for v in range(0,popnum)] pop.append(vec) # 各世代のエリート数 topelite = int(elite*popsize) # メインループ scores = [] for i in range(maxiter): for vec in pop: x = convertn(vec) scores.append([costf(x),vec]) scores.sort() ranked = [v for (s,v) in scores] # 結果が良かったものをエリートとする。 pop=ranked[0:topelite] # エリートから突然変異や交配を行ったものを作成し、 # 新しい個体群（次の世代）を生成する。 while len(pop)<popsize: if random.random()<mutprob: # 突然変異 c = random.randint(0, topelite) pop.append(mutate(ranked[c])) else: # 交叉 c1=random.randint(0, topelite) c2=random.randint(0, topelite) pop.append(crossover(ranked[c1], ranked[c2])) return convertn(scores[0][1]) def costf(x): return (3*(x**4)) - (5*(x**3)) + (2*(x**2)) def convertn(vec): x,y = 0,0 for v in vec: x += v * (10 ** y) y -= 1 return x if __name__ == '__main__': print geneticoptimize()
以上がメインの焼きなまし法による解法です。
実際に正しいのかどうかのテストコードを作成しました。
if __name__ == '__main__': success, failure = 0,0 for i in range(0, 100): ans = annealingoptimize() if (ans >= -0.05 and ans <= 0.05): failure += 1 if (ans > 0.8 and ans <= 0.9): success += 1 print success,failure
メインの中身をこのように変えてみましょう。
100回試行して、大局的最小解に行き着けたか
あるいは、行き着けなかったかを出力します。
結果は以下の通りです。
% python genetic_simu.py 27 木 23:37:32 100 0
成功した回数が100件
失敗した回数が0件
となりました。
焼きなまし法よりも遺伝的アルゴリズムの方が結果が良くなりました。
しかし、今回の成功、失敗の判断は、
-0.05 <= ans <= 0.05 なら 失敗
0.8 < ans <= 0.9 なら 成功
と大変曖昧なため、一概にも遺伝的アルゴリズムの方が優れているとは言えません。
また、焼きなまし法では1,000回で比較していましたが、
遺伝的アルゴリズムは時間がかかったため、100回で比較しました。
焼きなまし法は最終的にはヒルクライムと同等の動きとなるため、
（大局的な最小解に収束するかどうかはわかりませんが、）
必ず局所的最小解に収束するのに対し、
遺伝的アルゴリズムは確率依存ですので、安定的な性能が出せるかどうかはわかりませ
ん。
ただ、それでも遺伝的アルゴリズムの汎用性の高さ、精度の高さは目を見張るものがあ
ります。
