研究方針

問題点

　本研究で対象とする実際の問題において、計算機で自動的に解を求めるためには、 以下のような問題点があるため、実用のシステムの開発が難しい。

1. 問題解決に必要な制約が多種多様であり、計算機で表現しきれない。
2. 探索空間が膨大であり、通常の探索手法（特に厳密解法）では効果が期待できない。

基本方針

　そこで、以上の問題点を解決するために、以下のような方針とした。

《制約違反点数》

　制約の重要度を違反点数で表現することにし、制約違反点数の合計を最少化することを目的とする。

《制約の整理分類》

　制約の適用対象ごとに整理・分類し、各制約の参照データを明確にすることで、少数の分かりやすい制約にまとめる。

《探索手法》

　初期値を与え、それから反復改良していくことで解を求める探索手法である、制約違反点数を最少化する戦略を用いた山登り法（MCHC）を導入する。 初期値として、既存のデータ（時間割編成なら過去の時間割）を用いることも可能である。 また、初期値は厳密な解ではなく、適当に制約を大体満足しているという程度でよく、他の手法で簡単に作成ができる。

《対話型システム》

　制約として計算機表現の難しい要求事項や人間の知識を編成に活かすため、ユーザと協調して探索を進める対話型システムとする。 また、MCHCでは問題によって局所最適解に陥りやすい（制約密度の小さい問題）欠点があるが、これを人間の知識を対話によって回避する。