可変近傍検索

可変近傍探索（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つ定義する

${\displaystyle \min {\{f(x)|x\in X,X\subseteq S\}}}$、（１）

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

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

${\displaystyle {f(x^{*})\leq f(x),\qquad \forall {x}\,\in X}}$。

問題（１）の正確なアルゴリズムは、最適解x*を見つけ、その最適構造を検証すること、またはそれが実現不可能な場合は、手順において、達成可能な解が存在しない、すなわち、解が無制限であることを示すことである。CPU時間は有限かつ短くなければならない。連続最適化では、ある程度の許容度を許容することが合理的である。すなわち、実行可能な解が見つかった ときに停止し、${\displaystyle X=\varnothing }$${\displaystyle x^{*}}$

${\displaystyle {f(x^{*})\leq f(x)+\epsilon ,\qquad \forall {x}\,\in X}}$または ${\displaystyle {(f(x^{*})-f(x))/f(x^{*})<\epsilon ,\qquad \forall {x}\,\in X}}$

いくつかのヒューリスティックは、近似解や最適解を迅速に受け入れるが、その最適性の検証は行わない。それらのいくつかは誤った証明、すなわち、得られた解が以下を満たすという証明 を持つ。${\displaystyle x_{h}}$

${\displaystyle {(f(x_{h})-f(x))/f(x_{h})\leq \epsilon ,\qquad \forall {x}\,\in X}}$ 一部の人にとっては、これはめったに小さいことではありません。 ${\displaystyle \epsilon }$

ヒューリスティックは、無限の計算時間を回避する結果として、局所最適値の問題に直面します。問題の局所最適値とは、 ${\displaystyle x_{L}}$

${\displaystyle {f(x_{L})\leq f(x),\qquad \forall {x}\,\in N(x_{L})\cap X}}$

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

