TOP > 国内特許検索 > プログラム及びスケジューリング装置

プログラム及びスケジューリング装置 新技術説明会

国内特許コード P07A010036
整理番号 2003-018
掲載日 2007年6月22日
出願番号 特願2003-385876
公開番号 特開2005-149148
登録番号 特許第4467286号
出願日 平成15年11月14日(2003.11.14)
公開日 平成17年6月9日(2005.6.9)
登録日 平成22年3月5日(2010.3.5)
発明者
  • 亀井 且有
  • 糸賀 健
  • 谷口 典之
出願人
  • 学校法人立命館
発明の名称 プログラム及びスケジューリング装置 新技術説明会
発明の概要

【課題】 致死遺伝子の生成を抑止しつつ、探索効率を向上する。
【解決手段】共存型遺伝的アルゴリズム(共存型GA)を用いてコンピュータで演算することによりナーススケジューリング問題を解決するスケジューリング方法である。各個体間に課せられた最低限満たさなければならない制約条件の下で初期世代の個体群を生成するステップS2と、初期世代の個体群を元にして生成された所定の世代の個体群から2つの個体を親ペアとして選択するステップS4と、ステップS4で選択された親ペアを構成する各個体を互いに交叉させるステップS5と、ステップS5で交叉された結果生まれた子ペアを親ペアと置き換えて次世代候補を生成するステップS6と、ステップS4~S8を複数回実行した後、複数の次世代候補の中から次世代解を選択するステップS9とを含む。
【選択図】 図3

従来技術、競合技術の概要


従来より、所定の集団に属する各要員のスケジュールを最適化するスケジューリング問題が一般的に知られている。この種のスケジューリング問題として、例えば、特許文献1に開示されているように遺伝的アルゴリズム(Genetic Algorithm、以下単にGAと呼ぶ。)に代表される進化的計算手法を用いた解法が提案されている。



遺伝的アルゴリズムとは、生物の進化を模倣した最適化手法の一種であり、その具体的な処理を説明すると、まず、ランダムに生成した個体の集合としての初期個体集団を生成し、この各個体を所定の評価尺度に従って評価する。そして、そのうちの2つの個体を選択し、この2個体の一部を互いに交換する交叉処理を行う。この交叉処理によって生成された新たな個体の一部を変更して新たな個体を生成する突然変異処理を行う。そして、この突然変異処理において生成された新たな個体の解としての優秀さを所定の評価尺度に従って評価し、個体集団中の最も低い個体の評価値と比較し、新たな個体の評価値の方が優れている場合には、個体集団中の最も劣った個体と入れ替える操作を行う。これらの処理を繰り返すことにより、与えられた問題の準最適解が得られるというものである。



前記特許文献1に開示されたスケジューリング方法では、初期個体集団の中からより評価値の高い個体をランダムに選択し、この2個体に対して交叉を実行するようにしている。そして、交叉によって生成された個体に連続して何度も突然変異を施すことによって解の改善を図るようにしている。



特許文献2には、複数の交叉法を用意するとともに、この中からより良い解を生成する交叉法を選択する処理を行うことが開示されている。そして、遺伝操作を施した個体群が前世代の個体群と同じ場合には、突然変異の操作を行う割合を高くして、局所解から脱出するようにすることが示されている。



非特許文献1には、多重制約性と多目的性に対して提案される共存型GAが開示されている。この共存型GAは、複数の個体からなる集団全体に対して制約条件を課し、評価項目を適用して集団全体を改善することを目的とするものであり、この共存型GAにおいては、各個体は他の個体と多重の制約条件によって拘束されており、個体は解候補の一部を担い個体集団としての解候補を表すこととしている。



共存型GAを例えばナーススケジューリング問題(Nurse Scheduling Problem、以下単にNSPという。)に適用した場合について説明する。勤務スケジュール表は看護師個人の例えば1ヶ月のスケジュールを集合して全体のスケジュールが構成される。この個人の1ヶ月のスケジュールが一個体となり、全体の1ヶ月のスケジュールが一集団となる。このナーススケジューリング問題では、看護師数をnとし、また日数をmとするとn×m行列を決定する問題となる。そして、準最適解を導出すべく以下に示す処理を順次実行する。
H1:看護師の属する集団に課せられたある制約条件を満たした初期個体集団をランダムに生成する。たとえば、1日の各勤務における必要人員数等がこの制約条件に該当する。
H2:各個体の評価を与えられた個体の評価尺度にしたがって計算し、その結果を評価値とする。
H3:個体の評価値に応じて選ばれやすくなるようにバイアスをかけてランダムに2個体を選択する。この選ばれた2個体を親ペアと呼ぶ。
H4:親ペアの一部を互いに交換して新たな個体を生成する。生成された2個体を子ペアと呼び、親ペアの一部を互いに交換する操作を交叉と呼ぶ。このとき、前記制約条件を満たした初期個体集団を生成することにより、交叉処理を行っても常にこの制約条件が満たされるようになっている。
H5:生成された子ペアを親ペアと置き換えて新たな集団を生成する。この新たに生成された集団を次世代解候補と呼ぶ。
H6:生成された次世代解候補の評価を予め設定された集団の評価尺度にしたがって計算し、その結果を評価値とする。
H7:H4~H6を繰り返すことで複数の次世代解候補を生成する。
H8:複数の次世代候補の中から集団の評価により1つの次世代解を選択し、現世代解を次世代解に置き換える。
H9:前記処理H2~H8を1サイクルとして繰り返し処理を行う。これにより、全体のスケジュールが準最適解に達することとなる。

【特許文献1】特開2000-132604号公報

【特許文献2】特開平9-69050号公報

【非特許文献1】北野宏明、「遺伝的アルゴリズム(2)」、日本、産業図書、1995年、p.89-125

