(57)【要約】【課題】最適解探索時間を短縮可能な遺伝的アルゴリズムの処理方法を提供する。【解決手段】第１世代データ[1]〜[2m-1]の過半数の評価値結果がスレーブから返信された時点で、マスタは返信された評価値結果に基づいて現世代データを遺伝的操作し新たなデータを生成し、この生成したデータ[1]〜[m]と評価値未計算の現世代データ[m+1]〜[2m-1]を第２世代データとして各スレーブに割り当てる。評価値最良の現世代データの遺伝的操作で生成した第２世代データ[m]と評価値未計算の第２世代データ[m+1]〜[2m-1]の評価値結果がスレーブから返信された時点で、第２世代のデータ生成と同様にして次の第３世代のデータを生成するようにして世代交代を繰り返す。【選択図】図３
2008009621.tif 000002
【特許請求の範囲】
【請求項１】
現世代の複数の個体データの評価値を計算する評価値計算処理と、該評価値計算処理で得た評価値に基づいて前記現世代の個体データの遺伝的操作を行って次世代の複数の個体データを生成する個体データ生成処理とを繰り返して世代交代を行って最適解を探索する遺伝的アルゴリズムの処理方法において、
前記評価値計算処理で前記現世代の個体データの過半数以上の評価値を計算した時点で、評価値が得られた過半数以上の前記現世代個体データに対して前記個体データ生成処理を実行し、当該固体データ生成処理で生成した個体データと評価値未計算の現世代個体データとを次世代の個体データとし当該次世代個体データについて前記評価値計算処理を実行し、評価値最良の現世代個体データを遺伝的操作して生成した次世代個体データと前記評価値未計算の次世代個体データの評価値結果を含む過半数以上の評価値を計算した時点で、次世代の個体データ生成と同様にして更に次の世代の個体データを生成するようにして世代交代を繰り返し行うことを特徴とする遺伝的アルゴリズムの処理方法。
【請求項２】
現世代の複数の個体データの各評価値に基づいて前記個体データの遺伝的操作を行って次世代の複数の個体データを生成する個体データ生成処理を実行するマスタと、該マスタから割り当てられた個体データの前記評価値を計算する評価値計算処理を各自のタイミングでそれぞれ実行して前記マスタに返信する複数のスレーブとを用い、前記個体データ生成処理と前記評価値計算処理を繰り返して世代交代を行って最適解を探索する遺伝的アルゴリズムの処理方法において、
前記マスタが、前記現世代の個体データの過半数以上の評価値計算結果が前記スレーブから返信された時点で、評価値の返信された過半数以上の前記現世代個体データに対して前記個体データ生成処理を実行し、当該固体データ生成処理で生成した個体データと評価値未計算の現世代個体データとを次世代の個体データとし前記複数のスレーブに割り当て、評価値最良の現世代個体データを遺伝的操作して生成した次世代個体データと前記評価値未計算の次世代個体データの評価値結果を含む過半数以上の評価値計算結果が前記スレーブから返信された時点で、次世代の個体データ生成と同様にして更に次の世代の個体データを生成するようにして世代交代を繰り返し行うことを特徴とする遺伝的アルゴリズムの処理方法。
【請求項３】
前記マスタが、前記過半数以上の評価値計算結果を返信したスレーブに対して、評価値最良の現世代個体データを遺伝的操作して生成した次世代個体データと前記評価値未計算の次世代個体データを含む過半数以上の次世代個体データを割り当てるようにしたことを特徴とする請求項２に記載の遺伝的アルゴリズムの処理方法。
【請求項４】
前記マスタが、評価値計算処理速度が速いことが期待されるスレーブ順に、評価値最良の現世代データを遺伝的操作して生成した次世代個体データと前記評価値未計算の次世代個体データを含む過半数以上の次世代個体データを割り当てるようにしたことを特徴とする請求項２に記載の遺伝的アルゴリズムの処理方法。
【請求項５】
前記マスタは、評価値最良の現世代個体データの遺伝的操作で生成する次世代個体データと前記評価値未計算の次世代個体データの合計値が、全ての次世代個体データの過半数となるようにすることを特徴とする請求項２〜4のいずれか１つに記載の遺伝的アルゴリズムの処理方法。
【請求項６】
請求項２〜５のいずれか１つに記載の遺伝的アルゴリズムの処理方法を用いて、列車運行をシミュレートする列車運行シミュレート方法であって、
前記マスタは、列車運行区間の列車運行ダイヤの変化パターンを前記現世代の個体データとして生成して各スレーブに割り当て、前記各スレーブは個体データの評価値として列車運行区間全体の踏切遮断時間の合計値を計算し、前記遺伝的アルゴリズムの処理方法を用いて評価値が最小となるように遺伝的操作して前記踏切遮断時間の合計値の変化をシミュレートし、踏切遮断時間の合計値が最小となる列車運行ダイヤを探索することを特徴とする列車運行シミュレート方法。
【請求項７】
請求項２〜５のいずれか１つに記載の遺伝的アルゴリズムの処理方法を用いて、列車運行をシミュレートする列車運行シミュレート方法であって、
前記マスタは、列車運行区間の列車運行ダイヤの変化パターンを前記現世代の個体データとして生成して各スレーブに割り当て、前記各スレーブは個体データの評価値として列車運行区間全体の踏切遮断時間の合計値を計算し、前記遺伝的アルゴリズムの処理方法を用いて評価値が最大となるように遺伝的操作して前記踏切遮断時間の合計値の変化をシミュレートし、ダイヤ乱れが生じた場合の踏切遮断時間の合計値の最大値を探索することを特徴とする列車運行シミュレート方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遺伝的アルゴリズムの処理方法に関し、特に、次世代データの生成を効率良く行い、最適解探索時間を短縮可能な遺伝的アルゴリズムの処理方法に関する。また、この遺伝的アルゴリズムの処理方法を用いた列車運行シミュレート方法に関する。
【背景技術】
【０００２】
組合せ最適化問題において、比較的短時間で最適解を求める手法の１つとして、遺伝的アルゴリズムがあり、この遺伝的アルゴリズムの最適解探索の処理速度を向上させる方法として、複数の処理装置を用いたマスタ／スレーブ・システムにより評価値を並列計算する方法がある。
【０００３】
マスタ／スレーブ・システムは、マスタで遺伝的アルゴリズムの遺伝的操作（選択、交叉、突然変異等）を行って評価用データ（各世代の個体データ）を生成して複数のスレーブにそれぞれ割り当て、各スレーブは割り当てられた評価用データの評価値を並列計算してマスタに返信する。マスタは返信された評価値について再度遺伝的操作を行い、生成した評価用データを各スレーブに割り当てる。この操作を予め設定した条件を満足するまで繰り返して世代交代を繰り返す。しかし、このシステムは、各スレーブの評価値計算時間がばらつく場合、最も遅いスレーブからの返信を待たなければならない。
【０００４】
そこで、マスタ／スレーブ・システムを用いた遺伝的アルゴリズムの処理を効率良く行うために、従来、特許文献１に記載されているように、マスタに各スレーブの性能を登録し、登録された各スレーブの性能に応じて割り当てる評価用データ数を異ならせ、性能の高いスレーブには多くの評価用データを割り当て、性能の低いスレーブには少ない評価用データを割り当てることにより、全てのスレーブの計算時間を均一化して、最適解探索までの処理時間の短縮化を図るようにした方法が提案されている。
【特許文献１】特開２００５−１９０３７２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、特許文献１の方法の場合、各スレーブが登録されている性能を常に発揮できることが保証されている場合は、評価値計算時間が均一化でき最適解探索までの処理時間の短縮化を図れる。しかしながら、例えば各スレーブがマスタから依頼される評価値計算の他に予め割り当てられた固有のローカル処理を有しローカル処理の合間に評価値計算を行うような場合には、ローカル処理の負荷状況に応じて各スレーブの評価値計算の処理時間が変化する。また、性能の低下により登録した性能が発揮できないスレーブが存在する場合は、当該スレーブからの計算結果の返信が大幅に遅延する。このため、各スレーブの評価値計算時間にばらつきが生じる。更には、スレーブのいずれかに故障が生じて計算結果が返信されない場合は、計算結果が返信されなかった評価値データを別のスレーブに割り当てて再計算させなければならない。このような場合、特許文献１の方法は全ての評価値計算結果の返信を待つ必要があるために、最適解探索の処理速度が大幅に低下するという問題がある。
【０００６】
本発明は上記問題点に着目してなされたもので、複数の処理装置の処理能力の相違や変化に影響されることなく、最適解探索の処理時間を短縮可能な遺伝的アルゴリズムの処理方法を提供することを目的とする。また、本発明の遺伝的アルゴリズムの処理方法を用いた列車運行シミュレート方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
このため、請求項１の発明は、現世代の複数の個体データの評価値を計算する評価値計算処理と、該評価値計算処理で得た評価値に基づいて前記現世代の個体データの遺伝的操作を行って次世代の複数の個体データを生成する個体データ生成処理とを繰り返して世代交代を行って最適解を探索する遺伝的アルゴリズムの処理方法において、前記評価値計算処理で前記現世代の個体データの過半数以上の評価値を計算した時点で、評価値が得られた過半数以上の前記現世代個体データに対して前記個体データ生成処理を実行し、当該固体データ生成処理で生成した個体データと評価値未計算の現世代個体データとを次世代の個体データとし当該次世代個体データについて前記評価値計算処理を実行し、評価値最良の現世代個体データを遺伝的操作して生成した次世代個体データと前記評価値未計算の次世代個体データの評価値結果を含む過半数以上の評価値を計算した時点で、次世代の個体データ生成と同様にして更に次の世代の個体データを生成するようにして世代交代を繰り返し行うことを特徴とする。
【０００８】
請求項２の発明は、現世代の複数の個体データの各評価値に基づいて前記個体データの遺伝的操作を行って次世代の複数の個体データを生成する個体データ生成処理を実行するマスタと、該マスタから割り当てられた個体データの前記評価値を計算する評価値計算処理を各自のタイミングでそれぞれ実行して前記マスタに返信する複数のスレーブとを用い、前記個体データ生成処理と前記評価値計算処理を繰り返して世代交代を行って最適解を探索する遺伝的アルゴリズムの処理方法において、前記マスタが、前記現世代の個体データの過半数以上の評価値計算結果が前記スレーブから返信された時点で、評価値の返信された過半数以上の前記現世代個体データに対して前記個体データ生成処理を実行し、当該固体データ生成処理で生成した個体データと評価値未計算の現世代個体データとを次世代の個体データとし前記複数のスレーブに割り当て、評価値最良の現世代個体データを遺伝的操作して生成した次世代個体データと前記評価値未計算の次世代個体データの評価値結果を含む過半数以上の評価値計算結果が前記スレーブから返信された時点で、次世代の個体データ生成と同様にして更に次の世代の個体データを生成するようにして世代交代を繰り返し行うことを特徴とする。
【０００９】
請求項２において、請求項３のように、前記マスタが、前記過半数以上の評価値計算結果を返信したスレーブに対して、評価値最良の現世代個体データを遺伝的操作して生成した次世代個体データと前記評価値未計算の次世代個体データを含む過半数以上の次世代個体データを割り当てるようにするとよい。
【００１０】
請求項２において、請求項４のように、前記マスタが、評価値計算処理速度が速いことが期待されるスレーブ順に、評価値最良の現世代データを遺伝的操作して生成した次世代個体データと前記評価値未計算の次世代個体データを含む過半数以上の次世代個体データを割り当てるようにしてもよい。
【００１１】
請求項５のように、前記マスタは、評価値最良の現世代個体データの遺伝的操作で生成する次世代個体データと前記評価値未計算の次世代個体データの合計値が、全ての次世代個体データの過半数となるようにするとよい。
【００１２】
請求項６の発明は、請求項２〜５のいずれか１つに記載の遺伝的アルゴリズムの処理方法を用いて列車運行をシミュレートする列車運行シミュレート方法であって、前記マスタは、列車運行区間の列車運行ダイヤの変化パターンを前記現世代の個体データとして生成して各スレーブに割り当て、前記各スレーブは個体データの評価値として列車運行区間全体の踏切遮断時間の合計値を計算し、前記遺伝的アルゴリズムの処理方法を用いて評価値が最小となるように遺伝的操作して前記踏切遮断時間の合計値の変化をシミュレートし、踏切遮断時間の合計値が最小となる列車運行ダイヤを探索することを特徴とする。
【００１３】
請求項７の発明は、請求項２〜５のいずれか１つに記載の遺伝的アルゴリズムの処理方法を用いて列車運行をシミュレートする列車運行シミュレート方法であって、前記マスタは、列車運行区間の列車運行ダイヤの変化パターンを前記現世代の個体データとして生成して各スレーブに割り当て、前記各スレーブは個体データの評価値として列車運行区間全体の踏切遮断時間の合計値を計算し、前記遺伝的アルゴリズムの処理方法を用いて評価値が最大となるように遺伝的操作して前記踏切遮断時間の合計値の変化をシミュレートし、ダイヤ乱れが生じた場合の踏切遮断時間の合計値の最大値を探索することを特徴とする。
【発明の効果】
【００１４】
本発明の遺伝的アルゴリズムの処理方法によれば、過半数以上の評価値計算結果が得られた時点で、次の世代の個体データ生成処理を実行するので、同じ世代の全ての個体データの評価値計算結果を待つことなく世代交代が進行し、しかも、現世代の最良の個体データの性質を次世代に引き継ぐ特性を損なうことなく最適解探索の処理速度を向上でき、最適解探索時間を短縮化できる。
【００１５】
また、マスタ／スレーブ・システムにおいて、全てのスレーブの評価値計算結果を待つ必要がないので、ローカル処理の影響や性能低下により評価値計算の遅いスレーブや、故障で評価値計算結果が返信できないスレーブが存在しても、これらスレーブの影響を受けることなく遺伝的アルゴリズムを実行でき最適解探索の処理速度が低下することがない。
【００１６】
本発明の列車運行シミュレート方法によれば、列車運行区間内の総踏切遮断時間を最小化する列車運行ダイヤを容易に探索することが可能となる。また、列車運行ダイヤが乱れた場合の列車運行区間内の総踏切遮断時間の最大値を容易に探索することが可能となる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の実施形態を図面に基づいて説明する。
図１は、本発明の遺伝的アルゴリズムの処理方法を適用する最適解探索システムの一実施形態を示す構成図である。
図１において、本実施形態の最適解探索システムは、１つのマスタコンピュータ（以下、マスタと称す）１と、マスタ１にネットワークを介して通信可能に接続されるＮ（Ｎ＝２ｍ−１：ｍ≧２とする）台のスレーブコンピュータ（以下、スレーブと称す）２1〜２2m-1とを備えて構成される。前記スレーブ２1〜２2m-1は、処理速度が速いことが期待されるスレーブ群２1〜２mと処理速度が速いことが期待されないスレーブ群２m+1〜２2m-1に分け、マスタ１に登録する。
【００１８】
前記マスタ１は、初期世代のＮ個の個体データ［１］〜［２ｍ−１］を例えば乱数を用いて生成する共に、スレーブから返信される個体データの評価値計算結果に基づいて個体データの遺伝的操作（選択、交叉、突然変異等）を行って次世代の個体データを生成する個体データ生成処理を実行する。また、マスタ１は、生成した個体データを各スレーブ２1〜２2m-1に割り当てる。
【００１９】
各スレーブ２1〜２2m-1は、マスタ１から割り当てられた個体データの評価値を計算する評価値計算処理の他に、予め割り当てられた固有のローカル処理を実行する。評価値計算処理は、ローカル処理の合間に各自のタイミングで実行してマスタ１に返信する。
【００２０】
この最適解探索システムは、マスタ１における評価値計算結果に基づく遺伝的操作による個体データ生成処理とＮ台のスレーブ２1〜２2m-1により評価値を並列計算する評価値計算処理とを繰り返して世代交代を繰り返し行う遺伝的アルゴリズムを用いて最適解を探索する。
【００２１】
具体的には、現世代の個体データの過半数以上の評価値計算結果がスレーブから返信された時点で、マスタ１は評価値の返信された過半数以上の現世代個体データに対して遺伝的操作による個体データ生成処理を実行し、この処理で生成した個体データと評価値未計算の現世代個体データとを次世代の個体データとしスレーブ２1〜２2m-1に割り当て、スレーブ２1〜２2m-1は次世代の個体データの評価値を計算する。マスタ１は、評価値最良の現世代個体データを遺伝的操作して生成した次世代個体データと評価値未計算の次世代個体データの評価値結果を含む過半数以上の評価値計算結果がスレーブから返信された時点で、次世代の個体データ生成と同様にして更に次の世代の個体データを生成するようにして世代交代を繰り返し行い、最適解を探索する。
【００２２】
次に、図２及び図３を参照して本実施形態の最適解探索動作について詳述する。
図２は、マスタ１の処理動作を説明するフローチャートであり、図３は、世代交代の過程を示す説明図である。
図２のステップ１（図中Ｓ１で示し、以下同様とする）で、マスタ１は乱数を用いて図３に示すような初期世代の個体データ［１］〜［２ｍ−１］を生成し、各スレーブ２1〜２2m-1に割り当てる。各スレーブ２1〜２2m-1は、ローカル処理の合間に自身のタイミングで割り当てられた個体データ［１］〜［２ｍ−１］の評価値をそれぞれ計算してマスタ１に返信する。
【００２３】
ステップ２で、全てのスレーブ２1〜２2m-1から評価値の計算結果が返信されたか否かを判定し、ＹＥＳと判定するとステップ３に進む。
尚、所定時間経過しても評価値の計算結果が返信されないスレーブが存在する場合は、評価値計算結果を既に返信した別のスレーブに、その個体データの評価値計算を行わせて評価値の計算結果を取得する。
【００２４】
ステップ３で、遺伝的操作を行って図３に示すような新たな２ｍ−１個の第１世代の個体データ［１］〜［２ｍ−１］を生成する。具体的には、例えば取得した評価値に応じて２つの初期世代個体データを交叉させる遺伝的操作により２ｍ−１個の第１世代の個体データ［１］〜［２ｍ−１］を生成する。生成した第１世代の個体データ［１］〜［２ｍ−１］を各スレーブ２1〜２2m-1に割り当て、各スレーブ２1〜２2m-1からの返信を待つ。
ステップ４で、過半数であるｍ個の評価値計算結果が返信されたか否かを判定し、ｍ個の評価値計算結果が返信された時点で、判定がＹＥＳとなってステップ５に進む。通常は図１の処理速度が速いことが期待されるスレーブ群から評価値結果が返信される。
【００２５】
ステップ５で、残りの評価値計算結果を待たずに評価値計算結果が返信された過半数ｍ個の個体データに対してステップ３と同様の遺伝的操作を行って、図３に示すような新たなｍ個の個体データ［１］〜［ｍ］を生成する。ここで、データ［ｍ］は、返信された評価値の中で最良の評価値の第１世代個体データを遺伝的操作して生成した個体データ（例えば評価値計算結果の最も良い個体データと２番目に良い個体データを交叉させて生成した個体データ）とする。また、評価値未計算である残りの（ｍ−１）個の第１世代個体データをデータ［ｍ＋１］〜［２ｍ−１］とする。そして、遺伝的操作で生成した新たな個体データ［１］〜［ｍ］と評価値未計算の第１世代個体データである個体データ［ｍ＋１］〜［２ｍ−１］とを図３に示すような（２ｍ−１）個の第２世代の個体データ［１］〜［２ｍ−１］とし、各スレーブ２1〜２2m-1に割り当て、各スレーブ２1〜２2m-1からの返信を待つ。
【００２６】
第２世代の個体データ［１］〜［２ｍ−１］をスレーブ２1〜２2m-1に割り当てる方法としては、データ［ｍ］から評価値未計算のデータ［ｍ＋１］〜［２ｍ−１］までの過半数ｍ個の第２世代個体データを、評価値計算結果を既に返信したｍ個のスレーブに割り当て、残りのデータ［１］〜［ｍ−１］までの（ｍ−１）個の第２世代個体データを評価値計算結果の返信を待ちきれなかった残りのスレーブに割り当てる。
また、データ［ｍ］から評価値未計算のデータ［ｍ＋１］〜［２ｍ−１］までの過半数ｍ個の第２世代個体データを処理速度が速いことが期待されるスレーブ順に割り当て、残りの（ｍ−１）個の第２世代個体データを残りのスレーブに割り当てるようにしてもよい。
【００２７】
ステップ６では、第２世代のデータ［ｍ］と評価値未計算のデータ［ｍ＋１］〜［２ｍ−１］の評価値計算結果が返信されたか否かを判定し、これら個体データの評価値が返信された時点で判定がＹＥＳとなり、ステップ７に進む。
ステップ７では、返信された評価値の中で予め設定した条件を満足した評価値があるか否かを判定する。そして、予め設定した条件を満足した評価値が存在して判定がＹＥＳとなるまで、ステップ５〜７の動作を繰り返して世代交代を繰り返す。図３では第３世代まで記載したが、第３世代以降、同様にして世代交代が行われる。
【００２８】
尚、図３は、データ［ｍ］から評価値未計算のデータ［ｍ＋１］〜［２ｍ−１］までの過半数ｍ個の個体データは、残りの個体データ［１］〜［ｍ−１］より速く返信されるものとして示してあるが、データ［ｍ］から評価値未計算のデータ［ｍ＋１］〜［２ｍ−１］までのデータが返信される以前に他の個体データの評価値が返信される場合が考えられる。この場合は、ステップ５では、前記他の個体データも含めて遺伝的操作を行って個体データを生成する。例えば、返信された他の個体データの数がα個とした場合、遺伝的操作によって新たに（ｍ＋α）個の個体データを生成する。そして、評価値計算結果の返信を待ちきれなかった（（ｍ−１）−α）個の評価値未計算の個体データと返信された評価値の中で最良の評価値の個体データを遺伝的操作して生成する個体データとの合計が過半数のｍ個となるように、前記（ｍ＋α）個の生成データの中の（α＋１）個を評価値の良い順の個体データを用いて生成する。そして、この（α＋１）個の評価値最良の個体データと評価値未計算の（（ｍ−１）−α）個の個体データからなるｍ個の個体データを、処理速度の速いスレーブ順、或いは、評価値を返信したスレーブに割り当て、残りの個体データを他のスレーブに割り当てるようにして世代交代を行う。
【００２９】
図４は、一つの列車運行区間に存在する全ての踏切の総遮断時間を最小化するような列車ダイヤの探索を例として、従来方法と本発明方法の比較結果を示す図である。
この場合、評価値は各踏切の遮断時間の合計値（総遮断時間）である。個体データは、該当する列車運行区間を走行する全ての列車の駅出発時刻、駅到着時刻を並べたもので、計画ダイヤに対して時刻を種々変化させて複数を生成する。
【００３０】
図４において、縦軸は評価値であり、横軸は総評価値計算数である。Ｎは個体データ数、ｍは評価値計算数を示す。図中、Ｎ＝３０，ｍ＝３０及びＮ＝５９，ｍ＝５９は、全ての個体データの評価値計算結果の返信を待って遺伝的操作を行う従来方法の場合を示し、Ｎ＝５９，ｍ＝３０は、５９個の個体データ数の過半数である３０個の評価値計算結果が返信された時点で遺伝的操作を行う本発明方法の場合を示す。この例では、評価値（踏切の総遮断時間）は小さい値程よい。
【００３１】
図４から明らかなように、本発明方法は、従来方法に比べて少ない評価値計算数で小さい評価値が得られ、従来方法より短時間で最適解を探索可能であることがわかる。また、評価値の収束性に関しては従来方法と遜色のないことがわかる。
【００３２】
そして、処理速度が速いことが期待されるスレーブ群で最も遅いスレーブの処理速度をＴ１とし、処理速度が速いことが期待されないスレーブ群で最も遅いスレーブの処理速度をＴ２としたとき、少なくともＴ１／Ｔ２＝０．５以下の場合、言い換えれば、処理速度の速いスレーブ群で最も遅いスレーブの処理速度が、処理速度の遅いスレーブ群で最も遅いスレーブの処理速度より２倍以上速い場合に、最適解探索の効率が向上する。
【００３３】
図５は、評価値計算数ｍを一定とし、個体データ数Ｎを変えた場合の収束性について、本発明方法と従来方法の比較結果である。
図５において、Ｎ＝６０，ｍ＝３０は、６０個の個体データをオーバーラップなしで２分割し、各々に対して独立に遺伝的操作を行った場合を示し、Ｎ＝４０，ｍ＝３０及びＮ＝４８，ｍ＝３０は、それぞれ遺伝的操作を開始する時点の評価値計算数を過半数より多くした場合を示す。
【００３４】
図５から、評価値計算数ｍを一定とした場合に個体データ数Ｎが（２ｍ−１）個のときが最も早く評価値が小さくなり、最適であることがわかる。言い換えれば、本発明方法では、個体データの過半数の評価値が計算された時点で遺伝的操作を行うことが最適解探索効率が最も良い。
【００３５】
図６は、個体データ数Ｎを奇数、評価値計算数ｍを丁度過半数（Ｎ＝２ｍ−１）とし、図３と同様の計算方法に基づいて遺伝的アルゴリズムを実行した場合の収束性の比較を示したものである。
図６の略収束値に近い領域Ａに着目すると、世代当たりの評価値計算数ｍを減らして世代数を増やした場合に収束性が良いことがわかる。また、収束値の領域Ｂでは、評価値計算数を減らして世代数を増やした場合と評価値計算数を増やして世代数を減らした場合とで、収束性に差異はない。尚、総評価値計算数は、（世代当たりの評価値計算数）×（世代数）である。
【００３６】
以上から明らかなように、本発明の処理方法を用いれば、従来方法に比べて最適解探索時間を短縮することが可能となり、遺伝的アルゴリズムを用いた最適解探索の効率を向上できる。また、評価値計算を行うスレーブ側に評価値計算結果の返信が遅れたり返信できなかったりするスレーブが存在しても、これらスレーブの影響を受けることなく遺伝的アルゴリズムを実行でき最適解探索の処理速度が低下することがない。
【００３７】
尚、上記実施形態は、複数のコンピュータをネットワークを介して接続する構成例を示したが、１台のコンピュータ内に複数のＣＰＵが搭載されている場合や１つのＣＰＵによって実質的に複数の処理を並列的に実行可能な場合等、本発明は実質的に複数の処理手段（ＣＰＵ）による並列処理が可能な任意のコンピュータシステムを適用可能である。
【００３８】
次に、上述した遺伝的アルゴリズムの処理方法を用いた本発明の列車シミュレート方法について説明する。
本発明の列車シミュレート方法を適用する列車シミュレート装置としては、例えば図２のマスタ１に列車運行管理装置から列車運行ダイヤ等のデータを入力するようにすればよい。また、各スレーブは、例えば各駅に設置する駅端末装置等を使用するとよい。このような構成によれば、列車シミュレートシステムの導入が容易であり、また、既存の設備を有効利用することができ、システム導入のためのコストを低減できる等の利点がある。
【００３９】
以下に、列車運行区間の全ての踏切の総遮断時間を最小とするような列車ダイヤを探索する列車シミュレート方法について説明する。
この場合、個体データは、図７に示すように、対象とする列車運行区間を走行する全ての列車の各駅における例えば出発時刻の変化パターンとする。具体的には、図７のように、計画ダイヤを示す個体データ列を全て０とし、これに対して各駅の出発時刻を微小変化させた変化パターンを生成して個体データ列とする。図７中、「０」は計画ダイヤそのままを示し、「＋１」は計画ダイヤより１秒遅らせることを示し、「−１」は計画ダイヤより１秒早めることを示す。尚、図７では３個の個体データだけであるが、このようなデータを（２ｍ−１）個生成する。このように生成した（２ｍ−１）個の個体データを、前述した本発明の遺伝的アルゴリズムの処理方法を用いて図２のフローチャートに従って個体データの世代交代を繰り返し行って、列車運行区間の全ての踏切の総遮断時間が最小となる列車ダイヤを探索する。
【００４０】
尚、踏切の総遮断時間を最小とするような列車ダイヤを探索する本実施形態の列車シミュレート方法では、図３の初期世代として図７のような列車運行ダイヤの変化パターンを個体データとして生成する。また、評価値計算結果は踏切遮断時間の合計値であり小さい程よい。従って、第２世代の個体データ［ｍ］は、評価値の最も小さい個体データと次に小さい個体データを交叉させて生成することになる。そして、例えば予め評価値の閾値を設定し、前記閾値以下となった評価値が得られた時にステップ７の判定がＹＥＳとなって遺伝的アルゴリズムを終了するようにすればよい。この場合、閾値以下の評価値となった個体データが、踏切総遮断時間を最小とする列車ダイヤである。
【００４１】
次に、ダイヤ乱れによる踏切遮断時間の変動幅算定のシミュレート方法について説明する。この場合、列車運行区間の踏切の総遮断時間の最大を探索する。
以下では、上述の列車シミュレートで探索した総踏切遮断時間を最小とする踏切時間短縮ダイヤについてシミュレートする例について説明する。
この場合、個体データは、前述のシミュレートにより探索した踏切時間短縮ダイヤを基準ダイヤとする。従って、図７の計画ダイヤのデータ列を踏切時間短縮ダイヤのデータ列に置き換えればよく、踏切時間短縮ダイヤを示す個体データ列を全て０とし、これに対して各駅の出発時刻を微小変化させた変化パターンを生成して個体データ列とする。
【００４２】
列車シミュレートにより踏切時間短縮ダイヤを探索した後、この踏切時間短縮ダイヤに基づいて生成した（２ｍ−１）個の個体データを、前述した本発明の遺伝的アルゴリズムの処理方法を用いて図２のフローチャートに従って個体データの世代交代を繰り返し行って、踏切遮断時間の変動を算定する。そして、この場合は、踏切遮断時間の最大を探索するので、評価値は大きい程良いものとする。従って、第２世代の個体データ［ｍ］は、評価値の最も大きい個体データと次に大きい個体データを交叉させて生成することになる。そして、例えば予め評価値の閾値を設定し、前記閾値以上となった評価値が得られた時にステップ７の判定がＹＥＳとなって遺伝的アルゴリズムを終了するようにすればよい。この場合、閾値以上の評価値が踏切総遮断時間を最大値として探索できる。
【００４３】
図８に、ダイヤ乱れによる踏切遮断時間の変動幅算定について、従来の遺伝的アルゴリズムの処理方法と本発明の処理方法との比較結果を示す。
図８は、本発明の遺伝的アルゴリズムの処理方法を用いて探索した踏切時間短縮ダイヤにおいて、ダイヤ乱れが生じた場合の最大の踏切遮断時間を探索した時の収束性について、従来方法と本発明方法との比較結果を示す。図中、評価値は踏切遮断時間（秒）である
【００４４】
図中、Ｎ＝９９，ｍ＝９９は、全ての個体データの評価値計算結果の返信を待って遺伝的操作を行う従来方法の場合を示し、Ｎ＝９９，ｍ＝５０は、個体データ数の過半数の評価値計算結果が返信された時点で遺伝的操作を行う本発明方法の場合を示す。
図８に示すように、従来方法と本発明方法との収束性には差異がなく、この探索の事例についても本発明の処理方法が有効であることがわかる。
【図面の簡単な説明】
【００４５】
【図１】本発明の遺伝的アルゴリズムの処理方法を適用する最適解探索システムの一実施形態を示す構成図。
【図２】同上実施形態のマスタの処理動作を説明するフローチャート
【図３】同上実施形態による世代交代の過程を示す説明図。
【図４】踏切遮断時間の合計値を最小化する列車ダイヤの探索例における従来方法と本発明方法の比較結果を示す図
【図５】評価値計算数を一定とし個体データ数を変えた場合の収束性についての本発明方法と従来方法の比較結果を示す図
【図６】本発明方法における個体データ数を変えたときの収束性の比較を示した図
【図７】踏切遮断時間の合計値を最小化する列車ダイヤ探索に用いる個体データ例の説明図
【図８】ダイヤ乱れ時の踏切遮断時間の変動幅探索時の収束性について従来方法と本発明方法との比較結果を示す図
【符号の説明】
【００４６】
１    マスタ
２1〜２2m-1    スレーブ
【図１】
2008009621.tif 000003
【図２】
2008009621.tif 000004
【図３】
2008009621.tif 000005
【図４】
2008009621.tif 000006
【図５】
2008009621.tif 000007
【図６】
2008009621.tif 000008
【図７】
2008009621.tif 000009
【図８】
2008009621.tif 000010