ニューラルネットワークによる組合せ最適化問題の一般的解法
スポンサーリンク
概要
- 論文の詳細を見る
ダイナミックな動作をするサブネットとスタティックな動作をするサブネットの,二つのサブネットより構成される動的-静的ニューラルネットワーク(DS-net)による,組合せ最適化問題の解法について述べる.一般に,組合せ最適化問題をニューラルネットワークによって解く場合,変数の2次式(特に,双1次形式)で表された関数の最小化として定式化された問題を扱うが,Yaoらが提案したDS-net^<(2)>は,線形制約を処理するサブネットをもち,線形制約付き最小化問題をそのままの形でマッピングできるという特徴がある.本論文では,シグマ-パイニューロンの導入により,目的関数と制約条件がともに2次の非線形制約付き最適化問題をも扱うことができるように,DS-netを拡張する.そして,和積標準形論理式の充足可能性問題(CNF-3SAT問題)がこのような非線形制約付きの最小化問題へ変換できることから,提案するニューラルネットワーク解法がNP完全な組合せ問題の一般的な解法となり得ることを示す.また,シミュレーション実験により,本手法の有効性を検証する.その結果,本手法がグリーディー解法の動作をネットワーク動作に埋め込めることが示され,また最適解を求める上で重要となるネットワークの初期状態の選び方が与えられる.
- 1995-03-25
著者
関連論文
- 有限視野を持つ群ロボットのための一点収束アルゴリズムとその誤差に対する強度の評価
- 視野に制約のあるロボットによる一点集合と合意の問題
- アドホックネットワーク向けトークン巡回自己安定分散アルゴリズム
- A Universal Self-Stabilizing Mutual Exclusion Algorithm (New Developments of Theory of Computation and Algorithms)
- 単方向リングネットワークでの一様なランダム化自己安定相互排除
- 分散システムにおける資源割り当てアルゴリズム(計算量理論)
- 双方向リングネットワーク上での自己安定2:相互排除(計算機構とアルゴリズム)
- 拡張された分散$k$-相互排除(計算量理論)
- 拡張された分散κ-相互排除
- 統一的中間表現を用いた自動並列化コンパイラの実装 : ソースコードから統一的中間表現への変換
- 光配線を用いたパターン認識システム基本回路の設計と試作
- APWC回路におけるシグモイド関数生成回路の設計
- メタ記号列の学習について : パターンと記号の統合へのメモリベース・モデルからのアプローチ
- メタ記号列の学習について : パターンと記号の統合へのメモリベース・モデルからのアプローチ
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- 第3回コンプレックスコンピュータシステム国際会議 (ICECCS'97)の参加報告
- Visual Debugger における履歴情報の保存と利用
- 2レベル脳型コンピュータのための構造連想メモリ
- 2レベル脳型コンピュータの道路交通システムへの応用
- 2レベル脳型コンピュータの道路交通システムへの応用
- OEICによるスイッチマトリスクの一方法
- OEICによる並列処理
- 光インタコネクション
- 実時間処理用共有メモリ
- コンプレックスコンピュータシステム国際会議報告
- APWC回路におけるシグモイド関数生成回路の設計
- APWC回路におけるシグモイド関数生成回路の設計
- 多角形を捜索するために必要な捜索者数について
- Cooperative Control Algorithms for Anonymous Mobile Robots
- シンプル・マルチヘッドオートマタに関する2,3の性質 (計算機構の数学的研究)
- 25)マルチプロセッサによるグラフィックターミナルの高速化について(テレビジョン電子装置研究会(第91回)画像表示研究会(第50回))
- Web上の学習ナビゲータの作成法について(e-Learning教育システムの成果と目指すべきもの/一般)
- 多数個マルチプロセッサの時間評価のためのシミュレータ
- ニューロコンピュータAN1における組合せ最適化問題の解法と問題点
- 分枝限定法の並列実装の一方法
- VLIWハードウェアスタックプロセッサ
- 世界規模分散ファイルシステムSKINNY
- リングネットワークにおける一様な自己安定 k-相互排除システム
- リングネットワークにおける一様な自己安定k-相互排除システム
- 自己安定相互排除アルゴリズムの実験的評価とその改良
- リングの方向付け問題を有限状態数で解く自己安定アルゴリズム(アルゴリズムと計算量理論)
- 擬似Kohonen Networkのハードウェア化
- 擬似Kohonen NetworkのLVQ学習
- ONBAM : オブジェクトモデルニューロンによる能動メモリ
- ONBAM : オブジェクトモデルニューロンによる能動メモリ
- 分散システムの一つのスケジューリング問題(アルゴリズムの数学的基礎理論とその応用)
- システム診断問題のニューラルネットによる近似解法
- PMCモデルによるシステム診断のニューラルネット解法
- 広域ネットワーク向きファイルキャッシュプロトコルの実験的評価
- 新機能マシンNFM : メモリベースAIアーキテクチャ
- 直交光バスを想定した並列演算器
- 多安定問題として見たディジタルネットワークの同期問題 (多値論理およびその応用)
- ハードウェアスタックVLIWプロセッサSBCの概要
- マルチメディアデータ処理向きVLIWプロセッサの評価
- マルチメディアデータ処理向きVLIWプロセッサの評価
- マルチメディアデータ処理向きVLIWプロセッサの評価
- シフトレジスタ形しきい値素子回路網の計算機設計
- 状態遷移機械における高速マッチングチップの設計
- $k$-コータリのgraph-nondominatednessについて (アルゴリズムと計算の理論)
- 分散相互排除システムの可用度を改善するコーラム再割当アルゴリズム(計算理論とその応用)
- 分散相互排除システムの可用度を改善するコーラム再割当アルゴリズム
- グラフ上の相互排除のためのNDコータリ
- 構造化ストリングデータにおける知識獲得および生成
- 構造を持つストリング生成のための知識獲得の一方法
- WAN向きファイルキャッシュプロトコルSCAUPの提案とその正当性の検証
- VLIWプロセッサSBCについて
- ハードウェアスタックVLIWプロセッサSBCのためのコンパイラ
- VLIWハ-ドウェアスタックプロセッサを用いたマルチメディアデータ処理
- VHSPプロセッサの設計
- HDLによるVLIWハードウェアスタックプロセッサの設計
- 実時間マルチメディア処理のためのVLIWハードウェアスタックプロセッサ
- ニューラルネットワークによる組合せ最適化問題の一般的解法
- ATMスイッチにおける三段階スケジューリング法の提案とその評価
- ATMスイッチにおける三段階スケジューリング法の提案とその評価
- ATMスイッチにおける三段階スケジューリング法の提案とその評価(並列・分散)
- リングネットワ-クにおけるリ-ダ選挙アルゴリズムの実験的評価
- ベクトル加算システム上の系列の探索法
- 多重バス結合並列プロセッサのための最適時間ソーティングアルゴリズム (並列処理)
- On Forming a Series-Parallel Graph by Removing Nodes of a Planar Graph (Studies on Computational Complexities and Related Topics)
- サイモン・フレーザー大学計算科学科の紹介(海外情報)
- LANにおける自律管理システムに関する研究 : ユーザー管理と共有ファイルシステム管理
- 侵入者は見つかるか : 美術館捜索問題
- 分散競合解消問題
- 3. 分散相互排除問題とコータリ (<特集> フォールトトレラント分散システム向けアルゴリズム)
- 分散アルゴリズムについて(パラレル・アルゴリズム)
- ビザンティン合意問題 : 信頼性の低い分散ネットワーク上での合意問題
- ホップフィ-ルドニュ-ラルネットワ-クによる実数集合の分割 (ニュ-ロコンピュ-ティング論文)
- プロダクションシステムのための並列マッチング方式とマルチプロセッサによる一評価
- 自己組織化ニューラルネットによるデータベースアクセス
- 3SAT問題のニューラルネットワーク解法(理論計算機科学とその周辺)
- ニューラルネットベースのAIシステム構築法
- 分散環境で動作する分散アルゴリズムシミュレータ
- 書き換え型プロダクションシステムのための高速マッチングアルゴリズム
- 予測によるニューラルネット誤差逆伝搬アルゴリズムの高速化
- 事例ベース推論によるデータベースアクセス
- 固有の識別番号を仮定しないネットワークにおけるリーダー選挙問題
- 自己診断システムにおけるネットワーク構造と計算複雑さの関係 (計算機科学の数学的基礎)
- 計算機ネットワークに自律的に適応する分散システムの検討
- メモリ結合型マルチプロセッサMC1について
- 構造連想メモリベース・アーキテクチャ