5分でPythonのランダムヒルクライミングアルゴリズムをマスターする

ランダム化ヒルクライミングは最適化アルゴリズムです。検索プロセスの一部としてランダム性を使用します。これにより、このアルゴリズムは、他のローカル検索アルゴリズムがうまく機能しない非線形目的関数に適したものになります。これは局所探索アルゴリズムでもあり、単一の解を修正し、局所最適解が見つかるまで探索空間の比較的局所的な領域を探索することを意味します。つまり、単峰性最適化問題に適しているか、グローバル最適化アルゴリズムを適用した後に使用するのに適しています。

このチュートリアルでは、関数の最適化のための山登り法最適化アルゴリズムについて説明します。このチュートリアルを完了すると、次のことが分かります。

ヒルクライミングは、関数の最適化のためのランダム化された局所探索アルゴリズムです。
Python でヒルクライミングアルゴリズムをゼロから実装する方法。
ヒルクライミングアルゴリズムを適用し、アルゴリズムの結果を調べる方法。

チュートリアルの概要

このチュートリアルは、次の 3 つの部分に分かれています。

ヒルクライミングアルゴリズム
ヒルクライミングアルゴリズムの実装
ヒルクライミングアルゴリズムの適用例

ヒルクライミングアルゴリズム

ランダム化ヒルクライミングアルゴリズムは、ランダムローカル探索最適化アルゴリズムです。入力として、開始点とステップサイズ (検索空間内の距離) を受け取ります。アルゴリズムは、初期ポイントを現在の最良の候補ソリューションとして取得し、指定されたポイントのステップ距離内に新しいポイントを生成します。結果ポイントが計算され、それが現在のポイントと同等かそれ以上であれば、それが現在のポイントとみなされます。新しいポイントはランダム性を使用して生成されます。これはランダムヒルクライミングとも呼ばれます。つまり、アルゴリズムは検索の一環として、応答面の凹凸のある領域、ノイズの多い領域、不連続な領域、または誤解を招く領域をスキップできます。同等の評価を持つ異なるポイントを受け入れることは、アルゴリズムが応答面の平坦な領域などの検索空間の探索を継続できるようにするため重要です。無限ループを回避するために、いわゆる「横方向」の移動を制限することも役立つ場合があります。このプロセスは、関数評価の最大数に達するか、指定された数の関数評価内で改善が見られない場合など、停止条件が満たされるまで継続されます。このアルゴリズムの名前の由来は、応答曲面の丘を（ランダムに）登って局所最適値に到達するからです。これは、目的関数を最大化するためにのみ使用できるという意味ではありません。それはただの名前です。実際、通常は関数を最大化するのではなく、最小化します。ローカル検索アルゴリズムであるため、ローカル最適解に陥る可能性があります。ただし、複数回の再起動により、アルゴリズムはグローバル最適値を見つけることができる場合があります。ステップサイズは、検索空間内でより適切な近傍ポイントを見つけられるほど十分に大きくする必要がありますが、検索が局所最適値を含む領域から外れてしまうほど大きくしてはなりません。

ヒルクライミングアルゴリズムの実装

この記事の執筆時点では、SciPy ライブラリはランダムヒルクライミングの実装を提供していません。ただし、私たち自身で実装することは可能です。まず、目的関数と、目的関数に対する各入力変数の境界を定義する必要があります。目的関数は単なる Python 関数であり、Objective() という名前を付けます。境界は、入力変数ごとに 1 つの次元を持ち、変数の最小値と最大値を定義する 2D 配列になります。たとえば、1 次元の目的関数と境界は次のように定義されます。

 # 目的関数 
定義目標(x):  
 0を返す 
 # 入力範囲を定義する 
境界=配列([[-5.0, 5.0]])

次に、問題領域内のランダムなポイントとして初期ソリューションを生成し、目的関数を使用してそれらを評価できます。

 # 初期点を生成する 
