自己適応島遺伝的アルゴリズムにおける 非反復化と非同期化による探索効率の向上

高島 栄一 (0251056)


遺伝的アルゴリズム(Genetic Algorithm,以下GA)の解の探索効率は, 交叉率,突然変異率などのパラメータ値に依存する. 人手によるパラメータ調整の労力を軽減するために, パラメータを自動的に調整する適応GAが提案されている.
しかし,そのほとんどが,少数のパラメータしか同時に適応させることができな い.多数のパラメータを同時に適応させる適応GAは,いくつかあるが, そのほとんどが反復して問題を解くために大きな計算量を必要としていた.

本発表では,合理的な計算量で同時に多数のパラメータの適応を行う自己適応島 GA(Self Adaptive Island GA,以下SAIGA)と 非同期化したSAIGAであるA-SAIGA(Asynchronous-Self Adaptive Island GA,以下A-SAIGA)を提案する.
両提案手法はメタGAと島GAを組み合わせて用いる. 各島に異なるパラメータを与え,各島で解の探索を行いつつ, 解の探索効率を観測する. そして,複数の島から得られた観測結果に基づいて 新しいパラメータを生成し探索を続ける. 並行して多数の観測結果を得ることができるために, 反復することなしに,パラメータの適応を行うことができる.
さらに,A-SAIGAは, 島間の同期を取る必要性をなくすことにより,SAIGAに比べ,時間単位の 解の探索効率が向上するように変更したアルゴリズムである.

本発表では,はじめに研究背景としてGAおよび適応GAについて述べる.
つぎに,提案手法である自己適応島GAと非同期自己適応島GAについて述べる.
そして,本研究では両提案手法の有効性を調べるために様々な問題 に対して解の探索効率を計測したが, 本発表ではその中でも特にジョブショップスケジューリング問題に焦点をあてて その評価実験とその結果について述べる.
最後に,結論と今後の課題について述べる.