数理科学は、合理的な意思決定に役立ちます。勘や経験よりも良い結果が得られます。この数理科学が扱う分野の一つに、組み合わせ最適化があります。ナップサック問題、巡回セールスマン問題、生産スケジューリング問題等があり、複数ある組み合わせのなかで、最もよいものを選択することが目的です。ナップサック問題は、容積と価値が異なる複数の品物の中からナップサックに詰めるものを決めることです。当然、ナップサックの大きさは限られており、詰められた品物の価値の総和が最も大きくなるように選択します。例えば、遠足に持っていくおやつの選択は、ナップサック問題になります。駄菓子屋さんに売っている商品の中から限られた予算の中で複数を選択し、満足度を最大にします。巡回セールスマン問題は、複数の地点を１回ずつ巡回するときに移動距離が最小となる経路を探します。生産スケジューリング問題は、複数の製品を複数の機械を使って処理するときに、最も早くすべての処理を完了できるような処理順序を決めます。できるだけよい組み合わせを選びたいものですし、何らかのアドバイスを受けることができればいいですよね。
組み合わせ最適化の問題では、ある組み合わせを選択すればその評価値を簡単に計算することができます。したがって、すべての組み合わせを列挙してそれぞれの評価値を計算し、最もよいものを選べばよいのです。難点は、選択対象が増えるに従って組み合わせの総数が爆発的に大きくなってしまい手に負えなくなることです。組み合わせ総数の計算方法は、高校の数学Aで学んでいますね。一般的にn!もしくはxnを使って計算することができます。おやつを7種類の中から選択する組み合わせは、全部で27 = 128通りになります。これぐらいでしたら、すべての組み合わせを根気よく列挙して評価値を計算することができそうです。もちろん、簡単なプログラムを作成して、最良の解を発見することができます。すべての組み合わせを列挙する方法は、簡単で最適解が保証されることが特徴です。しかし、規模が大きくなるとコンピュータでも膨大な時間を要することになり、事実上、解けない問題となります。
プログラミングで解決しようとするなら、乱数を使って組み合わせをランダムにあたっていく方法が考えられます。もっとも、問題の性質上、良好な組み合わせの近くには、良好な組み合わせが存在していますので、全くのランダムに探すよりは近くの組み合わせを探していく方が効率的です。ただし、近くばかりを探していると最適解を探すことができなくなりますので、遠くも見渡す必要があります。このような探索法のひとつに、生物の進化を模した遺伝的アルゴリズムがあります。遺伝的アルゴリズムでは、ある組み合わせを示す数列や文字列を染色体と呼びます。そして、一つの染色体を一つの個体とみなして集団を形成します。集団から個体を選択して遺伝的操作を加えて新しい個体を生成し、淘汰を経て、次の世代の集団を形成していきます。遺伝的操作には図１に示している通り、交叉と突然変異があります。例では染色体が１～５までの数値を一度ずつ使用することで、ある組み合わせを示しています。交叉は、集団内から２つの個体を選んで染色体の一部を交換して新しい２つの個体を生成します。一部を交換することで、もとの染色体が示す組み合わせに近い新しい組み合わせを作り出します。親から子がうまれるイメージですが、生物を模して新しい組み合わせを生成させる発想は面白いですね。突然変異は、染色体の一部をランダムに書き換えることで、元の個体とは大きく異なる組み合わせを生成すること目的とします。突然変異は、低い確率で実施します。
遺伝的アルゴリズムの全体的な流れは、図２に示される通りです。まずは、初期集団をランダムに生成します。そして、集団から個体を２体ずつ選んで交叉の処理を繰り返したのちに、突然変異を実施します。そして新たにうまれた個体の評価値を計算します。最後に、現在の集団と遺伝的操作によって生成された集団の中から、淘汰により個体を削除して集団数を保ちます。この際に、評価値の高い組み合わせほど高い確率で残れるようにしておきます。こうして次世代の集団に入れ替わります。この流れを繰り返していけば、より良い解が発見できるという仕組みです。
基本的な流れは簡単ですが、プログラミングに際してはいくつかの問題があります。組み合わせをどのようにして染色体で表現するのか、交叉によって作られて染色体が正しく組み合わせを示せるか等です。図1の交叉の下部に示されている通り、単純に一部分を入れ替えてしまうと有効な組み合わせを示せなくなってしまうことが起きます。このような状態を回避できるように染色体を設計したり、プログラムを作成したりしなくてはなりません。
今回は、遺伝的アルゴリズムを取り上げましたが、このように発見的な探索手法を総合した枠組みをメタヒューリスティクスと呼んでいます。他にも自然界の現象を模倣した探索法の枠組みは多数あります。私の研究室では、メタヒューリスティクスにそれぞれの問題の特性を取り入れることで、探索能力の向上を図っています。写真のように、卒研生が試行錯誤しながらプログラムを作成しては性能評価を繰り返しています。