JPH06169199A - プリント基板上に部品を自動で配置する装置 - Google Patents

Abstract

(57)【要約】 【目的】 エキスパ―トシステム（ＥＳ）による最終配
置結果の一部に対して、ユ―ザが配置改善したい部品群
を指定し、遺伝アルゴリズム（ＧＡ）を用いて、自動で
配置改善を図る。 【構成】 この発明のプリント基板上に部品を自動で配
置する装置は、入出力装置と、配置対象デ―タベ―ス
と、配置エキスパ―トユニットと、配置結果ファイルと
を含む配置エキスパ―トシステムで得られた配置結果に
対して、配置改善装置を用いて、遺伝アルゴリズム（Ｇ
Ａ）による一連の操作を行なわせ、自動で配置改善を行
なう。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は部品群の配置場所を一連
の操作によって最適化する配置改善装置を含むプリント
基板上に部品を自動で配置する装置に関する。

【０００２】

【従来の技術】プリント基板上に部品を配置する装置と
しては、従来よりいくつかのエキスパ―トシステムが提
案されている。例えば

【０００３】文献［１］半田・月本・堀内・奥本、“プ
リント配線板における部品配置エキスパ―トシステ
ム”、情報処理学会第４２回全国大会論文集、講演番号
６Ｊ−７、１９９１年。

【０００４】文献［２］阪本・大岩・土田・吉村、“プ
リント基板自動配置エキスパ―トシステムＥＳＰＡ
Ｒ”、情報処理学会第３７回全国大会論文集、講演番号
２Ｇ−６、１９８９年。

【０００５】が知られている。これらのエキスパ―トシ
ステムは基板設計者と同様に、配置すべき部品を１つず
つ選択して、その時点での最適な場所に配置していくと
いう方法が取られている。この方法によれば、配置の後
半において、配置可能なスペ―スが少なくなるので、必
ずしも好ましい場所に置けない場合が出てくる。この様
な不具合を解決する方法としては、配置済の部品を引き
剥がしたり、ずらしたりしてスペ―スを作って配置する
という方法が提案されている。

【０００６】しかしその改善方法は、部品の大きさが様
々であること、配置済部品の位置関係を変えてしまうこ
と、から起こる影響を考慮しなければならないので、あ
らゆる場合を想定した改善は困難である。

【０００７】またエキスパ―トシステムと言えども設計
者の限定された知識を使っているので、エキスパ―トシ
ステムの配置結果に対しては部分的な手修正は不可欠で
ある。

【０００８】一方、基準部品選択部、配置部品選択部、
配置場所決定部を設け、部品がプリント基板上の一箇所
に集中することのない、比較的に良い近似解を効率良く
求めようとする先行技術はある。

【０００９】しかし、ある程度部品が配置された後で
は、配置部品とその基準部品の間の配置コストが予め規
定された基準値よりも大きくなってしまい、良い配置が
出来なくなる。そのような場合の改善方法として、コス
トチェック後のずらし操作と、ずらし操作前後の評価方
法がある。

【００１０】しかしその改善方法は、部品の大きさが様
々であること、既配置部品の位置関係を変えてしまうこ
と、から起こる影響を考慮しなければならないので、あ
らゆる場合を想定した改善は困難である。

【００１１】

【発明が解決しようとする課題】上記したように、従来
のエキスパ―トシステムでは、配置すべき部品を１つず
つ選択して、その時点での最適な場所に配置していくの
で、配置の後半になると配置可能なスペ―スが少なくな
り、必ずしも好ましい場所に置けない場合が出てくる。

【００１２】本発明はこのような問題を考慮してなされ
たもので、その目的とするところは、従来のエキスパ―
トシステムによる最終配置結果に対して、ユ―ザが、配
置改善したい部品群を指定し、それらの部品群の配置場
所を、経験的知識を考慮しながら、複数個の解候補を用
いて並列的に最適化する装置を付加することにより部品
配置に関するエキスパ―トシステム（ＥＳ）による配置
結果の一部を遺伝アルゴリズム（ＧＡ）で改善しようと
するものであり、更には部品配置処理の途中過程で、配
置結果の一部分を最適に配置しなおすことのできるプリ
ント基板上に部品を自動で配置する装置を提供すること
にある。

【００１３】

【課題を解決するための手段】この発明のプリント基板
上に部品を自動で配置する装置は、プリント基板を指定
して、熟練設計者の経験的知識を用いて、部品を１つず
つ選択しながら自動で配置をする装置において、基板名
等を入力したり配置結果を出力する入出力装置と、前記
プリント基板の部品情報などを蓄える配置対象デ―タベ
―スと、前記配置対象デ―タベ―スに基づいて、全部品
を前記プリント基板上に配置する配置エキスパ―トユニ
ットと、前記入出力装置で出力されて画面表示される、
その全部品配置結果を蓄える配置結果ファイルと、を含
む配置エキスパ―トシステムと；

【００１４】前記画面表示された全部品配置結果を見
て、配置改善したい部品群を指定する配置改善部品指定
インタ―フェ―スと、前記配置改善部品指定インタ―フ
ェ―スによって指定された部品群のデ―タから成る配置
改善対象デ―タファイルと、前記配置改善対象デ―タフ
ァイルからのデ―タを受け、それら部品群の配置場所を
一連の操作によって最適化する配置改善装置と；を含
み、前記配置改善装置の一連の操作は、

