JPH09128362A - 最適配置方法及びその装置 - Google Patents

Abstract

(57)【要約】 【課題】 集積回路、プリント板、資源等の最適配置を
求めるニューラルネットワークによる最適配置方法に関
し、より短い時間で、より良い近似解を得られるニュー
ラルネットワーク及び方法を提案することを目的とす
る。 【解決手段】 各ニューロンが個々に独立にその入力か
ら出力を出すのではなく、互いに相互作用を及ぼしなが
らネットワークの出力を決定する。選択されたニューロ
ン（黒います目）の出力は、このニューロンと同じ行、
列の他のニューロンに作用し、同一の行、列に重複して
ニューロンが選択されることはない。これによって常に
必要条件を満足することを保証できる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、工場や集積回路、
プリント板、資源等における配置問題を、簡単かつ高速
に解決する最適配置方法及びその装置に関する。

【０００２】

【従来の技術、及び発明が解決しようとする課題】従来
の技術として、“Recent models and techniques for
solving thelayout problem”Sunderesh S.Heragu (Eur
opean Journal of OperationalResearch 57(1992)136-1
44 North-Holland) 、及び“Suboptimal solution forP
LA multiple column folding ”F Luccio and M C Pino
tti（Computer-AidedDesign, colume22 number 8 octob
er 1990 p515-520)等が挙げられる。

【０００３】一般に、最適配置方法には、従来より様々
な方法が提案されている。その中で比較的容易に最適配
置或いは最適配置に近い配置が得られる方法として、シ
ミュレーティッドアニーリングと呼ばれる方法が、広く
用いられている。

【０００４】このシミュレーティッドアニーリング法
は、物体の冷却過程をモデルとしている。詳しく説明す
ると、この方法は「温度パラメータ」と呼ばれる繰り返
し計算回数に相当するパラメータを用いて、温度が高い
ときには配置を大きく変化させ、温度が低くなるにした
がって配置の変化を小さくしていき、目的値を得る手法
である。

【０００５】上記のシミュレーティッドアニーリング法
では、温度の初期値、冷却過程での配置変更スケジュー
リング、評価関数のしきい値等、多くのパラメータを設
定しなければならず、また、最適配置により近い配置を
得る為には、その分温度を十分緩やかに冷却しなければ
ならない為、非常に時間がかかるという問題点があっ
た。

【０００６】また、最適配置方法には、進化的プログラ
ミング或いは遺伝的アルゴリズムと呼ばれる手法や、ニ
ューラルネットワークと呼ばれる方法も提案されてい
る。進化的プログラミング或いは遺伝的アルゴリズム
は、生物の進化モデルを基にしており、遺伝子に相当す
る“ユニット”を交換させながら、目的値により近い、
あるいは目的とする値の最小値あるいは最大値により近
い値を得ることができる遺伝子を優性保存し、繰り返し
計算を行う方法である。この場合、各ユニットは、被配
置物と配置場所の関係を示すことになる。

【０００７】このような進化的プログラミング或いは遺
伝的アルゴリズムでもシミュレーティッドアニーリング
法と同様に、遺伝子の数、ユニットの交換スケジューリ
ング、評価関数のしきい値等の多くのパラメータを設定
しなければならない。

【０００８】更に、最適配置により近い配置を得る為に
は、その分多くの遺伝子を用いなければならず、非常に
時間がかかり、また大量の記憶領域が必要となるという
問題点があった。

【０００９】上記いずれの方法においても、非常に時間
がかかるということは（問題にもよるが）天文学的な数
値を意味することであることは良く知られていることで
ある。

【００１０】一方、ホップフィールド型と呼ばれるモデ
ルのニューラルネットワークによる方法が知られてい
る。これは、生物の神経網をモデルにしており、ニュー
ロンを呼ばれるプロセスユニットを用い、ニューロンの
入出力状態を変化させることにより、目的値を得る、ま
たは目的とする値を最小あるいは最大とする方法であ
る。この方法では、ニューロンの入出力が、被配置物と
配置場所の関係を示すことになる。入出力の変化量は、
ニューロンの伝達信号の遅延、必要十分条件、及び目的
値または目的とする値から決定される。

【００１１】ここで図１５は、従来のホップフィールド
型ニューラルネットワークの概念図である。同図におい
て、各プロセスユニット３０は、その出力Ｖi が他の全
てのプロセスユニットの入力Ｕi となるように構成され
ている。そして、各プロセスユニットの入出力の関係を
決定するものとして、例えば同図に示すようなシグモイ
ド関数が用いられていた。

【００１２】そして、入力値の変化量ｄＵi ／ｄＴは、
必要十分条件とコスト関数を計算することにより求めて
いた。ここで必要十分条件の計算は、必要条件を満たし
ているか否かに関するペナルティ項を導入する計算であ
り、多くの時間が費やされるものである。

【００１３】ここで、上記ペナルティ項、必要条件につ
いて説明しておく。ペナルティ項（ペナルティ関数）
は、目的関数の最小化と同時に必要条件（制約条件とも
いう）を満足するという２つの異なる目標を達成する尺
度として導入されるものであり、必要条件の不満足度に
相応した正の値をとることから、必要条件をやぶったと
きに課せられるペナルティと考えることができるもので
ある。

