数理最適化セミナーのご案内

B.6 重み付き局所探索法WLS

　このアルゴリズムは最適化問題を局所探索により近似的に解くものです．問題が二次式を含む場合は整数変数のみを扱うことができ，すべて線形式の場合は連続変数も扱うことができます．近似解法のため得られた解の最適性の保証はありません．

　本アルゴリズムは各制約式に疑似的に「重み」をもたせ，制約違反量の合計を目的関数と合わせて最小化します．

　WLSの対象となる問題を以下のように定義します．

\begin{equation*} \begin{aligned} & \text{minimize} & & c^\top x + \frac{1}{2} x^\top Q x \\ & \text{subject to} & & f_{i}(x) \le b_i, & i \in M_L, \\ & & & f_{i}(x) \ge b_i, & i \in M_G, \\ & & & f_{i}(x) = b_i, & i \in M_E, \\ & & & l_j \le x_j \le u_j, & x_j \in N_I \cup N_C, \\ & & & x_j \in \mathbb{Z}, & j \in N_I, \\ & & & x_j \in \mathbb{R}, & j \in N_C. \; \end{aligned} \end{equation*}

　ここで，$f_{i}(x)$は線形式あるいは二次式を表します．

　上の問題に対して重み$w^+, w^-$を導入し，以下のような緩和問題を考えます．

\begin{equation*} \begin{aligned} & \text{minimize} & & c^\top x + \frac{1}{2} x^\top Q x + \sum_{i \in M_L \cup M_E} w^+_i y^+_i + \sum_{i \in M_G \cup M_E} w^-_i y^-_i \\ & \text{subject to} & & f_{i}(x) - y^+_i \le b_i, & i \in M_L, \; \\ & & & f_{i}(x) + y^-_i \ge b_i, & i \in M_G, \; \\ & & & f_{i}(x) - y^+_i + y^-_i = b_i, & i \in M_E, \; \\ & & & l_j \le x_j \le u_j, & x_j \in N_I \cup N_C, \\ & & & x_j \in \mathbb{Z}, & j \in N_I, \\ & & & x_j \in \mathbb{R}, & j \in N_C, \\ & & & y^+_i \ge 0, & i \in M_L \cup M_E, \; \\ & & & y^-_i \ge 0, & i \in M_G \cup M_E. \; \end{aligned} \end{equation*}

　アルゴリズムの各反復では，重み$w^+, w^-$を当該制約式の違反量が大きいものほど大きくなるよう内部で自動調整します．探索時は自動調整された重み$w^+, w^-$に基づき，上記緩和問題において目的関数が減少する方向へ解が遷移します．これにより制約条件に違反している解から違反を解消する方向や目的関数値が減少する方向へ解が遷移し，より良い解が得られます．

　本アルゴリズムは緩和問題に対して局所探索を行うため，制約式をすべて満たす解が存在しない場合においてもできるだけ制約を満たす解が得られます．

　本アルゴリズムはソフト制約付きの最適化問題を扱えます．ここでソフト制約とは，制約違反に対して所与の重みに比例したペナルティがかかる制約のことです．ソフト制約に違反した解も実行可能解となります．したがってソフト制約は通常の制約に比べ満たすべき優先度が低く，ソフト制約同士であれば所与の重みが大きいほど優先度が高いと解釈できます．本アルゴリズムでは所与の重みを重み$w^+, w^-$の自動調整の際の上限値として扱うことで，上記の優先度に合わせた制約違反の解消を実現します．

　類似アルゴリズムである制約充足問題ソルバwcspとの関連に触れながら，技術的な詳細を簡単に説明します．WLSとwcspはいずれも局所探索の性能向上のための工夫をもつ手法です．wcspはタブー・サーチと呼ばれるアルゴリズムを用いることで得られる局所最適解の質の向上を狙います．一方でWLSは近傍操作の種類を増やすことで同様の効果を狙います．各近傍操作においてwcspは1つの離散変数の値しか変化させないのに対し，WLS は最大4つの整数変数の値を変化させます．wcspが複数回の近傍操作をしないと得られないような解もWLSは一回の近傍操作で得られます．

　WLS は近傍操作の計算時間の削減を「隣接リスト」というデータ構造を用いて実現します．ここで隣接リストとは，変数同士の関連度の推定値に基づき，強く関連する変数の組を保持するリストです．2つ以上の整数変数の値を変化させる際にはこの隣接リストを用い，改善解を得る見込みが薄い近傍操作をスキップします．

　本アルゴリズムは，係数が1である線形な制約式に対する高速化手法を取り入れています．したがってそのような制約式が多い最適化問題，特に大規模な集合被覆問題や集合分割問題に対して高い性能を発揮します．

　本アルゴリズムの詳細については[19]をご参照ください．

　高度な機能として，変数に対し「割当ラベル」が設定された場合，WLSは設定から二部グラフ（頂点が2つのグループに分けられ、異なるグループの頂点同士だけが辺で結ばれるグラフ）を構築することによって，探索範囲を拡大します．4つの整数変数の値を変化させる近傍操作において割当ラベルの情報が考慮され，割当の交換などの有望な近傍操作に基づき，より深く探索を行います．

B.5 タブー・サーチによる資源制約スケジューリング問題解法
C. 使い方に関するサポート

 

 

上に戻る