可変近傍探索

可変近傍探索（VNS）[ 1 ]は、 1997年にMladenovićとHansenによって提案され、[ 2 ]、一連の組合せ最適化問題と大域最適化問題を解くためのメタヒューリスティック手法です。現在の解の遠隔近傍を探索し、改善が見られた場合のみ、そこから新しい解へと移動します。局所探索法は、近傍の解から局所最適解に到達するために繰り返し適用されます。VNSは、離散および連続最適化問題の解を近似するために設計されており、線形計画問題、整数計画問題、混合整数計画問題、非線形計画問題など を解くことを目的としています

はじめに

VNSは、2つのフェーズで近傍を体系的に変更します。まず、局所最適解を見つけるための降下フェーズ、最後に、対応する谷から抜け出すための摂動フェーズです

アプリケーションの数は急速に増加しており、ロケーション理論、クラスター分析、スケジューリング、車両ルーティング、ネットワーク設計、ロットサイジング、人工知能、エンジニアリング、プーリング問題、生物学、系統発生、信頼性、幾何学、電気通信設計など、 多くの分野に関連しています。

VNSを理解するために重要な書籍はいくつかある。例えば、Handbook of Metaheuristics、2010、[ 3 ] Handbook of Metaheuristics、2003 [ 4 ]およびSearch methodologies、2005 [ 5 ]などである 。このアプローチの動機となった以前の研究は以下に記載されている。

  1. ダビドン、WC [ 6 ]
  2. フレッチャー、R.、パウエル、MJD [ 7 ]
  3. ムラデノビッチ、N. [ 8 ]および
  4. J. ブリンベルグ、N. ムラデノビッチ[ 9 ]

VNS方法論に関する最近の調査と多数の応用については、4OR、2008 [ 10 ]およびAnnals of OR、2010に掲載されています。

問題の定義

決定論的最適化問題を1つ 定義する

ここで、 S、X、x、f はそれぞれ、解空間、実行可能集合、実行可能解、実数値目的関数である。S が有限だが大きな集合である場合、組合せ最適化問題が定義される。 の場合、連続最適化モデルが存在する。 S＝Rn{\displaystyle {S=R^{n}}}

解決策が最適であるのは、 ×∗∈×{\displaystyle {x^{*}\in X}}

問題( 1 )の正確なアルゴリズムは、最適解x*を見つけ、その最適構造を検証すること、または実現不可能な場合は、達成可能な解が存在しない、すなわち、解が無限大であることを示すことである。CPU時間は有限かつ短くなければならない。連続最適化の場合、ある程度の許容範囲を許容することが合理的である。つまり、実行可能な解が見つかった 時点で停止し、×＝∅{\displaystyle X=\varnothing }×∗{\displaystyle x^{*}}

いくつかのヒューリスティックは、近似解、あるいは最適解を、その最適性の検証なしに、迅速に受け入れます。それらの中には、誤った証明を持つものもあり、つまり、得られた 解はxh{\displaystyle x_{h}}

あるεに対しては、これはめったに小さくならない。

ヒューリスティックスは、無限の計算時間を避ける結果として、局所最適解の問題に直面します。問題の局所最適解とは、次のようなものです xL{\displaystyle x_{L}}

は 近傍を表すN(xL){\displaystyle N(x_{L})}xL{\displaystyle x_{L}}

説明

(Mladenović、1995) によれば、VNS は、局所的最小値への降下と、局所的最小値を含む谷からの脱出の両方において、近傍変更の手順を体系的に実行するメタヒューリスティックです。

VNS は次の認識に基づいて構築されています。

  1. ある近傍構造に関する局所最小値は、必ずしも別の近傍構造の局所最小値であるとは限りません。
  2. グローバル最小値とは、すべての可能な近傍構造に関するローカル最小値です。
  3. 多くの問題では、1 つまたは複数の近傍に関する局所最小値は互いに比較的近くなります。

