20221223_技術グループ発表_最適化・探索

技術調査報告 最適化・探索 2022年12月 ＨＥＲＯＺ株式会社

目次 ◼ はじめに • グループ活動の目的 • 厳密解法とメタヒューリスティクス ◼ 厳密解法 • 組合せ最適化に対する厳密解法の流れ • 厳密解法の標準的アプローチ • 強い定式化の勧め ◼ メタヒューリスティクス • 概要 • メタヒューリスティクスが適した問題の大別 • 順序性を考慮するアルゴリズム • 順序性を考慮しないアルゴリズム 2

グループ活動の目的 ◼ 目的 • 最適化手法に関する実践的な知識を習得することで、実案件へ対応力の平準化 に資する ◼ 背景 • 当社は機械学習をバックグラウンドとするエンジニアが多く、実案件にて最適 化手法を扱う場合には一部経験者を中心にアサインされてきた • 必ずしも数理最適化を専門としていないメンバーでも案件に対応できるよう、 実践的な知識を効率的に付与する必要性 • とくに、最適化手法には厳密解を求める方針と近似解を求める方針の2つに大別 され、各方針に関する理解や使い分けの判断ができることが重要（今発表のメ インコンテンツ） 3

厳密解法とメタヒューリスティクス ➢ 最適化アルゴリズムは、解の最適性が理論的に保証された「厳密解法」と、最適性よりも短時 間でベターな解を得ることに特化した「メタヒューリスティクス」に大別される。 ➢ メリデメを理解し適用する問題のタイプに応じた吟味が必要（ハイブリットもあり得る） 探索分類 厳密解法 メタヒュー リスティク ス 特 徴 採用のポイント 👍 Good ・真の最適解（大域最適解）が得られる ・モデリングインターフェースが豊富で実装が容易 👎 Bad ・ある程度の規模の問題には有償ソルバーが必須（自前実装は 無謀） ・問題の規模やタイプによっては現実的な時間で解が得られな い可能性（解けないものは解けない） ・小規模〜中規模の問題 ・目的関数が線形 ・大域最適性や再現性が重要 👍 Good ・決定変数が膨大となる大規模問題でも、現実的な時間でベ ターな解が得られる ・焼きなまし法、遺伝的アルゴリズムなど、多数の手法があり、 選択の幅が大きい 👎 Bad ・C++等での自前実装が基本となるため実務者には敷居が高い ・最適性の保証がなく、局所的最適解が出力されやすい ・解の再現性を担保するのが手間 ・チューニングするパラメータが多い傾向にあり、その方法も 体系だったものは少なく試行錯誤となりがち ・大規模問題である ・目的関数が本質的に非線形 ・大域最適性や再現性はあま り重視しない ・計算速度が重要 4

組合せ最適化に対する厳密解法の流れ ➢ 決定変数が離散的（整数値、バイナリ）である最適化問題を「組合せ最適化」と呼ぶ ➢ 組合せ最適化に厳密解法を適用する流れは概ね下記のとおり ①定式化 • 目的関数と制約条件を整理して数理計画問題とし ての表現に変換する • 定式化の方法によってソルバーのパフォーマンス が大きく変わるため、チューニングの定石を知っ ておくことが重要 ナップザック問題 ②モデリングインターフェース上の実装 • PuLPやORtools等の、手元の開発言語でソルバー を動作させるモジュールを利用して実装を行う ③求解と評価 • 出力された最適解を評価する。実行可能解でない、 制約を満たしていないなどの不具合がある場合は 実装が適切か確認する 数理計画問題としての定式化 5

厳密解法の標準的アプローチ ➢ ソルバーが厳密解法で問題を解く際の詳細ロジックは企業秘密であるものの、大ま かには以下の2手法を組み合わせている • 分枝限定法（branch and bound） • 切除平面法（cutting plane method） ➢ 定式化を適切に行うためには、上記手法に対する理解が必要 6

