遺伝的アルゴリズムの収束理論

概要

論文の詳細を見る
遺伝的アルゴリズム(GA)において、収束理論は、GAの問題解決能力の可能性と限界を明らかにするために重要な課題であり、現在研究が開始されつつある。GAの手本である集団遺伝学においては、二倍体細胞の最も簡単な2遺伝子座・2対立遺伝子モデルの淘汰・交差方程式でも、リミットサイクルをもつ場合があることが知られており、一般的な収束理論の確立は極めて難しい問題である。一方、GAでは、これまで、主に、半数体細胞を前提としたアルゴリズムについて研究されてきており、その最も簡単な2遺伝子座・2対立遺伝子モデルの淘汰・交差を用いた2ピット問題(タイプI、II)の解法に関して、一点収束および最大値/非最大値への収束初期条件がほぼ解明されている。GAの淘汰・交差方程式は、基本的に、集団遺伝学における一般的な淘汰・交差方程式の特定化であるため、GA固有の収束理論は確立可能であろうと想定される。本稿では、このようなGA収束理論の確立をねらいとして、GA差分方程式の解析という数理生物学的手法を用いて、nビット問題に対するGA(淘汰・交差)の一点収束性と最大値/非最大値への収束条件を明らかにする。
一般社団法人情報処理学会の論文
1993-03-01