産業上の利用分野


本発明は、プログラム及びスケジューリング装置に関し、特に探索効率を向上するための対策に係るものである。

特許請求の範囲 【請求項1】
所定の集団に属する各要員の所定期間における日毎のスケジュールを構成するデータを個体とし、遺伝的アルゴリズムを用いて演算することにより全要員についての個体の集合である個体群の最良解を、全要員の所定期間におけるスケジュールとして作成するスケジューリング装置としてコンピュータを機能させるプログラムであって、
前記所定期間の各日において、前記各個体間に課せられた制約条件としての必要要員数を満足する初期世代の個体群を生成する初期個体群生成手段と、
前記初期世代の個体群又は前記初期世代の個体群を元にして生成された所定の世代の個体群、である現行世代の個体群から2つの個体を親ペアとして選択し、その際に、親ペアの一方をランダム選択するとともに、親ペアの他方を現行世代の個体群を構成する各個体の評価値に基づく評価の悪い個体ほど選択され易い確率で選択する処理を行う親ペア選択手段と、
前記親ペア選択手段によって選択された親ペアを構成する各個体についてそれぞれ同一の日を交差箇所として設定し、設定された交差箇所について、親ペアを構成する各個体を互いに交叉させて子ペアを生成する交叉手段と、
前記交叉手段によって交叉された結果生まれた子ペアを親ペアと置き換えることで、制約条件を満足する現行世代の個体群から、制約条件が満足された状態が維持された次世代候補の個体群を生成し、その次世代候補の個体群をメモリに格納する次世代候補生成手段と、
前記親ペアの選択、交叉及び次世代候補の生成を複数回実行させて、複数の次世代候補の個体群を生成させる複数次世代候補生成処理の制御手段と、
前記制御手段によって次世代候補の生成が複数回行われた結果得られてメモリに格納されている複数の次世代候補の個体群それぞれの評価値に基づいて、複数の次世代候補に対するパレート最適選択を行い、パレート最適解となった次世代候補の中からランダムに1つの次世代候補の個体群を選択して、選択された次世代候補の個体群を次世代の個体群とする次世代選択処理を行う次世代選択手段と、
前記次世代選択手段によって選択された次世代の個体群を現行世代の個体群に置換して、複数次世代候補生成処理及び次世代選択処理を所定回数繰り返させる繰り返し手段と、
を備え、
更に、次世代候補の中から最良解となる個体群を選択する手段を備え、この手段による最良解の選択は、次世代候補の個体群の評価値が、最適解に対して距離最小のものを選択することにより行われる、
前記スケジューリング装置として前記コンピュータを機能させるプログラム。

【請求項2】
次世代候補の個体群の評価値には、一日に関する評価項目から得られる評価値が含まれ、前記一日に関する評価項目には、特定の要員の組み合わせ禁止に関する評価項目が含まれる請求項1記載のプログラム。

【請求項3】
所定の集団に属する各要員の所定期間における日毎のスケジュールを構成するデータを個体とし、遺伝的アルゴリズムを用いて演算することにより全要員についての個体の集合である個体群の最良解を、全要員の所定期間におけるスケジュールとして作成するスケジューリング装置であって、
前記所定期間の各日において、前記各個体間に課せられた制約条件を満足する初期世代の個体群を生成する初期個体群生成手段と、
前記初期世代の個体群又は前記初期世代の個体群を元にして生成された所定の世代の個体群、からなる現行世代の個体群から2つの個体を親ペアとして選択し、その際に、親ペアの一方をランダム選択するとともに、親ペアの他方を現行世代の個体群を構成する各個体の評価値に基づく評価の悪い個体ほど選択され易い確率で選択する処理を行う親ペア選択手段と、
前記親ペア選択手段によって選択された親ペアを構成する各個体についてそれぞれ同一の日を交差箇所として設定し、設定された交差箇所について、親ペアを構成する各個体を互いに交叉させて子ペアを生成する交叉手段と、
前記交叉手段によって交叉された結果生まれた子ペアを親ペアと置き換えることで、制約条件を満足する現行世代の個体群から、制約条件が満足された状態が維持された次世代候補の個体群を生成し、その次世代候補の個体群をメモリに格納する次世代候補生成手段と、
前記親ペアの選択、交叉及び次世代候補の生成を複数回実行させて、複数の次世代候補の個体群を生成させる複数次世代候補生成処理の制御手段と、
前記制御手段によって次世代候補の生成が複数回行われた結果得られてメモリに格納されている複数の次世代候補の個体群それぞれの評価値に基づいて、複数の次世代候補に対するパレート最適選択を行い、パレート最適解となった次世代候補の中からランダムに1つの次世代候補の個体群を選択して、選択された次世代候補の個体群を次世代の個体群とする次世代選択処理を行う次世代選択手段と、
前記次世代選択手段によって選択された次世代の個体群を現行世代の個体群に置換して、複数次世代候補生成処理及び次世代選択処理を所定回数繰り返させる繰り返し手段と、
を備え、
更に、次世代候補の中から最良解となる個体群を選択する手段を備え、この手段による最良解の選択は、次世代候補の個体群の評価値が、最適解に対して距離最小のものを選択することにより行われる、
スケジューリング装置。

【請求項4】
次世代候補の個体群の評価値には、一日に関する評価項目から得られる評価値が含まれ、前記一日に関する評価項目には、特定の要員の組み合わせ禁止に関する評価項目が含まれる請求項3記載のスケジューリング装置。
産業区分
  • 演算制御装置
  • 機構・伝動
  • 制御調整
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2003385876thum.jpg
出願権利状態 権利存続中
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記「問合せ先」までお問い合わせください。


PAGE TOP

close
close
close
close
close
close
close