Courseraで離散最適化を勉強していたら、フォーラムにIG(iterated greedy) というアルゴリズムが出てきたので紹介します。
元の論文はこちら。
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.7721
グラフ彩色の練習問題で使ってみたところ、非決定性もなく、むつかしい操作もなく、そこそこの計算量でそれなりの解が得られました。メモリの使用量や計算時間も、エッジのソート分を見ておけばOKなので組込みなどの厳しい環境でも使えます。
グラフ彩色問題
https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2
今回はエッジに対する色分け問題です。実装と評価が簡単なので、他の問題でもとりあえずやってみる価値はあると思います。
アルゴリズム
通常のgreedy algorithmは一回で近似解を求めに行きますが、IGではgreedy algorithmを繰り返すことでより良い近似解を求めます。
本質的にはこれだけです。これでうまくいく理由は、一般的に制約プログラミングでは、制約の厳しい所から値を設定していくのが有効と言われています。一回目のgreedy algorithmで彩色した結果、彩色が厳しかったところから再度greedy algorithmを使うことで、うまく精度を上げています。これにヒューリスティックな方法を組み合わせることで、さらに良い解が見つかる可能性があります。
もっと厳密な話は上の論文を読んでみてください。
とあるグラフでやってみた結果
エッジの数 n = 1000でIGを試してみた結果です。
縦軸を色数K、横軸をIGのイテレーション数としてプロットしてみます。iteration=0は、通常のgreedy algorithmの結果です。イテレーションを回すと、色数Kが少しずつ減っているのがわかります。これに、様々な既存手法を加えることで、さらに色数を減らすことが期待できます。
