Document

組合せ最適化の近似解法
• 厳密解法
• 近似解法
• 発見的解法
近似解法
• 時間をかけて最適解を求めるのではなく、短時間でそれなり
に良い解を見つける、という解法
• 精度保障があるもの: 近似解法
(得られる解が、必ず、最適解の2倍以内、など)
• 精度保証がないもの: 発見的解法(メタ・ヒューリスティック)
(精度保証はないが、実験的に良い解が得られることがわ
かっているもの、あるいはそう思われるもの)
• 問題固有の性質を使うので、解法が細分化されている
(スケジューリング用、配送計画用、など)
組合せ最適化の近似解法
• 様々な手法がある
最もよく使われる方法:
1. 整数条件を線形緩和する
xi ∈ { 0,1 }  0 ≦ xi ≦ 1
(解集合が広くなるので、最適解は悪くはならない)
2. 得られた問題の最適解を見つける
(一般に小数解。整数解なら元問題の最適解)
3. 得られた最適解を、何かしらのルールで整数に丸める
(実行不能にならないように丸める)
巡回セールスマン問題の精度保証近似
• 巡回セールスマン問題は、前述の通り近似するのも難しい
• ただし、頂点間の距離に三角不等式が成り立つと、精度保
証のある近似アルゴリズムが作れる
• しかし、問題の構造を非常に強く利用するため、他の問題
に応用することは難しい
2近似アルゴリズム
• 最小全張木を求めましょう
 最適解よりも重みが小さい
(サイクルから枝を1本取ると、全張木 ≧ 最小全張木)
• 全張木をなぞって、経路を作りましょう
 ( 2×最適解)よりも重みが小さい
2近似アルゴリズム (2)
• 1度来た頂点に来たときは、短絡しましょう
 (3角不等式が成り立てば)できた経路はより短くなる
 (2×最小木)より同じか短くなる
 (2×最適解)よりは短くなる
発見的解法
• 様々な手法がある。代表的なものだけ
貪欲算法
• 変数の値をひとつずつ、(決めた変数の部分について)
実行可能で目的関数が最も良くなるように決定していく
近傍探索
• 現在の解をちょっと変更して得られる解に移動し、
解空間を探索する
遺伝的アルゴリズム
• 解の集合に、それら解の特徴を引き継ぐような解をいく
つか追加し、全体の中から目的関数の悪いものを取り除
く、という作業を繰り返す
貪欲解法:最大重みクリーク
最大重みクリーク問題:与えられたグラフと頂点重みに対し
て、頂点重みの和が最大となるようなクリークを見つける
貪欲算法:
• 空集合から出発し、追加してクリークになるよう頂点の
中で重みが最大のものを追加する
• 追加できなくなったら終了
3
4
5
1
4
2
1
3
2
1
3
3
近傍探索
• 解をちょっと変更して得られる解に移動する
• 解 x ( n 次元01ベクトルで表現)に対して、 x にある操作をして得
られる解、及びその集合を近傍と呼び、N(x) と表記する
例1: xi を選び、 xi が 0 なら1、1なら0と、反転させる
例2: xi と xj を選び、それらの値を入れ替える
例3: xi := xi+1, xi+1 := xi+2, …, xi+j:= xi と、巡回させる
それぞれ、 |N(x)| = O(n), O(n2), O(n2)
• どれくらい解構造と良く関係しているか、および |N(x)|の大きさが、
性能を左右する
局所探索(図解)
• 近傍の中のより良い解に移動していく方法
1. 初期解 x を見つける
2. N(x) の中に、x よりも目的関数値が良い解があれば、
x をその解に変更する
3. N(x) が x よりも良い解を含まなくなるまで繰り返す
最急降下法:
1. 探索方向を決める
2. どれくらい進むか決める
局所的な情報のみを利用する
点は同じだが、どこでも行け
るので、近傍の概念がない
局所最適解
• 最終的に得られる
「 N(x) が x よりも良い解を含まない」
ような x を局所最適解という
大域的最適解  局所最適解
局所最適解  × 大域的最適解
• 局所最適解は、大域的最適解(本当の最適解)より、
一般的に悪いが、平均的にはそれほど悪くない
(実験的には、誤差20-30%くらい?)
巡回セールスマン問題の局所探索
2-opt近傍:
現在の経路から、2つの枝の行き先と出発点を入れ替えて得
られる経路を近傍とする
• 全部で O(都市数2) 個
2-optの性質
• 局所最適解は、平均的に誤差 10-20%
• 局所探索をすると最悪の場合、局所最適解にたどり着くまで、
O(2都市数) 回の入れ替えをする可能性がある
• しかし、平均的にはO( 都市数2 ) 回の入れ替えで局所最適解
に到達する
近傍の高速な評価
• 解の評価値を計算するには、1つ O(n) 時間かかる
 すべての近傍の評価をするのに、 O(n3) 時間かかる
