JPH0773158A

JPH0773158A - 計画立案方法および装置

Info

Publication number: JPH0773158A
Application number: JP17176593A
Authority: JP
Inventors: Haruki Inoue; 春樹井上; Hiroyuki Ichikawa; 弘幸市川; 英雄 ▲吉▼田; Hideo Yoshida; Yasuhiro Terada; 保広寺田; Noboru Abe; 登阿部; Yoshiyuki Sato; 良幸佐藤; Masakazu Yahiro; 正和八尋; Akemi Ootsuki; 朱美大槻
Original assignee: Hitachi Engineering Co Ltd Ibaraki; Hitachi Ltd
Current assignee: Hitachi Ltd; Hitachi Industry and Control Solutions Co Ltd
Priority date: 1993-07-12
Filing date: 1993-07-12
Publication date: 1995-03-17
Also published as: US5623580A

Abstract

(57)【要約】【目的】与えられた問題に対する最適な計画立案を、高
速に行う手段を提供すること。【構成】与えられた計画対象となる問題を受け付ける設
定手段と、前記計画対象となる問題において、最小化ま
たは最大化を図る項目を表す目的関数を作成し、作成さ
れた目的関数の値を最小化または最大化する処理を行う
最適化手段と、最適化処理に必要な定数を少なくとも記
憶する記憶手段と、前記最適化手段での処理結果を表示
する表示手段を具備し、前記最適化手段は、前回立案さ
れた計画と、新たに立案された計画における前記目的関
数の差分値を計算する第１の機能と、前記目的関数の差
分値と前記記憶手段内に設定された定数値とを比較し
て、前記目的関数の差分値が、前記定数値より小さい場
合に、前回立案した計画を、今回立案した計画に置き換
え計画候補とする第２の機能を有する手段である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、各種分野における様々
な計画立案等における、最適な計画案を提供する手段に
関し、特に、順列、組合せの数が膨大で、かつ、必ず最
適解となる計画案が存在する問題を、簡易な構成で極め
て高速に解決する手段に関する。

【０００２】

【従来の技術】従来から、多種多様な分野（例えば、電
子基板のプリントパターン設計、製造プロセス、、下水
道配管設計、物流システム等）における、各種問題を対
象とする計画立案問題において、最大、あるいは、最小
とする項目を決め、該項目を、最大、あるいは、最小と
する計画案である最適解を、現実的に許容し得る時間内
に見つけ出すために各種の手法が提案されてきた。

【０００３】例えば、文献「「巡回セールスマン問題」
に画期的解法−カオス利用で驚異の高成績、科学朝日、
１９９３−Ｆｅｂ．」、あるいは、特開平２−３０４５
８７号公報「最短距離、最短時間または最低交通費算出
装置」に記載されているように、相互結合型ニューラル
ネットワーク、カオス等を応用して、各種分野における
計画立案問題の最適化を、現実的に許容し得る時間内で
行う手段を実現しようとするものであった。

【０００４】

【発明が解決しようとする課題】与えられた計画問題に
対して、考えうる全ての計画案の組合せを検討する、い
わゆる「列挙法」に対して、前記のように相互結合型ニ
ューラルネットワーク、カオス等の応用例を含む近年の
最適化手段の共通的な考え方は、まず、初めにある計画
案を立案し、当該計画案の内容を少しずつ、効率的に変
更させ（すなわち、ランダムに立案するのではなく、少
ない立案回数で最適解を得ようとする工夫を施してい
る）、計画問題において、最終的に最大または最小にし
たい項目を表す、目的関数の値を評価していき、優れた
計画（例えば、目的関数値を減少させる計画）を、次候
補の計画案として採用し、最終的に短時間で最適解、す
なわち、目的関数を最大または最小にする計画案を得よ
うするものである。

【０００５】しかしながら、従来の各種の手法において
は、第１に、新たに計画立案を行う毎に、前記目的関数
の最適化を行うための計画立案時のパラメータである、
計画対象となる計画の構成要素数ｎの、少くとも２〜３
乗回の、計画立案のための処理が必要であること、さら
に、第２に、最適解へ到達できるという理論的裏づけが
なく、経験的に最適性を評価しているために、最適解、
あるいは、準最適解に到達するのに長い処理時間を要
し、しかも、最適解に到達する確率が極めて低いという
問題点を有していた。

【０００６】例えば、前記文献に記載されているシステ
ムにおいては、３０ヶ所を各々１回だけ訪問する経路の
うち、最短であるものを決定する、いわゆる「巡回セー
ルスマン問題」の解決を、最近のコンピュータ（例え
ば、１０〜１００（ＭＩＰＳ）の能力を有するワークス
テーション等）を使用しても、２０秒という長時間を要
してしまう。しかも、３（％）の確率で、最適解を誤っ
て求めてしまう。

