ランダムなパッチがチャールズ・ダーウィンのイメージに進化するアニメーション
ランダムな画像集団の進化。アニメーションの各フレームは、各パッチのグレースケールレベルからなるゲノムを持つ、最も適応度の高い個体を示す世代です。進化は、1. 適応度の評価、2. 個体の順位付け、3. 次に適応度の高い個体からいくつかの遺伝子を取り込む、という手順を繰り返します。適応度とは、チャールズ・ダーウィンの画像との誤差差です。

コンピュータサイエンスにおける進化計算とは、生物進化に着想を得た大域的最適化のためのアルゴリズム群であり、人工知能とソフトコンピューティングの分野においてこれらのアルゴリズムを研究する分野です。技術的には、メタヒューリスティックまたは確率的最適化の特性を持つ、集団ベースの試行錯誤型問題解決器群を指します。

進化計算では、候補解の初期集合が生成され、反復的に更新されます。各新世代は、あまり望ましくない解を確率的に除去し、小さなランダムな変化を導入することで生成されます。また、手法によっては親の情報も混合されます。生物学用語では、解の集団は自然選択（または人為選択）、突然変異、そして場合によっては組み換えの対象となります。その結果、集団は徐々に適応度（この場合はアルゴリズムで 選択された適応度関数）が増加するように進化します。

進化計算技術は、幅広い問題設定において高度に最適化された解を生み出すことができるため、コンピュータサイエンスの分野で広く利用されています。より具体的な問題群やデータ構造に適した、多くの派生型や拡張版が存在します。進化計算は、進化生物学においても、一般的な進化過程の共通側面を研究するためのin silico実験手法として用いられることがあります。

歴史

進化のプロセスを模倣して問題を解決するという概念は、コンピュータの出現以前に遡り、例えばアラン・チューリングが1948年に遺伝的探索の手法を提案した際に遡る。[1]チューリングのB型u-マシンは原始的なニューラルネットワークに似ており、ニューロン間の接続は一種の遺伝的アルゴリズムによって学習された。彼のP型u-マシンは強化学習の手法に似ており、快感や苦痛の信号によって機械に特定の行動を学習させる。しかし、チューリングの論文は1968年まで発表されず、彼は1954年に亡くなったため、この初期の研究は、その後発展する進化計算の分野にほとんど影響を与えなかった。[2]

進化コンピューティングという分野は、1950年代から1960年代にかけて本格的に始まりました。[1]当時、進化のプロセスをコンピューティングに利用しようとする試みがいくつか独立して行われ、それぞれ約15年間、個別に発展しました。この目標を達成するために、進化戦略、進化プログラミング、遺伝的アルゴリズムという3つの分野がそれぞれ異なる場所で生まれました。4つ目の分野である遺伝的プログラミングは、1990年代初頭にようやく登場しました。これらのアプローチは、選択の方法、許容される突然変異、遺伝子データの表現方法が異なります。1990年代までには、歴史的な分野間の区別が曖昧になり始め、1991年には4つのパラダイムすべてにまたがる分野を表すために「進化コンピューティング」という用語が作られました。[3]

1962年、ローレンス・J・フォーゲルは米国で進化プログラミングの研究を開始しました。これは人工知能の試みと考えられていました。このシステムでは、有限状態機械を用いて予測問題を解きます。これらの機械は変異（状態の追加または削除、あるいは状態遷移規則の変更）され、変異した機械の中で最良のものが将来の世代でさらに進化します。最終的な有限状態機械は、必要に応じて予測を生成するために使用できます。進化プログラミング手法は、予測問題、システム同定、自動制御に効果的に適用されました。最終的には、時系列データの処理やゲーム戦略の進化のモデル化にも拡張されました。[3]

1964年、インゴ・レッヒェンベルクとハンス＝パウル・シュヴェーフェルはドイツで進化戦略のパラダイムを導入した。 [3]従来の勾配降下法では局所的最小値に陥る可能性があるため、レッヒェンベルクとシュヴェーフェルは、ランダムな突然変異（ある解ベクトルの全パラメータに適用）を用いてこれらの最小値から脱出する方法を提案した。親解から子解を生成し、より成功した解を将来の世代のために保存した。この手法は、二人によって初めて流体力学の最適化問題を解くために使用された。[4]当初、この最適化手法はコンピュータを使わずに実行され、代わりにサイコロを振ってランダムな突然変異を決定していた。1965年までに、計算は完全に機械によって実行されるようになった。[3]