• しかし、実際には、x と x の近傍の対称差は 枝4本のみ
 x の評価値を基にすれば、1つ定数時間で評価できる
局所探索 (2)
挿入近傍:
現在の経路から、ある都市を他の都市の次に挿入して得られ
る経路を近傍とする
• 全部で O(都市数2) 個
局所探索 (3)
• 局所最適解は、平均的に誤差 10-20% 、2-opt より多少悪い
ようである
• 局所探索をすると最悪の場合、局所最適解にたどり着くまで、
O(2都市数) 回の入れ替えをする可能性がある
• しかし、平均的にはO( 都市数2 ) 回の入れ替えで局所最適
解に到達する
• 工夫すると、1つの近傍の評価を O( 1 ) の時間で行える
局所探索:計算時間
• (シンプレックス法のように)最悪の場合、指数回の反復を繰
り返す可能性がある
• 実験的には、反復の回数はだいたい O(|N(x)|) 回程度
• 1反復の計算時間は、通常 |N(x)| に大きく依存する
• |N(x)| が大きければ、それだけ解の精度は上がる
(へんな局所最適解につっかえなくなる)
しかし、計算時間は増大する
局所探索:2つの改善方針
• 各反復で、N(x) の解をひとつずつチェックする場合
1. (best 改善)最も目的関数値が良くなるものを見つける
2. (first 改善) 目的関数が良くなる解がみつかったら、その時
点で移動する
• 一般に、first 改善のほうが速い。
性能はあまり変わらない
- Best改善の計算時間:
O(|N(x)|2) より小さいくらい
- first改善の計算時間:
O(|N(x)|) より大きいくらい
望みがない近傍の探索を省略
• 2-optで、枝 (u,v) と (x,y) を入れ替えた場合、距離の変化は
d(u,v) + d(x,y) - ( d(u,x) + d(v,y) ) だけ変化する
 解が改善されるためには、 d(u,v)-d(u,x) か d(x,y)-
d(v,y) のどちらか1つは正になる必要がある
• 各 u について、 d(u,v)-d(u,x) が正になるような x について
のみ、2-opt のチェックを行えばよい
u
v
※ d(u,x) が小さいものから
順に d(u,v) と同じになるまで
調べればよい
探索範囲が劇的に小さくなる
y
x
発見的解法:セービング法
• 最初、ルートを空にする
• 頂点を1つずつ、最も移動距離が増えない位置に挿入
• 計算時間は O(都市数2)
平均的に、誤差10-20%くらいに収まる
Iterated(反復)局所探索
• 局所探索は、局所最適解で止まってしまう
 局所最適解に来たら、解を(少々大きく)変更して、脱出する
そして、局所探索を行い、繰り返す
(良い解のそばには良い解があるだろう、という推測より)
多スタート局所探索
• 局所最適解は、大域的最適化(本当の最適解)より、一般的に、
悪いが、平均的にはそれほど悪くない(誤差20-30%くらい?)
• 局所最適解は(実験的には)短時間で見付かる
• 「下手な鉄砲数打ちゃ当たる」で、局所最適解を沢山見つけよう、
という方法
1. (ランダムに)初期解を作り、局所探索をする、という操作を沢山
繰り返す。
2. 得られた局所最適解の中から、一番良いものを選ぶ
• 1000回くらい(たとえば)繰り返せば、それなり良い解(誤差10%程
度)が短時間で見付かる
ガイデッド局所探索
• 近傍探索系のアルゴリズムは、一般的に、局所的な変更を繰り返
すことで良い解を見つける
 ときに、無視される部分が出てくる
 無視された部分が改良されないため、
良い精度が出ないことがある
• 「無視される部分」を、重み(重要度)を増すことで「無視されない
ように」すると、精度が上がることがある
1. (重みを基準にして)近傍へ移動する
2. 悪い状態で放置されている部分の重みを少し増す
3. 繰り返す
ガイデッド局所探索 (2)
• わかりにくいので、最大充足問題を例にして解説する
x1,…,xn : 論理変数 (真か偽、 0 か1 のみを値としてとる)
C1,…,Cm : クローズ (変数&変数の否定を ∪で繋げたもの)
最大充足問題:
C1,…,Cm のうち最も多くのものを真とするような変数への真偽値の
割り当てを求めよ
• 「ある xi の値を反転(真偽)する」という操作を元に、近傍探索
ができる
• 解が大きく動かないと、いつまでも真にならないクローズが出る
ガイデッド局所探索 (3)
• クローズに重み w を与え、最大重み充足問題を考える
 通常の最大充足問題は w を 1 とした特殊ケース
