(57)【特許請求の範囲】
【請求項１】
データを格納する第１の格納手段と、
複数の調整関数を組み込み関数として格納する第２の格納手段と、
問題を記述する状態ｑの初期値と、前記状態ｑのコスト関数U(q)を定義するためのパラメタと、調整パラメタβ、Ｑ、およびαと、調整関数の選択条件のデータを、前記第１の格納手段に入力する入力手段と、
前記第１の格納手段に入力されたデータと、該第１の格納手段に格納された前記調整関数の選択条件のデータに基づき前記第２の格納手段に格納された前記複数の調整関数の中から選択された調整関数ΘU 、ΘK 、ΘZ 、Ａ、およびＢを用いて、前記コスト関数U(q)の最小値に対応する状態qminを求める決定論的ダイナミクスである、
ｄｑi ／ｄｔ
＝−（β／ｎ）τK （ｐ）ｐi
＋（β／ｎ）［Ｂi （ｘ）∂ΘZ （ζ，ｗ）／∂ｗ−∂Ｂi （ｘ）／∂ｗ］
（ｉ＝１，．．．，ｎ）                                                （１）
ｄｐi ／ｄｔ
＝（β／ｎ）τU（ｑ）Ｆi （ｑ）
−（β／ｎ）［（１／Ｑ）∂ΘZ （ζ，ｗ）／∂ζ ＋α∂ΘZ （ζ，ｗ）／∂ｗ］ｐi
（ｉ＝１，．．．，ｎ）                                                （２）
ｄζ／ｄｔ
＝［−（β／ｎ）τK （ｐ）Ｋ（ｐ）−β］／Ｑ
＋（β／ｎ）［Ａ（ｘ）∂ΘZ （ζ，ｗ）／∂ｗ−∂Ａ（ｘ）／∂ｗ］      （３）
ｄｗ／ｄｔ
＝［−（β／ｎ）τK （ｐ）Ｋ（ｐ）−β］α
−（β／ｎ）［Ａ（ｘ）∂ΘZ （ζ，ｗ）／∂ζ−∂Ａ（ｘ）／∂ζ］
＋（β／ｎ）Σ［τU （ｑ）Ｆi （ｑ）Ｂi （ｘ）＋∂Ｂi （ｘ）／∂ｑi］  （４）
但し、
0003821266.tif 000006
ｑ≡（ｑ1 ，．．．，ｑn）∈Ｄ⊂Ｒn
ｐ≡（ｐ1 ，．．．，ｐn）∈Ｒn
ｘ≡（ｑ，ｐ，ζ，ｗ）∈Γ≡Ｄ×Ｒn ×Ｒ2
Ｕ：Ｒn ⊃Ｄ→Ｒ
Ｆi （ｑ）≡−∂Ｕ（ｑ）／∂ｑi
τU （ｑ）≡［ｄΘU（ｕ）／ｄｕ］u=U(q)
Ｋ（ｐ）≡Σｐi2
τK （ｐ）≡−２［ｄΘK（ｋ）／ｄｋ］k=K(p)
ΘU ：Ｒ⊃ＤU≡Ｕ（Ｄ）→Ｒ
ΘK ：［０，∞）→Ｒ
ΘZ ：Ｒ2→Ｒ
Ａ：Γ→Ｒ
Ｂ＝（Ｂ1 ，．．．，Ｂn ）：Γ→Ｒn
から成る常微分方程式（１）乃至（４）の右辺の値を計算し、前記第１の格納手段に格納する方程式計算手段と、
前記第１の格納手段に格納された常微分方程式（１）乃至（４）の右辺の値を用いて数値積分を実行する数値積分実行手段と、
前記数値積分実行手段にて得られた状態ｑの分布を離散幅毎に集計して、状態ｑの複数の値の実現度数を計算する度数計算手段と、
前記度数計算手段の計算結果に基づいて前記状態qminの１つ以上の候補を求め、前記第１の格納手段に格納する候補選択手段と、
前記第１の格納手段に格納された候補を、可視化して出力する出力手段と
を備えることを特徴とする処理装置。
【請求項２】
前記第１の格納手段に格納された１つ以上の候補の各状態から前記コスト関数U(q)の値が良くなる方向に変化させて、U(q)の値が最も小さくなる状態を求める最適状態探索手段を更に備えることを特徴とする請求項１記載の処理装置。
【請求項３】
データを格納する第１の格納手段と、
複数の調整関数を組み込み関数として格納する第２の格納手段と、
問題を記述する状態ｑの初期値と、前記状態ｑのコスト関数U(q)を定義するためのパラメタと、調整パラメタβ、Ｑ、およびαと、調整関数の選択条件のデータを、前記第１の格納手段に入力する入力手段と、
前記第１の格納手段に入力されたデータと、該第１の格納手段に格納された前記調整関数の選択条件のデータに基づき前記第２の格納手段に格納された前記複数の調整関数の中から選択された調整関数ΘU 、ΘK 、ΘZ 、Ａ、およびＢを用いて、前記コスト関数U(q)の最小値に対応する状態qminを求める決定論的ダイナミクスである、
ｄｑi ／ｄｔ
＝−（β／ｎ）τK （ｐ）ｐi
＋（β／ｎ）［Ｂi （ｘ）∂ΘZ （ζ，ｗ）／∂ｗ−∂Ｂi （ｘ）／∂ｗ］
（ｉ＝１，．．．，ｎ）                                                （１）
ｄｐi ／ｄｔ
＝（β／ｎ）τU（ｑ）Ｆi （ｑ）
−（β／ｎ）［（１／Ｑ）∂ΘZ （ζ，ｗ）／∂ζ ＋α∂ΘZ （ζ，ｗ）／∂ｗ］ｐi
（ｉ＝１，．．．，ｎ）                                                （２）
ｄζ／ｄｔ
＝［−（β／ｎ）τK （ｐ）Ｋ（ｐ）−β］／Ｑ
＋（β／ｎ）［Ａ（ｘ）∂ΘZ （ζ，ｗ）／∂ｗ−∂Ａ（ｘ）／∂ｗ］      （３）
ｄｗ／ｄｔ
＝［−（β／ｎ）τK （ｐ）Ｋ（ｐ）−β］α
−（β／ｎ）［Ａ（ｘ）∂ΘZ （ζ，ｗ）／∂ζ−∂Ａ（ｘ）／∂ζ］
＋（β／ｎ）Σ［τU （ｑ）Ｆi （ｑ）Ｂi （ｘ）＋∂Ｂi （ｘ）／∂ｑi］  （４）
但し、
0003821266.tif 000007
ｑ≡（ｑ1 ，．．．，ｑn）∈Ｄ⊂Ｒn
ｐ≡（ｐ1 ，．．．，ｐn）∈Ｒn
ｘ≡（ｑ，ｐ，ζ，ｗ）∈Γ≡Ｄ×Ｒn ×Ｒ2
Ｕ：Ｒn ⊃Ｄ→Ｒ
Ｆi （ｑ）≡−∂Ｕ（ｑ）／∂ｑi
τU （ｑ）≡［ｄΘU（ｕ）／ｄｕ］u=U(q)
Ｋ（ｐ）≡Σｐi2
τK （ｐ）≡−２［ｄΘK（ｋ）／ｄｋ］k=K(p)
ΘU ：Ｒ⊃ＤU≡Ｕ（Ｄ）→Ｒ
ΘK ：［０，∞）→Ｒ
ΘZ ：Ｒ2→Ｒ
Ａ：Γ→Ｒ
Ｂ＝（Ｂ1 ，．．．，Ｂn ）：Γ→Ｒn
から成る常微分方程式（１）乃至（４）の右辺の値を計算し、前記第１の格納手段に格納する方程式計算手段と、
前記第１の格納手段に格納された常微分方程式（１）乃至（４）の右辺の値を用いて数値積分を実行する数値積分実行手段と、
前記数値積分実行手段にて得られた状態ｑの分布を離散幅毎に集計して、状態ｑの複数の値の実現度数を計算する度数計算手段と、
前記度数計算手段の計算結果に基づいて前記状態qminの１つ以上の候補を求め、前記第１の格納手段に格納する候補選択手段と、
前記第１の格納手段に格納された候補を、可視化して出力する出力手段として、
コンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、最適構造問題、最適配置問題、最適経路問題等のような最適化問題において、コスト関数の最適値を探索する処理装置に関する。
【０００２】
【従来の技術】
近年、様々な産業分野において、最適化問題を解決することが要求されている。最適化問題とは、与えられたコスト関数が最大、最小、あるいは局所最大、局所最小となるような状態を探索する問題である。コスト関数の符号を変えることにより、最大あるいは局所最大を求める問題は、最小あるいは局所最小を求める問題に置き換えられる。以下では、主として、最小あるいは局所最小を求める問題として最適化問題を説明する。
【０００３】
例えば、ＣＡＤ（computer-aided design ）においては、建築物、構造物等の強度を高め、外力に対する安定性を高めるために、強度や安定性の評価値がコスト関数として用いられ、その最適値に対応する構造が求められる。また、材料設計においては、材料の原子・分子レベルのエネルギーがコスト関数として用いられ、最低エネルギー状態に対応する構造が求められる。さらに、より一般的なパラメタフィッティング問題においても、コストを最適にするようなパラメタの組が求められる。
【０００４】
このような最適化問題を解決するための従来の方法としては、降下法（Descent Method）と確率的方法の２つの方向がある。降下法の代表的アルゴリズムである最急降下法（Steepest Descent Method ）は、与えられた状態からコスト関数の値が下がる方向を計算し、その方向に状態を変化させて、コスト関数の最小値の１つの候補を求める方法である。これにより、コスト関数の極小値が得られる。
【０００５】
また、確率的方法の代表的アルゴリズムには、ランダム法、シミュレーティド・アニーリング法（Simulated Annealing Method，ＳＡ法）、および遺伝アルゴリズム法（Genetic Algorithm Method，ＧＡ法）がある。
【０００６】
ランダム法は、状態をランダムに選び、コスト関数の値が小さい状態をピックアップしていく方法である。ＳＡ法は、次の状態を定めるためにメトロポリス（metropolis）のアルゴリズムを用いる。このアルゴリズムによれば、次の状態のコストが下がればその状態が採用され、コストが上がればある確率をもってその状態が採用される。その確率は温度パラメタに依存しており、最初は温度を高めに設定してメトロポリスのアルゴリズムを用い、徐々に、温度を低くしていく方法が取られている。
【０００７】
ＧＡ法は、生物進化の機構を模倣した最適化方法である。この方法では、状態を染色体と呼ばれる文字列で表現し、染色体の集団に選択、交差、突然変異等の遺伝子操作を行って、各遺伝子を最適化していく。
【０００８】
【発明が解決しようとする課題】
しかしながら、上述した従来の方法には次のような問題がある。
最急降下法は、探索途中にコスト関数が極小となる状態があれば、それにトラップされてしまい、その状態から抜け出せなくなる。したがって、必ずしもコスト関数が最小の状態を見つけられるとは限らない。ランダム法は、状態数が有限かつ少ない時は厳密解を見つけられる可能性があるが、状態数が多くなれば良く機能しない。
【０００９】
また、ＳＡ法では、メトロポリスのアルゴリズムにより低コスト値の状態の実現確率を高めるために温度を低くする必要があるが、そうすると探索のための状態の変化が緩慢になる。このため、一旦、極小状態にトラップされると、長時間待たなければ、その状態から抜け出せない。そこで、最初は温度を高めに設定し、徐々に低くしていく方法が効果的と考えられるが、この温度スケジューリングの方法には決定的あるいは汎用的なものはなく、どのようにして温度スケジュールを設定するかが問題となる。
【００１０】
また、ＧＡ法は、近傍探索能力に欠けるため、近くにより最適な状態があってもそれを見つけられずに、ニアミスを起こしやすい。また、最適な状態が見つけられるという理論的裏付けに乏しい。
【００１１】
本発明の課題は、コスト関数の局所的な形に依らずに、その最適値を効率的に探索する処理装置を提供することである。
【００１２】
【課題を解決するための手段】
図１は、本発明の処理装置の原理図である。図１の処理装置は、入力手段１、候補探索手段２、および出力手段３を備える。
【００１３】
入力手段１は、問題を記述する状態と、状態のコストを与えるコスト関数の情報を入力する。また、候補探索手段２は、コスト関数の最適値により近いコスト値の状態の実現確率を高めるような決定論的ダイナミクスを用いて、最適状態の１つ以上の候補を求める。そして、出力手段３は、得られた候補を出力する。
【００１４】
候補探索手段２は、入力手段１により入力された情報を用いて、状態を表す変数の集合とダイナミクスの計算アルゴリズムを決定し、それらに従って計算を行う。そして、コスト関数の最適値に対応する最適状態の候補となる変数値の集合を求める。出力手段３は、候補探索手段２が求めた候補を、探索結果として出力する。
【００１５】
ダイナミクスとは、方程式等に基づく計算により生成された座標（点）の時間的発展に対応する。状態を座標変数とする状態空間におけるダイナミクスを求めることにより、初期位置の近傍探索から出発して、適当な条件下で与えられた状態空間全体を探索することができ、コスト関数の極小値等にトラップされることがない。したがって、コスト関数の局所的な形に依らずに計算を行うことができる。
【００１６】
また、コスト関数の最適値により近いコスト値の状態の実現確率を高めるようなダイナミクスを用いることで、系の温度を下げることなく最適値に近いコスト値の周辺を探索することができる。したがって、従来の確率的方法のように、最適値により近いコスト値の状態の実現確率を高めるために状態の変化を遅らせる必要がなく、処理が効率化される。
【００１７】
このように、本発明のポイントは、コスト関数の最適値により近いコスト値の状態の実現確率を高めるような決定論的ダイナミクスを用いて、最適状態を探索することである。
【００１８】
また、図１の処理装置は、処理の精度をより高めるために、格納手段４と最適状態探索手段５をさらに備える。格納手段４は、候補探索手段２が求めた１つ以上の候補を格納し、最適状態探索手段５は、それらの候補の各状態からコスト関数の値が良くなる方向に変化させて、最適状態に近い状態を求める。
【００１９】
最適状態探索手段５が行う計算は、例えば、降下法の計算に対応し、候補の状態よりさらに最適値に近いコスト値の状態を求めることができる。こうして得られた状態の中で最も良いコスト値を持つ状態を選択すれば、精度の高い解が得られる。
【００２０】
例えば、図１の入力手段１は、後述する図２の入力部１０および図１７の入力装置５３に対応し、図１の候補探索手段２は、図２のコスト関数値計算部１２、方程式計算部１４、数値積分実行部１５、度数計算部１７、および候補選択部１８に対応する。また、例えば、図１の出力手段３は、図２の出力部１９および図１７の出力装置５４に対応し、図１の格納手段４は、図１７のメモリ５２に対応し、図１の最適状態探索手段５は、図２の降下部２０に対応する。
【００２１】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本実施形態においては、ｎ個の実変数によって表される状態ｑ＝（ｑ1 ，．．．，ｑn ）によって定まるコスト関数Ｕ（ｑ）の最小値とそのときの状態ｑmin （もしくは、より最小に近い値とそのときの状態）を探索する。ただし、Ｕ（ｑ）は微分可能な関数とする。Ｕ（ｑ）の符号を変えることにより、最小値を探索する問題を最大値を探索する問題に置き換えることもできる。ここでは、以下のような性質を持つ計算を実現することが目標となる。
（Ａ）近傍探索能力を有する。
（Ｂ）探索途中に極小状態があってもそれにトラップされない。
（Ｃ）パラメタや調整関数を設定することによって、低コスト値の状態の実現確率を高めることができる。ただし、ＳＡ法のように、探索が緩慢になるようなことは回避する。
（Ｄ）充分長時間計算すると、各状態の実現確率がどうなるか、どのような条件が必要かも含めて、最適な状態が見つけられるという理論的裏付けがある。
【００２２】
このような目標を実現するため、まず、決定論的ダイナミクスを用いてｑmin のいくつかの候補を求める。次に、それぞれの候補の状態からなんらかの降下法を用いてコスト値を降下させ、ｑmin もしくはより最小に近い状態を求める。
【００２３】
ここでは、ｑmin の候補を求める決定論的ダイナミクスの一例として、次のような常微分方程式を用いる。
0003821266.tif 000002
ただし、ここでは、以下のような定義を用いている。
【００２４】
【数１】
0003821266.tif 000003
【００２５】
ｑ≡（ｑ1 ，．．．，ｑn ）∈Ｄ⊂Ｒn                           （５）
ｐ≡（ｐ1 ，．．．，ｐn ）∈Ｒn                               （６）
ｘ≡（ｑ，ｐ，ζ，ｗ）∈Γ≡Ｄ×Ｒn ×Ｒ2                     （７）
Ｕ：Ｒn ⊃Ｄ→Ｒ                                              （８）
Ｆi （ｑ）≡−∂Ｕ（ｑ）／∂ｑi                               （９）
τU （ｑ）≡［ｄΘU （ｕ）／ｄｕ］u=U(q)                    （１０）
Ｋ（ｐ）≡Σｐi 2                                           （１１）
τK （ｐ）≡−２［ｄΘK （ｋ）／ｄｋ］k=K(p)                （１２）
ΘU ：Ｒ⊃ＤU ≡Ｕ（Ｄ）→Ｒ                                （１３）
ΘK ：［０，∞）→Ｒ                                        （１４）
ΘZ ：Ｒ2 →Ｒ                                              （１５）
Ａ：Γ→Ｒ                                                  （１６）
Ｂ＝（Ｂ1 ，．．．，Ｂn ）：Γ→Ｒn                         （１７）
（１）〜（４）の常微分方程式はニュートン方程式を拡張したものに相当し、ｑi を座標とすると、ｐi は運動量に相当する。また、ここでは、拡張変数としてζとｗが導入されている。ΘU 、ΘK 、ΘZ 、Ａ、およびＢは調整関数として導入された滑らかな関数であり、β、Ｑ、およびαは調整パラメタとして導入されている。βは設定温度の役割を果たす。これらの調整関数および調整パラメタは、任意に設定することができる。このとき、（１）〜（４）式は、次のような特徴を有する。
【００２６】
（２）式の左辺は運動量の時間変化を表し、右辺第１項のＦi （ｑ）はコスト関数の微分に負の符号を付加して得られる力を表している。言い換えれば、状態の変化の方向（加速度の方向）には、コスト関数の微分と逆の符号の成分が含まれている。したがって、コスト関数が増加する場合には、それとは逆の方向に状態が変化し、コスト関数が減少する場合には、その方向に状態が変化する。このように、（２）式は、コスト関数が極小となる状態があれば、その方向に近づいていく性質を示しており、上述した（Ａ）の性質を有している。
【００２７】
また、（２）式の右辺第２項はｐi に比例する摩擦力を表し、ΘZ （ζ，ｗ）により記述されるｐi の係数は摩擦係数に相当する。（３）式の左辺はζの時間変化を表し、右辺第１項の−（β／ｎ）τK （ｐ）Ｋ（ｐ）は系の温度を表し、Ｋ（ｐ）は系の運動エネルギーを表す。
【００２８】
ここで、∂ΘZ （ζ，ｗ）／∂ζがζの増加関数であるものとし、系の温度が設定温度βを超えてζの時間変化が正になったとすると、（２）式の右辺の摩擦力が大きくなり、運動量が減少して、系の温度が低下する。また、逆に、系の温度が設定温度βを下回りζの時間変化が負になったとすると、（２）式の右辺の摩擦力が小さくなり、運動量が増加して、系の温度が上昇する。（２）式の摩擦力は、正負両方の値をとることができる。
【００２９】
したがって、（２）、（３）式は、系の温度を設定温度βに近づけようとする性質を示している。実際に、適当な条件下では、系の温度の時間平均がβになることが証明できる。そこで、βを高く設定する等の調整を行って系に熱振動を与えてやれば、極小状態から脱出させることが可能になる。このように、（２）、（３）式は、上述した（Ｂ）の性質を有している。
【００３０】
また、通常の場合は成立すると考えられるいくつかの条件が成り立てば、長時間（理論的には無限時間）経過後にＵ（ｑ）がｕ１からｕ２の範囲の値をとる確率は、（２）式のτU （ｑ）を生成する調整関数ΘU を用いて表すことができる。より具体的には、系がエルゴード性を持てば、付加的な数学的条件の下で、この確率は次式により与えられることが証明できる。
【００３１】
【数２】
0003821266.tif 000004
【００３２】
Ｓ≡｛ｑ∈Ｄ｜ｕ１≦Ｕ（ｑ）≦ｕ２｝×Ｒn+2                 （１９）
ｋU （ｕ）＝ｅｘｐ［−ΘU （ｕ）］                          （２０）
ここで、（１８）式の左辺は時間ｔに関する定積分の極限値を表し、右辺はコスト関数Ｕ（ｑ）の値ｕに関する定積分を表す。左辺のＴt （ｘ）は座標ｘの時間的発展（フロー）を表し、χS （ｘ）は、ｘが集合Ｓの要素であるとき１となり、そうでないとき０となる関数である。
【００３３】
また、右辺のΩはコスト関数の状態数の密度を表す関数であり、ｋU （ｕ）Ω（ｕ）は、系のコスト値Ｕ（ｑ）がｕとなる確率密度を表す。（１８）式の確率は、Ｕ（ｑ）がｕ１からｕ２の範囲の値をとる状態に滞在する時間の割合を表し、その範囲への軌道の訪問頻度と呼ぶこともできる。
【００３４】
（１８）式は、適当な条件下で、系が次式の密度関数ρ（ｘ）により与えられる不変測度を持つという事実から証明される。
0003821266.tif 000005
このρ（ｘ）はｘ＝（ｑ，ｐ，ζ，ｗ）の状態が実現される確率密度を表している。
【００３５】
上述した（Ｃ）の性質を実現するには、（１８）式のｋU Ωがｕの最小値付近で極大となるように、ｋU を設定すればよい。密度関数Ωは、通常、ｕの増加とともに急激に増加するので、ｋU をｕの増加とともに急激に減少する関数等として適当に設定すれば、ｋU Ωのピークをｕの最小値に近づけることができる。ｋU を急減関数にするには、ΘU を急増関数にすればよい。これにより、長時間後には、低コスト値の状態の訪問頻度を高めることができる。
【００３６】
関数ｋU は、系の進行速度（即ち、探索速度）を決定する設定温度βとは独立に設定することができるため、低コスト値の状態の実現確率を高めながら、探索速度の低下を回避できることが理論的に保証される。したがって、従来のＳＡ法のように、低コスト値の状態の実現確率を高めるために温度を低くした結果、探索速度が低下するという問題が生じない。このように、（２）式は、上述した（Ｃ）および（Ｄ）の性質を有している。
【００３７】
言い換えれば、（１８）式の確率を実現するような不変測度を持つ常微分方程式の一例が、（１）〜（４）式である。（１）〜（４）式は、調整パラメタと調整関数を適当に設定することで、与えられた個々の問題に柔軟に対応できるという利点を持っている。しかしながら、（１８）式の確率を実現するようなダイナミクスは（１）〜（４）式に限られず、他の定式化も可能である。例えば、導入される拡張変数は、必ずしも２つ（ζとｗ）である必要はない。
【００３８】
次に、（１）〜（４）式を用いてコスト関数の最適値を探索する処理装置について説明する。この処理装置は、例えば、コンピュータを用いて構成され、（１）〜（４）式を適当な数値積分法で解いていき、ｑmin の候補を求める。ただし、一般には、最適解への収束は保証されないので、適当な終了条件を設定して、探索を終了する。次に、得られたｑmin の候補のそれぞれを初期値として、適当な降下法によりコスト値を降下させ、より最適な状態を求める。
【００３９】
図２は、このような処理装置の構成図である。図２の処理装置は、入力部１０、コスト定義部１１、コスト関数値計算部１２、関数作成部１３、方程式計算部１４、数値積分実行部１５、チェック部１６、度数計算部１７、候補選択部１８、出力部１９、および降下部２０を備える。
【００４０】
入力部１０は、入力データ２１を入力し、コスト定義部１１は、コスト関数およびその偏導関数を設定する。コスト関数値計算部１２は、コスト定義部１１により設定された関数の時刻ｔにおける値を計算し、関数作成部１３は、必要に応じて新たな調整関数を作成する。方程式計算部１４は、コスト関数値計算部１２および関数作成部１３からの情報を用いて、時刻ｔにおける（１）〜（４）式の計算を行う。数値積分実行部１５は、方程式計算部１４の計算結果を用いて数値積分を実行し、チェック部１６は、積分結果をチェックする。
【００４１】
度数計算部１７は、コスト関数Ｕ、運動エネルギーＫ（温度）、注目する座標値ｑobs 等の実現度数（頻度）を計算し、候補選択部１８は、それらの度数に基づいて最適状態ｑmin の候補を選択する。出力部１９は、積分結果および度数計算部１７の計算結果を出力データ２２としてファイルに出力する。
【００４２】
数値積分実行部１５は、終了条件が成立するかどうかをチェックし、それが成立しなければ、時刻ｔをΔｔだけ進めて、次の積分を実行する。そして、終了条件が成立すれば、積分を終了する。
【００４３】
その後、出力データ２２がディスプレイ画面上で可視化されるとともに、得られた複数の最適状態候補２３が降下部２０に渡される。降下部２０は、入力データ２１と最適状態候補２３に基づいて、降下法によりｑmin を探索し、得られた状態を最適状態２４として出力する。この最適状態２４も、ディスプレイ画面上で可視化することができる。
【００４４】
図２において、数値積分実行部１５、チェック部１６、度数計算部１７、候補選択部１８、出力部１９、および降下部２０は、与えられた問題に依存しない汎用的な機能を持つ。
【００４５】
図３は、入力データ２１を示している。この入力データにおいて、パラメタ３１は、コスト関数を定義する際に必要なパラメタであり、自由度３２は、与えられた問題を記述する状態変数の数ｎである。
【００４６】
また、シミュレーション条件３３には、ステップ数、時間刻み幅、終了条件、出力指定パラメタ等が含まれる。ステップ数は、数値積分および降下法の反復回数を表し、時間刻み幅は数値積分の間隔Δｔを表し、終了条件は数値積分および降下法の終了条件を表す。出力指定パラメタは、出力データ２２の出力間隔等を指定するパラメタである。終了条件としては、例えば、次のようなものが用いられる。
（ａ）計算時間または処理ステップ数があらかじめ決められた値に到達したとき、計算を終了する。
（ｂ）あらかじめ決められたＵ（ｑ）の目標値を下回るコスト値の状態が所定の数以上得られたとき、計算を終了する。
【００４７】
また、度数計算パラメタ３４には、離散幅、変域パラメタ等が含まれる。離散幅は、与えられた変数や関数の値の実現度数を計算する際の値の間隔を表し、変域パラメタは、変数や関数の値の計算範囲を表す。
【００４８】
また、調整パラメタ３５は、上述のパラメタβ、Ｑ、およびαの値であり、調整関数の選択条件３６は、上述の関数ΘU 、ΘK 、ΘZ 、Ａ、およびＢを設定するための条件である。処理装置には、あらかじめ様々な調整関数が組み込み関数として格納されており、それらの識別番号を選択条件として入力すれば、指定された組み込み関数が自動的に設定される。また、新規関数の定義を選択条件として入力すれば、新たな調整関数が設定される。
【００４９】
また、境界条件３７は、コスト関数の定義域Ｄに関する境界条件を表す。例えば、トーラスが境界条件として指定されると、処理装置は、領域Ｄがトーラス状に連続しているものとみなして、数値積分を行う。
【００５０】
また、図４は、出力データ２２を示している。この出力データにおいて、状態変数値の時間変化４１は、変数ｑの変化を表し、その他の変数値の時間変化４２は、ｑ以外の変数の変化を表す。最適コスト値の時間変化４３は、探索により得られたコスト値の最適値の変化を表す。
【００５１】
また、コスト関数値の度数４４は、離散幅毎に集計されたコスト値の実現度数を表し、系の温度の度数４５は、離散幅毎に集計された温度の実現度数を表し、注目する座標の度数４６は、離散幅毎に集計された座標値ｑobs の実現度数を表す。
【００５２】
次に、図５から図１２までを参照しながら、図２の処理装置の処理についてより詳細に説明する。
図５は、入力部１０の処理のフローチャートである。入力部１０は、まず、入力データ２１を入力し（ステップＳ１１）、状態変数やその他の変数の初期値を定義する処理を行い（ステップＳ１２）、度数計算の準備を行う（ステップＳ１３）。
【００５３】
初期値の定義において、自動生成を行うかどうかをユーザに問い合せ（ステップＳ１４）、自動生成の指示があれば、所定の方法で各変数の初期値を生成して（ステップＳ１５）、処理を終了する。自動生成の指示がなければ、所定の外部ファイルから初期値を読み込んで各変数に設定し（ステップＳ１６）、処理を終了する。
【００５４】
図６は、コスト定義部１１の処理のフローチャートである。コスト定義部１１は、まず、パラメタ３１に基づいてコスト関数およびその偏導関数を定義し（ステップＳ２１）、コスト関数を改変するかどうかをユーザに問い合せる（ステップＳ２２）。改変の指示があれば、コスト関数を改変し（ステップＳ２３）、処理を終了する。改変の指示がなければ、コスト関数を改変せずに、処理を終了する。コスト関数の改変の例としては、定義されたコスト関数の比較的大きな値の部分を探索対象から除外するような処理が考えられる。
【００５５】
図７は、コスト関数値計算部１２の処理のフローチャートである。コスト関数値計算部１２は、コスト定義部１１からコスト関数を受け取り、時刻ｔにおいて更新された状態ｑに基づいて、コスト関数値を計算する（ステップＳ３１）。そして、コスト関数の偏導関数値を計算して（ステップＳ３２）、処理を終了する。
【００５６】
図８は、関数作成部１３の処理のフローチャートである。関数作成部１３は、まず、調整関数の選択条件３６に基づいて、調整関数の新規作成を行うかどうかを決定する（ステップＳ４１）。選択条件３６が新規作成を指示していれば、入力された情報に基づいて調整関数を作成し（ステップＳ４２）、処理を終了する。新規作成の指示がなければ、調整関数を作成せずに、処理を終了する。
【００５７】
図９は、方程式計算部１４の処理のフローチャートである。方程式計算部１４は、まず、（１）〜（４）式の計算に必要な温度等の変数を計算し（ステップＳ５１）、その結果を用いて（１）〜（４）式の右辺を計算する（ステップＳ５２）。そして、境界条件３７に関する処理を行い（ステップＳ５３）、処理を終了する。
【００５８】
図１０は、数値積分実行部１５およびチェック部１６の処理のフローチャートである。数値積分実行部１５は、Runge-Kutta 法、Gear法、またはその他の方法により数値積分を行い（ステップＳ６１）、チェック部１６は、数値エラーが発生したかどうかをチェックする（ステップＳ６２）。
【００５９】
数値エラーが発生しなければ、度数計算部１７に後続する処理を依頼し（ステップＳ６３）、処理を終了する。数値エラーが発生すれば、終了条件が成立するかどうかに関わらず数値積分を終了させ（ステップＳ６４）、処理を終了する。
【００６０】
図１１は、候補選択部１８の処理のフローチャートである。候補選択部１８は、まず、度数計算部１７の計算結果に基づいて、これまでに得られた状態の中から最適状態の複数の候補を選択する（ステップＳ７１）。そして、それらの状態をｑmin の候補として記憶し、対応するコスト値をＵmin の候補として記憶して（ステップＳ７２）、処理を終了する。
【００６１】
図１２は、降下部２０の処理のフローチャートである。降下部２０は、まず、与えられたｑmin の候補を初期状態として、所定の降下法の計算ステップを進め（ステップＳ８１）、コスト関数値を計算する（ステップＳ８２）。次に、計算結果をファイルに出力し（ステップＳ８３）、終了条件が成立するかどうかをチェックする（ステップＳ８４）。
【００６２】
終了条件が成立しなければ、ステップＳ８１以降の処理を繰り返し、終了条件が成立すれば、降下法を終了する（ステップＳ８５）。そして、出力データをディスプレイ画面上で可視化し（ステップＳ８６）、得られた最適状態を出力して（ステップＳ８７）、処理を終了する。
【００６３】
次に、ｎ＝２とおき、コスト関数Ｕ（ｑ）を７つの２次元ガウス（Gauss ）関数の和で表して、４次のRunge-Kutta 法により数値積分のシミュレーションを行った結果を説明する。探索領域Ｄは２次元トーラスとし、調整関数は次のように設定した。
Ａ＝０
Ｂ＝０
ΘU （ｕ）＝（１／２Ｔ′）ｕ2 
Θk （ｋ）＝（１／２Ｔ）ｋ
ΘZ （ζ，ｗ）＝（１／２Ｔ）（Ｑζ2 ＋α′ｗ2 ）
ここで、Ｔ′、Ｔ、およびα′は、調整関数を決定するパラメタであり、次のように設定した。
Ｔ′＝１０．０
Ｔ＝１０．０
α′＝０．０
また、調整パラメタは次のように設定した。
β＝ｎＴ＝２０．０
Ｑ＝０．００１
α＝０．０
また、初期条件は、ｑ1 ＝ｑ2 ＝ｐ2 ＝ζ＝ｗ＝０．０、ｐ1 ＝Ｔ0.5 とおき、数値積分のステップ数は１０００００００とし、数値積分の時間刻み幅は０．０００１とした。すべてのステップにおいてデータを出力するとデータ量が膨大になることがあるので、ここでは、データの出力間隔を１０００ステップ毎とした。
【００６４】
このとき、Ｕ（ｑ）は図１３に示すような関数で与えられ、複数の極小値を含んでいる。これらの極小値のうち最も小さい値が、コスト関数の最適値となる。指定されたステップ数の数値積分を行った後、図１４に示すような座標値の分布が得られ、座標値の実現度数は図１５のようになった。図１５では、図１３の極小値に対応する位置において、度数が大きくなっていることが分かる。また、コスト関数値の実現度数は図１６のようになった。図１６における度数のピークは、図１３の極小値に対応している。
【００６５】
以上説明した実施形態においては、コスト関数を実ｎ変数の微分可能な関数としているが、離散型の変数により記述される問題においても、適当なコスト関数を定めれば、同様の探索を行うことができる。離散型の最適化問題としては、例えば、最適配置問題、最適経路問題、最適ネットワーク問題、最適フロー問題、最適効率問題等がある。
【００６６】
最適配置問題は、都市設計における施設の配置等を最適化する問題であり、最適経路問題は、車両のナビゲーションや電気回路等において経路を最適化する問題である。
【００６７】
また、最適ネットワーク問題は、ガスや水道の配管、電気配線、通信ネットワーク等を最適化する問題であり、最適フロー問題は、道路上の交通フローやネットワーク上のデータフロー等を最適化する問題であり、最適効率問題は、科学、工学、経済、ビジネス等の分野で効率を最適化する問題である。
【００６８】
ところで、上述した図２の処理装置は、図１７に示すような情報処理装置（コンピュータ）を用いて構成することができる。図１７の情報処理装置は、ＣＰＵ（中央処理装置）５１、メモリ５２、入力装置５３、出力装置５４、外部記憶装置５５、媒体駆動装置５６、およびネットワーク接続装置５７を備え、それらはバス５８により互いに接続されている。
【００６９】
メモリ５２は、例えば、ＲＯＭ（read only memory）、ＲＡＭ（random access memory）等を含み、処理に用いられるプログラムとデータを格納する。ＣＰＵ５１は、メモリ５２を利用してプログラムを実行することにより、必要な処理を行う。
【００７０】
図２の入力部１０、コスト定義部１１、コスト関数値計算部１２、関数作成部１３、方程式計算部１４、数値積分実行部１５、チェック部１６、度数計算部１７、候補選択部１８、出力部１９、および降下部２０は、メモリ５２の特定のプログラムコードセグメントに格納されたソフトウェアコンポーネントに対応し、１つ以上のインストラクションからなるプログラムにより実現される。
【００７１】
入力装置５３は、例えば、キーボード、ポインティングデバイス、タッチパネル等であり、ユーザからの指示や情報の入力に用いられる。出力装置５４は、例えば、ディスプレイ、プリンタ、スピーカ等であり、ユーザへの問い合わせや処理結果の出力に用いられる。
【００７２】
外部記憶装置５５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク（magneto-optical disk）装置等である。この外部記憶装置５５に、上述のプログラムとデータを保存しておき、必要に応じて、それらをメモリ５２にロードして使用することもできる。また、外部記憶装置５５は、コスト関数、調整関数等を格納するデータベースとしても用いられる。
【００７３】
媒体駆動装置５６は、可搬記録媒体５９を駆動し、その記録内容にアクセスする。可搬記録媒体５９としては、メモリカード、フロッピーディスク、ＣＤ−ＲＯＭ（compact disk read only memory ）、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。この可搬記録媒体５９に上述のプログラムとデータを格納しておき、必要に応じて、それらをメモリ５２にロードして使用することもできる。
【００７４】
ネットワーク接続装置５７は、ＬＡＮ（local area network）等の任意のネットワーク（回線）を介して外部の装置と通信し、通信に伴うデータ変換を行う。また、必要に応じて、上述のプログラムとデータを外部の装置から受け取り、それらをメモリ５２にロードして使用することもできる。
【００７５】
図１８は、図１７の情報処理装置にプログラムとデータを供給することのできるコンピュータ読み取り可能な記録媒体を示している。可搬記録媒体５９や外部のデータベース６０に保存されたプログラムとデータは、メモリ５２にロードされる。そして、ＣＰＵ５１は、そのデータを用いてそのプログラムを実行し、必要な処理を行う。
【００７６】
【発明の効果】
本発明によれば、コスト関数の最適値に対応する状態を探索する処理において、近傍探索能力と極小状態へのトラップを回避する能力を用いて、最適状態の候補を次々に探索することができる。これらの２つの能力は、必ずしも、力関数の性質や温度制御に依らなくとも、調整関数を適当に設定することにより実現するすることもできる。
【００７７】
また、探索速度を制御する温度パラメタの値に直接依存しない形で、低コスト値の状態の実現確率を高めることができる。このため、温度パラメタの値を、数値計算誤差による不備が発生しない程度にまで高くすることができ、処理速度の向上が期待できる。
【図面の簡単な説明】
【図１】本発明の処理装置の原理図である。
【図２】処理装置の構成図である。
【図３】入力データを示す図である。
【図４】出力データを示す図である。
【図５】入力部の処理のフローチャートである。
【図６】コスト定義部の処理のフローチャートである。
【図７】コスト関数値計算部の処理のフローチャートである。
【図８】関数作成部の処理のフローチャートである。
【図９】方程式計算部の処理のフローチャートである。
【図１０】数値積分実行部およびチェック部の処理のフローチャートである。
【図１１】候補選択部の処理のフローチャートである。
【図１２】降下部の処理のフローチャートである。
【図１３】コスト関数を示す図である。
【図１４】座標値の分布を示す図である。
【図１５】座標値の実現度数を示す図である。
【図１６】コスト関数値の実現度数を示す図である。
【図１７】情報処理装置の構成図である。
【図１８】記録媒体を示す図である。
【符号の説明】
１  入力手段
２  候補探索手段
３  出力手段
４  格納手段
５  最適状態探索手段
１０  入力部
１１  コスト定義部
１２  コスト関数値計算部
１３  関数作成部
１４  方程式計算部
１５  数値積分実行部
１６  チェック部
１７  度数計算部
１８  候補選択部
１９  出力部
２０  降下部
２１、３１、３２、３３、３４、３５、３６、３７  入力データ
２２、４１、４２、４３、４４、４５、４６  出力データ
２３  最適状態候補
２４  最適状態
５１  ＣＰＵ
５２  メモリ
５３  入力装置
５４  出力装置
５５  外部記憶装置
５６  媒体駆動装置
５７  ネットワーク接続装置
５８  バス
５９  可搬記録媒体
６０  データベース
【図１】
0003821266.tif 000008
【図２】
0003821266.tif 000009
【図３】
0003821266.tif 000010
【図４】
0003821266.tif 000011
【図５】
0003821266.tif 000012
【図６】
0003821266.tif 000013
【図７】
0003821266.tif 000014
【図８】
0003821266.tif 000015
【図９】
0003821266.tif 000016
【図１０】
0003821266.tif 000017
【図１１】
0003821266.tif 000018
【図１２】
0003821266.tif 000019
【図１３】
0003821266.tif 000020
【図１４】
0003821266.tif 000021
【図１５】
0003821266.tif 000022
【図１６】
0003821266.tif 000023
【図１７】
0003821266.tif 000024
【図１８】
0003821266.tif 000025