【しっかり学ぶ数理最適化】4.7~4.8

2025年後期輪読会 数理最適化 メタヒューリスティック (4.7~4.8) 京都大学 工学部 情報学科 数理工学コース 稲葉 陽孔 1

アジェンダ ■ 概要(メタヒューリスティック) ■ 多スタート局所探索法 ■ 反復局所探索法 ■ 遺伝的アルゴリズム ■ アニーリング法 ■ タブー探索法 ■ 誘導局所探索法 ■ ラグランジュヒューリスティック 2

概要(メタヒューリスティック ) 多くの組み合わせ最適化問題に対して適用できる発見的解法の一般的な手法 手法の方向性として以下があり、それらを適切に組み合わせることで解を探索する 集中化：過去の探索で得られた良い解と似た構造を持つ解を集中的に探索する 多様化：過去の探索で得られた解とは異なる構造を持つ解を探索する 一般的に用いられる操作 ・過去の探索履歴を利用して新たな解を探索する ・探索した解を評価し，次の解の探索に必要な情報を取り出す 代表的なアイデア ・複数の初期解に対して、局所探索法を適用して複数の局所最適解を得る ・改悪解への移動を許して局所最適解から脱出する ・評価関数(x) を適応的に制御して局所最適解から脱出する． 3

多スタート局所探索法 複数の初期解から局所探索法を実行し，得られた局所最適解の中で最良のものを出力する手法 アルゴリズム 動作の様子(多スタート局所探索法) 初期解の定め方 ランダム多スタート局所探索法：初期解をランダムに設定する GRASP：ランダム性を加えた貪欲法によって初期解を設定 例(GRASP) 巡回セールスマン問題にて、以下の手順で巡回路の初期解を生成する 1.適当な都市を初期地点として、未訪問の都市の中で距離が近いほど行く確率が高くなるようにランダム に訪問 2.１のアルゴリズムをもとにすべての都市を訪問し、出発地点に戻る 4

反復局所探索法 過去の探索で得られた良い解にランダムな変形を加えたものを初期解として、 局所探索法を適用する手続きを繰り返す手法 アルゴリズム 動作の様子(反復局所探索法) ランダムな変形の際に、近傍の大きさが一定のままだと、暫定解を更新できないまま終わりうるので、近 傍の大きさを大きくしながらランダムな変形を加える→可変近傍探索法 アルゴリズ(※|Nk|は広義単調増加する) 動作の様子(可変近傍探索法) 5

遺伝的アルゴリズム 「複数の解から新しい解を生成し、その中から適切な解を複数選ぶ」を繰り返して探索を多様化させる手法 アルゴリズム 動作の様子(遺伝アルゴリズム) Step2(交叉)のための親の選び方 ルーレット選択：解の質(適応度)に比例した確率で選択 トーナメント選択：集団からランダムに選び、その中で適応度が最も高いものを選択 6

遺伝的アルゴリズム Step5(選択)のための手法 家族内選択：次世代の集団 P' に含まれるすべての解が類似するのを防ぐために、親子の中からは１つし か選べないようにする（子は親と性質が似るため） Step2(交叉)のための手法 交叉の手法のベース： k点交叉：高々k箇所しか0と１が入れ替わらないようなマスクに限定して交叉する手法 一様交叉：一切の制約なしにランダムに0,1を 振り分けてマスクを作る手法 k点交叉の弱み：新たに生成される子 x' の分布 に各要素 xj の順序に依存する偏りが生じる →順序交叉で解決 7

遺伝的アルゴリズム Step2(交叉)のための手法（続き） 順序交叉 動作の様子(順序交叉) →子となる解において、σi≠σjが常に成り立つ 8

アニーリング法 現在の解の近傍でランダムに選択した解が改善策なら100%、改悪策なら一定の確率で移動する方法 →局所探索法が改善解にしか移動できないため，局所最適解に到達すると探索できない欠点を解消 アルゴリズム 動作の様子(アニーリング法) 近傍探索の終了条件 ：近傍からランダムに解を選ぶ回数が近傍の大きさの一定倍である 温度tの更新方法 幾何冷却法：t=βtとして(0<β<1)更新する方法 対数冷却法：t=c/log(k+1)(k:更新回数)にする手法(収束を遅くすると最適解に近づくため、 あえて温度を下げにくくしているが、かえって実用的ではない) 9

タブー探索法 タブー箇所にはいかないようにしながらも、 xの近傍の中の最良解 (≠x)を選び続ける手法 タブー箇所を作ることで、「 x→x’と更新した後に、 x’の近傍の最良解が xの場合に更新できない」欠点を解消 アルゴリズム 動作の様子(タブー探索法) タブーリストの作り方 ・Step3の解を逐次入れ続ける→探索した解の周辺からの脱却が厳しいまま ・近傍操作により値が変化した変数(xj) or その変数の値をタブーリストに入れ、 xjの変更 or xjの変更前への逆戻りを禁止する また、タブー期間を設けて、タブーリストの変数をtターンでなくす手法もある タブー探索法の効率化 配列(t1,,,tn)を用意し、ti=-infで初期化する.探索k回目に変数xjが更新されたらtj=kとし、k-tj≦tgなら 変数xjの値の操作が禁止と判定できる(O(1)) 10

誘導局所探索法 評価関数を適切に変化させながら、局所最適化を行う手法 アルゴリズム fの更新に関して 直前の局所探索法で得られた局所最適解の 構成要素の中で、コストが大きな要素に ペナルティを加える 例(巡回セールスマン問題 ) 以下の評価関数においてp_uvがペナルティー (初期値は0)で、局所探索解で巡回した辺 の中でd_uv/(1+p_uv)が最大となる u,vにおいて、p_uv+=1とする 動作の様子(誘導局所探索法) 11

ラグランジュヒューリスティック ラグランジュ緩和問題の解から元の問題の実行可能解を求める手法 例（集合被覆問題） 問題文 ラグランジュ緩和問題 ラグランジュ緩和問題の解 ラグランジュ双対問題 この時、z_LR(u)（緩和問題の目的値）は条件よりz(x)以下なので、z(x)の最適値の下界となる。 そのため、z_LR(u)の最大値を求める(ラグランジュ双対問題)必要が出る →劣勾配法を用いて効率的に質の高い実行可能解を算出 12

ラグランジュヒューリスティック (劣勾配法 ) ラグランジュ緩和問題の解から元の問題の実行可能解を求める手法 アルゴリズム 動作の様子(劣勾配法) 反復が有限回で終わらない可能性もあるので、 λ=2とし、30回連続でzLR(u)が改善しなかったら λ=0.5λと更新し続け、 λが十分小さくなった時に 終了することで回避する場合もある uの更新式 13

ラグランジュヒューリスティック 緩和解で値が１の変数＋すでに満たされた制限を除いた部分問題から、 近似解法を利用して元問題の実行可能解を求める手法 アルゴリズム（貪欲法による部分問題の解決） cjではなくc^{~}_j(u)が最小のものを選ぶパターンも存在する 14