JPH0561848A

JPH0561848A - 最適アルゴリズムの選定及び実行のための装置及び方法

Info

Publication number: JPH0561848A
Application number: JP3221526A
Authority: JP
Inventors: Hironari Masui; 裕也増井; Ikuo Matsuba; 育雄松葉
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1991-09-02
Filing date: 1991-09-02
Publication date: 1993-03-12

Abstract

(57)【要約】【目的】与えられた多峰性多変数関数に最適な極小・極
大点探索アルゴリズムの選定と実行、及び同期的変数更
新処理の収束性の改善。【構成】予め、関数を特徴付ける量の統計量の値が異な
る複数の多峰性多変数関数のそれぞれに、極小点又は極
大点の探索のための複数のアルゴリズムを適用して、そ
の結果についての対比データを作成し、記憶装置１０１
に格納しておく。ある多峰性多変数関数が与えられる
と、その関数に最適なアルゴリズムを、この関数を特徴
付ける量の統計量の値と前記対比データとに基づいて、
前記複数のアルゴリズムの中から選択する。全変数の同
期的更新に際して、更新の変化量をある割合で圧縮する
ことより、収束性を改善する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、多峰性多変数関数のコ
ンピュータ処理に関し、特に、この型の関数の極小点又
は極大点（それぞれ最小点と最大点を含む）を探索する
ための最適アルゴリズムの、コンピュータによる選定と
実行に関する。この型の関数のコンピュータ処理は、各
種の最適化問題の求解、各種の制御などに応用される。

【０００２】

【従来の技術】多峰性多変数関数の最小点の探索の代表
的な例は、ニューラルネットワークモデルを用いて最適
化問題を解く場合の、エネルギー最小化計算である。

【０００３】従来、ニュ−ラルネットワ−クのエネルギ
−最小化のためのアルゴリズムとしては、Biological C
ybernetics, Vol．５２,１９８５年，第１４１−１５２
頁，「"Neural" Computation of Decisions in Optimiz
ation Problems」（以後文献１という）に述べられてい
る方法、SCIENCE, Vol．２２０, No．４５９８,１９８
３年５月１３日，第６７１−６８０頁，「Optimization
by simulated annealing」（以後文献２という）に述
べられている方法、電子情報通信学会技術研究報告，９
０，２７４，１９９０年，第１−６頁，「平均場近似ア
ニ−リング法による最適化計算法」（以後文献３とい
う）に述べられている方法等があった。文献１に述べら
れている方法は、高速であるが、極小解にトラップされ
ると脱出不可能であり、文献２に述べられている方法
は、最小解への到達が可能であるが、計算時間が非常に
長く、文献３に述べられている方法は、短時間で最小解
の近似解が得られる。このように、これらの提案された
諸アルゴリズムは、それぞれの特徴を持っている。

【０００４】また、エネルギー最小化処理の過程で、各
ニューロンの状態を反復的に多数回更新することが必要
である。ニューロンの状態更新の基本的な方法は、同期
的方法と非同期的方法である。同期的方法は、全ニュー
ロンの状態を並行的に更新するものであり、計算時間は
短いが、ニューラルネットワークの状態が必ずしも常に
安定点に収束するとは限らない。他方、非同期的方法
は、ある一つのニューロンの状態を更新してから、この
ニューロンの更新された状態を前提として次のニューロ
ンの状態を更新するという、逐次的な方法であり、収束
は確実に生じるけれども、長時間を要する。折衷的な方
法として、村田健郎他著、１９８８年丸善発行、「工学
における数値シミュレ−ション」、第５７頁（以後文献
４という）に述べられている、チェッカ−ボ−ド法があ
る。この方法は、ニュ−ロンを格子点に割当てて、その
座標値の和によって偶数点と奇数点とに分類し、偶数点
だけの同期的更新と奇数点だけの同期的更新を交互に繰
り返すというものであり、比較的短時間での確実な収束
が期待できる。

【０００５】

【発明が解決しようとする課題】前述のように、従来提
案されている諸アルゴリズムは、それぞれの特徴を持っ
ているので、適用対象となる多峰性多変数関数の性質
（例えば、ニューラルネットワークの構成によって定ま
るような）に応じて、最適なアルゴリズムを選択するこ
とが望ましい。しかるに、これらのアルゴリズムの中か
ら、任意に与えられた多峰性多変数関数にとって最適な
（例えば、与えられたニューラルネットワークに対し
て、そのエネルギ−を最も小さくなしうるような）アル
ゴリズムを、予め定量的に判断して選定するための選択
基準は、未だ知られていない。

【０００６】また、変数の値（例えば、ニュ−ロンの状
態）の反復更新についても、前述のチェッカーボード法
は、一般的には計算時間の短縮と確実な収束が期待でき
るとはいえ、全変数（ニュ−ロン）を複数の群に分け
て、各群ごとの同期的更新を逐次的に行なわなければな
らないため、処理が複雑になり、ス−パ−コンピュ−タ
等でベクトル化して計算を行なう場合には、ベクトル化
率が低くなって、計算時間が長くなるという欠点があっ
た。