【０００７】そこで、本発明の目的は、上記問題点を解
決し、組合せの数が膨大である計画問題の中から、目的
関数を最大あるいは最小にする計画案である最適解を、
極めて短時間で求める手段を提供することである。

【０００８】

【課題を解決するための手段】上記課題を解決するた
め、以下の手段が考えられる。

【０００９】すなわち、与えられた計画対象となる問
題、および、該問題の解決に必要な変数の値を少なくと
も受け付ける設定手段と、前記計画対象となる問題にお
いて、最小化または最大化を図る項目を表す目的関数を
作成し、作成された目的関数の値を最小化または最大化
する計画を立案する最適化手段と、計画立案に必要な変
数を少なくとも記憶する記憶手段とを具備し、前記最適
化手段は、前回立案された計画と、新たに立案された計
画における前記目的関数の差分値を計算する演算手段
と、前記目的関数の差分値と前記記憶手段内に、予め設
定された変数の値とを比較して、前記目的関数の差分値
が、前記予め設定された変数の値より小さい場合に、前
回立案した計画を、今回立案した計画に置き換え、最適
計画候補とする再計画手段を備える計画立案装置であ
る。また、さらに、表示手段を備え、前記表示手段は、
最適化手段での計画立案結果を表示する計画立案装置も
好ましい。

【００１０】また、以下の計画立案方法も考えられる。

【００１１】与えられた計画候補の内容を変更して、計
画において最小化または最大化を図る項目を表す目的関
数の値を、最小あるいは最大にする計画立案方法であっ
て、計画が順列問題である場合には、順列の要素並びの
一部を変更し、また、計画が組合わせ問題である場合に
は、選択する要素の少なくとも１つを、変更して選択
し、前記変更によって生ずる目的関数値の差分を演算
し、その差分値が、計画変更のたびに徐々に減少する値
範囲内に一様に分布する値より小さい場合には、変更後
の計画を最適計画候補とする計画立案方法である。

【００１２】

【作用】本発明は、ニューラルネットワーク等の、冗長
な他の最小化手段を採用せず（すなわち、従来は最適化
のために不必要な手段も多く有していた）、極めて明解
な最適化方法である。

【００１３】すなわち、本発明は、計画立案の繰り返し
処理内に、わずか２ステップの処理しか含まない。すな
わち、（ステップ１）：前回立案した計画にもとづき、計画内
容を変化させ、今回、新たに計画を立案し、変化させた
部分に着眼して、該変化によって生じた、前回と今回の
目的関数の差分値である、目的関数差分値を定める。

【００１４】（ステップ２）：上記ステップにおいて得
られた目的関数差分値を、予め定められている値と比較
し、前回計画が優れている場合、すなわち、前記目的関
数差分値が前記予め定められている値以内でない時に
は、ステップ１に戻る。

【００１５】今回計画が優れている場合、すなわち、前
記目的関数差分値が前記予め定められている値以内の場
合には、前回計画を今回計画に置き換える処理を行う。

【００１６】以上の２つのステップを、最適化を図る対
象の要素数をｎとすると、最適解を得ようとする場合に
は、ｎ³回、最適解に十分近い準最適解を得ようとする
場合は、Ｃ×ｎ²（回）（例えば、Ｃ＝４０）処理を繰
り返せばよい。

【００１７】（ステップ１）は、目的関数の種類、およ
び、新計画の立案方法によって、その処理の回数が定ま
るが、差分値に着眼することで、最適化を図る対象の要
素数ｎに依存しないようになる。

【００１８】（ステップ２）においては、繰り返し処理
の初期段階では、比較的、新計画への置き換え処理が多
いが、最適解の近傍エリアに到達してからは、置き換え
処理の回数は極めて少なくなる。計画の更新回数は、ｎ
に依存はするが、ｎ²よりはるかに小さいため、前記繰
り返し回数ｎ³、あるいは、ｃｎ²に比べ無視し得ること
になる。

【００１９】（ステップ２）における、予め定めること
が必要な値は、（ステップ１）の再計画の方法と対応
し、計画立案回数の増加により、そのとり得る値の範囲
が小さくなる値とすれば良い。後述の実施例では、一様
でないマルコフ連鎖に従う値を採用する。

【００２０】なお、本発明の主要部は、前記２つのステ
ップを実行する手段と、計画立案に必要な定数を記憶す
る手段とを少なくとも有する簡単な構成により、様々な
分野での、計画立案の最適化を完全に達成できる点にあ
り、計画立案に必要な定数については、任意に選択可能
とする。

【００２１】（ステップ１）は、例えば、高級言語の１
種であるＣ言語を使用すると、１行程度で記述でき、
（ステップ２）にも、ほとんどの計画立案において、１
行程度で記述可能である。

【００２２】したがって、１回の検討は、コンピュータ
の機械語命令を使用しても、数ステップ程度で記載可能
であるので、従来の方法に比べ、格段の処理の高速化が
図れる。

