Techniques to Improve Exploration Efficiency of Parallel Self Adaptive Genetic Algorithms by Dispensing Iteration and Synchronization

摘要

遺伝的アルゴリズム（GA）の解の探索効率は，交叉率，突然変異率などのパラメータ値に依存する．人手によるパラメータ調整の労力を軽減するために，パラメータを自動的に調整する適応GAが提案されている．しかし，多数のパラメータを同時に調整する適応GAのほとんどは，反復して問題を解くために大きな計算量を必要とする．本論文では，従来の多数のパラメータを同時に調整する適応GAより少ない計算量で多数のパラメータを同時に適応させる自己適応島GA（SAIGA）と非同期SAIGAを提案する．これらの手法は島GAの一種であり，各島に異なるパラメータを与え，各島で解を探索しつつ解の探索効率を観測する．そして，複数の島から並行して得られる観測結果により新しいパラメータを生成し探索を続ける．その結果，反復することなしに，パラメータを適応させることができる．更に非同期SAIGAは，島間で同期をとる必要性をなくすことにより，その結果，SAIGAに比べ，時間単位の解の探索効率が向上するように変更したアルゴリズムである．実験により，これらの手法の有効性を確認した．