ガイド付きローカル検索

ガイド付きローカル検索は、メタヒューリスティック検索方法です。メタヒューリスティック手法は、ローカル検索アルゴリズムの上に構築してその動作を変更する手法です。

ガイド付きローカル検索では、検索中にペナルティが蓄積されます。ペナルティは、ローカル検索アルゴリズムがローカル最小値やプラトーから抜け出すのに役立ちます。特定のローカル検索アルゴリズムがローカル最適値に落ち着くと、GLS は特定のスキーム (以下で説明) を使用して目的関数を変更します。次に、ローカル検索は、検索をローカル最適値から抜け出すように設計された拡張目的関数を使用して実行されます。重要なのは、目的関数の変更方法です。

この手法の現在の形は、Christos Voudouris博士によって開発され、博士論文で詳細が述べられています。^[1] GLSは、Chang Wang、Edward Tsang、Andrew Davenportによって開発された制約充足問題を解決するためのニューラルネットワークアーキテクチャであるGENETに触発され、拡張されました。GLSとGENETの両方の局所最小値からの脱出メカニズムは、強化学習に似ています。

概要

ソリューションの特徴

GLS を適用するには、特定の問題に対してソリューションフィーチャを定義する必要があります。ソリューションフィーチャは、異なる特性を持つソリューションを区別するために定義され、局所最適値の周りの類似領域を認識して回避できるようにします。ソリューションフィーチャの選択は、問題の種類によって異なり、ある程度は局所検索アルゴリズムによっても異なります。フィーチャごとにコスト関数が定義されます。 $f_{i}$ $c_{i}$

各特徴には、局所最小値における特徴の発生回数を記録するためのペナルティ (最初は 0 に設定) も関連付けられています。 $p_{i}$

多くの場合、特徴とコストは目的関数から直接得られます。たとえば、巡回セールスマン問題では、「ツアーが都市 X から都市 Y まで直接行われるかどうか」を特徴として定義できます。X と Y の間の距離はコストとして定義できます。SAT 問題と重み付け MAX-SAT 問題では、特徴は「現在の割り当てによって節 C が満たされるかどうか」になります。

実装レベルでは、各機能に対して、その機能が現在のソリューションに存在するかどうかを示すインジケーター関数を定義します。ソリューションがプロパティを示す場合は 1 、それ以外の場合は 0 になります。 $i$ $I_{i}$ $I_{i}$ $x$ $i$

選択的なペナルティの変更

GLS は、各特徴にペナルティを課すことの効用を計算します。ローカル検索アルゴリズムがローカル最小値x を返すと、GLS は、そのソリューションに存在する、以下に定義される最大の効用を持つすべての特徴に (特徴のペナルティの増分を通じて) ペナルティを課します。 $\operatorname {util} (x,i)$

\operatorname {util} (x,i)=I_{i}(x){\frac {c_{i}(x)}{1+p_{i}}}.

アイデアとしては、コストの高い機能にペナルティを課すことですが、機能がより頻繁にペナルティを課されるにつれて、そうすることの有用性は低下します。

拡張コスト関数による検索

GLS は、拡張コスト関数 (以下に定義) を使用して、局所最小値に存在する特徴にペナルティを課すことで、局所検索アルゴリズムを局所最小値から外すことができます。その考え方は、これらの特徴が存在しない周囲の検索空間よりも局所最小値をよりコストがかかるようにすることです。

g(x)=f(x)+\lambda a\sum _{1\leq i\leq m}I_{i}(x)p_{i}

パラメータ λ は、ソリューションの検索の強度を変更するために使用できます。λ の値が高いほど、より多様な検索が行われ、プラトーと盆地がより粗く検索されます。一方、値が低いほど、ソリューションの検索がより集中的になり、検索ランドスケープ内のプラトーと盆地がより細かく検索されます。係数は、目的関数のペナルティ部分を目的関数の変化に対してバランスをとるために使用され、問題に固有です。設定の簡単なヒューリスティックは、最初の局所的最小値までの目的関数の平均変化を記録し、この値を問題インスタンスの GLS 機能の数で割った値に設定することです。 $a$ $a$ $a$