遺伝的アルゴリズムを用いた近似最適化手法の一般的設計指針と応用のための基礎的研究

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

今年度の本研究課題において、(1)遺伝的アルゴリズムにおける集団の多様性を低コストで維持する方法、(2)集団を適切にクラスタリングして探索を効率化する方法、について研究を行った。(1)に関して、本研究ではGAの世代モデルに着目して探索能力を改善する手法を提案した。GAの世代モデルは、探索集団から交叉オペレーターを適用するための解候補を選択する複製選択と、交叉で生成された新たな探索点のうちどれを選択して集団に残すかを決定する生存選択からなる。通常これらは交叉によって生成された探索点の評価値のみを用いて行い、高い評価値を持つものが次世代の集団として選択される。生存選択によって集団の多様性は失われる傾向にあり、最終的には集団が収束して探索が終了する。本研究では生存選択において解候補の評価値だけでなく、選択による多様性の損失量を局所的に考慮する方法を提案した。提案手法を巡回セールスマン問題へ適用した結果、これまでに他の研究者によって提案されている最も優れている近似解法の性能を大きく上回る性能を得ることに成功した。たとえば、ベンチマーク問題のひとつである4461都市問題であれば、研究室のパソコンを用いて3時間程度で90%の確率で最適解を見つけることができる。同じ問題に対し従来手法を用いた場合、同様の計算時間において最適解発見率は30%程度である。(2)に関して、本研究ではGAの探索集団を探索状況に応じて適応的にクラスタリングする手法を提案した。探索空間の形状が複数の谷を持つ場合、一般にGAの探索集団を何らかの方法でクラスタリングするのが有効であると考えられているが、提案手法ではクラスタリングの規範として、(i)各クラスターに含まれる固体の要素数がある一定値以上になる(ii)探索空間内で集団の密度がある一定値を越えてはならない、という制約を導入した。その結果、組合せ最適化問題の中では最も困難な問題のひとつであるジョブショップスケジューリング問題において、提案手法により従来この問題に対して最も優れているとされるGAと同等の性能を実現することができた。