【０００７】本発明の第１の目的は、与えられた多峰性
多変数関数に最適な（例えば、ニュ−ラルネットワ−ク
に対して最もエネルギ−を小さくするような）極小点又
は極大点探索アルゴリズムを、複数のアルゴリズムの中
から自動的に選定し、更にはそれを実行することができ
る装置及び方法を、提供することにある。

【０００８】本発明の第２の目的は、群分けをせずに全
変数の値（例えば、全ニュ−ロンの状態）を一斉に同期
的に更新しても、確実な収束が期待できるような変数更
新方法を、提供することにある。

【０００９】

【課題を解決するための手段】本発明の基本的特徴の一
つは、多峰性多変数関数の特徴の指標として、関数を特
徴付ける量（例えば、ニューラルネットワークの構成）
自体ではなく、それらの統計量を採用し、諸アルゴリズ
ムを適用した結果がこのような統計量の変化によってど
のように変化するかを示すデータを、予め作成して保持
し、このデータを、最適アルゴリズムの選定の尺度とし
て参照するところにある。

【００１０】すなわち、本発明の最適アルゴリズム選定
装置は、関数を特徴付ける量の統計量の値を異にする複
数の多峰性多変数関数のそれぞれについての、複数の極
小点又は極大点探索アルゴリズムの適用結果の対比デー
タが格納されている記憶装置と、与えられた多峰性多変
数関数に最適なアルゴリズムを、この与えられた多峰性
多変数関数を特徴付ける量の統計量の値と前記対比デー
タとに基づいて、前記複数のアルゴリズムの中から選択
する、処理装置とを備える。この統計量としては、例え
ば、しきい値の平均と分散の少なくとも一方を用いるこ
とができる。

【００１１】ニューラルネットワークの場合には、この
関数はエネルギー関数であり、関数を特徴付ける量はシ
ナプスの結合荷重とニューロンのしきい値の少なくとも
一方であり、対比データは算出された最小エネルギーで
ある。非線形計画法の場合には、関数は非線形計画法に
おける評価関数であり、関数を特徴付ける量はこの評価
関数における係数の少なくとも一つであり、対比データ
は算出された最小関数値又は最大関数値である。また、
ニューラルネットワークからなる連想記憶の場合には、
関数はこの連想記憶の特性を表わす関数であり、関数の
特徴を表わす量は連想記憶の一群のキーパターンの相関
量であり、対比データは連想記憶の応答の正誤率を示す
データである。

【００１２】この装置における最適アルゴリズム選定方
法は、ニューラルネットワークと非線形計画法の場合に
は、与えられた多峰性多変数関数を特徴付ける量の統計
量の値を計算するステップと、前記対比データを参照し
て、この計算された統計量の値に最も近い統計量の値に
対して最小又は最大の関数値を与えるアルゴリズムを選
択するステップとを備える。また、連想記憶の場合に
は、与えられた一群のキーパターン中の諸パターン対間
の相関量の値の平均及び分散の少なくとも一方の値を計
算するステップと、前記対比データを参照して、前記計
算された値に最も近い同種の量の値に対して最も良い正
誤率を与えるアルゴリズムを選択するステップとを備え
る。これらの方法において、実質上同一の関数値又は正
誤率を与える複数のアルゴリズムが存在するときには、
それらの中から計算時間が最も短いものを選択すればよ
い。

【００１３】前記の最適アルゴリズム選定装置の記憶装
置に、更に、前記複数のアルゴリズムのそれぞれを実行
するためのプログラムを格納し、そして、処理装置に、
選択した最適アルゴリズムを実行するためのプログラム
を実行する機能を与えれば、最適アルゴリズム実行装置
が得られる。

【００１４】本発明のもう一つの基本的特徴は、選択さ
れたアルゴリズムの実行に際して、諸変数の値の更新に
おける変化量を、通常の方法によるよりも圧縮して、同
期的更新を行なうところにある。

【００１５】すなわち、本発明の変数値更新方法は、選
択されたアルゴリズムに従って仮の更新値を算出するス
テップと、前記仮の更新値と更新前の値の差を所定のパ
ラメータに従って圧縮して更新後の値を決定するステッ
プと、これらの両ステップを適用して全変数の値を同期
的に更新するステップを含む。このパラメータは、定数
でもよいし、あるいは、反復更新の回が進むにつれて一
定の方向に変更されてもよい。

【００１６】

【作用】本発明の最適アルゴリズム選定装置及び方法に
よれば、コンピュータが、与えられた多峰性多変数関数
を特徴付ける量の統計量の値を計算し、この計算された
統計量の値をキーとして、記憶装置に保持されている諸
アルゴリズムの性能対比データを参照して、与えられた
関数に最適なアルゴリズムを選定する。

【００１７】また、本発明の最適アルゴリズム実行装置
によれば、コンピュータが、前述のようにして選定した
最適アルゴリズムを、与えられた関数に適用して、解を
作成する。

【００１８】更に、本発明のアルゴリズム実行方法によ
れば、各変数の値の更新に際して、急激な値の変化を抑
制しつつ、全変数の値の同期的な更新を行なう。その結
果、高速でしかも確実な収束が期待できる。

