二次割当問題の交換要素を適応的に決定するカオス的局所探索法
スポンサーリンク
概要
- 論文の詳細を見る
二次割当問題はNP困難な組合せ最適化問題である.二次割当問題の特殊な例に,巡回セールスマン問題がある.巡回セールスマン問題に対する最も強力な近似解法の一つとしてLin-Kernighan法がある.Lin-Kernighan法における探索では,交換する枝数を適応的に決定するという特徴がある.本稿ではLin-Kernighan法の持つ特徴を二次割当問題に応用した新しい探索法を提案している.提案法では,交換する要素数を適応的に決定することで,計算時間を押さえつつ,効率の良い探索法を実現している.本稿ではさらに,提案手法が局所最適解に陥ることを避けるために,カオスダイナミクスを導入した手法も提案している.カオスダイナミクスの有効性を評価するために,既存の二次割当問題の局所探索法との性能比較を行う.数値実験の結果より,カオスダイナミクスを導入することで,効率良く局所最適解を抜け出すことができることが示された.
- 一般社団法人電子情報通信学会の論文
- 2013-03-07
著者
-
黒田 佳織
埼玉大学大学院理工学研究科
-
池口 徹
埼玉大学大学院理工学研究科
-
藤原 寛太郎
埼玉大学大学院理工学研究科
-
渡辺 明生
埼玉大学工学部
-
黒田 佳織
埼玉大学大学院理工学研究科数理電子情報部門
関連論文
- マルチプルアライメントに対するカオスサーチ法のパラメータ値調整法
- ダイナミカルノイズを付加したカオスニューラルネットワークを用いた二次割当問題の解法
- ヒューリステック解法を用いたサロゲートネットワークの作成について
- A-2-33 サロゲートノイズを含むカオス時系列の長期予測(A-2.非線形問題,一般セッション)
- 非線形時系列解析とサロゲートデータ法(非線形科学と統計科学の対話,研究会報告)
- 組み合わせ最適化問題のニューラル解法に関する理論的考察(通信と非線形特集及び一般)
- カオスニューロダイナミクスを用いた組み合わせ最適化技法
- カオスダイナミクスを用いた二次割り当て問題の解法とその性能解析
- A-2-25 カオスニューラルネットワークを用いたTSPの解法における発火判定法の改良
- カオスダイナミクスを用いた二次割り当て問題の一解法とリアプノフ次元を用いたダイナミクスの定量化
- RBFネットワークとDPCMによる非線形予測を用いた画像圧縮
- STDP学習により形成されるニューラルネットワークの複雑構造解析(非線形問題)
- 複雑ネットワークに対するカオスルーティング
- 2-opt法とOr-opt法をカオスニューロンで駆動する巡回セールスマン問題の解法
- 空間閾値モデルと近傍情報を用いた巡回セールスマン問題の解探索空間削減法
- ネットワーク定量化指標を用いたカオス時系列の解析
- AS-3-1 カオス時系列解析と複雑ネットワーク理論(AS-3. ネットワークダイナミクスの理論と応用,シンポジウムセッション)
- 自己組織ニューラルネットワークにおけるシナプス荷重の時空間的解析
- A-2-21 ニューラルネットワーク構造推定のためのスパイク列から連続時系列への変換法(A-2.非線形問題,一般セッション)
- A-2-19 STDP学習によるニューラルネットワークにおけるフィードフォワード構造の自己組織化(A-2.非線形問題,一般セッション)
- A-2-17 フィードバック抑制を制御することによるSTDPの律動的活動の生成(A-2.非線形問題,一般セッション)
- 非ホロノームアルゴリズムとデフレーション法を融合したICAアルゴリズム(研究速報)
- 嗅球における確率同期現象と二状態間遷移(機械学習によるバイオデータマインニング,生命現象の非線形性,一般)
- NLP2010-3 嗅球における確率同期現象と二状態間遷移(企画セッション:生命現象の非線形性,機械学習によるバイオデータマインニング,生命現象の非線形性,一般)
- RBFネットワークとDPCMによる非線形予測を用いた画像圧縮
- A-2-5 カオス結合系におけるネットワークの推定(A-2. 非線形問題,一般セッション)
- 日経株式市場に隠された複雑ネットワーク構造の推定
- スパイク列から連続時系列への変換を用いた入力情報の再構成
- ソフトタブーサーチを用いた巡回セールスマン問題の解法
- リカレントネットワークにおけるSTDPにより形成される機能的結合パタン(一般)
- リカレントネットワークにおけるSTDPにより形成される機能的結合パタン(一般)
- モチーフ抽出問題に対するカオスモチーフサンプラー法における不応性効果の影響
- モチーフ抽出問題に対するカオスモチーフサンプラー法における不応性効果の影響
- サロゲートデータ法によるインターネットトラフィックデータの解析
- サロゲートデータを用いたネットワークトラフィックの解析
- ニューロンクラスによるスパイク間隔統計の相違
- ニューロンクラスによるスパイク間隔統計の相違
- LIFモデルとBVPモデルで見られる高次スパイク間隔統計の相違
- ニューロンモデルのクラス分類と入力の性質によるスパイク統計の相違
- BVPニューロンへの有色ノイズ刺激とその応答
- A-2-2 二次割当問題を解くための力オスダイナミクスに対するダイナミカルノイズの印加(A-2.非線形問題,一般セッション)
- 時間枠制約付き配送計画問題に対するカオスダイナミックスを用いたメタヒューリスティック解法(非線形問題)
- 非線形モデリングの予測精度と時系列の非線形性との関係
- 多次元力学系における非線形性モデリングの有用性の評価
- 情報量基準とサンプリング法を用いた非線形予測可能性の評価
- 非線形予測のための新しい予測精度評価指標
- 非線形予測のための新しい予測精度評価指標
- 視覚、聴覚、力覚情報を利用したカオスの提示
- NLP2000-38 / NC2000-32 人工現実感によるカオスの可視化と可触化
- NLP2000-38 / NC2000-32 人工現実感によるカオスの可視化と可触化
- STDPネットワークによる時空間パターンから同期発火への情報変換
- A-2-20 STDP学習により生じる同期現象の周波数依存性(A-2.非線形問題,一般セッション)
- 自己組織ニューラルネットワークにおけるシナプス荷重の時空間的解析
- A-2-14 巡回セールスマン問題のためのカオスサーチに対するパラメータ調整法(A-2.非線形問題,一般セッション)
- A-2-27 微小なノイズを付加したカオスニューラルネットワークを用いた二次割当問題の解法(A-2.非線形問題,一般セッション)
- A-2-34 カオスダイナミクスを用いたゲノム配列からのモチーフ抽出の実用化(A-2.非線形問題,一般セッション)
- Lin-Kernighanアルゴリズムをカオス駆動する巡回セールスマン問題の解法
- カオスダイナミクスを用いた2-opt法とOr-opt法に対する巡回セールスマン問題の解法
- 複雑ネットワーク理論とその応用(ネットワークダイナミクスとその応用)
- ボラティリティーとスプレッド変化に基づく為替相場の非線形モデル化
- 動的かつ確率的な最適化最適化問題と最適戦略
- 隔年結実を起こす植物個体の新しい非線形モデル
- スパイク列から瞬時平均発火時系列への変換を用いたニューロンへの入力情報の再加構成(非線形問題, 電子情報通信における萌芽的研究論文)
- 決定論的カオスの解析システム : 評価及び時系列解析の強化
- 決定論的カオス解析システムの構築と評価
- 決定論的カオスの情報視覚化システム : 多次元情報の効果的な提示
- 決定論的カオスの学習・モデル創造システム
- PHANToMを用いた多次元情報の提示
- STDP学習則により導かれる神経雪崩(非線形問題, 電子情報通信における萌芽的研究論文)
- 偏相関解析による非線形ダイナミカルシステムの結合形態の推定
- 複雑ネットワークに対するカオスルーティング
- ボラティリティーとスプレッド変化に基づく為替相場の非線形モデル化
- A-2-3 マーク付き点過程から連続時系列への変換法(A-2.非線形問題,一般セッション)
- A-2-3 ウェーブレット変換を用いたノイジーなカオス時系列の極大値検出(A-2.非線形問題,一般セッション)
- 量子化された観測データに対するノイズの評価について
- A-2-14 相関次元推定における量子化誤差及びノイズの影響
- 局所線形予測法における近傍探索の一手法について
- PHANToMを用いた決定論的カオス教育システム
- PHANToMを用いた決定論的カオスのマルチモーダル提示
- PHANToMを用いた決定論的カオスのマルチモーダル提示(非線形回路とシステム及び一般)
- A-2-4 ニューロンへの入力情報の適応的再構成(A-2.非線形問題,一般セッション)
- 二次の非線形結合に対する偏相関解析
- AS-1-7 STDP学習則により導かれる神経雪崩におけるパタン再現性解析(AS-1.ネットワークダイナミクス研究の展開,シンポジウムセッション)
- いくつかの加振機構による電気接点の劣化現象に関する研究 : 接触抵抗変動のモデリング
- パケットルーティング問題に対するカオスニューロダイナミクスを用いた改良法の提案
- パケット経路選択方法のサロゲート解析
- カオスニューロダイナミクスを用いたパケットルーティングの最適化
- 複雑ネットワークから得られる時系列の周期性とランダム性に対する理論的解析
- カオス振動を発する低周波治療器の製作とその性能解析
- ダイナミカルノイズを印加したカオスニューラルネットワークに対する統計的解析
- 事象の大きさと発生間隔を用いる非線形モデリングの性能解析
- A-2-22 事象の大きさと発生間隔を用いる非線形モデリングの特性解析
- A-2-10 Spike Time Metricのマーク付き点過程時系列への拡張(A-2.非線形問題,一般セッション)
- 電子回路を用いたカオス振動子における共通ノイズ同期現象
- 古典的多次元尺度法を用いた実ネットワークの解析
- 複雑ネットワークの成長予測
- 組合せ最適化問題の適応的局所探索法とカオスニューロダイナミクス
- Spike Time Metricを用いたマーク付き点過程からのネットワーク構造の推定
- 二次割当問題の交換要素を適応的に決定するカオス的局所探索法
- Spike Time Metricを用いたマーク付き点過程からのネットワーク構造の推定