【００１４】そして、上記２つの目標を満足させること
により、求める最適解のより良い近似解が得られるこ
と、すなわち最適配置により近い配置が得られることが
期待できることが知られている。

【００１５】このようなホップフィールド型ニューラル
ネットワークでは、パラメータの数が少なく、計算の並
列処理化が可能な為、上記シミュレーティッドアニーリ
ング法等と比べると、比較的短時間で最適配置、あるい
は最適配置に近い配置が得られものである。

【００１６】しかしながら、各プロセスユニットが互い
に独立にその入力から出力を決定していたため、常に問
題の必要条件が満たされることを保証することができな
かった。また、このため上記ペナルティ項を導入する計
算を行わなければならなかったので、ニューロンの入力
値の変化量を決定する運動方程式が非常に複雑なものと
なり、計算のために多くの時間が費されていた。

【００１７】本発明の課題は、少ないパラメータを用
い、短時間で最適配置を得ることができる最適配置方法
及びその装置を提供することである。

【００１８】

【課題を解決するための手段】図１は、本発明の原理ブ
ロック図である。同図において、非重複選出手段１は、
Ｎ×Ｎ個のプロセスユニット３よりなるニューラルネッ
トワークにおいて、上記プロセスユニット３のなかから
入力値の大きなものから順に、且つ、各被配置物の配置
場所が重複しないようにＮ個を選び出すものである。

【００１９】入力値更新手段２は、上記選択したプロセ
スユニットの入力値を変化させるものである。入力値の
変化は、前記選択した各プロセスユニットの示す被配置
物の配置により得られた値のみを変数として各プロセス
ユニットの入力値の変化量を計算して行うものである。

【００２０】Ｎ個の被配置物をＮ個の場所に配置し、目
的値を得る、又は目的とする値を最小あるいは最大とす
ることで最適配置を得る最適配置方法において、Ｎ個の
被配置物をＮ個の場所に配置することが必要条件とな
る。

【００２１】本発明によれば、非重複選出手段１によ
り、被配置物と配置場所の関係を示すＮ×Ｎ個のプロセ
スユニット３の中から、入力値の大きなプロセスユニッ
トから順に、且つ各被配置物の配置場所が互いに重複し
ないようにＮ個を選び出すことにより、プロセスユニッ
トを選択する時点で既に上記必要条件を満たすことがで
きる。

【００２２】これによって、必要十分条件としてのペナ
ルティ項の計算を行う必要はなく、入力値更新手段２に
より実際の配置による値Ｒのみを変数として計算（コス
ト関数の計算）することで、入力値の変化量を計算で
き、入力値を更新する。

【００２３】

【発明の実施の形態】以下、本発明の実施例について図
面を参照しながら詳述する。図２は、本発明のニューラ
ルネットワークの概念図である。

【００２４】同図において、プロセスユニット群１０は
Ｎ×Ｎ個のプロセスユニットである。従来のホップフィ
ールド型ネットワークと異なる点は、各プロセスユニッ
トが独立にその入力から出力を出すのではなく、互いに
相互作用を及ぼしながらネットワークの出力を決定する
ことである。

【００２５】上記プロセスユニット群１０は、例えば同
図の左上に示されるように、ある選択されたプロセスユ
ニット（例えば中央の黒いマス目）の出力（＝１）が、
当該プロセスユニットと同じ列と行のプロセスユニット
（上下左右４方向の矢印で示される）の出力を抑制する
ような作用を及ぼすように構成されている。

【００２６】本発明では、上記ニューラルネットワーク
において、以下の式（１）に従ってＮ個のプロセスユニ
ットを選択する。

【００２７】

【数１】

【００２８】ここで、上記（１）式において、Ｕi,j は
ｉ行ｊ列番目のプロセスユニットの入力を示し、Ｖi,j
＝１は被配置物ｉが配置場所ｊに配置されていることを
示す。また、Ｖi,j ＝０は被配置物ｉが配置場所ｊに配
置されていないことを示す。

【００２９】すなわち、入力値の大きなプロセスユニッ
トから順に、且つ選択する各プロセスユニットの列及び
行が互いに重複しないようにしてＮ個のプロセスユニッ
トを選択する。

【００３０】これにより本発明では、以下の式（２）、
（３）に示す必要条件を満足することができる。

【００３１】

【数２】

【００３２】このようにプロセスユニットの選択の段階
で既に必要条件を満足するようにしていることより、ｄ
Ｕi ／ｄｔの計算は、従来の方法のように必要十分条件
についての計算をする必要はなく、コスト関数の計算の
みで算出することができる。

【００３３】ここで上記必要十分条件についての計算と
は、従来の技術で述べたペナルティ項に係わる計算と同
様のものである。また、コスト関数の計算とは本実施例
における後述する実際の配置による値Ｒを意味するもの
と考えても良い。