【００１５】（１）部品名の列で表現された複数の初期
解を１つは配置エキスパ―トシステムの結果から作成
し、他はランダムに作成し、これら複数の初期解をそれ
ぞれ解候補とし、

【００１６】（２）前記解候補毎に、配置改善対象部品
に接続している各信号線の両端の２つのピンを結ぶ直線
を対角線とする長方形の２辺の長さの和を計算で求め、
複数の信号線の夫々に対応する前記２辺の長さの和の総
和を求めて前記解候補毎の評価参考値とし、次いで前記
各解候補が、経験的知識からくる制約条件を満たしてい
るか否かをチェックし、もし前記制約条件を満たしてい
ない解候補に対しては対応する前記評価参考値を、制約
条件の重要度に応じて、所定の値だけアップし、最後
に、全ての解候補の評価参考値の中の最大値から、各解
候補の評価参考値を差し引き、更に、その差の値に正の
定数をプラスした値を、その解候補の評価値とする。

【００１７】（３）前記複数の解候補毎に求められた評
価値に応じた確率で、新たに、前記解候補の個数と同数
個の解候補を複製し、前の同数個の解候補を破棄し、新
たに複製された解候補の間での部分解の交換や、解候補
内部での配置変更を行なう。

【００１８】（４）、（３）の操作を指定回数繰り返
し、解候補の評価値が全て同じ値になったら、前記繰り
返しの操作を中止して、そこまでの最良解を出力するよ
うに構成されている。更に、この発明のプリント基板上
に部品を自動で配置する装置は、

【００１９】プリント基板上の予め設定された格子上に
ＩＣ等の部品を配置していく場合に、次に配置する為の
基準となる既配置部品を基準部品として選択する基準部
品選択手段と、選択された基準部品に対して最も接続本
数の多い未配置部品を選択決定する配置部品選択手段
と；前記基準部品に最も近い未配置場所を配置場所とし
て決定する配置場所仮決定手段と、この配置場所として
仮決定された未配置場所に前記選択決定された未配置部
品を配置する配置場所決定手段と；

【００２０】前記配置場所仮決定手段において配置され
た配置部品とその基準部品との間の配置コストが、予め
規定された基準値よりも大きいか否かを調べるコストチ
ェック手段と；

【００２１】もし上記配置コストが、予め規定された基
準値よりも大きい場合に、基準部品を中心とし配置部品
を周上に含む矩形内の既配置部品を最適に配置し直す配
置改善手段と；より構成される。

【００２２】

【作用】本発明によれば、熟練設計者の経験的知識を用
いて、部品を１つずつ選択・配置し、更にその最終的配
置結果に対して、ユ―ザが、配置改善したい部品群を指
定し、それらの部品群を配置場所を、経験的知識を考慮
しながら、複数個の解候補を用いて並列的に最適化する
ので、全体として、ユ―ザの満足のいく配置結果を得る
ことが可能となる。

【００２３】更に、本発明によれば、部品配置処理の途
中過程において、配置部品とその基準部品に対して配置
コストをチェックし、配置コストが、予め規定された基
準値よりも大きい場合に、基準部品を中心とし配置部品
を周上に含む矩形内の既配置部品を、最適に配置し直す
ので、全体としてユ―ザの満足のいく配置結果を得るこ
とが可能となる。

【００２４】

【実施例】以下、図面を参照して本発明の一実施例に係
わるプリント基板部品配置装置につき説明する。

【００２５】図１は本発明の装置の概略的な構成を示す
ブロック図である。概略的には入出力装置１、配置対象
デ―タベ―ス２、配置エキスパ―トユニット３、配置結
果ファイル４で成る配置エキスパ―トシステムと、配置
改善部品指定インタ―フェ―ス５、配置改善対象デ―タ
ファイル６、配置改善装置７の７つのブロックから構成
される。図２は配置改善装置７の内部処理の手順を示す
フロ―チャ―トである。 本システムは基本的には、入
出力装置１から基板名等を入力して、配置対象デ―タベ
―ス２より基板の部品情報・ピン情報・接続情報等を取
り出し、そのデ―タを基に配置エキスパ―トユニット３
によって全部品を配置する。その配置結果は配置結果フ
ァイル４に蓄えられ、そして入出力装置１に出力され
る。出力は部品が配置された基板が画面表示される。ユ
―ザはその画面表示された配置結果を見て、配置改善し
たい部品を配置改善指定インタ―フェ―ス５によって指
定する。この指定によって配置改善対象デ―タファイル
６ができる。このデ―タファイルを基に配置改善装置７
が最適化を試み、その結果を配置結果ファイル４に送
る。改善結果は、再び入出力装置１の画面上に出力され
る。このように構成されたプリント基板部品配置装置に
ついて、更に詳しく説明する。

【００２６】配置エキスパ―トシステムは従来の知られ
ているシステムであり、上記文献［１］に開示されてい
る。今、配置エキスパ―トシステムにより、図３に示す
配置結果が得られたとする。但し図３は配置結果の一部
を示す図であり、またその図も簡略化してある。本来、
信号線は部品のピン間の接続関係を表すものであるが、
ここではそれらの信号線を２部品毎にまとめて１本の線
で表し、その横に実際の線の本数を書いて、簡略化して
いる。

