情報処理学会 第77回全国大会講演要旨

大規模な組合せ最適化問題の例として、数字をヒントに敷き詰められたマスを黒マスと白マスに塗り分けて絵を出すパズルゲームであるピクロスを用いる。ピクロスの問題の形式は正方形であることが多く、全部で2のn^2乗(nは問題の幅)パターンの塗り分け方が存在するが、効率的な解法のアルゴリズムが存在しないため進化計算(GA)を適用する。通常のGAを問題に合わせた交叉や突然変異を用いてある程度の大規模なピクロスの解を求める。さらに、局所探索や部分解を用いた様々な手法によりサイズの大きなピクロスの解を求める。