【００３４】図３は、本発明の最適配置を得る計算方法
を示すフローチャートである。同図において、ｔは繰り
返し回数、ｔ＿ｌｉｍｉｔは計算の打ち切りを決める最
大繰り返し回数である。また、Ｑは目的値である。

【００３５】同図において処理が開始されると、まずｔ
＝０とし、終了条件を設定する。すなわち、ｔ＿ｌｉｍ
ｉｔ及び目的値Ｑを設定する（Ｓ１）。次に、時刻ｔに
おける各プロセスユニット全ての入力値Ｕi,j(t)を乱数
を用いて初期化する（Ｓ２）。

【００３６】以上のように設定値、及び初期状態を決定
すると、続いて最適解を得るための処理を行う。まず上
記（１）式を用いて全てのプロセスユニットの出力Ｖi,
j(t)を計算する。すなわち、上述したように、Ｎ×Ｎ個
の全てのプロセスユニットより、入力値の大きなものか
ら順に且つ互いに重複しないようにしてＮ個のプロセス
ユニットを選択する（Ｓ３）。

【００３７】これにより、上記した必要条件（２）、
（３）式を満足することができる。よって、ｄＵij／ｄ
ｔをコスト関数を計算することにより求めることができ
る。すなわち、以下の（４）式を用いてｄＵij／ｄｔを
計算する（Ｓ４）。ここで、ｄＵij／ｄｔはプロセスユ
ニットの入力値の変化量を表す。

【００３８】

【数３】

【００３９】上記（４）式において、Ｒは実際の配置に
よる値（コスト）である。上記計算の結果、ｄＵij／ｄ
ｔが０以上の値になった場合は、この時の解を保存して
処理を終了する（Ｓ５，Ｓ１０）。そうでなければ、次
の繰り返し回数ｔ＋１における各プロセスユニットの入
力値を、上記算出した変化量によって計算する（Ｓ
６）。つまり、以下の（５）式を用いて計算する。

