【しっかり学ぶ数理最適化】4.6

2025年度後期輪読会 しっかり学ぶ数理最適化 4章 整数計画と組み合わせ最適化(4.6) 京都大学大学院 工学研究科 M1 河田 賢斗 0

アジェンダ  局所探索法の概略  近傍の定義と解の表現  探索空間と解の評価  移動戦略  局所探索法の効率化 1

アジェンダ  局所探索法の概略  近傍の定義と解の表現  探索空間と解の評価  移動戦略  局所探索法の効率化 2

局所探索法の概略 局所探索法のフローについて スタート 実行可能解 𝑥 ∈ 𝑆 解 に変形を加える (近傍操作を行う)☞ 内に改善解 ( を満た す解)があれば 現在の解 𝑥 から 改善解 𝑥 に移動する 解の集合 𝑁 𝑥 ⊂ 𝑆 を作成  特徴  単純なアイデアに基づく  設計の自由度が大きい • 近傍の定義 高性能な • 探索空間 アルゴリズムを • 移動戦略 設計可能 内に改善解 がなければ 局所探索法を終了する フィニッシュ 3

アジェンダ  局所探索法の概略  近傍の定義と解の表現  探索空間と解の評価  移動戦略  局所探索法の効率化 4

近傍の定義と解の表現 近傍内に改善解が含まれる可能性を高め、近傍の大きさを抑制的に 【具体例】 巡回セールスマン問題におけるλ-opt近傍( が一般的) λ-opt近傍 :λ本のリンク(エッジ)の切断及び再接続による近傍を指す ※2-opt近傍では交差するリンクを切断し、再接続する(下図参照) 2-opt近傍の近傍操作の例 5

近傍の定義と解の表現 【具体例】 順列で解を表現できる問題(Ex. 巡回セールスマン問題) に対する、挿 入近傍や交換近傍 挿入近傍:順列内の要素を1つ移動させる(Or-opt近傍にも拡張可能) π 1 2 3 4 5 6 π’ 1 5 2 3 4 6 交換近傍:順列内の2つの要素を入れ替える π 1 2 3 4 5 6 π’ 1 5 3 4 2 6 6

近傍の定義と解の表現 局所探索法は、「良い解同士は似た構造を持つ」という 近接最適性(Proximity Optimality Principle; POP)に基づき設計さ れている 【具体例】 巡回セールス問題 ☞良い巡回路同士に共通して含まれる辺が非常に多い傾向 2-opt近傍や3-opt近傍に基づく局所探索法が有利 一方で、交換近傍では4本の辺が同時に交換されるため、 近接最適性の観点からは不利 7

近傍の定義と解の表現 近傍の大きさの設定も重要である 小 近傍の大きさ 大 解の質 低下 上昇 計算時間 小さい 大きい 解の質と計算時間の双方を考慮する必要性 小さな近傍と大きな近傍の組み合わせで探索する手法も有効 ☞ 計算時間を抑えつつ、解の質を向上させる仕組み (Ex. 2-opt近傍と3-opt近傍の組み合わせ) 8

アジェンダ  局所探索法の概略  近傍の定義と解の表現  探索空間と解の評価  移動戦略  局所探索法の効率化 9

探索空間と解の評価 探索空間とは、探索の対象となる解全体の集合を表す 実行可能解を一つ求めることが困難な問題や、複雑な近傍操作が必要 となる問題における探索空間とは? 実行可能領域 探索方針は3つに分類できる (1)実行可能領域のみ探索 (1)実行可能領域のみ探索 (2)実行不可能領域も探索 (3)実行可能領域と異なる探索空間を導入 実行可能領域 実行不可能領域 探索空間 実行可能領域 (2)実行不可能領域も探索 (3)実行可能領域と異なる探索空間を導入 10

探索空間と解の評価 実行可能解を求めることが困難な問題について 【具体例】 集合分割問題 ☞ペナルティ関数を導入し、実行不可能領域も探索する(前頁の(2)) …式(1) (ペナルティ関数) …式(2) (解 の評価関数) 𝑓(𝑥 ) < 𝑓(𝑥) (𝑥 ∈ 𝑁 𝑥 ) True False 𝑥 → 𝑥 に移動する手続き を繰り返す Finish 探索中に生じた最良の 実行可能解𝑥 ♭ を出力 11

探索空間と解の評価 前頁の問題ではペナルティ重み 実行可能解の質が依存 の値の大小に、導出される ペナルティ重み 小 局所探索法は 実行不可能領域 から抜けにくい 最 小 化 大 実行可能解間を 移動しにくい 最 小 化 実行不可能領域 最 小 化 実行不可能領域 実行不可能領域 12

探索空間と解の評価 適当なペナルティ重みを与えて1度適用するのみでは、質の高い実行可能 解を得ることは難しい 【改善案】 ペナルティ重みの更新 × 局所探索法 ☞ 重み付け法 【重み付け法のフロー】 直前の局所探索法で 実行可能解なし True ペナルティ重みの値を 増加させる¹ False ¹: ,…, ペナルティ重みの値を 減少させる² ²: 13

