(57)【要約】【課題】最適化処理に用いる評価関数の学習精度を向上させる。【解決手段】情報処理装置１０は、記憶部１１と演算部１２を有する。記憶部１１は、最適化処理に用いる評価関数１３の情報を記憶する。演算部１２は、被評価データ１４を生成する。演算部１２は、評価関数１３を用いて被評価データ１４に対して最適化処理を進めて、最適化処理を進めた後の被評価データ１４の状態に応じた評価値１５を算出する。演算部１２は、被評価データ１４および評価値１５に基づいて評価関数１３を更新する。【選択図】図１
2015148926.tif 000002
【特許請求の範囲】
【請求項１】
最適化処理に用いる評価関数の情報を記憶する記憶部と、
被評価データを生成し、前記評価関数を用いて前記被評価データに対して前記最適化処理を進めて、前記最適化処理を進めた後の前記被評価データの状態に応じた評価値を算出し、前記被評価データおよび前記評価値に基づいて前記評価関数を更新する演算部と、
を有する情報処理装置。
【請求項２】
前記演算部は、前記評価関数を更新する際に、前記最適化処理を進めた後の前記被評価データの状態に応じた評価値と現在の評価値との差に基づいて、前記被評価データの中から演算に用いる評価データを選択する、
請求項１記載の情報処理装置。
【請求項３】
前記演算部は、更新した評価関数を用いて他の被評価データに対して前記最適化処理を進めて、前記最適化処理を進めた後の前記他の被評価データの状態に応じた他の評価値を算出することで、前記更新した評価関数を更に更新する、
請求項１または２記載の情報処理装置。
【請求項４】
前記記憶部には、第１の評価関数の情報が記憶され、
前記演算部は、前記被評価データおよび前記評価値に基づいて第２の評価関数を算出した場合、前記第１の評価関数による評価結果と前記第２の評価関数による評価結果との比較に応じて、前記第１の評価関数を前記第２の評価関数に更新するか判断する、
請求項１乃至３の何れか一項に記載の情報処理装置。
【請求項５】
前記最適化処理は、複数段階の処理を含み、
前記評価値は、前記被評価データに対して前記最適化処理の途中であるｎ段階目（ｎは１以上の整数）までの処理を実行することで算出される、
請求項１乃至４の何れか一項に記載の情報処理装置。
【請求項６】
コンピュータが実行する評価関数学習方法であって、
被評価データを生成し、
評価関数を用いて前記被評価データに対して最適化処理を進めて、前記最適化処理を進めた後の前記被評価データの状態に応じた評価値を算出し、
前記被評価データおよび前記評価値に基づいて前記評価関数を更新する、
評価関数学習方法。
【請求項７】
コンピュータに、
被評価データを生成し、
評価関数を用いて前記被評価データに対して最適化処理を進めて、前記最適化処理を進めた後の前記被評価データの状態に応じた評価値を算出し、
前記被評価データおよび前記評価値に基づいて前記評価関数を更新する、
処理を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置、評価関数学習方法およびプログラムに関する。
【背景技術】
【０００２】
情報処理装置の演算能力が向上するに伴い、情報処理装置を用いて様々な組み合わせ最適化問題を解く試みが行われている。組み合わせ最適化問題の一例として、回路部品としてのセルをプリント板に配置するときに、ある評価基準（例えば、セル間の配線が短いことや占有面積が小さいことなど）の観点から好ましい配置パターンを探索する問題が挙げられる。組み合わせ最適化問題を情報処理装置に解かせることで、好ましい解を自動的に得ることができ、人間の経験や勘に依存していた作業を支援することができる。
【０００３】
組み合わせ最適化問題の中には、最適解を求めるための効率的なアルゴリズムが知られておらず、また、網羅的に全ての組み合わせを検討することが計算量の観点から難しい問題がある。そのような組み合わせ最適化問題については、ヒューリスティクスによって解を探索することがある。例えば、解を探索する最適化処理が複数のステップに分割可能であるとき、評価関数を用いて次の１ステップの操作候補の中から評価値の高い操作を選択していくことで、最適化処理を１ステップずつ進める方法がある。ヒューリスティクスを用いることで、最適解または最適解に近い準最適解を求めることができる。
【０００４】
なお、半導体集積回路のレイアウト設計においてセルを自動配置する集積回路配置装置が提案されている。この集積回路配置装置は、あるチップ領域を分割線（カットライン）によって２つの領域に分割し、カットラインを横切る配線（ネット）の数が最小になるようにセルを２つの領域に振り分ける。また、集積回路配置装置は、信号の遅延時間が大きいクリティカルパスを抽出し、遅延時間が小さくなるように、クリティカルパス上のセルおよびクリティカルパス上のネットに接続されたセルを移動させる。
【０００５】
また、ＬＳＩ（Large Scale Integration）素子の配置パターンを決定する要素配置装置が提案されている。この要素配置装置は、アルゴリズムまたはヒューリスティクスを用いて配置パターンの解を探索し、探索途中で得られる解候補を画面に逐次表示する。要素配置装置は、画面に表示した解候補に対して、要素間の相対的位置関係や制約条件を変更する操作を許容し、変更された相対的位置関係や制約条件を反映して探索を継続する。
【０００６】
また、集積回路のセルをチップ上に配置するセル配置方法が提案されている。このセル配置方法では、カットラインにより分割された２つの配置領域にセルを振り分けるとき、次の３つの条件が満たされるようにする。（１）カットラインと交差する信号線の数が最小になり、（２）信号線を引くことが可能な格子線の使用率が２つの配置領域の間で均等になり、（３）各配置領域についてセル面積の合計がその配置領域の面積を超えない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平８−９６０１３号公報
【特許文献２】特開平９−３３０３５０号公報
【特許文献３】特開平１０−２５６３７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記のように、情報処理装置に最適化処理を実行させるにあたっては、適切な評価関数を用意することになる場合がある。例えば、データから抽出される特徴量に対応する変数とパラメータ（例えば、特徴量にかける重みとしての係数など）とを含む評価関数を定義しておく。ただし、変数やパラメータが多い場合など、適切な評価関数を人間が定義すること（例えば、適切なパラメータの値を決定すること）が容易でない場合もある。
【０００９】
そこで、教師付き機械学習の手法を用いて、サンプルデータから評価関数を学習することが考えられる。例えば、人間から見て「良い」サンプルデータと「悪い」サンプルデータとを用意し、「良い」サンプルデータの特徴量から良い評価値が算出され「悪い」サンプルデータの特徴量から悪い評価値が算出されるような評価関数を算出する。例えば、評価関数に含まれるパラメータの値が、統計的手法を用いて算出される。
【００１０】
しかし、このような方法で評価関数を学習するにあたっては、人間がサンプルデータを用意することになるため、サンプル数が不足することがある。その結果、学習された評価関数の精度が低くなり、人間から見て「悪い」操作に対して良い評価値が算出されてしまうことで「悪い」操作が選択されるなど、最適化処理が非効率になってしまうことがある。一方、情報処理装置が自動生成したデータは、人間による「良い」「悪い」の判断が付与されていないため、そのまま評価関数の学習に用いることは容易でない。
【００１１】
１つの側面では、本発明は、最適化処理に用いる評価関数の学習精度を向上させる情報処理装置、評価関数学習方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
１つの態様では、記憶部と演算部とを有する情報処理装置が提供される。記憶部は、最適化処理に用いる評価関数の情報を記憶する。演算部は、被評価データを生成し、評価関数を用いて被評価データに対して最適化処理を進めて、最適化処理を進めた後の被評価データの状態に応じた評価値を算出し、被評価データおよび評価値に基づいて評価関数を更新する。また、１つの態様では、コンピュータが実行する評価関数学習方法が提供される。また、１つの態様では、コンピュータに実行させるプログラムが提供される。
【発明の効果】
【００１３】
１つの側面では、最適化処理に用いる評価関数の学習精度が向上する。
【図面の簡単な説明】
【００１４】
【図１】情報処理装置の例を示す図である。
【図２】設計装置のハードウェア例を示すブロック図である。
【図３】ＬＳＩレイアウトの最適化問題の例を示す第１の図である。
【図４】ＬＳＩレイアウトの最適化問題の例を示す第２の図である。
【図５】設計装置の機能例を示すブロック図である。
【図６】機械学習に用いるサンプルの生成例を示す図である。
【図７】機械学習に用いる誤差関数の例を示す図である。
【図８】パラメータ学習の手順例を示すフローチャートである。
【図９】１ステップ最適化の手順例を示すフローチャートである。
【図１０】コンテナパッキングの最適化問題の例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、情報処理装置の例を示す図である。
【００１６】
第１の実施の形態の情報処理装置１０は、組み合わせ最適化問題を解くときに用いる評価関数を、教師付き機械学習によって生成する。組み合わせ最適化問題の一例として、ＬＳＩ設計においてプリント板上の回路ブロックの配置パターンを決定することが挙げられる。評価関数を用いた最適化処理は、例えば、ＬＳＩ設計などの設計作業を支援するＣＡＤ（Computer Aided Design）ソフトウェアに実装される。情報処理装置１０が学習した評価関数は、情報処理装置１０または他の情報処理装置において利用され得る。
【００１７】
情報処理装置１０は、記憶部１１および演算部１２を有する。情報処理装置１０は、コンピュータと呼ばれてもよい。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性の記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）などの不揮発性の記憶装置でもよい。演算部１２は、例えば、プロセッサである。プロセッサは、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）であってもよく、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の集積回路を含んでもよい。プロセッサは、ＲＡＭなどの記憶装置（例えば、記憶部１１）に記憶されたプログラムを実行するものであってもよい。また、２以上のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼んでもよい。
【００１８】
記憶部１１は、最適化処理に用いる評価関数１３（第１の評価関数）を示す情報を記憶する。評価関数１３には、例えば、被評価データの特徴を示す特徴量に相当する１または２以上の変数と、変数以外のパラメータ（例えば、特徴量の重みに相当する係数）とが含まれる。その場合、評価関数１３の情報には、機械学習によって算出されたパラメータの値が含まれる。評価関数１３の変数に被評価データの特徴量を代入することで、評価関数１３による被評価データの評価結果を示す評価値を算出できる。被評価データの特徴量としては、例えば、回路ブロック間の配線のうちある条件を満たす配線の数や、プリント板上の各サブ領域に配置した回路ブロックの合計面積などが挙げられる。
【００１９】
演算部１２は、サンプルデータとしての被評価データを用いて、最適化処理に用いる評価関数の精度が上がるように評価関数を学習する（例えば、評価関数に含まれるパラメータの値を算出する）。後述するように、演算部１２は、記憶部１１に記憶された情報が示す評価関数１３（第１の評価関数）を評価関数１３ａ（第２の評価関数）に更新する。評価関数１３ａは、例えば、パラメータの値が評価関数１３とは異なる。ただし、評価関数１３ａは、評価関数１３に含まれない変数やパラメータを含んでいてもよい。
【００２０】
評価関数１３ａを算出するにあたり、演算部１２は、被評価データ１４を生成する。例えば、被評価データ１４は、配置を決定すべき回路ブロックや配置パターンの制約条件の情報を含む。被評価データ１４は、人間が作成したサンプルデータでなくてよく、所定のアルゴリズムに従ってまたはランダムに自動生成したものでよい。例えば、被評価データ１４は、人間が作成したサンプルデータをランダムに変形したものでもよい。
【００２１】
被評価データ１４が生成されると、演算部１２は、評価関数１３を用いて被評価データ１４に対して最適化処理を進める。最適化処理においては、演算部１２は、複数の候補の中から評価関数１３の評価値が良いものを選択していく。最適化処理が複数段階の部分最適化処理を含む場合、演算部１２は、最適化処理の途中であるｎ段階目（ｎは１以上の整数）までの部分最適化処理を実行してもよい。ｎは所定の固定値であってもよい。例えば、演算部１２は、プリント板の領域を２分割して評価値が高くなるように回路ブロックを２つのサブ領域に振り分けることを、階層的にｎ回繰り返す。
【００２２】
そして、演算部１２は、最適化処理を進めた後の被評価データ１４の状態に応じた評価値１５を算出する。例えば、演算部１２は、プリント板の領域をｎ回だけ階層的に分割したときの配置パターンの特徴量を評価関数１３の変数に代入することで、評価値１５を算出する。一般に、あるサンプルデータの良否がその時点では明確とは言えない場合であっても、最適化処理を進めると、元のサンプルデータが良かったか悪かったかが明確になることが多い。すなわち、最適化処理を進める前の特徴量から算出される評価値よりも、最適化処理を進めた後の特徴量から算出される評価値の方が、明確に良い値または明確に悪い値になることが多い。そこで、演算部１２は、生成した被評価データ１４から直接得られる評価値に代えて、最適化処理を進めた後の評価値１５を使用することとする。
【００２３】
評価値１５が算出されると、演算部１２は、生成した被評価データ１４および最適化処理を進めた後の評価値１５に基づいて、評価関数１３を評価関数１３ａに更新する（例えば、評価関数１３のパラメータの値を更新する）。例えば、演算部１２は、被評価データ１４の特徴量と評価値１５の組を含む複数の特徴量と評価値の組を回帰分析することで、評価関数１３ａのパラメータの値を算出する。このとき、演算部１２は、最適化処理を進める前の元のサンプルデータの特徴量と最適化処理を進めた後の状態の評価値との間の関係を推定することになる。評価関数１３ａの算出に用いる評価値１５は、被評価データ１４の良否をより明確に表している可能性が高いため「理想評価値」と言うこともできる。
【００２４】
この処理は、被評価データ１４の数が非常に多いと時間がかかることがある。その場合、自動的に生成されたデータのうち一部だけを使うことでデータを削減し、処理時間を短縮することができる。このとき、最初の評価値と評価値１５の差が小さいサンプルデータは、従来の学習結果がうまく機能していることを意味するため、推定処理に入力しても結果に大きな影響は与えない。しかし、差が小さいものを全く選択せずに推定処理を実行すると、既存の学習結果を壊してしまう可能性が生じる。したがって、データを選択する際に、評価値の差が大きいものが選択される確率を増やし、差が小さいものは低い確率で選択することで、データを削減しても修正に必要なデータを取りこぼす可能性を下げることが期待できる。例えば、最初の評価値と評価値１５の差が０〜１００のときは選択確率を１％、評価値の差が１００〜２００のときに選択確率を１０％というように、予め評価値の差に対応する確率を決めておき、乱数を使用して推定処理に使用するデータを選択すればよい。
【００２５】
第１の実施の形態の情報処理装置１０によれば、最適化処理に用いる評価関数を学習するにあたり、被評価データ１４に対して最適化処理を進めた後の評価値１５が算出され、被評価データ１４と評価値１５とに基づいて評価関数１３が更新される。これにより、被評価データ１４が人手によらずに自動生成されたものであってもその良否を推定することができ、被評価データ１４を利用して、評価関数１３の精度（例えば、評価関数１３に含まれるパラメータの値の精度）を向上させることができる。
【００２６】
よって、人間が用意するサンプルデータの不足を補うことができ、評価関数を教師付き機械学習によって算出するときの負担を軽減することができる。また、評価関数の精度が向上することで、人間から見て「悪い」候補に対して良い評価値が算出されてしまうことを抑制でき、最適解または準最適解を効率的に探索できるようになる。
【００２７】
［第２の実施の形態］
次に、第２の実施の形態を説明する。第２の実施の形態の設計装置１００は、ＬＳＩレイアウト設計を支援する。設計装置１００はコンピュータとして実現できる。その場合、設計装置１００は、ＬＳＩレイアウト設計に用いられるＣＡＤソフトウェアを実行する。
【００２８】
図２は、設計装置のハードウェア例を示すブロック図である。
設計装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。ＣＰＵ１０１は、第１の実施の形態の演算部１２の一例である。ＲＡＭ１０２またはＨＤＤ１０３は、第１の実施の形態の記憶部１１の一例である。
【００２９】
ＣＰＵ１０１は、プログラムの命令を実行する演算回路を含むプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されているプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、設計装置１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列実行してもよい。また、複数のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼んでもよい。
【００３０】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に用いるデータを一時的に記憶する揮発性メモリである。なお、設計装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【００３１】
ＨＤＤ１０３は、ＯＳ（Operating System）やアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。アプリケーションソフトウェアには、ＬＳＩレイアウト設計に用いるＣＡＤソフトウェアが含まれる。なお、設計装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。
【００３２】
画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、設計装置１００に接続されたディスプレイ２１に画像を出力する。ディスプレイ２１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ（ＰＤＰ：Plasma Display Panel）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。
【００３３】
入力信号処理部１０５は、設計装置１００に接続された入力デバイス２２から入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス２２としては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、設計装置１００に、複数の種類の入力デバイスが接続されていてもよい。
【００３４】
媒体リーダ１０６は、記録媒体２３に記録されたプログラムやデータを読み取る読み取り装置である。プログラムには、ＬＳＩレイアウト設計に用いるＣＡＤソフトウェアのプログラムが含まれ得る。記録媒体２３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。媒体リーダ１０６は、例えば、記録媒体２３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００３５】
通信インタフェース１０７は、ネットワーク２４に接続され、ネットワーク２４を介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース１０７は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【００３６】
なお、設計装置１００は、媒体リーダ１０６および通信インタフェース１０７の少なくとも一方を備えていなくてもよい。また、設計装置１００は、ユーザが操作する端末装置からリモートアクセスされる場合には、画像信号処理部１０４および入力信号処理部１０５の少なくとも一方を備えていなくてもよい。また、ディスプレイ２１および入力デバイス２２の少なくとも一方が、設計装置１００の筐体と一体に形成されていてもよい。
【００３７】
次に、設計装置１００を用いて解くＬＳＩレイアウトの最適化問題の例を説明する。
図３は、ＬＳＩレイアウトの最適化問題の例を示す第１の図である。
ここでは、パーティショニングベース配置法によって、回路部品としてのセルの最適な配置パターンを探索することを考える。入力データとして、複数のセルとセル間を結合するネットとセルを配置可能な領域とを示す設計データが与えられる。各セルには１以上のピンが設けられており、また、全体の領域のエッジには外部のＬＳＩと接続するためのピンが設けられていることがある。１つのネットは、２または３以上のピンに接続される。図３の例では、セル＃１〜＃８とセル＃１〜＃８を配置可能な領域Ｒが定義されている。図３では、ネットについては記載を省略するか簡略化した記載としている。
【００３８】
パーティショニングベース配置法では、設計装置１００は、領域を２分割して複数のセルを２つの領域に割り振ることを、各セルの位置が十分に限定されるまで階層的に繰り返す。ある領域を２分割してセルを割り振る操作が、ヒューリスティクスにおける１ステップに相当する。セルを２つの領域に割り振る方法（分割パターン）は複数通りあるため、設計装置１００は、１ステップ毎に、複数の分割パターンの中から評価関数によって算出される評価値の最も良い分割パターンを選択する。この評価値は、最適化処理の途中で算出するものであるため「中間評価値」と言うこともできる。設計装置１００は、選択した分割パターンを基準にして、次のステップとして分割した領域を更に２分割する。
【００３９】
一例として、設計装置１００は、領域ＲのＸ軸方向に分割線（カットライン）を引くことで、領域Ｒを面積の等しい領域Ｒ０と領域Ｒ１に分割する。設計装置１００は、セル＃１〜＃８それぞれを領域Ｒ０，Ｒ１の何れかに配置することで、分割パターンを生成する。各分割パターンについて、その特徴量を評価関数に代入することで評価値が算出される。図３の例では、領域Ｒ０にセル＃１，＃３，＃４，＃８が配置され、領域Ｒ１にセル＃２，＃５，＃６，＃７が配置されている。領域Ｒ０に配置されたセルと領域Ｒ１に配置されたセルとを接続するネットが存在する場合、当該ネットはカットラインと交差することになる。カットラインと交差するネットの数をカット数と呼ぶことがある。
【００４０】
領域Ｒの分割について評価値の最も良い分割パターンが選択されると、設計装置１００は、領域Ｒ０のＹ軸方向にカットライン（１ステップ前のカットラインと垂直なもの）を引くことで、領域Ｒ０を面積の等しい領域Ｒ００と領域Ｒ０１に分割する。設計装置１００は、前のステップで領域Ｒ０に配置されたセル＃１，＃３，＃４，＃８それぞれを領域Ｒ００，Ｒ０１の何れかに配置することで、分割パターンを生成する。図３の例では、領域Ｒ００にセル＃１，＃４が配置され、領域Ｒ０１にセル＃３，＃８が配置されている。
【００４１】
同様に、設計装置１００は、領域Ｒ１のＹ軸方向にカットラインを引くことで、領域Ｒ１を面積の等しい領域Ｒ１０と領域Ｒ１１に分割する。設計装置１００は、前のステップで領域Ｒ１に配置されたセル＃２，＃５，＃６，＃７それぞれを領域Ｒ１０，Ｒ１１の何れかに配置することで、分割パターンを生成する。図３の例では、領域Ｒ１０にセル＃５，＃６が配置され、領域Ｒ１１にセル＃２，＃７が配置されている。このように、パーティショニングベース配置法では、選択した上位の分割パターンに基づいて領域が細分化されて複数の部分最適化問題が生成されることが、階層的に繰り返される。
【００４２】
ここで、ステップ毎に複数の分割パターンの中から「良い」分割パターンを選択する基準としては、様々な基準が考えられる。一例として、カット数に着目するものとして、ミニカット法、バランス考慮カット法、重み付きのミニカット法などが挙げられる。
【００４３】
ミニカット法では、カット数、すなわち、カットラインと交差するネットの数を評価値とし、評価値が小さい分割パターンを良い分割パターンと定義する。ただし、一方の領域に配置したセルの合計面積と他方の領域に配置したセルの合計面積とが等しいかほぼ等しい（例えば、両者の差が閾値以下になる）ことを制約条件とする。
【００４４】
バランス考慮カット法は、２つの領域の間でセルの合計面積のバランスが取れてない分割パターンも一定の限度で許容するものである。バランス考慮カット法では、例えば、評価関数が式（１）のように与えられる。Ｃｕｔｓはカット数、Ｄ0は一方の領域に配置したセルの合計面積、Ｄ1は他方の領域に配置したセルの合計面積を表す。式（１）の第２項は、セルの合計面積の偏りを示す項である。ｗaはカット数に対して付与される重み、ｗbは合計面積の偏りに対して付与される重みである。すなわち、カット数と合計面積の偏りの２つが、一定の重みに基づいて評価される。重みｗa，ｗbを変えると、各分割パターンの良否の評価も変わり得る。重みｗa，ｗbは後述するように、最適なＬＳＩレイアウトを探索する前に行われる教師付き機械学習によって学習することができる。
【００４５】
【数１】
2015148926.tif 000003
【００４６】
重み付きのミニカット法は、全てのネットを均等に評価するのではなく、ネットに接続されたピンの数に応じてネットを重み付けして評価するものである。重み付きのミニカット法では、カットラインと交差するネットがピン数に応じて分類され、ピン数毎にカット数がカウントされる。重み付きのミニカット法では、例えば、評価関数が式（２）のように与えられる。Ｃｕｔｓ（ｉ）はピン数ｉのネットについてのカット数、ｗiはＣｕｔｓ（ｉ）に対して付与される重みである。評価値はｗ2×Ｃｕｔｓ（２），ｗ3×Ｃｕｔｓ（３），…の合計になり、評価値が小さいほど良い分割パターンとなる。重みｗiは後述するように教師付き機械学習によって学習することができる。
【００４７】
【数２】
2015148926.tif 000004
【００４８】
図４は、ＬＳＩレイアウトの最適化問題の例を示す第２の図である。
パーティショニングベース配置法によって回路部品としてのブロックをプリント板上に配置する、他の最適化問題の例を挙げる。ここでは、各ネットは２つのピンに接続されており、２つのブロックを結んでいるものとする。２つのブロックの間には、１または２以上のネットをグループ化したネットグループが接続される。ネットグループの中には、配線の長さがＸ以下であるという最大線長制約が与えられたものが含まれる。この最適化問題では、最大線長制約を満たすために要する面積に着目する。
【００４９】
例えば、評価関数が式（３）のように与えられる。Ｄはある領域に配置されたブロックの合計面積を表す。両端のブロックの何れも領域面積ｓの領域に含まれており、最大線長制約がなくｎ本のネットを含むネットグループについて、Ｎａ０（ｎ）は当該ネットグループの数、Ｗａ０（ｎ）は当該ネットグループの使用幅、Ｌａ０（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。狭い領域にブロックを配置すると配線が長くなる可能性があるため、ネットグループの線長は領域面積ｓに依存する。
【００５０】
また、両端のブロックの何れも領域面積ｓの領域に含まれており、最大線長制約がありｎ本のネットを含むネットグループについて、Ｎａ１（ｎ）は当該ネットグループの数、Ｗａ１（ｎ）は当該ネットグループの使用幅、Ｌａ１（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。また、両端のブロックの何れも領域面積ｓの領域に含まれており、少なくとも一方のブロックに最大線長制約のある他のネットグループが接続されておりｎ本のネットを含むネットグループについて、Ｎａ２（ｎ）は当該ネットグループの数、Ｗａ２（ｎ）は当該ネットグループの使用幅、Ｌａ２（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。最大線長制約のあるネットグループに接続されたブロックだけでなく、それと隣接するブロックも配置の制約を受けることを考慮したものである。１つのネットグループが、Ｎａ０またはＮａ１とＮａ２の両方にカウントされることがある。
【００５１】
また、両端のブロックの一方のみが領域面積ｓの領域に含まれており、最大線長制約がなくｎ本のネットを含むネットグループについて、Ｎｂ０（ｎ）は当該ネットグループの数、Ｗｂ０（ｎ）は当該ネットグループの使用幅、Ｌｂ０（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。また、両端のブロックの一方のみが領域面積ｓの領域に含まれており、最大線長制約がありｎ本のネットを含むネットグループについて、Ｎｂ１（ｎ）は当該ネットグループの数、Ｗｂ１（ｎ）は当該ネットグループの使用幅、Ｌｂ１（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。また、両端のブロックの一方のみが領域面積ｓの領域に含まれており、少なくとも一方のブロックに最大線長制約のある他のネットグループが接続されておりｎ本のネットを含むネットグループについて、Ｎｂ２（ｎ）は当該ネットグループの数、Ｗｂ２（ｎ）は当該ネットグループの使用幅、Ｌｂ２（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。
【００５２】
また、両端のブロックの何れも領域面積ｓの領域に含まれておらず、最大線長制約がなくｎ本のネットを含むネットグループについて、Ｎｃ０（ｎ）は当該ネットグループの数、Ｗｃ０（ｎ）は当該ネットグループの使用幅、Ｌｃ０（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。また、両端のブロックの何れも領域面積ｓの領域に含まれておらず、最大線長制約がありｎ本のネットを含むネットグループについて、Ｎｃ１（ｎ）は当該ネットグループの数、Ｗｃ１（ｎ）は当該ネットグループの使用幅、Ｌｃ１（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。また、両端のブロックの何れも領域面積ｓの領域に含まれておらず、少なくとも一方のブロックに最大線長制約のある他のネットグループが接続されておりｎ本のネットを含むネットグループについて、Ｎｃ２（ｎ）は当該ネットグループの数、Ｗｃ２（ｎ）は当該ネットグループの使用幅、Ｌｃ２（ｓ，ｎ）は当該ネットグループの線長の見積もりを表す。
【００５３】
【数３】
2015148926.tif 000005
【００５４】
Ｎａ０（ｎ），Ｎａ１（ｎ），Ｎａ２（ｎ），Ｎｂ０（ｎ），Ｎｂ１（ｎ），Ｎｂ２（ｎ），Ｎｃ０（ｎ），Ｎｃ１（ｎ），Ｎｃ２（ｎ）は、分割パターンから抽出される特徴量を示す変数である。一方、Ｗａ０（ｎ），Ｌａ０（ｓ，ｎ），Ｗａ１（ｎ），Ｌａ１（ｓ，ｎ），Ｗａ２（ｎ），Ｌａ２（ｓ，ｎ），Ｗｂ０（ｎ），Ｌｂ０（ｓ，ｎ），Ｗｂ１（ｎ），Ｌｂ１（ｓ，ｎ），Ｗｂ２（ｎ），Ｌｂ２（ｓ，ｎ），Ｗｃ０（ｎ），Ｌｃ０（ｓ，ｎ），Ｗｃ１（ｎ），Ｌｃ１（ｓ，ｎ），Ｗｃ２（ｎ），Ｌｃ２（ｓ，ｎ）はパラメータであり、後述するように教師付き機械学習によって学習することができる。
【００５５】
設計装置１００は、例えば、分割した２つの領域それぞれについて式（３）に基づく値を算出し、２つの領域の値の合計を分割パターンの評価値として用いる。式（３）の評価式から算出される評価値は、ブロックの合計面積とネットの合計面積とを含む見積もり面積を表している。この評価値が小さいものが良い分割パターンであると定義できる。
【００５６】
図４の例では、ある領域がカットラインによって、領域面積ｓの領域Ｒ０と領域面積ｓの領域Ｒ１とに分割されている。ある分割パターンとして、領域Ｒ０にはブロック＃１，＃２，＃３，＃４が配置され、領域Ｒ１にはブロック＃５が配置されている。
【００５７】
領域Ｒ０内においてブロック＃１とブロック＃２の間には、最大線長制約のない１６本のネットを含むネットグループが接続されている。よって、このネットグループには、パラメータＷａ０（１６），Ｌａ０（ｓ，１６）が適用される。領域Ｒ０内においてブロック＃３とブロック＃４の間には、最大線長制約のある１６本のネットを含むネットグループが接続されている。よって、このネットグループには、パラメータＷａ１（１６），Ｌａ１（ｓ，１６）が適用される。領域Ｒ０内においてブロック＃２とブロック＃３の間には、最大線長制約のない１２本のネットを含むネットグループが接続されている。また、ブロック＃３には、上記のように、最大線長制約のある他のネットグループが接続されている。よって、このネットグループには、パラメータＷａ０（１２），Ｌａ０（ｓ，１２）とパラメータＷａ２（１２），Ｌａ２（ｓ，１２）が適用される。
【００５８】
領域Ｒ０にあるブロック＃１から他の領域に向かって、最大線長制約のない６本のネットを含むネットグループが伸びている。よって、領域Ｒ０の評価値を算出するにあたってこのネットグループには、パラメータＷｂ０（６），Ｌｂ０（ｓ，６）が適用される。領域Ｒ０にあるブロック＃２から他の領域に向かって、最大線長制約のない８本のネットを含むネットグループが伸びている。よって、領域Ｒ０の評価値を算出するにあたってこのネットグループには、パラメータＷｂ０（８），Ｌｂ０（ｓ，８）が適用される。
【００５９】
領域Ｒ１にあるブロック＃５から他の領域に向かって、最大線長制約のない８本のネットを含むネットグループが伸びている。よって、領域Ｒ１の評価値を算出するにあたってこのネットグループには、パラメータＷｂ０（８），Ｌｂ０（ｓ，８）が適用される。また、両端のブロックの何れも領域Ｒ１になく最大線長制約のない６本のネットを含むネットグループが、領域Ｒ１を通過している。よって、領域Ｒ１の評価値を算出するにあたってこのネットグループには、パラメータＷｃ０（６），Ｌｃ０（ｓ，６）が適用される。
【００６０】
次に、設計装置１００における評価関数のパラメータの機械学習を説明する。
図５は、設計装置の機能例を示すブロック図である。
設計装置１００は、人手サンプル記憶部１１１、自動サンプル記憶部１１２、パラメータ記憶部１１３、初期値算出部１１４、自動サンプル生成部１１５、回帰分析部１１７、パラメータ更新部１１８および変数設定部１１９を有する。人手サンプル記憶部１１１、自動サンプル記憶部１１２およびパラメータ記憶部１１３は、例えば、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域として実装される。初期値算出部１１４、自動サンプル生成部１１５、回帰分析部１１７、パラメータ更新部１１８および変数設定部１１９は、例えば、ＣＰＵ１０１が実行するプログラムのモジュールとして実装される。
【００６１】
人手サンプル記憶部１１１は、パラメータの学習に用いる分割パターンのサンプルであって、人間が作成したサンプル（人手サンプル）を記憶する。人手サンプルは、良い分割パターンの例として使用することができる。人手サンプルは、例えば、複数のブロック・ブロック間を接続する複数のネット・領域面積・各ブロックの位置などの情報を含む。
【００６２】
自動サンプル記憶部１１２は、パラメータの学習に用いる分割パターンのサンプルであって、自動サンプル生成部１１５によって自動生成されたサンプル（自動サンプル）を記憶する。自動サンプルは、良い分割パターンである場合もあるし悪い分割パターンであることもある。自動サンプルは、例えば、複数のブロック・ブロック間を接続する複数のネット・領域面積・各ブロックの振り分け結果などの情報を含む。また、各自動サンプルには、自動サンプル生成部１１５によって算出された「理想評価値」が付与されている。理想評価値は、自動サンプルの良否の推定結果を表すと言うことができる。
【００６３】
パラメータ記憶部１１３は、評価関数に含まれるパラメータおよび算出されたパラメータの値を含むパラメータ情報を記憶する。初期値算出部１１４によって、パラメータの初期値が算出されてパラメータ記憶部１１３に格納される。その後、パラメータ更新部１１８によって、精度が上がるように１回または２回以上パラメータの値が更新され得る。図４および式（３）の例の場合、Ｗａ０（１），Ｌａ０（ｓ，１），Ｗａ０（２），Ｌａ０（ｓ，２），Ｗａ０（３），Ｌａ０（ｓ，３）などのパラメータの値が、パラメータ記憶部１１３に記憶される。なお、ネット数ｎが１以上所定の最大値以下の整数の範囲に限定してパラメータの値を用意してもよく、最大値を超える数のネットを含むネットグループに対してはｎ＝最大値に対応するパラメータの値を適用してもよい。
【００６４】
初期値算出部１１４は、人手サンプル記憶部１１１に記憶された人手サンプルを教師データとして用いて教師付き機械学習を行い、評価関数のパラメータの初期値を算出する。まず、初期値算出部１１４は、人手サンプルを良い分割パターンを示す良いサンプルとする。また、初期値算出部１１４は、ランダムな分割パターンを自動生成し、人手サンプルと異なるサンプルを悪い分割パターンを示す悪いサンプルとする。
【００６５】
そして、初期値算出部１１４は、良いサンプルから良い評価値（例えば、低い評価値）が算出され、悪いサンプルから悪い評価値（例えば、高い評価値）が算出されるように、評価関数のパラメータを学習する。パラメータの学習には、例えば、ＳＶＭ（Support Vector Machine）などの機械学習の手法を用いる。ＳＶＭでは、ベクトル空間上で良いサンプルと悪いサンプルを最も明確に分割できる境界面、すなわち、良いサンプルとの距離および悪いサンプルとの距離の両方が最大になる境界面が算出される。初期値算出部１１４は、算出したパラメータの値をパラメータ記憶部１１３に格納する。
【００６６】
自動サンプル生成部１１５は、パラメータの値の精度を上げるために、人手サンプルとは異なる自動サンプルを生成し、自動サンプルの良否を推定した理想評価値を算出する。まず、自動サンプル生成部１１５は、人手サンプル記憶部１１１に記憶された人手サンプルの変形などを通じて、人手サンプルと異なる自動サンプルを生成する。
【００６７】
次に、自動サンプル生成部１１５は、生成した自動サンプルから始めて、所定ステップ（例えば、３ステップ）だけ最適化処理を進める。このとき、各ステップで分割パターンの選択に用いる評価関数のパラメータの値としては、パラメータ記憶部１１３に現在記憶されているもの（例えば、初期値算出部１１４が算出した初期値）を使用する。例えば、自動サンプル生成部１１５は、最適化処理を３ステップ進めることで、自動サンプルの分割パターンが示す各領域を更に８分割した分割パターンを生成する。自動サンプル生成部１１５は、最適化処理を１ステップずつ進める１ステップ最適化部１１６を有する。
【００６８】
そして、自動サンプル生成部１１５は、所定ステップだけ最適化処理を進めた後の分割パターンに対応する理想評価値を算出する。理想評価値は、所定ステップだけ最適化処理を進めた後の分割パターンの特徴量を、パラメータ記憶部１１３に記憶されているパラメータの値を適用した評価関数に代入することで算出できる。例えば、８分割された各領域の評価値の合計を、自動サンプルに対応する理想評価値とする。すなわち、自動サンプルの分割パターン自体の特徴量から算出される評価値に代えて、所定ステップだけ最適化処理を進めた後の分割パターンの特徴量から算出される評価値が、パラメータの学習に使用されることになる。最適化処理を進めることで自動サンプルの時点よりも分割パターンの良否がより明確になる可能性が高いため、理想評価値は、自動サンプルの良否を推定したものと言うことができる。自動サンプル生成部１１５は、生成した自動サンプルと算出した理想評価値とを対応付けて、自動サンプル記憶部１１２に格納する。この処理において、自動サンプル生成部１１５は、自動サンプルの数が非常に多い場合は、第１の実施の形態の場合と同様に、データのうち一部だけを使うことでデータを削減し、処理時間を減らすことができる。このとき、選択を乱数に基づいて確率的に行い、理想評価値と現在の評価値の差が大きいサンプルを自動サンプル記憶部１１２に格納する確率を増やすことで、データを削減しても修正に必要なデータを取りこぼす可能性を下げることが期待できる。
【００６９】
回帰分析部１１７は、自動サンプル記憶部１１２に記憶された自動サンプルおよび理想評価値を用いて、回帰分析を行いパラメータの値を算出する。まず、回帰分析部１１７は、各自動サンプルの分割パターンから、ブロックの合計面積やネットグループ数など（式（３）のＤやＮａ０（１），Ｎａ０（２）など）の特徴量を抽出する。そして、回帰分析部１１７は、自動サンプルから抽出した特徴量を評価関数に代入することで算出される評価値と当該自動サンプルに対応付けられた理想評価値との誤差が最小になるように、パラメータの値を調整する。パラメータの学習には、例えば、ε−ＳＶＲ（Support Vector Regression）などの回帰分析手法を用いることができる。
【００７０】
パラメータ更新部１１８は、回帰分析部１１７によって算出されたパラメータの値が、パラメータ記憶部１１３に記憶されている現在のパラメータの値と比べて改善しているか判断する。改善していると判断した場合、パラメータ更新部１１８は、パラメータ記憶部１１３に記憶されたパラメータの値を、回帰分析部１１７によって算出されたパラメータの値へと更新する。その場合、設計装置１００は、更新されたパラメータの値を用いて、再度パラメータの学習を進めてもよい。一方、改善していないと判断した場合、パラメータ更新部１１８は、回帰分析部１１７によって算出されたパラメータの値を採用しない。その場合、設計装置１００は、パラメータの学習を終了してもよい。
【００７１】
パラメータの値が改善しているかは、自動サンプルなどのサンプルを用いて検証することができる。例えば、設計装置１００は、あるサンプルの分割パターンから始めて最後まで（個々のブロックの位置が十分に限定されるまで）最適化処理を行い、最終的な分割パターンを生成する。パラメータ更新部１１８は、現在のパラメータの値を用いて算出される当初の分割パターンの評価値と最終的な分割パターンの良否との相関を確認する。また、パラメータ更新部１１８は、新たなパラメータの値を用いて算出される当初の分割パターンの評価値と最終的な分割パターンの良否との相関を確認する。
【００７２】
そして、パラメータ更新部１１８は、この相関が改善している場合に、パラメータの値が改善していると判断する。最適化後の分割パターンが「良い」ときに当初の分割パターンについて良い評価値が算出され、かつ、最適化後の分割パターンが「悪い」ときに当初の分割パターンについて悪い評価値が算出されていれば、相関が強いと言える。パラメータ更新部１１８は、相関の強弱を示す指標値として相関係数を算出してもよい。
【００７３】
変数設定部１１９は、ユーザからの入力に応じて、評価関数に新たな変数や新たなパラメータを追加することを許容する。ユーザから変数やパラメータの追加が指示されると、変数設定部１１９は、追加する変数やパラメータを回帰分析部１１７に通知する。すると、回帰分析部１１７は、次に回帰分析を行うとき、追加した変数に対応する新たな特徴量を自動サンプルから抽出し、変数およびパラメータが追加された新たな評価関数について回帰分析を行う。変数やパラメータの追加は、自動サンプル生成部１１５、回帰分析部１１７およびパラメータ更新部１１８がパラメータの学習を繰り返している途中で行うことも可能である。よって、ユーザは、評価関数の学習状況を見ながら、評価値が改善されるような好ましい変数やパラメータを評価関数に適宜追加することができる。
【００７４】
図６は、機械学習に用いるサンプルの生成例を示す図である。
前述のように、自動サンプル生成部１１５は、人手サンプルに基づいて自動サンプルを生成する。これにより、人手サンプルの不足をカバーすることができる。自動サンプルの生成方法としては、最適化問題の内容に応じて様々な生成方法が考えられる。
【００７５】
例えば、自動サンプル生成部１１５は、人手サンプルが示すＬＳＩレイアウトの中からランダムに一部分の領域を切り出して部分問題として採用する。すなわち、自動サンプル生成部１１５は、切り出した領域に含まれるブロックやブロック間を接続するネットの情報を維持しつつブロックの位置情報を消去することで、切り出した領域のレイアウトを初期化して自動サンプルのベースとして使用する。このとき、切り出した領域の内と外とを結合するネットについては、領域のエッジにピンが設定されていると仮定して取り扱う。自動サンプル生成部１１５は、切り出して初期化した領域について１ステップだけ最適化処理を進めた（領域を１回分割した）分割パターンを、自動サンプルとして使用する。
【００７６】
図６の例では、人手サンプルが示す全体領域の中にブロック＃１〜＃８が配置されている。ブロック＃１とブロック＃６、ブロック＃２とブロック＃７、ブロック＃５とブロック＃８とがネットで接続されている。自動サンプル生成部１１５は、この全体領域の中からブロック＃１〜＃５を含みブロック＃６〜＃８を含まない領域を抽出したとする。すると、自動サンプル生成部１１５は、ブロック＃１〜＃５の位置情報を消去する。また、自動サンプル生成部１１５は、ブロック＃１，＃６間のネットと領域のエッジとが交差する点にピンが設定され、当該ピンとブロック＃１とがネットで接続されているものとして扱う。ブロック＃２，＃７間のネットおよびブロック＃５，＃８間のネットについても同様に取り扱う。そして、自動サンプル生成部１１５は、領域を２つに分割してブロック＃１〜＃５を振り分けた分割パターンを、自動サンプルとして生成する。
【００７７】
なお、他の自動サンプルの生成方法として、ブロックの大きさや配線層の数や配線ピットなどの設計条件を、人手サンプルのものからランダムに変更する方法も考えられる。
図７は、機械学習に用いる誤差関数の例を示す図である。
【００７８】
前述のように、初期値算出部１１４は、分割パターンのサンプルから抽出される特徴量と当該サンプルの良否の判断結果とから、良いサンプルに良い評価値が付き悪いサンプルに悪い評価値が付くように評価関数のパラメータを学習する。例えば、初期値算出部１１４は、式（４）の値が最小になるようなパラメータの値を探索する。パラメータの値の探索においては、例えば、最急降下法などの探索方法を用いることができる。
【００７９】
式（４）を用いる場合、良いサンプルと悪いサンプルの組み合わせが全て列挙される。ｄｉｆｆjは、ｊ番目の組み合わせについて、良いサンプルの評価値と悪いサンプルの評価値との差を表す。ｅｒｒ０（ｘ）は誤差関数であり、Ｌは所定の正の値である。ｅｒｒ０（ｘ）は、図７（Ａ）に示すように、ｘが−Ｌ以下のときは０を返し、ｘが−Ｌより大きいときはｘ＋Ｌを返す。すなわち、式（４）の第１項は、−Ｌより大きいｄｉｆｆjの値の和を最小化する目的を示している。λは所定の値であり、ｗiは評価関数に含まれるｉ番目のパラメータを表す。式（４）の第２項は、過学習を抑制する正規化項である。ただし、パラメータの値の２乗和を、パラメータの値の絶対値の和に置き換えてもよい。
【００８０】
【数４】
2015148926.tif 000006
【００８１】
また、前述のように、回帰分析部１１７は、分割パターンのサンプルから抽出される特徴量と当該サンプルの理想評価値とから、特徴量と理想評価値との関係を最も適切に表現できるように評価関数のパラメータを学習する。例えば、回帰分析部１１７は、式（５）の値が最小になるようなパラメータの値を探索する。パラメータの値の探索においては、例えば、最急降下法などの探索方法を用いることができる。
【００８２】
式（５）において、ｖjはｊ番目のサンプルの理想評価値を表し、ａjはｊ番目のサンプルの特徴量の集合を表す。よって、ｖj−ｆ（ａj）はｊ番目のサンプルの理想評価値とｊ番目のサンプルの特徴量を評価関数に代入したときの評価値との誤差を表している。ｅｒｒ１（ｘ）は誤差関数であり、εは所定の正の値である。ｅｒｒ１（ｘ）は、図７（Ｂ）に示すように、ｘの絶対値がε以下のときは０を返し、ｘの絶対値がεより大きいときは｜ｘ｜−εを返す。すなわち、式（５）の第１項は、評価値の誤差の絶対値のうちεを超えるものの和を最小化する目的を示している。ただし、評価値の誤差の絶対値を、評価値の誤差の２乗に置き換えてもよい。式（４）と同様に、第２項は正規化項である。
【００８３】
【数５】
2015148926.tif 000007
【００８４】
次に、設計装置１００が実行するパラメータの機械学習の手順を説明する。
図８は、パラメータ学習の手順例を示すフローチャートである。
（Ｓ１０）初期値算出部１１４は、人手サンプル記憶部１１１に記憶された複数の分割パターンのサンプル（人手サンプル）を、良いサンプルとして取得する。
【００８５】
（Ｓ１１）初期値算出部１１４は、ランダムに複数の分割パターンを生成し、生成した分割パターンのうち人手サンプルと異なるものを悪いサンプルとして採用する。
（Ｓ１２）初期値算出部１１４は、ステップＳ１０の良いサンプルとステップＳ１１の悪いサンプルとを用いて、評価関数のパラメータの初期値を算出する。例えば、初期値算出部１１４は、良いサンプルおよび悪いサンプルそれぞれからネットグループ数Ｎａ０（１），Ｎａ０（２），…などの特徴量を抽出する。初期値算出部１１４は、ＳＶＭなどの教師付き機械学習の手法を用いて、良いサンプルの特徴量から良い評価値が算出され悪いサンプルの特徴量から悪い評価値が算出されるように、使用幅Ｗａ０（１），Ｗａ０（２），…や線長Ｌａ０（１），Ｌａ０（２），…などのパラメータの値を算出する。初期値算出部１１４は、算出したパラメータの値をパラメータ記憶部１１３に格納する。
【００８６】
（Ｓ１３）自動サンプル生成部１１５は、人手サンプル記憶部１１１に記憶された人手サンプルからランダムに一部分の領域を切り出して各ブロックの位置情報を消去することで、出現するブロックやネットがランダムに変化する設計データを自動生成する。ただし、自動サンプル生成部１１５は、ブロックサイズや配線層の数や配線ピットなどの設計条件をランダムに変更するなど、他の方法によって設計データを自動生成してもよい。自動サンプル生成部１１５は、最適化問題の内容に応じて生成方法を選択してもよい。
【００８７】
（Ｓ１４）自動サンプル生成部１１５は、ステップＳ１３で切り出した領域についての設計データに対して、１ステップ最適化部１１６を呼び出すことで最適化処理を１ステップだけ進める。このとき、ステップＳ１２で算出されたパラメータの初期値（または、その後に以下のステップＳ２０で更新されたパラメータの値）を適用した評価関数が使用される。例えば、１ステップ最適化部１１６は、ステップＳ１３で切り出した領域を２分割して、ブロックを２つの領域に割り振る。自動サンプル生成部１１５は、１ステップ進んだ後の分割パターンを自動サンプルＰとして取得する。
【００８８】
（Ｓ１５）自動サンプル生成部１１５は、ステップＳ１１５で生成された自動サンプルＰに対して、１ステップ最適化部１１６を複数回呼び出すことで最適化処理を更に３ステップ進める。このとき、ステップＳ１２で算出されたパラメータの初期値（または、その後に以下のステップＳ２０で更新されたパラメータの値）を適用した評価関数が使用される。例えば、ステップＳ１４で２分割した領域それぞれが更に８分割される。
【００８９】
（Ｓ１６）自動サンプル生成部１１５は、ステップＳ１５を実行した後の分割パターンから理想評価値を算出する。例えば、自動サンプル生成部１１５は、細分化された各領域について、ネットグループ数Ｎａ０（１），Ｎａ０（２），…などの特徴量と使用幅Ｗａ０（１），Ｗａ０（２），…や線長Ｌａ０（１），Ｌａ０（２），…などのパラメータの値とから算出された、見積もり面積についての評価値を取得する。自動サンプル生成部１１５は、細分化された各領域の評価値を合計したもの（見積もり面積の合計）を理想評価値とする。ただし、各領域の評価値を合計する方法は一例であり、他の方法で理想評価値を算出してもよい。自動サンプル生成部１１５は、算出した理想評価値とステップＳ１４で生成した自動サンプルＰとを対応付けて、自動サンプル記憶部１１２に格納する。
【００９０】
（Ｓ１７）自動サンプル生成部１１５は、回帰分析を行うのに十分な数の自動サンプルＰが得られたか判断する。自動サンプルＰの所要数は、ユーザによって予め指定されてもよい。所要数の自動サンプルＰが得られた場合はステップＳ１８に処理が進み、所要数の自動サンプルＰが得られていない場合はステップＳ１３に処理が進む。
【００９１】
（Ｓ１８）回帰分析部１１７は、自動サンプルＰと理想評価値との複数の組み合わせを用いて、評価関数のパラメータの値を算出する。例えば、回帰分析部１１７は、２分割された領域それぞれのネットグループ数Ｎａ０（１），Ｎａ０（２），…など、各自動サンプルＰ（ステップＳ１５で３ステップ進める前のもの）から特徴量を抽出する。そして、回帰分析部１１７は、ε−ＳＶＲなどの回帰分析の手法を用いて、評価関数から算出される評価値と理想評価値との誤差が最小になるように、使用幅Ｗａ０（１），Ｗａ０（２），…や線長Ｌａ０（１），Ｌａ０（２），…などのパラメータの値を算出する。
【００９２】
（Ｓ１９）パラメータ更新部１１８は、ステップＳ１８で算出したパラメータの値が、パラメータ記憶部１１３に記憶されている現在のパラメータの値より改善しているか検証する。パラメータの値が改善していると判断される場合はステップＳ２０に処理が進み、改善していないと判断される場合はステップＳ２１に処理が進む。
【００９３】
改善を検証するにあたり、例えば、設計装置１００は、複数のサンプルそれぞれに対して最適化処理を最後まで進めて最終的なブロック配置の良否を判断する。パラメータ更新部１１８は、現在のパラメータの値を用いて算出される当初の分割パターンの評価値と最終的なブロック配置の良否との相関を判断する（例えば、相関係数などの指標値を算出する）。また、パラメータ更新部１１８は、新たなパラメータの値を用いて算出される当初の分割パターンの評価値と最終的なブロック配置の良否との相関を判断する。後者の相関が前者より改善していれば、パラメータ更新部１１８は、パラメータの値が改善したと判断することができる。ただし、他の方法で改善の有無を判断してもよい。
【００９４】
（Ｓ２０）パラメータ更新部１１８は、パラメータ記憶部１１３に記憶されたパラメータの値を、ステップＳ１８で算出されたものに更新する。
（Ｓ２１）自動サンプル生成部１１５は、パラメータ学習の終了条件が満たされたか判断する。終了条件としては、例えば、パラメータの値が改善しなくなったことや、ステップＳ１３〜Ｓ２０の処理が所定回数繰り返されたことなどが挙げられる。終了条件が満たされていない場合はステップＳ１３に処理が進み、パラメータの学習が継続される。終了条件が満たされた場合はパラメータの学習が終了する。
【００９５】
図９は、１ステップ最適化の手順例を示すフローチャートである。
このフローチャートの処理は、上記のステップＳ１４，Ｓ１５で実行される。
（Ｓ３０）１ステップ最適化部１１６は、領域を２つに分割する。
【００９６】
（Ｓ３１）１ステップ最適化部１１６は、分割前の領域に含まれる複数のブロックを分割した２つの領域に割り振ることで、分割パターンを１つ生成する。分割パターンを探索する方法としては、例えば、貪欲法や局所探索法などの近似アルゴリズムを用いる。
【００９７】
（Ｓ３２）１ステップ最適化部１１６は、ステップＳ３１で生成した分割パターンから特徴量を抽出する。１ステップ最適化部１１６は、パラメータ記憶部１１３に記憶されている現在のパラメータの値を適用した評価関数に、抽出した特徴量を代入することで、ステップＳ３１の分割パターンの良否を示す評価値を算出する。この評価値は、最適化処理の途中における評価を示すものであるため「中間評価値」と呼ぶこともできる。
【００９８】
（Ｓ３３）１ステップ最適化部１１６は、ステップＳ３２で算出された評価値が、現在記録しているもの（過去に算出された最良の評価値）よりも改善しているか判断する。評価値が小さいほど良い評価を示す場合、１ステップ最適化部１１６は、ステップＳ３２で算出された評価値が現在記録しているものより小さいか判断する。評価値が改善している場合はステップＳ３４に処理が進み、改善していない場合（評価値が現在記録しているものと同じか悪い場合）はステップＳ３５に処理が進む。なお、記録している評価値がない場合（最初の分割パターンの評価値である場合）は、改善しているものとして扱う。
【００９９】
（Ｓ３４）１ステップ最適化部１１６は、ステップＳ３１で生成した分割パターンを、現在までに探索された中で最良の分割パターンとして記録しておく。また、ステップＳ３２で算出した評価値を、現在までに探索された範囲で最良の評価値として記録しておく。このとき、前回記録しておいた分割パターンや評価値は削除してよい。
【０１００】
（Ｓ３５）１ステップ最適化部１１６は、分割パターンの探索の終了条件が満たされたか判断する。終了条件は、ステップＳ３１で使用する近似アルゴリズムに依存する。終了条件としては、例えば、分割パターンを所定数生成したことや、所定回数連続して評価値が改善しなかったことなどが挙げられる。終了条件が満たされた場合はステップＳ３６に処理が進み、終了条件が満たされていない場合はステップＳ３１に処理が進む。
【０１０１】
（Ｓ３６）１ステップ最適化部１１６は、最後に記録した分割パターン、すなわち、探索された中で評価値が最も良い（例えば、評価値が最も小さい）分割パターンを取得し、最適化処理を１ステップ進めた分割パターンとして出力する。
【０１０２】
以上、ＬＳＩレイアウトの最適化問題を例にして、設計装置１００による評価関数の学習について説明した。ただし、第２の実施の形態の評価関数の学習方法は、ＬＳＩレイアウト以外の他の分野の最適化問題にも適用することが可能である。以下では、他の最適化問題の例として、コンテナパッキングの最適化問題を説明する。
【０１０３】
図１０は、コンテナパッキングの最適化問題の例を示す図である。
ここでは、様々な大きさをもつ複数の直方体の貨物を、同じ大きさの複数のコンテナに分散して詰め込むことを考える。様々なパッキングパターンのうち、使用するコンテナの数が少なくなるものを良いパッキングパターンとして評価する。
【０１０４】
あるパッキングパターンからは、例えば、図１０に示すような特徴量が抽出される。使用されるｍ個のコンテナを、充足率（コンテナの容量に対する貨物の合計容量の割合）に基づいてソートし、充足率が高い順に各コンテナに識別番号を付与する。また、貨物をそのサイズに応じて複数の区分に分類しておく。例えば、幅（ｘ軸）の単位長をＵｘ、奥行（ｙ軸）の単位長をＵｙ、高さ（ｚ軸）の単位長をＵｚとする。（Ｕｘ，Ｕｙ，Ｕｚ）以内に収まる貨物を区分＃１、区分＃１のサイズを超えるが（２Ｕｘ，Ｕｙ，Ｕｚ）以内に収まる貨物を区分＃２、区分＃２のサイズを超えるが（２Ｕｘ，２Ｕｙ，Ｕｚ）以内に収まる貨物を区分＃３、区分＃２のサイズを超えるが（３Ｕｘ，Ｕｙ，Ｕｚ）以内に収まる貨物を区分＃４というように、複数の区分を定義しておくことができる。
【０１０５】
すると、特徴量として、コンテナ毎に各区分の貨物の数を抽出することができる。図１０において、Ｎi,jはｊ番目のコンテナ（コンテナ＃ｊ）に詰め込まれた区分＃ｉの貨物の数を表す。コンテナパッキングでは、例えば、評価関数が式（６）のように与えられる。Ｆｕｌｌｎｅｓｓは使用されているコンテナ全体の充足率を表す。ｗ0は充足率に付与する重みを表し、ｗi,jはＮi,jに付与する重みを表す。この評価関数では、Ｆｕｌｌｎｅｓｓ，Ｎi,jが変数であり、ｗ0，ｗi,jがパラメータである。
【０１０６】
【数６】
2015148926.tif 000008
【０１０７】
この最適化問題に対しては、例えば、探索アルゴリズムとしてタブーサーチ法を用いることが考えられる。コンテナパッキングのタブーサーチ法については、例えば、Zhihong Jin, Takahiro Ito and Katsuhisa Ohno, "The Three-Dimensional Bin Packing Problem and Its Practical Algorithm", JSME (Japan Society of Mechanical Engineers) International Journal, Vol.46 No.1, pp.60-66, 2004-06-25に記載がある。
【０１０８】
タブーサーチ法を用いた場合、最初に、複数のコンテナに対してランダムに貨物が割り振られる。各コンテナの中では、タブーサーチ法を再帰的に用いることで（例えば、コンテナ内の領域を分割していくことで）、コンテナ内での各貨物の位置を算出できる。そして、初期のパッキングパターンから始めて、幾つかの貨物をコンテナ間で移動させる。例えば、あるコンテナに含まれる１または２以上の貨物を、空のコンテナまたは空でない他のコンテナに移動させる。また、例えば、あるコンテナに含まれる１または２以上の貨物と、他のコンテナに含まれる１または２以上の貨物とを交換する。
【０１０９】
幾つかの貨物の移動１回が、ヒューリスティクスにおける１ステップに相当する。移動によって得られる複数のパッキングパターンの中から、評価関数によって算出される評価値が最も良いものが選択され、選択されたパッキングパターンに基づいて次のステップが実行される。このとき、直近Ｎ回（例えば、直近７回）採用したパッキングパターンをタブーリストとして記憶しておき、タブーリストに含まれるパッキングパターンは次のステップで使用しないようにする。これにより、同じ貨物の移動が繰り返されるのを防ぐ。
【０１１０】
設計装置１００は、ＬＳＩレイアウトの最適化の場合と同様に、コンテナパッキングの最適化に用いる評価関数のパラメータｗ0，ｗi,jを教師付き機械学習によって学習することができる。例えば、設計装置１００は、人間が作成したパッキングパターンを人手サンプルとして取得し、人手サンプルからランダムに幾つかの貨物を交換したパッキングパターンを生成する。そして、設計装置１００は、生成したパッキングパターンから元の人手サンプルに戻す貨物の移動が良い交換操作であり、他の貨物の移動が悪い交換操作であると評価されるように、評価関数のパラメータの初期値を算出する。
【０１１１】
また、設計装置１００は、例えば、人手サンプルからランダムに数ステップだけ貨物を移動させることで、パッキングパターンの自動サンプルを生成する。そして、設計装置１００は、上記で算出したパラメータの初期値を適用した評価関数を用いて、自動サンプルに対して数ステップ（例えば、３ステップ）最適化処理を進め、数ステップ進めた後のパッキングパターンから理想評価値を算出する。設計装置１００は、生成した自動サンプルと算出した理想評価値とを回帰分析し、パラメータの値を更新することができる。
【０１１２】
第２の実施の形態の設計装置１００によれば、最適化処理に用いる評価関数を学習するにあたり、自動サンプルが生成され、自動サンプルに対して最適化処理を進めた後の評価値が理想評価値として算出される。そして、自動サンプルと理想評価値とを回帰分析することで評価関数のパラメータの値が更新される。これにより、自動サンプルの良否を推定することができ、自動サンプルを利用して評価関数のパラメータの精度を向上させることができる。よって、人間が用意する人手サンプルの不足を補うことができ、評価関数を教師付き機械学習によって算出するときの負担を軽減することができる。特に、変数やパラメータの数が多い場合でも、回帰分析を行うのに十分な数のサンプルを用意できる。
【０１１３】
また、評価関数の精度が向上することで、人間から見て「悪い」候補に対して良い評価値が算出されてしまうことを抑制でき、最適解または準最適解を効率的に探索できるようになる。また、評価関数の学習を繰り返す中で、好ましい新たな変数やパラメータを追加することができるなど、ユーザによって評価関数を適宜変形することが可能となる。
【０１１４】
なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１０にプログラムを実行させることで実現することができる。第２の実施の形態の情報処理は、設計装置１００にプログラムを実行させることで実現することができる。
【０１１５】
プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体２３）に記録しておくことができる。記録媒体としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体からＨＤＤなどの他の記録媒体（例えば、ＨＤＤ１０３）にプログラムを複製して（インストールして）実行してもよい。
【符号の説明】
【０１１６】
１０  情報処理装置
１１  記憶部
１２  演算部
１３，１３ａ  評価関数
１４  被評価データ
１５  評価値
【図１】
2015148926.tif 000009
【図２】
2015148926.tif 000010
【図３】
2015148926.tif 000011
【図４】
2015148926.tif 000012
【図５】
2015148926.tif 000013
【図６】
2015148926.tif 000014
【図７】
2015148926.tif 000015
【図８】
2015148926.tif 000016
【図９】
2015148926.tif 000017
【図１０】
2015148926.tif 000018