分布推定アルゴリズムにおけるアニーリングの改善

点击翻译按钮获取中文摘要

布推定アルゴリズムとは、最適化問題をサシプリングし(適当にいくつか解を選び評価し)、得られた情報から統計的推定を用いて最適化問題の目的関数を予測することで最適化を行う方法である。サンプリングによる最適化自体は遺伝的アルゴリズムの分野で研究されてきたが、分布推定アルゴリズムの一つの特徴は、統計学を用いることでアルゴリズムを数理的に構成した点にある。本研究では、この分布推定アルゴリズムを2つの方向へ数理的に拡張し、数値実験により有効性を確認した。まず第一に局所解の問題に対して階層型インポータンスサンプリングを提案した。遺伝的アルゴリズムでは、局所解の問題に対して多様性の観点から研究が進められてきた。本研究では、複数の乱雑度(多様性)を同時に実現することで、常に一定の乱雑度を保ちつつ、最適化を同時に進める方法を提案した。この方法は従来法を数理的に拡張することで実現できる。また、乱雑度の制御は収束速度に対応しており、これに対しては、統計的推定精度の観点で最適な乱雑度(収束速度)制御方法を提案した。第二に、過去のサンプル(個体)を再利用する方法を提案した。遺伝的アルゴリズムは良いサンプルを次世代で再利用する枠組みとなっているが、一方で分布推定アルゴリズムは過去のサンプルを用いることは定式化の関係上難しい。遺伝的アルゴリズムでは多様性が重要だと認識されているが、過去のサンプルのうち良いものだけを集めると、そこには必然的に偏りが生じる。モンテカルロ積分の観点では、集めたサンプルの分布がわかっていれば偏りを取り除くことができる。提案手法ではモンテカルロ積分(インポータンスサンプリング)の観点から各サンプルに対して重みをつけ、集めたサンプルの分布を陽に記憶することで、インポータンスサンプリングを近似する形で過去サンプルを保存する方法を提案した。