歴史 問題を解決するために進化の過程を模倣するという概念は、コンピュータの出現以前にも存在し、例えばアラン・チューリングが 1948年に遺伝的探索法を提案した時などが挙げられます。[ 4 ] uマシンは 原始的なニューラルネットワーク に似ており、ニューロン間の接続は一種の遺伝的アルゴリズム によって学習されました。彼のP型uマシンは 強化学習 法に似ており、快感と痛みの信号が機械に特定の行動を学習させるように指示します。しかし、チューリングの論文は1968年まで発表されず、彼は1954年に亡くなったため、この初期の研究は後に発展する進化計算の分野にほとんど影響を与えませんでした。[ 5 ]
進化コンピューティングという分野は、1950年代から1960年代にかけて本格的に始まりました。[ 4 ] 進化戦略 、進化プログラミング 、遺伝的アルゴリズム という3つの分野がそれぞれ異なる場所で出現しました。4番目の分野である遺伝的プログラミング は、最終的に1990年代初頭に出現しました。これらのアプローチは、選択方法、許容される突然変異、および遺伝的データの表現方法が異なります。1990年代までに、歴史的な分野間の区別は曖昧になり始め、1991年に「進化コンピューティング」という用語が作られ、4つのパラダイムすべてにまたがる分野を指すようになりました。[ 6 ]
1962年、ローレンス・J・フォーゲルは 米国で進化プログラミング の研究を開始し、これは人工知能の 取り組みとみなされました。このシステムでは、有限状態機械を 使用して予測問題を解決します。これらの機械は突然変異（状態の追加または削除、あるいは状態遷移ルールの変更）され、これらの突然変異した機械の中で最も優れたものが将来の世代でさらに進化します。最終的な有限状態機械は、必要に応じて予測を生成するために使用できます。進化プログラミング手法は、予測問題、システム同定、および自動制御にうまく適用されました。最終的には、時系列データの処理やゲーム戦略の進化のモデル化にも拡張されました。[ 6 ]
1964年、インゴ・レヒェンベルク とハンス・パウル・シュヴェーフェルは ドイツで進化戦略 のパラダイムを導入した。 [ 6 ] 従来の勾配降下 法では局所的最小値に陥る結果が生じる可能性があるため、レヒェンベルクとシュヴェーフェルは、ランダムな突然変異（ある解ベクトルのすべてのパラメータに適用）を使用してこれらの最小値から脱出できることを提案した。子解は親解から生成され、2つのうちより成功した方が将来の世代のために保持された。この手法は、流体力学 の最適化問題を解くために最初に2人によって使用された。[ 7 ] [ 6 ]
ジョン・ヘンリー・ホランドは1960年代に 遺伝的アルゴリズム を導入し、1970年代にミシガン大学でさらに発展した。 [ 8 ] 組み換えを シミュレートするために使用された。以前の方法では一度に1つの最適な生物しか追跡できなかった（子供が親と競争する）のに対し、ホランドの遺伝的アルゴリズムは大規模な集団を追跡した（各世代で多くの生物が競争する）。
1990年代までに、ジョン・コザ らが提唱した遺伝的プログラミング と呼ばれる新しい進化計算のアプローチが登場した。[ 6 ] 高水準プログラミング言語 で書かれたプログラムそのものである（1958年には機械語を使用する試みがいくつかあったが、ほとんど成功しなかった）。コザにとって、プログラムはLisp S式 であり、これは部分式のツリーと考えることができる。この表現により、プログラムは部分ツリーを交換することができ、一種の遺伝的混合を表す。プログラムは特定のタスクをどれだけうまく完了したかに基づいてスコアが付けられ、そのスコアは人工選択に使用される。シーケンス誘導、パターン認識、プランニングはすべて、遺伝的プログラミングパラダイムの成功した応用例である。
進化計算の歴史には他にも多くの人物が関わってきましたが、彼らの研究は必ずしもこの分野の主要な歴史的流れに当てはまるものではありませんでした。進化アルゴリズム と人工生命 技術を用いた進化 の初期の計算シミュレーションは、1953年にニルス・アール・バリチェリ によって行われ、最初の結果は1954年に発表されました。 [ 9 ] アレックス・フレイザーで、 人工選択 のシミュレーションに関する一連の論文を発表しました。[ 10 ] [ 11 ] [ 12 ] [ 13 ]
テクニック 進化計算技術は、主にメタヒューリスティック 最適化 アルゴリズム を伴います。大まかに言えば、この分野には以下が含まれます。
近年、多くの疑わしいアルゴリズムが提案されてきましたが、それらは既存のアルゴリズム（多くの場合、粒子群最適化）の単なるコピーであり、比喩が変わっただけで、アルゴリズム自体は全く新しいものではありません。これらの疑わしいアルゴリズムの多くを網羅した詳細なカタログが、進化計算の動物誌に掲載されています。[ 14 ] [ 15 ]
進化アルゴリズム 進化アルゴリズムは、一般的に 生殖 、突然変異 、組換え 、自然選択 といった生物学的進化 にヒントを得たメカニズムを実装する手法のみを用いるという点で、進化計算のサブセットを形成します。最適化問題の候補解は 集団内の個体の役割を果たし、コスト関数は 解が「生息」する環境を決定します（適応度関数 も参照）。そして、上記の演算子を繰り返し適用することで、集団 の進化が 起こります。
この過程において、進化システムの基盤を形成する2つの主要な力が存在します。 組換え （例えば交叉 ）と突然変異は 必要な多様性を生み出し、それによって新しさを促進します。一方、選択は 品質を高める力として作用します。
このような進化過程の多くの側面は確率的で ある。組換えや突然変異によって変化した情報はランダムに選択される。一方、選択演算子は決定論的である場合もあれば、確率的である場合もある。後者の場合、適応度の高い個体は 適応度 の低い個体よりも選択される可能性が高いが、通常は適応度の低い個体でも親になったり生き残ったりする可能性がある。
進化アルゴリズムと生物学 遺伝的アルゴリズムは、 生物システム やシステム生物学 をモデル化する手法を提供するものであり、システムの将来の状態を予測するために用いられることから、力学系 の理論と密接に関連している。これは、生物学における発生の秩序だった、厳密に制御された、高度に構造化された性質を鮮やかに（しかし誤解を招く可能性もあるが）強調する一つの方法に過ぎない。
しかし、アルゴリズムや情報科学、特に計算理論 の利用は、力学系との類推にとどまらず、進化そのものを理解する上でも重要である。
この見解の利点は、発生には中央制御がなく、生物は細胞内および細胞間の局所的な相互作用の結果として発生することを認識している点にある。プログラム開発の類似性に関する最も有望なアイデアは、細胞内のプロセスと現代のコンピュータの低レベル動作との間に明らかな類似性があることを示唆するものと思われる。[ 16 ] [ 17 ]
さらに、計算理論 の概念に従うと、生物の微細なプロセスは根本的に不完全で決定不可能であり（完全性（論理） ）、細胞とコンピュータの類似性の背後には粗雑な比喩以上のものがあることを示唆している。[ 18 ]
計算との類似性は、遺伝システム と生物学的構造の関係にも当てはまり、これは生命の起源を説明する上で最も差し迫った問題の一つを明らかにするものだとよく考えられている。
進化型オートマトン [ 19 ] [ 20 ] [ 21 ] は、進化型チューリングマシン [ 22 ] [ 23 ] [ 21 ] [ 24 ] 進化型有限オートマトン、 終端モード で動作する進化型オートマトンの中で最も単純なサブクラスは、与えられたアルファベット上の任意の言語を受け入れることができ、これには再帰的に列挙できない言語 (対角化言語など) や、再帰的に列挙できるが再帰的ではない言語 (ユニバーサルチューリングマシンの言語など) が含まれます[ 25 ]
著名な実践者 活発な研究者のリストは当然ながら動的で網羅的ではありません。コミュニティのネットワーク分析は2007年に発表されました。[ 26 ]
出版物
ジャーナル 進化計算に関する論文や進化計算を用いた論文は文献に溢れているが、進化計算に特化した学術誌もいくつか存在する。
参考文献 ↑ デ・ヨング、ケネス・A. (2006).進化計算：統一的アプローチ . マサチューセッツ州ケンブリッジ：MIT Press. ISBN 978-0-262-52960-0 。 ↑ クルーゼ、ルドルフ。モスタギム、サナズ。ボーゲルト、クリスチャン。ブラウン、クリスチャン。スタインブレッチャー、マティアス (2022)。 「計算知能」。 計算知能: 方法論的紹介 。コンピュータ サイエンスのテキスト (第 3 版)。チャム：シュプリンガー・インターナショナル・パブリッシング。 pp. 2–3 . 土井 : 10.1007/978-3-030-42227-1 。 ISBN 978-3-030-42226-4 。↑ Chaturvedi, Devenda K. (2008), "Introduction to Soft Computing", Soft Computing 、第 103 巻 、ベルリン、ハイデルベルク: Springer、pp. 1–10 、 doi : 10.1007/978-3-540-77481-5_1 、 ISBN 978-3-540-77480-8 1 2 Eiben, AE; Smith, JE (2015), Evolutionary Computing: The Origins , Natural Computing Series, Berlin, Heidelberg: Springer, pp. 13–24 , doi : 10.1007/978-3-662-44874-8_2 , ISBN 978-3-662-44873-1 ↑ Burgin, Mark; Eberbach, Eugene (2013年4月12日). "進化的機械の文脈における進化的チューリング". arXiv : 1304.3762 [ cs.AI ]. 1 2 3 4 5 Fogel, David B. 編 (1998). 進化計算 ：化石記録 . ニューヨーク：IEEE Press. ISBN 0-7803-3481-7 . OCLC 38270557 . ↑ Fischer, Thomas (1986)、「Kybernetische Systemanalyse einer Tuchfabrik zur Einführung einescomputergestützten Dispositionssystems der Fertigung」、 DGOR 、ベルリン、ハイデルベルク: Springer、p. 120、 土井 ： 10.1007/978-3-642-71161-9_14 、 ISBN 978-3-642-71162-6 ↑ミッチェル 、 メラニー（1998）。 遺伝的アルゴリズム入門 。MIT Press。doi : 10.7551 /mitpress/ 3927.001.0001。ISBN 978-0-262-28001-3 。↑ バリチェリ、ニルス・アール (1954)。 「進化の過程におけるエセンピ・ヌメリシ」。 メソッド : 45–68 。 ↑ Fraser AS (1958). " 遺伝モデルのモンテカルロ解析". Nature . 181 (4603): 208–9 . Bibcode : 1958Natur.181..208F . doi : 10.1038/181208a0 . PMID 13504138. S2CID 4211563 . ↑ Koza, John R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection . MIT Press . ISBN 978-0-262-11170-6 。↑ GC Onwubolu および BV Babu、 Onwubolu 、Godfrey C.; Babu、BV (2004 年 1 月 21 日)。 工学における新しい最適化手法 。Springer。ISBN 9783540201670 2016年9月17日 に取得 。 ↑ 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 . ↑ Campelo, Felipe; Aranha, Claus (2018年6月20日). "Ec Bestiary: 進化型、群知能型、その他のメタファーベースのアルゴリズムの動物誌" . doi : 10.5281/zenodo.1293352 . ↑ 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 . ↑ 「生物学的情報」 。 スタンフォード哲学百科事典 。スタンフォード大学形而上学研究所。2016年。 ↑ 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 . ↑ A. Danchin (2008). "細菌はコンピュータとしてコンピュータを作る" . FEMS Microbiol. Rev. 33 (1): 3– 26. doi : 10.1111/j.1574-6976.2008.00137.x . PMC 2704931 . PMID 19016882 . ↑ 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 。↑ Burgin, M. および Eberbach, E. (2010) Bounded and Periodic Evolutionary Machines、Proc. 2010 Congress on Evolutionary Computation (CEC'2010)、バルセロナ、スペイン、2010、pp. 1379–1386 1 2 Burgin, M.; Eberbach, E. (2012). "進化オートマタ: 進化計算の表現力と収束". The Computer Journal . 55 (9): 1023– 1029. doi : 10.1093/comjnl/bxr099 . ↑ Eberbach E. (2002) 進化的計算の表現力について: ECはアルゴリズム的か?、Proc. 2002 World Congress on Computational Intelligence WCCI'2002、ホノルル、ハワイ、2002、564–569。 ↑ Eberbach, E. (2005) 進化計算の理論に向けて、BioSystems、v. 82、pp. 1-19。 ↑ Eberbach, Eugene; Burgin, Mark (2009). "進化的オートマタを進化的計算の基礎とする：ラリー・フォーゲルは正しかった". 2009 IEEE Congress on Evolutionary Computation . IEEE. pp. 2149–2156 . doi : 10.1109/CEC.2009.4983207 . ISBN 978-1-4244-2958-5 . S2CID 2869386 . ↑ Hopcroft, JE、R. Motwani、JD Ullman (2001) 『オートマタ理論、言語、計算入門』、Addison Wesley、ボストン/サンフランシスコ/ニューヨーク ↑ JJ Merelo および C. Cotta (2007). "最もつながりの強い EC 研究者は誰か? 進化計算における著者の複雑なネットワークの中心性分析". arXiv : 0708.2021 [ cs.CY ].
参考文献 Th. Bäck、DB Fogel、Z. Michalewicz (編)、『進化計算ハンドブック』、1997年、ISBN 0750303921 Th. Bäck および H.-P. Schwefel。「パラメータ最適化のための進化アルゴリズムの概要」。Wayback Machineに 2018 年 7 月 12 日に アーカイブ済み。Evolutionary Computation、1(1):1–23、1993 年。 W. バンツハフ、P. ノルディン、RE ケラー、FD フランコーネ。『遺伝的プログラミング入門』。モーガン・カウフマン、1998年。 S. Cagnoni 他、「進化計算の実世界への応用」、Springer-Verlag Lecture Notes in Computer Science 、ベルリン、2000 年。 R. Chiong、Th. Weise、Z. Michalewicz (編)、『実世界アプリケーションのための進化アルゴリズムの変種』、Springer 、2012年、ISBN 3642234232 K.A. デ・ヨング著『進化計算：統一的アプローチ』MIT Press 、マサチューセッツ州ケンブリッジ、2006年 AE Eiben、JE Smith、「進化的計算からモノの進化へ」、Nature、521:476-482、doi:10.1038/nature14544、2015年 A.E.アイベン、J.E.スミス著、『進化計算入門』、シュプリンガー社、初版2003年、第2版2015年 DB Fogel著『進化計算：機械知能の新しい哲学に向けて』IEEE Press、ピスカタウェイ、ニュージャージー州、1995年。 LJ Fogel、AJ Owens、MJ Walsh。『シミュレーションによる進化を通じた人工知能』ニューヨーク：John Wiley、1966年。 D.E. ゴールドバーグ著『探索、最適化、機械学習における遺伝的アルゴリズム』アディソン・ウェスリー、1989年。 JH ホランド著『自然系および人工系における適応』ミシガン大学出版局 、アナーバー、1975年。 P. ヒングストン、L. バローネ、Z. ミハレヴィッチ （編）、『進化による設計』、自然コンピューティングシリーズ、2008年、シュプリンガー 、ISBN 3540741097 JR Koza著『遺伝的プログラミング：自然進化によるコンピュータのプログラミングについて』MIT Press、マサチューセッツ州、1992年。 FJ Lobo、CF Lima、Z. Michalewicz （編）、『進化アルゴリズムにおけるパラメータ設定』、Springer 、2010年、ISBN 3642088929 Z. ミハレヴィッチ著 、『遺伝的アルゴリズム＋データ構造－進化プログラム』、1996年、シュプリンガー社 、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. シュヴェーフェル著『コンピュータモデルの数値最適化』ジョン・ワイリー・アンド・サンズ、ニューヨーク、1981年。1995年 – 第2版。 D. Simon著『進化最適化アルゴリズム』（2014年3月10日、 Wayback Machineに アーカイブ済み）。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: ポルセリオ・スカバーの生存ルールに基づく新しい最適化アルゴリズム". arXiv : 1709.09840 [ cs.NE ].
外部リンク スタンフォード哲学百科事典に掲載された生物学的情報に関する記事（英語）
