(57)【要約】【課題】設定された世代数分繰り返して遺伝的操作を行う遺伝的アルゴリズムは、生成する個体数が多い程、解の種類が増えるため最適解を得る可能性が高くなるという長所を持つが、生成する個体数に比例して解を得るまでの処理時間が増えるという短所を持つ。また個体数が少なければ処理時間は短くなるが解の種類が減るため、最適解でない解に収束する可能性が高くなるという問題点を持つ。【解決手段】本発明は、最初の世代においては、少量の個体数ではじめ途中の世代から残りの個体を投入することで従来の遺伝的アルゴリズムと同等の精度を持ちながらも最適解を得るまでの処理時間が短時間であるという特徴を持つ遺伝的アルゴリズムにおける最適解探索時間短縮化システム、探索時間短縮化方法及びそのプログラムを提供するものである。【選択図】      図１
2004355220.tif 000002
【特許請求の範囲】
【請求項１】
遺伝的アルゴリズムに基づき個体の評価を行う評価手段と個体への遺伝的操作を行う遺伝子操作手段とによって組み合わせ最適化問題の解法を行う探索時間短縮化システムであって、
最初の世代から遺伝的操作を実行する個体の個体数（以下、初期個体数と称す）と、遺伝的操作を実行する全世代数（以下、全世代数と称す）と、途中の世代で追加をする個体の個体数（以下、追加個体数と称す）と、個体の追加を行う世代の世代数（以下追加世代数と称す）と、を入力する入力手段を備え、
前記評価手段は、前記初期個体数で指定された数の個体について遺伝的操作の対象として取り出し遺伝的アルゴリズムの適用を開始し、前記遺伝子操作手段によって遺伝的操作の実行される都度世代数のカウントを行うとともに遺伝的操作の行われた個体の評価を行い、
前記遺伝子操作手段は、前記評価手段の評価し終えた個体について遺伝的操作を行い遺伝的操作を行った個体を前記評価手段に戻し、
さらに、前記評価手段は、カウントした世代数が前記追加世代数と一致すると、前記追加個体数分の新たな個体を遺伝的操作の対象として追加し、カウントした世代数が前記全世代数と一致すると遺伝的操作を終了することを特徴とする探索時間短縮化システム。
【請求項２】
請求項１において、前記遺伝子操作手段は、最初の世代から前記追加世代数までの世代には前記初期個体数で指定された個体数分の個体に対して遺伝的操作を行い、前記追加世代数＋１の世代から前記全世代数までの世代については、前記初期個体数と前記追加個体数を合計した数の個体に対して遺伝的操作を行うことを特徴とする探索時間短縮化システム。
【請求項３】
請求項１において、前記遺伝子操作手段は、選択・淘汰、交叉、突然変異、個体生成の遺伝的操作を行うとともに、交叉と突然変異は指定された発生率に従って操作を行うことを特徴とする探索時間短縮化システム。
【請求項４】
請求項１において、前記評価手段は、予め記憶装置に登録された評価規則に従い、個体の評価を行うことを特徴とする探索時間短縮化システム。
【請求項５】
遺伝的アルゴリズムに基づいて複数の個体に対し複数の世代にわたり遺伝的操作を行い組み合わせ最適化問題を解法する探索時間短縮化システムにおける探索時間短縮化方法であって、
最初の世代から遺伝的操作を実行する個体の個体数（以下、初期個体数と称す）と、遺伝的操作を実行する全世代数（以下、全世代数と称す）と、途中の世代で追加をする個体の個体数（以下、追加個体数と称す）と、個体の追加を行う世代の世代数（以下追加世代数と称す）と、を入力するとともに世代数のカウントフィールドを１で初期化する第１のステップと、
前記初期個体数で指定された数の個体を取り出し遺伝的アルゴリズムの処理を開始する第２のステップと、
前記世代数のカウントフィールドの世代数と前記追加世代数とが一致するかを比較する第３のステップと、
前記第２のステップの比較で一致すると、前記追加個体数分の個体を遺伝的アルゴリズムの対象として新規に追加する第４のステップと、
前記第３のステップの比較で一致しない場合、及び前記第４のステップで個体の追加が行われた場合に、全個体の評価を行う第５のステップと、
前記第５のステップで評価が行われた全個体について遺伝的操作を行う第６のステップと、
前記世代数のカウントフィールドの値が前記全世代数と一致するかを比較する第７のステップと、
前記第７のステップでの比較が一致しない場合は、世代数のカウントフィールドの値に１を足し、前記第３のステップに戻る第８のステップと、
前記第７のステップでの比較が一致すると、評価点数の高い個体の情報を出力する第９のステップと、
を備えることを特徴とする探索時間短縮化方法。
【請求項６】
遺伝的アルゴリズムに基づいて複数の個体に対し複数の世代にわたり遺伝的操作を行い組み合わせ最適化問題を解法する探索時間短縮化システムにが実行させるプログラムであって、
コンピュータに、
最初の世代から遺伝的操作を実行する個体の個体数（以下、初期個体数と称す）と、遺伝的操作を実行する全世代数（以下、全世代数と称す）と、途中の世代で追加をする個体の個体数（以下、追加個体数と称す）と、個体の追加を行う世代の世代数（以下追加世代数と称す）と、を入力するとともに世代数のカウントフィールドを１で初期化する第１のステップと、
前記初期個体数で指定された数の個体を取り出し遺伝的アルゴリズムの処理を開始する第２のステップと、
前記世代数のカウントフィールドの世代数と前記追加世代数とが一致するかを比較する第３のステップと、
前記第２のステップの比較で一致すると、前記追加個体数分の個体を遺伝的アルゴリズムの対象として新規に追加する第４のステップと、
前記第３のステップの比較で一致しない場合、及び前記第４のステップで個体の追加が行われた場合に、全個体の評価を行う第５のステップと、
前記第５のステップで評価が行われた全個体について遺伝的操作を行う第６のステップと、
前記世代数のカウントフィールドの値が前記全世代数と一致するかを比較する第７のステップと、
前記第７のステップでの比較が一致しない場合は、世代数のカウントフィールドの値に１を足し、前記第３のステップに戻る第８のステップと、
前記第７のステップでの比較が一致すると、評価点数の高い個体の情報を出力する第９のステップと、
を実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は遺伝的アルゴリズムを使用した組合せ最適化問題に関し、特に初期世代においては、一部の個体数で遺伝的アルゴリズムの適用をはじめ、途中の世代から残りの個体を投入することで従来の遺伝的アルゴリズムと同等の精度を持ちながらも最適解を得るまでの処理時間が短時間である遺伝的アルゴリズムにおける最適解探索時間短縮化システム、探索時間短縮化方法及びそのプログラムに関する。
【０００２】
【従来の技術】
組合せ最適化問題においては、比較的短時間で最適解を求める手法の一つとして、生物の進化過程をモデルとした計算手法、遺伝的アルゴリズムが用いられることが多い。
【０００３】
遺伝的アルゴリズムは、個体を構成する要素の組合せを遺伝子で表し、その遺伝子を持つ個体に対して遺伝的操作（選択・淘汰、交叉、突然変異、個体生成）を繰り返すことで１または複数の最適解の探索を行う手法である。
【０００４】
遺伝的操作のうちの選択・淘汰は、次の世代にどのような個体を残し、どのような個体を無くしていくかを決めるもので、評価値の高い個体を残すのが良い解を求めるのための原則ではあるが、最も評価値の高い個体を残す、ランダムに選択した個体を残す、複数の方法を組み合わせる等の方法がある。
【０００５】
交叉は、２つの個体を選択し、ランダムな位置で区切って個体を構成する要素（遺伝子）を交換する。
【０００６】
突然変異は、１つの個体でランダムに選択した２箇所の遺伝子を入れ替える等の操作をし、交叉では行えないような変換を行う。
【０００７】
個体生成は、選択・淘汰、交叉、突然変異を行った個体を次の世代として生成するものである。
【０００８】
このようにして遺伝的操作を対象とする個体に対して複数世代実行する。
【０００９】
以上のように操作した個々の個体ついて、環境への適応状態の評価を行い、個々の個体に評価値を設定する。これを指定した世代数または、指定した評価値（しきい値）になるまで繰り返し実行を行うものである。
【００１０】
尚、本発明に関連する文献として、遺伝的アルゴリズムによる最適解の探索の効率化に関し、個体を表現する文字列に対して各文字位置ごとに文字分布を定め、その文字分布をもとに各文字ごとに乱雑度を求め、乱雑度が大きい文字位置にはより高い変異率を設定することで遺伝的操作の効率化を図る内容が特許文献１にある。
【００１１】
また、遺伝的アルゴリズムについて説明した書籍として非特許文献１がある。
【００１２】
【特許文献１】
特開平１０−２２８４６０（ページ５−１３、図１）
【非特許文献１】
伊庭  斎志：遺伝的アルゴリズムの基礎、オーム社、１９９３（ページ１−１０）
【００１３】
【発明が解決しようとする課題】
遺伝的アルゴリズムは、生成する個体数が多い程、解の種類が増えるため最適解を得る可能性が高くなるという長所を持つが、生成する個体数に比例して解を得るまでの処理時間が増えるという短所を持つ。
また、個体数が少なければ処理時間は短くなるが、解の種類が減るため、局所解（最適解でない解）に収束する可能性が高くなるという問題を持つ。
【００１４】
本発明は、最初の世代においては、一部の個体数ではじめ途中の世代から残りの個体を追加投入することで、従来の遺伝的アルゴリズムと同等の精度を持ちながらも最適解を得るまでの処理時間が短時間であるという上記のような問題を解決する遺伝的アルゴリズムにおける最適解探索時間短縮化システム、探索時間短縮化方法及びそのプログラムを提供するものである。
【００１５】
【課題を解決するための手段】
本発明の第１の探索時間短縮化システムは、遺伝的アルゴリズムに基づき個体の評価を行う評価手段と個体への遺伝的操作を行う遺伝子操作手段とによって組み合わせ最適化問題の解法を行う探索時間短縮化システムであって、
最初の世代から遺伝的操作を実行する個体の個体数（以下、初期個体数と称す）と、遺伝的操作を実行する全世代数（以下、全世代数と称す）と、途中の世代で追加をする個体の個体数（以下、追加個体数と称す）と、個体の追加を行う世代の世代数（以下追加世代数と称す）と、を入力する入力手段を備え、
前記評価手段は、前記初期個体数で指定された数の個体について遺伝的操作の対象として取り出し遺伝的アルゴリズムの適用を開始し、前記遺伝子操作手段によって遺伝的操作の実行される都度世代数のカウントを行うとともに遺伝的操作の行われた個体の評価を行い、
前記遺伝子操作手段は、前記評価手段の評価し終えた個体について遺伝的操作を行い遺伝的操作を行った個体を前記評価手段に戻し、
さらに、前記評価手段は、カウントした世代数が前記追加世代数と一致すると、前記追加個体数分の新たな個体を遺伝的操作の対象として追加し、カウントした世代数が前記全世代数と一致すると遺伝的操作を終了することを備える。
【００１６】
本発明の第２の探索時間短縮化システムは、第１の発明において、前記遺伝子操作手段は、最初の世代から前記追加世代数までの世代には前記初期個体数で指定された個体数分の個体に対して遺伝的操作を行い、前記追加世代数＋１の世代から前記全世代数までの世代については、前記初期個体数と前記追加個体数を合計した数の個体に対して遺伝的操作を行うことを備える。
【００１７】
本発明の第３の探索時間短縮化システムは、第１の発明において、前記遺伝子操作手段は、選択・淘汰、交叉、突然変異、個体生成の遺伝的操作を行うとともに、交叉と突然変異は指定された発生率に従って操作を行うことを備える。
【００１８】
本発明の第４の探索時間短縮化システムは、第１の発明において、前記評価手段は、予め記憶装置に登録された評価規則に従い、個体の評価を行うことを備える。
【００１９】
本発明の第１の探索時間短縮化方法は、遺伝的アルゴリズムに基づいて複数の個体に対し複数の世代にわたり遺伝的操作を行い組み合わせ最適化問題を解法する探索時間短縮化システムにおける探索時間短縮化方法であって、
最初の世代から遺伝的操作を実行する個体の個体数（以下、初期個体数と称す）と、遺伝的操作を実行する全世代数（以下、全世代数と称す）と、途中の世代で追加をする個体の個体数（以下、追加個体数と称す）と、個体の追加を行う世代の世代数（以下追加世代数と称す）と、を入力するとともに世代数のカウントフィールドを１で初期化する第１のステップと、
前記初期個体数で指定された数の個体を取り出し遺伝的アルゴリズムの処理の対象とする第２のステップと、
前記世代数のカウントフィールドの世代数と前記追加世代数とが一致するかを比較する第３のステップと、
前記第２のステップの比較で一致すると、前記追加個体数分の個体を遺伝的アルゴリズムの対象として追加する第４のステップと、
前記第３のステップの比較で一致しない場合及び前記第４のステップで個体の追加が行われた場合に、個体の評価を行う第５のステップと、
前記第５のステップで評価が行われたすべての個体について遺伝的操作を行う第６のステップと、
前記世代数のカウントフィールドの値が前記全世代数と一致するかを比較する第７のステップと、
前記第７のステップでの比較が一致しない場合は、世代数のカウントフィールドの値に１を足し、前記第３のステップに戻る第８のステップと、
前記第７のステップでの比較が一致すると、評価点数の高い個体の情報を出力する第９のステップと、
を備える。
【００２０】
本発明の第１のプログラムは、遺伝的アルゴリズムに基づいて複数の個体に対し複数の世代にわたり遺伝的操作を行い組み合わせ最適化問題を解法する探索時間短縮化システムにが実行させるプログラムであって、
コンピュータに、
最初の世代から遺伝的操作を実行する個体の個体数（以下、初期個体数と称す）と、遺伝的操作を実行する全世代数（以下、全世代数と称す）と、途中の世代で追加をする個体の個体数（以下、追加個体数と称す）と、個体の追加を行う世代の世代数（以下追加世代数と称す）と、を入力するとともに世代数のカウントフィールドを１で初期化する第１のステップと、
前記初期個体数で指定された数の個体を取り出し遺伝的アルゴリズムの処理の対象とする第２のステップと、
前記世代数のカウントフィールドの世代数と前記追加世代数とが一致するかを比較する第３のステップと、
前記第２のステップの比較で一致すると、前記追加個体数分の個体を遺伝的アルゴリズムの対象として追加する第４のステップと、
前記第３のステップの比較で一致しない場合及び前記第４のステップで個体の追加が行われた場合に、個体の評価を行う第５のステップと、
前記第５のステップで評価が行われたすべての個体について遺伝的操作を行う第６のステップと、
前記世代数のカウントフィールドの値が前記全世代数と一致するかを比較する第７のステップと、
前記第７のステップでの比較が一致しない場合は、世代数のカウントフィールドの値に１を足し、前記第３のステップに戻る第８のステップと、
前記第７のステップでの比較が一致すると、評価点数の高い個体の情報を出力する第９のステップと、
を実行させる。
【００２１】
【発明の実施の形態】
次に、本発明の実施例について図面を参照して詳細に説明する。
【００２２】
最初に、本発明の第１と第２の実施例の構成について図１を参照して説明を行う。
【００２３】
本発明は、パーソナルコンピュータ等のコンピュータ１００に接続されたキーボード等の入力装置１０１と、ディスプレイ等の表示装置やプリンタ等の印刷装置からな出力装置１０２と、磁気ディスク装置等の記憶装置１０３と、コンピュータ１００の主記憶装置上で動作するプログラムと、から構成されている。
【００２４】
コンピュータ１００で動作する個々のプログラムとして、入力装置１０１からの入力データを受け付け全体の動作の制御指示を行う入力手段１１０と、
個体の遺伝子情報からなる構成要素を定義する環境定義手段１１１と、
個体についての評価を行う規則を定義する評価規則定義手段１１２と、
乱数を生成する乱数生成手段１１３と、
環境定義手段１１１の内容を元に指定された数の個体を乱数生成手段１１３による乱数を使用して生成する初期個体生成手段１１４と、
個体に対して遺伝的操作を行う遺伝子操作手段１１５と、
個体の評価値を個体ごとに算出する評価手段１１７と、
指定された世代数の実行後、評価値の高い個体情報を出力装置１０２に出力する出力手段１１８と、から構成されている。
【００２５】
以降においては、学校の時間割を遺伝的アルゴリズムを適用して決定する場合を使用して説明する。例えば、１年から４年まである大学があり、各学年にＡ，Ｂ、Ｃの学科（クラス）が３クラスあったとする。また、月曜日から土曜日まで毎日５時間目まで授業があるとし各クラスの週当たりの授業時間数の合計は３０時間とする。
【００２６】
問題は、４学年の各クラスについて月曜日から土曜日までの各時間の教科を時間割として設定するものである。このときの１つの個体は、１クラスの月曜日から金曜日までの連続した３０時間の時間割を４学年すべてのクラスについて含むものとし、個体の遺伝子は、各時間の教科（例えば、英会話、英作文等）とする。そのとき個体は３６０（＝４学年Ｘ３クラスＸ６日Ｘ５時間）の要素（遺伝子）から構成される。これを図４に示す。図４によると最初の３０要素は、１年Ａクラスの月曜１時限から土曜５時限までの時間割、次の３０要素は、１年Ｂクラスの時間割であり、最後の３０要素は、４年Ｃクラスの時間割となっている。
【００２７】
尚、このように定義した個体の遺伝的操作は、同じクラス内、また同じクラス同士で行うものとする。
【００２８】
環境定義手段１１１によって、各学年の各クラスごとに当該クラスが１週間に履修する各教科別の合計時間数が記憶装置１０３に設定される。例えば１年Ａクラスの週当たりの合計英会話時間は４時間、英作文は３時間、等々である。
この履修教科の時間数を各クラスごとに合計すると３０時間に近い時間数となり、３０時間に満たない時間は、空き時間となる。空き時間がある場合は週の空き時間数も各教科の時間数と同様に捉え週の合計時間数が３０時間となるようにする。
【００２９】
評価規則定義手段１１２は、個体についての評価を行う評価規則と個々の評価規則の持つ点数とを記憶装置１０３に登録する。例えば、
・２時間連続で行う科目が連続していない時間割は減点する。
・教員の都合として都合が悪い時間に教科の割り当てがされている場合は減点する。
・次の授業までの空き時間が２時間以上あるときは減点とする。
・空き教室の判定として同じ時間に教室が不足した場合は減点とする。
・同じ教科を同じ日に２度以上割り当てた場合は減点とする。
等時間割設定に関する制約についていろいろな規則を登録する。
【００３０】
さらに規則の重みを勘案して減点する点数を加減し決定する。減点のみでなく規則に沿っている場合は加点してもよい。また、一旦設定した規則についての点数は固定したものでなく適宜変更することもできる。
【００３１】
乱数生成手段１１３は、例えば１から３０までの数値についてその順序をランダムに配列した順列を、生成する数を個体数Ｘクラス数に見合って複数組作り記憶装置１０３に登録する。
【００３２】
初期個体生成手段１１４は、指定された数の初期個体を生成する。このとき、乱数生成手段１１３が生成した１から３０までの一組の順列を取り出し、環境定義手段１１１によって登録された各クラスの各教科の時間数情報に従って個体の要素を作成する。例えば、１年Ａクラスについて、登録された最初の教科が英会話で週当たりの合計時間数が４時間の場合、４時間の英会話を取り出した順列の先頭から４つまでの番号に従い、月曜日の１時限を１として１年Ａクラスの時間割に対応する個体上にランダムに配置する。初期個体生成手段１１４は、すべてのクラスについて以上のような操作を行い生成した個体を記憶装置１０３に登録する。
【００３３】
遺伝子操作手段１１５は、各個体を構成する教科に対し遺伝的操作（選択・淘汰、交叉、突然変異、個体生成）を実行する。
【００３４】
評価手段１１７は、各世代についての遺伝的操作の開始前に操作の対象となる個体について、評価規則定義手段１１２によって登録された規則を記憶装置１０３から読み出し、定義された規則に従い各個体の評価を行い評価値を個体ごとに設定する。また、評価手段１１７は、実行した世代数をカウントし、終了する世代数を検出すると遺伝的操作処理を終了する。
【００３５】
次に、本発明の実施例の動作について図面を参照して説明する。
【００３６】
図２のフローチャートでは特定世代の指定がない場合を、図３のフローチャートでは特定世代の指定のある場合のフローチャートを示す。
【００３７】
本発明の第１の実施例の動作について図２のフローチャートを参照して説明を行う。
【００３８】
利用者は入力装置１０１から時間割の設定に必要な情報を入力する。時間割設定対象期間として、例えば１日、週、２週、月等がある。さらに、授業を開講する時間数を日ごとに指定する。また、対象とする学年と学年当たりの学科（クラス）数を入力する。さらに時間割設定対象期間内に実施する各クラスそれぞれについての教科種別とその教科の合計時間数を入力する。
【００３９】
コンピュータ１００の入力手段１１０では入力された情報を環境定義手段１１１に渡し、環境定義手段１１１はこの内容をもとに個体の構成要素数を含む構成情報を作成し、これを記憶装置１０３に環境情報として記憶する（ステップＳ１）。例えば、４学年、学年当たりの学科数が３、月曜から土曜日まで毎日５時間開講とした場合、各学年の各学科についての時間割についての個体の構成情報は図４に例示したようになり、この場合３６０の要素（遺伝子）を含むものとなる。
【００４０】
利用者は続いて個々の個体を評価するための記号化された評価規則と評価規則の持つ点数を入力し、評価規則定義手段１１２は、これを評価規則情報として記憶装置１０３に登録する（ステップＳ２）。尚、本実施例の説明では各クラスの週当たりの合計時間数を一律３０時間としたが、必ずしも同じ時間数にする必要はない。
【００４１】
続いて利用者は、生成する個体数（例えば５０００個体）、実行する世代数（例えば２００世代）を入力する。
【００４２】
入力手段１１０はこれを受け付けると、乱数生成手段１１３に生成する個体数情報を渡し、乱数の生成を指示する。
【００４３】
乱数生成手段１１３は、環境定義手段によって生成された環境情報からクラスごとの個体を構成する要素数を取り出す。乱数生成手段１１３は、１からこの取り出したクラスごとの要素数までのすべての整数の順列を指示された個体数Ｘクラス数分ランダムに作成してこれを記憶装置１０３に登録し（ステップＳ３）、入力手段１１０に終了を通知する。入力手段１１０は、続いて、生成する個体数を指定して初期個体生成手段１１４に個体の生成を指示する。
【００４４】
初期個体生成手段１１４は、環境情報から取り出した個体の構成情報と各クラスごとの教科とその教科の合計時間数、及び乱数生成手段１１３が生成したランダムな順列を元にランダムに教科種別を個体上に配置し、指定された個数分個体を生成すると記憶装置１０３に登録する（ステップＳ４）。
【００４５】
次に、入力手段１１０は、評価手段１１７に実行する世代数、実行する個体数を通知する。
【００４６】
この通知を受けた評価手段１１７は、初期集団発生処理を行い初期個体生成手段１１４によって生成され登録された記憶装置１０３から通知をうけた実行する個体数分の個体を取り出すとともに、世代数のカウントフィールドを１として初期化する（ステップＳ５）。
【００４７】
評価手段１１７は、評価に際し評価規則定義手段１１２によって登録された評価規則を記憶装置１０３から読み出し、登録された規則を一つずつ順に評価対象となる個体に対し適用する。規則に反する場合は、ペナルティを科して減点し、規則に順ずる場合は加点する。このようにして定義された規則すべてを適用し評価を実行する。採点した結果を個体ごとに設定し記憶する（ステップＳ６）。尚、初期個体生成時にはある決まられた同じ点数が各個体に割り当てられている。
【００４８】
次に、遺伝子操作手段１１５は、評価対象となる個体について遺伝的操作を行う。具体的には、以下の操作を順に行う。
（１）選択・淘汰としては以下のような方法がある。
【００４９】
・評価値が最も良い個体を１または複数個残す。
【００５０】
・ランダムに選んだ２つの個体で評価値の良い方を残す。
【００５１】
・ランダムに選んだ個体を残す。
（２）交叉としては以下のような方法がある。尚、交叉の場合は、評価対象となる個体すべてを乱数に従い、予め２つの個体からなる組に分けておき、同じ組の個体同士で交叉を行うことにする。
【００５２】
・同じ組の個体の同じクラス間同士でランダムに区切ったある箇所から後ろの遺伝子をお互いに入れ替える。例えば１年のＡクラスについて、水曜日の２時限と３時限の間で区切ったとすると、同じ組の他の個体の１年Ａクラスの水曜日の３時限以降から土曜日の５時限までの遺伝子情報をその組の他の個体の該当部分と入れ替える。
【００５３】
・同じ組の個体の同じクラス間同士でランダムに区切った２箇所の間を他の個体の該当部分と入れ替える。
（３）突然変異としては以下のような方法がある。
【００５４】
・１つの個体の同じクラスの遺伝子についてランダムに選択した２箇所を入れ替える。
【００５５】
・１つの個体の同じクラスの遺伝子についてランダムに選択した複数箇所を入れ替える。
【００５６】
尚、交叉と突然変異の場合は、それぞれ別個に０％から１００％までの発生率を予め定義し、その発生率に従って各世代における遺伝的操作を行ったり、行わなかったりする（ステップＳ７）。尚、この％の数値も利用者から設定することができる。
【００５７】
次に、以上の遺伝的操作を対象とするすべての個体について実行したかを確認する（ステップＳ８）。すべての個体について実行していない場合は、（ステップＳ７）に戻る。すべての個体について実行をし終えた場合は、評価手段１１７に戻る。
【００５８】
評価手段１１７は、すべての世代についての遺伝的操作を終えたか確認する（ステップＳ９）。すべての世代についての処理を終えていない場合は、世代数のカウントフィールドに１を加算する（ステップＳ１０）。そして（ステップＳ６）に戻り個体の評価を実行する。
【００５９】
（ステップＳ８）の評価ですべての世代の評価を終えた場合は、出力手段１１８は、最終評価を実行し評価点数の最も高い個体または比較的高い個体の遺伝子情報とその評価点数とを指定された個体数分出力装置１０２に出力して終了する（ステップＳ１１）。
【００６０】
本実施例では、初期集団発生で生成した個体数は変化しない。したがって、個体数が多ければ、最適解を得る可能性は高いが、処理時間は長くなる。
【００６１】
次に第２の実施例の動作について、図３のフローチャートを参照して説明する。
【００６２】
図３のフローチャートには、図２のフローチャートの中ほどに（ステップＳ１２）と（ステップＳ１３）が追加されていて、（ステップＳ１）から（ステップＳ１１）の内容は図２と同じである。
【００６３】
本実施例では、利用者から特定世代数が指定されていて実行した世代数が指定された特定世代数に到達すると、評価する個体の追加を行う内容を持つものであり、その他は第１の実施例と同じである。主に第１の実施例との相違点を説明する。
【００６４】
最初に利用者は、生成する個体数（例えば５０００個体）、実行する世代数（例えば２００世代）、最初から実行する個体数（例えば１０００個体）、途中で追加する個体数（例えば４０００個体）、途中で個体の追加を行う特定世代数（例えば１００世代）を入力する。
【００６５】
次に、入力手段１１０は、評価手段１１７に利用者の入力した情報を通知する。
【００６６】
評価手段１１７は、（ステップＳ５）と（ステップＳ６）において、最初から実行する個体数分の個体を、記憶装置１０３から取り出し、世代数のカウントフィールドを１として初期化する。し、それぞれの個体について評価を実行する。
【００６７】
次に評価手段１１７は、途中で個体を追加する特定世代数に達したかをチェックする（ステップＳ１２）。特定世代数に達した場合は、先に受け取った途中から追加する個体数に従い、記憶装置１０３から未評価の個体を入力して評価の対象に追加し（ステップＳ１３）、追加された個体も含めた（ステップＳ６）での評価を行う。評価を終えると（ステップＳ７）での遺伝的操作を行う。
【００６８】
（ステップＳ１２）の評価で特定世代ではない場合は、（ステップＳ６）での評価を行う。
【００６９】
本実施例の場合、処理の段階に応じて個体数を変化させている。まず、初期集団発生で少数の個体を生成し、この個体に対して特定世代まで評価と遺伝的操作を繰り返す。特定世代に到達した時に個体数追加を行い、第１の実施例の場合と同じ個体数まで個体を追加する。その後は終了条件になるまで評価と遺伝的操作を繰り返す。
【００７０】
第２の実施例では、初期集団生成から特定世代までの個体数を減らすことにより、処理時間短縮が可能となる。また、特定世代で個体数追加を行うため、第２の実施例の場合と同数の個体を扱うことで深い探索を行い、最適解を得る可能性を高めることができる。このように必要とする個体数を一度に処理するのではなく、段階的に個体数を増加させることで、第２の実施例の精度を保ちつつ、短時間での処理を可能にすることができる。
【００７１】
最後に、以上説明した２つの実施例のそれぞれの処理時間を算定する。
【００７２】
両実施例ともに扱う個体数は５，０００個、終了条件（終了世代数）を２００世代とし、１個体の評価と遺伝的操作に掛かる時間を１秒と仮定する。
【００７３】
第１の実施例の場合、単純に５０００個の個体を終了条件に到達するまで処理を繰り返すのみであり、処理時間は５０００個×２００世代×１秒＝１、０００、０００秒となる。
【００７４】
第２の実施例では、初期の個体数を１，０００個とし、１００世代目に４，０００個の個体を追加することとする。
【００７５】
この場合の処理時間は１，０００個×１００世代×１秒＋５，０００個×１００世代×１秒＝６００，０００秒となる。
【００７６】
第２の実施例では第１の実施例に比較すると、４０％処理時間を短縮していることが判る。また、第２の実施例における処理個体数は、第１の実施例と同数であるため、第１の実施例の場合と同等の精度を持つと言える。また、第２の実施例では、最初に投入する個体数、個体の追加を行う世代数、追加を行う世代における追加する個体数は適宜変更することができる。
【００７７】
さらに、第２の実施例では遺伝的アルゴリズムを時間割の作成に適用する場合を元に説明をしたが、初期個体数、追加する個体数、個体数追加を行う世代数、終了世代数を指定して、様々な遺伝的アルゴリズムを用いた組み合わせ最適化問題に適用することが可能である。
【００７８】
【発明の効果】
本発明の効果は３点あり、まず第１は、時間割の設定作業を遺伝的操作アルゴリズムを適用して行うことで容易に時間割が作成できることである。
【００７９】
第２に「処理時間が短縮できること」、第３に「従来の手法と同等の精度を保持できること」である。これは前述しているように、初期集団生成から特定世代までの個体数を減らし、特定世代で段階的に個体数追加を行うことで、従来の手法と同数の個体を扱うことで深い探索を行い、短時間で最適解が得られるからである。
【図面の簡単な説明】
【図１】本発明の実施の形態の構成を説明するブロック図である。
【図２】本発明の第１の実施例の動作を説明するフローチャートである。
【図３】本発明の第２の実施例の動作を説明するフローチャートである。
【図４】本発明の実施例の時間割を作成するための個体の構成要素の説明図である。
【符号の説明】
１００    コンピュータ
１０１    入力装置
１０２    出力装置
１０３    記憶装置
１１０    入力手段
１１１    環境定義手段
１１２    評価規則定義手段
１１３    乱数生成手段
１１４    初期個体生成手段
１１５    遺伝子操作手段
１１７    評価手段
１１８    出力手段
【図１】
2004355220.tif 000003
【図２】
2004355220.tif 000004
【図３】
2004355220.tif 000005
【図４】
2004355220.tif 000006