(57)【特許請求の範囲】
【請求項１】
問題に対する解の探索空間を探索して最適解を求める問題解決演算装置であって、
前記問題および探索パラメータ値を入力する入力部と、
入力された問題に対する解候補となる染色体パターンの集団を格納するメモリと、
前記染色体パターンの集団に対して、前世代の染色体パターンを選択する生殖処理、または該前世代の２つの染色体パターンの一部のコピーを組み合わせて染色体パターンを生成する交叉処理を施す複製／交叉処理部と、
前記染色体パターンの集団に対して、染色体パターンの指定位置の内容を前記探索パラメータ値により指定される確率で他の位置の内容と交換する突然変異処理を施す突然変異処理部と、
前記染色体パターンの集団の各染色体パターンの評価値を算出する評価値計算処理部と、
１つの世代に属する複数の染色体パターンにコーディングされた値の標準偏差に対して予め定められた規定値と、探索実行回数に対して予め定められた規定値と、ジェネレーションの値の増加に対する染色体パターンの評価値の増加の割合を示す評価値の伸び率に対して予め定められた規定値とを保持し、前記複製／交叉処理部および突然変異処理部による各処理の組み合わせを用いて探索を行う状態における探索過程を観測して、標準偏差が該標準偏差の規定値を下回るという第１の条件、１つの状態における探索実行回数が該探索実行回数の規定値を上回るという第２の条件、および評価値の伸び率が該伸び率の規定値を下回るという第３の条件がそれぞれ成立するか否かを判定する評価観測処理部と、
前記問題解決演算装置が探索を行う複数の状態の１つを示す遷移フラグであって、各状態から遷移する先の状態を予め定めた遷移順序に従って値が更新されるような遷移フラグを保持し、前記第１の条件が成立したとき、または、前記第２の条件と前記第３の条件が成立したときに、該遷移フラグの値を現在の状態の遷移先である次の状態に合わせて更新し、更新された遷移フラグの値により選択される状態で探索を行うための制御信号を前記複製／交叉処理部および突然変異処理部に出力して該複製／交叉処理部および突然変異処理部による各処理を選択的に組み合わせることで前記問題解決演算装置を該現在の状態から該次の状態へ遷移させて、該現在の状態とは異なる組み合わせの処理を前記染色体パターンの集団に適用する状態遷移を複数回繰り返し、該現在の状態および次の状態に共通する処理に対しては、該現在の状態と該次の状態とでそれぞれ異なる探索パラメータ値を適用する遷移制御処理部と、
探索終了条件が満たされたとき、探索により変更された染色体パターンの集団を出力する出力部と
を備えることを特徴とする問題解決演算装置。
【請求項２】
問題に対する解の探索空間を探索して最適解を求める問題解決演算装置であって、
前記問題および探索パラメータ値を入力する入力部と、
入力された問題に対する解候補となる染色体パターンの集団を格納するメモリと、
前記染色体パターンの集団に対して、前世代の染色体パターンを選択する生殖処理、または該前世代の２つの染色体パターンの一部のコピーを組み合わせて染色体パターンを生成する交叉処理を施す複製／交叉処理部と、
前記染色体パターンの集団に対して、染色体パターンの指定位置の内容を前記探索パラメータ値により指定される確率で他の位置の内容と交換する突然変異処理を施す突然変異処理部と、
前記染色体パターンの集団の各染色体パターンの評価値を算出する評価値計算処理部と、
１つの世代に属する複数の染色体パターンにコーディングされた値の標準偏差に対して予め定められた規定値と、探索実行回数に対して予め定められた規定値と、ジェネレーションの値の増加に対する染色体パターンの評価値の増加の割合を示す評価値の伸び率に対して予め定められた規定値とを保持し、前記複製／交叉処理部および突然変異処理部による各処理の組み合わせを用いて探索を行う状態における探索過程を観測して、標準偏差が該標準偏差の規定値を下回るという第１の条件、１つの状態における探索実行回数が該探索実行回数の規定値を上回るという第２の条件、および評価値の伸び率が該伸び率の規定値を下回るという第３の条件がそれぞれ成立するか否かを判定する評価観測処理部と、
前記問題解決演算装置が探索を行う複数の状態の１つを示す遷移フラグであって、各状態から遷移する先の状態を予め定めた遷移順序に従って値が更新されるような遷移フラグを保持し、前記第１の条件が成立したとき、または、前記第２の条件と前記第３の条件が成立したときに、該遷移フラグの値を現在の状態の遷移先である次の状態に合わせて更新し、更新された遷移フラグの値により選択される状態で探索を行うための制御信号を前記複製／交叉処理部および突然変異処理部に出力して該複製／交叉処理部および突然変異処理部による各処理を選択的に組み合わせることで前記問題解決演算装置を該現在の状態から該次の状態へ遷移させて、該現在の状態とは異なる組み合わせの処理を前記染色体パターンの集団に適用する状態遷移を複数回繰り返し、該現在の状態および次の状態に共通する処理に対しては、該現在の状態と該次の状態とでそれぞれ異なる探索パラメータ値を適用する遷移制御処理部と、
探索実行回数が最大実行回数に達したとき、探索により変更された染色体パターンの集団を出力する出力部と
を備えることを特徴とする問題解決演算装置。
【請求項３】
評価値が劣る下位の染色体パターンに対して山登り処理を施す山登り処理部をさらに備え、前記遷移制御処理部は、前記制御信号を用いて前記複製／交叉処理部、突然変異処理部、および山登り処理部による各処理を選択的に組み合わせることを特徴とする請求項２記載の問題解決演算装置。
【請求項４】
問題に対する解の探索空間を探索して最適解を求める問題解決演算装置であって、
前記問題と第１、第２、および第３の探索パラメータ値を入力する入力部と、
入力された問題に対する解候補となる染色体パターンの集団を格納するメモリと、
前記染色体パターンの集団に対して、前世代の染色体パターンを選択する生殖処理、または該前世代の２つの染色体パターンの一部のコピーを組み合わせて染色体パターンを生成する交叉処理を施す複製／交叉処理部と、
前記染色体パターンの集団に対して、染色体パターンの指定位置の内容を前記第１の探索パラメータ値により指定される確率で他の位置の内容と交換する突然変異処理を施す突然変異処理部と、
前記染色体パターンの集団から前記第２の探索パラメータ値により指定される比率で染色体パターンを選び、選ばれた染色体パターンの近傍を探索する近傍探索処理を行う近傍探索処理部と、
前記染色体パターンの集団に対して、染色体パターンの持つ値の順序を反転させる反転処理部と、
前記染色体パターンの集団に対して、前記第３の探索パラメータ値により指定される比率で、ランダムに発生させた複数の新しい染色体パターンを追加するリクルートメント処理部と、
前記染色体パターンの集団の各染色体パターンの評価値を算出する評価値計算処理部と、
１つの世代に属する複数の染色体パターンにコーディングされた値の標準偏差に対して予め定められた規定値と、探索実行回数に対して予め定められた規定値と、ジェネレーションの値の増加に対する染色体パターンの評価値の増加の割合を示す評価値の伸び率に対して予め定められた規定値とを保持し、前記複製／交叉処理部、突然変異処理部、近傍探索処理部、反転処理部、およびリクルートメント処理部による各処理の組み合わせを用いて探索を行う状態における探索過程を観測して、標準偏差が該標準偏差の規定値を下回るという第１の条件、１つの状態における探索実行回数が該探索実行回数の規定値を上回るという第２の条件、および評価値の伸び率が該伸び率の規定値を下回るという第３の条件がそれぞれ成立するか否かを判定する条件処理部と、
前記問題解決演算装置が探索を行う複数の状態の１つを示す遷移フラグであって、各状態から遷移する先の状態を予め定めた遷移順序に従って値が更新されるような遷移フラグを保持し、前記第１の条件が成立したとき、または、前記第２の条件と前記第３の条件が成立したときに、該遷移フラグの値を現在の状態の遷移先である次の状態に合わせて更新し、更新された遷移フラグの値により選択される状態で探索を行うための制御信号を前記複製／交叉処理部、突然変異処理部、近傍探索処理部、反転処理部、およびリクルートメント処理部に出力して該複製／交叉処理部、突然変異処理部、近傍探索処理部、反転処理部、およびリクルートメント処理部による各処理を選択的に組み合わせることで前記問題解決演算装置を該現在の状態から該次の状態へ遷移させて、該現在の状態とは異なる組み合わせの処理を前記染色体パターンの集団に適用する状態遷移を複数回繰り返し、該現在の状態および次の状態に共通する処理に対しては、該現在の状態と該次の状態とでそれぞれ異なる探索パラメータ値を適用する遷移制御処理部と、
探索実行回数が最大実行回数に達したとき、探索により変更された染色体パターンの集団を出力する出力部と
を備えることを特徴とする問題解決演算装置。
【請求項５】
前記染色体パターンの集団に対して、山登り処理を施す山登り処理部をさらに備え、前記遷移制御処理部は、前記制御信号を用いて前記複製／交叉処理部、突然変異処理部、および山登り処理部による各処理を選択的に組み合わせることを特徴とする請求項４記載の問題解決演算装置。
【請求項６】
前記山登り処理部は、
ａ．前記染色体パターンの集団から選んだ山登り処理の初期の染色体パターンの中の隣接する２つの遺伝子を置換したときの前記評価値のゲインを求め、
ｂ．前記評価値のゲインが最も大きくなる置換を行い、
ｃ．既に行った置換によりゲインが影響を受けない範囲で、該ゲインが正となる置換を行うことを繰り返して中間の染色体パターンを求め、
ｄ．該中間の染色体パターンを前記初期の染色体パターンとして用いて、前記ａ、ｂ、およびｃの各処理を繰り返し、
ｅ．前記ゲインが正となる置換がなくなれば処理を終えて、山登り処理の最後の染色体パターンを得る
ことを特徴とする請求項５記載の問題解決演算装置。
【請求項７】
問題解決演算装置により問題に対する解の探索空間を探索して最適解を求める問題解決演算方法であって、
入力部が、前記問題および探索パラメータ値を入力し、
複製／交叉処理部が、メモリに格納された、入力された問題に対する解候補となる染色体パターンの集団に対して、前世代の染色体パターンを選択する生殖処理、または該前世代の２つの染色体パターンの一部のコピーを組み合わせて染色体パターンを生成する交叉処理を施し、突然変異処理部が、該メモリに格納された該染色体パターンの集団に対して、染色体パターンの指定位置の内容を前記探索パラメータ値により指定される確率で他の位置の内容と交換する突然変異処理を施すことで、該染色体パターンの集団を変更し、
評価値計算処理部が、前記メモリに格納された前記染色体パターンの集団を参照して、該染色体パターンの集団の各染色体パターンの評価値を算出し、
評価観測処理部が、１つの世代に属する複数の染色体パターンにコーディングされた値の標準偏差に対して予め定められた規定値と、探索実行回数に対して予め定められた規定値と、ジェネレーションの値の増加に対する染色体パターンの評価値の増加の割合を示す評価値の伸び率に対して予め定められた規定値とを保持し、前記複製／交叉処理部および突然変異処理部による各処理の組み合わせを用いて探索を行う状態における探索過程を観測して、標準偏差が該標準偏差の規定値を下回るという第１の条件、１つの状態における探索実行回数が該探索実行回数の規定値を上回るという第２の条件、および評価値の伸び率が該伸び率の規定値を下回るという第３の条件がそれぞれ成立するか否かを判定し、
遷移制御処理部が、前記問題解決演算装置が探索を行う複数の状態の１つを示す遷移フラグであって、各状態から遷移する先の状態を予め定めた遷移順序に従って値が更新されるような遷移フラグを保持し、前記第１の条件が成立したとき、または、前記第２の条件と前記第３の条件が成立したときに、該遷移フラグの値を現在の状態の遷移先である次の状態に合わせて更新し、更新された遷移フラグの値により選択される状態で探索を行うための制御信号を前記複製／交叉処理部および突然変異処理部に出力して該複製／交叉処理部および突然変異処理部による各処理を選択的に組み合わせることで前記問題解決演算装置を該現在の状態から該次の状態へ遷移させて、該現在の状態とは異なる組み合わせの処理を前記染色体パターンの集団に適用する状態遷移を複数回繰り返し、該現在の状態および次の状態に共通する処理に対しては、該現在の状態と該次の状態とでそれぞれ異なる探索パラメータ値を適用し、
出力部が、探索実行回数が最大実行回数に達したとき、探索により変更された染色体パターンの集団を出力する
ことを特徴とする問題解決演算方法。
【請求項８】
問題に対する解の探索空間を探索して最適解を求める問題解決演算装置であって、
前記問題および探索パラメータ値を入力する入力部と、
入力された問題に対する解候補となる染色体パターンの集団を格納するメモリと、
前記染色体パターンの集団に対して、前世代の染色体パターンを選択する生殖処理、または該前世代の２つの染色体パターンの一部のコピーを組み合わせて染色体パターンを生成する交叉処理を施す複製／交叉処理部と、
前記染色体パターンの集団に対して、染色体パターンの指定位置の内容を前記探索パラメータ値により指定される確率で他の位置の内容と交換する突然変異処理を施す突然変異処理部と、
前記染色体パターンの集団の各染色体パターンの評価値を算出する評価値計算処理部と、
１つの世代に属する複数の染色体パターンにコーディングされた値の標準偏差に対して予め定められた規定値と、探索実行回数に対して予め定められた規定値と、ジェネレーションの値の増加に対する染色体パターンの評価値の増加の割合を示す評価値の伸び率に対して予め定められた規定値とを保持し、前記複製／交叉処理部および突然変異処理部による各処理の組み合わせを用いて探索を行う状態における探索過程を観測して、標準偏差が該標準偏差の規定値を下回るという第１の条件、１つの状態における探索実行回数が該探索実行回数の規定値を上回るという第２の条件、および評価値の伸び率が該伸び率の規定値を下回るという第３の条件がそれぞれ成立するか否かを判定する評価観測処理部と、
前記問題解決演算装置が探索を行う複数の状態の１つを示す遷移フラグであって、各状態から遷移する先の状態を予め定めた遷移順序に従って値が更新されるような遷移フラグを保持し、前記第１の条件が成立したとき、または、前記第２の条件と前記第３の条件が成立したときに、該遷移フラグの値を現在の状態の遷移先である次の状態に合わせて更新し、更新された遷移フラグの値により選択される状態で探索を行うための制御信号を前記複製／交叉処理部および突然変異処理部に出力して該複製／交叉処理部および突然変異処理部による各処理を選択的に組み合わせることで前記問題解決演算装置を該現在の状態から該次の状態へ遷移させて、該現在の状態とは異なる組み合わせの処理を前記染色体パターンの集団に適用する状態遷移を複数回繰り返し、該現在の状態および次の状態に共通する処理に対しては、該現在の状態と該次の状態とでそれぞれ異なる探索パラメータ値を適用する遷移制御処理部と、
探索実行時間が最大実行時間に達したとき、探索により変更された染色体パターンの集団を出力する出力部と
を備えることを特徴とする問題解決演算装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、例えばトラベリングセールスマン問題などのような組み合わせ最適化問題の解決方式に係り、さらに詳しくはそれぞれ複数の最適解探索手法を組み合わせた複数の探索状態の間での状態遷移の概念を導入することによって、最適解の探索を高速化する、状態遷移の概念を導入した問題解決演算装置およびその方法に関する。
【０００２】
【従来の技術】
本発明が対象とする問題解決演算装置は、いわゆる数理計画問題の解を求める装置である。対象とする数理計画問題としてはトラヒック制御、特に通信ネットワークにおけるパケットなどの最適伝送経路、または電力ネットワークの配電経路の制御、交通システムにおける物流配送経路の決定、列車ダイヤ、バスダイヤ、及びフライトスケジュールなどのスケジュール問題、並列処理プロセッサの間の負荷分散方式、及びプロセッサ間の結合網のルーティング制御などがある。
【０００３】
これらの数理計画問題の中で、「Ｎ個の都市を重複を許さずに最短距離で回れ」と言うトラベリングセールスマン問題に対しては、全ての組み合わせを探索して最適解を求める手法を適用すると都市数Ｎの増加と共に計算時間が指数関数的に増加する。このような問題はいわゆるＮＰ困難（ノン・デターミニスティック・ポリノミアル・ハード）と言われ、いわゆる多項式以内の時間では、最適解を求めるアルゴリズムが存在しないことがすでに判明している。
【０００４】
このような数理計画問題の最適解を求める従来の最適化手法を、厳密性、すなわち得られる解の最適性の観点から見ると▲１▼厳密な最適解を求める方法としての厳密解法と、▲２▼近似最高解を高速に求める方法としての近似解法とに大別される。
【０００５】
また解の探索方法と言う観点から見ると、最適化手法は▲３▼厳密な列挙、あるいは等化的な列挙によって厳密な最適解を求める列挙共通手法、▲４▼最適解、あるいは近似解を生成するためのルールを用いて、ただ１つの解にヒューリスティックにしぼり込む手法としての発見的手法、及び▲５▼▲３▼と▲４▼の中間的方法であって、解空間の部分領域を探索することによって近似最適解を求める手法としての探索的手法との３つに分類される。
【０００６】
このような最適化手法の１つとしての遺伝的アルゴリズム（ＧＡ）は、前述の▲２▼と▲５▼とに分類される方法であって、ランダムな遺伝子を持つ複数の個体からなる初期集団を生成した後に、生殖（リプロダクション）、交叉（クロスオーバ）、及び突然変異（ミューテーション）と言う３種類の遺伝子操作を用いて、最適解の探索を探索終了条件が満たされるまで繰り返すことを基本とする。
【０００７】
ここで生殖とは、前世代の個体のうちのいくつかをランダムに選択して現世代の個体を決定する処理であり、その結果の個体に対して次の交叉の処理が行われる。交叉は個体の一部を交換する、すなわち２つの個体の遺伝子型を部分的に相互に入れ替えることによって子孫としての新しい個体を生成する処理であり、また突然変異は子孫となる各個体の遺伝子の一部を対立遺伝子に交換、あるいは変異させる処理であり、従来の遺伝的アルゴリズムでは最適解探索の終了条件が満たされるまで、これらの３つの遺伝子操作が繰り返し行われていた。
【０００８】
【発明が解決しようとする課題】
このような数理計画問題に対して、遺伝的アルゴリズムを適用して最適解を探索するために、世代交代を繰り返し、ジェネレーションの値が大きくなると、ジェネレーションの値の増加に対する解の評価値としてのフィットネス値の増加の割合が減少する、すなわちフィットネス値の伸び率が鈍化すると言う問題点があった。
【０００９】
解を探索すべき問題の規模が大きく、また複雑な場合には、この問題点は特に重要であり、現実的な時間内に実用的なフィットネス値を満足する解を探索することが難しいと言う問題点があった。
【００１０】
本発明は、ＧＡアルゴリズムを用いて、大規模で複雑な問題に対しても、ジェネレーション値が小さな段階で良好な評価値、あるいは、大きなフィットネス値を持つ解に到達することを可能にすることを目的とする。
【００１１】
【課題を解決するための手段】
図１は本発明の原理ブロック図である。同図は、数理計画問題などの解決を目的として、その問題に対する解の探索空間を探索して最適解を求めるために、状態遷移の概念を導入した問題解決演算装置の原理構成ブロック図である。
【００１２】
図１において、最適解探索手段１は一般に複数個設けられ、それぞれ１つ以上の最適解探索手法の組み合わせを用いた状態で最適解を探索するものである。ここで最適解探索手法は、例えば遺伝的アルゴリズムにおいては前述の生殖、交叉、及び突然変異などの手法であり、また遺伝的アルゴリズム以外の探索手法も含むものである。
【００１３】
探索過程観測及び状態遷移手段２は、最適解探索手段１の１つによる最適解の探索過程を観測し、その探索の過程において予め定められた条件が満たされた時、複数の最適解探索手段１のうちの他の１つによる探索に状態を遷移させるものである。
【００１４】
また、本発明のもう１つの問題解決演算装置は、入力部、メモリ、複製／交叉処理部、突然変異処理部、評価値計算処理部、評価観測処理部、遷移制御処理部、および出力部を備え、問題に対する解の探索空間を探索して最適解を求める。
【００１５】
入力部は、問題および探索パラメータ値を入力し、メモリは、入力された問題に対する解候補となる染色体パターンの集団を格納する。複製／交叉処理部は、染色体パターンの集団に対して、前世代の染色体パターンを選択する生殖処理、または前世代の２つの染色体パターンの一部のコピーを組み合わせて染色体パターンを生成する交叉処理を施し、突然変異処理部は、染色体パターンの集団に対して、染色体パターンの指定位置の内容を探索パラメータ値により指定される確率で他の位置の内容と交換する突然変異処理を施す。評価値計算処理部は、染色体パターンの集団の各染色体パターンの評価値を算出し、評価観測処理部は、１つの世代に属する複数の染色体パターンにコーディングされた値の標準偏差に対して予め定められた規定値と、探索実行回数に対して予め定められた規定値と、ジェネレーションの値の増加に対する染色体パターンの評価値の増加の割合を示す評価値の伸び率に対して予め定められた規定値とを保持し、複製／交叉処理部および突然変異処理部による各処理の組み合わせを用いて探索を行う状態における探索過程を観測して、標準偏差が標準偏差の規定値を下回るという第１の条件、１つの状態における探索実行回数が探索実行回数の規定値を上回るという第２の条件、および評価値の伸び率が伸び率の規定値を下回るという第３の条件がそれぞれ成立するか否かを判定する。
【００１６】
遷移制御処理部は、問題解決演算装置が探索を行う複数の状態の１つを示す遷移フラグであって、各状態から遷移する先の状態を予め定めた遷移順序に従って値が更新されるような遷移フラグを保持し、第１の条件が成立したとき、または、第２の条件と第３の条件が成立したときに、遷移フラグの値を現在の状態の遷移先である次の状態に合わせて更新し、更新された遷移フラグの値により選択される状態で探索を行うための制御信号を複製／交叉処理部および突然変異処理部に出力して複製／交叉処理部および突然変異処理部による各処理を選択的に組み合わせることで問題解決演算装置を現在の状態から次の状態へ遷移させて、現在の状態とは異なる組み合わせの処理を染色体パターンの集団に適用する状態遷移を複数回繰り返し、現在の状態および次の状態に共通する処理に対しては、現在の状態と次の状態とでそれぞれ異なる探索パラメータ値を適用する。出力部は、探索実行回数が最大実行回数に達したとき、探索により変更された染色体パターンの集団を出力する。
本発明のさらに別の問題解決演算装置は、入力部、メモリ、複製／交叉処理部、突然変異処理部、評価値計算処理部、評価観測処理部、遷移制御処理部、および出力部を備え、問題に対する解の探索空間を探索して最適解を求める。
入力部は、問題および探索パラメータ値を入力し、メモリは、入力された問題に対する解候補となる染色体パターンの集団を格納する。複製／交叉処理部は、染色体パターンの集団に対して、前世代の染色体パターンを選択する生殖処理、または前世代の２つの染色体パターンの一部のコピーを組み合わせて染色体パターンを生成する交叉処理を施し、突然変異処理部は、染色体パターンの集団に対して、染色体パターンの指定位置の内容を探索パラメータ値により指定される確率で他の位置の内容と交換する突然変異処理を施す。評価値計算処理部は、染色体パターンの集団の各染色体パターンの評価値を算出し、評価観測処理部は、１つの世代に属する複数の染色体パターンにコーディングされた値の標準偏差に対して予め定められた規定値と、探索実行回数に対して予め定められた規定値と、ジェネレーションの値の増加に対する染色体パターンの評価値の増加の割合を示す評価値の伸び率に対して予め定められた規定値とを保持し、複製／交叉処理部および突然変異処理部による各処理の組み合わせを用いて探索を行う状態における探索過程を観測して、標準偏差が標準偏差の規定値を下回るという第１の条件、１つの状態における探索実行回数が探索実行回数の規定値を上回るという第２の条件、および評価値の伸び率が伸び率の規定値を下回るという第３の条件がそれぞれ成立するか否かを判定する。
遷移制御処理部は、問題解決演算装置が探索を行う複数の状態の１つを示す遷移フラグであって、各状態から遷移する先の状態を予め定めた遷移順序に従って値が更新されるような遷移フラグを保持し、第１の条件が成立したとき、または、第２の条件と第３の条件が成立したときに、遷移フラグの値を現在の状態の遷移先である次の状態に合わせて更新し、更新された遷移フラグの値により選択される状態で探索を行うための制御信号を複製／交叉処理部および突然変異処理部に出力して複製／交叉処理部および突然変異処理部による各処理を選択的に組み合わせることで問題解決演算装置を現在の状態から次の状態へ遷移させて、現在の状態とは異なる組み合わせの処理を染色体パターンの集団に適用する状態遷移を複数回繰り返し、現在の状態および次の状態に共通する処理に対しては、現在の状態と次の状態とでそれぞれ異なる探索パラメータ値を適用する。出力部は、探索終了条件が満たされたとき、探索により変更された染色体パターンの集団を出力する。
【００１７】
【作用】
本発明においては、１つ以上の最適解探索手法の組み合わせを用いた状態で最適解の探索が行われる。この最適解探索手法としては、前述のように遺伝的アルゴリズムにおけるいくつかの手法、及び遺伝的アルゴリズム以外の最適化手法を組み合わせたものが用いられ、また複数の最適解探索手段において同一の手法が用いられる場合には、例えば探索のパラメータとして別の値が用いられることもある。
【００１８】
１つの最適解探索手段１によってある最適解探索手法の組み合わせ状態で最適解探索が行われている場合、その探索過程が観測され、例えば解のフィットネス値の伸び率が規定値を下回るなどのように予め定められた条件が達成された時、その状態での最適解の探索は中止され、最適解探索手法の別の組み合わせ（または探索パラメータの変化）を用いた状態での探索が他の最適解探索手段１によって行われる。すなわち解の探索状態の遷移が行われることになる。
【００１９】
以上のように、本発明によればそれぞれ１つ以上の最適解探索手法の組み合わせを用いた状態で最適解を探索する複数の最適解探索手段１の間で探索の状態遷移が行われ、ある最適解探索手段１による探索の効果が低下した時には別の最適解探索手段１により最適解探索が続行される。
【００２０】
【実施例】
図２は本発明の問題解決演算装置の基本構成ブロック図である。同図において演算装置は大きく探索モジュール１１と制御モジュール１２とで構成され、探索モジュール１１内には複数の探索状態１６−１、１６−２、１６−３、・・・、１６−Ｍの間を遷移する探索部１３が備えられ、また制御モジュール１２の中には観測部１４と遷移制御部１５とが備えられている。
【００２１】
探索モジュール１１は問題の入力に対して最適解を出力するものであり、探索モジュール１１内の探索部１３が取り得る複数の探索状態１６−１、・・・、１６−Ｍはそれぞれ図１の最適解探索手段１に相当し、それぞれ１つ以上の最適解探索手法を組み合わせた状態である。この最適解探索手法には遺伝的アルゴリズムの手法以外の探索手法も含まれる。
【００２２】
制御モジュール１２は探索モジュール１１の最適解探索過程を観測し、その観測結果に基づいて探索モジュール１１内の探索部１３に最適解探索状態の遷移を行わせる。観測部１４は探索された解の評価値（あるいはフィットネス値）の上昇率、すなわちジェネレーション値の変化に対するフィットネス値の変化率を観測する機能、１つの世代における個体の集団内のフィットネス値の分散などを観測する機能、探索の実行回数を観測する機能、遺伝的アルゴリズムにおけるその他の評価基準を観測する機能などを含んでいる。ある１つの状態における探索部１３による探索の効果が低下したと判定された時には、別の状態における探索部１３による探索への変更、すなわち探索状態の遷移が行われる。
【００２３】
図２における各ブロックの動作を更に説明すると、探索モジュール１１は遺伝的アルゴリズムを用いた処理中に世代毎の集団の状況、例えばフィットネス値の最大値、及び分散などを出力し、制御モジュール１２の内部の観測部１４は探索モジュール１１の出力を観測して、観測結果を状態遷移条件と比較し、その比較結果に応じて遷移制御部１５に対して状態遷移を行わせるための指示を出力する。その指示を受けた遷移制御部１５は、探索部１３の探索状態を切り替えることにより、探索モジュール１１による最適解の探索を続行させる。その動作は探索の終了条件が満足されるまで繰り返し行われる。
【００２４】
図３は本発明における最適解探索状態の状態遷移の説明図である。同図においては、与えられた問題に対する最適値を探索するための探索状態として第１の最適値探索状態２１〜第５の最適値探索状態２５の５つが設けられ、各最適値探索状態は一般に複数の最適値探索手法の組み合わせを用いた状態で最適値の探索を行う。
【００２５】
それぞれの最適値探索状態の間では、状態遷移のための遷移条件１２、２３、２５、３１、３４、４３、５１、５４が探索効果の向上の可能性に対応して設定されている。例えば、第１の最適値探索状態２１からは、第２の最適値探索状態２２に対して遷移条件１２が設定され、また第５の最適値探索状態２５からは、第１の最適値探索状態２１に対する遷移条件５１と、第４の最適値探索状態２４に対する遷移条件５４が設定されている。
【００２６】
次に前述の巡回セールスマン問題を具体例として用いて、本発明の実施例を説明する。図４、及び図５は巡回セールスマン問題における都市の配置の例である。図５は図４にその配置を示した各都市のＸ座標とＹ座標を示したものである。ここで示した１００個の都市を重複を許さずに最短距離で巡回する解を求める問題が巡回セールスマン問題である。
【００２７】
遺伝的アルゴリズムを用いた巡回セールスマン問題の解法では、まず解の候補となる巡回経路を染色体としてコーディングを行う。本実施例では、都市名を遺伝子としてセールスマンが巡回する順番に都市名を並べたものを染色体とするコーディング法を採用した。図６は解の候補のコーディング結果の例である。同図において、１番目に巡る都市名から１００番目に巡る都市名までが、各都市の番号を用いてコーディングされ、１つの解の候補が染色体として表現されている。このような巡回経路に対応する距離の総和が解のコストに対応し、そのコストの最小化をはかるのが巡回セールスマン問題である。
【００２８】
巡回セールスマン問題における解ｘの評価関数であるフィットネス関数ｆ（ｘ）は、例えば次式で表される。
【００２９】
【数１】
0003697446.tif 000002
ここで、ｄｉ（ｘ）は解ｘにおけるｉ−１番目の都市とｉ番目の都市の間の距離であり、ｎは都市の数（図４ではｎ＝１００）である。ただし、ｄ１（ｘ）は出発点から１番目の都市までの距離であり、ｄｎ（ｘ）はｎ−１番目（最後から２番目）の都市とｎ番目の都市（最後の都市であると同時に出発点でもある）の間の距離であるものとする。バイアスＫは図４の隣接する都市を結んで得られる円の直径（都市間の距離の最大値）と都市の数ｎとの積である。
【００３０】
（１）式の右辺の  外１  がこの問題における解ｘのコストを表しており、コ
【００３１】
【外１】
0003697446.tif 000003
ストが小さいほどフィットネス関数ｆ（ｘ）の値が大きくなることがわかる。
【００３２】
図７は実施例としての巡回セールスマン問題に対する状態遷移の説明図である。同図に示されるように、本実施例での最適解探索過程は状態０〜状態３の４つの状態の間で、遷移条件０１、１２、２３、３１に従って状態遷移を行うことによって実行される。
【００３３】
図８は図７における各状態での遺伝的アルゴリズムのオペレーションの組み合わせの例である。同図において状態０では前世代からの優秀個体のひきつぎ、生殖（リプロダクション，Ｒ）、及び交叉（クロスオーバ，Ｃ）の３つのオペレーションの組み合わせによって最適解の探索処理が行われる。最初の世代の場合、優秀個体は前世代の代わりに初期の個体の集団（ポピュレーション）から取り出される。この状態０は初期処理を行う状態である。
【００３４】
状態１では状態０における３つのオペレーションに加えて突然変異（ミューテーション，Ｍ）のオペレーションが組み合わされて、最適解の探索処理が行われる。本実施例では後述するように状態０と状態１での同一のオペレーション、例えば前世代からの優秀個体のひきつぎのオペレーションにおけるパラメータ、すなわち次の世代にひきつぐ優秀個体の割合を一定として処理を行ったが、このパラメータを状態０と状態１とで変化させることも当然可能である。なおこの状態１は、通常の遺伝的アルゴリズムの処理を行う状態である。
【００３５】
状態２では、状態１での４つのオペレーションに加えて更に近傍探索が行われ、この近傍探索が重点的に行われる状態である。この近傍探索は、１つの世代の集団の中でフィットネス値の大きい方からいくつかの個体を選び、各個体に対して突然変異と同様の処理を集中的に繰り返し行うものである。近傍探索においては、フィットネス値が改善される場合のみ染色体のパターンの実際の変更を行う。この近傍探索における主なパラメータの値としては、近傍探索繰り返し回数として１世代の個体当たりの回数が１以上であり、近傍探索の範囲、すなわち近傍探索を施す個体数の集団内の全個体数に対する比率は０．０以上、１．０以下である。
【００３６】
図９に近傍探索の概念を示す。図９において、染色体のパターンを変えることにより、フィットネス値が増大するような解（染色体）が探索されることがわかる。
【００３７】
状態３は前世代からの優秀個体のひきつぎと、新個体の受け入れの２つのオペレーションの組み合わせによって最適解を探索する状態であり、新たな集団を受け入れる状態である。この新個体の受け入れに対するパラメータとしての集団内の新個体の比率は、０．０から１．０の間に設定される。
【００３８】
図１０に新個体の受け入れ（リクルートメント）の概念を示す。図１０において、新個体はランダムに発生するため、その染色体のパターンは広範囲に分散することがわかる。
【００３９】
次に状態０〜３における各オペレーションに対して共通的に設定されるパラメータについて説明する。まず、１世代の染色体の総数、すなわち個体の総数であるポピュレーションのサイズは１０に設定され、前世代からの優秀個体のひきつぎの割合、すなわちジェネレーションオーバラップ率（ジェネレーションギャップ率の反対の概念）としては優秀な方から４０％を次の世代にひきつぐ操作が行われた。また、突然変異、すなわち１つの染色体における１組の遺伝子の値の交換、図６ではある１組の都市名の交換は０．０１、すなわち１％の頻度で行われた。この問題に対する突然変異操作においては、染色体の左端から１つずつ順に遺伝子の位置を指していき、指されている位置の内容を１％の確率で他の任意の位置の内容と交換していく。
【００４０】
図７における各状態の間での遷移条件は次の３つの条件の組み合わせとして設定された。第１の条件（条件１）はポピュレーションとしての１０個の染色体における各遺伝子の標準偏差の和が規定値を下回ることである。
【００４１】
図１１はこの第１の条件の説明図である。同図において、ｎ個のスロットの各々についてｍ個の染色体における各遺伝子の値（都市番号）の平均値と標準偏差が求められる。さらに、各スロット毎の標準偏差から標準偏差の和が求められ、その和が規定値を下回る場合に第１の条件が満足されたものとする。すなわち、第１の条件は各染色体をｎ次元空間における点としてとらえ、その点を表すｎ個の座標（都市番号）に対する標準偏差がある規定値以下になることで、ｎ次元空間における染色体のバラつきが小さくなることを意味する。
【００４２】
第２の条件（条件２）は探索処理の実行回数が予め定められた規定値を上回ることである。
第３の条件（条件３）はフィットネス値の伸び率が規定値を下回ることである。これはフィットネス値を表す関数ｆ（ｘ）に解候補としての染色体のｄｉ（ｘ）の値を代入して、各ジェネレーションに対するフィットネスの値を計算し、フィットネス値の変化率を求めることによって判定される。
【００４３】
図１２はこの第３の条件におけるフィットネス値の変化率の説明図である。図１２では、各ジェネレーションに属する複数の個体のフィットネス値のうち、最も大きな値がプロットされている。同図に示すようにフィットネス値の変化率は次式によって計算される。
【００４４】
【数２】
0003697446.tif 000004
引継ぎ操作を施せば、前のジェネレーションの最大のフィットネス値を持つ個体は必ず次のジェネレーションに引き継がれるため、各ジェネレーションにおけるフィットネス値の最大値は前のジェネレーションにおける最大値を下回ることはない。したがって、ジェネレーションを経るにつれて、フィットネス値の最大値は単調に増加する。
【００４５】
図７において、実施例における問題解決演算装置は初期において状態０で最適解を探索し、遷移条件０１が満足されると状態１での探索に移行する。その後は状態１→状態２→状態３→状態１→・・・の状態遷移を、例えば最大実行時間に至るまで繰り返す。
【００４６】
本実施例では遷移条件０１，１２及び２３はすべて同一とし、
第１の条件∪（第２の条件∩第３の条件）                …（３）
が成立するときに状態遷移を行うものとした。
【００４７】
すなわち本実施例では、第２の条件と第３の条件が同時に成立するか、あるいは第１の条件のみが成立する時に状態０から状態１、状態１から状態２、及び状態２から状態３への状態遷移が行われる。また状態３から状態１への遷移条件３１は第１の条件に一致するものとした。ここでは、各遷移条件の論理構造が同じという意味であり、しきい値のようなパラメータの値はそれぞれ異なったものを用いることもできる。
【００４８】
図１３は以上の説明に対応して図２に示した問題解決演算装置の基本構成を更に詳細に示したものである。同図において、図２の制御モジュール１２と探索モジュール１１はセル３０に含まれ、セル３０は入力信号を受け取る入力部３１、解を出力する出力部３２、入力データ及び探索過程における解候補などを格納するメモリ３３、解のフィットネス値を計算するフィットネス値計算処理部３４、遺伝的アルゴリズムにおける複製、交叉のオペレーションなどを実行する複製／交叉処理部３５、突然変異のオペレーションを実行する突然変異処理部３６及び前述の近傍探索を行う近傍探索処理部３７から構成されている。
【００４９】
フィットネス値計算処理部３４、複製／交叉処理部３５、突然変異処理部３６、および近傍探索処理部３７による処理を組み合わせることにより、セル３０は図２に示すＭ個の探索状態１６−１〜１６−Ｍのうちいずれの状態にも設定され得る。
【００５０】
図２の観測部１４に対応する評価観測処理部３８は標準偏差の和の規定値であるダイバーシティ・メジャ、ジェネレーションギャップ率であるジェネレーションギャップ・メジャ、フィットネス値の伸び率の規定値であるグロースレート・メジャ、及び実行回数の最大限度値としてのターミネーション・メジャに基づいて、遷移制御部１５に対応するＧＡオペレーション遷移制御処理部３９に対する必要な指示を行う。ＧＡオペレーション遷移制御処理部３９は複製／交叉処理部３５、突然変異処理部３６、および近傍探索処理部３７に対する制御信号を出力する。
【００５１】
例えばジェネレーションギャップ・メジャにより定義されるジェネレーションギャップ率は、前世代からの優秀個体の引継ぎのオペレーションを行う際のパラメータである。これは、１つのポピュレーションに含まれる個体の数に対する引き継がれる個体の数の比率を表し、このパラメータに従ってＧＡアルゴリズムとしての引継ぎのオペレーションが実行される。
【００５２】
図１３に示すようなセルを複数個設けて、それぞれが独立して最適解を探索するような並列処理を行わせれば、探索効率はさらに向上する。
図１４は、山登り法を適用することのできる複数のセルを並列に接続した本発明の問題解決演算装置の構成図である。図１４において、セル４１−１〜４１−Ｎはそれぞれマイグレーション値分配処理部５６および並列処理制御部５７に接続され、並列に処理を行う。並列処理により解の成長の速度はさらに向上する。
【００５３】
各セルは条件１処理部５２、条件２処理部５３、条件３処理部５４、ＧＡオペレーション遷移制御処理部５５、入力部４２、メモリ４３、出力部４４、フィットネス値計算処理部４５、複製／交叉処理部４６、突然変異処理部４７、近傍探索処理部４８、反転処理部４９、リクルートメント処理部５０、山登り処理部５１を備える。このうち、入力部４２、メモリ４３、出力部４４、フィットネス値計算処理部４５、複製／交叉処理部４６、突然変異処理部４７、近傍探索処理部４８の機能は、それぞれ図１３の入力部３１、メモリ３３、出力部３２、フィットネス値計算処理部３４、複製／交叉処理部３５、突然変異処理部３６、近傍探索処理部３７と基本的に同じである。
【００５４】
図１４の反転処理部４９は、染色体の遺伝子の一部の順序を反転させるオペレーションを行い、リクルートメント処理部５０は新個体の受入れのオペレーションを行う。また、山登り処理部５１は近傍探索と類似する山登り法による探索を行う。フィットネス値計算処理部４５は、標準偏差の和、各ジェネレーションにおける処理実行回数、フィットネス値の伸び率を算出して、それぞれ条件１処理部５２、条件２処理部５３、条件３処理部５４に送る。
【００５５】
条件１処理部５２、条件２処理部５３、条件３処理部５４は、これらの値をそれぞれの規定値と比較して、条件１、条件２、条件３が成立するか否かをＧＡオペレーション遷移制御処理部５５に伝える。ＧＡオペレーション遷移制御処理部５５は、図７の遷移条件０１、１２、２３、３１が成立するか否かを判定し、その結果設定される遷移フラグｓに応じてフィットネス値計算処理部４５、複製／交叉処理部４６、突然変異処理部４７、近傍探索処理部４８、反転処理部４９、リクルートメント処理部５０、山登り処理部５１を制御する。
【００５６】
マイグレーション値分配処理部５６は、各セルのメモリ４３から最もフィットネス値の大きな染色体のパターンを収集し、収集した染色体の中でさらに最も良いフィットネス値を持つものを各セルに分配する。
【００５７】
並列処理制御部５７は各セルの処理の開始と停止の同期を取り、それらに並列処理を行わせる。また、並列処理制御部５７は並列処理の制御を行うと同時に、マイグレーション値分配処理部５６をも制御する。
【００５８】
図１５および１６は、図１４の問題解決演算装置の各セルによる最適解の探索処理のフローチャートである。
図１５において処理が開始されると、まず各セルにおいて初期化の操作が行われる（ステップＳ１）。この操作により、各セルの入力部４２から問題およびパラメータが読み込まれ、メモリ４３上で初期のポピュレーションの発生が行われる。また、読み込まれた問題に応じてフィットネス関数のバイアスＫの値が決定される。
【００５９】
次に、ＧＡオペレーション遷移制御処理部５５は遷移フラグｓを０とおき、
状態０での探索処理を行うための制御信号を発生する。これにより、複製／交叉処理部４６による引継ぎ、リプロダクション、交叉の各処理と、山登り処理部５１による探索処理が続けて行われる（ステップＳ２）。
【００６０】
そして、（３）式が表す状態１への遷移条件が成立すると、ＧＡオペレーション遷移制御処理部５５は遷移フラグｓを１とおき、状態１での探索処理を行うための制御信号を発生する（ステップＳ３）。
【００６１】
図１６に示すように、状態１においては、複製／交叉処理部４６による引継ぎ、リプロダクション、交叉の各処理と、突然変異処理部４７による突然変異処理と、反転処理部４９による反転処理と、山登り処理部５１による探索処理が続けて行われる（ステップＳ４）。
【００６２】
以後、ＧＡオペレーション遷移制御処理部５５は、次の状態への遷移条件が成立するまで同じ状態での探索処理を繰り返し（ステップＳ５、ＮＯ）、次の状態への遷移条件が成立すると（ステップＳ５、ＹＥＳ）、終了条件が成立するか否かを判定する（ステップＳ６）。
【００６３】
次の状態への遷移条件とは、状態１から状態２、および状態２から状態３へ遷移する場合は（３）式により表され、状態３から状態１への場合は条件１に相当する。また、終了条件とは、例えば探索処理の最大実行回数に達することである。終了条件が成立しなければ（ステップＳ６、ＮＯ）、ＧＡオペレーション遷移制御処理部５５は遷移フラグｓを次の状態に合わせて更新し（ステップＳ７）、遷移フラグｓの値により選択される状態での探索処理を行うための制御信号を発生する（ステップＳ３）。ステップＳ７では、遷移フラグｓは１、２、３の順に更新される。
【００６４】
ｓ＝２のときは状態２に遷移し、複製／交叉処理部４６による引継ぎ、リプロダクション、交叉の各処理と、突然変異処理部４７による突然変異処理と、反転処理部４９による反転処理と、近傍探索処理部４８による近傍探索処理と、山登り処理部５１による探索処理が続けて行われる（ステップＳ４）。また、ｓ＝３のときは状態３に遷移し、複製／交叉処理部４６による引継ぎ処理と、リクルートメント処理部５０による新個体の受入れ処理が続けて行われる（ステップＳ４）。
【００６５】
終了条件が成立すると（ステップＳ６、ＹＥＳ）、ＧＡオペレーション遷移制御処理部５５は探索処理の終了を指示する制御信号を発生し、処理を終える。このとき、最後のジェネレーションの個体のうちで最もフィットネス値の大きなものが、解として出力部４４から出力される。
【００６６】
次に図１７から図２２までを参照しながら、図１４の問題解決演算装置による処理をより詳細に説明する。
図１７は、複製／交叉処理部４６による交叉処理のフローチャートであり、図１８は、交叉処理により親染色体ｐｉ、ｐｊから子染色体ｃｉ、ｃｊが生成される様子を示している。図１８では、１０個の遺伝子から成る染色体を例にとり、１〜１０の数字が各遺伝子を表している。
【００６７】
図１７において処理が開始されると、まず親染色体ｐｉ、ｐｊの２つの交叉点を決め（ステップＳ１１）、親ｐｊから子ｃｉへコピーする部分ｇｃを決める（ステップＳ１２）。このとき、各染色体の左端と右端は連結しているものとみなす。例えば図１８では、親ｐｊの３個の遺伝子８、５、７が子ｃｉへコピーされることになる。
【００６８】
次に、親ｐｉのコピーを親ｐｉ′とし、親ｐｉ′のｇｃに対応する部分（ｇｃ部分）に含まれる遺伝子の値が親ｐｊのｇｃ部分に含まれるものと同じになるように遺伝子の並べ換えを行う（ステップＳ１３）。そして、親ｐｉ′のｇｃ部分以外の遺伝子の順序が親ｐｉの対応する遺伝子の順序と同じになるようにする（ステップＳ１４）。
【００６９】
次に、親ｐｊのｇｃ部分の遺伝子を子ｃｉのｇｃ部分にコピーし（ステップＳ１５）、親ｐｉ′のｇｃ以外の部分の遺伝子を子ｃｉのｇｃ以外の部分にコピーする（ステップＳ１６）。こうして、親ｐｊの遺伝子８、５、７が子ｃｉのｇｃ部分にコピーされ、親ｐｉ′の遺伝子１、２、６、および、９、４、３、１０が子ｃｉのｇｃ以外の部分にコピーされる。
【００７０】
次に、親ｐｉと親ｐｊの立場をそっくり入れ換えて同様の処理を行うことにより、親ｐｊ′（不図示）を経て子ｃｊが生成される。このように、交叉処理においては、２つの染色体の一部をコピーして組み合わせることにより別の２つの染色体を生成する。交叉処理前の染色体内の遺伝子の配列順序は、交叉処理後の染色体内においても矛盾無く保存される。
【００７１】
図１９は、リクルートメント処理部５０による新個体の受入れ処理を示している。新個体の受入れ処理においては、各遺伝子をランダムに発生させて生成した新染色体をポピュレーションに導入する。これにより、解の多様性を高めた次世代のポピュレーションを発生する。大きなフィットネス値を持つ前のジェネレーション（前世代）の優秀個体は、複製／交叉処理部４６により次のジェネレーション（次世代）に引き継がれる。
【００７２】
図２０は、山登り処理部５１による探索処理のフローチャートであり、図２１は、この処理における隣接遺伝子の置換を示す図である。
図２０において処理が開始されると、まず全ての隣接する遺伝子ｉおよびｉ＋１の組について置換を行い、フィットネス値の増加（ゲイン）を調べる（ステップＳ２１）。この中に正のゲインがないときは（ステップＳ２２、ＮＯ）、入力された染色体をそのまま出力して処理を終了する。
【００７３】
正のゲインが１つ以上あるときは（ステップＳ２２、ＹＥＳ）、その中でゲインが最大となる置換を行い（ステップＳ２３）、行った置換によってゲインが影響を受けないような範囲で他の正のゲインの置換が残っているかどうか調べる（ステップＳ２４）。正のゲインの置換が残っていれば（ステップＳ２４、ＹＥＳ）、位置的に近い次の正のゲインの置換を行い（ステップＳ２５）、染色体を一周して正のゲインの置換がなくなるまでステップＳ２４、Ｓ２５の処理を繰り返す。
【００７４】
そして、行った置換により影響を受けない範囲での正のゲインの置換がなくなると（ステップＳ２４、ＮＯ）、ステップＳ２１に戻って、再び全ての隣接置換のフィットネス値のゲインを調べる。以後、ステップＳ２２で正のゲインがなくなるまで図２０の処理を繰り返す。このような山登り法を採用することにより、短い時間でより優秀な個体を得ることができる。
【００７５】
図２２は、反転処理部４９による反転処理の一例を示す図である。図２２において、染色体の一部の遺伝子６、２、８、５の順序が反転されて、５、８、２、６となり別の染色体が生成される。この反転処理は図８では突然変異のオペレーションの集合に含まれる。
【００７６】
図２３〜図２５は本発明の問題解決演算装置による図４の巡回セールスマン問題のシミュレーション結果である。これらの図においてオプティマムは理想的なフィットネス値（最適解のフィットネス値）を示し、ウィズ・ステートは本発明の演算装置、すなわち状態遷移の概念を導入した場合の結果を示し、ノー・ステートは状態遷移を行わない場合（状態０）の結果を示す。図２４は、図２３におけるジェネレーション０から３５０００の結果を拡大した図であり、図２５は図２４におけるフィットネス１８０００から２００００の部分を拡大した図である。
【００７７】
このシミュレーションにおいては、各集団の個体数を１６、各個体の染色体の長さを１００、交叉確率を１．０、突然変異確率を０．０１、前世代からの引継ぎ個体数を６、反転確率を０．１とした。１．０の交叉確率は、２つの親染色体から２つの子染色体を生成するとき、１．０の確率で交叉点を計算して決めることを意味する。もし、交叉確率が０．８であれば、残りの０．２の確率で交叉点を計算により決めずに、単純に片方の親染色体をそのまま子染色体とする。また、０．１の反転確率は、１つの染色体が与えられたときに、その染色体中のランダムに決めた一部分における遺伝子の反転処理を０．１の確率で行うことを意味する。
【００７８】
状態遷移の概念を用いることにより、その概念を用いない場合と比較して１／３から１／２の時間で理想的なフィットネス値に到達すること、及び状態遷移の概念を用いない場合には理想的な値、すなわちフィットネス値の最適値にいつまでたっても到達しない場合があることが分かる。
【００７９】
このように状態遷移の概念を導入することによってフィットネス値の最適値に早く収束することになるが、前述の状態２における近傍探索、及び状態３における新個体の受け入れはこの収束を早めるために特に有効である。
【００８０】
遺伝的アルゴリズムでは、集団内の個体の多様性が小さくなると、クロスオーバを行ってもフィットネス値の改善が進まなくなる。そこで個体の多様性が減少した場合には、何らかの方法で多様性を回復する必要がある。新個体の受け入れはこの多様性回復の手段として有効になる。
【００８１】
通常の突然変異の処理では、各個体を表すｎ次元空間の点が１ジェネレーションあたり１回だけ移動することになるが、山登り処理および近傍探索では１ジェネレーションあたり何回も移動が行われる。更に通常の突然変異では点の移動の結果としてのフィットネス値の変化は確率的に正にも負にもなるのに対して、山登り処理および近傍探索では必ず正、または０になるように制御される。従って、これらの探索方法を用いることにより探索空間における局所的探索が促進され、通常の突然変異の処理に比較して短時間、すなわち少ないジェネレーションの間に大きなフィットネス値を持つ点に移動できる確率が大きくなる。これらの探索方法と遺伝的アルゴリズムを適切に組み合わせれば、結果的に探索空間における大局的探索が促進される。
【００８２】
状態３での新個体の受け入れは多様性の回復のためにのみ用意された処理であり、この処理では均一化した解候補の集団の一部を新たな解候補と入れ替えることにより、集団の多様性を常に保ちつつ、よりフィットネス値の高い解に到達することができる。
【００８３】
以上の説明においては、各状態において複数の探索方法が組み合わされて最適解の探索が行われるものとしたが、例えば一部の状態において探索手法を１つだけ、例えば近傍探索のみを用いて最適解を探索することも当然可能である。
【００８４】
【発明の効果】
以上詳細に説明したように、本発明によれば一般に複数の最適化手法をそれぞれ組み合わせた複数の状態の間で、状態遷移を繰り返しながら最適解を探索することによって、従来の手法に比較して質の高い解を短時間で得ることが可能となり、例えば巡回セールスマン問題のような数理計画問題の問題解決演算の高速化に寄与するところが大きい。
【図面の簡単な説明】
【図１】本発明の原理構成ブロック図である。
【図２】本発明の問題解決演算装置の基本構成を示すブロック図である。
【図３】最適解探索状態の状態遷移の説明図である。
【図４】巡回セールスマン問題における都市の配置例を示す図である。
【図５】図４内の各都市の位置（座標）を示す図である。
【図６】解の候補のコーディング結果の例を示す図である。
【図７】実施例における状態遷移の説明図である。
【図８】各状態でのオペレーションの組み合わせの例を示す図である。
【図９】近傍探索の概念を示す図である。
【図１０】新個体の受け入れ（リクルートメント）の概念を示す図である。
【図１１】第１の条件における標準偏差の和の説明図である。
【図１２】第３の条件におけるフィットネス値の変化率の説明図である。
【図１３】遺伝的アルゴリズムを用いる問題解決演算装置の構成を示すブロック図である。
【図１４】並列処理を行う問題解決演算装置の構成を示すブロック図である。
【図１５】最適解探索処理のフローチャート（その１）である。
【図１６】最適解探索処理のフローチャート（その２）である。
【図１７】交叉処理のフローチャートである。
【図１８】交叉処理の例を示す図である。
【図１９】新個体の受け入れ処理を示す図である。
【図２０】山登り処理のフローチャートである。
【図２１】隣接置換を示す図である。
【図２２】反転処理を示す図である。
【図２３】ＧＡアルゴリズムによるシミュレーション結果を示す図（その１）である。
【図２４】ＧＡアルゴリズムによるシミュレーション結果を示す図（その２）である。
【図２５】ＧＡアルゴリズムによるシミュレーション結果を示す図（その３）である。
【符号の説明】
１        最適解探索手段
２        探索過程観測及び状態遷移手段
１１      探索モジュール
１２      制御モジュール
１３      探索部
１４      観測部
１５      遷移制御部
１６−１、１６−２、１６−３、１６−Ｍ      探索状態
３０、４１−１、４１−２、４１−Ｎ      セル
３１、４２      入力部
３２、４４      出力部
３３、４３      メモリ
３４、４５      フィットネス値計算処理部
３５、４６      複製／交叉処理部
３６、４７      突然変異処理部
３７、４８      近傍探索処理部
３８      評価観測処理部
３９、５５      ＧＡオペレーション遷移制御処理部
４９      反転処理部
５０      リクルートメント処理部
５１      山登り処理部
５２      条件１処理部
５３      条件２処理部
５４      条件３処理部
５６      マイグレーション値分配処理部
５７      並列処理制御部
【図１】
0003697446.tif 000005
【図２】
0003697446.tif 000006
【図３】
0003697446.tif 000007
【図４】
0003697446.tif 000008
【図５】
0003697446.tif 000009
【図６】
0003697446.tif 000010
【図７】
0003697446.tif 000011
【図８】
0003697446.tif 000012
【図９】
0003697446.tif 000013
【図１０】
0003697446.tif 000014
【図１１】
0003697446.tif 000015
【図１２】
0003697446.tif 000016
【図１３】
0003697446.tif 000017
【図１４】
0003697446.tif 000018
【図１５】
0003697446.tif 000019
【図１６】
0003697446.tif 000020
【図１７】
0003697446.tif 000021
【図１８】
0003697446.tif 000022
【図１９】
0003697446.tif 000023
【図２０】
0003697446.tif 000024
【図２１】
0003697446.tif 000025
【図２２】
0003697446.tif 000026
【図２３】
0003697446.tif 000027
【図２４】
0003697446.tif 000028
【図２５】
0003697446.tif 000029