組合せ最適化の近似解法 ・ 厳密解法 ・ 近似解法 ・ 発見的解法.

Presentation on theme: "組合せ最適化の近似解法 ・ 厳密解法 ・ 近似解法 ・ 発見的解法."— Presentation transcript:

1 組合せ最適化の近似解法 ・ 厳密解法 ・ 近似解法 ・ 発見的解法

2 近似解法 ・ 時間をかけて最適解を求めるのではなく、短時間でそれなりに良い解を見つける、という解法 ・ 精度保障があるもの： 近似解法
・ 精度保障があるもの：　近似解法 　　（得られる解が、必ず、最適解の2倍以内、など） ・ 精度保証がないもの：　発見的解法（メタ･ヒューリスティック） 　　（精度保証はないが、実験的に良い解が得られることがわかっているもの、あるいはそう思われるもの） ・ 問題固有の性質を使うので、解法が細分化されている 　　　（スケジューリング用、配送計画用、など）

3 組合せ最適化の近似解法 ・ 様々な手法がある 最もよく使われる方法： 1. 整数条件を線形緩和する
1. 　整数条件を線形緩和する 　　xi ∈ { 0,1 } 　 　 0 ≦ xi ≦ 1 　（解集合が広くなるので、最適解は悪くはならない） 2.　得られた問題の最適解を見つける 　（一般に小数解。整数解なら元問題の最適解） 3. 　得られた最適解を、何かしらのルールで整数に丸める 　（実行不能にならないように丸める）

4 巡回セールスマン問題の精度保証近似 ・ 巡回セールスマン問題は、前述の通り近似するのも難しい
・ ただし、頂点間の距離に三角不等式が成り立つと、精度保証のある近似アルゴリズムが作れる ・ しかし、問題の構造を非常に強く利用するため、他の問題に応用することは難しい

5 ２近似アルゴリズム ・ 最小全張木を求めましょう  最適解よりも重みが小さい （サイクルから枝を1本取ると、全張木 ≧ 最小全張木）
　　  最適解よりも重みが小さい 　　（サイクルから枝を1本取ると、全張木 ≧ 最小全張木） ・ 全張木をなぞって、経路を作りましょう 　　  （ 2×最適解）よりも重みが小さい

6 ２近似アルゴリズム (2) ・ 1度来た頂点に来たときは、短絡しましょう  （3角不等式が成り立てば）できた経路はより短くなる
　  （3角不等式が成り立てば）できた経路はより短くなる 　  （2×最小木）より同じか短くなる 　  （2×最適解）よりは短くなる

7 発見的解法 ・ 様々な手法がある。代表的なものだけ 貪欲算法
　　・ 変数の値をひとつずつ、（決めた変数の部分について）実行可能で目的関数が最も良くなるように決定していく 近傍探索 　　・ 現在の解をちょっと変更して得られる解に移動し、 　　　　解空間を探索する 遺伝アルゴリズム 　　・ 解の集合に、それら解の特徴を引き継ぐような解をいくつか追加し、全体の中から目的関数の悪いものを取り除く、という作業を繰り返す

8 貪欲解法：最大重みクリーク 最大重みクリーク問題：与えられたグラフと頂点重みに対して、頂点重みの和が最大となるようなクリークを見つける
貪欲算法： 　　・ 空集合から出発し、追加してクリークになるよう頂点の中で重みが最大のものを追加する 　　・ 追加できなくなったら終了 ３ ４ ５ １ ４ ２ １ ３ ２ １ ３ ３

9 近傍探索 ・ 解をちょっと変更して得られる解に移動する
・ 解 x （ n 次元01ベクトルで表現）に対して、 x にある操作をして得られる解、及びその集合を近傍と呼び、N(x) と表記する 例１： xi を選び、 xi が 0 なら1、1なら0と、反転させる 例２： xi と xj を選び、それらの値を入れ替える 例３： xi := xi+1, xi+1 := xi+2, …, xi+j:= xi と、巡回させる それぞれ、 |N(x)| = O(n), O(n2), O(n2) ・ どれくらい解構造と良く関係しているか、および |N(x)|の大きさが、性能を左右する

10 局所探索（図解） ・ 近傍の中のより良い解に移動していく方法 1. 初期解 x を見つける
2. N(x) の中に、x よりも目的関数値が良い解があれば、 　　　 x をその解に変更する 3. N(x) が x よりも良い解を含まなくなるまで繰り返す 最急降下法： 1. 探索方向を決める 2. どれくらい進むか決める 局所的な情報のみを利用する 点は同じだが、どこでも行け るので、近傍の概念がない

