バイナリ二次計画問題の近似解法

前述した結果にもとづき、大規模な無制約／制約付きバイナリ二次計画問題の解法として、

厳密解法ではなく、メタヒューリスティックスによる近似解法を採用する。

メタヒューリスティックスには、タブーサーチ(TS: Tabu Search)、焼きなまし法(SA:

Simulated Annealing)、遺伝的アルゴリズム(GA: Genetic Algorithm)、進化的アルゴリズ

ム(EV: Evolutionary Algorithm)など各種の手法が提案されているが、本稿では、無制約バ

イナリ二次計画問題に多用され良い結果が報告されているタブーサーチを採用し、これを 制約付きバイナリ二次計画問題へ拡張することとする。

タブーサーチは、近似解法の基本手法である局所探索法(Local Search、 or Hill Climbing、

or Neighborhood Search)がベースとなっており、これに、局所最適解(Local Optimum)か らの脱出戦略を取り入れた手法である。平たく言えば、局所探索法で探索の集中化

(Intensification)を行い、局所最適解からの脱出で探索の多様化(Diversification)を図ると

いう仕掛けである。局所探索法では、現在の解周辺(近傍: neighborhood)の局所的情報のみ に基づいて、目的関数を常に改善する方向へ移動(move)する探索戦略を採用しているため、

局所最適解に陥りやすい。タブーサーチでは、目的関数を改善しない方向への移動も許容 することで、局所最適解から脱出することを試みる。ただし、目的関数の改悪方向への移 動を許すと、元の探索位置へ戻るというサイクリング現象が生じるので、移動情報を格納 するタブーリストというものを用意してサイクリングを防いでいる(但 し完全に防止できる 訳ではない)。このタブーリストの導入が、タブーサーチという名称の由来である。タブー リストを利用する原理は簡単で、まず探索の反復過程で移動が発生した時点において、そ の移動情報(更新された変 数 など)に潜伏可能期間(tabu tenureという)としての初期値を与 え、探索の反復を実行する度にすべての移動情報の潜伏可能期間から１を減じるだけでよ い。探索の反復過程では、潜伏可能期間が残っているタブー期間中にタブーリストに記載され た箇所への移動は近傍探索から除く仕組みが採用される。

このタブーリストによる探索戦略は、短期的情報に基づく(recency based)局所最適解から

の脱出方法とされている。これ以外にも、タブーサーチでは、長期的情報に基づく全域最 適解探索戦略の枞組みを持っており、解探索過程の統計的情報(変数が更新された頻度、変 数にある値が割当てられた頻度など)に基づいて、未知あるいは探査不足の探索領域へ踏み 込む方法が提案されている。なおタブーサーチの文献では、短期的情報のことをshort-term

memory、長期的情報のことをlong-term memoryと呼んでいる。

本稿では、以上に述べた局所探索法と短期的情報に基づくタブーサーチのアルゴリズムの 概要を記述するとともに、文献[46]で提案された長期的情報に基づくタブーサーチ手法であ るDiversification-driven tabu searchの概要、および、この長期的情報に基づくタブーサー チ手法に対して本稿が提案する拡張方式の提案内容についての記載を行う。

5.2.3.1 局所探索法と短期的情報に基づくタブーサーチのアルゴリズム

局所探索法と短期的情報に基づくタブーサーチのアルゴリズムの概要を記述する。特に、

目的関数が二次形式を持つ問題の場合、その近傍の考え方を合わせて紹介する。

局所探索法の一般的アルゴリズムは以下のとおりである。

◯局所探索法の枞組み

① 初期解の設定。現在の解←初期解

② 改善解が存在しなくなるまで、以下を繰り返す。

・現在の解の近傍の設定

・現在の解における近傍探索

・改善解が近傍に存在すれば、move : 現在の解←改善解

上記局所探索法は、下記の短期的情報としてのタブーサーチの枞組みの中で実行される。

以下に、短期的情報としてのタブーサーチの枞組みを記述する。

① 初期解の設定（現在の解←初期解）。移動情報（タブーリスト）の初期化

② 指定された反復回数分、以下を繰り返す。

・現在の解の近傍の設定

・現在の解における近傍探索(ただし、タブー期間中の移動情報に記録された箇所へ の移動は対象外とする)

・改善解が近傍に存在すれば、move : 現在の解←改善解

改善解が近傍に存在しなければ、move : 現在の解←探索近傍で最良の近傍解

・すべての移動情報の潜伏可能期間から１を減じる

現在の解に対応する移動情報に潜伏可能期間の初期値(所与)を設定

注1）改善解とは、目的関数の最良値とその解が保存されているものとして、その最 良値をさらに改良する解を意味する。目的関数の最良値とその解は、改善解への 移動がなされる度に更新されるものとする。

注2）移動(move)の実現方法には即時移動と最良移動の２種類がある。前者はひとつの

候補移動が決定する度にすぐ移動すること、後者は近傍から最良の移動を決定後 に一回移動すること、を意味する。

注3）タブーサーチでは、タブー期間中の移動禁止則を緩める こと(Aspiration criteria)も考慮されており、その場合、タブー期間中であっても、その移動が改善 解となれば移動が許可される。一般的には、“既存暫定解の更新“などで活用 されることが多い。

ここで、目的関数の解

 x

1

, x

2

,  , x

m

  x

i

   0 , 1 