解=境界[:, 0] + rand(len(境界)) * (境界[:, 1] - 境界[:, 0])  
 # 初期点を評価する 
 solution_eval =目的(ソリューション)

これで、100 や 1,000 など、「n_iterations」として定義されたアルゴリズムの反復回数を反復処理できるようになりました。

 # ヒルクライムを走る 
 i が範囲内(n_iterations)の場合:

アルゴリズムの反復における最初のステップは、ステップを実行することです。これには、検索空間の境界に相対する事前定義された「step_size」パラメータが必要です。平均が現在のポイントで、標準偏差が 'step_size' によって定義されるガウス分布からランダムなステップを取得します。これは、ステップの約 99% が現在のポイントの (3 * step_size) 以内にあることを意味します。

 # 一歩踏み出す 
候補=解+ randn(len(bounds)) * step_size

このアプローチを取る必要はありません。おそらく、0 からステップサイズまでの一様分布を使用することをお勧めします。例えば：

 # 一歩踏み出す 
候補=解+ rand(len(bounds)) * step_size

次に、目的関数を使用して新しい候補ソリューションを評価する必要があります。

 # 候補ポイントを評価する 
 candidate_eval =目標（候補者）

次に、この新しいポイントが現在の最良のポイントと同等かそれ以上であると評価されるかどうかを確認し、同等かそれ以上であると評価される場合は、現在の最良のポイントをこの新しいポイントに置き換える必要があります。

 # 新しいポイントを保持するかどうかを確認します 
候補評価< = 解決評価の場合:  
 # 新しいポイントを保存する 
 解決策、 solution_eval =候補、candidate_eval  
 # 進捗状況を報告する 
 print(' > %d f(%s) = %.5f' % (i, solution, solution_eval))

それでおしまい。このヒルクライミングアルゴリズムは、目的関数の名前、各入力変数のスコープ、反復の合計回数、およびステップをパラメーターとして受け取り、見つかった最適なソリューションとその評価を返す再利用可能な関数として実装できます。

 # ヒルクライミング局所探索アルゴリズム 
 def hillclimbing(目的、境界、n_iterations、ステップサイズ):  
 # 初期点を生成する 
解=境界[:, 0] + rand(len(境界)) * (境界[:, 1] - 境界[:, 0])  
 # 初期点を評価する 
 solution_eval =目的(ソリューション)  
 # ヒルクライムを走る 
 i が範囲内(n_iterations)の場合:  
  # 一歩踏み出す 
候補=解+ randn(len(bounds)) * step_size  
  # 候補ポイントを評価する 
 candidate_eval =目標（候補者）  
  # 新しいポイントを保持するかどうかを確認します
  候補評価< = 解決評価の場合:  
   # 新しいポイントを保存する 
   解決策、 solution_eval =候補、candidate_eval  
   # 進捗状況を報告する 
   print(' > %d f(%s) = %.5f' % (i, solution, solution_eval))  
 [ソリューション、ソリューション評価] を返す

Python でヒルクライミングアルゴリズムを実装する方法がわかったので、それを使用して目的関数を最適化する方法を見てみましょう。

ヒルクライミングアルゴリズムの適用例

このセクションでは、山登り最適化アルゴリズムを目的関数に適用します。まず、目的関数を定義しましょう。 [-5, 5]の範囲にある単純な1次元x^2目的関数を使用します。以下の例では、関数を定義し、入力値のグリッドに対する関数の応答曲面の折れ線グラフを作成し、f(0.0) = 0.0 の最適値を赤い線でマークします。

 # 凸単峰性最適化関数 
 numpyからarangeをインポート 
 matplotlibからpyplotをインポートする 
 # 目的関数 
定義目標(x):  
 x[0]**2.0を返す 
 # 入力範囲を定義する 
 r_min、 r_max = -5.0、5.0  
 # 入力範囲を 0.1 刻みで均一にサンプリングする 
入力=範囲(r_min, r_max, 0.1)  
 # 計算ターゲット 