• 無視されているクローズ(いつまでも真にならないクローズ)がで
ないよう、各反復で偽になっているクローズの重みを増す
(真になっているものは減じる)
• 「なかなか充足できないクローズを充足しよう」という目的が強くな
るため、満遍なく解空間を探索できるようになる
最大充足可能性問題
例題)わかりにくいので、最大充足可能性問題を例にして解説する
(¬x1 ∨ ¬x2 )
(x1 ∨ ¬x3 ∨ ¬x4 )
(x1 ∨ ¬x3 ∨ ¬x5 )
(x1 ∨ ¬x4 ∨ ¬x5 )
(x2 ∨ ¬x3 ∨ ¬x4 )
(x2 ∨ ¬x3 ∨ ¬x5 )
(x2 ∨ ¬x4 ∨ ¬x5 )
(x3 ∨ x4 ∨ x5 )
(x3 ∨ x5 ∨ ¬x6 )
( ¬ x3 ∨ x4 ∨ ¬x6 )
• 全ての変数に真を割当てたものは、局所最適解になる
(一番上のクローズだけ満たされない)
• 近傍探索・局所探索をするうちに、1番上のクローズを真にするもの、
つまり、 x1, x2 を偽にする変更の重みが増す
良質部分の抽出
• 乱拓的な要素を入れた局所探索は毎回異なる解を出す
• が、似たような解が多く出てくる
また、どの解にも使われないもの、が出てくる
• 「どの解にも使われないものは、最適解でも使われないだろう」
という観察から、そのような部分は捨ててしまう、という戦略が
考えられる
• 問題をスリム化できるので、
厳密解法、あるいはじっくり解く
タイプの発見的解法が使える
アニーリング法
• 近傍の解へ移動する際に、現在の解よりも良くないものにも一定
の確率で移動する方法
1. 初期解 x を見つける
2. N(x) の中から適当に1つ選ぶ
3. その解が、x よりも目的関数値が良いなら、無条件に移動
悪い場合は、ある確率 T で移動
4. 繰り返して、適当にとめる
アニーリング法 (2)
• 化学反応の状態遷移の仕組みが発想のおおもと
(エネルギーの高い状態(不安定な状態)から低い、安定した状態
へは無条件で動く。不安定な状態へは(温度に依存する)確率
によって動く)
•化学反応は、高い温度から低い温度へゆっくりと冷ますと、自然
にあるべき状態に(だいたい)落ち着く
(焼きなましのようなもの)
確率 Tを、温度がさめるのと同じように、反復数が増大
するにしたがい、指数関数の逆関数的に小さくしていく
 指数解の反復を繰り返すと、
ほぼ確率1で最適解に収束
アニーリング法:特徴
• 近傍を見つけてさいころを振るだけなので、作るのが簡単
• 温度の制御も簡単
• 細い谷が続いているような構造(近傍の中に、改善解が少しし
かない、ということが続く状況)では、谷に沿って下っていくこ
とが困難なため、効率よく改善されない
タブサーチ
• 近傍の中で(自分以外の)一番良い解に移動
(悪い解にも移動する)
• 毎回、(もともといた解に戻らないように)近傍に移動禁止領
域を作る (タブーリスト)
• 移動禁止領域は、一定時間経過後、削除する
移動禁止領域の設定
• どのようにして移動禁止領域を設定するか
- ある要素 e を解に挿入した
 e を解から出さない
- 解の要素 e を解に含まれない要素 f と交換した
 e,f の関わる交換はしない
- 解の i 番目に要素を挿入した
 i 番目の要素は出さない
タブリスト:
e5, e9, e2, e7, e21, e25
タブサーチの例
• 最大クリーク問題に対する近傍探索を例にして解説する
• タブリストは、「クリークから抜いた頂点」で、リストにある頂点は追
加する頂点として選ばないことにする
• タブリストの頂点は、挿入されたあと5回目で消すことにする
局所的に、なめるように進んでいく
タブサーチの特徴
• タブーリストの効果で、局所最適解の周辺を集中的に探すこ
とになり、良い解のそばには良い解がある、という構造が極
めてよく成り立つのであれば、精度の高い解を見つけられる
• 近傍中で一番良い解を探すので、それに時間がかかる
• タブーリストの設計&長さにより性能が激変するため、設計に
注意が必要
 タブーリストにとどまる時間が短期であるもの、長期であるも