【００２３】例えば、従来の方法では、１回の検討時に
ｎ³個のステップを含んでいるため、これをｎ³回繰り返
すと、合計でｎ⁶個の処理ステップを要す。

【００２４】例えば、前記文献では、最適化、すなわ
ち、最小化または最大化を図る項目を表す目的関数Ｅ
（ｉ）を、合計距離とし、その最小化を図るためにＥ
（ｉ）を次のように定義している。

【００２５】Ｅ（ｉ）＝ΣΣΣｄab・Ｖbc（i）・（Ｖbc-1（ｉ）＋Ｖ
bc+1（ｉ））（第一のΣは、ａ＝１からｎまでの総和、第二のΣは、
ｂ＝１からｎまでの総和、第三のΣは、ｃ＝１からｎま
での総和を表す）ここで、ｄｉｊは、地点ｉとｊの距
離、Ｖｉｊは，地点ｉをｊ番目に訪れる確率を表す。

【００２６】この式を実行するには、少なくともｎ³回
の計算が必要である。厳密には、前記文献の記載例で
は、ｎ⁴の項が存在するが、余りに処理時間を要するの
で、以下の説明では、従来例をｎ³回の計算が必要とし
て説明する。

【００２７】一方、本発明は、１回の立案時、ｎを要素
に含まないので、ｎ³回これを繰り返しても、わずかＣ
×ｎ³回（Ｃは、１回の立案に必要なステップ数≒１０
程度）で完了する。

【００２８】１秒間に１０⁹回の命令実行が可能（１０
００「ＭＩＰＳ」）なコンピュータを使用して、ｎ＝１
０００の最適化問題を解法しようとすると、従来方法で
の処理時間Ｔｏｌｄは少なくとも、Ｔｏｌｄ＝（ｎ³×ｎ³）／（１０００（MIPS））＝（１０００）⁶／１０⁹ ＝１０¹⁸／１０⁹＝１０⁹（秒）≒３２（年間）要するのに対し（最初のｎ³は、１回の再計画に必要な
処理数、さらに、次のｎ³は、繰返しの回数を示す)、本
発明での処理時間Ｔｎｅｗは高々、Ｔｎｅｗ＝（Ｃ×ｎ³）／（１０００（MIPS））＝（１０×（１０００）³）／１０⁹ ＝１０¹⁰／１０⁹＝１０（秒）であるから、１／１０⁸に処理時間が短縮され、処理の
高速化が達成されることになる。

【００２９】これは、高速化の達成と同時に、処理許容
時間が定められている場合には、同一時間で解法し得る
問題の大きさが飛躍的に大きくなることを示している。

【００３０】例えば、許容時間を１００００秒（≒３時
間）とすると、従来方法での解法可能な最適化の対象の
数をｎｏｌｄとすると、ｎｏｌｄ＝⁶√（１００００×１０⁹）＝⁶√（１０¹³）＜１４８（⁶√は、６乗根を表
す）であるのに対し、本発明で解法可能な最適化の対象数ｎ
ｎｅｗは、ｎｎｅｗ＝³√（１００００×１０⁹／１０）＝³√（１０¹²）＝１０⁴ （³√は、３乗根を表
す）である。すなわち、１００００秒以内に、１００００個
の要素を有する最適化問題が解法できることになる。

【００３１】

【実施例】次に、本発明の実施例について図面を参照し
て詳細に説明する。

【００３２】図１に、本発明にかかる計画立案装置（以
下、「最適化装置」と称することが多い）の構成例を示
す。

【００３３】本装置は、最適化手段１と、設定手段２
と、記憶手段３とを有して構成される。

【００３４】設定手段２は、与えた計画対象となる問題
を受け付ける機能、計画立案に必要なパラメータを示す
定数等を受け付ける機能等を少なくとも有する手段であ
り、例えば、キーボード、マウス等により実現できる。

【００３５】最適化手段１は、最適な計画を立案する手
段であり、与えた計画対象となる問題において最小また
は最大とする項目を表現する目的関数を作成し、該目的
関数の値を、最大または最小にするため、以下のステッ
プ１、２の処理を少なくとも行う手段であり、例えば、
ＣＰＵ、ＲＯＭ、ＲＡＭ等の電子デバイスにて実現でき
る。

【００３６】ステップ１としては、前回立案した計画に
もとづき、計画内容を変化させ、今回、新たに計画を立
案し、変化させた部分に着眼して、該変化によって生じ
た、前回と今回の目的関数の差分値である、目的関数差
分値を定める。

【００３７】さらに、ステップ２としては、上記ステッ
プにおいて得られた目的関数差分値を、予め定められて
いる値と比較し、前回計画が優れている場合、すなわ
ち、前記目的関数差分値が前記予め定められている値以
内でない時には、ステップ１に戻る。