【００２７】尚、この配置結果は入出力装置１の画面上
に表示されているものとする。ユ―ザはこの配置結果を
見て、もし配置改善したい部品があれば、その部品を配
置改善部品指定インタ―フェ―ス５によって指定する。
指定方法は画面上で部品をマウスでクリックする等の方
法をとる。今、配置改善対象部品として、図３の部品
Ａ、Ｃ、Ｄ、Ｅが指定されたとする。配置改善対象デ―
タファイル６にはこれら４部品の名前と配置場所が受け
渡される。

【００２８】配置改善装置７は、これら４部品が占めて
いる領域（図ではα，β，γ，δ）を配置改善対象領域
とし、配置対象デ―タベ―ス２と配置結果ファイル４を
参照しながら、４部品の最良の配置状態を算出する。配
置改善装置７の動作は、基本的には、図２のフロ―チャ
―トで示したように

【００２９】（１）部品名の列で表現された複数の初期
解を１つは配置エキスパ―トシステムの結果から作成
し、他はランダムに作成し、これら複数の初期解をそれ
ぞれ解候補とし（ステップＳ１）、

【００３０】（２）前記解候補毎に、配置改善対象部品
に接続している各信号線の両端の２つのピンを結ぶ直線
を対角線とする長方形の２辺の長さの和を計算で求め、
複数の信号線の夫々に対応する前記２辺の長さの和の総
和を求めて前記解候補毎の評価参考値とし、次いで前記
各解候補が、経験的知識からくる制約条件を満たしてい
るか否かをチェックし、もし前記制約条件を満たしてい
ない解候補に対しては対応する前記評価参考値を、制約
条件の重要度に応じて、所定の値だけアップし、最後
に、全ての解候補の評価参考値の中の最大値から、各解
候補の評価参考値を差し引き、更に、その差の値に正の
定数をプラスした値を、その解候補の評価値とする（ス
テップＳ２）。

【００３１】（３）前記複数の解候補毎に求められた評
価値に応じた確率で、新たに、前記解候補の個数と同数
個の解候補を複製し、前の同数個の解候補を破棄し（ス
テップＳ３）、新たに複製された解候補の間での部分解
の交換や、解候補内部での配置変更を行なう（ステップ
Ｓ４）。

【００３２】（４）、（３）の操作を指定回数繰り返
し、解候補の評価値が全て同じ値になったら、前記繰り
返しの操作を中止して、そこまでの最良解を出力する
（ステップＳ５）。 上述した基本的動作を、更に具体的に説明する。

【００３３】基本的動作を行なうに先立ち、予めパラメ
―タとして初期解の数は４、上述した動作中（４）に示
す（３）の繰り返し回数は１０、動作中（２）における
正の定数は０．５と定める。

【００３４】制約条件は「部品Ａは基板の下端に配置さ
れなければならない」という条件だけとし、もしこの条
件を満たさなければ評価参考値を＋３とするものとす
る。尚、実際問題においては制約条件は通常複数ありう
るが、そのような場合はその各制約条件の重要度に応じ
て評価参考値をそれぞれ増加させればよい。

【００３５】さて、まず初期解を４つ作る。１つは配置
エキスパ―トシステムの結果から、残りはランダムに作
る。下に示す（ｉ）は前者、（ｉｉ）、（ｉｉｉ）、
（ｉｖ）は後者の方法で作ったものとする： （ｉ） Ｄ，Ｅ，Ａ，Ｃ （ｉｉ） Ｄ，Ｃ，Ｅ，Ａ （ｉｉｉ）Ａ，Ｄ，Ｃ，Ｅ （ｉｖ） Ｅ，Ａ，Ｄ，Ｃ これら４つの初期解をそれぞれ解候補とする。各解候補
はその部品名の順に、図３に示す配置改善対象領域α，
β，γ，δに配置された状態を表示すものとする。

【００３６】次に、上述した（２）に従う方法でそれぞ
れの評価値を求める。説明を簡単にするために、縦また
は横に隣合う部品同士を繋ぐ信号線の長さは全て１とす
る。従って例えば、図３の部品ＣとＤを繋ぐ信号線の長
さは３となる。この計算方法で各解候補の評価参考値を
計算すると、（ｉ）は長さ１の線が２＋３＋１＝６本、
長さ２の線が２＋４＋２＋５＝１３本、長さ３の線が１
＋４＝５本あるので、その評価参考値は６＊１＋１３＊
２＋５＊３＝４７となる。ここで評価参考値は仮相配線
長と言える。同様にして（ｉｉ）、（ｉｉｉ）、（ｉ
ｖ）の評価参考値を求めると、 （ｉｉ）（１＋１＋２）＊１＋（２＋２＋４＋５）＊２
＋（３＋４）＊３＝５１ （ｉｉｉ）（１＋２＋３＋５）＊１＋（１＋２＋２＋
４）＊２＋４＊３＝４１ （ｉｖ）（１＋２＋２＋４）＊１＋（１＋３＋４＋５）
＊２＋２＊３＝４１

