Maximum Neural Network with Nonlinear Self-Feedback and Its Application to Maximum Independent Set Problem
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, based on the maximum neural network, we propose a new parallel algorithm that can escape from local minima and has powerful ability of searching the globally optimal or near-optimum solution for the maximum independent set problem (MISP). Given a graph, the aim of the MISP is to find the largest set of vertices such that no two vertices in the set are connected by an edge. The MISP is a classic optimization problem in computer science and in graph theory with many real-world applications, and is also known to be NP-complete. By adding a nonlinear self-feedback to the maximum neural network, we proposed a parallel algorithm that introduces richer and more flexible nonlinear dynamics and can prevent the network from getting stuck at local minima. After the nonlinear dynamics has vanished, the proposed algorithm then is fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. A large number of instances have been simulated to verify the proposed algorithm.
- 社団法人 電気学会の論文
- 2005-02-01
著者
-
唐 政
富山大学 工学部
-
Tang Zheng
The Faculty Of Engineering Miyazaki University
-
XU Xinshun
Faculty of Engineering, Toyama University
-
WANG Jiahai
the Faculty of Engineering, Toyama University
-
XU Xinshun
the Faculty of Engineering, Toyama University
-
Xu Xinshun
Faculty Of Engineering Toyama University
-
Wang Jiahai
Faculty Of Engineering Toyama University
-
Wang Jiahai
The Faculty Of Engineering Toyama University
関連論文
- 加速度センサを用いた感情を込めた歩行動作の識別実験
- 腕のスティフネスとPseudo-Hapticsの関係について : Pseudo-hapticsの特性の研究(人と感覚,人工現実感)
- 腕のスティフネスとPseudo-Hapticsの関係について--Pseudo-hapticsの特性の研究 (マルチメディア・仮想環境基礎)
- 両眼網膜像差による奥行きを持つ両義的仮現運動の知覚(視知覚とその応用及び一般)
- 立体視によって知覚される傾斜面の傾斜量および形状(視知覚とその応用及び一般)
- ステレオグラムの刺激のサイズが傾斜面知覚に与える影響(一般セッション,「手」,「マルチモーダル感覚知覚&統合とその応用」及び一般)
- Depth Reversalによって知覚される傾斜面の傾斜量と形状(一般セッション,「手」,「マルチモーダル感覚知覚&統合とその応用」及び一般)
- 低反射・高透過スクリーンを用いた人工影表示システム(インタラクティブシステム・画像入力デバイス・方式,及び一般)
- 残像を利用した両眼立体視に関する研究
- 残像を利用した両眼立体視に関する研究(マルチモーダル情報処理とインタフェース&応用システム及び一般)
- Fixation Mapと被験者数の関連性(インタラクティブシステム・画像入力デバイス・方式,及び一般)
- 両眼視差定義による奥行き運動の残効(一般セッション,「手」,「マルチモーダル感覚知覚&統合とその応用」及び一般)
- ステレオグラムの刺激のサイズが傾斜面知覚に与える影響 (ヒューマンインフォメーション,コンシューマエレクトロニクス)
- Depth Reversalによって知覚される傾斜面の傾斜量と形状 (ヒューマンインフォメーション,コンシューマエレクトロニクス)
- ランダムドットステレオグラムの要素数が融像および奥行き知覚に与える影響
- ランダムドットステレオグラムの要素数が融像および奥行き知覚に与える影響(マルチモーダル情報処理とインタフェース&応用システム及び一般)
- 色残効を利用した両眼立体視に関する研究
- 融像時間によるホロプターと nonius ホロプターの比較
- TCRの認識多様性を考慮した免疫的ネットワーク
- 細胞死を考慮した多値免疫的ネットワーク
- A-2-18 免疫的ネットワークと画像認識への応用
- 適応性を有する多値免疫ネットワークとその応用
- ノニアス (Nonius) を用いたホロプター計測における刺激提示時間の影響
- ノニアス(Nonius)を用いたホロプター計測における刺激提示時間の影響(マルチモーダル情報処理とインタフェース&応用システム及び一般)
- 誘導遺伝的アルゴリズムを用いたスケジューリング問題の解法
- 反復局所探索法と目的関数調整法の組合せ方法の検討(研究速報)
- A-2-12 パターン分類のための改良Cross-validation法(A-2.非線形問題,一般講演)
- 視対象の方向知覚における両眼視差の効果
- 目的関数調整法を用いた組合せ最適化問題の解法
- ラグランジュ目的緩和法を用いた組合せ最適化問題の解法(数理モデル一般)
- ラグランジュ目的緩和法を用いた組合せ最適化問題の解法
- 立体視によって知覚される傾斜面の傾斜量および形状(視知覚とその応用及び一般)
- 両眼網膜像差による奥行きを持つ両義的仮現運動の知覚(視知覚とその応用及び一般)
- 両眼立体視とキャストシャドーの提示がVR空間における Pick-and-Place Task に与える影響
- 物体重心の移動軌跡解析による生体検出(一般セッション14)
- 顔・人体への誘目性を考慮した視覚探索モデルの提案(一般セッション7)
- 顔・人体への誘目性を考慮した視覚探索モデルの提案(一般セッション3,三次元画像,多視点画像)
- 物体重心の移動軌跡解析による生体検出(一般セッション5,三次元画像,多視点画像)
- 顔・人体への誘目性を考慮した視覚探索モデルの提案(一般セッション3,三次元画像,多視点画像)
- 物体重心の移動軌跡解析による生体検出(一般セッション5,三次元画像,多視点画像)
- Time to Contactの判断におけるDifferential Perspectiveの効果(一般セッション,「手」,「マルチモーダル感覚知覚&統合とその応用」及び一般)
- フラッシュラグ効果における聴覚情報の寄与(テーマセッション「マルチモーダル」,「手」,「マルチモーダル感覚知覚&統合とその応用」及び一般)
- 動画像による視覚的注意モデルの構築(一般セッション4)
- アニマシー知覚を利用した生体検出(テーマ関連セッション1)
- VR空間におけるキャストシャドウの提示法が物体操作に与える影響(一般セッション1)
- 動画像による視覚的注意モデルの構築(一般セッション4,顔・ジェスチャの認識・理解)
- アニマシー知覚を利用した生体検出(テーマ関連セッション1,顔・ジェスチャの認識・理解)
- VR空間におけるキャストシャドウの提示法が物体操作に与える影響(一般セッション1,顔・ジェスチャの認識・理解)
- 動画像による視覚的注意モデルの構築(一般セッション4,顔・ジェスチャの認識・理解)
- アニマシー知覚を利用した生体検出(テーマ関連セッション1,顔・ジェスチャの認識・理解)
- VR空間におけるキャストシャドウの提示法が物体操作に与える影響(一般セッション1,顔・ジェスチャの認識・理解)
- ジェスチャインタフェースを用いた3次元モデリング手法の提案(セッション3:エンターテイメントのためのCG,テーマ:エンターテイメントのためのCGおよびCG一般)
- ジェスチャインタフェースを用いた3次元モデリングシステムの構築
- ジェスチャインタフェースを用いた3次元モデリングシステムの構築(人工現実感及び一般)
- 両眼視差定義による奥行き運動の残効 (ヒューマンインフォメーション,コンシューマエレクトロニクス)
- Time to Contactの判断におけるDifferential Perspectiveの効果 (ヒューマンインフォメーション,コンシューマエレクトロニクス)
- A Fast and Reliable Approach to TSP using Positively Self-feedbacked Hopfield Networks
- Objective Function Adjustment Algorithm for Combinatorial Optimization Problems(Numerical Analysis and Optimization)
- An Expanded Maximum Neural Network with Chaotic Dynamics for Cellular Radio Channel Assignment Problem(Nonlinear Problems)
- A Neural-based Algorithm for Topological Via-minimization Problem
- Design and realization of a network security model
- Neuron-MOS V_T Cancellation Circuit and Its Application to a Low-Power and High-Swing Cascode Current Mirror
- 1 : n^2 MOS Cascode Circuits and Their Applications
- 運動領域サイズの検出が可能なMST野モデル
- ULRネットワークを用いたテンポーラルバックプロパゲーションに基づくファジィコントローラ
- 競合作用に基づく多方向運動検出ネットワーク
- 多方向の運動検出ネットワーク
- An Elastic Net Learning Algorithm for Edge Linking of Images
- 触覚受容器分布を考慮した2軸振動刺激による触覚提示装置の開発
- 触覚受容器分布を考慮した2軸振動刺激による触覚提示装置の開発
- 触覚受容器分布を考慮した2軸振動刺激による触覚提示装置の開発(人工現実感)
- 運動刺激への能動的関与が運動・奥行き効果(Kinetic Depth Effect)に与える影響(マルチモーダル情報処理とインタフェース&応用システム及び一般)
- ランダムドットステレオグラムの要素数が融像および奥行き知覚に与える影響
- 運動刺激への能動的関与が運動・奥行き効果 (Kinetic Depth Effect) に与える影響
- VR空間における物体性向上のためのポインタの提案
- VR空間における物体性向上のためのポインタの提案
- VR空間における物体性向上のためのポインタの提案(人工現実感)
- An Efficient Neural Algorithm for Two-layer Planarization Problem in Graph Drawing
- Maximum Neural Network with Nonlinear Self-Feedback and Its Application to Maximum Independent Set Problem
- シナプス間の相互作用を考慮したニューロンモデル
- 運動刺激への能動的関与が運動・奥行き効果 (Kinetic Depth Effect) に与える影響
- A Learning Algorithm of Elastic Net for Multiple Traveling Salesmen Problem
- A-2-8 速度情報を持つ多方向運動検出ネットワーク
- Multiple-Valued Neuro-Algebra
- A Model of Neurons with Unidirectional Linear Response
- A-2-15 極小値脱出法を用いたスケジューリング問題の解法
- A Chaotic Maximum Neural Network for Maximum Clique Problem(Biocybernetics, Neurocomputing)
- A New Parallel Algorithm Analogous to Elastic Net Method for Bipartite Subgraph Problem
- A Modified Hopfield Neural Network for the Minimum Vertex Cover Problem
- An Improved Transiently Chaotic Neural Network with Application to the Maximum Clique Problems
- An Elastic Net Learning Algorithm for Edge Linking of Images(Neural Netoworks and Bioengineering)
- 山登り学習法を用いたフローショップ問題の一解法
- 運動物体の相対距離変化知覚の速度依存性
- バブル de チャット
- 入力の時間差を考慮したニューロンモデルとその運動方向選択機能
- Stochastic Competitive Hopfield Network and Its Application to Maximum Clique Problem(Neural Networks and Bioengineering)