PCFG-LA混合モデルに基づく分布推定アルゴリズム

摘要

分布推定アルゴリズムは従来の進化アルゴリズムにおいて交叉や突然 IV異によるサンプリングを，推定分布からのサンプリングに置き換えた手法である．近年，分布推定アルゴリズムはプログラムや関数の進化に適用されており，問題によっては従来手法である遺伝的プログラミングよりも高い探索性能を示すことが報告されている． PAGE (Programmigwith Annotated Grammar Estimation）は PCFG (Probabilistic Context-Free Grammar)に Aづく分布推定 7ルゴリズムであり， PCFG-LA (PCFG with Latent Anotations）と呼ばれるモデルを用いた手法である． PAGEは有用部分構造の推定に適しているものの，解が複数ある問題や，解が一意に表現れない間題においては分布推定が効率的に行われない．本論文では， PCFG-LAを混合モデルに拡張した， PCFG-LAMM (PCFG-LA Mixture Model）を考案し， PCFG-LAMMに基づく分布推定アルゴリズムを提案する．提案手法 UPAGE (Unsupervised PAGE）をいくつかの問題に適用することで， UPAGEは PAGEより少ない適合度評価回数で解を獲得することができることを示す．また，多峰性の問題では， UPAGEは一度の試行で複数解を獲得す