【００３８】今回計画が優れている場合、すなわち、前
記目的関数差分値が前記予め定められている値以内の場
合には、前回計画を今回計画に置き換える処理を行う。

【００３９】次に、記憶手段３は、設定手段２を介して
与えられた問題、最適化のために使用する定数等を少な
くとも記憶する手段であり、例えばＲＡＭにて実現され
る。

【００４０】なお、図１には図示しないが、液晶、ＥＬ
ディスプレイ、ＣＲＴ等の表示手段を最適化手段に接続
し、設定手段を介して記憶手段に格納された計画対象問
題、必要な定数、最適化手段による処理結果等を表示す
る構成にするのが好ましい。

【００４１】次に、図２に、最適化手段１の処理手順を
示す。

【００４２】本手段は、目的関数差分値を計算するステ
ップＡと、今回の計画と前回の計画を、前記目的関数差
分値および前記記憶手段３に格納されている定数値とを
比較して、計画を更新するか否かを判断するステップＢ
と、今回計画が優れている場合に（すなわち、前記目的
関数差分値が、予め定められた値の範囲内であると
き）、最適解候補を更新するステップＣと、上記をＣ×
ｎ²回（例えばＣ＝４）、または、ｎ³回繰り返すよう
に、繰り返しポインタｉを更新するステップＤを実行す
る機能を有している。

【００４３】本発明の動作の詳細を示すため、図３以下
を参照して説明する。

【００４４】図３は、いわゆる「巡回セールスマン問
題」を計画問題例としたもので、前記手段２を介して与
えられた問題が、設定された状態を示している（このよ
うな状態は、例えば、表示手段に表示させる構成にして
おけば良い）。

【００４５】さて、本問題は、地点「０：●」を出発
し、地点「１」から「１０」までを１回だけ訪問して、
再度地点「●」に戻る経路のうちで、例えば、距離が最
も短くなるものを決定する問題である。

【００４６】ここでは、目的関数を距離の総和とし、最
適化の目的は距離を最も短くすることとしたが、目的関
数は、全箇所を訪問するのに要する所要時間の総和であ
っても、自動車等の訪問に使用する手段が消費するエネ
ルギーの総和であってもよいことは言うまでもない。

【００４７】さて、設定された訪問順をベクトルＸで表
現すると、Ｘ＝（１，２，３，４，５，６，７，８，９，１０）と
なる。

【００４８】また、各地点の間の距離は、予め定まって
いるものとする。

【００４９】ここでは、記憶装置３の中に、地点ｆから
地点ｔ（ｆ，ｔは、０から１０の数）までの距離マトリ
ックスＤ（ｆ，ｔ）（図３参照）が格納されている。

【００５０】図４は、本発明の第１の主たる工夫点であ
って、図２に示すステップＡの処理を説明したものであ
る。

【００５１】計画立案の基本的コンセプトは、与えられ
た計画Ｘの要素の並びを少し変化させてみることであ
る。ここでは、これを「摂動」と称している。

【００５２】すなわち、例えば、ベクトルＸを構成する
要素のｊ＝３番目と、ｋ＝８番目の範囲に含まれる要素
の並びを逆転させるわけである。この時ｊとｋはｊ＜ｋおよび１≦ｊ，ｋ≦１０なる条件を満足し、かつ、各々上記範囲内で一様分布す
る乱数である。

【００５３】この操作により、新たな計画Ｙは、Ｙ＝（１，２，８，７，６，５，４，３，９，１０）となる。

【００５４】次に、ある計画Ａの目的関数をＦ（Ａ）と
すると、ここでは合計距離であるから、以下での計算の
都合上、地点「●」を「１１」とすると、Ｆ（Ｘ）＝ΣＤm→m+1 （Σは、ｍ＝１から１０までの総和をとる）＝Ｄ_1→2＋Ｄ_2→3＋Ｄ_3→4＋Ｄ_4→5＋Ｄ_5→6＋Ｄ_6→7＋Ｄ_7→8＋Ｄ_8→9＋Ｄ_9→10＋Ｄ_10→11 ＝１７＋２３＋２７＋４１＋３４＋４５＋４３＋１２＋２２＋２４＝２８８となり、同様に、Ｆ（Ｙ）＝Ｄ_1→2＋Ｄ_2→8＋Ｄ_8→7＋Ｄ_7→6＋Ｄ_6→5＋Ｄ_5→4＋Ｄ_4→3 ＋Ｄ_3→9＋Ｄ_9→10＋Ｄ_10→11 ＝１７＋４５＋４３＋４５＋３４＋４１＋２７＋２７＋２２＋２４＝３２５となる。

【００５５】図４をみてもＹの方が直感的に長いことが
分かる。ここでＸとＹの目的関数差分値ΔＦｘｙを、 ΔＦｘｙ＝Ｆ（Ｙ）−Ｆ（Ｘ）と定義すると、 ΔＦｘｙ＝３２５−２８８＝３７となる。

