| 内容要旨 | | 1研究の背景と目的 制約充足問題(Constraint Satisfaction Problem:CSP)とは,与えられた制約を充足する値の組合せを求める問題の総称である.制約の性質として,制約の順序に依存せず制約の並びをいかようにも変える事が可能であるため,従来の推論技術よりもより広い範囲に応用可能である.また人工知能の領域における様々な問題は,いくつかの変数と制約により記述可能であるためCSPにより定式化可能であり,実際にスケジューリング・図形処理・言語処理等の問題は制約充足問題として解く事ができる.この様な応用の広さによりCSPは人工知能の基盤技術の一つとして位置付けられており,CSPに関連した研究が多く行われ,様々なCSPの解法が提唱されている.また個々の制約に対し重みを設けることにより制約問題を最適化問題とした問題も存在する.このような重みをつけた制約問題は制約最適化問題(Constraint optimization problem:COP)と呼ばれ,実世界に存在する問題を記述する際によく用いられている. しかしながら実際の問題では過制約となることが多々あり,従来の制約充足問題の解法では解無しとなることが多くあった.このような過制約の問題は,部分的に制約違反を認めつつ,多くの制約を満たす解を探索することにより解ける.このような問題の事を不完全制約充足問題(Partial CSP:PCSP)と呼ぶ.PCSPのうち,重みが付加され最適化問題としたものを不完全制約最適化問題(Partial COP:PCOP)と呼ぶ. ここではPCOPを0-1整数線形計画問題(Integer Linear Problem:ILP)に帰着させ,これを解くことによりPCOPの解を得る手法について述べる.ILPの解法としてはILPの緩和問題である線形計画問題(Linear Problem:LP)の解を単体法で求め,LPの解である実数解のうち適当なものを0-1に丸めることにより,問題規模を縮小させたILPをつくることを繰り返す手法を用いており,これによりILPの準最適解を求めている. 2方法2.1PCOPからILPへの帰着 PCOPの制約を置き換えることで常に制約が満たされるようにし,ILPへの帰着を行うことで,ILPの解がPCOPの解となる.ここで如何にPCOPの制約を置き換え常に制約が満たされるようにするかが鍵になる. そこでノードiとノードjとの間のアークdi:djにFalseなるアーク制約要素を設ける.Falseはノードiとノードjが如何なる値をとっても成立するアーク制約要素である,これにより,どのような場合でも常に元々のアーク制約要素もしくはFalseが成立することでアークが成立し,常に制約を満たすようにPCOPを置き換えることができる. Falseを用いて置き換えられたPCOPのILPへの帰着は,ノードの値の一つ一つ・アーク制約の一つ一つ・制約そのものを0-1変数に割り当て,この0-1変数を基にして制約式と目的関数を作る方法により実現される.ILPへの帰着においてFalseについてはアーク制約に含まれず,制約そのものの0-1変数として表される. 2.2単体法の反復適用 先に示した変換により得られるILPは0-1整数計画問題である.ILPの解法は様々なものがあり,0-1整数計面問題の近似解法としては掃き出し補数法があげられる. しかしながら,PCOPをILPに帰着したものは,元のPCOPが制約が強いためすべて満たせないにも関わらず,局所制約伝播による整合化が困難である特徴を持つ.そのためILPの最適解周辺でのコスト平面は凸凹が多く局所最適が数多くあり,単純に局所探索を行うことでは近似最適解を得ることは困難であると考えられる. そこでILPの緩和問題の実数最適解を求め,実数解のうち適当なものを0-1に丸めることにより,問題規模を縮小させたILPをつくる,縮小させたILPも同様に実数最適解を求め,さらに縮小させたILPをつくる.この手法を適当回数繰り返すことにより,最終的なILPの解を得ることとした.ここで緩和問題の解法として単体法を用いることで高速化をはかった.また各々のILPの緩和問題の実数最適解の周りについても所探索を行うことにより,準最適解が得られるようにした. 0-1整数計画問題の最適解は実数最適解の近傍にあるとは限らず,離れている場合がしばしば存在する.このような場合,実数最適解に対してすべての変数について丸めを行い近傍探索を行うだけでは局所最適に陥る.これに対し一部の変数について丸めを行い,再度実数最適解を求めることにより,当初の実数最適解から離れることができ,局所最適を逃れつつ準最適解を求めることが可能となる. 丸めを行うノードは,丸めによる制約状態への影響が少ないノードが選ばれる.制約状態への影響は,丸めによる変数の変化と考えられるため,実数最適解と整数解との差が最も少ない変数に対して行うのが良いと考えられる.また丸め先は,実数最適解と丸め先の整数解との差が最も小さくなるように選ばれる. 2.3実験方法 PCOPの問題として広く用いられている,グラフの塗り分け問題を使用した.ノードの数・一つのノードの要素数・アークの密度・アーク制約要素の密度をパラメータとし,計算時間・解の値の比較評価には,全解探索により最適解が得られるPBB(Partial Branch Bound)および準最適解が得られるGSATを用いた. ノード数による計算時間の変化,PBBとの計算時間・解コストの比較,GSATとの計算時間・解コストの比較を行った. 3結果 ノード数による計算時間の変化は,全体の傾向としてはノードの数が増えると急に計算時間が延る.しかしながら一回毎の単体法の計算時間を見ていくと,合計の計算時間の延びと比較してそれほど急には延ていない結果が得られた.またアーク密度が高い問題やアーク制約要素密度が低い問題,すなわち制約のきつい問題では単体法の計算時間が長くなる結果が得られた. PBBとの比較では,計算時間は一部PBBの方が速い結果が得られたが大部分は単体法の反復適用の方が速い結果が得られた.解コストの比は全体の平均をとるとPBBの1.16倍となり,アーク制約密度が高いもしくは低い場合に低くなり,0.6付近で悪い値をとる. GSATとの比較では,計算時間はアーク制約要素密度が高い問題では2桁近く速く解が得られているが,アーク制約要素密度が低い問題では同じ程度から数倍程度遅くなった.解コストはアーク制約要素密度が高い問題ではGSATより良い結果が得られる場合が多くあるが,アーク制約要素密度が低い問題ではGSATとほぼ同じかやや悪い結果となった. 4考察 ノード数による計算時間の変化は,最終解を得るまでに必要とされる単体法の計算回数が増えるためと考えられる.単体法の計算時間は単体法の制約の数もしくは変数の数により変化するが,計算時間のオーダはほとんどの問題において制約の数や変数の数の多項式オーダーであると考えられる.一方単体法の繰り返し回数はノード数の多項式オーダである.よって本手法の計算時間は,ほとんどの問題において,多項式オーダーであると考えられる. PBBとの比較で計算時間が一部PBBの方が速いのは実験に用いたノード数が10と小さいためと考えられる.実際の問題では,PBBの計算時間はノード数の指数オーダとなるので,本手法の方が速いと考えられる. GSATとの比較でアーク制約要素密度が低い問題で計算時間がかかるのは単体法の一回当りの計算時間が延びているためである. アーク制約要素密度が低い問題はコスト平面上に局所最適となる小さな穴が数多く開いているものと考えられ,アーク制約要素密度が高い問題はコスト平面上に局所最適となる大きな穴が幾つか開いているものと考えられる.そのため,アーク制約要素密度が低い問題では,単体法の反復適用により最適な穴の近傍にたどり着くが,そこからの近傍探索に失敗することにより局所最適に陥るものと考えられる.一方アーク制約要素密度が高い問題では,最適な穴の近傍から探索に成功しやすいため,準最適解が得られているものと考えられる. 5結論 本稿ではCSPの拡張であるPCOPについて,その解法の手法について示した. スケジューリング問題など現実の問題の多くはCSPによって記述する事で効率的に解が得られるが,実際には相反する条件あるなどCSPの範疇では処理不可能なものが数多くあった.これに対しPCOPを用いる事で相反する条件も含めあらゆる条件が記述できるため,応用範囲が大きく広まるものと考えられ,PCOPの解法は有効であると考えられる. |
| 審査要旨 | | 本論文は「単体法の反復適用による不完全制約充足問題の解決の研究」と題し、人工知能分野等で基盤となっている制約充足問題(Constraint Satisfaction Problem,CSP)の拡張に位置付けられる、過制約で部分的に制約違反を許容して多くの制約を充たす解を求める不完全制約充足問題(Partial CSP,PCSP)、及び制約や取り得る値に重みが付された状況下で最適解を求める不完全制約最適化問題(Partial Constraint Optimization Problem,PCOP)の効率的解法の研究について記している。 第1章は序論であり、第2章で本論文で対象とする上記のような制約充足問題について記し、その既存の解法について説明している。不完全制約充足問題(PCSP)、不完全制約最適化問題(PCOP)のこれまでの解決には、1)不完全分技限定法、2)不完全バックマーキング法、3)Arc Consistency Countの方法、4)不完全フォワードチェッキングの方法が使われている。しかし、PCSP、PCOPは制約違反を許容するために、局所制約伝播による整合化の適用が困難になる等で解計算速度が不十分な状況にあり、有効な効率化手法が必要とされている背景について述べている。 第3章では、本論文で活用する線形計画法について、単体法(シンプレックス法)と0-1整数計画法を中心にまとめている。数理計画法は実数の多次元空間での最適化問題を扱う数学的色彩の強い分野であり、離散的な記号操作を主とする人工知能、知識処理の手法とは異なる分野と見なされてきたが、実は密接な関係があることを記している。特に、知識処理で数値的に評価可能な最も良い解、最も好ましい解といった最適解を求める場合は数理計画法との関係は深く、本論文はこの観点から行った研究となっている。 第4章「不完全制約最適化問題から0-1整数計画問題への帰着」では、本論文でPCOPを数理計画法の手法を活用して解く際に必要となる、不等式制約と最小化を図る目的関数の構成法について論じている。充足されないアーク制約を持つ解も許容するPCOPを効率的に扱うために、可能な値の組が存在しないアーク制約をまとめて表すFalse制約要素の導入を図っている。これらによってPCOPを0-1整数計画問題へ帰着できることになるが、この帰着による問題規模の変化についても示している。 第5章は「単体法の反復適用による高速解法の原理と論点」と題し、考案した単体法の反復適用による解決について論じている。これはPCOPを0-1整数計画問題へ帰着した問題を解くものであるが、問題規模に対して指数的に増大する時間を要する最適解計算でなく、準最適解計算を行う近似解法による高速化となっている。0-1整数計画問題の近似解法としてはこれまでに、掃き出し補数法等の単体法による実数最適解の近傍を局所探索する方法が存在した。しかし、PCOPから帰着された問題は元のPCOPの制約がきついことにより全てを充たせない場合を主として扱うので、最適解周辺でのコスト平面は凹凸が多く、局所最適解が数多く存在し、単純に局所探索を行うことでは(準)最適解を得ることは困難となる。 そこで、本論文では0-1整数計画の実数緩和問題の実数最適解を単体法で求め、この実数解のうちで適当な部分を0-1に丸めることにより、規模を縮小した問題とする。この縮小問題も同様に実数最適解を求め丸めを行うことにより、更に縮小した問題を作り、これを反復して最終的に0-1の準最適解を得る。単体法の実数最適解近傍の局所探索よりも、当初の実数最適解から離れた位置に存在するより良い解も探索することになり、改善が達成されることになる。なお、実数最適解近傍の局所探索も有効であるので、この機能も組み入れている。0-1への丸め操作は基本的に丸めによる制約状態への影響が少ない部分について行うのであるが、この方法と影響について考察している。 第6章「不完全制約充足問題の単体法反復適用による解法システムとその評価」では、第5章の原理に基づいて作成したシステムについて記し、その性能評価を重み付けグラフ塗り分け問題を対象にして行った結果を示している。丸め操作の範囲を決定する境界値は実験に基づき定めている。作成した解法システムの性能は、最適解を求める部分分技限定法(Partial Branch and Bound,PBB)と、近似解法として局所最適解への捕捉時にはランダムリスタートを行う0-1離散値空間での降下法であるGSAT法と比較することにより示している。 PCOPノード数による計算時間の変化は、全体の傾向としてはノード数の増加につれて時間が増大することになるが、各回の単体法の所要計算時間は急速には増大せず、これにより全体として指数オーダ以下の計算時間が得られる結果となっている。 PBB法は指数オーダの計算時間となるので大幅な速度向上が図られることになり、また準最適解の品質は解コストで比較するとPBB法による最適解の全体平均で16%増し程度であり、1/3程の問題で最適解が得られた結果を示している。GSAT法との比較では、制約の緩い問題に対しては計算時間は1桁から2桁近く高速になるが、制約がきつい問題の場合には同程度になることを示している。解の品質についても同様の傾向であり、制約の緩い問題に対しては優位となるが、制約のきつい問題には同程度となっている。実用的にはここで言う制約の緩い場合が大部分となるので、本手法が有効となる。制約のきつい問題に対して本手法が必ずしも十分でない要因については、コスト平面の形状に基づいて考察している。 本論文のシステムの実用的応用として、当番表割り当て問題について具体例を示し、その他の応用可能性についても言及している。 第7章では本論文の成果と今後の課題についてまとめている。 以上を要するに、本論文は制約充足問題の拡張であり、これまで有効な効率的解法が存在しなかった制約や取り得る値に重みが付された不完全制約最適化問題(PCOP)を対象にして、その準最適解の高速計算には連続値領域で動作する数理計画法の手法の活用が効果的であるとの観点から、単体法と0-1値への丸め操作の反復適用による解法を考案し、そのシステムを実装して、解を計算する速度性能等を実験的に実証して有効性を示したものであり、電子情報工学上貢献するところが少なくない。 よって本論文は博士(工学)の学位請求論文として合格と認められる。 |