【００３７】となる。次に制約条件をチェックする。
（ｉ）と（ｉｉ）が制約条件を満たさないので、
（ｉ）、（ｉｉ）の評価参考値はそれぞれ４７＋３＝５
０、５１＋３＝５４となる。これら評価参考値から評価
値を計算すると、 （ｉ） ５４−５０＋０．５＝４．５ （ｉｉ） ５４−５４＋０．５＝０．５ （ｉｉｉ）５４−４１＋０．５＝１３．５ （ｉｖ） ５４−４１＋０．５＝１３．５ となる。次にこれらの評価値に応じた確率で新たに４個
の解候補を複製する：

【００３８】ここで（ｉ）〜（ｉｖ）の評価値の和をと
ると、４．５＋０．５＋１３．５＋１３．５＝３２とな
り、評価値に応じた確率とは各評価値を３２で割った値
である。即ち、

【００３９】

【数１】

【００４０】この確率に応じて、新たに４個の解候補を
複製する。（ｉｉ）は値が小さいので複製される可能性
は小さく、（ｉｉｉ）、（ｉｖ）は値が大きいので複製
される可能性が大きい。従って、 （ｉ） Ｄ，Ｅ，Ａ，Ｃ←前の（ｉ）より複製 （ｉｉ） Ａ，Ｄ，Ｃ，Ｅ←前の（ｉｉｉ）より複製 （ｉｉｉ）Ａ，Ｄ，Ｃ，Ｅ←前の（ｉｉｉ）より複製 （ｉｖ） Ｅ，Ａ，Ｄ，Ｃ←前の（ｉｖ）より複製

【００４１】（ｉｉｉ）は評価値が高いので２個複製
し、一方（ｉｉ）は評価値が低いので１つも複製してい
ないことに注意する。但し、ここでの複製方法は確率的
にあるので、（ｉｉ）が複製されることもありうる。解
候補の数は常に一定にしたいので、前の４つの解候補は
破棄する。

【００４２】次に、上述した４つの解候補をランダムに
２つずつの組、例えば（ｉ）と（ｉｉ）及び（ｉｉｉ）
と（ｉｖ）に分ける。これら夫々の組に対して以下に例
示する方法で部分解の交換を行なう。例として部品数が
８個の場合、部品名を通番１、２、…８で表し （ａ） ３ ５ ２ ４ ８ １ ７ ６ （ｂ） １ ６ ７ ４ ２ ５ ４ ３

【００４３】という２つの文字列の組を考える。まず、
（ａ）の第１成分から上下に３→１と辿る。そして次に
（ａ）より文字１を探し、１→５と辿る。これを繰り返
すと、５→６，６→３となり、再び３に戻る。｛３→
１，１→５，５→６，６→３｝を１つのサイクルと呼
ぶ。次にまだ使用していない文字を（ａ）より探す。２
が未使用なので、今度は２から２→７，７→８，８→２
と辿る。これによって２つ目のサイクル｛２→７，７→
８，８→２｝ができる。このような操作を未使用の文字
が無くなるまで繰り返す。最後にこの一連の操作ででき
たサイクルのうちで偶数回目のものに対して、（ａ），
（ｂ）間で文字の交換をする。すると （ａ） ３ ５ ７ ４ ２ １ ８ ６ （ｂ） １ ６ ２ ４ ８ ５ ７ ３ が得られる。

【００４４】（ｉ），（ｉｉ），（ｉｉｉ），（ｉｖ）
のそれぞれの組に対して、上記の方法で部分文字列の変
換、即ち部分解の交換を行なう。この場合、どちらの組
に対しても偶数個目のサイクルが存在しないので、部分
解の交換は行なわれない。

【００４５】次に、各解候補の内部で２部品の交換を行
なう。この方法は非常に小さい確率（ここでは０．２と
する）で２部品交換を行なうか否かを決める。ここでは
（ｉ）に対してのみ、２部品交換を行なうことになった
とする。（ｉ）のどの２部品を交換するかはランダムで
ある。ここではＣとＤを交換したとする： （ｉ） Ｃ，Ｅ，Ａ，Ｄ（評価参考値：４０，評価
値：４．５） （ｉｉ） Ａ，Ｄ，Ｃ，Ｅ（評価参考値：４１，評価
値：３．５） （ｉｉｉ）Ａ，Ｄ，Ｃ，Ｅ（評価参考値：４１，評価
値：３．５） （ｉｖ） Ｅ，Ａ，Ｄ，Ｃ（評価参考値：４４，評価
値：０．５） 以上が前記配置改善装置の一連の操作のうちの（３）の
第１回目の操作である。更に、（３）の操作をもう１度
繰り返す： （ｉ） Ｃ，Ｅ，Ａ，Ｄ←前の（ｉ）より複製 （ｉｉ） Ｃ，Ｅ，Ａ，Ｄ←前の（ｉ）より複製 （ｉｉｉ）Ａ，Ｄ，Ｃ，Ｅ←前の（ｉｉ）より複製 （ｉｖ） Ａ，Ｄ，Ｃ，Ｅ←前の（ｉｉｉ）より複製

