空間閾値モデルと近傍情報を用いた巡回セールスマン問題の解探索空間削減法
スポンサーリンク
概要
- 論文の詳細を見る
巡回セールスマン問題(TSP)は,NP困難なクラスに属する代表的な組合せ最適化問題である.TSPの最適解には,近くの都市に接続する辺が多く含まれるため,物理的距離が近い2都市間に張られる辺のみを残すことで,近似解法を適用する際の解探索空間を削減する手法が用いられる.一方,現実の地理的空間上のネットワークの複雑さを解析するために,様々な複雑ネットワークモデルが提案されている.これらのモデルを用いて構築されるネットワークは,TSPの最適解を構成する辺の特徴と類似している.そこで本報では,これらの複雑ネットワークモデルの1つである空間閾値モデルに近傍情報を導入することでTSPの解探索空間を削減する手法を提案する.その結果,提案手法を用いた場合,従来法と比べてより少ない辺で最適解を構成する辺を網羅できることがわかった.
- 2009-05-08
著者
-
松浦 隆文
埼玉大学大学院理工学研究科理工学専攻
-
池口 徹
埼玉大学大学院理工学研究科研究部数理電子情報部門
-
河村 裕介
埼玉大学
-
池口 徹
埼玉大
-
河村 裕介
埼玉大学大学院理工学研究科数理電子情報系専攻
-
松浦 隆文
埼玉大
-
池口 徹
埼玉大学大学院理工学研究科:埼玉大学総合研究機構脳科学融合研究センター
-
池口 徹
埼玉大学大学院理工学研究科
-
池口 徹
Graduate School Of Science And Engineering Saitama University:brain Science Institute Saitama Univer
-
松浦 隆文
埼玉大学大学院理工学研究科
-
松浦 隆文
東京理科大学工学部経営工学科
関連論文
- マルチプルアライメントに対するカオスサーチ法のパラメータ値調整法
- ダイナミカルノイズを付加したカオスニューラルネットワークを用いた二次割当問題の解法
- ヒューリステック解法を用いたサロゲートネットワークの作成について
- A-2-43 サロゲートデータ法を用いたリカレンスプロット作成時の閾値決定法(A-2.非線形問題,一般セッション)
- A-2-33 サロゲートノイズを含むカオス時系列の長期予測(A-2.非線形問題,一般セッション)
- 非線形時系列解析とサロゲートデータ法(非線形科学と統計科学の対話,研究会報告)
- A-2-4 カオスニューロンを用いた組合せ最適化技法における不応性効果のサロゲート解析(A-2.非線形問題,一般セッション)
- 組み合わせ最適化問題のニューラル解法に関する理論的考察(通信と非線形特集及び一般)
- カオスニューロダイナミクスを用いた組み合わせ最適化技法
- A-2-8 二次割り当て問題のニューラルダイナミクス解法におけるコーディング法の性能解析
- カオスダイナミクスを用いた二次割り当て問題の解法とその性能解析
- A-2-25 カオスニューラルネットワークを用いたTSPの解法における発火判定法の改良
- A-2-24 発火率制御を導入したカオスダイナミクスによる二次割り当て問題の解法
- カオスダイナミクスを用いた二次割り当て問題の一解法とリアプノフ次元を用いたダイナミクスの定量化
- A-2-6 カオスダイナミクスを用いた二次割り当て問題の一解法
- 嗅球における確率同期現象と二状態間遷移 (ニューロコンピューティング)
- RBFネットワークとDPCMによる非線形予測を用いた画像圧縮
- STDP学習により形成されるニューラルネットワークの複雑構造解析(非線形問題)
- 複雑ネットワークに対するカオスルーティング
- 2-opt法とOr-opt法をカオスニューロンで駆動する巡回セールスマン問題の解法
- 空間閾値モデルと近傍情報を用いた巡回セールスマン問題の解探索空間削減法
- A-2-11 地理的複雑ネットワークモデルを用いた巡回セールスマン問題の解探索空間の削減手法(A-2.非線形問題,一般セッション)
- ネットワーク定量化指標を用いたカオス時系列の解析
- AS-3-1 カオス時系列解析と複雑ネットワーク理論(AS-3. ネットワークダイナミクスの理論と応用,シンポジウムセッション)
- A-2-31 複雑ネットワーク定量化指標を用いたカオスの定量化(A-2. 非線形問題,一般セッション)
- 自己組織ニューラルネットワークにおけるシナプス荷重の時空間的解析
- A-2-19 STDP学習によるニューラルネットワークにおけるフィードフォワード構造の自己組織化(A-2.非線形問題,一般セッション)
- A-2-17 フィードバック抑制を制御することによるSTDPの律動的活動の生成(A-2.非線形問題,一般セッション)
- 非ホロノームアルゴリズムとデフレーション法を融合したICAアルゴリズム(研究速報)
- 嗅球における確率同期現象と二状態間遷移(機械学習によるバイオデータマインニング,生命現象の非線形性,一般)
- NLP2010-3 嗅球における確率同期現象と二状態間遷移(企画セッション:生命現象の非線形性,機械学習によるバイオデータマインニング,生命現象の非線形性,一般)
- RBFネットワークとDPCMによる非線形予測を用いた画像圧縮
- A-2-5 カオス結合系におけるネットワークの推定(A-2. 非線形問題,一般セッション)
- A-2-13 結合写像格子で構成された複雑ネットワーク構造の推定(A-2.非線形問題,一般講演)
- 日経株式市場に隠された複雑ネットワーク構造の推定
- スパイク列から連続時系列への変換を用いた入力情報の再構成
- ソフトタブーサーチを用いた巡回セールスマン問題の解法
- リカレントネットワークにおけるSTDPにより形成される機能的結合パタン(一般)
- リカレントネットワークにおけるSTDPにより形成される機能的結合パタン(一般)
- モチーフ抽出問題に対するカオスモチーフサンプラー法における不応性効果の影響
- モチーフ抽出問題に対するカオスモチーフサンプラー法における不応性効果の影響
- A-2-6 タブーサーチを用いたDNA塩基配列からのモチーフ抽出(A-2. 非線形問題)
- サロゲートデータ法によるインターネットトラフィックデータの解析
- A-2-24 パケット発生間隔を考慮したトラフィックデータの解析
- サロゲートデータを用いたネットワークトラフィックの解析
- ニューロンクラスによるスパイク間隔統計の相違
- ニューロンクラスによるスパイク間隔統計の相違
- LIFモデルとBVPモデルで見られる高次スパイク間隔統計の相違
- ニューロンモデルのクラス分類と入力の性質によるスパイク統計の相違
- A-2-23 カオス系列刺激によるBVPニューロンの応答とその統計的解析
- A-2-17 有色ノイズ入力を与えたBV ニューロンの応答
- BVPニューロンへの有色ノイズ刺激とその応答
- A-2-2 二次割当問題を解くための力オスダイナミクスに対するダイナミカルノイズの印加(A-2.非線形問題,一般セッション)
- A-2-15 STDP学習による自己組織ニューラルネットワークの統計的スパイク解析(A-2. 非線形問題,一般セッション)
- A-2-27 配送計画問題に対するカオスダイナミクスを用いた台数削減手法(A-2. 非線形問題,一般セッション)
- 時間枠制約付き配送計画問題に対するカオスダイナミックスを用いたメタヒューリスティック解法(非線形問題)
- A-2-16 動径基底関数ネットワークを用いた画像信号の非線形予測(A-2.非線形問題,一般講演)
- 非線形モデリングの予測精度と時系列の非線形性との関係
- A-2-6 多変数時系列からのネットワーク構造推定(A-2.非線形問題,一般講演)
- A-2-23 STDP学習則によるニューラルネット構造のスモールワールド化(A-2. 非線形問題, 基礎・境界)
- 多次元力学系における非線形性モデリングの有用性の評価
- 情報量基準とサンプリング法を用いた非線形予測可能性の評価
- A-2-9 モデルの複雑さを考慮した非線形予測可能性の評価指標(A-2. 非線形問題)
- 非線形予測のための新しい予測精度評価指標
- 非線形予測のための新しい予測精度評価指標
- A-2-16 離散的データに対するサロゲート法の危険性
- Dangers of Chaos Game Representation
- 視覚、聴覚、力覚情報を利用したカオスの提示
- NLP2000-38 / NC2000-32 人工現実感によるカオスの可視化と可触化
- NLP2000-38 / NC2000-32 人工現実感によるカオスの可視化と可触化
- SPDARを用いたカオスのストレンジアトラクタのマルチモーダル提示 : 4次元情報の提示
- STDPネットワークによる時空間パターンから同期発火への情報変換
- A-2-20 STDP学習により生じる同期現象の周波数依存性(A-2.非線形問題,一般セッション)
- A-2-20 ニューラルネットワーク構造とダイナミクスに与える外部入力の影響(A-2.非線形問題,一般セッション)
- 自己組織ニューラルネットワークにおけるシナプス荷重の時空間的解析
- A-2-7 STDP学習により時間変化するニューラルネットワークの複雑ネットワーク構造(A-2.非線形問題,一般講演)
- A-2-14 巡回セールスマン問題のためのカオスサーチに対するパラメータ調整法(A-2.非線形問題,一般セッション)
- A-2-27 微小なノイズを付加したカオスニューラルネットワークを用いた二次割当問題の解法(A-2.非線形問題,一般セッション)
- A-2-34 カオスダイナミクスを用いたゲノム配列からのモチーフ抽出の実用化(A-2.非線形問題,一般セッション)
- A-2-5 Lin-Kernighanアルゴリズムを用いたカオスサーチの一改良(A-2.非線形問題,一般セッション)
- Lin-Kernighanアルゴリズムをカオス駆動する巡回セールスマン問題の解法
- カオスダイナミクスを用いた2-opt法とOr-opt法に対する巡回セールスマン問題の解法
- A-2-20 2-opt法とOr-opt法をカオス駆動する巡回セールスマン問題の解法(A-2. 非線形問題,一般セッション)
- A-2-19 カオスダイナミクスを用いたLin-Kernighanアルゴリズムによる巡回セールスマン問題の解法(A-2. 非線形問題,一般セッション)
- 複雑ネットワーク理論とその応用(ネットワークダイナミクスとその応用)
- ボラティリティーとスプレッド変化に基づく為替相場の非線形モデル化
- 隔年結実を起こす植物個体の新しい非線形モデル
- スパイク列から瞬時平均発火時系列への変換を用いたニューロンへの入力情報の再加構成(非線形問題, 電子情報通信における萌芽的研究論文)
- 決定論的カオスの解析システム : 評価及び時系列解析の強化
- 決定論的カオス解析システムの構築と評価
- 決定論的カオスの情報視覚化システム : 多次元情報の効果的な提示
- 決定論的カオスの学習・モデル創造システム
- PHANToMを用いた多次元情報の提示
- STDP学習則により導かれる神経雪崩(非線形問題, 電子情報通信における萌芽的研究論文)
- 偏相関解析による非線形ダイナミカルシステムの結合形態の推定
- 複雑ネットワークに対するカオスルーティング
- ボラティリティーとスプレッド変化に基づく為替相場の非線形モデル化
- A-2-3 ウェーブレット変換を用いたノイジーなカオス時系列の極大値検出(A-2.非線形問題,一般セッション)
- 量子化された観測データに対するノイズの評価について
- A-2-14 相関次元推定における量子化誤差及びノイズの影響