範囲調節型GAの改良と0-1ハードナップサック問題
スポンサーリンク
概要
- 論文の詳細を見る
動的計画法(DP)はナップサック問題のための最も有名な解法の一つである.このDPは擬似多項式時間で最適解を得ることが可能であり,現存するほとんどのインスタンスを解くことができることが知られている.そのため0-1ナップサック問題に関しては,NP困難な問題の中でも比較的簡単な部類に属すると言われている.現在,ナップサック問題のための最も強力なアルゴリズムは,Martelloらによって提案されたDPベースのComboである.このアルゴリズムは,多くの異なるコンセプトの組合せと考えられるため,Comboと名付けられた.しかし,Comboの提案者の一人であるPisingerはComboにも解きにくい問題があることをベンチマーク問題によって示している.本論文では,タイプの異なる各種ナップサック問題へも柔軟に対応可能なように改良した起因レベルの設定式を提案するとともに,更なる解精度の向上と計算時間の短縮を目指した改良範囲調節型遺伝的アルゴリズムを提案する.このアルゴリズムは,貪欲解法から得られる各荷物の安定性を考慮することで解の探索範囲を徐々に拡大させることができる.この提案手法を解の獲得が困難とされる各種インスタンスに適用することでその有効性を検証する.
- 日本知能情報ファジィ学会の論文
- 2007-08-15
著者
-
井田 憲一
前橋工科大学工学部情報工学科
-
井田 憲一
前橋工科大学大学院工学研究科
-
井田 憲一
前橋工科大学大学院工学研究科システム情報工学専攻
-
井田 憲一
前橋工科大学
-
安藤 紀幸
前橋工科大学大学院工学研究科
-
井田 憲一
前橋工科大 大学院
関連論文
- 特集によせて
- リエントラントフローショップ問題のための範囲限定型シフト探索と機械探索型左シフトの提案
- 固定費付き輸送問題のための遺伝的アルゴリズムの提案と数値実験
- ナップサック問題のための探索範囲調節型GAの提案
- ジョブショップスケジューリング問題におけるアクティブソリューション空間と探索
- スパニングトリー型遺伝的アルゴリズムによる2目的固定費付き輸送問題
- 遺伝的アルゴリズムによる広帯域ネットワーク設計問題の一解法
- ハイブリッド化遺伝的アルゴリズムによる並列ワークステーションを持つ多目的組立ラインバランシング問題
- GAによる多目的、多重選択ナップサック問題の解法
- スパニンクトリー型遺伝的アルゴリズムによる2目的一般輸送問題の一解法
- 遺伝的アルゴリズムによるファジィ多目標を持つシステム信頼性最適化
- 遺伝的アルゴリズムによるファジィ最短経路問題の一解法
- 遺伝的アルゴリズムによる二目的LANトポロジ-設計問題の一解法
- ファジィ最小木問題の一解法
- ニュ-ラルネットワ-ク技法と遺伝的アルゴリズムによる非線形整数計画問題の一解法
- スパニングツリーに基づく遺伝的アルゴリズムによる固定費付き輸送問題
- スパニングトリー型遺伝的アルゴリズムによる一般輸送問題の一解法
- GAによる多目的0-1ナップサック問題の解法
- 0-1非線形目標計画問題の一解法とそのシステム信頼性の最適化問題への応用
- ニューラルネットワークによるシステム信頼性最適化問題の一解法
- Mathematicaによるニューラルネットワークの応用II : 多峰性関数最適化問題
- Mathematicaによるニューラルネットワークの応用II : 0-1非線形計画問題
- 遺伝的アルゴリズムによるファジィ係数を伴う最小経路配分問題
- 遺伝的アルゴリズムによる2目的最小経路配分問題
- GAによるフレキシブルジョブショップスケジューリング問題の一解法
- スライス構造型遺伝的アルゴリズムの提案と金属板断裁加工問題への応用(研究速報)
- 特集によせて
- 容量なし施設配置問題のための遺伝的アルゴリズムの提案
- GAによる作業者配置スケジューリング問題の一解法
- Mathematicaによるニューラルネットワークの応用II : 非線形整数計画問題
- ニューラルネットワーク技法による2目的ファジィ最短経路問題の一解法
- Mathematicaによるニューラルネットワークの応用II : 二次計画問題
- Mathematicaによるニューラルネットワークの応用II : 一般割当て問題
- Mathematicaによるニューラルネットワークの応用II : 最大フロー問題
- ニュ-ラルネットワ-クによるファジィ多目的線形計画問題の一解法
- ニュ-ラルネットワ-ク技法による2目的ファジイ最短経路問題の一解法
- ニューラルネットワークによる線形計画問題の一解法
- 分岐限定法とニュ-ラルネットワ-クによるシステム信頼性最適化問題の一解法
- 特集によせて
- 特集によせて
- JSPのための遊休時間短縮アルゴリズムの提案と数値実験
- 遊休時間短縮型GAによるジョブショップスケジューリング問題の一解法
- 特徴抽出型メロディ自動生成システムの開発
- 範囲調節型GAの改良と0-1ハードナップサック問題
- パレタイジング問題のための形質を継承する遺伝的アルゴリズムの提案(ニューラルネットワーク及び生物工学)
- 非スライス構造型フロアプラン設計のための改良遺伝的アルゴリズムの提案(ニューラルネットワーク及び生物工学)
- 免疫アルゴリズムによるレイアウト設計問題の一解法
- 免疫アルゴリズムを用いたレイアウト設計問題 (特集 知能化技術と設備管理)
- ファジィ多目的線形計画問題のための2段階アプローチの改良
- 進化算法による多目的確率的条件付き一般輸送問題の一解法
- 進化算法によるファジィ多目的一般輸送問題の一解法
- ファジィ係数を伴う最小木問題の一解法
- 遺伝的アルゴリズムによる多目的非線形整数計画問題の一解法
- 4.意思決定者の選好を反映した会話型ファジィ多目的意思決定問題の一解法(ファジィOR研究会 第30回研究発表会)
- 2目的ファジィ最短経路問題の一解法
- 2目的ファジイ最短経路問題の一解法
- ウインドウ環境における統計解析パッケージ : Windows95/NT版
- 目標計画型GAによるジョブショップスケジューリング問題の一解法 (特集 知能技術の先進的システム設計・管理)