【００４６】そして、ランダムに決めた２つずつの組
（ｉ），（ｉｉｉ）；（ｉｉ），（ｉｖ）に対して、先
に述べた方法で部分解の交換を行なうと、（ｉ），（ｉ
ｉｉ）に対しては、｛Ｃ→Ａ，Ａ→Ｃ｝、｛Ｅ→Ｄ，Ｄ
→Ｅ｝という２つのサイクルがあるので（ｉ）のＥ，Ｄ
と、（ｉｉｉ）のＤ，Ｅを上下で交換する。（ｉｉ），
（ｉｖ）の組に対しても同様である。 （ｉ） Ｃ，Ｄ，Ａ，Ｅ（評価参考値：４１，評価
値：０．５） （ｉｉ） Ｃ，Ｄ，Ａ，Ｅ（評価参考値：４１，評価
値：０．５） （ｉｉｉ）Ａ，Ｅ，Ｃ，Ｄ（評価参考値：３３，評価
値：８．５） （ｉｖ） Ａ，Ｅ，Ｃ，Ｄ（評価参考値：３３，評価
値：８．５） 各解候補の内部での２部品の交換は今回は行なわれなか
ったとする（確率が０．２と小さいので）。

【００４７】上記の４つの解候補に対して更にもう一度
（３）の操作を施すと、（ｉｉｉ）＝（ｉｖ）のコピ―
が４つできるので、（４）の終了条件により、ここまで
の最良解であるＡ，Ｅ，Ｃ，Ｄを出力して終了する。

【００４８】配置改善装置７による配置改善結果の情報
は配置結果ファイルＡに蓄えられ、再び入出力装置１の
画面上に出力される。図４はその出力結果の例である。
図３と同様、信号線は１部品毎にまとめて１本の線で表
している。

【００４９】尚、上述した実施例は全部品の配置結果を
見て、配置改善したい部品群を指定したが例えば配置エ
キスパ―トユニット３の作業を途中で中断して、その時
点で未配置の部品を配置改善装置７によって配置するこ
ともできる。

【００５０】次に、部品配置処理の途中過程において、
配置部品と、その基準部品に対して配置コストをチェッ
クし、配置コストが、予め規定された基準値よりも大き
い場合に、基準部品を中心とし、配置部品を周上に含む
矩形内の既配置部品を、最適に配置しなおすことのでき
る実施例について以下に説明する。

【００５１】図５は実施例システムの概略的な構成を示
すブロック図である。この実施例システムは、概略的に
は配置対象デ―タ入力部１０、配置問題解決処理部２
０、配置結果出力部３０の３つのブロックから構成され
る。配置対象デ―タ入力部１０は、プリント基板の部品
情報、ピン情報、接続情報等のデ―タを入力する為のも
のである。

【００５２】配置問題解決処理部２０は、配置対象デ―
タ入力部１から与えられる入力デ―タに従って配置問題
を解決処理するもので、基準部品選択部２ａ、配置部品
選択部２ｂ、配置場所仮決定部２ｃ、コストチェック部
２ｄ、配置改善装置２ｅ、配置場所決定部２ｆの６つの
処理機能を備えている。これら６つの処理機能は互いに
関連して動作する。２ａ，２ｂ，及び２ｆの処理機能に
ついては、詳細は略す。 基本的には、先ず基準部品選
択部２ａにて前記入力デ―タに基づいて、既に配置決定
された既配置部品の中から、以下に示す配置部品を選択
決定する為の基準となる既配置部品を基準部品αとして
選択する。次に、配置部品選択部２ｂが起動され、前述
した如く選択された基準部品αに対して、その基準部品
との接続本数が最大の未配置部品βを１つ選択する。次
に、配置場所仮決定部２ｃにおいて配置部品βの配置場
所を仮決定する。

【００５３】コストチェック部２ｄでは、２部品α，β
間の配置コストを計算し、その配置コストが、予め規定
された基準値よりも大きいか否かを調べる。もし小さい
か若しくは等しければ、配置場所決定部２ｆにて部品β
の仮の配置場所を配置場所として決定する。大きけれ
ば、配置改善装置２ｅが起動され、基準部品αを中心と
し配置部品βを周上に含む矩形内の既配置部品を、最適
に配置し直す。このように構成されたプリント基板上に
部品を自動で配置する装置について、更に詳しく説明す
る。

【００５４】今、図６に示すようにプリント基板の予め
設定された格子上の点に１６個の部品が既に配置済みで
あり、基準部品選択部２ａにて部品Ｋが基準部品とし
て、配置部品選択部２ｂにて部品Ｐが選択部品として、
配置場所仮決定部２ｃにて（ｘ５，ｙ３）の位置に仮配
置されたとする。ここで（ｍ，ｎ）は格子点の列と行の
対を表すものとする。また、部品を配置するときは、そ
の１番ピンが左上にくる向きで配置するものとする。

【００５５】尚、図６では、以下の説明に関連する信号
線のみを表示している。その表示方法は、部品のピン間
の信号線を、簡単の為に、２部品毎にまとめて１本の線
で表し、その横に実際の線の本数を書いて、簡略化して
いる。

【００５６】コストチェック部２ｄでは、部品Ｋ，Ｐ間
の配置コストを請求項（４）に従い計算し、その値が、
配置コストの予め規定された基準値よりも大きいか否か
を調べる。ここでは、全ての２部品の対に対して、基準
値１２が予め与えられているものとする。さて２部品
Ｋ，Ｐ間の配置コストを計算すると、 （ｘ方向の格子座標の差＋ｙ方向の格子座標の差）×
（Ｋ，Ｐ間の接続本数）＝（２＋１）×５＝１５ となる。この値は基準値１２よりも大きいので、次は配
置改善装置２ｅが起動されることになる。

