局所探索法(Local Search)の基本設計を学ぼう！

最も基本的な局所探索（Local Search）

局所探索法は数々のメタヒューリスティクスの基本となるアルゴリズムであり、最も自然な近傍探索となっています。

アルゴリズムは以下のように記述されます。

1. 適当な初期解を与える
2. 解が改善されなくなるまで解の改善を試みる
3. もうこれ以上改善できない、というところまで繰り返したら解を出力する

疑似コードは以下のようになります。

x = initital_solution　//適当な初期解を与える

while improve(x): //解が改善されなくなるまで繰り返す
    x = improve(x)

return x //解の更新が終わったら解を返す

パッとみてわかるように、非常に単純な構造です。

解の更新を行う関数「improve」の定義の仕方によって局所探索法の性能が変わってくるため、そこの工夫が大切です。

上記疑似コードからわかるように、局所探索法は

1. 初期解の構成
2. 解の改善方法
3. 局所探索による解の更新

という三つのステップから構成されています。

この中で、初期解構築と解の改善方法に関しては問題ごとに違いが出てくるところなので、本記事ではこれ以上は立ち入らないこととします。

多点出発局所探索法（multi start local search）

次は先ほどの局所探索から派生した、多点スタートの局所探索法についてご紹介していきます。

多点出発という名の通り、様々な初期解から出発してより良い解を探していく手法になります。

アルゴリズムは以下のとおりです。

1. 初期解を与える
2. 解が改善されなくなるまで解の更新を繰り返す
3. 指定した終了条件が満たされるまで１､2を繰り返す。

疑似コードは以下のようになります。

while True://終了条件が満たされるまで繰り返す
  x = initial_solution　//初期解を与える

  while improve(x)://改善できる限り解を更新
    x = improve(x)

  x* = x or x*　//最良の解を暫定解とする
return x*

多点出発局所探索法が有効な問題

多点出発の局所探索が有効な問題には、以下のような性質があります。

大渓谷性（big valley property）

局所探索を適用した際、良い局所的最適解ほど、より多くの初期解から到達可能。

多点出発局所探索法においては、解の多様化の実現は初期解のランダム性に依存しており、集中化に関しては局所探索のみに頼っているという状況です。

そのため、十分な最適化性能を実現するためにはさらなる工夫が必要になってきます。

反復局所探索法（iterated local search）

局所探索法を繰り返す際に、初期解から解の改善を試みるのではなく、得られた局所的最適解と近い解からさらに良い解を見つけようとする戦略を、反復局所探索法と呼びます。

このアルゴリズムを実現するためには局所的最適解から抜け出すための「拡張された近傍」を新たに定義する必要があります。

近傍の定義については問題ごとに個別の工夫が必要になるため、ここでは深く立ち入ることはしません。

反復局所探索法の疑似コードは以下のようになります。

x = initial_solution //初期解設定

while True://終了条件が満たされるまで繰り返す

    while improve(x):
        x = improve(x)　//解を更新する

    x* = x or x*　//暫定解を更新
    x = kick(x)　//局所解の近傍を次の初期点とする

return x*

反復局所探索が有効な問題

反復局所探索法が有効な問題には「近接最適性」という性質があります。

近接最適性（proximate optimality property）

良い解に近いところには良い解が存在する

ここでいう「近い解」とは、多項式時間で計算可能な摂動(ほんの少しズラす操作)によって得られる解という意味です。