分枝限定法(1/2) ➢ 問題の「緩和」と「分割」を組み合わせることで効率的に厳密解を求める手法 • • （緩和）各子問題を連続最適化問題に緩和した問題を内点法、単体法などで解く （分割）一部の変数の範囲を制限した「部分問題」を作る もとの最適化問題 部分問題への分割 連続最適化問題への緩和 7

分枝限定法(2/2) ➢ 「分割」と「緩和」でなぜ解けるのか？（最大化問題の場合） • • • • • 部分問題の最適値 ≦ 元問題の最適値 元問題の最適値 ≦ 緩和問題の最適値 緩和問題を解いて、整数解であれば下界の更新、非整数解であれば上界の更新を行う ある部分問題の上界より良い暫定解が見つかれば、その部分問題をさらに分割、探索する 必要はない（限定操作） 下界と上界を挟みうちで更新していくことで、現実的な時間で最適解に辿り着くはず 8

切除平面法（1/2） ➢ 分枝限定法の特性上、上界と下界の更新精度がパフォーマンスを左右する ➢ 「元問題の探索空間」と「線形緩和問題の探索空間」の差分が少ない方が有利 ➢ 線形緩和問題の探索空間を「うまくカット」して元問題の探索空間に近づけようと するのが切除平面法 ➢ 整数解を切り落とさないよう余分な探索空間をカットする（平面カット） 👍 うまいカット 👎 うまくないカット カットしすぎ。 整数解を切り落として しまっている 線形緩和問題の探索空間（凸多面体） ※内部の赤丸が整数解 探索空間を全然カット できていない 9

切除平面法（2/2） ➢ 「うまいカット」についてもう少し数学的に考えてみる ➢ 実行可能な整数解全体の凸包のことを整数多面体（integer polyhedron）とよぶ ➢ 「うまいカット」とは整数多面体に近づくカットのこと ➢ 一般に整数多面体の陽な表現を知ることは困難なので、如何に「うまいカット」を見つけるか が厳密解法の主要な研究テーマであり、有償ソルバーのコア技術でもある 主要なソルバー 各ソルバーに実装された 平面カットアルゴリズム 線形緩和問題の探索空間と整数多面体 10

厳密解法の設計は難しい ➢ 分枝限定法 + 切除平面法で組合せ最適化問題を解くアルゴリズムを自装しようと すると、下記のようなチューニングを分析者自身で行う必要がある ◼ 定式化 • 同じ最適化問題でも複数の定式化が考えられ、平面カットがうまく行きやすい 「強い定式化」を意識する（後述） ◼ 分枝限定法 • 問題の分割方法（どの変数をどの値で分割するか？） • 探索方法（分割した部分問題をどの順番で解いていくか？深さ優先探索？最良 探索？） • 部分問題の求解アルゴリズムをどうするか（内点法？単体法？） ◼ 切除平面法 • 平面カットのアルゴリズムをどう設計するか？ ◼ 上記すべてを自前設計するのは厳しい。定式化以外はソルバーに任せましょう 11

「強い定式化」の勧め ➢ 探索空間がなるべく広がらないようにすること、平面カットがしやすい形状にする ことが大事 ➢ 上記が考慮された定式化を「強い定式化」と呼ぶ ➢ ちょっとした工夫でソルバーのパフォーマンスが顕著に変わるので、以下に示す程 度の内容は押さえておきましょう（後日、GROWIにまとめる予定） 1. 整数変数はバイナリ変数（0 or 1）に変換する 2. 大きすぎる定数（いわゆるBiG-M法）の使用は可能な限り避ける 3. 最大値の最小化（最小値の最大化）のような問題に注意 4. 解の対称性を除く工夫をする 12

強い定式化の例（グラフ彩色問題） ➢ 学校のクラス分け。仲の悪いメンバー同士は同じクラスに入らないようにしつつ、 なるべく少ないクラス数にしたい A組 B組 C組 実線で結ばれたペアは仲が悪い 不仲なメンバーが同じクラスに入らないよう3組に分割 13