【００５６】図５は、本発明において見出した目的関数
値の推移の有する特有な性質を示したものである。図５
上図は、横軸に立案回数ｉ毎に定まる計画順ベクトルＸ
（ｉ）、縦軸に、その目的関数値を定義したものであ
る。

【００５７】計画順ベクトルの並びを、少しずつ変化さ
せ、その時の目的関数値を比較しながら、適正に、最適
解に近い計画順ベクトルに置きかえて行く。

【００５８】この場合、図に示すように、例えば、Ｘ
（ｉ）の様な極点（本実施例では、極小点）になる場合
でも、次のベクトルに移行し、十分な立案を行なった後
に、最適解ベクトルＸｏｐｔに達することがわかる。

【００５９】したがって、この様に、毎回新しい計画Ｘ
i+1を作成し、その目的関数値Ｆ（Ｘi+1）を演算し、前
回の計画Ｘｉの目的関数値Ｆ（Ｘi）と比較して、より
小さい、あるいは、大きなものを最適計画候補としてい
く処理を行えば良いのであるが、この方法であると、計
画対象数であるｎが大きくなった場合に、新しい計画を
作成し、目的関数値を計算するのに膨大な時間を要する
ことになる。

【００６０】そこで、本発明では、このような課題を解
決するために、立案毎に新しい計画を作成することを不
要とする性質を計画問題の有するから性質から見出し
た。

【００６１】図５下図は、横軸に計画順ベクトルＸiを
とり、縦軸に、その目的関数Ｆ（Ｘi）のＸiに対する微
分値ΔＦ（Ｘi）をとって表現したものである。

【００６２】すなわち、 ΔＦ（Ｘi）＝ｄＦ（Ｘi）／ｄＸi＝Ｆ（Ｘi+1）−Ｆ
（Ｘi）である。

【００６３】これは、立案回数毎の目的関数差分値を表
しており、新しい計画「Ｘi+1」の目的関数値が前回の
計画における目的関数値より小さくなる場合には、負と
なり、そうでない場合は、ゼロ、または、正となる。

【００６４】その推移は、図に示される通り、Ｆ（Ｘ
i）と対応するが、波形はゼロを中心とした、減衰振動
（すなわち、振幅が小さくなりながら周期も変化してい
く波形）に類似した波形になる。

【００６５】厳密な実験によると、一般的な計画問題に
おいては、問題の内容に関わらず、このような形とな
り、Ｘiを時刻と考えた場合の振幅の減衰度合は、例え
ば、Ｃ／ｌｏｇ（ｉ＋２）（本実施例では、Ｃ＝１
００）の相似形になることがわかった。

【００６６】これは、ΔＦが正になった場合、つまり、
新しい計画の目的関数値が前回の計画より悪くなった時
でも（すなわち、最小化問題の場合には増加した場合：
最小化問題の場合には減少した場合）、Ｃ／ｌｏｇ（ｉ
＋２）より小さな場合には、新しい計画を最適解候補に
置き換えてゆくことにより、十分大きなｉに対応する順
ベクトルＸｉでは、必ず最適解に達することを示してい
る。

【００６７】この性質は、最適化の処理性能の向上に極
めて大きな貢献を行なう。何故ならば、立案のくり返し
毎に、新しい計画を全て作成し、該新計画に対する目的
関数値を演算する必要がなく、単に、少し計画を変化さ
せ（すなわち、要素並びの一部を変化させ）、かかる変
化させた部分のみについて、検討すればよいわけであ
る。これにより、最適化の対象である数ｎに依存せず
に、目的関数値がどのように推移するかの検討が可能と
なり、計画問題の解決を高速に実現できる。

【００６８】このことを、以下具体例を参照して説明す
る。

【００６９】最適化の第１の工夫は、ΔＦｘｙの演算方
法にある。図４に示す例においては、Ｆ（Ｘ）＝Σ
（Ｄmx）（Σは、mx＝１から１０までの総和を表し、
文字Ｘは、計画Ｘに関することを表す）Ｆ（Ｙ）＝Σ（Ｄmy）（Σは、my＝１から１０までの
総和を表し、文字Ｙは、計画Ｙに関することを表す）の
全てを計算したが、図５に示した様に、最適化のために
は(距離の総和を最小にするためには)、多くの冗長な処
理を含んでいる。

【００７０】何故ならば、最適化を行うのに必要なの
は、目的関数値ではなく、目的関数差分値であるからで
ある。

【００７１】図４において、本発明による操作を行なっ
た場合、ある２点の評価に可逆性（順番が変わっても、
ある２点間の関係が不変、例えば、→、でも→
でも距離は同じであること等をいう）がある場合には、
高々２か所の変更が行なわれているだけであり、しかも
これは、最適化対象数ｎに依存していない。