【００５７】配置改善装置２ｅでは、部品Ｋを中心とし
部品Ｐを周上に含む矩形内の、原則として全ての既配置
部品Ｂ，Ｃ，Ｄ，Ｆ，Ｇ，Ｈ，Ｊ，Ｋ，Ｌ，Ｍ，Ｎ，
Ｏ，Ｐ，Ｑが対象となる。但し、部品配置処理には通
常、配置順や配置場所に関する制約条件、例えば「コネ
クタとの接続本数の多い部品はなるべくコネクタに隣接
配置する」、のような制約条件が付加されている部品が
存在する。そのような部品は一般に配置順や配置場所に
関し、優先されて配置処理されるので、たとえ前記矩形
内に配置されていても改善の対象から外すべきである。
ここでは、部品Ａ，Ｂ，…，Ｊ、及びＬ，Ｏ，Ｑがその
ような改善不要の部品であるとする。従って、矩形内の
４つの既配置部品Ｋ，Ｍ，Ｎ，Ｐを配置改善の対象とす
る。このように配置改善部品を限定しても以下の説明の
一般性が失わることはない。

【００５８】配置改善装置２ｅでは、これら４部品の配
置改善部品を、最適に配置し直す。４部品の配置場所
は、ここでは説明を簡単にするために、それらが以前占
めていた領域（ｘ３，ｙ４）、（ｘ４，ｙ３）、（ｘ
４，ｙ４）、（ｘ５，ｙ３）だけを使うものとする。
（ｘ５，ｙ５）のような矩形内の空き場所の扱いに付い
ては、その場所に、他部品と全く接続関係の無い部品が
存在しているものと考え、以下の説明において、その部
品を含めて考えれば良い。配置改善装置２ｅの作業は、
基本的には、

【００５９】部品名Ｋ，Ｍ，Ｎ，Ｐの列で表現された複
数個の解候補に対し、それぞれの配置コストを求め、そ
れら配置コストに応じた確率で新たに同数個の解候補を
複製し、前回の同数個の解数個の解候補を破棄し、新し
い解候補の間での部分解の交換や解候補内部での配置変
更を行なう、

【００６０】この一連の操作を、ランダムに作成した複
数個の初期解から始めて、指定回数繰り返す、但し解候
補が全て互いに同一になったらそこで繰り返しを中止
し、そこまでの最良解を出力する。ここでは、解候補の
個数は４、指定回数は１０とする。さて、まず初期解ラ
ンダムに４つ作る： （１）Ｋ，Ｍ，Ｎ，Ｐ （２）Ｐ，Ｎ，Ｋ，Ｍ （３）Ｎ，Ｍ，Ｐ，Ｋ （４）Ｍ，Ｐ，Ｋ，Ｎ 各解はその部品名の順に、配置領域（ｘ３，ｙ４）、
（ｘ４，ｙ３）、（ｘ４，ｙ４）、（ｘ５，ｙ３）に配
置された状態を表すものとする。次、配置コストを求め
る。まず（１）に関しては、ＰＧ間の配置コストが （ｘ方向の格子座標の差＋ｙ方向の格子座標の差）×
（ＰＧ間の接続本数）＝（３＋１）×３＝１２、

【００６１】同様にして、ＰＫ間が（２＋１）×５＝１
５、ＭＫ間が（１＋１）×２＝４、ＮＪ間が（１＋１）
×３＝６、ＭＪ間が１×４＝４、ＮＫ間が１×１＝１、
ＫＧ間が１×３＝３であるから（１）の配置コストは１
２＋１５＋４＋６＋４＋１＋３＝４５である。同様にし
て（２），（３），（４）の配置コストを求めると、そ
れぞれ３０、４０、３４となる。次に、これら配置コス
トに応じた確率で新たに４個の解候補を複製する。 （１）Ｐ，Ｎ，Ｋ，Ｍ←前回の（２）より複製 （２）Ｐ，Ｎ，Ｋ，Ｍ←前回の（２）より複製 （３）Ｎ，Ｍ，Ｐ，Ｋ←前回の（３）より複製 （４）Ｍ，Ｐ，Ｋ，Ｎ←前回の（４）より複製

【００６２】（２）は配置コストが低いので２個複製
し、一方（１）は配置コストが高いので１つも複製して
いないことに注意する。但し、ここでの複製方法は確率
的であるので、（１）が複製されることもありうる。解
候補の数は常に一定にしたいので、前回の４つの解候補
は破棄する。次に４つの解候補をランダムに２つずつの
組に分ける：（１），（３）；（２），（４）。そして
それぞれの組に対して、方法で部分解の交換を行なう。

【００６３】例として、部品数が８個の場合、部品名を
通書１、２…で表し、２つの文部列の組を考える場合の
文書の交換例については前述した実施例におけると同様
であり、その説明を省略する。

【００６４】（１），（３）の組に対してはサイクルが
１つしか存在しない。（２），（４）の組に対してはサ
イクルが２つ存在するが、２つ目のサイクルは｛Ｋ→
Ｋ｝である。従って、この場合どちらの組に対しても、
実質的に部分解の交換は行なわれない。

