連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学 Hokkaido University 須藤　康裕 Yasuhiro Sudo 栗原　正仁 Masahito Kurihara

研究の位置付け 計算機工学 AI OR CSP 線形計画 HDFCSP Fuzzy 並べ替え

目次 ファジィ制約充足問題とは 離散領域の問題点 連続領域の導入 SpreadRepair アルゴリズム 変更候補値の算出方法 スケジューリング問題による計算例 おわりに

制約充足問題とは 有限で離散的な領域　　　　　から値を選ぶ複数の変数　　　　　に対して、全ての制約　　　　　を満たすような値の割り当てを探し出す問題 ファジィ制約充足問題 通常の制約充足問題の制約に、ファジィ関係を導入し，充足度をメンバーシップ値によって表す最適化問題の一種 拡張

２項制約と無向グラフ ２項制約を持つCSPの制約ネットワークは しばしばグラフを用いて表現される 変数が頂点，制約が辺に対応付けられる 制約 　 しばしばグラフを用いて表現される 変数が頂点，制約が辺に対応付けられる 変数 変数 制約 制約 変数 制約 制約 制約 変数 変数 制約

３項以上の制約とハイパーグラフ 通常のグラフでは辺が枝分れしなければならず表現できない 制約 制約は 頂点ではないことに注意 制約 制約 変数 変数 制約 制約は 頂点ではないことに注意 制約 変数 制約 変数 紛らわしいので，統一する 変数 制約 変数 変数 制約

離散領域の問題点 離散的である 有限である 領域を多く持つ必要があるときに 探索範囲を広げてしまう (組合せ的爆発) 例： 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 → Xi 1 3 5 7 9 12

探索アルゴリズムの開発 領域を離散化せずに探索可能な アルゴリズムを提案 離散連続領域を持つCSPのアルゴリズムは 存在しない 　 存在しない 領域を離散化すると不都合が生じる 領域を離散化せずに探索可能な アルゴリズムを提案

基本的なアルゴリズム 反復改善アルゴリズム 全探索 使用不可能 特定の条件下で使用可能 変更候補値の算出が条件 最も改善される値

反復改善アルゴリズム 制約違反が減少するように変数の値を１つずつ変更していく （制約違反最小化） 制約違反が減少するように変数の値を１つずつ変更していく　（制約違反最小化） ファジィ制約充足問題では全制約中最悪の制約違反を改善する SpreadRepair アルゴリズムを開発

SpreadRepair アルゴリズム(1) 変数 変数 制約 変数 制約 制約 変数 変数 制約 制約 変数 変数 制約 変数 変数 制約 変数 変数 制約 制約

SpreadRepair アルゴリズム(2) ここの制約にも注意を 払う どちらか片方を変更する 変数 制約 変数 変数 制約 制約 目標の制約 変数 ここと

変更候補値の算出方法 変更候補値をmax(Cmin)とし、全ての極、交点、l, u について充足度を求め、最大のものを得る l u R 1 Cn l u R 1 変更候補値をmax(Cmin)とし、全ての極、交点、l, u について充足度を求め、最大のものを得る

計算例(スケジューリング問題) A (0) B (1) C (2) D (3) E (4) F (5) ジョブ 実行可能時刻 資源 ①, ③ [0.6,1],[2.4, 2.8] ①, ③ B (1) [1, 1.2], [2, 2.5] ① C (2) [1, 2] ①, ② D (3) [0, 0.5], 2 ②, ③ E (4) [1, 2], [4, 5.5] ② F (5) [0, 1], [2, 2.3] ③ B C A F E D

おわりに ファジィ制約充足問題に連続領域を導入し、反復改善アルゴリズム SpreadRepairを提案した

今後の課題 実装として、より自由なメンバーシップ関数をユーザが構築できるようにする 現実的な問題への応用と、その効率を実験により検証する

問題全体としての充足度 = C1・C2・…・Cn 問題全体としての充足度は、全ての制約の充足度のand(min)をとる X Y and(X, Y) 1 0.5 0.8 問題全体としての充足度は、全ての制約の充足度のand(min)をとる = C1・C2・…・Cn ファジィ制約充足問題を解くことは、最悪の制約違反をなるべく小さくすることである