【００７２】図４で説明すると、ＸからＹを生成する場
合に変更されたのは、ＸのＤ_2→3とＤ_8→9を取り除いた
点と、Ｄ_2→8とＤ_3→9が加わった点のみである。これを
数式で表すと、 ΔＦｘｙ＝Ｆ（Ｙ）−Ｆ（Ｘ）＝（Ｄ_1→2＋Ｄ_2→8＋Ｄ_8→7＋Ｄ_7→6＋Ｄ_6→5＋Ｄ_5→4＋Ｄ_4→3 ＋Ｄ_3→9＋Ｄ_9→10＋Ｄ_10→11） −（Ｄ_1→2＋Ｄ_2→3＋Ｄ_3→4＋Ｄ_4→5＋Ｄ_5→6＋Ｄ_6→7＋Ｄ_7→8 ＋Ｄ_8→9＋Ｄ_9→10＋Ｄ_10→11）ここで本問題では任意の地点ｊ，ｋに対してＤj→k＝Ｄk→j が成立するので ΔＦｘｙ＝（Ｄ_2→8＋Ｄ_3→9）−（Ｄ_2→3＋Ｄ_8→9）となる。操作ポインターｊ，ｋを用いて一般化すると、 ΔＦｘｙ＝（Ｄ(j-1)→k＋Ｄj→(k+1)）−（Ｄ(j-1)→j
＋Ｄk→(k+1)）…（式１）となり、最適化対象数ｎに依存せず、３回の加算、減算
を行なうのみでよいことがわかる。

【００７３】今まで順ベクトルの並びの変更すなわち、
主として、数学的順列問題について述べてきたが、同様
な考え方で、数学的組合せ問題も解決することが可能で
ある。図６は、記憶手段３内の、予め格納されている
定数例を示したものである。

【００７４】テーブルｊとＫはそれぞれｉ＝１からｉ＝
ｎ³まで次の様な性質を有する整数値がセットされてい
る。

【００７５】 (１)Ｊ（ｉ）＜Ｋ（ｉ）（以下、ｉは立案回数） (２)１≦Ｊ（ｉ），Ｋ（ｉ）≦ｎ (３)上記(２)レンジ内でギ一様分布する。

【００７６】式１を、再度、書き直すと、 ΔＦ（ｉ）＝（Ｄ(J(i)-1)→K(i)＋ＤJ(i)→(K(i)+1)）− （Ｄ(J(i)-1)→j(i)＋ＤK(i)→(K(i)+1)）……（式２）ここで、本実施例での値Ｊ（ｉ）＝３Ｋ（ｉ）＝８を（式２）に代入すると、 ΔＦ（ｉ）＝（Ｄ2→8＋Ｄ3→9） −（Ｄ2→3＋Ｄ8→9）＝（４５＋２７）−（２３＋１２）＝７２−３５＝３７＝Ｆ（Ｙ）−Ｆ（Ｘ）となり、ｎに依存せずに、目的関数差分値が求まること
がわかる。

【００７７】また、図６に示される、Ｃは、目的関数値
差ΔＦｘｙと比較するための定数であり、ｉ＝１からｎ
³まで、例えば、次の様な値が、記憶手段が備えるテー
ブル上に設定されている。Ｃ（ｉ）＝（Ｃ₁・ａ（ｉ））／ｌｏｇ（ｉ＋２）但し、ｌｏｇは、自然対数、ａ（ｉ）は、「０．０」か
ら「１．０」に分布する一様乱数である。

【００７８】すなわち、立案回数ｉの増加により、分布
するレンジが小さくなる様な値であればよい。Ｃ₁は、
ΔＦにより容易に定めることができる。Ｃ₁＝１００と
した場合のＣ（ｉ）の分布エリアの推移を図６に示す。
斜線内にＣ（ｉ）は存在することになる（これは、一様
でないマルコフ連鎖になっている）。

【００７９】図７は、本装置が正しく動作することを検
証するための説明図である。

【００８０】予め最適解が判明している問題（与えられ
た全ての点を一度、訪問する計画問題、いわゆる「セー
ルスマン巡回問題」）を、ランダムな訪問の順番を初期
値とし、最適解に到達するか否かを検証した様子を示し
ている。

【００８１】円周上に地点を配置すれば、その最適解は
明らかに円であり、ｎ＝８、１６、３２においては、図
の様に最適解に達していることがわかる。

【００８２】図８は、図７の問題を本発明にかかる手段
を使用して解決する場合、最適化の対象となる対象数ｎ
を変えるとともに、初期状態Ｘを変えて実験し、最適解
に到達した回数の度数分布を作成したものである。ｎ＝
５００までにおいて、全てｎ³回以下で、最適解に達し
ており、４×ｎ²回においても、ほとんど最適解に達し
ていることがわかる。

【００８３】これは、少なくともｎ³回の検討を行なえ
ば最適解に達し、４×ｎ²回程度検討を行なえば、実用
上有効な準最適解が得られることを示していることにほ
かならない。

