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
August 26, 2024
1
150
遺伝的アルゴリズムを実装する
NearMeの技術発表資料です
PRO
August 26, 2024
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
並列で⽣成AIにコーディングをやらせる
nearme_tech
PRO
1
49
希望休勤務を考慮したシフト作成
nearme_tech
PRO
0
21
Hub Labeling による高速経路探索
nearme_tech
PRO
0
64
Build an AI agent with Mastra
nearme_tech
PRO
0
69
Rustで強化学習アルゴリズムを実装する vol3
nearme_tech
PRO
0
36
Webアプリケーションにおけるクラスの設計再入門
nearme_tech
PRO
1
81
AIエージェント for 予約フォーム
nearme_tech
PRO
2
150
ULID生成速度を40倍にしたった
nearme_tech
PRO
2
55
Amazon AuroraとMongoDBの アーキテクチャを比較してみたら 結構違った件について
nearme_tech
PRO
0
28
Featured
See All Featured
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Bootstrapping a Software Product
garrettdimon
PRO
307
110k
Reflections from 52 weeks, 52 projects
jeffersonlam
351
20k
Adopting Sorbet at Scale
ufuk
77
9.5k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
35
2.4k
KATA
mclloyd
30
14k
Producing Creativity
orderedlist
PRO
346
40k
The Invisible Side of Design
smashingmag
301
51k
Faster Mobile Websites
deanohume
307
31k
Optimising Largest Contentful Paint
csswizardry
37
3.3k
Gamification - CAS2011
davidbonilla
81
5.4k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.4k
Transcript
0 遺伝的アルゴリズムを実装する 2024-08-23 第102回NearMe技術勉強会 Takuma KAKINOUE
1 遺伝的アルゴリズム(GA)について • そもそもGAとは? ◦ 近似解の探索のためのヒューリスティックな⼿法 ▪ 探索⼿法は、⽣物の進化から着想を得ている • 選択、交叉、突然変異
◦ 多⽬的最適化にも有効 ▪ 解集団を⽤いた多点局所探索というアプローチのため • GAで解ける問題の例 ◦ ナップザック問題 ◦ 巡回セールスマン問題 ◦ 機械学習モデルのハイパーパラメータのチューニング
2 選択(Selection)の⼿法 • エリート(elite)⽅式 ◦ 適応度の⾼いn個の個体を残す⽅式 • ルーレット(roullet)⽅式 ◦ SoftMax関数を使って適応度に応じて確率的に個体を選択する⽅式
• トーナメント(tournament)⽅式 ◦ 解集団をn個のグループに分割し、各グループの中で ⼀番適応度の⾼い個体のみ残す⽅式
3 交叉(Crossover)の⼿法 • ⼀点(one-point)交叉 ◦ 染⾊体内のある1箇所で分割して、交叉させる⽅法 • ⼆点(two-point)交叉 ◦ 染⾊体内のある2箇所で分割して、交叉させる⽅法
• ⼀様(uniform)交叉 ◦ 染⾊体に含まれる遺伝⼦の⻑さと同じ⻑さのmaskを⽣成し、 maskが1の部分の遺伝⼦を⼊れ替える⽅法
4 ⼀点交叉のコード 区切りのindexをランダムで 指定して、両親の遺伝⼦を 区切ってコピーしたものを 結合し、⼦の遺伝⼦としている。
5 GAの⼿法 ※どちらも親集団μ個から個集団λ個が⽣成される • ( μ, λ ) - ES
◦ ⼦集団λ個の中から上位μ個を選択して次世代の親とする⽅法 • ( μ + λ ) - ES ◦ 親集団μ個と⼦集団λ個の和集合の中から上位μ個を選択して次世代の親とする ⽅法 ◦ ⼤域的最適解を得られやすい
6 アルゴリズムのフローチャート 1. 個体(Individual)をランダムに⽣成して、初期の解集団(Population)を構築 2. 以下をn世代繰り返す a. 解集団の各個体に対して適合度(Fitness)を算出する b. 解集団から適合度が⾼い個体を上位μ個抽出(selection)する
c. bで抽出された個体同⼠を交叉(Crossover)させて、新たな個体をλ個⽣成する d. cで新たに⽣成された各個体に対して突然変異(Mutation)を⾏う e. 解集団を以下の個体に置き換える i. ( μ, λ )の場合、”cで⽣成されたλ個の個体” ii. ( μ + λ )の場合、”bで抽出されたμ個の個体”と”cで⽣成されたλ個の個体” 3. 解集団からパレート解を抽出し、出⼒する(多⽬的最適化の場合)
7 実装する上で⼯夫した点 • インターフェース部分 ◦ 各⼿法をクロージャ(Closure)を使って実装
8 コードを動かしてみる • git ◦ https://github.com/kakky-hacker/algorithm_sandbox • command ◦ cd
genetic_algorithm ◦ python sample/knapsack.py ▪ 以下のナップザック問題を解く • 値段 = [100, 200, 650, 1100, 2100, 3300] • 嬉しさ = [2, 5, 16, 32, 64, 105] • 所持⾦ = 40000
9 PythonのGAフレームワーク • DEAP ◦ スター数がこの3つの中で⼀番多い(2024/08/23時点) ◦ https://github.com/DEAP/deap • Platypus
◦ 前に使ったことがあったので久しぶりに覗いたら最後のcommitが6年前だった.. ◦ https://github.com/andyrimmer/Platypus • pymoo ◦ 多⽬的最適化に特化しているらしい ◦ https://github.com/anyoptimization/pymoo
10 Thank you