Vol.19 No.3 (2004/05) 進化的計算

私のブックマーク

進化的計算

阪南大学経営情報学部
筒井茂義
tsutsui@hannan-u.ac.jp

１．はじめに

遺伝的アルゴリズム(GA)，遺伝的プログラミング(GP)，進化戦略(ES)，進化プログラミング(EP)など進化的計算の歴史は意外と古い．例えば，D.B.Fogel (Ed)”Evolutionary Computation The Fossil Record”, IEEE Press (1998) のpp.87-94 に紹介されている，Fraser, A.S.: “Simulation of Genetic Systems byAutomatic Digital Computers” (1957) では，当時のディジタルコンピュータ”SILLIAC” を用いて，遺伝子型としてバイナリ表現を用いた個体進化のプロセスのモデリングとそのシミュレーションの研究が行われている．ここでは既にGAのベースとなるオペレータなどが試みられている．GAについていえば，Holland,J. H.: “Adaptation in Natural and Aritificial System”, The University ofMichigan Press (1975)により，ほとんどその基礎が作られたといってよい．ESでは，Rechenberg, I.やSchwefel, H.-P.の研究が1960年代にすでに発表されている．

　GAが広く知られるようになったのは，1989年に発行された Golberg, D. E.:”Genetic Algorithms in Search, Optimization, and Machine Learning”,Addison-Wesley の貢献が大きい．ところで，Godberg から直接聞いた話であるが，この出版時点で同氏はESの存在を知らなかったとのことである．1990年代になり，それぞれの独立した「島」で進化して来た手法が互いに遭遇し，相互交流が始まったといえる．また，「進化的計算」としてのコミュニティが認知されれるようになった．
　これにより，GA/ES/EPといった区別自体の意味合いは薄れているが，歴史的経緯により，用語上使い分けられている．多くの研究者の「参入」により，活発な研究が行われ，同時に多くの国際会議が開かれるようになった．1990年代後半からは，本格的な実用のステージに入っている．今後は，進化ロボット，バイオロジカル応用，進化ハードウェア，進化的スケジューリング，金融・経済への応用といった，応用分野別での研究区分やそれぞれの分野における新しいスキームの提案が重要になってくると思われる．
　さて，以下では，進化的計算に関する，ジャーナルや書籍シリーズ，国際会議，研究グループ等による重要な情報源，最近の話題としてのEDAsなどを紹介したい．

２．主要ジャーナル，書籍シリーズ

