階層型山登り法 : 制約充足問題の高速な解法
スポンサーリンク
概要
- 論文の詳細を見る
Minton等が提案した最小矛盾戦略に基づく山登り法(MCHC, Min-Conflicts Hill Climbing)は、制約充足問題に対する非常に有効な手法のひとつである。MCHCは、ある種の制約充足問題を、問題の規模が大きい場合でも、高速に解くことができる。MCHCでは、制約充足問題を制約違反の数を最小化する最適化問題に置き換え、その最適化問題を山登り法を用いて解く。しかし、山登り法による最小化では、変換された最適化問題が多数の局所最適解を持つような場合には、制約違反数が0であるような最適解に到達できる確率は非常に小さい。本稿では、MCHCの持つこの問題点を克服するために、局所最適解から脱出するための手読きEFLOPと、EFLOPを用いて効率的に制約充足解を探索するための手法である階層型山登り法(HHC)を提案し、その効果を検証する。
- 一般社団法人情報処理学会の論文
- 1994-03-07
著者
関連論文
- 2-F-10 POS分析とアンケートに基づく大学生協の食育向上の試み(大学でのOR)
- コンフィグレーションにおけるAI技術の適用(E-コマースとAI)
- 数値属性からの例外ルール発見
- 平均的解析の拡張
- 5J-1 最小近傍法の平均的挙動の解明
- 意外性の高いルールの発見のための高速なアルゴリズム
- 分散制約充足問題の難しさに関する考察
- 重複概念の獲得が可能なクラスタリングアルゴリズムについて
- 訓練事例をガイドとする分類規則の学習
- 近傍に基づく類似事例検索の理論的解析
- 重複概念の獲得が可能なクラスタリングの一提案
- クラスタリングを用いたベイズ分類器の拡張
- K-最小近傍法におけるノイズの影響
- 線形計画法を用いた知識ベースの信頼性の評価
- EFLOP : 制約充足問題における局所最適解からの脱出法
- 階層型山登り法 : 制約充足問題の高速な解法
- サイクルを考慮した生産計画の一解法
- Simulated Annealingによる大規模生産計画問題の解法
- 仮説推論 (「計画問題と人工知能」〔第4回〕)
- 仮定に基づく組み合わせ最適化手法
- 生産計画問題におけるスケジューリング方式
- 制約充足問題における制約緩和法を用いた最適化
- スケジューリング問題における探索方式
- ウィンターワークショップ・イン・石垣島参加報告(会議報告)
- 診断エキスパートシェルDeLaにおける原因仮説の扱い
- ディシジョンラティスに基づく診断型エキスパートシェル : その『すがた』
- ディシジョンラティスに基づく診断型エキスパートシェル : その『こころ』
- 第50回AIセミナー : IT研究者・技術者のキャリアプランニングとマネジメント(アーティクル)
- 交渉による多目的計画問題の解法
- 数理計画法とAIの推論 (AIの手法と周辺の基礎理論)
- 大規模空間データからの最適領域集合の効率的な発見方法
- ディシジョンラティスに基づく知識の調整と獲得 : DeLa/1