最近、制約充足問題(CSP:Constraint Satisfaction Problem)の近似解法 として制約違反最少化戦略に基づいたアルゴリズムが各種提案されて いる。これらは局所最適解からの脱出方法を中心に議論されているが、 積極的に大域的探索を行う方法はあまり見当たらない。
文献「遺伝的アルゴリズムによる制約充足問題の解法（情処研報,Vol.95, No.86,95-AI-101）」（松本他）では、遺伝的アルゴリズム(GA)の大域的 探索機能に着目して、制約違反最少化戦略をＧＡの適応度計算に当て はめ、さらに山登り法とハイブリッド化する方法を提案している。 またこの方法が、制約密度が低く局所最適解に陥りやすいとされてい る問題に対して、従来方法(GSAT)より解を発見できる確率が高いこと を示している。しかし探索速度に関しては、制約密度が高い問題に対 しては優れているものの、低い問題に対しては従来手法からの改善は 見られなかった。そこで本論文では、ＧＡ部の探索速度を向上させる 方法を提案する。通常のＧＡはダーウィン進化論に基づいており、探索は交叉と突然 変異のみで行なわれている。これに対して本手法では新たにウイルス による感染を導入し、探索(進化)に方向性を持たせることで高速化を 図る。ウイルス感染による生物進化のメカニズムやダーウィン進化論 に対する優位性に関しては、中原・佐川「ウイルス進化論」（泰流社） によって詳細に述べられている。従って、制約充足問題に対するウイ ルスの構成方法と感染のアルゴリズムの提案が本研究の目的である。
→長谷川のホームページへ戻る