制約処理の新展開とハイブリッドドメイン・ファジィ制約充足北海道工業大学須藤康裕はじめに制約充足問題とは、 n { D } 有限で離散的な領域 i i 1 から値を選ぶ複数の変 n r 数 {X i }i1 に対して、全ての制約 {Ck }k 1 を満たすような値の割り当てを探し出す問題変数領域 X1 青、赤 X2 青、赤 X3 青、赤 X4 青、赤図１．制約充足問題（グラフ色塗り問題）の例制約充足問題に関する研究の最近の動向（文献：横尾氏、平山氏による）より現実的な問題を表現するために、 • 分散 -アルゴリズムが局所情報のみで動作 • 動的 -時間と共に制約が変化 • 不完全 -制約が強くて解が存在しない等の新しいタイプのCSPが研究されているこれらの研究を背景にハイブリッドドメイン・ファジィCSPを提案構成～主な研究の内容 1. はじめに制約充足問題とは、研究の背景 2. 分散制約充足システムのJavaRMIによる実装 3. スケジューリング問題に特化した動的制約充足問題の解の質の向上 4. 不完全制約充足問題の探索停止条件 5. ハイブリッドドメイン・ファジィ制約充足問題 6. おわりに 1. 分散制約充足システムの JavaRMIによる実装分散制約充足問題とは、制約充足問題の変数がネットワーク上のノードに分散された問題で、ノード間通信によって解を探索するノード変数ノードノード制約変数制約変数図２．制約ネットワーク PaintColor エージェントの生成を依頼 RMIServer エージェントを送る CalcServer エージェントを割り振る：コンピュータ CalcClient CalcClient CalcClient ：エージェント図３． JavaRMＩによる分散制約充足システムエージェントは分散breakoutアルゴリズムによって自分自身の値を決定する図４．分散グラフ色塗りシステムの実行画面２．動的制約充足問題とスケジューリング問題動的制約充足問題とは、通常の制約充足問題の列 {Pi }in0 であり、Piは Pi-1に対して制約を追加するなどの変更が加えられて得られる Job Domain A 1,2 B 2,3 C 3,4 D 1,4,5 Job Domain A 1,2 B 2,3 C 3,4 D 1,4,5 E 2,5 図５．制約が変更された例（変数が増加）実験の目的：・動的制約充足問題の解として求められるもの • 計算時間の短縮 • 解の安定性解が複数存在する場合これらを犠牲にすることなく解の質を高めることが可能かどうか確認実験：ジョブの実行時刻Tzから最後に変数を変更した時刻Txを引いた値をTyとする。 Ty = Tz – Tx ：余裕とする • • • • • 時間を１単位時間づつ進める実行に移るジョブを削除 Tyをカウントするランダムでジョブを追加問題を解く 80 70 70 60 60 50 50 40 先後中 30 20 30 20 10 0 0 先後中 40 10 1 2 3 4 5 6 7 8 9 10 11 12 13 中後先 14 15 ジョブを納期までの余裕で降順 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ジョブを納期までの余裕で昇順図６．ジョブとドメインの順序を入れ替えた結果中後先 15 ３．不完全制約充足問題の探索停止条件不完全制約充足問題とは、制約が強過ぎる過制約な制約充足問題すべての制約を満たす解が一般には存在しない反復改善型のbreakoutアルゴリズムでは計算を途中で止める必要があるこれまでの探索停止条件：停止しないときがある制約充足数＞十分値提案する探索停止条件： • 最長有限連の長さがあるしきい値θ を越えたときに停止する最長有限連の長さ＞ θ ∵無限連が生じて必ず停止するいつか連の長さが θを越える 90 A，B，C，D，E：連 80 A 制約違反数 70 60 B 50 最長有限連 40 C 30 20 D 10 無限連 E 0 1 101 201 301 401 501 601 701 801 901 1001 1101 1201 1301 1401 1501 1601 1701 1801 1901 2001 ステップ数（時間）図７．最長有限連