フォルマント兄弟の「和音平均化旋律・運指法計画」で用いられている制約プログラミングについて（２）
フォルマント兄弟の「和音平均化旋律・運指法計画」
2013.2.24 大垣、ソフトピアジャパン：フォルマント兄弟(三輪眞弘＋佐近田展康)、山崎雅史
「MIDIアコーディオンによる合成音声の発話及び歌唱の研究」総括報告・シンポジウム
2014.2.22 大垣、ソフトピアジャパン： フォルマント兄弟(三輪眞弘＋佐近田展康)、久保田晃弘、福田貴成、山崎雅史
「MIDIアコーディオンによる合成音声の発話及び歌唱の研究」（新しい時空間における表現研究）
日本学術振興会科学研究費補助金研究・基礎研究(C)研究課題番号23520175
2014.2.22の総括報告における発表用スライドは以下からダウンロードできます。
フォルマント兄弟の「和音平均化旋律・運指法計画」への制約プログラミングの適用
2013.2.23の中間報告での発表用スライド・補足資料は以下からダウンロードできます。
フォルマント兄弟の「和音平均化旋律・運指法計画」（スライド）
フォルマント兄弟の「和音平均化旋律・運指法計画」（補足資料）
2.制約プログラミングとその周辺
2.1.制約プログラミングの定義
制約プログラミングとは何か、という問いに対する答えは、制約プログラミングに関わる人の立場により様々だろうが、 ここでは、それは問題を解くための手法であり、(a)問題を変数の集合と、その変数間に存在する制約の集合として定式化する モデルリング手法と(b)問題空間が持ちうる状態の中から、制約を充足する状態を求めるために、制約を有効に使って効率的に 解を求める手法を備えたものであるとする。プログラミングパラダイムの観点から見た場合の特徴は、問題の宣言的な記述と 求解アルゴリズムの分離であり、記述のためのシンタクスが処理系毎に定められ、処理系が備えている汎用のソルバーを使って 問題を解くことになる。通常のプログラミングにおいては、データ構造の宣言とともに、問題を解くためのアルゴリズムを 記述することがプログラミングの中心であるのと比較して、かなり違ったパラダイムであり、アルゴリズムを明示的に 与えようとすると条件の分岐が多くなりすぎて、事実上解くプログラムの記述が困難な問題を解くためのものと考えることができる。 更には、確率を導入する拡張は可能であるものの、基本となるモデル上では制約は決定的であると見做される。（条件付制約下での 制約充足解を求めるためには、非決定的な探索が必須となるが、条件つきの制約自体は静的に決定的に宣言可能である。）
2.2.数理計画法
実際には、上記の定義は非常に広くて、「制約」の記述形式の制限や「探索」の方法を限定しなければ、狭義での制約プログラミングでは ないものも包含してしまう。例えば問題を連立方程式や連立不等式の組で表現した時の様々な求解アルゴリズムはそれらの中に 含まれてしまうことになるだろう。それらの中で特に、目的関数の値を最適化する変数の組を求める手法は数理計画法と 呼ばれる領域を形作っており、連続変数に対する制約なしの非線形最適化手法であるニュートン法や同じく連続変数に対する 一次連立不等式の制約つきの一次式の最適化手法である線形計画法なども含まれることになる。
線形計画法の求解アルゴリズムとしては非常に長い産業応用の歴史を持つダンツィヒによる単体法や、ひと頃特許騒動で 有名になったカーマーカー法を含む内点法などが有名であるが、これらは汎用の求解アルゴリズムであり、問題を 定義した制約不等式をマトリクス表示した入力を読み取り、目的関数を最適化する変数の値の組をベクトルとして出力する ソルバーが提供されている。これらのアルゴリズムは問題の複雑さに比して高速であり、制約条件を用いて解の存在領域を狭めていき、 効率的に最適解に辿り着くことができるため、大規模な実用的な問題への数多くの適用事例を持っている。
一方で変数の一部を 整数値に制限した混合整数計画問題、凡ての変数を整数に制限した全整数計画も定式化可能であるが、これらは 連続変数における単体法や内点法のような高速なアルゴリズムがなく、分枝限定法、分枝切除法のような枝刈り手法を 用いた探索をすることになるため、線形計画問題に比べて実用的な時間で解ける規模は制限される。その中で、変数を [0,1]のいずれかをとる離散変数（0-1変数と呼ばれることが多い）に限定した上で専用の効率的なアルゴリズムを 用いる、0-1整数計画問題の研究も行われている。
2.3.論理プログラミング
他方で、人工知能研究との関わりで人口に膾炙するようになったProlog言語処理系を代表とする、論理プログラミングと 呼ばれる手法があるが、これは記号論理学における述語論理体系に基づくもので、非常に制限されたシンタクスの論理式 （ホーン節と呼ばれる標準形）で問題を宣言的に記述し、論理式の集合が真になるように宣言中に含まれる変数に値を 付けることにより問題を解くことを実現するものであり、求解にあたっては処理系に組み込まれたバックトラックを 用いた汎用の探索機構を用いる。対象となっている問題領域の違いはあるが、こちらも処理系がソルバーの役割をしており、 解を解く部分をプログラミングする必要がないという点では共通している。
この仕組みは形式的に非常にエレガントであり、非常に汎用的な定理の自動証明システムなのだが、問題の規模が大きくなると バックトラックに頼る探索はすぐに組み合わせ爆発を起こして、実用的な時間での求解が困難になることがしばしばであるため、 実用的なシステムにおいては、問題に合わせて探索空間の枝刈りをする処理を明示的にプログラムしてやる必要がある場合が ほとんどである。既述のように論理プログラミングは人工知能研究に関連が深く、日本でも過去、第5世代コンピュータの 開発プロジェクトなどを通じ、基礎、応用の両方にわたる多くの研究がなされたし、優れたProlog処理系が開発されている。
2.4.制約プログラミング
上述のような手法と区別されるものとして制約プログラミングを狭く捉えた場合、制約プログラミングの特徴は以下のような 点に存するであろう。(a)変数は離散的であるが、真偽の二値を持つ論理変数だけではなく、 有限の領域を持つ領域変数を持つことが多い。(b)制約のシンタクスも論理プログラミングや数理計画法に比べてより柔軟で、 論理的な制約もあれば、算術的な制約もあるし、より高水準の組み合わせ論的な制約（例えばある値の出現回数の制約など）も 可能である場合が多い。(c)制約を充足する変数の値の組を求めることが求解であり、ある目的関数の値の、制約条件下での 最適化のための手法ではない。
制約プログラミングにおける求解アルゴリズムとしては、論理プログラミング同様、バックトラック機構を用いた探索が 一般的だが、制約を用いた自動的な枝刈りの機構を備えており、制約条件によっては効率的な求解が可能である。 しかし組み合わせ爆発の問題の一般的な回避ができるわけではないので、 実用システムでは探索の制御を明示的にプログラムすることが多い。
また、制約毎に充足確率を持った確率的制約プログラミング、制約の充足に優先度を持たせたり、制約を階層化するアプローチ、 あるいは集合に対する制約を扱う演算領域の拡張など、モデルの拡張の提案も多い。一方で制約のシンタクスには形式的な 制限があるわけではなく、どのような制約を扱えるかは処理系に依存しており、上記の手法に比べて形式的に融通が利く一方で、 理論的な解析が困難であるといった研究上の難しさがある。
2.5.SAT
上述の数理計画法における0-1整数計画問題における0-1変数は、真偽の2値を持つ論理変数と等価であるが、 制約プログラミングにおいても変数を0-1の2値変数に制限し、制約式のシンタクスにも制限を加えた上で 高速な汎用アルゴリズムを与えるSATと呼ばれる手法の研究が近年急速に進展している。
高速なSATソルバーの提供が行われるようになってきており、通常の離散有限の領域変数とそれらの間の制約として モデル化した問題をSATに変換し、SATソルバーで解いた後、結果を逆変換して元の問題に戻してやるといった 解き方も可能になっているが、変換にかかるコストが大きいことや、通常の有限領域の変数上の制約として 定義された原問題に対して変換後のSATの問題が極めて大規模になる傾向にあることから、実用上は適用可能な シーンが限定されることも現時点では少なくない。しかし他方で問題の形式が制限されて理論的な解析がしやすいことから、 今後も改善が行われていくものと考えられる。制約充足問題における相転移現象の研究が行われているのも この領域であり、近年注目を浴び、急速に研究が進展している分野である。
2.6.諸手法間の関係
上記の幾つかの手法は、問題を記述する変数の性質や制約式の形式に関する制約が異なってはいるが、いずれも 問題を宣言的に定義し、汎用の求解アルゴリズムを実装したソルバーを提供して、アルゴリズムを明示的に書くのが 困難な問題を解くための手法である点は共通しており、実際に研究において相互に影響を与え合っている。 制約充足問題の汎用ソルバーの中に、上記の様々な手法による複数のソルバーを備え、問題によってソルバーを 使い分けることができるようにする試みも日本国内で既に研究成果がある。
実用的な問題解決の場面でも特に問題が大規模な場合に、幾つかの手法を組み合わせて用いることしばしば行われている。 一般に問題の形式が特に具体的に特定の構造を持つ場合には、それ専用のアルゴリズムを開発すれば良く、 汎用的で遅い方法に拘る必要はない。特に既知のアルゴリズムが知られている形式に現実の問題を帰着させることが できる場合には、既知のアルゴリズムを用いれば良い。いずれの場合でもアルゴリズムの計算量への配慮は必要であり、 規模によって適用可否を見極めて、適切な解法を選択する必要がある。
数論の分野に例を求めると、例えば2つの整数の最大公約数を求めるアルゴリズムであればユークリッドの互除法という O(logN)の高速なアルゴリズムが知られているが、素因数分解は計算複雑性理論上困難な問題であるとされており、 総当りで2から順に√nまでの素数で割っていくという単純な方法では、数が少し大きくなると計算時間が 爆発して実用的ではなくなる（この性質に依拠するのが現在、公開鍵暗号として一般的なRSA暗号である）。 そのため大きな数に対しては、ポラード・ロー法、連分数法、楕円曲線法、各種の篩法など、様々な アルゴリズムが提案されていて、目的に応じてそれらの特徴を見極めて利用することになるだろう。 （例えばポラード・ロー法はフロイドの循環検出法に基づく擬似乱数を用いる確率的なアルゴリズムであり、 実行時間と素因数発見確率がトレードオフの関係にあることが知られていて、対象となる数が素数の場合には 常に失敗することが保証されているが、合成数であっても失敗する場合があることに注意しなくてはならない。）
2.7.量子コンピュータ
一方で、量子コンピュータを用いれば、現在事実上求めることが難しい大きさであっても、遥かに少ない計算回数で 素因数分解を行うことができることが1994年にショアにより示されている。量子コンピュータの研究領域の一つは、 従来、解く事が困難であった問題を少ない計算量で求める手法の研究であり、初期の成果として、探索問題に対する ドイチュとジョサの解法があるのも良く知られている。
量子コンピュータは状態を重ね合わせて持つことができるという量子の性質を用いているのだが、それが候補の状態を 保持できる領域変数の（ごく粗いものではあるけれど）アナロジーになっていて、非常に興味深い。ただしこちらは状態の 重ね合わせを単なるビット列で持つに過ぎないからアナロジーは極めて肌理の粗いものに過ぎないのだが、それでもなお、 量子コンピュータが実用化されることになれば、量子制約プログラミングというのが成り立つのではないかと考えることは できるだろう。例えばセス・ロイドの著作（Seth Lloyd, "Programming the Universe : A Quantum Computer Scientist Takes on the Cosmos", 2006, 邦訳：「宇宙をプログラムする宇宙－いかにして「計算する宇宙」は複雑な世界を創ったか？」, 水谷淳訳, 早川書房, 2007） を読んで、そういう印象を抱いたことがある。
2.8.制約プログラミング適用にあたっての留意点
制約プログラミングを用いて個別の問題を解くことに話を限定した場合でも、隣接、関連する他の分野においてと同様に、 一つの問題に対する具体的なモデル化や求解のアプローチには多様な可能性がある。また、解かなくてはならない 現実の問題の持つ性質や求解にかけられる時間や求解の目的（例えば充足解の存在の証明か、全ての充足解の列挙か、 好ましい性質をもった充足解を手早く見つけることか、等）や求解のための時間の制限、あるいはメモリのサイズ等の 条件に応じて、変数のモデルを作り、解の探索の制御をしてやる必要がある。問題を分割して一部のみに制約プログラミングを 適用することが必要なケースもあるだろう。
従って、現実の問題を制約プログラミングを用いて解く場合には、 問題を表現する変数を定め、問題の持つ制約条件を変数間の制約として記述するモデリングの作業と、問題を解く求解 アルゴリズムに対して、実用的な時間で必要な答えを得るための探索の制御を決める作業が重要であるということになる。
(2014.2.2初稿, 2.9, 11改訂, 2.11公開, 2.14, 2.19加筆・修正, 2025.1.18 noteにて公開)