【００４０】 Ｕi,j(t+1) = Ｕi,j(t) + (Ｑ−Ｒ） ・・・（５） そして、（５）式の計算結果より各プロセスユニットの
入力値を変化させる。続いて、繰り返し回数ｔ＋１にお
けるプロセスユニットの出力Ｖi,j(t+1)を計算する（Ｓ
７）。すなわち、上記のようにして入力値を変化させた
Ｎ×Ｎ個のプロセスユニットにおいて、（１）式を用い
て出力Ｖi,j(t+1)を計算する。

【００４１】最後に、ｔがｔ＿ｌｉｍｉｔ（計算の打ち
切りを決める最大繰り返し回数）になったか否かを判定
し（Ｓ８）、ｔがｔ＿ｌｉｍｉｔになった場合は、解を
保存して計算を終了する。一方、ｔが未だｔ＿ｌｉｍｉ
ｔになっていない場合には、ｔに１を加えて（Ｓ９）、
上記Ｓ５あるいはＳ８のいずれかの条件を満たすまでの
あいだ、上記Ｓ４からＳ９の過程を繰り返す。

【００４２】ところで、ここで、上記フローチャートの
（１）式及び（４）式を用いた計算により、本発明のＮ
×Ｎ個のプロセスユニットの系のエネルギーＥの時間微
分（＝ｄＥ／ｄｔ）が常に０以下であることを証明し
て、各プロセスユニットの入力値を（４）式に従って繰
り返し更新することにより系を常に収束させることが出
来ることを示しておく。

【００４３】命題：

【００４４】

【数４】

【００４５】は以下の（１）（２）の二つの条件下で常
に満足される。

【００４６】

【数５】

【００４７】

【数６】

【００４８】証明：

【００４９】

【数７】

【００５０】ここで、

【００５１】

【数８】

【００５２】とする。今、ａ行ｂ列番目のプロセスユニ
ットの入力のみが時間ｔとｔ＋ｄｔの間に変化したとす
ると、ｄＥ／ｄｔは以下のようになる。

【００５３】

【数９】

【００５４】ここで、上記条件（１）（２）より、次の
二つの場合を考えることが必要十分条件となる。 １）Ｖa,b(t+dt) ＝ Ｖa,b(t) ２）Ｖa,b(t+dt) ＝ ０、Ｖa,b(t) ＝ １ 上記場合１）が満たされた場合、

【００５５】

【数１０】

【００５６】となる。なぜなら、Ｖa,b(t+dt) −Ｖa,b
(t)＝０。上記場合２）が満たされた場合、

【００５７】

【数１１】

【００５８】となる。なぜなら、Ｖa,b(t+dt) −Ｖa,b
(t)＝−１、且つ

【００５９】

【数１２】

【００６０】したがって、

【００６１】

【数１３】

【００６２】となる。証明終わり。以下、本発明の第１
の実施例について図面を参照しながら詳述する。

【００６３】第１の実施例では、５個の資源を５個の場
所に配置する場合の最適配置を考えるものとする。この
問題を解くために、図４に示す５行５列のアレイに配置
したプロセスユニットを用いる。ここで、同図によって
５×５の２５個のプロセスユニットが示されているもの
とする。同図に示すアレイの各行は各被配置物（資源）
に対応し、各列は各配置場所（場所）に対応する。

【００６４】すなわち、同図に示すアレイの１行目は被
配置物１に対応し、２行目は被配置物２に対応するもの
である。他の３、４、５行も同様にして各被配置物に対
応するものである。同じく、アレイの１列目は配置場所
１に対応し、２列目は配置場所２に対応するものであ
る。他の３、４、５列も同様にして各配置場所に対応す
るものである。

【００６５】図５は、図４に示す５×５個の各プロセス
ユニットの入力値を示す図である。同図に示す入力値
は、ここでは初期設定値であるものとする。初期設定値
は、ランダムに（例えば乱数を用いて）設定するもので
あっても良い。

【００６６】同図において、例えば１行２列番目のプロ
セスユニットの入力値、すなわち被配置物１を配置場所
２に配置する場合に対応するプロセスユニットの入力値
は１１である。

【００６７】以上述べた条件のもとで、以下に図３に示
すフローチャートのステップＳ３に対応する第１の実施
例の処理を説明する。ここで、図６（ａ）〜（ｄ）は、
本発明におけるプロセスユニットの出力方法を示す図で
ある。言い換えるならば、図６は、図２に示す互いに相
互作用を及ぼしながらネットワークの出力を決定するプ
ロセスユニット群１において、図５に示す５×５のプロ
セスユニットの入力値の状態を例にして、入力値の大き
なものから順にプロセスユニットを選択する方法ととも
に、選択した５個のプロセスユニットが必要条件を満た
すようにする上記相互作用を示す図であると言える。

【００６８】まず同図（ａ）において、入力値が最大
（９０）である１行１列番目のプロセスユニットが選択
される。つまり、当該プロセスユニットが示す被配置物
１が同じく当該プロセスユニットが示す配置場所１に配
置される。このように選択されることは、当該プロセス
ユニットの出力が１になることを意味する。この出力
は、図の矢印で示されるような当該プロセスユニットと
同じ行、同じ列の各プロセスユニットの出力を抑制する
ように働く。これにより、上記選択された１行１列番目
のプロセスユニットと同じ行、列の各プロセスユニット
は、以後選択されないことになる。

【００６９】したがって、次に、同図（ｂ）において、
上記選択した１行１列番目のプロセスユニット、及び当
該プロセスユニットと同じ行、同じ列のプロセスユニッ
トを除いたプロセスユニットの中から選択が行われるこ
とになる。すなわち、入力値が最大（７１）である２行
２列番目のプロセスユニットが選択される。そして、同
図（ａ）の説明と同様にして、当該プロセスユニットと
同じ行、同じ列の各プロセスユニットは、以後選択され
ないことになる。

【００７０】以下、同図（ｃ）、（ｄ）においても同様
にして、既に選択されたプロセスユニットと、当該プロ
セスユニットと同じ列、同じ行のプロセスユニットを除
いた残りのプロセスユニットのなかから入力値が最大の
ものを順次選択していくことで、５個のプロセスユニッ
ト選択することにより必要条件を満足することを保証で
きる。

【００７１】尚、同図（ｂ）、（ｃ）、（ｄ）において
は、既に選択されたプロセスユニットは黒います目で示
してある。そして、上記図６の選択の結果、図７に示す
ように資源１が場所１に、資源２が場所２に、資源３が
場所３に、資源４が場所４に、資源５が場所５にそれぞ
れ配置される。

【００７２】図７は、５個の場所に配置された５個の資
源を示す説明図である。同図において例えばfacility #
1 in location #1とは、資源１が場所１に配置されるこ
とを示している。

【００７３】続いて、図３に示すフローチャートのステ
ップＳ４に対応する第１の実施例の計算法を説明する。
本実施例においては、５個の被配置物を５個の配置場所
に配置する際、被配置物ｉ及びｊ（ｉ，ｊ；１〜５の整
数）に対して、被配置物ｉと被配置物ｊとの間の負荷Ｃ
i,j と、配置場所ｐ及びｑ（ｐ，ｑ；１〜５の整数）と
の距離Ｄp,q が与えられた時、全ての被配置物ｉ及びｊ
に対して、その負荷と距離の積を最小にする最適配置を
考える。

【００７４】即ち、以下の（６）式で表される実際の配
置による値Ｒ（コスト）を最小にすることを考える。

【００７５】

【数１４】

【００７６】ここで（６）式において、Ｖi,p は、被配
置物ｉが配置場所ｐに配置されているか否かによって、
０あるいは１の値をとるものである。Ｖi,p ＝１は、被
配置物ｉが配置場所ｐに配置されていることを示す。ま
た、Ｖi,p ＝０は、被配置物ｉが配置場所ｐに配置され
ていないことを示す。

【００７７】また、被配置物ｉと被配置物ｊ間の負荷Ｃ
i,j と、配置場所ｐと配置場所ｑの距離Ｄp,q は、与え
られた問題によって既に決定している値であり、本実施
例では図８に示す値が与えられている。すなわち本実施
例では図７に示すような５つの場所に５つの資源を配置
する問題であるので、例えば場所１（location #1)と場
所５のように距離が遠い場合、図８に示すようにｄ1,5
(=ｄ5,1)の値は３となっており、場所１と場所３のよう
に距離が近い場合はｄ1,3 (=ｄ3,1)の値は１となってい
る。

【００７８】したがって、上述したように選択され、図
７に示すように資源１が場所１に、資源２が場所２に、
資源３が場所３に、資源４が場所４に、資源５が場所５
にそれぞれ配置された場合の実際の配置による値Ｒは、
図８に示される値を用いて（６）式を計算すると、以下
のように算出できる。

【００７９】 （Ｃ1,2 ×Ｄ1,2 ）＋（Ｃ1,3 ×Ｄ1,3 ）＋（Ｃ1,4 ×Ｄ1,4 ）＋（Ｃ1,4 × Ｄ1,4 ）＋（Ｃ1,5 ×Ｄ1,5 ）＋（Ｃ2,3 ×Ｄ2,3 ）＋（Ｃ2,4 ×Ｄ2,4 ）＋（ Ｃ2,5 ×Ｄ2,5 ）＋（Ｃ3,4 ×Ｄ3,4 ）＋（Ｃ4,5 ×Ｄ4,5 ） ＝（１×５）＋（１×２）＋（２×４）＋（３×１）＋（２×３）＋（１×０ ）＋（２×２）＋（１×０）＋（２×０）＋（１×５） ＝３３ このようにＲの値は３３となる。

【００８０】ここで、時間ｔから時間ｔ＋１になったと
きの各プロセスユニットの入力値の変化量は（４）式に
より得られる。したがって、上記のようにＲの値３３が
得られ、また本実施例においては目標値Ｑは２０に設定
してあるものとすると、上記５個の各プロセッサユニッ
ト（１行１列番目、２行２列番目、３行３列番目、４行
４列番目、５行５列番目）の入力値の変化量（ｄＵij／
ｄｔ）はＱ−Ｒ、即ち−１３となる。

【００８１】よって、上記５個の各プロセッサユニット
の時間ｔでの入力値（９０、７１、６２、４５、３７）
は、それぞれ時間ｔ＋１においては入力値（７７、５
８、４９、３２、２４）となる。

【００８２】続いて、上記１行１列番目、２行２列番
目、３行３列番目、４行４列番目、５行５列番目の５個
のプロセスユニット以外のプロセスユニットの入力値の
変化量を計算する。

【００８３】このとき、本実施例では、上記選択した５
個のプロセスユニットの一部の配置を入れ換えることに
より、入力値の変化量を計算する。これにより、必要条
件を保証でき、且つ入力値の変化量の計算を簡略化でき
る。

【００８４】たとえば、２行１列番目のプロセスユニッ
トの入力値を決定する際、図９に示すように、当該プロ
セスユニットの示す被配置物２を配置場所１に一時的に
配置する。この時、配置場所１に配置されている被配置
物１を当該被配置物２が配置されていた配置場所２に一
時的に配置する。

【００８５】これにより、Ｒが簡単に計算でき、２８を
得る。したがって、上記のように目的値Ｑは２０なの
で、上記２行１列番目のプロセスユニットの入力値は−
８変化する。

【００８６】その後、被配置物１及び２は元の配置場所
に戻される。これと同様の方法で、残りの全てのプロセ
スユニットの入力値の変化量を求める。但し、１行２列
番目のプロセスユニットは被配置物１及び配置場所２に
対応するプロセスユニットとすると、２行１列番目のプ
ロセスユニットの入力値の変化量は１行２列番目のプロ
セスユニットの入力値の変化量と等しくなる。したがっ
て、どちらかを計算すればよい。

【００８７】そして、入力値の変化量が正の値（ｄＵij
／ｄｔ＞０）である場合は、解を保存し、計算を終了す
る。そうでなければ、全てのプロセスユニットについ
て、（６）式に従って入力を変化させる。

【００８８】以上で、時間ｔにおける一連の過程が終了
する。続いて、上述した時間ｔにおける一連の過程を、
時間ｔ＋１においても同様にして行う。このように、上
記過程を繰り返すうちに（６）式の値を減少させること
ができる。但し、ここでいう減少とは、常時減少するも
のとは限らない。一時的にではあるが増加することもあ
り得る。

【００８９】そして、上記過程を繰り返すうちに、Ｑ−
Ｒ≧０となった場合、その時の解は最適解、あるいは最
適解に近いものであり、解を保存して計算を終了する。
本実施例における被配置物は、工場、倉庫、品物、集積
回路、プラント等でもよい。またその時、本実施例にお
ける被配置物間の負荷や配置場所間の距離は他の評価値
で置き換えられる。さらに、本発明は最適日程計画、最
適工程計画にも用いることができる。

【００９０】次に、本発明の第２の実施例について、図
面を参照して詳述する。第２の実施例は、ＰＬＡ ｆｏ
ｌｄｉｎｇ問題に関して最適配置を得る手法を説明す
る。ここで上記折りたたみＰＬＡとは、行や列を切断し
折りたたむことで更に面積効率を向上するＰＬＡのこと
である。

【００９１】この問題において、本実施例では、Ｎ本の
まっすぐなラインをＮ個の互いに平行なまっすぐな配置
場所に配置する際、当該ラインに対して垂直、且つ、単
数個のライン或いは複数個のライン間を接合する別のま
っすぐなライン「ネット」が複数存在し、当該配置場所
に対して垂直な別のまっすぐな配置場所「トラック」が
複数存在する時、当該ネットが互いに交わらないよう
に、当該トラックに当該ネットを最大２つまで設定で
き、且つ、できる限り少ないトラック数で当該ネットを
当該トラックに設定できるよう、当該ラインを当該配置
場所に配置する最適配置方法を考える。

【００９２】尚、本実施例では、上記第１の実施例のよ
うな関数等による目的とする値ではなく、トラック数で
表される値を最小にすることを考える。図１０は、ＮＭ
ＯＳ ＮＯＲ回路によるＰＬＡ（Programmable Logic A
rray)の構成を示す図である。