３．主要国際会議

  • GECCO 2004 (Genetic and Evolutionary Computation Conference
    2004)
    http://gal4.ge.uiuc.edu:8080/GECCO-2004/
    　ISGEC（２．参照）が主催する進化的計算関連での最大の国際会議であり，毎年開催される．2004年は，6月26日－30日の期間でシアトルで開催される．カバーする範囲は，GA，GP，ES，EP，EHW(進化型ハードウェア)，RWA(リアルワールドアプリケーション）AL（人工生命），進化形ロボット，バイオインフォマティクス応用，免疫アルゴリズム，ACO (Ant Colony Optimization) などで，進化的計算に関連する幅広いテーマから構成されている．採録率を50%未満にすることを基準にしている．しかし参加者を増やすために，多くのワークショップを同時に開催している．また，査読なしの論文 “Late-BreakingPapers” を募集し，口頭発表の機会とともに別途論文集が発行される．Late-Breaking Papers の締め切りは5月21日であるので，本号発行時点でまだ間に合うと思われる．
  • CEC 2004 (2004 Congress on Evolutionary Computation)
    http://cec2004.org/
    　IEEE Neural Networks Society が主催する進化計算関連の学会であり，規模的にはGECCOよりやや小さいが，ほぼ匹敵する．毎年開催され，今年は，6月20日－23日の期間でオレゴンで開かれる．米国以外で開催されることもあるが，GECCOと時期が重なることが多い．カバーする範囲は，GECCOとほぼ同じといってよい．日本やヨーロッパからの参加者はそうではないが，両学会の設立経緯から米国からの参加者はGECCO派とCEC派にある程度分かれているように見える．
  • PPSN VIII (The 8th International Conference on Parallel Problem
    Solving from Nature)
    http://events.cs.bham.ac.uk/ppsn04/
    　偶数年にヨーロッパで開催される学会であり，今年は9月18－22の期間でBirmingham大学（イギリス）で開催される．「自然にヒントを得た並列型問題解決手法に関する国際会議」となっているが，カバーする範囲は，GECCO，CECとほぼ同じである．この学会も採録率を50%未満にすることを基準にしており，各回100件程度の論文が発表される．この学会の特徴は，研究発表がシングルポスターセッションで行われることであるある．1日に3つのセッションが組まれる．各セッションは，セッションチェアーによる論文内容の紹介から始まる．比較的密度の濃いディスカッションが行えるので，お勧め学会である．
  • FOGA 05 (Foundation of Genetic Algorithms 2005)
    http://www.geocities.com/foga05/
    　遺伝的アルゴリズムの理論的側面に重点を置いた国際学会であり，ISGEC が主催している．例年PPSNと同じ時期に近隣場所で行われてきたが，次回は，2005年1月5日－9日に会津大学で開催される．発表論文数は20件程度であり，非常に密度の高いディスカッションが行われる．
  • FEA (International Workshop on Frontiers in Evolutionary Algorithms)
    2年ごとに行われ，次回は2005年．2003年のサイトはhttp://scsx01.sc.ehu.es/ccwgrrom/FEA2003/
  • EA (International Conference on Artificial Evolution)
    同じく，2年ごとに行われ，次回は2005年．2003年のサイトはhttp://minimum.inria.fr/ea/ea03/

４．関連分野の国際会議

　３．では，進化的計算の主要な国際会議を紹介したが，個別の分野に特化した国際会議も多く開催されている．また，情報処理関係の国際会議で進化的計算のセッションが組まれる．ここでは，その一部を紹介する．

５．有用な研究情報のサイト

　進化的計算の研究に有用な情報が得られるサイトは非常に多くある．ここではその一部を紹介したい．多くの情報は，下記のサイトから辿ることができる．

  • EvoWeb (Website of EvoNet – the European Network of Excellence in Evolutionary Computing)
    http://evonet.inria.fr/
    　EvoNetは，進化的計算に関連する研究や技術に関する，情報提供，交流，啓蒙などの活動を行っているヨーロッパのネットワークであり，EvoWeb はそのサイトである．国際会議やジャーナルなどの情報，コース情報，研究者などのデータベースなど満載されている．website tour のページもあり，進化的計算に関連することで調べることがあれば，まず EvoWeb を訪問することがお勧めである．
  • EC Digest (The Evolutionary Computation Mail Digest)
    http://ec-digest.research.ucf.edu/
    　以前，米国海軍の研究所がサポートしていた GA-List Digests が，2003年8月よりEC Digestとして生まれ変わった（サポート先も変更）．進化的計算に関連する最新のニュースや投稿記事が定期的に配信されるので，大変有用である．記事も投稿できる．参加の登録は　listserv@listserv.gmu.edu の本文にsubscribe ec-digest-l ＜Your Name (up to 4 words)＞を記入する．なお，上記のサイトから，過去のダイジェストが閲覧できる．
  • Information about GP/GA
    http://www.genetic-programming.org/
    GP/GAに関連する各種情報へのリンク集である．
  • IlliGAL (Illinois Genetic Algorithms Laboratory)
    http://www-illigal.ge.uiuc.edu/index.php3
    　D. E. Goldbergの研究室のサイトである．同研究室では，ビルディングブロックやリンケージラーニングなど，GAの基礎的な研究が精力的に行われている．それらの成果は，IlliGAL Tecnical Reoportとして公開され，ダウンロードできる．また，開発されたソースコードも公開されている．
  • KanGAL (Kanpur Genetic Algorithms Laboratory)
    http://www.iitk.ac.in/kangal/index.html
    　Dab, K.は，Goldberg の最初の PhD学生であった．同氏は，mGAなど，IlliGALでのGoldberg の研究に多大な貢献をしている．近年は多目的最適化などでの業績を上げており，このサイトから論文を入手できる．
  • Koza, J.
    http://www.genetic-programming.com/johnkoza.html
    　GPの提唱者Kozaのホームページ
  • Rechenberg, I.
    http://www.bionik.tu-berlin.de/
    　ESの提唱者の一人であるIngo Rechenbergのホームページ．
  • ACO (Ant Colony Aptimization)
    http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
    　Dorigo, M. によって提供されているACOに関するサイトで，論文のほか，各種情報が提供されている．
  • 人工生命の宝庫
    http://www2.create.human.nagoya-u.ac.jp/~ari/stuff/alifesoft.html
    　名古屋大学の有田先生の人工生命に関連するリンク集であるが，カバーされている範囲は広く，進化的計算に関連する多くの有用なリンク先が一口コメントとともに紹介されているすばらしいサイトである．国内外の多くの研究室も紹介されている．

６．EDAs (Estimation of Distribution Algorithms)

　近年，EDAs（Estimation of Distribution Algorithms；分布推定アルゴリズム）が進化的計算の新しいフレームワークとして注目されている（EDAs の名称に関しては，分布推定法の方式に関するアルゴリズムと誤解されやすいので，適切と思えないが，名称は既に定着してしまった）．EDAsは，集団で探索するという意味で従来のGAやESと同じであるが，交叉や突然変異といった遺伝的オペレータは使われない．選択オペレータによって選ばれた個体の分布状況に注目する．個体分布密度が高いところは有望な探索領域と考える．この領域により多くの子個体を生成する．このために，集団の個体分布状況を確率モデルを用いて推定を行う．推定された確率モデルに基づいて，次世代の子個体を生成する．
　分布推定法には，変数ごとに独立に推定を行う周辺分布モデルから，変数間の絡みを考慮する複雑なモデルを用いる手法が考えられ，また，パラメトリック法／ノン・パラメトリック法など，各種のモデル構築手法が提案されている．以下では，EDAsに関する研究論文が収集できる代表的な研究グループのサイトを紹介する．なお，先に紹介したIlliGALでも，EDAsに関する先駆的な研究のであるCompact GA (cGA), Extended Compact GA (ECGA), Bayesian Optimization Algorithm (BOA) などの論文を入手できる．なお，EDAsに関しては，本学会誌も，Vol.18,No.5（2003年9月）に特集「遺伝的アルゴリズムの発展」で紹介されているので，参照されたい．

７．むすび

　進化的計算の歴史を振り返ってみると，明らかに計算機の進歩とともに進んでいる．過去の研究者が既に着想していても当時の計算機の能力ではできなかった研究や実用的応用が可能になってきた．この意味から，計算機のパワーに依存するだけではない新しい着想の研究が求められているように思える．
　しかし一方，計算機の性能の向上や並列計算機技術の進歩，さらには高速インターネットの実用化などは，従来の発想を超えさせるエンジンにもなっているのも事実である．経営経済，バイオインフォマティクス，ロボットなど，進化的計算の発想は多くの展開分野があり，ブレークスルーの研究がなされている．たとえば，U-Mart プロジェクトやロボカップなどがあげられる．このような研究活動の情報については，今後の号での紹介に期待したい．
　以上，進化的計算関連の主なサイトを紹介したが，筆者のリック集 http://www.hannan-u.ac.jp/~tsutsui/internet.htmlをベースにしているので，重要なリンク先が見落とされるとも思われ，また，進化的計算全般を網羅しているわけではないことを最後におことわりしておかねばならない．