【００１９】

【実施例】図１は、本発明による最適アルゴリズム選定
・実行装置の概要を示す。外部メモリ１０１には、複数
の最小化アルゴリズムを実行するための各プログラム
と、これらのアルゴリズムを構成の統計量が異なる種々
のニューラルネットワークに適用したときの優劣を表わ
す、アルゴリズム対比データとが、保持されている。与
えられたニュ−ラルネットワ−クの構造を表わすデータ
をキ−ボ−ド１０２により入力し、コンピュ−タ１０３
は、このニューラルネットワークの構成の統計量を算出
し、外部メモリ１０１に保持されているアルゴリズム対
比データを参照して、このニューラルネットワークに最
適なアルゴリズムを選定し、そして、選定されたアルゴ
リズムを適用して、このニュ−ラルネットワ−クのエネ
ルギ−最小化計算を実行し、得られた解をディスプレイ
１０４に表示する。

【００２０】アルゴリズム対比データは、前記の文献３
でも用いられているスピングラスモデルを試算の対象と
して用い、結合荷重としきい値の統計量が異なる種々の
スピングラスモデルに各アルゴリズムを適用して、得ら
れた最小エネルギーの値を、その場合の前記統計量と共
に、対比に便利な形式に編集したものである。与えられ
たニュ−ラルネットワ−クの同種の統計量を算出して、
それらの値をキーとしてアルゴリズム対比データを参照
することにより、このニューラルネットワークに最適な
アルゴリズムを選定することができる。また、選定され
たアルゴリズムの適用に際して、各ニューロンの状態
（出力値）の更新における変化量を適当に圧縮すること
により、同期的更新を行なうにもかかわらず、確実な収
束が期待できる。

【００２１】一般に、ニュ−ラルネットワ−クは、図２
に示す相互結合型ニュ−ラルネットワ−クで表わされ
る。複数のニューロン２０１が、それぞれ固有の結合荷
重を持つシナプス２０２によって相互接続されている。
各ニューロン２０１は、図３に示すように、しきい値と
出力関数３０４を有し、重み付き総入力３０３の値に応
じて出力信号３０５を決定する。出力関数は、本実施例
では、図４に示すような離散的に２値のみを取りうる階
段関数４０１ではなく、単調増加するアナログ値を取り
うる飽和型のシグモイド関数とした。これらニューロン
の協調的及び競合的な動作により、ネットワ−クのエネ
ルギ−は、最小値状態へ向かって収束して行く。なお、
エネルギ−関数は、Ｗ_ijをｉ番目のニューロンからｊ番
目のニュ−ロンへの結合荷重、ａ_iをｉ番目のニュ−ロ
ンのしきい値、Ｖ_iをｉ番目のニューロンの出力値、Ｎ
をニュ−ロンの総数としたとき、一般に次式で定義され
る。

【００２２】

【数１】

【００２３】まず、アルゴリズム対比データの作成手順
を説明する。一般に、相互結合型ニュ−ラルネットワ−
クのエネルギ−関数は、複雑なエネルギ−曲面を呈し、
多くの極小解を有する。そのため、エネルギ−が真に最
小となる最適解に達することは非常に困難であり、良質
な準最適解へ高速に到達するための様々なアルゴリズム
が提案されている。本実施例では、代表的なアルゴリズ
ムとして、文献１に記載されたホップフィ−ルドらの方
法（以後Ｈ法と略称する）、文献２に記載されたシミュ
レ−テッドアニ−リング法（以後ＳＡ法と略称する）、
並びに文献３に記載された平均場近似アニ−リング法
（以後ＭＦＡＡ法と略称する）と混合法を採用し、これ
らをスピングラスモデルに適用する。スピングラスモデ
ルでは、ニュ−ロン間の結合荷重と各ニュ−ロンのしき
い値が正又は負の値を取りうる正規乱数として与えら
れ、かつ、Ｗ_ij＝Ｗ_jiである。このとき、設定する正規
乱数の平均と分散を変えることにより、エネルギ−曲面
の形状が調節可能である。

【００２４】図５及び図６は、前記のモデルにおいて、
結合荷重の平均ＷA及び分散Ｗσ、並びにしきい値の平
均ａA及び分散ａσが変化したときの、前記４アルゴリ
ズムの性能の比較結果を示す。各アルゴリズムにおける
反復計算回数は、Ｈ法では１０００回、ＳＡ法とＭＦＡ
Ａ法では１００００回とし、混合法では、ＭＦＡＡ法で
１００回、その後のＳＡ法で１００００回とした。ニュ
ーロンの総数は５０個である。そして、１０種類の系列
を異にする正規乱数を初期状態として与え、各結果のエ
ネルギ−値の平均がプロットされている。これらのグラ
フにおいて、横軸（対数目盛）は変化せしめられた統計
量を示し、縦軸は、Ｈ法により得られた最小エネルギ−
値ＥHを基準として、その他のアルゴリズムで得られた
最小エネルギ−ＥのＥHに対する規格化誤差ＥＲ、すな
わち、ＥＲ＝（ＥH−Ｅ）／ＥHを示している。▽印はＳ
Ａ法、△印はＭＦＡＡ法、○印は混合法を、それぞれ表
わす。ＥＲ＝０％の横軸がＨ法による求解結果であり、
規格化誤差が正の大きな値になるほど、より最適解に近
い解が得られたことを示す。