結果= [objective([x]) for x in inputs]  
 # 入力と結果の折れ線グラフを作成する 
 pyplot.plot(入力、結果)  
 # 最適な入力値を定義する 
 x_optima = 0.0  
 # 最適な入力に垂直線を描く 
 pyplot.axvline( x = x_optima 、 ls = '--' 、 color = 'red' )  
 # プロットを表示 
 pyplot.show()

例を実行すると、目的関数の折れ線グラフが作成され、関数の最適値が明確にマークされます。

次に、ヒルクライミングアルゴリズムを目的関数に適用します。まず、疑似乱数ジェネレータにシードを設定します。通常、これは必要ありませんが、この場合は、後で結果をプロットできるように、アルゴリズムを実行するたびに同じ結果 (同じ乱数シーケンス) が得られるようにする必要があります。

 # 疑似乱数ジェネレータのシード値 
シード(5)

次に、検索の設定を定義します。この場合、アルゴリズムの 1,000 回の反復を検索し、ステップサイズとして 0.1 を使用します。ステップサイズを生成するためにガウス関数を使用していると仮定すると、すべてのステップの約 99% が、指定されたポイント (0.1*3) の距離内、つまり 3 標準偏差以内になることを意味します。

 n_iterations = 1000    
 # 最大ステップサイズを定義する 
ステップサイズ= 0.1

次に、検索を実行して結果を報告します。

 # ヒルクライミング検索を実行する 
ベスト、スコア=ヒルクライミング(目的、境界、反復回数、ステップサイズ)  
 print('完了しました!')  
 print('f(%s) = %f' % (ベスト、スコア))

すべてをまとめると、完全な例が以下にリストされます。

 # 1次元目的関数の山登り探索 
 NumPyからasarrayをインポート 
 numpy.randomからrandnをインポートする 
 numpy.randomからrandをインポート 
 numpy.randomからシードをインポート 
 # 目的関数 
定義目標(x):  
 x[0]**2.0を返す 
 # ヒルクライミング局所探索アルゴリズム 
 def hillclimbing(目的、境界、n_iterations、ステップサイズ):  
 # 初期点を生成する 
解=境界[:, 0] + rand(len(境界)) * (境界[:, 1] - 境界[:, 0])  
 # 初期点を評価する 
 solution_eval =目的(ソリューション)  
 # ヒルクライムを走る 
 i が範囲内(n_iterations)の場合:
  # 一歩踏み出す 
候補=解+ randn(len(bounds)) * step_size  
  # 候補ポイントを評価する 
 candidate_eval =目標（候補者）  
  # 新しいポイントを保持するかどうかを確認します 
  候補評価< = 解決評価の場合:  
   # 新しいポイントを保存する 
   解決策、 solution_eval =候補、candidate_eval  
   # 進捗状況を報告する 
   print(' > %d f(%s) = %.5f' % (i, solution, solution_eval))  
 [ソリューション、ソリューション評価] を返す 
 # 疑似乱数ジェネレータのシード値 
シード(5)  
 # 入力範囲を定義する 
境界=配列([[-5.0, 5.0]])  
 # 合計反復回数を定義する
n_iterations = 1000    
 # 最大ステップサイズを定義する 
ステップサイズ= 0.1  
 # ヒルクライミング検索を実行する 
ベスト、スコア=ヒルクライミング(目的、境界、反復回数、ステップサイズ)  
 print('完了しました!')  
 print('f(%s) = %f' % (ベスト、スコア))

