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
ShibaNyan
September 10, 2018
Programming
0
1.8k
遺伝的アルゴリズムでシフト組みを自動化した話
BitValley2018 AfterPartyのLTでお話しました.
当番のシフトを組むのに時間がかかりすぎるという問題を,遺伝的アルゴリズムを使ってLINE BOTに実装することで解決しました.
ShibaNyan
September 10, 2018
Tweet
Share
More Decks by ShibaNyan
See All by ShibaNyan
証明写真を30円で作る
shiba6v
0
870
IPythonマジックコマンドを作る
shiba6v
1
1.6k
畳み込みニューラルネットワーク(CNN)の判断根拠の可視化手法 (20分トーク用)
shiba6v
1
1k
Other Decks in Programming
See All in Programming
Laravel や Symfony で手っ取り早く OpenAPI のドキュメントを作成する
azuki
2
120
みんなでプロポーザルを書いてみた
yuriko1211
0
280
エンジニアとして関わる要件と仕様(公開用)
murabayashi
0
300
受け取る人から提供する人になるということ
little_rubyist
0
250
TypeScript Graph でコードレビューの心理的障壁を乗り越える
ysk8hori
2
1.1k
CSC509 Lecture 11
javiergs
PRO
0
180
Figma Dev Modeで変わる!Flutterの開発体験
watanave
0
140
3 Effective Rules for Using Signals in Angular
manfredsteyer
PRO
0
120
TypeScriptでライブラリとの依存を限定的にする方法
tutinoko
3
690
Generative AI Use Cases JP (略称:GenU)奮闘記
hideg
1
300
リアーキテクチャxDDD 1年間の取り組みと進化
hsawaji
1
220
3rd party scriptでもReactを使いたい! Preact + Reactのハイブリッド開発
righttouch
PRO
1
610
Featured
See All Featured
Dealing with People You Can't Stand - Big Design 2015
cassininazir
364
24k
Building Adaptive Systems
keathley
38
2.3k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.3k
10 Git Anti Patterns You Should be Aware of
lemiorhan
655
59k
Building a Scalable Design System with Sketch
lauravandoore
459
33k
Building a Modern Day E-commerce SEO Strategy
aleyda
38
6.9k
VelocityConf: Rendering Performance Case Studies
addyosmani
325
24k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
506
140k
The Cult of Friendly URLs
andyhume
78
6k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
0
100
Stop Working from a Prison Cell
hatefulcrawdad
267
20k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
26
1.4k
Transcript
遺伝的アルゴリズムで シフト組みを自動化した話 BitValley 2018 AfterParty LT
自己紹介 • シバニャン • 京都大学工学部4回生 • Twitter: @_6v_ • CAMPHOR-
当番のシフト • 30コマ,約30人のシフト組み • 1コマに1人割り当てる
シフト決定の流れ 調整サービス シフト組み シフト発表 • 調整サービスを利用してシフトを提出してもらう • 手動でシフト組み • グループLINEで完成したシフトを発表
シフト組みの難しさ • 30コマ,約30人のシフト組み • 30^30 通り(≒2×10^44)
シフト組みの難しさ • 30コマ,約30人のシフト組み • 30^30 通り(≒2×10^44) 2時間かかる・・・ 自動化したい・・・
シフト組みの課題 • 同じ人が2回入らないといけない場合がある • 2回入る場合は日時が離れている方が良い • △,×を考慮するべき など・・・
シフト組みの課題 • 同じ人が2回入らないといけない場合がある • 2回入る場合は日時が離れている方が良い • △を考慮するべき など・・・
遺伝的アルゴリズムでやる シフトを遺伝子に見立てて,生物が交叉,突然 変異,自然淘汰によって進化するようにシフトを 改良していく [(枠1),(枠2),(枠3),…,(枠30)] 例) [(Gさん),(Eさん),(Nさん),…,(Eさん)] [(Aさん),(Lさん),(Gさん),…,(Oさん)]
遺伝的アルゴリズムの説明 • シフト表をランダムに30パターン生成 ↓ • シフト表の良さを評価 ↓ • 評価が良かったシフト6個残して後は消す ↓
• 交叉,突然変異させて30個に増やす 200ループ
遺伝的アルゴリズムの説明 • シフト表をランダムに30パターン生成 200ループ [(Gさん),(Eさん),(Nさん),…,(Eさん)] [(Aさん),(Lさん),(Gさん),…,(Oさん)] … (30パターン) [(Rさん),(Aさん),(Nさん),…,(Dさん)]
遺伝的アルゴリズムの説明 • シフト表をランダムに30パターン生成 • シフト表の良さを評価 200ループ [(Gさん),(Eさん),(Nさん),…,(Eさん)] : 300点 [(Aさん),(Lさん),(Gさん),…,(Oさん)]
: 100点 … (30パターン) [(Rさん),(Aさん),(Nさん),…,(Dさん)] : 50点
遺伝的アルゴリズムの説明 • シフト表をランダムに30パターン生成 • シフト表の良さを評価 • 評価が良かったシフト6個残して後は消す 200ループ [(Gさん),(Eさん),(Nさん),…,(Eさん)] :
300点 [(Aさん),(Lさん),(Gさん),…,(Oさん)] : 100点 … (6パターン)
遺伝的アルゴリズムの説明 • シフト表をランダムに30パターン生成 • シフト表の良さを評価 • 評価が良かったシフト6個残して後は消す • 交叉,突然変異させて30個に増やす 200ループ
[(Gさん),(Eさん),(Nさん),…,(Eさん)] [(Aさん),(Lさん),(Gさん),…,(Oさん)] [(Aさん),(Eさん),(Nさん),…,(Oさん)] … (30パターン)
遺伝的アルゴリズムの説明 • シフト表をランダムに30パターン生成 • シフト表の良さを評価 • 評価が良かったシフト6個残して後は消す • 交叉,突然変異させて30個に増やす 200ループ
[(Gさん),(Eさん),(Nさん),…,(Eさん)] [(Aさん),(Lさん),(Gさん),…,(Oさん)] [(Aさん),(Eさん),(Nさん),…,(Oさん)] [(Gさん),(Eさん),(Nさん),…,(Tさん)] … (30パターン)
遺伝的アルゴリズムの説明 • シフト表をランダムに30パターン生成 ↓ • シフト表の良さを評価 ↓ • 評価が良かったシフト6個残して後は消す ↓
• 交叉,突然変異させて30個に増やす 200ループ
遺伝的アルゴリズムの説明 • シフト表をランダムに30パターン生成 ↓ • シフト表の良さを評価 ↓ • 評価が良かったシフト6個残して後は消す ↓
• 交叉,突然変異させて30個に増やす 200ループ 大事なのはここ! 評価する式を立てる
シフト組みの課題 より • 同じ人が2回入らないといけない場合がある • 2回入る場合は日時が離れている方が良い • △,×を考慮するべき
シフト組みの課題 より • 同じ人が2回入らないといけない場合がある →同じ人が2回入ったら 100点 を減らす • 2回入る場合は日時が離れている方が良い →(離れている日数)×1点
を加える • △,×を考慮するべき →△一個につき10000点,×一個につき1000000 点 を減らす
シフト組みの課題 より • 同じ人が2回入らないといけない場合がある →同じ人が2回入ったら 100点 を減らす • 2回入る場合は日時が離れている方が良い →(離れている日数)×1点
を加える • △,×を考慮するべき →△一個につき10000点,×一個につき1000000 点 を減らす 評価式を追加するだけで, 簡単にシフトの決め方を 変えられる!
BOTにして 使ってみる
まとめ • 遺伝的アルゴリズムを使うと,いい感じのシフ トが組める • シフトの組み方の変更が簡単 • BOTにすると非エンジニアも使えて便利