Thesis or Dissertation 非同期進化的アルゴリズムによるプログラム進化

原田, 智広  ,  ハラダ, トモヒロ  ,  Harada, Tomohiro

pp.1 - 205 , 2015-03-25 , The University of Electro-Communications
Description
本研究では,問題の特性や事前知識によらず汎用的に最適解を獲得可能なメタヒューリスティック最適化手法の一つである進化的アルゴリズム(Evolutionary Algorithm:EA)に着目し,解を同期的に進化させることが困難な問題に対して,すべての解の評価を待たずに非同期に進化させる非同期進化法を提案し,その有効性を検証することを目的とする.その目的達成に向けて本研究では,二種類の非同期EAを提案する.一つ目は,非同期なデジタル生物の進化をシミュレートするTierraを拡張し,絶対評価にもとづいて解を進化させるTierra型非同期EA(Tierra-based Asynchronous EA:TAEA)を提案するとともに,適合度を進化の過程で適応的に調節する機構を導入した適応型TAEA(TAEA+)を提案する.二つ目は,非同期に得られる部分的な解評価から更新される指標を用いて相対評価に基づいて解を進化させる非同期リファレンス評価を用いるEA(Asynchronous Reference-based Evaluation EA:ARE-EA)を提案する.提案手法の有効性を検証するために,本研究では(1)一般的なベンチマーク問題である関数同定問題における関数進化,(2)実応用を想定したアセンブリプログラム進化,(3)宇宙機への適用を念頭においたプログラムのビット反転が生じる環境でのアセンブリプログラム進化を実験する.提案手法をEAの代表的な手法である遺伝的プログラミング(Genetic Programming:GP)に適用した結果,提案非同期進化法であるTAGP(TAGP+を含む)とARE-GPは,(i)部分的な解の評価のみで,全体の解の評価を利用可能な従来の同期進化法と同等以上の関数近似性能を達成可能であり,(ii)解の評価時間のばらつきが大きいほど関数近似性能が向上する.また,(iii)与えられた正常なプログラムを維持可能であることに加えて,実行ステップ数の最小化が可能である.さらに,(iv)プログラムの改変や変数のエラーが発生してもプログラム進化を可能にすることを明らかにした.具体的には,(i)に関しては,関数同定問題において,TAGP+とARE-GPは同期GPの( + )-GPを上回る関数近似性能を示し,非同期GPである非同期steady-stateGP(ASSGP)と比較しても同等以上の性能を示すことが明らかになった.(ii)に関しては,評価時間にばらつきがある場合に評価時間にばらつきがない場合と比べてARE-GPの関数近似性能が向上する可能性があることが示唆された.(iii)に関しては,アセンブリプログラムの進化において,TAGPとARE-GP,同期GPであるSSGPはいずれも与えられた正常なプログラムを維持可能であり,その中でもTAGPとARE-GPはSSGPでは獲得できない実行ステップ数の短いプログラムを生成可能であることが分かった,(iv)に関しては,プログラムのビット反転が発生する環境において,TAGPとARE-GPは正常なプログラムを維持可能であり,さらに初期に与えたプログラムよりもサイズの小さなプログラムを生成可能である.
Full-Text

http://ir.lib.uec.ac.jp/infolib/user_contents/9000000782/9000000782.pdf

Number of accesses :  

Other information