ファジィ制約充足問題への連続領域の導入 Introducing continuous domains to fuzzy constraint satisfaction problems 須藤康裕 Yasuhiro Sudou 三田村保大堀隆文 Tamotsu Mitamura Takahumi Oohori 栗原正仁 Masahito Kurihara 目次はじめに  制約充足問題とは  離散領域の問題点  連続領域の導入  反復改善アルゴリズムの適応  変更候補値の算出方法  計算例  おわりに  制約充足問題とは  n { D } 有限で離散的な領域 i i 1 から値を選ぶ複数の変数 { X i }in1 に対して、全ての制約 {Ck }rk 1 を満たすような値の割り当てを探し出す問題拡張ファジィ制約充足問題通常の制約充足問題の制約に、ファジィ関係を導入し充足に程度が存在する最適化問題の一種制約充足問題の例変数領域 X1 青，黄 X2 青，黄 X3 青，黄 X４青，黄 X５青，黄 X６青，黄：制約隣接するノードと異なる色にする X1 X2 X3 X4 X5 X6 制約充足問題（グラフ色塗り問題）の例離散領域の問題点離散的である  有限である  例： Di = {1, 2, 5, 9, 12, …} 領域を多く持つ必要があるときに探索範囲を広げてしまう連続領域の導入離散的な領域の他に、連続領域をドメインに加える混合領域制約充足問題と定義さらに適切な解が得られるようになる  離散的な領域だけで定式化するより、高速に解を得ることができる  混合領域制約充足問題の定義ファジィ制約充足問題の変数領域に連続領域を導入する  領域をと定義する  lj=ujの場合、離散的な領域と同じである  例： Di = {1, [2, 5], 7, [9, 12], …} 反復改善アルゴリズムの適応そのままでは通常のCSPの為のアルゴリズムが使用できない  領域を離散化すると不都合がある  領域を離散化せずに探索可能なアルゴリズムを適用する必要がある基本的なアルゴリズム反復改善法全探索特定の条件下で使用可能使用不可能変更候補値の算出が条件最も改善される値反復改善アルゴリズム制約違反が減少するように変数の値を１つずつ変更していく  ファジィ制約充足問題では最も違反している制約違反を改善する  最悪の制約違反に関係する全ての変数の変更候補値を求める必要がある反復改善アルゴリズム最も違反している制約の有する全ての変数の変更候補値を算出する  全ての変更候補値の中で、最も値の大きいものを持つ変数の値を変更する  最悪の違反が減少しない場合は隣接する変数の値を変更していく  繰り返し  変更候補値の算出方法 Xa C X C1 X1 C：最悪の制約違反 Cn Xn  変数 X の値を変更する場合その他の変数を全て固定して考える変更候補値の算出方法 R 1 C C1 Cn 0 l  u 変更候補値をmax(Cmin)とし、全ての極、交点、 l, u について充足度を求め、最大のものを得る計算例領域： A C1 DA = 1, 2, [3, 7], 9 C2 DB = 4, 5, [6, 10] DC = [0, 3], [6, 8] B 初期値： C3 C 制約： VA = 3 C1 = A(A-2B) VB = 6 C2 = 2A-C VC = 7 C3 = C(B-C) 計算例１段階目 A C1 B C2 C3 C VA = 3 C1 = A(A-2B) = -27 DA = 1, 2, [3, 7], 9 VB = 6 C2 = 2A-C = -1 DB = 4, 5, [6, 10] VC = 7 C3 = C(B-C) = -7 DC = [0, 3], [6, 8] A について変更候補値を求める場合C1とC2についてBとCを固定 C2 = 2A-7 C1 = A(A-12) クリスプな領域： VA = 1：-27 → -11 VA = 2： -27 → -20 VA = 9： -27 → -27 ←連続領域： VA = 3：-27 → -27 B について変更候補値を求める場合C1とC3についてAとCを固定 C1 = 9-6B C3 = 7B-24 クリスプな領域： VB = 4：-27 → -21 VB = 5： -27 → -14 ←連続領域： VB = 6：-27 → -27 計算例２段階目 A C1 B C2 C3 C VA = 1 C1 = A(A-2B) = -11 DA = 1, 2, [3, 7], 9 VB = 6 C2 = 2A-C = -5 DB = 4, 5, [6, 10] VC = 7 C3 = C(B-C) = -7 DC = [0, 3], [6, 8] B について変更候補値を求める場合C1とC3についてAとCを固定 C3 = 7B-49 C1 = 1-2B クリスプな領域： VB = 4：-27 → -21 VB = 5： -27 → -14 ←連続領域： VB = 6：-11 → -11 C について変更候補値を求める場合C2とC3についてAとBを固定 C3 = C(6-C) C2 = 2-C ←連続領域： VC ≒0.3： -11 → -1.7 A, Bについては現在の割り当てが最善なので C を変更する計算例３段階目 A C1 B C2 C3 C VA = 1 C1 = A(A-2B) = -11 DA = 1, 2, [3, 7], 9 VB = 6 C2 = 2A-C = 1.7 DB = 4, 5, [6, 10] VC = 0.3 C3 = C(B-C) = 1.71 DC = [0, 3], [6, 8] A について変更候補値を求める場合C1とC2についてBとCを固定 C1 = A(A-12) C2 = 2A-0.3 クリスプな領域： VA = 1：-27 → -11 VA = 2： -27 → -20 VA = 9： -27 → -27 連続領域： 1段階目を参照 B について変更候補値を求める場合C1とC3についてAとCを固定 C1 = 1-2B C3 = 0.3(B-0.3) クリスプな領域： VB = 4：-11 → -7 VB = 5： -11 → -9 ←連続領域： VB = 6：-11 → -11 計算例４段階目 A C1 B C2 C3 C VA = 1 C1 = A(A-2B) = -7 DA = 1, 2, [3, 7], 9 VB = 4 C2 = 2A-C = 1.7 DB = 4, 5, [6, 10] VC = 0.3 C3 = C(B-C) = 1.11 DC = [0, 3], [6, 8] A について変更候補値を求める場合C1とC2についてBとCを固定 C1 = A(A-8) C2 = 2A-0.3 クリスプな領域： VA = 1：-7 → -7 VA = 2： -7 → -12 VA = 9： -7 → 9 連続領域： VA = 7：-7 → -7 B について変更候補値を求める場合C1とC3についてAとCを固定 Bは直前に変更したばかりなので最善な割り当てである計算例５段階目 A C1 B C2 C3 C VA = 9 C1 = A(A-2B) = 9 DA = 1, 2, [3, 7], 9 VB = 4 C2 = 2A-C = 17.7 DB = 4, 5, [6, 10] VC = 0.3 C3 = C(B-C) = 1.11 DC = [0, 3], [6, 8] B について変更候補値を求める場合C1とC3についてAとCを固定 C1 = 81-18B C3 = 0.3(B-0.3) クリスプな領域： VB = 4：0.1 → 1.11 VB = 5：0.1 → -9 ←連続領域： VB = 6：0.1 → -7 C について変更候補値を求める場合C2とC3についてAとBを固定 C3 = C(4-C) C2 = 18-C ←連続領域： VC =2： 1.11 → 4 計算終了 A C1 B  C2 C3 C VA = 9 C1 = A(A-2B) = 9 VB = 4 C2 = 2A-C = 17.7 VC = 2 C3 = C(B-C) = 4 これ以上どの変数の値を変更しても違反が改善されない局所最適状態おわりに制約充足問題に連続領域を導入することに成功した  制約を表すメンバーシップ関数が１つの区間で微分可能ならば、高速に変更候補値を求めることが可能である 