【００２５】図５（Ａ）は、結合荷重の分散Ｗσのみを
変化させ、結合荷重の平均ＷA並びにしきい値の平均ａA
及び分散ａσを“０”に設定したときの、これら４種の
アルゴリズムの性能の比較結果を示す。横軸はＷσを示
す。まず、ＳＡ法に着目すると、これによる解は、常
に、４アルゴリズムの中で最も最適解から遠い。したが
って、このアルゴリズムは、現実的な反復回数の範囲で
は、有効性を充分に発揮することができそうもない。次
に、ＭＦＡＡ法は、Ｗσが２以下のときには、これらの
アルゴリズムの中で最良の解が得られている。しかしな
がら、Ｗσが３以上では混合法と順位が逆転し、Ｗσが
８以上ではＨ法と同等になり、このように、Ｗσの増加
に従って徐々に性能が劣化している。この原因は、ＭＦ
ＡＡ法は近似法であるため、Ｗσが大きくなってエネル
ギ−曲面が複雑になり、多くの極小点が生じるにつれ
て、近似化による誤差が大きくなるためであると、定性
的に理解できる。他方、混合法は、Ｗσが０．０７以下
ではＨ法より僅かに劣るが、しかし、Ｗσが０．０８以
上では安定して良好な解が得られている。これは、Ｗσ
が大きくなって極小解が増加したときに、単純な最急降
下法であるＨ法とは対照的に、極小解からの脱出が可能
な混合法の特質が発揮されるためである。

【００２６】次に、図５（Ｂ）は、Ｗσ＝０．１、ａσ
＝ａA＝０として、結合荷重の平均ＷAを変化させたとき
の比較結果を示す。ＭＦＡＡ法と混合法はＷAが０．０
２以上、ＳＡ法はＷAが０．４以上で、Ｈ法と同等にな
る。これは、結合荷重の平均が大きくなるにつれて、結
合荷重の分散の影響が小さくなり、エネルギ−曲面が単
調になるためであろう。

【００２７】更に、図６（Ａ）は、Ｗσ＝０．１、ＷA
＝ａA＝０として、しきい値の分散ａσを変化させたと
きの比較結果を示す。優劣はａσが変化しても変動せ
ず、しきい値の分散の影響はほとんど無視できることが
分かる。

【００２８】最後に、図６（Ｂ）は、Ｗσ＝０．１、Ｗ
A＝ａσ＝０として、しきい値の平均ａAを変化させたと
きの比較結果を示す。混合法はａAが０．００２以上、
ＭＦＡＡ法はａAが０．３以上、ＳＡ法はａAが０．７以
上において、それぞれＨ法と同等になる。これは、しき
い値の平均が大きくなるにつれて、エネルギ−曲面が単
調になるためであろう。混合法は、ａAが０．２のとき
にホップフィ−ルドらの方法と優劣が逆転しているが、
その差は２％程度なので、これは誤差とみなせる。

【００２９】この他に、Ｗσを０．１以外の値とした場
合におけるＷA、ａσ、ａAの変化も想定できるが、その
場合でも、アルゴリズムの優劣は同様な傾向を示すもの
と推察される。したがって、最適なアルゴリズムは、Ｗ
σのみを考慮するだけでもおおよそは推定可能であり、
厳密性が要求される場合にのみ、ＷA、ａσ、ａAについ
ても検討すれば足りるであろう。

【００３０】スピングラスモデルについて各種アルゴリ
ズムの性能比較をする処理手順を、図７（Ａ）にＰＡＤ
図で示す。図中の各ブロックにおける処理は、次のとお
りである。

【００３１】ブロック７０１：結合荷重及びしきい値を
初期状態に設定する。ブロック７０２：結合荷重及びしきい値の終了状態を設
定する。ブロック７０３：結合荷重がブロック７０２で設定した
終了状態になるまで、ブロック７０４ないし７０７を繰
り返す。ブロック７０４：結合荷重を変化させる。ブロック７０５：しきい値がブロック７０２で設定した
終了状態になるまで、ブロック７０６と７０７を繰り返
して、ブロック７０３へ処理を移す。ブロック７０６：しきい値を変化させる。ブロック７０７：諸アルゴリズムの性能比較を行なう。
すなわち、ブロック７０１、７０４、７０６での処理に
より特定された結合荷重としきい値の下で、各アルゴリ
ズムによりエネルギー最小化計算を行ない、得られた解
（最小エネルギー値）と、そのときのＷA、Ｗσ、ａA、
ａσを記録する。解の値そのものの代りに、それらを比
較して得られる順位を記録してもよい。以上の処理が終
わると、ブロック７０５へ処理を移す。