のを作って、安定させる
遺伝的アルゴリズム
• 生物の進化の過程をシミュレートしたような解法
生物は、交配・遺伝・突然変異・自然淘汰を繰り返して、ある
意味で最適なものに変化していく。そのようなプロセスを経
る解法を作る
遺伝的アルゴリズム (2)
• いくつかの解の集合を保持
• 毎回、これらの親の特徴を持つ解(子供)を作り(交叉)、集
合に追加する
• 目的関数が悪いものを取り除き、繰り返す
• 適当に止める
交叉(交配)
• 現在の解の特徴を受け継ぐ解(子供)を生成
• 解をいくつか(普通は2個)選ぶ
• それらの共通部分を受け継がせ、共通しないところは適当
にアレンジする
101101000100110111
101101011100100000
1957320648
0643195782
1011010**1001*0***
1957 と 064 を含む
101101001100110010
8064219573
交叉の工夫
• (問題によっては)交叉による解が実行可能になるとは限らない
• 実行可能解を得るため、(共通しない部分)の設定の仕方を工
夫する、あるいは、共通部分も変更する
- 実行可能領域の凸性の利用
- 実行不能解から、近傍探索により実行可能解へ
- 解の、実行可能性をたもつ分解を利用
101101000100110111
101101011100100000
1957320648
0643195782
1011010**1001*0***
1957 と 064 を含む
101101001100110010
8064219573
ナップサック問題
最大積載量のあるナップサックに荷物を詰める問題
• 荷物はいくつかある
• 荷物はそれぞれ重さが違う
• 荷物はそれぞれ価値が違う
荷物の価値の合計が最大になる詰め込み方を求めよ
ナップサック問題 (2)
• NP-complete 問題である
• 動的計画法で、比較的簡単に解ける
• 普通の問題では数理的に不要である変数を消すと問題がと
ても小さくなる
• 近似解法もある
ビンパッキング問題
• いくつかのビンに、物を詰め込む
• 物はそれぞれ大きさがある(形は気にしない)
• ビンの容積が決まっていて、詰め込む物の大きさの合計
は、容積以下でなければいけない
• どういう詰め込み方をすると、ビンの数が最小になるだろう
か
ビンパッキング問題 (2)
• NP-complete 問題である
• ビンの数が少ないと、ナップサック問題を使って解ける
遺伝的アルゴリズムの例
• ナップサック問題で考える。交叉は2つ解の共通部分を含み、
和集合に含まれるような解
a b c d e f g h i j
重さ 5 8 7 4 6 3 7 5 8 6
価値 5 6 8 6 8 5 4 4 7 7
解1: abcdh
解2: abefg
解3: bdei
解4: fghij
重29, 価29
重30, 価28
重28, 価27
重29, 価27
重さ制限: 30
解1+2: ab deg
解2+3: be adf
解3+4: i defj
解4+1: h bic
良い部分は残り、悪い部分はなくなる
重30, 価29
重24, 価30
重27, 価33
重28, 価25
遺伝的アルゴリズムの特性
• 近傍探索ではうまく解けない問題が解ける事がある
(逆もある)
• 実行不能解から、近傍探索により実行可能解へ
• 局所性の高い問題には不向き(クリークなど)
• 作りようによってはすごくいいものができるが、出来が悪くなる
こともある
• いい解法を作ろうとすると、いろいろな工夫を加えなければなら
ない
• パラメータ、交叉を工夫する必要がある
• プログラミングが大変(局所探索などに比べると)
• こっている分、速度が遅い
工夫
突然変異
- 解集合が変なところで停滞することがある(同じような悪い
解ばかりになる)。それを防ぐため、ときに突然変異を起こし、
親の遺伝情報の一部を受け継がないような子供を作る
交叉の工夫
- 1つの親の組から作る子供の数、子供の作り方を工夫する
グループ化
- 生物が群を作り、群の中で交配して、群(地域)により独自
に進化するように、解集合をいくつかのグループに分割し、そ
れぞれのグループ内の交配を多くするようにする
局所探索
- 交叉してできた解を局所探索で改良し、それを子供とする
まとめ
• 線形計画法による近似(独立集合)
• 発見的解法(メタ・ヒューリスティック)
• 局所探索法(貪欲解法)
• 巡回セールスマン問題の近傍探索: 挿入、2-opt
• 近傍探索の高速化
目的関数の評価法、可能性のない候補の除外
• 近傍探索(タブサーチ・アニーリング)
• 遺伝的アルゴリズム