このデモは、グラフ分割問題に対する Tabu Search の実行状況を リアルタイムに示したものです。 グラフ分割問題とは、グラフが与えられたときにカットの重みの和を最小に するような点の分割を求める問題です。 この場合では全ての枝の重みを1と仮定しているので、カットの重みの和と カットに含まれる枝の本数は同じになります。
上記の Current Solution や Best Solution の図では、白い線が枝、赤と水色の円 が点を示しています。赤の点集合と水色の点集合に分割していますが、この場合、 点数が偶数で赤と水色の点集合に含まれる点の数は等しいものと仮定します。 両端点の色が異なる枝はカットに含まれますので、 このような枝の本数を最小にするのが問題の目的になります。
Current Solution の図は現在の Tabu Search が探索している解、 Best Solution の図は、これまでの探索で最も優れた解を表しています。また、 下の黄緑色の波形は目的関数(カットに含まれる枝の本数)の推移を示しています。 下の方が目的関数の値が小さく、 黄色の線は現在までの最良解の目的関数の位置を表しています。
目的関数値が悪化する解も探索するのが Tabu Search の大きな特徴の一つであって、 目的関数値が上下しながらより優れた解に到達していく様子がこの波形から読み取る ことができます。
藤澤 克樹
このデモは 京都大学 藤澤克樹 先生 のプログラムを利用しています。