(57)【特許請求の範囲】
【請求項１】
系統空間に接続関係が示された複数のノードを発生空間に配置する配置最適化問題を、コンピュータを用いて処理する方法であって、
該コンピュータの入力部からの指示に応じて、該コンピュータのＣＰＵが、
該複数のノードをグループ化して、ノードの集合からなるハイパーノードを複数形成するハイパーノード形成ステップと、
該ハイパーノード形成ステップにて形成された該複数のハイパーノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、遺伝的アルゴリズムを実行することにより、該複数のハイパーノードを該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のハイパーノードを該発生空間に配置するハイパーノード配置ステップと、
該ハイパーノード配置ステップにて得られた該複数のハイパーノードの位置及び形状をもとにして、該複数のノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、更に遺伝的アルゴリズムを実行することにより、該複数のノードを最適な状態で該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のノードを該発生空間に配置するノード最適配置ステップとを実行することにより、該複数のノードの配置最適化問題を処理するとともに、
該ノード最適配置ステップが、該ハイパーノード配置ステップで求められた解のうちの最適解が目的とする条件を満たしていない場合に、当該求められた解のうちの最適解以外の解に基づいて、該複数のノードを該発生空間に配置する問題の解を求めることを特徴とする、配置最適化問題処理方法。
【請求項２】
該ハイパーノード配置ステップが、該ハイパーノードを配置する際の制約条件を考慮して、該複数のハイパーノードを該発生空間に配置することを特徴とする、請求項１記載の配置最適化問題処理方法。
【請求項３】
該ハイパーノードが、該ハイパーノードを構成する複数のノードの部分的な集合からなるサブハイパーノードを複数そなえ、
該ハイパーノードにおける該制約条件を、該サブハイパーノードにおける制約条件に基づいて求める制約条件探索ステップをそなえたことを特徴とする、請求項２記載の配置最適化問題処理方法。
【請求項４】
該発生空間が２次元空間である場合に、上記ハイパーノード配置ステップ及びノード最適配置ステップが、それぞれ上記ハイパーノード及びノードの形状を２次元の形状に規定して上記ハイパーノード及びノードを該発生空間に配置することを特徴とする、請求項１記載の配置最適化問題処理方法。
【請求項５】
該発生空間が長方形である場合に、上記ハイパーノード配置ステップ及びノード最適配置ステップにおいて、それぞれ上記ハイパーノード及びノードの形状を長方形に規定して上記ハイパーノード及びノードを該発生空間に配置する際に、
上記ハイパーノード配置ステップ及びノード最適配置ステップが、
それぞれ、上記ハイパーノード及びノードを該長方形の中心座標に関する情報と該長方形の縦／横比に関する情報とから構成される遺伝子として表現し、該発生空間に上記複数のハイパーノード及びノードを配置する問題の解候補として当該遺伝子の配列からなる染色体を用いて、該遺伝的アルゴリズムを実行することを特徴とする、請求項１記載の配置最適化問題処理方法。
【請求項６】
該遺伝的アルゴリズムを実行する際に、該染色体に、遺伝オペレーションとして、該染色体を構成する該遺伝子における該長方形の中心座標に関する情報及び該長方形の縦／横比に関する情報を他の染色体を構成する該遺伝子における当該各情報と置き換えた張り付け交叉が施されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項７】
該遺伝的アルゴリズムを実行する際に、該染色体に、遺伝オペレーションとして、該染色体を構成する該遺伝子における該長方形の中心座標に関する情報を他の染色体を構成する該遺伝子における当該情報と置き換えた張り付け交叉が施されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項８】
該張り付け交叉が、該長方形の中心座標に関する情報の重み付き平均に基づくことを特徴とする、請求項７記載の配置最適化問題処理方法。
【請求項９】
該遺伝的アルゴリズムを実行する際に、該染色体に、遺伝オペレーションとして、該染色体を構成する該遺伝子における該長方形の縦／横比に関する情報を他の染色体を構成する該遺伝子における当該情報と置き換えた張り付け交叉が施されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項１０】
該張り付け交叉が、該長方形の縦／横比に関する情報の重み付き平均に基づくことを特徴とする、請求項９記載の配置最適化問題処理方法。
【請求項１１】
該遺伝的アルゴリズムを実行する際に、該染色体に、遺伝オペレーションとして、該染色体を構成する該遺伝子における該長方形の縦／横比に関する情報を変化させた突然変異が施されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項１２】
該突然変異において、該長方形の縦／横比に関する情報を一定の割合で増加又は減少させることを特徴とする、請求項１１記載の配置最適化問題処理方法。
【請求項１３】
該突然変異において、該長方形の縦／横比に関する情報を一定の割合で増加させるか減少させるかを、確率的に決定することを特徴とする、請求項１２記載の配置最適化問題処理方法。
【請求項１４】
該遺伝的アルゴリズムを実行する際に、該染色体に、遺伝オペレーションとして、該染色体を構成する該遺伝子における該長方形の中心座標に関する情報を変化させた突然変異が施されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項１５】
該突然変異において、確率的に選択された数値を該長方形の中心座標に関する情報に加算して、該長方形の中心座標に関する情報を変化させることを特徴とする、請求項１４記載の配置最適化問題処理方法。
【請求項１６】
該遺伝的アルゴリズムを実行する際に、該染色体に遺伝オペレーションとしての選択が施される前に、該発生空間に配置された該複数のハイパーノード同士を接続する配線の長さの総和を考慮して、該染色体の適応度値が算出されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項１７】
該遺伝的アルゴリズムを実行する際に、該染色体に遺伝オペレーションとしての選択が施される前に、該発生空間に配置された該複数のハイパーノード同士の重なり部分の面積の総和を考慮して、該染色体の適応度値が算出されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項１８】
該遺伝的アルゴリズムを実行する際に、該染色体に遺伝オペレーションとしての選択が施される前に、該発生空間に配置された該複数のハイパーノード同士を接続する配線の長さの総和及び該複数のハイパーノード同士の重なり部分の面積の総和を考慮して、該染色体の適応度値が算出されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項１９】
該適応度値の算出が、該複数のハイパーノード同士を接続する配線の長さの総和及び該複数のハイパーノード同士の重なり部分の面積の総和のいずれかに重み付け演算を施して行なわれることを特徴とする、請求項１８記載の配置最適化問題処理方法。
【請求項２０】
該遺伝的アルゴリズムを実行する際に、該染色体に遺伝オペレーションとしての選択が施される前に、該発生空間に配置された該複数のハイパーノード同士の隙間部分の面積の総和を考慮して、該染色体の適応度値が算出されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項２１】
該遺伝的アルゴリズムを実行する際に、該染色体に遺伝オペレーションとしての選択が施される前に、該発生空間に配置された該複数のハイパーノード同士を接続する配線の長さの総和及び該複数のハイパーノード同士の隙間部分の面積の総和を考慮して、該染色体の適応度値が算出されることを特徴とする、請求項５記載の配置最適化問題処理方法。
【請求項２２】
該適応度値の算出が、該複数のハイパーノード同士を接続する配線の長さの総和及び該複数のハイパーノード同士の隙間部分の面積の総和のいずれかに重み付け演算を施して行なわれることを特徴とする、請求項２１記載の配置最適化問題処理方法。
【請求項２３】
２次元以上の空間に複数のエレメントを配置する配置最適化問題を、コンピュータを用いて処理する方法であって、
該コンピュータの入力部からの指示に応じて、該コンピュータのＣＰＵが、
該複数のエレメントをグループ化して、エレメントの集合からなるハイパーエレメントを複数形成するハイパーエレメント形成ステップと、
該ハイパーエレメント形成ステップにて形成された該複数のハイパーエレメントの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、遺伝的アルゴリズムを実行することにより、該複数のハイパーエレメントを該空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のハイパーエレメントを該空間に配置するハイパーエレメント配置ステップと、
該ハイパーエレメント配置ステップにて得られた該複数のハイパーエレメントの位置及び形状をもとにして、該複数のエレメントの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、更に遺伝的アルゴリズムを実行することにより、該複数のエレメントを最適な状態で該空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のエレメントを該空間に配置するエレメント最適配置ステップとを実行することにより、該複数のエレメントの配置最適化問題を処理するとともに、
該エレメント最適配置ステップが、該ハイパーエレメント配置ステップで求められた解のうちの最適解が目的とする条件を満たしていない場合に、当該求められた解のうちの最適解以外の解に基づいて、該複数のエレメントを該発生空間に配置する問題の解を求めることを特徴とする、配置最適化問題処理方法。
【請求項２４】
系統空間に接続関係が示された複数のノードを発生空間に最適に配置するノード配置最適化問題を処理する配置最適化問題処理装置であって、
入力部と、
該入力部からの指示に応じて、該複数のノードをグループ化して、ノードの集合からなるハイパーノードを複数形成するハイパーノード形成部と、
該入力部からの指示に応じて、該ハイパーノード形成部にて形成された該複数のハイパーノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、遺伝的アルゴリズムを実行することにより、該複数のハイパーノードを該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のハイパーノードを該発生空間に配置するハイパーノード配置部と、
該入力部からの指示に応じて、該ハイパーノード配置部により得られた該複数のハイパーノードの位置及び形状をもとにして、該複数のノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、更に遺伝的アルゴリズムを実行することにより、該複数のノードを最適な状態で該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のノードを該発生空間に配置するノード最適配置部とをそなえて構成されるとともに、
該ノード最適配置部が、該ハイパーノード配置部により求められた解のうちの最適解が目的とする条件を満たしていない場合に、当該求められた解のうちの最適解以外の解に基づいて、該複数のノードを該発生空間に配置する問題の解を求めることを特徴とする、配置最適化問題処理装置。
【請求項２５】
系統空間に接続関係が示された複数のノードを発生空間に最適に配置するノード配置最適化問題をコンピュータにより処理するための配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
該配置最適化問題処理プログラムが、該コンピュータのＣＰＵを、
該コンピュータの入力部からの指示に応じて、該複数のノードをグループ化して、ノードの集合からなるハイパーノードを複数形成するハイパーノード形成部、
該入力部からの指示に応じて、該ハイパーノード形成部にて形成された該複数のハイパーノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、遺伝的アルゴリズムを実行することにより、該ハイパーノード形成部により形成された該複数のハイパーノードを該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のハイパーノードを該発生空間に配置するハイパーノード配置部、および、
該入力部からの指示に応じて、該ハイパーノード配置部により得られた該複数のハイパーノードの位置及び形状をもとにして、該複数のノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、更に遺伝的アルゴリズムを実行することにより、該複数のノードを最適な状態で該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のノードを該発生空間に配置するノード最適配置部として機能させるとともに、
該ノード最適配置部が、該ハイパーノード配置部により求められた解のうちの最適解が目的とする条件を満たしていない場合に、当該求められた解のうちの最適解以外の解に基づいて、該複数のノードを該発生空間に配置する問題の解を求めるように機能させることを特徴とする、配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
（目次）
発明の属する技術分野
従来の技術（図２２，図２３）
発明が解決しようとする課題
課題を解決するための手段
発明の実施の形態
・（ａ）本発明の一実施形態にかかる配置最適化問題処理装置の構成（図１，図２）
・（ｂ）本発明の一実施形態にかかる配置最適化問題処理装置の動作（図３〜図８，図１３〜図２１）
・（ｃ）配置最適化問題の具体例（図９〜図１２）
・（ｄ）その他
発明の効果
【０００２】
【発明の属する技術分野】
本発明は、例えば大規模集積回路（ＬＳＩ；large scale integration)上の各回路を最適な状態で配置する回路配置最適化問題、より一般的には、２次元以上の空間に複数のノード（又はエレメント）を最適な状態で配置するノード配置最適化問題（又はエレメント配置最適化問題）を処理する際に用いて好適な、配置最適化問題処理方法及び装置並びに配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【０００３】
【従来の技術】
ノード配置最適化問題は、具体的には、系統空間に接続関係が示された複数のノードを発生空間に最適な状態で配置（マッピング）する問題であり、グラフマッピング問題と言われるものである。
まず、系統空間における複数のノードの接続関係を図２２に示す。この図２２において、符号１３０ａ〜１３０ｈは、発生空間における配置が既に決まっている固定ノードを示し、符号１００〜１０２，１１０，１１１，１２０〜１２２は、発生空間における最適配置を求めるべき非固定ノードを示す。また、符号１０００は系統空間を示す。
【０００４】
系統空間１０００においては、複数のノード間の接続関係がグラフ１００１として与えられており、このグラフ１００１においては、各ノード１３０ａ〜１３０ｈ，１００〜１０２，１１０，１１１，１２０〜１２２が頂点とみなされるとともに、各ノード間の接続関係（図２２に示す両側矢印）が頂点間の辺とみなされる。なお、図２２では、各ノード間の結合強度をこの両側矢印の太さにより示している。
【０００５】
ここで、複数の非固定ノード１００〜１０２，１１０，１１１，１２０〜１２２を発生空間に配置する際には、以下の制約条件が考慮される。
（ｉ）発生空間における各ノードの大きさ
各ノードはそれぞれ固有の大きさをもっている。
（ii）系統空間における複数のノードの接続関係
複数のノード間の接続関係がグラフ１００１として与えられている。また、あるノードは固定ノードと接続されている。
【０００６】
そして、上記制約条件を考慮しながら、例えば最適化問題解決アルゴリズムとしての遺伝的アルゴリズムを実行することにより、複数のノード１００〜１０２，１１０，１１１，１２０〜１２２の発生空間における最適配置が決定され、その決定に基づいて、上記複数のノード１００〜１０２，１１０，１１１，１２０〜１２２が発生空間に配置される。
【０００７】
なお、遺伝的アルゴリズムは、生物進化の原理に着想を得たアルゴリズムであり、配置最適化問題の解の候補を遺伝子の配列である染色体として表現し、各染色体に対して各種遺伝オペレーション（選択／自己複製，突然変異及び交叉）を施して世代を更新することにより、大きな適応度値を持つ染色体の遺伝子配列として求められる最適解（即ち、上記複数のノード１００〜１０２，１１０，１１１，１２０〜１２２の発生空間における最適配置）を求めるためのものである。
【０００８】
ここで、上記複数のノード１００〜１０２，１１０，１１１，１２０〜１２２を発生空間に配置した結果の一例を図２３に示す。
一般的には、発生空間は２次元以上の空間であり、各ノードは発生空間の次元に応じた任意の形状を有していればよいが、図２３では、発生空間２０００が長方形であり、各ノード（図２２に示す非固定ノード１００〜１０２，１１０，１１１，１２０〜１２２）がそれらの形状を長方形に規定されて発生空間２０００に配置された場合を示している。なお、この図２３においても、符号１３０ａ〜１３０ｈは、発生空間における配置が既に決まっている固定ノードを示す。
【０００９】
このように、遺伝的アルゴリズムを実行してノード配置最適化問題を処理することにより、接続関係のみが示された複数のノードの実際の空間における最適配置を求めることができる。
例えば、前述したＬＳＩにおいて、ＬＳＩ上の各回路の最適配置を求めることができれば、ＬＳＩの小型化を図ることができるほか、当該各回路を接続する配線の長さを最小化して配線性を向上させることができるので、ＬＳＩにおける処理の高速化を図ることもできる。
【００１０】
【発明が解決しようとする課題】
しかしながら、ノード配置最適化問題を処理する際に用いられる最適化問題解決アルゴリズムとして、遺伝的アルゴリズムを用いた場合には、最適化問題の規模が大きいとき、即ち、最適配置を求めるべきノード数が非常に多いときには、複数のノードの最適配置を求めるのに膨大な時間を要するという課題がある。
【００１１】
本発明は、このような課題に鑑み創案されたもので、問題規模の大きいノード配置最適化問題を処理する際にも、複数のノードの最適配置を高速に求めることができるようにした、配置最適化問題処理方法及び装置を提供することを目的とするとともに、更には、ノード配置最適化問題を処理すべくコンピュータを動作させるための配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【００１２】
【課題を解決するための手段】
このため、請求項１記載の本発明の配置最適化問題処理方法は、系統空間に接続関係が示された複数のノードを発生空間に配置する配置最適化問題を、コンピュータを用いて処理する方法であって、該コンピュータの入力部からの指示に応じて、該コンピュータのＣＰＵが、該複数のノードをグループ化して、ノードの集合からなるハイパーノードを複数形成するハイパーノード形成ステップと、該ハイパーノード形成ステップにて形成された該複数のハイパーノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、遺伝的アルゴリズムを実行することにより、該ハイパーノード形成ステップにて形成された該複数のハイパーノードを該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のハイパーノードを該発生空間に配置するハイパーノード配置ステップと、該ハイパーノード配置ステップにて得られた該複数のハイパーノードの位置及び形状をもとにして、該複数のノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、更に遺伝的アルゴリズムを実行することにより、該複数のノードを最適な状態で該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のノードを該発生空間に配置するノード最適配置ステップとを実行することにより、該複数のノードの配置最適化問題を処理するとともに、該ノード最適配置ステップが、該ハイパーノード配置ステップで求められた解のうちの最適解が目的とする条件を満たしていない場合に、当該求められた解のうちの最適解以外の解に基づいて、該複数のノードを該発生空間に配置する問題の解を求めることを特徴としている。
【００１３】
また、請求項２記載の本発明の配置最適化問題処理方法は、請求項１記載の配置最適化問題処理方法において、ハイパーノード配置ステップが、ハイパーノードを配置する際の制約条件を考慮して、複数のハイパーノードを発生空間に配置することを特徴としている。
さらに、請求項３記載の本発明の配置最適化問題処理方法は、請求項２記載の配置最適化問題処理方法において、ハイパーノードが、ハイパーノードを構成する複数のノードの部分的な集合からなるサブハイパーノードを複数そなえ、ハイパーノードにおける制約条件を、サブハイパーノードにおける制約条件に基づいて求める制約条件探索ステップをそなえたことを特徴としている。
【００１６】
さらに、請求項４記載の本発明の配置最適化問題処理方法は、請求項１記載の配置最適化問題処理方法において、発生空間が２次元空間である場合に、上記ハイパーノード配置ステップ及びノード最適配置ステップが、それぞれ上記ハイパーノード及びノードの形状を２次元の形状に規定して上記ハイパーノード及びノードを発生空間に配置することを特徴としている。
【００１７】
また、請求項５記載の本発明の配置最適化問題処理方法は、請求項１記載の配置最適化問題処理方法において、発生空間が長方形である場合に、上記ハイパーノード配置ステップ及びノード最適配置ステップにおいて、それぞれ上記ハイパーノード及びノードの形状を長方形に規定して上記ハイパーノード及びノードを発生空間に配置する際に、上記ハイパーノード配置ステップ及びノード最適配置ステップが、それぞれ、上記ハイパーノード及びノードを長方形の中心座標に関する情報と長方形の縦／横比に関する情報とから構成される遺伝子として表現し、発生空間に上記複数のハイパーノード及びノードを配置する問題の解候補としてその遺伝子の配列からなる染色体を用いて、遺伝的アルゴリズムを実行することを特徴としている。
【００１８】
さらに、請求項６記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に、遺伝オペレーションとして、染色体を構成する遺伝子における長方形の中心座標に関する情報及び長方形の縦／横比に関する情報を他の染色体を構成する遺伝子における各情報と置き換えた張り付け交叉が施されることを特徴としている。
【００１９】
また、請求項７記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に、遺伝オペレーションとして、染色体を構成する遺伝子における長方形の中心座標に関する情報を他の染色体を構成する遺伝子における情報と置き換えた張り付け交叉が施されることを特徴としている。
【００２０】
さらに、請求項８記載の本発明の配置最適化問題処理方法は、請求項７記載の配置最適化問題処理方法において、張り付け交叉が、長方形の中心座標に関する情報の重み付き平均に基づくことを特徴としている。
また、請求項９記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に、遺伝オペレーションとして、染色体を構成する遺伝子における長方形の縦／横比に関する情報を他の染色体を構成する遺伝子における情報と置き換えた張り付け交叉が施されることを特徴としている。
【００２１】
さらに、請求項１０記載の本発明の配置最適化問題処理方法は、請求項９記載の配置最適化問題処理方法において、張り付け交叉が、長方形の縦／横比に関する情報の重み付き平均に基づくことを特徴としている。
また、請求項１１記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に、遺伝オペレーションとして、染色体を構成する遺伝子における長方形の縦／横比に関する情報を変化させた突然変異が施されることを特徴としている。
【００２２】
さらに、請求項１２記載の本発明の配置最適化問題処理方法は、請求項１１記載の配置最適化問題処理方法において、突然変異において、長方形の縦／横比に関する情報を一定の割合で増加又は減少させることを特徴としている。
また、請求項１３記載の本発明の配置最適化問題処理方法は、請求項１２記載の配置最適化問題処理方法において、突然変異において、長方形の縦／横比に関する情報を一定の割合で増加させるか減少させるかを、確率的に決定することを特徴としている。
【００２３】
さらに、請求項１４記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に、遺伝オペレーションとして、染色体を構成する遺伝子における長方形の中心座標に関する情報を変化させた突然変異が施されることを特徴としている。
また、請求項１５記載の本発明の配置最適化問題処理方法は、請求項１４記載の配置最適化問題処理方法において、突然変異において、確率的に選択された数値を長方形の中心座標に関する情報に加算して、長方形の中心座標に関する情報を変化させることを特徴としている。
【００２４】
さらに、請求項１６記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に遺伝オペレーションとしての選択が施される前に、発生空間に配置された複数のハイパーノード同士を接続する配線の長さの総和を考慮して、染色体の適応度値が算出されることを特徴としている。
【００２５】
また、請求項１７記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に遺伝オペレーションとしての選択が施される前に、発生空間に配置された複数のハイパーノード同士の重なり部分の面積の総和を考慮して、染色体の適応度値が算出されることを特徴としている。
【００２６】
さらに、請求項１８記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に遺伝オペレーションとしての選択が施される前に、発生空間に配置された複数のハイパーノード同士を接続する配線の長さの総和及び複数のハイパーノード同士の重なり部分の面積の総和を考慮して、染色体の適応度値が算出されることを特徴としている。
【００２７】
また、請求項１９記載の本発明の配置最適化問題処理方法は、請求項１８記載の配置最適化問題処理方法において、適応度値の算出が、複数のハイパーノード同士を接続する配線の長さの総和及び複数のハイパーノード同士の重なり部分の面積の総和のいずれかに重み付け演算を施して行なわれることを特徴としている。
【００２８】
さらに、請求項２０記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に遺伝オペレーションとしての選択が施される前に、発生空間に配置された複数のハイパーノード同士の隙間部分の面積の総和を考慮して、染色体の適応度値が算出されることを特徴としている。
【００２９】
また、請求項２１記載の本発明の配置最適化問題処理方法は、請求項５記載の配置最適化問題処理方法において、遺伝的アルゴリズムを実行する際に、染色体に遺伝オペレーションとしての選択が施される前に、発生空間に配置された複数のハイパーノード同士を接続する配線の長さの総和及び複数のハイパーノード同士の隙間部分の面積の総和を考慮して、染色体の適応度値が算出されることを特徴としている。
【００３０】
さらに、請求項２２記載の本発明の配置最適化問題処理方法は、請求項２１記載の配置最適化問題処理方法において、適応度値の算出が、複数のハイパーノード同士を接続する配線の長さの総和及び複数のハイパーノード同士の隙間部分の面積の総和のいずれかに重み付け演算を施して行なわれることを特徴としている。
【００３１】
また、請求項２３記載の本発明の配置最適化問題処理方法は、２次元以上の空間に複数のエレメントを配置する配置最適化問題を、コンピュータを用いて処理する方法であって、該コンピュータの入力部からの指示に応じて、該コンピュータのＣＰＵが、該複数のエレメントをグループ化して、エレメントの集合からなるハイパーエレメントを複数形成するハイパーエレメント形成ステップと、該ハイパーエレメント形成ステップにて形成された該複数のハイパーエレメントの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、遺伝的アルゴリズムを実行することにより、該ハイパーエレメント形成ステップにて形成された該複数のハイパーエレメントを該空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のハイパーエレメントを該空間に配置するハイパーエレメント配置ステップと、該ハイパーエレメント配置ステップにて得られた該複数のハイパーエレメントの位置及び形状をもとにして、該複数のエレメントの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、更に遺伝的アルゴリズムを実行することにより、該複数のエレメントを最適な状態で該空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のエレメントを該空間に配置するエレメント最適配置ステップとを実行することにより、該複数のエレメントの配置最適化問題を処理するとともに、該エレメント最適配置ステップが、該ハイパーエレメント配置ステップで求められた解のうちの最適解が目的とする条件を満たしていない場合に、当該求められた解のうちの最適解以外の解に基づいて、該複数のエレメントを該発生空間に配置する問題の解を求めることを特徴としている。
【００３２】
さらに、請求項２４記載の本発明の配置最適化問題処理装置は、系統空間に接続関係が示された複数のノードを発生空間に最適に配置するノード配置最適化問題を処理する配置最適化問題処理装置であって、入力部と、該入力部からの指示に応じて、該複数のノードをグループ化して、ノードの集合からなるハイパーノードを複数形成するハイパーノード形成部と、該入力部からの指示に応じて、該ハイパーノード形成部にて形成された該複数のハイパーノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、遺伝的アルゴリズムを実行することにより、該ハイパーノード形成部により形成された該複数のハイパーノードを該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のハイパーノードを該発生空間に配置するハイパーノード配置部と、該入力部からの指示に応じて、該ハイパーノード配置部により得られた該複数のハイパーノードの位置及び形状をもとにして、該複数のノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、更に遺伝的アルゴリズムを実行することにより、該複数のノードを最適な状態で該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のノードを該発生空間に配置するノード最適配置部とをそなえて構成されるとともに、該ノード最適配置部が、該ハイパーノード配置部により求められた解のうちの最適解が目的とする条件を満たしていない場合に、当該求められた解のうちの最適解以外の解に基づいて、該複数のノードを該発生空間に配置する問題の解を求めることを特徴としている。
【００３３】
また、請求項２５記載の本発明の配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体は、系統空間に接続関係が示された複数のノードを発生空間に最適に配置するノード配置最適化問題をコンピュータにより処理するための配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体であって、該配置最適化問題処理プログラムが、該コンピュータのＣＰＵを、該コンピュータの入力部からの指示に応じて、該複数のノードをグループ化して、ノードの集合からなるハイパーノードを複数形成するハイパーノード形成部、該入力部からの指示に応じて、該ハイパーノード形成部にて形成された該複数のハイパーノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、遺伝的アルゴリズムを実行することにより、該ハイパーノード形成部により形成された該複数のハイパーノードを該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のハイパーノードを該発生空間に配置するハイパーノード配置部、および、該入力部からの指示に応じて、該ハイパーノード配置部により得られた該複数のハイパーノードの位置及び形状をもとにして、該複数のノードの位置及び形状を表わす遺伝子の配列からなる染色体を解候補として用い、更に遺伝的アルゴリズムを実行することにより、該複数のノードを最適な状態で該発生空間に配置する問題の解を求め、当該求められた解に基づいて、該複数のノードを該発生空間に配置するノード最適配置部として機能させるとともに、該ノード最適配置部が、該ハイパーノード配置部により求められた解のうちの最適解が目的とする条件を満たしていない場合に、当該求められた解のうちの最適解以外の解に基づいて、該複数のノードを該発生空間に配置する問題の解を求めるように機能させることを特徴としている。
【００３４】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（ａ）本発明の一実施形態にかかる配置最適化問題処理装置の構成
図１は本発明の一実施形態にかかる配置最適化問題処理装置の構成を示すブロック図であり、この図１に示す配置最適化問題処理装置１は、前述したノード配置最適化問題（グラフマッピング問題）を処理するものである。
【００３５】
ここで、図１において、５Ａは各種の設定画面や処理にて得られた複数ノードの最適配置等を表示する表示部、５はこの表示部５Ａ上における表示状態を制御する表示制御部、７Ｂは表示部５Ａ上の表示データを参照しオペレータがその表示データに対する応答情報を入力するキーボード，マウス等の入力部、７Ｄは入力部７Ｂを制御する入力制御部である。
【００３６】
また、８はハードディスクで、このハードディスク８は、配置最適化問題処理装置１を動作させるために必要となる一切の情報（ＯＳ等）を記憶するものであるとともに、後述する配置最適化問題処理プログラムを記憶するものである。
なお、６は外部ファイル読出書込部，６Ａは外部ファイル，７Ａは印字部，７Ｃは印字制御部であり、外部ファイル読出書込部６及び印字部７Ａは、それぞれ、入力部７Ｂからの指示に応じて、表示部５Ａに表示された複数ノードの最適配置等を、外部ファイル６Ａ又は所定の用紙に記録するものである。
【００３７】
また、４は配置最適化問題処理装置１を構成する各部を統括的に管理するためのＣＰＵである。
本実施形態にかかる配置最適化問題処理装置１においては、ＣＰＵ４は、図２に示すようなハイパーノード形成部４１，ハイパーノード配置部４２及びノード最適配置部４３に相当する機能を有している。
【００３８】
ここで、ハイパーノード形成部４１は、系統空間に接続関係が示された複数のノードをグループ化して、ノードの集合からなるハイパーノードを複数形成するものである。さらに、本実施形態においては、このハイパーノード形成部４１は、ハイパーノードを配置する際の制約条件を求める制約条件探索部としての機能も有している。
【００３９】
また、ハイパーノード配置部４２は、最適化問題解決アルゴリズム（例えば遺伝的アルゴリズム）を実行して、ハイパーノード形成部４１により形成された複数のハイパーノードを発生空間に配置する問題の解を求め、その求められた解に基づいて、複数のハイパーノードを発生空間に配置するものである。
さらに、ノード最適配置部４３は、ハイパーノード配置部４２により得られた複数のハイパーノードの配置関係を考慮しながら、更に最適化問題解決アルゴリズム（例えば遺伝的アルゴリズム）を実行して、複数のノードを最適な状態で発生空間に配置する問題の解（即ち最適解）を求め、その求められた解に基づいて、複数のノードを発生空間に配置するものである。
【００４０】
なお、上述したハイパーノード形成部４１，ハイパーノード配置部４２及びノード最適配置部４３に相当する機能は、実際には、前述したハードディスク８やＣＤ−ＲＯＭ（図示せず）等の記録媒体に記録されたプログラム（以下、配置最適化問題処理プログラムという）を図示しないメモリ（ＲＡＭ）に読み出し、そのプログラムを起動してＣＰＵ４で実行することにより、ＣＰＵ４の動作として実現される。
【００４１】
ここで、配置最適化問題処理プログラムは、複数のノードをグループ化して、ノードの集合からなるハイパーノードを複数形成するハイパーノード形成部４１、最適化問題解決アルゴリズムを実行して、ハイパーノード形成部４１により形成された複数のハイパーノードを発生空間に配置する問題の解を求め、その求められた解に基づいて、複数のハイパーノードを発生空間に配置するハイパーノード配置部４２、および、ハイパーノード配置部４２により得られた複数のハイパーノードの配置関係を考慮しながら、更に最適化問題解決アルゴリズムを実行して、複数のノードを最適な状態で発生空間に配置する問題の解を求め、その求められた解に基づいて、複数のノードを発生空間に配置するノード最適配置部４３として、コンピュータを機能させるものである。
【００４２】
なお、この配置最適化問題処理プログラムは、例えばＣＤ−ＲＯＭ等に記録されており、ＣＤ−ＲＯＭ等からコンピュータにおけるハードディスク８にインストールされて使用される。
即ち、上述したハードディスク８やＣＤ−ＲＯＭ等が、配置最適化問題処理プログラムを記録したコンピュータ読み取り可能な記録媒体に相当する。
【００４３】
このように、本実施形態にかかる配置最適化問題処理装置１は、上述したＣＰＵ４，表示部５Ａ，表示制御部５，外部ファイル読出書込部６，印字部７Ａ，印字制御部７Ｃ，入力部７Ｂ，入力制御部７Ｄ，ハードディスク８等を有する一般的な計算機システム（コンピュータ）を用いて実現することが可能である。
（ｂ）本発明の一実施形態にかかる配置最適化問題処理装置の動作の説明
本発明の一実施形態にかかる配置最適化問題処理装置１の動作として、前述したノード配置最適化問題の処理方法について、図１８〜図２１に示すフローチャート等を参照しながら説明する。
【００４４】
本実施形態にかかる配置最適化問題処理装置１においては、以下に示す各ステップ（ハイパーノード形成ステップ，制約条件探索ステップ，ハイパーノード配置ステップ及びノード最適配置ステップ）を実行することにより、複数のノードの配置最適化問題が処理される。
まず、ハイパーノード形成部４１により、系統空間に接続関係が示された複数のノードがグループ化されて、ノードの集合からなるハイパーノードが複数形成される〔ハイパーノード形成ステップ（図１８のステップＡ１）〕。
【００４５】
ここで、系統空間における複数のノードの接続関係（結合関係）を図４に示す。この図４においても、前出した図２２と同様に、符号１３０ａ〜１３０ｈは、発生空間における配置が既に決まっている固定ノードを示し、符号１００〜１０２，１１０，１１１，１２０〜１２２は、発生空間における最適配置を求めるべき非固定ノードを示す。また、符号１０００は系統空間（系統空間の次元は任意でよい）を示す。
系統空間１０００においては、複数のノード間の接続関係がグラフ１００１として与えられており、このグラフ１００１においては、各ノード１３０ａ〜１３０ｈ，１００〜１０２，１１０，１１１，１２０〜１２２が頂点とみなされるとともに、各ノード間の接続関係（図４に示す両側矢印）が頂点間の辺とみなされる。なお、図４でも、各ノード間の結合強度をこの両側矢印の太さにより示している。
【００４６】
そして、本実施形態においては、ハイパーノード形成部４１により、系統空間１０００における複数の非固定ノード１００〜１０２，１１０，１１１，１２０〜１２２がグループ化されて、ハイパーノード１０〜１２が形成される。例えば図４に示すように、ノード１００〜１０２がグループ化されてハイパーノード１０が形成され、ノード１１０，１１１がグループ化されてハイパーノード１１が形成され、ノード１２０〜１２２がグループ化されてハイパーノード１２が形成される。
【００４７】
即ち、本実施形態においては、ハイパーノード形成部４１により、図５（より一般的には図３）に示すように問題を表現しているグラフ１００１が階層化されるのである。
各階層は以下のように構成される。図５に示すように、第０階層のハイパーノード（このハイパーノードは複数の非固定ノード１００〜１０２，１１０，１１１，１２０〜１２２全てからなる）がハイパーノード形成部４１により分割されて、第１階層のハイパーノード１０〜１２が形成される。より一般的には、図３に示すように、第ｉ階層（ｉ＝０〜Ｎ−１）のハイパーノードがハイパーノード形成部４１により分割されて、第ｉ＋１階層のハイパーノードが複数形成される。
【００４８】
従って、上位の階層ほどグラフは単純になり、逆に下位の階層ほどグラフは複雑になる。そして、最下層（図５では第２階層，図３では第Ｎ階層）のグラフはもとのグラフ１００１と一致する。
換言すれば、系統空間１０００におけるグラフにおいて、高い結合強度で結合された非固定ノード同士をまとめてハイパーノードとし、さらにそれらをまとめて更に上位のハイパーノードとすることによって、この階層構造を得ることができる。
【００４９】
続いて、ハイパーノード形成部４１により、上記ハイパーノード１０〜１２を配置する際の制約条件（ハイパーノード１０〜１２の面積及びハイパーノード１０〜１２の接続関係，結合強度）が、上記ノード１００〜１０２，１１０，１１１，１２０〜１２２の面積及びノード１００〜１０２，１１０，１１１，１２０〜１２２の接続関係，結合強度に基づいて求められる〔制約条件探索ステップ（図１８のステップＡ２）〕。なお、ノード１００〜１０２，１１０，１１１，１２０〜１２２の面積及びノード１００〜１０２，１１０，１１１，１２０〜１２２の接続関係，結合強度は予め与えられているものとする。
【００５０】
即ち、各階層におけるハイパーノードの面積は、各ハイパーノードを構成する下位の階層のハイパーノード（又はノード）の面積の総和として求められる。
また、各階層におけるハイパーノード間の接続関係及び結合強度は、下位の階層のハイパーノード間の接続関係及び結合強度に基づいて決定される。本来ならば、ハイパーノード間の接続関係及び結合強度は、各ハイパーノードを構成するノード間の接続関係及び結合強度に基づいて決定されるが、この方法では時間がかかる。従って、本実施形態においては、下位の階層のハイパーノード間の接続関係及び結合強度から上位の階層のハイパーノード間の接続関係及び結合強度を推定することにより、各階層毎にハイパーノード間の接続関係及び結合強度を決定している。
【００５１】
具体的には、ハイパーノード間の接続関係は、あるハイパーノードを構成する下位の階層のハイパーノード（又はノード）と、他のハイパーノードを構成する下位の階層のハイパーノード（又はノード）との接続関係（図４に示す両側矢印）の有無や数等を考慮して決定される。
また、ハイパーノード間の結合強度は、あるハイパーノードを構成する下位の階層のハイパーノード（又はノード）と、他のハイパーノードを構成する下位の階層のハイパーノード（又はノード）との結合強度に基づいて決定される（詳細は図１９のステップＢ１〜Ｂ６参照）。
【００５２】
ここで、最下位の階層のノードがノード１００，１０１，１１０，１１１の４個であり、ハイパーノード１０がノード１００，１０１からなり、ハイパーノード１１がノード１１０，１１１からなる場合の、ノード１００，１０１，１１０，１１１間の結合強度表の一例を図７に示す。この場合には、ハイパーノード１０，１１間の結合強度は、ノード１００，１１０間の結合強度０，ノード１００，１１１間の結合強度０，ノード１０１，１１０間の結合強度０，ノード１０１，１１１間の結合強度４の総和４として推定することができる。
【００５３】
つまり、より一般的には、ハイパーノードが、そのハイパーノードを構成する複数のノードの部分的な集合からなるサブハイパーノード（下位の階層のハイパーノード）を複数そなえ、ハイパーノード形成部４１により、そのハイパーノードにおける制約条件がサブハイパーノードにおける制約条件に基づいて求められるのである。
【００５４】
そして、ハイパーノード配置部４２により、例えば最適化問題解決アルゴリズムとしての遺伝的アルゴリズムが実行されて、ハイパーノード形成部４１により形成された複数のハイパーノード１０〜１２（図４，図５参照）を発生空間に配置する問題の解が求められ、その求められた解のうちの最適解に基づいて、複数のハイパーノード１０〜１２が発生空間に配置される（ハイパーノード配置ステップ）。このとき、複数のハイパーノード１０〜１２は、前述のごとく求められたハイパーノードを配置する際の制約条件を考慮して発生空間に配置される。
【００５５】
さらに、ノード最適配置部４３により、ハイパーノード配置部４２により得られた複数のハイパーノード１０〜１２の配置関係が考慮されながら、更に最適化問題解決アルゴリズム（例えば遺伝的アルゴリズム）が実行されて、複数のノード１００〜１０２，１１０，１１１，１２０〜１２２を最適な状態で発生空間に配置する問題の解を求め、その求められた解（即ち最適解）に基づいて、複数のノード１００〜１０２，１１０，１１１，１２０〜１２２が発生空間に配置される（ノード最適配置ステップ）。なお、このとき、複数のノード１００〜１０２，１１０，１１１，１２０〜１２２は、予め与えられているノードを配置する際の制約条件を考慮して発生空間に配置される。
【００５６】
つまり、一般的には、各階層（第１階層から第Ｎ−１階層）毎に複数のハイパーノードが発生空間に配置され、最後に最下層（第Ｎ階層）の複数のノードが発生空間に配置される。即ち、遺伝的アルゴリズムを実行して、最上位の階層（第１階層）から解を求めはじめ、順次、下位の階層（第２階層から第Ｎ階層）の解を求めることにより、配置最適化問題の最適解（複数のノードの発生空間における最適配置）が求められる。
【００５７】
即ち、上述したハイパーノード配置ステップ，ノード最適配置ステップは、図１８のステップＡ３に相当するのであり、更に詳細には図２０のステップＣ１〜Ｃ５に相当する。
そして、ノード最適配置部４３では、上述したノード最適配置ステップにおいて求められた最適解（最下位の階層のノード１００〜１０２，１１０，１１１，１２０〜１２２の位置及び形状）が目的とする条件を満たしているか否かが判断され（図１８のステップＡ４／図２１のステップＤ１）、この条件を満たしている場合や条件を満たしていなくても解の改良を行なわない場合には最適解の探索が終了する（図１８のステップＡ４のＹＥＳルート／図２１のステップＤ１のＹＥＳルート，図２１のステップＤ２のＮＯルート）。
【００５８】
ここで、上記複数のノード１００〜１０２，１１０，１１１，１２０〜１２２を発生空間に配置した結果の一例を図６に示す。
一般的には、発生空間は２次元以上の空間であり、各ノードは発生空間の次元に応じた任意の形状を有していればよいが、本実施形態においては、説明を簡便にすべく、図６に示すように、発生空間２０００が長方形であり、ハイパーノード配置部４２及びノード最適配置部４３により、各ハイパーノード１０〜１２及び各ノード１００〜１０２，１１０，１１１，１２０〜１２２がそれらの形状を長方形に規定されて発生空間２０００に配置された場合を示している。なお、この図６においても、符号１３０ａ〜１３０ｈは、発生空間における配置が既に決まっている固定ノードを示す。
【００５９】
ところで、上述した遺伝的アルゴリズムについて説明すると、遺伝的アルゴリズムは、生物の遺伝の機構を模倣してそれを工学的に応用した技術であり、確率的探索，学習及び最適化の一手法と考えることができる。
生物の進化の過程では、既存の個体（親）から新たなる個体（子）が生まれる際に、個体のもつ染色体同士の交叉，染色体上の遺伝子の突然変異などが起こる。そして、環境に適応しない個体は淘汰され、環境により適応した個体が生きのびて新たな親となってさらに新たな子孫を作ることにより、環境に適応した個体の集団が生きのびていく。
【００６０】
各個体がどの程度環境に適応するかは、染色体（遺伝子の一次元ストリング）によって決定されるが、遺伝的アルゴリズムでは、配置最適化問題の解候補が遺伝子の一次元ストリングである染色体として表現される。そして、配置最適化問題の目的関数がいわゆる環境に相当し、目的関数を最適にするものほど大きい値をとるような適応度関数が染色体に対して定義される。
【００６１】
そして、遺伝的アルゴリズムでは、染色体の遺伝子配列を変化させて問題の最適解になりうる染色体（目的関数をより最適にする解）を生成するために、各染色体に、図１４に示すような各種の遺伝オペレーション（選択／自己複製，交叉及び突然変異）が施される。
ここで、選択（Selection ）／自己複製（Reproduction）は、集団の中で適応度の高い染色体をもつ個体をより高い確率で選択して次世代の親とする操作であり（図１５参照）、交叉（Crossover ）は、２つの親の染色体の一部を互いに入れ換えて新たな個体（子）を作りだす操作であり（図１６参照）、突然変異（Mutation）は、１つの染色体の一部の遺伝子をランダムに置き換えて個体を変化させる操作である（図１７参照）。
【００６２】
本実施形態においては、ハイパーノード及びノードが、それぞれハイパーノード配置部４２及びノード最適配置部４３により、これらの形状である長方形の中心座標，長方形の縦／横比から構成される遺伝子として表現される。
そして、ハイパーノード配置部４２及びノード最適配置部４３では、それぞれ、発生空間に上記複数のハイパーノード及びノードを配置する問題の解候補として当該遺伝子の全配列からなる染色体を用いて、遺伝的アルゴリズムが実行される。
【００６３】
ここで、ハイパーノード１０〜１２の配置を求める際に使用する染色体の構成の一例を図８に示す。この図８には、左から順にハイパーノード１０〜１２の遺伝子構成が示されており、一番左側の遺伝子の値〔（ｘ＝０．２４，ｙ＝０．７４），（Ｘ＝０．５２，Ｙ＝０．５３）〕は、ハイパーノード１０の中心座標がｘ＝０．２４，ｙ＝０．７４であり、ハイパーノード１０の縦／横比がＸ：Ｙ＝０．５２：０．５３であることを示している。なお、他の遺伝子の値についても同様である。
【００６４】
ここで、遺伝的アルゴリズムを実行する際には、ハイパーノード及びノードを示す遺伝子における長方形の中心座標，長方形の縦／横の比率が、目的関数が最小となるように決定される。
そして、本実施形態においては、各染色体に、遺伝オペレーションとして、張り付け交叉，突然変異，選択等が施される。
【００６５】
ここで、張り付け交叉には、例えば以下に示すような５つの態様がある。
（１）長方形の中心座標及び長方形の縦／横比の張り付け交叉
ある染色体において適当な遺伝子の集合を選び、その選ばれた遺伝子の有する長方形の中心座標，長方形の縦／横比を、他の染色体における同じ集合の遺伝子の有する長方形の中心座標，長方形の縦／横比と置き換える。
【００６６】
即ち、ある染色体を構成する特定の部位の遺伝子における長方形の中心座標，長方形の縦／横比を、他の染色体を構成する同じ部位の遺伝子における長方形の中心座標，長方形の縦／横比と置き換える。
（２）長方形の中心座標のみの張り付け交叉
ある染色体において適当な遺伝子の集合を選び、その選ばれた遺伝子の有する長方形の中心座標を、他の染色体における同じ集合の遺伝子の有する長方形の中心座標と置き換える。
【００６７】
即ち、ある染色体を構成する特定の部位の遺伝子における長方形の中心座標を、他の染色体を構成する同じ部位の遺伝子における長方形の中心座標と置き換える。
（３）長方形の縦／横比のみの張り付け交叉
ある染色体において適当な遺伝子の集合を選び、その選ばれた遺伝子の有する長方形の縦／横比を、他の染色体における同じ集合の遺伝子の有する長方形の縦／横比と置き換える。
【００６８】
即ち、ある染色体を構成する特定の部位の遺伝子における長方形の縦／横比を、他の染色体を構成する同じ部位の遺伝子における長方形の縦／横比と置き換える。
（４）長方形の中心座標の重みつき平均に基づいた張り付け交叉
ある染色体において適当な遺伝子の集合を選び、その選ばれた遺伝子の有する長方形の中心座標と、他の染色体における同じ集合の遺伝子の有する長方形の中心座標との重み付き平均値を計算し、この計算された平均値を他の染色体の対応する遺伝子の長方形の中心座標と置き換える。これにより、解が極端に変化するのを防ぐことができる。
（５）長方形の縦／横比の重みつき平均に基づいた張り付け交叉
ある染色体において適当な遺伝子の集合を選び、その選ばれた遺伝子の有する長方形の縦／横比と、他の染色体における同じ集合の遺伝子の有する長方形の縦／横比との重み付き平均値を計算し、この計算された平均値を他の染色体の対応する遺伝子の長方形の縦／横比と置き換える。これによっても、解が極端に変化するのを防ぐことができる。
【００６９】
また、突然変異には、例えば以下に示すような２つの態様がある。
（１）長方形の縦／横比の突然変異
染色体を構成する１つ（又は複数）の遺伝子における長方形の縦／横比を、一定の割合で増加させて変化させる（例えば長方形の縦の長さだけを長くする等）。あるいは、染色体を構成する１つ（又は複数）の遺伝子における長方形の縦／横比を、一定の割合で減少させて変化させる（例えば長方形の縦の長さだけを短くする等）。
【００７０】
また、染色体を構成する１つ（又は複数）の遺伝子における長方形の縦／横比を、一定の割合で増加又は減少させて変化させる。このとき、増加させるか減少させるかは、確率的に決定される。
（２）長方形の中心座標の突然変異
染色体を構成する１つ（又は複数）の遺伝子における長方形の中心座標に、確率的に選択された正又は負の比較的小さな数値を加えることにより、長方形の中心座標を変化させる。
【００７１】
さらに、選択が施される前には、各染色体の適応度値が算出されるが、この適応度値の算出方法には、例えば以下に示すような２つの態様がある。これらの各態様は、階層に応じて適切な方が優先的に使用される。
（１）ハイパーノード（又はノード）同士の重なり部分の面積の総和を考慮した方法
発生空間に配置された複数のハイパーノード（又はノード）同士を接続する配線の長さの総和と、複数のハイパーノード（又はノード）同士の重なり部分の面積の総和とを考慮して、染色体の適応度値が算出される。なお、ハイパーノード（又はノード）同士が重なった様子を図１３（ｂ）に示す。この図において、１４０は発生空間又は上位の階層のハイパーノードを示し、１４１は配置されたハイパーノード又はノードを示し、Ｐはハイパーノード（又はノード）同士の重なり部分を示す。
【００７２】
ここで、適応度値の算出は、複数のハイパーノード（又はノード）同士を接続する配線の長さの総和及び複数のハイパーノード（又はノード）同士の重なり部分の面積の総和のいずれかに重み付け演算を施して行なうこともできる。このときは、次式▲１▼のように定義された適応度関数が使用される。
0003905959.tif 000002
これによって、配線長が短い解やハイパーノード（又はノード）が重ならないような解を求めることができる。
（２）ハイパーノード（又はノード）同士の隙間部分の面積の総和を考慮した方法
発生空間に配置された複数のハイパーノード（又はノード）同士を接続する配線の長さの総和と、複数のハイパーノード（又はノード）同士の隙間部分の面積の総和とを考慮して、染色体の適応度値が算出される。なお、ハイパーノード（又はノード）間に隙間が生じた様子を図１３（ａ）に示す。この図において、１４０は発生空間又は上位の階層のハイパーノードを示し、１４１は配置されたハイパーノード又はノードを示し、Ｓはハイパーノード（又はノード）同士の隙間部分を示す。
【００７３】
ここで、適応度値の算出は、複数のハイパーノード（又はノード）同士を接続する配線の長さの総和及び複数のハイパーノード（又はノード）同士の隙間部分の面積の総和のいずれかに重み付け演算を施して行なうこともできる。このときは、次式▲２▼のように定義された適応度関数が使用される。
0003905959.tif 000003
これによって、配線長が短い解やハイパーノード（又はノード）を配置する際に隙間部分が生じにくい解を求めることができる。
【００７４】
ところで、上述したようにして求められた最適解（最下位の階層のノード１００〜１０２，１１０，１１１，１２０〜１２２の位置及び形状）が目的とする条件を満たしておらず、解の改良を行なう場合には、ハイパーノード配置部４２により、階層の後戻り（バックトラック）が行なわれ、再度最適解が探索される（図１８のステップＡ４のＮＯルートからステップＡ５／図２１のステップＤ２のＹＥＳルートからステップＤ３〜ステップＤ１１）。
【００７５】
つまり、本実施形態においては、第ｉ階層（ｉ＝０〜Ｎ−１）で遺伝的アルゴリズムにより得られた最適解をもとにして、それより下位の階層の最適化が実施されるが、第ｉ階層での最適解以外の解をもとにして、それより下位の階層の最適化を実施した方が、最終的には良い解が生じる可能性がある。
そこで、得られた解が目的とする条件を満たしていない場合には、ハイパーノード配置部４２では、この得られた解を改善するために、上位の階層に後戻りし、その階層での最適解以外の解に基づいて、再度最適解が探索される。このように階層を縦に渡る方向での最適化も有効である。
【００７６】
即ち、ハイパーノード配置部４２では、求められた解のうちの最適解以外の解に基づいて、複数のハイパーノード１０〜１２が発生空間２０００に配置されるのである。
なお、この階層の後戻りにより探索された最適解が目的とする条件を満たしている場合には、配置最適化問題処理装置１におけるノード配置最適化問題の処理は終了する。
【００７７】
このように、本発明の一実施形態にかかる配置最適化問題処理装置１におけるノード配置最適化問題の処理方法によれば、複数のノードをグループ化することにより形成されたハイパーノードを発生空間に配置し、このハイパーノードの配置関係を考慮しながら複数のノードを発生空間に配置することにより、問題規模の大きいノード配置最適化問題を処理する際にも、複数のノードの最適配置を高速に求めることができる。
【００７８】
ここで、上位の階層の複数のハイパーノード内における下位の階層のハイパーノード（又はノード）を配置する際に、上位の階層のハイパーノード毎に遺伝的アルゴリズムを実行すれば、ノード配置最適化問題における演算を並列処理にて行なうことができるため、配置最適化問題の最適解をより高速に発見できるようになる。
【００７９】
そして、このような遺伝的アルゴリズムの大域的探索法により、効率的に配置最適化問題の最適解を探索することができる。
さらに、ハイパーノード間の接続関係及び結合強度を、下位の階層のハイパーノード間の接続関係及び結合強度から推定して決定することにより、ハイパーノード間の接続関係及び結合強度の決定にかかる時間を短縮することができる。
【００８０】
また、最下位の階層のノードの位置及び形状が目的とする条件を満たしてない場合には、階層の後戻り（バックトラック）を行なって再度最適解を探索することにより、より最適な解を探索することができる。特に、遺伝的アルゴリズムにおいては、各階層毎に複数の解候補が存在するため、階層の後戻りを行なう際に前に使用した解（最適解）以外の解をただちに採用することができ、階層の後戻りを高速に行なうことができる。
【００８１】
さらに、各染色体に、遺伝オペレーションとして、配置最適化問題に適した張り付け交叉が施されることにより、配置最適化問題の解候補として生成される染色体の質を向上させることができ、その結果、最適解を効率的に探索することができる。
また、上記張り付け交叉が、染色体を構成する遺伝子の有する長方形の中心座標や長方形の縦／横比の重み付き平均に基づくことにより、解が極端に変化するのを防ぐことができ、適応度の増大に寄与することができる。
【００８２】
さらに、適応度値の算出が、ハイパーノード同士を接続する配線の長さの総和及びハイパーノード同士の重なり部分の面積の総和のいずれかに重み付け演算を施して行なわれることにより、目的に応じた解〔配線長が短い解やハイパーノード（又はノード）が重ならないような解〕を求めることができる。
また、適応度値の算出が、ハイパーノード同士を接続する配線の長さの総和及びハイパーノード同士の隙間部分の面積の総和のいずれかに重み付け演算を施して行なわれることにより、目的に応じた解〔配線長が短い解やハイパーノード（又はノード）を配置する際に隙間部分が生じにくい解〕を求めることができる。
【００８３】
（ｃ）配置最適化問題の具体例
上述した配置最適化問題の具体例として、（１）ＬＳＩ配置問題（フロアプラン），（２）ＬＳＩ配置問題（階層的配置法）について簡単に説明する。
（１）ＬＳＩ配置問題（フロアプラン）
ＬＳＩの配置問題の一種にフロアプランがある。これは配置するセルの面積は定まっているが、セルの各辺の長さが可変である問題のことをいう。
【００８４】
このフロアプランを処理する際に、上述した配置最適化問題処理装置１及び処理方法を用いることができる。
即ち、フロアプランは、面積が一定であり、且つ、縦／横比が変化する複数の長方形を定められた領域に配置する問題に置き換えることができる。この場合には、目的関数は、複数の長方形間を接続する配線の長さの総和と複数の長方形間の重なり部分の面積の総和とを加算したものになる。そして、この目的関数に基づいて適応度値が算出される。
（２）ＬＳＩ配置問題（階層的配置法）
ＬＳＩの配置問題においては、セル間の接続関係，固定セル（パッドと呼ばれる）と非固定セルとの接続関係が与えられた場合に、非固定セルを定められた配置領域へ配線の長さを最小にするように配置する問題が重要な問題の１つである。
【００８５】
このような問題の中には、セルが予めグループ化されてハイパーセルが形成され、これが階層論理情報として与えられている場合（例えば、セルの集合によりフィルタ部や増幅部等が形成されるような場合）がある。
即ち、例えば図９に示すように、予め、セル１００′〜１０２′がグループ化されてハイパーセル１０′が形成され、セル１１０′，１１１′がグループ化されてハイパーセル１１′が形成され、セル１２０′〜１２２′がグループ化されてハイパーセル１２′が形成されているような場合がある。なお、セル１２２′は、セル１２２０〜１２２２から構成されている。また、図９において、符号１３０ａ′〜１３０ｇ′は、ＬＳＩにおける配置が既に決まっている固定セルであり、各セル間の結合強度は、図９に示す両側矢印の太さにより示される。さらに、符号１０００′は系統空間である。さらに、図９に示すセルの階層を図１０に示す。
【００８６】
この場合には、ハイパーセルが、上述したハイパーノードに相当するため、上述した配置最適化問題処理装置１及び処理方法を用いることができる。便宜上、最上位の階層はＬＳＩ全体であり、最下位の階層は全てのセルであると定める。
（ｉ）適応度値
目的関数は、各階層におけるハイパーセル間を接続する配線の長さの総和とハイパーセル同士の重なり部分の面積の総和との重みつきの和である。
【００８７】
従って、適応度値は、
適応度値＝（一定数）−（目的関数）                          …▲３▼
により求めることができる。
（ii）配置方法
与えられたＬＳＩ配置データが階層論理情報である場合には、既にセルが階層化されてハイパーセルが形成されているので、階層的な配置方法を応用することができる。
【００８８】
そして、第ｉ階層のハイパーセル間の結合強度は、その下位の第ｉ＋１階層のハイパーセル間の結合強度から決定することができるので、計算時間を著しく短縮することができる。なお、このとき用いられるセル間結合強度表を図１２に示す。
第ｉ階層のハイパーセルのＬＳＩ上の配置が遺伝的アルゴリズムによって決定される。また、第ｉ＋１階層のハイパーセルのＬＳＩ上の配置は、第ｉ階層の配置結果を参照して第ｉ＋１階層のハイパーセルの初期配置が構成された後に、遺伝的アルゴリズムによって決定される。
【００８９】
そして、上記の手順を、最上位の階層から最下位の階層まで実施することにより、ＬＳＩ上のセルの最適配置を求めることができる。
なお、セルを階層的にＬＳＩ上に配置して得られた結果を図１１に示す。この図１１において、符号２０００′はＬＳＩ上の領域を示す。
このように、遺伝的アルゴリズムと階層的配置法とを組み合わせれば、適応度の増加を加速することができる。
【００９０】
（ｄ）その他
なお、上述においては、ノード及びハイパーノードの形状が長方形である場合について説明したが、処理対象となる配置最適化問題に応じて、ノード及びハイパーノードの形状を単連結な任意の形状（例えば円形，楕円形，多角形，長方形の和集合等）にしてもよい。
【００９１】
特に、ノード及びハイパーノードの形状が長方形の和集合として表現できる図形ならば、上述した議論を拡張することができるので、上述した配置最適化問題処理装置１及び処理方法を適宜用いることができる。
さらに、ノード及びハイパーノードの形状は３次元のものであってもよい。
また、上述においては、ハイパーノード配置部４２，ノード最適配置部４３が、最適化問題解決アルゴリズムとして遺伝的アルゴリズムを実行した場合について説明したが、他の最適化問題解決アルゴリズム〔例えばミンカット法（ｍｉｎ−ｃｕｔ法），ｎ要素交換法，自己組織化法等〕を実行してもよい。さらに、ハイパーノード配置部４２とノード最適配置部４３とが、それぞれ異なる最適化問題解決アルゴリズムを実行しても構わない。
【００９２】
なお、上述した配置最適化問題処理装置１及び処理方法は、染色体の遺伝子のとる値が連続的な値である場合にも拡張することができる。
ところで、上述した配置最適化問題処理装置１及び処理方法においては、系統空間に接続関係が示された複数のノードを発生空間に配置する場合について説明したが、より一般的に、複数のエレメントを配置する場合にも適用できる。
【００９３】
つまり、本発明の配置最適化問題処理方法は、２次元以上の空間に複数のエレメントを配置するに際し、複数のエレメントをグループ化して、エレメントの集合からなるハイパーエレメントを複数形成するハイパーエレメント形成ステップと、最適化問題解決アルゴリズムを実行して、ハイパーエレメント形成ステップにて形成された複数のハイパーエレメントを空間に配置する問題の解を求め、その求められた解に基づいて、複数のハイパーエレメントを空間に配置するハイパーエレメント配置ステップと、ハイパーエレメント配置ステップにて得られた複数のハイパーエレメントの配置関係を考慮しながら、更に最適化問題解決アルゴリズムを実行して、複数のエレメントを最適な状態で空間に配置する問題の解を求め、その求められた解に基づいて、複数のエレメントを空間に配置するエレメント最適配置ステップとを実行することにより、複数のエレメントの配置最適化問題を処理することを特徴としてもよい。
【００９４】
【発明の効果】
以上詳述したように、請求項１〜２５記載の本発明によれば、複数のノード（又はエレメント）をグループ化することにより形成されたハイパーノード（又はハイパーエレメント）を空間に配置し、このハイパーノードの位置及び形状をもとにして複数のノードを空間に配置することにより、問題規模の大きいノード配置最適化問題を処理する際にも、複数のノードの最適配置を高速に求めることができる利点がある。
【図面の簡単な説明】
【図１】本発明の一実施形態にかかる配置最適化問題処理装置の構成を示すブロック図である。
【図２】本発明の一実施形態にかかる配置最適化問題処理装置におけるＣＰＵの構成を示す機能ブロック図である。
【図３】階層化されたノードについて説明するための図である。
【図４】系統空間における複数のノードの接続関係を示す図である。
【図５】階層化されたノードについて説明するための図である。
【図６】複数のノードを発生空間に配置した結果の一例を示す図である。
【図７】結合強度表の一例を示す図である。
【図８】染色体の構成の一例を示す図である。
【図９】複数のセルの接続関係を示す図である。
【図１０】階層化されたセルについて説明するための図である。
【図１１】複数のセルをＬＳＩ上に配置した結果の一例を示す図である。
【図１２】結合強度表の他の例を示す図である。
【図１３】（ａ），（ｂ）はともに、ハイパーノード又はノードの配置について説明するための図である。
【図１４】染色体に施される遺伝オペレーションについて説明するための図である。
【図１５】染色体に施される遺伝オペレーションについて説明するための図である。
【図１６】染色体に施される遺伝オペレーションについて説明するための図である。
【図１７】染色体に施される遺伝オペレーションについて説明するための図である。
【図１８】本発明の一実施形態にかかる配置最適化問題処理装置の動作を説明するためのフローチャートである。
【図１９】本発明の一実施形態にかかる配置最適化問題処理装置の動作を説明するためのフローチャートである。
【図２０】本発明の一実施形態にかかる配置最適化問題処理装置の動作を説明するためのフローチャートである。
【図２１】本発明の一実施形態にかかる配置最適化問題処理装置の動作を説明するためのフローチャートである。
【図２２】従来の配置最適化問題処理方法について説明するための図である。
【図２３】従来の配置最適化問題処理方法について説明するための図である。
【符号の説明】
１  配置最適化問題処理装置
４  ＣＰＵ
４１  ハイパーノード形成部
４２  ハイパーノード配置部
４３  ノード最適配置部
５  表示制御部
５Ａ  表示部
６  外部ファイル読出書込部
６Ａ  外部ファイル
７Ａ  印字部
７Ｂ  入力部
７Ｃ  印字制御部
７Ｄ  入力制御部
８  ハードディスク（コンピュータ読み取り可能な記録媒体）
１０〜１２  ハイパーノード
１００〜１０２，１１０，１１１，１２０〜１２２  非固定ノード
１００′〜１０２′，１１０′，１１１′，１２０′〜１２２′，１２２０〜１２２２  非固定セル
１３０ａ〜１３０ｈ  固定ノード
１３０ａ′〜１３０ｇ′固定セル
１４０  発生空間又は上位の階層のハイパーノード
１４１  ハイパーノード又はノード
１０００，１０００′  系統空間
１００１  グラフ
２０００  発生空間
２０００′  ＬＳＩ上の領域
【図１】
0003905959.tif 000004
【図２】
0003905959.tif 000005
【図３】
0003905959.tif 000006
【図４】
0003905959.tif 000007
【図５】
0003905959.tif 000008
【図６】
0003905959.tif 000009
【図７】
0003905959.tif 000010
【図８】
0003905959.tif 000011
【図９】
0003905959.tif 000012
【図１０】
0003905959.tif 000013
【図１１】
0003905959.tif 000014
【図１２】
0003905959.tif 000015
【図１３】
0003905959.tif 000016
【図１４】
0003905959.tif 000017
【図１５】
0003905959.tif 000018
【図１６】
0003905959.tif 000019
【図１７】
0003905959.tif 000020
【図１８】
0003905959.tif 000021
【図１９】
0003905959.tif 000022
【図２０】
0003905959.tif 000023
【図２１】
0003905959.tif 000024
【図２２】
0003905959.tif 000025
【図２３】
0003905959.tif 000026