SURE: Shizuoka University REpository
http://ir.lib.shizuoka.ac.jp/
Title
Author(s)
ニューロダイナミクスに基づく最適化問題の解法とその
応用に関する研究
二宮, 洋
Citation
Issue Date
URL
Version
1998-03-21
http://doi.org/10.11501/3137413
ETD
Rights
This document is downloaded at: 2016-02-15T14:41:44Z
静岡大学 博士論文
ニューロダイナミクスに基づく
最適化問題の解法
とその応用に関する研究
絆周大学国書
平成10年1月
大学院電子科学研究科
電子応用工学専攻
二宮 洋
論文要旨
近年，ホップフィールドらは組み合わせ問題の一つである巡回セールスマン問
題にニューラルネットワークを適用し，実用的な解が短時間で得られることを示
した．以来，多くの分野の研究者の参入によってニューラルネットワークの研究
は学際的な広がりを呈し，様々な問題に応用されてきた．一般に最適化問題を解
くための手法として直接探索法，勾配法，逆行列演算法が知られている．これら
は逐次的アルゴリズムであるため，大規模な最適化問題に対しては計算量が膨大
となり，収束に時間がかかるといった問題がある．一方，ホップフィールドらが
提案した手法は神経系の特徴である並列処理機構を生かしたアナログ電子回路モ
デル（ホップフィールド型ニューラルネットワーク）によるものである・つまり，
ネットワークに対してある評価関数（エネルギー関数）を定義し，ネットワークの
ダイナミクスがこの関数を常に減少させる方向へ動作することを示した．ホップ
フィールド型ニューラルネットワークによる解法は，エネルギー関数を最適化問
題に対して合目的的に決定することによって，回路が定常状態に到達した点が最
適化問題の極小解あるいは最小解となることを利用した手法である．
本論文ではホップフィールド型ニューラルネットワークを応用した，いくつか
の最適化問題に対する新たな解法の提案とその応用についての検討を行う．具体
的には，組み合わせ最適化問題に対する研究として，巡回セールスマン問題の解
法に関する研究，及び，タイリング問題の解法に関する研究を行う．また，ディ
ジタル信号処理へのホップフィールド型ニューラルネットワークの応用に関する
研究として，ディジタル回路の論理関数を最適化問題として定式化することによ
り，ニューラルネットワークディジタル順序回路の設計を行う．これらの研究を
通して，ニューラルネットワークの高並列性を利用した，従来の計算機にはない
新たな計算可能性の探求を目指す．
組み合わせ最適化問題として取り上げる巡回セールスマン問題（TSP）は，これ
まで，ホップフィールド型ニューラルネットワークを応用した最適化問題の解法
の研究対象として非常に多くの関心を集めてきた．そのほとんどが，エネルギー
関数の構成法として，都市の訪問順序に基づく手法が用いられてきた．この手法
では，都市とその順序を示すために，Ⅳ都市のTSPに対してⅣ2個のニューロン
が必要であり，また，問題の規模が増加すると収束率が急速に低下することが指
摘されてきた．一方，本研究で着目する都市隣接性に基づくエネルギー関数の構
成法では，Ⅳ都市のTSPに対して（Ⅳ−1）〃／2のニューロンでネットワークを構
成することができ，前者と比較して，比較的局所解へ陥りにくいという性質を持
っ．しかし，エネルギー関数に全ての都市を訪問するという制約が含まれていな
いため，複数の巡路に分かれる解に収束するという欠点がある．本研究では，後
者の手法に対して，この欠点を克服する新たな手法を提案し，従来の研究で扱わ
れてきた問題よりも大きな規模の問題に対して有効であることを示す．
また，もう一つの組み合わせ最適化問題として取り上げるタイリング問題とは，
有限の升目上に隙間なくポリオミノを敷き詰めていく問題である．ポリオミノと
は正方形の集合によって表される多角形のことである．これまで，ニューラルネッ
トワークを用いた組み合わせ最適化問題の研究対象のほとんどは巡回セールスマ
ン問題であった．一方，ポリオミノを用いたタイリング問題はこれまでにも取り
上げられてきたが，そのほとんどは逐次的アルゴリズムであり，ニューラルネッ
トワークを用いた並列的手法はほんの数例しかなかった．本研究では，前述の巡
回セールスマン問題で用いた隣接性に着目し，タイリング問題に対し，ポリオミ
ノの接触度を表す関数を新たに導入し，従来法で用いられたエネルギー関数を改
良する．さらに，従来法において使用されてきたマキシマムニューロンをアナロ
グニューロンに置き換えることによって処理することを考えた．このことは，ア
ナログ値を持つ，唆味なタイリングを許すことで，局所解からの脱出を可能にす
る．最後に，本研究の有効性をシミュレーションにより確認する．
次に，ディジタル信号に対するホップフィールド型ニューラルネットワークの
応用として，ディジタル順序回路の設計を行う．これまで，ディジタル信号処理
プロセッサに対するホップフィールド型ニューラルネットワークの応用として，
AD変換器や直交変換器等のディジタル信号処理プロセッサが研究されてきた．ま
た，ディジタル加算器や乗算器といった回路の設計も行われてきた．本研究では，
加算器や乗算器などの組合せ回路ではなく，フィードバックのあるディジタル順
序回路へのホップフィールド型ニューラルネットワークの応用として，時系列の
信号に対して大域収束性を持つゲート回路，ラッチ回路等を構成する．ニューラ
ルネットワークディジタル順序回路の設計手法は，まず，論理関数を最適化問題
に置き換えて定式化し，ネットワークのエネルギー関数を構成する．このエネル
ギー関数から目的とする回路を設計するという手法である．さらに，設計された
ラッチ回路をリカレントネットワーク上に配置することで，任意のディジタル順
序回路が構成できることを示す．設計された回路はシミュレーションとブレッド
ボード上での実験により，その動作が確認される．
最後に，本論文の結論を述べ，本論文の有効性及び，今後の展望について示す．
目次
1．1背景・‥‥ ‥‥ ‥・ ‥‥・‥
1．2 ホップフィールド型ニューラルネットワーク
1．3 論文構成‥ ‥・・・‥ ‥・
2．1概要・ ‥・ ・‥
2．2 都市隣接性に基づくTSPの解法・
2．2．1 エネルギー関数‥ ・
2．2．2 部分巡路・‥・
2．3 部分巡路の修復法・ ・
2．3．1従来法（外部入力修正による手法）・
2．3．2 提案手法（階層的修復法） ‥
2 2 3 3 4 5
1 1 1 1 1 1
2 都市隣接性に基づく巡回セールスマン問題の解法
6 6 7 9
1序論
15
16
2．4 シミュレーション‥・ ・‥
18
2．4．1 シミュレーションの概要・
2．4．2 シミュレーションアルゴリズム・
2．4．3 シミュレーション結果・ ・
2．5 まとめ・ ・
18
24
2．6 付録
25
19
19
3 アナログニューラルネットワークによる接触検出関数を用いたタイリング
27
問題の解法
3．1概要・ ・
27
3．2 従来法・ ・‥
3．3 提案手法・ ‥・ ・
3．3．1接触検出関数を含むエネルギー関数とアナログニューラル
ネットワーク
3．3．2 最適化アルゴリズム ‥ ・‥‥ ・
3．4 シミュレーション結果及び考察 ‥ ‥ ・
3．4．1 シミュレーション結果・ ・ ・
3．4．2 エネルギー関数の各係数に関する考察
3．4．3 ネットワークの過渡遷移に関する考察 ・
28
3．5 まとめ・ ・ ・ ‥・
41
4
31
31
34
36
36
37
39
4 ホップフィールド型ニューラルネットワークによるディジタル順序回路 42
4．1概要 … ……… ……… …… 42
4．2 従来法によるニューラルネットワーク論理積回路の設計・ 43
4．3 大域収束性を持つニューラルネットワークディジタル回路の設計・46
46
4．3．1 論理積回路の設計‥ ・
51
4．3．2 Dラッチ回路の設計
57
4．3．3 全加算器の設計・ ‥
61
4．4 ディジタル順序回路の構成・
61
4．4．1 Dフリップ・フロツプの構成・
63
4．4．2 シフトレジスタの構成・
63
4．4．3 非同期式カウンタの構成・
67
4．5 まとめ・ ・
5 リカレントニューラルネットワークによるディジタル順序回路の設計 68
5．1概要・ ・‥ ‥・
68
5．2 3層バイナリーリカレントニューラルネットワーク
69
5．3 ディジタル順序回路の設計・ ‥‥ ‥‥
71
5．3．1 準備・ ‥ ‥ ・ ・‥ ‥
71
5．3．2 次状態デコーダの設計・ ‥ ・
72
5．4 シミュレーション結果・ ・‥ ‥ ‥
76
5．5 まとめ ‥ ‥ ‥ ‥
76
6 結論
79
謝辞
83
参考文献
84
5
1 序論
1．1 背景
近年，ニューラルネットワークは新しい情報処理能力をもつシステムとして注
目を集めており，そのモデルや応用に関して盛んに研究が行われている．ニュー
ラルネットワークはこれまでの逐次処理装置と異なり，単純な機能をもつ素子が
相互に多数結合し，情報を高並列に処理することが大きな特徴である．このよ
うな研究ブームの背景には，ニューラルネットワークに対する次のような期待が
あると考えられる．まず一つは，そこから人間の認識思考能力を機械的に実現す
るための新しい方法論が得られるのではないかという期待である．もう一つは，
ニューラルネットワークの持つ高並列性という，従来の計算機にはない特徴によ
る新しい計算能力への期待である．
この後者の観点から，ニューラルネットワークの計算能力を検証する上で，さ
まざまな問題，たとえば，信号処理，線形・非線形計画法，組み合わせ問題等へ
の応用が関心を集めている．その中で代表的なものの一つに，ホップフィールド
らが提案したアナログ電子回路モデル【1日4］により構成された相互結合型ニュー
ラルネットワークを用いた最適化問題の解法がある．以下，このネットワークを
ホップフィールド型ニューラルネットワークと称する．このネットワークの動作
は単純な勾配法と見なすことができ，エネルギー関数を使って定式化することに
より，一種の最適化マシンと見ることができる．これにより，様々な最適化問題，
例えば，組み合わせ問題【3日23】，信号処理【25日33】，線形・非線形計画法【4］【34］
等を高速に解くことが可能であることが報告されている．また，ネットワークの
入出力特性が2値の飽和特性で表されることから，ディジタル回路への応用が関
心を集めている【35日36上
本論文では，ホップフィールド型ニューラルネットワークを用いたいくつかの
最適化問題に対する新たな手法の提案とその応用を目的としている．具体的には，
巡回セールスマン問題の解法に関する研究【9】，及び，タイリング問題の解法に関
する研究【20日23］を行う・また，ネットワークのディジタル回路への応用として，
ホップフィールド型ニューラルネットワークによるディジタル順序回路【37日42］
の構成法に関する検討を行う．これらの研究を通して，ニューラルネットワーク
の高並列性を利用した，従来の計算機にはない新たな計算可能性の探求を目指す．
研究の序となる本章では，以下，ホップフィールド型ニューラルネットワーク
について概説する．
6
苺 ＋≡オ
外部入力電流Ii シナプス結合荷重丁毎
覇
ニュ−ロン’
川
積分器 正負反転出力の
ニューロアンプ
図1．1：ホップフィールド型ニューラルネットワーク
1．2 ホップフィールド型ニューラルネットワーク
ここでは，本研究で扱うホップフィールド型ニューラルネットワーク【1日41に
っいて説明する．ホップフィールド型ニューラルネットワークのアナログ電子回
路モデルを図1．1に示す．図1．1の回路で五番目のニューロンに注目すると，その
ダイナミックスは次式で与えられる．
堵一芸＋差別＋ム （1・1）
ここで，犯はニューロンの個数，筍はJ番目のニューロンから五番目のニューロン
へのシナプス結合荷重を表し，叫，Ⅵ，んはそれぞれ，五番目のニューロンの入力
電圧，出力電圧，外部からの入力電流を表している．非線形素子であるニューロ
ンアンプの入出力特性は，単調増加な非線形飽和特性を持つ（1．2）のようなシグ
イモイド関数で表わされる．
Ⅵ＝J伽）＝去（1＋血（β刷 （1・2）
この特性を図1．2に示す・瑚ま正負の値を取り得るが，回路上では筍が負の場合，
これを抵抗で表わすことができないので，正負の反転した入出力特性を持つニュー
ロンアンプを用いて実現する．この場合，入出力特性は（1．2）に負の符号をつけ
たものとなる．
7
V．
図1．2：シグモイド関数
ホップフィールド型ニューラルネットワークでは，出力Ⅵを変数とするエネル
ギー関数且が次式で定義される．
β＝一芸墓研均一ご用 （1・3）
回路は，エネルギー関数且が常に減少する方向に動作し，極小（理想的には最小）
になったときに平衡状態に達する．従って，目的とする出力になったときエネル
ギー関数が最小になるように筍とムを決めれば，所望する動作を獲得できる・つ
まり，対象となる最適化問題に対して，最適解が最小となるエネルギー関数を定
義し，そのエネルギー関数と（1．3）を比較することによって，回路定数花，んを
決定する．
また，（1．1）においてri＝∞とした場合，ニューラルネットワークの動作方程
式は次式のように書き換えることができる【19ト
血i ∂E
（1．4）
df ∂Ⅵ
っまり，ニューロンの入出力特性が単調増加関数であることを考慮すれば，ニュー
ラルネットワークの動作は最適化問題の評価関数β（エネルギー関数）を最急降下
法に基づいて解くことと等価であると考えることができる．
8
本論文では，このネットワークを用いた，巡回セールスマン問題【31およびタイ
リング問題【171【18】の解法を提案する・また，信号処理プロセッサへの応用とし
て，ホップフィールド型ネットワークによるディジタル順序回路の設計法【37日42】
を示す．
1．3 論文構成
本論文の構成を以下に示す．第2章では都市隣接性に基づく巡回セールスマン
問題（TSP）の解法について示す．これまで，ホップフィールド型ニューラルネッ
トワークを用いた最適化問題の解法としてTSPを例題とする研究が非常に多くな
されてきた【3日5日8トそのほとんどが，エネルギー関数の構成法として，都市の
訪問順序に基づく手法【31が用いられてきた・この手法では，都市とその順序を
示すために，〃都市のTSPに対してⅣ2個のニューロンが必要であり，また，問
題の規模が増加すると収束率が急速に低下することが指摘されてきた．この手法
の局所解への陥りを防ぐ方法として，ガウシアンマシンの利用【10】や，カオスノ
イズなどの外部ノイズを加える方法【12日14】など様々な研究発表がなされている・
一方，都市隣接性に基づくエネルギー関数の構成法では，Ⅳ都市のTSPに対して
（Ⅳ−1）坤2個のニューロンでネットワークを構成することができ，前者と比較
して，比較的局所解へ陥りにくいという性質を持つ【7】【8】・しかし，エネルギー関
数に全ての都市を訪問するという制約が含まれていないため，複数の巡路に分か
れる解に収束するという欠点があり，今日まであまり取り上げられていない．本
研究では，後者の手法に対して，複数の巡路（部分巡路）を階層的に修復する手法
（階層的修復法）を加えた解法を提案する．階層的修復法では，まず最初に構成さ
れた各部分巡路を1つの都市と置き換えることにより，部分巡路の集合が一つの
TSPを構成すると考える．これを1階層上のTSPとする．本手法には近い都市同
士を結ぶ特徴があるが，1階層上のTSPを解くことで得られた巡路を基に下の階
層の部分巡路を近づける．すなわち，各部分巡路を段階的に接近させ，結合を促
し，準最適解を得る．本手法は比較的大きなTSPに対してもアルゴリズムを再
帰的に用いることにより，容易に応用できる．その結果，都市の訪問順序に基づ
く手法と比較して，より大きな規模のTSPについて準最適解が得られることを
示す．
第3章では，ホップフィールド型ニューラルネットワークによるタイリング問
題の解法について示す．タイリング問題とは有限の升目上に隙間なくポリオミノ
を敷き詰めていく問題である．ポリオミノとは正方形の集合によって表される多
角形のことである．ポリオミノを用いたタイリング問題はこれまでにも取り上げ
られてきた【57日60】・しかし，これらはすべて逐次的手法であり，文献【101によ
9
り初めて並列的手法が用いられ，そこでは，確率的ニューラルネットワークを用
いた最適化問題としてタイリング問題が扱われている．タイリング問題はNP完
全問題であり，文献【10】では，実験に用いた問題のサイズが小さいにも関わらず，
正解への収束性はあまりよいものではなかった．その後，文献【17日18】ではさら
に大きな問題として，ポリオミノの回転及び反転を考えないことを前提として，
7×7の升目上で10個のポリオミノを敷き詰めるタイリング問題を解くことに成
功している．この間題は，約1．3×1014通りの候補から唯一解を求めるものであ
り非常に難しい問題である．しかし，【17日18】では，エネルギー関数の最小値が最
適解に対応していないという問題があった【20日23】・
一方，第2章で扱うTSPの解法では都市の隣接性に注目していた．本研究では
この隣接性に着目し，タイリング問題に対し，ポリオミノの接触度を表す関数
を新たに導入し，従来法で用いられたエネルギー関数を改良する【21日23】・さら
に，従来法において用いられていたマキシマムニューラルネットワークをアナロ
グニューラルネットワークによって処理することを考えた．このことは，曖昧な
タイリングを許すことで，局所解からの脱出を可能にする．我々のアルゴリズム
によれば，10×10の升目上に14個のポリオミノを配置するタイリング問題を解
くことができた．この間題の全候補は，約1．6×1024通りであり，本アルゴリズ
ムがより大きく複雑なタイリング問題に対応できることが検証される．
第4章では，ディジタル信号に対するホップフィールド型ニューラルネットワー
クの応用として，ディジタル順序回路の設計を行う．これまで，ディジタル信号
に対するホップフィールド型ニューラルネットワークの応用として，AD変換器
【4日24日25】や直交変換器【26日33】等の信号処理プロセッサが研究されてきた・また，
加算器や乗算器といったディジタル回路の設計も行われてきた【35日36】・本研究で
は，加算器や乗算器などの組合せ回路だけではなく，フィードバックのあるディ
ジタル順序回路にこのホップフィールドのニューラルネットワークを応用するこ
とで，次段への信号遅延のないニューラルネットワークディジタル順序回路を構
成することを目標とする．
ディジタル順序回路をホップフィールド型ニューラルネットワークを用いて構
成するためには，論理関数を最適化問題に置き換えて定式化し，ネットワークの
エネルギー関数を構成する必要がある．そこで，まず，論理関数からエネルギー
関数を構成し，時系列の入力信号に対して大域収束性を有するゲート回路，ラッ
チ回路，及び，全加算器を設計する方法を示す．そして，それら，ゲート回路や
ラッチ回路を従来のディジタル回路の設計法を用いて組合せることによりフリッ
プ・フロツプ，シフト・レジスタ，及び，非同期式カウンタを構成する．また，大
域収束性を持つ全加算器を組み合わせることにより，リプルキャリー型加算器を
構成する．これらの回路が正確に動作することをシミュレーションにより確認す
10
る．また，いくつかの回路については，ブレッドボード上に実装しその動作検証
を行う．
さらに，第5章において，第4章で設計するラッチ回路（ラッチニューロン）を
入力層及び出力層に用いた3層で構成された階層型ニューラルネットワークを提
案する．通常，階層型ニューラルネットワークの学習には非常に多くの時間が費
やされてきた．そこで，本研究では，通常のディジタル回路の設計と同様に学
習パターンの入出力関係のプール代数を利用した学習則，Boolean−liketraining
algorithm（BIm）を学習則として用いる・これにより，任意のディジタル順序回
路が階層型ニューラルネットワークで設計できることをシミュレーションを通し
て検証する．
最後に，第6章において，本論文の総括を述べる．
11
2 都市隣接性に基づく巡回セールスマン問題の解法
2．1 概要
本章ではホップフィールド型ニューラルネットワークを用いた最適化問題の解
法の研究に対する試みとして，都市隣接性に基づく巡回セールスマン問題（TSP）
の解法を取り上げる．近年，ニューラルネットワークを用いた最適化問題の解法
の研究が盛んに行われている．その中でもよく扱われるのがTSPであり，様々な
解法が提案されてきた【3］【5日8トその中で，エネルギー関数の構成法として，都
市の訪問順序に基づく手法【3】や，巡路中の都市隣接性に基づく手法【7】【8】などが
ある．
前者の手法は数多く研究されてきたが，収束性の問題が以前から指摘されてき
た．この手法の局所解への陥りを防ぐ方法として，ガウシアンマシンの利用【10】
や，カオスノイズなどの外部ノイズを加える方法【12日14】など様々な研究発表が
なされている．
一方，後者の手法においては，エネルギー関数に全ての都市を訪問するという
制約が含まれていないため，複数の巡路に分かれる解に収束するという欠点があ
り，今日まであまり取り上げられていない．しかし，エネルギー関数の構成が前
者の手法と比較して単純であることから，局所解へ陥りにくいとされている．従っ
て，都市隣接性に基づく手法は，複数の巡路（部分巡路）を何らかの方法を用いて
修復することができれば，都市の訪問順序に基づく手法よりも比較的容易に準最
適解を得ることができる【71【8】．ところが，どちらのエネルギー関数を用いた手法
の研究においても，その中で扱われる問題の規模は30都市程度であった．
本研究では，後者のエネルギー関数を用いた手法に対して，部分巡路を修復す
るための手段として階層的修復法を提案する．階層的修復法では，まず最初に構成
された各部分巡路を1つの都市とみなすことにより，部分巡路集合を一つのTSP
と考える．これを1階層上のTSPとする．本手法には近い都市同士を結ぶ特徴が
あるが，1階層上のTSPを解くことで得られた巡路を基に下の階層の部分巡路を
近づける．すなわち，各部分巡路を段階的に接近させ，結合を促し，準最適解を
得る．本手法は比較的大きなTSPにおいてもアルゴリズムを再帰的に用いるこ
とにより，容易に応用できる．前進オイラー法を用いてシミュレーションを行っ
た結果，これまで扱われてきた問題と比較して50都市というより大きな規模の
TSPに対して準最適解が得られることを示す．
12
ABCDEF
‡三二
BCDEF
■盗菖国書
図2．1：隣接性に基づくネットワーク表現
2．2 都市隣接性に基づくTSPの解法
2．2．1 エネルギー関数
巡路中の都市隣接性に基づくTSPのニューラルネットワーク表現を説明する．
都市隣接性に基づく手法とは，各都市間距離の短いパスを優先的に選び，最短巡
路を得るというものである．よって，ニューロンの出力晦は，都市宜と都市Jが隣
接しているかどうか，つまり，2都市間にパスが存在するか否かを示す・晦＝晦
であるため，ニューロンの半分は必要がない．更に，対角項も意味をなさないの
で必要がない．従って，五＜Jを満たすニューロンのみを考慮すればよく，N都市
間題に対するネットワーク表現は図2．1のようにN（沖1）／2個のニューロンで表さ
れる．
ここでは各行各列に2個のニューロンが発火している，つまり，各都市が他の
2都市と隣接しているという制約条件を使うため，エネルギー関数は次式のよう
になる．
β（Ⅴ）＝ ∑∑晦もy
J＝ly＝才＋1
＋入∑（2−∑侮−∑‰）2
才＝l
y＝∬＋l
y＝1
＋2人∑∑侮（1−‰）
ここで，屯は，都市∬，y間の距離を意味する・また，各項は，それぞれ，
第1項：巡路の総距離を表し，最短順路を得るための目的項
第2項：各都市が他の2都市と隣接するための制約項
第3項：自己結合削除項【16】
である．
13
（2．1）
閣
川
捌
仙
郷
日
影
ABCDEFG
≡テ≡千三≡
図2．2：部分巡路とネットワーク状態
自己結合削除項は，エネルギー関数の結合荷重の対角要素を除去し，各ニュー
ロンの出力値を0または1に近づける働きがある．
本手法では，ホップフィールド型ニューラルネットワークを用いている．（2．1）
とホップフィールドのエネルギー関数（1．3）を係数比較し，結合荷重l明肋肌と外部
入力んを求めると次のようになる．
l穐Jmn＝−2人（∂七m＋あ几＋あm＋＆n）
（2．2）
たくJ，m＜犯，た≠m，J≠犯，1＜り，m，乃＜〃
ん＝6人−dたJ
（2．3）
ここで∂七mはクロネッカーのデルタと呼ばれ，次式で表される．
（2．4）
∂七m＝〈㍊孟ニse
これらの係数を用いて，ネットワークの動作方程式（1．1）を数値解析すること
によりシミュレーションを行う．本研究では，動作方程式の解析に前進オイラー
法を適用する．
2．2．2 部分巡路
本研究で用いるエネルギー関数には，全ての都市を訪問するという制約が入っ
ていない．したがって，都市配置によりいくつかの部分巡路に分かれる解に収束
する場合がある．図2．2に部分巡路が現れやすい都市配置と部分巡路の例，及び
ネットワーク状態を示す．つまり，都市が遍在するとエネルギー関数の性質上，
部分巡路に分かれた解に収束する．しかしこの状態がエネルギー関数の最小値で
あると考えられる．
都市隣接性に基づく手法は近くの都市同士を結びつけることにより，巡路を形
成しようとするため，都市が部分的な群を作って遍在すれば都市群ごとに部分巡
路を作ることになる．したがって，部分巡路を解消するためには都市群の偏りを
14
なくす必要がある．そこで，一度ネットワークを動作させた後，ネットワークが
収束した時点で，各部分巡路の所属都市を検索し，部分巡路修復の情報とする．
次に，そのとき現れた部分順路の修復法について述べる．
2．3 部分巡路の修復法
ネットワークを動作させ，部分巡路が存在する解に収束した場合，この部分巡
路同士を結合させ，単一巡路に収束させる．ここでは，部分順路を単一順路に修
復するための方法に関して，従来法と提案手法について述べる．
2．3．1従来法（外部入力修正による手法）
複数の部分巡路ができた場合，ニューロン卿への外部入力んyを増減し，どこ
かの都市間の結合を切り，別の都市間を結合させ単一巡路に収束させる．すなわ
ち，んyを変化させることにより，各部分巡路間の距離を擬似的に近づけ，単一巡
路に導いている．
複数の部分巡路に分かれている場合は，外部入力んyの修正量は以下の通りで
ある．
0・5α（んは。一転）if G≠q
△んy＝
−αd叩 if（左＝q＝1
〈
0 if
（2．5）
G＝q＝0
ここで丸田はも廿の中の最大値を指し，Gは基準の都市と同じ部分巡路に属する
時，1となる関数である・G≠qの時，基準の部分巡路とその他の部分巡路に
属する都市間距離を縮め，G＝q＝1の時，基準の部分巡路内の都市間距離を
拡げ，G＝q＝0の時には，基準の部分巡路に属さない都市間は同じ部分巡路
に属するかどうか不明なので，外部入力の変更を保留することを意味する．この
過程を部分巡路の数だけ繰り返し，その都度修正量を求め，それらを加算したも
のが総修正量となる．
最後に単一の巡路が得られる場合もあれば，いかなる巡路も得られない場合も
ある．いかなる巡路も得られない場合は，
CO打Ⅳrl：部分巡路内で消滅した結合数の2倍
CO打Ⅳr2：部分巡路内から外部へのびた結合数
を求め，これより適応係数rを次式に従い導く．
r＝7（4−CO［Wrl−CO打Ⅳr2）／4
15
（2．6）
これを（2．5）に乗じたものを次の修正量とする．外部入力を次式により修正した
後，ネットワークを再び動作させ，収束したら結合状態をチェックする．
んy＝んy＋△んy （2・7）
単一巡路に収束すればそれを解とし，複数の部分巡路に収束した場合には再々度
外部入力を修正して修復を試みる．
2．3．2 提案手法（階層的修復法）
ここでは，階層的表現を用い，部分巡路を段階的に近づけていくことにより単
一巡路を求める手法を提案する．ネットワークが収束し，何らかの巡路を構成し
ている場合，部分巡路の数，各部分巡路に属する都市を検索する（図2．3（1））．最
初に構成された巡路及び都市をレベル1での部分巡路とする．次に各部分巡路の
重心をとり，それぞれをGla，Glb，GIc，…とする（図2．3（1））．ここで得られた
重心をそれぞれを1つの都市としてみなすとレベル1で生じた複数の部分巡路の
集合（すなわち，各部分巡路の重心の集合）が1つのTSPを構成することになる．
これをレベル2（1階層上）のTSPとする．レベル2においてTSPを解くことによ
りレベル2の巡路が得られる（図2．3（2））．ここでレベル2の巡路の重心をG2aと
する．都市数が多い場合，レベル2における順路の重心が複数存在する可能性が
ある．その場合，それぞれの重心をG2孔，G2b，G2C，…としたレベル3の都市
配置考え，レベル3においてTSPを解くことによりさらに1階層上の巡路を形成
する．以上の換作を再帰的に用いることにより，TSPを階層的に表現することが
できる．この階層的表現により得られた情報を基に部分巡路を修復する．
次にどのように階層的表現を用いて単一巡路に収束させるのかを示す．本手法
のエネルギー関数（2．1）は，近い都市同士を結合するという特徴があるため，1階
層上の巡路を基に部分巡路同士を近づけていき，単一巡路に収束させる．まず，
レベル1の部分巡路の重心GIs（β＝α，む，C，…）からレベル2の部分巡路の重心G2a
へのベクトルC（∬，y）を求める（図2．3（3））．次に，レベル1の各部分巡路をその形を
保持しながら，次式に従い
か（∬，y）＝か（∬，封）＋（㍍＊G（C2αエーClβ訂，C2αy−Clβy）） （2・8）
各ベクトルの㍍倍だけG2aへ近づけ，都市配置を変更する（図2．3（4））．ここで
か（X，y）は都市座標を表すベクトル，GIs。，GIsyはGIsの座標，G2aJ，G2a甘はG2a
の座標である．このようにして各部分巡路を近づけることにより，都市の遍在性
が段階的に弱められる．ここで再度TSPを解くことにより，部分巡路同士を結合
させる．この操作を繰り返し，単一巡路が得られた時点で収束とする．
このアルゴリズムをレベル1から再帰的に用いることにより，比較的大きな問
題にも容易に応用できる．
16
図2．3：部分巡路の階層表現と修復法
17
表2．1：パラメータ
都 市 配 置
入
仇
△β
㍍
亡
（a ）
1．
0
2．
0
0．
001
0 ．2
0 ．5
（b ）
1．
0
2．
0
0．
001
0．
2
0 ．5
（C ）
1．
0
2．
0
0．
001
0．
2
0 ．5
（d ）
1．
0
2．
0
0．
001
0 ．1
0 ．5
（e ）
1．
0
2．
0
0．
001
0．
25
0 ．5
（f ）
1．
0
2．
0
0．
001
0．
2
0 ．5
2．4 シミュレーション
2．4．1 シミュレーションの概要
シミュレーションはネットワークの動作方程式を次式の前進オイラー法で解析
する．
‰J（f＋1）＝搬出）＋△搬出） （2．9）
収束性を高めるためにシグモイド関数のシャープニングを行う．シャープニング
はネットワークの反復につれてシグモイド関数（1．2）のゲインβの値を次式に従っ
て増加させる．
β＝仇＋△β （2．10）
都市座標を変更し，ネットワークを再起動する際は，新たな問題を解くことと等
価になるため，ニューロンへの入力値とシグモイド関数の利得であるβの値を初
期化する．また，最適解の吸引領域は入力電圧の原点の近傍を含んでいると思わ
れるため，ニューロンへの入力電圧‰王の初期値は原点近傍0．0士1．Oe−5の間の
乱数を用いる【15］．
シミュレーションに使用した各パラメータを表2．1に示す．ここで，各パラメー
タの意味は以下の通りである．
入：エネルギー関数の制約項の係数
仇：シグモイド関数のゲインの初期値
△β：シグモイド関数のゲインの増分
㍍：部分巡路同士を近づける際の刻み係数
亡：ニューロンを発火状態とみなす限界
18
2．4．2 シミュレーションアルゴリズム
本研究において使用したアルゴリズムを図2．4に示す．
2．4．3 シミュレーション結果
シミュレーションの試行はそれぞれの例題に対して50回ずつ行った．都市配置，
図2．5，2．6，2．7についてのシミュレーション結果を表2．2に示す．例題1はホップ
フィールドらが扱った都市配置【31で，部分巡路はできなかった．例題2，3は相島
らが扱った問題【8］で部分巡路数4となった．例題1においてエネルギー関数の係
数人は0．7∼5．0の間の任意の状態で等しい解へ収束する．例題3においても係数
人の有効範囲を調べた結果，人は0．2∼3．3の間の任意の数で等しい解へ収束する
ことが確認された．例題1，2，3いずれの場合にも準最適解への収束確率は100％
であった．
表2．2：シミュレーション結果
都市配置
例題 1
例題 2
例題 3
都 市数
10
15
20
4
4
部 分 巡 路 数 （レベ ル 2）
1
0
1
1
準 最 適解 探 索 率 （
％）
100
100
100
部分 巡 路 数 （レベ ル 1）
都市配置，図2．8，2．9，2．10についてのシミュレーション結果を表2．3に示す．例
題4，5，6は都市数30∼50の比較的大きなオリジナル問題である．すべての例
題に関して，準最適解への収束ではあるが高い収束性が得られた．
表2．3：シミュレーション結果
都市配置
例題 4
例題 5
例題 6
都 市数
30
40
50
部 分 巡 路 数 （レベ ル 1）
8
5
5
部 分 巡 路 数 （レベ ル 2）
1
2
1
準 最適 解 探 索 率 （
％）
100
100
100
19
Sub−rOutinel
（
各ニューロンの内部状態を乱数により初期化；
do（
（2．9）による抜上の更新；
（2．10）によるシャープニング；
）while（△Ukl≠0）
）
Sub−rOutine2
（
部分巡路の検索；
重心の算出；
重心間のベクトルGの算出；
重心を都市とみなす；
）
Main−rOutine
（
初期設定；
do（
do（
Sut＞rOutinel；
Sut＞rOutine2；
）while（2階層以下）
部分巡路をCを用いて（2．8）により1階層上の重心へ近づける；
）while（部分巡路が存在）
）
図2．4：シミュレーションアルゴリズム
20
Dist＝2．689726
図2．5：例題1
Dist＝3．516756
図2．6：例題2
21
Dist＝3．543609
図2．7：例題3
Dist＝4．786241
図2．8：例題4
22
Dist＝5．941163
図2．9：例題5
Dist＝5．847003
図2．10：例題6
23
2．5 まとめ
本手法は，近い都市同士を結び巡路を形成し，部分巡路が形成されれば部分巡
路同士を近づけるという直感的にもわかりやすく，人間の思考に近い解法と言え
る．比較的大きな問題においても100％の確率で一つの準最適解に収束すること
から，この巡路中の都市隣接性に基づく手法はホップフィールドらの訪問順序に
基づく手法と比較して，収束確率が高いと言える．これは訪問順序に基づく手法
と異なり，各ニューロンが都市間のパスを表しているため，目的項が単純に表記
されるためである．これに加え，全都市を訪問する制約が含まれないため，エネ
ルギー関数の起伏が減少するものと考えられる．また，部分巡路が出現した場合，
都市配置を変更していくことにより，エネルギー関数の最小値が段階的に変化す
る．こうして部分巡路を結合し，単一巡路に収束させることにより準最適解が得
られる．これまでホップフィールド型ニューラルネットワークを用いたTSPの解
法の研究では，30都市程度までの例題しか扱われておらず，本論文で扱ったよう
な比較的大きな問題は解析されていなかった．提案手法を用いることにより，準
最適解ではあるが，50都市という比較的大きな問題でも意味のある解に収束する
ことが確認された．これらのことから，本手法は比較的大きな問題に対しても有
効であることが確認された．
24
2．6 付録
都市配置の座標データ（淋y座標）を以下に示す．スケールは一辺の長さ1の正
方形とする．
付表1：座標データ1
例題 1
例題 2
例 題 3
0．
1707 0 ．
2293
0 ．10 3 3 0 ．1 10 0
0．
083 3 0 ．
8567
0 ．
22 93 0 ．
7 6 10
0．
8067 0 ．
1200
0．
190 0 0 ．
5000
0．
24 39 0 ．
1463
0．
7367 0 ．
3567
0．
1967 0 ．
1600
0．
400 0 0 ．
4439
0．
1167 0 ．
8033
0．
2 367 0．
6 500
0．
5 17 1 0 ．
9 4 14
0．
2 833 0 ．
6033
0．
2 567 0．
0 500
0．
6 19 5 0 ．
2634
0．
7 700 0 ．
7233
0．
3 100 0．
3 900
0．
668 3 0 ．
2536
0．
5 733 0 ．
8300
0．
3 100 0．
8 867
0．
6 8 7 8 0 ．5 1 2 9
0．
8 733 0 ．
8500
0．
4 0 3 3 0 ．1 1 6 7
0．
848 8 0．
3 609
0．
0 66 7 0 ．
3967
0．
4 033 0．
286 7
0．
873 2 0．
6 536
0．
2 93 3 0 ．
3 133
0．
4 633 0．
8 13 3
0．
8 83 3 0 ．
2 967
0．
54 00 0．
650 0
0．
623 3 0 ．
1200
0．
5 800 0 ．
3 16 7
0 ．1 16 7 0 ．
6 300
0．
70 33 0 ．
866 7
0．
6900 0 ．
9 367
0．
7 167 0 ．
780 0
0．
6 16 7 0 ．
2 767
0．
7 6 0 0 0 ．16 0 0
0．
78 00 0 ．
4 10 0
0．
8 100 0 ．
623 3
0．
8 167 0 ．
8267
0．
87 00 0 ．
2667
0．
880 0 0 ．
1467
25
付表2：座標データ2
0．682330．15299
0．741080．48299
0．998750．02750
0．445020．08951
0．776210．14612
0．715660．33863
0．268990．40315
0．064670．91818
0．325020．03629
0．966280．44011
0．858180．13178
0．418620．03961
0．888790．24250
0．686030．85195
0．010100．58278
0．614220．12455
0．499400．47694
付表3：例題6の座標データ
0．329020．87533
0．403060．71151
0．742880．90771
0．521740．57064
0．888390．50581
0．544820．65487
0．943820．99652
0．799190．19562
0．845180．88595
0．326550．23136
0．277500．14426
0．373240．42238
0．301890．25831
0．099090．40413
0．644860．27085
0．914300．48100
0．197240．91598
0．095030．67971
0．242160．58071
0．289380．37208
0．267890．20106
0．135200．41627
0．432260．30226
0．466230．69018
0．398850．51311
0．410780．27772
0．043280．29551
0．802480．65249
0．905480．00656
0．122810．45415
0．930720．16547
0．437820．42647
0．716270．32167
0．651020．84124
0．505940．89703
0．008940．34986
0．924130．19227
0．801630．41200
0．476360．51332
0．405260．13715
0．676200．27421
0．575210．38414
0．879880．97955
0．784230．66601
0．869870．03836
0．929870．10752
0．256290．65496
0．565540．43760
0．624320．07184
0．313030．49754
0．104800．15998
0．622360．30464
0．996370．63091
0．425520．94327
0．254890．69900
0．388650．56044
0．908870．78994
0．885490．55089
0．054540．78820
0．101170．98337
0．761100．02960
0．306530．96805
0．975160．10456
0．895110．92984
0．689260．60842
0．915370．49687
0．978270．92486
0．971860．07019
0．369580．66732
0．404430．48436
0．405130．23621
0．558030．86068
0．946320．56099
0．873930．34550
0．335700．37046
0．683710．56102
0．857690．68072
0．777490．93503
0．193240．00363
0．830770．38292
0．128450．55287
0．187900．59722
0．899350．51082
0．458420．71618
0．762630．86926
0．171670．49226
0．515180．21827
0．435900．08930
0．246990．87472
0．547530．36888
0．299050．19059
0．432810．29414
0．486310．89676
0．675070．88858
0．657370．04718
0．101500．42848
0．308790．18680
0．790830．23646
0．915010．96103
0．252200．26621
0．564560．63753
0．577810．69625
0．880000．55782
26
3 アナログニューラルネットワークによる接触検出関
数を用いたタイリング問題の解法
3．1 概要
本章では，ニューラルネットワークの最適化問題に対する計算可能性を示す一
例としてタイリング問題を扱う．タイリング問題とは有限の升目上に隙間なくポ
リオミノを敷き詰めていく問題である．ポリオミノとは正方形の集合によって表
される多角形のことである．ポリオミノを用いたタイリング問題はこれまでに
も取り上げられてきた【57日60】．しかし，これらはすべて逐次的手法であり，文献
【10］により初めて並列的手法が用いられ，そこでは，確率的ニューラルネットワー
クを用いた最適化問題としてタイリング問題が扱われている．タイリング問題は
NP完全問題であり，文献【101では，実験に用いた問題のサイズが小さいにも関
わらず，正解への収束性はあまりよいものではなかった・その後，文献【17】【18】で
はさらに大きな問題として，ポリオミノの回転及び反転を考えないことを前提と
して，7×7の升目上で10個のポリオミノを敷き詰めるタイリング問題を解くこ
とに成功している．この間題は，約1．3×1014通りの候補から唯一解を求めるも
のであり非常に難しい問題である・しかし，【17日18］では，エネルギー関数の最小
値が最適解に対応していないという問題があった【20日23ト
一方，第2章で示したように，ニューラルネットワークを用いた最適化問題の
解法に関する研究としては，ホップフィールド等による巡回セールスマン問題の
近似解法がある【3】．しかし，TSPに代表される最適化問題のエネルギー関数は，
局所的収束の問題があり，必ずしも良好な結果が得られるとは限らない．そこで，
第2章では，比較的局所的収束に陥りにくい性質を持つ都市隣接性に基づく新し
いTSPのエネルギー関数を用い，比較的大きな規模の問題に対する準最適解を得
るアルゴリズムを提案した．
ここでは，第2章で用いた都市隣接性という考えを発展させ，タイリング問題
に応用する・つまり，タイリング問題のエネルギー関数【171【18】に対し，ポリオミ
ノの接触度を表す関数を新たに導入し，従来法で用いられたエネルギー関数を改
良する【23日21】【22ト さらに，従来法において用いられていたマキシマムニューロ
ンをアナログニューロンに変更して処理することを考えた．このことは，本来，存
在するかしないか，つまり，離散的な値しか持ち得ないポリオミノに対して，ア
ナログ量を許すことで，曖昧なタイリングを可能にし，局所解からの脱出を促す
ためである．提案アルゴリズムによれば，10×10の升目上に14個のポリオミノを
配置するタイリング問題を解くことができた．この間題の全候補は，約1．6×1024
通りであり，本アルゴリズムが従来法に比べて，より大きく複雑なタイリング間
27
題に対応できることが検証される．
3．2 従来法
刑 ＃2 ＃3 ＃4 ＃5
圏醒鼎殿圃
上蔀上下巨要
マーカーに対応したサイドボード
鵬 ＃7 ≠相 ＃9 ＃10
軒下旦仁∃匡］
7×7のニューラルアレイ上のマーカー
マーカーに対応したサイドボード
図3．1：10個のポリオミノとそのマーカー
まず，タイリング問題を解くための従来法（以下手法1）の並列アルゴリズムに
ついて説明する【17日18】．ここでは簡単のため，例題として7×7の升目上で10個
のポリオミノを配置するタイリング問題【17］【18］を扱う．手法1ではニューロンモ
デルとして（3．1）に示すマキシマムニューロンを用いている．
晦た ＝1iH毎＞O and 巧錘＝mα叫句た）
for
x＝11‥・1m and fory＝1，‥・，n
（3．1）
＝ 0 0therwise．
ここで，竹中・〃示はわた番目のニューロンの出力，入力をそれぞれ表している．
一つのポリオミノにつき，座標を表現するためのニューラルアレイと形を表現
するためのサイドボードを7×7の大きさでそれぞれ図3．1のように用意する．例
題を解くためには10×7×7のニューラルアレイが必要であり，また，サイド
ボード上のポリオミノをニューラルアレイ上のマーカーに写像させる手法をとっ
ている．これによりマーカーとなるニューロン一つで，ポリオミノの座標と形を
28
k一→
ニューロンの
サイドボード
三次元配列
孤立空間検出用
サイドボード
図3・2：マーカーのためのニューラルアレイ（左）とマーカーに関するサイドボー
ド（右）
表現できる・したがって，図3・2に示すような10×7×7の鞍上からなるニュー
ラルアレイと同様な大きさのl‰からなるサイドボードにより例題を解く・研
番目のニューロンの動作方程式は（3．2）のように与えられる．
−A（∑∑‰−1トβ（∑侮−1）
q＝lr＝l
q＝1
−CJ（卯毎＋伽（∑∑‰）
（3．2）
9＝lr＝1
ここで第一項はi番目のニューラルアレイ上にポリオミノを一つだけ発火させ
るための制約条件である．第二項はニューラルアレイを上から貫くことによって
マーカーが同じ場所に重ならないようにするための制約条件である．第三項はサ
イドボードを上から下まで貫くことによってポリオミノが重ならないようにする
ための目的条件である・ここでJ（五）はそれぞれのポリオミノの形を表しながら，
重複を検出するための関数であり次のように表される．
JH ＝∑（1㍍＋佗誹．1＋‰…＋‰＋2，た＋佗什2，叫）
9＝1
9≠1
29
●
●
（3．3）
●
J（10）＝ ∑（協＋‰直1＋塩．1，た＋塩川，叫）・
9＝1
9≠10
ここで佗fはサイドボードでの値を示し，恒，fはその座標を示す．マーカー
晦が発火したとき，それぞれの形に従い，β，土が決められ鳴f＝1となる．図
3．2において，11番目のサイドボードは孤立空間をなくすために用いられている．
ここでいう孤立空間とは次式で表される条件を満たすときである．
∑協＝0，∑‰＿1，た＝1，∑‰…＝1，
q＝1 9＝l
q＝1
∑堤が＿1＝1，肌d，∑堤が十1＝1・
9＝l
q＝1
このとき＃11を
喘小串＝咋lJ…＝札が＿1＝軋誹＋1＝1
とすることにより，孤立空間は消滅する・また，手法1では，（3．2）の第三項にお
いて−CJ（可と−CJ（卯毎をバランスよく使用することにより大域的最小値への
収束性を向上させている．第四項は局所的最小から退避し，大域的最小へ収束さ
せるための丘登りのための項である・関数ん匝）は∬＝0の場合，1となり，他の
場合は0となる．このような動作方程式を用いながら手法1は7×7のタイリン
グ問題を解いている．また，1．2節で示したように，ニューラルネットワークの動
作方程式は（1．4）のようにエネルギー関数の偏微分によって表されるため，手法1
のエネルギー関数は（3．4）のように導かれる．
β＝緒真裏Ⅵ町−1）2＋言責差（左侮−1）2
m
n
＋妄妾票差′（嘱一指ん（諾Ⅵ9r）2・
（3．4）
（3．4）を用いたアルゴリズムではタイリング問題の最適解において，ポリオミノ
の数だけ，つまり畑のニューロン出力侮だけが1となり，その他のニューロン
出力晦七の値は0となる・ところが，（3．4）の第二項はタイリング問題の最適解の
時点ではゼロとならず値を持つ．つまり，第二項は上層のmx几ニューラルアレ
イ上のすべての場所で各層に関するマーカーニューロンの重なりを制約している
30
ため，mXm個のニューロンが重複なく発火したときにゼロとなる項である．こ
れは上に挙げたタイリング問題の最適解と矛盾する．したがってこの最適化問題
において，正解が出現したとき，手法1ではエネルギー関数が最小とならない．
そこで，本研究では以上のような手法1の問題点である（3．4）で示されるエネル
ギー関数の第二項を取り除き，新たな目的条件を組み入れたエネルギー関数を提
案する．
3．3 提案手法
3．3．1接触検出関数を含むエネルギー関数とアナログニューラルネットワーク
本手法では，タイリング問題のエネルギー関数を次式のように新たに定義する．
β＝油差差Ⅵ町−1）2＋指差差′（略
＋言妾真裏g（略＋指差差侮（1瑚）・（3・5）
ここで，均七は研番目のニューロンの出力を表しており，第一項は第五番目の
ニューラルネットワークアレイ上にポリオミノを一つだけ発火させるための制約
条件である・第二項は（3．4）の第三項と同様にしてポリオミノが重ならないように
するための制約条件である・従って。柏‖まそれぞれ（3．4）と同様に表される．第
三項は各ポリオミノの他のポリオミノや外枠との接触状況を検出するための目的
条件である．すなわち，すべてのポリオミノが他のポリオミノや外枠と完全に接
したときに関数がゼロとなるように定義している．
図3．3（a）に示すように最適解ではすべてのポリオミノの周囲は他と接触する．
ここで接触検出関数タ（可‥（g（卯＝1，2，…，10）はそれぞれポリオミノの形状に
よって定義され，次式のように与えられる．
g（可＝C（五）一拍） （3．6）
ここでC（五日ま五番目のポリオミノの周囲の長さを示す（図3．3（b））．また，抑）
は五番目のポリオミノが他のポリオミノや外枠と接触しているか否かを検出する
関数であり，次式で定義される．
g（1）′＝∑（佐一1，た＋塩湖．1＋払出2
q＝1
＋佗州頼＋軋州組＋均，州頼
31
亮
（b）−『単位境界
この例題では▼n（i）＝12
国粋
（a）
図3．3：例題における最適解と接触検出関数
＋塩．2，頼2＋佗什3両l＋‰＋鋤
＋‰＋2，七一1＋‰…＿1＋塩，た＿1）
● （3．7）
g（10）′＝ ∑耽り，た＋‰＿埴十1＋堤が＋2
匹1
＋‰十1，軒2＋‰十2，仙＋‰十2，た
＋‰＋1，た＿1＋堤か1）・
ここで叱土は（3．4）と同様にサイドボードでの値を示し，恒，土はその座標を示す．
ここでのβ，fは各ポリオミノの周囲の座標によって決められる．また，第四項はア
ナログニューロンモデルを使用する上で必要となる，ニューロンの出力を二値
（0，1）に強制するための項である・ここで，重複検出関数J（i）と接触検出関数拍）
は，ポリオミノの面積や形状によってその最大値が大きく変化する．そこで本手
法では，ポリオミノの面積や形状によらず，各ポリオミノの重複及び接触の影響の
みをエネルギー関数へ反映させるために，重複検出関数及び接触検出関数を次式
のように正規化する．このことにより，エネルギー関数の係数β及びCを問題ご
とに大きく調節する必要がなくなる．
巧＝指差差等
（3．8）
32
電＝言畠票差等
（3．9）
ここでF（可は単位正方形を1としたポリオミノの面積である．これによりエネ
ルギー関数（3．5）は次式のように書き換えられる．
4÷′声量，′ 1、2．月÷貴さJ（小島
β
妄岩（謀叛r￣1）2＋書芸妄言
C（可
＋言妾票差旦欝＋指差差侮（1−侮）・
（3．10）
すべてのポリオミノが与えられた升目に重複なく配置され，かつ，すべてのポリオ
ミノが他のポリオミノまたは外枠と完全に接したとき（3．10）のエネルギー関数は
最小値ゼロとなる・この点から見ても，（3．10）は明らかに（3．4）とは異なる．
（1．4）に従ってわた番目のニューロンの動作方程式は次式のように与えられる．
仙b
df
−A（∑∑Ⅵ町−1）−β
q＝lr＝1
ーC
再川井
C（五）
J（i）晦た
F（可
一書（1−2侮）・ （3・11）
ここで，巧錘は研番目のニューロンの入力を表している．
更に，本手法ではニューロンの入出力関係において（3．1）の代わりに，（1．2）で与
えられるシグモイド関数を用いる．入出力関係にシグモイド関数を持つアナログ
ニューロンを用いることにより，入力値の非常に微細な変化がェネルギー関数に
反映されることになる．また，入出力関係のアナログ化に伴いサイドボードでの
アナログ値l‰はマーカーの和とした（図3・4）・これにより次のような効果がある．
手法1では入力値が最大のマーカーのみサイドボードに反映されるが，本手法で
＃6のアナログニコL一一ロンの配列
●
●
●
＃6のアナログサイドボード
●
●
■
■
■ ＝0．1 − ＝0．2
●
■
』
●
＃6の手法1におけるサイドボード
l■
●
●
■
●
●
●
●
ー ＝0．3 』『＝1．0
図3・4：ポリオミノのアナログ表現（例題の＃6）
33
はすべてのマーカー（図3．4（a））に対し，それぞれの出力値に対応するポリオミノ
がサイドボード上に配置（図3・4（b））され，その値は晦に加算される（図3・4（C））・
結果として，その場所に配置される可能性のあるすべてのポリオミノの影響がそ
の可能性の大きさに準じてネットワークの動作に反映されることになる．ここで，
可能性の大きさとはニューロンが持つ値の大きさのこと，つまり，大きな出力値を
持つニューロンほどその場所に配置される可能性が高いことを意味する．これに
対し，手法1では入力値が最大のマーカーのみ，つまり，その時点で最もその場所
に配置される可能性の高いポリオミノの影響のみがネットワークの動作に反映さ
れることになる．（図3．4（d））．
本手法では，アナログニューラルネットワークを用いているため，マキシマム
ニューラルネットワークを用いた一つのアレイ上に一つのニューロンしか発火さ
せない従来法に対し，ニューロンの出力値が微小な時点からその値がェネルギー
関数に反映されることになる．
3．3．2 最適化アルゴリズム
本手法では，基本的に，（3．11）を前進オイラー法により数値積分する手法を用
いている．以下に最適化アルゴリズムを示す．
StepO．初期設定
Stepl・ニューロンへの入力Uijkに乱数を入力
晦た＝α×RAⅣβJⅣαJJ招，た
（3．12）
Step2・（1・2）を基に出力値V；jkを算出
Step3・全てのl‰を初期化
Step4・マーカーに関係するl‰に出力値を加算
げV示＝α，喘た＝喘た＋瓜，
鶴頼1＝仏神＋α，
吋什1，た＝軋十1，た＋α，
軋．坤＝軋＋2，た＋α，
34
軋十2，た＝喘＋2，た＋α，
喘＋2，頼1＝喘＋2両1＋α
（3．13）
Step5・（3・11）により動作方程式dthjk／dtを算出
If（iter modlO）＜w then（iterは反復回数）
−A（∑∑‰−1トβ
J（i）鞍上
9＝lr＝1
−C g（卯毎
C（可
ダ（五）
一書（1−2侮）・
（3．11）
−A（∑∑恥−1）一
寸＝lr＝l
ーC豊一計−2侮）・
（3．14）
Step6・前進オイラー法に従いUijk（iter＋1）を算出
（句拍fer＋1）＝【句拍fer）＋△
d巧錘（記er）
df
（3．15）
Step7．入力値の飽和値の設定
If Uijk（iter＋1）＞ULM then Uijk（iter）＝坊Ⅶ3
If Uijk（iter＋1）＜ULin then晦k（ifer）＝tLin
ここで，坊mJ＝1．0，仇血＝−1．0．
Step8・定常状態になれば（E＝0）Steplへ
他は時刻士を△f（＝10￣2）増加させる
Step9．反復回数がTを越えたら終了．他はStep2．へ
ここで，Step・1におけるニューロンへの入力thjkに対する初期値は【17］［181に従っ
て経験的に決めた．また，Step5．では，局所解からの脱出を可能にするために，パ
ラメータ山を導入し，反復回数に応じて動作方程式を変化させる処理【17】【181を用
いた・つまり，（3．11）のダイナミクスでは，重複及び接触検出関数，J（可及び拍）
にニューロンの出力Ⅵ沖をかけることで，関数のネットワークへの影響を，それぞ
れのポリオミノの出現の可能性に応じて変化させている．これに対し，（3．14）の
ダイナミクスでは，重複及び接触検出関数を直接ネットワークに反映させている．
35
例3
図3．5：例題
3．4 シミュレーション結果及び考察
3．4．1 シミュレーション結果
最適解への収束性を調べるため，図3．5に示す5つの各例題について100回以上
のシミュレーションを行った．
表3．1：シミュレーション結果
山＝2，A＝2．0，β＝1．0，C＝1．0，か＝1．0，
仇肌＝1．0，仇血＝−1．0，α＝1．0×10￣6
例題
問題 の 大 き さ
複雑度
平均反復回数
手法 1
本 手法
1
10 × 7 × 7
1．
3 ×10 14
92 2
10 0 ％
100 ％
2
1 1 ×8 × 8
4．
1 ×10 16
57 7
3
12 ×8 × 8
5．
2 × 10 18
58 6
4
12 ×9 × 9
2．
2 × 10 19
7 14
5
14 × 10 × 10
1．
6 × 1024
646
ー
−
−
−
100 ％
100 ％
100 ％
10 0 ％
結果を表3．1に示す．ここで表3．1の複雑度とは回転と反転を除いた起こりうる
配置パターンの総和である．つまり，ここで述べている複雑度とは，すべてのポ
リオミノの升目上への配置可能な場所の場合の数を意味している．しかし，実際
のタイリング問題の難しさはポリオミノの形状及びその配置によっても大きく影
響されると考えられる．このようなタイリング問題の難しさに関する考察はここ
では行っていない．また，ポリオミノの回転を考慮に入れた場合，考えられるポ
リオミノの方向は4方向であるため，回転を考慮しない場合の複雑度の4乗とな
り，さらに，ポリオミノの反転を考慮した場合はその2乗となる．回転や反転を
36
考慮すると，複雑度の非常に大きな問題となるため，ここでは，【17】【18】と同様
に，回転と反転は考慮に入れない．
表3・1に示すように，ニューロンへの入力鞍上に対する初期値を（3．12）に従って
乱数で与えたにも関わらず，すべての例題に対して，局所最小値に捕まることなく
最適解に収束した．さらに，手法1と比較すると，例題2から例題5に関して手法1
でシミュレーションを行った場合，正解を得ることができなかった．例題1に関し
ては，手法1を用いて，（3．4）における係数をA＝1．0，β＝1．0，C＝1．0，か＝1．0と
し，U＝7を用いた場合の平均反復回数が930回であったのに対し，提案手法では
平均反復回数が922回であり，正解を得るまでの反復回数はほぼ同じであった．こ
こで用いたエネルギー関数の各係数は経験的に最も速く収束したシミュレーショ
ンから得たものである．以上のことから，本手法は，従来法に比べ，より大きな
問題に対しても対処可能であるとことが確認された．
3．4．2 エネルギー関数の各係数に関する考察
表3・2：平均反復回数（収束率）の比較
A＝1．0，β＝1．0，C＝1．0，か＝0．0，
坊mJ＝1．0，仇血＝−1．0，α＝1．0×10￣6
（
J
0
1
2
3
4
例題 1
例題2
例題3
例題4
例題 5
6586 （
100％） 4741 （
100％） 6002 （
100％） 7060 （
100％）
−（
0％）
5117 （
100％） 4038 （
100％） 4933 （
100％） 4966 （
100％） 5264 （
100％）
3957 （
100％） 3805 （
100％） 4142 （
100％） 4509 （
100％） 4442 （
100％）
3666 （
100％） 3683 （
100％） 3997 （
100％） 3877 （
100％） 4118 （
100％）
3736 （
100％）
5
ー（
0％）
ー（
0％）
6
一（
0％）
≧7
−（
0％）
ー（
0％）
−（
0％）
−（
0％）
−（
0％）
−（
0％）
3805 （
100％） 3928 （
100％）
−（
0％）
3886 （
100％） 9939 （
100％）
ー（
0％）
−（
0％）
−（
0％）
3728 （
100％） 4037 （
100％）
ここではまず，【17］【18】従ってエネルギー関数の第一，二，三項の係数を正規化して
1．0とし，第四項の影響をなくすためにその係数を0．0，つまりA＝1．0，β＝1．0，
C＝1．0，か＝0．0とし，さらにUを変化させた場合のシミュレーションを行う．
シミュレーション結果を表3．2に示す．表3．2より，第一項及び第四項は収束速度
に大きく関与していることがわかる・また，初期値α×RAⅣβ（α＝1．0×10−6）
37
表3・3：初期値設定においてα＝1．0×10−2とした場合のシミュレーション結果
A＝2．0，β＝1．0，C＝1．0，か＝1．0，
坊Ⅶ∬＝1．0，仇血＝−1．0，α＝1．0×10￣2
（
J
0
平均反復回数 （
収束率）
1
684 （
69％）
2
820 （
79％）
3
842 （
13％）
4
978 （
2％）
5
8 13 （
4％）
≧6
−（
0％）
62 1 （
53％）
に対しては，1∼3の範囲の山を用いることで，すべての例題で正解を得るこ
とができた・初期値依存性について調べるために，例題1に対して，初期値を
α×RAⅣβ（α＝1．0×10￣2）とした場合のシミュレーション結果を表3．3に示す．
表3・3より，ゼロ近傍から初期値を離すと，山の値により，最適解へ収束する割合
が変化していることがわかる．
次に，第二項，第三項，つまり重複検出関数，接触検出関数のネットワーク動作
への影響を調べるために例題1に対して係数β，Cを0．1刻みで変化させてシミュ
レーションを行った結果，正解を得ることができた係数の範囲とその時の平均反
復回数を表別に示す・これらの項は（3．8）及び（3．9）によりポリオミノの面積及び
形状に対して正規化されているので，係数β及びCを変化させることにより重複
検出関数及び接触検出関数の影響を直接調べることができる．表3．4より，接触検
出関数の係数Cの方が重複検出関数の係数βよりも自由度が少ないことがわかる．
表3．4：係数β及びCの関係
山＝2，A＝1・0，か＝0．0，坊偶∬＝1．0，仇血＝−1．0，α＝1．0×10￣6
係数 β
係数 C
平均反復回数
係数 βを変化 させた場合
0．
6 ∼3．
9
1．
0
4335
係数 C を変化 させた場合
1．
0
0．
8 ∼ 1．
2
5165
38
また，表3．1，表3．2に共通して各例題の複雑度が増していっても平均反復回数
が増加しているわけではなく，複雑度の桁数と比較すれば，平均反復回数はほぼ
同程度であると考えられる．これが，ニューラルネットワークの並列性によるも
のなのか，それとも反復回数が複雑度ではなく，ポリオミノの形状及び配置場所
に依存したタイリング問題の難しさにより変化するものなのかに関する考察は，
難しさの定義等を含めて，今後の課題としたい．
3．4．3 ネットワークの過渡遷移に関する考察
シミュレーション結果よりポリオミノの非常に興味深い過渡的な遷移が確認さ
れた・ここではネットワークの過渡遷移に対する考察を行う．例題1に対する過
渡遷移の一例を図3．6に示す．
ここで，ポリオミノの線が太く色が濃い方がマーカーの出力値が大きい事を示
す．また，同じポリオミノが複数存在するのは，アナログニューラルネットワー
クを用いているため，値を持ったマーカーニューロンが個々のポリオミノに対し
て複数個存在するためである．図3．6において，注目すべきことは枠周りからポリ
オミノが定着し始め，さらには定着しはじめたポリオミノが他のポリオミノとの
競合により抑制されたりすることである．これはアナログニューラルネットワー
クと接触検出関数の組み合わせの効果と考えられる．つまり，接触検出関数が導
入されたことにより，棒型や鍵型，コの字型など枠と接触可能な部分の多い，比
較的枠と接触しやすいポリオミノが図3．6では250反復時までに定着している．そ
してその後，新たに形作られた枠（定着したポリオミノによって形成される）に
応じてその形と接触しやすいポリオミノが定着している．また，アナログニュー
ラルネットワークの効果は例えば．図3．6の右上に出現する正方形型のポリオミノ
の動作に見られる．正方形のポリオミノが一度，定着しそうになりながらも，棒
型のポリオミノが競合するように出現したことにより，接触検出関数の影響で最
終的にはより最適な場所に移動している．これはアナログニューラルネットワー
クがその場所に配置可能なすべてのポリオミノの影響をネットワーク動作に反映
させた結果である．これらの現象は他の例題についても同様に観測された．
結果として，本手法では5つの例題に対し，ゼロ近傍の初期値に対しては，最
適解へ100％収束することを確認した．ただし，回転と反転が許されない条件に
おいて，図3．5に示す解が唯一解であるという保証はない．しかし，本研究では
図3．5に示す解以外の最適解は検出されなかった．また，本手法が手法1に比べ，
より大きく複雑なタイリング問題に対し有効な手法であることがシミュレーショ
ンにより示された．問題の規模（チェッカーボードの広さ，ポリオミノの数）が
増加した場合，必要なニューロン数が増加する．この場合，本手法を用いた場合
でも，局所解に陥り，最適解が求まらないことがある．更に大きな問題に対して
39
0 ●1−6 ●0＝
ケ ●0＝ 匡≡ヨ
099＝凝固彰習
0ウ
圃−α儲蜜認軒α1番圃：9●g図
9・0−エ・0＝ ■
C ●0＝ Eコ
l ●0＝
Z ●0＝
9 ●0＝ 圏
9・0＝ −
009＝凝固彰習 09g＝凝固箪笥
＝
U
n
＿J
00g＝凝回彰習
＝
lt
■
；
‘
≡
ン
・
＝
き
：
…
…
‥
”
■
“l
1
l＿
」
09Z＝凝固梨習
‡
≡
l
00Z＝凝回影習 09t＝凝固詫習
00l＝凝回詫召
は，エネルギー関数，パラメータの選び方などを含めての検討が必要になる．
3．5 まとめ
本章では，ニューラルネットワークに基づくタイリング問題の解法について検
討した・ここでは，接触検出関数を含む新たなェネルギー関数を定義し，これを
アナログニューラルネットワークに対して適用することで，従来法よりも優れた
能力を有する解法を提案した．また，幾つかの例題を用い，提案手法の最適解へ
の収束性についてシミュレーションにより調査した．その結果，本手法が従来法
では試みられていなかった比較的大きく複雑なタイリング問題に対しても有効で
あることが検証された．
今後の課題として，ポリオミノの形状及びその配置場所によって決定されるタ
イリング問題の難しさと提案手法の関係に対する考察，また，ポリオミノの回転や
反転を考慮した場合を含め，問題サイズが大型化した場合のエネルギー関数及び，
そのパラメータの選び方に関する考察が挙げられる．さらに，山のネットワークの
ダイナミクスへの影響に関しても詳しく調査が必要である．
41
4 ホップフィールド型ニューラルネットワークによる
ディジタル順序回路
4．1 概要
本論文ではこれまで，組み合わせ最適化問題に対するニューラルネットワーク
の適用について述べてきた．一方，ニューロンの入出力特性，つまり，シグモイ
ド関数（1．2）が飽和特性を持つということを利用して，ホップフィールド型ニュー
ラルネットワークをアナログーディジタル（AD）変換器，直交変換器等のディジタ
ル信号処理プロセッサに応用する研究が盛んに行われている【4】【24日33トこれら
のプロセッサはニューラルネットワークの持つ並列性により，従来の設計技術に
よる回路よりも高速な信号処理が期待されている．また，ニューラルネットワー
クはアナログ回路により設計できるため，従来のディジタル回路による設計より
もチップ面積の小さなプロセッサを実現することが可能である．これらの点から，
近年，組み合わせ論理回路への応用として，基本ゲート回路，ディジタル加算器，
及び，乗算器【35］【361が設計された．このような研究は，第2，3章で扱ってきた
ような最適化問題の求解法としてニューラルネットワークを利用する研究とは異
なり，その最適化の能力を応用し，ネットワークがそれぞれのプロセッサの機能
を持つように設計することが目的である．このため，それぞれの機能を最適化問
題として定式化し，エネルギー関数を導出する必要がある．このエネルギー関数
からネットワークを構成することで最適化問題の解が目的とする回路の出力とな
り，プロセッサが実現される．
本研究では，ホップフィールド型ニューラルネットワークのディジタル信号処理
プロセッサへの応用として，フィードバックを有するディジタル順序回路の構成
法を提案する・提案手法は，まず基本となるゲート回路やラッチ回路の論理関数
を最適化問題として定式化し，ネットワークのエネルギー関数を構成する．この
エネルギー関数から大域収束性を有するゲート回路やラッチ回路を設計する．ま
た，提案手法と従来法の比較のために，従来，設計されたニューラルネットワー
ク加算器とは異なる大域収束性を持っ全加算器の設計，及びそれらを組み合わせ
たリプルキャリー型加算器の構成を行い，本手法の有効性を示す．
さらに，これら設計されたゲート回路やラッチ回路を従来のディジタル回路の
設計技術を用いて組み合わせることにより，フリップ・フロップを，更にはフリッ
プ・フロップの組合せによりシフト・レジスタ及び非同期式カウンタを構成する．
これらの構成された回路が正確に動作することはシミュレーションにより確認さ
れる・また，いくつかの回路については実際にアナログ電子回路でブレッドボー
ド上に実装しその動作を確認する．
42
4．2 従来法によるニューラルネットワーク論理積回路の設計
論理積を行うニューラルネットワークを構成する場合，論理積を最適化問題に
置き換えて定式化し，エネルギー関数を構成する必要がある．ニューラルネット
ワークは，エネルギー関数を時間とともに常に減少させる方向に動作するので，
エネルギー関数が最小になったときのニューロンの状態が論理積の結果に等しく
なるようにすればよい．
2つの入力Aとβ，出力Vの論理積を考えると，回路の動作は次のような目的
条件と制約条件の最適化問題として定式化することができる【35】【36】．
＜目的条件＞
minlβ（A＋β）−Vl
（4．1）
＜制約条件＞
minlV（1−V）】
（4．2）
（4・1）は目的とする条件を表わす．例えば，β＝0．4の場合，この式が最適化さ
れると入力Aとβが両方とも1の場合だけ出力が0．5より大きく，それ以外の場
合には0・5より小さくなり，しきい値を0．5にすることにより論理積が実現できる
ことがわかる・また，（4．2）は出力を0または1のディジタル値にするための条件
である・エネルギー関数を構成するために（4．1）と（4．2）は次式に置き換えられる．
El＝（β（A＋β上り2 （4．3）
昆＝Ⅴ（1−Ⅴ） （4．4）
（4・3）を2で割り，式（4．4）と加え合わせて定数項を除くと，論理積用のエネルギー
β＝一芸V2−（β（山βト岬 （4．5）
このエネルギー関数のβ＝0．4の場合のグラフを図4．1に示す．図4．1から，ニュー
ロンアンプの出力に初期値として0．5を与えれば，入力Aとβがともに0，及び，
どちらかが0の場合には，ネットワークのエネルギーが減少する方向は出力Vが0
になる方向となることが分かる．また，入力Aとβがともに1の場合には，ネッ
トワークのエネルギーが減少する方向は出力Vが1になる方向となる．従って，初
期値としてⅤ＝0・5【Ⅴ］（即ちニューロンへの入力祝＝0【VDを与えれば，ニューラ
ルネットワークのエネルギー最小化の原理によって正しく論理積を行うことがわ
かる．
（1．3）と（4．5）を比較すると
43
図4．1：従来法による論理積回路のエネルギー関数
7㌢＝1
（4．6）
および
J ＝ βA＋ββ−1
＝ n・A＋7も・β＋弟・鴨
が導かれる．よって，回路の各パラメータが以下のように定まる．
符＝乃＝1，㍍＝了も＝β，Ⅵ＝−1
（4．9）
回路図を図4．2に示す．
β＝0．4の場合の回路の動作をシミュレーションで検証した．シミュレーション
結果を図4・3に示す・ここで，本章におけるシミュレーションは動作方程式（1．1）
を後退オイラー法を用いて数値積分することにより行った．図より，出力Vの初
期値を0．5にした場合，論理積が正確に動作していることが確認できる．
44
図4．2：従来法によるニューラルネットワーク論理積回路
InputA
OutputV
InputB
1．
1．
こ：：［＿＿」
0． L＿」0．
1．0
1．
0．0
0．
L
L
L
1．0
1．
0．0
0．
1．0
1．
0．0
0．
夏＝＝L
L
Ll
1．
0．
』＝」
1．
0． 』＝＝＝＝＝」
1．
に＝」 に二＝」
0．
図4．3：従来法によるニューラルネットワーク論理積回路の解析結果
45
4．3 大域収束性を持つニューラルネットワークディジタル回路の
設計
前節で述べた設計手法では，ニューロンアンプの出力の初期値を0．5として動
作させる必要がある．従って，設計できる回路が時系列の入力を扱わない組み合
わせ回路に限定される・時系列の入力を扱う回路や順序回路を設計する場合には，
次時刻の入力が定まれば現時刻の状態から出発して次時刻の状態へ一意に収束す
るようなエネルギー関数を構成する必要がある．本研究では，これを満たすエネ
ルギー関数を大域収束性を持っェネルギー関数と呼ぶ．本研究では，論理関数か
ら大域収束性を持つエネルギー関数を導出し，ニューラルネットワークディジタ
ル順序回路を実現する．
4．3．1 論理積回路の設計
2つの入力Aとβ，出力Vの論理積を示す論理関数は
Ⅴ＝A・β
（4．10）
である・（4．10）を次のような目的条件の最適化問題として定式化する．
＜目的条件＞
minlA・β−Vl
（4．11）
また，出力を2値化する制約条件は
＜制約条件＞
minlV（1−nl
（4．12）
となる・これらの条件を最適化するニューラルネットワークを構成すれば，その
ネットワークは論理積回路と同じ動作をする．（4．11），（4．12）を組み合わせてエネ
ルギー関数を構成するために，（4．11），（4．12）を次式のように変更する．
El＝（A・β−V）2 （4．13）
筏＝Ⅴ（1−Ⅴ） （4．14）
（4．13）を2で割り，（4．14）と加え合わせて定数項を除くと，論理積用のエネルギー
関数が得られる．
（4．15）
β＝一芸v2−（A・β−1）
46
山岳しぎ山
図4．4：論理積回路のエネルギー関数
このエネルギー関数を図4．4に示す．この図からニューロンに初期値としてどのよ
うな値を与えても，ニューラルネットワークのエネルギー最小化の原理によって
正しく論理積を行うことがわかる．言い換えれば，順序回路のように前時刻の値
を初期値として回路が動作する場合でも正しく論理積を行うことが証明される．
例えば，時刻＝こおいて論理積回路の出力値が0であったとする．そして次時刻
f＋1で入力A，βともに1が入力されたならば，時刻fにおける出力値0を初期
値として回路は動作し，出力値1の状態に遷移することになる．本研究では，前
時刻の出力状態から現時刻の状態へ正しく状態遷移をする回路，即ち，大域収束
するエネルギー関数を持つ回路を大域収束性を持つ回路と呼ぶ．
（1．3）と（4．15）を比較すると
ち＝1
（4．16）
および
J ＝ A・β−1
＝ 九・β＋乃・鴨
が導かれる．よって，回路の各パラメータが以下のように定まる．
ち＝乃＝1，㍍＝A，鴨＝−1
47
（4．19）
図4．5：論理積回路
回路図を図4．5に示す．ここで，コンダクタンスn＝Aは入力Aの値によってそ
の値が変化する・即ち，孤は入力Aが0【Ⅴ】のときに抵抗値∞【n】（0【針1］）となり，
入力Aが1【V】のときに抵抗値lln】（1【n−1】）となる．この非線形抵抗は電圧によっ
てon，0仔するスイッチと線形抵抗R＝1【n】を直列につなぐことによって実現す
ることができる・スイッチは制御信号の電圧値1【Ⅴ】のときonとなり，0【V】のと
き0仔となればよいので理想的なMOSトランジスタにより実現できる．この非線
形抵抗を図4．6に示す．
図4．5のネットワークの動作に対するシミュレーションを行った．前節で扱った
論理積回路は大域収束性を持たないので，正しい動作を得るにはⅤ＝0．5に初期
値を設定しなければならなく，時系列の入力に対する動作の保証ができなかった．
図4．5の回路は，その大域収束性から時系列の入力に対しても正しい動作が得られ
る．回路の動作をシミュレーションにより検証した．シミュレーション結果を図
4．7に示す．また，既存のアナログ素子によるブレッドボード上への実装を行った．
その実験結果を図4．8に示す．これらの結果から，我々が提案したホップフィール
ド型ニューラルネットワークによる大域収束性を持つ論理積回路が正確に動作す
ることが確認できる．
48
node
node
nodea
．−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−●−−−−−l
図4．6：非線形抵抗
1AO
lβ01VO
100 200 300 400 500［nsec］
図4．7：論理積回路のシミュレーション結果
49
09
￥割増￥α翳回教諺豊：9●中国
4．3．2 Dラッチ回路の設計
Dラッチの論理関数は次式のように定義される．
Q叶1＝e・Qれ＋C・β （4．20）
ここで，Qn，Qれ十1は現状態，次状態の出力を表し，C，βはクロック及び入力を
示す・本研究では，入力，出力値は，1または0の2値表示であるので，e＝1−C
とおいて論理関数を変形する．
Q叶1＝（1−C）・Qn＋C・β （4．21）
（4・21）より，Dラッチの動作は次のような目的条件の最適化問題として定式化さ
れる．
＜目的条件＞
minI（1−C）・Qn＋C・D−Qn＋1f （4．22）
しかし，ホップフィールド型ニューラルネットワークは現状態の出力仇を保持
する機能を持たないので，Qnを目的条件の中に入れることは適当ではない．そこ
で，目的条件からQnを消去する方法を以下に示す．
目的条件をクロックCを基準にして表すと
C＝0 のとき m叫仇一々叶ll
C＝1のとき m叫か−Q叶11
C＝0（記憶）の場合は，現状態と次状態は同一である．即ち，現状態，次状態のエネ
ルギー関数も等しい・従って，C＝0の時には回路の状態は遷移せず，同一状態を
保つ・これは（4・23）において常にQn＝Q叶lが成立する時，エネルギーが最小であ
ることを示す・一方，C＝1の場合には（4．24）より次状態の出力Q叶1は現状態の出
力Qnに依存しないことが分かる・これは（4．24）においてはQnをDon，tcare（￠）と
して扱って良いことを意味する・以上の理由より，（4．22）中で常にQn＝Q叶1＝Q
とする事が可能である．
この結果，（4．22）は次のように書き換えられる．
＜目的条件＞
minトC・Q＋C・pl
（4．25）
また，出力を2値化する制約条件は
＜制約条件＞
51
m叫Q（1−Q）】 （4．26）
となる・（4．25），（4．26）はエネルギー関数を構成するために次式に書き換えられる．
β1＝（−C・Q＋C・β）2 （4．27）
筏＝Q（1−Q） （4．28）
（4．27）を2で割り，（4．28）と加え合わせて定数項を除くとDラッチ用のエネルギー
β＝一芸（2−C）Q2−（C・β一明 （4・29）
このエネルギー関数を図4．9に示す．この図から，次状態の入力C，かが定まれば，
エネルギー最小化の原理に従い，回路の出力Qは現状態の値Qnから正しい次状
態の値Q叶1へ遷移することがわかる．
山岳LOuu
1
0utputQ
図4．9：Dラッチ回路のエネルギー関数
（1．3）と（4．29）を比較すると
乃＝2−C
（4．30）
52
および
J ＝ C・上）−1
＝ 花・β＋茄・鴨
が導かれる．よって，回路の各パラメータが以下のように定まる．
乃＝2−C，了も＝C，苅＝1，％＝−1
（4．33）
これらのパラメータをもとに構成された回路を図4．10に示す．
図4．10：Dラッチ回路
コンダクタンス符，花はクロックCによってその値が変化する非線形抵抗であ
る・花についてはC＝1【Ⅴ】のときに花＝1【n￣1】（抵抗値は1【n】），C＝0【Ⅴ］の
ときに花＝0【n￣11（抵抗値は∞【n】）となるので，論理積における非線形コンダ
クタンスの㌔（図4・6）と同様に，クロックCを制御信号とするスイッチと，1【n］
の抵抗で構成することができる・符については，乃＝2−Cより，2つのコンダ
クタンスれ＝2と筑＝−Cの並列コンダクタンスとして構成できる．ここで，シ
ナプス結合荷重における負の値のコンダクタンスは正負を反転したニューロンア
ンプを用いて実現されることを考慮すると，コンダクタンスれ＝2と7も＝Cを
図4・11の様に接続することにより符が構成できる．
この回路の動作をシミュレーションにより検証した，シミュレーション結果を
図4．12に示す．時系列の入力に対して正しくかラッチの動作をしていることが確
53
認できる．また，ブレッドボード上への実装を行いその動作検証を行った．実験
結果を図4．13に示す．
54
図4・11：非線形コンダクタンス乃
0 100 200 300 400 500［nsec］
図4．12：Dラッチ回路のシミュレーション結果
55
り頂
喋斐鎧嫌e壇瓦かホ1
卜C︰巴．寸区
4．3．3 全加算器の設計
ここでは，提案手法と従来法との比較のため，大域収束性を持つ全加算器を設
計し，提案手法の有効性を示す．A，βを入力，Gnを下段からの桁上がりビット，
方を和，‰を桁上げビットとすると，全加算器の論理関数は次のように与えら
れる．
Å・点・Gn＋A・β・Gn＋A・β・Gn＋A・β・Gれ
A＋β＋Gn−2A・β−2A・G几
−2β・Gn＋4A・β・Gn，
G f＝A・β＋A・Gn＋β・Gn，
ここで，A＝1−A，点＝1−β，an＝1−G凡とする．
これまでと同様に，（4．34），（4．35）は次のような目的条件に定式化される．
＜目的条件＞
minlA＋β＋Gn−2A・β−2A・Gn
−2β・G托＋4A・β・Gn一利，
minlA・β＋A・Gn＋β・Gれ−C f卜
また，出力を2値化するための制約条件は次のように与えられる．
＜制約条件＞
min げ（1−g）l
minlG f（1−㍍）l
これらの条件から，全加算器のエネルギー関数は次式のようになる．
毎＝一芸∫2−（A＋β＋Gn−2A・β−2A・Gn
−2β・Gn＋4A・β・Gn−1）ぶ，
助mt一芸弘一（A・β＋A・G几＋β・Gn−1）G血
全加算器のエネルギー関数を図4．14，4．15に示す．これら図から，全加算器が時
系列の入力に対して正確に動作することがわかる．
（1．3）と（4．40）および（4．41）比較することにより，全加算器を設計することがで
きる．シミュレーション結果を図4．16に示す．また，全加算器を3段つなげた3
ビットリプルキャリー型加算器のシミュレーション結果を図4．17に示す．これら
の結果から，我々が提案した設計手法が単純なゲート回路やラッチ回路だけでは
なく，より大きな規模の回路に対しても有効であることが確認できる．
57
Energyち
1
0utputS
図4・14：全加算器のエネルギー関数（ぶ）
Energyも鵬
1
0utputq。t
図4・15‥全加算器のエネルギー関数（G血）
58
A
β
□
0 100 200 300 400 500［nsec］
図4．16：全加算器のシミュレーション結果
59
Ao
Al
A2
β0
β1
0100 200 300 400 閣。。］
図4．17：3ビットリプルキャリー型加算器のシミュレーション結果
60
4．4 ディジタル順序回路の構成
4．4．1 Dフリップ・フロツプの構成
ここでは，前節で設計した大域収束性を持つDラッチ回路及びゲート回路を組
み合わせてフリップ・フロツプを構成する．Dラッチ回路によるレーシングを避け
るため，ラッチを2つ組合せ，前段のラッチ（主ラッチ）にクロックCを，後段の
ラッチ（従ラッチ）に反転クロックを入力して，マスタースレーブ型Dフリップ・
フロツプを構成する．回路図を図4．18に示す．
Master
Slave
Cell
Cell
図4．18：Dフリップ・フロツプ
ここで，従ラッチには反転クロックが入力されるため，従ラッチを構成するD
ラッチの非線形抵抗符，策は反転クロックにより制御される・
この回路の動作をシミュレーションにより検証した．シミュレーション結果を
図4．19に示す．図より，時系列入力に対して，ダウンエッジトリガ型マスタスレー
ブDフリップ・フロツプの動作をしていることが確認できる．また，前節で実装
したDラッチを2個用いて，アナログ素子によるDフリップ・フロツプを構成し
た．その実験結果を図4．20に示す．図より，Dフリップ・フロツプとして正確に
動作していることが確認できる．
61
＿D
図4．19：Dフリップ・フロツプのシミュレーション結果
図4．20：Dフリップ・フロツプの実験結果
62
4．4．2 シフトレジスタの構成
シフトレジスタは図4．21のようにDフリップ・フロツプを従属接続することに
よって構成できる．ここでは，4ビットシフトレジスタを構成した．この回路の
動作をシミュレーションにより検証した．シミュレーション結果を図4．22に示す．
時系列の入力に対して，シフトレジスタとして正確に動作していることが確認で
きる．
4．4．3 非同期式カウンタの構成
非同期式カウンタはTフリップ・フロツプを従属接続することで構成できる．
図4．23にTフリップ・フロップを，図4．24に非同期式カウンタの構成図を示す．
ここでは，4ビット非同期式カウンタを設計し，そのシミュレーションを行っ
た．シミュレーション結果を図4．25に示す．図より，4ビット非同期式カウンタ
として正確に動作していることが確認できる．
63
D
N Mo s。 N
l q 。 N l N
n N
q l
n
q m
図4．21：シフトレジスタ
Qo
Ql
十 三 ．
「叫ヰ一十十一十小十十叶や十十一一十十十十十十本十十十十十十十一幅十十
Q2
Q3「 ． 「 ．＿
0 100 200 300 400 500 600［nsec］
図4．22：4ビットシフトレジスタのシミュレーション結果
64
Master slave Inverter
Cell Cell Cell
図4．23：Tフリップ・フロツプ
65
ql
Qo
l c●皿 Cd
＼
qn
c鵬 ノ
、．．＿−−−−−−−−−−−−．／
図4．24：非同期式カウンタ
Q2「 「￣￣ ￣￣￣「＿ † L
Q3「∴ 日．日．仁1．1．．．」
0 500 1000 1500［nsec］
図4．25：4ビット非同期式カウンタのシミュレーション結果
66
4．5 まとめ
本章では，ホップフィールド型ニューラルネットワークの応用として，ディジ
タル順序回路を構成し，その動作を検証した．また，いくつかの回路については
アナログ素子によりブレッドボード上へ実装し，その動作確認を行った．本研究
では，順序回路を設計するにあたり，論理関数を最適化問題に置き換えて定式化
し，大域収束するエネルギー関数を構成する手法を提案した．本手法による設計
例として，ゲート回路，ラッチ回路及び全加算器を設計した．つまり，提案手法
を用いれば，ゲート回路やラッチ回路などの基本的な回路のみではなく，全加算
器などの比較的大きな規模のディジタル回路の設計も行うことができる．ニュー
ラルネットワークディジタル順序回路の特徴は回路全体が並列に動作するため，
従来のディジタル回路に比べて，高速な演算が可能である．つまり，回路の論理
関数をネットワークのエネルギー関数に変換できれば，ディジタルゲートを用い
て同回路を構成する場合と比べ，高速な回路を実現することができる．
また，本研究で設計した大域収束性を持つゲート回路やラッチ回路を組み合わ
せてフリップ・フロツプ及びシフト・レジスタを構成し，シミュレーションによ
りそれらの動作を確認した．ただし，これらの回路はゲート回路やラッチ回路を
従来のディジタル設計技術に基づいて機能的に組み合わせることにより構成され
ているので，ネットワーク全体のエネルギー関数の大域収束性を証明することが
できない．このため，ゲート回路やラッチ回路を組み合わせて構成された順序回
路を設計する場合，その動作はシミュレーションにより確認しなければならない．
本章ではニューラルネットワークディジタル順序回路の設計例として，Dラッ
チ回路を取り上げ，その組み合わせで，いくつかのディジタル順序回路を構成し
た．一方，SRラッチ回路も同様な設計手法を用いて構成することができる．つ
まり，SRラッチの論理関数から大域収束性を持つエネルギー関数を構成するこ
とができる．また，SRラッチ回路を組み合わせることで，いくつかのディジタル
順序回路を構成することができる【38】【40】において確認することができる．
67
5 リカレントニューラルネットワークによるディジタ
ル順序回路の設計
5．1 概要
近年，ニューラルネットワークの応用として静的なパターン認識ばかりでなく
動的な時系列パターンの扱いが重要になりつつある【49】【47】【48】・時系列パターン
を扱うためにはいくつかの方法がある．入力層にディレーを設けて時系列パター
ンを空間的パターンに変換してから階層型ネットワークに入力して学習させる方
法【50】やディレー素子をフィードフォワード結合に挿入したTimeDelayNeural
Networkl51］に時系列パターンを学習させる方法がある．また，リカレントニュー
ラルネットワークを用いてカオス等の時系列信号を学習させる研究（例えば【521
等）も近年，注目を浴びている．一方，バイナリーリカレントニューラルネット
ワークを用いて有限状態マシーンを構成しようという試みも近年なされている
【53日54ト しかし，これらの学習法は全て勾配法に基づいており，学習を収束させ
る為には非常に多くの反復が必要である．
第4章では，これら時系列信号処理へのアプローチとしてホップフィールドネッ
トワークを用いたディジタル順序回路の設計を試みた．その中で，時系列入力に
対して大域収束性を持つ，いくつかのゲートおよびラッチ回路（ニューロン）を設
計した．さらに，これらの回路を組み合わせていくつかのディジタル順序回路を
構成した．しかし，ここで提案したディジタル順序回路は従来のディジタル回路
の構成法を基に，我々が提案したゲートおよびラッチニューロンを組み合わせた
回路にすぎなかった．このため，その動作を確認するためにはシミュレーション
を行う必要があった．
一方，近年，空間パターンのバイナリー写像に対して，勾配法に基づくものと
は異なる学習則が提案された【55】【56】．これらの学習則は学習収束のための反復
が必要なく，非常に高速なアルゴリズムである．文献【55】では，3層バイナリー
フィードフォワードニューラルネットワーク（3LBFNN）に対して，学習パターン
の空間幾何に基づいた学習則，eXpand−and−trunCatelearning（ETL）が提案された．
また，文献【56】では，4層バイナリーフィードフォワードニューラルネットワーク
（4LBFNN）に対して，通常のディジタル回路の設計と同様に学習パターンの入出
力関係のプール代数を利用した学習則，Boolean−liketrainingalgorithm（BIJm）
が提案された．通常のディジタル回路とBmを用いた4LBFNNの回路構造の
違いは，通常のディジタル回路は論理ゲートを組み合わせて構成するのに対し，
4LBFNNはアナログ素子により構成できるところにある．これにより，Bmは
一度学習が終了した後に，学習パターンの変更および新たな学習パターンの学習
68
がこれまでに構成されたネットワークを変更することなしに容易に行うことがで
きるアルゴリズムである．通常のディジタル回路の設計では入出力パターンが変
更された場合，はじめから回路を再設計しなくてはならず，既に設計された回路
の変更なしに容易に入出力パターンを変更することは不可能であった．
本研究では，前節で提案したラッチニューロンを入力層および出力層に用いた3
層バイナリーリカレントニューラルネットワーク（3LBRNN）を提案する．中間層
にはパーセプトロンモデルを用いる．そして，3LBRNNの学習則としてBmを
用いることにより，複雑なディジタル順序回路（有限状態マシーン）が非常に高速
に学習できることを示す・文献【561では4層で構成されたニューラルネットワー
クに対してBmを用いていたが，本研究では3層で構成されたニューラルネッ
トワークに対してBmを用いる．これにより，Bmの特徴を生かし，遷移状
態の変更および新たな状態遷移の学習を容易に行うことができる．さらに，提案
する3LBRNNの動作確認をシミュレーションにより行う．
図5．1：3層バイナリーリカレントニューラルネットワーク
5．2 3層バイナリーリカレントニューラルネットワーク
本研究で用いた3層リカレントニューラルネットワークを図5．1に示す．それぞ
れ，マスタ一層（M層），中間層（H層），スレーブ層（S層）で構成されており，M層
の五番目のニューロンからH層のJ番目のニューロンへの結合荷重をWl（招），H
層の五番目のニューロンからS層のJ番目のニューロンへの結合荷重をⅥ／招，刃と
する．それぞれの結合荷重は−1，0，＋1の3値をとる．また，H層とM層，S層
では異なるニューロンモデル用いる．M層，S層には第4章で設計した大域収束
69
山hP芝山
1 −（D−1≧1
0u中山Q
図5．2：エネルギー関数（かが整数の場合）
性を持つラッチニューロンを用いる．このニューロンは制御信号（クロック信号）
によって現状態を記憶，もしくは入力値を出力することができる．このニューロ
ンでM層，S層を構成し，S層のニューロンにM層に入力するクロックの逆相ク
ロックを入力することによりネットワークを構成する．つまり，クロック制御の
マスタースレーブ形同期式ニューラルネットワークを構成する．ここで問題とな
るのがラッチニューロンへの入力かである．前章での設計では，ディジタル回路
を想定して設計しており，入力かの値は0または1のディジタル値として設計し
てきた．大域収束性の証明においてもかはディジタル値であるとして証明を行っ
た．しかし，本研究で用いるネットワークの構成からS層への入力は整数である．
つまり，ラッチニューロンへの入力かが整数値であることが考えられる．そこで，
ラッチニューロンが整数値の入力に対しても大域収束性が保証されることを図を
用いて示す．整数値の入力を持つラッチニューロンのエネルギー関数を図5．2に
示す．ここで，クロックC＝0のときは図4．9と同じグラフとなり，出力は入力
かに関わらず現状態を保持する．また，クロックC＝1の時は図より，入力かが
か≦0のとき出力QはQ＝0となり，β≧1のときQ＝1となることがわかる．
つまり，入力かが整数のときも大域収束性が保証されていることが分かる．この
ようなラッチニューロンをS層に用いる．しかし，M層に用いるラッチニューロ
ンは（5．1）の非線形入出力特性を持たなければならない．
70
V＝ん（明＝anh（≡） （5・1）
そこで，入出力特性としてシグモイド関数（1．2）を持つラッチニューロンの入出力
特性を次のような関係式を用いて変更しなければならない．
お（打）＝
ん（打）＋1
（5．2）
（5．2）より，（4．33）に示したパラメータを（5．3）のように変更することで（5．1）の入
出力特性を持つラッチニューロンを得る．
乃＝1一言，花＝C，茄＝C，Ⅵ＝芸 （5・3）
次に，H層のニューロンモデルを示す．このモデルには（5．4）に示されるような
入出力関係を持つパーセプトロンモデルを用いる．
打 ＝ ∑芸1昭端−β
（5．4）
Ⅴ ＝ ん（打）
ここで，打，Vはそれぞれニューロンの内部状態および出力を示し，端，W拍＝
1…m）はそれぞれ，ニューロンへの入力および結合荷重を示す．非線形関数ん
は（5．5）で示されるステップ関数である．
Ⅴ＝ん（打）＝ Oif［／＜0
1if打＞0
（5．5）
以上のようにH層ニューロンにはパーセプトロンモデル，M層，S層ニューロ
ンにはラッチニューロンモデルを用いることで，本研究で用いる3層バイナリー
リカレントニューラルネットワークを構成する．
5．3 ディジタル順序回路の設計
5．3．1 準備
学習アルゴリズムを述べる前にここでは3層バイナリーリカレントニューラル
ネットワークの初期構造について述べる．M層，H層およびS層のニューロン数
をそれぞれm，れ βとする．またH層の開値鋸ま，
貼（可＝m ∀査＝1，…，ん
とする．つまり，M層のニューロン数と同じ値を持つ．また，結合荷重の初期値
は以下のように設定する．
Wi（招）＝ −1 ∀招
l鳩（招）＝ 0 ∀招
71
0／0
図5．3：例題1の状態遷移図
表5．1：例題1の状態遷移表
Q ； Q 昔 ∬
Q T ＋l
Q 芸＋l z
0 0 0
1 0 0
0 0 1
0 1 0
0 1 0
0 0 0
0 1 1
0 0 0
1 0 0
1 0 0
1 0 1
1 1 0
1 1 0
0 0 0
1 1 1
0 0 1
5．3．2 次状態デコーダの設計
学習アルゴリズムは具体例（例題1）に基づいて説明する．つまり，図5．3に示す
状態遷移を持つ3LBRNNを学習することを考える．図5．3の状態遷移表を表5．1に
示す・また，図5・3および表5．1において可Zは入力∬と出力Zを示す．このような
入出力端子を実現するためのニューロンを含んだ3LBRNNの初期構造を前節に
従って図5．4に示す．入力∬を実現するためのニューロンモデルとしてH層ニュー
ロンと同様なパーセプトロンモデルを用いる．しかし，その入出力特性は（5．5）と
は異なり，V＝−lifU＜0，Ⅴ＝lif打≧0とする．その開値はβ＝1とす
る．出力Zを実現するニューロンにはS層ニューロンの他のニューロンと同様に
Dラッチニューロンを用いる．また，点線の結合は−1の結合荷重を，実線の結合
は＋1の結合荷重を意味する．H層ニューロンの開値はそれぞれのニューロン内に
示す．ここで，各層のニューロンを図5．4において左から順番に1，2，…と番号付
72
けを行う．
図5．4：3LBRNNの初期構造
諺 昔
十も署
司何 0 0 0
QlLJ ｛ 0 0
百β冒
十も穿
Ql 0 千 0
Q 司0 土 0
斎 諾 盃
0
0
君 諾 盃
Z
百雷
賢 Q 署
司 0 0 0 0
Q恒
0 ① 0
雷 工 雷
図5．5：例題1のカルノーマップ
学習アルゴリズムの説明を簡単にするために次状態デコーダのカルノーマップ
を表5．1より導き出す．例題のカルノーマップを図5．5に示す．ここで，Bmに
は最小項のミニマルカバーを行う場合，ミニマルカバーどうしが重なり合ってほ
ならないという制約が設けられている．このような制約を設けても最小項の数は
変わらないことを明記しておく．以上のような制約の基で，論理関数の簡略化を
行った結果，例題の論理関数は次のようになる．
QT十1＝QT・窃・∬＋窃・雷
（5．6）
73
Q冨＋1＝窃・∬ （5．7）
Z＝Q竿・Q冨・∬ （5・8）
Bmでは最小項の数だけH層ニューロンの数が必要である．つまり，図5．3の例
題では（5．6）−（5．8）より4個のH層ニューロンが必要である・
最初に，出力がQT＋1の学習，つまり（5．6）の学習を行う．（5．6）の第一項QT・窃・∬
の学習について考える．この最小項に対してはH層ニューロン，1，を用いる．まず，
NOTの変数房についてはM層ニューロン，2，とH層ニューロン，1，の結合は−1で，
TRUEの変数QT，XについてはM層ニューロン，1，，，3，とH層ニューロン，1，の結
合は＋1とする．また，H層ニューロン，1，からS層ニューロン，1，への結合は＋1と
する・これにより最小項研・窃・∬を学習することができる・実際には，結合荷重
はWi（1，1）＝1，Wi（2，1）＝一1，Wi（3，1）＝＋1およびⅥち（1，1）＝＋1となる．つ
まり，変数がNOTの時はM層からH層への結合荷重は初期構造（図5．4）からの変
化はなく，変数がTRUEの時のみ，それに対応する結合荷重を＋1にすればよい．
また，H層からS層への結合荷重は学習している最小項に対応するH層ニューロ
ンと出力層ニューロン間を＋1にすればよい．
次に（5．6）の第二項窃・雷の学習を行う．この学習にはH層ニューロン，2，を用い
る．第二画房・到ま研・窃・雷とQ；・モ詔・雷の二つの項に対してミニマルカバーを
行った結果，得られた項である．これらの項はカルノーマップ上で隣接している．
つまり，所とQ竿の1ビットのみが異なった最小項である．このような場合は，そ
の異なった変数，ここではM層ニューロン，1，からH層ニューロン，2，への結合荷重
を0にする．さらに，H層ニューロン，2，の開値から1を引くことにより窃・雷を学
習することができる・具体的には，Wl（1，2）＝0，Wl（2，2）＝−1，Wl（3，2）＝−1，
切ら（2，1）＝＋1およびβ（2）＝2となる．
さらに，（5．7）について考える．この場合も先ほどの（5．6）の第二項の場合と同
様に二つの最小項研・モ詔・∬とQT・窃・∬に対してミニマルカバーを行った結
果である．この最小項Z芳・∬に対してH層ニューロン，3，を用いる．結合荷重は
Wl（1，3）＝0，Wi（2，3）＝−1，勒（3，3）＝＋1およびl鴨（3，2）＝＋1となり，開値
はβ（3）＝3−1＝2となる．
最後に（5．8）の最小項QT・Q冒・∬を学習する・これを学習するためにH層ニュー
ロン，4，を用いる・結合荷重はWi（1，4）＝＋1，Wl（2，4）＝＋1，Wi（3，4）＝＋1お
よびⅥら（4，3）＝＋1となる．
このように学習を進めていった結果，（5．6）−（5．8）の論理関数の全ての最小項を
学習した3LBRNNは図5．6のようになる．
次に，学習パターンを例題2のように変更するための方法を示す．例えば，図
5．3の状態遷移図が図5．7のように変更された場合を考える．図5．7の状態遷移表を
74
図5．6：例題1の3LBRNN
図5．7：例題2の状態遷移図
表5．2に示す．表5．2のアンダーラインの状態が表5．1と異なるところである．出力
Zの学習の変更を行う・出力Zの変更点は現状態がQT・Q冒・雷の時に次状態が0から
1に変更される点である．これを実現するためにH層ニューロン，5，が必要となる．
この学習は前述の学習法と同様に行うことができる．結合荷重はWi（1，5）＝＋1，
Wi（2，5）＝＋1，仇（3，5）＝−1およびⅥら（5，3）＝＋1となる．次状態QT＋1の学習
の変更を行う・まず，現状態研・研・雷の学習パターンの変更を行う・これを実現
するためにH層ニューロン，6，を用いる．M層ニューロンからH層ニューロン，6，
への結合荷重を前述の学習法と同様に求める．次にH層ニューロン，6，からS層
ニューロン，1，への結合荷重を−1にすることにより学習パターンを1から0に変更
することができる．具体的には，Wi（1，6）＝＋1，Wl（2，6）＝−1，Wl（3，6）＝−1，
Ⅵち（6，1）＝−1とする・このようにすることで，最初に学習したパターンの発火を
75
表5．2：例題2の状態遷移表
研 （
謂＋
∬
Q T 十l
Q 芸＋l z
0 0 0
1 0 0
0 0 1
0 1 0
0 1 0
0 0 0
0 1 1
0 0 0
1 0 0
9 0 0
1 0 1
1 1 0
1 1 0
土 0 土
1 1 1
1 0 1
抑制することができる．次に，現状態QT・Q旨・雷の学習パターンを0から1に変更す
る．既にH層ニューロン，5，に現状態QT・Q芸・到ま学習されているので，H層ニュー
ロン，5，からS層ニューロン，1，への結合荷重をW式5，1）＝＋1とすることで実現で
きる．つまり，現状態の最小項が同じ場合，同一のH層ニューロンで実現できる・
最後に現状態QT・Q冒・∬の学習パターンの変更は・H層ニューロン，7，を用いて結
合荷重を勒（1，7）＝＋1，勒（2，7）＝＋1，勒（3，7）＝＋1および明（7，1）＝＋1と
することで実現される．このような学習則を用いることにより，Bmは一度設
計した回路を変更することなしに新たな学習パターンを学習する能力を持つ・図
5．7の状態遷移を行う3LBRNNを図5．8に示す．
5．4 シミュレーション結果
ここでは，我々が提案する3LBRNNの動作をシミュレーションにより検証す
る．図5．6と図5．8の3LBRNNのシミュレーション結果をそれぞれ図5・9（a）および
図5．9（b）に示す．シミュレーションはM層およびS層のDラッチニューロンの動作
方程式（1．1）を後退オイラー法を用いて数値積分することにより行った・図5・9（a）
および図5．9（b）より，我々が提案する3LBRNNが正確に状態遷移を学習している
ことが確認できる．ここで，クロックの周期は100【ns】とした・
5．5 まとめ
本研究ではラッチニューロンを入力層および出力層に用いた3層バイナリーリ
カレントニューラルネットワーク（3LBRNN）を提案した・そのネットワークに対
する学習則にBoolean−1iketrainingalgorithm（BIm）を用いることにより第4章
76
図5．8：例題2の3LBRNN
の設計手法では実現が困難であった，より複雑なディジタル順序回路（有限状態
マシーン）を非常に高速に学習することが可能となった．さらに，我々が提案す
る3LBRNNに対してシミュレーションを行いディジタル順序回路が正確に設計
されていることを検証した．Bmは学習パターンを学習した後に，学習パター
ンの変更および新たな学習パターンの学習をする場合これまでに構成したネット
ワークの構造を変更する必要がないアルゴリズムである．このアルゴリズムを用
いることにより，一度学習が終了した後でも自由に状態遷移を変更することがで
きる能力を持つディジタル順序回路を3LBRNNを用いて実現することができた．
このような能力は従来のディジタル回路技術では不可能であった．
77
（b）
図5．9：シミュレーション結果
（a）例題1 （b）例題2
78
6 結論
本論文では，ニューラルネットワークの計算能力を検証する上で，最適化問題
に対する新たな解法とその応用に関するいくつかの提案とともに，その計算可能
性についての考察を行った．ニューラルネットワークはこれまでのノイマン型コ
ンピュータとは異なり，単純な機能をもつ素子が相互に多数結合し，情報を並列
に分散処理することが大きな特徴である．また，ニューラルネットワークはその
高並列性という，従来の計算機にはない特徴による高速な演算が期待できる．本
研究では，主に，ホップフィールドが提案したアナログ電子回路モデルにより構
成された相互結合型ニューラルネットワーク（ホップフィールド型ニューラルネッ
トワーク）を用いた最適化問題の解法とその応用に関する研究を行った．ホップ
フィールドらは，このネットワークに対して，エネルギー関数を定義することに
よって，高速に，最適化問題を解くことができることを示した．つまり，ニュー
ラルネットワークによる最適化問題の解法とは，その動作がエネルギー関数を最
小化する方向へ動作することを用いた最適化手法である．これにより，最適化問
題に対して，従来のように詳細な逐次的アルゴリズムを用意する必要はなく，問
題の最小値とエネルギー関数の最小値が一致するように最適化問題を定式化する
ことができれば，容易に，かつ，高速に最適解を求めることができる．そこで，
本研究では，ホップフィールド型ニューラルネットワークを用いた最適化問題に
対する解法とその応用に関するいくつかの提案を行った．
第2章では都市隣接性に基づく巡回セールスマン問題（TSP）の解法について示
した．これまで，ホップフィールド型ニューラルネットワークを用いた最適化問
題の解法としてTSPを例題として用いた研究が非常に多くされてきた．そのほ
とんどが，エネルギー関数の構成法として，都市の訪問順序に基づく手法が用い
られてきた．この手法では，都市とその順序を示すために，Ⅳ都市のTSPに対し
てⅣ2個のニューロンが必要であり，また，問題の規模が増加すると局所解への
収束の問題が非常に大きな問題となった．この手法の局所解への陥りを防ぐ方法
として，ガウシアンマシンの利用や，カオスノイズなどの外部ノイズを加える方
法など様々な研究発表がされている．一方，都市隣接性に基づくエネルギー関数
の構成法では，Ⅳ都市のTSPに対して（Ⅳ一項町2のニューロンでネットワーク
を構成することができ，また，前者と比較して，比較的局所解へ陥りにくいとい
う性質を持つことが報告されてきた．しかし，この手法はエネルギー関数に全て
の都市を訪問するという制約が含まれていない．このため，複数の巡路に分かれ
る解に収束するという欠点があり，今日まであまり取り上げられていなかった．
本研究では，後者の手法に対して，複数の順路を階層的に修復する手法（階層的
修復法）を加えた解法を提案した．本手法は部分順路を段階的に接近させること
79
で準最適解を求める手法であり，エネルギー関数の性質上，比較的大きなTSPに
おいてもアルゴリズムを再帰的に用いることにより，容易に応用できる．その結
果，本手法によれば，都市の訪問順序に基づく手法と比較して比較的大きな規模
のTSPについても準最適解が得られることが示された．
第3章では，ホップフィールド型ニューラルネットワークによるタイリング問
題の解法について示した．ここでは，従来，その解法のほとんどが逐次的手法に
よるものであったタイリング問題の解法にニューラルネットワークを適用した．
本研究では，従来，提案されたタイリング問題のニューラルネット解法の問題点
を指摘し，その問題点を克服した上で，さらに大きな問題に対しても有効となる
手法を提案した．そこでは，第2章で扱ったTSPにおける都市の隣接性に注目し，
タイリング問題に対し，ポリオミノの接触度を表す関数を新たに導入し，エネル
ギー関数を改良した．さらに，従来法において用いられていたマキシマムニュー
ラルネットワークをアナログニューラルネットワークによって処理することを考
えた．このことにより，唆味なタイリングを許すことを可能とし，局所解からの
脱出を容易化した．提案アルゴリズムによれば，最大で，10×10の升目上に14
個のポリオミノを配置するタイリング問題を解くことができた．この間題におけ
る組み合わせ方の全候補は，約1．6×1024通りである．従来法で扱われていた問
題が，7×7の升目上に10個のポリオミノを敷き詰めるタイリング問題で，その
全候補が約1．3×1014通りであることを考慮すると，本アルゴリズムがより大き
く複雑なタイリング問題に対応可能であることがわかる．また，本研究では，局
所収束を避けるために，ネットワークの動作中に動作方程式を変化させるという
処理を行った．このような処理は非常に興味深い結果を示すにも関わらず，これ
までほとんど研究されていなかった．また，その理論的な解明は全くなされてい
ない．そこで，本研究では，いくつかのシミュレーションを通して，この処理の
及ぼす影響についての考察を行った．しかし，理論的解明については，大域収束
との関連性を含めて今後の課題である．
第4章では，ホップフィールド型ニューラルネットワークのディジタル信号処
理への応用に関する研究として，ディジタル順序回路の構成法を提案した．本研
究におけるディジタル順序回路の設計では，ゲート回路，ラッチ回路，及び，全
加算器の論理関数を最適化問題として定式化を行い，エネルギー関数を構成した．
これにより，時系列の入力信号に対して大域収束性を持たせることができた．さ
らに，これらを，従来のディジタル回路の設計法に基づいて組み合わせることに
より，様々なディジタル順序回路及びリプルキャリー型加算器を構成した．提案
した回路の動作検証は，シミュレーション及びブレッドボード上への実装を通し
て行われた．これにより，ホップフィールド型ニューラルネットワークによって
ディジタル順序回路を構成することができることが示された．また，本研究の特
80
徴は大域収束を得るためにシナプス結合荷重に非線形コンダクタンスを導入した
ところにある．このような，ネットワークの動作中に外部からの信号によってシ
ナプス結合荷重を変化させて大域収束させる手法はこれまでほとんど報告されて
いない．そこで，非線形シナプス結合荷重を第2，3章で扱ったような組み合わ
せ最適化問題に対して応用することで，これまでとは違ったアプローチで大域収
束性を得られるのではないかと考えられる．このことについては，今後の課題で
ある．
第5章では，第4章で設計したラッチ回路（ラッチニューロン）を入力層及び出
力層に用い，3層で構成された階層型ニューラルネットワーク（3−1ayerbinaryre−
currentneuralnetworks，3LBRNN）を提案した．第4章で提案した設計手法では，
基本となるゲート回路やラッチ回路を従来の設計手法を用いて組み合わせること
で単純なディジタル順序回路を構成した．本研究では，3LBRNNに，より複雑な
ディジタル順序回路を学習させることができることを示した．また，通常，階層
型ニューラルネットワークの学習には非常に多くの時間が必要とされてきた．そ
こで，本研究では，通常のディジタル回路の設計と同様に学習パターンの入出力
関係のブール代数を利用した学習則，Boolean−liketrainingalgorithm（BIJrA）を
学習則として用いた．これにより，ディジタル順序回路が階層型ニューラルネッ
トワークで高速に設計することができた．最終的に，設計された回路の動作検証
をシミュレーションにより行い，正確に動作していることを確認した．さらに，
Bmはシナプス荷重として，士1，0の3値で学習が可能である．これを利用す
れば，本研究で提案した3LBRNNのチップ化を行うことにより，ニューラルネッ
トワーク，つまり，アナログ回路によるプログラマブルロジックアレイの実現が
可能となる．
本論文ではホップフィールド型ニューラルネットワークを用いたいくつかの最
適化問題の解法について述べた．ニューラルネットワークのダイナミクスがある
評価関数に対する単純な勾配法であることを利用した最適化問題の解法の利点は
非常に高速に何らかの解が求まる点にある．しかし，その解の大域収束性は初期
値やェネルギー関数のパラメータ等に大きく依存してしまう．このため，この解
法には局所収束してしまうという問題点がある．これは，最適化問題において最
大の問題点であり，この間題に対していくつかの研究がなされている．それらは，
カオスノイズ印加型ニューラルネットワーク，カオスニューラルネットワーク，ガ
ウシアンマシンなどいくつかの提案はあるものの，理論的背景を持った具体的な
解決策はまだ完成されていない．本論文でもこの間題は何度か取り上げた．第3
章では，ネットワークの動作において2つのダイナミクスを交互に用いるアルゴ
リズムを使用した．しかし，この手法は経験的に用いたものであり，大域収束を
得る保証，ならびに，そのダイナミクスの解明についてもまだ未解決のままであ
81
る．今後，その理論的解明も含めて研究する予定である．第4章においては，論
理関数の大域収束性を得るために，外部からの信号によって制御される非線形シ
ナプス結合荷重を提案した．このシナプスを用いれば，時系列の信号に対して論
理関数が大域収束性を持つことは証明したが，一般の組み合わせ最適化問題に用
いた場合に関する考察は行っていない．この非線形シナプス結合荷重を用いるこ
とは，第3章のアルゴリズムと非常に類似していると考えられる．つまり，第3
章の手法は離散時間系で反復回数によってダイナミクスを変化させているのに対
して，第4章で用いる制御信号によってシナプス結合荷重を変化させることは連
続時間系でダイナミクスを変化させていることに相当する．このように本研究で
は，いくつかの最適化問題の解法を通してニューラルネットワークの計算能力の
検証を行い，さらには，その中で最大の問題点である大域収束という問題に対し
て，ダイナミクスを変化させる，もしくは，シナプスに非線形性を持たせるとい
う一つの新たな手法を提案した．本手法の特徴の一つは，変化させるそれぞれの
ダイナミクスに関しては既存のニューラルネットワークのダイナミクスを用いて
いる点にある．このため，新たなニューラルネットワークを導入する必要なく大
域収束性を得ることができる．今後，本手法の理論的解明とともに，ニューラル
ネットワークを用いた大域収束アルゴリズムの発展が期待できる．
82
謝辞
本研究を進めるにあたって，終始，御勉励いただいた浅井秀樹教授に心より御
礼申し上げます．また，本論文の審査をして下さいました市川朗教授，渡辺健蔵
教授，大坪順次教授に深く感謝いたします．
本研究において，終始，有益なる御討論及び御助言をしていただいた西垣正勝
博士（本学情報学部）に深謝いたします．また，これまでの研究において浅井研究
室の皆様には活発な討論を通じて大変お世話になりました・特に，神尾武司氏（本
学博士課程学生），中山武司氏（松下電器産業（株）），江川邦隆氏（デンソー（株）），
小野寺克明氏（NTT（株）），佐藤一路氏（キヤノン（株）），安達晴康氏（三栄ハイテッ
クス（株）），山元敏之氏（本学修士課程学生），中川朗洋氏（本学修士課程学生），加
茂篤司氏（本学修士課程学生），米山輝氏（本学修士課程学生）との活発な討議は本
研究にとって大変有意義なものでありました．皆様に深謝の意を表します．
最後に，これまでの自分の学生生活を有意義なものにしていただいた，かけが
えのない友人達に，また，とりわけ今日まで私を支えていただいた両親をはじめ
家族の皆に，感謝の気持ちを表します．
83
参考文献
【1］Hopfield，J．J．，‘NeuralNetworksandPhysicalSystemswithEmergentCllec一
七iveComputationalAbilitiea，，PrDC・NaはAcad・Sci・tLgA，79，pp・2554−2558，
April，1982．
［21Hopfield，J．J．，‘‘NeuronswithGradedResponseHaveCollectiveComputa−
tionalPropertiesLikeThoseofTwひStateNeuronsIProc・Natl・Acad・Sci・
捌，81，pp．308＆3092，M郷1984・
［3】Hopfield，J．J・and恥nk，D・W・，””Neural”ComputationofDecisionsinOp−
timizationProblems”，BoiL．Cybern．52，141−1521985
［41恥nkD．W．andHopfieldJ・J・：‘Simple‘Neural’optimizationNetworks：An
A／DConverter，SignalDecisionCircuit，andaLinearProgrmmingCircuit
州，IEEE7ね1ZS・Ch7Y：uiteSyst・ICAS−3315，Pp・533−5411MayI1986・
［5］S．Abe，”TheoriesontheHopBeldneuralnetworks”，PrDC・IJCW89，VOl・Ⅰ，
pp．557−564，June1989・
［6】S．Abe，”GlobalConvergenceandSuppressionofSpuriousStatesoftheHop一
fieldNeuralNetworksM，IEmTh17S・CirY：uitsSyst・，VOl・401nO・4IApri11993・
［7】JoppeA．，CardonH・R・A・andBiochJ・C・，”ANeuralNetworksforSolvingthe
TravellingSalemanProblemontheBasisofCityAdjacencylnTheTbur”，
血femαtOmd〃e髄耶α〃如0止Co肪reれCe，1989・
【8】相島定行，萬膳義久，”巡路中の都市隣接性に基づいた巡回セールスマン問題の
ニューラルネットへの埋込み”，信学論（DII），J74−D−ⅠⅠ，nO・8pp・1080−1089，
1991
［9］Ninomiya，H．，Sato，K．，Nakayama，T・andAsai，H・：‘‘NeuralNetwork
Approach toTraNeling Salesman Problem Based on HierarChicalCity
Adjacency’’，Proc．1995mIhterY”tionaLCoゆrmce onlVburdNbt−
wo止β世運巧〝CⅣⅣ叫，VOl．50f6，pp・262♭2631（Nov・1995）・
［10］Akiyama，Y．，％mashita，A．，Kajiwara，M・andAiso，H・：”Combinatorial
optimizationwithGaussianmaChin鴎，”PrDC・hLt・JbintCo14Ntu7dlVbtworks，
1989．
84
［11］A．Marumoto，Y．HayakawaandY・Sawada，”DynamicPropertiesofaChaos
Neural Network
ModelforInformation
Processing”，Prvc．Iht．Symp．
Ⅳ0ムm，pp．20む209（1993）
［12］Asai，H．，Onodera，K．，Kamio，T．andNinomiya，H・‥“AStudyofHopfield
NeuralNetworkswithExtemalNoises’’，PrDC．肪卿CW，95，VOl．40f6，
pp．158も1589（Nov．1995）．
［13】Onodera，K．，Kamio，T．，Ninomiya，H・andAsai，H・：‘ApplicationofHopfield
NeuralNetworkswithExternalNoisetoTSPs”，PrDC．NOLm′95，VOl．lof
2，pP．375−378（Dec．1995）．
［14］Hasegawa，M．，Ikeguchu，T．，Matozaki，T．andAihara，K．：”AnAnalysison
AdditiveEfrbctsofNonlinearDynamicsforCombinatorialOptimization，
I打CE7hns．onF仇damentals．，VOl．E8匹A，nO．1，Pp．206−213，Jan．，1997．
【15】上坂吉則，”2値変数の実数値関数から導かれるエネルギーを持つニューロン
回路網の安定性についで，，信学技報，PRU88−6
【16］秋山泰，”ホップフィールド型ニューラルネットにおけるエネルギー最小状態
への収束性を向上させる3つの技法”，信学技報，NC90−40
［171Y・TbkefujiandK・C・Lee：”AParallelAlgorithmforTilingProblems，”IEm
Tm旧．〃血†dmehノ0ぬ，VOl．1，pp．14㌻145，1990．
［18］Y．T址efuji：”NeuralNetworkParallelComputing，”KluwerAcademicPub−
J由九e†3，1992．
［191Y．T址e叫iandK．C．Lee：”ArtificialNeuralNetworksforFbuトColoringMap
Problemsand K−Colorability Problems，”IEm Thns．ChrY：uits e的st・，
VOl．38，pp．32♭333，1991．
［20】Nakayama，T．，Ninomiya，H．andAsai，H．，：‘‘Neuro−BasedOptimizationfor
TilingProblem’’，PrDC．ICONIP，94，VOl．20f3，pp．7871792，Oct．1994．
［21］Nakayama，T．，Ninomiya，H．andAsai，H．：’’Neuro−BasedTilingAlgorithm
Using
Fitting
Violation
Fhnction
of
Polyominoes，”PrDC．IEEEPCAS’96，
VOl．4，（May1996）．
［221Asai，H．，Nakayama，T．andNinomiya，H．：‘‘TilingAlgorithmwithFitting
ViolationFbnctionforAnalogNeuralArray”，PrDC．IEEBVlCⅣⅣ’96，VOl・l
Of4，pp．565−570（June1996）．
85
【231二宮 洋，中山武司，浅井秀樹，：“アナログニューラルネットワークによる
接触検出関数を用いたタイリングアルゴリズム’’，電子情報通信学会論文誌，
A分冊，VOl．J88−A，nO．11．
［24】BangW．Lee，BingJ．Sheu，”HardwareAnnealinginAnalogVLSINeurocom−
puting”，nuWerAcademicPublisherβ．（1991）．
［25］Avitable，G．，Fbrti，M．，Manetti，S．andMarini，M．：‘℃naClassofNonsym−
metricalNeuralNetworkswithApplicationtoADC’’，IEEE7hns．CIrcuits
elSyst．，VOl．38，nO．2，pp．202−209，Fbb．1991．
［26】AndrewD．Culhane，MartinC．PeckerarandC．R．K．Marrian，：”A Neural
NetApproachtoDiscreteHartleyandFburierTranSforms”，LEm7ねns．
CA昂vol・36，nO．5，pp．695−703，May，1989．
［27］Kami0，T・，Ninomiya，H．andAsai，H．，：‘DiscreteWalshTransformbyLinear
ProgrammingNeuralNet’’，P7Y）C．ICONIP，94，VOl．20f3，pp．809−814，Oct．
1994．
［28】Kami0，T．，Ninomiya，H．andAsai，H．：“ANeuralNetApproachtoDiscrete
ⅥblshTranSform，IEUCEThlZS．凡ndamentaLs．，VOl．E77lA，nO．11，pp．
1882−1886（Nov．1994）．
［291Asai，H．，Kamio，T．andNinomiya，H．：“DiscreteWdshTranSformProc窃−
SOrBasedonHopfieldNeuralNetwork’’，PrDC．1995IEEElhsかⅦmentation
elMesurtment7tChnoLqy Co垂rtmce卿卿TC，96），pp．3171322（Apri1
1995）．
［30】Kami0，T・，Ninomiya，H．andAsai，H．：‘‘convergenceofHopfieldNeural
NetworkforOrthogonalTransformation’’，PrDC．IEEEPCAS，95，VOl．lof
3，pp・493−496（Apri11995）．
［31】Kami0，T．，Ninomiya，H．andAsai，H．：‘‘DesignandImplementation
of
Neuro−BasedDiscreteWalshTransformProcessor’’，PrDC．mEEPCⅣⅣ，96，
VOl・20f4，pp．926−931（June1996）．
［32】Kami0，T．，Adachi，H．，Ninomiya，H．andAsai，H．：‘‘DiscreteWdshTranS−
form
Neuro
Chip
Using
OTA
Circuits’’，Proc．ICONIP，96，VOl．20f2，
pp．1063−1068（Sept．1996）．
86
【331Kami0，T・，Adachi，H・，Ninomiya，H．andAsai，H．：‘‘ADesignMethodof
DWTAnalogNeuroChipforVLSIImplementatiod’，Prvc・IEEE”TC’971
VOl・20f2，pp・12仙1214（M町1997）．
［34］Ninomiya，H・andAsai，H・：“OrthogonalizedSteepestDescentMethodfor
SoIvingNonlinearEquations’’，PrYN：．1995mEEhltemationalSymposium
OnChuitsand的stems御CAS，95），VOl．lof3，pp・740−743（April
1995）．
［35】Morisue，M．andKoinuma，H．：‘‘NeuralNetⅥ旧rksforDigtalApplications”，
Pmc・上郡CA昂vol・3，pp．218払2192，1989．
【36］坂井意一郎，森末道忠，鯉沼秀之さ’ニューラルネットワークディジタル加算
器及び乗算器のシミュレーショゾ，信学論（A），VOl．J74TA，nO・8，Pp・1222−
1231，1991
［37］Ninomiya，H．andAsai，H．：‘‘DesignandSimulationofNeuralNetworkDigi
italSequentialCircuits’’，PrDC．1993Jbint TtchnicalCol垂rmce on CirL
C髄吋馳βfe〝ば Cbmp扉emαmdCommw房斑点b掴〃rGCCC∫嘲，VOl．l of
2，pp．91−96（July1993）．
［38】Ninomiya，H．andAsai，H．：‘‘NeuralNetworksforDigitalSequentialCiト
Cuits’’，P7m・19931htermationaLSymposiumonNbnLinear77LeOryandits
AppEicationsrWOLmJ叫，VOl．20f4，pp．507−510（Dec．1993）．
［39］Ninomiya，H・andAsai，H．：‘‘DesignandSimulationofNeuralNetworkDigi−
talSequentialCircuits’’，neinstituteqfBectrDnic，IゆrmationandCom一
mwlkα如れ勒imeer3卿Cり7ね旧αCtわ旧0†l凡れ血me†血血げ戯ec細れ査C5，
ComuniationsandConq，uterSciences，VOl・E77lA，nO．6，pp．968−976（June
1994）．
［40】Ninomiya，H・andAsai，H．：“NeuralNetworksforDigitalSequentialCirL
Cuiti’，LEUCE7ねns・凡ndamentaLs．，VOl・E77lA，nO．12，pp．2112−2115（Dec．
1994）．
［411Ninomiya，H．，Egawa，K．，Kami0，T．andAsai，H．：‘‘DesignandImplemen−
tationofNeuralNetworkLogicCircuitswithGlobalConvergence，Prvc．
IEEEPCⅣⅣ’96，VOl．20f4，pp．980−985（June1996）．
87
［42］Ninomiya，H．andAsai，H．：”RecurrentNeurdNetw。rkSforDigitalSequen−
tialCircuits’’，PrDC・1996hLternationaL仇ゆTCnαOn肋uratJゆmation
Prvcessing〝CONm’96），VOl・lof2，pp．541−546（Sept．1996）・
［43】YamamOtO，H・，Nakayama，T・，Ninomiya，H．肌dAsai，H・：‘‘Neuro−Based
Optimization
Algorithmfor
Three
Dimensiond
Puzzles’’，Prvc．1996
血femαfiomd旅C九m血Jmゆ代れα0mα和也i叫′馳血糊，Comp祝tergαれd
Communications〝TGCgCC’96），VOl．lof2，pp．377−380（July1996）・
［44】YamamOtO，H・，Naknyama，T・，Ninomiya，H．andAsai，H・：‘‘Applicationof
Neur0−BasedOptimizationAlgorithmtoTh℃eDimenSionalCylindricPuz−
Zles’’，Prvc・1EEEPCⅣⅣ町vol・20f4，pp．1246−1250（June1997）・
［45】YamamOtO，H・，Nakayama，T・，Ninomiya，H．肌dAsai，H・：‘‘Neuro−Based
OptimizationAlgorithmforThreeDimensionalPuzzleS”，LUCE7ね1ZS．On
凡ndamentaLs・IV01・E88−AInO・6Ipp・1049−1054，JunC，1997・
［46】YAmamOtO，H．，Ninomiya，H．andAsai，H．：且Neurc＞BasedOptimizationA1−
gorithmforR∝tangularPuzZlei’，伽C．ITaCngCCT97；vol．20f2，pp．1029−
1032（July1997）．
［47］Ninomiya，H．，Kamo，A．，Ybneyama，T．andAsai，H．：‘‘AFhstAlgorithm
forSpatiotemporalPatternAnalysisofNeuralNetworkswithMultivalued
LoglC，PrtK．NOLm′971vol．lof2，pp．273−276，Nov．，1997．
［48］Yoneyama，T．，Ninomiya，H．andAsai，H．：“D窃ignof3−％luedNeuralNet−
ⅥⅥrkswithCyclicConnectionforLimitCycleGeneratoi’，PrDC．NOLTA，971
VOl．lof2，pp277−280，Nov．，1997．
【49】麻生秀樹：“ニューラルネットワークによる時系列処理の学習”，電学論，
VOl．110−C，nO．3，pp．112−118，1990．
【501荒川 薫，原島 博：“バックプロパグーションによる階層形ニューラル非
線形フィルタの設計’’，信学論（A），VOl・J74TA，nO・3，pp．421−429，1991．
［51］Day，S．T．and
Davenport，M．R・‥‘‘continuous−time
temporalback−
propagetionwith adaptive timedelayshIIEEE7hlZS・NturdNbtworks，
VOl．4，nO．2，pp．348−354，1993．
［52］Sato，M．：“ALearningAlgorithmtoTbaL：hSpatiotemporalPatternstoRか
currentNeuralNetworks’’，BioL．勒bemetics，62，pp・259・263，1990．
88
［53］Zeng，Zheng，Goodman，RodneyM・andSmyth，PadhraiC：‘‘DiscreteR＆
currentNeuralNetworksforGrammaticalInference’’，IEEEThlZS．1Vburd
Networks，VOl．5，nO．2，pp．320−330，March，1994・
［54】Nishigaki，M．：‘‘UniversalDigitalSequentialCircuit
UsingProgrammable
Ⅵbvelet Array andIts Application，PrDC・NOLm’95，VOl・20f2，pp・
1041−1044（1995）．
［551Kim，JungH・andPark，Sung−Kwon：“TheGeometricalLeamingofBinary
NeuralNetworks’’，IEmmns．NburdNbtwo7＊S，VOl．6，nO．1，pp．2371247，
January，1995．
［56】Gray，DonaldL．andMichel，AnthonyN．：‘ATrainingAlgorithmforBinary
FbedforwardNeuralNetworks’’，IEEE7hns．NburdNetworb，VOl．3，nO．2，
pp．320−330，March，1992．
［57］D．A．Klarner：”PackingarectanglewithcongruentN−Ominoes，”J Combinal・
7九eo叩，VOl．7，pp．10㌢115，1969．
［58】S．W．Golomb：”Tilingwith sets ofpolyominoes，”J Combinat・77LeOry，
VOl．9，pp．6ひ71，1970．
［59］M．S．KlmkinandA．Liu：”Polyominoesontheinfinitecheckerboard，”J
Com一
鋸れα土．耶IeOr飢VOl．A28，pp．ト16，1980．
［601S．W．Golomb：”Polyominoes whichtilerectangles，”J．Combina．丁九eory，
VOl．A51，pp．11ト124，1989．
89

「民主主義」と

カリスマリーダーはどこにいる？