(57)【要約】【課題】  遺伝子アルゴリズムにより求めた解が最適値であるか否かを適正に判定することのできる最適値の判定装置を提供する。【解決手段】  突然変異部６におけるある時点での解およびそれを導出する個体に対して所定の変動値を付与するとともに、変動値を付与された個体について評価値のヒストグラムの作成および評価値の平均、分散を計算する変動値付与部７と、変動値付与部７により、変動値を変化させながら付与された個体についての評価値のヒストグラムを比較し、この評価値のヒストグラムに基づいて規則性があるか否かを判断し、法則性がある場合に最適値であると判定する判定部８と、を備えている。【選択図】  図１
2009020562.tif 000002
【特許請求の範囲】
【請求項１】
複数個の染色体からなる個体を初期の個体として複数個生成する個体生成部と、
前記個体生成部により生成された複数個の前記個体の各々の評価関数値を算出する個体評価値計算部と、
前記個体評価計算部による評価結果に基づいて複数個の前記個体のうち最良値を選択する個体選択部と、
前記個体選択部により選択された前記個体を親個体として、これら各親個体を交叉させ、子個体を生成する個体交叉部と、
予め設定された突然変異確率に従って、遺伝的アルゴリズムの突然変異処理を行う突然変異部と、
前記突然変異部におけるある時点での解およびそれを導出する個体に対して所定の変動値を付与するとともに、変動値を付与された個体について評価値のヒストグラムの作成および評価値の平均、分散を計算する変動値付与部と、
前記変動値付与部により、変動値を変化させながら付与された前記個体についての評価値のヒストグラムを比較し、この評価値のヒストグラムに基づいて法則性があるか否かを判断し、規則性がある場合に最適値であると判定する判定部と、
を備えていることを特徴とする最適値の判定装置。
【請求項２】
前記変動値付与部は、あらかじめ変動量を徐々に変化させた複数の変動遺伝子群を備えており、これら各変動遺伝子群に基づいて変動量を付与するものであることを特徴とする請求項１に記載の最適値の判定装置。
【請求項３】
前記個体選択部は、評価結果が最小値のものを最良値として選択するものであり、
前記変動値付与部は、変動量を「＋側」に変化させるものであることを特徴とする請求項１または請求項２に記載の最適値の判定装置。
【請求項４】
複数個の染色体からなる個体を初期の個体として複数個生成する個体生成処理と、
前記個体生成部により生成された複数個の前記個体の各々の評価関数値を算出する個体評価値計算処理と、
前記個体評価計算部による評価結果に基づいて複数個の前記個体のうち最良値を選択する個体選択処理と、
前記個体選択部により選択された前記個体を親個体として、これら各親個体を交叉させ、子個体を生成する個体交叉処理と、
予め設定された突然変異確率に従って、遺伝的アルゴリズムの突然変異処理を行う突然変異処理と、
前記突然変異部におけるある時点での解およびそれを導出する個体に対して所定の変動値を付与するとともに、変動値を付与された個体について評価値のヒストグラムの作成および評価値の平均、分散を計算する変動値付与処理と、
前記変動値付与部により、変動値を変化させながら付与された前記個体についての評価値のヒストグラムを比較し、この評価値のヒストグラムに基づいて法則性があるか否かを判断し、規則性がある場合に最適値であると判定する判定処理と、
を備えていることを特徴とする最適値の判定方法。
【請求項５】
前記変動値付与処理は、あらかじめ変動量を徐々に変化させた複数の変動遺伝子群を備えており、これら各変動遺伝子群に基づいて変動量を付与するものであることを特徴とする請求項４に記載の最適値の判定方法。
【請求項６】
前記個体選択処理は、評価結果が最小値のものを最良値として選択するものであり、
前記変動値付与処理は、変動量を「＋側」に変化させるものであることを特徴とする請求項４または請求項５に記載の最適値の判定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適値の判定装置および最適値の判定方法に係り、特に遺伝的アルゴリズムを用いた最適値の判定装置および最適値の判定方法に関するものである。
【背景技術】
【０００２】
一般に、複数のパラメータがあり、そのすべての組み合わせ数が膨大な数となる場合、その膨大な組み合わせ問題を解くのに遺伝的アルゴリズムを用いることが有効であるとされている。
【０００３】
しかしながら、遺伝子アルゴリズムを用いて膨大な数の組み合わせ問題を解く場合、一般に、ある一定の時間、計算を続けることから、例えすでに最適値となる解が求められていたとしても、計算を続けてしまうことになり、無駄な時間を消費してしまうという問題を有している。
【０００４】
そのため、従来から、遺伝子アルゴリズムを用いて求めた解が最適値であるか否かを判定する手段が各種提示されている。この最適値の判定手段として、例えば、評価値の平均、分散の値が以前の世代のものと同じ値になった場合に、収束とみなし、その値を最適値として計算を終了する方法がある（例えば、特許文献１参照。）。
【特許文献１】特開２００５−２９３５２８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、前記特許文献１に開示された最適値の判定手段では、評価値の平均、分散の値が以前の世代のものと同じ値になった場合に収束とみなすものであり、世代分の遺伝子で求めた平均と分散であることから、次世代で進化する可能性などがあり、必ずしも最適な解であるとはいえないという問題を有している。
【０００６】
本発明は前記した点に鑑みてなされたものであり、遺伝子アルゴリズムにより求めた解が最適値であるか否かを適正に判定することのできる最適値の判定装置および最適値の判定方法を提供することを目的とするものである。
【課題を解決するための手段】
【０００７】
上記課題を解決するための請求項１に記載の発明に係る最適値の判定装置は、
複数個の染色体からなる個体を初期の個体として複数個生成する個体生成部と、
前記個体生成部により生成された複数個の前記個体の各々の評価関数値を算出する個体評価値計算部と、
前記個体評価計算部による評価結果に基づいて複数個の前記個体のうち最良値を選択する個体選択部と、
前記個体選択部により選択された前記個体を親個体として、これら各親個体を交叉させ、子個体を生成する個体交叉部と、
予め設定された突然変異確率に従って、遺伝的アルゴリズムの突然変異処理を行う突然変異部と、
前記突然変異部におけるある時点での解およびそれを導出する個体に対して所定の変動値を付与するとともに、変動値を付与された個体について評価値のヒストグラムの作成および評価値の平均、分散を計算する変動値付与部と、
前記変動値付与部により、変動値を変化させながら付与された前記個体についての評価値のヒストグラムを比較し、この評価値のヒストグラムに基づいて規則性があるか否かを判断し、法則性がある場合に最適値であると判定する判定部と、
を備えていることを特徴とする。
【０００８】
請求項２に記載の発明は、請求項１において、前記変動値付与部は、あらかじめ変動量を徐々に変化させた複数の変動遺伝子群を備えており、これら各変動遺伝子群に基づいて変動量を付与するものであることを特徴とする。
【０００９】
請求項３に記載の発明は、請求項１または請求項２において、前記個体選択部は、評価結果が最小値のものを最良値として選択するものであり、前記変動値付与部は、変動量を「＋側」に変化させるものであることを特徴とする。
【００１０】
また、請求項４に記載の発明に係る最適値の判定方法は、
複数個の染色体からなる個体を初期の個体として複数個生成する個体生成処理と、
前記個体生成部により生成された複数個の前記個体の各々の評価関数値を算出する個体評価値計算処理と、
前記個体評価計算部による評価結果に基づいて複数個の前記個体のうち最良値を選択する個体選択処理と、
前記個体選択部により選択された前記個体を親個体として、これら各親個体を交叉させ、子個体を生成する個体交叉処理と、
予め設定された突然変異確率に従って、遺伝的アルゴリズムの突然変異処理を行う突然変異処理と、
前記突然変異部におけるある時点での解およびそれを導出する個体に対して所定の変動値を付与するとともに、変動値を付与された個体について評価値のヒストグラムの作成および評価値の平均、分散を計算する変動値付与処理と、
前記変動値付与部により、変動値を変化させながら付与された前記個体についての評価値のヒストグラムを比較し、この評価値のヒストグラムに基づいて規則性があるか否かを判断し、法則性がある場合に最適値であると判定する判定処理と、
を備えていることを特徴とする。
【００１１】
請求項５に記載の発明は、請求項４において、前記変動値付与処理は、あらかじめ変動量を徐々に変化させた複数の変動遺伝子群を備えており、これら各変動遺伝子群に基づいて変動量を付与するものであることを特徴とする。
【００１２】
請求項６に記載の発明は、請求項４または請求項５において、前記個体選択処理は、評価結果が最小値のものを最良値として選択するものであり、前記変動値付与処理は、変動量を「＋側」に変化させるものであることを特徴とする。
【発明の効果】
【００１３】
請求項１に記載の発明に係る最適値の判定装置によれば、変動値付与部により変動値を変化させながら付与された個体について作成された評価値のヒストグラムを比較し、判定部により、この評価値のヒストグラムに基づいて法則性があるか否かを判断し、規則性がある場合に最適値であると判定するようにしているので、遺伝子アルゴリズムを用いた解が最適値であるか否かを確実に判定することができ、その結果、演算時間の短縮を図ることができ、演算効率の向上を図ることができる。
【００１４】
請求項２に記載の発明によれば、変動値付与部は、あらかじめ備えられた変動量を徐々に変化させた複数の変動遺伝子群に基づいて変動量を付与するものであるので、変動量の付与処理を効率よく行うことができる。
【００１５】
請求項３に記載の発明によれば、個体選択部により評価結果が最小値のものを最良値として選択するとともに、変動値付与部により、変動量を「＋側」に変化させることにより、適正に最適値であるか否かを判定することかできる。
【００１６】
請求項４に記載の発明に係る最適値の判定方法によれば、変動値付与処理により変動値を変化させながら付与された個体について作成された評価値のヒストグラムを比較し、この評価値のヒストグラムに基づいて法則性があるか否かを判断し、規則性がある場合に最適値であると判定処理するようにしているので、遺伝子アルゴリズムを用いた解が最適値であるか否かを確実に判定することができ、その結果、演算時間の短縮を図ることができ、演算効率の向上を図ることができる。
【００１７】
請求項５に記載の発明によれば、変動値付与処理は、あらかじめ備えられた変動量を徐々に変化させた複数の変動遺伝子群に基づいて変動量を付与するものであるので、変動量の付与処理を効率よく行うことができる。
【００１８】
請求項６に記載の発明によれば、個体選択処理により評価結果が最小値のものを最良値として選択するとともに、変動値付与処理により、変動量を「＋側」に変化させることにより、適正に最適値であるか否かを判定することかできる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明に係る最適値の判定装置の実施の形態を図面を参照して説明する。
図１は遺伝的アルゴリズムを用いた最適値の判定装置の構成図である。
【００２０】
本実施形態の遺伝的アルゴリズムを用いた最適値の判定装置１は、コンピュータなどにより構成され、図１に示すように、個体生成部２と、個体評価値計算部３と、個体選択部４と、個体交叉部５と、突然変異部６と、変動値付与部７と、判定部８とを備えている。
【００２１】
ここで、本実施形態においては、本実施形態の最適値の判定装置１が、鉄道路線において、踏切遮断時間の最短時間を設定する場合に適用される例について説明する。
【００２２】
個体生成部２は、複数個の染色体からなる個体（遺伝子）を初期の個体として複数個生成する機能を有するものであり、本実施形態では、図２に示すように、生成すべき親染色体の個数がｍ個に設定されているものとする。
本実施形態においては、個体生成部２は、例えば、鉄道路線における駅出発時間を微動させる値として各個体を生成するものである。
【００２３】
個体評価値計算部３は、個体生成部２により生成された複数個の個体の各々の評価関数値を、所定の手順に従って算出する処理を行うように構成されており、例えば、評価関数値が最小になるようにするものである。
【００２４】
個体選択部４は、個体評価計算部による評価結果を参照して、複数個の個体のうち最良値を選択する処理を行うように構成されており、例えば、個体値から最小値のものを２つ選択する。本実施形態においては、図３に示すように、「個体１」および「個体４」が最良値として選択されることになる。
【００２５】
個体交叉部５は、個体選択部４により選択された２つの個体を親個体として、これら各親個体を交叉させ、子個体を生成する処理を行うように構成されている。
本実施形態においては、図４に示すように、個体選択部４により選択された「個体１」および「個体４」を所定の交叉位置で交叉させて「子個体１」および「子個体２」をそれぞれ生成するように構成されている。
【００２６】
突然変異部６は、予め設定された突然変異確率に従って、遺伝的アルゴリズムの突然変異処理をそれぞれ実行する処理を行うように構成されており、本実施形態においては、図５に示すように、例えば、「子個体２」の一部を所定の突然変異確率に基づいて突然変異させるものとする。
【００２７】
変動値付与部７は、ある時点での解およびそれを導出する個体に対して変動遺伝子群から選択した変動値を付与する処理を行うように構成されている。さらに、変動値付与部７は、変動値を付与された個体について評価値のヒストグラムを作成するとともに、評価値の平均、分散を計算する処理を行うように構成されている。この処理は、変動値を徐々に大きく設定しながら、繰り返し評価値のヒストグラムを作成するとともに、評価値の平均、分散を計算する処理を行う。
【００２８】
本実施形態においては、例えば、変動範囲が小さい方から、例えば、［０，＋５］、［０，＋５，＋１０］、［０，＋５，＋１０，＋１５］、［０，＋５，＋１０，＋１５，＋２０］といった変動量をあらかじめ設定するようになっている。例えば、図６に示すように、「個体１」から「個体３」について、所定の「変動遺伝子群１」、「変動遺伝子群２」といった変動遺伝子群をあらかじめ設定しておくものとする。
【００２９】
なお、本実施形態においては、個体選択部４において、最良値として最小値を選択するようにしているので、変動量を「＋側」に設定するようにしているが、個体選択部４において、最良値として最大値を選択するようにした場合には、変動量を「−側」に設定するようにすればよい。
また、変動量についても、本実施形態においては、「＋５」単位で変動量を大きく設定するようにしているが、いずれの値を変動量として設定するようにしてもよい。
【００３０】
判定部８は、変動値付与部７により、繰り返して変動値を付与された個体についての評価値のヒストグラムを比較し、この評価値のヒストグラムに基づいて法則性があるか否かを判断する処理を行うように構成されている。
すなわち、図７に示すように、評価値が最適値である場合には、変動値を大きくしていった場合に、得られた評価値の平均値が徐々に最適解から遠ざかり、評価値のヒストグラムに規則性が認められるので、この場合には、最適値であると判定する。一方、図８に示すように、最適値でない場合には、得られた解の平均値がばらばらとなり、規則性が認められないことになる。よってこの場合は、最適値でないと判定する。
【００３１】
次に、前述の最適値の判定装置１を用いた最適値の判定方法について図９に示すフローチャートを参照して説明する。
【００３２】
まず、判定装置１が動作を開始すると、個体生成部２は、鉄道路線における駅出発時間を微動させる値として複数個の染色体からなるｍ個の個体を生成する（ＳＴ１）。
続いて、個体評価値計算部３により、個体生成部２により生成された複数個の個体の各々の評価関数値を算出する（ＳＴ２）。
【００３３】
その後、個体選択部４により、個体評価計算部による評価結果を参照して、複数個の個体のうち最小値となる「個体１」および「個体４」の２つの個体を選択する（ＳＴ３）。
そして、個体交叉部５により、個体選択部４により選択された２つの個体を親個体として、これら各親個体を交叉させ、「子個体１」および「子個体２」をそれぞれ生成する（ＳＴ４）。
【００３４】
この個体交叉部５により生成された個体について、突然変異部６により、予め設定された突然変異確率に従って、遺伝的アルゴリズムの突然変異処理を行い、「子個体２」の一部を所定の突然変異確率に基づいて突然変異させる（ＳＴ５）。
【００３５】
前述の処理をある一定時間行った後、変動値付与部７により、ある時点での解およびそれを導出する個体に対して変動遺伝子群から選択した変動値を付与し（ＳＴ６）、変動値を徐々に大きくしながら付与された個体について評価値のヒストグラムを作成するとともに、評価値の平均、分散を計算する（ＳＴ７）。
【００３６】
そして、評価部により、変動値付与部７に作成された評価値のヒストグラムを比較し、この評価値のヒストグラムに基づいて法則性があるか否かを判断し（ＳＴ８）、変動値を大きくしていった場合に、得られた解の平均値が徐々に最適解から遠ざかり、評価値のヒストグラムに規則性が認められた場合には、最適値であると判定する（ＳＴ８：YES）。そして、最適値であると判定された場合は、計算を終了する。
一方、得られた解の平均値がばらばらとなり、規則性が認められない場合は、最適値でないと判定する（ＳＴ８：NO）。そして、最適値でないと判断された場合は、再び、遺伝子アルゴリズムによる計算を続行する。
【００３７】
したがって、本実施形態においては、変動値付与部７により、変動値を徐々に大きくしながら付与された個体について作成された評価値のヒストグラムに基づいて法則性があるか否かを判断し、評価値のヒストグラムに規則性が認められた場合には、最適値であると判定するようにしているので、遺伝子アルゴリズムを用いた解が最適値であるか否かを確実に判定することができ、その結果、演算時間の短縮を図ることができ、演算効率の向上を図ることができる。
【００３８】
なお、前記実施形態においては、本実施形態の最適値の判定装置１が、鉄道路線において、踏切遮断時間の最短時間を設定する場合に適用される例について説明したが、これに限定されるものではなく、遺伝子アルゴリズムを用いて演算する対象のいずれについても適用することが可能である。
【００３９】
また、前記実施形態においては、１つのコンピュータにより最適値の判定装置１を１つのコンピュータにより構成する場合について説明したが、例えば、図１０に示すように、マスター端末９と、複数のスレーブ端末１０，１０…とにより最適値の判定装置１を構成するようにしてもよい。
【００４０】
この場合、各スレーブ端末１０は、個体生成部と、個体評価値計算部と、個体選択部と、個体交叉部と、突然変異部と、変動値付与部とをそれぞれ備えるとともに、マスター端末９は、判定部を備えるように構成し、各スレーブ端末１０により、評価値の計算および変動範囲ごとに計算を行い、マスター端末９により、スレーブ端末による計算結果に基づいて最適値の判定を行う。
これにより、最適値の判定処理をより迅速に行うことが可能となる。
【図面の簡単な説明】
【００４１】
【図１】本発明に係る最適値の判定装置の実施形態を示す構成図である。
【図２】本実施形態の個体生成部における個体の例を示す説明図である。
【図３】本実施形態の個体評価値計算部における計算結果の例を示す説明図である。
【図４】本実施形態の個体交叉部における交叉例を示す説明図である。
【図５】本実施形態の突然変異部における突然変異例を示す説明図である。
【図６】本実施形態における変動遺伝子群の例を示す説明図である。
【図７】本実施形態における評価値が規則性をもって最適値であると判定される場合のヒストグラムの例を示すグラフである。
【図８】本実施形態における評価値が規則性をもたず最適値でないと判定される場合のヒストグラムの例を示すグラフである。
【図９】本発明に係る最適値の判定方法を示すフローチャートである。
【図１０】本発明の最適値の判定装置の変形例を示す構成図である。
【符号の説明】
【００４２】
１  最適値判定装置
２  個体生成部
３  個体評価値計算部
４  個体選択部
５  個体交叉部
６  突然変異部
７  変動値付与部
８  判定部
９  マスター端末
１０  スレーブ端末
【図１】
2009020562.tif 000003
【図２】
2009020562.tif 000004
【図３】
2009020562.tif 000005
【図４】
2009020562.tif 000006
【図５】
2009020562.tif 000007
【図６】
2009020562.tif 000008
【図７】
2009020562.tif 000009
【図８】
2009020562.tif 000010
【図９】
2009020562.tif 000011
【図１０】
2009020562.tif 000012