連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学 Hokkaido University 須藤 康裕 栗原 正仁 Yasuhiro Sudo Masahito Kurihara 研究の位置付け 計算機工学 OR AI CSP 線形計画 HDFCSP Fuzzy 並べ替え 目次 ファジィ制約充足問題とは 離散領域の問題点 連続領域の導入 SpreadRepair アルゴリズム 変更候補値の算出方法 スケジューリング問題による計算例 おわりに 制約充足問題とは n { D } 有限で離散的な領域 i i 1 から値を選ぶ複数 の変数 { X i }in1 に対して、全ての制約 {Ck }rk 1 を 満たすような値の割り当てを探し出す問題 拡張 ファジィ制約充足問題 通常の制約充足問題の制約に、ファジィ関係を導入 し,充足度をメンバーシップ値によって表す最適化 問題の一種 2項制約と無向グラフ 2項制約を持つCSPの制約ネットワークは しばしばグラフを用いて表現される 変数が頂点,制約が辺に対応付けられる 変数 制約 変数 制約 変数 制約 制約 制約 変数 制約 変数 3項以上の制約とハイパーグラフ 通常のグラフでは辺が枝分れしなければなら ず表現できない 変数 制約 変数 制約は 頂点ではな いことに注意 制約 制約 変数 変数 変数 制約 変数 変数 制約 紛らわしい ので,統一 する 離散領域の問題点 離散的である 有限である 例: Di = {青,黄} Di = {1, 2, 5, 9, 12, …} Di = {1, 1.1, 1.2, …, 2, 5, …} 領域を多く持つ必要があるときに 探索範囲を広げてしまう (組合せ的爆発) 連続領域の導入 離散的な領域の他に、連続領域をドメインに加える 混合領域ファジィ制約充足問題と定義 さらに適切な解が得られるようになる 離散的な領域だけで定式化するより、最適解の 近似解を高速に求めることを目的とする 混合領域ファジィ制約充足問題の定義 ファジィ制約充足問題の変数領域に連続 領域を導入する 領域を と定義する lj=ujの場合、離散的な領域と同じである 例: Di = {1}∪[3, 5] ∪ {7} ∪[9, 12] ∪ … Di 1 3 5 7 9 12 → Xi 探索アルゴリズムの開発 離散連続領域を持つCSPのアルゴリズムは 存在しない 領域を離散化すると不都合が生じる 領域を離散化せずに探索可能な アルゴリズムを提案 基本的なアルゴリズム 反復改善アルゴリズム 全探索 特定の条件下で使用可能 使用不可能 変更候補値の算出が条件 最も改善される値 反復改善アルゴリズム 制約違反が減少するように変数の値を1つ ずつ変更していく (制約違反最小化) ファジィ制約充足問題では全制約中最悪 の制約違反を改善する SpreadRepair アルゴリズムを開発 SpreadRepair アルゴリズム(1) 制約 変数 変数 制約 変数 制約 制約 制約 変数 変数 変数 変数 制約 変数 制約 変数 制約 変数 制約 変数 SpreadRepair アルゴリズム(2) ここの制約 にも注意を 払う どちらか片方を変更する 変数 制約 変数 制約 ここと 制約 変数 目標の制 約 変数 変更候補値の算出方法 R 1 C C1 Cn 0 l u 変更候補値をmax(Cmin)とし、全ての極、交点、 l, u について充足度を求め、最大のものを得る 計算例(スケジューリング問題) ジョブ 実行可能時刻 A (0) B (1) C (2) D (3) E (4) F (5) [0.6,1],[2.4, 2.8] [1, 1.2], [2, 2.5] [1, 2] [0, 0.5], 2 [1, 2], [4, 5.5] [0, 1], [2, 2.3] B C A E D F 資源 ①, ③ ① ①, ② ②, ③ ② ③ おわりに ファジィ制約充足問題に連続領域を導入し、 反復改善アルゴリズム SpreadRepairを提 案した SpreadRepairを実装したプログラムで、混 合領域ファジィ制約充足問題を解くことが できた 今後の課題 実装として、より自由なメンバーシップ関数 をユーザが構築できるようにする 現実的な問題への応用と、その効率を実 験により検証する 問題全体としての充足度 X 0 0 Y 0 1 and(X, Y) 0 0 1 0 0 1 1 1 0.5 0.8 0.5 問題全体としての充足 度は、全ての制約の充 足度のand(min)をとる = C1・C2・…・Cn ファジィ制約充足問題を解くこ とは、最悪の制約違反をなる べく小さくすることである
© Copyright 2024 ExpyDoc