進化計算手法を用いた 看護師勤務表の自動生成システム 立命館大学 情報理工学部 助手 串田 淳一 知能情報学科 立命館大学 情報理工学部 教授 亀井 且有 知能情報学科 1 研究背景 ナーススケジューリング問題(NSP) 病院などの医療施設に勤める看護師の 勤務スケジュールを一定の制約の下で決定する問題 現状 • 作成に多大な労力と時間を費やしている • 自動化への要求 ⇒ 普及していない • 企業の自動作成ソフト ⇒ 6，7割の満足度 （ユーザの要求を反映しにくい） より解探索能力の高いアルゴリズムの開発 ユーザの要求を伝えるための対話機構の開発 （ユーザ⇔システム） 2 ナーススケジューリング問題 ナース数を縦の行、勤務日数を横の行に表わし、 下記のとおり各セルにシフトの種類を割り当てる問題 個人 スキル 名前 ベテラン Aさん Bさん Cさん Eさ ん Fさ ん Gさん ベテラン 中堅 中堅 新人 新人 1 日 準 2 準 日 準 深 日 深 日数 3 4 5 日 日 日 日 準 深 日 日 日 深 準 日 日 深 3 2 2 7 準 深 日 準 日 日 3 2 2 3 2 2 … 日 準 深 休 3 3 3 3 4 3 4 3 3 2 2 3 2 2 2 2 2 2 6 6 6 6 6 6 … 1日 日 深 準 6 準 深 日 準 3 2 2 3 2 2 3 2 2 3 2 2 NSPにおける制約条件 個人のスケジュール ・決められた勤務回数を守る ・無理のない勤務パターン （例：夜勤→日勤は避ける） １日のスケジュール ・決められた勤務人数を守る ・スキルバランスの維持 （例：新人とベテランをペアにする） これらを考慮しながら最適な勤務表を生成→多目的最適化問題 3 新技術の基となる研究成果・技術 最適化アルゴリズム (NSPでの解を探すための手法) Differential Evolution (DE) 生物進化に着想を得た進化計算の一手法 -実数値関数のための最適化手法 DEの特徴 ・制御パラメータが少なく設定が容易 ・他の進化戦略と比べ収束が早く頑強 扱いやすく探索能力が高い最適化アルゴリズム -1995年にStorn, Priceにより提案 看護師勤務表の自動生成システムへの応用 4 Differential Evolution (DE) 生物進化の仕組みを工学的にモデル化した手法 適応度 -確率的な直接探索法 -解集団を用いた多点探索 初期世代集団の生成 適応度計算 親個体の選択 適応度が高い個体を親として選択 子の生成 親は交叉，突然変異によって子を生成 （遺伝演算） 制御パラメータ： 個体数，スケーリングファクタ(S)，交叉率(CR) 5 DEのNSPへの適用 ・決定変数および制約条件の選定：解空間の設定 ・最小化（最大化）すべき評価関数の設定 （個体がどのくらい優秀かを決定する関数） ・コーディング方法の決定 問題の解候補を遺伝子表現（整数の列）する 1 0 1 4 2 遺伝子型（整数列） 適応度 0 評価関数 コーディング 解空間の設定 解：表現型 6 従来技術とその問題点 従来の最適化アルゴリズム ・遺伝的アルゴリズム（GA） ・共存型遺伝的アルゴリズム（CGA） GA 進化計算 コーディング方法 GAを適用した際の特徴 表一つを1個体として表現 個体長が長く，遺伝演算で 致死遺伝子が発生 （必要な制約を満たさない個体） 勤務者が足りない・多すぎるなど CGA 致死遺伝子は抑制できるが多様 な解が生成されにくい 1 … … CGA 2 3 4 … j … n nurse1 nurse2 nurse3 … … … … … i … 日 1 3 4 … j … n 看護 日 12 数 看護 日 2 3 4 … …j … …n 師nurse 数 1 1 2 3 4 j 看護 n 師nurse 1 2 3 4 … j … n 1数 nurse 師nurse 2 1 nursenurse 2 1 nursenurse 3 2 nurse3nurse 2 nurse3 nurse3 i i i nursem i nursem nursem nursem … GA 表の一部（個人のスケジュール） を1個体として表現 … nursem 7 新技術の特徴・従来技術との比較 順序表現を用いたコーディング方法を提案 表一つを1個体として表現 •DEの遺伝操作を行っても致死遺伝子が生まれない （各日の必要人数は常に守られる） •遺伝子長は各日の必要勤務者の合計 →GAよりも少ない遺伝子長でスケジュールを表現可能 •3交代制以外の勤務においても適用可能 8 勤務表自動生成システムの構成 病院の勤務体制 看護師の要望 NSPのモデル化 NSPの問題設定 (看護師数，制約条件) 最適化アルゴリズム Differential Evolution DEによる解探索 インタフェースを通じてユーザが制御 問題の解を求める （最適な勤務表を出力） 9 評価関数 NSPの制約条件→性質から 7つの評価項目に分類 評価関数 F1 F2 F3 F4 評価関数 F5 F6 F7 (1) (2) (3) (4) 個人に関する評価項目 勤務パターン負荷の軽減 禁止パターンの低減 必要日数の確保 勤務間隔の均等化 各日に関する評価項目 (5) 必要人数の確保 (6) グループ必要人数の確保 (7) 看護の質の維持 必ず満たす必要あり 初期個体集団から 常に満たされる 評価関数の値＝ペナルティ(制約違反)の数 最小化問題となるよう定式化 （すべてのFの値が小さいほど良い表） 10 評価関数の設定例 例：必要日数の確保 日:11∼12，準:3~4, 深:3~4 名前 1 Aさん 日 準 日 Bさん 準 日 日 日 2 3 4 5 6 各勤務の合計 7 日 深 9 6 2 11 11 3 2 12 12 4 5 11 日 9 3 2 12 8 1 2 11 12 4 2 9 日 準 準 深 深 準 Cさん 準 準 深 日 日 日 Dさん 深 日 日 深 準 Eさん 日 準 日 日 準 Fさん 深 日 深 準 日 深 深 … 準 準 深 休 0+0+2+2=4 全員のペナルティの合計 =評価値 例：勤務パターン負荷の軽減 勤務パターン評価値（３日間） 2+1+2+0=5 … 30 29 ペナルティ (上限・下限との差) 4×4×4 = 64 通り 勤務パターン 評価値(ペナルティ) 最優先パターン 0点 「日深準」 「深休休」 優先パターン 1点 「準休日」 「休日準」 妥協パターン 2点 「日準準」 「休準準」 禁止パターン 10点 「休休深」 「準日休」 例 各個人のパターンの ペナルティを算出 11 NSPの目的関数 ３つの目的関数を設定 ⇒ 本問題の目的：H1,H2,H3の最小化 H1= 勤務パターン負荷度合の軽減+勤務間隔の均等化 H2= 必要日数の確保+禁止パターンの低減 （→0） H3= 看護婦の質 最適解との距離 distance = H , H = ( H 1 , H 2 , H 3 ) 本問題の目的： distanceが最小となる解を求める H2 H3 H1 最適解 (全ての制約を満たす表) 12 解の改善方法 親より優れた子が生成された→世代交代 H1が改善 両目的が改悪 H2 子 子 H2 子 改善の方向 親 子 子 子 H2が改善 H1 H1かH2のどちらかが改善されていれば 世代交代を行う （親を削除→子を選択） H1 世代交代の条件を緩和 →多様性の維持 13 初期スケジュール 看護師：23人，日数：一ヶ月 チーム： A/B，スキルレベル：ベテラン，中堅，新人 (10段階) 希望休暇：希，研修：研，会議：会 14 最適解との距離 ・2目的： H1, H2の最小化 ・3目的(易) ： H1, H2, H3の最小化 ・3目的(難) ： H1, H2, H3の最小化 (抑止パターンを追加) 1600 DEパラメータ 個体数50 S=0.35 CR=0.9 Pm=0.01 1400 最適解までの距離 1200 1000 3目的(難) 800 3目的(易) 600 2目的 400 200 0 0 1000 2000 3000 4000 5000 世代 6000 7000 8000 9000 10000 15 システムの出力例 3目的(難)での最良解 日勤：空白，準夜勤：準，深夜勤：深 16 ユーザによる操作 スライドバーで 解探索の方向を制御 個体集団 個体の進化の方向を指定 H1を重視 H2を重視 DE+ユーザ制御 =ユーザの求める解を効率的に探索 17 想定される用途 ・病院、医療機関の労務管理 ・交代制工場勤務等、複雑な勤務体系を布いて いる職場の勤務管理 提案システムにより 満足度の高い勤務表の作成が可能となれば →勤務表作成者の負担の軽減 →看護師の労働条件の改善 18 実用化に向けた課題 現在の状況 ・簡易的なインタフェースの構築 ・2目的，3目的の簡略化したNSPにおいて性能を検証 １．病院を対象としたアンケート調査，聞き取り調査 →制約条件を分析しNSPのモデル化を行う ２．パラメータの検証 →問題のサイズに応じた最適な制御パラメータを分析 ３．使いやすいインタフェースの開発 →初期条件や制約の入力など，PC初心者でも扱えるような設計 19 企業への期待 •NSPモデル化のための医療機関へのアンケート調査 •解探索アルゴリズムの高速化 •インタフェースの開発 共同研究先を探しています 20 本技術に関する知的財産権 • 発明の名称 ：スケジューリング装置、コン ピュータプログラム、及びデータ • 出願番号 ：特願2010-208417 • 出願人 ：学校法人立命館 • 発明者 ：串田 淳一、亀井 且有 21 産学連携の経歴 2004年 ソフトウェア関連企業との共同研究実施 ⇒特許技術移転 「ナーススケジューラV4.0」販売 22 お問い合わせ先 立命館大学 研究部 理工リサーチオフィス 山本 淳一 ＴＥＬ 077-561-2802 ＦＡＸ 077-561-2811 e-mail [email protected] 23
© Copyright 2024 ExpyDoc
