人工知能における様々な理論と応用の問題が制約充足問題(Constraint Satisfaction Problem:CSP)に帰着できる.例えば,図面理解やスケジューリングなどの組み合わせ探索を含むような問題は,制約充足問題としてよく研究されている.制約充足問題の解法は人工知能の基礎技術として重要な位置をしめている.

　このような制約充足問題を解く一般的な解法としては,バックトラックアルゴリズムに基づくものと局所探索(Local Search:LS)の反復改善に基づくものがある.さらに,無駄な探索をなるべく減らして探索空間を絞るために,様々な整合アルゴリズム(Consistency Algorithm:CA)が近年提案されている.一方,すべての制約を満たすことが困難或いは不可能な場合,なるべく数多くの制約を満たす,いわゆる最大制約充足問題(MAX CSP),不完全制約充足問題(Partial CSP:PCSP)の研究も近年注目されている.しかし,このような過制約問題(over constraint problem)の研究に対して,すべての制約を満たす解(厳密解)が多数存在する場合,何らかの解の評価関数を用いてよりよい解或いは最適解を求める,いわゆる制約最適化問題(Constraint Optimization Problem:COP)の研究はまだ十分に研究されていない.通常CSPでは,すべての制約を満たす解の一つを求めればよい.これに対して,COPでは「制約充足」と評価関数値の「最適化」の両方を考慮しなければならない.つまり,COPがCSPより困難な問題である.通常のCSPを解くアルゴリズムを用いて,COPを解く場合,解の精度或いは計算時間の面で効率が悪いので,新しい方法の研究が必要となる.

　一方,オペレーションズリサーチ(Operations Research:OR)または数理計画の分野においては,長い間に研究された様々な最適化問題を解くアルゴリズムが存在する.特に,線形計画法には,単体法(simplex法)という非常に効率的な解法が存在し,広く使われている.例えば,もともと人工知能領域の推論問題としてのコストに基づくアブダクション問題と仮説推論問題などを0-1整数計画問題に帰着し,それから単体法を応用すれば,効率的に解決できる.「AIとORは,どちらのほうがよいか」ではなく,両方を有効的に融合することが非常に重要であると思われる.

　我々はCOP,特に,COPの変数の値に対する重み付きのCOP(Value-based COP:VCOP)を研究対象として,数理計画法を利用した近似解法を提案している.まずVCOPを0-1整数線形計画問題(0-1 Integer Linear Programming:ILP)に帰着し,それに対応する連続緩和の線形計画問題(Linear Programming:LP)の実数最適解を求める.そして,実数最適解の周りの局所探索により整数最適解或いは良い整数近似解を求める.本論文では,この方法の特徴,原理,アルゴリズム及び評価などの詳しい内容を示す.従来の局所探索手法に比較すると,一番大きな特徴は,「数理計画法」+「局所探索」という点である.

　この方法は、近似解法として,緩い制約問題に対して平均的に解の精度においても,計算時間においても通常の局所探索法よりよいことがランダムに生成されたVCOPの例題に対する実験結果から分かる.下の図はこの方法の構成図である.

図表

　図に示すように,場合によって線形計画法の性質及び実数最適解を利用して,ILPは解がない或いは実数最適解自体が最適解であるのを判断することが可能である.通常の局所探索法では,終了条件として時間或いは反復回数の限定により設定され、解が無くても,途中で最適解を求められても,このような限定値に至るまでに終了しないため、「無解」か「最適解」かのようなことを判断することができない.もちろん,整数解がないかつ実数解が存在する場合には,ILPも「無解」のような判断ができない.

　我々は,VCOPをILPに帰着する方法として,値に基づく帰着法(略称して,値帰着法)とアークに基づく帰着法(略称して,アーク帰着法)を提案している.値帰着法ではVCOPの一つの値をILPの一つの0-1変数に対応させ,アーク帰着法ではVCOPの一つのアークをILPの一つの0-1変数に対応させる.後者はたくさんのアーク変数を用いるので,ILPを解くための計算時間が前者よりかかるが,前者に比べてよりよい実数最適解を求めることが可能である.

　局所探索法として,GSAT(Greedy Local Search Algorithm for Sat Problem)とGLS(Guided Local Search)が典型的である.前者は,特にSAT問題によく使われ,非常に有名な手法である.後者は,近年提案され,制約充足問題だけではなく,一般な組み合わせ最適化問題にも適すると思われているが,まだ広く知られていないようである.GSATは局所最適解から脱出するために,ランダムにリスタート戦略を用いている.これに対して,GLSは,局所最適解から抜け出すために,毎回局所最適解の「最悪」の特徴(feature)に対して,罰金(penalty)を与えることによって,拡張コスト関数(augmented cost function)を修正する.このような修正により探索を再開できる.

　一方,GSATとGLSに対して,我々は緩和問題の実数最適解を探索の初期値に設定する.探索空間を二つの領域,すなわち実数最適解の周りと実数最適解から離れた部分の領域に分ける.探索の戦略として,実数最適解の周りを優先的に探索し,その中の良い近似解を早く見出す.具体的なアルゴリズムとして,GLSのような罰金を持っている拡張コスト関数を用いる.拡張コスト関数には,探索を実数最適解の周りに集中させるための実数最適解ガイド項或いは関数と呼ばれる部分を追加している.

　数理計画法と局所探索の橋渡しの役割を果たす実数最適解は,解空間に関する非常に重要な「大局の最適化の情報」を持っているから,これを十分に生かせば,効率よい近似法を発現する可能性があると考えられる.本研究はこのような試みの一つであるとも言える.