他の多くのメタヒューリスティックとは異なり、VNSとその拡張の基本スキームは単純で、必要なパラメータは少なく、場合によってはパラメータを必要としません。そのため、VNSは、他の手法よりも単純な方法で非常に優れたソリューションを提供するだけでなく、そのパフォーマンスの理由を解明し、より効率的で洗練された実装を可能にします。

最近言及された論文の中には、これを研究できるものがいくつかあります。例えば、(Hansen and Mladenović 1999, 2001a, 2003, 2005; Moreno-Pérez et al.; [ 11 ] )

局所探索ヒューリスティックは、初期解 x を選択し、近傍⁠ ⁠内でxからの下降方向を見つけ、同じ方向に⁠ ⁠内の⁠ ⁠の最小値に進むことで実行されます。下降方向がない場合、ヒューリスティックは停止し、そうでない場合は反復されます。通常、最善の改善とも呼ばれる最高の下降方向が使用されます。この一連のルールは§ アルゴリズム 1にまとめられています。ここでは、初期解xが与えられていると想定しています。出力は、 x′で表される局所的最小値とその値で構成されます。すべてのx ∈ xに対して近傍構造⁠ ⁠が定義されていることに注意してください。各ステップで、 xの近傍⁠ ⁠が完全に探索されます。これは時間がかかる場合があるため、代わりに最初の降下ヒューリスティックを使用することもできます。ベクトルは体系的に列挙され、下降の方向が見つかったらすぐに移動します。これは§アルゴリズム2にまとめられています。 N(x){\displaystyle N(x)}f(x){\displaystyle f(x)}N(x){\displaystyle N(x)}N(x){\displaystyle N(x)}N(x){\displaystyle N(x)}xi∈N(x){\displaystyle x^{i}\in N(x)}

アルゴリズム1: 最良改善（最高降下）ヒューリスティック

関数BestImprovement ( x ) 繰り返すx ′ ← xx ← argmin_ { f ( y ) }, y ∈ N ( x ) ( f ( x ) ≥ f ( x ′) ) となるまでx ′ を返す

アルゴリズム2: 第一改善（第一降下）ヒューリスティック

関数FirstImprovement（x） 繰り返すx ′ ← x ; i ← 0繰り返す私←私+ 1x ← argmin { f ( x ), f ( x ^ i ) }, x ^ i ∈ N ( x ) ( f ( x ) < f ( x ^ i )またはi = | N ( x )| ) になるまで( f ( x ) ≥ f ( x ′) ) となるまでx ′ を返す

あらかじめ選択された近傍構造の有限集合を 、xのk 番目の近傍の解の集合を と表すものとします。 Nk(k=1,...,kmax){\displaystyle {\mathcal {N}}_{k}(k=1,...,k_{\max })}Nk(x){\displaystyle {\mathcal {N}}_{k}(x)}

