フローショップスケジューリング問題の地形解析と遺伝的局所探索による解法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 総作業時間(makespan)最小・順列型フローショップスケジューリング問題(PFSP)を題材とした探索空間の地形(landscape)を解析する.特にクリティカルブロックに基づく近傍と, 確率的局所探索を用いる場合を考える。例として最適解が既知な, 比較的規模の小さい問題を取り上げ, ランダムに生成した局所最適解および真の最適解の相互の関係を調べたところ, 目的関数である総作業時間と, 各局所最適解から他の局所最適解への距離平均, 各局所最適解から真の最適解への距離との間に強い正の相関が存在することが分かった.これらの相関は, 局所最適解が探索空間内にクラスタとなって存在する, いわゆる「大谷構造」(big valley structure)が探索空間に存在することを示唆している.したがってこの大谷構造を有効に利用できる局所探索によってこの問題が効果的に解けることが期待できる.そこでジョブショプ問題解法として以前提案されたMSXF-GAによるPFSP解法を提案した.さらに比較的難問なベンチマーク問題を用いた計算機実験により本方法の有効性を検証した.
- 1998-07-15
著者
関連論文
- 購買行動解析のためのトピック追跡モデル(人工知能,データマイニング)
- 文書集合と著者集合の依存関係を説明する潜在変数モデル(データ工学,Web情報システム)
- ユーザの嗜好の時系列性と先行性に着目した協調フィルタリング(コンテンツ技術,Web情報システム)
- ユーザの興味とオブジェクトのトピックに着目した情報検索モデル(コンテンツ技術,Web情報システム)
- 顧客生涯価値を高めるためのリコメンデーション法(一般セッション,データ工学とメディア理解との融合)
- 顧客生涯価値を高めるためのリコメンデーション法(一般セッション,データ工学とメディア理解との融合)
- Innovatorの発見によるリコメンデーションのパーソナライズ手法の提案(「自動化:推論,発見,学習,データマイニング」及び一般)
- 購買順序を考慮した協調フィルタリング(「自動化:推論,発見,学習,データマイニング」及び一般)
- ベイズ階層言語モデルによる教師なし形態素解析(言語モデル・ウェブ解析)
- 誤り訂正学習による動作認識と個人適応への試み
- 方向性特徴は何故有効なのか? : 抽象図形によるアプローチ(一般セッション4,移動カメラ画像処理におけるパターン認識とメディア理解)
- 知識共有サイトにおける投稿数の乗算確率過程的成長モデル
- グラフ索引構造を用いた高速類似探索(人工知能,認知科学)
- D-4-2 大規模タグクラウドを地形図として可視化するTopigraphy(D-4. データ工学,一般セッション)
- ディリクレ過程混合モデルに基づく離散データの共クラスタリング
- ディリクレ混合過程モデルに基づく半教師有り学習(一般セッション,データ工学とメディア理解との融合)
- ノンパラメトリックベイズモデルによるグラフクラスタリング(一般セッション,データ工学とメディア理解との融合)
- ディリクレ過程混合モデルに基づく共クラスタリング (「プリファレンスモデリングと推薦システム」及び一般)
- 分布が変化するデータにおけるモデル学習法(データマイニング)
- 購買順序を効率的に用いた協調フィルタリング
- 内容と関連するタグの教師なし抽出(「Webインテリジェンス」及び一般)
- K-004 学習者の視点に基づく協調学習履歴の構造化(K分野:教育工学・福祉工学・マルチメディア応用)
- 固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
- 固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
- 固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
- 一般化受理確率関数を備えた確率的局所探索法による多目的最適化
- 遺伝的局所探索法によるジョブショップスケジューリング問題の解法
- クロスエントロピー最小化に基づくネットワークデータの埋め込み(知識処理)
- 著者の興味と文書の内容の依存関係に着目した潜在変数モデル(「Webインテリジェンス」及び一般)
- LD-005 Relative Innovatorの発見によるパーソナライズ手法の提案(データベース)
- ユーザの網羅性を反映したランキング手法の提案(セッション7:ウェブにおける情報処理,社会システムと知能)
- 誤り訂正学習による動作認識の試み
- ディリクレ過程混合モデルに基づく離散データの共クラスタリング
- ディリクレ過程混合モデルに基づく離散データの共クラスタリング
- ディリクレ混合過程モデルに基づく半教師有り学習(一般セッション,データ工学とメディア理解との融合)
- ノンパラメトリックベイズモデルによるグラフクラスタリング(一般セッション,データ工学とメディア理解との融合)
- クロスエントロピーに基づくネットワークデータの埋め込み
- 階層的独立固有時間刻み法によるグラフ可視化計算の高速化
- トピックモデルに基づく文書群の可視化
- 購買順序を効率的に用いた協調フィルタリング
- 購買順序を効率的に用いた協調フィルタリング
- D-032 最大エントロピー法に基づく推薦システムでのユーザ行動のモデル化(D分野:データベース)
- 複数対象トラッキングにおける,適応的なパラメータ推定手法(一般セッション,データ工学とメディア理解との融合)
- 複数対象トラッキングにおける,適応的なパラメータ推定手法(一般セッション,データ工学とメディア理解との融合)
- ノンパラメトリックベイズに基づく複数対象時系列のクラスタリングとトラッキング(人工知能,認知科学)
- D-040 ネットワーク索引構造を用いた類似探索と可視化(データベース,一般論文)
- ノンパラメトリックベイズモデル
- フローショップスケジューリング問題の地形解析と遺伝的局所探索による解法
- ジョブショップスケジューリング問題とクリティカルブロックSA法
- 統計的機械学習技術による潜在構造の発見(SDN(Software-Defined Network),クラウド,ネットワーク仮想化,サービス品質,コンテンツ配信,一般)
- 統計的機械学習技術による潜在構造の発見(SDN(Software-Defined Network),クラウド,ネットワーク仮想化,サービス品質,コンテンツ配信,一般)