【００９３】同図において、ＡＮＤアレイ（ＡＮＤ平
面）は縦の列として７本の入力線Ａ〜Ｇ（ネット）を有
し、ＯＲアレイ（ＯＲ平面）は縦の列としての２本の出
力線Ｈ〜Ｉ（ネット）を有する。また、横方向に６本の
ライン１〜６（product lines)を有する。上記縦の入出
力線と横のラインの交点には、同図に示すようにトラン
ジスタ２０が設けられている。

【００９４】この問題を解くために、本実施例では、図
１１に示す６行６列のアレイに配置した６×６個のプロ
セスユニットを用いる。ここで当該アレイの各行が各ラ
インに対応し、各列が当該各ラインの各配置場所に対応
する。また、同図における黒いプロセスユニットは当該
プロセスユニットに対応するラインが当該プロセスユニ
ットに対応する配置場所に配置されていることを示す。
また、白いプロセスユニットは当該プロセスユニットに
対応するラインが当該プロセスユニットに対応する配置
場所に配置されていないことを示す。

【００９５】第２の実施例においても、第１の実施例に
おける図６の説明による方法と同様に、当該６×６個の
プロセスユニットの中から入力値の大きなものから順
に、且つ、ラインと配置場所が重複しないよう６個を選
び出す。尚、図１１においては特に入力値は図示しては
いないが、上記のようにして６個のプロセスユニットを
選び出した結果、図１２に示すようにライン１が配置場
所１に、ライン２が配置場所３に、ライン３が配置場所
２に、ライン４が配置場所６に、ライン５が配置場所５
に、ライン６が配置場所４にそれぞれ配置されるものと
する。