11 局所探索：最大クリーク クリークの近傍： クリークに頂点を１つ加え、その頂点に隣接しないクリークの頂点をのぞいたもの 局所探索：
・ 近傍の中に、自分より良い解があったら、その解に移動する ・ 近傍の中に、自分より良い解が ないような解を見つけたら、 それを出力して終了

12 局所最適解 最終的に得られる ・ N(x) が x よりも良い解を含まない ような x を局所最適解という 大域的最適解  局所最適解
大域的最適解　　局所最適解 局所最適解　  ×　大域的最適解 局所最適解は、大域的最適解（本当の最適解）より、 　　一般的に悪いが、平均的にはそれほど悪くない （実験的には、誤差20-30%くらい？）

13 巡回セールスマン問題の局所探索 2-opt近傍： 現在の経路から、2つの枝の行き先と出発点を入れ替えて得られる経路を近傍とする
　現在の経路から、2つの枝の行き先と出発点を入れ替えて得られる経路を近傍とする ・ 全部で O（都市数2） 個

14 2-optの性質 ・ 局所最適解は、平均的に誤差 10-20%

15 近傍の高速な評価 ・ 解の評価値を計算するには、１つ O(n) 時間かかる  すべての近傍の評価をするのに、 O(n3) 時間かかる
・ しかし、実際には、x と x の近傍の対称差は 枝4本のみ 　  x の評価値を基にすれば、１つ定数時間で評価できる

16 局所探索 (2) 挿入近傍： 　現在の経路から、ある都市を他の都市の次に挿入して得られる経路を近傍とする ・ 全部で O（都市数2） 個

17 局所探索 (3) ・ 局所最適解は、平均的に誤差 10-20% 、2-opt より多少悪いようである

18 発見的解法：セービング法 ・ 最初、ルートを空にする ・ 頂点を１つずつ、最も移動距離が増えない位置に挿入 ・ 計算時間は O（都市数2）
平均的に、誤差10-20%くらいに収まる

19 望みがない近傍の探索を省略 順に d(u,v) と同じになるまで 調べればよい u v 探索範囲が劇的に小さくなる x y
・ 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) のどちらか１つは正になる必要がある ・ 各 u について、 d(u,v)－d(u,x) が正になるような x についてのみ、2-opt のチェックを行えばよい ※ d(u,x) が小さいものから 順に d(u,v) と同じになるまで 調べればよい u v 探索範囲が劇的に小さくなる x y

20 局所探索：計算時間 ・ （シンプレックス法のように）最悪の場合、指数回の反復を繰り返す可能性がある
・ 実験的には、反復の回数はだいたい O(|N(x)|) 回程度 ・ １反復の計算時間は、通常 |N(x)| に大きく依存する ・ |N(x)| が大きければ、それだけ解の精度は上がる （へんな局所最適解につっかえなくなる） 　しかし、計算時間は増大する

21 局所探索：２つの改善方針 ・ 各反復で、N(x) の解をひとつずつチェックする場合
1. （best 改善）最も目的関数値が良くなるものを見つける 2. （first 改善） 目的関数が良くなる解がみつかったら、その時点で移動する ・ 一般に、first 改善のほうが速い。 　　性能はあまり変わらない 　－ Best改善の計算時間： 　　 O(|N(x)|2) より小さいくらい 　－ first改善の計算時間： 　　 O(|N(x)|)　より大きいくらい

22 Iterated（反復）局所探索  局所最適解に来たら、解を（少々大きく）変更して、脱出する ・ 局所探索は、局所最適解で止まってしまう
　 　局所最適解に来たら、解を（少々大きく）変更して、脱出する 　　　　そして、局所探索を行い、繰り返す （良い解のそばには良い解があるだろう、という推測より）

23 多スタート局所探索 ・ 局所最適解は、大域的最適化（本当の最適解）より、一般的に、悪いが、平均的にはそれほど悪くない（誤差20-30%くらい？） ・ 局所最適解は（実験的には）短時間で見付かる ・ 「下手な鉄砲数打ちゃ当たる」で、局所最適解を沢山見つけよう、という方法 1. （ランダムに）初期解を作り、局所探索をする、という操作を沢山繰り返す。 2. 得られた局所最適解の中から、一番良いものを選ぶ ・ 1000回くらい（たとえば）繰り返せば、それなり良い解（誤差10%程度）が短時間で見付かる

24 ガイデッド局所探索 ・ 近傍探索系のアルゴリズムは、一般的に、局所的な変更を繰り返すことで良い解を見つける
　 ときに、無視される部分が出てくる 　 無視された部分が改良されないため、 　　　　　良い精度が出ないことがある ・ 「無視される部分」を、重み（重要度）を増すことで「無視されないように」すると、精度が上がることがある 1. （重みを基準にして）近傍へ移動する 2. 悪い状態で放置されている部分の重みを少し増す 3. 繰り返す