ジョン・ヘンリー・ホランドは1960年代に遺伝的アルゴリズムを導入し、それは1970年代にミシガン大学でさらに開発されました。 [5]他のアプローチが問題解決に重点を置いていたのに対し、ホランドは主に遺伝的アルゴリズムを使用して適応を研究し、それをどのようにシミュレートできるかを決定することを目指しました。ビット文字列として表現された染色体の集団は、人為的選択プロセスによって変換され、ビット文字列内の特定の「対立遺伝子」ビットが選択されました。他の突然変異方法の中でも、染色体間の相互作用は、異なる生物間のDNAの組み換えをシミュレートするために使用されました。以前の方法は一度に1つの最適な生物を追跡するだけでしたが（子が親と競合する）、ホランドの遺伝的アルゴリズムは大規模な集団を追跡しました（各世代で多くの生物が競合する）。

1990 年代までには、遺伝的プログラミングと呼ばれるようになった進化計算への新しいアプローチが登場し、ジョン・コザらによって提唱されました。[3]このクラスのアルゴリズムでは、進化の対象自体が高級プログラミング言語で書かれたプログラムでした(1958 年には機械語を使用する試みもありましたが、ほとんど成功しませんでした)。コザの場合、プログラムはLisp の S 式であり、これは部分式のツリーと考えることができます。この表現により、プログラムは部分木を交換でき、一種の遺伝的混合を表現します。プログラムは特定のタスクをどれだけうまく完了したかに基づいてスコアが付けられ、そのスコアが人為的選択に使用されます。配列誘導、パターン認識、プランニングはすべて遺伝的プログラミング パラダイムの成功した応用でした。

進化計算の歴史には、他にも多くの人物が関わっていますが、彼らの研究は必ずしもこの分野の主要な歴史的分野の一つに当てはまるわけではありません。進化アルゴリズムと人工生命技術を用いた進化の最も初期の計算シミュレーションは、1953年にニルス・オール・バリセリによって行われ、最初の結果は1954年に発表されました。 [6] 1950年代のもう一人の先駆者はアレックス・フレイザーで、人工選択のシミュレーションに関する一連の論文を発表しました。[7]学術的な関心が高まるにつれて、コンピュータの性能が劇的に向上し、コンピュータプログラムの自動進化などの実用的なアプリケーションが可能になりました。[8]進化アルゴリズムは現在、人間の設計者が作成したソフトウェアよりも効率的に多次元問題を解くために、またシステム設計を最適化するために使用されています。[9] [10]

テクニック

進化的コンピューティング技術は、主にメタヒューリスティック 最適化 アルゴリズムを伴います。大まかに言えば、この分野には以下が含まれます。

近年、多くの疑わしいアルゴリズムが提案されていますが、それらは既存のアルゴリズム（多くの場合、粒子群最適化）のコピーに過ぎず、メタファーが変更されただけで、アルゴリズム自体は全く新しいものではありません。これらの疑わしいアルゴリズムの多くを網羅したカタログが、進化計算ベストイアリに掲載されています。[11]また、これらの疑わしい「斬新な」アルゴリズムの多くは、実験的な検証が不十分であることにも留意する必要があります。[12]

進化アルゴリズム

進化的アルゴリズムは、一般的に生殖、突然変異、組み換え、自然選択といった生物進化に着想を得たメカニズムを実装する手法のみを用いる点で、進化計算のサブセットを形成します。最適化問題に対する候補解は集団内の個体の役割を果たし、コスト関数は解が「生存する」環境を決定します（適応度関数も参照）。上記の演算子を繰り返し適用することで、集団の進化が起こります。

このプロセスには、進化システムの基礎を形成する 2 つの主な力があります。 組み換え(交差など) と突然変異により必要な多様性が生み出され、それによって新規性が促進される一方で、選択は品質を向上させる力として機能します。