【００９６】その後、各ネットはレフトエッヂファース
ト法と呼ばれる方法で、各トラックに設置される。当該
レフトエッヂファースト法は、与えられたラインの配置
に対し、最も少ないトラック数でネットを設置する方法
を提供するものである。

【００９７】図１２は、図１１に示すように選択され、
上記レフトエッヂファースト法により設置されたライ
ン、ネットの配置を示す図である。同図において、各黒
点は図１０の各トランジスタ２０を示す。

【００９８】ライン１〜６は、上記した配置場所に配置
されるので、上記レフトエッヂファースト法により、ネ
ットＡ〜Ｇは図１２に示すように配置される。したがっ
て、同図より明らかなように、実際の配置による値とし
てのトラック数は５である。

【００９９】第２の実施例においても、入力値の変化量
を実際の配置による値のみを変数として用いて各プロセ
スユニットの入力値を変更する。例えば、時間ｔにおい
て各ラインが図１２に示されるようになっていたとする
と、上記のようにトラック数は５であるので、実際の配
置による値は５である。

【０１００】ここで、仮に目的値Ｑを２とすると、１行
１列番目、２行３列番目、３行２列番目、４行６列番
目、５行５列番目、６行４列番目の６個のプロセスユニ
ットの入力値は時間ｔ＋１において、Ｑ−Ｒ、即ち一３
変化する。

【０１０１】さらに、上記選択した１行１列番目、２行
３列番目、３行２列番目、４行６列番目、５行５列番
目、６行４列番目の６個のプロセスユニット以外のプロ
セスユニットの入力値の更新量を以下のようにして決定
する。

【０１０２】ここで、図１３、図１４は ５行４列番目
のプロセスユニットの入力値を決定する方法を示す概念
図（その１）、（その２）である。上記選択した６個の
プロセスユニット以外のプロセスユニットの入力値を更
新する方法であって、例えば、図１３及び１４に示すよ
うに５行４列番目のプロセスユニットの入力値を決定す
る際、当該プロセスユニットの示すライン５を同じく当
該プロセスユニットの示す配置場所４に一時的に配置す
る。