【００６５】次に、各解の内部で２部品の交換を行な
う。その方法は非常に小さい確率（ここでは０．２とす
る）で２部品交換を行なうか否かを決める。ここでは
（３）に対してのみ、２部品交換を行なうことになった
とする。（３）のどの２部品を交換するかはランダムで
ある。ここではＮとＫを交換したとする： （１）Ｐ，Ｎ，Ｋ，Ｍ（配置コストは３０） （２）Ｐ，Ｎ，Ｋ，Ｍ（配置コストは３０） （３）Ｋ，Ｍ，Ｐ，Ｎ（配置コストは３１） （４）Ｍ，Ｐ，Ｋ，Ｎ（配置コストは３４） 以上が一連の繰り返し操作の第１回目の操作である。こ
の時点ではまだ一連の繰り返し操作の終了条件を満たし
ていないので、第２回目の操作に入る： （１）Ｐ，Ｎ，Ｋ，Ｍ←前回の（１）より複製 （２）Ｐ，Ｎ，Ｋ，Ｍ←前回の（２）より複製 （３）Ｋ，Ｍ，Ｐ，Ｎ←前回の（３）より複製 （４）Ｋ，Ｍ，Ｐ，Ｎ←前回の（３）より複製

【００６６】そして、ランダムに決めた２つずつの組
（２），（３）；（１），（４）に対して、先に述べた
方法で部分解の交換を行なうと、（２），（３）に対し
ては｛Ｐ→Ｋ，Ｋ→Ｐ｝、｛Ｎ→Ｍ，Ｍ→Ｎ｝という２
つのサイクルがあるので（２）のＰ，Ｋと（３）のＫ，
Ｐを上下で交換する。（１），（４）の組に対しても同
様である： （１）Ｋ，Ｎ，Ｐ，Ｍ（配置コストは３３） （２）Ｋ，Ｎ，Ｐ，Ｍ（配置コストは３３） （３）Ｐ，Ｍ，Ｋ，Ｎ（配置コストは２８） （４）Ｐ，Ｍ，Ｋ，Ｎ（配置コストは２８） 各解の内部での２部品の交換は今回は行なうことになら
なかったとする（確率が０．２と小さいので）。

【００６７】上記の４つの解候補に対して更に第３回目
の操作に入る。第３回目の操作では、（３）又は（４）
のみが複製されたとする。この場合、一連の繰り返し操
作の終了条件の１つである「解候補が全て互いに同一」
という条件を満たすので、操作を終了する。そしてここ
までの最良解であるＰ，Ｍ，Ｋ，Ｎを出力して終了す
る。図３はこの出力結果（改善結果）を図示したもので
ある。

【００６８】尚、本発明は上述した実施例に限定される
ものではない。例えば実際的には部品の大きさは様々で
あるから、それらの大きさを考慮し、部品同士が重なら
ないように配置しなければならないことは勿論である。
また配置改善装置２ｅで対象とする矩形は、基準部品と
選択部品を含む種々の矩形に対して適用することができ
る。また配置改善装置２ｅにおける複数個の初期解の作
成方法には、ランダムな作成方法の他に、例えば経験的
知識を用いたエキスパ―トシステムを用いて比較的良い
初期解を作る等、種々の方法を適用することができる。
その他、本発明はその要旨を逸脱しない範囲で種々変形
して実施することができる。

【００６９】

【発明の効果】以上詳述したように本発明のプリント基
板上に部品を自動で配置する装置によれば、プリント基
板上に、熟練設計者の経験的知識を用いて、部品を１つ
ずつ選択・配置し、更にその最終的配置結果に対して、
ユ―ザが、配置改善したい部品群を指定し、それらの部
品群の配置場所を、経験的知識を考慮しながら、複数個
の解候補を用いて並列的に最適化するので、全体として
非常に優れた配置結果を得ることが可能となる。また所
々に確率的な選択方法が採られているむので、いわゆる
局所的最適解にとらわれることは少ない。更に、部品配
置処理の途中過程において、配置部品とその基準部品の
間の配置コストが予め規定された基準値よりも大きい場
合に、基準部品を中心とし配置部品を周上に含む矩形内
の既配置部品を、配置コストを減らすことを目的に最適
に配置し直すので、全体として非常に優れた配置結果を
得ることが可能となる。

【図面の簡単な説明】

【図１】この発明のプリント基板上に部品を自動で配置
する装置のシステム構成図。

【図２】図１に示す配置改善装置７の内部処理の手順を
示すフロ―チャ―ト。

【図３】この発明の配置エキスパ―トシステムによって
配置されたプリント基板上の部品の配置結果を示す図。

【図４】この発明の配置改善装置によって配置改善され
た結果を示す部品配置図。

【図５】この発明のプリント基板上に部品を自動で配置
する装置の概略的な構成を示すブロック図。

【図６】図５に示す実施例においてプリント基板上に部
品を配置処理する途中過程を示す図。

【図７】図５及び図６に示す実施例においてプリント基
板上の部品の配置改善を行なった後を示す図。

【符号の説明】