このような進化過程の多くの側面は確率的である。組み換えや突然変異によって変化した情報はランダムに選択される。一方、選択作用素は決定論的または確率的である。後者の場合、適応度の高い個体は適応度の低い個体よりも選択される確率が高くなりますが、通常は弱い個体であっても親になるか生き残るチャンスがあります。

進化アルゴリズムと生物学

遺伝的アルゴリズムは、生物システムやシステム生物学をモデル化する手法を提供します。これらの手法は、システムの将来の状態を予測するために用いられるため、動的システム理論と関連しています。これは、生物学における発生の秩序ある、よく制御された、高度に構造化された特徴に注目を集めるための、鮮やかで（しかし誤解を招く可能性もある）方法に過ぎません。

しかし、アルゴリズムと情報科学、特に計算理論の使用は、動的システムとの類推を超えて、進化そのものを理解する上でも重要です。

この見解の利点は、発達に中央制御が存在しないことを認識できる点です。生物は細胞内および細胞間の局所的な相互作用の結果として発達します。プログラムと発達の類似性に関する最も有望なアイデアは、細胞内のプロセスと現代のコンピュータの低レベル動作との間に、一見密接な類似性があることを示唆するものであると考えられます。[13]したがって、生物システムは、入力情報を処理して次の状態を計算する計算機械のようなものであり、古典的な力学システムよりも計算に近いと言えます。[14]

さらに、計算理論の概念に従えば、生物におけるミクロなプロセスは根本的に不完全で決定不能（完全性（論理））であり、「細胞とコンピュータの類似性の背後には単なる粗雑な比喩以上のものがある」ことを意味している。[15]

計算との類似性は、遺伝システムと生物学的構造の関係にも及び、これは生命の起源を説明する上で最も差し迫った問題の 1 つを明らかにするとよく考えられています。

進化的オートマトン[16] [17] [18]は、進化的チューリングマシン[19] [20]の一般化であり、生物学的計算と進化的計算の特性をより正確に調査するために導入された。特に、進化的計算の表現力に関する新しい結果を得ることを可能にする[18] [21]。これは、自然進化と進化的アルゴリズムおよびプロセスの決定不能性に関する最初の結果を裏付けるものである。端末モードで動作する進化的オートマトンの中で最も単純なサブクラスである進化的有限オートマトンでは、指定されたアルファベット上の任意の言語を受け入れることができ、これには非再帰的に列挙可能な言語（例えば、対角化言語）と再帰的に列挙可能だが再帰的ではない言語（例えば、汎用チューリングマシンの言語）[22] が含まれる。

著名な実践者

活動中の研究者のリストは当然ながら流動的であり、網羅的ではありません。コミュニティのネットワーク分析は2007年に発表されました。[23]

出版物

ジャーナル

進化計算に関する記事や進化計算を使用する記事は文献に溢れていますが、進化計算に特化したジャーナルもいくつかあります。

会議

進化計算分野の主な会議には以下が含まれる。

参照

