ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to

Presentation on theme: "ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to"— Presentation transcript:

1 ファジィ制約充足問題への 連続領域の導入 Introducing continuous domains to
fuzzy constraint satisfaction problems 須藤　康裕 Yasuhiro Sudou 三田村　保 Tamotsu Mitamura 大堀　隆文 Takahumi Oohori 栗原　正仁 Masahito Kurihara

2 目次 はじめに 制約充足問題とは 離散領域の問題点 連続領域の導入 反復改善アルゴリズムの適応 変更候補値の算出方法 計算例 おわりに

3 制約充足問題とは 有限で離散的な領域　　　　　から値を選ぶ複数の変数　　　　　に対して、全ての制約　　　　　を満たすような値の割り当てを探し出す問題 ファジィ制約充足問題 通常の制約充足問題の制約に、ファジィ関係を　導入し充足に程度が存在する最適化問題の一種 拡張

4 制約充足問題の例 ：制約 隣接するノードと異なる色にする 制約充足問題（グラフ色塗り問題）の例 領域 X1 X2 X3 X４ X５ X６
変数 領域 X1 青，黄 X2 X3 X４ X５ X６ X1 X2 X3 X6 X2 ：制約 隣接するノードと異なる色にする X3 X4 X5 X6 　制約充足問題（グラフ色塗り問題）の例

5 離散領域の問題点 離散的である 有限である 領域を多く持つ必要があるときに 探索範囲を広げてしまう
例： Di = {1, 2, 5, 9, 12, …} 領域を多く持つ必要があるときに 探索範囲を広げてしまう

6 連続領域の導入 離散的な領域の他に、連続領域をドメインに加える 混合領域制約充足問題と定義 さらに適切な解が得られるようになる
離散的な領域だけで定式化するより、高速に解を得ることができる

7 混合領域制約充足問題の定義 ファジィ制約充足問題の変数領域に連続領域を導入する 領域を と定義する
領域を　　　　　　　　　　と定義する lj=ujの場合、離散的な領域と同じである 例： Di = {1, [2, 5], 7, [9, 12], …}

8 反復改善アルゴリズムの適応 領域を離散化せずに探索可能な アルゴリズムを適用する必要がある
そのままでは通常のCSPの為のアルゴリズムが使用できない 領域を離散化すると不都合がある 領域を離散化せずに探索可能な アルゴリズムを適用する必要がある

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

10 最悪の制約違反に関係する全ての変数の変更候補値を求める必要がある
反復改善アルゴリズム 制約違反が減少するように変数の値を１つずつ変更していく ファジィ制約充足問題では最も違反している制約違反を改善する 最悪の制約違反に関係する全ての変数の変更候補値を求める必要がある

11 反復改善アルゴリズム 最も違反している制約の有する全ての変数の変更候補値を算出する
全ての変更候補値の中で、最も値の大きいものを持つ変数の値を変更する 最悪の違反が減少しない場合は隣接する変数の値を変更していく 繰り返し

12 変更候補値の算出方法 X Xa X1 Xn C C1 Cn C：最悪の制約違反 変数 X の値を変更する場合その他の変数を全て固定して考える

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

14 計算例 領域： A C B C1 C2 C3 DA = 1, 2, [3, 7], 9 DB = 4, 5, [6, 10]
DC = [0, 3], [6, 8] 制約： C1 = A(A-2B) C2 = 2A-C C3 = C(B-C) VA = 3 VB = 6 VC = 7 初期値：

15 計算例 １段階目 A について変更候補値を求める場合C1とC2についてBとCを固定
VA = 3 VB = 6 VC = 7 C1 = A(A-2B) = -27 C2 = 2A-C = -1 C3 = C(B-C) = -7 DA = 1, 2, [3, 7], 9 A C B C1 C2 C3 計算例 １段階目 DB = 4, 5, [6, 10] DC = [0, 3], [6, 8] A について変更候補値を求める場合C1とC2についてBとCを固定 B について変更候補値を求める場合C1とC3についてAとCを固定 C1 = 9-6B C2 = 2A-7 C3 = 7B-24 C1 = A(A-12) クリスプな領域： クリスプな領域： VA = 1：-27 → -11 VA = 2： -27 → -20 VA = 9： -27 → -27 VB = 4：-27 → -21 VB = 5： -27 → -14 ←連続領域： ←連続領域： VB = 6：-27 → -27 VA = 3：-27 → -27

