共同開発者： 田村 直之 （神戸大学 工学部 助教授）
井上 克己 （神戸大学 工学部電気電子工学科 助教授）
川村 尚生 （鳥取大学 工学部知能情報工学科 助手）
制約解消系とは、簡単に言うと連立不等式など変数の間の関係を表す算術式や論理式の解を求めるための仕掛けで、生産スケジューリング、資源割り当てなどの問題を解決するために利用されている。近年では、多様で複雑な問題を解くために複数の制約解消系を組み合わせて協調制約解消システムとして使うことについての研究が進んでいる。
これまで開発された協調制約解消システムは、同種の制約解消問題しか扱えないものが多かったが、本プロジェクトでは各種の制約解消アルゴリズムを協調的・競争的に並列動作させることにより、単一のアルゴリズムをチューニングする以上の効果を得ることを試みる。
各種の制約解消アルゴリズムを協調的・競争的に並列動作させることにより、単一のアルゴリズムをチューニングする以上の効果を得ようという試みである。提案者はJava言語で記述されたProlog処理系の開発者であり、かつてPrologプログラミングコンテストで優勝した実績を持つ本システムの実現を十分期待できる実力の持ち主である。
また、リソースの最適配置問題や生産スケジューリングなどの分野で使われるORやAIのいくつかの技法がJavaで統一的に扱えるようになるという副次効果にも注目したい。
並列動作する複数の制約ソルバをを協調・競争させ、効率よく解を求める
ためのものであり、以下の機能を実現する。
(1) 問題記述
(2) 複数の制約ソルバの並行実行
(3) 複数の制約ソルバの分散実行
PrologからJavaへのトランスレータ処理系であるProlog Cafeは、開発者の番原氏が開発した優れた処理系だが、それをマルチスレッド化したうえで、上記の機能をすべてJava言語から利用できるように実装するものである。
HECSは協調制約解消システムであり、番原氏が開発していたProlog Cafe処理系のマルチスレッド拡張とスケジューラ、田村氏が開発していた制約処理用のクラスライブラリCream、平行動作・協調SATソルバmultisatとProlog Cafeの拡張として作られたモバイルエージェント記述言語処理系Maglogから構成する。SATソルバとは論理式が成り立つように変数の真偽値の割当て方を求める仕組みの総称である。
HECSは、上記の構造の中で次の機能を実現するものとして分担して開発が進められた。
(1) 複数の制約ソルバの並行実行機能
(2) 複数の制約ソルバの分散実行機能
(3) 複数の制約ソルバ間での解情報の交換機能
(4) 実行時間制約下での解探索機能（与えられた時間内での最善解探索機能）
(5) 複数の制約ソルバに対してCPU 資源を動的に割当てるスケジューリング機能
(6) 複数のソルバから最適なソルバを選択する機能
(7) 整数有限領域上で、最適解の探索および準最適解の確率的探索を行うソルバ(並行実行機能による実現)
(8) ブール制約問題に対するSATソルバおよび確率的SATソルバ(並行実行機能による実現)
(9) 実数領域上での線形な制約条件に対して、最適解の探索を行うソルバ(並行実行機能による実現)
CreamはJava言語で書かれた制約処理ライブラリであるが種々の方式の探索アルゴリズムを新たに実装する。
MultisatはProlog Cafe上にいくつかのSatソルバとして実装する。
MaglogはProlog Cafeに分散実行の能力を持たせるためにエージェント機構として実装する。
Creamには、次の探索アルゴリズムが新たに実装された。
・ 分岐限定法(branch-and-bound method)による最適解探索
・ Random Search 法による準最適解探索
・ Simulated Annealing 法による準最適解探索
・ Taboo Search 法による準最適解探索
・ Iterative Branch-and-Bound 法による準最適解探索
Multisatには以前から知られているアルゴリズムが実装された。
・ Bf： 全ての可能な変数割り当てに対してBestFirstで式を評価するソルバ。
・ Satz: 単位節に注目した割当てを行うDPLLベースのソルバ。
・ Walksat: 変数の割当てを乱数で生成して局所探索する確率的ソルバ。
・ zchaff: 節を加えながらbacktrack ＋2Watching Literals により割当ての伝播を行うDPLLベースのソルバ。
本プロジェクトの目的は、これらのアルゴリズムを協調的、競争的に並列動作させることにより、単一のアルゴリズムをチューニングするよりも一般的によい結果を得るということであった。そのためのコンテナとしてProlog Cafeの上で動くスケジューラが開発された。
また、Maglogは複数のコンピュータに分散されて配置されたProlog Cafeの間をつなぐためのエージェントを実現するものとして、Ruby言語およびJava言語を使用して開発されているが、実行時には基本的にJavaの環境で動作する。
| 図1:Jobshop問題での性能評価 |
図１の性能評価の例では、taboo探索の挙動がもっとも良い事が示されている。本来は、taboo探索が行き詰ったところで確率的な探索のいずれかが助けるという構図を期待していたが、今のところは微かな徴候しか窺えない。
HECSとそのサブシステムは本体部分がGPL2ライセンスで公開されており、http://kaminari.scitec.kobe-u.ac.jp/hecs/ から入手できる。(サブシステムのアルゴリズムの中にオープンソースライセンスでないものがあるので、その点に関しては上記リンクから情報を得ていただきたい)
Ａ：優れている Ｂ：期待した程度 Ｃ：もっと頑張れ Ｄ：落第
先鋭性：Ｂ：
生産性：Ａ：
完成度：Ｂ：
波及力：Ａ：
面白いシステムが出来たと思う。特に各種アルゴリズムに計算資源を割当てるためのスケジューラと分散並列実行の仕組みが実装できたことは重要で今後の実験の基盤が作れたと考える。
この種のシステムは基本的なアルゴリズムとフレームワークができた後の実験とチューニングが肝要である。今回はそこまでたどり着いていない状況が窺えるが、今後、複数のアルゴリズムをうまくスケジュールするための考察や実験を行う必要がある。また、より大きな計算機リソースを用意してこのアプローチの優位性を評価するための実験やグリッドコンピューティングの導入実験を行うべきであろう。