参考文献

  1. ^ ab Eiben, AE; Smith, JE (2015),進化コンピューティング：その起源、ナチュラルコンピューティングシリーズ、ベルリン、ハイデルベルク：Springer Berlin Heidelberg、pp.  13– 24、doi :10.1007/978-3-662-44874-8_2、ISBN 978-3-662-44873-1、2022年5月6日閲覧
  2. ^ Burgin, Mark; Eberbach, Eugene (2013年4月12日). 「進化的機械の文脈における進化的チューリング」. arXiv : 1304.3762 [cs.AI].
  3. ^ abcde 進化計算：化石記録デイビッド・B・フォーゲル ニューヨーク：IEEEプレス 1998年ISBN 0-7803-3481-7. OCLC  38270557。{{cite book}}: CS1 メンテナンス: その他 (リンク)
  4. ^ Fischer, Thomas (1986)、「Kybernetische Systemanalyse Einer Tuchfabrik zur Einführung Eines Computergestützten Dispositionssystems der Fertigung」、DGOR、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、p. 120、土井：10.1007/978-3-642-71161-9_14、ISBN 978-3-642-71162-6、2022年5月6日閲覧
  5. ^ ミッチェル、メラニー (1998). 遺伝的アルゴリズム入門. MIT出版. doi :10.7551/mitpress/3927.001.0001. ISBN 978-0-262-28001-3。
  6. ^ バリチェリ、ニルス・アール (1954)。 「進化の過程におけるエセンピ・ヌメリシ」。メソッド: 45–68。
  7. ^ Fraser AS (1958). 「遺伝モデルのモンテカルロ解析」. Nature . 181 (4603): 208–9 . Bibcode :1958Natur.181..208F. doi :10.1038/181208a0. PMID  13504138. S2CID  4211563.
  8. ^ Koza, John R. (1992).遺伝的プログラミング：自然選択によるコンピュータのプログラミングについて. MIT Press . ISBN 978-0-262-11170-6。
  9. ^ GC OnwuboluとBV Babu、Onwubolu, Godfrey C.; Babu, BV (2004年1月21日). エンジニアリングにおける新しい最適化手法. Springer. ISBN 9783540201670. 2016年9月17日閲覧。
  10. ^ Jamshidi M (2003). 「インテリジェント制御のためのツール：ファジーコントローラ、ニューラルネットワーク、遺伝的アルゴリズム」. Philosophical Transactions of the Royal Society A. 361 ( 1809): 1781–808 . Bibcode :2003RSPTA.361.1781J. doi :10.1098/rsta.2003.1225. PMID  12952685. S2CID  34259612.
  11. ^ Campelo, Felipe; Aranha, Claus (2018年6月20日). 「Ec Bestiary: 進化型、群集型、その他のメタファーベースアルゴリズムのベストイアリ」. doi :10.5281/ZENODO.1293035. {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  12. ^ Kudela, Jakub (2022年12月12日). 「進化的計算手法のベンチマークと分析における重要な問題」. Nature Machine Intelligence . 4 (12): 1238–1245 . arXiv : 2301.01984 . doi :10.1038/s42256-022-00579-0. ISSN  2522-5839. S2CID  254616518.
  13. ^ 「生物学的情報」スタンフォード哲学百科事典。スタンフォード大学形而上学研究室。2016年。
  14. ^ JG Diaz Ochoa (2018). 「弾性マルチスケールメカニズム：計算と生物学的進化」. Journal of Molecular Evolution . 86 (1): 47– 57. Bibcode :2018JMolE..86...47D. doi :10.1007/s00239-017-9823-7. PMID  29248946. S2CID  22624633.
  15. ^ A. Danchin (2008). 「バクテリアはコンピューターを作るコンピューターである」FEMS Microbiol. Rev. 33 (1): 3– 26. doi :10.1111/j.1574-6976.2008.00137.x. PMC 2704931. PMID 19016882  .  
  16. ^ Burgin, Mark; Eberbach, Eugene (2013). 「再帰的に生成される進化的チューリングマシンと進化的オートマトン」 Xin-She Yang (編).人工知能、進化的コンピューティング、メタヒューリスティクス. 計算知能研究 第427巻. Springer-Verlag. pp.  201– 230. doi :10.1007/978-3-642-29694-9_9. ISBN 978-3-642-29693-2。
  17. ^ Burgin, M. および Eberbach, E. (2010) 有界および周期的進化マシン、進化計算に関する会議 (CEC'2010) Proc. 2010 Congress on Evolutionary Computation (CEC'2010)、バルセロナ、スペイン、2010年、pp. 1379–1386
  18. ^ ab Burgin, M.; Eberbach, E. (2012). 「進化オートマトン：進化計算の表現力と収束性」.コンピュータジャーナル. 55 (9): 1023– 1029. doi :10.1093/comjnl/bxr099.
  19. ^ Eberbach E. (2002)「進化的計算の表現力について：ECはアルゴリズムか？」、2002年世界計算知能会議WCCI'2002議事録、ホノルル、ハワイ、2002年、564-569ページ。
  20. ^ Eberbach, E. (2005) 進化計算理論に向けて、BioSystems、v. 82、pp. 1-19。
  21. ^ エバーバッハ、ユージン、バージン、マーク (2009). 「進化計算の基礎としての進化オートマトン：ラリー・フォーゲルの正しさ」2009 IEEE 進化計算会議. IEEE. pp.  2149– 2156. doi :10.1109/CEC.2009.4983207. ISBN 978-1-4244-2958-5. S2CID  2869386。
  22. ^ ホップクロフト、JE、R. モトワニ、JD ウルマン (2001) オートマトン理論、言語、計算入門、アディソン・ウェスレー、ボストン/サンフランシスコ/ニューヨーク
  23. ^ JJ MereloとC. Cotta (2007). 「最も繋がりの強いEC研究者は誰か？進化計算における著者の複雑ネットワークの中心性分析」arXiv : 0708.2021 [cs.CY].

参考文献

  • Th. Bäck、D.B. Fogel、Z. Michalewicz（編）、進化計算ハンドブック、1997年、ISBN 0750303921
  • Th. BäckとH.-P. Schwefel. パラメータ最適化のための進化的アルゴリズムの概要. 2018年7月12日アーカイブ, Wayback Machine Evolutionary Computation, 1(1):1–23, 1993.
  • W. Banzhaf、P. Nordin、R.E. Keller、FD Francone著『遺伝的プログラミング入門』Morgan Kaufmann、1998年。
  • S. Cagnoni 他「進化型コンピューティングの現実世界への応用」、Springer-Verlag Lecture Notes in Computer Science、ベルリン、2000 年。
  • R. Chiong、Th. Weise、Z. Michalewicz（編）、Variants of Evolutionary Algorithms for Real-World Applications、Springer、2012年、ISBN 3642234232
  • KA De Jong著『進化的計算：統一的アプローチ』MIT Press、マサチューセッツ州ケンブリッジ、2006年
  • AE EibenとJE Smith、「進化的計算から事物の進化へ」、Nature、521:476-482、doi:10.1038/nature14544、2015年
  • AE EibenとJE Smith著『進化コンピューティング入門』Springer、初版2003年；第2版2015年
  • DBフォーゲル著『進化的計算：機械知能の新たな哲学に向けて』IEEE Press, ピスカタウェイ, ニュージャージー州, 1995年.
  • LJフォーゲル、AJオーウェンズ、MJウォルシュ著『シミュレーテッド・エボリューションによる人工知能』ニューヨーク：ジョン・ワイリー、1966年。
  • DEゴールドバーグ著『探索、最適化、機械学習における遺伝的アルゴリズム』アディソン・ウェスリー、1989年。
  • JHホランド著『自然システムと人工システムにおける適応』ミシガン大学出版局、アナーバー、1975年。
  • P. Hingston、L. Barone、Z. Michalewicz（編）、Design by Evolution、Natural Computing Series、2008年、Springer、ISBN 3540741097
  • JRコザ著『遺伝的プログラミング：自然進化によるコンピュータプログラミング』MIT出版、マサチューセッツ州、1992年。
  • FJ Lobo、CF Lima、Z. Michalewicz（編）、進化アルゴリズムにおけるパラメータ設定、Springer、2010年、ISBN 3642088929
  • Z. Michalewicz , 遺伝的アルゴリズム + データ構造 - 進化プログラム, 1996, Springer , ISBN 3540606769
  • Z. ミハレヴィッツとDBフォーゲル著『How to Solve It: Modern Heuristics』、Springer、2004年、ISBN 978-3-540-22494-5
  • I.レッヒェンベルク。進化戦略: 生物進化の原理を最適化する技術システム。 Fromman-Hozlboog Verlag、シュトゥットガルト、1973年（ドイツ語）
  • H.-P. Schwefel著『コンピュータモデルの数値最適化』John Wiley & Sons, New-York, 1981年。1995年第2版。
  • D. Simon. 進化的最適化アルゴリズム（Wayback Machineで2014年3月10日アーカイブ）. Wiley, 2013.
  • M. Sipper; W. Fu; K. Ahuja; JH Moore (2018). 「進化的アルゴリズムのパラメータ空間の調査」BioData Mining . 11 2. doi : 10.1186/s13040-018-0164-x . PMC  5816380 . PMID  29467825.
  • Y. Zhang; S. Li. (2017). 「PSA：porcellio scaberの生存則に基づく新しい最適化アルゴリズム」arXiv : 1709.09840 [cs.NE].
  • スタンフォード哲学百科事典における生物学的情報に関する記事（英語）