(57)【特許請求の範囲】
【請求項１】
解を構成する部分の一部分を固定する遺伝アルゴリズムを用いて求解演算を行う最適化問題解法装置であって、
染色体群からなる部分集団群をランダムに生成する初期集団生成部と、
前記初期集団生成部において作成した部分集団群の染色体群の相関関係を示す頻度表を作成する頻度算出部と、
前記初期集団生成部が生成した各部分集団の染色体群について、前記頻度表に基づき固定部分を算出する初期固定部分計算部と、
前記初期集団生成部が生成した各部分集団の染色体群について、理想となる値に対する適応度を求める評価選択部と、
部分集団が有する前記評価選択部が求めた適応度が最も高い染色体と、他の部分集団における適応度が最も高い染色体との適応度を比べ、適応度が高いと判断した染色体と適応度が低い染色体が属する部分集団の固定部分とを比べ、適応度が低い染色体が属する部分集団の固定部分を、適応度が高いと判断した染色体と適応度が低い染色体が属する部分集団の固定部分との矛盾する部分を除いた状態に変更する交信部と、
を具備したことを特徴とする最適化問題解法装置。
【請求項２】
前記請求項１に記載された最適化問題解法装置において、
前記染色体について、ランダムに２個のペアを組み合わせ、各ペア毎に交叉確率で交叉させるか否かを決めこれに基づき交叉する交叉部と、
前記交叉後の部分集団に予め与えられた突然変異確率でビット反転する突然変異部と、  を具備したことを特徴とする最適化問題解法装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は最適化問題解法装置に係り、特に遺伝アルゴリズムによる求解演算における染色体操作において、染色体を構成する一部分を固定化することにより最適解の探索空間を小さくして、短時間で演算可能としたものに関する。
【０００２】
【従来の技術】
例えばナップザック問題の如き、組合せ最適化問題の解法として分枝限定法などの厳密解を求める手法があるが、これは問題の規模が大きくなると計算量が極めて莫大なものとなりその面から実用にならなくなる。厳密な最適解は必ずしも得られないがそれに近い準最適解を高速に求める可能性のある手法として、遺伝アルゴリズム（Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ，ＧＡ）がある。
【０００３】
【発明が解決しようとする課題】
ところで遺伝アルゴリズムでは、染色体を構成する構成要素の数が大きくなると、良い解を見つけるために必要な構成要素の組み合わせが莫大な数になり、実用的観点からやはり計算時間の短縮が重要になる。
【０００４】
従って、遺伝アルゴリズムによる求解計算における染色体操作において、解（即ち染色体）を構成する部分の一部分を固定する（つまり変化させない）ことにより、最適解あるいは準最適解の探索空間を小さくして、それにより計算時間を短縮した最適化問題解法装置を提供することが必要となる。
【０００５】
ところで、解を構成する部分の一部分を固定する手法は、既に本発明者等により発明され、平成７年１月１７日付けで平成７年特許願第５２８０号として特許出願されている。本発明の目的は、遺伝アルゴリズムの染色体表現としてビット列が用いられる場合において、部分固定の異なる手法を提供するものである。
【０００６】
【課題を解決するための手段】
前記目的を達成するため、例えば図１（Ａ）に示す如き大きさと価値の品物１〜１０が存在する場合、大きさが１００のナップザック袋に詰めた品物の価値の総和の最大のものを見つけるという、ナップザック問題を解く場合、本発明では、図１（Ｂ）に示す如く、初期集団生成部１、頻度算出部２、初期固定部分計算部３、評価・選択部４、交叉部５、突然変異部６、交信部７、固定部分計算部８を設ける。
【０００７】
初期集団生成部１では、図１（Ｃ）に示す如き部分集団の染色体▲１▼〜▲６▼をランダムに作成する。変数ｘ１  〜ｘ１０は品物１〜１０に対応するものであり、品物をナップザック袋に詰めるように選択されたとき「１」、選択されないとき「０」を示す。従って染色体▲１▼は、品物１〜４、６、８、１０は選択されず、品物５、７、９が選択された場合を示す。
【０００８】
頻度算出部２は、この部分集団の染色体▲１▼〜▲６▼において、後述するように、各変数間の相関関係をチェックする。例えばｘ１  とｘ２  、ｘ２  とｘ３  、ｘ１  とｘ３  ・・・の如く、この部分集団の染色体▲１▼〜▲６▼において、各変数間にどのような「１」、「０」の状態が存在するのかその相関関係を算出し、後述する頻度表を作成するものである。
【０００９】
初期固定部分計算部３は、この頻度算出部２の算出した頻度表により、後述するように初期固定部分を求める。この場合は、図１（Ｄ）に示す如く、例えば染色体の１０ケの構成要素１〜１０に対して下段に示す如き初期固定部分を得る。このうち、「１」と「０」は固定位置とその値を示し、？は非固定を表す。
【００１０】
評価・選択部４は、部分集団の染色体▲１▼〜▲６▼の適応度即ちナップザック袋に詰めた品物の価値の総和を算出し、図１（Ｃ）の右側の値を求める。この例ではナッブザック袋の大きさ（Ｓ＝１００）を越える染色体はないが、もし越えた場合には、適応度をゼロとする。
【００１１】
それから評価・選択部４は、ある確率により染色体▲１▼〜▲６▼のうち▲４▼と▲５▼を消去して▲２▼と▲３▼を複写する。
交叉部５は、前記の染色体について、ランダムに２個ペアを組み合わせ、図１（Ｅ）のペアを作る。各ペア毎に、交叉確率で交叉させるかしないかを決める。例えば図１（Ｅ）に示す３番目のペアを交叉させるとき、まず各ビットを等確率で０又は１を選んでそれらを入れ換えビット列を用意する。このとき図１（Ｆ）に示す如き入れ換えビット列が用意されたとき、これを図１（Ｄ）の下方に示す初期固定部分と比較し、初期固定部分の「１」又は「０」の位置が、用意された入れ換えビット列の「０」の位置に合うとき、部分固定ありの一様交叉の入れ換えビット列として、これにより、交叉させ、図１（Ｇ）の＋印の部分のビットが入れ換えられる。この結果、交叉後の部分集団は、図１（Ｈ）に示す如きものとなる。
【００１２】
突然変異部６は、前記交叉後の部分集団に予め与えられた突然変異確率でビット反転する。ただし固定部分はビット反転させない。例えば図１（Ｈ）に示す部分集団の第４行目の染色体の第６番目のビットを突然変異させる。
【００１３】
このような評価・選択部４〜突然変異部６の操作を予め規定された世代数繰り返し行う。そして例えば１０世代後に交信部７により隣接部分集団（例えば東西南北）の染色体と比較する。
【００１４】
このとき、隣接部分集団からの最良染色体と自部分集団の最良染色体、つまり適応度がもっとも高い染色体の持つ適応度と隣接部分集団の最良染色体の持つ適応度とを比較する。
【００１５】
その結果次の３つが考えられる。
ａ．自部分集団の最良染色体が、隣接部分集団の最良染色体のどれよりも良い、つまり適応度が高い。
【００１６】
ｂ．自部分集団の最良染色体が隣接部分集団の最良染色体のどれよりも悪い、つまり適応度が低い。
ｃ．いずれでもない。
【００１７】
ａ．もし自部分集団の最良染色体が隣接部分集団のどれよりも良ければ、現部分集団の染色体について、固定部分計算部８において、前記初期固定部分を計算した部分と同じ手順で新しい固定部分を計算する。まず頻度表を求め、新しい固定部分を求める。
【００１８】
ｂ．もし自部分集団の最良染色体が隣接部分集団のどれよりも悪いならば、東、西、南、北の隣接部分集団の最良染色体について、固定部分計算部８において、前記初期固定部分を計算したものと同じ手順で新しい固定部分を計算する。まず頻度表を求め、新しい固定部分を求める。
【００１９】
そして、部分集団の大きさが元の大きさと同じになるように、前記東、西、南、北の各最良染色体に加え、この固定部分を必ず含む染色体をランダムに２つ生成して自部分集団を構成する。
【００２０】
ｃ．いずれでもないとき、例えば、東の最良染色体が自部分集団の最良染色体よりも良いとき、固定部分計算部８において、この東の最良染色体と自部分集団の固定部分を比較し、東の最良染色体と矛盾する固定部分を除く。
【００２１】
このようなことを繰り返し行うことによりもっとも適応度の良い染色体を、短時間で得ることができる。
【００２２】
【発明の実施の形態】
本発明の一実施例を説明するに先立ち、本発明において使用したナップザック問題（Ｋｎａｐｓａｃｋ  ｐｒｏｂｌｅｍ）について説明する。Ｎ個の品物があり、それぞれに大きさＳｉ（Ｓｉ＞０）と価値Ｖｉ（Ｖｉ＞０）が与えられているとき（ｉ＝１、２、・・・Ｎ）、これらの品物をいくつか選んで大きさＳのナップザック袋に詰めるとき、詰めた品物の大きさの総和がップザック袋の大きさを越えず、かつ価値の総和を最大にする品物の組を見つける問題である。
【００２３】
形式的には以下のように定義される。変数ｘｉ  で品物ｉを詰める（ｘｉ  ＝１）、詰めない（ｘｉ  ＝０）を表す。そのときのナップザック袋の品物の価値の総和Ｖ（｛ｘｉ  ｝）は、
【００２４】
【数１】
0003595043.tif 000002
【００２５】
となる。このときナップザック問題は、
【００２６】
【数２】
0003595043.tif 000003
【００２７】
と書くことができる。
図１（Ａ）に１０個の品物の簡単な例をあげる。便宜上、品物を番号１、２・・・１０で表す。ナップザック袋の大きさＳ＝１００のときの、ナップザック問題の最適解は｛ｘｉ  ｝＝｛１、１、０、１、１、１、１、０、１、０｝、最適値（詰めた品物の価値の総和）は１１７、詰めた品物の大きさの総和は９９である。
【００２８】
本発明の一実施例を図２〜図４に基づき説明する。図２は本発明の第１実施例構成図、図３は本発明の第１実施例における部分集団最適化部の詳細図、図４は本発明の動作説明図である。
【００２９】
図中、１０は集団制御部、１１は初期集団生成部、１２は部分集団交信部、１３、１３−１〜１３−ｎは部分集団最適化部、１４は部分集団制御部、１５は部分解固定計算部、１６は適応度演算部、１７は選択演算部、１８は交叉演算部、１９は突然変異演算部、２０は局所改善演算部、２１は部分解固定変更部、２２は部分固定解生成部、２３は部分集団記憶部である。
【００３０】
集団制御部１０は、初期集団生成部１１や部分集団最適化部１３−１、１３−２・・・の動作を制御したり、これらに対してデータやパラメータを入力したり、部分集団最適化部１３−１、１３−２・・・からの計算結果を総和して、最終的な計算結果つまり解を出力するものである。
【００３１】
初期集団生成部１１は、各部分集団の各染色体を生成する。実施例では、各部分集団最適化部１３−１、１３−２・・・における各染色体を生成するものである。一般に、できるだけ異なる染色体で集団が作られることが望ましい。例えば乱数生成器を用いて、長さＮビットのランダムなビット列をつくる。これを１個の染色体として各部分集団の染色体数分だけ用意する。いまＮ＝１０とし、１部分集団毎の染色体の数を６としたとき、例えば図１（Ｃ）に示す▲１▼〜▲６▼の６個の染色体を１部分集団用に作る。従って部分集団が５つあれば、３０個の染色体が作られる。
【００３２】
部分集団交信部１２は、初期集団生成部１１で作成した染色体を部分集団最適化部１３−１、１３−２・・・１３−ｎに分配したり、部分集団最適化部１３−１、１３−２・・・１３−ｎ間において染色体に関する情報を交信するものである。
【００３３】
部分集団最適化部１３、１３−１、１３−２・・・１３−ｎは染色体の頻度計算を行ったり、固定部分を計算したり、評価つまり適応度の計算を行ったり、適応度の高い染色体を残し、低い染色体を消すという選択を行ったり、２つの染色体を交叉させて新しい染色体を得たり、染色体を一部反転させて突然変異させたり、反転を多数回繰り返して適応度が改善されるときのみ反転させて局所改善したりするものである。
【００３４】
このため、図３に示す部分集団最適化部１３に代表して示す如く、各部分集団最適化部では、部分集団制御部１４、部分解固定計算部１５、適応度演算部１６、選択演算部１７、交叉演算部１８、突然変異演算部１９、局所改善演算部２０、部分解固定変更部２１、部分固定解生成部２２、部分集団記憶部２３等を具備する。
【００３５】
部分集団制御部１４は、集団制御部１０から入力されたデータやパラメータを部分集団記憶部２３に入力したり、部分集団交信部１２から入力された染色体を部分集団記憶部２３に入力したり、部分集団記憶部２３に保持された染色体を部分集団交信部１２に出力したり、部分解固定計算部１５〜局所改善演算部２０を選択的に動作させるものである。
【００３６】
部分解固定計算部１５は、部分集団の染色体の頻度算出を行い、これに基づき固定部分を計算するものであり、図１（Ｂ）に示す頻度算出部と固定部分計算部を備えるものである。
【００３７】
次に部分解固定計算部１５の動作をその頻度算出と固定部分計算に分けて説明する。
ある部分集団の初期染色体がランダムに生成されて、図５（Ａ）に示す染色体▲１▼〜▲６▼のように与えられているとき、まず、図５（Ｂ）に示す頻度表を作成する。この頻度表は、染色体の任意の２ビットが「１、１」、「１、０」、「０、１」、「０、０」のどのパターンであるかということを、染色体▲１▼〜▲６▼について作成したものであり、各ビット間の相関関係を表すものである。
【００３８】
頻度表は４個の数字により構成され、縦軸は図５（Ａ）に示すｉ（１〜９）を示し、横軸はｊ（２〜１０）を示す。この４個の数字はｉとｊの２ビットの組み合わせのパターンのうち、どれが何回存在しているかを示すものであり、左上の数字はパターン「１、１」の出力頻度を示し、左下の数字はパターン「０、１」の出力頻度を示し、右上の数字はパターン「１、０」の出力頻度を示し、右下の数字はパターン「０、０」の出力頻度を示す。
【００３９】
従って図５（Ｂ）の頻度表に示す左上側の４個の数字は、ｉ＝１、ｊ＝２のとき、つまり、図５（Ａ）に示す染色体▲１▼〜▲６▼の最左側の２ビットのパターンの状態を示すものである。この染色体▲１▼〜▲６▼の最左側の２ビットには「１、１」のパターンが２回、「０、１」のパターンが１回、「１、０」のパターンが２回、「０、０」のパターンが１回存在していることを、この左上側の数字は示している。
【００４０】
同様に図５（Ｂ）の頻度表の右下側の４個の数字は、ｉ＝９、ｊ＝１０のとき、つまり前記染色体▲１▼〜▲６▼の最右側の２ビットのパターンに、「１、１」のパターンが０、「０、１」のパターンが３回、「１、０」のパターンが２回、「０、０」のパターンが１回存在していることを示している。
【００４１】
次に固定部分計算のため、頻度しきい値を６として、図５（Ｂ）に示す
Ｆ１１（ｉ、ｊ）＋Ｆ００（ｉ、ｊ）≧６
または  Ｆ１０（ｉ、ｊ）＋Ｆ０１（ｉ、ｊ）≧６
となる（ｉ、ｊ）を探す。これにより図５（Ｂ）の頻度表から（２、７）、（５、１０）が検出される。これらの位置２、７、５、１０を固定位置として、それらの「１」、「０」の値はＦ１１（ｉ、ｊ）またはＦ００（ｉ、ｊ）、Ｆ１０（ｉ、ｊ）又はＦ０１（ｉ、ｊ）の大きい方の値を選ぶ。同じときはランダムに選ぶ。
【００４２】
これにより固定部分として、図５（Ｃ）に示す如く、ビット位置の２、５、７、１０番目のものを、「１」、「０」に固定する。なお？は非固定を表す。
本発明では、このように各ビットと他のビットとの関係に着目して、固定・非固定を決める。一般的には染色体（ビット列）内のビット間に強い相関を持つ部分群を固定する。そのため前記の如く、部分集団内で同じ値が高い頻度で出現する変数の組、例えば前記（２、７）、（５、１０）を検出してそれらの変数を固定部分とした。
【００４３】
即ち、ある適当な正整数に（以下変数の数という、前記の例はＫ＝２）を決める（２≦Ｋ＜Ｎ、Ｎは染色体のビット長）。
変数の組（ｘｊ１、ｘｊ２、ｘｊ３、・・・ｘｊＫ）の値が（０、０、０、・・・０、０）、（１、０、０、・・・０、０）、（１、１、０、・・・０、０）・・・、（１、１、１、・・・１、０）、（１、１、１、・・・１、１）、（全部で２Ｋ  通りある）となる頻度を部分集団内の全染色体に関して計算する。即ち頻度表を作る。
【００４４】
変数組の値が（ｐ１  、ｐ２  、・・・ｐＫ  ）のときの頻度を、Ｆｐ１  、ｐ２  、・・・ｐＫ  （ｘｊ１、ｘｊ２、・・・、ｘｊＫ）で表わす。
【００４５】
【数３】
0003595043.tif 000004
【００４６】
このとき
【００４７】
【数４】
0003595043.tif 000005
【００４８】
を満たす。
あるしきい値（以下、頻度しきい値という）Ｔ（０＜Ｔ≦Ｍ）を用意する。ある値の組（ｐ１  、ｐ２  、・・・、ｐＫ  ）において、
【００４９】
【数５】
0003595043.tif 000006
【００５０】
を満たす、変数の組（ｘｊ１、ｘｊ２、・・・、ｘｊＫ）が存在するとき、ｘｊ１、ｘｊ２、・・・、ｘｊＫを固定部分に含ませる。
別の手法として、ある値の組（ｐ１  、ｐ２  、・・・ｐＫ  ）において、
Ｆｐ１、ｐ２、・・・ｐＫ（ｘｊ１、ｘｊ２、・・・、ｘｊＫ）≧Ｔ
を満たす変数の組（ｘｊ１、ｘｊ２、・・・、ｘｊＫ）が存在するとき、ｘｊ１、ｘｊ２、・・・、ｘｊＫを固定部分に含ませるようにしてもよい。
【００５１】
更に他の手法として、ＫとＴをそれぞれ１種類ずつに限定せずに、それぞれ複数種類用意し、それらを用いてそれぞれ上記の計算法で求めた固定部分を組み合わせて、例えば集合和を求めて、それを固定部分とすることも可能である。
【００５２】
適応度演算部１６は部分集団内で各染色体の適応度を演算する。即ちナップザック袋に詰めた品物の価値の総和Ｖ（｛ｘｉ  ｝）を計算する。このとき大きさの総和も計算し、ナップザック袋の大きさを越えた染色体が存在したとき、その適応度をゼロとする。
【００５３】
例えば図６（Ａ）に示す染色体▲１▼〜▲６▼に対して適応度及び大きさの総和を求める。この例では、ナップザック袋の大きさＳ＝１００を越える染色体はないが、あればその染色体の適応度はゼロとなる。
【００５４】
選択演算部１７は部分集団内の各染色体のうち適応度の高いものを残し、適応度の低いものを削除する。この削除したとき、必要ならば適応度の高いものを同じ部分集団内に複製する。このとき、ルーレット・ホイール選択により確率を定めて残存消去の選択を行うことができる。染色体ｋの適応度をＨｋ  とすると、染色体ｋの残存を、
確率＝Ｈｋ  ／（Ｈ１  ＋Ｈ２  ＋・・・＋ＨＮ  ）
で選択する。
【００５５】
図６（Ａ）の例では、同（Ｂ）に示す如く、各染色体の適応度の総和が４８７であるので、これら６個の染色体をそれぞれ確率７２／４８７、８６／４８７、１１６／４８７、７３／４８７、４９／４８７、９１／４８７で総数６個になるまで、重複を許して選択する。その結果選択操作によって、図６（Ｃ）に示す如き染色体が選択される。
【００５６】
なお、図１（Ｂ）における評価・選択部４は、前記適応度演算部１６と選択演算部１７で構成される。
交叉演算部１８は、選択された染色体に更に交叉操作を施すものである。まず前記図６（Ｃ）に示す６個の染色体に対してランダムに２個ずつペアを組み合わせ、図７に示すペアＰ１  、Ｐ２  、Ｐ３  を得る。このペアＰ１  〜Ｐ３  について、予め与えられる交叉確率で、ペア毎に交叉させるかさせないかを決める。この場合、ペアＰ１  とＰ２  については交叉を行わず、ペアＰ３  に対して交叉を行う。交叉には一様交叉と部分固定有りの一様交叉があるが、本発明では前記の如く、染色体の相関関係に基づき固定部分を算出するので、後者の部分固定有りの一様交叉に基づき交叉を行う。
【００５７】
一様交叉は、染色体を構成する各ビットを等確率で「０」または「１」を選んでそれらを並べた入れ換えビット列を用意する。例えば図７（Ｂ）を用意する。染色体ＡとＢとの、部分固定のない一様交叉とは、入れ換えビット列の対応するビットが「１」ならば染色体ＡとＢとでビットを入れ換え、「０」ならばそのままにすることを指すものである。
【００５８】
例えば図７（Ｃ）に示す如き染色体ＡとＢについて、前記図７（Ｂ）に示す入れ換えビット列に基づき一様交叉を行うとき、＋マークのビットにおいて入れ換えが行われ、交叉後は染色体Ａ′、Ｂ′となる。
【００５９】
ところで部分固定有りの一様交叉は、固定位置が入れ換えビット列の「１」の部分にすべて入らないように、固定位置に対応する入れ換えビットが必ず「０」になる、入れ換えビット列を用意する。ビットの入れ換えは部分固定なしと同じように行う。
【００６０】
例えば固定部分が図７（Ｄ）に示すものであるとき、図７（Ｅ）の▲１▼に示す入れ換えビット列は、固定位置に対応する部分が「０」であるので要件を満たすが、図７（Ｅ）の▲２▼に示す入れ換えビット列は左から２番目の部分が「０」でないので要件を満たしていない。
【００６１】
入れ換えビット列が図７（Ｅ）▲１▼であって、染色体ＡとＢが図７（Ｆ）に示すものであるとき、＋マークのビットで入れ換えが起こるので、部分固定有りの一様交叉による交叉後は、図７（Ｆ）のＡ′、Ｂ′に示す如きものとなる。
【００６２】
従って、選択演算部１７において、前記図６（Ｃ）に示す如き選択後の各染色体について前記図７（Ａ）に示す染色体の各ペアにおいて、交叉演算部１８は、予め与えられた交叉確率により部分固定有りの一様交叉を施す。この結果、図７（Ａ）に示すペアＰ３  で交叉が起き、その入れ換えビット列が図７（Ｅ）▲１▼であったとき、図８（Ａ）に示す如く、ペアＰ３  の＋マークのビットで入れ換えが起こり、ペアＰ３  ′が得られる。その結果、この交叉後の部分集団は、図８（Ｂ）に示す如きものとなる。なお確率により複数のペアでこの入れ換えが行われるとき、入れ換えビット列は、各ペア毎に違うものを用意する。
【００６３】
突然変異演算部１９は、染色体について予め与えられた突然変異確率でビット反転を行う。ただし固定部分はビット反転させない。例えば図８（Ｂ）に示す部分集団の第４行目の染色体の第６番目のビットに突然変異が起きたとき、その変異後は図８（Ｃ）に示すものとなる。
【００６４】
局所改善演算部２０は、予め与えられた確率で、前記突然変異演算部１９で説明したビット反転を複数回繰り返し行うものである。このとき適応度が高くなるときにのみ反転させ、反転させても適応度が高くならないときは、反転させなかったものとする。
【００６５】
部分解固定変更部２１は、図９（Ａ）に示す如く、自己の部分集団最適化部１３−１の最良染色体と隣接の部分集団最適化部１３−２、１３−３、１３−４、１３−５の最良染色体とを比較して、自部分集団最適化部１３−１における固定部分を変更するものである。
【００６６】
即ち、ある世代で、自部分集団最適化部１３−１が固定部分を更新するとする。この時点で、この部分集団最適化部１３−１が保持するものが、図９（Ｂ）に示す６個の染色体であり、その固定部分が図９（Ｃ）に示すものであり、隣接の部分集団最適化部１３−２、１３−３、１３−４、１３−５からの各適応度のもっとも高い染色体つまり最良染色体が、それぞれ図９（Ｄ）であったとする。
【００６７】
各部分集団最適化部１３−１、１３−２、１３−３、１３−４、１３−５・・・には、図示省略した比較部が設けられており、これらを前記部分集団交信部１２により、正方格子トーラス接続し、隣接部分集団の染色体の適応度が検知できるように構成されている。
【００６８】
図９（Ａ）に示す例では、部分集団最適化部１３−１に保持される染色体を自部分集団の染色体とするとき、隣接の部分集団最適化部１３−２、１３−３、１３−４、１３−５に保持される染色体をそれぞれ東、西、南、北の染色体という。そして次の処理を行う。
【００６９】
先ず自部分集団の、適応度がもっとも高い染色体である最良染色体の持つ適応度と、各隣接部分集団の最良染色体の持つ適応度とを比較する。これにより次の３つの場合を考える。
【００７０】
▲１▼自部分集団の最良染色体が隣接部分集団のどれよりも良いとき、つまり自部分集団の最良染色体の適応度が隣接部分集団の各最良染色体の適応度のどれよりも高いとき。
【００７１】
▲２▼自部分集団の最良染色体が隣接部分集団のどれよりも悪いとき、つまり自部分集団の最良染色体の適応度が隣接部分集団の各最良染色体の適応度のどれよりも低いとき。
【００７２】
▲３▼前記▲１▼、▲２▼のいずれでもないとき。
それぞれのケースにおいて、固定部分の変更の仕方が異なる。以下に各ケースについて説明する。
【００７３】
▲１▼自部分集団の最良染色体が、隣接部分集団の各最良染色体のどれよりも良い場合には、図９（Ｂ）に示す現部分集団の染色体について、前記図５において初期固定部分を演算したものと同じ手順で新しい固定部分を演算する。まず図１０（Ａ）に示す如く、頻度表を求める。
【００７４】
そして頻度しきい値を６として
Ｆ１１（ｉ、ｊ）＋Ｆ００（ｉ、ｊ）≧６
またはＦ１０（ｉ、ｊ）＋Ｆ０１（ｉ、ｊ）≧６
となる（ｉ、ｊ）を探す。これにより、図１０（Ａ）の頻度表から（３、７）、（５、９）が検出される。これらの位置３、５、７、９を固定位置とし、それらの値を、Ｆ１１（ｉ、ｊ）又はＦ００（ｉ、ｊ）、Ｆ１０（ｉ、ｊ）又はＦ０１（ｉ、ｊ）の大きい方の値を選ぶ。同じときはランダムに選ぶ。これにより図１０（Ｂ）に示す如きビット位置に固定部分「０」、「１」を持つ新しい固定部分が得られる。なお図１０（Ｂ）において？は非固定を表わす。
【００７５】
部分集団の染色体自体については変更はない。
なお、部分群の大きさ、頻度しきい値は世代毎に異なってもい。また既に固定部分の割合が非固定部分よりもある一定値以上であったときは、固定部分を再度計算しない。
【００７６】
▲２▼自部分集団の最良染色体が、隣接部分集団のどれよりも悪い場合には、図９（Ｄ）に示す、隣接部分集団の最良染色体をあたかも１つの部分集団とみなして、初期固定部分を演算したものと同じ手順で新しい固定部分を演算する。まず図１１（Ａ）に示す如く、頻度表を求める。
【００７７】
そして頻度しきい値を４として、
Ｆ１１（ｉ、ｊ）＋Ｆ００（ｉ、ｊ）≧４
またはＦ１０（ｉ、ｊ）＋Ｆ０１（ｉ、ｊ）≧４
となる（ｉ、ｊ）を探す。これにより図１１（Ａ）の頻度表から（２、５）、（２、７）、（３、９）、（５、７）が検出される。これらの位置２、３、５、７、９を固定位置とし、それらの値は、Ｆ１１（ｉ、ｊ）またはＦ００（ｉ、ｊ）、Ｆ１０（ｉ、ｊ）またはＦ０１（ｉ、ｊ）の大きい方の値を選ぶ。同じときはランダムに選ぶ。これにより図１１（Ｂ）に示す如きビット位置に固定部分「０」、「１」をもつ新しい固定部分が得られる。なお図１１（Ｂ）において？は非固定を表す。それから、後述する部分固定解生成部２２により、図１１（Ｃ）に示す自部分集団を構成する。
【００７８】
なお、部分群の大きさ、頻度しきい値は世代毎に異なってもよい。
▲３▼前記▲１▼、▲２▼のいずれでもない場合、例えば東の最良染色体「００１１１００１０１」が自部分集団の最良染色体よりも良いとき、これと図９（Ｃ）で示す如き自部分集団の固定部分を比較する。即ち、
0003595043.tif 000007
を比較する。そして矛盾する固定部分を除く。
【００７９】
この例では、固定部分の３ビット目と７ビット目の２箇所とも自部分集団の染色体よりも良い「東」染色体と異なるので、この矛盾する固定部分を除き、新しい、固定部分を下記の通りオール？となる。
【００８０】
新しい固定部分  ？？？？？？？？？？
部分集団の染色体自体については変更はない。
部分固定解生成部２２は、前記▲２▼の如く、隣接部分集団の最良染色体の共通部分を演算することにより得られた新しい固定部分を含む染色体をランダム生成して自部分集団を再構成するものである。前記▲２▼の例では、部分解固定変更部２１から、図１１（Ｂ）に示す新しい固定部分が伝達されたとき、図９（Ｄ）に示す「東」、「西」、「北」、「南」の各最良染色体に加えて、部分集団の大きさが元の大きさになるように、この新しい固定部分を必ず含む染色体をランダムに２つ生成して、図１１（Ｃ）に示す新しい自部分集団を構成する。
【００８１】
なお、前記説明では、隣接部分集団として、東、西、北、南の４つを使用した例について説明したが、隣接部分集団はこれに限定されるものではなく、２個でもあるいは５個以上でも適宜設定できるものである。
【００８２】
本発明の動作を図４に示すフローチャートに基づき以下のステップにより説明する。
Ｓ１．最初に、集団制御部１０に対し、例えばナップザック問題の解生成の場合には、データとして品物の個数Ｎと各品物の大きさ、価値、ナップザック袋の大きさを入力する。例えば図１（Ａ）に示す如く、１０個の品物の大きさ、価値、ナップザック袋の大きさを１００等を入力する。またパラメータとして部分集団あたりの染色体の数（前記の例では６）、固定部分変更世代数（例えば１０世代毎１、交叉確率、突然変異率、局所改善率、選択確率等を入力する。これらのデータ、パラメータは部分集団最適化部１３−１、１３−２・・・、初期集団生成部１１に入力される。
【００８３】
いま部分集団最適化部の数を５個としたとき、初期集団生成部１１は、１部分集団最適化部あたり６個の染色体、即ち全体で６×５＝３０個の染色体を例えば乱数生成器を用いて作成する。そしてこの作成した染色体を、部分集団交信部１２を経由して部分集団最適化部１３−１、１３−２・・・に６個ずつ分配する。このようにして例えば部分集団最適化部１３−１には、図５（Ａ）に示す如き、染色体が受信される。このようにして初期染色体集団が生成される。
【００８４】
Ｓ２．部分集団最適化部１３−１、１３−２・・・では、図３に示す如く、部分解固定計算部１５が、この６個の染色体に基づき部分集団の染色体の頻度算出を行い、これに基づき固定部分を計算する。このため、初めに、図５（Ｂ）に示す如く、頻度表を作成する。そしてそのＦ１１（ｉ、ｊ）＋Ｆ００（ｉ、ｊ）またはＦ１０（ｉ、ｊ）＋Ｆ０１（ｉ、ｊ）がしきい値例えば６以上の（ｉ、ｊ）を探し、（２、７）、（５、１０）を検出し、前記の如く、図５（Ｃ）に示す如く、ビット位置の２、５、７、１０番目のものを「１」、「０」に固定した固定部分を算出する。
【００８５】
Ｓ３．このようにして固定部分を求めたあと、各部分集団で染色体集団の評価、選択、交叉、変異等を行い、次世代集団を求める。例えば図６（Ａ）に示す染色体▲１▼〜▲６▼の適応度の計算を適応度演算部１６で行い、選択演算部１７で例えばルーレット・ホイール選択により残存消去選択し、交叉演算部１８により、前記図７、図８（Ａ）に説明した如き交叉演算を行い、突然変異演算部１９により、ある確率に基づき図８（Ｃ）（Ｄ）に説明した如き突然変異を行う。そして局所改善演算部２０により、ある確率に応じて反転の繰り返しを行う。このようにして次世代の染色体の部分集団を得る。即ち初期染色体集団に対しこれを１回行えば第２世代の部分集団となり、２回行えば第３世代の部分集団となる。
【００８６】
Ｓ４．部分集団制御部１４は、前記（３）を行う毎に、更に改善が進むと判断したとき、終了と判定せず前記（３）の反復を行う。
Ｓ５．そしてこの反復を、予めパラメータにより定められた回数、例えば１０回行ったとき、隣接部分集団と中間結果を交換する。例えば図９に示す如く、自部分集団最適化部１３−１では、隣接部分集団最適化部１３−２、１３−３、１３−４、１３−５から、部分集団交信部１２を経由してそれぞれの部分集団の最良染色体を受信する。
【００８７】
例えば、「東」、「西」、「北」、「南」の隣接部分集団の最良染色体が伝達されたとき、自部分集団最適化部１３−１ではこれらの最良染色体の適応度を計算する。勿論適応度を一緒に伝達してもよい。そしてこれらの隣接部分集団の最良染色体が自部分集団の最良染色体より良いか悪いか比較する。
【００８８】
Ｓ６．この比較の結果に応じて次の▲１▼、▲２▼、▲３▼のように固定部分を変更し、または自部分集団を再編成する。
▲１▼即ち、自部分集団の最良染色体が、隣接部分集団の最良染色体のどれよりも良いとき、前記▲１▼の如く、自部分集団内の固定部分を再度計算し、それを固定部分とする。この場合、部分群の大きさ、頻度しきい値は前記Ｓ２と同じでなくてもよい。世代毎に異なっていてもよい。ただし既に固定部分の割合が非固定部分よりも、予め定められたある一定値以上であったときは、固定部分を再度計算しない。
【００８９】
▲２▼もし自部分集団の最良染色体が隣接部分集団の最良染色体のどれよりも悪いとき、隣接部分集団の最良染色体を集めてきて、それをあたかも１つの部分集団とみなして、前記▲２▼の如く、固定部分を計算する。この場合、部分群の大きさ、頻度しきい値は前記Ｓ２と同じでなくてもよく、世代毎に異なってもよい。次いで、その固定部分を含む染色体をランダムに生成して、これと隣接部分集団の最良染色体を必ず含ませた、図１１（Ｃ）に示す如き、自部分集団を再度構成する。
【００９０】
▲３▼前記▲１▼、▲２▼のいずれでもないとき、前記▲３▼の如く、自部分集団の最良染色体よりも良い隣接部分集団の最良染色体と自部分集団の固定部分とを比較して、矛盾する固定部分をはずす。このとき自部分集団に隣接部分集団の最良染色体を含ませてもよい。
【００９１】
例えば、固定部分のあるビットの値が「０」で、隣接部分集団の最良染色体の対応する位置のビットの値が「１」ならば、その「０」のビットを固定部分から除く。
【００９２】
Ｓ７．各部分集団最適化部のそれぞれで、前記ステップＳ３と同じ処理を行う。このようなことを終了条件が満たされるまで繰り返す。そしてこれ以上改善が進まないと判断された時点で終了する。そしてそのときの染色体が集団制御部１０から演算結果として出力される。
【００９３】
このような構成により、以下のナップザック問題について、図１４に示す結果が得られた。使用したナップザック問題は、品物数＝９００、品物の大きさは１から１０００までの整数値で、その価値は１から１０００までの整数値とした。疑似一様乱数を用いて、これらの値を与えた。大きさが大きいほど、価値も大きいとしている。大きさと価値の標本相関係数＝０．９７である。ナップザックの大きさ（上限）＝２０００００である。
【００９４】
遺伝アルゴリズムの、選択法はルーレット（ｒｏｕｌｅｔｔｅ  ｗｈｅｅｌ）選択、交叉法は非固定ＧＡでは一様交叉を使用し、部分固定ＧＡでは部分固定有りの一様交叉を用い、突然変異はビット反転を用い、局所改善は使用していない。遺伝アルゴリズムのパラメータ値は、部分集団数６４（＝８×８）、部分集団内の染色体数４０（総染色体数２５６０）、固定部分変更２０世代毎、交叉確率０．６、突然変異率０．００１。なおこれらは最良のパラメータ値の組合わせではない。
【００９５】
シミュレーションは、第８０００世代まで実施した。比較のため、解の部分固定を行わないが、部分集団に分ける並列遺伝アルゴリズムの場合も同様にシミュレーションした。
【００９６】
図１４は解を見つけた世代数を比較している。
第０世代目での最良値（解）は２０１３４６で、解２２００００は、それぞれ、第４８４、３０６世代目に、解２２５５００は、それぞれ、第７６７３、１２８９世代目に見つけている。これらの世代数の比（加速の割合）は、１．６、６．０であった。部分固定を行うことにより、探索時間が短縮された即ち、より最適な解を見つけるのに必要な世代数が減ったことを示している。
【００９７】
このように部分固定を行うことにより、より最適な解を見つけるのに必要な世代数が減少すること、つまり探索時間が短縮されることがわかる。
本発明の第２実施例を図１２及び図１３に基づき説明する。図１２、図１３において、３０は集団制御部、３１は部分集団交信部、３２、３２−１〜３２−ｍは部分集団最適化部、３３は部分集団制御部、３４は部分解固定計算部、３５は解生成部、３６は適応度演算部、３７は選択演算部、３８は交叉演算部、３９は突然変異演算部、４０は局所改善演算部、４１は部分解固定変更部、４２は部分固定解生成部、４３は部分集団記憶部である。
【００９８】
本発明の第１実施例では、集団制御部１０に入力されたデータ、パラメータに基づき、初期集団生成部１１が部分集団最適化部１３−１、１３−２・・・に必要な数の染色体を生成して送出していたが、本発明の第２実施例では、図１３の部分集団最適化部３２に代表的に示す如く、解生成部３５において集団制御部３０に入力されたデータ、パラメータに基づき、部分集団最適化部３２−１、３２−２・・・に必要な数の染色体を生成するものである。他は同一であるのでその詳細な動作説明は省略する。
【００９９】
なお、集団制御部３０は集団制御部１０に対応し、部分集団交信部３１は部分集団交信部１２に対応し、部分集団最適化部３２、３２−１、３２−２・・・は部分集団最適化部１３、１３−１、１３−２・・・に対応し、部分集団制御部３３は部分集団制御部１４に対応し、部分解固定計算部３４は部分解固定計算部１５に対応し、適応度演算部３６は適応度演算部１６に対応し、選択演算部３７は選択演算部１７に対応し、交叉演算部３８は交叉演算部１８に対応し、突然変異演算部３９は突然変異演算部１９に対応し、局所改善演算部４０は局所改善演算部２０に対応し、部分解固定変更部４１は部分解固定変更部２１に対応し、部分固定解生成部４２は部分固定解生成部２２に対応し、部分集団記憶部４３は部分集団記憶部２３に対応する。
【０１００】
本発明の第２実施例では、各部分集団最適化部３２−１、３２−２・・・において並列的に初期染色体集団を生成するので、演算を短時間で行うことができる。
【０１０１】
前記説明は、図５（Ａ）、（Ｂ）に示す如く、頻度表を染色体の２ビットの組み合わせ（ｉ、ｊ）により作成した例について説明したが、本発明はこれに限定されるものではない。
【０１０２】
例えば染色体が図１５（Ａ）に示す如く与えられているとき部分群の大きさ（変数の数）Ｋ＝３の場合、固定部分を下記の如く求める。これは前記Ｋ＝２の拡張として同様に計算できる。便宜上、３個の変数をｉ・ｊ・ｋで表す。前記Ｋ＝２の場合と同様に下記の頻度を求める。
【０１０３】
即ち、頻度  Ｆ１１１（ｉ、ｊ、ｋ）、Ｆ１１０（ｉ、ｊ、ｋ）、Ｆ１０１（ｉ、ｊ、ｋ）、Ｆ１００（ｉ、ｊ、ｋ）、Ｆ０１１（ｉ、ｊ、ｋ）、Ｆ０１０（ｉ、ｊ、ｋ）、Ｆ００１（ｉ、ｊ、ｋ）、Ｆ０００（ｉ、ｊ、ｋ）を求める。
【０１０４】
変数が３個なので、頻度表は三次元立体的な表になるため、前記図５（Ｂ）で示すＫ＝２の場合のように、二次元平面的な表の形で簡便に記述することができないので、ここには具体値を記載しない。
【０１０５】
例えば頻度しきい値を６とした場合、
Ｆ１１１（ｉ、ｊ、ｋ）＋Ｆ０００（ｉ、ｊ、ｋ）≧６
またはＦ１１０（ｉ、ｊ、ｋ）＋Ｆ００１（ｉ、ｊ、ｋ）≧６
またはＦ１０１（ｉ、ｊ、ｋ）＋Ｆ０１０（ｉ、ｊ、ｋ）≧６
またはＦ１００（ｉ、ｊ、ｋ）＋Ｆ０１１（ｉ、ｊ、ｋ）≧６
のどれかが成り立つような（ｉ、ｊ、ｋ）を探す。
【０１０６】
この場合は１組存在し、それは（２、７、９）であった。
このときの頻度は、
Ｆ１１１（２、７、９）＝０、Ｆ１１０（２、７、９）＝０、Ｆ１０１（２、７、９）＝０、Ｆ１００（２、７、９）＝３
Ｆ０００（２、７、９）＝０、Ｆ００１（２、７、９）＝０、Ｆ０１０（２、７、９）＝０、Ｆ０１１（２、７、９）＝３
であった。
【０１０７】
これらの位置２、７、９を固定位置とし、それらの値は、Ｆ１００（２、７、９）とＦ０１１（２、７、９）とを比べて、大きい方の値を選ぶ。
仮に、Ｆ１００（２、７、９）＞Ｆ０１１（２、７、９）ならば、固定部分は図１５（Ｂ）に示す如きものとなる。ここで「１」と「０」は固定位置とその値、？は非固定を表す。この例では同じなので、どちらかをランダムで選んで、例えば固定部分は、図１５（Ｃ）に示す如きものとする。
【０１０８】
また染色体が図１５（Ｄ）に示す如く与えられているとき、部分群の大きさ（変数の数）Ｋ＝４の場合では、固定部分を下記の如く求める。便宜上、４個の変数をｉ、ｊ、ｋ、ｌで表す。
【０１０９】
まず頻度Ｆ１１１１（ｉ、ｊ、ｋ、ｌ）、Ｆ１１１０（ｉ、ｊ、ｋ、ｌ）、Ｆ１１０１（ｉ、ｊ、ｋ、ｌ）、Ｆ１１００（ｉ、ｊ、ｋ、ｌ）、Ｆ００００（ｉ、ｊ、ｋ、ｌ）、Ｆ０００１（ｉ、ｊ、ｋ、ｌ）、Ｆ００１０（ｉ、ｊ、ｋ、ｌ）、Ｆ００１１（ｉ、ｊ、ｋ、ｌ）、Ｆ１０１１（ｉ、ｊ、ｋ、ｌ）、Ｆ１０１０（ｉ、ｊ、ｋ、ｌ）、Ｆ１００１（ｉ、ｊ、ｋ、ｌ）、Ｆ１０００（ｉ、ｊ、ｋ、ｌ）、Ｆ０１００（ｉ、ｊ、ｋ、ｌ）、Ｆ０１０１（ｉ、ｊ、ｋ、ｌ）、Ｆ０１１０（ｉ、ｊ、ｋ、ｌ）、Ｆ０１１１（ｉ、ｊ、ｋ、ｌ）を求める。
【０１１０】
そして例えば頻度しきい値を５とした場合、
Ｆ１１１１（ｉ、ｊ、ｋ、ｌ）＋Ｆ００００（ｉ、ｊ、ｋ、ｌ）≧５
またはＦ１１１０（ｉ、ｊ、ｋ、ｌ）＋Ｆ０００１（ｉ、ｊ、ｋ、ｌ）≧５
またはＦ１１０１（ｉ、ｊ、ｋ、ｌ）＋Ｆ００１０（ｉ、ｊ、ｋ、ｌ）≧５
またはＦ１１００（ｉ、ｊ、ｋ、ｌ）＋Ｆ００１１（ｉ、ｊ、ｋ、ｌ）≧５
またはＦ１０１１（ｉ、ｊ、ｋ、ｌ）＋Ｆ０１００（ｉ、ｊ、ｋ、ｌ）≧５
またはＦ１０１０（ｉ、ｊ、ｋ、ｌ）＋Ｆ０１０１（ｉ、ｊ、ｋ、ｌ）≧５
またはＦ１００１（ｉ、ｊ、ｋ、ｌ）＋Ｆ０１１０（ｉ、ｊ、ｋ、ｌ）≧５
またはＦ１０００（ｉ、ｊ、ｋ、ｌ）＋Ｆ０１１１（ｉ、ｊ、ｋ、ｌ）≧５
のどれかが成立するような変数組（ｉ、ｊ、ｋ、ｌ）を探す。
【０１１１】
この場合は、１組あって、（２、７、９、１０）であった。
Ｆ１１１１（２、７、９、１０）＝０、Ｆ１１１０（２、７、９、１０）＝０、Ｆ１１０１（２、７、９、１０）＝０、Ｆ１１００（２、７、９、１０）＝０、Ｆ００００（２、７、９、１０）＝０、Ｆ０００１（２、７、９、１０）＝０、Ｆ００１０（２、７、９、１０）＝０、Ｆ００１１（２、７、９、１０）＝０、Ｆ１０１１（２、７、９、１０）＝０、Ｆ１０１０（２、７、９、１０）＝０、Ｆ１００１（２、７、９、１０）＝３、Ｆ１０００（２、７、９、１０）＝０、Ｆ０１００（２、７、９、１０）＝０、Ｆ０１０１（２、７、９、１０）＝０、Ｆ０１１０（２、７、９、１０）＝２、Ｆ０１１１（２、７、９、１０）＝１
これらの位置２、７、９、１０を固定位置とし、それらの値は、Ｆ１００１（２、７、９、１０）とＦ０１１０（２、７、９、１０）とを比べて大きい方の値つまりＦ１００１（２、７、９、１０）を選ぶ。
【０１１２】
これにより固定部分は２、７、９、１０の各ビット位置となり、その値は「１００１」となる。即ち、図１５（Ｅ）に示す如きものとなる。
また同一の染色体集団を使って固定部分を異なる条件で計算した例を示す。部分染色体集団が例えば図１６（Ａ）の如く、染色体の総数Ｍ＝８、各染色体のビット数＝１０で与えられる。
【０１１３】
このときに固定部分の計算を、変数の数Ｋ、頻度しきい値Ｔを下記の条件１）、２）でそれぞれ求める。
条件１）：Ｋ＝３、  Ｔ＝６
条件２）：Ｋ＝２、  Ｔ＝８
条件１）
変数の組（ｉ、ｊ、ｋ）に関して頻度
Ｆ１１１（ｉ、ｊ、ｋ）、Ｆ１１０（ｉ、ｊ、ｋ）、Ｆ１０１（ｉ、ｊ、ｋ）、Ｆ１００（ｉ、ｊ、ｋ）、Ｆ０００（ｉ、ｊ、ｋ）、Ｆ００１（ｉ、ｊ、ｋ）、Ｆ０１０（ｉ、ｊ、ｋ）、Ｆ０１１（ｉ、ｊ、ｋ）
を求める。そして
Ｆ１１１（ｉ、ｊ、ｋ）＋Ｆ０００（ｉ、ｊ、ｋ）≧６
またはＦ１１０（ｉ、ｊ、ｋ）＋Ｆ００１（ｉ、ｊ、ｋ）≧６
またはＦ１０１（ｉ、ｊ、ｋ）＋Ｆ０１０（ｉ、ｊ、ｋ）≧６
またはＦ１００（ｉ、ｊ、ｋ）＋Ｆ０１１（ｉ、ｊ、ｋ）≧６
のいずれかを満たす（ｉ、ｊ、ｋ）を探す。
【０１１４】
１組あって、それは（２、４、８）である。
Ｆ１１１（２、４、８）＝１、Ｆ１１０（２、４、８）＝３、Ｆ１０１（２、４、８）＝０、Ｆ１００（２、４、８）＝０、Ｆ０００（２、４、８）＝０、Ｆ００１（２、４、８）＝３、Ｆ０１０（２、４、８）＝０、Ｆ０１１（２、４、８）＝１
従って固定位置は２、４、８である。それらの位置の値は、Ｆ１１０（２、４、８）とＦ００１（２、４、８）がともに３で同じなので、ランダムにどちらかを選び、１、１、０となり、固定部分は図１６（Ｂ）に示す如きものとなる。
【０１１５】
条件２）
変数の組（ｉ、ｊ）に関して、頻度Ｆ１１（ｉ、ｊ）、Ｆ１０（ｉ、ｊ）、Ｆ０１（ｉ、ｊ）、Ｆ００（ｉ、ｊ）を求める。その結果図１６（Ｃ）に示す頻度表が得られる。この頻度表の各（ｉ、ｊ）に対応した欄には４つの値が並べられているが、これは左から順にＦ１１（ｉ、ｊ）、Ｆ１０（ｉ、ｊ）、Ｆ０１（ｉ、ｊ）、Ｆ００（ｉ、ｊ）を示す。
【０１１６】
この頻度表より
Ｆ１１（ｉ、ｊ）＋Ｆ００（ｉ、ｊ）≧８
またはＦ１０（ｉ、ｊ）＋Ｆ０１（ｉ、ｊ）≧８
のどれかを満たす（ｉ、ｊ）を探す。しかしこの場合は１組も存在しない。従って固定部分は、図１６（Ｄ）に示す如き、オール？の、固定値のない非固定部分のみのものとなる。
【０１１７】
また本発明では、固定部分の計算のやり方を、状況変化に応じて変えることができる。遺伝アルゴリズムの探索の初期の段階、つまり初期の世代では染色体集団は一般にかなりばらついているので、固定部分の計算としては、相対的に緩い条件、例えばＫ＝３、Ｔ＝６を用い、その後、例えば１００世代後は、染色体集団のばらつきが減少しているので、相対的に厳しい条件、例えばＫ＝３、Ｔ＝８を使用する。一般にＫが大きい程、Ｔが大きい程、計算で得られる固定部分が小さくなり、厳しい条件になる。
【０１１８】
本発明では、固定部分を異なる条件で計算し、それらで得られた固定部分を組み合わせて、これらとは別の新たな固定部分とすることができる。ある条件１）と条件２）があって、それらから固定位置とその値が求まっているものとする。ある位置が両者のどちらかのみに含まれるときは、それを両者とは別の新たな固定部分に入れる。またある位置が両者に含まれるときは、両者の値が一致したときのみ、それを新たな固定部分に入れる。
【０１１９】
例えば図１７に示す如く、条件１）、条件２）からの結果が得られるとき、変数２は両者に含まれ、値が一致しているので、新たな固定部分に入れる。しかし変数４は両者に含まれるものの、値が一致していないので、新たな固定部分には入れない。また変数３、７は条件２のみに含まれているので、新たな固定部分に入れる。変数８は条件１のみに含まれているので、新たな固定部分に入れる。このようにして、図１７に示す如き新たな固定部分が得られる。
【０１２０】
本発明によれば頻度表により相関関係の大きいところを検出し、それに基づき固定部分を求めるので、適切な固定部分を検出することができる。
【０１２１】
【発明の効果】
本発明によれば、染色体の部分間での相関関係を、遺伝操作によって壊されにくくし、その結果演算時間が短縮される。
本発明によれば、部分集団内での染色体の固定部分を、より的確に決めることができ、それにより演算時間が短縮できる。
【０１２２】
本発明によれば、世代が進むと共に部分集団が変化するのに対応して、染色体の固定部分をより的確に決めることができ、これによりこれまた演算時間を短縮することができる。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明の一実施例構成図である。
【図３】本発明の一実施例における部分集団最適化部の構成図である。
【図４】本発明の動作説明図（その１）である。
【図５】本発明の動作説明図（その２）である。
【図６】本発明の動作説明図（その３）である。
【図７】本発明の動作説明図（その４）である。
【図８】本発明の動作説明図（その５）である。
【図９】本発明の動作説明図（その６）である。
【図１０】本発明の動作説明図（その７）である。
【図１１】本発明の動作説明図（その８）である。
【図１２】本発明の第２実施例構成図である。
【図１３】本発明の第２実施例における部分集団最適化部の構成図である。
【図１４】本発明において解を見つけた世代の説明図である。
【図１５】本発明における固定部分計算説明図の他の例である。
【図１６】本発明における、同一の染色体集団に対して、固定部分を異なる条件で計算したときの説明図である。
【図１７】本発明における、異なる条件で得られた固定部分を組み合わせて別の固定部分を演算したときの説明図である。
【符号の説明】
１  初期集団生成部
２  頻度算出部
３  初期固定部分計算部
４  評価・選択部
５  交叉部
６  突然変異部
７  交信部
８  固定部分計算部
１０  集団制御部
１１  初期集団最適化部
１２  初期集団交信部
１３、１３−１〜１３−ｎ  部分集団最適化部
１４  部分集団制御部
１５  部分解固定計算部
１６  適応度演算部
１７  選択演算部
１８  交叉演算部
１９  突然変異演算部
２０  局所改善演算部
２１  部分解固定変更部
２２  部分固定解生成部
２３  部分集団記憶部
【図１】
0003595043.tif 000008
【図２】
0003595043.tif 000009
【図３】
0003595043.tif 000010
【図４】
0003595043.tif 000011
【図５】
0003595043.tif 000012
【図６】
0003595043.tif 000013
【図７】
0003595043.tif 000014
【図８】
0003595043.tif 000015
【図９】
0003595043.tif 000016
【図１０】
0003595043.tif 000017
【図１１】
0003595043.tif 000018
【図１２】
0003595043.tif 000019
【図１３】
0003595043.tif 000020
【図１４】
0003595043.tif 000021
【図１５】
0003595043.tif 000022
【図１６】
0003595043.tif 000023
【図１７】
0003595043.tif 000024