例を実行すると、改善が検出されるたびに、反復回数、関数への入力、目的関数からの応答など、検索の進行状況が報告されます。検索の最後に、最適なソリューションが見つかり、その評価が報告されます。この場合、アルゴリズムの 1,000 回の反復で 36 の改善があり、ソリューションは 0.0 の最適入力に非常に近く、f(0.0) = 0.0 と評価されることがわかります。

 > 1 f([-2.74290923]) = 7.52355  
 > 3 f([-2.65873147]) = 7.06885  
 > 4 f([-2.52197291]) = 6.36035  
 > 5 f([-2.46450214]) = 6.07377  
 > 7 f([-2.44740961]) = 5.98981  
 > 9 f([-2.28364676]) = 5.21504  
 > 12 f([-2.19245939]) = 4.80688  
 > 14 f([-2.01001538]) = 4.04016  
 > 15 f([-1.86425287]) = 3.47544  
 > 22 f([-1.79913002]) = 3.23687  
 > 24 f([-1.57525573]) = 2.48143  
 > 25 f([-1.55047719]) = 2.40398  
 > 26 f([-1.51783757]) = 2.30383  
 > 27 f([-1.49118756]) = 2.22364  
 > 28 f([-1.45344116]) = 2.11249  
 > 30 f([-1.33055275]) = 1.77037  
 > 32 f([-1.17805016]) = 1.38780  
 > 33 f([-1.15189314]) = 1.32686  
 > 36 f([-1.03852644]) = 1.07854  
 > 37 f([-0.99135322]) = 0.98278  
 > 38 f([-0.79448984]) = 0.63121  
 > 39 f([-0.69837955]) = 0.48773  
 > 42 f([-0.69317313]) = 0.48049  
 > 46 f([-0.61801423]) = 0.38194  
 > 48 f([-0.48799625]) = 0.23814  
 > 50 f([-0.22149135]) = 0.04906  
 > 54 f([-0.20017144]) = 0.04007  
 > 57 f([-0.15994446]) = 0.02558  
 > 60 f([-0.15492485]) = 0.02400  
 > 61 f([-0.03572481]) = 0.00128  
 > 64 f([-0.03051261]) = 0.00093  
 > 66 f([-0.0074283]) = 0.00006  
 > 78 f([-0.00202357]) = 0.00000  
 > 119 f([0.00128373]) = 0.00000  
 > 120 f([-0.00040911]) = 0.00000  
 > 314 f([-0.00017051]) = 0.00000  
終わり！  
 （[-0.00017051]）= 0.000000

検索の進行状況を、各改善後の最善の解決策の評価の変化を示す折れ線グラフとして表示すると興味深いかもしれません。次に、hillclimbing() を更新して目的関数の評価を追跡し、改善があるたびにこのスコアのリストを返すことができます。

 # ヒルクライミング局所探索アルゴリズム 
 def hillclimbing(目的、境界、n_iterations、ステップサイズ):  
 # 初期点を生成する 
解=境界[:, 0] + rand(len(境界)) * (境界[:, 1] - 境界[:, 0])  
 # 初期点を評価する 
 solution_eval =目的(ソリューション)  
 # ヒルクライムを走る
スコア=リスト()  
 スコアを追加します(solution_eval)  
 i が範囲内(n_iterations)の場合:  
  # 一歩踏み出す 
候補=解+ randn(len(bounds)) * step_size  
  # 候補ポイントを評価する 
 candidate_eval =目標（候補者）  
  # 新しいポイントを保持するかどうかを確認します 
  候補評価< = 解決評価の場合:  
   # 新しいポイントを保存する 
   解決策、 solution_eval =候補、candidate_eval  
   # スコアを記録する 
   スコアを追加します(solution_eval)  
   # 進捗状況を報告する 
   print(' > %d f(%s) = %.5f' % (i, solution, solution_eval))  
 [ソリューション、ソリューション評価、スコア] を返します。

次に、これらのスコアの折れ線グラフを作成し、検索中に見つかった各改善に対する目的関数の相対的な変化を確認できます。

 # 最高スコアの折れ線グラフ 
 pyplot.plot(スコア, '.-')  
 pyplot.xlabel('改善数')  
 pyplot.ylabel('評価 f(x)')  
 pyplot.show()

