スケジューリング装置、コンピュータプログラム、及びデータ
【課題】複数の看護師のスケジュール全体を一つの個体として扱いつつも、致死遺伝子となるスケジュールの発生を防止する。
【解決手段】本発明のスケジューリング装置では、スケジューリングデータを複数個記憶する記憶部２０と、スケジューリングデータを最適化する最適化処理を行う処理部１０と、を備えている。前記スケジューリングデータは、日毎の各看護師の勤務形態を規定した部分コードを複数有している。部分コードは、要素として看護師特定値を有しており、要素の順位が看護師の勤務形態を示している。看護師特定値は、要員リストに基づく順序表現で表されている。
【解決手段】本発明のスケジューリング装置では、スケジューリングデータを複数個記憶する記憶部２０と、スケジューリングデータを最適化する最適化処理を行う処理部１０と、を備えている。前記スケジューリングデータは、日毎の各看護師の勤務形態を規定した部分コードを複数有している。部分コードは、要素として看護師特定値を有しており、要素の順位が看護師の勤務形態を示している。看護師特定値は、要員リストに基づく順序表現で表されている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スケジューリング装置、コンピュータプログラム、及びデータに関するものである。
【背景技術】
【０００２】
従来より、所定の集団に属する各要員のスケジュールを最適化するスケジューリング問題が、一般に知られている。スケジューリング問題として代表的なものに、ナーススケジューリング問題（Ｎｕｒｓｅ Ｓｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ；ＮＳＰ）がある。ＮＳＰでは、要員は看護師であり、一定期間（例えば、１月間）における各日の看護師の勤務形態（日勤、準夜勤、深夜勤、休日）を示すスケジュール表を最適化する問題となる。
【０００３】
スケジューリング問題を、遺伝的アルゴリズムに代表される進化的アルゴリズム用いて解く試みが、従来より行われている。例えば、特許文献１には、ＮＳＰなどのスケジューリング問題を、遺伝的アルゴリズム（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ；ＧＡ）を用いて解決するスケジューリング方法が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１４９１４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明者らは、スケジューリング問題における最適解（準最適解）を効率的に求めるために、Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎ（ＤＥ）とよばれる最適化方法を用いるという着想を得た。ＤＥは、ＧＡと同様に進化的アルゴリズムである。ＤＥでは、（１）探索空間内にランダムに複数の初期個体（解）を生成しておく、（２）すべての個体を評価する、（３）親個体から新しい解（子個体）を生成する（４）子個体が親より優れていれば親個体を削除して子個体を残す、という４つの工程を有する。
ＤＥでは、（２）〜（４）を繰り返すことで、複数の個体（個体群）の世代交代を生じさせて個体を進化させることで解を探索する。
【０００６】
ここで、スケジューリング問題にＤＥやＧＡを適用する場合、個体をどのように表現（コーディング）するかが問題となる。スケジューリング問題において、最適化したいのは、複数の要員の所定期間内のスケジュール表である。したがって、一つのスケジュール表を一つの個体とすることが考えられる。
しかし、スケジュール表に対応する個体同士において交叉の操作を行うと、致死遺伝子が生じ易いという問題がある。
【０００７】
例えば、スケジューリング問題において、重要な制約として、役割毎の「必要人数の確保」が挙げられる。ＮＳＰの場合、各日において、日勤、準夜勤、深夜勤という勤務形態（役割）毎に必要とされる人数が予め決まっている。ところが、各日において勤務形態ごとの必要人数が確保できているスケジュール表であっても、そのスケジュール表自体を個体とすると、交叉が行われることにより、必要人数が確保できなくなり、致死遺伝子となる可能性がある。
【０００８】
特許文献１では、致死遺伝子の発生を防止するため、要員全員のスケジュールではなく、要員一名のスケジュールを一つの個体とし、個体の集合で一つのスケジュール表を構成し、個体間で交叉等の遺伝的操作を行う共存型ＧＡが記載されている。
しかし、ＤＥでは、そのアルゴリズム上、一つのスケジュール表を一つの個体とすることが望ましい。したがって、ＤＥを適用する上では、共存型ＧＡのように要員一名のスケジュールを一つの個体とするのではなく、複数要員のスケジュール全体を一つの個体とすべきである。
【０００９】
そこで、本発明は、複数要員のスケジュール全体を一つの個体として扱いつつも、致死遺伝子となるスケジュール（個体）の発生を防止することを目的とする。
【課題を解決するための手段】
【００１０】
（１）本発明は、複数の要員のスケジューリングを行うスケジューリング装置であって、複数の要員それぞれの役割を所定の期間内において単位期間毎に規定したスケジューリングデータを複数個記憶する記憶部と、前記記憶部に記憶されたスケジューリングデータを親個体とする世代交代を、進化的アルゴリズムに従って繰り返させることで、前記記憶部に記憶されたスケジューリングデータを最適化する最適化処理を行う処理部と、を備え、前記スケジューリングデータは、単位期間毎の各要員の役割を規定した部分コードを複数有して構成され、各単位期間に対応する前記部分コードは、当該単位期間において最適化処理の対象となる要員の数に対応した数の要素を有するリストとして構成され、さらに前記部分コードは、当該部分コードの各要素が要員を特定する要員特定値となっているとともに、当該部分コードの要素の順位が要員の役割を示しており、前記部分コードの要員特定値は、前記複数の要員のうち、前記部分コードにおいて先行する順位の要員特定値によって特定された要員を除外した要員リストにおける順位によって、要員を特定するものである、ことを特徴とするスケジューリング装置である。
【００１１】
（２）前記進化的アルゴリズムとしては、交叉の操作が行われるアルゴリズムを採用するのが好適である。
【００１２】
（３）より具体的には、前記進化的アルゴリズムは、Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎが好適である。
【００１３】
（４）前記処理部は、前記スケジューリングデータに対して突然変異の操作を行う突然変異処理部を備えるのが好ましい。
【００１４】
（５）要員リストの要素となる要員として、スケジューリングの対象である複数の要員のうち、単位期間において最適化処理の対象とならない要員を初期条件として設定する設定部を更に備えるのが好ましい。
【００１５】
（６）個体の優劣の決定に用いられる複数の目的関数それぞれの重要性の度合いをユーザが調整するためのインターフェース部を更に備え、前記処理部は、親個体と、親個体から進化的アルゴリズムに従って得られた子個体と、を比較して、優れた個体を次世代の個体として選択するよう構成されているとともに、個体間の優劣を複数の目的関数に基づいて決定するよう構成され、さらに、前記処理部は、個体の優劣を前記複数の目的関数に基づいて決定する際に、インターフェース部を介して調整された前記度合いに応じた重みを、前記複数の目的関数の値に乗じた上で、個体間の優劣を決定するのが好ましい。
【００１６】
（７）他の観点からみた本発明は、コンピュータを、前記（１）〜（６）のいずれか１項に記載のスケジューリング装置として機能させるためのコンピュータプログラムである。
【００１７】
（８）さらに他の観点からみた本発明は、複数の要員それぞれの役割を所定の期間内において単位期間毎に規定したスケジューリングデータを複数個記憶する記憶部と、前記記憶部に記憶されたスケジューリングデータを親個体とする世代交代を、進化的アルゴリズムに従って繰り返させることで、前記記憶部に記憶されたスケジューリングデータを最適化する最適化処理を行う処理部と、を備えて複数の要員のスケジューリングを行うスケジューリング装置として機能するコンピュータが、前記スケジューリングデータとして用いるデータであって、単位期間毎の各要員の役割を規定した部分コードを複数有し、各単位期間に対応する前記部分コードは、当該単位期間において最適化処理の対象となる要員の数に対応した数の要素を有するリストとして構成され、さらに前記部分コードは、当該部分コードの各要素が要員を特定する要員特定値となっているとともに、当該部分コードの要素の順位が要員の役割を示しており、前記部分コードの要員特定値は、前記複数の要員のうち、前記部分コードにおいて先行する順位の要員特定値によって特定された要員を除外した要員リストにおける順位によって、要員を特定するものである、ことを特徴とするデータである。
【発明の効果】
【００１８】
本発明によれば、複数要員のスケジュール全体を一つの個体として扱いつつも、致死遺伝子となるスケジュール（個体）の発生を防止することができる。
【図面の簡単な説明】
【００１９】
【図１】スケジューリング装置の機能ブロック図である。
【図２】スケジュール表の例を示す図である。
【図３】スケジューリング装置のスケジューリング処理を示すフローチャートである。
【図４】ＤＥ操作を示す概念図である。
【図５】ＤＥ操作によって生成される差分変異親ベクトルの説明図である。
【図６】交叉（ｅｘｐｏｎｅｎｔｉａｌ ｃｒｏｓｓｏｖｅｒ）の説明図である。
【図７】交叉（ｂｉｎｏｍｉａｌ ｃｒｏｓｓｏｖｅｒ）の説明図である。
【図８】探索空間における親個体及び子個体の分布を示す図である。
【図９】世代交代に伴う解探索範囲の変遷を示す図である。
【図１０】最適解との距離に関する説明図である。
【図１１】スケジューリングデータのデータ構造図である。
【図１２】スケジューリングデータの要員特定値の解釈の仕方の説明図である。
【図１３】（ａ）は順序表現の要員特定値を採用した場合の交叉を示し、（ｂ）は要員を直接的に特定した要員特定値を採用した場合の交叉を示す図である。
【図１４】実験結果１を示すグラフである。
【図１５】実験結果１における解探索範囲の変遷を示す図である。
【図１６】実験結果１における最適解に対応するスケジュール表である。
【図１７】実験結果２での個体群の解探索空間における配置を示す図である。
【図１８】実験結果２における準最適解に対応するスケジュール表である。
【図１９】実験結果３での個体群の解探索空間における配置を示す図である。
【図２０】実験結果３における準最適解に対応するスケジュール表である。
【図２１】実験結果４における最適解に対応するスケジュール表である。
【図２２】重みを調整することによる探索方向の制御の様子を示す図である。
【図２３】ＤＥにおける問題点の説明図である。
【図２４】パレートランクルーレット選択の説明図である。
【図２５】突然変異方法の比較結果を示す表である。
【図２６】スケジューリングデータの冗長性の説明図である。
【図２７】コーディング方法の比較結果を示す表である。
【発明を実施するための形態】
【００２０】
以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。
［１．スケジューリング装置の構成］
図１に示すスケジューリング装置１は、複数の要員（看護師）の所定期間のスケジューリングを生成し、そのスケジュールを出力するめのものである。スケジューリング装置１は、複数の要員それぞれの役割を単位期間毎（日毎）に規定したスケジューリングデータを個体として取り扱う。
【００２１】
図２は、複数の要員（スタッフ）の役割を、所定期間（図２では１４日）内の日毎に規定したスケジュール表の例を示している。図２では、要員の役割として、勤務形態の種別（日勤、準夜勤、深夜勤、休日）が規定されている。図２では、日勤は空欄で示し、準夜勤は「準」で示し、深夜勤は「深」で示し、休日は「休」で示した。なお、このスケジュール表をデータ化したスケジューリングデータの構造については、後述する。
【００２２】
本実施形態のスケジューリング装置１は、個体であるスケジューリングデータを、様々な制約の下で最適化し最良解（最適解または準最適解）となるスケジューリングデータを求める。本実施形態では、最適化処理のためのアルゴリズムとして、ＤＥ（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎ；差分進化）を採用する。ＤＥは、構成が簡単であり、パラメータが少なく、最適解への収束に優れ頑強であるという特徴を有する。
【００２３】
スケジューリング装置１は、コンピュータをスケジューリング装置として機能させるためのコンピュータプログラムを、コンピュータにインストールして構成されている。後述するスケジューリング装置１の機能は、コンピュータプログラムがコンピュータによって実行されることで発揮される。コンピュータは、処理装置、記憶装置、入出力装置などを有するものであり、例えば、パーソナルコンピュータを利用できる。なお、コンピュータプログラムは、ＣＤ−ＲＯＭなどの記録媒体に格納して流通させることができる。
【００２４】
図１は、スケジューリング装置１の機能ブロックを示している。スケジューリング装置１は、処理部１０、記憶部２０、初期条件設定部３０、調整用インターフェース部４０を備えている。
処理部１０は、ＤＥのアルゴリズムに従って、記憶部２０に記憶されている個体群の世代交代を繰り返して、個体の最適化を行うものである。
処理部１０は、初期個体群生成部１１と、ＤＥ操作部１２と、突然変異処理部１３と、個体評価部１４と、最良解更新部１５と、を備えている。記憶部２０は、個体群記憶２１と、最良解記憶部２２と、を備えている。
【００２５】
初期個体群生成部１１は、初期世代の個体群（例えば、３０個の個体群）となるスケジュールデータ群を生成して、それらの個体群を個体群記憶部２１に記憶させる。初期世代の個体群は、解の探索空間内においてランダムに決定して生成される。ただし、初期条件設定部３０によって、希望休暇、会議、研修の日程など、変更不可の日程が初期条件として設定されると、その初期条件を満足するようにスケジュールデータが生成される。なお、スケジュールデータは、交叉処理が行われて世代交代が生じても、一日の必要要員数、より具体的には、日勤、準夜勤、深夜勤といった勤務形態毎に要求される要員数が常に満足されるよう構成されている。
【００２６】
ＤＥ操作部１２は、ＤＥのアルゴリズムに従って、個体群記憶部２１に記憶されている現行世代の個体から次世代の個体を生成し、次世代の個体群を個体群記憶部２０に記憶させる。ＤＥのアルゴリズムの詳細については後述する。
突然変異処理部は、個体群記憶部２１に記憶されている個体について突然変異操作を行い、突然変異した個体を個体群記憶部２１に記憶させる。突然変異を行うことで、解（個体）が局所解から脱出し易くなる。個体に対して突然変異を行うための条件及びその方法の詳細については後述する。
【００２７】
個体評価部１４は、個体群記憶部２１に記憶されている個体それぞれの評価を行うものである。評価は、個体の最適解からの距離（ユークリッド距離）を求めることで行われる。
最良解更新部１５は、世代交代によって得られた個体のいずれかの最適解までの距離が、最良解記憶部２２に記憶されているそれまでの最良解の最適解までの距離よりも小さい場合には、最良解記憶部２２に記憶されている解（個体）を、より距離の小さい個体で置き換えるためのものである。
【００２８】
個体群記憶部２１は、処理部１０における処理の対象となる個体群（現行世代の個体群）を記憶するためのものである。個体群記憶部２１には、初期個体群生成部１１によって生成された個体群（初期世代の個体群）が記憶されるとともに、ＤＥ操作部１２によって世代交代した個体群（次世代の個体群）が記憶される。また、突然変異処理部１３によって突然変異処理された個体も個体群記憶部２１に記憶される。
最良解記憶部２２は、世代交代にともなって得られた過去の全個体のうち、最適解までの距離が最も小さい個体（最良解）を記憶するためのものである。世代交代を何度か繰り返した後に最良解記憶部２２に記憶されている解（最適解又は準最適解）が、スケジューリング装置１の出力となる。
【００２９】
初期条件設定部３０は、初期世代の個体群が生成される際に、希望休暇、会議、研修の日程など、変更不可の日程を初期条件として設定するためのものである。初期条件は、ユーザが任意に設定することができる。
調整用インターフェース部４０は、解の探索方向をユーザが調整するためのインターフェースである。解の探索方向をユーザが調整できるため、ユーザの満足度の高い解を発見することが可能となる。なお、初期条件設定部３０及び調整用インターフェース部４０については、後述する。
【００３０】
［２．スケジューリング装置の処理］
図３は、上記スケジューリング装置１の処理の流れを示している。まず、初期個体群生成部１１によって、所定数の初期個体の生成が行われる（ステップＳ１）。この際、初期条件設定部３０によって設定された初期条件があれば、初期条件を満たす初期個体が生成される。
【００３１】
続いて、個体評価部１４が、個体群記憶部２１に記憶されている各個体の評価を行う（ステップＳ２）。また、評価の結果、全個体の中において、最良解記憶部２２に記憶されているそれまでの最良解の最適解までの距離よりも小さい距離を持つ個体が存在する場合、最良解更新部１５は、最良解記憶部２２に記憶されている解（個体）を、より距離の小さい個体で置き換える。
また、評価の結果、最適解が発見された場合（最適解までの距離＝０の場合）、または、所定の終了条件（繰り返し回数が所定回数に達した、等）に至った場合には、スケジューリング装置１は処理を終了する（ステップＳ３）。
【００３２】
ステップＳ３において処理終了とならなかった場合、ＤＥ操作部１２は、個体群記憶部２１に記憶されている個体群の世代交代をＤＥのアルゴリズムに従って行う（ステップＳ４）。また、突然変異処理部１３は、個体群記憶部２１に記憶されている個体群に対する突然変異が必要であるか否かの判断を行い（ステップＳ５）、突然変異が必要な場合には、個体群に対する突然変異操作を行う（ステップＳ６）。なお、突然変異操作は省略してもよい。
上記ステップＳ２〜Ｓ６までの処理は、ステップＳ３において処理終了と判断されるまで繰り返し実行される。
【００３３】
［３．ＤＥ操作（ＤＥによる世代交代）］
図４は、ＤＥのアルゴリズムによって、現行世代の個体群を構成する複数の個体（ｎｐ個の個体）から、次世代の個体群を構成する複数の個体（ｎｐ個の個体）を生成する方法を示している。
【００３４】
ＤＥ操作による世代交代は、基本的に、（１）複数の親個体（現行世代の複数の個体）から、子個体を生成する、（２）親と子を比較する、（３）優れている方を次世代の個体として選択する、という３ステップで実行される。
【００３５】
［３．１ 子個体の生成］
子個体ｕの生成のため、ＤＥ操作部１２は、現行世代の複数の個体から、ＤＥ操作の対象となる一つの個体（対象親個体）ｘｉを選択するとともに、残りの現行世代の複数の個体から３つの個体ｘ１ｐ，ｘ２ｐ，ｘ３ｐをランダムに選択する。
【００３６】
続いて、ＤＥ操作部１２は、３つの個体ｘ１ｐ，ｘ２ｐ，ｘ３ｐを用いて、差分変異親個体ｖを生成する。
３つの個体ｘ１ｐ，ｘ２ｐ，ｘ３ｐそれぞれをベクトルとみなした場合、図５にも示すように、差分変異親個体（差分変異親ベクトル）ｖは、ベースベクトルｘ１ｐに対して、差分生成ベクトルｘ２ｐ，ｘ３ｐ間の差分にスケーリング係数（ｓｃａｌｉｎｇ ｆａｃｔｏｒ）を乗じたものを加えたものとなる。
【００３７】
さらに、ＤＥ操作部１２は、差分変異親個体ｖと対象親個体ｘとを用いて交叉操作を行って、子個体ｕを生成する。
交叉は、図６に示すように指数関数的に減少する確率で遺伝子交換を行う交叉（ｅｘｐｏｎｅｎｔｉａｌ ｃｒｏｓｓｏｖｅｒ）でもよいし、図７に示すように、各要素ごとに独立に一定の確率ＣＲで差分変異親の遺伝子を用いる交叉（ｂｉｎｏｍｉａｌ ｃｒｏｓｓｏｖｅｒ）でもよい。
なお、図６及び図７では、対象親個体（ベクトル）ｘ、子個体(ベクトル)ｕ，差分変異親個体（ベクトル）ｖを構成する個々の遺伝子を、ｘｊ，ｕｊ，ｖｊ（ｊは遺伝子座を示す番号。図６及び図７では、ｊ＝１〜１２）で示した。
【００３８】
図６に示す交叉（ｅｘｐｏｎｅｎｔｉａｌ ｃｒｏｓｓｏｖｅｒ）では、（１）まず、交叉開始位置（Ｓｔａｒｔ ｐｏｉｎｔ）となる遺伝子座ｊを決定する（図６ではＳｔａｒｔ ｐｏｉｎｔ＝５）。
（２）次に、交叉開始位置から、順次、それぞれの遺伝子座（ｊ＝５，６，７，８，・・・）について、０から１の間の乱数値を発生させる。図６では、遺伝子座ｊの乱数値をｒａｎｄｊで示した。
（３）そして、交叉開始位置からｒａｎｄｊが連続してＣＲ以下となる区間（図６では、遺伝子座ｊ＝５〜９の区間）については、子個体ｕの遺伝子ｕ５〜ｕ９として、差分変異親個体の遺伝子ｖ５〜ｖ９を用いる。残りの区間（図６では、遺伝子座ｊ＝１〜４及び１０〜１２）については、子個体ｕの遺伝子ｕ１〜ｕ４，ｕ１０〜ｕ１２として、対象親個体ｘの遺伝子ｘ１〜ｘ４，ｘ１０〜ｘ１２を用いる。以上の処理によって子個体ｕが生成される。
【００３９】
図７に示す交叉（ｂｉｎｏｍｉａｌ ｃｒｏｓｓｏｖｅｒ）では、図中に示す式に従って、子個体ｕの遺伝子ｕｊとして、対象親個体ｘの遺伝子ｘｊを用いるか、差分変異親個体ｖの遺伝子ｖｊを用いるかを決定する。具体的には、まず、子個体ｕの各遺伝子（要素）ｕｊ毎に、０〜１の間の乱数値ｒａｎｄｊ［０，１］を求める。この乱数値ｒａｎｄｊ［０，１］が、所定の確率ＣＲ以下であれば、子個体ｕの遺伝子ｕｊとして、差分変異親個体ｖｊの遺伝子ｖｊを用い、そうでなければ、対象親個体の遺伝子ｘｊを用いる。
【００４０】
なお、子個体ｕの遺伝子のうち、一つ（１次元）の遺伝子（要素）については、必ず差分変異親のものを用いることを保証するため、遺伝子座ｊが特定の値ｊｒである場合には、乱数値ｒａｎｄｊ［０，１］にかかわりなく、子個体ｕの遺伝子ｕｊとして、差分変異親個体ｖｊの遺伝子ｖｊが用いられる。
【００４１】
ＤＥでは、差分変異親を用いた交叉操作が行われるため、図８に示すように、探索空間でみたときに、現行世代の親個体の集団が属する範囲よりも、子個体の集団が属する範囲の方が広くなる。つまり、ＤＥでは、現行世代よりも広い範囲で解（個体）の探索を行えるため、局所解に陥りにくく、適切な解探索が行える。
そして、ＤＥでは、図９に示すように、世代交代を繰り返すと、個体間の差分が小さくなるため、個体集団の存在領域も徐々に収束していき、解の探索範囲が狭くなる。つまり、ＤＥでは、世代交代を繰り返すと、大域探索から局所探索へシフトしていく。これにより、ＤＥでは、局所解に陥ることを避けつつ最適解に近づくことが可能である。
【００４２】
［３．２ 親個体と子個体の比較及び次世代の選択］
ＤＥ操作部１２は、現行世代の対象親個体ｘｉと、生成された子個体ｕと、を比較し、優れているほうの個体を、次世帯の親個体ｘｉとして選択する。ＤＥ操作部１２は、個体群記憶部２１に記憶されている現行世代の親個体ｘｉを、選択された次世代の親個体に、置換する。
【００４３】
ＤＥ操作部１２は、個体ｘｉ，ｕ間の優劣を、複数の目的関数を用いて決定する。本実施形態では、次の３つの目的関数Ｈ１，Ｈ２，Ｈ３を定義義する。これらの目的関数の値は、小さいほどよく、最適解であれば、Ｈ１＝０，Ｈ２＝０，Ｈ３＝０となる。
ただし、個体の優劣の判断に関しては、説明の簡略化のため、これらの目的関数のうち、２つの目的関数Ｈ１，Ｈ２を用いた場合について説明する。なお、目的関数Ｈ１，Ｈ２，Ｈ３の詳細については後述する。
【数１】
【００４４】
次世代の個体ｘｉとして、生成された子個体ｕが選択される場合（実質的な世代交代が生じる場合）の条件の例（条件１）を、以下に示す。
【数２】
上記条件１において、Ｈ１Ｃは生成された子個体についての目的関数Ｈ１の値、Ｈ１Ｐは親個体についての目的関数Ｈ１の値、Ｈ２Ｃは生成された子個体ｕについての目的関数Ｈ２の値、Ｈ２Ｐは親個体についての目的関数Ｈ２の値である（下記条件２，３についても同様）。
上記条件１では、両目的関数Ｈ１，Ｈ２の双方について、対象親個体ｘｉよりも、子個体ｕの方が改善されていることが、子個体ｕが、次世代の個体として選択される条件となっている。この場合、両目的関数Ｈ１，Ｈ２を改善できる子個体ｕが生成される確率が低くなるため最適解発見までに時間がかかる。
【００４５】
また、次世代の個体ｘｉとして、生成された子個体ｕが選択される場合（実質的な世代交代が生じる場合）の条件の他の例（条件２）を、以下に示す。
【数３】
上記条件２では、目的関数Ｈ１，Ｈ２のうち、いずれか一方の目的関数が親個体ｘｉよりも改善されていれば、子個体ｕが次世代として選択される。条件２の場合、実質的な世代交代が行われるための制約が緩和されるため、個体が進化し易く、個体集団の多様性が維持され易いというメリットがある。
【００４６】
また、次世代の個体ｘｉとして、生成された子個体ｕが選択される場合（実質的な世代交代が生じる場合）の条件のさらに他の例（条件３）を、以下に示す。
【数４】
上記３では、２つの目的関数Ｈ１，Ｈ２それぞれに重みα，１−αを乗じたものの和を、個体の適応度とした上で、個体の適応度が、親個体よりも優れている場合に、子個体ｕが次世代として選択される。なお、個体の適応度は、小さいほど、優れている（最適解に近い）ことを示す。また、重みα，１−αは、各目的関数Ｈ１，Ｈ２それぞれの重要性の度合いを示しており、重要な目的関数ほど、重みを大きくすればよい。この重みは、調整用インターフェース部４０によって、ユーザによって調整可能であるが、その詳細は、後述する。
【００４７】
ＤＥ操作部１２は、上記のようなＤＥ操作は、現行世代の全個体（ｘ１〜ｘｎｐ）を対象親個体ｘｉとして行う。これにより、個体群２１に記憶されている全個体について、世代交代がなされる。
【００４８】
［４．多目的最適化］
本実施形態のスケジューリング装置１によって解かれるスケジューリング問題は、多目的最適化問題である。多目的最適化問題とは、目的関数が複数存在し、各目的関数値をひとまとめにせずに扱う問題をいう。
図１０に示すように、本実施形態では、最適化は、目的関数値Ｈ１，Ｈ２，Ｈ３に基づく最適解までの距離（ｄｉｓｔａｎｃｅ）が最小となる解（個体）を求めることである。なお、最適解は、Ｈ１＝０，Ｈ２＝０，Ｈ３＝０となり、距離＝０となる。
【００４９】
［４．１ ＮＳＰにおける評価関数］
以下、目的関数Ｈ１，Ｈ２，Ｈ３の元になる評価関数を説明する。
下記表１に示すように、ＮＳＰでは、その性質から、６つの評価項目を挙げることができ、各評価項目に応じた評価関数Ｆ１ｉ，Ｆ２ｉ，Ｆ３ｉ，Ｆ４ｉ，Ｇ１ｊ，Ｇ２ｊを定義する。
評価関数Ｆ１ｉ，Ｆ２ｉ，Ｆ３ｉ，Ｆ４ｉは、看護師ｉ個人に関する評価項目であり、評価関数Ｇ１ｊ，Ｇ２ｊは、１日に関する評価項目である。
【表１】
【００５０】
［４．１．１ 勤務パターンの負荷度合いの軽減］
表１における第１の評価項目「勤務パターンの負荷度合いの軽減」については、下記のように定式化される。
【数５】
【００５１】
上記式では、看護師ｉの勤務パターン評価値ａｉ，ｊの総和が、評価関数Ｆ１ｉの値となる。上記式中の勤務パターン評価値を、下記表２のように定義する。
【表２】
【００５２】
勤務パターンは、看護師ｉにおけるｊ日を含む連続する３日間の勤務形態の組み合わせである。表２において、「日」は、ある日の看護師の勤務形態が「日勤」であることを示し、「準」は、ある日の看護師の勤務形態が「準夜勤」であることを示し、「深」は、ある日の看護師の勤務形態が「深夜勤」であることを示し、「休」は、ある日の看護師の勤務形態が「休日」であることを示している。勤務パターンの評価値ａｉ，ｊは、勤務パターンに応じて、表２のように定義される。表２では、勤務負荷の少ない最優先パターンの評価値が最も小さく、勤務負荷の大きい禁止パターンの評価値が最も大きくなるようにして、勤務負荷が大きいほど制約条件が重くなるようにした。
【００５３】
［４．１．２ 必要日数の確保］
表１における第２の評価項目「必要日数の確保」については、下記のように定式化される。
【数６】
【００５４】
上記式では、看護師ｉが１月に各勤務形態を行う必要日数の上下限に違反する日数が評価関数Ｆ２ｉの値となる。ここで、必要日数とは、各看護師が１月に書く勤務形態を行う日数である。勤務形態毎の必要日数は、一般に、下記表３に示す通りになる。
【表３】
【００５５】
［４．１．３ 勤務日数間隔の均等化］
表１における第３の評価項目「勤務間隔の均等化」については、下記のように定式化される。
【数７】
【００５６】
上記式では、各看護師ｉに割り付ける日数の上下限を違反する日数が、評価関数Ｆ３ｉの値となる。例えば、休日は、評価対象期間ｈｋが５日間であり、休日を割り付ける上下限としては、評価対象期間の５日間において１〜５日となる。また、深夜勤は、評価対象期間ｈｋが７日であり、深夜勤を割り付ける上下限としては、評価対象期間の７日間において０〜３日となる。
【００５７】
［４．１．４ 禁止パターンの低減］
表１における第４の評価項目「禁止パターンの低減」については、下記のように定式化される。
【数８】
【００５８】
上記式では、禁止パターンの回数が、評価関数Ｆ４ｉの値となる。ここでは、禁止パターンとしては、２日間禁止パターンを用いる。２日禁止パターンとしては、例えば、看護師ｉの２日間の勤務形態の組み合わせが、「土日祝の日勤，深夜勤」、「研修，深夜勤」、「土日祝の日勤，土日祝の日勤」、又は「準夜勤，希望休暇」の組み合わせとなっている場合がある。
【００５９】
［４．１．５ 必要人数の確保］
表１における第５の評価項目の「必要人数の確保」に関し、ここでの必要人数とは、一日に各勤務形態で勤務する人数である。
【００６０】
【表４】
【００６１】
表４に示すように、例えば、準夜勤の必要人数は３人、深夜勤の必要人数は３人、平日の日勤の必要人数は１１〜１３人、土日祝の日勤の必要人数は３人である。一日に各勤務形態で勤務する人数の確保は、スケジューリングを行う上で最も重要な条件となる。本実施形態では、初期個体群生成部１１によって生成される個体は、すべて、必要人数の確保がなされたものとなり、世代交代が行われても、必要人数が確保された状態が維持される。つまり、必要人数の確保に関する評価関数Ｇ１ｊは、常に、Ｇ１ｊ＝０である。世代交代が行われても必要人数が確保されることについては、後述する。
【００６２】
［４．１．６ 看護の質の維持］
表１における第６の評価項目の「看護の質の維持」については、下記のように定式化される。
【数９】
【００６３】
看護の質の維持には、例えば、「深夜勤に新人は０〜１人で割り付ける」、「準夜勤にベテランは１〜２人で割り付ける」、「日勤にベテランは１〜２人で割り付ける」といった条件が必要とされる。上記式では、このような人数の上下限に違反する人数が、評価関数Ｇ２ｊの値となる。
【００６４】
［４．２ 目的関数の定義］
目的関数Ｈ１，Ｈ２，Ｈ３は、上記の６つの評価関数Ｆ１ｉ，Ｆ２ｉ，Ｆ３ｉ，Ｆ４ｉ，Ｇ１ｊ，Ｇ２ｊのうち、常に評価関数値＝０となるＧ１ｊを除いた６つの評価関数Ｆ１ｉ，Ｆ２ｉ，Ｆ３ｉ，Ｆ４ｉ，Ｇ２ｊによって定義される。
つまり、
Ｈ１＝Ｆ１ｉ＋Ｆ４ｉ＋Ｆ３ｉ
Ｈ２＝Ｆ２ｉ
Ｈ３＝Ｇ２ｊ
である。
【００６５】
［４．３ 個体の最適解からの距離］
個体評価部１４は、各個体の最適解からの距離を、目的関数Ｈ１，Ｈ２，Ｈ３を軸とするユークリッド空間における距離（ユークリッド距離）として算出することで、各個体の評価を行う。なお、目的関数Ｈ１，Ｈ２，Ｈ３は、３つすべてを用いる必要はなく、２つでもよい。また、目的関数は、上記のものに限られず、スケジュール問題の性質に応じて適切に設定すればよい。
【００６６】
［５．スケジューリングデータ］
以下、最適化処理の対象となるスケジューリングデータ（個体）のデータ構造を、定義する。本実施形態のスケジューリングデータは、図２に示すような２次元のスケジュール表を、遺伝子配列に類似した１次元のデータ配列（遺伝子型のスケジューリングデータ）で表現される。
【００６７】
図１１に示すようにスケジューリングデータは、スケジューリングの対象となる所定期間内のスケジューリングの単位期間の数に応じた数の部分コードを複数連結して構成されている。
図２のスケジュール表は、スケジューリングの単位期間が「１日」であり、スケジューリングの対象となる所定期間が「３０日」となっている。これに対応して、図１１のスケジューリングデータでは、各日に対応した部分コードが、３０日分設けられている。
【００６８】
各日の部分コードは、その部分コードに対応する日における、各要員（看護師）の役割（勤務形態）を規定した数値配列リスト（遺伝子コード）となっている。
この部分コードを構成する数値配列リストにおいては、リスト要素となる数値が、看護師を特定する看護師特定値（要員特定値）となっている。
【００６９】
また、部分コードを構成する数値配列リストにおける要素の順位（遺伝子座）は、看護師の勤務形態を示している。図１１において、１日目の部分コードは、順位１〜順位１１までを有しており、１１個の看護師特定値によって１１人の看護師の勤務形態を特定している。
具体的には、順位１〜順位５までは「日勤」を示しており、順位６〜順位８までは深夜勤を示しており、順位９〜順位１１までは準夜勤を示している。なお、部分コードで特定されていない看護師は、その部分コードに対応する日において休日である。このような順位と勤務形態との対応は、世代交代が生じても不変である。
【００７０】
図１１では、看護師特定値＝｛１０，６，３，２，１｝で特定される看護師が日勤であり、看護師特定値＝｛５，５，３｝で特定される看護師が深夜勤であり、看護師特定値＝｛４，２，１｝で特定される看護師が準夜勤であり、残りの看護師が休日である。
【００７１】
各日の部分コードは、表１の第５の評価項目「必要人数の確保」が満たされるように形成されている。各日において各勤務形態で勤務する看護師の人数の確保は、業務を適切に遂行する上で必要不可欠である。
そこで、部分コードでは、各勤務形態において必要とされる人数に応じた数の要素数が確保されている。必要人数が、日勤では５人、深夜勤では３人、準夜勤３人であり、その日におけるトータルの必要人数が１１人（最適化処理の対象となる要員の数）である場合、図１１のように、部分コードの総要素数は１１個となり、そのうち、日勤の要素数として５個、深夜勤の要素数として３個、準夜勤の要素数として３個が確保される。
【００７２】
なお、各勤務形態において必要とされる人数は、日によって異なることがあるため、部分コード毎に、各勤務形態に対応する要素数が異なっても良い。また、部分コード毎に、部分コード全体の要素数が異なっても良い。また、図１１の部分コードでは、休日である看護師の明示的な特定を省略しているが、休日である看護師を明示的に特定してもよい。
【００７３】
部分コードにおける要員特定値（看護師特定値）は、順序表現で要員（看護師）を特定する。順序表現では、全要員を示す要員リスト（順序リスト）を用いて、要員を特定する。具体的には、要員として、ａ，ｂ，ｃ，ｄ，ｅ，ｆが存在し、全要員数が６名の場合を想定する。この場合、基本の要員リスト＝｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝となる。
そして、図１２（ａ）に示すように、ある１日において、日勤にａ，ｃ，ｅを割り付け、深夜勤にｄを割り付け、準夜勤にｆを割り付ける場合、部分コードの総要素数は、５個であり、部分コード＝｛１，２，３，２，２｝となる。
【００７４】
図１２（ｂ）にも示すように、図１２（ａ）の部分コードにおいて、順位１の要員特定値（遺伝子コード）＝１は、要員ａを示している。この要員特定値＝１は、順序リストである要員リスト（基本要員リスト）＝｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝における要員ａの順序（位置）である「１」に対応したものである。
【００７５】
部分コードにおいて順位２の要員特定値（遺伝子コード）＝２は、要員ｃを示している。この要員特定値＝２は、部分コードにおいて先行する順位＝１の要員特定値によって特定された要員ａを、基本要員リストから除外した要員リスト（第１の縮減要員リスト）＝｛ｂ，ｃ，ｄ，ｅ，ｆ｝における要員ｃの順序（位置）である「２」に対応したものである。
【００７６】
部分コードにおいて順位３の要員特定値（遺伝子コード）＝３は、要員ｅを示している。この要員特定値＝３は、部分コードにおいて先行する順位＝１，２の要員特定値によって特定された要員ａ，ｃを、基本要員リストから除外した要員リスト（第２の縮減要員リスト）＝｛ｂ，ｄ，ｅ，ｆ｝における要員ｅの順序（位置）である「３」に対応したものである。
【００７７】
部分コードにおいて順位４の要員特定値（遺伝子コード）＝２は、要員ｄを示している。この要員特定値＝２は、部分コードにおいて先行する順位＝１，２，３の要員特定値によって特定された要員ａ，ｃ，ｅを、基本要員リストから除外した要員リスト（第３の縮減要員リスト）＝｛ｂ，ｄ，ｆ｝における要員ｄの順序（位置）である「２」に対応したものである。
【００７８】
部分コードにおいて順位５の要員特定値（遺伝子コード）＝２は、要員ｆを示している。この要員特定値＝２は、部分コードにおいて先行する順位＝１，２，３，４の要員特定値によって特定された要員ａ，ｃ，ｅ，ｄを、基本要員リストから除外した要員リスト（第４の縮減要員リスト）＝｛ｂ，ｆ｝における要員ｆの順序（位置）である「２」に対応したものである。
【００７９】
総要員数をＴとすると、部分コードにおいて、各順位ｊの要員特定値は、１からＴ−（ｊ−１）の範囲の整数値をとる。例えば、上記のように総要員数Ｔ＝６である場合、順位ｊ＝１の要員特定値は、１〜６の範囲の整数値をとり、順位ｊ＝２の要員特定値は、１〜５の範囲の整数値をとる。
【００８０】
このような部分コードでは、遺伝的操作として交叉が行われた場合であっても、１日における必要人数の確保（第５の評価項目）という制約は、常に満たされる。例えば、図１３（ａ）に示すように、第１部分コードと第２部分コードとの間で交叉が行われても、部分コードの要素数が変動するわけではないので、交叉前の第１及び第２部分コードにおいて「必要人数の確保」の制約が満たされている以上、交叉後の第１及び第２部分コードにおいても制約が満たされた状態が維持される。
【００８１】
一方、図１３（ａ）のように順序表現で要員を特定するのではなく、要員特定値として要員を直接的に特定する値を採用した場合を図１３（ｂ）に示す。図１３（ｂ）の第１部分コード及び第２部分コード間で交叉を行うと、交叉後の第１及び第２部分コードでは、同一の要員に複数の勤務形態が割り付けられた不適切な割り付けとなっており、結果的に「必要人数の確保」の制約が満たされなくなる。つまり、図１３（ｂ）の第１及び第２部分コードは、致死遺伝子となる。
【００８２】
これに対し、本実施形態では、第１部分コードと第２部分コード間で交叉を行っても、同一順位の要素間での交叉となるため、交叉後の第１及び第２部分コードにおいても、各順位の要員特定値は、順位に応じた数値範囲（１〜Ｔ−（ｊ−１））内に収まったものとなる。したがって、交叉後の第１及び第２部分コードの各要員特定値は、要員を特定するための値として適正なものであることが保証される。したがって、本実施形態では、交叉を行っても致死遺伝子が生じない。
【００８３】
また、部分コードに対して、遺伝的操作として突然変異が行われる場合には、突然変異後の要員特定値がとる範囲を、その要員特定値が属する部分コードにおける順位に応じた範囲（１〜Ｔ−（ｊ−１））とすることで、突然変異後の要員特定値は、要員を特定するための値として適正なものであることが保証される。
【００８４】
なお、初期個体群生成部１１が初期個体としてのスケジュールデータを生成する場合において、初期条件設定部３０によって、各要員の希望休暇の日、会議のある日、研修のある日が初期条件として設定された場合、その初期条件が満たされるように、スケジュールデータが生成される。例えば、ある要員が休暇を希望している日又は会議・研修がある日についての部分コードを生成する場合、その部分コードの生成に用いられる基本要員リストから、休暇を希望する要員及び会議又は研修がある要員が除外される。この結果、休暇を希望している要員は、その日の勤務を割り付けられることがなくなる。また、会議又は研修がある要員は、日勤などの通常の勤務形態が割り付けられることがなくなる。なお、評価関数を計算する場合、会議又は研修の勤務形態は、日勤とみなされる。
【００８５】
本実施形態のスケジュールデータは、上記のような部分コードを複数個連結してなるものであるため、交叉や突然変異などをおこなっても、「必要人数の確保」の制約が満たされるという効果は、スケジュールデータについても生じる。
【００８６】
［６．スケジューリングデータとＤＥ］
一般的なＤＥは、各遺伝子座ｊにおける遺伝子コード（本実施形態では、要員特定値）の値として、実数値をとる。これに対して、本実施形態の要員特定値は、整数値しかとらない。
しかし、ＤＥ操作では、差分変異親個体を生成する際に、ベクトル差分を求めたりベクトル和を求めたりするため、その際に、差分変異親個体（スケジューリングデータ）の要員特定値が、実数となる可能性がある。実数値となった要員特定値は、小数点以下の切り捨て、切り上げ、又は四捨五入などにより、実数値に近い整数値に変換される。
【００８７】
また、ＤＥ操作によって、差分変異親個体の要員特定値が適切な解探索範囲から外れる可能性もある。要員特定値は、その要員特定値の属する部分コードにおける順位に応じた範囲（１〜Ｔ−（ｊ−１））の値しかとりえないが、ＤＥ操作によって、差分変異親の要員特定値が、当該範囲（１〜Ｔ−（ｊ−１））を超えることもありえる。要員特定値が、当該範囲（１〜Ｔ−（ｊ−１））を超えた場合には、当該範囲を超えないように、要員特定値が調整される。かかる調整は、例えば、当該範囲の下限（１）又は上限（Ｔ−（ｊ−１））のうち、超えた値が近い方の値を要員特定値として採用することで行われる。
【００８８】
［７．実験結果］
［７．１ 実験結果１］
図１４〜図１５は、本実施形態のスケジューリング装置１において、２つの目的関数Ｈ１，Ｈ２を用いた場合での実験結果を示している。図１４に示すように、本実施形態のスケジュール装置１は、評価回数が５０００００回を超えた時点（時間として１０分程度）で、最適解を発見した。また、図１５は、個体群記憶部２１に記憶されている世代交代中の個体群の分布（Ｈ１，Ｈ２を軸とするユークリッド空間における分布）を示している。図１５（ａ）は世代交代の１世代目であり、図１５（ｂ）は５０００世代目であり、図１５（ｃ）は１５０００世代目を示している。図１５に示すように、世代交代の初期では、個体が広く分布しており探索範囲が広く大域探索を行っているのに対し、世代交代が進むと探索範囲が収束し、局所探索へシフトして行き、最終的に最適解が得られる。
【００８９】
図１６は、スケジューリング装置１が、最適解として得られた個体（スケジューリングデータ）を２次元のスケジュール表に変換して表示した結果を示している。図１６のスケジュール表は、Ｈ１，Ｈ２の制約を全て満たしている。なお、図１６のスケジュール表において、左側の数字（１〜２３）は看護師を示す番号であり、上側の数字（１〜３０）は、日付を示している。また、表中において、空欄は「日勤」を、「深」は「深夜勤」を、「準」は「準夜勤」を示している。
【００９０】
［７．２ 実験結果２］
図１７及び図１８は、評価項目「勤務パターン負荷度合いの軽減」に対応する評価関数Ｆ１ｉについて、表５に示す勤務パターンを採用した場合の実験結果２を示している。
【表５】
【００９１】
表５では、表２に比べて、妥協パターンが追加されたものとなっている。この場合、目的関数Ｈ１の改善が難しくなったため、図１７に示すように、Ｈ２のみが０となる解（準最適解）に収束した。
図１８は、得られた準最適解を２次元のスケジュール表に変換して表示した結果を示している。図１８のスケジュール表では、表５における妥協パターンが散見されるが、その他の制約は満たしたものとなっている。
【００９２】
［７．３ 実験結果３］
図１９及び図２０は、本実施形態のスケジューリング装置１において、３つの目的関数Ｈ１，Ｈ２，Ｈ３をすべて用いた場合での実験結果を示している。図１９に示すように、Ｈ１，Ｈ３については、０となったが、Ｈ２については８となる準最適解が得られた。図２０は、得られた準最適解を２次元のスケジュール表に変換して表示した結果を示している。
【００９３】
［７．４ 実験結果４］
図２１は、初期条件設定部３０によって、各要員の希望休暇の日、会議のある日、研修のある日を初期条件として設定した場合に得られた解をスケジュール表に変換したものを示している。この場合は、最適解が得られた。なお、スケジュール表において、「希」は「希望休暇」を、「会」は「会議」を、「研」は「研修」を、示している。
【００９４】
［８．調整用インターフェース部］
調整用インターフェース部４０は、前述のように、解の探索方向をユーザが調整するためのインターフェースである。調整の対象としては、例えば、次世代の個体ｘｉとして生成された子個体ｕが選択される場合（実質的な世代交代が生じる場合）の条件３における重みαが挙げられる。ユーザは、調整用インターフェース部４０を介して、処理部１０による最適化処理の前において、又は最適化処理中において随時、この重みαを調整することができる。αを調整することによって、目的関数Ｈ１，Ｈ２それぞれの重要性の度合いを調整することができる。
【００９５】
αを調整すると、世代交代の際に、対象親個体ｘｉが子個体ｕに置換される条件が変化することになる。つまり、αを調整すると、図２２に示すように、重要性の度合いの大きい目的関数の値が改善される方向に探索空間を選択することになる。つまり、αが大きくなるように調整することでＨ１を改善でき、１−αが大きくなるように調整することで、大きくすることでＨ２を改善できる。
このように、ユーザが、調整用インターフェース部４０を介して、探索の方向（どの制約を重視するか）を制御することで、ユーザの満足度の高い解を発見することができる。
【００９６】
［９．突然変異］
一般的なＤＥでは、個体の要素が実数値であるのに対し、本実施形態では、個体の要素（要員特定値）として整数値が採用されている。このため、図２３に示すように、個体の同一の要素についての要員特定値が全て同じ値になり易い。このように、図２３のようになると、個体間の差分が生まれないため、局所解から脱出するのが困難となり、解を改善できなくなる。
【００９７】
そこで、本実施形態では、突然変異操作によって、この問題を解決している。
図３のステップＳ５において示したように、突然変異処理部１３は、ＤＥ操作による世代交代(ステップＳ４)の後、突然変異操作の必要性について判定する。突然変異の必要性は、個体群記憶部２１に記憶されている全個体群の各要素について、同一の要素についての要員特定値が全て同じ値になっているか否かで判定してもよいが、要員特定値が全て同じ値になっているか否かにかかわり無く、所定の確率（突然変異率Ｐｍ）に応じて、突然変異の必要性を判定してもよい。
【００９８】
要員特定値がすべて同じ値になっている場合、個体群記憶部２１に記憶されている個体群の中から、１個体を選択し、個体間で同じ値になっている要員特定値を変化させる突然変異を行う（ステップＳ６）。なお、突然変異は、個体群の一部の１又は複数の個体に対して行っても良いし、全個体に対しておこなってもよい。
【００９９】
突然変異は、突然変異後の要員特定値がとる範囲が、突然変異の対象である要員特定値が属する部分コードにおける順位に応じた範囲（１〜Ｔ−（ｊ−１））となるように行われる。突然変異の方法としては、例えば、要員特定値をランダムで他の値に変更する方法（方法１）や、要員特定値の１増加又は１減少をランダムに選択する方法（方法２）がある。
【０１００】
また、個体群記憶部２１に記憶されている個体群のうち、部突然変異させる個体を選択する方法としては、全個体からランダムに選択する方法（ランダム選択法）や、図２４に示すように各個体のパレート解で個体をランク分けしたパレートランクが高い個体（評価が悪い個体）ほど高い確率で選ぶ方法（パレートランクルーレット選択）がある。
【０１０１】
図２５は、３つの目的関数Ｈ１，Ｈ２，Ｈ３で、個体数Ｎｐ＝４０、スケーリング係数Ｓ＝０．３５，交叉確率ＣＲ＝０．８５、突然変異率Ｐｍ＝０．０１の条件下において、所定回数の世代交代を繰り返した後の最良解の最適化との差（Ｈ１＋Ｈ２＋Ｈ３）を求めたものである。なお、図２５における最適解との差は、５試行の平均となっている。
図２５によれば、突然変異対象の選び方としてランダム選択法を用い、突然変異の方法として方法１を用いた場合と、突然変異対象の選び方としてパレートランクルーレット選択法を用い、突然変異の方法として方法１を用いた場合と、の結果が良好であった。
【０１０２】
［１０．スケジューリングデータの冗長性に関する考察］
スケジュール表（表現型）をコーディングしたスケジューリングデータ（遺伝子型）は、冗長性を持つ。図２６に示すように、３つの異なる複数のスケジューリングデータ（図２６では、部分コードの日勤部分だけを示した）が、同じ要員の組み合わせ｛Ａ，Ｂ，Ｃ｝を示している。つまり、本実施形態のコーディングは、複数のスケジューリングデータ（遺伝子型）が一つのスケジュール表（表現型）に対応する多対一（冗長）写像コーディングとなっている。
【０１０３】
図２７は、３つの目的関数Ｈ１，Ｈ２，Ｈ３で、個体数Ｎｐ＝４０、スケーリング係数Ｓ＝０．３５，交叉確率ＣＲ＝０．８５、突然変異率Ｐｍ＝０．０１の条件下において、突然変異対象の選び方としてランダム選択法を用い、突然変異の方法として方法１を用いた場合における、所定回数の世代交代を繰り返した後の最良解の最適化との差（Ｈ１＋Ｈ２＋Ｈ３）を求めたものである。なお、図２７における最適解との差は、５試行の平均となっている。
【０１０４】
図２７によれば、本実施形態のように多対一（冗長）写像コーディングとなっているスケジューリングデータの場合は、最適解との差が１１であったのに対し、一つのスケジュール表に対して一つのスケジューリングデータだけが対応するように一対一写像とした場合は、最適解との差が１７．４であった。
【０１０５】
かかる結果より、多対一（冗長）写像コーディングとなっている本実施形態のスケジューリングデータは、一対一写像コーディングに比べて、優れていることがわかる。
【０１０６】
なお、上記において開示した事項は、例示であって、本発明を限定するものではなく、様々な変形が可能である。
例えば、スケジューリング装置１は、ナーススケジューリングに限られず、他の業種における従業員のシフトスケジュールや、学校におけるゼミ等の発表スケジュールを調整するための装置としても利用することができる。
また、進化的アルゴリズムは、ＤＥに限られず、ＧＡなどの他の進化的アルゴリズムであってもよい。
【符号の説明】
【０１０７】
１ スケジューリング装置
１０ 処理部
１１ 初期個体群生成部
１２ ＤＥ操作部
１３ 突然変異処理部
１４ 個体評価部
１５ 最良解更新部
２０ 記憶部
２１ 個体群記憶部
２２ 最良解記憶部
【技術分野】
【０００１】
本発明は、スケジューリング装置、コンピュータプログラム、及びデータに関するものである。
【背景技術】
【０００２】
従来より、所定の集団に属する各要員のスケジュールを最適化するスケジューリング問題が、一般に知られている。スケジューリング問題として代表的なものに、ナーススケジューリング問題（Ｎｕｒｓｅ Ｓｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ；ＮＳＰ）がある。ＮＳＰでは、要員は看護師であり、一定期間（例えば、１月間）における各日の看護師の勤務形態（日勤、準夜勤、深夜勤、休日）を示すスケジュール表を最適化する問題となる。
【０００３】
スケジューリング問題を、遺伝的アルゴリズムに代表される進化的アルゴリズム用いて解く試みが、従来より行われている。例えば、特許文献１には、ＮＳＰなどのスケジューリング問題を、遺伝的アルゴリズム（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ；ＧＡ）を用いて解決するスケジューリング方法が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１４９１４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明者らは、スケジューリング問題における最適解（準最適解）を効率的に求めるために、Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎ（ＤＥ）とよばれる最適化方法を用いるという着想を得た。ＤＥは、ＧＡと同様に進化的アルゴリズムである。ＤＥでは、（１）探索空間内にランダムに複数の初期個体（解）を生成しておく、（２）すべての個体を評価する、（３）親個体から新しい解（子個体）を生成する（４）子個体が親より優れていれば親個体を削除して子個体を残す、という４つの工程を有する。
ＤＥでは、（２）〜（４）を繰り返すことで、複数の個体（個体群）の世代交代を生じさせて個体を進化させることで解を探索する。
【０００６】
ここで、スケジューリング問題にＤＥやＧＡを適用する場合、個体をどのように表現（コーディング）するかが問題となる。スケジューリング問題において、最適化したいのは、複数の要員の所定期間内のスケジュール表である。したがって、一つのスケジュール表を一つの個体とすることが考えられる。
しかし、スケジュール表に対応する個体同士において交叉の操作を行うと、致死遺伝子が生じ易いという問題がある。
【０００７】
例えば、スケジューリング問題において、重要な制約として、役割毎の「必要人数の確保」が挙げられる。ＮＳＰの場合、各日において、日勤、準夜勤、深夜勤という勤務形態（役割）毎に必要とされる人数が予め決まっている。ところが、各日において勤務形態ごとの必要人数が確保できているスケジュール表であっても、そのスケジュール表自体を個体とすると、交叉が行われることにより、必要人数が確保できなくなり、致死遺伝子となる可能性がある。
【０００８】
特許文献１では、致死遺伝子の発生を防止するため、要員全員のスケジュールではなく、要員一名のスケジュールを一つの個体とし、個体の集合で一つのスケジュール表を構成し、個体間で交叉等の遺伝的操作を行う共存型ＧＡが記載されている。
しかし、ＤＥでは、そのアルゴリズム上、一つのスケジュール表を一つの個体とすることが望ましい。したがって、ＤＥを適用する上では、共存型ＧＡのように要員一名のスケジュールを一つの個体とするのではなく、複数要員のスケジュール全体を一つの個体とすべきである。
【０００９】
そこで、本発明は、複数要員のスケジュール全体を一つの個体として扱いつつも、致死遺伝子となるスケジュール（個体）の発生を防止することを目的とする。
【課題を解決するための手段】
【００１０】
（１）本発明は、複数の要員のスケジューリングを行うスケジューリング装置であって、複数の要員それぞれの役割を所定の期間内において単位期間毎に規定したスケジューリングデータを複数個記憶する記憶部と、前記記憶部に記憶されたスケジューリングデータを親個体とする世代交代を、進化的アルゴリズムに従って繰り返させることで、前記記憶部に記憶されたスケジューリングデータを最適化する最適化処理を行う処理部と、を備え、前記スケジューリングデータは、単位期間毎の各要員の役割を規定した部分コードを複数有して構成され、各単位期間に対応する前記部分コードは、当該単位期間において最適化処理の対象となる要員の数に対応した数の要素を有するリストとして構成され、さらに前記部分コードは、当該部分コードの各要素が要員を特定する要員特定値となっているとともに、当該部分コードの要素の順位が要員の役割を示しており、前記部分コードの要員特定値は、前記複数の要員のうち、前記部分コードにおいて先行する順位の要員特定値によって特定された要員を除外した要員リストにおける順位によって、要員を特定するものである、ことを特徴とするスケジューリング装置である。
【００１１】
（２）前記進化的アルゴリズムとしては、交叉の操作が行われるアルゴリズムを採用するのが好適である。
【００１２】
（３）より具体的には、前記進化的アルゴリズムは、Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎが好適である。
【００１３】
（４）前記処理部は、前記スケジューリングデータに対して突然変異の操作を行う突然変異処理部を備えるのが好ましい。
【００１４】
（５）要員リストの要素となる要員として、スケジューリングの対象である複数の要員のうち、単位期間において最適化処理の対象とならない要員を初期条件として設定する設定部を更に備えるのが好ましい。
【００１５】
（６）個体の優劣の決定に用いられる複数の目的関数それぞれの重要性の度合いをユーザが調整するためのインターフェース部を更に備え、前記処理部は、親個体と、親個体から進化的アルゴリズムに従って得られた子個体と、を比較して、優れた個体を次世代の個体として選択するよう構成されているとともに、個体間の優劣を複数の目的関数に基づいて決定するよう構成され、さらに、前記処理部は、個体の優劣を前記複数の目的関数に基づいて決定する際に、インターフェース部を介して調整された前記度合いに応じた重みを、前記複数の目的関数の値に乗じた上で、個体間の優劣を決定するのが好ましい。
【００１６】
（７）他の観点からみた本発明は、コンピュータを、前記（１）〜（６）のいずれか１項に記載のスケジューリング装置として機能させるためのコンピュータプログラムである。
【００１７】
（８）さらに他の観点からみた本発明は、複数の要員それぞれの役割を所定の期間内において単位期間毎に規定したスケジューリングデータを複数個記憶する記憶部と、前記記憶部に記憶されたスケジューリングデータを親個体とする世代交代を、進化的アルゴリズムに従って繰り返させることで、前記記憶部に記憶されたスケジューリングデータを最適化する最適化処理を行う処理部と、を備えて複数の要員のスケジューリングを行うスケジューリング装置として機能するコンピュータが、前記スケジューリングデータとして用いるデータであって、単位期間毎の各要員の役割を規定した部分コードを複数有し、各単位期間に対応する前記部分コードは、当該単位期間において最適化処理の対象となる要員の数に対応した数の要素を有するリストとして構成され、さらに前記部分コードは、当該部分コードの各要素が要員を特定する要員特定値となっているとともに、当該部分コードの要素の順位が要員の役割を示しており、前記部分コードの要員特定値は、前記複数の要員のうち、前記部分コードにおいて先行する順位の要員特定値によって特定された要員を除外した要員リストにおける順位によって、要員を特定するものである、ことを特徴とするデータである。
【発明の効果】
【００１８】
本発明によれば、複数要員のスケジュール全体を一つの個体として扱いつつも、致死遺伝子となるスケジュール（個体）の発生を防止することができる。
【図面の簡単な説明】
【００１９】
【図１】スケジューリング装置の機能ブロック図である。
【図２】スケジュール表の例を示す図である。
【図３】スケジューリング装置のスケジューリング処理を示すフローチャートである。
【図４】ＤＥ操作を示す概念図である。
【図５】ＤＥ操作によって生成される差分変異親ベクトルの説明図である。
【図６】交叉（ｅｘｐｏｎｅｎｔｉａｌ ｃｒｏｓｓｏｖｅｒ）の説明図である。
【図７】交叉（ｂｉｎｏｍｉａｌ ｃｒｏｓｓｏｖｅｒ）の説明図である。
【図８】探索空間における親個体及び子個体の分布を示す図である。
【図９】世代交代に伴う解探索範囲の変遷を示す図である。
【図１０】最適解との距離に関する説明図である。
【図１１】スケジューリングデータのデータ構造図である。
【図１２】スケジューリングデータの要員特定値の解釈の仕方の説明図である。
【図１３】（ａ）は順序表現の要員特定値を採用した場合の交叉を示し、（ｂ）は要員を直接的に特定した要員特定値を採用した場合の交叉を示す図である。
【図１４】実験結果１を示すグラフである。
【図１５】実験結果１における解探索範囲の変遷を示す図である。
【図１６】実験結果１における最適解に対応するスケジュール表である。
【図１７】実験結果２での個体群の解探索空間における配置を示す図である。
【図１８】実験結果２における準最適解に対応するスケジュール表である。
【図１９】実験結果３での個体群の解探索空間における配置を示す図である。
【図２０】実験結果３における準最適解に対応するスケジュール表である。
【図２１】実験結果４における最適解に対応するスケジュール表である。
【図２２】重みを調整することによる探索方向の制御の様子を示す図である。
【図２３】ＤＥにおける問題点の説明図である。
【図２４】パレートランクルーレット選択の説明図である。
【図２５】突然変異方法の比較結果を示す表である。
【図２６】スケジューリングデータの冗長性の説明図である。
【図２７】コーディング方法の比較結果を示す表である。
【発明を実施するための形態】
【００２０】
以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。
［１．スケジューリング装置の構成］
図１に示すスケジューリング装置１は、複数の要員（看護師）の所定期間のスケジューリングを生成し、そのスケジュールを出力するめのものである。スケジューリング装置１は、複数の要員それぞれの役割を単位期間毎（日毎）に規定したスケジューリングデータを個体として取り扱う。
【００２１】
図２は、複数の要員（スタッフ）の役割を、所定期間（図２では１４日）内の日毎に規定したスケジュール表の例を示している。図２では、要員の役割として、勤務形態の種別（日勤、準夜勤、深夜勤、休日）が規定されている。図２では、日勤は空欄で示し、準夜勤は「準」で示し、深夜勤は「深」で示し、休日は「休」で示した。なお、このスケジュール表をデータ化したスケジューリングデータの構造については、後述する。
【００２２】
本実施形態のスケジューリング装置１は、個体であるスケジューリングデータを、様々な制約の下で最適化し最良解（最適解または準最適解）となるスケジューリングデータを求める。本実施形態では、最適化処理のためのアルゴリズムとして、ＤＥ（Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎ；差分進化）を採用する。ＤＥは、構成が簡単であり、パラメータが少なく、最適解への収束に優れ頑強であるという特徴を有する。
【００２３】
スケジューリング装置１は、コンピュータをスケジューリング装置として機能させるためのコンピュータプログラムを、コンピュータにインストールして構成されている。後述するスケジューリング装置１の機能は、コンピュータプログラムがコンピュータによって実行されることで発揮される。コンピュータは、処理装置、記憶装置、入出力装置などを有するものであり、例えば、パーソナルコンピュータを利用できる。なお、コンピュータプログラムは、ＣＤ−ＲＯＭなどの記録媒体に格納して流通させることができる。
【００２４】
図１は、スケジューリング装置１の機能ブロックを示している。スケジューリング装置１は、処理部１０、記憶部２０、初期条件設定部３０、調整用インターフェース部４０を備えている。
処理部１０は、ＤＥのアルゴリズムに従って、記憶部２０に記憶されている個体群の世代交代を繰り返して、個体の最適化を行うものである。
処理部１０は、初期個体群生成部１１と、ＤＥ操作部１２と、突然変異処理部１３と、個体評価部１４と、最良解更新部１５と、を備えている。記憶部２０は、個体群記憶２１と、最良解記憶部２２と、を備えている。
【００２５】
初期個体群生成部１１は、初期世代の個体群（例えば、３０個の個体群）となるスケジュールデータ群を生成して、それらの個体群を個体群記憶部２１に記憶させる。初期世代の個体群は、解の探索空間内においてランダムに決定して生成される。ただし、初期条件設定部３０によって、希望休暇、会議、研修の日程など、変更不可の日程が初期条件として設定されると、その初期条件を満足するようにスケジュールデータが生成される。なお、スケジュールデータは、交叉処理が行われて世代交代が生じても、一日の必要要員数、より具体的には、日勤、準夜勤、深夜勤といった勤務形態毎に要求される要員数が常に満足されるよう構成されている。
【００２６】
ＤＥ操作部１２は、ＤＥのアルゴリズムに従って、個体群記憶部２１に記憶されている現行世代の個体から次世代の個体を生成し、次世代の個体群を個体群記憶部２０に記憶させる。ＤＥのアルゴリズムの詳細については後述する。
突然変異処理部は、個体群記憶部２１に記憶されている個体について突然変異操作を行い、突然変異した個体を個体群記憶部２１に記憶させる。突然変異を行うことで、解（個体）が局所解から脱出し易くなる。個体に対して突然変異を行うための条件及びその方法の詳細については後述する。
【００２７】
個体評価部１４は、個体群記憶部２１に記憶されている個体それぞれの評価を行うものである。評価は、個体の最適解からの距離（ユークリッド距離）を求めることで行われる。
最良解更新部１５は、世代交代によって得られた個体のいずれかの最適解までの距離が、最良解記憶部２２に記憶されているそれまでの最良解の最適解までの距離よりも小さい場合には、最良解記憶部２２に記憶されている解（個体）を、より距離の小さい個体で置き換えるためのものである。
【００２８】
個体群記憶部２１は、処理部１０における処理の対象となる個体群（現行世代の個体群）を記憶するためのものである。個体群記憶部２１には、初期個体群生成部１１によって生成された個体群（初期世代の個体群）が記憶されるとともに、ＤＥ操作部１２によって世代交代した個体群（次世代の個体群）が記憶される。また、突然変異処理部１３によって突然変異処理された個体も個体群記憶部２１に記憶される。
最良解記憶部２２は、世代交代にともなって得られた過去の全個体のうち、最適解までの距離が最も小さい個体（最良解）を記憶するためのものである。世代交代を何度か繰り返した後に最良解記憶部２２に記憶されている解（最適解又は準最適解）が、スケジューリング装置１の出力となる。
【００２９】
初期条件設定部３０は、初期世代の個体群が生成される際に、希望休暇、会議、研修の日程など、変更不可の日程を初期条件として設定するためのものである。初期条件は、ユーザが任意に設定することができる。
調整用インターフェース部４０は、解の探索方向をユーザが調整するためのインターフェースである。解の探索方向をユーザが調整できるため、ユーザの満足度の高い解を発見することが可能となる。なお、初期条件設定部３０及び調整用インターフェース部４０については、後述する。
【００３０】
［２．スケジューリング装置の処理］
図３は、上記スケジューリング装置１の処理の流れを示している。まず、初期個体群生成部１１によって、所定数の初期個体の生成が行われる（ステップＳ１）。この際、初期条件設定部３０によって設定された初期条件があれば、初期条件を満たす初期個体が生成される。
【００３１】
続いて、個体評価部１４が、個体群記憶部２１に記憶されている各個体の評価を行う（ステップＳ２）。また、評価の結果、全個体の中において、最良解記憶部２２に記憶されているそれまでの最良解の最適解までの距離よりも小さい距離を持つ個体が存在する場合、最良解更新部１５は、最良解記憶部２２に記憶されている解（個体）を、より距離の小さい個体で置き換える。
また、評価の結果、最適解が発見された場合（最適解までの距離＝０の場合）、または、所定の終了条件（繰り返し回数が所定回数に達した、等）に至った場合には、スケジューリング装置１は処理を終了する（ステップＳ３）。
【００３２】
ステップＳ３において処理終了とならなかった場合、ＤＥ操作部１２は、個体群記憶部２１に記憶されている個体群の世代交代をＤＥのアルゴリズムに従って行う（ステップＳ４）。また、突然変異処理部１３は、個体群記憶部２１に記憶されている個体群に対する突然変異が必要であるか否かの判断を行い（ステップＳ５）、突然変異が必要な場合には、個体群に対する突然変異操作を行う（ステップＳ６）。なお、突然変異操作は省略してもよい。
上記ステップＳ２〜Ｓ６までの処理は、ステップＳ３において処理終了と判断されるまで繰り返し実行される。
【００３３】
［３．ＤＥ操作（ＤＥによる世代交代）］
図４は、ＤＥのアルゴリズムによって、現行世代の個体群を構成する複数の個体（ｎｐ個の個体）から、次世代の個体群を構成する複数の個体（ｎｐ個の個体）を生成する方法を示している。
【００３４】
ＤＥ操作による世代交代は、基本的に、（１）複数の親個体（現行世代の複数の個体）から、子個体を生成する、（２）親と子を比較する、（３）優れている方を次世代の個体として選択する、という３ステップで実行される。
【００３５】
［３．１ 子個体の生成］
子個体ｕの生成のため、ＤＥ操作部１２は、現行世代の複数の個体から、ＤＥ操作の対象となる一つの個体（対象親個体）ｘｉを選択するとともに、残りの現行世代の複数の個体から３つの個体ｘ１ｐ，ｘ２ｐ，ｘ３ｐをランダムに選択する。
【００３６】
続いて、ＤＥ操作部１２は、３つの個体ｘ１ｐ，ｘ２ｐ，ｘ３ｐを用いて、差分変異親個体ｖを生成する。
３つの個体ｘ１ｐ，ｘ２ｐ，ｘ３ｐそれぞれをベクトルとみなした場合、図５にも示すように、差分変異親個体（差分変異親ベクトル）ｖは、ベースベクトルｘ１ｐに対して、差分生成ベクトルｘ２ｐ，ｘ３ｐ間の差分にスケーリング係数（ｓｃａｌｉｎｇ ｆａｃｔｏｒ）を乗じたものを加えたものとなる。
【００３７】
さらに、ＤＥ操作部１２は、差分変異親個体ｖと対象親個体ｘとを用いて交叉操作を行って、子個体ｕを生成する。
交叉は、図６に示すように指数関数的に減少する確率で遺伝子交換を行う交叉（ｅｘｐｏｎｅｎｔｉａｌ ｃｒｏｓｓｏｖｅｒ）でもよいし、図７に示すように、各要素ごとに独立に一定の確率ＣＲで差分変異親の遺伝子を用いる交叉（ｂｉｎｏｍｉａｌ ｃｒｏｓｓｏｖｅｒ）でもよい。
なお、図６及び図７では、対象親個体（ベクトル）ｘ、子個体(ベクトル)ｕ，差分変異親個体（ベクトル）ｖを構成する個々の遺伝子を、ｘｊ，ｕｊ，ｖｊ（ｊは遺伝子座を示す番号。図６及び図７では、ｊ＝１〜１２）で示した。
【００３８】
図６に示す交叉（ｅｘｐｏｎｅｎｔｉａｌ ｃｒｏｓｓｏｖｅｒ）では、（１）まず、交叉開始位置（Ｓｔａｒｔ ｐｏｉｎｔ）となる遺伝子座ｊを決定する（図６ではＳｔａｒｔ ｐｏｉｎｔ＝５）。
（２）次に、交叉開始位置から、順次、それぞれの遺伝子座（ｊ＝５，６，７，８，・・・）について、０から１の間の乱数値を発生させる。図６では、遺伝子座ｊの乱数値をｒａｎｄｊで示した。
（３）そして、交叉開始位置からｒａｎｄｊが連続してＣＲ以下となる区間（図６では、遺伝子座ｊ＝５〜９の区間）については、子個体ｕの遺伝子ｕ５〜ｕ９として、差分変異親個体の遺伝子ｖ５〜ｖ９を用いる。残りの区間（図６では、遺伝子座ｊ＝１〜４及び１０〜１２）については、子個体ｕの遺伝子ｕ１〜ｕ４，ｕ１０〜ｕ１２として、対象親個体ｘの遺伝子ｘ１〜ｘ４，ｘ１０〜ｘ１２を用いる。以上の処理によって子個体ｕが生成される。
【００３９】
図７に示す交叉（ｂｉｎｏｍｉａｌ ｃｒｏｓｓｏｖｅｒ）では、図中に示す式に従って、子個体ｕの遺伝子ｕｊとして、対象親個体ｘの遺伝子ｘｊを用いるか、差分変異親個体ｖの遺伝子ｖｊを用いるかを決定する。具体的には、まず、子個体ｕの各遺伝子（要素）ｕｊ毎に、０〜１の間の乱数値ｒａｎｄｊ［０，１］を求める。この乱数値ｒａｎｄｊ［０，１］が、所定の確率ＣＲ以下であれば、子個体ｕの遺伝子ｕｊとして、差分変異親個体ｖｊの遺伝子ｖｊを用い、そうでなければ、対象親個体の遺伝子ｘｊを用いる。
【００４０】
なお、子個体ｕの遺伝子のうち、一つ（１次元）の遺伝子（要素）については、必ず差分変異親のものを用いることを保証するため、遺伝子座ｊが特定の値ｊｒである場合には、乱数値ｒａｎｄｊ［０，１］にかかわりなく、子個体ｕの遺伝子ｕｊとして、差分変異親個体ｖｊの遺伝子ｖｊが用いられる。
【００４１】
ＤＥでは、差分変異親を用いた交叉操作が行われるため、図８に示すように、探索空間でみたときに、現行世代の親個体の集団が属する範囲よりも、子個体の集団が属する範囲の方が広くなる。つまり、ＤＥでは、現行世代よりも広い範囲で解（個体）の探索を行えるため、局所解に陥りにくく、適切な解探索が行える。
そして、ＤＥでは、図９に示すように、世代交代を繰り返すと、個体間の差分が小さくなるため、個体集団の存在領域も徐々に収束していき、解の探索範囲が狭くなる。つまり、ＤＥでは、世代交代を繰り返すと、大域探索から局所探索へシフトしていく。これにより、ＤＥでは、局所解に陥ることを避けつつ最適解に近づくことが可能である。
【００４２】
［３．２ 親個体と子個体の比較及び次世代の選択］
ＤＥ操作部１２は、現行世代の対象親個体ｘｉと、生成された子個体ｕと、を比較し、優れているほうの個体を、次世帯の親個体ｘｉとして選択する。ＤＥ操作部１２は、個体群記憶部２１に記憶されている現行世代の親個体ｘｉを、選択された次世代の親個体に、置換する。
【００４３】
ＤＥ操作部１２は、個体ｘｉ，ｕ間の優劣を、複数の目的関数を用いて決定する。本実施形態では、次の３つの目的関数Ｈ１，Ｈ２，Ｈ３を定義義する。これらの目的関数の値は、小さいほどよく、最適解であれば、Ｈ１＝０，Ｈ２＝０，Ｈ３＝０となる。
ただし、個体の優劣の判断に関しては、説明の簡略化のため、これらの目的関数のうち、２つの目的関数Ｈ１，Ｈ２を用いた場合について説明する。なお、目的関数Ｈ１，Ｈ２，Ｈ３の詳細については後述する。
【数１】
【００４４】
次世代の個体ｘｉとして、生成された子個体ｕが選択される場合（実質的な世代交代が生じる場合）の条件の例（条件１）を、以下に示す。
【数２】
上記条件１において、Ｈ１Ｃは生成された子個体についての目的関数Ｈ１の値、Ｈ１Ｐは親個体についての目的関数Ｈ１の値、Ｈ２Ｃは生成された子個体ｕについての目的関数Ｈ２の値、Ｈ２Ｐは親個体についての目的関数Ｈ２の値である（下記条件２，３についても同様）。
上記条件１では、両目的関数Ｈ１，Ｈ２の双方について、対象親個体ｘｉよりも、子個体ｕの方が改善されていることが、子個体ｕが、次世代の個体として選択される条件となっている。この場合、両目的関数Ｈ１，Ｈ２を改善できる子個体ｕが生成される確率が低くなるため最適解発見までに時間がかかる。
【００４５】
また、次世代の個体ｘｉとして、生成された子個体ｕが選択される場合（実質的な世代交代が生じる場合）の条件の他の例（条件２）を、以下に示す。
【数３】
上記条件２では、目的関数Ｈ１，Ｈ２のうち、いずれか一方の目的関数が親個体ｘｉよりも改善されていれば、子個体ｕが次世代として選択される。条件２の場合、実質的な世代交代が行われるための制約が緩和されるため、個体が進化し易く、個体集団の多様性が維持され易いというメリットがある。
【００４６】
また、次世代の個体ｘｉとして、生成された子個体ｕが選択される場合（実質的な世代交代が生じる場合）の条件のさらに他の例（条件３）を、以下に示す。
【数４】
上記３では、２つの目的関数Ｈ１，Ｈ２それぞれに重みα，１−αを乗じたものの和を、個体の適応度とした上で、個体の適応度が、親個体よりも優れている場合に、子個体ｕが次世代として選択される。なお、個体の適応度は、小さいほど、優れている（最適解に近い）ことを示す。また、重みα，１−αは、各目的関数Ｈ１，Ｈ２それぞれの重要性の度合いを示しており、重要な目的関数ほど、重みを大きくすればよい。この重みは、調整用インターフェース部４０によって、ユーザによって調整可能であるが、その詳細は、後述する。
【００４７】
ＤＥ操作部１２は、上記のようなＤＥ操作は、現行世代の全個体（ｘ１〜ｘｎｐ）を対象親個体ｘｉとして行う。これにより、個体群２１に記憶されている全個体について、世代交代がなされる。
【００４８】
［４．多目的最適化］
本実施形態のスケジューリング装置１によって解かれるスケジューリング問題は、多目的最適化問題である。多目的最適化問題とは、目的関数が複数存在し、各目的関数値をひとまとめにせずに扱う問題をいう。
図１０に示すように、本実施形態では、最適化は、目的関数値Ｈ１，Ｈ２，Ｈ３に基づく最適解までの距離（ｄｉｓｔａｎｃｅ）が最小となる解（個体）を求めることである。なお、最適解は、Ｈ１＝０，Ｈ２＝０，Ｈ３＝０となり、距離＝０となる。
【００４９】
［４．１ ＮＳＰにおける評価関数］
以下、目的関数Ｈ１，Ｈ２，Ｈ３の元になる評価関数を説明する。
下記表１に示すように、ＮＳＰでは、その性質から、６つの評価項目を挙げることができ、各評価項目に応じた評価関数Ｆ１ｉ，Ｆ２ｉ，Ｆ３ｉ，Ｆ４ｉ，Ｇ１ｊ，Ｇ２ｊを定義する。
評価関数Ｆ１ｉ，Ｆ２ｉ，Ｆ３ｉ，Ｆ４ｉは、看護師ｉ個人に関する評価項目であり、評価関数Ｇ１ｊ，Ｇ２ｊは、１日に関する評価項目である。
【表１】
【００５０】
［４．１．１ 勤務パターンの負荷度合いの軽減］
表１における第１の評価項目「勤務パターンの負荷度合いの軽減」については、下記のように定式化される。
【数５】
【００５１】
上記式では、看護師ｉの勤務パターン評価値ａｉ，ｊの総和が、評価関数Ｆ１ｉの値となる。上記式中の勤務パターン評価値を、下記表２のように定義する。
【表２】
【００５２】
勤務パターンは、看護師ｉにおけるｊ日を含む連続する３日間の勤務形態の組み合わせである。表２において、「日」は、ある日の看護師の勤務形態が「日勤」であることを示し、「準」は、ある日の看護師の勤務形態が「準夜勤」であることを示し、「深」は、ある日の看護師の勤務形態が「深夜勤」であることを示し、「休」は、ある日の看護師の勤務形態が「休日」であることを示している。勤務パターンの評価値ａｉ，ｊは、勤務パターンに応じて、表２のように定義される。表２では、勤務負荷の少ない最優先パターンの評価値が最も小さく、勤務負荷の大きい禁止パターンの評価値が最も大きくなるようにして、勤務負荷が大きいほど制約条件が重くなるようにした。
【００５３】
［４．１．２ 必要日数の確保］
表１における第２の評価項目「必要日数の確保」については、下記のように定式化される。
【数６】
【００５４】
上記式では、看護師ｉが１月に各勤務形態を行う必要日数の上下限に違反する日数が評価関数Ｆ２ｉの値となる。ここで、必要日数とは、各看護師が１月に書く勤務形態を行う日数である。勤務形態毎の必要日数は、一般に、下記表３に示す通りになる。
【表３】
【００５５】
［４．１．３ 勤務日数間隔の均等化］
表１における第３の評価項目「勤務間隔の均等化」については、下記のように定式化される。
【数７】
【００５６】
上記式では、各看護師ｉに割り付ける日数の上下限を違反する日数が、評価関数Ｆ３ｉの値となる。例えば、休日は、評価対象期間ｈｋが５日間であり、休日を割り付ける上下限としては、評価対象期間の５日間において１〜５日となる。また、深夜勤は、評価対象期間ｈｋが７日であり、深夜勤を割り付ける上下限としては、評価対象期間の７日間において０〜３日となる。
【００５７】
［４．１．４ 禁止パターンの低減］
表１における第４の評価項目「禁止パターンの低減」については、下記のように定式化される。
【数８】
【００５８】
上記式では、禁止パターンの回数が、評価関数Ｆ４ｉの値となる。ここでは、禁止パターンとしては、２日間禁止パターンを用いる。２日禁止パターンとしては、例えば、看護師ｉの２日間の勤務形態の組み合わせが、「土日祝の日勤，深夜勤」、「研修，深夜勤」、「土日祝の日勤，土日祝の日勤」、又は「準夜勤，希望休暇」の組み合わせとなっている場合がある。
【００５９】
［４．１．５ 必要人数の確保］
表１における第５の評価項目の「必要人数の確保」に関し、ここでの必要人数とは、一日に各勤務形態で勤務する人数である。
【００６０】
【表４】
【００６１】
表４に示すように、例えば、準夜勤の必要人数は３人、深夜勤の必要人数は３人、平日の日勤の必要人数は１１〜１３人、土日祝の日勤の必要人数は３人である。一日に各勤務形態で勤務する人数の確保は、スケジューリングを行う上で最も重要な条件となる。本実施形態では、初期個体群生成部１１によって生成される個体は、すべて、必要人数の確保がなされたものとなり、世代交代が行われても、必要人数が確保された状態が維持される。つまり、必要人数の確保に関する評価関数Ｇ１ｊは、常に、Ｇ１ｊ＝０である。世代交代が行われても必要人数が確保されることについては、後述する。
【００６２】
［４．１．６ 看護の質の維持］
表１における第６の評価項目の「看護の質の維持」については、下記のように定式化される。
【数９】
【００６３】
看護の質の維持には、例えば、「深夜勤に新人は０〜１人で割り付ける」、「準夜勤にベテランは１〜２人で割り付ける」、「日勤にベテランは１〜２人で割り付ける」といった条件が必要とされる。上記式では、このような人数の上下限に違反する人数が、評価関数Ｇ２ｊの値となる。
【００６４】
［４．２ 目的関数の定義］
目的関数Ｈ１，Ｈ２，Ｈ３は、上記の６つの評価関数Ｆ１ｉ，Ｆ２ｉ，Ｆ３ｉ，Ｆ４ｉ，Ｇ１ｊ，Ｇ２ｊのうち、常に評価関数値＝０となるＧ１ｊを除いた６つの評価関数Ｆ１ｉ，Ｆ２ｉ，Ｆ３ｉ，Ｆ４ｉ，Ｇ２ｊによって定義される。
つまり、
Ｈ１＝Ｆ１ｉ＋Ｆ４ｉ＋Ｆ３ｉ
Ｈ２＝Ｆ２ｉ
Ｈ３＝Ｇ２ｊ
である。
【００６５】
［４．３ 個体の最適解からの距離］
個体評価部１４は、各個体の最適解からの距離を、目的関数Ｈ１，Ｈ２，Ｈ３を軸とするユークリッド空間における距離（ユークリッド距離）として算出することで、各個体の評価を行う。なお、目的関数Ｈ１，Ｈ２，Ｈ３は、３つすべてを用いる必要はなく、２つでもよい。また、目的関数は、上記のものに限られず、スケジュール問題の性質に応じて適切に設定すればよい。
【００６６】
［５．スケジューリングデータ］
以下、最適化処理の対象となるスケジューリングデータ（個体）のデータ構造を、定義する。本実施形態のスケジューリングデータは、図２に示すような２次元のスケジュール表を、遺伝子配列に類似した１次元のデータ配列（遺伝子型のスケジューリングデータ）で表現される。
【００６７】
図１１に示すようにスケジューリングデータは、スケジューリングの対象となる所定期間内のスケジューリングの単位期間の数に応じた数の部分コードを複数連結して構成されている。
図２のスケジュール表は、スケジューリングの単位期間が「１日」であり、スケジューリングの対象となる所定期間が「３０日」となっている。これに対応して、図１１のスケジューリングデータでは、各日に対応した部分コードが、３０日分設けられている。
【００６８】
各日の部分コードは、その部分コードに対応する日における、各要員（看護師）の役割（勤務形態）を規定した数値配列リスト（遺伝子コード）となっている。
この部分コードを構成する数値配列リストにおいては、リスト要素となる数値が、看護師を特定する看護師特定値（要員特定値）となっている。
【００６９】
また、部分コードを構成する数値配列リストにおける要素の順位（遺伝子座）は、看護師の勤務形態を示している。図１１において、１日目の部分コードは、順位１〜順位１１までを有しており、１１個の看護師特定値によって１１人の看護師の勤務形態を特定している。
具体的には、順位１〜順位５までは「日勤」を示しており、順位６〜順位８までは深夜勤を示しており、順位９〜順位１１までは準夜勤を示している。なお、部分コードで特定されていない看護師は、その部分コードに対応する日において休日である。このような順位と勤務形態との対応は、世代交代が生じても不変である。
【００７０】
図１１では、看護師特定値＝｛１０，６，３，２，１｝で特定される看護師が日勤であり、看護師特定値＝｛５，５，３｝で特定される看護師が深夜勤であり、看護師特定値＝｛４，２，１｝で特定される看護師が準夜勤であり、残りの看護師が休日である。
【００７１】
各日の部分コードは、表１の第５の評価項目「必要人数の確保」が満たされるように形成されている。各日において各勤務形態で勤務する看護師の人数の確保は、業務を適切に遂行する上で必要不可欠である。
そこで、部分コードでは、各勤務形態において必要とされる人数に応じた数の要素数が確保されている。必要人数が、日勤では５人、深夜勤では３人、準夜勤３人であり、その日におけるトータルの必要人数が１１人（最適化処理の対象となる要員の数）である場合、図１１のように、部分コードの総要素数は１１個となり、そのうち、日勤の要素数として５個、深夜勤の要素数として３個、準夜勤の要素数として３個が確保される。
【００７２】
なお、各勤務形態において必要とされる人数は、日によって異なることがあるため、部分コード毎に、各勤務形態に対応する要素数が異なっても良い。また、部分コード毎に、部分コード全体の要素数が異なっても良い。また、図１１の部分コードでは、休日である看護師の明示的な特定を省略しているが、休日である看護師を明示的に特定してもよい。
【００７３】
部分コードにおける要員特定値（看護師特定値）は、順序表現で要員（看護師）を特定する。順序表現では、全要員を示す要員リスト（順序リスト）を用いて、要員を特定する。具体的には、要員として、ａ，ｂ，ｃ，ｄ，ｅ，ｆが存在し、全要員数が６名の場合を想定する。この場合、基本の要員リスト＝｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝となる。
そして、図１２（ａ）に示すように、ある１日において、日勤にａ，ｃ，ｅを割り付け、深夜勤にｄを割り付け、準夜勤にｆを割り付ける場合、部分コードの総要素数は、５個であり、部分コード＝｛１，２，３，２，２｝となる。
【００７４】
図１２（ｂ）にも示すように、図１２（ａ）の部分コードにおいて、順位１の要員特定値（遺伝子コード）＝１は、要員ａを示している。この要員特定値＝１は、順序リストである要員リスト（基本要員リスト）＝｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ｝における要員ａの順序（位置）である「１」に対応したものである。
【００７５】
部分コードにおいて順位２の要員特定値（遺伝子コード）＝２は、要員ｃを示している。この要員特定値＝２は、部分コードにおいて先行する順位＝１の要員特定値によって特定された要員ａを、基本要員リストから除外した要員リスト（第１の縮減要員リスト）＝｛ｂ，ｃ，ｄ，ｅ，ｆ｝における要員ｃの順序（位置）である「２」に対応したものである。
【００７６】
部分コードにおいて順位３の要員特定値（遺伝子コード）＝３は、要員ｅを示している。この要員特定値＝３は、部分コードにおいて先行する順位＝１，２の要員特定値によって特定された要員ａ，ｃを、基本要員リストから除外した要員リスト（第２の縮減要員リスト）＝｛ｂ，ｄ，ｅ，ｆ｝における要員ｅの順序（位置）である「３」に対応したものである。
【００７７】
部分コードにおいて順位４の要員特定値（遺伝子コード）＝２は、要員ｄを示している。この要員特定値＝２は、部分コードにおいて先行する順位＝１，２，３の要員特定値によって特定された要員ａ，ｃ，ｅを、基本要員リストから除外した要員リスト（第３の縮減要員リスト）＝｛ｂ，ｄ，ｆ｝における要員ｄの順序（位置）である「２」に対応したものである。
【００７８】
部分コードにおいて順位５の要員特定値（遺伝子コード）＝２は、要員ｆを示している。この要員特定値＝２は、部分コードにおいて先行する順位＝１，２，３，４の要員特定値によって特定された要員ａ，ｃ，ｅ，ｄを、基本要員リストから除外した要員リスト（第４の縮減要員リスト）＝｛ｂ，ｆ｝における要員ｆの順序（位置）である「２」に対応したものである。
【００７９】
総要員数をＴとすると、部分コードにおいて、各順位ｊの要員特定値は、１からＴ−（ｊ−１）の範囲の整数値をとる。例えば、上記のように総要員数Ｔ＝６である場合、順位ｊ＝１の要員特定値は、１〜６の範囲の整数値をとり、順位ｊ＝２の要員特定値は、１〜５の範囲の整数値をとる。
【００８０】
このような部分コードでは、遺伝的操作として交叉が行われた場合であっても、１日における必要人数の確保（第５の評価項目）という制約は、常に満たされる。例えば、図１３（ａ）に示すように、第１部分コードと第２部分コードとの間で交叉が行われても、部分コードの要素数が変動するわけではないので、交叉前の第１及び第２部分コードにおいて「必要人数の確保」の制約が満たされている以上、交叉後の第１及び第２部分コードにおいても制約が満たされた状態が維持される。
【００８１】
一方、図１３（ａ）のように順序表現で要員を特定するのではなく、要員特定値として要員を直接的に特定する値を採用した場合を図１３（ｂ）に示す。図１３（ｂ）の第１部分コード及び第２部分コード間で交叉を行うと、交叉後の第１及び第２部分コードでは、同一の要員に複数の勤務形態が割り付けられた不適切な割り付けとなっており、結果的に「必要人数の確保」の制約が満たされなくなる。つまり、図１３（ｂ）の第１及び第２部分コードは、致死遺伝子となる。
【００８２】
これに対し、本実施形態では、第１部分コードと第２部分コード間で交叉を行っても、同一順位の要素間での交叉となるため、交叉後の第１及び第２部分コードにおいても、各順位の要員特定値は、順位に応じた数値範囲（１〜Ｔ−（ｊ−１））内に収まったものとなる。したがって、交叉後の第１及び第２部分コードの各要員特定値は、要員を特定するための値として適正なものであることが保証される。したがって、本実施形態では、交叉を行っても致死遺伝子が生じない。
【００８３】
また、部分コードに対して、遺伝的操作として突然変異が行われる場合には、突然変異後の要員特定値がとる範囲を、その要員特定値が属する部分コードにおける順位に応じた範囲（１〜Ｔ−（ｊ−１））とすることで、突然変異後の要員特定値は、要員を特定するための値として適正なものであることが保証される。
【００８４】
なお、初期個体群生成部１１が初期個体としてのスケジュールデータを生成する場合において、初期条件設定部３０によって、各要員の希望休暇の日、会議のある日、研修のある日が初期条件として設定された場合、その初期条件が満たされるように、スケジュールデータが生成される。例えば、ある要員が休暇を希望している日又は会議・研修がある日についての部分コードを生成する場合、その部分コードの生成に用いられる基本要員リストから、休暇を希望する要員及び会議又は研修がある要員が除外される。この結果、休暇を希望している要員は、その日の勤務を割り付けられることがなくなる。また、会議又は研修がある要員は、日勤などの通常の勤務形態が割り付けられることがなくなる。なお、評価関数を計算する場合、会議又は研修の勤務形態は、日勤とみなされる。
【００８５】
本実施形態のスケジュールデータは、上記のような部分コードを複数個連結してなるものであるため、交叉や突然変異などをおこなっても、「必要人数の確保」の制約が満たされるという効果は、スケジュールデータについても生じる。
【００８６】
［６．スケジューリングデータとＤＥ］
一般的なＤＥは、各遺伝子座ｊにおける遺伝子コード（本実施形態では、要員特定値）の値として、実数値をとる。これに対して、本実施形態の要員特定値は、整数値しかとらない。
しかし、ＤＥ操作では、差分変異親個体を生成する際に、ベクトル差分を求めたりベクトル和を求めたりするため、その際に、差分変異親個体（スケジューリングデータ）の要員特定値が、実数となる可能性がある。実数値となった要員特定値は、小数点以下の切り捨て、切り上げ、又は四捨五入などにより、実数値に近い整数値に変換される。
【００８７】
また、ＤＥ操作によって、差分変異親個体の要員特定値が適切な解探索範囲から外れる可能性もある。要員特定値は、その要員特定値の属する部分コードにおける順位に応じた範囲（１〜Ｔ−（ｊ−１））の値しかとりえないが、ＤＥ操作によって、差分変異親の要員特定値が、当該範囲（１〜Ｔ−（ｊ−１））を超えることもありえる。要員特定値が、当該範囲（１〜Ｔ−（ｊ−１））を超えた場合には、当該範囲を超えないように、要員特定値が調整される。かかる調整は、例えば、当該範囲の下限（１）又は上限（Ｔ−（ｊ−１））のうち、超えた値が近い方の値を要員特定値として採用することで行われる。
【００８８】
［７．実験結果］
［７．１ 実験結果１］
図１４〜図１５は、本実施形態のスケジューリング装置１において、２つの目的関数Ｈ１，Ｈ２を用いた場合での実験結果を示している。図１４に示すように、本実施形態のスケジュール装置１は、評価回数が５０００００回を超えた時点（時間として１０分程度）で、最適解を発見した。また、図１５は、個体群記憶部２１に記憶されている世代交代中の個体群の分布（Ｈ１，Ｈ２を軸とするユークリッド空間における分布）を示している。図１５（ａ）は世代交代の１世代目であり、図１５（ｂ）は５０００世代目であり、図１５（ｃ）は１５０００世代目を示している。図１５に示すように、世代交代の初期では、個体が広く分布しており探索範囲が広く大域探索を行っているのに対し、世代交代が進むと探索範囲が収束し、局所探索へシフトして行き、最終的に最適解が得られる。
【００８９】
図１６は、スケジューリング装置１が、最適解として得られた個体（スケジューリングデータ）を２次元のスケジュール表に変換して表示した結果を示している。図１６のスケジュール表は、Ｈ１，Ｈ２の制約を全て満たしている。なお、図１６のスケジュール表において、左側の数字（１〜２３）は看護師を示す番号であり、上側の数字（１〜３０）は、日付を示している。また、表中において、空欄は「日勤」を、「深」は「深夜勤」を、「準」は「準夜勤」を示している。
【００９０】
［７．２ 実験結果２］
図１７及び図１８は、評価項目「勤務パターン負荷度合いの軽減」に対応する評価関数Ｆ１ｉについて、表５に示す勤務パターンを採用した場合の実験結果２を示している。
【表５】
【００９１】
表５では、表２に比べて、妥協パターンが追加されたものとなっている。この場合、目的関数Ｈ１の改善が難しくなったため、図１７に示すように、Ｈ２のみが０となる解（準最適解）に収束した。
図１８は、得られた準最適解を２次元のスケジュール表に変換して表示した結果を示している。図１８のスケジュール表では、表５における妥協パターンが散見されるが、その他の制約は満たしたものとなっている。
【００９２】
［７．３ 実験結果３］
図１９及び図２０は、本実施形態のスケジューリング装置１において、３つの目的関数Ｈ１，Ｈ２，Ｈ３をすべて用いた場合での実験結果を示している。図１９に示すように、Ｈ１，Ｈ３については、０となったが、Ｈ２については８となる準最適解が得られた。図２０は、得られた準最適解を２次元のスケジュール表に変換して表示した結果を示している。
【００９３】
［７．４ 実験結果４］
図２１は、初期条件設定部３０によって、各要員の希望休暇の日、会議のある日、研修のある日を初期条件として設定した場合に得られた解をスケジュール表に変換したものを示している。この場合は、最適解が得られた。なお、スケジュール表において、「希」は「希望休暇」を、「会」は「会議」を、「研」は「研修」を、示している。
【００９４】
［８．調整用インターフェース部］
調整用インターフェース部４０は、前述のように、解の探索方向をユーザが調整するためのインターフェースである。調整の対象としては、例えば、次世代の個体ｘｉとして生成された子個体ｕが選択される場合（実質的な世代交代が生じる場合）の条件３における重みαが挙げられる。ユーザは、調整用インターフェース部４０を介して、処理部１０による最適化処理の前において、又は最適化処理中において随時、この重みαを調整することができる。αを調整することによって、目的関数Ｈ１，Ｈ２それぞれの重要性の度合いを調整することができる。
【００９５】
αを調整すると、世代交代の際に、対象親個体ｘｉが子個体ｕに置換される条件が変化することになる。つまり、αを調整すると、図２２に示すように、重要性の度合いの大きい目的関数の値が改善される方向に探索空間を選択することになる。つまり、αが大きくなるように調整することでＨ１を改善でき、１−αが大きくなるように調整することで、大きくすることでＨ２を改善できる。
このように、ユーザが、調整用インターフェース部４０を介して、探索の方向（どの制約を重視するか）を制御することで、ユーザの満足度の高い解を発見することができる。
【００９６】
［９．突然変異］
一般的なＤＥでは、個体の要素が実数値であるのに対し、本実施形態では、個体の要素（要員特定値）として整数値が採用されている。このため、図２３に示すように、個体の同一の要素についての要員特定値が全て同じ値になり易い。このように、図２３のようになると、個体間の差分が生まれないため、局所解から脱出するのが困難となり、解を改善できなくなる。
【００９７】
そこで、本実施形態では、突然変異操作によって、この問題を解決している。
図３のステップＳ５において示したように、突然変異処理部１３は、ＤＥ操作による世代交代(ステップＳ４)の後、突然変異操作の必要性について判定する。突然変異の必要性は、個体群記憶部２１に記憶されている全個体群の各要素について、同一の要素についての要員特定値が全て同じ値になっているか否かで判定してもよいが、要員特定値が全て同じ値になっているか否かにかかわり無く、所定の確率（突然変異率Ｐｍ）に応じて、突然変異の必要性を判定してもよい。
【００９８】
要員特定値がすべて同じ値になっている場合、個体群記憶部２１に記憶されている個体群の中から、１個体を選択し、個体間で同じ値になっている要員特定値を変化させる突然変異を行う（ステップＳ６）。なお、突然変異は、個体群の一部の１又は複数の個体に対して行っても良いし、全個体に対しておこなってもよい。
【００９９】
突然変異は、突然変異後の要員特定値がとる範囲が、突然変異の対象である要員特定値が属する部分コードにおける順位に応じた範囲（１〜Ｔ−（ｊ−１））となるように行われる。突然変異の方法としては、例えば、要員特定値をランダムで他の値に変更する方法（方法１）や、要員特定値の１増加又は１減少をランダムに選択する方法（方法２）がある。
【０１００】
また、個体群記憶部２１に記憶されている個体群のうち、部突然変異させる個体を選択する方法としては、全個体からランダムに選択する方法（ランダム選択法）や、図２４に示すように各個体のパレート解で個体をランク分けしたパレートランクが高い個体（評価が悪い個体）ほど高い確率で選ぶ方法（パレートランクルーレット選択）がある。
【０１０１】
図２５は、３つの目的関数Ｈ１，Ｈ２，Ｈ３で、個体数Ｎｐ＝４０、スケーリング係数Ｓ＝０．３５，交叉確率ＣＲ＝０．８５、突然変異率Ｐｍ＝０．０１の条件下において、所定回数の世代交代を繰り返した後の最良解の最適化との差（Ｈ１＋Ｈ２＋Ｈ３）を求めたものである。なお、図２５における最適解との差は、５試行の平均となっている。
図２５によれば、突然変異対象の選び方としてランダム選択法を用い、突然変異の方法として方法１を用いた場合と、突然変異対象の選び方としてパレートランクルーレット選択法を用い、突然変異の方法として方法１を用いた場合と、の結果が良好であった。
【０１０２】
［１０．スケジューリングデータの冗長性に関する考察］
スケジュール表（表現型）をコーディングしたスケジューリングデータ（遺伝子型）は、冗長性を持つ。図２６に示すように、３つの異なる複数のスケジューリングデータ（図２６では、部分コードの日勤部分だけを示した）が、同じ要員の組み合わせ｛Ａ，Ｂ，Ｃ｝を示している。つまり、本実施形態のコーディングは、複数のスケジューリングデータ（遺伝子型）が一つのスケジュール表（表現型）に対応する多対一（冗長）写像コーディングとなっている。
【０１０３】
図２７は、３つの目的関数Ｈ１，Ｈ２，Ｈ３で、個体数Ｎｐ＝４０、スケーリング係数Ｓ＝０．３５，交叉確率ＣＲ＝０．８５、突然変異率Ｐｍ＝０．０１の条件下において、突然変異対象の選び方としてランダム選択法を用い、突然変異の方法として方法１を用いた場合における、所定回数の世代交代を繰り返した後の最良解の最適化との差（Ｈ１＋Ｈ２＋Ｈ３）を求めたものである。なお、図２７における最適解との差は、５試行の平均となっている。
【０１０４】
図２７によれば、本実施形態のように多対一（冗長）写像コーディングとなっているスケジューリングデータの場合は、最適解との差が１１であったのに対し、一つのスケジュール表に対して一つのスケジューリングデータだけが対応するように一対一写像とした場合は、最適解との差が１７．４であった。
【０１０５】
かかる結果より、多対一（冗長）写像コーディングとなっている本実施形態のスケジューリングデータは、一対一写像コーディングに比べて、優れていることがわかる。
【０１０６】
なお、上記において開示した事項は、例示であって、本発明を限定するものではなく、様々な変形が可能である。
例えば、スケジューリング装置１は、ナーススケジューリングに限られず、他の業種における従業員のシフトスケジュールや、学校におけるゼミ等の発表スケジュールを調整するための装置としても利用することができる。
また、進化的アルゴリズムは、ＤＥに限られず、ＧＡなどの他の進化的アルゴリズムであってもよい。
【符号の説明】
【０１０７】
１ スケジューリング装置
１０ 処理部
１１ 初期個体群生成部
１２ ＤＥ操作部
１３ 突然変異処理部
１４ 個体評価部
１５ 最良解更新部
２０ 記憶部
２１ 個体群記憶部
２２ 最良解記憶部
【特許請求の範囲】
【請求項１】
複数の要員のスケジューリングを行うスケジューリング装置であって、
複数の要員それぞれの役割を所定の期間内において単位期間毎に規定したスケジューリングデータを複数個記憶する記憶部と、
前記記憶部に記憶されたスケジューリングデータを親個体とする世代交代を、進化的アルゴリズムに従って繰り返させることで、前記記憶部に記憶されたスケジューリングデータを最適化する最適化処理を行う処理部と、
を備え、
前記スケジューリングデータは、
単位期間毎の各要員の役割を規定した部分コードを複数有して構成され、
各単位期間に対応する前記部分コードは、当該単位期間において最適化処理の対象となる要員の数に対応した数の要素を有するリストとして構成され、
さらに前記部分コードは、当該部分コードの各要素が要員を特定する要員特定値となっているとともに、当該部分コードの要素の順位が要員の役割を示しており、
前記部分コードの要員特定値は、前記複数の要員のうち、前記部分コードにおいて先行する順位の要員特定値によって特定された要員を除外した要員リストにおける順位によって、要員を特定するものである、
ことを特徴とするスケジューリング装置。
【請求項２】
前記進化的アルゴリズムは、交叉の操作が行われるアルゴリズムである
請求項１記載のスケジューリング装置。
【請求項３】
前記進化的アルゴリズムは、Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎである
請求項１又は２記載のスケジューリング装置。
【請求項４】
前記処理部は、前記スケジューリングデータに対して突然変異の操作を行う突然変異処理部を備える
請求項１〜３のいずれか１項に記載のスケジューリング装置。
【請求項５】
要員リストの要素となる要員として、スケジューリングの対象である複数の要員のうち、単位期間において最適化処理の対象とならない要員を初期条件として設定する設定部を更に備える
請求項１〜４のいずれか１項に記載のスケジューリング装置。
【請求項６】
個体の優劣の決定に用いられる複数の目的関数それぞれの重要性の度合いをユーザが調整するためのインターフェース部を更に備え、
前記処理部は、親個体と、親個体から進化的アルゴリズムに従って得られた子個体と、を比較して、優れた個体を次世代の個体として選択するよう構成されているとともに、個体間の優劣を複数の目的関数に基づいて決定するよう構成され、
さらに、前記処理部は、個体の優劣を前記複数の目的関数に基づいて決定する際に、インターフェース部を介して調整された前記度合いに応じた重みを、前記複数の目的関数の値に乗じた上で、個体間の優劣を決定する
請求項１〜５のいずれか１項に記載のスケジューリング装置。
【請求項７】
コンピュータを、請求項１〜６のいずれか１項に記載のスケジューリング装置として機能させるためのコンピュータプログラム。
【請求項８】
複数の要員それぞれの役割を所定の期間内において単位期間毎に規定したスケジューリングデータを複数個記憶する記憶部と、前記記憶部に記憶されたスケジューリングデータを親個体とする世代交代を、進化的アルゴリズムに従って繰り返させることで、前記記憶部に記憶されたスケジューリングデータを最適化する最適化処理を行う処理部と、を備えて複数の要員のスケジューリングを行うスケジューリング装置として機能するコンピュータが、前記スケジューリングデータとして用いるデータであって、
単位期間毎の各要員の役割を規定した部分コードを複数有し、
各単位期間に対応する前記部分コードは、当該単位期間において最適化処理の対象となる要員の数に対応した数の要素を有するリストとして構成され、
さらに前記部分コードは、当該部分コードの各要素が要員を特定する要員特定値となっているとともに、当該部分コードの要素の順位が要員の役割を示しており、
前記部分コードの要員特定値は、前記複数の要員のうち、前記部分コードにおいて先行する順位の要員特定値によって特定された要員を除外した要員リストにおける順位によって、要員を特定するものである、
ことを特徴とするデータ。
【請求項１】
複数の要員のスケジューリングを行うスケジューリング装置であって、
複数の要員それぞれの役割を所定の期間内において単位期間毎に規定したスケジューリングデータを複数個記憶する記憶部と、
前記記憶部に記憶されたスケジューリングデータを親個体とする世代交代を、進化的アルゴリズムに従って繰り返させることで、前記記憶部に記憶されたスケジューリングデータを最適化する最適化処理を行う処理部と、
を備え、
前記スケジューリングデータは、
単位期間毎の各要員の役割を規定した部分コードを複数有して構成され、
各単位期間に対応する前記部分コードは、当該単位期間において最適化処理の対象となる要員の数に対応した数の要素を有するリストとして構成され、
さらに前記部分コードは、当該部分コードの各要素が要員を特定する要員特定値となっているとともに、当該部分コードの要素の順位が要員の役割を示しており、
前記部分コードの要員特定値は、前記複数の要員のうち、前記部分コードにおいて先行する順位の要員特定値によって特定された要員を除外した要員リストにおける順位によって、要員を特定するものである、
ことを特徴とするスケジューリング装置。
【請求項２】
前記進化的アルゴリズムは、交叉の操作が行われるアルゴリズムである
請求項１記載のスケジューリング装置。
【請求項３】
前記進化的アルゴリズムは、Ｄｉｆｆｅｒｅｎｔｉａｌ Ｅｖｏｌｕｔｉｏｎである
請求項１又は２記載のスケジューリング装置。
【請求項４】
前記処理部は、前記スケジューリングデータに対して突然変異の操作を行う突然変異処理部を備える
請求項１〜３のいずれか１項に記載のスケジューリング装置。
【請求項５】
要員リストの要素となる要員として、スケジューリングの対象である複数の要員のうち、単位期間において最適化処理の対象とならない要員を初期条件として設定する設定部を更に備える
請求項１〜４のいずれか１項に記載のスケジューリング装置。
【請求項６】
個体の優劣の決定に用いられる複数の目的関数それぞれの重要性の度合いをユーザが調整するためのインターフェース部を更に備え、
前記処理部は、親個体と、親個体から進化的アルゴリズムに従って得られた子個体と、を比較して、優れた個体を次世代の個体として選択するよう構成されているとともに、個体間の優劣を複数の目的関数に基づいて決定するよう構成され、
さらに、前記処理部は、個体の優劣を前記複数の目的関数に基づいて決定する際に、インターフェース部を介して調整された前記度合いに応じた重みを、前記複数の目的関数の値に乗じた上で、個体間の優劣を決定する
請求項１〜５のいずれか１項に記載のスケジューリング装置。
【請求項７】
コンピュータを、請求項１〜６のいずれか１項に記載のスケジューリング装置として機能させるためのコンピュータプログラム。
【請求項８】
複数の要員それぞれの役割を所定の期間内において単位期間毎に規定したスケジューリングデータを複数個記憶する記憶部と、前記記憶部に記憶されたスケジューリングデータを親個体とする世代交代を、進化的アルゴリズムに従って繰り返させることで、前記記憶部に記憶されたスケジューリングデータを最適化する最適化処理を行う処理部と、を備えて複数の要員のスケジューリングを行うスケジューリング装置として機能するコンピュータが、前記スケジューリングデータとして用いるデータであって、
単位期間毎の各要員の役割を規定した部分コードを複数有し、
各単位期間に対応する前記部分コードは、当該単位期間において最適化処理の対象となる要員の数に対応した数の要素を有するリストとして構成され、
さらに前記部分コードは、当該部分コードの各要素が要員を特定する要員特定値となっているとともに、当該部分コードの要素の順位が要員の役割を示しており、
前記部分コードの要員特定値は、前記複数の要員のうち、前記部分コードにおいて先行する順位の要員特定値によって特定された要員を除外した要員リストにおける順位によって、要員を特定するものである、
ことを特徴とするデータ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図１１】
【図１２】
【図１３】
【図２４】
【図２６】
【図８】
【図９】
【図１０】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２５】
【図２７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図１１】
【図１２】
【図１３】
【図２４】
【図２６】
【図８】
【図９】
【図１０】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２５】
【図２７】
【公開番号】特開２０１２−６４０３１（Ｐ２０１２−６４０３１Ａ）
【公開日】平成２４年３月２９日（２０１２．３．２９）
【国際特許分類】
【出願番号】特願２０１０−２０８４１７（Ｐ２０１０−２０８４１７）
【出願日】平成２２年９月１６日（２０１０．９．１６）
【出願人】（５９３００６６３０）学校法人立命館 (359)
【公開日】平成２４年３月２９日（２０１２．３．２９）
【国際特許分類】
【出願日】平成２２年９月１６日（２０１０．９．１６）
【出願人】（５９３００６６３０）学校法人立命館 (359)
[ Back to top ]