強い定式化の例（グラフ彩色問題） ➢ 各クラスの「番号」がどれかは本質的でない ➢ 解が無駄な対称性を持っている → ソルバーの求界性能に悪影響 A組とC組のメンバーが入れ替わっても解としては同じ A組 A組 B組 B組 C組 C組 14

強い定式化の例（グラフ彩色問題） ➢ 各クラスにメンバーがいるか否かを表す変数 約」を加える ➢ 一般性を失うことなく解空間を狭くできる に対して「対称性を除去する制 → 強い定式化 クラス数の最小化問題 弱い定式化 はk番目の組にメンバーが いるか否かを表す0-1変数 強い定式化 解の対称性を除去する 制約を追加 メンバーがいるクラス の番号が必ず先になる よう制御 15

メタヒューリスティクス概要 メタヒューリスティクスの主な流れは、 ・解の評価 ・解の遷移（探索） の繰り返しである。 解2に遷移 解1を評価 解3に遷移 解2を評価 解Nに遷移 解3を評価 集中化、多様化といった相反する戦略のバランスをとることで、 より高性能なアルゴリズムを実現する。 集中化 多様化 良い解同士が似た構造を持 つ前提（※近接最適性）で、 似た解を探索する 局所最適解に陥ることを防 ぐため、 似ていない解を探索する 16

メタヒューリスティクスが適した問題の大別 メタヒューリスティクスが適した問題には、大きく分けて2通りの問題がある。 順序性のある問題例： ぷよぷよ どの順でぷよを置いた かで連鎖に大きな違い が出る 順序性のない問題例： カードゲームの デッキ構築 デッキ全体で評価すれ ばよいため、順序とい う概念がない ※順序性のある問題のことを「近似最適性がなくメタヒューリスティクスが適さない」と評するサ イトも見かけた。おそらくアプローチを片方しか知らない記述 17

順序性を考慮するアルゴリズム：ビームサーチ 1/4 順序性のある問題では、ある状態から「可能な操作をする→操作に応じて状態を遷移→途中状態を 仮評価」を繰り返し、最終状態の評価を最大化することを目的として探索を行う。 ビームサーチでは各操作に応じた状態をまず全て評価する。 ぷよぷよで言うと、 「一つ目のぷよを左端に置く」 「一つ目のぷよを中央に置く」 「一つ目のぷよを右端に置く」 などが対応 数字は操作後の 暫定評価値。 ぷよぷよでは 「盤面上のぷよが消えた場合の期待 連鎖数」など 5 1 3 18

順序性を考慮するアルゴリズム：ビームサーチ 2/4 次に、評価順に指定した数（幅）のノードを選択し、可能な操作を全て行う 下記は幅2の例 ぷよぷよで言うと、 「一つ目のぷよを左端に置く」 「一つ目のぷよを中央に置く」 「一つ目のぷよを右端に置く」 などが対応 評価5,1,3の中の上位2つは 5,3 5 6 11 1 7 ぷよぷよで言うと、 「二つ目のぷよを左端に置く」 「二つ目のぷよを中央に置く」 「二つ目のぷよを右端に置く」 などが対応 3 5 10 3 19

順序性を考慮するアルゴリズム：ビームサーチ 3/4 その後も、同様の処理を繰り返す ぷよぷよで言うと、 「一つ目のぷよを左端に置く」 「一つ目のぷよを中央に置く」 「一つ目のぷよを右端に置く」 などが対応 5 1 ぷよぷよで言うと、 「二つ目のぷよを左端に置く」 「二つ目のぷよを中央に置く」 「二つ目のぷよを右端に置く」 などが対応 3 6 11 7 5 10 3 15 12 20 13 11 14 ぷよぷよで言うと、 「三つ目のぷよを左端に置く」 「三つ目のぷよを中央に置く」 「三つ目のぷよを右端に置く」 などが対応 20