これらすべてをまとめると、検索を実行し、検索中に改善されたソリューションの目的関数スコアをプロットする完全な例がここにあります。

 # 1次元目的関数の山登り探索 
 NumPyからasarrayをインポート 
 numpy.randomからrandnをインポート 
 numpy.randomからrandをインポート 
 numpy.randomからシードをインポート 
 matplotlibからpyplotをインポートする 
 # 目的関数 
定義目標(x):  
 x[0]**2.0を返す 
 # ヒルクライミング局所探索アルゴリズム 
 def hillclimbing(目的、境界、n_iterations、ステップサイズ):  
 # 初期点を生成する 
解=境界[:, 0] + rand(len(境界)) * (境界[:, 1] - 境界[:, 0])  
 # 初期点を評価する 
 solution_eval =目的(ソリューション)  
 # ヒルクライムを走る 
スコア=リスト()  
 スコアを追加します(solution_eval)  
 i が範囲内(n_iterations)の場合:  
  # 一歩踏み出す 
候補=解+ randn(len(bounds)) * step_size  
  # 候補ポイントを評価する 
 candidate_eval =目標（候補者）  
  # 新しいポイントを保持するかどうかを確認します 
  候補評価< = 解決評価の場合:  
   # 新しいポイントを保存する 
   解決策、 solution_eval =候補、candidate_eval  
   # スコアを記録する 
   スコアを追加します(solution_eval)  
   # 進捗状況を報告する 
   print(' > %d f(%s) = %.5f' % (i, solution, solution_eval))  
 [ソリューション、ソリューション評価、スコア] を返します。  
 # 疑似乱数ジェネレータのシード値 
シード(5)  
 # 入力範囲を定義する 
境界=配列([[-5.0, 5.0]])  
 # 合計反復回数を定義する 
 n_iterations = 1000    
 # 最大ステップサイズを定義する 
ステップサイズ= 0.1  
 # ヒルクライミング検索を実行する 
 best、score、 scores = hillclimbing (objective、bounds、n_iterations、step_size) ベスト、スコア、scores = hillclimbing (objective、bounds、n_iterations、step_size)  
 print('完了しました!')  
 print('f(%s) = %f' % (ベスト、スコア))  
 # 最高スコアの折れ線グラフ 
 pyplot.plot(スコア, '.-')  
 pyplot.xlabel('改善数')  
 pyplot.ylabel('評価 f(x)')  
 pyplot.show()

例を実行すると、以前と同じように検索が実行され、結果が報告されます。ヒルクライミング検索中に目的関数の各改善された評価を示す折れ線グラフを作成します。検索中、目的関数の評価が約 36 回変更され、アルゴリズムが最適値に収束するにつれて初期に大きな変更が発生し、検索の終了時には小さくて気付かないほどの変化が発生することがわかります。

目的関数が 1 次元である場合、上記のように応答曲面をプロットするのは簡単です。検索中に見つかった最良の候補ソリューションを応答曲面の点としてプロットすることで、検索の進行状況を確認すると興味深いかもしれません。応答面に沿って最適値につながる一連の点を期待します。これは、まず hillclimbing() 関数を更新して、検索中に各最適な候補ソリューションがどこにあるかを追跡し、次に最適なソリューションのリストを返すことによって実現できます。

 # ヒルクライミング局所探索アルゴリズム 
 def hillclimbing(目的、境界、n_iterations、ステップサイズ):  
 # 初期点を生成する 
解=境界[:, 0] + rand(len(境界)) * (境界[:, 1] - 境界[:, 0])  
 # 初期点を評価する 
 solution_eval =目的(ソリューション)
 # ヒルクライムを走る 
ソリューション=リスト()  
 ソリューション.append(ソリューション)  
 i が範囲内(n_iterations)の場合:  
  # 一歩踏み出す 
