第 5 章 二次式を活用した設備更新コスト平準化問題とその解法
5.2 設備更新コスト平準化問題の解法
5.2.4 タブーサーチによる制約付きバイナリ二次最適化問題の近似解法
これまでは、制約なしバイナリ二次計画問題の近似解法について記述を行ったが、本稿で は、Diversification-driven tabu search方式を制約付きバイナリ二次最適化問題への近似解 法へ適用することを提案し、その方式について記述を行う。
なお、設備更新コスト平準化問題の定式化にあたり、制約条件の尐ない基本形をバイナリ 二次計画問題として定式化を行ったが、ここで述べる手法については、二次制約式を含ん だ場合でも、同様の手順で適用を行うことができるため、設備更新コスト平準化問題の制 約条件の拡張に対応した手法として提案できることを付記する。
5.2.4.1 定式化
前節で導入した無制約バイナリ二次計画問題のタブーサーチによる解法を拡張して、
制約付きバイナリ二次最適化問題へ適用する。拡張の方法として、２つの方式がある。
① ペナルティ関数を活用して、無制約問題に変形し、拡張問題を解く方式である。
②最適化問題の解法の中で、解の探索を行い、探索された解に対し、実行可能解、
すなわち、制約条件を満たす解であるかを確認する必要がある。そのため、制約 条件の追加に際しては、この確認手順を増やすことで対応可能である。
本稿では、シンプルなペナルティ法を採用する。ここでいうペナルティ法とは、所与 のペナルティで不等式制約を緩和し、無制約最適化問題へ変換する手法を示している。
この無制約最適化問題を、前記の無制約バイナリ二次計画問題向けのタブーサーチで解 く。
ここで、線形制約を考慮した制約付きバイナリ二次計画問題（CBQ1）、および
x
j2=x
jを 利用して目的関数の一次項をなくす変形を行った問題（CBQ2）を、以下に示す。（CBQ1） min (1/2)
Σ
i∈NΣ
j∈Nq
i jxixj +Σ
j∈Nc
jx
js.t.
Σ
j∈Na
i jx
j ≤ bi (i∈M)x
j∈{0,1} (j∈N)（CBQ2） min
Σ
i∈NΣ
j∈Nq
i jxixjs.t.
Σ
j∈Na
i jx
j ≤ bi (i∈M)x
j∈{0,1} (j∈N)制約条件が付与された最適化問題に対し、ペナルティ関数を活用して、制約なしの最適化問 題に変形することができる
このペナルティ関数に関する理論を活用して、（CBQ2）に付与された制約条件に対して、ペナ ルティ関数を加えた問題（CBQp）は、以下のように定式化を行うことができる。
（CBQp） min
Σ
i∈NΣ
j∈Nq
i jxixj +Σ
i∈Mρimax(Σ
j∈Na
i jx
j –bi ,0) s.t.x
j∈{0,1} (j∈N)ここで、ρi>0(i∈M)は各不等号制約のペナルティ係数（所与）である。
問題（CBQp）を無制約バイナリ二次計画問題用のタブーサーチで解くためには、以下の変更 が必要となる。
① 評価関数の変更
局所探索の実行時に、解の評価として、（CBQp）のペナルティ付き評価関数を使用す る。この評価関数の最良値と解は、タブーサーチの枞組み内で保持され、解の良し 悪しの判定に利用される。
② 実行可能解の取得
局所探索の実行時に、解の評価と同時に、現在の解が制約式をすべて満足するかの 判定を行い、満足していれば実行可能解として、その最良値を保持する情報と比較・
更新される。このように、実行可能解の最良値と解も、タブーサーチの枞組み内で 保持され、最終的に得られた実行可能解の最良値と解が求めるものである。
ペナルティ関数の活用については、制約条件が1次不等式でなくとも、2次不等式等へも 一般化して利用することができる。さらに、この場合でも、ペナルティ関数を活用する上 記変更についても、タブーサーチの枞組みを変更する必要はない。
5.2.4.2 提案解法の計算複雑度と効率化
ペナルティ付き評価関数は目的関数項とペナルティ項で構成されるので、その計算量は、
前述した無制約目的関数の計算量にペナルティ項の計算量が加算される。後者は、容易に
O
(mn) と算定できる。この計算量を削減するために、前述の差分計算法を適用する。この方法では、それぞれの不等式制約値を𝐺𝑖 𝑥 = 𝑗 ∈𝑁𝑎𝑖𝑗𝑥𝑗 − 𝑏𝑖 (𝑖 ∈ 𝑀)と置いて、ある変数 xk
の反転∇kによる増分を∇kGi(x)=sign(∇k)ai k(i∈M)と算定する。したがって、前回の不等式 制約値ベクトルを保存しておき、この差分計算を採用することにより、１反転近傍による ペナルティ項の計算は
O
(m)で行えることになる。ただし、実際に１反転を実行した場合の後処理として、さらに不等式制約値ベクトルの更 新：Gi(x)←Gi(x)+sign(∇k)ai k(i∈M)が
O
(m)で必要である。前述5.2.3.3 の結果を合わせ てまとめると、１反転近傍による評価関数の算定は差分計算法によりO
(n+m)で実行され る。さらに、2反転近傍についても、１反転近傍を逐次２回実施すればよいので、同じ計算 複雑度で実行できる。この結果より、制約付きバイナリ二次計画問題のタブーサーチによる解法の計算複雑度は、
n‟=n+mとして下記のようになる。
・最良移動による１反転近傍探索：
T
1=O
(αn‟ ) ここで、α：１反転近傍探索内の繰返し回数・最良移動による２反転近傍探索：
T
2=O
(βn‟ )+O
(nlogn)ここで、β：２反転近傍探索における評価変数数、第２項は整列の計算複雑度
・短期的情報に基づくタブーサーチ：
T
3=κ
1(T
1+T
2) ここで、κ
1：局所探索の最大繰返し回数・長期的情報に基づくタブーサーチ：
T
4=κ
2T
3ここで、
κ
2：短期的情報に基づくタブーサーチの試行回数 5.2.4.3 提案解法による数値実験長期的情報に基づくタブーサーチにより、制約付きバイナリ二次計画問題の近似解を求め る数値実験を行った。そのために、5.2.2 で実施した厳密解法の数値実験と同じ問題例に対 して近似解を求め、厳密解との比較を行った。ここで、タブーサーチの実行用に設定した
パラメタを下記に示す。
◯長期的情報に基づくタブーサーチの実行パラメタ
・エリート解の最大個数：5
・短期的情報に基づくタブーサーチの試行回数：
κ
2=10・短期的情報に基づくタブーサーチの終了条件
改善解が発見されなくなるまでの連続反復回数(cutoff rounds):10n
・２反転近傍探索における評価変数数：β= 0.1n
・不等号制約のペナルティ係数：ρi=100(i∈M)
・潜伏可能期間の初期値：TabuTenure=ttmin+ Random[1,ttmax] ここで、ttmin = max{n/20,3} forn < 100
= max{n/100,5} forn≧100 ttmax = n/10 forn≦100
= 10 forn >1000
= 5 otherwise
タブーサーチによる実行結果を表 5-3に示す。同表より、厳密解が得られる小規模問題例 では、タブーサーチによっても厳密解が得られる可能性が高いことがわかる。しかも、タ ブーサーチは厳密解法より100～1000倍程度速く、厳密解が得られる保証はないものの大 規模問題の近似解を安価に求める手法として、タブーサーチは有望な解法であろうと解釈 できる。
なお数値実験に使用したPCは、Dell Optiplex GX745(Celeron(R) D CPU 3.06GHz、物 理メモリ2.99GB)である。
問題 変数
数(n) BB実行
時間(s) TS実行
時間(s) 厳密解の
値 TSによるエリート解の値
No.1 No.2 No.3 No.4 No.5 P50 50 2.937 0.031 440.419 440.419 440.419 440.419 440.419 440.419 P60 60 13.031 0.047 382.487 382.487 382.487 382.487 382.487 394.974 P70 70 35.719 0.110 1817.746 1817.74 0
6 1817.74
6 1817.74
6 1886.47
4 1928.33 P80 80 8.625 0.079 134.452 134.452 134.452 134.452 134.452 134.452 4 P90 90 27.812 0.109 834.665 834.665 834.665 834.665 834.665 857.155 P100 100 192.672 0.140 629.3705 629.370 5
5 629.370
5 629.370
5 629.370
5 629.370 表 5-3 制約付きバイナリ二次計画問題の数値実験の結果 5
ペナルティ法を活用して、制約付き二次最適化問題を、制約なし問題に帰着させて解くと こができた。今回利用したペナルティ法は汎用的手法であり、設備更新コスト平準化問題 の定式化で、制約条件に二次制約式が入っても、その解法が適用可能である。ただし、制 約条件の追加に伴って、計算複雑度を算定し、効率的な制約条件への対応を行う必要があ る。二次制約における計算複雑度についても、本稿の説明の中で、目的関数が二次式であ った場合の１反転近傍探索と同様の効率化方式が利用可能であるため、計算複雑度のオー ダも、その部分が加わるレベルとなる。