局所降下法を記述する際にも、この記法が用いられます。近傍またはは、解空間Sに導入された1つ以上の計量関数（または準計量関数）から誘導されます。最適解（または大域最小値）とは、問題が最小値に達する実行可能な解です。となる解が存在しないとき、を に関して問題の局所最小値と呼びます。 N′k(x),k=1,...,kmax′{\displaystyle {\mathcal {N'}}_{k}(x),k=1,...,k'_{\max }}Nk(x){\displaystyle {\mathcal {N}}_{k}(x)}N′k(x){\displaystyle {\mathcal {N'}}_{k}(x)}xopt{\displaystyle x_{\text{opt}}}x′∈X{\displaystyle x'\in X}Nk(x){\displaystyle {\mathcal {N}}_{k}(x)}x∈N′k(x)⊆X{\displaystyle x\in {\mathcal {N'}}_{k}(x)\subseteq X}f(x)<f(x′){\displaystyle f(x)<f(x')}

複数の近傍を使用して問題を解決するために、事実 1 ～ 3 を 3 つの異なる方法で使用できます。

  1. 決定論的
  2. 確率論的
  3. 決定論的かつ確率論的。

まず、§アルゴリズム3で、後で使用する近傍変更関数の手順を示します。関数NeighborhoodChange()は、新しい値と近傍kで得られた現在の値を比較します（1f(x′){\displaystyle f(x')}行目f(x){\displaystyle f(x)}）。改善が得られた場合には、kは初期値に戻され、新しい現在の値が更新されます（2行目）。そうでない場合は、次の近傍が考慮されます（3行目）。

アルゴリズム3: 近隣の変化

関数NeighborhoodChange ( x , x ′ , k )f ( x ′ ) < f ( x )ならば​x ← x ′ // 移動するk ← 1 // 初期近傍そうでない場合k ← k + 1 // 次の近傍

VNS が適切なソリューションを提供しない場合は、ローカル検索での最初の改善戦略と最良の改善戦略を比較する、近傍を減らす、揺れを強化する、VND を採用する、FSS を採用する、パラメータ設定を試してみるなど、プロセスで支援できるステップがいくつかあります。

基本VNS法（BVNS法）（メタヒューリスティックスハンドブック、2010年）[ 3 ]は、近傍の決定論的変化と確率的変化を組み合わせたものである。その手順は§アルゴリズム4に示されている。多くの場合、連続する近傍はネストされる。ステップ4では、決定論的ルールを適用した場合に発生する可能性のある循環を回避するために、点x′がランダムに生成されることに注目されたい。ステップ5では、通常は最良の改善局所探索（§アルゴリズム1 ）が採用される。ただし、これは最初の改善（ §アルゴリズム2 ）に置き換えることもできる。 Nk{\displaystyle {\mathcal {N}}_{k}}

アルゴリズム4: 基本的なVNS

関数VNS ( x , kmax , tmax )繰り返すk ← 1繰り返すx ′ ← Shake ( x , k ) // 振るx ″ ← BestImprovement ( x ′ ) // ローカル検索x ← NeighbourhoodChange ( x , x ″ , k ) // 近隣を変更k = kmaxまでt ← CPU時間()t > tmaxまで

VNSの変種

基本的なVNSは、ランダム化を用いた最良改善降下法です。[ 3 ]追加の労力をかけずに、降下上昇法に変換できます。NeighborhoodChange()関数において、解が現在の解よりも悪い場合でも、ある確率でxをx''に置き換えます。また、第一改善法にも変更できます

基本的なVNSの別のバリエーションとして、「Shaking」ステップにおいて、 k番目の近傍からランダムに生成されたb個（パラメータ）の解の中から最良の解x′ を求めるという方法があります。この拡張には2つのバリエーションがあります。

  1. b 点のうち最良のものから 1 つのローカル検索のみを実行する。
  2. すべてのローカル検索を実行し、最適なものを選択します。

論文（FleszarとHindi [ 12 ]）にはアルゴリズムが記載されている。

拡張

  • VND [ 13 ]
    可変近傍降下法（VND）は、近傍の変更が決定論的に行われる場合に得られます。アルゴリズムの説明では、初期解xが与えられていると仮定します。ほとんどの局所探索ヒューリスティックは、降下フェーズで非常に少数の近傍を使用します。最終解はすべての近傍に関して局所最小値となるはずであるため、VNDを使用する場合、単一の近傍構造を使用する場合よりも大域最小値に到達する可能性が高くなりますkmax{\displaystyle k_{\max }}
  • RVNS [ 14 ]
    縮約VNS法（RVNS法）は、ランダムに点を選択し、降下を行わない場合に得られる。代わりに、これらの新しい点の値を既存の点の値と比較し、改善があれば更新を行う。許容される最大CPU時間や、2つの改善間の最大反復回数など、停止条件が選択されていると仮定する。Nk(x){\displaystyle {\mathcal {N}}_{k}(x)}tmax{\displaystyle t_{\max }}
    アルゴリズムの説明を簡略化するため、以下では を使用します。したがって、RVNS はと という2つのパラメータを使用します。RVNS は、局所探索のコストが高い非常に大規模なインスタンスで有用です。パラメータの最適値は多くの場合2であることが観察されています。さらに、2つの改善間の反復回数の最大値が、通常、停止条件として使用されます。RVNS はモンテカルロ法に似ていますが、より体系的です。tmax{\displaystyle t_{\max }}tmax{\displaystyle t_{\max }}kmax{\displaystyle k_{\max }}kmax{\displaystyle k_{\max }}
  • 歪んだVNS
    歪んだVNS（SVNS）法（Hansen et al.）[ 15 ]は、現在の解から遠く離れた谷を探索する問題に対処します。実際、広い領域で最良の解が見つかった後、改善された解を得るためにはある程度の努力が必要です。離れた近傍でランダムに抽出された解は、現在の解とは大きく異なる場合があり、VNSはある程度、マルチスタートヒューリスティック（ランダムに生成された解から反復的に降下を行うヒューリスティックで、あまり効率的ではないことが知られています）に退化する可能性があります。したがって、現在の解からの距離をある程度補正する必要があります
  • 可変近傍分解探索
    可変近傍分解探索法（VNDS）（Hansen et al.）[ 16 ]は、基本的なVNSを、問題の分解に基づく2段階VNSスキームに拡張する。説明を容易にするため、一般性を損なうことなく、解xはいくつかの要素の集合を表すと仮定する。
  • 並列VNS
    p-メディアン問題を解くために、VNSを並列化するいくつかの方法が最近提案されています。García-Lópezら[ 17 ]では  、そのうち3つがテストされています
    1. 局所探索を並列化する
    2. 現在の近傍から抽出された解の数を増やし、それぞれから並列に局所探索を行う
    3. (ii) と同じことを行いますが、見つかった最適な解決策に関する情報を更新します。
    越智らは、巡回購買者問題を解くために3つの並列VNS戦略を提案している。 [ 18 ]
  • 主双対VNS
    ほとんどの現代のヒューリスティックでは、最適解と得られた解の値の差は完全に不明です。主ヒューリスティックの保証された性能は、目的関数値の下限がわかれば決定できます。この目的のために、標準的なアプローチは、問題の数理計画法に基づいて、主変数の整数性条件を緩和することです
しかし、問題の次元が大きい場合、緩和問題であっても標準的な商用ソルバーでは正確に解くことが不可能になる可能性があります。そのため、双対緩和問題もヒューリスティックに解くことが良いアイデアと考えられます。プライマルヒューリスティックの性能については、保証された限界が得られました。プライマルデュアルVNS（PD-VNS）（Hansen et al.）[ 19 ]では、保証された限界と正確な解の両方を達成するための一般的な方法が提案されています。
  • 可変近傍分岐[ 20 ]
    混合整数線形計画法 (MILP) 問題は、等式制約または不等式制約、および一部の変数に対する整数制限に従って、線形関数を最大化または最小化することから構成されます。
  • 可変近傍定式化空間探索[ 21 ]
    FSSは、1つの問題を複数の定式化で定義でき、定式化を移動することが正当であるため、非常に有用な手法です。局所探索は定式化内で機能することが証明されており、最初の定式化における初期解から開始すると最終解が示唆されます。局所探索は、異なる定式化を体系的に切り替えます。これは、円充填問題（CPP）を対象に調査されました。CPPの非線形計画法による定式化において、直交座標におけるCPPの停留点は、極座標における停留点とは厳密には一致しません。

応用

VNS、あるいはVNSの変種の応用は非常に豊富で、数多くあります。VNSが見つかる分野には、科学論文集などがあります

結論

VNSは、ハンセンとムラデノビッチ[ 22 ]によって提示されたいくつかの特徴を示唆しており、そのいくつかをここで紹介する

  1. シンプルさ：VNSはシンプルで明確、そして普遍的に適用可能です
  2. 精度: VNSは正確な数学的定義に基づいて定式化されている
  3. 一貫性：問題を解決するためのヒューリスティックのすべての行動は、VNS原則に従う
  4. 有効性: VNSは、すべての、または少なくとも最も現実的なインスタンスに対して最適またはほぼ最適なソリューションを提供します。
  5. 効率: VNSは最適または最適に近いソリューションを生成するのに中程度の計算時間を要する
  6. 堅牢性：VNSの機能は、さまざまなインスタンスにわたって一貫している
  7. 使いやすさ：VNSにはパラメータがないので、理解、表現、使用が簡単です。
  8. イノベーション：VNSは新しいタイプのアプリケーションを生み出しています
  9. 一般性：VNSはさまざまな問題に対して良好な結果をもたらします
  10. インタラクティブ性: VNSはユーザーが自分の知識を取り入れて解決プロセスを改善できるようにします。
  11. 多様性: VNS は、ユーザーが選択できる特定のほぼ最適なソリューションを生成できます。

VNSへの関心は急速に高まっており、このテーマに関する論文数は毎年増加しています（10年前はわずか数本、5年前は約12本、2007年には約50本）。さらに、2005年11月にテネリフェ島で開催された第18回EUROミニカンファレンスは、VNSに特化して開催されました。このカンファレンスは、 2007年のIMA Journal of Management Mathematics、2008年のEuropean Journal of Operational Research（http://www.journals.elsevier.com/european-journal-of-operational-research/）、そしてJournal of Heuristics（https://www.springer.com/mathematics/applications/journal/10732/）の特集号の発行につながりました。

参考文献

  1. ^ Hansen, P.; Mladenović, N.; Perez, JAM (2010). 「変数近傍探索：方法と応用」Annals of Operations Research . 175 : 367–407 . doi : 10.1007/s10479-009-0657-6 . S2CID  26469746
  2. ^ Nenad Mladenović ; Pierre Hansen (1997). 「変数近傍探索」. Computers and Operations Research . 24 (11): 1097–1100 . CiteSeerX 10.1.1.800.1797 . doi : 10.1016/s0305-0548(97)00031-2 . 
  3. ^ a b c Gendreau, M.; Potvin, JY. (2010). 「メタヒューリスティックスハンドブック」. Springer.
  4. ^ Glover, F.; Kochenberger, GA (2003). 「メタヒューリスティックスハンドブック」 Kluwer Academic Publishers.
  5. ^ Burke, EK.; Kendall, G. (2005). Burke, Edmund K.; Kendall, Graham (eds.).検索手法. 最適化と意思決定支援技術の入門チュートリアル. Springer. doi : 10.1007/978-1-4614-6940-7 . ISBN 978-1-4614-6939-1。
  6. ^ Davidon, WC (1959). 「最小化のための可変メトリックアルゴリズム」アルゴンヌ国立研究所報告書 ANL- 5990
  7. ^ Fletcher, R.; Powell, MJD (1963). 「最小化のための急速収束降下法」 . Comput. J. 6 ( 2): 163– 168. doi : 10.1093/comjnl/6.2.163 .
  8. ^ Mladenović, N. (1995). 「可変近傍アルゴリズム ― 組み合わせ最適化のための新しいメタヒューリスティック」.モントリオールで開催されたOptimization Daysにおける論文抄録: 112.
  9. ^ Brimberg, J.; Mladenović, N. (1996). 「連続的なロケーション・アロケーション問題を解くための可変近傍アルゴリズム」Stud. Locat. Anal . 10 : 1–12 .
  10. ^ Hansen, P.; Mladenović, N.; Perez, JAM (2008). 「変数近傍探索：手法と応用」. 4OR . 6 (4): 319– 360. doi : 10.1007/s10288-008-0089-1 . S2CID 538959 . 
  11. ^ジャイアンツ州モレノペレス;ハンセン、P.ムラデノビッチ、N. (2005)。 「並列変数近傍探索」。アルバでは、E (編集)。並列メタヒューリスティック: 新しいクラスのアルゴリズム。ページ 247 ～ 266。CiteSeerX 10.1.1.615.2796。土井：10.1002/0471739383.ch11。ISBN  9780471739388。
  12. ^ Fleszar, K; Hindi, KS (2004). 「可変近傍探索による資源制約付きプロジェクトスケジューリング問題の解法」Eur J Oper Res . 155 (2): 402– 413. doi : 10.1016/s0377-2217(02) 00884-6
  13. ^ Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E. (2000). 「マルチソースウェーバー問題を解くためのヒューリスティックの改良と比較」 . Oper. Res . 48 (3): 444– 460. doi : 10.1287/opre.48.3.444.12431 .
  14. ^ Mladenović, N.; Petrovic, J.; Kovacevic-Vujcic, V.; Cangalovic, M. (2003b). 「タブー探索と可変近傍探索によるスペクトル拡散レーダー多相符号設計問題の解決」Eur. J. Oper. Res . 151 (2): 389– 399. doi : 10.1016/s0377-2217(02)00833-0 .
  15. ^ハンセン、P.;ジョーマール, B ;ムラデノビッチ、N;パレイラ、A (2000)。 「加重最大充足可能性問題の変数近傍探索」。Les Cahiers du GERAD G–2000–62、HEC モントリオール、カナダ。
  16. ^ Hansen, P; Mladenović, N; Pérez-Brito, D (2001). 「変数近傍分解探索」. J Heuristics . 7 (4): 335– 350. doi : 10.1023/A:1011336210885 . S2CID 31111583 . 
  17. ^ガルシア＝ロペス、F;メリアン・バティスタ、B;モレノ・ペレス、JA (2002)。 「p メディアン問題の並列変数近傍探索」。Jヒューリスティック。8 (3): 375–388 .土井: 10.1023/A:1015013919497。S2CID 16096161。 
  18. ^ Ochi, LS; Silva, MB; Drummond, L (2001). 「旅行購入者問題の解決のためのGRASPとVNSに基づくメタヒューリスティクス」 MIC'2001 , ポルト: 489–494 .
  19. ^ Hansen, P; Brimberg, J; Uroševi´c, D; Mladenović, N (2007a). 「単純なプラント配置問題のための主-双対変数近傍探索」 . INFORMS J Comput . 19 (4): 552– 564. doi : 10.1287/ijoc.1060.0196 .
  20. ^ Hansen, P.; Mladenović, N.; Urosevic, D. (2006). 「変数近傍探索と局所分岐」. Computers and Operations Research . 33 (10): 3034– 3045. CiteSeerX 10.1.1.108.987 . doi : 10.1016/j.cor.2005.02.033 . 
  21. ^ Mladenović, N.; Plastria, F .; Urosevic, D. (2006). 「円充填問題への再定式化降下の適用」. Computers and Operations Research . 32 (9): 2419– 2434. doi : 10.1016/j.cor.2004.03.010 .
  22. ^ Hansen, P; Mladenović, N (2003). 「変数近傍探索」. Glover F; Kochenberger G (編).メタヒューリスティックスハンドブック. 国際オペレーションズ・リサーチ＆マネジメント・サイエンスシリーズ. 第57巻. ドルドレヒト: クルーワー. pp.  145– 184. CiteSeerX 10.1.1.635.7056 . doi : 10.1007/0-306-48056-5_6 . ISBN  978-1-4020-7263-5。
「 https://en.wikipedia.org/w/index.php?title=Variable_neighborhood_search&oldid=1311725415」より取得