進化的計算

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

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

進化的計算技術は、幅広い問題設定において高度に最適化されたソリューションを生み出すことができるため、コンピュータサイエンスの分野で人気があります。より具体的な問題群やデータ構造に適した多くの変種や拡張機能が存在します。進化的計算は、一般的な進化プロセスの共通側面を研究するためのコンピューター内実験手順 として、進化生物学でも使用されることがあります。

進化のプロセスを模倣して問題を解決するという概念は、コンピュータの出現以前にさかのぼり、例えばアラン・チューリングが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]従来の勾配降下法では局所的最小値に陥る結果が生じる可能性があるため、レッヒェンベルクとシュヴェフェルは、ランダムな突然変異（何らかの解ベクトルのすべてのパラメータに適用）を使用してこれらの最小値から抜け出すことを提案した。子解は親解から生成され、2つのうちより成功した方が将来の世代のために保持された。この手法は、2人によって初めて流体力学の最適化問題を解くために使用された。^[4]当初、この最適化手法はコンピュータを使わずに実行され、代わりにサイコロを使ってランダムな突然変異を決定していた。1965年までに、計算は完全に機械で実行されるようになった。^[3]

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

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

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

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

• エージェントベースモデリング
• 蟻コロニー最適化
• 人工免疫システム
• 人工生命（デジタル生物も参照）
• 文化アルゴリズム
• 共進化アルゴリズム
• 差異的進化
• 二段階進化
• 分布推定アルゴリズム
• 進化アルゴリズム
• 進化的プログラミング
• 進化戦略
• 遺伝子発現プログラミング
• 遺伝的アルゴリズム
• 遺伝的プログラミング
• 文法の進化
• 学習可能な進化モデル
• 学習分類システム
• ミームアルゴリズム
• 神経進化
• 粒子群最適化
• カブトムシの触角探索
• 自己組織化マップ、競争学習などの自己組織化
• 群知能

最近提案された他の多くのアルゴリズムを含む詳細なカタログが、Evolutionary Computation Bestiaryに掲載されています。^[11]ただし、最近のアルゴリズムの多くは実験的検証が不十分であることに注意することが重要です。^[12]

進化的アルゴリズムは、一般的に生殖、突然変異、組み換え、自然淘汰、適者生存などの生物進化にヒントを得たメカニズムを実装する技術のみを使用する点で、進化的計算のサブセットを形成します。最適化問題に対する候補ソリューションは、集団内の個体の役割を果たし、コスト関数はソリューションが「生きる」環境を決定します (適応度関数も参照)。上記の演算子を繰り返し適用すると、集団の進化が起こります。

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

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

遺伝的アルゴリズムは、システムの将来の状態を予測するために使用されるため、動的システムの理論にリンクされた生物システムとシステム生物学をモデル化する手法を提供します。これは、生物学における発達の秩序立った、よく制御された、高度に構造化された特徴に注意を向けるための、鮮明な（しかし誤解を招く可能性のある）方法にすぎません。

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

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

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

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

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

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

• カリヤンモイ・デブ
• ケネス・A・デ・ヨング
• ピーター・J・フレミング
• デビッド・B・フォーゲル
• ステファニー・フォレスト
• デビッド・E・ゴールドバーグ
• ジョン・ヘンリー・ホランド
• テオ・ヤンセン
• ジョン・コザ
• ズビグニエフ・ミハレヴィチ
• メラニー・ミッチェル
• ピーター・ノルディン
• リカルド・ポリ
• インゴ・レッヒェンベルグ
• ハンス・パウル・シュヴェフェル

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

• 進化計算（ジャーナル）（1993年創刊）
• 人工生命（ジャーナル）（1993年創刊）
• IEEE Transactions on Evolutionary Computation（1997年設立）
• 遺伝的プログラミングと進化型マシン（2000 年設立）
• スウォームインテリジェンス（2007年設立）
• 進化型知能（2008年設立）
• 人工進化と応用ジャーナル (2008-2010)
• ミームティックコンピューティング（2009年設立）
• 国際応用進化計算ジャーナル（2010年創刊）
• 群集と進化計算（2011年設立）
• 群知能と進化計算に関する国際ジャーナル（2012年創刊）

進化計算分野の主な会議には以下のものがある。

• ACM 遺伝的および進化的計算会議（GECCO）、
• IEEE進化計算会議（CEC）、
• EvoStarは、EuroGP、EvoApplications、EvoCOP、EvoMUSARTの4つの会議で構成されています。
• 自然からの並列問題解決(PPSN)。

• スタンフォード哲学百科事典の生物学的情報に関する記事（英語）

• Th. Bäck、DB Fogel、Z. Michalewicz (編集者)、進化計算ハンドブック、1997 年、ISBN  0750303921
• Th. Bäck と H.-P. Schwefel。パラメータ最適化のための進化的アルゴリズムの概要。2018 年 7 月 12 日にWayback Machineにアーカイブ。進化的計算、1(1):1–23、1993。
• W. Banzhaf、P. Nordin、RE 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 アイベンと JE スミス、「進化的計算から物事の進化へ」、ネイチャー、521:476-482、doi:10.1038/nature14544、2015 年
• AE Eiben および JE Smith、「進化的コンピューティング入門」、Springer、第 1 版、2003 年、第 2 版、2015 年
• DB Fogel. 進化的計算。機械知能の新しい哲学に向けて。IEEE Press、ニュージャージー州ピスカタウェイ、1995 年。
• LJ Fogel、AJ Owens、MJ Walsh。『シミュレートされた進化による人工知能』ニューヨーク：John Wiley、1966年。
• DE Goldberg. 探索、最適化、機械学習における遺伝的アルゴリズム。Addison Wesley、1989年。
• JH Holland. 自然および人工システムにおける適応。ミシガン大学出版局、アナーバー、1975年。
• P. Hingston、L. Barone、Z. Michalewicz (編集者)、Design by Evolution、Natural Computing Series、2008 年、Springer、ISBN 3540741097 
• JR Koza. 遺伝的プログラミング: 自然進化によるコンピュータのプログラミングについて。MIT Press、マサチューセッツ、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、ニューヨーク、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].