(57)【特許請求の範囲】
【請求項１】
計算機が遺伝的アルゴリズムを用いて最適化問題を処理する方法であって，
遺伝的アルゴリズムにおける処理対象となる領域についての部分領域への分割方法が異なるごとに，当該分割方法により分割された部分領域の各々に基づく遺伝子から構成される染色体を持つ個体を生成して該生成した個体の集団を島とし，複数の島によって島モデルを構成し，前記島モデルの各島に，遺伝的アルゴリズムと組み合わされた，それぞれ他の島とは異なるヒューリスティックな解法に基づく既存型アルゴリズムを対応させる情報をメモリに記憶し，
前記各島ごとに，当該島に対応する前記遺伝的アルゴリズムと前記既存型アルゴリズムとによるハイブリッド型遺伝的アルゴリズムを用いて，当該島における個体の集団の中で適応度の高い染色体を持つ個体をより高い確率で選択して次世代の親とする選択／自己複製の操作，二つの染色体の一部を互いに入れ換えて新たな個体を作り出す交叉の操作，および一つの染色体の一部の遺伝子をランダムに置き換える突然変異の操作を一世代とする操作を繰り返すことにより，前記島における個体の染色体の情報を更新し，
かつ，所定の世代毎に，前記島モデルにおける島間で個体を交換する
ことを特徴とするハイブリッド型遺伝的アルゴリズムの島モデルによる最適化問題処理方法。
【請求項２】
前記島モデルにおける第１の島と第２の島の個体を親として生じた子供は，第１の島もしくは第２の島，または他の第３の島に入れることによって，島間での個体の交換を行う
ことを特徴とする請求項１記載のハイブリッド型遺伝的アルゴリズムの島モデルによる最適化問題処理方法。
【請求項３】
前記島モデルは，少なくとも，それぞれ異なる既存型アルゴリズムＬi に対応づけられるＮ個の島ｉ（ｉ＝１，２，…，Ｎ）と，必要な数だけ用意された異なる既存型アルゴリズムＬj ，Ｌk のペアに対応づけられる島（ｊ，ｋ）（ｊ≠ｋ（ｊ，ｋ＝１，２，…，Ｎ））とから構成される
ことを特徴とする請求項１または請求項２記載のハイブリッド型遺伝的アルゴリズムの島モデルによる最適化問題処理方法。
【請求項４】
計算機により遺伝的アルゴリズムを用いて最適化問題を解くためのプログラムを記録した計算機読み取り可能な記録媒体であって，
遺伝的アルゴリズムにおける処理対象となる領域についての部分領域への分割方法が異なるごとに，当該分割方法により分割された部分領域の各々に基づく遺伝子から構成される染色体を持つ個体を生成して該生成した個体の集団を島とし，複数の島によって島モデルを構成し，前記島モデルの各島に，遺伝的アルゴリズムと組み合わされた，それぞれ他の島とは異なるヒューリスティックな解法に基づく既存型アルゴリズムを対応させる情報をメモリに記憶し，
前記各島ごとに，当該島に対応する前記遺伝的アルゴリズムと前記既存型アルゴリズムとによるハイブリッド型遺伝的アルゴリズムを用いて，当該島における個体の集団の中で適応度の高い染色体を持つ個体をより高い確率で選択して次世代の親とする選択／自己複製の操作，二つの染色体の一部を互いに入れ換えて新たな個体を作り出す交叉の操作，および一つの染色体の一部の遺伝子をランダムに置き換える突然変異の操作を一世代とする操作を繰り返すことにより，前記島における個体の染色体の情報を更新し，
かつ，所定の世代毎に，前記島モデルにおける島間で個体を交換する処理を，
計算機に実行させるためのプログラムを記録した
ことを特徴とするハイブリッド型遺伝的アルゴリズムの島モデルによる最適化問題処理プログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，計算機による遺伝的アルゴリズム（ＧＡ：Genetic Algorithm ）が適用可能な最適化問題の処理方法であって，特にハイブリッド型遺伝的アルゴリズムの島モデルによる最適化問題処理方法に関する。
【０００２】
【従来の技術】
遺伝的アルゴリズムとは，生物の遺伝の機構を模倣して，それを工学的に応用した技術である。生物の進化の過程では，既存の個体（親）から新たなる個体（子）が生まれる際に，個体の持つ染色体同士の交叉，染色体上の遺伝子の突然変異などが起こる。そして，環境に適応しない個体は淘汰され，環境により適応した個体が生きのびて新たな親となり，さらに新たな子孫を作っていく。このようにして，環境に適応した個体の集団が生き伸びていく。各個体がどの程度環境に適応するかは，染色体（遺伝子の一次元ストリング）によって決定される。
【０００３】
遺伝的アルゴリズムでは，図２６に示すように，最適化問題の解候補を遺伝子の一次元ストリングである染色体として表現し，解候補の集団に対して選択（selection ）／自己複製（reproduction）・交叉（crossover ）・突然変異（mutation）等の操作を繰り返し施すことにより最適解の探索を行う。最適化問題の目的関数が環境に相当し，目的関数を最適にするものほど大きい値を取るような適応度関数が染色体に対して定義される。
【０００４】
選択／自己複製とは，図２７に示すように，集団の中で適応度の高い染色体を持つ個体をより高い確率で選択して次世代の親とする操作である。交叉とは，図２８に示すように，二つの染色体（親）の一部を互いに入れ換えて新たな個体（子）を作り出す操作である。突然変異とは，図２９に示すように，一つの染色体の一部の遺伝子をランダムに置き換える操作である。これらの操作を繰り返すことによって，適応度のより高い染色体すなわち目的関数をより最適化する解が得られる。
【０００５】
【発明が解決しようとする課題】
遺伝的アルゴリズムでは集団の多様性を維持するのが一般には難しい。本発明は，遺伝的アルゴリズムが適用可能な最適化問題において，解候補が狭い解空間の部分集合に偏るのを防ぐことを課題とする。
【０００６】
【課題を解決するための手段】
本発明の基本的な考え方を説明する。遺伝的アルゴリズムの集団の多様性を維持するために，「島」と呼ばれるいくつかの集団を準備する。図１に示すように，例えば三つの「島」または集団を考える。これらを「島１」，「島２」，「島３」と呼ぶ。これらの遺伝的アルゴリズムを使って同じ最適化問題を解くことを考える。そして，この最適化問題を解くための高速な既存型アルゴリズムがあると仮定する。ここで，既存型アルゴリズムとは，ヒューリスティックな解法に基づくアルゴリズムである。これらの既存型アルゴリズムをＬ1 ，Ｌ2 ，Ｌ3 ，…とする。Ｌ1 とＬ2 は同じ手法であってパラメータが違うだけでもよく，また，まったく別の手法であってもよい。これら三つの島の個体は，次のようにして交叉を実施する。
・「島１」ではＧＡと既存型アルゴリズムＬ1 が組み合わされている。
・「島２」ではＧＡと既存型アルゴリズムＬ2 が組み合わされている。
・「島３」ではＧＡと既存型アルゴリズムＬ1 とＬ2 が組み合わされている。
・「島１」の個体と「島２」の個体を親とした結果生じた子供は「島３」の集団に入れる。
・「島１」の個体と「島３」の個体を親とした結果生じた子供は「島１」または「島３」の集団に入れる。
・「島２」の個体と「島３」の個体を親とした結果生じた子供は「島２」または「島３」の集団に入れる。
【０００７】
上記のようにして，「島」の間で個体をやりとりすると，ＧＡと組み合わせている既存型アルゴリズムと一般には矛盾が生じない。図１に示す三つの「島」で説明した方法は，以下のように一般化できる。
【０００８】
一般にＮ個の島，「島１」，「島２」，…，「島Ｎ」を考える。これらの「島ｉ」（ｉ＝１，…，Ｎ）の集団は遺伝的アルゴリズムを，高速な既存型アルゴリズムＬｉ（ｉ＝１，…，Ｎ）と組み合わされている。ここで，一般に既存型アルゴリズムＬｉは，いくつかの既存型アルゴリズムの組み合わせであっても差し支えない。
【０００９】
図２に示すように，これらのＮ個の島の他に NＣ2 ＝Ｎ（Ｎ−１）／２個の「島（ｉ，ｊ）」（ｉ＜ｊ，ｉ＝１，…，Ｎ，ｊ＝２，…，Ｎ）を準備する。この新しい「島（ｉ，ｊ）」は，既存型アルゴリズムＬｉとＬｊを遺伝的アルゴリズムと組み合わせている。
【００１０】
「島」の間の個体の交換方法は，以下のような方法で行う。
・「島ｉ」と「島ｊ」（ｉ＜ｊ）の個体を親として生じた子供は「島（ｉ，ｊ）」に入れる。
・「島ｉ」と「島（ｉ，ｋ）」の個体を親として生じた子供は「島ｉ」に入れるか「島（ｉ，ｋ）」に入れる。
・「島ｉ」と「島（ｋ，ｉ）」の個体を親として生じた子供は「島ｉ」に入れるか「島（ｋ，ｉ）」に入れる。
【００１１】
基本的には個体の交換は，上記のような「島」の間のみで行われる。
【００１２】
もし，「島ｉ」と「島（ｊ，ｋ）」（ｉ≠ｊ≠ｋ）との間で個体の交換を許すとすると，新しい「島」を作るのが自然である。この新しい島を「島（ｉ，ｊ，ｋ）」で示す。この島では，遺伝的アルゴリズムと既存型アルゴリズムＬｉ，Ｌｊ，Ｌｋとが組み合わされている。さらに「島（ｉ，ｊ）」と「島（ｋ，ｌ）」（Ｎ≧４，ｉ≠ｊ≠ｋ≠ｌ）の間の個体の交換を考えると，さらに遺伝的アルゴリズムと既存型アルゴリズムＬｉ，Ｌｊ，Ｌｋ，Ｌｌとを組み合わせた集団のいる「島（ｉ，ｊ，ｋ，ｌ）」が必要になる。
【００１３】
このように，個体の交換を実施する島の制限を緩くすればするほど，新しい島が必要になる。このような島の数は，最初の島の数をＮとすると，全部で（２N −１）島となる。このようにして生成された「島」の集合を「島」のタワーと呼ぶ。
【００１４】
図３は，Ｎ＝４の場合の島のタワーの例を示す。なお，実際の適用上は個体の交換を適当に制限して「島」の総数に制限を設ける必要がある。
【００１５】
本発明に係る方法は，遺伝的アルゴリズムの島モデルを用いて集団の多様性の維持を効果的に実施する方法であり，適応度の増大に寄与するとともに，遺伝的アルゴリズムの計算速度を増加させる方法である。また，この方法によって，遺伝的アルゴリズムの大域的探索法により効率的に最適化問題の解の探索を実施できる。
【００１６】
【発明の実施の形態】
図４に，本発明の動作の流れの概要を示す。まず，ＧＡと組み合わせるその他のアルゴリズムＬ1 ，Ｌ2 ，…，ＬN を選択し（Ｓ１），Ｎ個の島ｉ（ｉ＝１，２，…，Ｎ）を用意して，島ｉの集団はハイブリッド型遺伝的アルゴリズム（ＧＡ＋Ｌi ）に従って発展するようにし（Ｓ２），必要な数だけタワーの島（ｉ，ｊ，…，ｋ，ｌ）を用意する（Ｓ３）。
【００１７】
各島（ｉ，ｊ，…，ｋ，ｌ）においてハイブリッド型遺伝的アルゴリズム（ＧＡ＋Ｌi ＋Ｌj ＋…＋Ｌk ＋Ｌl ）で進化させ（Ｓ４），一定の世代毎に各島の間で個体の交叉を実行し（Ｓ５），子供を適切な島のタワーのいずれかの島に入れる（Ｓ６）。ステップＳ４〜Ｓ６の処理を適応度が基準値以上になるまで繰り返し（Ｓ７），適応度が基準値以上のものが得られたら処理を終了する。または，所定の世代数だけステップＳ４〜Ｓ６を繰り返し，その後処理を終了する。以下の実施の形態の説明では，特に断らないが終了条件は任意に定めることができる。
【００１８】
〔配置問題への応用〕
遺伝的アルゴリズムの島モデルの実施の形態として，配置問題のパッキングを取り上げる。この問題は，大きさと配置要素間の結合が定義された複数の配置要素を，所定の配置領域内に重ならないように，かつ結合関係がある配置要素間の距離ができるだけ短くなるように配置する問題である。
【００１９】
最初に通常の（島モデルでない）遺伝的アルゴリズムによる解法を説明し，これをもとにして島モデルによる実施の形態を説明する。
【００２０】
配置問題の配置結果が与えられたとする。このとき，一般には配置要素は点ではなく大きさを持つために，配置領域に配置要素同士が重なって配置される。配置領域を縦もしくは横，または縦と横に適当な幅で分割する。これらの分割された領域を部分配置領域と呼ぶ。
【００２１】
配置要素の相対的な位置関係をできるかぎり保存するために，上記で定義された部分配置領域内で，セルの位置をもとにして，ある定められた方法で配置要素に順序を付ける。この順序をもとにして，部分配置領域内の適当な位置からセルを詰めていくことによって，配置結果の重なりをとる局所的パッキング法により重なりを解消する。
【００２２】
本例では，遺伝的アルゴリズムによって部分配置領域を合わせた配置領域全体のセルの重なりを解消する。また局所的パッキング法と遺伝的アルゴリズムを組み合わせて大局的に最適なパッキングを実現する。
【００２３】
〔配置領域の分割方法と局所的パッキング法〕
配置要素の相対的な位置関係をなるべく維持するために，パッキングを配置領域全体で行うのではなく，配置領域をいくつかの部分配置領域に分割し，これらの部分領域に含まれている配置要素ごとにパッキングを行う。このように部分配置領域で行うパッキングを局所的パッキング法と呼ぶ。ここで配置領域が長方形の場合に，次にような分割法が考えられる。
(a) 配置領域全体を格子状に分割することで部分配置領域を定義する。
(b) 大きな固定配置要素を配置領域から取り去った残りの領域をもとにして部分配置領域を定義する。
(c) 細長い固定配置要素を配置領域から取り去った残りの領域をもとにして部分配置領域を定義する。
(d) 階層的に配置領域を分割して部分配置領域を作る。
【００２４】
上記の方法によって得られた部分配置領域に，以下のような局所的パッキング法を適用する。
(1) 煉瓦積み方式のパッキング法（図５参照）
図５に示すように，下から長方形の配置要素を順番に積み上げていく方法である。
(2) テトリス方式のパッキング法（図６参照）
図６に示すように，様々な大きさの長方形の配置要素を上から落としていき，ある高さになると，配置要素の落とし場所を順次右隣に移して積み上げていく方法である。
(3) 凝縮方式のパッキング法（図７参照）
図７に示すように，配置領域の中央に凝縮させていく方法である。
(4) 拡散方式のパッキング法（図８参照）
図８に示すように，凝縮方式とは反対に配置領域の周辺側から配置要素を並べていく方法である。
【００２５】
〔遺伝的アルゴリズムによる部分配置領域の境界の噛み合わせ（ＧＡｃ）〕
部分領域ごとに局所的パッキング法を実施すると，一般的にある部分領域での配置要素と他の部分配置領域の配置要素の境界部分が噛み合わない状況が起こる。この境界部分を噛み合わせることを遺伝的アルゴリズムによって実施する。以下，この遺伝的アルゴリズムをＧＡｃと略記する。
【００２６】
染色体のコード法は，次のように定める。部分配置領域の境界の噛み合っていない境界にある配置要素は，重なっている配置要素とその近傍にある配置要素として定義される。これらの配置要素に番号を付ける。染色体はこれらの配置要素の座標の値を並べたものとする。
【００２７】
上記の染色体に作用する交叉としては，以下のような方法が考えられる。
・貼り付け交叉法。
・座標の重み付き平均をもとにした交叉法。
【００２８】
ここで，貼り付け交叉法は，親の二つの個体のうち一つの親の染色体の領域を適当な方法で選択し，この領域の遺伝子をもう一方の親の染色体のコピーの対応する領域に貼り付けることで子供の染色体を作り出す方法である。
【００２９】
座標の重み付き平均をもとにした交叉法は，親の二つの個体の染色体の同じ領域を適当な方法で選択する。この領域にある遺伝子すなわち配置要素の座標の親の二個体の重み付き平均を計算し，その結果得られた座標を該当する領域の遺伝子とする染色体をもつ個体を子供とする方法である。これらの交叉法を用いて，親の遺伝子を保存することによって，適応度の増大を高速に行うことが可能になる。
【００３０】
前記の染色体に作用する突然変異としては以下のような方法が考えられる。
・セルの座標をランダムに動かす突然変異。
・重なっているセルの座標をランダムに動かす突然変異。
・重なっているセルの座標とその近傍にあるセルの座標をランダムに動かす突然変異。
【００３１】
突然変異は，セルの座標に微小な正または負の値をランダムに加えることで実行する。座標を変更するセルの選択を他のセルと重なっているセルにすると，セルの重なりの解消を効率よく進めることができる。また，重なっているセルだけでなくこれらのセルの近傍にあるセルをも動かすことで，解空間の探索を広く行うことができる。
【００３２】
適応度（フィットネス）として，以下のように定義されたフィットネス関数を使用できる。
【００３３】
［フィットネス］＝定数−［重みＷ１］×［重なっている配置要素の総数］−［重みＷ２］×［元の配置問題のコスト］
［フィットネス］＝定数−［重みＷ１］×［配置要素の重なっている部分の面積の総和］−［重みＷ２］×［元の配置問題のコスト］
このようにフィットネスを定義することによって，配置要素の重なりを取り除きパッキングすることができる。
【００３４】
遺伝的アルゴリズムＧＡｃの高速化のために，高速なアルゴリズムを組み合わせる。部分配置領域ごとに局所的なパッキングを施すために，どうしても部分配置領域の境界付近で配置要素が噛み合わない事態がおこる。この境界付近の配置要素の不一致を，以下のようなヒューリステックな方法を用いて解決する。
(1) 重なっている配置要素を選択する。
(2) 重なっている配置要素の近傍にある配置要素を選択する。
(3) 選択された配置要素を，上下左右斜めに定められた距離の範囲で移動させる。
(4) 移動した位置で他の配置要素と重なっていない場合には，配置要素をそこに置く。
【００３５】
以上の操作を選択した全ての配置要素について実施する。
【００３６】
〔局所的パッキング法の遺伝的アルゴリズムによる最適化（ＧＡｐ）〕
遺伝的アルゴリズムによって局所的パッキング法を最適化する。以下，この遺伝的アルゴリズムをＧＡｐと略記する。染色体のコード法は，次のように定める。染色体は局所的パッキング法を指定するまとまったパラメータを並べたものである。この染色体は，配置領域の部分配置領域への分割法を指定する。例えば，染色体は各部分配置領域の幅と高さから構成されている。さらに染色体には，各部分配置領域でどのような局所的パッキング法でパッキングするかを指定する遺伝子を持たせてもよい。図９に示すように，配置領域を９分割する場合には，染色体は各部分配置領域の幅ｗ1 〜ｗ3 ，高さｈ1 〜ｈ3 から構成される。さらに，各部分配置領域のパッキング法ｐ1 〜ｐ9 を含めてもよい。
【００３７】
このように染色体が各部分配置領域の幅と高さから構成されている場合には，交叉において，親である二つの染色体から交叉によってできた子供の染色体で各部分領域の幅／高さの総和が配置領域の幅／高さに一致する必要がある。二つの親の染色体のある領域を考え，この部分を交叉の対象とするとき，子供の染色体の対応する染色体領域の遺伝子の値を二つの親の重み付けられた平均とする。これにより，生成される子供の染色体は前に述べた条件を満足する。
【００３８】
図１０に交叉の例を示す。図１０（Ａ）に示すように，親Ｐ０の染色体の遺伝子ｗ2 ，ｗ3 ，ｈ1 の部分を，親Ｐ１の遺伝子ｗ'2，ｗ'3，ｈ'1の部分と交叉させる場合に，ｗ2 ，ｗ3 ，ｈ1 とｗ'2，ｗ'3，ｈ'1との重み付け平均をとって，ｗ''2 ，ｗ''3 ｈ''1 とする。
【００３９】
染色体の突然変異は，染色体の遺伝子をランダムに選択する。このとき常に二つの異なる部分領域の幅／高さに対応する遺伝子をペアで選択する。これらの二つの遺伝子のうちの一つに対応する部分領域の幅／高さを小さなランダムな量を加えたならば，もう一つの遺伝子から同じ量だけ引く。こうすることで，部分配置領域の幅／高さの総和を配置領域の幅／高さに一致させることができる。
【００４０】
図１１に，突然変異の例を示す。図１１において，ｗ2 およびｈ2 にある量をそれぞれ加える突然変異を行い，ｗ'2およびｈ'2とした場合には，他のｗ3 およびｈ3 から同じ量を引いてｗ'3およびｈ'3とする。
【００４１】
適応度として，以下のように定義された適応度を使用できる。
【００４２】
［フィットネス］＝定数−［重みＷ１］×［重なっている配置要素の総数］−［重みＷ２］×［元の配置問題のコスト］
［フィットネス］＝定数−［重みＷ１］×［配置要素の重なっている部分の面積の総和］−［重みＷ２］×［元の配置問題のコスト］
〔局所的パッキング法をベースにした全配置の遺伝的アルゴリズムによる最適化（ＧＡｓ）〕
初期集団の準備法と染色体のコード法を説明する。図１２に示すように，染色体は，配置要素１〜９の座標（ｘ，ｙ）から構成されている。配置領域を部分配置領域へ分割する方法は，この場合，あらかじめ適当な分割法に固定しておく。同一の配置結果のコピーを適当な数だけ作る。これらの各コピーの配置領域を部分配置領域へ分割する。各コピー毎に各部分配置領域に作用させる局所的パッキング法をあらかじめ決めて，ある複数の候補の中から選択する。この割り当ては，コピー毎に異なるとする。この局所的パッキング法の割り当てに従って，各配置のコピーをパッキングする。こうして得られた配置の集団が遺伝的アルゴリズムの初期集団となる。図１３に，初期集団の例を示す。
【００４３】
交叉は，部分配置領域を基本的な単位として実施する。交叉に際しては，以下のような方法で，部分配置領域を選択する。
(1) 他の部分配置領域の配置要素との噛み合わせが旨くいっていない部分配置領域を選択する。
(2) 配置要素の間の間隔があらかじめ決められた規準を満たしていない部分配置領域を選択する。
(3) 選択された部分配置領域に属する配置要素の座標から構成されている染色体の領域を，別の親の対応する領域をもとにして以下のような方法で子供の染色体を作る。
(4) 一つの親の選択された部分配置領域に属する配置要素に対応する遺伝子からなる染色体の領域を，別の親の対応する部分配置領域に属する配置要素に対応する遺伝子からなる染色体の領域へ貼り付けることで交叉を実施する。図１４に，染色体の領域１に別の染色体の領域１’を貼り付けて交叉した例を示す。
(5) 二つの親の同一の部分配置領域に属する同じ配置要素の座標の重み付けられた平均をとることによって子供の染色体を作り出す交叉を実施する。図１５に，染色体の領域１と染色体の領域１’の座標の重み付けられた平均をとって，領域１”を貼り付けた交叉の例を示す。
【００４４】
突然変異は，以下のように行う。
(1) 図１６に示すように，適当に設定された確率で配置要素を選択し，配置要素の座標に正または負のランダムな小さな量を加えることで突然変異を起こす。これによって，より広い解空間を探索できるようになる。
(2) 図１７に示すように，重なっている配置要素を適当な確率で選択する。この選択された配置要素の座標に正または負のランダムな小さな量を加えることで突然変異を起こす。これによって，探索する解空間は狭くなるが，より効率的に解を探索できるようになる。
【００４５】
適応度は以前の定義と同じである。
【００４６】
［フィットネス］＝定数−［重みＷ１］×［重なっている配置要素の総数］−［重みＷ２］×［元の配置問題のコスト］
［フィットネス］＝定数−［重みＷ１］×［配置要素の重なっている部分の面積の総和］−［重みＷ２］×［元の配置問題のコスト］
〔遺伝的アルゴリズムと局所的パッキング法を組み合わせる方法〕
前記の遺伝的アルゴリズムと局所的パッキング法の組み合わせについて説明する。
【００４７】
〔１〕ＧＡｐ＋（ＧＡｃ＋Ｐａｃｋl ）
局所的パッキングの際に使用するパラメータ（配置領域の部分領域への分割法を定めるパラメータなど）をＧＡｐで最適化する。各パラメータの定められた局所的パッキング法Ｐａｃｋl で得られた配置で配置要素が噛み合わない部分配置領域の境界をＧＡｃで噛み合わせて得られた配置の適応度が，遺伝的アルゴリズムＧＡｐの適応度である。この組み合わせによって配置領域の部分領域への分割法を効率良く求めることができる。
【００４８】
図１８に，ＧＡｐ＋（ＧＡｃ＋Ｐａｃｋl ）の組み合わせの場合の処理の流れを示す。まず最初に，ＧＡｐの初期集団を準備する（Ｓ１１）。その後，ＧＡｐに基づき染色体の交叉を行い（Ｓ１２），染色体に突然変異を施す（Ｓ１３）。次に，ＧＡｐの染色体で定められた方法で配置領域を分割し，既存型アルゴリズムに基づく局所的パッキング法を実施する（Ｓ１４）。さらに，部分配置領域の境界をＧＡｃで噛み合わせる（Ｓ１５）。各パラメータの定められた局所的パッキング法Ｐａｃｋl で得られた配置で，配置要素が噛み合わない部分配置領域の境界をＧＡｃで噛み合わせて得られた配置の適応度を，ＧＡｐの適応度とし，これをもとに，所定の選択ルールに従って染色体を選択する（Ｓ１６）。選択方法としては，例えば，ルーレットモデル，モンテカルロモデルなどの各個体の適応度に比例した確率で選択する方法や，エリート保存戦略ルール，トーナメント選択戦略ルールなどを用いる。各個体の適応度が所定の終了条件として与えられた基準値以上かどうかを判定し（Ｓ１７），基準値以上の場合には処理を終了し，基準値に満たない場合にはステップＳ１２へ戻って，同様に次世代の遺伝子操作を繰り返す。
【００４９】
〔２〕ＧＡｃ＋（ＧＡｐ＋Ｐａｃｋl ）
局所的パッキングの際に使用するパラメータ（配置領域の部分領域への分割法を定めるパラメータなど）をＧＡｐで最適化する。各パラメータの定められた局所的パッキング法Ｐａｃｋl で得られた配置の中でもっとも適応度の高い配置についてＧＡｃによって噛み合っていない部分配置領域の境界の配置要素を噛み合わせる。この組み合わせによって配置結果に最も適した局所的パッキング法のパラメータを選択し効率的なパッキングを実行できる。
【００５０】
図１９に，ＧＡｃ＋（ＧＡｐ＋Ｐａｃｋl ）の組み合わせの場合の処理の流れを示す。まず最初に，ＧＡｐの初期集団を準備する（Ｓ２１）。その後，ＧＡｐに基づき染色体の交叉を行い（Ｓ２２），染色体に突然変異を施す（Ｓ２３）。次に，ＧＡｐの染色体で定められた方法で配置領域を分割し，局所的パッキング法を実施する（Ｓ２４）。ルーレット法などの所定の選択ルールに従って染色体を選択する（Ｓ２５）。個体の適応度が所定の基準値以上かどうかを判定し（Ｓ２６），基準値に満たない場合にはステップＳ２２へ戻って，同様に次世代の遺伝子操作を繰り返し，基準値以上の場合には，ステップＳ２７へ進む。最も適応度の高いＧＡｐの染色体で表現されている局所的パッキング法でパッキングを行い（Ｓ２７），部分配置領域の境界をＧＡｃで噛み合わせて（Ｓ２８），処理を終了する。
【００５１】
〔３〕ＧＡｐ＋（ＧＡｓ＋（ＧＡｃ＋Ｐａｃｋl ））
局所的パッキングの際に使用するパラメータ（配置領域の部分領域への分割法を定めるパラメータなど）をＧＡｐで最適化する。各部分領域に作用させる局所的パッキング法をベースにして全配置を最適にするＧＡｓを使用して，各パラメータの定められた局所的パッキング法Ｐａｃｋl で得られた配置で，配置要素が噛み合わない部分配置領域の境界をＧＡｃで噛み合わせることによって得られる配置を最適化する。これによって得られた配置の適応度が遺伝的アルゴリズムＧＡｐの適応度である。このような組み合わせによって，局所的なパッキング法を最適にするとともに，パッキングの結果得られた配置をも最適化することが可能になる。
【００５２】
図２０に，ＧＡｐ＋（ＧＡｓ＋（ＧＡｃ＋Ｐａｃｋl ））の組み合わせの場合の処理の流れを示す。まず，最初にＧＡｐの初期集団を準備する（Ｓ３１）。その後，ＧＡｐの交叉を行い（Ｓ３２），ＧＡｐの突然変異を行う（Ｓ３３）。次に，ＧＡｓの初期集団を準備し（Ｓ３４），ＧＡｓの交叉を行い（Ｓ３５），ＧＡｓの突然変異を行う（Ｓ３６）。ＧＡｐの染色体で定められた方法でＧＡｓの個体の配置領域を分割し局所的パッキング法を実施し（Ｓ３７），部分配置領域の境界をＧＡｃで噛み合わせて（Ｓ３８），所定の選択ルールに従ってＧＡｓを選択する（Ｓ３９）。ＧＡｓの適応度が所定の基準値以上かどうかを判定し（Ｓ４０），基準値に満たない場合にはステップＳ３５のＧＡｓの交叉処理へ戻り，基準値以上の場合には，ＧＡｓの染色体の適応度の中で最大の適応度を，対応するＧＡｐの染色体の適応度とし（Ｓ４１），ＧＡｐの適応度が所定の基準値以上かどうかを判定する（Ｓ４２）。基準値に満たない場合には，ステップＳ３２へ戻ってＧＡｐの次世代の遺伝子操作を繰り返し，基準値以上の場合には処理を終了する。
【００５３】
〔アイランドモデルによる最適化〕
アイランドモデルによる最適化を説明する。
【００５４】
〔１〕遺伝的アルゴリズムＧＡｓに基づいたアイランドモデル
図２１に，遺伝的アルゴリズムＧＡｓに基づいたアイランドモデルの例を示す。説明を簡単にするために，まず初めは二つの集団を考える。便宜上集団Ａと集団Ｂと呼ぶ。一つの集団に属する各個体の染色体に対応する配置領域の分割方法は同じとする。一方，二つの集団の配置領域の部分領域への分割方法は異なるとする。この二つの集団とは別の集団Ｃを作る。この集団Ｃの個体の染色体に対応する配置領域の分割法は，集団Ａと集団Ｂの個体の染色体に対応する配置領域の分割を含む分割とする。
【００５５】
各々の集団は独立に遺伝的アルゴリズムＧＡｓに基づいて発展している。何世代か経過するごとに，二つの集団Ａと集団Ｂから親となる個体を選択し，交叉を実行し，その結果生まれた子供を集団Ｃに返す。このとき，交叉は親の特徴をよく保存するために，以下のような方法で実行する。
(1) 配置要素の座標から構成されている染色体の領域を，別の親の対応する領域へ貼り合わせる。
(2) 二つの親の選択された染色体の領域の対応している遺伝子の座標について重み付き平均を取り，これを子供の染色体の遺伝子とする。
【００５６】
このような方法は二つの集団だけでなく，任意の数の集団の場合に一般化できる。
【００５７】
〔２〕遺伝的アルゴリズムＧＡｐ＋Ｐａｃｋl に基づいたアイランドモデル
図２２に，遺伝的アルゴリズムＧＡｐ＋Ｐａｃｋl に基づいたアイランドモデルの例を示す。説明の便宜上，三つの集団を考える。集団Ａは配置領域をＮｙ個の部分領域に横に分割した集団で，集団Ｂは配置領域を縦にＮｘ個の部分領域に分割した集団である。そして残りの集団Ｃは配置領域を縦にＮｘ個，横にＮｙ個の部分領域に分割した集団である。これらの帯状の部分領域の幅（ｈi ，ｗi ）を遺伝子として染色体を構成する。ある，一定の世代毎に各集団間の個体を交換する。これは以下のような手順で行う。
【００５８】
集団Ａと集団Ｂから個体を適当な方法で選択して，交叉を実行する。交叉は集団Ａの個体の染色体（ｈ1 ，ｈ2 ，ｈ3 ，…，ｈNy）と集団Ｂの染色体（ｗ1 ，ｗ2 ，ｗ3 ，…，ｗNx）から自然な方法で集団Ｃの染色体（ｈ1 ，ｈ2 ，ｈ3 ，…，ｈNy，ｗ1 ，ｗ2 ，ｗ3 ，…，ｗNx）を作り上げる。この交叉の結果生じた子供を集団Ｃへ入れる。同様にして集団Ｃと集団Ａの個体間の交叉を定義できる。すなわち，集団Ｃと集団Ａの個体の交叉は次のいずれかの方法で実施する。
【００５９】
(a) 集団Ｃの個体の染色体の中で，配置領域を横に分割したときの帯状領域の幅ｈを示すＮｙ個の遺伝子の集合と集団Ａの染色体の交叉を貼り付け交叉等で実施する。これによって得られた横方向への分割の幅ｈを遺伝子とする個体を集団Ａに入れる。また，この遺伝子の集合と集団Ｃの染色体の縦方向へ分割した帯状の部分配置領域の幅ｗを表す遺伝子の集合を合わせて染色体を作り，集団Ｃへ入れる。
【００６０】
(b) 集団Ｃの個体の染色体の中で，配置領域を縦に分割したときの帯状領域の幅ｗを示すＮｘ個の遺伝子の集合と集団Ａの染色体の交叉を貼り付け交叉等で実施する。これによって得られた縦方向への分割の幅ｗを表す遺伝子の集合と集団Ｃの染色体の横方向へ分割した帯状の部分配置領域の幅ｈを表す遺伝子の集合を合わせて集団Ｃの染色体を作り集団Ｃへ入れる。集団Ｃの個体の染色体の中で，配置領域を縦に分割した際の帯状領域の幅ｗを示す遺伝子の集合を，集団Ｂの染色体とみなしてこれを集団Ｂに入れる。
【００６１】
上記二つの方法を合わせて，集団Ａと集団Ｂと集団Ｃに属する染色体を交叉によって作り出し，それぞれを適合する集団に入れる。集団Ｃと集団Ｂの個体の交叉も同様である。
【００６２】
以上の本発明の実施の形態の特徴を列挙すると，以下のとおりである。
【００６３】
（１）既存型アルゴリズムと組み合わされた遺伝的アルゴリズムで島モデルによって最適化問題を解くことを特徴とする。
【００６４】
（２）上記（１）の遺伝的アルゴリズムの島モデルで，既存型アルゴリズムＬｉを持つＮ個の「島ｉ」（ｉ＝１，…，Ｎ）と異なる既存型アルゴリズムのペアＬｉ，Ｌｊを持つ「島（ｉ，ｊ）」（ｉ≠ｊ（ｉ，ｊ＝１，…，Ｎ））から構成されることを特徴とする。
【００６５】
（３）上記（２）の遺伝的アルゴリズムの島モデルの構成において，「島ｉ」と「島ｊ」（ｉ＜ｊ，（ｉ，ｊ＝１，…，Ｎ））の個体を親として生じた子供は「島（ｉ，ｊ）」に入れることを特徴とする。
【００６６】
（４）上記（２）の遺伝的アルゴリズムの島モデルの構成において，「島ｉ」と「島（ｉ，ｋ）」の個体を親として生じた子供は「島ｉ」に入れることを特徴とする。
【００６７】
（５）上記（２）の遺伝的アルゴリズムの島モデルの構成において，「島ｉ」と「島（ｉ，ｋ）」の個体を親として生じた子供は「島（ｉ，ｋ）」に入れることを特徴とする。
【００６８】
（６）上記（２）の遺伝的アルゴリズムの島モデルの構成において，「島ｉ」と「島（ｉ，ｋ）」の個体を親として生じた子供は「島ｉ」または「島（ｉ，ｋ）」に入れることを特徴とする。
【００６９】
（７）上記（１）の遺伝的アルゴリズムの島モデルで，「島」のタワーを構成することで，個体を交換できる「島」を増加させることを特徴とする。
【００７０】
（８）配置問題となる全ての分野の問題で，配置問題の解の配置要素の重なりを遺伝的アルゴリズムと局所的パッキング法を組み合わせる方法を使用することによって解消することを特徴とする。
【００７１】
（９）上記（８）の遺伝的アルゴリズムの染色体のコード法において，局所的パッキング法を指定するパラメータから構成されていることを特徴とする。
【００７２】
（１０）上記（８）の遺伝的アルゴリズムの染色体のコード法において，上記（９）のような構成法を用いる場合に，遺伝子として部分配置領域の幅または高さ指定するパラメータを用いる方法を特徴とする。
【００７３】
（１１）上記（８）の遺伝的アルゴリズムの染色体のコード法において，上記（９）のような構成法を用いる場合に，遺伝子として部分配置領域の局所的パッキング法を指定するパラメータを用いる方法を特徴とする。
【００７４】
（１２）上記（８）の遺伝的アルゴリズムの染色体のコード法において，上記（９）のような構成法を用いる場合に，染色体として上記（１０）と（１１）の遺伝子を組み合わせることを特徴とする。
【００７５】
（１３）上記（８）の遺伝的アルゴリズムに上記（１０）の染色体のコード法を用いる場合に，交叉法として親の染色体から交叉によってできた子供の染色体で各部分領域の幅（高さ）の総和が配置領域の幅（高さ）に一致することを特徴とする。
【００７６】
（１４）上記（８）の遺伝的アルゴリズムに上記（１０）の染色体のコード法を用いる場合に，交叉法として上記（１３）の方法において二つの親の染色体のある領域を考え，この部分を交叉の対象とするとき，子供の染色体の対応する染色体領域の遺伝子の値を二つの親の重み付けられた平均とすることを特徴とする。
【００７７】
（１５）上記（８）の遺伝的アルゴリズムに上記（１０）または（１２）の染色体のコード法を用いる場合において，突然変異として，染色体の遺伝子をランダムに，常に二つの異なる部分領域の幅（高さ）に対応する遺伝子をペアで選択し，これらの二つの遺伝子のうちの一つに対応する部分領域の幅（高さ）に小さなランダムな量を加えたならば，もう一つの遺伝子から同じ量だけ引くことを特徴とする。
【００７８】
（１６）上記（８）の遺伝的アルゴリズムに上記（１１）の染色体のコード法を用いる場合において，突然変異として，染色体の遺伝子をランダムに，選択し，可能な局所的パッキング法を指定しているパラメータから可能な値の集合からランダムに別のパラメータを選択しもとの遺伝子と置き換えることを特徴とする。
【００７９】
（１７）上記（８）の遺伝的アルゴリズムに上記（１０）または（１１）または（１２）の染色体のコード法を用いる場合において，適応度として次のフィットネス関数
［フィットネス］＝定数−［重み１］×［重なっている配置要素の総数］−［重み２］×［元の配置問題のコスト］
を用いることを特徴とする。
【００８０】
（１８）上記（８）の遺伝的アルゴリズムに上記（１０）または（１１）または（１２）の染色体のコード法を用いる場合において，適応度として次のフィットネス関数
［フィットネス］＝定数−［重み１］×［配置要素の重なっている部分の面積の総和］−［重み２］×［元の配置問題のコスト］
を用いることを特徴とする方法。
【００８１】
（１９）上記（８）の遺伝的アルゴリズムと局所的パッキング法の組み合わせ方法において，配置領域の部分配置領域への分割法を一つに固定し，この部分配置領域への分割をもとにして遺伝的アルゴリズムの交叉を実施することを特徴とする。
【００８２】
（２０）上記（１９）の遺伝的アルゴリズムと局所的パッキング法の組み合わせ方法において，遺伝的アルゴリズムの染色体のコード法として，遺伝子が配置要素の座標から構成されていることを特徴とする。
【００８３】
（２１）上記（１９）の遺伝的アルゴリズムと局所的パッキング法の組み合わせ方法において，初期集団の構成方法としてもとになる配置結果から同一の配置結果のコピーを適当な数だけ作り，各コピー毎に各部分配置領域に作用させる局所的パッキング法をあらかじめ決めてある複数の候補の中から選択し，この割り当てはコピー毎に異なるようにし，この局所的パッキング法の割り当てに従って，各配置のコピーをパッキングすることによって得られた配置の集団が遺伝的アルゴリズムの初期集団となることを特徴とする。
【００８４】
（２２）上記（１９）の遺伝的アルゴリズムと局所的パッキング法の組み合わせ方法において，遺伝的アルゴリズムの交叉として，一つの親の選択された部分配置領域に属する配置要素に対応する遺伝子からなる染色体の領域を別の親の対応する部分配置領域に属する配置要素に対応する遺伝子からなる染色体の領域へ貼り付けることで交叉を実施することを特徴とする。
【００８５】
（２３）上記（１９）の遺伝的アルゴリズムと局所的パッキング法の組み合わせ方法において，遺伝的アルゴリズムの交叉として，二つの親の同一の部分配置領域に属する同じ配置要素の座標の重み付けられた平均をとることによって子供の染色体を作り出す交叉を実施することを特徴とする。
【００８６】
（２４）上記（１９）の遺伝的アルゴリズムと局所的パッキング法の組み合わせ方法において，遺伝的アルゴリズムの突然変異として，適当に設定された確率で遺伝子（配置要素の座標）を選択し，遺伝子の座標に正または負のランダムな小さな量を加えることで突然変異を実施することを特徴とする。
【００８７】
（２５）上記（１９）の遺伝的アルゴリズムと局所的パッキング法の組み合わせ方法において，遺伝的アルゴリズムの突然変異として，重なっている配置要素を適当な確率で選択し，この選択された配置要素の座標に正または負のランダムな小さな量を加えることで突然変異を実施することを特徴とする。
【００８８】
（２６）上記（１９）における遺伝的アルゴリズムで使用する適応度として，以下のフィットネス関数で定義され関数を使用することを特徴とする。
【００８９】
［フィットネス］＝定数−［重み１］×［重なっている配置要素の総数］−［重み２］×［元の配置問題のコスト］
（２７）上記（１９）における遺伝的アルゴリズムで使用する適応度として，以下のフィットネス関数で定義され関数を使用することを特徴とする。
【００９０】
［フィットネス］＝定数−［重み１］×［配置要素の重なっている部分の面積の総和］−［重み２］×［元の配置問題のコスト］
（２８）上記（８）の遺伝的アルゴリズムと局所的パッキング法を組み合わせる方法において，局所的パッキングの際に使用するパラメータ（配置領域の部分領域への分割法を定めるパラメータなど）をＧＡｐで最適化し，各パラメータの定められた局所的パッキング法Ｐａｃｋl で得られた配置で配置要素が噛み合わない部分配置領域の境界をＧＡｃで噛み合わせて得られた配置の適応度が遺伝的アルゴリズムＧＡｐの適応度であるとし，この組み合わせによって配置領域の部分領域への分割法を効率良く求めることを特徴とする（ＧＡｐ＋（ＧＡｃ＋Ｐａｃｋl ））。
【００９１】
（２９）上記（８）の遺伝的アルゴリズムと局所的パッキング法を組み合わせる方法において，局所的パッキングの際に使用するパラメータ（配置領域の部分領域への分割法を定めるパラメータなど）をＧＡｐで最適化し，各パラメータの定められた局所的パッキング法Ｐａｃｋl で得られた配置の中でもっとも適応度の高い配置にＧＡｃによって噛み合っていない部分配置領域の境界の配置要素を噛み合わせ，この組み合わせによって配置結果に最も適した局所的パッキング法のパラメータを選択し効率的なパッキングを実行することを特徴とする（ＧＡｃ＋（ＧＡｐ＋Ｐａｃｋl ））。
【００９２】
（３０）上記（８）の遺伝的アルゴリズムと局所的パッキング法を組み合わせる方法において，局所的パッキングの際に使用するパラメータ（配置領域の部分領域への分割法を定めるパラメータなど）をＧＡｐで最適化し，各部分領域に作用させる局所的パッキング法をベースにして全配置を最適にするＧＡｓを使用して，各パラメータの定められた局所的パッキング法Ｐａｃｋl で得られた配置で配置要素が噛み合わない部分配置領域の境界をＧＡｃで噛み合わせることによって得られる配置を最適化し，これによって得られた配置の適応度が遺伝的アルゴリズムＧＡｐの適応度とし，このような組み合わせによって，局所的なパッキング法を最適にするとともに，パッキングの結果得られた配置をも最適化することを特徴とする（ＧＡｐ＋（ＧＡｓ＋（ＧＡｃ＋Ｐａｃｋl ）））。
【００９３】
（３１）上記（８）の遺伝的アルゴリズムと局所的パッキング法を組み合わせる方法において，遺伝的アルゴリズムとしてＧＡｓを使用するシステムにおいて，アイランドモデルを使用することを特徴とする。
【００９４】
（３２）上記（３１）のシステムのアイランドモデルにおいて，異なる集団の個体同士の交叉として貼り付け交叉を実行することを特徴とする。
【００９５】
（３３）上記（３１）のシステムのアイランドモデルにおいて，異なる集団の個体同士の交叉として選択された部分配置領域の対応している遺伝子の重み付き平均をとって，子供の染色体の遺伝子とすることを特徴とする。
【００９６】
（３４）上記（８）の遺伝的アルゴリズムと局所的パッキング法を組み合わせる方法において，遺伝的アルゴリズムとしてＧＡｐを，局所的パッキング法としてＰａｃｋl を使用するシステムにおいて，アイランドモデルを使用することを特徴とする。
【００９７】
（３５）上記（３４）のシステムのアイランドモデルにおいて，集団Ａを配置領域をＮｙ個の部分領域に横に分割した集団とし，集団Ｂを配置領域を縦にＮｘ個の部分領域に分割した集団とし，集団Ｃは配置領域を縦にＮｘ個，横にＮｙ個の部分領域に分割した集団としたとき，これら三つの集団を「島」とすることを特徴とする。
【００９８】
（３６）上記（３５）の三つの集団を「島」とするアイランドモデルにおいて，集団Ａと集団Ｂの個体同士の交叉として，集団Ａの個体の染色体と集団Ｂの染色体から自然な方法で集団Ｃの染色体を作り上げ，この交叉の結果生じた子供を集団Ｃへ入れることを特徴とする。
【００９９】
（３７）上記（３５）の三つの集団を「島」とするアイランドモデルにおいて，集団Ｃと集団Ａの個体同士の交叉として，集団Ｃの個体の染色体の中で配置領域を横に分割したときの帯状領域の幅を示すＮｙ個の遺伝子の集合と集団Ａの染色体の交叉を貼り付け交叉等で実施し，これによって得られた横方向への分割の幅を遺伝子とする個体を集団Ａに入れ，また集団Ａの染色体と集団Ｃの染色体の縦方向へ分割した帯状の部分配置領域の幅を表す遺伝子の集合を合わせて集団Ｃの染色体を作り集団Ｃへ入れることを特徴とする。
【０１００】
（３８）上記（３５）の三つの集団を「島」とするアイランドモデルにおいて，集団Ｃと集団Ｂの個体同士の交叉として，上記（３６），（３７）と同様な方法を使用することを特徴とする。
【０１０１】
【実施例】
〔セル配置問題への応用〕
ＬＳＩの設計の際のセル配置問題を考える。目的関数を総配線長とする。この目的関数を最小にするために非線形計画法を用いてセルの配置を求めることができる。一般には，セルは重なってはならないという制約条件があるが，これを非線形計画法に導入して解を求めるのは原理的には可能である。しかし，セルは大きさを持つためにセル間の重ならないような制約条件が必要となる。これを実用的な規模の問題で制約条件付きの非線形計画法等を効率良く解くことは一般には難しい。このために，図２３に示すように，制約条件のない場合を解き，この後に遺伝的アルゴリズムでセルの重なりを解消すれば効率的に目的とする最適解が得られる。
【０１０２】
〔ＬＳＩのフロアープランへの応用〕
ＬＳＩの配置問題の一種にフロアプランがある。図２４に示すように，配置するセルの面積は定まっているが，セルの各辺の長さが可変である問題をフロアプランという。この問題の場合にも，本発明に係る遺伝的アルゴリズムによるセルの重なりの解消法が使用できる。
【０１０３】
〔スケージュリング問題〕
図２５に示すように，スケジューリング問題におけるガントチャートの作成も，一種の配置問題とみなすことができる。この問題の場合にも，本発明に係る遺伝的アルゴリズムのアイランドモデルによって効率的に解を探索できる。
【０１０４】
【発明の効果】
以上説明したように，本発明によって，例えば遺伝的アルゴリズムと局所的パッキング法を組み合わせるというように，遺伝的アルゴリズムと既存型アルゴリズムとを組み合わせ，これらをアルゴリズムに応じた島モデルに適合させたことにより，適応度の増加を加速できるようになった。
【図面の簡単な説明】
【図１】本発明の基本的な考え方を説明するための図である。
【図２】Ｎ個の島と新しい島の例を示す図である。
【図３】Ｎ＝４の場合の島のタワーの例を示す図である。
【図４】本発明の動作の流れの概要を示す図である。
【図５】煉瓦積み方式のパッキング法の例を示す図である。
【図６】テトリス方式のパッキング法の例を示す図である。
【図７】凝縮方式のパッキング法の例を示す図である。
【図８】拡散方式のパッキング法の例を示す図である。
【図９】ＧＡｐの染色体コード法を説明するための図である。
【図１０】ＧＡｐの交叉を説明するための図である。
【図１１】ＧＡｐの突然変異を説明するための図である。
【図１２】ＧＡｓの染色体コード法を説明するための図である。
【図１３】ＧＡｓの初期集団を説明するための図である。
【図１４】ＧＡｓの交叉を説明するための図である。
【図１５】ＧＡｓの交叉を説明するための図である。
【図１６】ＧＡｓの突然変異を説明するための図である。
【図１７】ＧＡｓの突然変異を説明するための図である。
【図１８】ＧＡｐ＋（ＧＡｃ＋Ｐａｃｋl ）の組み合わせの場合の処理の流れを示す図である。
【図１９】ＧＡｃ＋（ＧＡｐ＋Ｐａｃｋl ）の組み合わせの場合の処理の流れを示す図である。
【図２０】ＧＡｐ＋（ＧＡｓ＋（ＧＡｃ＋Ｐａｃｋl ））の組み合わせの場合の処理の流れを示す図である。
【図２１】ＧＡｓに基づいたアイランドモデルの例を示す図である。
【図２２】ＧＡｐ＋Ｐａｃｋl に基づいたアイランドモデルの例を示す図である。
【図２３】本発明のセル配置問題への適用例を説明するための図である。
【図２４】本発明のＬＳＩのフロアプランニング問題への適用例を説明するための図である。
【図２５】本発明のスケジューリング問題への適用例を説明するための図である。
【図２６】遺伝的アルゴリズムを説明するための図である。
【図２７】選択／自己複製を説明するための図である。
【図２８】交叉を説明するための図である。
【図２９】突然変異を説明するための図である。
【符号の説明】
ＧＡ  遺伝的アルゴリズム
Ｌ1   既存型のアルゴリズム
Ｌ2   既存型のアルゴリズム
【図１】
0004763112.tif 000002
【図２】
0004763112.tif 000003
【図３】
0004763112.tif 000004
【図４】
0004763112.tif 000005
【図５】
0004763112.tif 000006
【図６】
0004763112.tif 000007
【図７】
0004763112.tif 000008
【図８】
0004763112.tif 000009
【図９】
0004763112.tif 000010
【図１０】
0004763112.tif 000011
【図１１】
0004763112.tif 000012
【図１２】
0004763112.tif 000013
【図１３】
0004763112.tif 000014
【図１４】
0004763112.tif 000015
【図１５】
0004763112.tif 000016
【図１６】
0004763112.tif 000017
【図１７】
0004763112.tif 000018
【図１８】
0004763112.tif 000019
【図１９】
0004763112.tif 000020
【図２０】
0004763112.tif 000021
【図２１】
0004763112.tif 000022
【図２２】
0004763112.tif 000023
【図２３】
0004763112.tif 000024
【図２４】
0004763112.tif 000025
【図２５】
0004763112.tif 000026
【図２６】
0004763112.tif 000027
【図２７】
0004763112.tif 000028
【図２８】
0004763112.tif 000029
【図２９】
0004763112.tif 000030