１…入出力装置、 ２…配置対象デ―タ
ベ―ス、３…配置エキスパ―トユニット、 ４…配置結
果ファイル、５…配置改善部品指定インタ―フェ―ス、
６…配置改善対象デ―タファイル、７…配置改善装置、
１０…配置対象データ入力部 ２０…配置問題解決処理部、 ２ａ…基準部品選択
部、２ｂ…配置部品選択部、 ２ｃ…配置場所
仮決定部、２ｄ…コストチェック部、 ２ｅ…配
置改善装置。２ｆ…配置場所決定部 ３０…
配置結果出力部

Claims (4)

【特許請求の範囲】
1. 【請求項１】 プリント基板を指定して、熟練設計者の
   経験的知識を用いて、部品を１つずつ選択しながら自動
   で配置をする位置において、基板名等を入力したり配置
   結果を出力する入出力装置と、前記プリント基板の部品
   情報などを蓄える配置対象デ―タベ―スと、前記配置対
   象デ―タベ―スに基づいて、全部品を前記プリント基板
   上に配置する配置エキスパ―トユニットと、前記入出力
   装置で出力されて画面表示される、その全部品配置結果
   を蓄える配置結果ファイルと、を含む配置エキスパ―ト
   システムと；前記画面表示された全部品配置結果を見
   て、配置改善したい部品群を指定する配置改善部品指定
   インタ―フェ―スと、前記配置改善部品指定インタ―フ
   ェ―スによって指定された部品群のデ―タから成る配置
   改善対象デ―タファイルと、前記配置改善対象デ―タフ
   ァイルからのデ―タを受け、それら部品群の配置場所を
   一連の操作によって最適化する配置改善装置とを含み、
   前記配置改善装置の一連の操作は、 （１）部品名の列で表現された複数の初期解を１つは配
   置エキスパ―トシステムの結果から作成し、他はランダ
   ムに作成し、これら複数の初期解をそれぞれ解候補と
   し、 （２）前記解候補毎に、配置改善対象部品に接続してい
   る各信号線の両端の２つのピンを結ぶ直線を対角線とす
   る長方形の２辺の長さの和を計算で求め、複数の信号線
   の夫々に対応する前記２辺の長さの和の総和を求めて前
   記解候補毎の評価参考値とし、次いで前記各解候補が、
   経験的知識からくる制約条件を満たしているか否かをチ
   ェックし、もし前記制約条件を満たしていない解候補に
   対しては対応する前記評価参考値を、制約条件の重要度
   に応じて、所定の値だけアップし、最後に、全ての解候
   補の評価参考値の中の最大値から、各解候補の評価参考
   値を差し引き、更に、その差の値に正の定数をプラスし
   た値を、その解候補の評価値とする。 （３）前記複数の解候補毎に求められた評価値に応じた
   確率で、新たに、前記解候補の個数と同数個の解候補を
   複製し、前の同数個の解候補を破棄し、新たに複製され
   た解候補の間での部分解の交換や、解候補内部での配置
   変更を行なう。 （４）、（３）の操作を指定回数繰り返し、解候補の評
   価値が全て同じ値になったら、前記繰り返しの操作を中
   止して、そこまでの最良解を出力する、ことを特徴とす
   るプリント基板上に部品を自動で配置する装置。
2. 【請求項２】 プリント基板上の予め設定された格子上
   にＩＣ等の部品を配置していく場合に、次に配置する為
   の基準となる既配置部品を基準部品として選択する基準
   部品選択手段と；選択された基準部品に対して最も接続
   本数の多い未配置部品を選択決定する配置部品選択手段
   と；前記基準部品に最も近い未配置場所を配置場所とし
   て決定する配置場所仮決定手段と；この配置場所として
   仮決定された未配置場所に前記選択決定された未配置部
   品を配置する配置場所決定手段と；前記配置場所仮決定
   手段において配置された配置部品とその基準部品との間
   の配置コストが、予め規定された基準値よりも大きいか
   否かを調べるコストチェック手段と；もし上記配置コス
   トが、予め規定された基準値よりも大きい場合に、基準
   部品を中心とし配置部品を周上に含む矩形内の既配置部
   品を最適に配置し直す配置改善手段と；を具備したこと
   を特徴とするプリント基板上に部品を自動で配置する装
   置。
3. 【請求項３】 部品名の列で表現された複数個の解候補
   に対し、それぞれの配置コストを求め、それら配置コス
   トに応じた確率で新たに同数個の解候補を複製し、前回
   の同数個の解候補を破棄し、新しい解候補の間での部分
   解の交換や解候補内部での配置変更を行なう、この一連
   の操作を、複数個の初期解から始めて、指定回数繰り返
   す、但し解候補が全て互いに同一になったらそこで繰り
   返しを中止し、そこまでの最良解を出力することを特徴
   とする請求項２に記載のプリント基板上に部品を自動で
   配置する装置。
4. 【請求項４】 任意の２部品Ａ，Ｂに対して、（ｘ方向
   の格子座標の差＋ｙ方向の格子座標の差）×（Ａ，Ｂ間
   の接続本数）を２部品Ａ，Ｂ間の配置コストとし、配置
   改善対象部品及びそれらと接続している部品の全てに対
   して、２部品毎にその間の配置コストを計算し、その和
   を解の配置コストとすることを特徴とする請求項２、あ
   るいは請求項３に記載のプリント基板上に部品を自動で
   配置する装置。