関数 BestImprovement(x)
  1: 繰り返し
  2: x' ← x
  3: x ← argmin_{f(y)}, y ∈ N(x)
  4: ( f(x) ≥ f(x') ) となるまで
  5: x'を返す

関数 FirstImprovement(x)
  1: 繰り返し
  2: x' ← x; i ← 0
  3: 繰り返し
  4: i ← i + 1
  5: x ← argmin{ f(x), f(x^i)}, x^i ∈ N(x)
  6: ( f(x) < f(x^i) または i = |N(x)| ) となるまで
  7: ( f(x) ≥ f(x') ) となるまで
  8: x'を返す

事前に選択された近傍構造の有限集合をと表し、xのk 番目の近傍の解の集合を と表すものとします。 ${\displaystyle {\mathcal {N}}_{k}(k=1,...,k_{max})}$${\displaystyle {\mathcal {N}}_{k}(x)}$

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

複数の近傍を使用して問題を解決するために、事実 1 ～ 3 を次の 3 つの異なる方法で使用できます: (i) 決定論的、(ii)確率論的、(iii) 決定論的と確率論的の両方。まず、アルゴリズム 3 で、後で使用する近傍変更関数の手順を示します。関数 NeighborhoodChange() は、新しい値 f(x') を近傍 k で取得された現在の値 f(x) と比較します (行 1)。改善が得られた場合には、k は初期値に戻され、新しい現在の値が更新されます (行 2)。それ以外の場合には、次の近傍が考慮されます (行 3)。

関数 NeighborhoodChange (x, x', k)
 1: f (x') < f(x) ならば
 2: x ← x' // 移動する
 3: k ← 1 // 初期近傍
 4: それ以外の場合
 5: k ← k+1 // 次の近傍

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

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

関数 VNS (x, kmax, tmax)
 1: 繰り返し
 2: く ← 1
 3: 繰り返し
 4: x' ← Shake(x, k) // 振る
 5: x'' ← BestImprovement(x' ) // ローカル検索
 6: x ← NeighbourhoodChange(x, x'', k) // 近傍を変更
 7: k = kmaxまで
 8: t ← CPU時間()
 9: t > tmax まで

基本的な VNS は、ランダム化による最良改善降下法です。^[3]追加の労力をかけずに、降下上昇法に変換できます。NeighbourhoodChange() 関数で、ソリューションが現在のソリューションよりも悪い場合でも、ある確率でxをx"に置き換えます。また、最初の改善方法に変更することもできます。基本的な VNS の別のバリエーションは、「Shaking」ステップで、k番目の近傍からランダムに生成された b (パラメーター) ソリューションの中で最良のソリューションとしてソリューションx' を見つけることです。この拡張には、(1) b ポイントの中で最良のものから 1 つのローカル検索のみを実行する、(2) b ポイントすべてのローカル検索を実行してから最良のものを選択するという 2 つのバリエーションが考えられます。論文 (Fleszar と Hindi ^[12] ) にアルゴリズムが記載されています。

• ベトナムドン^[13]

可変近傍降下法 (VND) は、近傍の変更が決定論的に実行される場合に得られます。そのアルゴリズムの説明では、初期ソリューションxが与えられていると仮定します。降下フェーズのほとんどのローカル検索ヒューリスティックでは、ごく少数の近傍が使用されます。最終ソリューションは、すべての近傍に関して局所的最小値である必要があります。したがって、VND を使用する場合、単一の近傍構造を使用する場合よりも、グローバルなソリューションに到達する可能性が高くなります。${\displaystyle k_{max}}$

• RVNS ^[14]

縮小 VNS (RVNS) 法は、ランダムなポイントが選択され、降下が行われない場合に得られます。代わりに、これらの新しいポイントの値が既存のポイントの値と比較され、改善された場合は更新が行われます。最大許容CPU 時間や 2 つの改善間の最大反復回数などの停止条件が選択されていることが前提となります。${\displaystyle {\mathcal {N}}_{k}(x)}$${\displaystyle t_{max}}$

アルゴリズムの説明を簡略化するために、以下では を使用します。したがって、RVNS はと の2 つのパラメータを使用します。RVNS は、ローカル検索にコストがかかる非常に大規模なインスタンスで役立ちます。パラメータの最適な値は多くの場合 2 であることがわかっています。さらに、2 つの改善間の最大反復回数が停止条件として通常使用されます。RVNS はモンテカルロ法に似ていますが、より体系的です。${\displaystyle t_{max}}$${\displaystyle t_{max}}$${\displaystyle k_{max}}$${\displaystyle k_{max}}$

• 歪んだVNS

歪んだ VNS (SVNS) 法 (Hansen ら) ^[15]は、現在の解から遠く離れた谷を探索する問題に対処します。実際、広い領域で最適な解が見つかったら、改善された解を得るためにある程度進む必要があります。離れた近傍でランダムに抽出された解は、現在の解とは大幅に異なる可能性があり、VNS はある程度、マルチスタート ヒューリスティック (ランダムに生成された解から反復的に降下を行うヒューリスティックで、あまり効率的ではないことが知られています) に退化する可能性があります。したがって、現在の解からの距離を補正する必要があります。

• 可変近傍分解探索

可変近傍分解探索（VNDS）法（Hansen et al.）^[16]は、基本的なVNSを問題の分解に基づく2レベルVNS方式に拡張する。説明を簡単にするため、一般性を損なうことなく、解xがいくつかの要素の集合を表すと仮定する。

• パラレルVNS

最近、p-Median 問題を解決するために、VNS を並列化する方法がいくつか提案されています。García-López ら^[17]では  、そのうちの 3 つがテストされています。(i) ローカル検索を並列化する、(ii) 現在の近傍から抽出されたソリューションの数を増やし、それぞれからローカル検索を並列に実行する、(iii) (ii) と同じことを行うが、見つかった最良のソリューションに関する情報を更新する。Ochiら^{[18]では、}旅行購入者問題を解決するために 3 つの並列 VNS 戦略も提案されています。

• プライマルデュアルVNS

現代のヒューリスティックのほとんどでは、最適解と得られた解の値の差はまったく不明です。主ヒューリスティックの保証されたパフォーマンスは、目的関数値の下限がわかっていれば決定できます。この目的を達成するために、標準的なアプローチは、問題の数理計画法に基づいて、主変数の整数条件を緩和することです。

しかし、問題の次元が大きい場合、緩和された問題であっても標準的な商用ソルバーでは正確に解くことができない可能性があります。したがって、デュアル緩和問題もヒューリスティックに解くことが良いアイデアと思われます。プライマルヒューリスティックのパフォーマンスに関する保証された境界が得られました。Primal-dual VNS (PD-VNS) (Hansen et al.) ^[19]では、保証された境界と正確な解の両方を達成するための1つの一般的な方法が提案されています。

• 可変近傍分岐^[20]

混合整数線形計画法 (MILP) 問題は、等式または不等式制約と、一部の変数に対する整数制限に従って、線形関数を最大化または最小化することから構成されます。

• 可変近傍定式化空間探索^[21]

FSS は、1 つの問題を追加の定式化で定義でき、定式化間を移動することが正当であるため、非常に便利な方法です。定式化内でローカル サーチが機能することが証明されており、最初の定式化の初期ソリューションから開始すると、最終ソリューションが示されます。ローカル サーチは、異なる定式化を体系的に切り替えます。これは、直交座標での CPP の非線形計画定式化の停留点は、厳密には極座標の停留点ではない円充填問題 (CPP)について調査されました。

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/) の特別号につながりました。

• 可変近傍探索に関する EURO ミニカンファレンス XXVIII
• 第5回可変近傍探索国際会議
• 第8回可変近傍探索国際会議