16 計算例 ２段階目 B について変更候補値を求める場合C1とC3についてAとCを固定
VA = 1 VB = 6 VC = 7 C1 = A(A-2B) = -11 C2 = 2A-C = -5 C3 = C(B-C) = -7 DA = 1, 2, [3, 7], 9 計算例 ２段階目 A C B C1 C2 C3 DB = 4, 5, [6, 10] DC = [0, 3], [6, 8] B について変更候補値を求める場合C1とC3についてAとCを固定 C について変更候補値を求める場合C2とC3についてAとBを固定 C3 = 7B-49 C3 = C(6-C) C1 = 1-2B C2 = 2-C ←連続領域： クリスプな領域： VC ≒0.3： -11 → -1.7 VB = 4：-27 → -21 VB = 5： -27 → -14 ←連続領域： A, Bについては現在の割り当てが最善なので C を変更する VB = 6：-11 → -11

17 計算例 ３段階目 A について変更候補値を求める場合C1とC2についてBとCを固定
VA = 1 VB = 6 VC = 0.3 C1 = A(A-2B) = -11 C2 = 2A-C = 1.7 C3 = C(B-C) = 1.71 DA = 1, 2, [3, 7], 9 A C B C1 C2 C3 DB = 4, 5, [6, 10] DC = [0, 3], [6, 8] A について変更候補値を求める場合C1とC2についてBとCを固定 B について変更候補値を求める場合C1とC3についてAとCを固定 C1 = 1-2B C1 = A(A-12) C3 = 0.3(B-0.3) C2 = 2A-0.3 クリスプな領域： クリスプな領域： VA = 1：-27 → -11 VA = 2： -27 → -20 VA = 9： -27 → -27 VB = 4：-11 → -7 VB = 5： -11 → -9 ←連続領域： 連続領域： 1段階目を参照 VB = 6：-11 → -11

18 計算例 ４段階目 A について変更候補値を求める場合C1とC2についてBとCを固定
VA = 1 VB = 4 VC = 0.3 C1 = A(A-2B) = -7 C2 = 2A-C = 1.7 C3 = C(B-C) = 1.11 DA = 1, 2, [3, 7], 9 A C B C1 C2 C3 DB = 4, 5, [6, 10] DC = [0, 3], [6, 8] A について変更候補値を求める場合C1とC2についてBとCを固定 B について変更候補値を求める場合C1とC3についてAとCを固定 Bは直前に変更したばかりなので最善な割り当てである C1 = A(A-8) C2 = 2A-0.3 クリスプな領域： VA = 1：-7 → -7 VA = 2： -7 → -12 VA = 9： -7 → 9 連続領域： VA = 7：-7 → -7

19 計算例 ５段階目 B について変更候補値を求める場合C1とC3についてAとCを固定
VA = 9 VB = 4 VC = 0.3 C1 = A(A-2B) = 9 C2 = 2A-C = 17.7 C3 = C(B-C) = 1.11 DA = 1, 2, [3, 7], 9 A C B C1 C2 C3 DB = 4, 5, [6, 10] DC = [0, 3], [6, 8] B について変更候補値を求める場合C1とC3についてAとCを固定 C について変更候補値を求める場合C2とC3についてAとBを固定 C1 = 81-18B C3 = C(4-C) C3 = 0.3(B-0.3) C2 = 18-C ←連続領域： クリスプな領域： VC =2： 1.11 → 4 VB = 4：0.1 → 1.11 VB = 5：0.1 → -9 ←連続領域： VB = 6：0.1 → -7

20 計算終了 これ以上どの変数の値を変更しても違反が改善されない局所最適状態 C1 = A(A-2B) = 9 VA = 9
VB = 4 VC = 2 C1 = A(A-2B) = 9 C2 = 2A-C = 17.7 C3 = C(B-C) = 4 これ以上どの変数の値を変更しても違反が改善されない局所最適状態

21 おわりに 制約充足問題に連続領域を導入することに成功した
制約を表すメンバーシップ関数が１つの区間で微分可能ならば、高速に変更候補値を求めることが可能である