反復ローカル検索

反復局所探索^{[1] [2]} ( ILS )は、応用数学とコンピュータサイエンスの用語であり、離散最適化問題を解決するための局所探索法または山登り法 の修正を定義します。

局所探索法では、改善可能な近傍が利用できない 局所最小値で行き詰まる可能性があります。

単純な変更は、ローカル検索ルーチンへの呼び出しを繰り返すことで、毎回異なる初期構成から開始します。これは繰り返しローカル検索と呼ばれ、以前のローカル検索フェーズで得られた知識が使用されないことを意味します。学習とは、以前の履歴、たとえば以前に見つかったローカル最小値に関する記憶がマイニングされ、ローカル検索の開始点がより良くなることを意味します。

暗黙の仮定は、局所最小値のクラスター分布です。関数を最小化する場合、ランダムな点から開始するよりも、値の低い局所最小値から開始する方が、適切な局所最小値を決定するのが簡単です。唯一の注意点は、特定の吸引盆地への閉じ込めを避けることです。そのため、局所最小値を次の実行の開始点に変換するキックには、適度な強さが必要ですが、メモリのないランダムな再起動に戻らないようにするには、強すぎてはいけません。

反復ローカル探索は、次の方法でローカルに最適なソリューションのシーケンスを構築することに基づいています。

1. 現在の局所最小値を乱す;
2. 変更されたソリューションから開始した後、ローカル検索を適用します。

摂動の強さは、軌道を異なる吸引域に導き、異なる局所最適値に導くのに十分でなければなりません。

ILS の摂動アルゴリズムを見つけるのは簡単な作業ではありません。主な目的は同じ局所的最小値に陥らないようにすることであり、この特性を確保するために、元に戻す操作は禁止されています。それにもかかわらず、良い順列は多くの値を考慮する必要があります。悪い順列には 2 種類あるからです。

1. 弱すぎる: 同じ局所的最小値に戻る
2. 強すぎる: ランダム再起動

この手順では、インスタンスにとって有意な値（平均確率でまれではない）となるように、摂動の値の数を固定します。その後、実行時にベンチマーク プロットをチェックして、渡されたインスタンスの平均的なアイデアを得ることができます。

与えられた摂動に対してどれが最も適しているかを事前に示す関数は存在しないため、最良の基準はそれを適応させることです。たとえば、Battiti と Protasi は、ILS フレームワークに完全に適合するMAX-SATの反応型検索アルゴリズムを提案しました^{[3] 。彼らは、}タブー検索アルゴリズムによって実装される「有向」摂動スキームを実行し、各摂動の後に標準的なローカル降下アルゴリズムを適用します。摂動を適応させるもう 1 つの方法は、検索中にその強度を決定論的に変更することです。

もう 1 つの手順は、元に戻せないプロパティをアクティブにしたまま、問題のサブ部分を最適化することです。この手順が可能な場合、摂動後に生成されるすべてのソリューションは非常に優れたものになる傾向があります。さらに、新しい部分も最適化されます。

この方法は、ジョブショップスケジューリング問題、^{[4] [5]}フローショップ問題、^[6]車両ルーティング問題^[7]など、いくつか の組み合わせ最適化問題に適用されています。

^[1]