【０１０３】ここで、６行５列番目のプロセスユニット
はライン６及び配置場所５に対応するプロセスユニット
である。この時、配置場所４に配置されているライン６
を当該ライン５が配置されていた配置場所５に一時的に
配置する。これにより、Ｒが簡単に計算でき、６を得
る。

【０１０４】したがって、上記目的値Ｑは２なので、上
記プロセスユニットの入力値は−４変化する。その後、
ライン５及び６は元の配置場所に戻される。これと同様
の方法で、残りのプロセスユニットの入力値を変化させ
る。

【０１０５】６行５列番目のプロセスユニットの入力値
の変化は５行４列番目のプロセスユニットの入力値の変
化を等しくなる。したがって、どちらかを計算すればよ
い。続いて、時間ｔ＋１において、上記のようにして入
力値を変化させた６×６個のプロセスユニットの中か
ら、入力値の大きなものから順に、且つ、ラインと配置
場所が重複しないよう６個を選び出し、上記時間ｔにお
ける過程と同様な過程を実行する。このような過程を繰
り返すうちにトラック数を減少させることができる。

【０１０６】但し、ここで言う減少とは、常に減少して
いくものとは限らない。一時的にではあるが増加するこ
ともあり得る。そして、上記過程を繰り返すうちに、上
記入力値の更新量が０以上となった場合に、その時の解
を保存して、計算を終了する。

【０１０７】尚、本発明において、目的値Ｑの値は、今
まで得られているＱ値よりも、例えばより良いＱ値を設
定する。例えば、ＴＳＰ（Traveling Salesman Proble
m) では、今まで総距離として１５００ｍ必要とするた
めの最適巡回経路が見つかっているとすれば、Ｑ値を仮
に１４００ｍとして本発明を適用して計算すれば良い。

【０１０８】本実施例におけるラインは、プリント板上
の配線、集積回路の配線、プラントの配線等でもよい。
さらに、本発明は最適日程計画、最適工程計画にも用い
ることができる。

【０１０９】

【発明の効果】以上述べたように、Ｎ個の被配置物をＮ
個の場所に配置し、目的値を得るまたは目的とする値を
最小或いは最大とする最適配置方法において、Ｎ個の被
配置物をＮ個の場所に配置することが必要条件である
が、従来のホップフィールドモデル等のニューラルネッ
トワークによる方法では、常に当該必要条件が満たされ
ることを保証できなかった。

【０１１０】しかし、本発明によれば当該必要条件が満
たされることを保証することができる。これにより、従
来のホップフィールドモデル等のニューラルネットワー
クによる方法と比較し、短時間で、且つ、最適配置或い
は最適配置に近い配置を得ることができる。

【０１１１】一方、従来のシミュレーティッドアニーリ
ング又は進化的プログラミング或は遺伝的アルゴリズム
による方法では、比較的容易に常に当該必要条件が満さ
れることを保証することができるが、その場合直接配置
を変化させることになる。

【０１１２】しかし、本発明によれば、各プロセスユニ
ットの入力値を変化させ配置を変化させているので、直
接配置を変化させる方法と比較し、最適配置以外の或い
は最適配置から遠い配置に収束することを防止すること
もできる。

【０１１３】更に、シミュレーティッドアニーリング又
は進化的プログラミング或いは遺的アルゴリズムによる
方法では、結局多くのパラメーターが必要となる。ま
た、ニューラルネットワークでは上記必要条件が常に満
たされることを保証できないために、プロセスユニット
に相当するニューロンの入力値の変化量を決める際、実
際の配置による値を一義的に決定できない。

【０１１４】本発明では、プロセスユニットの入力値の
変化を、実際の配置による値のみ変数として用いて上記
入力値を変更することにより、変化量の計算を簡略化で
き、数学的にも最適配置の或いは最適配置から近い配置
に収束することを保証できる。

【０１１５】したがって、従来の方法に比較し、短時間
で、且つ、最適配置或いは最適配置に近い配置を得るこ
とができる。また、更に、本発明ではプロセスユニット
の入力値の変化量を計算する方法を一義的に決めること
ができる。さらに、この方法を用いることにより、被配
物ｉ及びｊの実際の配置場所をそれぞれP(i)及びP(j)と
すると、

【０１１６】

【数１５】

【０１１７】となり、計算量が約半分になり、計算スピ
ードをおよそ倍にすることができる。尚、本発明の効果
は、実際のシミュレーション等により確かめられてい
る。上記シミュレーションでは、本発明の方法により得
られた解が、従来の方法より良い解を得ることができる
ことが確かめられている。

【図面の簡単な説明】

【図１】本発明の原理ブロック図である。

【図２】本発明のニューラルネットワークの概念図であ
る。

【図３】本発明の最適配置を得るための計算方法を示す
フローチャートである。

【図４】５行５列のアレイの概念図である。

【図５】５×５個のプロセスユニットの入力値を示す説
明図である。

【図６】（ａ）、（ｂ）、（ｃ）、（ｄ）は本発明にお
けるプロセスユニットの出力方法を示す図である。

【図７】５個の場所に配置された５個の資源を示す説明
図である。