探索空間と解の評価 解空間とは異なる探索空間を導入する例について考える 【具体例】 ⾧方形詰込み問題 (難点) 各荷物 の座標 ( ) の値を直接的に探索し、重なりを排除させる ことは困難 【改善案】 順列を解の表現とし、BLF法(Bottom-Left-Fill Algorithm) と呼ばれ るアルゴリズムにより荷物の配置を決定 ☞ 個の荷物からなる 通りの順列を探索の対象とし、各反復では荷 物を順番に左下から詰める方法 14

アジェンダ  局所探索法の概略  近傍の定義と解の表現  探索空間と解の評価  移動戦略  局所探索法の効率化 15

移動戦略 近傍内をどのような順序で探索し、どの改善解に移動するのかを定め るルールのことを移動戦略(Move Strategy)と呼ぶ 【具体例】 即時移動戦略(first admissible move strategy) ☞近傍内の解をランダムまたは決まった順序で探索し、最初に見つけ た改善解に移動 (計算時間:短) 最良移動戦略(best admissible move strategy) ☞近傍内のすべての解を走査し、最良の改善解に移動 (計算時間:⾧) 【ポイント】 近傍内の解を一巡する順序を定めたリストを用意し、近傍を探索 改善解が見つかった場合は、近傍操作の次の候補から探索を開始 16

アジェンダ  局所探索法の概略  近傍の定義と解の表現  探索空間と解の評価  移動戦略  局所探索法の効率化 17

局所探索法の効率化 近傍内の改善解を発見する探索を近傍探索と呼び、アルゴリズム全体 の効率化を図るために、これを効率化することが求められる 【手法】 (1) 評価関数の値の計算を効率化 ☞現在の解 と近傍解 の間で変化した変数のみ再計算すれ ばよい ☞集合分割問題における評価関数 (1反転近傍)が紹介されている の値の変化量を計算する方法 (2) 改善の可能性のない解の探索を省略 18

局所探索法の効率化 １反転近傍について 【フロー】  ,  評価関数は の2種類の近傍解が存在 ( ) と表され、 とすれば、 このとき、現在の解 に対して との評価関数の値の変化量を 同様に、 の場合は として得られる近傍解 と定義 と定義 19

局所探索法の効率化 すると、評価関数の値の変化量は下記の通り記述できる ・・・式(3) 𝒋 ・・・式(4) 𝒋 (※ )  制約条件 の値( )を予め計算して補助記憶に持てば、 を求めるために必要な計算の手間は となる  , した際には、各々 ばよい( ) の反転により現在の解 ・ が近傍解 に移動 と計算すれ 20

局所探索法の効率化 1反転近傍は評価関数の値の計算を効率化するうえで有効な手法 【ポイント】 A) 補助記憶(今回の問題では )を用いて評価関数の値( 化量を計算 B) 現在の解が移動する際に、補助記憶を更新する ( ) )の変 一方で、改善の可能性のない解の探索を省略することもアルゴリズム 全体の効率化にとっては重要 ☞近傍の操作を評価関数の値が改善される範囲に限定することも可能 【具体例】巡回セールスマン問題における 近傍 21

局所探索法の効率化 巡回セールスマン問題における 略する手法を考える 近傍を元に、無駄な探索を省 【2段階フロー】(都市 を始点とする辺交換の操作) 1. 辺{ }を削除し、辺{ }を追加 2. 辺{ }を削除し、辺{ }を追加 22

局所探索法の効率化 近傍内の改善解について 近傍の操作により改善解が得られる を満足 または のいずれか一方が満たされる必要性 始めに削除する辺{ 𝟏 𝟐 }を決定し、追加する辺{ 𝟐 𝟑 }について 𝒗𝟐𝒗𝟑 𝒗𝟏 𝒗𝟐 を満たすようにする (このとき 𝒗𝟐𝒗𝟑 𝒗𝟏 𝒗𝟐 かつ 𝒗𝟒 𝒗𝟏 𝒗𝟑 𝒗𝟒 である近傍解も探索の対象となる) 近傍内の探索を逃さないことを保証できる 23

局所探索法の効率化 𝒗𝟐 𝒗𝟑 𝒗𝟏 𝒗𝟐 を満たす辺の候補{ 𝟐 𝟑 }を効率よく走査したい 各都市 に対して距離 𝒖𝒗 の昇順に都市 の番号を記憶した近傍リストを使用 (本問題では、都市 𝟐 に対するリストを走査する) 完全な近傍リストを準備すると計算コストが高いため、適当なパラメータ を用意して距離 𝒖𝒗 の小さいほうから 番目までを近傍リストに記憶 その他の計算効率化の手法 集合分割問題； 𝒋 であれば少なくとも1つの制約条件 における が変化するまで変数 を探索の候補から除く 24

局所探索法の効率化 巡回セールスマン問題 ; don’t look bit と呼ばれる手法 don’t look bit とは？ ☞フラグを管理して近傍探索を効率化する手法 すべての都市に対して フラグを0とする 辺交換の操作をすべて試す☞ 改善解が得られたか？ 都市𝑣のフラグを0 とする ☞計算時間を 大幅に短縮 可能 False 都市 𝑣 のフラグを1とする 都市 に接続されている2本の辺のうち、 少なくとも一方が削除された場合 25