　本論文は「数理計画法を利用した離散制約最適化問題の解法に関する研究」と題し、人工知能等において基礎と応用の両面で重要な位置を占めている制約充足問題(Constraint Satisfaction Problem:CSP)の可能値に数値的な重みを付し、制約充足解の中でこの重みの和(コスト)が最小の解を求める制約最適化問題 (Constraint Optimization Problem:COP)の効率的解法についての研究をまとめたものであり、7章から構成されている。

　第1章「序論」では、最適解の計算は多くの工学的問題として重要であり、CSPに加えて近年COPが注目されてきたことを述べている。そして、その厳密な最適解の計算コストは非常に高いことから、準最適解の効率的近似解法が重要になることを述べ、線形計画の単体法(simplex法)の有効利用を図る本論文のアプローチの考え方を示している。

　第2章「制約充足問題」では、CSPとCOPに関して、問題の定義を記し、従来提案されてきたバックトラック型解法や反復改善による解法等について概観している。重み付きCSP、すなわちCOPの形式は値に重みを付すCOP(Value-based COP:VCOP)と、変数間の可能な関係制約を表わすアークに重みを付すCOP(Arc-based COP:ACOP)とに区分できることを記し、本論文ではVCOPの形式を対象にすることを述べている。また近年のCSP研究の新しい展開として、動的CSP、不完全CSP等の解法についても言及している。

　第3章「数理計画法」では、本研究で利用を図る数理計画の基礎的事項を整理して記している。

　第4章の「VCOPからILPへの帰着法」では、値に重みを付すVCOPを不等式制約によって表される等価な0-1整数計画問題に帰着する方法として、値に基づく帰着法(値帰着法)とアークに基づく帰着法(アーク帰着法)を提案し、少数の線形不等式制約で表す方法の検討を行っている。分析と実験的評価により、値帰着法はアーク帰着法と比べると必要な0-1変数の数が少なくなる点で有利であることを示している。

　第5章「実数最適解と整数解」では、0-1整数計画の0-1条件を緩和して単体法により効率的に求められる実数最適解と、0-1整数最適解との関係を調べるため、実数最適解の整数度と、0-1整数解の一致度を定義している。整数度が大きい程、実数最適解は0-1整数解に近く、一方、実数最適解の一致度が高い程、この0-1整数解は実数最適解に近い。実数最適解の整数度が大きい場合には四捨五入の丸め操作で0-1整数解が求められる場合があるが、これが可能になる条件を示す二つの定理を明らかにしている。また、VCOP問題を変換して得られる0-1整数計画の緩和問題を単体法で解く時、実数最適解を求める計算時間は、VCOPの4パラメータ、すなわち変数の数、変域サイズ、整数密度、アーク密度に関係していることを実験的に示している。

　第6章「実数最適解を利用した整数解の探索法」では、単体法によって得た実数最適解の近傍の準最適0-1解を求める効率的な局所探索法について記している。このような局所探索として、局所最適解に捕捉された場合に罰金を課して拡張コスト関数を修正して脱出を図り、探索を進める近年提案されたGLS(Guided Local Search)法の利用を図っている。このGLSのVCOPへ適用に際して追加した機能は、単体法によって得られる実数最適解に基づいて初期探索点を設定することと、探索がこの実数最適解の周囲を集中的に行えるようにするために、GLSの拡張コスト関数に実数最適解に関する項を加えていることである。これによって、初期探索点から出発し、局所最適点への捕捉から脱出を繰り返し、実数最適解の近くの0-1準最適解を見い出せるメカニズムを実現している。このような探索フェーズの後に、見い出した0-1準最適解の局所的な改善の可能性を試す改善フェーズも置いている。以上の本論文の手法をWOS(Walking near Optimal Solution)法と名付けている。これまでに0-1整数計画法やコストに基づく仮説推論において、単体法による実数最適解を初期探索点として局所的探索で準最適0-1解を見い出す手法が開発されていたが、これらは連続値空間で探索を行うのに対して、本論文のWOS法は0-1空間で探索を行う点が特徴と言える。

　例題を用いてWOS法の実験を行い、実数最適解の整数度が大きい程探索時間が短くなり、得られる解の最適性も良くなることを示している。元来のGLSとWOSを比較すると、平均として約1/2の計算時間を達成している。探索自体の時間はWOSはより短いが、初期探索点を得るための単体法が変数の数の増大と共に無視できなくなってきている。実験では命題論理式のSAT(Satisfiability Testing)問題の単解を求める効率的手法であるGSAT法を利用した場合との比較も行い、本WOS法が優れていることを示している。

　第7章では本論文の研究成果をまとめ、今後の課題について述べている。

　以上を要するに、本論文は人工知能等の分野で近年重要になりつつあるが計算コストが大である離散制約最適化問題(COP)において、特に値に重みを付すCOP(Value-based COP:VCOP)を対象として、数理計画法の手法の利点を利用する観点から、まず少数の不等式制約による等価な数理計画問題への変換法を示している。そして、線形計画の単体法を利用して初期探索点を定め、局所最適解からの脱出能力を有するGLS(Guided Local Search)法の機能を拡張し、単体法の実数最適解近傍を集中的に探索する能力をもつWOS(Walking near Optimal Solution)法と称する準最適0-1解の効率的探索法を考案し、実験等を通じて有効性を示したものであり、電子情報工学上貢献するところが少なくない。

　よって著者は、東京大学大学院工学系研究科電子情報工学専攻における博士(工学)の学位論文審査に合格したものと認める。