【図８】資源間の負荷と距離を示す説明図である。

【図９】２行１列番目のプロセスユニットの入力値を決
定する方法を示す概念図である。

【図１０】ＮＭＯＳ ＮＯＲ回路によるＰＬＡの構成を
示す図である。

【図１１】図１０に対応して６行６列のアレイに配置さ
れた６×６個のプロセスユニットの概念図である。

【図１２】図１１に示すように選択され、上記レフトエ
ッヂファースト法により設置されたライン、ネットの配
置を示す図である。

【図１３】５行４列番目のプロセスユニットの入力値を
決定する方法を示す概念図（その１）である。

【図１４】５行４列番目のプロセスユニットの入力値を
決定する方法を示す概念図（その２）である。

【図１５】従来のホップフィールド型ニューラルネット
ワークの概念図である。

【符号の説明】

１０ プロセスユニット群 ２０ トランジスタ ３０ プロセスユニット

Claims (9)

【特許請求の範囲】
1. 【請求項１】 Ｎ個の被配置物についてのＮ個の配置場
   所を示すＮ×Ｎ個のプロセスユニットよりなるニューラ
   ルネットワークにおいて、 上記プロセスユニットのなかから入力値の大きなものか
   ら順に、且つ、被配置物と配置場所が重複しないように
   Ｎ個を選び出し、 上記選択したプロセスユニットの入力値を変化させ、 目的値を得るあるいは目的とする値を最大または最小に
   することを特徴とする最適配置方法。
2. 【請求項２】 前記選択した各プロセスユニットの示す
   被配置物の配置により得られた値のみを変数として各プ
   ロセスユニットの入力値の変化量を決定して、前記入力
   値を変化させることを特徴とする請求項１記載の最適配
   置方法。
3. 【請求項３】 前記選択したＮ個のプロセスユニットに
   対し、あるプロセスユニットが示す被配置物の配置場所
   と他のプロセスユニットが示す被配置物の配置場所とを
   互いに交換させることにより、前記選択したＮ個のプロ
   セスユニット以外のプロセスユニットの入力値の変化量
   を決定することを特徴とする請求項２記載の最適配置方
   法。
4. 【請求項４】 Ｎ個の被配置物についてのＮ個の配置場
   所を示すＮ×Ｎ個のプロセスユニットよりなるニューラ
   ルネットワークにおいて、 上記プロセスユニットの入力値の大きなものから順に、
   且つ、被配置物と配置場所が重複しないようにＮ個を選
   び出す非重複選出手段と、 上記選択したプロセスユニットの入力値を変化させる入
   力値更新手段とを有し、 目的値を得るあるいは目的とする値を最大または最小に
   することを特徴とする最適配置装置。
5. 【請求項５】 前記入力値更新手段は、前記選択したＮ
   個のプロセスユニットの示す被配置物の配置により得ら
   れた値のみを変数として各プロセスユニットの入力値の
   変化量を決定して前記入力値を変化させることを特徴と
   する請求項４記載の最適配置装置。
6. 【請求項６】 前記選択したＮ個のプロセスユニットに
   対し、あるプロセスユニットが示す被配置物の配置場所
   と他のプロセスユニットが示す被配置物の配置場所とを
   互いに交換させる配置交換手段を更に有し、 前記選択したＮ個のプロセスユニット以外のプロセスユ
   ニットの入力値の変化量を決定することを特徴とする請
   求項５記載の最適配置装置。
7. 【請求項７】 Ｎ個の被配置物についてのＮ個の配置場
   所を示すＮ行Ｎ列のプロセスユニットよりなるニューラ
   ルネットワークにおいて、 前記各プロセスユニットのうち入力値の大きなものから
   順に且つ被配置物と配置場所が重複しないようにしてＮ
   個のプロセスユニットを選択し、 該選択による実際の配置による値を計算し、 該計算した値と目的値とから上記選択したＮ個のプロセ
   スユニットの入力値の更新量を求めて入力値を変化さ
   せ、 上記一連の過程を繰り返すことにより前記実際の配置に
   よる値を前記目的値に近づけることで最適解を得ること
   を特徴とする最適配置方法。
8. 【請求項８】 Ｎ行Ｎ列のプロセスユニットよりなるニ
   ューラルネットワークにおいて、 上記各プロセスユニットの出力が各プロセスユニットの
   行、列にある他のプロセスユニットの出力に影響するよ
   うにようにして互いに相互作用を及ぼしながらネットワ
   ークの出力を決定するプロセスユニット群、 を有することを特徴とするニューラルネットワーク装
   置。
9. 【請求項９】 行列のなかの最大入力値を選択し、 次に最大入力値が存在するｉ行ｊ列を除いて前記選択の
   処理を繰り返し実行し、 これによって各行列に１が１つだけ存在する行列を形成
   し、 この情報に基づいてコスト値を示すＲ値を計算し、 目的値とＲ値との差を前記最大入力値から差し引いて新
   しい入力状態が得られると、前記一連の処理を目的値に
   Ｒ値が収束するまで繰り返すことを特徴とする最適配置
   方法。