(57)【要約】【課題】遺伝的アルゴリズムにおいて最適解に近づく速度の向上を維持しつつ、広域探索による局所解からの離脱可能性の向上を両立させること。【解決手段】遺伝的アルゴリズム実行装置は、親個体２１の収束状態を示す混雑度を求め、更に前記混雑度から突然変異確率を決定する突然変異確率決定手段２２と、前記突然変異確率に基づき、前記個体の遺伝子情報に突然変異処理を施す突然変異処理手段２３とを備える。母集団２０において局所解の固体が支配的になった場合には混雑度が増加するので突然変異確率が増加し、広域探索機能がより強化さる。このような突然変異確率を動的に制御する特殊な突然変異処理によって、最適解に近づく速度の向上という効果を維持しつつ、局所解に捕らわれずに最適解に到達する確率が向上するという効果を両立させることができる。【選択図】図３
2008242927.tif 000002
【特許請求の範囲】
【請求項１】
複数の個体の収束状態を示す混雑度を求める混雑度算出手段と、
前記混雑度から突然変異確率を決定する突然変異確率決定手段と、
前記突然変異確率に基づき、前記子個体の遺伝子情報に突然変異処理を施す突然変異処理手段と
を備えたことを特徴とする遺伝的アルゴリズム実行装置。
【請求項２】
前記混雑度算出手段は、遺伝子情報であるパラメータ毎に、親個体のパラメータの最大値から最小値を減算したものを当該パラメータの取り得る最大値から最小値を減算した値で除算し、これを全てのパラメータについて平均した平均値を求め、１から前記平均値を減算した値を前記混雑度とすることを特徴とする請求項１に記載の遺伝的アルゴリズム実行装置。
【請求項３】
更に、
母集団から所定個数だけ親個体を選択して前記複数の親個体とする親個体選択手段と、
前記複数の親個体から複数の子個体を生成する子個体生成手段と、
前記子個体生成手段が生成した複数の子個体について評価値を算出する評価値算出手段と、
前記複数の子個体の中から評価値の良い所定個数の個体を選択する子個体選択手段と、
親個体の母集団からランダムに所定個数だけ親個体を取り出す親個体取り出し手段と、
前記子個体選択手段によって選択された子個体および前記親個体取り出し手段によって取り出された親個体の中から評価値の良い所定個数の個体を選択して、前記母集団に加える上位個体選択手段と
を備えたことを特徴とする請求項１に記載の遺伝的アルゴリズム実行装置。
【請求項４】
前記子個体生成手段は、親個体の遺伝子情報によって表されるベクトル空間における重心を求め、前記重心および親遺伝子情報の値から定められるベクトル空間上の超多面体の内部に子個体群の生成範囲を決定する生成範囲決定手段を備えたことを特徴とする請求項３に記載の遺伝的アルゴリズム実行装置。
【請求項５】
前記親個体選択手段は、評価値のよい個体ほど選択される確率が大きくなるように所定個数の個体を選択する重み付け選択手段と、
母集団の個体をランダムに２次元配列し、前記重み付け選択手段によって選択された個体およびこの個体と隣接する個体を所定個数選択する２次元選択手段と
を備えたことを特徴とする請求項３に記載の遺伝的アルゴリズム実行装置。
【請求項６】
半導体素子の物理モデルの複数のパラメータのそれぞれを遺伝子とする個体を定義し、試作された半導体素子の特性測定データに基づき、遺伝的アルゴリズムを使用してパラメータを最適化するパラメータ調整手段を備えたことを特徴とする請求項１に記載の遺伝的アルゴリズム実行装置。
【請求項７】
複数の親個体の収束状態を示す混雑度を求めるステップと、
前記混雑度から突然変異確率を決定するステップと、
前記複数の親個体から子個体を生成するステップと、
前記突然変異確率に基づき、前記子個体の遺伝子情報に突然変異処理を施すステップと
を含むことを特徴とする遺伝的アルゴリズム実行方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遺伝的アルゴリズム実行装置および遺伝的アルゴリズム実行方法に関するものであり、例えば、トランジスタなどの半導体素子の物理モデルの多数のパラメータを短時間で調整可能なパラメータ調整装置に好適な遺伝的アルゴリズム実行装置および遺伝的アルゴリズム実行方法に関するものである。
【背景技術】
【０００２】
ＬＳＩの製造を行う場合、まず、当該製造ラインでトランジスタ（MOSFET）のゲートのチャネル長Ｌおよびチャネル幅Ｗ等の形状の異なる幾つかのトランジスタ（MOSFET）のサンプルを試作する。次に、この試作品の電気的特性の測定結果から、当該製造ラインにおいて製造されるトランジスタの特性に高精度で合致するように、トランジスタの物理モデルの複数のパラメータを調整する。そして、このトランジスタの物理モデルを使用して、ＳＰＩＣＥなどの周知の回路シミュレータによって当該製造ラインにおいて製造する各種ＬＳＩ（トランジスタ）のシミュレーションが行われていた。
【０００３】
トランジスタの物理モデルは、Ｖｇ（ゲート電圧）、Ｖｄ（ドレイン電圧）、Ｉｄ（ドレイン電流）の関係等をゲートのチャネル長Ｌ、チャネル幅Ｗ等の変数および複数のパラメータを含む数式によって表現したものであり、多数のモデルが提案されている。そして、上記シミュレーションには例えば代表的な周知のＢＳＩＭ（Berkeley Short Channel 1GFET Model）が使用されていた。
【０００４】
ＢＳＩＭは多数の数式からなり、調整すべきパラメータの数は５０個以上ある。なお、トランジスタの物理モデルの詳細および従来のパラメータ調整方法については例えば下記文献に記載されているので、詳細な説明は省略する。
【非特許文献１】鳥谷部達監修「MOSFETのモデリングとBSIM3ユーザーズガイド」平成14年2月28日丸善発行。
【０００５】
また、従来、試作結果などから遺伝的アルゴリズムを用いて複数のパラメータを含む物理モデルのパラメータフィッティング（調整）処理を自動的に行うパラメータ調整装置が提案されている。例えば、本出願人が先に出願した下記の文献には、遺伝的アルゴリズムを用いて複数のパラメータを含む物理モデルのパラメータ調整処理を自動的に行うパラメータ調整装置が提案されている。
【特許文献１】特開２００５−３８２１６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記した特許文献１に示す従来のパラメータ調整方法においては、交叉処理として乱数を使用した特殊な交叉方法を採用していた。この交叉方法は、限定された範囲内ではあるが、遺伝子情報でるパラメータがランダムに変化するような、突然変異と類似した構成を取っており、従って、突然変異の処理は行われていなかった。
【０００７】
しかし、従来の方法では遺伝的アルゴリズムの特徴である広域探索機能が制限され、局所解に捕らわれてしまう恐れがあるという問題点があった。本発明の目的は、上記した従来技術の問題点を解決し、最適解に近づく速度の向上を維持しつつ、広域探索による局所解からの離脱可能性の向上を両立させることにある。
【課題を解決するための手段】
【０００８】
本発明の遺伝的アルゴリズム実行装置は、個体の収束状態を示す混雑度を求める混雑度算出手段と、前記混雑度から突然変異確率を決定する突然変異確率決定手段と、前記突然変異確率に基づき、前記個体の遺伝子情報に突然変異処理を施す突然変異処理手段とを備えたことを主要な特徴とする。
【０００９】
また、前記した遺伝的アルゴリズム実行装置において、前記混雑度算出手段は、遺伝子情報であるパラメータ毎に、個体のパラメータの最大値から最小値を減算したものを当該パラメータの取り得る最大値から最小値を減算した値で除算し、これを全てのパラメータについて平均した平均値を求め、１から前記平均値を減算した値を前記混雑度とする点にも特徴がある。
【００１０】
また、前記した遺伝的アルゴリズム実行装置において、更に、母集団から所定個数だけ親個体を選択して前記複数の親個体とする親個体選択手段と、前記複数の親個体から複数の子個体を生成する子個体生成手段と、前記子個体生成手段が生成した複数の子個体について評価値を算出する評価値算出手段と、前記複数の子個体の中から評価値の良い所定個数の個体を選択する子個体選択手段と、親個体の母集団からランダムに所定個数だけ親個体を取り出す親個体取り出し手段と、前記子個体選択手段によって選択された子個体および前記親個体取り出し手段によって取り出された親個体の中から評価値の良い所定個数の個体を選択して、前記母集団に加える上位個体選択手段とを備えた点にも特徴がある。
【００１１】
また、前記した遺伝的アルゴリズム実行装置において、前記子個体生成手段は、親個体の遺伝子情報によって表されるベクトル空間における重心を求め、前記重心および親遺伝子情報の値から定められるベクトル空間上の超多面体の内部に子個体群の生成範囲を決定する生成範囲決定手段を備えた点にも特徴がある。
【００１２】
また、前記した遺伝的アルゴリズム実行装置において、前記親個体選択手段は、評価値のよい個体ほど選択される確率が大きくなるように所定個数の個体を選択する重み付け選択手段と、母集団の個体をランダムに２次元配列し、前記重み付け選択手段によって選択された個体およびこの個体と隣接する個体を所定個数選択する２次元選択手段とを備えた点にも特徴がある。
【００１３】
また、前記した遺伝的アルゴリズム実行装置において、半導体素子の物理モデルの複数のパラメータのそれぞれを遺伝子とする個体を定義し、試作された半導体素子の特性測定データに基づき、遺伝的アルゴリズムを使用してパラメータを最適化するパラメータ調整手段を備えた点にも特徴がある。
【００１４】
本発明の遺伝的アルゴリズム実行方法は、複数の親個体の収束状態を示す混雑度を求めるステップと、前記混雑度から突然変異確率を決定するステップと、前記複数の親個体から子個体を生成するステップと、前記突然変異確率に基づき、前記子個体の遺伝子情報に突然変異処理を施すステップとを含むことを主要な特徴とする。
【発明の効果】
【００１５】
本発明の遺伝的アルゴリズム実行装置においては、母集団において局所解の固体が支配的になった場合には混雑度が増加する。すると突然変異確率が増加し、広域探索機能がより強化さる。このような突然変異確率を動的に制御する特殊な突然変異処理によって、最適解に近づく速度の向上という効果を維持しつつ、局所解に捕らわれずに最適解に到達する確率が向上するという効果を両立させることができる。
【発明を実施するための最良の形態】
【００１６】
以下の実施例においては、本発明をパラメータ調整装置に適用する例を開示するが、本発明は任意の遺伝的アルゴリズム実行装置および実行方法に適用可能である。以下実施例１について説明する。
【実施例１】
【００１７】
図２は、本発明を実施するためのコンピュータシステムのハードウェア構成例を示すブロック図である。周知のコンピュータ１０には入力装置として例えばキーボード１１、マウス１２が、出力装置として周知のディスプレイ装置１５が接続されている。また、データの入力あるいは出力のために、外部記憶装置１３やＬＡＮ１６が接続されている。本発明の遺伝的アルゴリズム実行装置は、後述するフローチャートによって示された処理を実行するプログラムを作成し、このプログラムをコンピュータシステムにインストールすることによって実現する。
【００１８】
図１は、本発明を適用したパラメータ調整装置を使用してシミュレーションを行う場合の全体の手順を示すフローチャートである。前記したように、ＬＳＩの製造を行う場合、まずＳ１０においては、当該ＬＳＩ製造ラインでゲートのチャネル長Ｌおよびチャネル幅Ｗ等の形状の異なる幾つかのトランジスタ（MOSFET）のサンプルを試作する。
【００１９】
図１０は、試作するトランジスタの形状の選択方法を示す説明図である。形状の選択方法は、例えば長さＬおよび幅Ｗの最大値および最小値の間を等間隔で、あるいは最小値に近い方をより細かく区分し、Ｌ−Ｗ平面上で十字形状になるように試作するトランジスタの区分（形状）を選択する。
【００２０】
Ｓ１１においては、試作したトランジスタの電気的特性を測定する。具体的にはＩｄＶｄ特性（Ｖｂ固定）、ＩｄＶｄ特性（Ｖｇ固定）、ＩｄＶｇ特性（Ｖｄ固定）についてそれぞれ複数個のサンプル値（離散データ）を得る測定を固定値を変えて複数回行う。
【００２１】
Ｓ１２においては、当該製造ラインにおいて製造されるトランジスタの特性に高精度で合致するように、本発明を適用したパラメータ調整装置を使用して後述する方法によってトランジスタの物理モデルのパラメータ調整処理を行う。
【００２２】
Ｓ１３においては、パラメータが調整された物理モデルを使用して、ＳＰＩＣＥなどの周知の回路シミュレーションプログラムを使用して、当該製造ラインにおいて製造する任意のチャネル長およびチャネル幅のトランジスタ回路の動作シミュレーションを行う。本発明を適用したパラメータ調整装置を使用することにより、物理モデルの精度の高いパラメータが短時間で得られ、精度の高いシミュレーションを行うことができる。
【００２３】
図３は、本発明の交叉、突然変異処理の概略を示す説明図である。この処理はＳ１２の遺伝的アルゴリズムを用いたパラメータ調整処理の中で行われる。図３においては、遺伝的アルゴリズムにおける個体（母集団）の１世代の世代交代処理の内容を示している。実際の処理においては、例えば評価値の良い個体が見つかるまでこの世代交代処理を繰り返す。
【００２４】
まず、遺伝子として調整すべき複数のパラメータ値を有する個体が所定個数含まれる母集団２０から所定個数の個体を選択（コピー）して親個体の集合２１とする。選択方法としてはランダムに選択する方法（実施例１）の他、評価値に基づく選択とランダムな選択とを組み合わせた方法（実施例２）も開示する。
【００２５】
次に、親個体集合２１から突然変異確率を算出する。詳細は後述するが、まず親個体集合２１から混雑度Ｓを算出し、混雑度Ｓから突然変異確率Ｍを算出する。交叉、突然変異処理２３においては、後述する特殊な交叉処理を実行すると共に、この突然変異確率Ｍに基づいて突然変異処理も実行し、子個体の集合２４を生成する。
【００２６】
評価値算出、上位選択処理２５においては、子個体の集合２４のそれぞれの個体について、評価値を計算し、評価値が上位の所定個の個体２６を選択する。これとは別に母集団２０から所定個数の固体２７をランダムに取り出す（母集団には残さない）。上位選択処理２８においては、個体２６および個体２７を加算した集合から評価値が上位の所定個の個体２９を選択し、母集団に加える。以上で１世代の世代交代が完了する。固体２７の数と固体２９の数を同数にすれば母集団の固体数は変わらない。
【００２７】
以下、Ｓ１２の遺伝的アルゴリズムを使用したパラメータ調整処理の内容について説明する。図４は、遺伝的アルゴリズムを使用したパラメータ調整（フィッティング）処理を示す概略フローチャートである。Ｓ２０においては、試作トランジスタから得た一つ以上の離散データ群（測定結果）を用意する。Ｓ２１においては、トランジスタの物理モデル関数の調整すべき任意のパラメータを遺伝子情報とする個体をＮ個生成し、個体母集団とする。
【００２８】
ＢＳＩＭには前記したように５０個以上のパラメータがあるが、シミュレーションしたい内容によっては、調整を行わずに代表値に固定しておけばよいか、あるいは無視してよいパラメータもある。従って、調整すべきパラメータの数ｎはシミュレーションする目的によって異なり、５０個以上の場合もあるが、例えば１０個の場合もある。そこで、調整すべきパラメータの数ｐｎに依存して遺伝的アルゴリズムにおける個体数Ｎや子の生成数（ｂ）などのパラメータを変化させるようにする。このことによって、ｐｎが小さければ処理も速くなる。実施例においては、例えば個体数Ｎ＝ｐｎ×１５とする。
【００２９】
また、ＢＳＩＭにおいては、各パラメータについて推奨するパラメータ初期値の範囲が定められているので、各パラメータについて、推奨するパラメータ初期値の範囲内においてランダムに初期値を決定して遺伝子の値とする。
【００３０】
Ｓ２１においては、各個体の評価値も計算する。評価値とは、個体中の遺伝子がモデルパラメータとしてどれだけ理想的な値に近いかを示す値である。評価値は、用意した離散データ群と個体中の遺伝子をモデルパラメータとするトランジスタ電気特性モデル関数で計算した推定データ群より計算する。評価関数としては、二乗誤差や誤差率などが用いられる。
【００３１】
なお、離散データ群間でスケーリングが異なる場合、二乗誤差を取るとスケールの小さいデータ群は評価値に与える影響が小さくなってしまう。そこで、本発明では各データ群中の離散データを正規化し、スケールを統一することによって調整精度を向上させる。
【００３２】
Ｓ２２においてはＳ２１で生成された個体母集団からａ個の親個体を選ぶ。ａは例えば調整するパラメータ数がｐｎ個の場合、ａ＝ｐｎ＋１であってもよい。Ｓ２３においては、選択された親個体から後述する交叉、突然変異処理によりｂ個の子個体を生成する。Ｓ２４においてはＳ２３で生成された子個体全ての評価値を計算する。
【００３３】
Ｓ２５においてはＳ２３で生成した子個体の中から評価の良い順にｃ個（例えば２個）を選択する。Ｓ２６においては母集団からランダムにｃ個の個体を取り出す。Ｓ２７においては、Ｓ２５およびＳ２６において選択あるいは取り出された個体２ｃ個の中から評価の良い順にｃ個を選択し、母集団に加える。以上処理によって個体の世代が１つ更新される。
【００３４】
Ｓ２８においては、世代更新処理を終了するか否かが判定され、判定結果が否定の場合にはＳ２２に移行するが、肯定の場合には処理を終了する。終了の条件は評価値が予め定められた所定値以上に達したか、評価値の増加率が所定値を下まわったか、あるいは世代交代回数が所定数に達したかなどである。
【００３５】
図５は、Ｓ２３の交叉、突然変異処理の内容を示すフローチャートである。ここで用いる交叉法は複数の親個体の遺伝子から計算された多面体の中から子個体の遺伝子を生成する実数値向け交叉法である。Ｓ３０においては、ａ個の親個体の重心Ｇを求める。即ち、個体の各パラメータ毎に平均値を求める。Ｓ３１においては、混雑度Ｓを計算し、この混雑度Ｓに基づいて突然変異確率Ｍを計算する。
【００３６】
図８は混雑度Ｓの内容を示す説明図である。図８においては、図示し易くするためにパラメータの数を２、親個体の数を３個、パラメータの取り得る最小値を０としてある。例えばパラメータＰｉの取り得る最大値から最小値を減算した値をＲｉとし、選択された親個体の当該パラメータの最大値から最小値を減算した値をＱｉとする。
【００３７】
探索の初期段階など、パラメータＰｉが特定の値に収束しておらず、広く分布している場合にはＱｉが大きく、Ｒｉに近い値であるが、パラメータＰｉが特定の値の近傍に収束した場合にはＱｉが小さくなり、０に近づく。
【００３８】
そこで、混雑度Ｓを下記の数式１のように定義する。即ち、パラメータ毎に、親個体のパラメータの最大値から最小値を減算した値Ｑｉを当該パラメータの取り得る最大値から最小値を減算した値Ｒｉで除算し、これを全てのパラメータについて平均した値を１から減算した値を混雑度Ｓとする。ｎはパラメータの数である。混雑度Ｓは０から１の間の値をとる。
【００３９】
【数１】
2008242927.tif 000003
【００４０】
更に、下記の数式２によって混雑度Ｓから突然変異確率Ｍを求める。図９は、混雑度Ｓから突然変異確率Ｍを求める１次関数を示す説明図である。定数ｅおよびｆは、突然変異確率Ｍが０から１の範囲に入り、かつ探索速度と探索範囲のバランスがとれるように、実験により決定されるが、例えばｅは０．３〜０．５程度、ｆは０〜０．１程度であってもよい。
【００４１】
【数２】
2008242927.tif 000004
【００４２】
Ｓ３２においては変数ｉの値を１にセットし、Ｓ３３においては重心Ｇ及び一様分布乱数を用いた下記の数式３より子個体Ｃを一つ生成する交叉処理を行う。ここで、ｐは選択された親個体の数、Ｃは生成される子個体の個体を示すベクトル、Ｐkは選択された親個体の個体を示すベクトルである。なお、本実施例では選択された親個体の数ａはｐｎ＋１個であるとする。また、ｕ（０，１）は区間［０，１］の一様分布乱数である。
【００４３】
【数３】
2008242927.tif 000005
【００４４】
数式３においては、まず、各親個体のベクトルＰkからそれぞれｘkを求め、次にＣkを順にＣaまで求め、最後にｘaとＣaを加算して子個体Ｃを求める。
【００４５】
図７は、調整するパラメータをα、βの２個、個体集団よりランダムに選ばれた親個体の数を３個とした時の交叉処理における探索範囲（子個体の生成範囲）を示す説明図である。重心Ｇから各親個体Ｐ１〜Ｐ３までのベクトルをε倍して子個体の生成範囲（図７の外側の三角形の内部）を決定し、その範囲から一様乱数を用いて子個体を生成する。εの推奨値は親個体の数がｐ個の時、√(p+1)である。なお、パラメータ数が３以上の場合には子個体の生成範囲は複数の超平面によって囲まれた超多面体の内部空間となる。
【００４６】
上記の様な交叉方法を用いることで、調整対象となるパラメータが実数値である問題に対してパラメータを陽に扱うことができ、有効な調整を行う事ができる。また、このような交叉手法は変数間の依存性に頑健で、スケールのとり方に依存しないという特徴があり、パラメータ間に依存性が強く、スケーリングが異なるパラメータが多数存在するトランジスタの電気特性モデル関数のパラメータ調整に適している。
【００４７】
Ｓ３４においては突然変異処理を行う。図６は、Ｓ３４の突然変異処理の内容を示すフローチャートである。Ｓ４０においては、変数ｉを１にセットする。Ｓ４１においては、一様分布乱数Ｒを生成する。Ｓ４２においては、乱数Ｒが突然変異確率Ｍより大きいか否かが判定され、判定結果が否定の場合にはＳ４３に移行するが、肯定の場合にはＳ４４に移行する。
【００４８】
Ｓ４３においては、更に一様乱数を生成して個体のｉ番目のパラメータを突然変異させる。即ち、一様乱数を用いて当該パラメータの取り得る範囲内において一様に分布する可能性のある新たなパラメータ値を生成し、個体のｉ番目のパラメータを上書きする。
【００４９】
Ｓ４４においては変数ｉに１を加算し、Ｓ４５においては変数ｉが定数ｐｎより大きいか否かが判定され、判定結果が否定の場合にはＳ４１に戻るが、肯定の場合には処理を終了する。
【００５０】
Ｓ３５においては変数ｉに１を加算し、Ｓ３６においては変数ｉが定数ｂより大きいか否かが判定され、判定結果が否定の場合にはＳ３３に戻るが、肯定の場合には交叉処理を終了する。この処理によってｂ個の子個体が生成される。ｂは１０×ｐｎ程度が望ましい。
【００５１】
以上のようなパラメータ調整処理によって、短時間で高精度のパラメータ調整ができる。そして、物理モデルに当該パラメータを採用することにより、試作をせずに高精度の回路シミュレーションを行うことができるので、半導体素子の製造効率が向上する。
【実施例２】
【００５２】
実施例１においては、母集団からランダムにａ個の個体を選択して親個体とする例を開示したが、これだと進化の速度が遅いという問題点がある。また、評価値の高い個体をより高い確率で選択することが考えられるが、この場合には局所解の個体が支配的となり、広域探索機能が低下するという問題点がある。そこで、実施例２においては、上記問題点を解決するために、評価値に基づく選択と２次元配置を用いたランダムな選択を組み合わせて親個体を選択する。
【００５３】
実施例１と実施例２との差異は、実施例１の図４のＳ２２のランダム選択処理が、実施例２においては、図１１の処理に変更されている点であり、その他の処理は同一である。従って、以下に相違点についてのみ説明する。
図１１は、実施例２における親個体選択処理の内容を示すフローチャートである。Ｓ５０においては、母集団の各個体について、評価値から選択確率を算出し、更に当選範囲を決定する。
【００５４】
図１２は、Ｓ５０の処理例を示す説明図である。図１２においては、図示するような評価値を持つ４つの個体が示されている。そこで、まず全個体の評価値の合計（図１２においては１０＋１５＋５＋２０＝５０）で各個体の評価値を除算し選択確率を算出する。例えば個体Ａの選択確率は１０／５０＝０．２となる。
【００５５】
次に、各個体について、当該個体より前の個体の選択確率を合算した値を下限、この下限に当該個体の選択確率を加算した値を上限とする当選範囲を算出する。この当選範囲は、０から１の間を各個体の評価値に比例した長さで重複無く区切ったものとなる。
【００５６】
Ｓ５１においては、変数ｉを１にセットする。Ｓ５２においては、区間（０，１）において一様分布する乱数を生成する。Ｓ５３においては、乱数値が当選範囲内に含まれる個体を当選個体とする。例えば図１２において、乱数値が０．４であれば個体Ｂの当選範囲０．２〜０．５の内にあるので、個体Ｂを当選個体とする。
【００５７】
Ｓ５４においては、すでに当選した個体と重複しているか否かが判定され、判定結果が否定の場合にはＳ５５に移行するが、肯定の場合にはＳ５２に戻る。Ｓ５５においては、当選個体としてリストに記憶する。Ｓ５６においては、変数ｉに１を加算し、Ｓ５７においては、変数ｉが所定の定数ｈより大きいか否かが判定され、判定結果が否定の場合にはＳ５２に移行するが、肯定の場合にはＳ５８に移行する。ｈは例えば最終的に選択される親個体数ａの１／ｎ（ｎは２以上の整数）である。
【００５８】
Ｓ５８においては、母集団の全ての個体をランダムに２次元に配置する。Ｓ５９においては、変数ｉを１にセットし、Ｓ６０においては、ｉ番目の当選個体を含む所定の大きさの長方形の内部に存在する個体を親個体として選択する。
【００５９】
図１３は、Ｓ６０の処理の内容を示す説明図である。個体は２次元の大きな長方形を埋めるようにランダムに（図１３では横１０個×縦６個）に配置されており、当選個体５０を含む所定の大きさの長方形５２（図１３では当選個体が左上に位置し、２×２＝４個の個体が入る正方形）に含まれる個体全て５０、５１を親個体として選択する。なお、当選個体５０が縁にあり、長方形５２が２次元配置から突出する場合には、図１３に示すように、長方形を２次元配置の反対側の辺に折り返して個体を選択する。
【００６０】
Ｓ６１においては、ｉに１を加算し、Ｓ６２においては、変数ｉが所定の定数ｈより大きいか否かが判定され、判定結果が否定の場合にはＳ６０に移行するが、肯定の場合にはＳ６３に移行する。長方形５２の縦および横の長さは個体間隔の整数倍であれば任意であり、最終的に選択される親個体数は前記した定数ｈ×（長方形内の個体数）となる。従って、親個体数が所望の数に近くなるように、定数ｈおよび長方形５２の縦、横の長さを決定する。Ｓ６３においては、重複している個体を排除する。
【００６１】
以上のような処理によって、評価値の高い個体が選択される確率を高くすると共に、評価値の低い個体も一定の確率で選択することができ、最適解に近づく速度の向上と広域探索による局所解からの離脱可能性の向上を両立させることができる。
【００６２】
以上実施例を説明したが、本発明の遺伝的アルゴリズム実行装置には以下のような変形例も考えられる。混雑度は複数のパラメータの混雑度の平均を求めて使用する例を開示したが、混雑度を各パラメータ毎に求め、この混雑度に基づき、パラメータ毎に異なる突然変異確率を求めて、パラメータ毎に突然変異処理を行ってもよい。
【００６３】
実施例においては、突然変異に関するパラメータｅ、ｆは定数とする例を開示したが、これらのパラメータを探索の初期段階、中盤、最終段階に応じて動的に変化させてもよい。例えば初期段階においては、広域探索機能を強化するためにパラメータｅ、ｆの値を大きめにし、中盤以降は探索速度を早くするためにパラメータｅ、ｆの値を小さくしてもよい。
【００６４】
探索の終盤においては、遺伝的アルゴリズムから例えば公知のＰｏｗｅｌｌ法あるいはその他の公知の局所的探索法に切り替えてもよい。終盤において探索方法を切り替えることにより、パラメータ調整時間がより短縮する。
【産業上の利用可能性】
【００６５】
本発明は、トランジスタの物理モデルを使用した、ＬＳＩ製造ラインにおいて製造する各種ＬＳＩのシミュレーションを行うパラメータ調整装置をはじめ、遺伝的アルゴリズムを使用する任意の装置に適用できる。
【図面の簡単な説明】
【００６６】
【図１】本発明を適用したパラメータ調整装置を使用してシミュレーションを行う場合の全体の手順を示すフローチャートである。
【図２】本発明を実施するためのコンピュータシステムのハードウェア構成例を示すブロック図である。
【図３】本発明の交叉、突然変異処理の概略を示す説明図である。
【図４】遺伝的アルゴリズムを使用したパラメータ調整（フィッティング）処理を示す概略フローチャートである。
【図５】Ｓ２３の交叉、突然変異処理の内容を示すフローチャートである。
【図６】Ｓ３４の突然変異処理の内容を示すフローチャートである。
【図７】交叉処理における子個体の生成範囲を示す説明図である。
【図８】混雑度Ｓの内容を示す説明図である。
【図９】混雑度Ｓから突然変異確率Ｍを求める１次関数を示す説明図である。
【図１０】試作するトランジスタの形状の選択方法を示す説明図である。
【図１１】実施例２における親個体選択処理の内容を示すフローチャートである。
【図１２】Ｓ５０の処理例を示す説明図である。
【図１３】Ｓ６０の処理の内容を示す説明図である。
【符号の説明】
【００６７】
２０…母集団
２１…親個体
２２…変位確率算出処理
２３…交叉、突然変異処理
２４…子個体
２５…評価値算出、上位選択処理
２６…上位子個体
２８…上位選択処理
２９…上位個体
【図１】
2008242927.tif 000006
【図２】
2008242927.tif 000007
【図３】
2008242927.tif 000008
【図４】
2008242927.tif 000009
【図５】
2008242927.tif 000010
【図６】
2008242927.tif 000011
【図７】
2008242927.tif 000012
【図８】
2008242927.tif 000013
【図９】
2008242927.tif 000014
【図１０】
2008242927.tif 000015
【図１１】
2008242927.tif 000016
【図１２】
2008242927.tif 000017
【図１３】
2008242927.tif 000018