【００８４】図９は、１０００（ＭＩＰＳ）の処理性能
を有するコンピューターで最適化を行なった場合、最適
解に到達するまでの保証時間を縦軸に、横軸に最適化対
象をとったものである。

【００８５】全ての可能ルートを調べる最も原始的な
「列挙法」では、ｎ＝１０で既に３６秒を要し、実用的
なｎの最大値は１２程度であることがわかる。

【００８６】前述のニューロやカオス等を応用した方法
では、ｎ＝５０〜１００が、実用上限界である。

【００８７】これに対し、本発明では、立案毎の処理が
ｎに依存していないため、例えば、６０秒でｎ＝８４４
の最適化を可能としている。

【００８８】図１０は、図９のレンジを縦／横軸ともに
拡張し、本発明による処理能力の限界を検討したもので
ある。４分間程度の処理時間を許容した場合、ｎ＝１３
００程度までの要素数を有する計画立案問題に対する最
適解が得られることが分かる。

【００８９】次に、実際の応用例において重要となる、
準最適解を得るための処理時間を検討するため、さら
に、縦／横軸を拡張した（図１１参照）。

【００９０】この結果、約１時間強（４０００秒）で、
ｎ＝１０００００という、従来、全く期待もされなかっ
た、膨大な計画を解決している。これは、例えば、電子
基板上のパターン設計等の極めて難しい計画問題にも、
本発明が適用しうる性能を有していることを示す。

【００９１】図１２に、極めてニーズの多い、製造業に
おける生産計画の最適化に、本発明を応用した例を示
す。

【００９２】本実施例では、製造設備Ａにて６種類の作
業〜を効率良く行なう計画例である。設備が１台の
為作業の移行時は冶具の交換、清掃、ＮＣ加工パラメー
タの設定等の、図に示す段取り時間が必要となる。

【００９３】この計画は、作業を巡回地点に、段取り時
間を巡回地点間の距離に対応させ、目的関数として総作
業時間をとり、これを最小とすることを考える。

【００９４】そうすると、前述の「巡回セールスマン問
題」に、１対１に対応することとなる。これはさらに、
総段取り時間を最小にすることと等価であり、初期計画
Ｘの総段取り時間が７７（分）であったものが、本発明
による装置によって、３９（分）となり、５０（％）
も、総作業時間が短縮される。

【００９５】実際の大規模な工場に配置される設備数
は、数百、作業数は、１ヶ月で数千〜数万におよぶが、
図１１によれば、極めて短時間に、現実的な最適解が得
られることを示しており、製造業の規模が大きくなれば
なるほど、本発明は、その効果を発揮するものと考えら
れる。

【００９６】図１３は、本発明のハードウェア構成の実
施例である。

【００９７】本実施例は、計画問題解決の一連の処理の
流れを制御する制御プロセッサ４と、目的関数差分値を
演算する加算プロセッサ５と、目的関数値差分と定数値
を比較し、必要な時に、新計画を最適計画候補とする判
定プロセッサ６と、前記Ｊ，Ｋ，Ｃ等の定数を格納する
記憶レジスタ７を有して構成され、これらの構成要素
は、バスライン８にて接続されている。

【００９８】制御プロセッサ４、加算プロセッサ５、お
よび判定プロセッサ６は、例えば、ＣＰＵ、ＲＯＭ、Ｒ
ＡＭ、ＲＯＭに内蔵されるプログラム等により実現され
る。

【００９９】記憶レジスタ７は、例えば、ＲＡＭにより
実現される。

【０１００】したがって、従来の直列処理型プロセッサ
に、サブＣＰＵ（処理装置）として組込み構成し、膨大
な組合せ数、または、順列数の中から最適値を与える、
順列の順番、組合せパターンを求める計画問題の解決が
必要な場合に、サブＣＰＵを起動し、問題解決処理を行
なわせる様にする。これにより、冗長性が取り除かれ
（前記サブＣＰＵは、最適値を求める処理以外の処理を
極力行わない構成とする）、処理性能が向上する。

【０１０１】

【発明の効果】本発明によれば、簡単な構成により、与
えられた問題に対する最適な計画立案を高速に行う手段
を提供できる効果がある。

【図面の簡単な説明】

【図１】最適化装置の構成例を示す図である。

【図２】最適化手段の処理手順の説明図である。

【図３】最適化情報の設定例を示す図である。

【図４】計画案の摂動と評価の説明図である。

【図５】目的関数差分値の推移例を示す図である。

【図６】設定される計画最適化のための定数例である。

【図７】本装置の動作例の説明図である。

【図８】最適化に要した検討回数の度数分布表である。

【図９】最適化を行う対象数と処理時間とを表すグラフ
である。

【図１０】最適化を行う対象数と処理時間とを表すグラ
フである。

【図１１】最適化を行う対象数と処理時間とを表すグラ
フである。

