(57)【要約】【課題】２次元以上の空間に複数の要素を最適な状態で配置する要素配置最適化問題において、問題規模の大きい要素配置最適化問題を高速に処理できるようにする。【解決手段】複数の要素の初期配置状態に関する情報がコンピュータに入力されると、遺伝的アルゴリズムをＣＰＵで実行して、初期配置状態にある複数の要素の疎密を解消する第１アルゴリズム実行ステップと、第１アルゴリズム実行ステップにて疎密が解消された後の複数の要素の中間配置状態に関する情報がコンピュータに入力されると、局所的疎密解消アルゴリズムをＣＰＵで実行して、中間配置状態にある複数の要素の疎密を更に解消する第２アルゴリズム実行ステップとを実行することにより、接続関係を維持しながら初期配置状態にある複数の要素の疎密を解消する。【選択図】図１
2007052799.tif 000002
【特許請求の範囲】
【請求項１】
接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、
上記複数の要素の初期配置状態に関する情報が該コンピュータに入力されると、遺伝的アルゴリズムを該ＣＰＵで実行して、該初期配置状態にある上記複数の要素の疎密を解消する第１アルゴリズム実行ステップと、
該第１アルゴリズム実行ステップにて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が該コンピュータに入力されると、局所的疎密解消アルゴリズムを該ＣＰＵで実行して、該中間配置状態にある上記複数の要素の疎密を更に解消する第２アルゴリズム実行ステップとを実行することにより、
該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消することを特徴とする、回路配置最適化問題処理方法。
【請求項２】
該第１アルゴリズム実行ステップが、上記複数の要素の配置状態を遺伝子として表現し、該空間に上記複数の要素を配置する問題の解候補として、当該遺伝子の配列からなり該空間として定義される染色体を用いることにより、該遺伝的アルゴリズムを実行することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項３】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に分割することにより該染色体を複数の領域に分割し、該染色体における上記複数の領域の中から選択された少なくとも一つの領域を、他の染色体における当該領域に対応する領域と交換することにより、遺伝オペレーションとしての交叉を実行することを特徴とする、請求項２記載の回路配置最適化問題処理方法。
【請求項４】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に分割することにより該染色体を複数の領域に分割し、該染色体における上記複数の領域の中の特定の領域の方が、他の染色体における当該領域に対応する領域よりも疎密が解消されている場合には、該染色体における当該領域を該他の染色体における当該領域に対応する領域に張り付けることにより、遺伝オペレーションとしての交叉を実行することを特徴とする、請求項２記載の回路配置最適化問題処理方法。
【請求項５】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に分割することにより該染色体を複数の領域に分割し、上記複数の領域の中の少なくとも一つの領域内において上記複数の要素のうちの少なくとも一つの要素を移動させることにより、遺伝オペレーションとしての突然変異を実行することを特徴とする、請求項２記載の回路配置最適化問題処理方法。
【請求項６】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、上記複数の要素の疎密が小さい染色体が大きな適応度値をとりうるような適応度値関数を用いて、遺伝オペレーションとしての選択を実行することを特徴とする、請求項２記載の回路配置最適化問題処理方法。
【請求項７】
上記複数の要素を配置する空間を複数の部分空間に分割したときに、該第２アルゴリズム実行ステップが、上記部分空間毎に上記複数の要素の疎密を解消することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項８】
該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムとして、流体力学のアナロジーが適用されたアルゴリズムを用いることを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項９】
該第２アルゴリズム実行ステップが、該中間配置状態にある上記複数の要素のうちの少なくとも一つの要素を、要素密度が高い場所から要素密度が低い場所へと移動させることにより、該流体力学のアナロジーが適用されたアルゴリズムを実行することを特徴とする、請求項８記載の回路配置最適化問題処理方法。
【請求項１０】
上記複数の要素を配置する該空間を複数の部分空間に分割したときに、該第２アルゴリズム実行ステップが、上記分割した部分空間内において、当該部分空間内に含まれる上記複数の要素のうちの少なくとも一つの要素を、要素密度が高い場所から要素密度が低い場所へと移動させることを特徴とする、請求項９記載の回路配置最適化問題処理方法。
【請求項１１】
該第２アルゴリズム実行ステップが、上記複数の要素間の近傍性を保存しながら、上記複数の要素のうちの少なくとも一つの要素を移動させることを特徴とする、請求項９記載の回路配置最適化問題処理方法。
【請求項１２】
該第２アルゴリズム実行ステップが、上記複数の要素間の順序性を保存しながら、上記複数の要素のうちの少なくとも一つの要素を移動させることを特徴とする、請求項９記載の回路配置最適化問題処理方法。
【請求項１３】
該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムとして、モーフィングのアナロジーが適用されたアルゴリズムを用いることを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項１４】
該第２アルゴリズム実行ステップが、該中間配置状態にある上記複数の要素に関する情報に基づいてモーフィング中心部を決定し、上記複数の要素のうちの少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させることにより、該モーフィングのアナロジーが適用されたアルゴリズムを実行することを特徴とする、請求項１３記載の回路配置最適化問題処理方法。
【請求項１５】
上記複数の要素を配置する該空間を複数の部分空間に分割したときに、該第２アルゴリズム実行ステップが、上記部分空間毎に該モーフィング中心部を決定し、上記部分空間内において、当該部分空間内に含まれる上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させることを特徴とする、請求項１４記載の回路配置最適化問題処理方法。
【請求項１６】
該第２アルゴリズム実行ステップが、上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させる際に、該モーフィング中心部から移動対象となる要素までの距離を線形的に拡大することを特徴とする、請求項１４記載の回路配置最適化問題処理方法。
【請求項１７】
該第２アルゴリズム実行ステップが、上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させる際に、該モーフィング中心部から移動対象となる要素までの距離を非線形的に拡大することを特徴とする、請求項１４記載の回路配置最適化問題処理方法。
【請求項１８】
該第２アルゴリズム実行ステップが、該中間配置状態にある上記複数の要素の疎密を解消する際に、疎密解消対象となる要素を逐次添加していくことを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項１９】
上記複数の要素の中に移動させることができない固定要素がある場合には、該第２アルゴリズム実行ステップが、該固定要素も疎密解消対象となる要素とみなして、該中間配置状態にある上記複数の要素の疎密を解消することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項２０】
上記複数の要素の中に他の要素に比べて該空間を占める割合が大きな要素がある場合には、該第２アルゴリズム実行ステップが、該大きな要素の移動量を小さくして、該中間配置状態にある上記複数の要素の疎密を解消することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項２１】
該第２アルゴリズム実行ステップが、該中間配置状態にある上記複数の要素の疎密を解消する際に、移動対象となる要素を一挙に移動させることを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項２２】
該第２アルゴリズム実行ステップが、該中間配置状態にある上記複数の要素の疎密を解消する際に、移動対象となる要素を徐々に移動させることを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項２３】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に縦方向に分割することにより複数の領域に縦方向に分割された該染色体の集団を少なくとも一つ有する第１アイランドと、上記複数の要素を配置する該空間を複数の部分空間に横方向に分割することにより複数の領域に横方向に分割された該染色体の集団を少なくとも一つ有する第２アイランドとを用いることを特徴とする、請求項２記載の回路配置最適化問題処理方法。
【請求項２４】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、該第１アイランドに属する該染色体及び該第２アイランドに属する該染色体にそれぞれ局所的疎密解消アルゴリズムを適用することにより上記各領域内である特定の要素を移動させ、該第１アイランドに属する該染色体及び該第２アイランドに属する該染色体における当該特定の要素の移動量のベクトル和に応じて上記各染色体内で当該特定の要素を移動させることにより、該第１アイランドに属する該染色体と該第２アイランドに属する該染色体との間で、遺伝オペレーションとしての交叉を実行することを特徴とする、請求項２３記載の回路配置最適化問題処理方法。
【請求項２５】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、該第１アイランド又は該第２アイランドに属する該染色体における特定の要素を含む領域を抽出し、抽出した該領域を該第２アイランド又は該第１アイランドに属する該染色体における該領域に読み替えて該第２アイランド又は該第１アイランドに戻すことにより、該第１アイランドに属する該染色体と該第２アイランドに属する該染色体との間で、遺伝オペレーションとしての交叉を実行することを特徴とする、請求項２３記載の回路配置最適化問題処理方法。
【請求項２６】
接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、
遺伝的アルゴリズムを該ＣＰＵで実行する第１アルゴリズム実行ステップと、
局所的疎密解消アルゴリズムを該ＣＰＵで実行する第２アルゴリズム実行ステップとをそなえることにより、
該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消することを特徴とする、回路配置最適化問題処理方法。
【請求項２７】
該第１アルゴリズム実行ステップが、上記複数の要素の配置状態を遺伝子として表現し、該空間に上記複数の要素を配置する問題の解候補として、当該遺伝子の配列からなり該空間として定義される染色体を用いることにより、該遺伝的アルゴリズムを実行している中で、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行することを特徴とする、請求項２６記載の回路配置最適化問題処理方法。
【請求項２８】
該第１アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行する際に用いるパラメータを遺伝子として表現し、該パラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いることにより、該遺伝的アルゴリズムを実行している中で、更に、該第１アルゴリズム実行ステップが、上記複数の要素の配置状態を遺伝子として表現し、該空間に上記複数の要素を配置する問題の解候補として、当該遺伝子の配列からなり該空間として定義される染色体を用いた遺伝的アルゴリズムを実行するとともに、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行することを特徴とする、請求項２６記載の回路配置最適化問題処理方法。
【請求項２９】
該第１アルゴリズム実行ステップが、上記複数の要素の配置状態を遺伝子として表現し、該空間に上記複数の要素を配置する問題の解候補として、当該遺伝子の配列からなり該空間として定義される染色体を用いることにより、該遺伝的アルゴリズムを実行している中で、更に、該第１アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行する際に用いるパラメータを遺伝子として表現し、該パラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いた遺伝的アルゴリズムを実行するとともに、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行することを特徴とする、請求項２６記載の回路配置最適化問題処理方法。
【請求項３０】
接続関係が規定された複数の要素を所要の空間に配置するに際し、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題をコンピュータにより処理するための回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
該回路配置最適化問題処理プログラムが、
上記複数の要素の初期配置状態に関する情報が入力されると、遺伝的アルゴリズムを実行して、該初期配置状態にある上記複数の要素の疎密を解消する第１アルゴリズム実行手段、及び、
該第１アルゴリズム実行手段にて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が入力されると、局所的疎密解消アルゴリズムを実行して、該中間配置状態にある上記複数の要素の疎密を更に解消する第２アルゴリズム実行手段として該コンピュータを機能させることを特徴とする、回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項３１】
接続関係が規定された複数の要素を所要の空間に最適な状態で配置する回路配置最適化問題をコンピュータにより処理するための回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
該回路配置最適化問題処理プログラムが、
遺伝的アルゴリズムを実行する第１アルゴリズム実行手段、及び、
局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行手段として該コンピュータを機能させることを特徴とする、回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば大規模集積回路（ＬＳＩ；large scale integration)上の各回路を最適な状態で配置する回路配置最適化問題、より一般的には、２次元以上の空間に複数の要素（配置要素）を最適な状態で配置する要素配置最適化問題を処理する際に用いて好適な、回路配置最適化問題処理方法及び回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
要素配置最適化問題は、具体的には、接続関係が規定された複数の要素を所要の空間（要素が２次元のものである場合には、所要の領域）に最適な状態で配置する問題であり、グラフマッピング問題と言われるものである。
例えば、前述したＬＳＩにおいて、ＬＳＩ上の各回路の最適配置を求めることができれば、ＬＳＩの小型化を図ることができるほか、当該各回路を接続する配線の長さを最小化して配線性を向上させることができるので、ＬＳＩにおける処理の高速化を図ることもできる。
【０００３】
要素配置最適化問題は、最適化問題解決アルゴリズム（例えば遺伝的アルゴリズム，ミンカット法，ｎ要素交換法等）を実行して、複数の要素の上記空間における最適配置を決定し、その決定に基づいて複数の要素を上記空間に配置することにより処理することができる。
ここで、要素配置最適化問題の規模が大きいとき（即ち、最適配置を求めるべき要素数が非常に多いとき）には、最適化問題解決アルゴリズムを高速に実行できるようにするために、各要素の大きさを考慮することなく、各要素を点（又は同一形状）とみなして要素の最適配置を決定していた。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、要素はそれぞれ固有の大きさをもっているため、このようにして決定された最適配置に基づいて要素を配置しても、要素同士が重なったり要素間に隙間が生じたりして、要素の配置に疎密が生じることがあるという課題がある。
従って、問題規模の大きい要素配置最適化問題を高速に処理するためには、各要素の大きさを考慮しないで最適化問題解決アルゴリズムを実行し、その結果生じた要素の配置の疎密を解消する必要がある。
【０００５】
本発明は、このような課題に鑑み創案されたもので、要素の配置に生じた疎密を解消して要素を上記空間に均一に配置できるようにして、問題規模の大きい要素配置最適化問題を高速に処理できるようにした、回路配置最適化問題処理方法を提供することを目的とするとともに、更には、要素配置最適化問題を処理すべくコンピュータを動作させるための回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００６】
このため、本発明の回路配置最適化問題処理方法は、接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、上記複数の要素の初期配置状態に関する情報が該コンピュータに入力されると、遺伝的アルゴリズムを該ＣＰＵで実行して、該初期配置状態にある上記複数の要素の疎密を解消する第１アルゴリズム実行ステップと、該第１アルゴリズム実行ステップにて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が該コンピュータに入力されると、局所的疎密解消アルゴリズムを該ＣＰＵで実行して、該中間配置状態にある上記複数の要素の疎密を更に解消する第２アルゴリズム実行ステップとを実行することにより、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消することを特徴としている（請求項１）。
【０００７】
ここで、該第１アルゴリズム実行ステップは、上記複数の要素の配置状態を遺伝子として表現し、該空間に上記複数の要素を配置する問題の解候補として、当該遺伝子の配列からなり該空間として定義される染色体を用いることにより、該遺伝的アルゴリズムを実行することができる（請求項２）。
このとき、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に分割することにより該染色体を複数の領域に分割し、該染色体における上記複数の領域の中から選択された少なくとも一つの領域を、他の染色体における当該領域に対応する領域と交換することにより、遺伝オペレーションとしての交叉を実行することができる（請求項３）。
【０００８】
また、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に分割することにより該染色体を複数の領域に分割し、該染色体における上記複数の領域の中の特定の領域の方が、他の染色体における当該領域に対応する領域よりも疎密が解消されている場合には、該染色体における当該領域を該他の染色体における当該領域に対応する領域に張り付けることにより、遺伝オペレーションとしての交叉を実行してもよい（請求項４）。
【０００９】
さらに、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に分割することにより該染色体を複数の領域に分割し、上記複数の領域の中の少なくとも一つの領域内において上記複数の要素のうちの少なくとも一つの要素を移動させることにより、遺伝オペレーションとしての突然変異を実行することができる（請求項５）。
【００１０】
また、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、上記複数の要素の疎密が小さい染色体が大きな適応度値をとりうるような適応度値関数を用いて、遺伝オペレーションとしての選択を実行することができる（請求項６）。
そして、本発明の回路配置最適化問題処理方法においては、上記複数の要素を配置する空間を複数の部分空間に分割したときに、該第２アルゴリズム実行ステップが、上記部分空間毎に上記複数の要素の疎密を解消することを特徴としている（請求項７）。
【００１１】
ここで、該第２アルゴリズム実行ステップは、該局所的疎密解消アルゴリズムとして、流体力学のアナロジーが適用されたアルゴリズムを用いることができる（請求項８）。
具体的には、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素のうちの少なくとも一つの要素を、要素密度が高い場所から要素密度が低い場所へと移動させることにより、該流体力学のアナロジーが適用されたアルゴリズムを実行することができる（請求項９）。
【００１２】
このとき、上記複数の要素を配置する該空間を複数の部分空間に分割したときに、該第２アルゴリズム実行ステップは、上記分割した部分空間内において、当該部分空間内に含まれる上記複数の要素のうちの少なくとも一つの要素を、要素密度が高い場所から要素密度が低い場所へと移動させることを特徴としている（請求項１０）。
ここで、該第２アルゴリズム実行ステップは、上記複数の要素間の近傍性を保存しながら、上記複数の要素のうちの少なくとも一つの要素を移動させることができる（請求項１１）。
【００１３】
また、該第２アルゴリズム実行ステップは、上記複数の要素間の順序性を保存しながら、上記複数の要素のうちの少なくとも一つの要素を移動させることをもできる（請求項１２）。
さらに、該第２アルゴリズム実行ステップは、該局所的疎密解消アルゴリズムとして、モーフィングのアナロジーが適用されたアルゴリズムを用いることもできる（請求項１３）。
【００１４】
具体的には、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素に関する情報に基づいてモーフィング中心部を決定し、上記複数の要素のうちの少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させることにより、該モーフィングのアナロジーが適用されたアルゴリズムを実行することができる（請求項１４）。
【００１５】
このとき、上記複数の要素を配置する該空間を複数の部分空間に分割したときに、該第２アルゴリズム実行ステップは、上記部分空間毎に該モーフィング中心部を決定し、上記部分空間内において、当該部分空間内に含まれる上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させることを特徴としている（請求項１５）。
【００１６】
ここで、該第２アルゴリズム実行ステップは、上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させる際に、該モーフィング中心部から移動対象となる要素までの距離を線形的に拡大することができる（請求項１６）。
また、該第２アルゴリズム実行ステップは、上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させる際に、該モーフィング中心部から移動対象となる要素までの距離を非線形的に拡大することもできる（請求項１７）。
【００１７】
さらに、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素の疎密を解消する際に、疎密解消対象となる要素を逐次添加していくこともできる（請求項１８）。
また、上記複数の要素の中に移動させることができない固定要素がある場合には、該第２アルゴリズム実行ステップは、該固定要素も疎密解消対象となる要素とみなして、該中間配置状態にある上記複数の要素の疎密を解消すればよい（請求項１９）。
【００１８】
さらに、上記複数の要素の中に他の要素に比べて該空間を占める割合が大きな要素がある場合には、該第２アルゴリズム実行ステップは、該大きな要素の移動量を小さくして、該中間配置状態にある上記複数の要素の疎密を解消すればよい（請求項２０）。
また、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素の疎密を解消する際に、移動対象となる要素を一挙に移動させることができる（請求項２１）。
【００１９】
さらに、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素の疎密を解消する際に、移動対象となる要素を徐々に移動させることができる（請求項２２）。
その他、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に縦方向に分割することにより複数の領域に縦方向に分割された該染色体の集団を少なくとも一つ有する第１アイランドと、上記複数の要素を配置する該空間を複数の部分空間に横方向に分割することにより複数の領域に横方向に分割された該染色体の集団を少なくとも一つ有する第２アイランドとを用いてもよい（請求項２３）。
【００２０】
このときは、該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、該第１アイランドに属する該染色体及び該第２アイランドに属する該染色体にそれぞれ局所的疎密解消アルゴリズムを適用することにより上記各領域内である特定の要素を移動させ、該第１アイランドに属する該染色体及び該第２アイランドに属する該染色体における当該特定の要素の移動量のベクトル和に応じて上記各染色体内で当該特定の要素を移動させることにより、該第１アイランドに属する該染色体と該第２アイランドに属する該染色体との間で、遺伝オペレーションとしての交叉を実行すればよい（請求項２４）。
【００２１】
また、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、該第１アイランド又は該第２アイランドに属する該染色体における特定の要素を含む領域を抽出し、抽出した該領域を該第２アイランド又は該第１アイランドに属する該染色体における該領域に読み替えて該第２アイランド又は該第１アイランドに戻すことにより、該第１アイランドに属する該染色体と該第２アイランドに属する該染色体との間で、遺伝オペレーションとしての交叉を実行してもよい（請求項２５）。
【００２２】
つまり、本発明の回路配置最適化問題処理方法は、接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、遺伝的アルゴリズムを該ＣＰＵで実行する第１アルゴリズム実行ステップと、局所的疎密解消アルゴリズムを該ＣＰＵで実行する第２アルゴリズム実行ステップとをそなえることにより、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消することを特徴としている（請求項２６）。
【００２３】
より具体的には、該第１アルゴリズム実行ステップが、上記複数の要素の配置状態を遺伝子として表現し、該空間に上記複数の要素を配置する問題の解候補として、当該遺伝子の配列からなり該空間として定義される染色体を用いることにより、該遺伝的アルゴリズムを実行している中で、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行するようになっている（請求項２７）。
【００２４】
さらに、該第１アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行する際に用いるパラメータを遺伝子として表現し、該パラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いることにより、該遺伝的アルゴリズムを実行している中で、更に、該第１アルゴリズム実行ステップが、上記複数の要素の配置状態を遺伝子として表現し、該空間に上記複数の要素を配置する問題の解候補として、当該遺伝子の配列からなり該空間として定義される染色体を用いた遺伝的アルゴリズムを実行するとともに、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行するようにしてもよい（請求項２８）。
【００２５】
また、該第１アルゴリズム実行ステップが、上記複数の要素の配置状態を遺伝子として表現し、該空間に上記複数の要素を配置する問題の解候補として、当該遺伝子の配列からなり該空間として定義される染色体を用いることにより、該遺伝的アルゴリズムを実行している中で、更に、該第１アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行する際に用いるパラメータを遺伝子として表現し、該パラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いた遺伝的アルゴリズムを実行するとともに、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行するようにしてもよい（請求項２９）。
【００２６】
ところで、本発明の回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、接続関係が規定された複数の要素を所要の空間に配置するに際し、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題をコンピュータにより処理するための回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、該回路配置最適化問題処理プログラムが、上記複数の要素の初期配置状態に関する情報が入力されると、遺伝的アルゴリズムを実行して、該初期配置状態にある上記複数の要素の疎密を解消する第１アルゴリズム実行手段、及び、該第１アルゴリズム実行手段にて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が入力されると、局所的疎密解消アルゴリズムを実行して、該中間配置状態にある上記複数の要素の疎密を更に解消する第２アルゴリズム実行手段として該コンピュータを機能させることを特徴としている（請求項３０）。
【００２７】
さらに、本発明の回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、接続関係が規定された複数の要素を所要の空間に最適な状態で配置する回路配置最適化問題をコンピュータにより処理するための回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、該回路配置最適化問題処理プログラムが、遺伝的アルゴリズムを実行する第１アルゴリズム実行手段、及び、局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行手段として該コンピュータを機能させることを特徴としている（請求項３１）。
【発明の効果】
【００２８】
以上詳述したように、本発明によれば、接続関係が規定された複数の要素を所要の空間に配置するに際し、遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえることにより、問題規模の大きい要素配置最適化問題を処理する場合にも、高速に要素の疎密の解消を行なうことができる利点がある（請求項１〜１０，１３〜１５，２６〜３１）。
【００２９】
また、本発明の回路配置最適化問題処理方法によれば、第２アルゴリズム実行ステップが、複数の要素間の近傍性を保存しながら要素を移動させたり、複数の要素間の順序性を保存しながら要素を移動させたりできるので、処理できる回路配置最適化問題の範囲を拡大することができる（請求項１１，１２）。
さらに、第２アルゴリズム実行ステップが、モーフィング中心部から移動対象となる要素までの距離を線形的に拡大したり、モーフィング中心部から移動対象となる要素までの距離を非線形的に拡大したりできるので、これによっても処理できる配置最適化問題の範囲を拡大することができる（請求項１６，１７）。
【００３０】
また、第２アルゴリズム実行ステップが、疎密解消対象となる要素を逐次添加したり、固定配置要素も疎密解消対象となる要素とみなしたり、大きな要素の移動量を小さくしたり、移動対象となる要素を一挙に移動させたり、移動対象となる要素を徐々に移動させたりできるので、更に処理できる配置最適化問題の範囲を拡大することができる（請求項１８〜２２）。
【００３１】
さらに、第１アルゴリズム実行ステップが、遺伝的アルゴリズムを実行する際に、縦方向に分割された染色体の集団を有する第１アイランドと、横方向に分割された染色体の集団を有する第２アイランドとを用いることもできるので、集団における解候補となる染色体の多様性を保持することができ、最適解を効率的に探索して、要素の疎密の解消をより効率的に行なうことができる（請求項２３〜２５）。
【発明を実施するための最良の形態】
【００３２】
以下、図面を参照して本発明の実施の形態を説明する。
（ａ）配置最適化問題処理装置の構成の説明
図１は配置最適化問題処理装置（回路配置最適化問題処理装置；以下、配置最適化問題処理装置という）の構成を示すブロック図であり、この図１に示す配置最適化問題処理装置１は、本発明の配置最適化問題処理方法（回路配置最適化問題処理方法；以下、配置最適化問題処理方法という）を実行するためのものである。
ここで、図１において、５Ａは各種の設定画面や処理にて得られた要素の最適配置結果等を表示する表示部、５はこの表示部５Ａ上における表示状態を制御する表示制御部、７Ｂは表示部５Ａ上の表示データを参照しオペレータがその表示データに対する応答情報を入力するキーボードやマウス等の入力部、７Ｄは入力部７Ｂを制御する入力制御部である。
【００３３】
また、８はディスク装置で、このディスク装置８は、配置最適化問題処理装置１を動作させるために必要となる一切の情報（ＯＳ等）を記憶するものであるとともに、後述する配置最適化問題処理プログラムを記憶するものである。
なお、６は外部ファイル読出書込部，６Ａは外部ファイル，７Ａは印字部，７Ｃは印字制御部であり、外部ファイル読出書込部６及び印字部７Ａは、それぞれ、入力部７Ｂからの指示に応じて、表示部５Ａに表示された複数ノードの最適配置等を、外部ファイル６Ａ又は所定の用紙に記録するものである。
【００３４】
そして、４は配置最適化問題処理装置１を構成する各部を統括的に管理するためのＣＰＵである。
また、このＣＰＵ４は、接続関係が規定された複数の要素を所要の空間に配置するに際し、第１アルゴリズム実行手段及び第２アルゴリズム実行手段として機能するものである。
【００３５】
ここで、第１アルゴリズム実行手段は、後述する遺伝的アルゴリズムを実行するものであり、第２アルゴリズム実行手段は、後述する局所的疎密解消アルゴリズムを実行するものである。
より具体的には、第１アルゴリズム実行手段は、上記複数の要素の初期配置状態に関する情報が入力されると、遺伝的アルゴリズムを実行して、初期配置状態にある上記複数の要素の疎密を解消するものである。
【００３６】
また、第２アルゴリズム実行手段は、上記第１アルゴリズム実行手段にて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が入力されると、局所的疎密解消アルゴリズムを実行して、中間配置状態にある上記複数の要素の疎密を更に解消するものである。
その他、第１アルゴリズム実行手段と第２アルゴリズム実行手段とを組み合わせて実行して、局所的疎密解消アルゴリズムを実行する際に用いるパラメータの最適値を求めた後に、当該パラメータの最適値を用いて第２アルゴリズム実行手段を実行して、初期配置状態にある上記複数の要素の疎密を解消するようにすることもできる。
【００３７】
そして、実際には、上記第１アルゴリズム実行手段及び第２アルゴリズム実行手段に相当する機能は、前述したディスク装置８やＣＤ−ＲＯＭ（図示せず）等の記録媒体に記録されたプログラム（回路配置最適化問題処理プログラム；以下、配置最適化問題処理プログラムという）を図示しないメモリ（ＲＡＭ）に読み出し、そのプログラムを起動してＣＰＵ４で実行することにより、ＣＰＵ４の動作として実現される。
【００３８】
ここで、配置最適化問題処理プログラムは、接続関係が規定された複数の要素を所要の空間に最適な状態で配置する配置最適化問題をコンピュータにより処理するためのものであり、上記第１アルゴリズム実行手段及び第２アルゴリズム実行手段としてコンピュータを機能させるものである。
なお、この配置最適化問題処理プログラムは、例えばＣＤ−ＲＯＭ等に記録されており、ＣＤ−ＲＯＭ等からコンピュータにおけるディスク装置８にインストールされて使用される。
【００３９】
即ち、上述したディスク装置８やＣＤ−ＲＯＭ等が、配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体に相当する。
このように、本実施形態にかかる配置最適化問題処理装置１は、上述したＣＰＵ４，表示部５Ａ，表示制御部５，外部ファイル読出書込部６，印字部７Ａ，印字制御部７Ｃ，入力部７Ｂ，入力制御部７Ｄ，ディスク装置８等を有する一般的な計算機システム（コンピュータ）を用いて実現することが可能である。
【００４０】
そして、配置最適化問題処理装置１においては、以下に説明するようにして、上記複数の配置要素９を配置領域１０に最適な状態で配置する配置最適化問題が処理される。
（ｂ）本発明の配置最適化問題処理方法の説明
（ｂ１）基本的な考え方
まず、本発明の配置最適化問題処理方法の基本的な考え方について、図２〜図５を用いて説明する。なお、図４，図５において、符号９は要素（以下、配置要素という）を示し、図３〜図５において、符号１０は配置要素９を配置するための空間（以下、配置領域という）を示している。
【００４１】
本発明の配置最適化問題処理方法によれば、接続関係が規定された複数の配置要素９を所要の配置領域１０に配置するに際し、まず、配置最適化問題処理装置１に、上記複数の配置要素９の初期配置結果（初期配置状態に関する情報）が入力される（図２のステップＳ１）。ここで、配置要素９はそれぞれ固有の大きさをもつので、一般には、配置要素９が配置領域１０に不均一に配置されて疎密が生じた状態の初期配置結果が入力される。
【００４２】
この配置要素９の初期配置結果が入力されると、配置最適化問題処理装置１では、配置要素９の疎密が解消される（図２のステップＳ２）。
ここで、このステップＳ２では、遺伝的アルゴリズムが実行されるとともに（図２のステップＳ３；第１アルゴリズム実行ステップ）、局所的疎密解消アルゴリズムが実行される（図２のステップＳ４；第２アルゴリズム実行ステップ）。
【００４３】
具体的には、ステップＳ３では、遺伝的アルゴリズムとして、遺伝的アルゴリズム（ＧＡｃ）又は遺伝的アルゴリズム（ＧＡｐ）が実行され、ステップＳ４では、局所的疎密解消アルゴリズムとして、流体力学のアナロジーが適用されたアルゴリズム、又は、モーフィングのアナロジーが適用されたアルゴリズムが実行される。なお、ＧＡは、Genetic Algorithm の略である。
【００４４】
なお、これらのアルゴリズムの詳細については、後述する。
また、ステップＳ３にて遺伝的アルゴリズム（ＧＡｐ）を実行する場合については、「（ｂ４）第２実施形態の説明」にて説明する。
ここで、遺伝的アルゴリズム（ＧＡｃ）を実行する際（ステップＳ３）には、まず、ステップＳ１において入力された配置要素９の初期配置結果を複製して、親の染色体とするための初期配置結果を複数作成する。続いて、配置領域１０を、図３（ｂ），図３（ａ）に示すように、縦方向又は横方向に適当な幅で分割して部分領域１０ａを形成する。そして、部分領域１０ａ単位で遺伝的アルゴリズム（ＧＡｃ）の交叉を行なうように定義して、遺伝的アルゴリズム（ＧＡｃ）を実行することにより、初期配置状態にある配置要素９の疎密を解消する。
【００４５】
例えば配置領域１０を縦方向に分割した場合に、ステップＳ３にて疎密を解消した中間配置状態にある配置要素９の一例を図４（ａ）に示す。この図４（ａ）に示す例では、遺伝的アルゴリズム（ＧＡｃ）を実行しただけでは、配置要素９の疎密は完全には解消されていない。なお、図４（ｂ）は、図４（ａ）に示す中間配置状態にある配置要素９の密度を示している。
【００４６】
そこで、配置最適化問題処理装置１では、ステップＳ３にて疎密が解消された後の配置要素９の中間配置結果（中間配置状態に関する情報）が入力されると、局所的疎密解消アルゴリズムを実行して、中間配置状態にある配置要素９の疎密が更に解消される（ステップＳ４）。
ステップＳ４では、局所的疎密解消アルゴリズムを実行して、ステップＳ３にて分割された配置領域１０の部分領域１０ａ内で、配置要素９を配置要素密度が高い場所から低い場所へ移動させることにより、中間配置状態にある配置要素９の疎密を解消する。以下では、局所的疎密解消アルゴリズムを実行して配置要素９の疎密を解消する方法を、局所的疎密解消法（ＬＯ）という。
【００４７】
なお、図４（ａ）に示す中間配置状態にある配置要素９の疎密を解消した結果を図５（ａ）に示す。また、図５（ｂ）に、図５（ａ）に示す配置状態にある配置要素９の密度を示す。
さらに、配置最適化問題処理装置１では、ステップＳ２により配置要素９の疎密が解消されたか（ステップＳ４にて得られた配置結果が所定の疎密解消の条件を満たしているか）が判断され（ステップＳ５）、配置要素９の疎密が解消されたと判断された場合には処理を終了する（ステップＳ５のＹＥＳルート）。
【００４８】
一方、配置要素９の疎密が解消されていないと判断された場合には、遺伝的アルゴリズムのパラメータと局所的疎密解消アルゴリズムのパラメータの変更を行なった後に（ステップＳ５のＮＯルートからステップＳ６）、前述したステップＳ２以降の動作を繰り返す。
このように、本発明の配置最適化問題処理方法によれば、接続関係が規定された複数の配置要素９を所要の配置領域１０に配置するに際し、遺伝的アルゴリズム（ＧＡｃ）を実行して初期配置状態にある配置要素９の疎密を解消した後に、局所的疎密解消アルゴリズムを実行して中間配置状態にある配置要素９の疎密を更に解消しているので、問題規模の大きい要素配置最適化問題を処理する場合にも、高速に配置要素９の疎密の解消を行なうことができる。
【００４９】
即ち、本発明の配置最適化問題処理方法によれば、遺伝的アルゴリズム（ＧＡｃ）による疎密解消法を用いているので、遺伝的アルゴリズム（ＧＡｃ）の大域的探索法により効率的に配置要素９の疎密の解消を行なうことができるほか、適応度の増大に寄与して配置最適化問題処理装置１の計算速度を増加させることができるため、配置最適化問題を高速に処理することができる。
【００５０】
このとき、局所的疎密解消アルゴリズムを実行して局所的疎密解消法（ＬＯ）を実行しているので、疎密の解消を見通し良く且つ効果的に実施することができる。
このように、本発明の配置最適化問題処理方法は、接続関係が規定された複数の配置要素９を所要の空間に配置するに際し、遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえることにより、初期配置状態にある上記複数の配置要素９の疎密を解消して、上記複数の配置要素９を配置領域１０に最適な状態で配置する配置最適化問題を処理しているのであるが、第１アルゴリズム実行ステップと第２アルゴリズム実行ステップとを組み合わせた各実施形態について、以下にて詳細に説明する。
【００５１】
（ｂ２）第１実施形態の説明
本発明の第１実施形態にかかる配置最適化問題処理方法について説明する。
第１実施形態にかかる配置最適化問題処理方法は、上記第１アルゴリズム実行ステップ（図２のステップＳ３）において、遺伝的アルゴリズム（ＧＡｃ）を実行し、第２アルゴリズム実行ステップ（図２のステップＳ４）において、局所的疎密解消アルゴリズムとして流体力学のアナロジーが適用されたアルゴリズムを実行するものである。
【００５２】
ここで、第１実施形態にて実行される遺伝的アルゴリズム（ＧＡｃ）は、配置要素９の配置結果を染色体とみなして、配置要素９の疎密を直接解消するための遺伝的アルゴリズムである。
即ち、第１実施形態にかかる配置最適化問題処理方法は、各染色体（即ち、配置要素９の配置結果）に遺伝的アルゴリズム（ＧＡｃ）を適用した後に、この遺伝的アルゴリズムとは異なる制御パラメータ（即ち異なる配置要素９の移動方法）をもつ局所的疎密解消法（ＬＯ）を各染色体に適用することで、効果的に配置要素９の疎密を解消しようとするものである。なお、この配置最適化問題処理方法は、ＧＡｃ＋ＬＯと表記することができる。
【００５３】
ここで、遺伝的アルゴリズム（ＧＡｃ）による疎密解消法について、図６〜図１１を用いて説明する。
まず、遺伝的アルゴリズムについて説明すると、遺伝的アルゴリズムは、生物の遺伝の機構を模倣してそれを工学的に応用した技術であり、確率的探索，学習及び最適化の一手法と考えることができる。
【００５４】
生物の進化の過程では、既存の個体（親）から新たなる個体（子）が生まれる際に、個体のもつ染色体同士の交叉，染色体上の遺伝子の突然変異などが起こる。そして、環境に適応しない個体は淘汰され、環境により適応した個体が生きのびて新たな親となってさらに新たな子孫を作ることにより、環境に適応した個体の集団が生きのびていく。
各個体がどの程度環境に適応するかは、染色体（遺伝子の一次元ストリング）によって決定されるが、遺伝的アルゴリズムでは、配置最適化問題の解候補が遺伝子の一次元ストリングである染色体として表現される。そして、配置最適化問題の目的関数がいわゆる環境に相当し、目的関数を最適にするものほど大きい値をとるような適応度関数が染色体に対して定義される。
【００５５】
そして、遺伝的アルゴリズムでは、染色体の遺伝子配列を変化させて問題の最適解になりうる染色体（目的関数をより最適にする解）を生成するために、各染色体に、図８に示すような各種の遺伝オペレーション（選択／自己複製，交叉及び突然変異）が施される。
ここで、選択（Selection ）／自己複製（Reproduction）は、集団の中で適応度の高い染色体をもつ個体をより高い確率で選択して次世代の親とする操作であり（図９参照）、交叉（Crossover ）は、２つの親の染色体の一部を互いに入れ換えて新たな個体（子）を作りだす操作であり（図１０参照）、突然変異（Mutation）は、１つの染色体の一部の遺伝子をランダムに置き換えて個体を変化させる操作である（図１１参照）。
【００５６】
そして、これらの遺伝オペレーションを施すことにより、適応度値（fitnessvalue ）のより高い染色体（即ち、目的関数をより最適にする解）を得ることができる。
ここで、第１実施形態では、上記第１アルゴリズム実行ステップが、複数の配置要素９の配置状態を遺伝子として表現し、配置領域１０に上記複数の配置要素９を配置する問題の解候補として、当該遺伝子の配列からなり配置領域１０として定義される染色体を用いることにより、遺伝的アルゴリズム（ＧＡｃ）を実行するようになっている。
【００５７】
まず、第１アルゴリズム実行ステップでは、遺伝的アルゴリズム（ＧＡｃ）を実行する際に、配置領域１０を複数の部分領域１０ａに分割することにより染色体を複数の帯状の領域に分割する。
即ち、第１アルゴリズム実行ステップでは、配置要素９の配置結果を必要なだけ複製して、これらを親の染色体とする。次に、配置領域１０を前述したように縦方向又は横方向に帯状に分割して〔図３（ａ），図３（ｂ）参照〕、染色体を複数の帯状領域に分割する。ただし、遺伝的アルゴリズム（ＧＡｃ）を実行する際には、分割方向はどの染色体でも同一であるとする。
【００５８】
続いて、第１アルゴリズム実行ステップでは、染色体における上記複数の帯状領域の中から選択された少なくとも一つの帯状領域を、他の染色体における当該帯状領域に対応する帯状領域（この帯状領域は、当該帯状領域に含まれる要素と同じ要素を含むものである）と交換することにより、遺伝オペレーションとしての交叉が実行される。
ここで、交叉の一例を図６に示す。図６に示すように、染色体１１，１２を親の染色体として確率的に選んでこれらのコピーを作り、染色体１１の帯状領域Ａ1 〜Ａ4 ，染色体１２の帯状領域Ｂ1 〜Ｂ4 のうち、選ばれた帯状領域を互いに交換することによって交叉が実行される。図６には、染色体１１の帯状領域Ａ3と染色体１２の帯状領域Ｂ3 とを交換して、帯状領域Ａ1 ，Ａ2 ，Ｂ3 ，Ａ4 からなる子の染色体１３を得た例が示されている。なお、図６には、染色体の一つの帯状領域を選択し、染色体同士でこの部分を交換して交叉を実行する例が示されているが、染色体の複数の帯状領域を選択し、染色体同士でこれらの部分を交換して交叉を実行してもよい。
【００５９】
また、第１アルゴリズム実行ステップでは、一方の染色体における上記複数の帯状領域の中のある特定の帯状領域の方が、他方の染色体における当該帯状領域に対応する帯状領域よりも疎密が解消されている場合には、染色体における当該帯状領域を他の染色体における当該帯状領域に対応する帯状領域に張り付けることにより、遺伝オペレーションとしての交叉を実行してもよい。
【００６０】
例えば、一方の染色体の帯状領域Ｒi （ｉ＝１，…，Ｎ）の中で配置要素９の疎密が著しいものを一つ又は複数選び、もし他方の染色体の対応する帯状領域Ｒi ′（ｉ＝１，…，Ｎ）の配置要素９の疎密が、上記一方の染色体の帯状領域Ｒi より少ない場合には、他方の染色体の帯状領域Ｒi ′を一方の染色体の対応する部分へ張り付けることにより、交叉を実行することができる。
【００６１】
また、一方の染色体の帯状領域Ｒi の配置要素９の疎密と、他方の染色体の対応する帯状領域Ｒi ′の配置要素９の疎密とを全て比較し、もし他方の染色体に疎密が少ない帯状領域Ｒi ′があればそれを一方の染色体の対応する部分へ張り付け、逆に一方の染色体に疎密が少ない帯状領域Ｒi があればそれを他方の染色体の対応する部分へ張り付けることにより、交叉を実行してもよい。
【００６２】
さらに、第１アルゴリズム実行ステップでは、上記複数の帯状領域の中の少なくとも一つの帯状領域内において、上記複数の配置要素９のうちの少なくとも一つの配置要素９を移動させることにより、遺伝オペレーションとしての突然変異が実行される。
ここで、突然変異の一例を図７に示す。図７に示すように、配置要素９をある確率で選び、この配置要素９の属する領域Ｒi の中で配置要素９をランダムに移動させることによって、突然変異が実行される。なお、図７では、移動させる配置要素９に網かけを施している。
【００６３】
最後に、第１アルゴリズム実行ステップでは、上記複数の配置要素９の疎密が小さい染色体が大きな適応度値をとりうるような適応度値関数（fitness 関数）を用いて、遺伝オペレーションとしての選択が実行される。
ここで、選択を実行する際には、以下のように定義された適応度値関数を用いればよい。
【００６４】
適応度値＝定数−（配置要素密度の最大値−配置要素密度の最小値）…(1) 
適応度値＝定数−（配置要素密度が平均配置要素密度以下である配置領域の面積 ）…(2)
適応度値＝定数−（配置要素密度が平均配置要素密度以上である配置領域の面積） …(3)
さらに、局所的疎密解消法（ＬＯ）について、図１２〜図１７を用いて説明する。
【００６５】
局所的疎密解消法（ＬＯ）は、前述したように、局所的疎密解消アルゴリズムを実行して、配置領域１０の部分領域１０ａ内で配置要素９を配置要素密度が高い場所から低い場所へ移動させることにより、中間配置状態にある配置要素９の疎密を解消するものである。なお、局所的疎密解消法（ＬＯ）は、各染色体毎（各配置結果毎）に適用される。
ここで、第１実施形態においては、局所的疎密解消アルゴリズムとして、流体力学のアナロジーが適用されたアルゴリズムを用いて、配置要素９の疎密の解消が行なわれる。
【００６６】
流体力学のアナロジーとは、配置領域１０の部分領域１０ａ内における配置要素９の移動を一種の流体の動きとしてとらえ、隣接する部分領域１０ａでの配置要素９の流れ（移動）の相互影響や、同一の部分領域１０ａでの流れの相互影響を、粘性のアナロジーで考慮したものである。
流体力学のアナロジーが適用されたアルゴリズムを用いて、配置要素９の疎密の解消を行なう際には、まず、配置領域１０が縦方向又は横方向に予め決められた幅で分割されて、配置領域１０が複数の帯状の領域に分けられる。
【００６７】
ここで、第１実施形態では、遺伝的アルゴリズムを実行する際に、配置領域１０を複数の部分領域１０ａに分割しているので、その部分領域１０ａをそのまま帯状領域とすることができる。
また、新たに配置領域１０を分割しなおすことにより、配置領域１０を複数の帯状の領域に分けてもよい。
【００６８】
この場合には、縦方向に分割された帯状領域の個数をＮ本とすると、各帯状領域はＳ1 ，Ｓ2 ，…，ＳN で示すことができる。同様に、横方向に分割された帯状領域の個数をＭ本とすると、各帯状領域はＴ1 ，Ｔ2 ，…，ＴM で示すことができる。なお、各帯状領域（Ｓi ，Ｔi ）の幅は、それぞれ異なっていても良い。
また、配置領域１０の分割を階層化すれば、配置要素９の密度を均一にしやすくできる。なお、配置領域１０の分割を細かくしていく場合には、分割を対称的に進める方法〔図１２（ａ）〜図１２（ｄ）参照〕と、分割を非対称的に進める方法がある。
【００６９】
一方、配置領域１０を階層的に分割せずに、最初から細分化しておけば、階層的に分割を進めていく方法よりも計算時間を短縮することができる。
そして、配置領域１０が複数の帯状の領域に分けられると、帯状領域Ｔi （Ｓi ）内に位置する配置要素９を、この帯状領域Ｔi （Ｓi ）内で配置要素密度が均一になるように移動する。即ち、流体が密度の高い所から低い所へと移動する動作を模倣して、配置要素９を密度の高い位置から密度の低い位置へと移動する。
【００７０】
即ち、上記第２アルゴリズム実行ステップ（図２のステップＳ４）では、中間配置状態にある上記複数の配置要素９のうちの少なくとも一つの配置要素９を、配置要素密度が高い場所から配置要素密度が低い場所へと移動させることにより、流体力学のアナロジーが適用されたアルゴリズムを実行しているのである。
そして、配置領域１０を複数の部分領域１０ａに分割したときには、第２アルゴリズム実行ステップでは、上記分割した部分領域１０ａ内において、当該部分領域１０ａ内に含まれる上記複数の配置要素９のうちの少なくとも一つの配置要素９を、配置要素密度が高い場所から配置要素密度が低い場所へと移動させている。
【００７１】
ここで、配置要素９を移動させる際には、以下のような方法を用いることができる。
（１）近傍性の保存
流体のアナロジーでいえば、粘性のため近接する配置要素９同士は容易に遠くへ引き離されない。
従って、図１４（ａ），図１４（ｂ）に示すように、近接する配置要素９同士は移動後も近くに位置するように移動させる。
【００７２】
即ち、第２アルゴリズム実行ステップでは、上記複数の配置要素９間の近傍性を保存しながら、上記複数の配置要素９のうちの少なくとも一つの配置要素９を移動させることができる。
（２）順序性の保存
図１５（ａ），図１５（ｂ）に示すように、ある配置要素９と別の配置要素９とが所定の位置関係を有する場合（例えば、ある配置要素９が別の配置要素９の上又は右の位置にある場合等）、移動後も２つの配置要素９がこの位置関係を保つように配置要素９を移動する。
【００７３】
これは配置最適化問題の解が与える配置要素９間の相対的な位置関係を保存する働きがある。
即ち、第２アルゴリズム実行ステップでは、上記複数の配置要素９間の順序性を保存しながら、上記複数の配置要素９のうちの少なくとも一つの配置要素９を移動させることができる。
【００７４】
（３）逐次添加法
一度に全ての配置要素９の移動を考慮するのではなく、最初はごく少数の配置要素９のみの移動を考慮する。これら少数の配置要素９を移動させて、これら少数の配置要素９の密度を均一にした後に、まだ考慮していない配置要素９の中から再び少数の配置要素９を選択し、すでに移動の終った配置要素９の集合に付け加える。そして、この新たに配置要素９が添加された配置要素９の集合について、配置要素９の密度を均一にするように配置要素９の移動を再度実施する。
【００７５】
例えば、図１６（ａ）に示すように、配置要素９を、符号Ａで示す配置要素９の集合と、符号Ｂで示す配置要素９の集合とに分ける。なお、図１６（ａ）では、符号Ａで示す配置要素９を斜線で示し、符号Ｂで示す配置要素９を網かけで示している。
そして、まず、図１６（ｂ），図１６（ｃ）に示すように符号Ａで示す配置要素９の集合の疎密を解消して、図１６（ｄ）に示すように、疎密が解消された当該配置要素９の集合に符号Ｂで示す配置要素９の集合を添加する。続いて、図１６（ｅ）に示すように、符号Ｂで示す配置要素９の集合の疎密を解消する。
【００７６】
即ち、第２アルゴリズム実行ステップでは、中間配置状態にある上記複数の配置要素９の疎密を解消する際に、疎密解消対象となる配置要素９を逐次添加していくことができる。
（４）固定配置要素の考慮
固定配置要素は移動させることができない配置要素９であるが、固定配置要素がある場合に、固定配置要素を考慮せずに固定配置要素以外の配置要素９のみを移動させると、固定配置要素の周辺の配置要素密度が大きくなりやすい傾向がある。
【００７７】
そこで、固定配置要素の周辺に配置要素９が集積しないようにするため、上記複数の配置要素９の中に固定配置要素がある場合には、第２アルゴリズム実行ステップでは、固定配置要素も疎密解消対象となる配置要素９とみなして、中間配置状態にある上記複数の配置要素９の疎密を解消することが好ましい。
（５）大きな配置要素の考慮
他の配置要素９に比べて配置領域１０を占める割合が大きな配置要素がある場合に、この大きな配置要素を移動させると、大きな配置要素は多数の配置要素９と重なりやすいため、配置要素密度を著しく増大させる恐れがある。
【００７８】
これを避けるためには、大きな配置要素の移動量を他の配置要素９の移動量に比べて比較的小さくすればよい。
即ち、上記複数の配置要素９の中に大きな配置要素がある場合には、第２アルゴリズム実行ステップでは、大きな配置要素の移動量を小さくして、中間配置状態にある上記複数の配置要素９の疎密を解消することが好ましい。
【００７９】
また、図１７に示すように、大きな配置要素９ａが帯状領域Ｔi と帯状領域Ｔi+1 とをまたぐように配置領域１０に存在している場合には、注意が必要である。特に、大きな配置要素９ａの周辺の配置要素９の移動方向が帯状領域Ｔi と帯状領域Ｔi+1 で反対である場合には、この大きな配置要素９ａは動かさないようにする必要がある。
（６）配置要素密度の高い帯状領域の疎密の解消方法
配置要素密度の高い帯状領域Ｓi （Ｔi ）の疎密の解消方法には、一挙に（一度に）配置要素９を移動させて一度に密度の高い帯状領域Ｓi （Ｔi ）をなくす方法と、徐々に（段階的に）配置要素９を移動させて段階的に高い配置要素密度をならしていく方法とがある。
【００８０】
即ち、第２アルゴリズム実行ステップでは、中間配置状態にある上記複数の配置要素９の疎密を解消する際に、移動対象となる配置要素９を一挙に移動させてもよいし、移動対象となる要素を徐々に移動させてもよい。
これにより、第１実施形態にかかる配置最適化問題処理方法においては、第１アルゴリズム実行ステップでは、上記複数の配置要素９の初期配置状態に関する情報が入力されると、遺伝的アルゴリズム（ＧＡｃ）を実行して、初期配置状態にある上記複数の配置要素９の疎密が解消される。
【００８１】
そして、第２アルゴリズム実行ステップでは、第１アルゴリズム実行ステップにて疎密が解消された後の上記複数の配置要素９の中間配置状態に関する情報が入力されると、局所的疎密解消アルゴリズムを実行して、中間配置状態にある上記複数の配置要素９の疎密が更に解消される。
上述のように第１アルゴリズム実行ステップと第２アルゴリズム実行ステップとを実行することにより、上記複数の配置要素９を配置領域１０に最適な状態で配置する配置最適化問題を処理することができる。
【００８２】
このように、本発明の第１実施形態にかかる配置最適化問題処理方法によれば、遺伝的アルゴリズム（ＧＡｃ）による疎密解消法と、流体力学のアナロジーが適用されたアルゴリズムを用いた局所的疎密解消法（ＬＯ）とを組み合わせているので、適応度の増加を加速して、遺伝的アルゴリズム（ＧＡｃ）の高速化を実現することができる。
また、遺伝的アルゴリズム（ＧＡｃ）において、配置要素９の疎密の解消に適した交叉を導入しているので、解を効率的に発生させることができ、最適解を効率的に探索することができる。
【００８３】
さらに、第２アルゴリズム実行ステップが、複数の配置要素９間の近傍性を保存しながら配置要素９を移動させたり、複数の配置要素９間の順序性を保存しながら配置要素９を移動させたりできるので、処理できる配置最適化問題の範囲を拡大することができる。
また、第２アルゴリズム実行ステップが、配置要素９の疎密を解消する際に、疎密解消対象となる配置要素９を逐次添加したり、固定配置要素も疎密解消対象となる配置要素９とみなしたり、大きな配置要素９の移動量を小さくしたり、移動対象となる配置要素９を一挙に移動させたり、移動対象となる配置要素９を徐々に移動させたりできるので、更に処理できる配置最適化問題の範囲を拡大することができる。
【００８４】
なお、上述においては、第１アルゴリズム実行ステップにて遺伝的アルゴリズム（ＧＡｃ）による疎密解消法を実行した後に、第２アルゴリズム実行ステップにて局所的疎密解消法（ＬＯ）を実行することにより、遺伝的アルゴリズム（ＧＡｃ）による疎密解消法と局所的疎密解消法（ＬＯ）とを組み合わせた場合について説明したが、第１アルゴリズム実行ステップが遺伝的アルゴリズム（ＧＡｃ）を実行している中で、第２アルゴリズム実行ステップが局所的疎密解消アルゴリズムを実行することにより、遺伝的アルゴリズム（ＧＡｃ）による疎密解消法と局所的疎密解消法（ＬＯ）とを組み合わせることもできる。
【００８５】
このときの配置最適化問題処理装置１の動作を、図１８に示すフローチャートを用いて説明する。
まず、配置最適化問題処理装置１に、上記複数の配置要素９の初期配置結果（初期配置状態に関する情報）が入力される（ステップＡ１）。
この配置要素９の初期配置結果が入力されると、配置最適化問題処理装置１においては、上記第１アルゴリズム実行ステップにより、配置結果のコピーを作ることにより染色体の集団が準備される（ステップＡ２）。
【００８６】
続いて、第２アルゴリズム実行ステップでは、各染色体（各配置結果）に対して、配置領域１０の分割方法は同じであるがその他の制御パラメータが異なる局所的疎密解消法（ＬＯ）が実行されて、配置結果の疎密の解消が試みられる（ステップＡ３）。なお、局所的疎密解消法（ＬＯ）は、流体力学のアナロジーが適用されたアルゴリズムを用いて実行される。
【００８７】
さらに、第１アルゴリズム実行ステップでは、各染色体に対して、遺伝オペレーションとしての交叉，突然変異及び選択が施され（ステップＡ４〜Ａ６）、最高の適応度値をもつ染色体（最適な染色体）の適応度値が所定の基準値以上であるか、又は、配置結果の疎密が解消されたかどうかが判断される（ステップＡ７）。
そして、最適な染色体の適応度値が所定の基準値以上でない、又は、配置結果の疎密が解消されていないと判断された場合には、上記ステップＡ３以降の処理を繰り返し（ステップＡ７のＮＯルート）、最適な染色体の適応度値が所定の基準値以上である、又は、配置結果の疎密が解消されていると判断された場合には、その最適な染色体が配置最適化問題の解として出力されて、配置最適化問題処理装置１での処理が終了する（ステップＡ７のＹＥＳルート）。
【００８８】
このようにしても、上述したものと同様の利点を得ることができる。
また、流体力学のアナロジーが適用されたアルゴリズムを用いて局所的疎密解消法（ＬＯ）を実行する際に、図１３（ａ）〜図１３（ｃ）に示すように、ある配置領域１０を縦方向に分割して各配置要素９を移動させるとともに、他の配置領域１０を横方向に分割して各配置要素９を移動させ、特定の配置要素９の、縦方向の分割における移動（移動方向と移動量）と、横方向の分割における移動（移動方向と移動量）を、例えばそれぞれベクトルとみなして、２つのベクトルを合成することにより、当該特定の配置要素９の移動方向と移動量を求め、これに基づいて当該特定の配置要素９を移動させてもよい。
【００８９】
（ｂ３）第１実施形態の変形例の説明
上述した第１実施形態においては、第２アルゴリズム実行ステップが、局所的疎密解消法（ＬＯ）を実行する際に、局所的疎密解消アルゴリズムとして、流体力学のアナロジーが適用されたアルゴリズムを用いる場合について説明したが、第２アルゴリズム実行ステップは、局所的疎密解消アルゴリズムとして、モーフィングのアナロジーが適用されたアルゴリズムを用いることもできる。
【００９０】
モーフィングのアナロジーとは、ある２次元画像を徐々に変形して他の画像にする画像処理技術であるモーフィング（morphing）を模倣し、配置領域１０の部分領域１０ａ内における配置要素９の移動をモーフィングにおける変形動作としてとらえたものである。ただし、画像処理技術のモーフィングとは異なり、配置要素９自体の大きさや形状は変化せず、配置要素９の配置領域１０上での位置座標のみが変化するようにする。
【００９１】
そして、モーフィングのアナロジーによって配置要素９の疎密の解消を実行する際には、前述の第１実施形態にて説明したように配置領域１０を分割して得られた各帯状領域内で、図１９（ａ）に示すように、それぞれ配置要素９を移動させる際の中心点（モーフィング中心部）Ｃを決定する。そして、図１９（ｂ）に示すように、この中心点Ｃを基準として、この中心点Ｃから配置要素までの距離に応じて、配置要素９間の相対的な位置関係を保ったまま配置要素９の座標を増加させることにより配置要素９間の距離を増大させ、配置要素９を当該配置要素９の方向に（即ち、配置要素９を中心点Ｃから配置要素９が存在する方向に放射状に拡散するように）移動させる。
【００９２】
ここで、モーフィングの中心点Ｃは、以下に示す方法のいずれかにより決定することができる。
（１）配置要素９の重心を用いる方法
配置要素９の重心の位置をモーフィングの中心とする方法である。
即ち、各配置要素９の座標を（ｘ1 ，ｙ1 ），（ｘ2 ，ｙ2 ），…，（ｘM ′，ｙM ′）とするとき、モーフィングの中心をその重心、
【００９３】
【数１】
2007052799.tif 000003
【００９４】
とする方法である。
（２）配置要素９の数に基づいた方法
配置領域１０の各帯状領域において、帯状領域のＸ軸に垂直な線であってこの線の両側に位置する配置要素９の数が等しくなるような線（Ｘ軸に垂直な線で配置要素数をＸ方向に二等分する線）と、帯状領域のＹ軸に垂直な線であってこの線の両側に位置する配置要素９の数が等しくなるような線（Ｙ軸に垂直な線で配置要素数をＹ方向に二等分する線）を決定する。そして、これら二つの線の交点をモーフィングの中心とする方法である。
【００９５】
（３）配置要素９の面積に基づいた方法
配置領域１０の各帯状領域において、帯状領域のＸ軸に垂直な線であってこの線の両側に位置する配置要素９の面積が等しくなるような線（Ｘ軸に垂直な線で配置要素の総面積をＸ方向に二等分する線）と、帯状領域のＹ軸に垂直な線であってこの線の両側に位置する配置要素９の面積が等しくなるような線（Ｙ軸に垂直な線で配置要素の総面積をＹ方向に二等分する線）を決定する。そして、これら二つの線の交点をモーフィングの中心とする方法である。
【００９６】
即ち、第２アルゴリズム実行ステップでは、中間配置状態にある上記複数の配置要素９に関する情報（配置要素９の重心，総数，総面積等）に基づいて中心点Ｃを決定し、上記複数の配置要素９のうちの少なくとも一つの配置要素９を中心点Ｃから離隔した場所へと移動させることにより、モーフィングのアナロジーが適用されたアルゴリズムを実行しているのである。
【００９７】
そして、上記複数の配置要素９を配置する配置領域１０を複数の帯状領域（又は部分領域１０ａ）に分割したときには、第２アルゴリズム実行ステップでは、当該帯状領域毎に中心点Ｃを決定し、当該帯状領域内において、当該帯状領域内に含まれる上記複数の配置要素９の少なくとも一つの配置要素９を上記中心点Ｃから離隔した場所へと移動させている。
【００９８】
ここで、配置要素９の移動量の決め方を以下に示す。
（１）配置要素９の移動量の線形的拡大
モーフィングの中心点Ｃから配置要素９の中心までの距離に比例させて（即ち線形に）、この中心点Ｃから当該配置要素９の方向に向かって配置要素９を移動させる。
即ち、第２アルゴリズム実行ステップでは、上記複数の配置要素９の少なくとも一つの配置要素９を中心点Ｃから離隔した場所へと移動させる際に、中心点Ｃから移動対象となる配置要素９までの距離を線形的に拡大することができる。
【００９９】
（２）配置要素９の移動量の非線形的拡大
モーフィングの中心点Ｃから当該配置要素９の方向に向かって配置要素９を移動させるときに、移動させる距離はこの中心点Ｃから配置要素９の中心までの距離に応じた非線形な関数で定義されている。
具体的には、中心点Ｃの近傍は配置要素９の疎密が大きいことから、中心点近傍の配置要素９の移動量を大きくする一方、分割された帯状領域（又は部分領域１０ａ）の内部で配置要素９を移動させるために、当該帯状領域の境界近傍の配置要素９の移動量はより小さくするようにする。
【０１００】
即ち、第２アルゴリズム実行ステップでは、上記複数の配置要素９の少なくとも一つの配置要素９を中心点Ｃから離隔した場所へと移動させる際に、中心点Ｃから移動対象となる配置要素９までの距離を非線形的に拡大することもできる。
このようなモーフィングのアナロジーが適用されたアルゴリズムを用いて局所的疎密解消法（ＬＯ）を実行しても、上述した第１実施形態の場合と同様の利点を得ることができる。
【０１０１】
また、第２アルゴリズム実行ステップが、配置要素９を中心点Ｃから離隔した場所へと移動させる際に、中心点Ｃから移動対象となる配置要素９までの距離を線形的に拡大したり、中心点Ｃから移動対象となる配置要素９までの距離を非線形的に拡大したりできるので、処理できる配置最適化問題の範囲を拡大することができる。
なお、この第１実施形態の変形例にかかる配置最適化問題処理方法においても、配置要素９の疎密を解消する際に、第１実施形態にて説明したように、逐次添加法を用いたり、固定配置要素や大きな配置要素を考慮したり、配置要素９を一挙に移動させたり、徐々に移動させたりすることができる。
【０１０２】
（ｂ４）第２実施形態の説明
本発明の第２実施形態にかかる配置最適化問題処理方法について説明する。
第２実施形態にかかる配置最適化問題処理方法は、上記第１アルゴリズム実行ステップ（図２のステップＳ３）において、遺伝的アルゴリズム（ＧＡｐ）を実行し、第２アルゴリズム実行ステップ（図２のステップＳ４）において、局所的疎密解消アルゴリズムとして、第１実施形態にて前述した流体力学のアナロジーが適用されたアルゴリズムを実行するものである。
【０１０３】
ここで、第２実施形態にて実行される遺伝的アルゴリズム（ＧＡｐ）は、局所的疎密解消法（ＬＯ）において配置領域１０を分割する幅を最適化するための遺伝的アルゴリズムである。
即ち、第２実施形態にかかる配置最適化問題処理方法は、局所的疎密解消法（ＬＯ）のパラメータである配置領域１０を分割する幅のリストからなる各染色体に遺伝的アルゴリズム（ＧＡｐ）を適用することにより、配置領域１０の分割を最適化して、効率的に配置要素９の疎密を解消しようとするものである。
【０１０４】
換言すれば、この方法は、配置領域１０の分割法を最適にするために、与えられた配置を初期配置として、局所的疎密解消法（ＬＯ）におけるパラメータ（配置領域１０の横幅）を遺伝的アルゴリズム（ＧＡｐ）で最適化することにより、疎密の解消を効率的に実施する方法である。
なお、この配置最適化問題処理方法は、ＧＡｐ＋ＬＯと表記することができる。
【０１０５】
つまり、第２実施形態では、上記第１アルゴリズム実行ステップが、上記第２アルゴリズム実行ステップにおいて実行される局所的疎密解消アルゴリズムにて用いられるパラメータを遺伝子として表現し、このパラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いることにより、遺伝的アルゴリズム（ＧＡｐ）を実行するようになっている。
【０１０６】
ここで、パラメータは、配置領域１０を分割する幅を規定する情報（部分領域１０ａの大きさを規定する情報）と、その他の局所的疎密解消法（ＬＯ）の制御パラメータとからなる。
つまり、遺伝的アルゴリズム（ＧＡｐ）では、部分領域１０ａの幅を規定する情報のリストと、その他の局所的疎密解消法（ＬＯ）の制御パラメータのリストとからなる染色体を用いている。
【０１０７】
例えば、配置領域１０を縦方向に分割する場合に、帯状領域Ｓ1 ，Ｓ2 ，…，ＳN の幅をそれぞれＷ1 ，Ｗ2 ，…，ＷN としたときの染色体の構成を、図２０に示す。ここで、幅Ｗ1 ，Ｗ2 ，…，ＷN の合計は、配置領域１０の横幅と等しくなければならない。なお、染色体１４は、その他の局所的疎密解消法の制御パラメータａ1 ，ａ2 も遺伝子として持っている。
【０１０８】
そして、第１アルゴリズム実行ステップでは、二つの親の染色体の遺伝子の重み付き平均を子の染色体の遺伝子とすることにより、遺伝オペレーションとしての交叉が実行される。
ここで、交叉の一例を図２１に示す。図２１に示すように、染色体１５，１６を親の染色体として確率的に選んでこれらのコピーを作り、染色体１５の遺伝子と染色体１６の遺伝子の適当な重みつき平均をとり、これを子の染色体１７の遺伝子とすることにより交叉が実行される。
【０１０９】
なお、図２１において、Ｗ1 〜Ｗ4 …，Ｍ1 〜Ｍ4 …，Ｚ1 〜Ｚ4 …は、帯状領域Ｓ1 ，Ｓ2 ，…，ＳN の幅を示しており、ａ1 …，ｂ1 …，ｃ1 …は、その他の局所的疎密解消法（ＬＯ）の制御パラメータを示している。
ここで、
Ｚi ＝（Ｗi ＋Ｍi ）／２ …(4)
ｃi ＝（ａi ＋ｂi ）／２ …(5) 
である。
【０１１０】
このほか、第１アルゴリズム実行ステップでは、パラメータに含まれる部分領域１０ａの幅を規定する情報の総和が変化しないように調整しながら、染色体の一部の帯状領域を他の染色体の当該帯状領域に対応する帯状領域に張り付けることにより、遺伝オペレーションとしての交叉を実行してもよい。
例えば、一方の染色体の一部分を他方の染色体に張り付ける際に、幅Ｗ1 ，Ｗ2 ，…，ＷN の合計が変化しないように他方の染色体に元からある遺伝子を調整しながら交叉を実行する。なお、他方の染色体の一部分を一方の染色体に張り付ける場合も同様である。
【０１１１】
さらに、第１アルゴリズム実行ステップでは、染色体の少なくとも二つの遺伝子を選択し、選択した上記遺伝子に任意の数値を加えることにより、パラメータに含まれる上記部分領域１０ａの幅を規定する情報の総和が変化しないように調整して、遺伝オペレーションとしての突然変異が実行される。
即ち、染色体の遺伝子に小さな変化をランダムに与えることによって突然変異を起こすのであり、具体的には、選択した遺伝子のうちの一方の遺伝子に所定の数を加える一方、他方の遺伝子から所定の数を引くことにより、部分領域１０ａの幅を規定する情報の総和が変化しないように調整しながら、突然変異が実行される。
【０１１２】
ここで、突然変異の一例を図２２に示す。図２２に示すように、染色体１８の任意の二つの遺伝子Ｗ3 ，Ｗ5 を選択し、遺伝子Ｗ5 に小さな正の乱数ΔＷを加える一方、遺伝子Ｗ3 から当該乱数ΔＷを差し引くことにより、部分領域１０ａの幅を規定する情報の総和が変化しないように調整しながら、染色体１８を染色体１８′に変化させる。なお、図２２に示す例では、その他の局所的疎密解消法（ＬＯ）の制御パラメータａ2 に絶対値の小さな乱数Δａを加えることによっても、染色体１８に突然変異を施している。
【０１１３】
より一般には、染色体の任意の二つの遺伝子をＷi ，Ｗj とし、小さな正の乱数をΔＷとし、突然変異後の遺伝子をＷi ′，Ｗj ′とすると、遺伝子Ｗi ′，Ｗj ′は以下のように表すことができる。
Ｗi ′＝Ｗi −ΔＷ …(6)
Ｗj ′＝Ｗj ＋ΔＷ …(7)
このほか、第１アルゴリズム実行ステップでは、染色体の任意のｍ個の遺伝子Ｗi1，Ｗi2，…，Ｗimを選択し、絶対値が小さな乱数をΔＷi1，ΔＷi2，…，ΔＷimを用いて、これらの遺伝子Ｗi1，Ｗi2，…，Ｗimに突然変異を施して遺伝子Ｗi1′，Ｗi2′，…，Ｗim′を生成してもよい。
【０１１４】
このとき、遺伝子Ｗi1′，Ｗi2′，…，Ｗim′は以下のように表すことができる。
Ｗik′＝Ｗik＋ΔＷik
但し、ΔＷi1＋ΔＷi2＋…＋ΔＷim＝０ …(8)
このように、第２実施形態においては、第１アルゴリズム実行ステップでは、遺伝的アルゴリズム（ＧＡｐ）を実行することにより、配置領域１０の分割幅の最適値の候補（最適幅の候補）が複数求められる。
【０１１５】
その後、第２アルゴリズム実行ステップでは、第１アルゴリズム実行ステップにて得られた複数の最適幅の候補によりそれぞれ配置領域１０を分割して、局所的疎密解消法（ＬＯ）を実行することにより、初期配置状態にある上記複数の配置要素９の疎密の解消が試みられる。
そして、第２実施形態においては、再度、第１アルゴリズム実行ステップでの処理に戻り、第１アルゴリズム実行ステップでは、以下のように定義された適応度値関数（即ち、上記複数の配置要素９の疎密を小さくできるような染色体が大きな適応度値をとりうるような適応度値関数）を用いて、遺伝オペレーションとしての選択が実行され、最も疎密が解消された配置結果としての染色体が選択される。
【０１１６】
適応度値＝定数−（配置要素密度の最大値−配置要素密度の最小値）…(9)
適応度値＝定数−（配置要素密度が平均配置要素密度以下である配置領域の面積） …(10)
適応度値＝定数−（配置要素密度が平均配置要素密度以上である配置領域の面積） …(11)
つまり、これらの適応度値関数を用いて、局所的疎密解消法（ＬＯ）を改善し、結果として、配置要素９の疎密解消を改善することが可能になる。
【０１１７】
即ち、第２実施形態にかかる配置最適化問題処理方法においては、第１アルゴリズム実行ステップと第２アルゴリズム実行ステップとを組み合わせて実行することにより、局所的疎密解消アルゴリズムを実行する際に用いるパラメータである分割幅の最適値を求めることを通して、初期配置状態にある上記複数の配置要素９の疎密が解消される。
これにより、上記複数の配置要素９を配置領域１０に最適な状態で配置する配置最適化問題を処理することができる。
【０１１８】
このように、本発明の第２実施形態にかかる配置最適化問題処理方法によれば、遺伝的アルゴリズム（ＧＡｐ）により配置領域１０の分割を最適化しているので、効率的に配置要素９の疎密を解消することができる。
また、遺伝的アルゴリズム（ＧＡｐ）を実行して得られた各染色体により指定される種々の幅で複数の配置領域１０を分割して、複数の配置領域１０に異なる局所的疎密解消法（ＬＯ）を適用し、最適な局所的疎密解消法（ＬＯ）を見つけているので、配置領域１０の最適な分割法を探索することができる。
【０１１９】
なお、以下に説明するようにして、上記第１アルゴリズム実行ステップが、遺伝的アルゴリズム（ＧＡｐ）を実行している中で、第２アルゴリズム実行ステップが、局所的疎密解消アルゴリズムを実行することにより、遺伝的アルゴリズム（ＧＡｐ）と局所的疎密解消法（ＬＯ）とを組み合わせることもできる。
このときの配置最適化問題処理装置１の動作を、図２３に示すフローチャートを用いて説明する。
【０１２０】
まず、配置最適化問題処理装置１に、上記複数の配置要素９の初期配置結果（初期配置状態に関する情報）が入力される（ステップＢ１）。
この配置要素９の初期配置結果が入力されると、配置最適化問題処理装置１では、上記第１アルゴリズム実行ステップにより、局所的疎密解消法（ＬＯ）のパラメータを遺伝子とする染色体の集団が準備される（ステップＢ２）。
【０１２１】
続いて、第２アルゴリズム実行ステップでは、各染色体に対応する局所的疎密解消法（ＬＯ）にて疎密の解消が試みられ〔即ち、それぞれの染色体により指定される幅で複数の配置領域１０を分割して、各配置領域１０毎に局所的疎密解消法（ＬＯ）にて疎密の解消が試みられ〕、適応度値が計算される（ステップＢ３）。なお、局所的疎密解消法（ＬＯ）は、流体力学のアナロジーが適用されたアルゴリズムを用いて実行される。
【０１２２】
その後、第１アルゴリズム実行ステップでは、各染色体に対して、遺伝オペレーションとしての交叉及び突然変異が施され（ステップＢ４，Ｂ５）、最高の適応度値をもつ染色体（最適な染色体）の適応度値が所定の基準値以上であるか、又は、最高の適応度値をもつ染色体により決定される幅で配置領域１０を分割して局所的疎密解消法（ＬＯ）を実行した場合に、配置要素９の疎密解消結果は満足できるものであるかが判断される（ステップＢ６）。
【０１２３】
そして、最適な染色体の適応度値が所定の基準値以上でない、又は、配置要素９の疎密解消結果は満足できるものでないと判断された場合には、上記ステップＢ３以降の処理を繰り返し（ステップＢ６のＮＯルート）、最適な染色体の適応度値が所定の基準値以上である、又は、配置要素９の疎密解消結果は満足できるものであると判断された場合には、そのときの配置要素９の配置結果が配置最適化問題の解として出力されて、配置最適化問題処理装置１での処理が終了する（ステップＢ６のＹＥＳルート）。
【０１２４】
このようにしても、上述したものと同様の利点を得ることができる。
なお、この第２実施形態にかかる配置最適化問題処理方法においても、配置要素９の疎密を解消する際に、第１実施形態にて説明したように、逐次添加法を用いたり、固定配置要素や大きな配置要素を考慮したり、配置要素９を一挙に移動させたり、徐々に移動させたりすることができる。
【０１２５】
（ｂ５）第２実施形態の変形例の説明
なお、上述した第２実施形態においては、第２アルゴリズム実行ステップが、局所的疎密解消法（ＬＯ）を実行する際に、局所的疎密解消アルゴリズムとして、流体力学のアナロジーが適用されたアルゴリズムを用いる場合について説明したが、前述した第１実施形態の変形例の場合と同様に、第２アルゴリズム実行ステップは、局所的疎密解消アルゴリズムとして、前述したモーフィングのアナロジーが適用されたアルゴリズムを用いることもできる。
【０１２６】
このように、モーフィングのアナロジーが適用されたアルゴリズムを用いて局所的疎密解消法（ＬＯ）を実行しても、上述した第２実施形態の場合と同様の利点を得ることができる。
この場合も、配置要素９の疎密を解消する際に、第１実施形態にて説明したように、逐次添加法を用いたり、固定配置要素や大きな配置要素を考慮したり、配置要素９を一挙に移動させたり、徐々に移動させたりすることができるのは言うまでもない。
【０１２７】
（ｂ６）第３実施形態の説明
本発明の第３実施形態にかかる配置最適化問題処理方法について説明する。
第３実施形態にかかる配置最適化問題処理方法は、上記第１アルゴリズム実行ステップ（図２のステップＳ３）において、遺伝的アルゴリズム（ＧＡｐ）を実行している中で、更に、第１アルゴリズム実行ステップが遺伝的アルゴリズム（ＧＡｃ）を実行するとともに、第２アルゴリズム実行ステップ（図２のステップＳ４）が局所的疎密解消アルゴリズムを実行することにより、遺伝的アルゴリズム（ＧＡｐ，ＧＡｃ）と局所的疎密解消法（ＬＯ）とを組み合わせるものである。
【０１２８】
即ち、第３実施形態にかかる配置最適化問題処理方法は、遺伝的アルゴリズム（ＧＡｐ）で最適解を求める際に、各世代の終了毎又は複数世代の終了毎に遺伝的アルゴリズム（ＧＡｃ）を実行するとともに、更に、この遺伝的アルゴリズム（ＧＡｃ）の実行中に局所的疎密解消法（ＬＯ）を実施するものである。
つまり、この方法は、遺伝的アルゴリズム（ＧＡｐ）の内側に、遺伝的アルゴリズム（ＧＡｃ）と局所的疎密解消法（ＬＯ）とを挿入したものであり、ＧＡｐ＋（ＧＡｃ＋ＬＯ）と表記することができる。
【０１２９】
このときの配置最適化問題処理装置１の動作を、図２４に示すフローチャートを用いて説明する。
まず、配置最適化問題処理装置１に、上記複数の配置要素９の初期配置結果（初期配置状態に関する情報）が入力される（ステップＣ１）。
この配置要素９の初期配置結果が入力されると、配置最適化問題処理装置１では、上記第１アルゴリズム実行ステップにより、局所的疎密解消法（ＬＯ）のパラメータを遺伝子とする、遺伝的アルゴリズム（ＧＡｐ）の染色体の集団が準備される（ステップＣ２）。
【０１３０】
続いて、第１アルゴリズム実行ステップでは、各染色体に対して、遺伝的アルゴリズム（ＧＡｐ）における遺伝オペレーションである交叉及び突然変異が施される（ステップＣ３，Ｃ４）。
そして、この遺伝的アルゴリズム（ＧＡｐ）の実行中に、更に第１アルゴリズム実行ステップにより、遺伝的アルゴリズム（ＧＡｃ）が実行されるとともに、第２アルゴリズム実行ステップにより、局所的疎密解消アルゴリズムが実行される（ステップＣ５〜Ｃ１２）。
【０１３１】
即ち、第１アルゴリズム実行ステップでは、上記ステップＣ１で取得した配置要素９の初期配置結果のコピーを作ることにより、遺伝的アルゴリズム（ＧＡｃ）の染色体の集団が準備される（ステップＣ５）。
そして、遺伝的アルゴリズム（ＧＡｐ）の複数の染色体により指定される配置領域１０の分割法により〔即ち、遺伝的アルゴリズム（ＧＡｐ）の複数の染色体により指定される幅で〕、複数の遺伝的アルゴリズム（ＧＡｃ）の染色体である配置領域１０がそれぞれ分割される（ステップＣ６）。
【０１３２】
さらに、第１アルゴリズム実行ステップでは、各染色体に対して、遺伝的アルゴリズム（ＧＡｃ）における遺伝オペレーションである交叉及び突然変異が施される（ステップＣ７，Ｃ８）。
その後、第２アルゴリズム実行ステップでは、各染色体（各配置結果）に対して、配置領域１０の分割方法は同じであるがその他の制御パラメータが異なる局所的疎密解消法（ＬＯ）が実行されて、配置結果の疎密の解消が試みられる（ステップＣ９）。なお、局所的疎密解消法（ＬＯ）は、流体力学のアナロジーが適用されたアルゴリズム、又は、モーフィングのアナロジーが適用されたアルゴリズムを用いて実行される。
【０１３３】
さらに、第１アルゴリズム実行ステップでは、各染色体に対して、遺伝的アルゴリズム（ＧＡｃ）における遺伝オペレーションである選択が施された後に（ステップＣ１０）、遺伝的アルゴリズム（ＧＡｃ）を行なうように定められた世代数を超えたかが判断される（ステップＣ１１）。
そして、定められた世代数を超えていないと判断された場合〔即ち、まだ定められた世代数分の遺伝的アルゴリズム（ＧＡｃ）が実行されていないと判断された場合〕には、上記ステップＣ７以降の処理を繰り返し（ステップＣ１１のＮＯルート）、定められた世代数を超えたと判断された場合〔即ち、定められた世代数分の遺伝的アルゴリズム（ＧＡｃ）が実行されたと判断された場合〕には、遺伝的アルゴリズム（ＧＡｃ）での最適な染色体の持つ適応度値が、遺伝的アルゴリズム（ＧＡｐ）の染色体の持つ適応度値とされる（ステップＣ１１のＹＥＳルートからステップＣ１２）。
【０１３４】
その後、第１アルゴリズム実行ステップでは、再度遺伝的アルゴリズム（ＧＡｐ）の実行に戻り、各染色体に対して、遺伝的アルゴリズム（ＧＡｐ）における遺伝オペレーションである選択が施され（ステップＣ１３）、最高の適応度値をもつ染色体（最適な染色体）の適応度値が所定の基準値以上であるか、又は、配置結果の疎密が解消されたかどうかが判断される（ステップＣ１４）。
【０１３５】
そして、最適な染色体の適応度値が所定の基準値以上でない、又は、配置結果の疎密が解消されていないと判断された場合には、上記ステップＣ３以降の処理を繰り返し（ステップＣ１４のＮＯルート）、最適な染色体の適応度値が所定の基準値以上である、又は、配置結果の疎密が解消されていると判断された場合には、その最適な染色体が配置最適化問題の解として出力されて、配置最適化問題処理装置１での処理が終了する（ステップＣ１４のＹＥＳルート）。
【０１３６】
このように、本発明の第３実施形態にかかる配置最適化問題処理方法によれば、前述した各実施形態と同様の効果を得ることができるほか、遺伝的アルゴリズム（ＧＡｐ）の実行中に、遺伝的アルゴリズム（ＧＡｃ）と局所的疎密解消法（ＬＯ）とを組み合わせて実行しているので、遺伝的アルゴリズム（ＧＡｐ）の更なる高速化を実現することができる。
【０１３７】
（ｂ７）第４実施形態の説明
本発明の第４実施形態にかかる配置最適化問題処理方法について説明する。
第４実施形態にかかる配置最適化問題処理方法は、上記第１アルゴリズム実行ステップ（図２のステップＳ３）において、遺伝的アルゴリズム（ＧＡｃ）を実行している中で、更に、第１アルゴリズム実行ステップが遺伝的アルゴリズム（ＧＡｐ）を実行するとともに、第２アルゴリズム実行ステップが局所的疎密解消アルゴリズムを実行することにより、遺伝的アルゴリズム（ＧＡｐ，ＧＡｃ）と局所的疎密解消法（ＬＯ）とを組み合わせるものである。
【０１３８】
即ち、第４実施形態にかかる配置最適化問題処理方法は、遺伝的アルゴリズム（ＧＡｃ）で最適解を求める際に、各世代の終了毎又は複数世代の終了毎に遺伝的アルゴリズム（ＧＡｐ）を実行するとともに、更に、この遺伝的アルゴリズム（ＧＡｐ）の実行中に局所的疎密解消法（ＬＯ）を実施するものである。
つまり、この方法は、第２実施形態にて前述したように遺伝的アルゴリズム（ＧＡｐ）と局所的疎密解消法（ＬＯ）とを組み合わせて実行することにより、配置領域１０の分割幅を最適化し、この分割幅で分割された配置領域１０を遺伝的アルゴリズム（ＧＡｃ）の染色体として用いて遺伝的アルゴリズム（ＧＡｃ）を実行し、更に効率的に解を探索するものである。
【０１３９】
なお、この配置最適化問題処理方法は、ＧＡｃ＋（ＧＡｐ＋ＬＯ）と表記することができる。
このときの配置最適化問題処理装置１の動作を、図２５に示すフローチャートを用いて説明する。
まず、配置最適化問題処理装置１に、上記複数の配置要素９の初期配置結果（初期配置状態に関する情報）が入力される（ステップＤ１）。
【０１４０】
配置要素９の初期配置結果が入力されると、配置最適化問題処理装置１では、上記第１アルゴリズム実行ステップにより、初期配置結果のコピーを作ることにより遺伝的アルゴリズム（ＧＡｃ）の染色体の集団が準備される（ステップＤ２）。
そして、この遺伝的アルゴリズム（ＧＡｃ）の実行中に、更に第１アルゴリズム実行ステップにより、遺伝的アルゴリズム（ＧＡｐ）が実行されるとともに、第２アルゴリズム実行ステップにより、局所的疎密解消アルゴリズムが実行される（ステップＤ３〜Ｄ９）。
【０１４１】
即ち、上記第１アルゴリズム実行ステップでは、局所的疎密解消法（ＬＯ）のパラメータを遺伝子とする、遺伝的アルゴリズム（ＧＡｐ）の染色体の集団が準備される（ステップＤ３）。
続いて、第１アルゴリズム実行ステップでは、各染色体に対して、遺伝的アルゴリズム（ＧＡｐ）における遺伝オペレーションである交叉及び突然変異が施される（ステップＤ４，Ｄ５）。
【０１４２】
そして、第２アルゴリズム実行ステップでは、各染色体により表される分割幅で配置領域１０を分割して、局所的疎密解消法（ＬＯ）を実行することにより、疎密の解消が試みられ、局所的疎密解消法（ＬＯ）の結果に基づいて適応度値が計算される（ステップＤ６）。なお、局所的疎密解消法（ＬＯ）は、流体力学のアナロジーが適用されたアルゴリズム、又は、モーフィングのアナロジーが適用されたアルゴリズムを用いて実行される。
【０１４３】
さらに、第１アルゴリズム実行ステップでは、各染色体に対して、遺伝的アルゴリズム（ＧＡｐ）における遺伝オペレーションである選択を施して、大きな適応度値をもつ染色体が選ばれる（ステップＤ７）。その後、遺伝的アルゴリズム（ＧＡｐ）を行なうように定められた世代数を超えたかが判断される（ステップＤ８）。
そして、定められた世代数を超えていないと判断された場合〔即ち、まだ定められた世代数分の遺伝的アルゴリズム（ＧＡｐ）が実行されていないと判断された場合〕には、上記ステップＤ４以降の処理を繰り返し（ステップＤ８のＮＯルート）、定められた世代数を超えたと判断された場合〔即ち、定められた世代数分の遺伝的アルゴリズム（ＧＡｐ）が実行されたと判断された場合〕には、上記ステップＤ７で選ばれた染色体が、遺伝的アルゴリズム（ＧＡｐ）での最適な染色体であると決定される（ステップＤ８のＹＥＳルートからステップＤ９）。
【０１４４】
その後、第１アルゴリズム実行ステップでは、再度遺伝的アルゴリズム（ＧＡｃ）の実行に戻り、上記ステップＤ９で決定された遺伝的アルゴリズム（ＧＡｐ）の染色体により指定される配置領域１０の分割法により〔即ち、ステップＤ９で決定された遺伝的アルゴリズム（ＧＡｐ）の染色体により指定される幅で〕、遺伝的アルゴリズム（ＧＡｃ）の染色体である配置領域１０が分割される（ステップＤ１０）。
【０１４５】
さらに、第１アルゴリズム実行ステップでは、各染色体に対して、遺伝的アルゴリズム（ＧＡｃ）における遺伝オペレーションである交叉，突然変異及び選択が施される（ステップＤ１１〜Ｄ１３）。
そして、最高の適応度値をもつ染色体（最適な染色体）の適応度値が所定の基準値以上であるか、又は、配置結果の疎密が解消されたかどうかが判断される（ステップＤ１４）。
【０１４６】
そして、最適な染色体の適応度値が所定の基準値以上でない、又は、配置結果の疎密が解消されていないと判断された場合には、上記ステップＤ１０以降の処理を繰り返し（ステップＤ１４のＮＯルート）、最適な染色体の適応度値が所定の基準値以上である、又は、配置結果の疎密が解消されていると判断された場合には、その最適な染色体が配置最適化問題の解として出力されて、配置最適化問題処理装置１での処理が終了する（ステップＤ１４のＹＥＳルート）。
【０１４７】
このように、本発明の第４実施形態にかかる配置最適化問題処理方法によれば、前述した各実施形態と同様の効果を得ることができるほか、遺伝的アルゴリズム（ＧＡｃ）の実行中に、遺伝的アルゴリズム（ＧＡｐ）と局所的疎密解消法（ＬＯ）とを組み合わせて実行しているので、遺伝的アルゴリズム（ＧＡｃ）の更なる高速化を実現することができる。
【０１４８】
（ｂ８）その他
上述した第１，第３，第４実施形態では、縦方向又は横方向のいずれか一方の同一方向に分割された染色体（即ち配置領域１０）を用いて遺伝オペレーション（ＧＡｃ）を実行する場合について説明したが、それぞれ異なる方向に分割された染色体を用いて遺伝オペレーション（ＧＡｃ）を実行することもできる。
【０１４９】
この場合に用いられるモデルをアイランドモデルといい、図２６を用いてこのアイランドモデルについて説明する。
図２６に示すアイランドモデルは、縦方向に分割された染色体の集団２１を複数有する第１アイランド２０と、横方向に分割された染色体の集団２３を複数有する第２アイランド２２からなる。
【０１５０】
なお、第１アイランド２０は少なくとも一つの集団２１を有していればよく、第２アイランド２２は少なくとも一つの集団２３を有していればよい。
つまり、第１アルゴリズム実行ステップでは、遺伝的アルゴリズム（ＧＡｃ）を実行する際に、上記複数の配置要素９を配置する配置領域１０を複数の部分領域１０ａに縦方向に分割することにより複数の帯状領域に縦方向に分割された染色体の集団２１を少なくとも一つ有する第１アイランド２０と、上記複数の配置要素９を配置する配置領域１０を複数の部分領域１０ａに横方向に分割することにより複数の帯状領域に横方向に分割された染色体の集団２３を少なくとも一つ有する第２アイランド２２とを用いるようになっている。
【０１５１】
各集団２１，２３は、通常は独立して遺伝的アルゴリズム（ＧＡｃ）や局所的疎密解消法（ＬＯ）に基づいて発展していくが、遺伝的アルゴリズム（ＧＡｃ）を適当な世代数実行する毎に、第１アイランド２０の一つの集団２１及び第２アイランド２２の一つの集団２３から何らかの方法で染色体を選択して、分割方向の異なるこれらの染色体を親の染色体として遺伝オペレーションとしての交叉を実行して、その結果生じた子の染色体をそれぞれの集団２１，２３へ戻すこともできる。
【０１５２】
このとき、分割方向の異なる染色体間の交叉は、以下のように実行することができる。
（１）交叉の第１の方法
集団２１から選択した染色体は縦方向に分割されており、この染色体に局所的疎密解消法（ＬＯ）を施すと、ある特定の配置要素９は、それが属する帯状領域内で定められた方向に定められた量だけ移動する。このときの移動量をベクトルｘ1 ′とする。
【０１５３】
一方、集団２３から選択した染色体は横方向に分割されており、この染色体に局所的疎密解消法（ＬＯ）を施すと、当該特定の配置要素９は、それが属する帯状領域内で定められた方向に定められた量だけ移動する。このときの移動量をベクトルｘ2 ′とする。
そして、当該配置要素９の移動量を合成ベクトルｘ1 ′＋ｘ2 ′として求め、各親の染色体においてそれぞれ当該配置要素９をその移動量だけ移動させることにより、集団２１から選択した染色体と集団２３から選択した染色体との間で交叉を実行して子の染色体を生成し、生成した子の染色体をそれぞれ元の集団に戻す。
【０１５４】
即ち、第１アルゴリズム実行ステップでは、遺伝的アルゴリズム（ＧＡｃ）を実行する際に、第１アイランド２０に属する染色体に局所的疎密解消法（ＬＯ）を適用する一方、第２アイランド２２に属する染色体に局所的疎密解消法（ＬＯ）を適用することにより、上記染色体の各領域内である特定の配置要素９を移動させる。そして、第１アイランド２０に属する染色体及び第２アイランド２２に属する染色体における当該特定の配置要素９の移動量のベクトル和を求め、このベクトル和に応じて上記各染色体内で当該特定の配置要素９を移動させることにより、第１アイランド２０に属する染色体と第２アイランド２２に属する染色体との間で、遺伝オペレーションとしての交叉が実行される。
【０１５５】
（２）交叉の第２の方法
集団２１から選択した染色体は縦方向に分割された帯状領域を有しているが、この帯状領域を横方向に分割された帯状領域に読み替えて集団２３の染色体に組み込むことにより、集団２１から選択した染色体と集団２３から選択した染色体との間で交叉を実行して、子の染色体を生成する。
【０１５６】
例えば、集団２１から選択した染色体における縦方向に分割されたある帯状領域に配置要素９1 〜９3 が含まれるとすると、まず、集団２３から選択した横方向に分割された染色体において、これら配置要素９1 〜９3 を含む帯状領域を探し出す。
そして、横方向に分割された染色体において、これら配置要素９1 〜９3 を含む帯状領域を探し出した結果、配置要素９1 ，９2 は横方向に分割された帯状領域のうちのある帯状領域に含まれ、配置要素９3 はその他の帯状領域に含まれていたとする。また、配置要素９1 ，９2 が含まれる帯状領域には、その他の配置要素９4 も含まれていたとする。
【０１５７】
このとき、横方向に分割された染色体において、配置要素９1 ，９2 が含まれる帯状領域におけるその他の配置要素９4 を配置要素９3 と読み替えるとともに、その他の帯状領域に含まれている配置要素９3 を配置要素９4 と読み替えることにより、縦方向に分割された帯状領域を横方向に分割された帯状領域に読み替えることができる。
なお、同様にして、集団２３から選択した染色体における帯状領域を、縦方向に分割された帯状領域に読み替えて、集団２１の染色体に組み込むことにより、集団２１から選択した染色体と集団２３から選択した染色体との間で交叉を実行してもよい。
【０１５８】
即ち、第１アルゴリズム実行ステップでは、遺伝的アルゴリズム（ＧＡｃ）を実行する際に、第１アイランド２０（又は第２アイランド２２）に属する染色体における特定の配置要素９を含む帯状領域を抽出し、抽出した帯状領域を第２アイランド２２（又は第１アイランド２０）に属する染色体における帯状領域に読み替えて第２アイランド２２（又は第１アイランド２０）に戻すことにより、第１アイランド２０に属する染色体と第２アイランド２２に属する染色体との間で、遺伝オペレーションとしての交叉が実行される。
【０１５９】
このときの配置最適化問題処理装置１の動作を、図２７に示すフローチャートを用いて説明する。
まず、配置最適化問題処理装置１に、上記複数の配置要素９の初期配置結果（初期配置状態に関する情報）が入力される（ステップＥ１）。
この配置要素９の初期配置結果が入力されると、配置最適化問題処理装置１では、上記第１アルゴリズム実行ステップにより、初期配置結果のコピーを作ることにより遺伝的アルゴリズム（ＧＡｃ）の染色体の集団がＮ個準備される（ステップＥ２）。
【０１６０】
次に、第１アルゴリズム実行ステップでは、Ｎ個の集団をα個の集団とβ個の集団にわけ（即ち、α＋β＝Ｎ）、α個の集団の染色体は縦方向に分割する一方、β個の集団の染色体は横方向に分割することにより、縦方向に分割された染色体の集合２１をα個有する第１アイランド２０と、横方向に分割された染色体の集合２３をβ個有する第２アイランド２２とを形成する（ステップＥ３）。
【０１６１】
そして、第１アルゴリズム実行ステップでは、各集団２１，２３毎に、独立して遺伝的アルゴリズム（ＧＡｃ）を実行する（ステップＥ４）。
この遺伝的アルゴリズム（ＧＡｃ）の実行中には、定められた世代数が経過する毎に、同一方向に分割された染色体をもつ集団間での交叉が実施される（ステップＥ５）。即ち、第１アイランド２０内では、ある集団２１の染色体と他の集団２１の染色体との間で交叉が実行される一方、第２アイランド２２内では、ある集団２３の染色体と他の集団２３の染色体との間で交叉が実行される。
【０１６２】
さらに、定められた世代数が経過する毎に、異なる方向に分割された染色体をもつ集団間での交叉が実施される（ステップＥ６）。即ち、第１アイランド２０に属する集団２１の染色体と、第２アイランド２２に属する集団２３の染色体との間で交叉が実行される。なお、この際、各染色体に局所的疎密解消法（ＬＯ）も適用される。
そして、最高の適応度値をもつ染色体（最適な染色体）の適応度値が所定の基準値以上であるか、又は、配置結果の疎密が解消されたかどうかが判断される（ステップＥ７）。
【０１６３】
そして、最適な染色体の適応度値が所定の基準値以上でない、又は、配置結果の疎密が解消されていないと判断された場合には、上記ステップＥ４以降の処理を繰り返し（ステップＥ７のＮＯルート）、最適な染色体の適応度値が所定の基準値以上である、又は、配置結果の疎密が解消されていると判断された場合には、その最適な染色体が配置最適化問題の解として出力されて、配置最適化問題処理装置１での処理が終了する（ステップＥ７のＹＥＳルート）。
【０１６４】
このように、異なる方向に分割された染色体をもつ集団間での交叉を実施するアイランドモデルを採用すれば、集団２１，２３における解候補となる染色体の多様性を保持することができるので、最適解を効率的に探索することができ、配置要素９の疎密の解消をより効率的に行なうことができる。
さらに、上述した第１〜第４実施形態では、遺伝的アルゴリズム（ＧＡｃ，ＧＡｐ）を実行する中で局所的疎密解消法（ＬＯ）を実行する際に、第２アルゴリズム実行ステップが、それぞれ固定のアルゴリズム（流体力学のアナロジーが適用されたアルゴリズム、及び、モーフィングのアナロジーが適用されたアルゴリズム）を用いる場合について説明したが、世代毎に用いるアルゴリズムを変更することがより好ましい。なお、染色体毎に異なる局所的疎密解消法（ＬＯ）を適用してもよい。
【０１６５】
また、第２アルゴリズム実行ステップでは、配置領域１０を分割しない状態で局所的疎密解消法（ＬＯ）を実施してもよい。
さらに、第１アルゴリズム実行ステップでは、染色体（配置領域１０）を分割しない状態で、遺伝的アルゴリズム（ＧＡｃ，ＧＡｐ）の突然変異を実行してもよい。
なお、以下に、本発明を応用できる配置最適化問題の具体例を示す。
【０１６６】
（１）ＬＳＩの設計の際のセル配置問題
セルは大きさをもつため、一般にはセルは重なってはならないという制約条件がある。
ここで、この制約条件を考慮して非線形計画法（例えば山登り法等）により最適なセル配置を求めるのは、原理的には可能であるが、実用的な規模のセル配置最適化問題を処理する場合には、一般にはより効率良く最適なセル配置を求めるのは難しい。
【０１６７】
このため、この制約条件を考慮しないで非線形計画法によりセル配置〔図２８（ａ）参照〕を求め、その後、本発明で説明したような方法によりセルの疎密を解消すれば〔図２８（ｂ）参照〕、より効率的に最適なセル配置を得ることができる。
（２）フロアプラン
フロアプランとは、ＬＳＩの配置問題の一種であり、配置するセルの面積は定まっているが、セルの各辺の長さが可変である問題のことをいう。
【０１６８】
この問題を解く際にも、本発明で説明したような方法を用いて、疎密の解消を行なうことができる〔図２９（ａ），図２９（ｂ）参照〕。
【図面の簡単な説明】
【０１６９】
【図１】本発明の配置最適化問題処理方法を実行する配置最適化問題処理装置の構成を示すブロック図である。
【図２】本発明の配置最適化問題処理方法を説明するためのフローチャートである。
【図３】（ａ），（ｂ）は、それぞれ配置領域を分割して部分領域を形成する様子を示す図である。
【図４】（ａ），（ｂ）は、それぞれ中間配置状態にある配置要素の一例を示す図である。
【図５】（ａ），（ｂ）は、それぞれ中間配置状態にある配置要素の疎密を解消した結果を示す図である。
【図６】本発明の第１実施形態にかかる配置最適化問題処理方法にて用いられる遺伝的アルゴリズム（ＧＡｃ）における交叉の一例を示す図である。
【図７】本発明の第１実施形態にかかる配置最適化問題処理方法にて用いられる遺伝的アルゴリズム（ＧＡｃ）における突然変異の一例を示す図である。
【図８】一般的な遺伝的アルゴリズムについて説明するための図である。
【図９】一般的な遺伝的アルゴリズムについて説明するための図である。
【図１０】一般的な遺伝的アルゴリズムについて説明するための図である。
【図１１】一般的な遺伝的アルゴリズムについて説明するための図である。
【図１２】（ａ）〜（ｄ）は、それぞれ本発明の第１実施形態にかかる配置最適化問題処理方法にて用いられる局所的疎密解消法（ＬＯ）を実行する際の配置領域の分割方法を示す図である。
【図１３】（ａ）〜（ｃ）は、それぞれ本発明の第１実施形態にかかる配置最適化問題処理方法にて用いられる流体力学のアナロジーが適用されたアルゴリズムを用いた配置要素の移動方法の一例を示す図である。
【図１４】（ａ），（ｂ）は、それぞれ本発明の第１実施形態にかかる配置最適化問題処理方法にて用いられる流体力学のアナロジーが適用されたアルゴリズムを用いた配置要素の移動方法の他の例を示す図である。
【図１５】（ａ），（ｂ）は、それぞれ本発明の第１実施形態にかかる配置最適化問題処理方法にて用いられる流体力学のアナロジーが適用されたアルゴリズムを用いた配置要素の移動方法の他の例を示す図である。
【図１６】（ａ）〜（ｅ）は、それぞれ本発明の第１実施形態にかかる配置最適化問題処理方法にて用いられる流体力学のアナロジーが適用されたアルゴリズムを用いた配置要素の移動方法の他の例を示す図である。
【図１７】本発明の第１実施形態にかかる配置最適化問題処理方法にて用いられる流体力学のアナロジーが適用されたアルゴリズムを用いた配置要素の移動方法の他の例を示す図である。
【図１８】本発明の第１実施形態にかかる配置最適化問題処理方法の他の例を説明するためのフローチャートである。
【図１９】（ａ），（ｂ）は、それぞれ本発明の第１実施形態の変形例にかかる配置最適化問題処理方法にて用いられるモーフィングのアナロジーが適用されたアルゴリズムを用いた配置要素の移動方法の一例を示す図である。
【図２０】本発明の第２実施形態にかかる配置最適化問題処理方法にて用いられる遺伝的アルゴリズム（ＧＡｐ）における染色体の一例を示す図である。
【図２１】本発明の第２実施形態にかかる配置最適化問題処理方法にて用いられる遺伝的アルゴリズム（ＧＡｐ）における交叉の一例を示す図である。
【図２２】本発明の第２実施形態にかかる配置最適化問題処理方法にて用いられる遺伝的アルゴリズム（ＧＡｐ）における突然変異の一例を示す図である。
【図２３】本発明の第２実施形態にかかる配置最適化問題処理方法の他の例を説明するためのフローチャートである。
【図２４】本発明の第３実施形態にかかる配置最適化問題処理方法を説明するためのフローチャートである。
【図２５】本発明の第４実施形態にかかる配置最適化問題処理方法を説明するためのフローチャートである。
【図２６】アイランドモデルを示す図である。
【図２７】アイランドモデルを用いた配置最適化問題処理方法を説明するためのフローチャートである。
【図２８】（ａ），（ｂ）は、それぞれ本発明をセル配置問題に適用した例を示す図である。
【図２９】（ａ），（ｂ）は、それぞれ本発明をフロアプランに適用した例を示す図である。
【符号の説明】
【０１７０】
１ 配置最適化問題処理装置
４ ＣＰＵ
５ 表示制御部
５Ａ 表示部
６ 外部ファイル読出書込部
６Ａ 外部ファイル
７Ｂ 入力部
７Ｄ 入力制御部
８ ディスク装置
９，９ａ 配置要素（要素）
１０ 配置領域（空間）
１０ａ 部分領域（部分空間）
１１〜１８，１８′ 染色体
２０ 第１アイランド
２１，２３ 集団
２２ 第２アイランド
【図１】
2007052799.tif 000004
【図２】
2007052799.tif 000005
【図３】
2007052799.tif 000006
【図４】
2007052799.tif 000007
【図５】
2007052799.tif 000008
【図６】
2007052799.tif 000009
【図７】
2007052799.tif 000010
【図８】
2007052799.tif 000011
【図９】
2007052799.tif 000012
【図１０】
2007052799.tif 000013
【図１１】
2007052799.tif 000014
【図１２】
2007052799.tif 000015
【図１３】
2007052799.tif 000016
【図１４】
2007052799.tif 000017
【図１５】
2007052799.tif 000018
【図１６】
2007052799.tif 000019
【図１７】
2007052799.tif 000020
【図１８】
2007052799.tif 000021
【図１９】
2007052799.tif 000022
【図２０】
2007052799.tif 000023
【図２１】
2007052799.tif 000024
【図２２】
2007052799.tif 000025
【図２３】
2007052799.tif 000026
【図２４】
2007052799.tif 000027
【図２５】
2007052799.tif 000028
【図２６】
2007052799.tif 000029
【図２７】
2007052799.tif 000030
【図２８】
2007052799.tif 000031
【図２９】
2007052799.tif 000032
【手続補正書】
【提出日】平成18年10月24日(2006.10.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、
上記複数の要素の初期配置状態に関する情報が該コンピュータに入力されると、該ＣＰＵによって遺伝的アルゴリズムを実行して、該初期配置状態にある上記複数の要素の疎密を解消する第１アルゴリズム実行ステップと、
該第１アルゴリズム実行ステップにて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が該コンピュータに入力されると、該ＣＰＵによって局所的疎密解消アルゴリズムを実行して、該中間配置状態にある上記複数の要素の疎密を更に解消する第２アルゴリズム実行ステップとをそなえ、
該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いることにより、
該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消することを特徴とする、回路配置最適化問題処理方法。
【請求項２】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、該染色体における上記複数の部分空間の中から選択された少なくとも一つの部分空間を、他の染色体における当該部分空間に対応する部分空間と交換することにより、遺伝オペレーションとしての交叉を実行することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項３】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、該染色体における上記複数の部分空間の中の特定の部分空間の方が、他の染色体における当該部分空間に対応する部分空間よりも疎密が解消されている場合には、該染色体における当該部分空間を該他の染色体における当該部分空間に対応する部分空間に張り付けることにより、遺伝オペレーションとしての交叉を実行することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項４】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、上記複数の部分空間の中の少なくとも一つの部分空間内において上記複数の要素のうちの少なくとも一つの要素を移動させることにより、遺伝オペレーションとしての突然変異を実行することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項５】
該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、上記複数の要素の疎密が小さい染色体が大きな適応度値をとりうるような適応度値関数を用いて、遺伝オペレーションとしての選択を実行することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項６】
該第２アルゴリズム実行ステップが、上記部分空間毎に上記複数の要素の疎密を解消することを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項７】
該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムとして、流体力学のアナロジーが適用されたアルゴリズムを用いることを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項８】
該第２アルゴリズム実行ステップが、該中間配置状態にある上記複数の要素のうちの少なくとも一つの要素を、要素密度が高い場所から要素密度が低い場所へと移動させることにより、該流体力学のアナロジーが適用されたアルゴリズムを実行することを特徴とする、請求項７記載の回路配置最適化問題処理方法。
【請求項９】
該第２アルゴリズム実行ステップが、上記分割した部分空間内において、当該部分空間内に含まれる上記複数の要素のうちの少なくとも一つの要素を、要素密度が高い場所から要素密度が低い場所へと移動させることを特徴とする、請求項８記載の回路配置最適化問題処理方法。
【請求項１０】
該第２アルゴリズム実行ステップが、上記複数の要素間の近傍性を保存しながら、上記複数の要素のうちの少なくとも一つの要素を移動させることを特徴とする、請求項８記載の回路配置最適化問題処理方法。
【請求項１１】
該第２アルゴリズム実行ステップが、上記複数の要素間の順序性を保存しながら、上記複数の要素のうちの少なくとも一つの要素を移動させることを特徴とする、請求項８記載の回路配置最適化問題処理方法。
【請求項１２】
該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムとして、モーフィングのアナロジーが適用されたアルゴリズムを用いることを特徴とする、請求項１記載の回路配置最適化問題処理方法。
【請求項１３】
該第２アルゴリズム実行ステップが、該中間配置状態にある上記複数の要素に関する情報に基づいてモーフィング中心部を決定し、上記複数の要素のうちの少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させることにより、該モーフィングのアナロジーが適用されたアルゴリズムを実行することを特徴とする、請求項１２記載の回路配置最適化問題処理方法。
【請求項１４】
該第２アルゴリズム実行ステップが、上記部分空間毎に該モーフィング中心部を決定し、上記部分空間内において、当該部分空間内に含まれる上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させることを特徴とする、請求項１３記載の回路配置最適化問題処理方法。
【請求項１５】
該第２アルゴリズム実行ステップが、上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させる際に、該モーフィング中心部から移動対象となる要素までの距離を線形的に拡大することを特徴とする、請求項１３記載の回路配置最適化問題処理方法。
【請求項１６】
該第２アルゴリズム実行ステップが、上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させる際に、該モーフィング中心部から移動対象となる要素までの距離を非線形的に拡大することを特徴とする、請求項１３記載の回路配置最適化問題処理方法。
【請求項１７】
接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、
該ＣＰＵによって遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、
該ＣＰＵによって局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえ、
該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いて該遺伝的アルゴリズムを実行し、
該第２アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行している中で、該局所的疎密解消アルゴリズムを実行することにより、
該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消することを特徴とする、回路配置最適化問題処理方法。
【請求項１８】
接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、
該ＣＰＵによって遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、
該ＣＰＵによって局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえ、
該第１アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行する際に用いるパラメータを遺伝子として表現し、該パラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いることにより、該遺伝的アルゴリズムを実行している中で、更に、該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いた遺伝的アルゴリズムを実行するとともに、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行することを特徴とする、回路配置最適化問題処理方法。
【請求項１９】
接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、
該ＣＰＵによって遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、
該ＣＰＵによって局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえ、
該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いることにより、該遺伝的アルゴリズムを実行している中で、更に、該第１アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行する際に用いるパラメータを遺伝子として表現し、該パラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いた遺伝的アルゴリズムを実行するとともに、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行することを特徴とする、回路配置最適化問題処理方法。
【請求項２０】
接続関係が規定された複数の要素を所要の空間に配置するに際し、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題をコンピュータにより処理するための回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
該回路配置最適化問題処理プログラムが、
上記複数の要素の初期配置状態に関する情報が入力されると、遺伝的アルゴリズムを実行して、該初期配置状態にある上記複数の要素の疎密を解消する第１アルゴリズム実行手段、及び、
該第１アルゴリズム実行手段にて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が入力されると、局所的疎密解消アルゴリズムを実行して、該中間配置状態にある上記複数の要素の疎密を更に解消する第２アルゴリズム実行手段として該コンピュータを機能させるとともに、
該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いるように該コンピュータを機能させることを特徴とする、回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
このため、本発明の回路配置最適化問題処理方法は、接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、上記複数の要素の初期配置状態に関する情報が該コンピュータに入力されると、該ＣＰＵによって遺伝的アルゴリズムを実行して、該初期配置状態にある上記複数の要素の疎密を解消する第１アルゴリズム実行ステップと、該第１アルゴリズム実行ステップにて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が該コンピュータに入力されると、該ＣＰＵによって局所的疎密解消アルゴリズムを実行して、該中間配置状態にある上記複数の要素の疎密を更に解消する第２アルゴリズム実行ステップとをそなえ、該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いることにより、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消することを特徴としている（請求項１）。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
このとき、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、該染色体における上記複数の部分空間の中から選択された少なくとも一つの部分空間を、他の染色体における当該部分空間に対応する部分空間と交換することにより、遺伝オペレーションとしての交叉を実行することができる（請求項２）。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
また、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、該染色体における上記複数の部分空間の中の特定の部分空間の方が、他の染色体における当該部分空間に対応する部分空間よりも疎密が解消されている場合には、該染色体における当該部分空間を該他の染色体における当該部分空間に対応する部分空間に張り付けることにより、遺伝オペレーションとしての交叉を実行してもよい（請求項３）。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
さらに、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、上記複数の部分空間の中の少なくとも一つの部分空間内において上記複数の要素のうちの少なくとも一つの要素を移動させることにより、遺伝オペレーションとしての突然変異を実行することができる（請求項４）。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
また、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、上記複数の要素の疎密が小さい染色体が大きな適応度値をとりうるような適応度値関数を用いて、遺伝オペレーションとしての選択を実行することができる（請求項５）。
そして、本発明の回路配置最適化問題処理方法においては、該第２アルゴリズム実行ステップが、上記部分空間毎に上記複数の要素の疎密を解消することを特徴としている（請求項６）。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
ここで、該第２アルゴリズム実行ステップは、該局所的疎密解消アルゴリズムとして、流体力学のアナロジーが適用されたアルゴリズムを用いることができる（請求項７）。
具体的には、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素のうちの少なくとも一つの要素を、要素密度が高い場所から要素密度が低い場所へと移動させることにより、該流体力学のアナロジーが適用されたアルゴリズムを実行することができる（請求項８）。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
このとき、該第２アルゴリズム実行ステップは、上記分割した部分空間内において、当該部分空間内に含まれる上記複数の要素のうちの少なくとも一つの要素を、要素密度が高い場所から要素密度が低い場所へと移動させることを特徴としている（請求項９）。
ここで、該第２アルゴリズム実行ステップは、上記複数の要素間の近傍性を保存しながら、上記複数の要素のうちの少なくとも一つの要素を移動させることができる（請求項１０）。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
また、該第２アルゴリズム実行ステップは、上記複数の要素間の順序性を保存しながら、上記複数の要素のうちの少なくとも一つの要素を移動させることをもできる（請求項１１）。
さらに、該第２アルゴリズム実行ステップは、該局所的疎密解消アルゴリズムとして、モーフィングのアナロジーが適用されたアルゴリズムを用いることもできる（請求項１２）。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
具体的には、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素に関する情報に基づいてモーフィング中心部を決定し、上記複数の要素のうちの少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させることにより、該モーフィングのアナロジーが適用されたアルゴリズムを実行することができる（請求項１３）。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
このとき、該第２アルゴリズム実行ステップは、上記部分空間毎に該モーフィング中心部を決定し、上記部分空間内において、当該部分空間内に含まれる上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させることを特徴としている（請求項１４）。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
ここで、該第２アルゴリズム実行ステップは、上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させる際に、該モーフィング中心部から移動対象となる要素までの距離を線形的に拡大することができる（請求項１５）。
また、該第２アルゴリズム実行ステップは、上記複数の要素の少なくとも一つの要素を該モーフィング中心部から離隔した場所へと移動させる際に、該モーフィング中心部から移動対象となる要素までの距離を非線形的に拡大することもできる（請求項１６）。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
さらに、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素の疎密を解消する際に、疎密解消対象となる要素を逐次添加していくこともできる。
また、上記複数の要素の中に移動させることができない固定要素がある場合には、該第２アルゴリズム実行ステップは、該固定要素も疎密解消対象となる要素とみなして、該中間配置状態にある上記複数の要素の疎密を解消すればよい。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
さらに、上記複数の要素の中に他の要素に比べて該空間を占める割合が大きな要素がある場合には、該第２アルゴリズム実行ステップは、該大きな要素の移動量を小さくして、該中間配置状態にある上記複数の要素の疎密を解消すればよい。
また、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素の疎密を解消する際に、移動対象となる要素を一挙に移動させることができる。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
さらに、該第２アルゴリズム実行ステップは、該中間配置状態にある上記複数の要素の疎密を解消する際に、移動対象となる要素を徐々に移動させることができる。
その他、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、上記複数の要素を配置する該空間を複数の部分空間に縦方向に分割することにより複数の領域に縦方向に分割された該染色体の集団を少なくとも一つ有する第１アイランドと、上記複数の要素を配置する該空間を複数の部分空間に横方向に分割することにより複数の領
域に横方向に分割された該染色体の集団を少なくとも一つ有する第２アイランドとを用いてもよい。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
このときは、該第１アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行する際に、該第１アイランドに属する該染色体及び該第２アイランドに属する該染色体にそれぞれ局所的疎密解消アルゴリズムを適用することにより上記各領域内である特定の要素を移動させ、該第１アイランドに属する該染色体及び該第２アイランドに属する該染色体における当該特定の要素の移動量のベクトル和に応じて上記各染色体内で当該特定の要素を移動させることにより、該第１アイランドに属する該染色体と該第２アイランドに属する該染色体との間で、遺伝オペレーションとしての交叉を実行すればよい。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
また、該第１アルゴリズム実行ステップは、該遺伝的アルゴリズムを実行する際に、該第１アイランド又は該第２アイランドに属する該染色体における特定の要素を含む領域を抽出し、抽出した該領域を該第２アイランド又は該第１アイランドに属する該染色体における該領域に読み替えて該第２アイランド又は該第１アイランドに戻すことにより、該第１アイランドに属する該染色体と該第２アイランドに属する該染色体との間で、遺伝オペレーションとしての交叉を実行してもよい。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
つまり、本発明の回路配置最適化問題処理方法は、接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、該ＣＰＵによって遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、該ＣＰＵによって局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえ、該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いて該遺伝的アルゴリズムを実行し、該第２アルゴリズム実行ステップが、該遺伝的アルゴリズムを実行している中で、該局所的疎密解消アルゴリズムを実行することにより、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消することを特徴としている（請求項１７）。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】削除
【補正の内容】
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
また、本発明の回路配置最適化問題処理方法は、接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、該ＣＰＵによって遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、該ＣＰＵによって局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえ、該第１アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行する際に用いるパラメータを遺伝子として表現し、該パラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いることにより、該遺伝的アルゴリズムを実行している中で、更に、該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いた遺伝的アルゴリズムを実行するとともに、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行することを特徴としている（請求項１８）。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
さらに、本発明の回路配置最適化問題処理方法は、接続関係が規定された複数の要素を所要の空間に配置するに際し、ＣＰＵをそなえたコンピュータを用いて、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題処理方法であって、該ＣＰＵによって遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、該ＣＰＵによって局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえ、該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いることにより、該遺伝的アルゴリズムを実行している中で、更に、該第１アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行する際に用いるパラメータを遺伝子として表現し、該パラメータを決定する問題の解候補として当該遺伝子の配列からなる染色体を用いた遺伝的アルゴリズムを実行するとともに、該第２アルゴリズム実行ステップが、該局所的疎密解消アルゴリズムを実行することを特徴としている（請求項１９）。
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
ところで、本発明の回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、接続関係が規定された複数の要素を所要の空間に配置するに際し、該接続関係を維持しながら初期配置状態にある上記複数の要素の疎密を解消するための回路配置最適化問題をコンピュータにより処理するための回路配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、該回路配置最適化問題処理プログラムが、上記複数の要素の初期配置状態に関する情報が入力されると、遺伝的アルゴリズムを実行して、該初期配置状態にある上記複数の要素の疎密を解消する第１アルゴリズム実行手段、及び、該第１アルゴリズム実行手段にて疎密が解消された後の上記複数の要素の中間配置状態に関する情報が入力されると、局所的疎密解消アルゴリズムを実行して、該中間配置状態にある上記複数の要素の疎密を更に解消する第２アルゴリズム実行手段として該コンピュータを機能させるとともに、該第１アルゴリズム実行ステップが、該空間を複数の部分空間に分割するとともに、当該部分空間における上記複数の要素の配置状態を遺伝子として表現し、当該遺伝子の配列からなる染色体を、該空間に上記複数の要素を配置する問題の解候補として用いるように該コンピュータを機能させることを特徴としている（請求項２０）。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】削除
【補正の内容】
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
以上詳述したように、本発明によれば、接続関係が規定された複数の要素を所要の空間に配置するに際し、遺伝的アルゴリズムを実行する第１アルゴリズム実行ステップと、局所的疎密解消アルゴリズムを実行する第２アルゴリズム実行ステップとをそなえることにより、問題規模の大きい要素配置最適化問題を処理する場合にも、高速に要素の疎密の解消を行なうことができる利点がある（請求項１〜９，１２〜１４，１７〜２０）。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
また、本発明の回路配置最適化問題処理方法によれば、第２アルゴリズム実行ステップが、複数の要素間の近傍性を保存しながら要素を移動させたり、複数の要素間の順序性を保存しながら要素を移動させたりできるので、処理できる回路配置最適化問題の範囲を拡大することができる（請求項１０，１１）。
さらに、第２アルゴリズム実行ステップが、モーフィング中心部から移動対象となる要素までの距離を線形的に拡大したり、モーフィング中心部から移動対象となる要素までの距離を非線形的に拡大したりできるので、これによっても処理できる配置最適化問題の範囲を拡大することができる（請求項１５，１６）。
【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
また、第２アルゴリズム実行ステップが、疎密解消対象となる要素を逐次添加したり、固定配置要素も疎密解消対象となる要素とみなしたり、大きな要素の移動量を小さくしたり、移動対象となる要素を一挙に移動させたり、移動対象となる要素を徐々に移動させたりできるので、更に処理できる配置最適化問題の範囲を拡大することができる。
【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
さらに、第１アルゴリズム実行ステップが、遺伝的アルゴリズムを実行する際に、縦方向に分割された染色体の集団を有する第１アイランドと、横方向に分割された染色体の集団を有する第２アイランドとを用いることもできるので、集団における解候補となる染色体の多様性を保持することができ、最適解を効率的に探索して、要素の疎密の解消をより効率的に行なうことができる。