Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
より良い解に辿り着くカギ-近傍設定の重要性
Search
NearMeの技術発表資料です
PRO
March 17, 2025
Programming
0
72
より良い解に辿り着くカギ-近傍設定の重要性
数理最適化でより良い解を見つけるための近傍設定の重要性を解説。巡回セールスマン問題を例に、構築法・改善法、2-optなどの近傍操作を紹介します。 #数理最適化 #組合せ最適化
NearMeの技術発表資料です
PRO
March 17, 2025
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
ULID生成速度を40倍にしたった
nearme_tech
PRO
1
20
Amazon AuroraとMongoDBの アーキテクチャを比較してみたら 結構違った件について
nearme_tech
PRO
0
10
GitHub Custom Actionのレシピ
nearme_tech
PRO
0
6
RustでDeepQNetworkを実装する
nearme_tech
PRO
1
11
ルートの質を評価する指標について
nearme_tech
PRO
0
19
Rustで作る強化学習エージェント
nearme_tech
PRO
2
67
ビームサーチ
nearme_tech
PRO
0
54
WASM入門
nearme_tech
PRO
1
58
ESLintをもっと有効活用しよう
nearme_tech
PRO
0
36
Other Decks in Programming
See All in Programming
これだけは知っておきたいクラス設計の基礎知識 version 2
masuda220
PRO
24
6.3k
The Implementations of Advanced LR Parser Algorithm
junk0612
0
160
Coding Experience Cpp vs Csharp - meetup app osaka@9
harukasao
0
740
Vibe Codingをせずに Clineを使っている
watany
17
6.2k
Firebase Dynamic Linksの代替手段を自作する / Create your own Firebase Dynamic Links alternative
kubode
0
240
AI Coding Agent Enablement - エージェントを自走させよう
yukukotani
14
5.9k
PHPで書いたAPIをGoに書き換えてみた 〜パフォーマンス改善の可能性を探る実験レポート〜
koguuum
0
150
Make Parsers Compatible Using Automata Learning
makenowjust
1
2k
State of Namespace
tagomoris
4
970
大LLM時代にこの先生きのこるには-ITエンジニア編
fumiyakume
3
880
リアクティブシステムの変遷から理解するalien-signals / Learning alien-signals from the evolution of reactive systems
yamanoku
3
1.2k
Preact、HooksとSignalsの両立 / Preact: Harmonizing Hooks and Signals
ssssota
1
1.4k
Featured
See All Featured
Designing Experiences People Love
moore
141
24k
Thoughts on Productivity
jonyablonski
69
4.6k
Git: the NoSQL Database
bkeepers
PRO
430
65k
Testing 201, or: Great Expectations
jmmastey
42
7.4k
Intergalactic Javascript Robots from Outer Space
tanoku
270
27k
Navigating Team Friction
lara
184
15k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.1k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.8k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Making the Leap to Tech Lead
cromwellryan
133
9.2k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
5
520
Bootstrapping a Software Product
garrettdimon
PRO
307
110k
Transcript
0 より良い解に辿り着くカギ-近傍設定の重要性 2025-03-14 第115回NearMe技術勉強会 Mizuki Wakabayashi
1 ⽬次 1. ⾃⼰紹介: 初めまして、若林瑞樹です 2. 数理最適化? 必要? AI? 機械学習
3. 数理最適化が必要となる難しい問題とは 4. より良い解へ辿り着くために...近傍設定の重要性
2 1. ⾃⼰紹介: 初めまして、若林瑞樹です 所属: 東京農⼯⼤学⼤学院修⼠⼀年 ⼯学府 知能情報システム⼯学専攻 研究室: 数理最適化がメイン.
特に、組合せ最適化(離散最適化) 私の研究内容: 学部: 機械学習の損失関数, 現在: 組合せ最適化 私の趣味: プログラミング, 筋トレ, 友⼈の研究室の⽅々とのスマブラ(スイッチ) 他の⽅々の研究内容(⼀部): ダイナミックプライシング, 相乗りタクシー , チームスポーツにおける個⼈の能⼒の推定, 移動距離や体⼒負荷を考慮したスポーツスケ ジューリング最適化等... ゼミでは進捗報告を全員で⾏う→ ⾃分の研究分野外の知識や⼿法も学んでいます
3 ‧数理最適化と調べると... 数理最適化は、問題の最適化を実現するための「最適解」を、問題の構造や数 学的な性質に基づいて発⾒するという「決定論的な⼿法」 ‧意思決定や、⼿法を求めるための技術であり、学習をして予測精度をあげるという分野ではない ‧個々の問題設定ごとに、制約条件や⽬的関数は異なる ‧より良い解を学習していくことは困難 ‧
その分野に対する知⾒や知識、最適化技術が必要 ‧数理最適化が使⽤される分野: 物流, 配送, スケジューリング ⽣産ライン, 機械学習のハイパーパラメータ等... 参考⽂ 献:https://www.brainpad.co.jp/doors/contents/about_mathematical_optimization/#%E3%80%8C%E6%95%B0%E7%90%86%E6%9C%80%E9%81%A9%E5%8C%96%E3%80%8D%E3%81%A8%E3%80%8CAI%E3%80%8 D%E3%80%8C%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%80%8D%E3%81%A8%E3%81%AE%E9%81%95%E3%81%84%E3%81%AF%EF%BC%9F 2. 数理最適化? 必要? AI?
4 ‧難しい問題の例: 巡回セールスマン問題 ‧N個の都市を訪れ、⼀周するための最⼩距離を求める問題 ‧ 下は52都市の例 3. 数理最適化が必要となる難しい問題とは ”x座標が⼩さい順に訪れる”という貪欲法 ”中⼼座標に近い順に訪れる”という貪欲法
5 ‧数理最適化における難しい問題: 計算量, 計算時間, 組合せ数が膨⼤であるため難しいという意味 ‧52都市の訪れるパターン→ 52! = 8.07* 10^67通り
‧現在の計算機をもってしても果てしない時間かかる ‧よって、全通りは試すことはできない! ‧しかし、研究者によって 数万都市レベルの最⼩距離ルートは算出 ‧右はスウェーデン24978都市の最適解 ‧数理最適化技術や、巡回セールスマン問題に対する知⾒や知識が深く関与 出典: https://www.math.uwaterloo.ca/tsp/sweden/tours/swtour_small.htm 3. 数理最適化が必要となる難しい問題とは
6 ‧52都市で、最⼩距離ルートを考えていただきたいです ‧どのような⽅針(⼿法、基準)で訪れていきますか? ‧1. スタート都市から近い都市を辿っていく ‧2. 最⼩全域⽊を解く⾵に、近い都市2つを 線で結んでいく...を繰り返す
3. 数理最適化が必要となる難しい問題とは
7 ‧52都市で、最⼩距離ルートを考えてみていただきたいです ‧どのような⽅針(⼿法、基準)で訪れていきますか? ‧⾚の点スタートで、近い順に訪れるという⽅法だと... → ‧右のようにちょっと遠い距離を取りこぼしてしまう ‧1都市, 1都市順番に選択していく⽅法では良い解はでなさそう.. ‧少しずつ解を作っていく⽅法→構築法などと呼びます... ‧⼀旦ルールを守ったルート(解)を作って、少しずつ解を改善していく⽅が良さそう...
‧初期解を改善していく⽅法→改善法などと呼びます 3. 数理最適化が必要となる難しい問題とは S S
8 ‧構築法 ‧貪欲法: なんらかの基準に貪欲に従って解を構築 ‧ビームサーチ: 構築するごとに、解の評価を⾏って上位BEAM_WIDTH数だけを残していく ‧改善法: 近傍と呼ばれる解の変更ルールを設定して⾏う(⼩さな変更の範囲) ‧近傍設定の例: ‧insert(a,
b )a都市の後ろにb都市を訪れる ‧swap(a, b) a都市とb都市の訪れる順番を逆に ‧swap(a,b,c) a,b,c都市の訪れる順番をc,b,aに ‧変更範囲が⼤きければ良いというわけではない ‧局所探索法: 近傍操作で、現在の解より良くなった→解の更新→その解に近傍操作 を繰り返していく ‧焼きなまし法: 序盤: 現在の解より悪くなった解を⾼い確率で受け⼊れて更新 終盤: 現在の解より良い解のみを基本的に受け⼊れて更新 3. 数理最適化が必要となる難しい問題とは
9 ‧改善法: 近傍と呼ばれる解の変更ルールを設定して⾏う(⼩さな変更の範囲) 3. 数理最適化が必要となる難しい問題とは ”x座標が⼩さい順に訪れる”という 貪欲法で作った初期解
10 ‧改善法: 近傍と呼ばれる解の変更ルールを設定して⾏う(⼩さな変更の範囲) 3. 数理最適化が必要となる難しい問題とは 近傍の設定が良ければ、どんな初期解からで も、最適ルートへ改善することは可能! ⼤域最適解 局所最適解1
局所最適解2
11 ‧近傍設定の例: ‧insert(a, b )a都市の後ろにb都市を訪れる ‧swap(a, b) a都市とb都市の訪れる順番を逆に ‧巡回セールスマン問題に対しては、上記のような近傍操作では より良い解を算出するのはかなり困難
‧swapやinsertをしてもそこまで良くなりそうにも思えない ‧スケジューリング問題や⼀定の問題に対してはswap(...)がかなり有効な場合も ‧巡回セールスマン問題に対しては有効ではない 4. より良い解へ辿り着くために...近傍設定の重要性
12 ‧巡回セールスマン問題における有効な近傍設定 ‧2-opt(a, b ): a->a1->,.... an -> bという順番を丸ごと逆順にする ‧例:
都市番号: 7->5->4->3->6>1->2->7 に対する2-opt(7,1) →7->6->3->4->5->1->2->7となる ‧同様に3-optや4-optのように、範囲内の順番を丸ごと逆順という近傍操作が有効 4. より良い解へ辿り着くために...近傍設定の重要性
13 ‧改善法: 近傍と呼ばれる解の変更ルールを設定して⾏う(⼩さな変更の範囲) ‧局所探索法: 近傍操作で、現在の解より良くなった→解の更新→その解に近傍操作 を繰り返していく ‧焼きなまし法: 序盤:
現在の解より悪くなった解を⾼い確率で受け⼊れて更新 終盤: 現在の解より良い解のみを基本的に受け⼊れて更新 そのほかにも様々な⼿法がありま↓ 遺伝的アルゴリズム(GA), 粒⼦群最適化(PSO), アリコロニー最適化(ACO), タブーサーチ (TS), ⼈⼯⿂群アルゴリズム, ハーモニーサーチ, 差分進化, Emperor Penguin Algorithm,... ⾃然現象や⽣物の様⼦から着想を得た 新しい?アルゴリズムは多々ありますが... 4. より良い解へ辿り着くために...近傍設定の重要性
14 ‧本質的には、近傍を設定して良い解を⾒つけていくということに変わりはない ‧適切な近傍設定無しに、⼿法ごとの優劣はほぼない ‧着想を得た物や⽣物等が異なるだけで、AIの研究のようなブレークスルーは⾒られない ‧しっかりと作り込むことで、局所探索法ベースのシンプルな⼿法でも優秀 ‧先ほどの巡回セールスマン問題も、反復局所探索法で最適解の算出に成功 ‧局所探索法ベースのメリット ‧検証しやすい、挙動の確認がわかりやすい→確率的な要素がないため ‧パラメータのチューニングが不要
‧GAでは突然変異確率など、SAでは初期温度や温度の下がりぐらい等のパラメータが必要 4. より良い解へ辿り着くために...近傍設定の重要性
15 ‧意思決定やより良い⼿法を得るには、数理最適化が必須 ‧ある⽅針に沿って少しずつ解を作っていく構築法では、良い解を導くのは困難 →初期解から近傍操作によって良くしていく改善法が有効 ‧世の中には改善法の中に無数⼿法が存在しているが、⼤きな差異はない ‧どのように今の解をより良くしていくかという近傍設定が重要 まとめ
16 Thank you