【Excel VBAで山登り法を実装】

ExcelVBA

山登り法（Hill Climbing）は、最適化問題を解くための反復的なアルゴリズムの一種です。このアルゴリズムは、解候補を評価し、現在の解の近傍の解候補のうち、目的関数値を改善するものを選択することによって、最適解に収束します。山登り法は、非常に単純で実装が容易であるため、多くの場合、最適化問題の初期段階で使用されます。

山登り法の実装方法

山登り法は、以下の手順で実装されます。

  1. 初期解を選択する
  2. 解の近傍を生成する
  3. 近傍の解の中で目的関数値を最大化（または最小化）するものを選択する
  4. 選択された近傍解が現在の解よりも優れていれば、現在の解を近傍解に置き換える
  5. 収束するまで手順2から手順4を繰り返す

実装するために、以下の手順で検討が必要です。

1.問題の定義

まず、山登り法を使用して解決したい問題を明確に定義します。例えば、関数の最大値や最小値を見つける問題が考えられます。

2.初期解の生成

ランダムに初期解を生成します。この初期解は、問題に依存します。

3.近傍解の生成

現在の解から近傍解を生成します。山登り法では、現在の解の近くにある解を生成することが多いです。

4.近傍解の評価

生成された近傍解を評価し、現在の解と比較します。問題が最大化問題であれば、近傍解が現在の解よりも大きければ、近傍解を新しい解として採用します。最小化問題の場合は、近傍解が現在の解より小さければ、近傍解を新しい解として採用します。

5.収束条件の確認

指定された収束条件が満たされるまで、手順3と4を繰り返します。収束条件は、問題によって異なります。例えば、一定の回数近傍解を評価した場合や、一定の回数新しい解が見つからなかった場合に収束したと判断することができます。

山登り法の問題設定とパラメーター設定

今回は以下の問題・パラメーター設定とした。

問題設定

関数：f(x)=-X^2+2x+2の最大値f(x)となるxを求める。※x=1のとき最大値f(x)=2となる。

パラメーター

初期解:start=0

ステップサイズ:stepSize=0.1

最大反復回数:maxIterations=10000※1000回でもよいと思う。

実装例

実装例は以下のとおり。

Option Explicit

Sub HillClimbing()
    
    ' 変数の宣言と初期値の設定
    Dim start As Double: start = 0 ' 初期解
    Dim stepSize As Double: stepSize = 0.1 ' 近傍解の生成に使用するステップサイズ
    Dim maxIterations As Long: maxIterations = 10000 ' 最大反復回数
    Dim current As Double ' 現在の解
    Dim neighbor As Double ' 近傍解
    Dim best As Double ' 最適解
    Dim bestValue As Double ' 最適解の目的関数値
    Dim currentValue As Double ' 現在の解の目的関数値
    Dim result As Double ' 最終的な解
    Dim i As Long
    
    ' 初期解の設定
    current = start
    ' 最適解と最適解の目的関数値の初期値を設定
    best = current
    bestValue = -best * best + 2 * best + 1
    ' 現在の解の目的関数値の初期値を設定
    currentValue = bestValue
    
    ' 反復処理
    For i = 1 To maxIterations
        ' 近傍解の生成
        neighbor = current + stepSize * (Rnd() - 0.5) * 2 ' ステップサイズを掛けたランダムな値を加算
        ' 近傍解の目的関数値の計算
        currentValue = -neighbor * neighbor + 2 * neighbor + 1
        ' 近傍解が現在の最適解よりも優れている場合、最適解と最適解の目的関数値を更新
        If currentValue > bestValue Then
            best = neighbor
            bestValue = currentValue
        End If
        ' 現在の解を近傍解に更新
        current = neighbor
    Next i
    
    ' 結果をメッセージボックスで表示
    result = best
    MsgBox "Result: " & result
    
End Sub

実行結果

実行結果は以下のとおりです。ランダム値を利用しているため、解にばらつきがでます。
(Resultの値はxの値です。)

まとめ

山登り法は、最適解が局所最適解に収束する可能性が高いため、グローバル最適解を見つけるためには、初期解の選択や探索戦略の改良などの工夫が必要です。また、近傍解の生成方法や目的関数の設計によって、解の質が大きく変わるため、問題に応じて最適なアルゴリズムを選択する必要があります。