25 ガイデッド局所探索 (2) ・ わかりにくいので、最大充足問題を例にして解説する
　　x1,…,xn ： 論理変数 （真か偽、 0 か1 のみを値としてとる） 　　C1,…,Cm ： クローズ （変数＆変数の否定を ∪で繋げたもの） 最大充足問題： C1,…,Cm のうち最も多くのものを真とするような変数への真偽値の割り当てを求めよ ・ 「ある xi の値を反転（真偽）する」という操作を元に、近傍探索ができる ・ 解が大きく動かないと、いつまでも真にならないクローズが出る

26 ガイデッド局所探索 (3) ・ クローズに重み w を与え、最大重み充足問題を考える  通常の最大充足問題は w を 1 とした特殊ケース
・ 無視されているクローズ（いつまでも真にならないクローズ）がでないよう、各反復で偽になっているクローズの重みを増す 　（真になっているものは減じる） ・ 「なかなか充足できないクローズを充足しよう」という目的が強くなるため、満遍なく解空間を探索できるようになる

27 最大充足可能性問題 例題）わかりにくいので、最大充足可能性問題を例にして解説する （¬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 を偽にする変更の重みが増す

28 良質部分の抽出 ・ 乱拓的な要素を入れた局所探索は毎回異なる解を出す ・ が、似たような解が多く出てくる
　また、どの解にも使われないもの、が出てくる ・ 「どの解にも使われないものは、最適解でも使われないだろう」 　という観察から、そのような部分は捨ててしまう、という戦略が 　考えられる ・ 問題をスリム化できるので、 厳密解法、あるいはじっくり解く タイプの発見的解法が使える

29 アニーリング法 ・ 近傍の解へ移動する際に、現在の解よりも良くないものにも一定の確率で移動する方法 1. 初期解 x を見つける
2.　N(x) の中から適当に1つ選ぶ 3.　その解が、x よりも目的関数値が良いなら、無条件に移動 　　悪い場合は、ある確率 T で移動 4.　繰り返して、適当にとめる

30 確率 Tを、温度がさめるのと同じように、反復数が増大 するにしたがい、指数関数の逆関数的に小さくしていく
アニーリング法 (2) ・ 化学反応の状態遷移の仕組みが発想のおおもと （エネルギーの高い状態（不安定な状態）から低い、安定した状態へは無条件で動く。不安定な状態へは（温度に依存する）確率によって動く） ・化学反応は、高い温度から低い温度へゆっくりと冷ますと、自然にあるべき状態に（だいたい）落ち着く 　　（焼きなましのようなもの）  指数解の反復を繰り返すと、 　　　ほぼ確率１で最適解に収束 確率 Tを、温度がさめるのと同じように、反復数が増大 するにしたがい、指数関数の逆関数的に小さくしていく

31 アニーリング法：特徴 ・ 近傍を見つけてさいころを振るだけなので、作るのが簡単 ・ 温度の制御も簡単
・ 細い谷が続いているような構造（近傍の中に、改善解が少ししかない、ということが続く状況）では、谷に沿って下っていくことが困難なため、効率よく改善されない

32 タブサーチ ・ 近傍の中で（自分以外の）一番良い解に移動 （悪い解にも移動する）
　　　（悪い解にも移動する） ・ 毎回、（もともといた解に戻らないように）近傍に移動禁止領域を作る　　（タブーリスト） ・ 移動禁止領域は、一定時間経過後、削除する

33 移動禁止領域の設定 ・ どのようにして移動禁止領域を設定するか － ある要素 e を解に挿入した  e を解から出さない
　－　解の要素 e を解に含まれない要素 f と交換した 　　　　　　　　  e,f の関わる交換はしない 　－ 　解の i 番目に要素を挿入した 　　　　　　　　  i 番目の要素は出さない タブリスト： 　 e5, e9, e2, e7, e21, e25

34 タブサーチの例 ・ 最大クリーク問題に対する近傍探索を例にして解説する
・ タブリストは、「クリークから抜いた頂点」で、リストにある頂点は追加する頂点として選ばないことにする ・ タブリストの頂点は、挿入されたあと５回目で消すことにする 局所的に、なめるように進んでいく

35 タブサーチの特徴 ・ タブーリストの効果で、局所最適解の周辺を集中的に探すことになり、良い解のそばには良い解がある、という構造が極めてよく成り立つのであれば、精度の高い解を見つけられる ・ 近傍中で一番良い解を探すので、それに時間がかかる ・ タブーリストの設計＆長さにより性能が激変するため、設計に注意が必要  タブーリストにとどまる時間が短期であるもの、長期であるものを作って、安定させる

