バイナリー2次計画問題の地形解析と遺伝的局所探索の性能
スポンサーリンク
概要
- 論文の詳細を見る
ある最適化問題の探索空間内における地形(landscape)を前もって認知することは, その最適化問題に対して有効に働く探索法の設計の助けになるかもしれない.本論文では, NP-困難であることが知られている, バイナリー2次計画問題(binary quadratic programming problem, BQP)の地形を解析するために, 比較的小規模なBQPの問題例に対して, ランダム解からスタートする局所探索法によって得られる複数の局所最適解と真の最適解との関係を調べた.その結果多くの問題例で, それらの局所最適解は, 最適解に向かって探索空間内にクラスタとなり存在することが明らかになった.これらの認知をもとに, 遺伝的局所探索法(genetic local search)を実装し, 大規模な問題例に対するその性能及び有効性を示す.
- 社団法人電子情報通信学会の論文
- 2001-10-01
著者
-
片山 謙吾
岡山理科大学工学部情報工学科
-
成久 洋之
岡山理科大学
-
井上 浩孝/成久
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について
- パソコン用コボルエディタについて
- 最大クリーク問題に対する地形解析
- Memetic アルゴリズム
- モジュラ法の非線形計画問題への適用(数理計画)
- 非線形整数計画問題の近似解法
- 代理制約法の多次元非線形ナップザック問題への適用
- 多次元非線形ナップザック問題のヒューリスティック解法(ナップサック問題)
- 代理制約法の多次元非線形ナップザック問題への適用(ナップサック問題)
- 複数制約非線形ナップザック問題に対するスマートグリーディ法
- 代理制約法を応用した多次元ナップザック問題のヒューリスティック解法
- 複合指数乱数を用いた新指数型進化的プログラミングの有効性について
- 新指数型進化的プログラミングの有効性について
- 線形変動パラメータによる指数型進化的プログラミング
- 集合被覆問題に対する効率的な遺伝的オペレータ
- 集合被覆問題に対する遺伝的局所探索法のパラメータの影響分析
- LP問題におけるKarmarkar法について
- ジョブショップスケジューリング問題に対する反復局所探索法について
- A-20-2 最大クリーク問題に対する反復κ-opt局所探索法(A-20.スマートインフォメディアシステム,一般講演)
- 最大クリーク問題に対するMemetic Algorithmの選択法
- 最大クリーク問題に対するk-opt局所探索法の解析
- 複合指数分布を用いた進化的プログラミング
- DS-1-4 2次割当問題に対する反復k-opt局所探索法の性能(DS-1. COMP学生シンポジウム,シンポジウムセッション)
- 2次割当問題に対する反復k-opt局所探索法のKick法の検討
- 最大クリーク問題に対する反復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.生体情報科学)
- アンサンブル自己生成ニューラルネットワークのための高速枝刈り法
- 複合ニューラルネットワークによる効率的なカオス時系列予測
- カオス時系列予測問題に対するアンサンブル自己生成ニューラルネットワークの並列特性
- アンサンブル自己生成ニューラルネットワークのための高速枝刈り法
- 複合ニューラルネットワークによる効率的なカオス時系列予測
- 遺伝的アルゴリズムの交叉法に対する性能評価(計算量理論とアルゴリズム論文小特集)
- 巡回セールスマン問題に対する並列遺伝的アルゴリズムの検討
- 巡回セールスマン問題に対する並列遺伝的アルゴリズムの検討
- 巡回セールスマン問題に対する並列遺伝的アルゴリズムの検討
- TSPに対する並列ハイブリッド遺伝的アルゴリズムの一検討
- TSPに対する並列ハイブリッド遺伝的アルゴリズムの一検討
- TSPに対する並列ハイブリッド遺伝的アルゴリズムの一検討
- TSPに対する並列ハイブリッド遺伝的アルゴリズムの一検討
- マルチスイッチング制御による指数型進化的プログラミングの効率化
- ノード配置問題に対するアント最適化法(モバイル,アドホック,ユビキタス,無線,セキュリティ,マルチアクセス,アクセスネットワーク・UserNetworkInterface,Homeネットワーク,一般)
- 最大クリーク問題に対する反復k-opt局所探索法のKick法におけるタイブレーク時の頂点選択方式の検討
- 最大クリーク問題に対する局所探索法と頂点選択方式
- Multiple Sequence Alignment の形式化手法である Maximum Weight Trace 法に対する解構築法
- A-004 大規模な最大クリーク問題に対するk-opt局所探索法の性能評価(A.モデル・アルゴリズム・プログラミング)
- 大規模な最大多様性問題に対する遺伝的局所探索(局所探索)(進化的計算)
- マルチプルアライメントに対する改善法
- バイナリー2次計画問題の地形解析と遺伝的局所探索の性能
- バイナリー2次計画問題に対する変形k-opt局所探索法
- バイナリー二次計画問題に対する遺伝的局所探索法の比較
- 二次割当問題に対する遺伝的反復局所探索法(研究速報)