(57)【特許請求の範囲】
【請求項１】
解の固定部分を計算する部分解固定部と、適時世代毎に該解の固定部分を変更する部分解固定変更部とを備えた複数の部分集団最適化手段と、
前記部分集団最適化手段における解情報を伝達する部分集団交信手段を具備したことを特徴とする最適化問題解法装置。
【請求項２】
前記解が遺伝的アルゴリズムにおける染色体であることを特徴とする請求項１記載の最適化問題解法装置。
【請求項３】
前記部分集団最適化手段における初期部分集団の設定の手法を部分集団最適化手段毎に変えることを特徴とする請求項１記載の最適化問題解法装置。
【請求項４】
前記部分集団最適化手段の部分解固定変更部は、隣接部分集団の計算結果にもとづき、該部分解固定変更部が有する部分集団の適時世代毎に解の固定部分を変更することを特徴とする請求項１記載の最適化問題解法装置。
【請求項５】
前記部分集団最適化手段の部分解固定変更部は、隣接部分集団の計算結果にもとづき、適時世代毎に部分解固定変更手段自身が有する解の固定部分を変更することを特徴とする請求項４記載の最適化問題解法装置。
【請求項６】
前記部分集団最適化手段は、部分集団に割り振られた位置情報に基づき、前記部分集団最適化手段の部分解固定変更部が有する部分集団を適時世代毎に解の固定部分変更の仕方を変えることを特徴とする請求項４記載の最適化問題解法装置。
【請求項７】
前記部分集団最適化手段は、前記部分集団最適化手段の部分解固定変更部が有する解の固定部分の変更の仕方を世代ごとに変えることを特徴とする請求項４記載の最適化問題解法装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は最適化問題解法装置に係り、特に最適解の探索空間を小さくして短時間で最適解を得ることを可能としたものである。
【０００２】
【従来の技術】
最適化問題の解法として、分枝限定法などの厳密解を求める手法は、問題の規模が大きくなると、計算量が極めて莫大なものとなりその面から実用にならなくなる。厳密な最適解は必ずしも得られないが、それに近い準最適解を高速に求める可能性のある手法として、遺伝アルゴリズム（Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）がある。
【０００３】
【発明が解決しようとする課題】
ところで遺伝アルゴリズムでは、染色体を構成する構成要素の数が大きくなると、良い解を見つけるために必要な構成要素の組み合わせが莫大な数になり、計算時間が非常に長くなるという問題がある。
【０００４】
従って本発明の目的は、このような問題を改善するため、遺伝アルゴリズムにおける求解計算における染色体操作、つまり構成要素の最適な組み合わせを求めるとき、最適解（又は準最適解）の探索空間を小さくして、それにより計算時間を短縮した最適化問題解法装置を提供することである。
【０００５】
【課題を解決するための手段】
前記目的を達成するため、本発明では、図１（Ａ）に示す如く、入力されたデータやパラメータ等を部分集団最適化部４−１、４−２、４−３・・・及び初期集団生成部２にそれぞれ伝達する集団制御部１と、初期集団を生成する初期集団生成部２と、初期集団生成部２で作成した染色体を部分集団最適化部４−１、４−２・・・に送出したり、部分集団最適化部４−１、４−２・・・のいずれかで変更した染色体を他に送信する部分集団交信部３と、染色体の評価、選択、交叉、変異を行ったり固定部分を変更する部分集団最適化部４−１、４−２・・・を設ける。
【０００６】
【作用】
本発明の動作を、例えば巡回セールスマン問題の解生成について説明する。即ち、ｎ個の都市があり、２都市Ｃｉ、Ｃｊ間のコストＰｉｊが与えられているとするとき（ｉ、ｊ＝１、２・・・ｎ）、ある都市から出発して、残りの全部の都市を１回ずつ巡回して、最初の都市に戻る巡回路の中で経路に沿ってのコストの総和ΣＰｉｊ（ツアー長）が最小となる巡回路を見つける問題である。
【０００７】
以下の説明では、ｎ＝１０の例について説明する。なお以下の説明では１０個の都市を数字０〜９で表示する。
集団制御部１にデータ（都市０〜９及び２都市間のコスト）と、必要なパラメータを入力する。これらのデータとパラメータは、初期集団生成部２と、部分集団最適化部４−１〜４−ｍに送出され、保持される。
【０００８】
初期集団生成部２は、先ず、部分集団最適化部４−１に送出する初期染色体集団を生成する。以下の場合は、各部分集団最適化部４−１、４−２・・・にそれぞれ４個の染色体集団を有する例である。この例で染色体とは、巡回すべき都市の順番を示したもので図１（Ｂ）に示すａ〜ｄがそれぞれ個々の染色体を表現しており、各数字は染色体の構成要素である。
【０００９】
初期集団生成部２は、このような染色体を作成し、部分集団交信部３を経由して部分集団最適化部４−１、４−２・・・に例えば４個ずつ送出する。
次に、部分集団最適化部４−１、４−２・・・は、それぞれ保持している４個の染色体のうちより共通の構成要素の組み合わせを検索し、これを初期固定部分とする。例えば、部分集団最適化部４−１が、図１（Ｂ）に示すａ〜ｄの４個の染色体を与えられているとき、「１６」、「５０９」が初期固定部分となる。この場合「１６」と「６１」及び「５０９」と「９０５」は巡回方向を変えれば同一であるので、同じ組み合わせとする。
【００１０】
それから各部分集団最適化部４−１、４−２・・・は、それぞれ保持している各染色体の評価を行う。即ち、各染色体の示す巡回路のツアー長を演算する。図１（Ｂ）のａの例では都市２と４間のコストＰ２４、都市４と５間のコストＰ４５・・・を加算してツアー長を演算する。ｂ〜ｄの染色体についても同様にしてツアー長を演算する。この場合、ツアー長が低い程良い評価が与えられるので、ツアー長の逆数を適応度として表現し、適応度の大きいもの程高い評価を付与する。そして適応度の高い染色体を選択して残し、低い染色体を消す。
【００１１】
またパラメータにより指示された確率によりその部分集団最適化部に残された染色体を交叉して新しい染色体を作る。同じくパラメータにより指示された確率により染色体の構成要素の順番を入れ替えて突然変異を生じさせる。この交叉、突然変異等を演算するとき、固定部分をそのまま固定させて新しい染色体を作る。
【００１２】
このようなことを複数回繰り返して評価を行い、適応度の高い染色体を選択して残し、交叉を行い、突然変異を行わせる。
それから隣接する部分集団最適化部において、同様に処理された染色体との比較を行う。部分集団最適化部４−１においては例えば部分集団最適化部４−２、４−３の染色体との比較を行う。
【００１３】
そして自部分集団最適化部４−１の最良の染色体が部分集団最適化部４−２の最良の染色体及び部分集団最適化部４−３の最良の染色体よりも良ければ、自部分集団最適化部４−１の染色体の集団で再計算を行い、固定部分を求める。
【００１４】
逆に自部分集団最適化部４−１の最良の染色体が部分集団最適化部４−２の最良の染色体及び部分集団最適化部４−３の最良の染色体よりも悪ければ、これら部分集団最適化部４−２、４−３の最良の染色体の共通部分を演算して求めたものを新しく固定部分とし、この新しい固定部分を含む染色体をランダム生成して自集団を再構成する。
【００１５】
このようなことを複数回繰り返し、そのツアー長、つまり適応度が改善されないと判断したとき、計算を終える。それまでに見つかった最もツアー長の低い染色体を最終的な解とする。
【００１６】
本発明によれば染色体の一部分を固定部分としたので、探索空間の大きさを小さくすることができ、短時間で解を得ることができる。
【００１７】
【実施例】
本発明の一実施例を図１〜図７に基づき、巡回セールスマン問題の解生成の場合について説明する。図１は本発明の原理図、図２は図１（Ａ）における部分集団最適化部の詳細図、図３は本発明の動作説明図、図４は本発明における染色体の操作処理説明図（その１）、図５は本発明における染色体の操作処理説明図（その２）、図６は本発明における染色体の操作処理説明図（その３）、図７は本発明における染色体の操作処理説明図（その４）である。
【００１８】
図中１は集団制御部、２は初期集団生成部、３は部分集団交信部、４、４−１、４−２・・・は部分集団最適化部、５は部分集団制御部、６は部分解固定計算部、７は適応度演算部、８は選択演算部、９は交叉演算部、１０は突然変異演算部、１１は局所改善演算部、１２は部分解固定変更部、１３は部分固定解生成部、１４は部分集団記憶部である。
【００１９】
集団制御部１は、初期集団生成部２や部分集団最適化部４−１、４−２・・・の動作を制御したり、これらに対してデータやパラメータを入力したり、部分集団最適化部４−１、４−２・・・からの演算結果を統合して最終的な演算結果つまり解を出力するものである。
【００２０】
初期集団生成部２は各部分集団の各染色体を生成するものである。例えば１染色体を１０個の構成要素で作成し、４個の染色体で１つの部分集団を構成するとき、図１（Ｂ）に示すａ〜ｄの如き４個の染色体を１部分集団に対して作成する。一般的にいえば、できるだけ最適に近く、かつできるだけ異なる染色体で部分集団が作られることが望ましい。
【００２１】
これらの染色体は、具体的には以下のように生成した。ある都市をランダムに１つ選び、それをＣ１  とする。部分巡回路Ｃ１  、Ｃ２  ・・・Ｃｋまで作られたとするとき、次に巡回する都市Ｃｋ＋１として、未巡回の都市の中から、都市Ｃｋから最もコストの小さい都市を選ぶ。順次これを繰り返して１つの完全な巡回路を作る。即ち、従来のニアレスト・ネーバ（Ｎｅａｒｅｓｔ  Ｎｅｉｇｈｂｏｒ）法に基づき作成する。
【００２２】
他の生成手法としては、出発点の都市をランダムに選び、未巡回の都市の中からコストの小さい都市ほど高い確率で選び出す。これを繰り返して１つの巡回路を作る。
【００２３】
さらに他の生成手法としては、部分集団それぞれで、出発点の都市をランダムに選び、そこから最もコストの小さい都市を順次結んで、ある一定長の部分巡回路を作る。この部分巡回路をその部分集団の固定部分として、部分集団内の染色体をランダムに生成する。
【００２４】
勿論、出発点としてある都市をランダムに１つ選び、次も未巡回の都市の中からランダムに１つ選ぶというランダム手法で都市を順次選択して巡回路を構成することもできる。染色体の生成手法はこれらのものに限定されるものではなく、他の手法により生成してもよい。
【００２５】
部分集団交信部３は、初期集団生成部２で作成した染色体を部分集団最適化部４−１、４−２・・・に分配したり、部分集団最適化部４−１、４−２・・・間において染色体に関する情報を交信するものである。
【００２６】
部分集団最適化部４−１、４−２・・・は、染色体の初期固定部分を計算したり、染色体の評価つまり適応度の計算を行ったり、適応度の高い染色体を残し、低い染色体を消すという選択を行ったり、２つの染色体を交叉させて新しい染色体を求めたり、染色体を一部分反転させて突然変異させたり、反転を多数回繰り返して低ツアー長になるときのみ反転させて局所改善したりするものである。
【００２７】
このため、図２に示す部分集団最適化部４に示す如く、各部分集団最適化部では、部分集団制御部５、部分解固定計算部６、適応度演算部７、選択演算部８、交叉演算部９、突然変異演算部１０、局所改善演算部１１、部分解固定変更部１２、部分固定解生成部１３、部分集団記憶部１４等を具備する。
【００２８】
部分集団制御部５は、集団制御部１から入力されたデータやパラメータを部分集団記憶部１４に入力したり、部分集団交信部３から入力された染色体を部分集団記憶部１４に入力したり、部分集団記憶部１４に保持された染色体を部分集団交信部３に出力したり、部分解固定計算部６〜局所改善演算部１３を選択的に動作させるものである。
【００２９】
部分解固定計算部６は、最初に作成された自部分集団最適化部で保持されている複数の染色体の全部に共通する部分巡回路をその部分集団での固定部分とする。もし全部に共通するものがなければ、パラメータとして与えられているある一定割合以上で含まれる部分巡回路を固定部分とする。
【００３０】
例えば、部分集団が図１（Ｂ）のａ〜ｄに示す染色体の場合には、「１６」、「９０５」が共通の部分巡回路であるので、これを固定部分とする。なおこの場合、巡回方向が逆の場合でも同方向と判断、例えば「６１」＝「１６」、「９０５」＝「５０９」として判断する。またｄのように、最初と最後に途切れていても、連続しているものとして部分巡回路の存在を判断する。
【００３１】
適応度演算部７は部分集団内で各染色体の適応度を演算するものである。前記の巡回セールスマン問題の場合、染色体で示される都市の巡回路を経由したときのコスト総和のもっとも少ないものがもっともすぐれた染色体であるので、この場合は、コスト総和の逆数を適応度として表すものとなる。従ってコスト総和のもっとも少ないものが適応度のもっとも大きなものとして演算されることになる。
【００３２】
選択演算部８は部分集団内の各染色体のうち適応度の高いものを残し、適応度の低いものを削除する。この削除したとき必要ならば適応度の高いものを同じ部分集団内に複製するものである。このとき、ルーレット・ホイール選択により確率を定めて残存消去の選択を行うことができる。
【００３３】
交叉演算部９は２つの染色体をクロスさせて違うタイプの２つの染色体を作るものである。具体的には、巡回セールスマン問題における都市名の順序列を矛盾なく交叉させることの出来る、ＰＭＸとよばれる交叉法を用いて説明する。例えば、図１（Ｂ）に示すａとｃの染色体を用いて交叉演算は図１（Ｃ）のように行う。
【００３４】
下線で示される固定部分「５０９」と「１６」をそれぞれ１つの都市と「Ｆ」、「Ｇ」とみなす。このような縮退させた（７都市）染色体の一対で、例えば図１（Ｃ）の染色体ａ′、ｃ′において△と△で示すように、先頭から２、３番目の間および４、５番目の間で交叉を行う。
【００３５】
それにはまず、△と△に挟まれる部分で同じ位置にある都市名をａ′とｃ′で交換し、つぎにその都市名の対応関係に従って△と△の外側の部分でも交換を行う。つまりａ′とｃ′において「Ｆ」と「８」、「７」と「Ｇ」をそれぞれ交換する。このようにしてａ′、ｃ′を交叉させた状態が、ａ′−１、ｃ′−１である。縮退させた都市名「Ｆ」、「Ｇ」をもとのように都市名の並び「５０９」、「１６」に戻した２つの染色体ａ′−２及びｃ′−２が、交叉によって得られる新しい染色体である。
【００３６】
突然変異演算部１０は、染色体についてランダムに部分巡回路を選び、その部分巡回路を逆順にする。例えば染色体３１６４２５０９８７について、反転部分を下記のように△と△で挟む。
【００３７】
△３１６４△２５０９８７
それからこの部分を反転させ、下記の染色体を得る。
４６１３２５０９８７
局所改善演算部１１は、前記突然変異演算部１０で説明した部分巡回路の反転を複数回繰り返し行うものである。このとき低いツアー長つまり適応度が高くなるときにのみ反転させるものとする。反転させても適応度が高くならなかったときは、反転させなかったものとする。
【００３８】
前記適応度演算部７〜突然変異演算部１０の動作説明をわかり易くするため、図４によりさらに説明する。先ず初期集団生成部２により、例えば図１に示す部分集団最適化部４−１に対し、▲１▼に示す４個の染色体ａ〜ｄを作成送出する。部分解固定計算部６では、受信した染色体について共通する部分巡回路を検出し、それらを初期固定部分とする。例えば図１（Ｂ）に示される染色体ａ〜ｄについて、下線された「１−６」および「５−０−９」が共通巡回路であり、初期固定部分となる。
【００３９】
適応度演算部７では、各染色体ａ〜ｄについて、データとして与えられている都市間のコストに基づき、その総コスト（ツアー長）を計算し、その逆数により▲２▼に示す適応度ｆ（ａ）〜ｆ（ｄ）を算出する。▲２▼のａ〜ｄに示す数字間の矢印は、数字で示される都市間の巡回路を示している。
【００４０】
例えば、染色体ｂについては、都市３から１に巡回するコストＰ３１、都市１から６に巡回するコストＰ１６、都市６から４に巡回するコストＰ６４・・・を最初受信した２都市間のコストデータに基づき抽出し、これらＰ３１＋Ｐ１６＋Ｐ６４・・・の総和を演算して染色体ｂによるコストを得る。それからその逆数を求め、染色体ｂの適応度ｆ（ｂ）を算出する、このようにして各染色体ａ〜ｄの適応度を求める。
【００４１】
選択演算部８では、適応度演算部７で計算された適応度ｆ（ａ）〜ｆ（ｄ）をみて、適応度の高い染色体を残し、低いものを消す。この場合、染色体ａのツアー長がもっとも低くつまり適応度ｆ（ａ）が最高で染色体ｄの適応度ｆ（ｄ）が最低のため、選択演算部８では▲３▼に示す如く、染色体ｄを消して染色体ａを複製して染色体ｄ′とする。この場合、例えばルーレットホイール選択により残存消去の確率を定めて選択することもできる。
【００４２】
交叉演算部９では、▲３▼に示す例えば染色体ａとｃについて△と△で挟まれる部分を交叉部分として交叉を行い、▲４▼に示す染色体ａ′、ｃ′を得る。
突然変異演算部１０では、▲４▼で示す例えば染色体ｂの△と△で挟まれる部分を逆順にして、▲５▼に示す染色体ｂ′を突然変異により得る。
【００４３】
部分解固定変更部１２は自部分集団の最良染色体と隣接部分集団の最良染色体とを比較して、自部分集団における染色体の固定部分を変更するもの、つまり自部分集団における解の固定部分を変更するものであって、変更する原因として、
▲１▼自部分集団の染色体の最良のものつまり自部分集団の最良染色体が隣接部分集団の最良染色体のいずれよりも良い場合、
▲２▼自部分集団の最良染色体が隣接部分集団の最良染色体のいずれよりも悪い場合、
▲３▼▲１▼、▲２▼のいずれでもない場合
である。
【００４４】
このため、図５に示す如く、各部分集団最適化部４−１、４−２・・・４−５・・・に図示省略した比較部を設けるとともに、これらを前記部分集団交信部３により、正方格子トーラス接続し、隣接部分集団の染色体の適応度が検知できるように構成されている。
【００４５】
図５の例では、部分集団最適化部４−１に保持される染色体を自部分集団の染色体とするとき、隣接の部分集団最適化部４−２、４−３、４−４、４−５に保持される染色体をそれぞれ東、西、南、北の染色体と呼ぶ。そして前記▲１▼、▲２▼、▲３▼のケースに応じて下記の処理が行われる。
【００４６】
▲１▼図６に示す如く、４個の自部分集団の染色体が存在するとき、その固定部分は「１−６」、「９−０−５」で示される。このような状態において、＊印で示された自部分集団の最良染色体の適応度が、「東」、「西」、「北」、「南」の隣接部分集団の最良染色体よりも適応度が良かった場合、図７の▲１▼に示す如く、自部分集団で固定部分の再計算を行い、それまでの前記「１−６、９−０−５」の外に「２−４」も固定部分とする。ただし既に固定部分の割合が非固定部分よりもある一定値以上のとき、固定部分を再度計算しない。
【００４７】
▲２▼自部分集団の最良染色体が「東」、「西」、「北」、「南」の隣接部分集団の最良染色体よりも悪い場合、図７の▲２▼に示す如く、隣接部分集団の最良染色体の共通部分を計算する。これにより得られた共通部分「３−８」を固定部分とした、新たな染色体を、部分固定解生成部１３でランダム生成して自部分集団を再構成する。この場合、自部分集団に隣接部分集団のうちの最良染色体を含ませてもよい。
【００４８】
▲３▼前記▲１▼、▲２▼のいずれでもない場合、即ち、自部分集団の最良染色体よりも良い適応度をもつ最良染色体と、悪い適応度をもつ最良染色体が混在する場合、その良い適応度をもつものと自部分集団の固定部分を比較して、この固定部分に矛盾部分が存在するか否かをチェックし、矛盾する固定部分を除いた新しい固定部分を得る。例えば図７の▲３▼に示す如く、「東」の最良染色体が良い適応度の場合、これと自部分集団の固定部分「１−６、９−０−５」を比較する。これにより「１−６」は「東」の最良染色体には存在しないので、これを固定部分から除き、また「９−０」は存在するが「９−０−５」は存在しないので固定部分を「９−０」と訂正する。
【００４９】
部分固定解生成部１３は、前記▲２▼の如く、隣接部分集団の最良染色体の共通部分を計算することにより得られた新しい固定部分を含む染色体をランダム生成して自集団を再構成するものである。前記図７の▲２▼の例では固定部分「３−８」を含む染色体を、自集団として４個ランダム生成する。
【００５０】
なお前記説明では、隣接部分集団として東、西、北、南の４つの使用した例について説明したが、隣接部分集団はこれに限定されるものではなく、２個でも、あるいは５個以上でも適宜設定できるものである。
【００５１】
本発明の動作を図３のフローチャートに基づき説明する。
（１）  最初に、集団制御部１に対し、例えば巡回セールスマン問題の解生成の場合には、データとして都市名（例えば前記０〜９）、２都市間の巡回コスト等が入力され、パラメータとして部分集団あたりの染色体の数（前記の例では４）、固定部分変更世代（例えば１０世代毎）、交叉確率（例えば０．６）、突然変異率（例えば０．６）、局所改善率（例えば０．４）、必要に応じて選択確率等を入力する。これらのデータ、パラメータは、部分集団最適化部４−１、４−２・・・初期集団生成部２に入力される。
【００５２】
いま部分集団最適化部の数を５個としたとき、初期集団生成部２は、１部分集団最適化部あたり４個の染色体、即ち全部で５×４＝２０個の染色体を例えばニアレスト・ネーバ法に基づき作成する。そしてこの作成した染色体を、部分集団交信部３を経由して部分集団最適化部４−１、４−２・・・に４個ずつ分配される。このようにして、例えば部分集団最適化部４−１には、図１（Ｂ）に示す如き染色体が受信される。
【００５３】
（２）  部分集団最適化部４−１では、部分解固定計算部６が、この受信した染色体について、共通する部分巡回路を検出する。これにより、図１（Ｂ）に示される染色体ａ〜ｄについて、「１−６」、「５−０−９」の共通の部分巡回路が検出されるので、これらを初期固定部分とする。もし部分集団内の全染色体に共通する部分巡回路が存在しないとき、ある一定割合以上で含まれる部分巡回路を固定部分とする。この一定割合は、前記パラメータの１つとして入力され、予め集団制御部１を経由して部分集団最適化部４−１、４−２・・・に保持されている。
【００５４】
（３）  このようにして解の固定部分を求めたあと、各部分集団で染色体集団の評価、選択、交叉、変異等を行い、次世代集団を求める。染色体ａ〜ｄの適応度の計算を適応度演算部７で行い、選択演算部８で例えばルーレット・ホイール選択により残存消去選択し、交叉演算部９によりある確率にもとづき２つの染色体の交叉を行い、突然変異演算部１０によりこれまたある確率により染色体の１部を突然変異させ、さらに局所改善演算部１１によりある確率により反転の繰り返しを行う。このようにして次世代の染色体の部分集団を得る。即ち初期染色体集団に対しこれを１回行えば第２世代の部分集団となり、２回行えば第３世代の部分集団となる。
【００５５】
（４）  部分集団制御部５はこの（３）を行う毎に、更に改善が進むと判断したとき、終了と判定せず、前記（３）の反復を行う。
（５）  そしてこの反復を、予めパラメータにより定められた回数、例えば１０回行ったとき、隣接部分集団と中間結果を交換する。例えば、図５に示す如く、自部分集団最適化部４−１では、隣接部分集団最適化部４−２、４−３、４−４、４−５から、部分集団交信部３を経由してそれぞれの部分集団の最良染色体を受信する。
【００５６】
例えば図６に示す如く、「東」、「西」、「北」、「南」の隣接部分集団の最良染色体が伝達されたとき、自部分集団最適化部４−１ではこれらの最良染色体の適応度を計算する。勿論適応度を一緒に伝達してもよい。そして、これらの隣接部分集団の最良染色体が、自部分集団の最良染色体より良いか悪いか比較する。
【００５７】
（６）  この比較の結果に応じて次の▲１▼、▲２▼、▲３▼のように固定部分を変更する。
▲１▼即ち、自部分集団の最良染色体が隣接部分集団の最良染色体のすべてよりも良い場合、図７の▲１▼で示す如く、自部分集団内の染色体に共通する（またはパラメータにより指示された一定割合以上含まれる）部分巡回路を再度求め、それを固定部分とする。図７の例では、すでに固定部分｛１−６、９−０−５｝が存在する場合において、この再計算の結果、新たな共通の部分巡回路として２−４が求められるので、その結果新しい固定部分が｛１−６、９−０−５、２−４｝となる。ただし、既に、固定部分の割合が、非固定部分よりも、パラメータにより指示された一定値以上であったときは、固定部分を再度計算しない。
【００５８】
▲２▼自部分集団の最良染色体が隣接部分集団の最良染色体のどれよりも悪い場合、図７の▲２▼で示す如く、隣接部分集団の最良染色体に共通する、またはパラメータにより指示された一定割合以上含まれる部分巡回路を求め、それを自部分集団における固定部分として含む染色体を部分固定解生成部１３によりランダムに生成して自部分集団を再度構成する。このとき自部分集団に隣接部分集団の最良染色体を含ませることができる。
【００５９】
▲３▼隣接部分集団の最良染色体に自部分集団の最良染色体よりも良いものと悪いものとが混在している、前記▲１▼、▲２▼のいずれでもない場合、図７の▲３▼で示す如く、隣接部分集団の最良染色体の良いもの、例えば「東」が良いときはこの「東」の染色体と自部分集団の固定部分とを比較して、矛盾する固定部分を除き、新しい固定部分を得る。
【００６０】
（７）  このように固定部分の変更を行ったあと前記（３）に戻る。そしてこのようなことを繰り返し、これ以上改善が進まないと判断された時点で終了する。そしてそのときの巡回路が集団制御部１から計算結果として出力される。
【００６１】
なお、前記説明では、自部分集団と隣接部分集団とのすべてを比較して前記▲１▼、▲２▼、▲３▼の変更を行っていたが、隣接部分集団に割り振られた位置情報に基づき、その変更のやり方を変えることもできる。例えば東西の隣接部分集団に対しては▲１▼と▲３▼、北南の隣接部分集団に対しては▲２▼と▲３▼のように固定部分変更の仕方を変えてもよい。このようにすることにより、計算時間の短縮及び誤った固定部分を訂正することができる。
【００６２】
また、例えば、東西を１つ飛び隣りの部分集団にして、比較することもできる。
なお前記説明では、例えば１０世代毎に固定部分の変更を同一の手法で行っていたが、例えば５世代毎に前記▲１▼、▲２▼、▲３▼を１つのみ順次行うようにしてもよい。またこれを世代毎に変えてもよい。これにより計算時間の短縮及び誤った固定部分を訂正することができる。
【００６３】
更に、固定部分の変更の仕方を部分集団のそれまでの変更履歴に依存して変えてもよい。例えば▲２▼が続く場合、▲２▼が多い場合には▲２▼というやり方で先ず行うようにする。これにより計算時間の短縮ができる。
【００６４】
また、例えば部分集団最適化部４−２と部分集団最適化部４−３における染色体を隣接部分集団との固定部分の非類似性を維持するため計算途中で部分集団ごとに入れ替えてもよい。これにより誤りの訂正や計算時間の短縮をはかることができる。
【００６５】
本発明の計算結果を図６、図７により５１の都市を巡回する例について説明する。パラメータ値は、部分集団数２５（＝５×５）、部分集団内の染色体数４０（総染色体数１０００）、固定部分変更１０世代毎、交叉確率０．６、突然変異率０．６、局所改善率０．４である。なおこれらは最良のパラメータ値の組み合わせではない。
【００６６】
図６（Ａ）は０世代目での集団内での最良染色体、つまり解を示すものでツアー長は４７３であった。これを５００世代目では図６（Ｂ）及び図７に示す如く、ツアー長が４２６のものを得ることができた。図７において縦軸はツアー長、横軸は世代数を示す。
【００６７】
次に本発明の第２実施例構成を図１０、図１１に基づき説明する。図１０は本発明の第２実施例構成図、図１０は第２実施例における部分集団最適化部２３の詳細構成図である。
【００６８】
図１０、図１１において２１は集団制御部、２２は部分集団交信部２３−１〜２３−ｍは部分集団最適化部、２４は部分集団制御部、２５は部分解固定計算部、２６は解生成部、２７は適応度演算部、２８は選択演算部、２９は交叉演算部、３０は突然変異演算部、３１は局所改善演算部、３２は部分解固定変更部、３３は部分固定解生成部、３４は部分集団記憶部である。
【００６９】
本発明の第１実施例では、集団制御部１に入力されたデータ、パラメータに基づき、初期集団生成部２が部分集団最適化部４−１、４−２・・・に必要な数の染色体を生成して送出していたが、本発明の第２実施例では、図１１の部分集団最適化部２３に代表的に示す如く、解生成部２６において、集団制御部２１に入力されたデータ・パラメータに基づき、部分集団最適化部２３−１、２３−２・・・２３−ｍに必要な数の染色体を生成するものである。他は同一であるのでその詳細な動作説明は省略する。
【００７０】
ところで、各部分集団最適化部２３−１、２３−２・・・における解生成部２６を、部分集団最適化部２３−１、２３−２・・・毎に異なる初期設定することにより、異なる染色体を生成することができるので、最適解の検出を正確に行うことができる。
【００７１】
なお、集団制御部２１は、集団制御部１に対応し、部分集団交信部２２は部分集団交信部３に対応し、部分集団最適化部２３−１、２３−２・・・は部分集団最適化部４−１、４−２・・・に対応し、部分集団制御部２４は部分集団制御部５に対応し、部分解固定計算部２５は部分解固定計算部６に対応し、適応度演算部２７は適応度演算部７に対応し、選択演算部２８は選択演算部８に対応し、交叉演算部２９は交叉演算部９に対応し、突然変異演算部３０は突然変異演算部１０に対応し、局所改善演算部３１は局所改善演算部１１に対応し、部分解固定変更部３２は部分解固定変更部１２に対応し、部分固定解生成部３３は部分固定解生成部１３に対応し、部分集団記憶部３４は部分集団記憶部１４に対応する。
【００７２】
本発明の第２実施例では、各部分集団最適化部２３−１、２３−２・・・で並列的に初期染色体集団を生成するので、演算を短時間で行うことができる。
本発明の第３実施例として、図１２〜図１４に基づき染色体がビット列で構成される場合について説明する。前記説明は、染色体が例えば都市名の順序列のようなオーダー・コーデングの場合であるが、図１２〜図１４の場合は染色体を２進数で表現するバイナリ・コーデングの場合に対するものである。例えば染色体を図１２（Ａ）に示す如きバイナリ・コードで表現する。
【００７３】
この場合、装置構成は図１、図２で示した本発明の第１実施例と同じ構成でも、図１０、図１１で示した本発明の第２実施例と同じ構成でもよい。部分集団最適化部等における個々のハードがビット列を扱うものである。いま、便宜上図１、図２に示したハード構成で構成された例について説明する。
【００７４】
バイナリ・コードの場合は、例えば数値関数の最適化を求める場合に使用されるものであり、ある関数の最大値、最小値を求めるようなとき、例えばＦ（Ｘ）＝Ｘ２  の最小値を求めるような場合に使用されるものであり、集団制御部に入力するデータ・パラメータとしては、この関数、Ｘの上限値、下限値、Ｘを表現するビット数等が入力される。
【００７５】
初期集団生成部により、図１２（Ｂ）の左側に示す如く部分集団最適化部４に対し例えば４個のバイナリ・コードの染色体を生成する。他の部分集団最適化部に対しても同様に染色体を生成送出する。そして部分解固定計算部により染色体の各ビット位置ごとに共通な部分「１０１」検出し、これを固定部分とする。
【００７６】
それから部分集団最適化部４において、これらの４個の染色体の評価を行う。この評価の結果、図１０（Ｂ）の▲１▼に示す、上から３番目の染色体が最低で１番上の染色体が最良のとき、最低の染色体を棄てて最良のものを複製するという選択を行う。
【００７７】
これにより得られた、図１０（Ｂ）の▲２▼に示す状態の染色体の部分集団に対し、交叉を行う。例えば、図１０（Ｂ）の▲２▼に示すａとｂとを点線位置で交叉して図１２（Ｂ）の▲３▼に示すａとｂとを生成し、図１２（Ｂ）の▲２▼に示すｃとｄとを点線位置で交叉して図１０（Ｂ）の▲３▼に示すｃとｄとを生成する。
【００７８】
それから図１２（Ｂ）の▲３▼に示す染色体の矢印で指示した構成要素の０、１を反転させて突然変異を行わせ、同▲４▼に示す如き染色体を得る。バイナリ・コードの染色体の場合は、０、１のコードを反転することにより突然変異が行われる。図１２（Ｂ）では省略したが、局所改善の場合も同様である。この場合、固定部分が存在することにより交叉ができる位置、突然変異ができる位置が、図１２（Ｃ）に示す如く、染色体の固定部分を行わない場合の交叉ができる位置、突然変異ができる位置に比較して位置が限定されるため、最適解を探す範囲が減少し、計算速度が早くなる。
【００７９】
このようなことを予め定められた世代数繰り返して行ったのち、隣接部分集団と中間結果を交換し、これに基づいて各部分集団で固定部分を変更する。このため、図１３（Ａ）に示す如く、部分集団最適化部４−１、４−２、４−３、４−４、４−５・・・を正方格子トーラス接続する。いま部分集団最適化部４−１を自部分集団とし、他を東西北南に隣接する隣接部分集団とするとき、各部分集団における染色体固定部分は、図１３（Ａ）に示す太線で囲まれたビットで示される。
【００８０】
そして図１３（Ｂ）に示す如く、自部分集団の最良染色体を＊印で示したものとし、各隣接部分集団における最良染色体を同図に示す通りのものとしたとき、部分集団最適化部４−１ではこれらの各部分集団の最良染色体の評価を行う。
【００８１】
▲１▼自部分集団の最良染色体（＊印の付加されたもの）が、隣接集団の最良染色体のいずれよりも良いとき、自部分集団の染色体の共通部分を再計算し、図１４▲１▼に示す如く、これを新しい固定部分Ｆ１  とする。
【００８２】
▲２▼自部分集団の最良染色体が隣接集団の最良染色体のいずれよりも悪いとき、図１４▲２▼に示す如く、隣接部分集団の最良染色体の共通部分を計算し、この結果得られた固定部分Ｆ２  、Ｆ３  を新しい固定部とする。そして図１４▲２▼の右側に示す如く、新しい固定部分Ｆ２  、Ｆ３  を必ず含む、染色体をランダムに生成して、自部分集団を再構成する。
【００８３】
▲３▼前記▲１▼、▲２▼のいずれでもないとき、図１４▲３▼に示す如く、自部分集団の最良染色体よりも良い隣接部分集団の最良染色体と比較して、矛盾する固定部分を除いたもの新しい固定部分とする。例えば東西の隣接部分集団の最良染色体が＊印の付加された自部分集団の最良染色体よりも良い場合、自部分集団の固定部分「１０」と「１」を東西のそれらと比較したとき矢印の線で接続したように矛盾がある。従ってこれらの矛盾する部分を除いた、図１４▲３▼の右端に示す如き、太枠で囲んだビットを新しい固定部分Ｆ４  とする。
【００８４】
このようなことを繰り返して、バイナリ・コーデングの染色体の場合も、オーダ・コーデングの場合と同様に最良の染色体を短時間で得ることができる。
【００８５】
【発明の効果】
請求項１及び請求項２に記載された本発明によれば、固定部分を検出し、その結果最適解の生成のための計算時間を大幅に短縮することができる。例えばバイナリコード染色体の構成要素が１０個の場合、固定部分がなければ探索空間の大きさは、２10であるが、２つの構成要素で１個の固定部分を構成するとき探索空間は２8 となり、その結果計算時間を短縮することができる。また誤った固定部分を訂正して、最適解の生成検出を行うことができる。
【００８６】
請求項３に記載された本発明によれば、最適解の検出を正確に行うことができる。
【００８７】
請求項５に記載された本発明によれば、誤った固定部分を訂正して、最適解の生成検出を行うことができる。
請求項６に記載された本発明によれば、誤った固定部分を訂正して、最適解の生成検出を行うことができる。
【００８８】
請求項７に記載された本発明によれば、計算時間を短縮することができ、かつ誤った固定部分を訂正して、最適解の生成検出を行うことができる。
請求項８に記載された本発明によれば、計算時間を短縮することができ、かつ誤った固定部分を訂正して最適解の生成検出を行うことができる。
【図面の簡単な説明】
【図１】本発明の第１実施例の原理図である。
【図２】本発明の第１実施例の部分集団最適化部の詳細図である。
【図３】本発明の動作説明図である。
【図４】本発明における染色体の操作処理説明図（その１）である。
【図５】本発明における染色体の操作処理説明図（その２）である。
【図６】本発明における染色体の操作処理説明図（その３）である。
【図７】本発明における染色体の操作処理説明図（その４）である。
【図８】本発明にもとづき得られる巡回路説明図である。
【図９】本発明におけるツアー長計算状態説明図である。
【図１０】本発明の第２実施例構成図である。
【図１１】本発明の第２実施例の部分集団最適化部の詳細図である。
【図１２】バイナリ・コーデングを処理する本発明の第３実施例の操作処理説明図（その１）である。
【図１３】本発明の第３実施例の操作処理説明図（その２）である。
【図１４】本発明の第３実施例の操作処理説明図（その３）である。
【符号の説明】
１  集団制御部
２  初期集団生成部
３  部分集団交信部
４  部分集団最適化部
４−１  部分集団最適化部
４−２  部分集団最適化部
５  部分集団制御部
６  部分解固定計算部
７  適応度演算部
８  選択演算部
９  交叉演算部
１０  突然変異演算部
１１  局所改善演算部
１２  部分解固定変更部
１３  部分固定解生成部
１４  部分集団記憶部
２１  集団制御部
２２  部分集団交信部
２３  部分集団最適化部
２３−１  部分集団最適化部
２４  部分集団制御部
２５  部分解固定計算部
２６  解生成部
２７  適応度演算部
２８  選択演算部
２９  交叉演算部
３０  突然変異演算部
３１  局所改善演算部
３２  部分解固定変更部
３３  部分固定解生成部
３４  部分集団記憶部
【図１】
0003559334.tif 000002
【図２】
0003559334.tif 000003
【図３】
0003559334.tif 000004
【図４】
0003559334.tif 000005
【図５】
0003559334.tif 000006
【図６】
0003559334.tif 000007
【図７】
0003559334.tif 000008
【図８】
0003559334.tif 000009
【図９】
0003559334.tif 000010
【図１０】
0003559334.tif 000011
【図１１】
0003559334.tif 000012
【図１２】
0003559334.tif 000013
【図１３】
0003559334.tif 000014
【図１４】
0003559334.tif 000015