方形ピースジグソーパズル問題におけるアントコロニー最適化の適用

大谷 隆浩  越野 亮  白山 政敏  

誌名
電子情報通信学会論文誌 D   Vol.J90-D   No.5   pp.1275-1281
発行日: 2007/05/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 画像・映像処理
キーワード: 
メタヒューリスティクス,  アントコロニー最適化,  パズル組立て,  

本文: PDF(257.6KB)>>
論文を購入




あらまし: 
本論文では,方形ピースジグソーパズル問題を効果的に解くために,アントコロニー最適化(Ant Colony Optimization: ACO)を適用する.ACOはアリのフェロモンを利用した食料採集行動を模倣した最適化手法であり,様々な組合せ最適化問題において従来手法を上回る性能を示している.本論文では現在最も精度が良いと考えられているMAX-MIN Ant System(MMAS)と,更に精度向上のために考案した改良手法である両方向Ant System(Bidirectional Ant System: BAS)を方形ピースジグソーパズル問題に適用する.また,複数の集団を用いて探索を行う分散型のACOを実装し,提案手法である両方向Ant Systemとの比較を行う.性能評価実験を行った結果,MMASと分散型のACO,両方向Ant Systemは従来手法の遺伝的アルゴリズムに比べ大幅な精度向上を実現でき,また両方向Ant Systemは分散型のACOに比べ効率的に最適解を求めることができたことを示す.