に対する近傍の概念やその種類について 簡単に述べておく。近傍とは、現在の解周辺のことであり、現在の解を尐し変形した解の 集合と解釈できる。今回の目的関数の解

 x

1

, x

2

,  , x

m

  x

i

   0 , 1 

^{に対する近傍とは、各}

項の 0 または１の値を変化させたものであり、よく使用される主な一般的近傍として、以 下のものが挙げられる。

①反転近傍(flip neighborhood)

ある0－1変数の値を反転させた解の集合。

一個の0－1変数のみの反転近傍を１反転近傍(1-flip neighborhood)、

二個の0－1変数の同時反転近傍を２反転近傍(2-flip neighborhood)という。

②スワップ近傍(swap neighborhood)

割当て問題で、割当て先と割当て元の値を交換した解の集合。

③シフト近傍(shift neighborhood)

割当て問題で、割当て先または割当て元の値を変化させた解の集合。

局所探索法の実行時間は、採用する近傍のサイズに比例する。近傍の最大サイズは、解を 変形させる次元によって決まり、１反転近傍では一次元変形であるので近傍の最大サイズ は変数の個数であるn、２反転近傍では二次元対称変形であるのでn(n–1)

/

2となる。スワ ップ近傍とシフト近傍は二次元変形である。バイナリ二次計画問題では、１反転近傍が多 用されているが、２反転近傍の採用も提案されている。

5.2.3.2 Diversification-driven tabu searchの概要と拡張提案

ここでは、無制約バイナリ二次計画問題に対する長期的情報に基づくタブーサーチ手法で あるDiversification-driven tabu searchの概要について記述する。これは、文献[46]で提案 された長期的情報に基づくタブーサーチ手法である。なお、対象とする無制約バイナリ二 次計画問題は、最大化問題としての無制約バイナリ二次計画問題: maxiMjMqijxixj

  0 , 1 ( j M ))

( x

j

 

を取り扱い、行列

( q

_ij

)

は整数値の対称行列とする。

無制約バイナリ二次計画問題の解法研究成果の中で、グローバーらによる最新の比較検証 結果に基づいて提案された短期的および長期的情報に基づくタブーサーチが、近似解法で ありながら、文献[46]で示された結果からわかる通り、厳密解に近い解が得られることが分

かる。そのため、本稿の最終目的達成に有望な解法であると判断して、まずこの解法の概 要をここで紹介する。

なお、、短期的情報に基づくタブーサーチについては、既に述べた通りであるが、文献[46]

で提案された長期的情報に基づくタブーサーチ手法Diversification-driven tabu searchとは、

下記のように与えられる。

A)初期解を変えて、短期的情報に基づくタブーサーチを複数回実行し、その中から最 良の解を選ぶ。

B) 1 回目の初期解はランダムに発生させ、２回目以降の初期解は、前回までに得られ て保持されている解集合EliteSolからランダムに一個を選ぶ。長期的情報に基づく タブーサーチは、この解を変形して作成する。変形の方法は、変数に0、1が割当て られた頻度情報に基づいて解構造の整合性を保つようにし、また変数が反転された 頻度情報にもとづいて、反転数が尐ない変数に反転の機会を与える(Diversification) ようにする。具体的には、各変数の頻度情報は下記スコア関数により評価され、こ のスコア関数値に基づき、その頻度の高い変数を高い確率的で値を反転（flip）させ て初期解を合成する。

𝑆𝑐𝑜𝑟𝑒 𝑥𝑖 =𝐸𝑙𝑖𝑡𝑒𝐹𝑟𝑒𝑞(𝑖) 𝑟 − 𝐸𝑙𝑖𝑡𝑒𝐹𝑟𝑒𝑞(𝑖)

𝑟² + 𝛽 1 −𝐹𝑙𝑖𝑝𝐹𝑟𝑒𝑞(𝑖)

max⁡_𝐹𝑟𝑒𝑞 ( 5-1 )

ただし、EliteSol は近傍探索で得られた最良解（エリート解と呼ぶ）を保持する集

合とし、その上限数をRとした場合、保持されたエリート解の中で、上位R個が保 持され、最良解が得られるたびに更新されていくものとする。このとき、(5-1)で使 われている記号は以下の意味を持つ。

r ： EliteSolに存在する解の数

EliteFreq(i) ： EliteSolに存在する解のうちxi1のである解の個数 FlipFreq(i) ：

x

iが反転された回数

max_Freq ： FlipFreq(i)の最大値 β ： 定数(0.3と設定)

ここで、(5-1)のスコア関数を評価することで、選択された最良解から反転される項 を確率的に選定するが、右辺の第1項により、エリート解に含まれる各項の回数が0 やrに近い項は敬遠され、r/2に近い項の選定が促され、また、第2項により、反転 選択の低い項が優先的に選定される。

な お 、 上 記 ア ル ゴ リ ズ ム が 複 数 回 の 繰 返 し さ れ 、 探 索 が 行 わ れ る が 、ランダムな初期 解による複数回試行型タブーサーチは、Multi-start tabu searchと呼称されている。

以上に述べたDiversification-driven tabu searchのアルゴリズム概要をもととして、本稿 で拡張を加えた解法アルゴリズムの枞組みを下記に示す。拡張部分は、局所探索の部分に １反転近傍探索だけでなく2反転近傍探索も導入したことである。

ドキュメント内 保全コスト平準化に向けた (ページ 113-119)