候補=解+ randn(len(bounds)) * step_size  
  # 候補ポイントを評価する
  candidate_eval =目標（候補者）  
  # 新しいポイントを保持するかどうかを確認します 
  候補評価< = 解決評価の場合:  
   # 新しいポイントを保存する 
   解決策、 solution_eval =候補、candidate_eval  
   # 解決策を追跡する 
   ソリューション.append(ソリューション)
   # 進捗状況を報告する 
   print(' > %d f(%s) = %.5f' % (i, solution, solution_eval))  
 [ソリューション、ソリューション評価、ソリューション] を返します。

次に、目的関数の応答曲面のプロットを作成し、前と同じように最適値にラベルを付けます。

 # 入力範囲を 0.1 刻みで均一にサンプリングする 
入力= arange (境界[0,0]、境界[0,1]、0.1)  
 # 入力と結果の折れ線グラフを作成する 
 pyplot.plot(入力、[objective([x]) for x in inputs], '--')  
 # 最適な入力に垂直線を描く 
 pyplot.axvline( x =[0.0], ls = '--' ,色= '赤' )

最後に、検索によって見つかった候補ソリューションのシーケンスを黒い点でプロットできます。

 # サンプルを黒い円としてプロットする 
 pyplot.plot(ソリューション、[objective(x) for x in solutions]、'o'、色= 'black' )

すべてをまとめると、以下は目的関数の応答面上に改善されたソリューションのシーケンスをプロットする完全な例です。

 # 1次元目的関数の山登り探索 
 NumPyからasarrayをインポート 
 numpyからarangeをインポート 
 numpy.randomからrandnをインポート 
 numpy.randomからrandをインポート 
 numpy.randomからシードをインポート 
 matplotlibからpyplotをインポートする 
 # 目的関数 
定義目標(x):  
 x[0]**2.0を返す 
 # ヒルクライミング局所探索アルゴリズム 
 def hillclimbing(目的、境界、n_iterations、ステップサイズ):  
 # 初期点を生成する 
解=境界[:, 0] + rand(len(境界)) * (境界[:, 1] - 境界[:, 0])  
 # 初期点を評価する 
 solution_eval =目的(ソリューション)  
 # ヒルクライムを走る 
ソリューション=リスト()  
 ソリューション.append(ソリューション)  
 i が範囲内(n_iterations)の場合:  
  # 一歩踏み出す 
候補=解+ randn(len(bounds)) * step_size  
  # 候補ポイントを評価する 
 candidate_eval =目標（候補者）  
  # 新しいポイントを保持するかどうかを確認します 
  候補評価< = 解決評価の場合:  
   # 新しいポイントを保存する 
   解決策、 solution_eval =候補、candidate_eval  
   # 解決策を追跡する 
   ソリューション.append(ソリューション) 
    # 進捗状況を報告する 
   print(' > %d f(%s) = %.5f' % (i, solution, solution_eval))  
 [ソリューション、ソリューション評価、ソリューション] を返します。  
 # 疑似乱数ジェネレータのシード値 
シード(5)  
 # 入力範囲を定義する 
境界=配列([[-5.0, 5.0]])  
 # 合計反復回数を定義する 
 n_iterations = 1000    
 # 最大ステップサイズを定義する 
ステップサイズ= 0.1  
 # ヒルクライミング検索を実行する 
ベスト、スコア、ソリューション=ヒルクライミング(目的、境界、反復回数、ステップ サイズ)  
 print('完了しました!')  
 print('f(%s) = %f' % (ベスト、スコア))  
 # 入力範囲を 0.1 刻みで均一にサンプリングする 
入力= arange (境界[0,0]、境界[0,1]、0.1)  
 # 入力と結果の折れ線グラフを作成する
pyplot.plot(入力、[objective([x]) for x in inputs], '--')  
 # 最適な入力に垂直線を描く 
 pyplot.axvline( x =[0.0], ls = '--' ,色= '赤' )  
 # サンプルを黒い円としてプロットする 
 pyplot.plot(ソリューション、[objective(x) for x in solutions]、'o'、色= 'black' )  
 pyplot.show()