最大クリーク問題に対する進化的アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
組合せ最適化問題の代表例である最大クリーク問題(maximum clique problem,MCP)に対して,これまでに遺伝的アルゴリズム等の進化的アプローチが多く提案されてきた.本研究では,高性能な進化的アルゴリズムの設計を目指し,まず,MCPにおける探索空間内の地形を解析する.その結果,DIMACSベンチマークグラフ群の多くの例題において,MCPに対するk-opt局所探索法によって算出される局所最適解群は,真の最適解との間に相関が見られない場合が多いことを示す.本論文では,このような悲観的な地形解析結果に対応するMemeticアルゴリズム(memetic algorithm,MA)を提案し,最先端の進化的アプローチとの比較を通して,本MAの有効性を示す.
- 2008-11-15
著者
-
成久 洋之
岡山理科大学工学部
-
片山 謙吾
岡山理科大学工学部情報工学科
-
南原 英生
岡山理科大学工学部情報工学科
-
植松 康祐
岡山理科大学情報処理センター
-
南原 英生
岡山理科大学工学部
-
成久 洋之
岡山理科大学工学部情報工学科
-
成久 洋之
岡山理科大学
-
成久 洋之
Department Of Information & Computer Engineering Okayama University Of Science
-
本城 秀雄
岡山理科大学大学院工学研究科修士課程情報工学専攻
-
小澤 克夫
岡山理科大学大学院工学研究科
-
貞松 政史
岡山理科大学工学部
-
井上 浩孝/成久
Graduate School Of Engineering Okayama University Of Science/department Of Information And Computer
-
片山 謙吾/成久
岡山理科大学工学部情報工学科
-
成久 洋之
岡山理科大学大学工学部情報工学科
-
南原 英生
岡山理科大学
-
片山 謙吾
岡山理科大学
関連論文
- 複合ニューラルネットワークを用いた円-ドル為替レート予測に関する研究(テーマセッション「ランダムネスと予測〜その基礎と応用」及び一般, ランダムネスと予測-その基礎と応用1)
- DS-1-3 Maximum Weight Trace問題に対するクリークを考慮したマルチプルアライメント(DS-1. COMP学生シンポジウム,シンポジウムセッション)
- 複合ニューラルネットワークを用いた円-ドル為替レート予測に関する研究(テーマセッション「ランダムネスと予測〜その基礎と応用」及び一般, ランダムネスと予測-その基礎と応用1)
- RoboCup サッカーシミュレーションリーグにおける強化学習の有効性
- Particle Swarm Optimizationの多様化に関する検討
- 進化的計算手法による関数最適化性能の比較
- バイナリー2次計画問題における遺伝的局所探索法での突然変異の効果
- D-1-7 k-opt局所探索法による遺伝的局所探索法の効果(D-1. コンピュテーション, 情報・システム1)
- バイナリー2次計画問題に対する遺伝的局所探索法の適用(自然科学)
- バイナリ-2次計画問題に対するκ-opt局所探索法の効率化
- パイナリー二次計画問題に対するk-opt局所探索法のパラメータについて
- D-1-2 バイナリー二次計画問題に対するk-opt局所探索法のパラメータに関する実験
- 探索傾向に基づいた知識の導入によるk-opt局所探索法の研究
- 貪欲的な操作による遺伝的交叉法の効果
- グラフ2分割問題における貪欲的交叉法の研究
- グラフ分割問題に対する遺伝的アルゴリズムの性能
- 遺伝的アルゴリズムによるグラフ分割問題の解法
- 最大クリーク問題に対する進化的アルゴリズム
- 最大重みクリーク問題に対する局所探索法(アルゴリズムとデータ構造・計算複雑度)
- AI-1-4 階層化意思決定法によるマルチカーエレベータ群制御(AI-1. CSTソリューションコンペティション2007:表彰式・シンポジウム,依頼シンポジウム,ソサイエティ企画)
- 階層化意思決定法によるマルチカーエレベータ制御(CSTコンペ・ソリューション発表,コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- バイナリー2次計画問題に対する知識を導入した高速k-opt局所探索法の効果
- 複合指数分布を用いた進化的プログラミング
- ソフトウェア開発における外注管理支援モデル
- ソフトウェアテスト空間を考慮した信頼性評価とその応用
- ペナルティパラメータを考慮したSUMT法の収束性について
- A-12-7 複数タスク問題におけるマルチエージェント強化学習の報酬発生タイミング(A-12.コンカレント工学,一般講演)
- 複数タスク問題に対するマルチエージェント強化学習の報酬発生タイミングと協調尺度
- 知覚情報の粗視化に基づくマルチエージェント強化学習の性能比較
- 視野の広さの違いによるAHP強化学習の性能比較
- マルチエージェント環境における知覚情報の分割を有する強化学習エージェントの有効性
- 複数タスクの問題に対するマルチエージェント強化学習の報酬に関して
- 強化学習ロボットに対する視覚情報の有効性の検証
- 強化学習エージェントへの階層化意志決定法の導入 : 追跡問題を例に
- Kheperaロボットを用いた強化学習手法の比較
- デッドロックを含む環境下における強化学習の性能と評価
- 2次元展開にもとづく被服の3次元表示
- 被服の2次元展開について
- ナップザック問題に対する効率的 GA の適用
- LP 問題における分散処理の効率性について
- LP問題のベクトル解法について
- 戦略パラメータを使用しない効率的EPについて
- パソコン用コボルエディタについて
- 最大クリーク問題に対する地形解析
- モジュラ法の非線形計画問題への適用(数理計画)
- 非線形整数計画問題の近似解法
- 代理制約法の多次元非線形ナップザック問題への適用
- 多次元非線形ナップザック問題のヒューリスティック解法(ナップサック問題)
- 代理制約法の多次元非線形ナップザック問題への適用(ナップサック問題)
- 複数制約非線形ナップザック問題に対するスマートグリーディ法
- 代理制約法を応用した多次元ナップザック問題のヒューリスティック解法
- 複合指数乱数を用いた新指数型進化的プログラミングの有効性について
- 新指数型進化的プログラミングの有効性について
- 線形変動パラメータによる指数型進化的プログラミング
- 集合被覆問題に対する効率的な遺伝的オペレータ
- 集合被覆問題に対する遺伝的局所探索法のパラメータの影響分析
- LP問題におけるKarmarkar法について
- A-20-2 最大クリーク問題に対する反復κ-opt局所探索法(A-20.スマートインフォメディアシステム,一般講演)
- 最大クリーク問題に対するMemetic Algorithmの選択法
- 最大クリーク問題に対するk-opt局所探索法の解析
- 複合指数分布を用いた進化的プログラミング
- DS-1-4 2次割当問題に対する反復k-opt局所探索法の性能(DS-1. COMP学生シンポジウム,シンポジウムセッション)
- 最大クリーク問題に対する反復k-opt局所探索法のKick法の性能比較
- 2次割当問題に対するk-opt局所探索法の検討
- Maximum Weight Trace 問題に対する枝重みクリークを考慮した解構築法
- マルチプルアラインメントに対するMaximum Weight Trace 法のクリークを考慮した貪欲法
- 横すべりを有する車両のファジィロバスト追従制御
- The Branching Compound Nonhomogeneous Poisson Process and Its Application to a Replacement Model〔邦文〕
- 大規模線形計画問題におけるRPPアルゴリズムの有効性について
- スパースマトリックスの処理特性について
- スパース行列の演算法について
- H-009 アンサンブル自己生成ニューラルネットワークの効率的なオンライン枝刈り法(H.生体情報科学)
- アンサンブル自己生成ニューラルネットワークのための高速枝刈り法
- 複合ニューラルネットワークによる効率的なカオス時系列予測
- カオス時系列予測問題に対するアンサンブル自己生成ニューラルネットワークの並列特性
- アンサンブル自己生成ニューラルネットワークのための高速枝刈り法
- 複合ニューラルネットワークによる効率的なカオス時系列予測
- 枝刈り自己生成ニューラルネットワークを用いた効率的なアンサンブル学習
- SD-1-7 アンサンブル自己生成ニューラルネットワークと階層型ニューラルネットワークのマッチングによる降水量推定
- 複合ニューラルネットワークによる効率的なカオス時系列予測
- カオス時系列予測問題に対するアンサンブル自己生成ニューラルネットワークの並列特性について
- アンサンブル自己生成ニューラルネットワークの性能分析
- 自己生成ニューラルネットワークのアンサンブル平均効果
- Ensemble Averaging 自己生成ニューラルネットワークによる時系列予測における予測精度の改善可能性
- 効率的なバックプロパゲーション学習の研究
- 進化的アルゴリズムによるニューラルネットワークの最適化
- テストデータのない場合の効率的な時系列予測
- アンサンブル自己生成ニューラルネットワークの汎化能力改善特性
- 特集に当って(本四架橋)
- Topological Aspects for Solving Generalized Transportation Problems〔邦文〕
- 多目的計画法について
- d-分割分権システムの解析
- 遺伝的アルゴリズムの交叉法に対する性能評価(計算量理論とアルゴリズム論文小特集)
- 巡回セールスマン問題に対する並列遺伝的アルゴリズムの検討
- 巡回セールスマン問題に対する並列遺伝的アルゴリズムの検討
- 巡回セールスマン問題に対する並列遺伝的アルゴリズムの検討
- TSPに対する並列ハイブリッド遺伝的アルゴリズムの一検討
- TSPに対する並列ハイブリッド遺伝的アルゴリズムの一検討
- TSPに対する並列ハイブリッド遺伝的アルゴリズムの一検討
- TSPに対する並列ハイブリッド遺伝的アルゴリズムの一検討