組合せ最適化の近似解法
• 厳密解法
• 近似解法
• 発見的解法
近似解法
• 時間をかけて最適解を求めるのではなく、短時間でそれなり
に良い解を見つける、という解法
• 精度保障があるもの： 近似解法
（得られる解が、必ず、最適解の2倍以内、など）
• 精度保証がないもの： 発見的解法（メタ･ヒューリスティック）
（精度保証はないが、実験的に良い解が得られることがわ
かっているもの、あるいはそう思われるもの）
• 問題固有の性質を使うので、解法が細分化されている
（スケジューリング用、配送計画用、など）
組合せ最適化の近似解法
• 様々な手法がある
最もよく使われる方法：
1. 整数条件を線形緩和する
xi ∈ { 0,1 } 0 ≦ xi ≦ 1
（解集合が広くなるので、最適解は悪くはならない）
2. 得られた問題の最適解を見つける
（一般に小数解。整数解なら元問題の最適解）
3. 得られた最適解を、何かしらのルールで整数に丸める
（実行不能にならないように丸める）
巡回セールスマン問題の精度保証近似
• 巡回セールスマン問題は、前述の通り近似するのも難しい
• ただし、頂点間の距離に三角不等式が成り立つと、精度保
証のある近似アルゴリズムが作れる
• しかし、問題の構造を非常に強く利用するため、他の問題
に応用することは難しい
２近似アルゴリズム
• 最小全張木を求めましょう
最適解よりも重みが小さい
（サイクルから枝を1本取ると、全張木 ≧ 最小全張木）
• 全張木をなぞって、経路を作りましょう
（ 2×最適解）よりも重みが小さい
２近似アルゴリズム (2)
• 1度来た頂点に来たときは、短絡しましょう
（3角不等式が成り立てば）できた経路はより短くなる
（2×最小木）より同じか短くなる
（2×最適解）よりは短くなる
発見的解法
• 様々な手法がある。代表的なものだけ
貪欲算法
• 変数の値をひとつずつ、（決めた変数の部分について）
実行可能で目的関数が最も良くなるように決定していく
近傍探索
• 現在の解をちょっと変更して得られる解に移動し、
解空間を探索する
遺伝的アルゴリズム
• 解の集合に、それら解の特徴を引き継ぐような解をいく
つか追加し、全体の中から目的関数の悪いものを取り除
く、という作業を繰り返す
貪欲解法：最大重みクリーク
最大重みクリーク問題：与えられたグラフと頂点重みに対し
て、頂点重みの和が最大となるようなクリークを見つける
貪欲算法：
• 空集合から出発し、追加してクリークになるよう頂点の
中で重みが最大のものを追加する
• 追加できなくなったら終了
３
４
５
１
４
２
１
３
２
１
３
３
近傍探索
• 解をちょっと変更して得られる解に移動する
• 解 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)|の大きさが、
性能を左右する
局所探索（図解）
• 近傍の中のより良い解に移動していく方法
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 ） 回の入れ替えで局所最適解
に到達する
近傍の高速な評価
• 解の評価値を計算するには、１つ O(n) 時間かかる
すべての近傍の評価をするのに、 O(n3) 時間かかる
• しかし、実際には、x と x の近傍の対称差は 枝4本のみ
x の評価値を基にすれば、１つ定数時間で評価できる
局所探索 (2)
挿入近傍：
現在の経路から、ある都市を他の都市の次に挿入して得られ
る経路を近傍とする
• 全部で O（都市数2） 個
局所探索 (3)
• 局所最適解は、平均的に誤差 10-20% 、2-opt より多少悪い
ようである
• 局所探索をすると最悪の場合、局所最適解にたどり着くまで、
O（2都市数） 回の入れ替えをする可能性がある
• しかし、平均的にはO（ 都市数2 ） 回の入れ替えで局所最適
解に到達する
• 工夫すると、1つの近傍の評価を O（ 1 ） の時間で行える
局所探索：計算時間
• （シンプレックス法のように）最悪の場合、指数回の反復を繰
り返す可能性がある
• 実験的には、反復の回数はだいたい O(|N(x)|) 回程度
• １反復の計算時間は、通常 |N(x)| に大きく依存する
• |N(x)| が大きければ、それだけ解の精度は上がる
（へんな局所最適解につっかえなくなる）
しかし、計算時間は増大する
局所探索：２つの改善方針
• 各反復で、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) のどちらか１つは正になる必要がある
• 各 u について、 d(u,v)－d(u,x) が正になるような x について
のみ、2-opt のチェックを行えばよい
u
v
※ d(u,x) が小さいものから
順に d(u,v) と同じになるまで
調べればよい
探索範囲が劇的に小さくなる
y
x
発見的解法：セービング法
• 最初、ルートを空にする
• 頂点を１つずつ、最も移動距離が増えない位置に挿入
• 計算時間は 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を、温度がさめるのと同じように、反復数が増大
するにしたがい、指数関数の逆関数的に小さくしていく
指数解の反復を繰り返すと、
ほぼ確率１で最適解に収束
アニーリング法：特徴
• 近傍を見つけてさいころを振るだけなので、作るのが簡単
• 温度の制御も簡単
• 細い谷が続いているような構造（近傍の中に、改善解が少しし
かない、ということが続く状況）では、谷に沿って下っていくこ
とが困難なため、効率よく改善されない
タブサーチ
• 近傍の中で（自分以外の）一番良い解に移動
（悪い解にも移動する）
• 毎回、（もともといた解に戻らないように）近傍に移動禁止領
域を作る （タブーリスト）
• 移動禁止領域は、一定時間経過後、削除する
移動禁止領域の設定
• どのようにして移動禁止領域を設定するか
－ ある要素 e を解に挿入した
e を解から出さない
－ 解の要素 e を解に含まれない要素 f と交換した
e,f の関わる交換はしない
－ 解の i 番目に要素を挿入した
i 番目の要素は出さない
タブリスト：
e5, e9, e2, e7, e21, e25
タブサーチの例
• 最大クリーク問題に対する近傍探索を例にして解説する
• タブリストは、「クリークから抜いた頂点」で、リストにある頂点は追
加する頂点として選ばないことにする
• タブリストの頂点は、挿入されたあと５回目で消すことにする
局所的に、なめるように進んでいく
タブサーチの特徴
• タブーリストの効果で、局所最適解の周辺を集中的に探すこ
とになり、良い解のそばには良い解がある、という構造が極
めてよく成り立つのであれば、精度の高い解を見つけられる
• 近傍中で一番良い解を探すので、それに時間がかかる
• タブーリストの設計＆長さにより性能が激変するため、設計に
注意が必要
タブーリストにとどまる時間が短期であるもの、長期であるも
のを作って、安定させる
遺伝的アルゴリズム
• 生物の進化の過程をシミュレートしたような解法
生物は、交配・遺伝・突然変異・自然淘汰を繰り返して、ある
意味で最適なものに変化していく。そのようなプロセスを経
る解法を作る
遺伝的アルゴリズム (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 問題である
• ビンの数が少ないと、ナップサック問題を使って解ける
遺伝的アルゴリズムの例
• ナップサック問題で考える。交叉は２つ解の共通部分を含み、
和集合に含まれるような解
a b c d e f g h i j
重さ ５ ８ ７ ４ ６ ３ ７ ５ ８ ６
価値 ５ ６ ８ ６ ８ ５ ４ ４ ７ ７
解１： abcdh
解２： abefg
解３： bdei
解４： fghij
重29, 価29
重30, 価28
重28, 価27
重29, 価27
重さ制限： ３０
解１＋２： ab deg
解２＋３： be adf
解３＋４： i defj
解４＋１： h bic
良い部分は残り、悪い部分はなくなる
重30, 価29
重24, 価30
重27, 価33
重28, 価25
遺伝的アルゴリズムの特性
• 近傍探索ではうまく解けない問題が解ける事がある
（逆もある）
• 実行不能解から、近傍探索により実行可能解へ
• 局所性の高い問題には不向き（クリークなど）
• 作りようによってはすごくいいものができるが、出来が悪くなる
こともある
• いい解法を作ろうとすると、いろいろな工夫を加えなければなら
ない
• パラメータ、交叉を工夫する必要がある
• プログラミングが大変（局所探索などに比べると）
• こっている分、速度が遅い
工夫
突然変異
－ 解集合が変なところで停滞することがある（同じような悪い
解ばかりになる）。それを防ぐため、ときに突然変異を起こし、
親の遺伝情報の一部を受け継がないような子供を作る
交叉の工夫
－ １つの親の組から作る子供の数、子供の作り方を工夫する
グループ化
－ 生物が群を作り、群の中で交配して、群（地域）により独自
に進化するように、解集合をいくつかのグループに分割し、そ
れぞれのグループ内の交配を多くするようにする
局所探索
－ 交叉してできた解を局所探索で改良し、それを子供とする
まとめ
• 線形計画法による近似（独立集合）
• 発見的解法（メタ･ヒューリスティック）
• 局所探索法（貪欲解法）
• 巡回セールスマン問題の近傍探索： 挿入、2-opt
• 近傍探索の高速化
目的関数の評価法、可能性のない候補の除外
• 近傍探索（タブサーチ・アニーリング）
• 遺伝的アルゴリズム
© Copyright 2024 ExpyDoc