【００３２】このようにして得られた性能比較の結果を
参照すれば、与えられた任意のニュ−ラルネットワ−ク
の同種統計量から、最適なアルゴリズムを選定すること
が可能であるから、その選定されたアルゴリズムを用い
て、与えられたニュ−ラルネットワ−クのエネルギ−最
小化計算を実行すればよい。図７（Ｂ）は、与えられた
ニューラルネットワークに最適なアルゴリズムを選定す
る処理手順を、ＰＡＤ図で示す。図中の各ブロックにお
ける処理は、次のとおりである。

【００３３】ブロック７０８：与えられたニュ−ラルネ
ットワ−クの結合荷重及びしきい値の統計量Ｗσ、Ｗ
A、ａσ、及びａAを計算する。ブロック７０９：ブロック７０８で得た統計量に最も近
い統計量に対する、前述のアルゴリズム性能比較結果を
参照する。ブロック７１０：ブロック７０９での参照の結果に基づ
き、最も小さいエネルギー値を与えるアルゴリズムを選
定する。なお、この観点からは同等な複数のアルゴリズ
ムが存在する場合には、他のファクター、例えば、計算
時間などに従って、選定を行なえばよい。

【００３４】次に、この選定方法の有効性を、巡回セ−
ルスマン問題（以後ＴＳＰ問題と略称する）を例にとっ
て検証する。ＴＳＰ問題とは、各都市を１度だけ通過し
て全都市を回るときに、都市間の移動距離の合計を最小
とする経路を求める問題である。これは、多項式で表わ
せる時間内では求解困難な、いわゆるＮＰ完全問題であ
る。ＴＳＰ問題のエネルギ−関数を次式に示す。

【００３５】

【数２】

【００３６】ただし、ニューロンはｎ行ｎ列に配列さ
れ、各行は各都市に対応し、各列は巡回の順位に対応す
る。Ｖ_XiはＸ行ｉ列のニュ−ロンの出力を表わし、ｄ_XY
はＸ番目とＹ番目の都市の距離を表わし、Ａ、Ｂ、及び
Ｃは任意の定数を表わす。このエネルギ−関数の第１項
は、各Ｖ_XYが２値（０，１）の一方に飽和したときに最
小値“０”を取り、第２項は、各行及び各列で１個のニ
ュ−ロンのみが“１”を出力して、他のニューロンはす
べて“０”を出力するときにのみ最小値“０”を取り、
第３項は、巡回総距離に対応し、これが最小になれば解
が得られたことになる。数２を数１と対応させて、結合
荷重及びしきい値を設定する。

【００３７】定数Ａ、Ｂ、及びＣを調節してＷσ、Ｗ
A、ａσ、及びａAを３通りに変化させたときの、各アル
ゴリズムで得られた規格化エネルギ−Ｅ／Ｎの比較を図
８に示し、図８における条件２の下で、各アルゴリズム
により得られた巡回経路を図９に示す。図９において、
（Ａ）はＨ法（反復１０００回）、（Ｂ）はＳＡ法（反
復１０００回）、（Ｃ）はＭＦＡＡ法（反復１０００
回）、（Ｄ）は混合法（ＭＦＡＡ法で反復１０回、ＳＡ
法で１０００回）により、それぞれ得られたものであ
る。

【００３８】条件１と条件２では、アルゴリズムの優秀
さは、混合法、ＭＦＡＡ法、Ｈ法、ＳＡ法の順番になっ
た。条件３では、混合法及びＭＦＡＡ法とＨ法がほぼ同
等であり、ＳＡ法が若干劣った。この結果は、図５
（Ａ）の対応するＷσでの順位と矛盾しない。ＷAとａA
が大きいために、混合法及びＭＦＡＡ法とＨ法の差は僅
かになった。しかしながら、図５（Ａ）と同様に、Ｗσ
が小さくなるにつれてエネルギ−差が減少する傾向は現
れており、また、エネルギ−差は微小であっても、図９
（Ｃ）と（Ｄ）では巡回経路が異なっていることから、
単なる数値誤差ではないことが確認できる。

【００３９】したがって、前述の方法により、複数のア
ルゴリズムの中から、与えられた問題に対して最適なア
ルゴリズムを選定することが可能である。次に、本発明
によるニューロン状態の更新方法を説明する。この方法
は、同期的状態更新方法の収束性を改善し、それによ
り、簡潔なプログラムで短時間に状態更新を行なうこと
ができ、ひいては、エネルギー最小化計算の高速化をも
たらすものである。

【００４０】本発明による状態更新方法は、次式に従っ
て、全ニューロンの状態を同期的に更新する。

【００４１】