36 遺伝的アルゴリズム ・ 生物の進化の過程をシミュレートしたような解法
生物は、交配・遺伝・突然変異・自然淘汰を繰り返して、ある意味で最適なものに変化していく。そのようなプロセスを経る解法を作る

37 遺伝的アルゴリズム (2) ・ いくつかの解の集合を保持 ・ 毎回、これらの親の特徴を持つ解（子供）を作り（交叉）、集合に追加する
・ 目的関数が悪いものを取り除き、繰り返す ・ 適当に止める

38 交叉（交配） ・ 現在の解の特徴を受け継ぐ解（子供）を生成 ・ 解をいくつか（普通は2個）選ぶ
・ それらの共通部分を受け継がせ、共通しないところは適当にアレンジする **1001*0*** 1957 と 064 を含む

39 交叉の工夫 ・ （問題によっては）交叉による解が実行可能になるとは限らない
・ 実行可能解を得るため、（共通しない部分）の設定の仕方を工夫する、あるいは、共通部分も変更する 　－ 実行可能領域の凸性の利用 　－ 実行不能解から、近傍探索により実行可能解へ 　－ 解の、実行可能性をたもつ分解を利用 **1001*0*** 1957 と 064 を含む

40 ナップサック問題 最大積載量のあるナップサックに荷物を詰める問題 ・ 荷物はいくつかある ・ 荷物はそれぞれ重さが違う
・ 荷物はそれぞれ価値が違う 荷物の価値の合計が最大になる詰め込み方を求めよ

41 ナップサック問題 (2) ・ NP-complete 問題である ・ 動的計画法で、比較的簡単に解ける
・ 普通の問題では数理的に不要である変数を消すと問題がとても小さくなる ・ 近似解法もある

42 ビンパッキング問題 ・ いくつかのビンに、物を詰め込む ・ 物はそれぞれ大きさがある（形は気にしない）
・ ビンの容積が決まっていて、詰め込む物の大きさの合計は、容積以下でなければいけない ・ どういう詰め込み方をすると、ビンの数が最小になるだろうか

43 ビンパッキング問題 (2) ・ NP-complete 問題である ・ ビンの数が少ないと、ナップサック問題を使って解ける

44 遺伝的アルゴリズムの例 a b c d e f g h i j 重さ ５ ８ ７ ４ ６ ３ 価値
・ ナップサック問題で考える。交叉は２つ解の共通部分を含み、和集合に含まれるような解 a b c d e f g h i j 重さ ５ ８ ７ ４ ６ ３ 価値 重さ制限：　３０ 解１： abcdh 重29, 価29 解２： abefg 重30, 価28 解３： bdei 重28, 価27 解４： fghij 重29, 価27 解１＋２： ab deg 重30, 価29 解２＋３： be adf 重24, 価30 解３＋４： i defj 重27, 価33 解４＋１： h bic 重28, 価25 良い部分は残り、悪い部分はなくなる

45 遺伝的アルゴリズムの特性 ・ 近傍探索ではうまく解けない問題が解ける事がある （逆もある） ・ 実行不能解から、近傍探索により実行可能解へ
　　　　（逆もある） ・ 実行不能解から、近傍探索により実行可能解へ ・ 局所性の高い問題には不向き（クリークなど） ・ 作りようによってはすごくいいものができるが、出来が悪くなることもある ・ いい解法を作ろうとすると、いろいろな工夫を加えなければならない ・ パラメータ、交叉を工夫する必要がある ・ プログラミングが大変（局所探索などに比べると） ・ こっている分、速度が遅い

46 工夫 突然変異 －　解集合が変なところで停滞することがある（同じような悪い解ばかりになる）。それを防ぐため、ときに突然変異を起こし、親の遺伝情報の一部を受け継がないような子供を作る 交叉の工夫 － １つの親の組から作る子供の数、子供の作り方を工夫する グループ化 － 生物が群を作り、群の中で交配して、群（地域）により独自に進化するように、解集合をいくつかのグループに分割し、それぞれのグループ内の交配を多くするようにする 局所探索 － 交叉してできた解を局所探索で改良し、それを子供とする

47 まとめ ・ 線形計画法による近似（独立集合） ・ 発見的解法（メタ･ヒューリスティック） ・ 局所探索法（貪欲解法）
・ 巡回セールスマン問題の近傍探索： 挿入、2-opt ・ 近傍探索の高速化 　　目的関数の評価法、可能性のない候補の除外 ・ 近傍探索（タブサーチ・アニーリング） ・ 遺伝的アルゴリズム