【図１２】生産計画システムへの応用例である。

【図１３】本発明にかかる装置のハードウェア実現例を
示す。

【符号の説明】

１…最適化手段、２…設定手段、３…記憶手段、４…制
御プロセッサ、５…加算プロセッサ、６…判定プロセッ
サ、７…記憶レジスタ

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成６年７月２７日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】図面の簡単な説明

【補正方法】変更

【補正内容】

【図面の簡単な説明】

【図１】最適化装置の構成例を示す図である。

【図２】最適化手段の処理手順の説明図である。

【図３】最適化情報の設定例を示す図である。

【図４】計画案の摂動と評価の説明図である。

【図５】目的関数差分値の推移例を示す図である。

【図６】設定される計画最適化のための定数例である。

【図７】本装置の動作例の説明図である。

【図８】最適化に要した検討回数の度数分布の図表であ
る。

【図１２】生産計画システムへの応用例である。

【符号の説明】１…最適化手段、２…設定手段、３…記憶手段、４…制
御プロセッサ、５…加算プロセッサ、６…判定プロセッ
サ、７…記憶レジスタ

フロントページの続き (72)発明者 ▲吉▼田英雄茨城県日立市幸町三丁目２番１号日立エンジニアリング株式会社内 (72)発明者寺田保広茨城県日立市大みか町五丁目２番１号株式会社日立製作所大みか工場内 (72)発明者阿部登茨城県日立市大みか町五丁目２番１号株式会社日立製作所大みか工場内 (72)発明者佐藤良幸茨城県日立市大みか町五丁目２番１号株式会社日立製作所大みか工場内 (72)発明者八尋正和茨城県日立市大みか町五丁目２番１号株式会社日立製作所大みか工場内 (72)発明者大槻朱美東京都千代田区神田駿河台四丁目６番地株式会社日立製作所システム事業部内

Claims

【特許請求の範囲】

【請求項１】与えられた計画対象となる問題、および、
該問題の解決に必要な変数の値を少なくとも受け付ける
設定手段と、前記計画対象となる問題において、最小化
または最大化を図る項目を表す目的関数を作成し、作成
された目的関数の値を最小化または最大化する計画を立
案する最適化手段と、計画立案に必要な変数を少なくと
も記憶する記憶手段とを具備し、前記最適化手段は、前回立案された計画と、新たに立案
された計画における前記目的関数の差分値を計算する演
算手段と、前記目的関数の差分値と前記記憶手段内に、
予め設定された変数の値とを比較して、前記目的関数の
差分値が、前記予め設定された変数の値より小さい場合
に、前回立案した計画を、今回立案した計画に置き換
え、最適計画候補とする再計画手段を備えることを特徴
とする計画立案装置。
【請求項２】請求項１において、さらに、表示手段を備
え、前記表示手段は、最適化手段での計画立案結果を表示す
ることを特徴とする計画立案装置。
【請求項３】請求項１において、前記記憶手段は、前記予め設定された変数をＣ（ｉ）、今回計画立案時
に、前回計画を構成する要素並びのＪ（ｉ）番目からＫ
（ｉ）番目の要素を逆順に並び変えるときに使用する変
数を、Ｊ（ｉ）、Ｋ（ｉ）（ｉは、立案回数）として、Ｊ（ｉ）＜Ｋ（ｉ）となり、かつ、１≦Ｊ（ｉ）≦ｎ、
１≦Ｋ（ｉ）≦ｎ（ｎは、計画対象を構成する要素数）
なる範囲で変化し、該範囲内で、一様分布するＪ（ｉ）
およびＫ（ｉ）を格納し、さらに、ｉが増加すると、とり得る値の範囲が小さくなる変数Ｃ
（ｉ）も格納することを特徴とする計画立案装置。
【請求項４】請求項３において、前記変数Ｃ（ｉ）は、計画立案毎に生成される、０．０≦ａ(ｉ)≦１．０なる
範囲で、一様に分布する実数ａ(ｉ)と、予め定められた
定数Ｃ₁および定数Ｃ₂により、Ｃ（ｉ）＝（Ｃ₁・ａ(ｉ)）／ｌｏｇ（ｉ＋Ｃ₂））
（Ｌｏｇは、自然対数）としたことを特徴とする計画立
案装置。
【請求項５】与えられた計画候補の内容を変更して、計
画において最小化または最大化を図る項目を表す目的関
数の値を、最小あるいは最大にする計画立案方法であっ
て、計画が順列問題である場合には、順列の要素並びの一部
を変更し、また、計画が組合わせ問題である場合には、
選択する要素の少なくとも１つを、変更して選択し、前記変更によって生ずる目的関数値の差分を演算し、そ
の差分値が、計画変更のたびに徐々に減少する値範囲内
に一様に分布する値より小さい場合には、変更後の計画
を最適計画候補とすることを特徴とする計画立案方法。