順序性を考慮するアルゴリズム：ビームサーチ 4/4 評価が最大の最終状態を選択し、その状態に到達できる操作を選択して終了 5 1 3 6 11 7 5 10 3 15 12 20 13 11 14 21

順序性を考慮しないアルゴリズム：山登り法 1/5 順序性のない問題では、ある状態から「状態を評価→状態を遷移 」を繰り返し、状態の評価を最大 化することを目的として探索を行う。 山登り法（局所探索法）ではまず初期状態評価する。 下記例はカードゲームのデッキの評価方法が定まっていることを前提にデッキを構築する例。 評価値 0.3 デッキの内容を入力して評価値を計算 22

順序性を考慮しないアルゴリズム：山登り法 2/5 次に、現在の解を少しだけ変更し、再評価する。 この少しだけ解を変えた状態を近傍と呼ぶ。 今回はデッキからランダムに1枚のカードをランダムな別のカードに変更することを近傍とする。 評価値 0.3 0.25 評価値を再計算 評価値が下がってしまった ドラゴンのカードを鬼のカードに変更 23

順序性を考慮しないアルゴリズム：山登り法 3/5 近傍に遷移して評価が上がらなかった場合は、別の近傍への遷移を行う。 評価値 0.3 0.35 評価値を再計算 評価値が上がった ジェレヌクのカードをライオンのカードに変更 24

順序性を考慮しないアルゴリズム：山登り法 4/5 近傍に遷移して評価が上がった場合は、遷移した状態からまた次の遷移を行う 評価値 0.35 0.4 ドラゴンのカードをバーサーカーの カードに変更 前回の遷移を保ったまま 25

順序性を考慮しないアルゴリズム：山登り法 5/5 評価値が上がらなくなるまで処理を繰り返し、評価最大の解を得る。 評価値の遷移は下記のように、必ず上がる。 評価値 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 評価値 4 5 6 26

順序性を考慮しないアルゴリズム：焼きなまし法 1/3 例えば、カードゲームでスライムのカードが3枚以上デッキに含まれるとかなり強いデッキとなるが、 スライムのカードが2枚以下だとあまり意味がない、というようなことがある。 この場合、カード1枚変更の近傍で山登り法を適用すると、スライム3枚のデッキに到達できない。 評価値 0.4 評価が下がるので 遷移不可 0.3 スライム2枚の状態に 遷移されないせいで、 この状態には遷移でき ない 0.99 27

順序性を考慮しないアルゴリズム：焼きなまし法 2/3 そこで、スコアが下がった場合も変化量に応じて遷移を許すことにする。 あるデッキnowのスコアをScore(now)、nowをnextに変化させる時、 𝑆𝑐𝑜𝑟𝑒 𝑛𝑒𝑥𝑡 ≥ 𝑆𝑐𝑜𝑟𝑒(𝑛𝑜𝑤)の時は山登り同様に遷移、 𝑆𝑐𝑜𝑟𝑒(𝑛𝑥𝑒𝑡) < 𝑆𝑐𝑜𝑟𝑒(𝑛𝑜𝑤)の時は変化量Δ = Score next − Score(now)に対し、 Δ Δ 確率 𝑒 𝑡 で遷移することにする。(最小化問題なら 𝑒− 𝑡 ) tは時間と共に徐々に低くすることで、ランダムに近い遷移から徐々に山登りに近づけていく 𝑃(𝑛𝑜𝑤 → 𝑛𝑒𝑥𝑡) 1 𝑃(𝑛𝑜𝑤 → 𝑛𝑒𝑥𝑡) 1 Δ 𝑒𝑡 Δ 𝑒𝑡 0 0 -1 0 tが高い時の遷移確率 1 -1 0 tが高い時の遷移確率 1Δ 28

順序性を考慮しないアルゴリズム：焼きなまし法 3/3 評価値は下がることもあるが、局所解を脱出できる可能性があり、 充分に時間があれば山登り法以上の結果が期待できる 評価値 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 評価値 4 5 6 29