【数３】Ｖ_i(ｔ＋１)＝{Ｖ_i'(ｔ＋１)＋τＶ_i(ｔ)}／（１＋τ）Ｖ_i'(ｔ＋１)＝ｆ(Ｖ_i(ｔ））

【００４２】ここで、Ｖ_i(ｔ）は、時刻ｔ、すなわち、
ｔ番目の反復計算で得られた各ニュ−ロンの出力を表わ
す。関数ｆは、ニュ−ロン状態を更新するアルゴリズム
を表わし、したがって、Ｖ_i'(ｔ＋１)は、従来の同期的
更新方法で得られる、時刻ｔ＋１でのニューロン出力で
ある。パラメ−タτは、後述する範囲内で適当に選ぶこ
とができ、例えば定数でよい。τ＝０にすると、通常の
同期的更新と同等になることに注意されたい。上記の式
は、本方法による状態更新の変化量が、従来方法による
変化量の１／（１＋τ）に圧縮されたことを意味する。
すなわち、数３は、次式と等価である。

【００４３】

【数４】Ｖ_i(ｔ＋１)−Ｖ_i(ｔ)＝｛Ｖ_i'(ｔ＋１)−Ｖ_i(ｔ)｝／（１＋τ）

【００４４】この方法について、数値シミュレ−ション
により有効性を検証する。対象とするモデルは、スピン
グラスモデル（ニュ−ロン数５０）とし、ＭＦＡＡ法を
適用した。

【００４５】まず、数３に示した方法において、τを変
化させたときの最小エネルギ−値の変化を図１０（Ａ）
に示す。図示のグラフでは、１０種類の異なる系列の正
規乱数列を初期状態として、得られた結果の平均値をプ
ロットしている。更に、１０種類の初期状態のうちで収
束したものの割合を図１０（Ｂ）に示す。

【００４６】図１０（Ａ）よれば、τ＝０からτ＝０．
１までは、満足できる結果は得られない。これは、図１
０（Ｂ）が示すように、収束しなかった場合があって、
そのときの値も平均値計算に含まれるためである。τ＝
０．２以上になると、全ての初期状態が収束をもたら
し、エネルギ−値も比較的安定している。ただし、τ＝
０．２のときと比較して、τ＝０．４では若干の劣化が
見受けられる。これは、τを大きくすると新しい状態に
変化し難くなるためであろう。したがって、τの値は、
０．２以上で、かつ、あまり大き過ぎないように、設定
するのが良いといえる。

【００４７】次に、一般に収束性が最も良いと考えられ
る非同期計算法と、単純な同期計算法と、文献４に記載
された、奇数番目のニュ−ロン群と偶数番目のニュ−ロ
ン群を別々に同期計算するチェッカ−ボ−ド法と、本発
明の方法の４手法について、比較検討する。

【００４８】シミュレ−ション条件として、各手法での
反復計算回数ｔを１００００回、パラメ−タτを０．２
とし、１０種類の系列の異なる正規乱数列をニュ−ロン
の初期状態として設定した。ス−パ−コンピュ−タのベ
クトル演算によるシミュレ−ション結果を、図１１に平
均値で示す。

【００４９】同期計算では、非同期計算よりも高速化さ
れて計算時間は短いけれども、５種類の初期状態につい
て、２つの状態の間での振動が生じた。つまり、同期計
算法は比較的に収束性の悪い手法であることが分かる。
他方、チェッカ−ボ−ド法では、どの初期状態を与えて
も無事に収束した。計算時間は、同期計算によるよりも
長いが、非同期計算と比較すれば短い。次に、本発明の
方法によれば、収束性が良く、しかも、チェッカ−ボ−
ド法よりも高速化されていることが分かる。したがっ
て、本発明の方法は、従来のチェッカ−ボ−ド法と比較
して、高速で、かつ、プログラム記述の簡便な方法とい
うことができる。

【００５０】叙上のシミュレ−ションではパラメ−タτ
を一定値に固定したが、τを反復番号ｔの関数として変
化させてもよい。その場合、ｔの増加につれてτを小さ
な値から大きな値へ徐々に増加させてゆけば、収束性が
一層良くなり、逆に、τを大きな値から小さな値へ徐々
に減少させてゆくと、最適解に一層近い解を得られるこ
とが期待できる。また、本方法はＭＦＡＡ法以外にも適
用可能であり、同様な効果が望める。

【００５１】図１２は、本方法の具体的な手順をＰＡＤ
図で示す。図中の各ブロックにおける処理は、次のとお
りである。

【００５２】ブロック１２０１：状態更新計算の反復回
数Ｔを設定する。ブロック１２０２：各ニューロンの初期状態を設定す
る。ブロック１２０３：ブロック１２０１で設定された反復
回数に達するまで、ブロック１２０４ないし１２０７を
繰り返す。ブロック１２０４：全ニューロンについて(ｉ＝１，
…，Ｎ)、反復ｔ番目の出力Ｖ_i（ｔ）から、反復ｔ＋１
番目の出力Ｖ_i'（ｔ＋１）を、選定されたエネルギ−最
小化アルゴリズムに従って同期的に計算する。ブロック１２０５：パラメータτを設定する。ブロック１２０６：全ニューロンについて(ｉ＝１，
…，Ｎ)、Ｖ_i（ｔ）と、ブロック１２０４で算出したＶ
_i'（ｔ＋１）と、ブロック１２０５で設定したτを用い
て、数３に従って新しい出力Ｖ_i（ｔ＋１）を計算す
る。

【００５３】この状態更新アルゴリズムは、また、前述
した諸アルゴリズムの性能比較のための計算にも、同様
に適用できることはいうまでもない。

【００５４】本発明は、非線形計画法のための最適アル
ゴリズムの選定及び実行にも、適用することができる。
組合せ最適化問題を解く方法の一つに非線形計画法があ
り、そのための様々なアルゴリズムが提案されていて、
問題に応じて最適なアルゴリズムを選択するのが望まし
い。それらのアルゴリズムは、ニューラルネットワーク
におけるエネルギー関数と等価な評価関数を設定して、
その最小値（又は最大値）を反復法によって探索するア
ルゴリズムに帰着する。そして、この評価関数の１次項
の係数はニューラルネットワークにおけるしきい値に対
応し、２次項の係数は結合荷重に対応する。したがっ
て、これらの探索アルゴリズムでもって前述の実施例に
おけるエネルギー最小化アルゴリズムを置き換えれば、
非線形計画法の最適アルゴリズムの選定及び実行を行な
うことができる。

【００５５】すなわち、予め、評価関数の１次項の係数
と２次項の係数のそれぞれの平均及び分散を種々に異な
らせて、複数の前記探索アルゴリズムにより最小化（又
は最大化）を行ない、得られた最小値（又は最大値）の
対比データを記憶装置に格納しておく。問題が与えられ
ると、それに対する評価関数の１次項の係数と２次項の
係数のそれぞれの平均及び分散を計算し、それらの値に
基づいて前記の対比データを参照して、最小（又は最
大）の評価関数値を与えるアルゴリズムを、最適のアル
ゴリズムとして選定し、そして実行する。このアルゴリ
ズムの実行は、ニューラルネットワークのエネルギー最
小化計算におけるのと同様な反復更新処理を含み、この
処理には、前述したような、状態変化量の圧縮を伴う同
期計算が適用できる。

【００５６】本発明は、更に、ニューラルネットワーク
による連想記憶のためのアルゴリズムにも、適用するこ
とができる。一般に、結合荷重としきい値を適当に選定
することにより、ニューラルネットワークに、同程度の
深さの複数のエネルギー極小点、すなわちネツトワーク
の複数の異なる安定状態を持たせることができ、そし
て、どの安定状態に収束するかは、諸ニューロンの初期
状態に依存する。各初期状態を入力パターンに対応付
け、その初期状態から収束する安定状態を出力パターン
に対応付けることにより、連想記憶が実現される。この
ような連想記憶を実現するための種々のアルゴリズムが
あり、それらの間の優劣は、設定したい記憶内容によっ
て異なる。

【００５７】本発明によれば、予め、設定すべき諸キー
パターンの間の相関量の平均と分散を変化させて各アル
ゴリズムを適用し、その結果の優劣を示す対比データを
作成して、記憶装置に格納しておく。相関量としては、
キーパターン間の内積を用いることができる。すなわ
ち、ｐ番目のキーパターン及びｑ番目のキーパターンに
対するｉ番目のニューロンの初期状態をそれぞれＶ
_i（ｐ）及びＶ_i（ｑ）で表わせば、これらのパターンの
相関量は次式で表わされる。

【００５８】

【数５】

【００５９】設定すべき一群のキーパターン中のすべて
のパターン対（ｐ，ｑ）についてこのような相関量を計
算し、次いでそれらの平均と分散を計算することができ
る。このようにして得られる平均と分散の値が種々に異
なる複数のキーパターン群を用意し、各キーパターン群
に各種の連想記憶アルゴリズムを適用して、結合荷重と
しきい値と出力パターンとを算定する。次いで、正しい
キーパターン及びそれらとは様々な程度で異なるパター
ンからなるテストパターン群を入力として与えて、出力
パターンを計算し、正しい応答が生じた率を対比データ
として記憶装置に格納する。設定すべきキーパターン群
が与えられると、それらのパターンの相関量の平均と分
散を計算し、それに最も近い条件の下で最高の正答率を
与えたアルゴリズムを選定して、実行する。出力パター
ンの計算に際して行なわれるニューロンの状態の反復更
新には、前述したような、状態変化量の圧縮を伴う同期
計算が適用できる。

【００６０】

【発明の効果】本発明によれば、与えられる様々な多峰
性多変数関数に対してそれぞれに最も適したアルゴリズ
ムを、コンピュータにより予め選定し、そして実行する
ことができ、更に、アルゴリズムの実行に際しては、同
期計算によって計算時間を短縮しながら、しかも、確実
な収束が期待できる。したがって、一般に長時間を要す
る多峰性多変数関数の極小点又は極大点の探索を、極め
て能率良く行なうことができる。

【００６１】加えて、対比データの収集のために諸アル
ゴリズムを適用する対象の変化を、統計量の変化によっ
て定めたので、比較的少量の、したがって作成も容易な
対比データによって、多種多様な関数のそれぞれに対す
る最適アルゴリズムを、的確に選定することができる。

【図面の簡単な説明】

【図１】本発明のシステム構成を示すブロックダイヤグ
ラム。

【図２】相互結合型ニュ−ラルネットワ−クの構成を表
わす模式図。

【図３】ニュ−ロンの機能を表わす模式図。

【図４】ニュ−ロンの出力関数を表わすグラフ。

【図５】荷重結合の統計量が変化したときのアルゴリズ
ムの性能比較を示すグラフ。

【図６】しきい値の統計量が変化したときのアルゴリズ
ムの性能比較を示すグラフ。

【図７】本発明によるアルゴリズムの性能比較の処理手
順と最適アルゴリズムの選定の処理手順とを示すＰＡＤ
図。

【図８】巡回セールスマン問題に適用した場合の諸アル
ゴリズムの性能比較データの例を示す図。

【図９】諸アルゴリズムにより得られた巡回セールスマ
ン問題の解の例を示す図。

【図１０】本発明の状態更新方法の効果を示すグラフ。

【図１１】本発明の状態更新方法と他の方法の比較デー
タを示す図。

【図１２】本発明による状態更新方法の処理手順を示す
ＰＡＤ図。

【符号の説明】

１０１・・・アルゴリズム対比データと実行プログラム
を格納した記憶装置１０３・・・コンピュータ７０１〜７０７・・・対比データ作成手順７０８〜７１０・・・最適アルゴリズム選定手順１２０１〜１２０７・・・反復更新手順

Claims

【特許請求の範囲】

【請求項１】多峰性多変数関数の極小点又は極大点の探
索のための複数のアルゴリズムを、関数を特徴付ける量
の統計量の値を異にする複数の多峰性多変数関数のそれ
ぞれに適用した結果の対比を示す、対比データが格納さ
れた記憶装置と、与えられた多峰性多変数関数に最適な
アルゴリズムを、この与えられた多峰性多変数関数を特
徴付ける前記量の統計量の値と前記対比データとに基づ
いて、前記複数のアルゴリズムの中から選択する処理装
置とを備えた、最適アルゴリズム選定装置。
【請求項２】請求項１において、前記統計量は平均及び
分散の少なくとも一方を含む、最適アルゴリズム選定装
置。
【請求項３】請求項１又は２において、前記関数はニュ
ーラルネットワークのエネルギー関数であり、関数を特
徴付ける前記量はシナプスの結合荷重とニューロンのし
きい値の少なくとも一方であり、前記対比データは算出
された最小エネルギー値である、最適アルゴリズム選定
装置。
【請求項４】請求項１又は２において、前記関数は非線
形計画法における評価関数であり、関数を特徴付ける前
記量は前記評価関数における係数の少なくとも一つであ
り、前記対比データは算出された最小関数値又は最大関
数値である、最適アルゴリズム選定装置。
【請求項５】請求項１又は２において、前記関数はニュ
ーラルネットワークからなる連想記憶の特性を表わす関
数であり、関数の特徴を表わす前記量は連想記憶の一群
のキーパターンの相関量であり、前記対比データは連想
記憶の応答の正誤率を示すデータである、最適アルゴリ
ズム選定装置。
【請求項６】請求項１ないし４のいずれかに記載された
装置において行なわれる方法であって、与えられた多峰
性多変数関数を特徴付ける量の統計量の値を計算するス
テップと、前記対比データを参照して、前記計算された
統計量の値に最も近い統計量の値に対して最小又は最大
の関数値を与えるアルゴリズムを選択するステップとを
備えた、最適アルゴリズム選定方法。
【請求項７】請求項５に記載された装置において行なわ
れる方法であって、与えられた一群のキーパターン中の
諸パターン対間の相関量の値の平均及び分散の少なくと
も一方の値を計算するステップと、前記対比データを参
照して、前記計算された値に最も近い同種の量の値に対
して最も良い正誤率を与えるアルゴリズムを選択するス
テップとを備えた、最適アルゴリズム選定方法。
【請求項８】請求項６又は７において、前記アルゴリズ
ム選択ステップは、実質上同一の関数値又は正誤率を与
える複数のアルゴリズムが存在するときに、それらの中
から計算時間が最短のアルゴリズムを選択する、最適ア
ルゴリズム選定方法。
【請求項９】請求項１ないし５のいずれかにおいて、前
記記憶装置には、更に前記複数のアルゴリズムのそれぞ
れを実行するためのプログラムが格納されており、前記
処理装置は、選択した最適アルゴリズムの実行のための
プログラムを実行する、最適アルゴリズム実行装置。
【請求項１０】請求項９に記載された装置において前記
選択されたアルゴリズムを実行する方法であって、前記
関数の各変数の値を反復して更新するステップが、前記
選択されたアルゴリズムに従って仮の更新値を算出する
ステップと、前記仮の更新値と更新前の値の差を所定の
パラメータに従って圧縮して更新後の値を決定するステ
ップと、前記算出ステップと決定ステップを適用して全
変数の値を同期的に更新するステップを含む、最適アル
ゴリズム実行方法。
【請求項１１】請求項１０において、前記圧縮のための
パラメータは全反復を通じて一定に保たれる、最適アル
ゴリズム実行方法。
【請求項１２】請求項１０において、前記圧縮のための
パラメータを反復更新の回が進むにつれて一定の方向に
変更するステップを含む、最適アルゴリズム実行方法。