進化アルゴリズム

計算知能（CI）において、進化的アルゴリズム（EA）は進化的計算^[1]のサブセットであり、一般的な集団ベースのメタヒューリスティック最適化アルゴリズムです。EAは、生殖、突然変異、組み換え、選択などの生物学的進化にヒントを得たメカニズムを使用します。最適化問題に対する候補解は集団内の個体の役割を果たし、適応度関数は解の質を決定します（損失関数も参照）。上記の演算子を繰り返し適用することで集団の進化が起こります。

進化的アルゴリズムは、理想的には基礎となる適応度地形について何の仮定も立てないため、あらゆるタイプの問題に対して近似解をうまく実行できることが多い。生物進化のモデリングに適用される進化的アルゴリズムの手法は、一般に、ミクロ進化プロセスの探究と細胞プロセスに基づくモデル計画に限定されている。EA の実際のアプリケーションのほとんどにおいて、計算の複雑さが阻害要因となっている。^[2]実際、この計算の複雑さは適応度関数の評価によるものである。適応度近似はこの困難を克服する解決策の 1 つである。しかし、一見単純な EA でも複雑な問題を解決できることが多いため、^[3]^[4]^[5]アルゴリズムの複雑さと問題の複雑さの間には直接的な関連がない可能性がある。

実装

以下は、一般的な単一目的遺伝的アルゴリズムの例です。

ステップ 1:個体の初期集団をランダムに生成します。(第 1 世代)

ステップ 2: 終了 (時間制限、十分な適応度の達成など) まで、次の再生ステップを繰り返します。

集団内の各個体の適応度を評価する
適応度に基づいて繁殖する個体を選択します。(親)
交叉と突然変異の操作を通じて新しい個体を繁殖させ、子孫を産みます。
集団の中で最も適合度の低い個体を新しい個体に置き換えます。

種類

類似の技術であっても、遺伝的表現やその他の実装の詳細、および適用される特定の問題の性質が異なります。

遺伝的アルゴリズム– これは最も一般的なタイプのEAです。問題の解決策を数値の文字列の形で求めます（伝統的にはバイナリですが、通常、最適な表現は解決する問題について何かを反映したものです）^[2]。このタイプのEAは、組み換えや突然変異などの演算子（場合によってはどちらか一方、または両方）を適用することで、最適化問題でよく使用されます。
遺伝的プログラミング– ここでは、ソリューションはコンピュータプログラムの形式であり、その適合性は計算問題を解決する能力によって決まります。遺伝的プログラミングには、デカルト遺伝的プログラミング、遺伝子発現プログラミング、文法的進化、線形遺伝的プログラミング、多重発現プログラミングなど、さまざまなバリエーションがあります。
進化型プログラミング- 遺伝的プログラミングに似ていますが、プログラムの構造は固定されており、数値パラメータは進化することができます。
進化戦略– 解の表現として実数のベクトルを使用し、通常は自己適応型突然変異率を使用します。この方法は主に数値最適化に使用されますが、組み合わせタスク用のバリエーションもあります。^[6]^[7]
微分進化– ベクトルの差に基づいているため、主に数値最適化問題に適しています。
共進化アルゴリズム – 遺伝的アルゴリズムや進化戦略に似ていますが、作成されたソリューションは他のソリューションとの相互作用の結果に基づいて比較されます。ソリューションは、検索プロセス中に競合または協力することができます。共進化アルゴリズムは、適応度地形が動的、複雑、または競合的な相互作用を含むシナリオでよく使用されます。^[8]^[9]
ニューロエボリューション– 遺伝的プログラミングに似ていますが、ゲノムは構造と接続の重みを記述することで人工ニューラルネットワークを表します。ゲノムのエンコードは直接的または間接的に行うことができます。
学習分類システム– ここでのソリューションは分類器のセット (ルールまたは条件) です。ミシガン LCS は個々の分類器のレベルで進化しますが、ピッツバーグ LCS は分類器セットの集団を使用します。当初、分類器はバイナリのみでしたが、現在では実数、ニューラルネット、またはS 式タイプが含まれます。適応度は通常、強度または精度に基づく強化学習または教師あり学習アプローチのいずれかで決定されます。
品質と多様性のアルゴリズム – QDアルゴリズムは、高品質で多様なソリューションを同時に目指します。問題に対する最善の解決策を見つけることだけに焦点を当てた従来の最適化アルゴリズムとは異なり、QDアルゴリズムは問題空間全体でさまざまなソリューションを探索し、パフォーマンスが高いだけでなく、多様でユニークなものを維持します。^[10]^[11]^[12]

理論的背景

以下の理論的原則は、すべてまたはほぼすべての EA に適用されます。

フリーランチ定理はない

最適化における「ただで買えるランチはない」という定理は、すべての最適化問題を考慮すると、すべての最適化戦略は同等に効果的であると述べています。同じ条件下では、どの進化アルゴリズムも根本的に他のアルゴリズムより優れていることはありません。これは、すべての問題のセットが制限されている場合にのみ当てはまります。これは、実際には必然的に行われることです。したがって、EA を改善するには、何らかの形で問題の知識を活用する必要があります (たとえば、特定の突然変異の強度または問題に適応したコーディングを選択することによって)。したがって、2 つの EA を比較する場合、この制約が暗黙的に適用されます。さらに、EA は、たとえば、開始集団全体をランダムに生成するのではなく、ヒューリスティックまたはその他の手順を通じていくつかの個体を作成することによって、問題固有の知識を使用できます。 ^[13]^[14] EA を特定の問題領域に合わせて調整するもう 1 つの可能性は、子孫を生成するプロセスで、適切なヒューリスティック、ローカル検索手順、またはその他の問題関連の手順を含めることです。この形式の EA の拡張は、ミームアルゴリズムとも呼ばれます。どちらの拡張機能も、検索プロセスを高速化し、より堅牢にすることができるため、実際のアプリケーションで重要な役割を果たします。^[13]^[15]

収束

子孫に加えて、少なくとも親世代の最良の個体が次の世代を形成するために使用されるEA（いわゆるエリートEA）の場合、最適値が存在するという条件下で収束の一般的な証明があります。一般性を失うことなく、証明には最大探索が想定されます。

エリート主義的な子孫の受容の特性と最適値の存在から、世代ごとにそれぞれの最良の個体の適応度の向上が確率で発生することがわかります。したがって、 $k$ $F$ $x'$ $P>0$

F(x'_{1})\leq F(x'_{2})\leq F(x'_{3})\leq \cdots \leq F(x'_{k})\leq \cdots

つまり、適応度値は単調に減少しないシーケンスを表し、最適値の存在により制限されます。これにより、シーケンスが最適値に対して収束することが分かります。

この証明は収束の速度について何も述べていないため、EA の実際の応用にはほとんど役立ちません。しかし、エリート EA を使用するという推奨を正当化します。ただし、通常の汎ミクティック人口モデルを使用する場合、エリート EA は非エリート EA よりも早期に収束する傾向があります。 ^[16]汎ミクティック人口モデルでは、配偶者選択 (実装に関するセクションのステップ 2) は、人口全体のすべての個体が配偶者として適格になるように行われます。非汎ミクティック人口では、選択が適切に制限されるため、汎ミクティックの個体と比較して、より優れた個体の分散速度が低下します。したがって、エリート EA の早期収束の一般的なリスクは、配偶者選択を制限する適切な人口モデルによって大幅に削減できます。^[17]^[18]

仮想アルファベット

1990年、デイビッド・E・ゴールドバーグは仮想アルファベットの理論を用いて、実数表現を使用すると、古典的な再結合演算子（例えば、一様またはn点交差）を使用するEAは、バイナリ数値のコーディングとは対照的に、検索空間の特定の領域に到達できないことを示しました。^[19]この結果、実数表現のEAでは、再結合に算術演算子（例えば、算術平均または中間再結合）を使用することが推奨されます。適切な演算子を使用すると、以前の意見に反して、実数値表現はバイナリ表現よりも効果的です。^[20]^[21]

生物学的プロセスとの比較

多くの進化アルゴリズムの限界として考えられるの^は^、遺伝子型と表現型の明確な区別がないことである。自然界では、受精卵細胞は胚発生と呼ばれる複雑な過程を経て^{成熟した表現}型になる。この間接的なエンコーディングは、遺伝子探索をより堅牢にする（つまり、致命的な突然変異の可能性を減らす）と考えられており、生物の進化可能性も向上させる可能性がある。 ^[22]^[23]このような間接的な（生成的または発達的とも呼ばれる）エンコーディングにより、進化は環境の規則性を利用することも可能になる。^[24]人工胚発生、または人工発達システムの分野における最近の研究は、これらの懸念に対処しようとしている。そして、遺伝子発現プログラミングは、遺伝子型が固定長の線形多遺伝子染色体で構成され、表現型が複数の発現ツリーまたは異なるサイズと形状のコンピュータプログラムで構成される遺伝子型-表現型システムをうまく探究している。^[25]^{[不適切な合成？ ]}

モンテカルロ法との比較

どちらの方法クラスにも共通しているのは、個々の探索ステップが偶然に決定されるという点です。しかし、主な違いは、EA は他の多くのメタヒューリスティックと同様に、過去の探索ステップから学習し、この経験を方法固有の形式で次の探索ステップの実行に組み込むことです。EA では、これはまず、パートナーの選択と次世代の形成のための適応度ベースの選択演算子を通じて行われます。次に、探索ステップの種類です。EA では、現在のソリューションから開始して変更するか、2 つのソリューションの情報を混合します。対照的に、モンテカルロ法で新しいソリューションを切り出す場合、通常、既存のソリューションとの関連性はありません。^[26]^[27]

一方、タスクの検索空間に学習するものが何もない場合、モンテカルロ法は、以前の検索から適切な結論を導き出そうとするアルゴリズムのオーバーヘッドを含まないため、適切なツールです。このようなタスクの例としては、干し草の山の中の針を探すこと、たとえば、狭いピークが 1 つある平らな (超) 平面の形の針を探すことが挙げられます。

アプリケーション

進化的アルゴリズムが実際に使用される分野はほぼ無制限であり^[5]、産業、^[28]^[29]エンジニアリング、^[2]^[3]^[30]複雑なスケジューリング、^[4]^[31]^[32]農業、^[33]ロボットの動作計画^[34]および金融^[35]^[36]から研究^[37]^[38]および芸術にまで及びます。進化的アルゴリズムの適用には、EA を使用したタスクへのアプローチが従来の正確な方法とは異なり、通常、エンジニアや他の分野のカリキュラムの一部ではないため、経験の浅いユーザーによる再考が必要です。たとえば、適応度計算では、目標を定式化するだけでなく、それに向けた進化的探索プロセスをサポートする必要があります。たとえば、元の品質基準のより良い評価にまだつながらない改善に報酬を与えることによってサポートします。たとえば、スケジューリングタスクで人員配置やエネルギー消費などのリソースのピーク使用率を回避する場合、最大使用率を評価するだけでは不十分です。むしろ、実際の最大ピーク値を下回る削減を評価するために、まだ許容可能なレベルを超えた回数と期間も記録する必要があります。^[39]そのため、初心者を対象とし、初心者の間違いを避け、アプリケーションプロジェクトを成功に導くのに役立つ出版物がいくつかあります。^[39]^[40]^[41]これには、問題を解決するためにEAを使用する必要がある場合と、使用しない方が良い場合の基本的な質問を明確にすることが含まれます。

例

2020年にGoogleは、 AutoML-Zeroがニューラルネットワークの概念などの古典的なアルゴリズムを再発見することに成功したと述べました。^[42]

コンピュータシミュレーションTierraとAvida は、マクロ進化のダイナミクスをモデル化しようとします。

ギャラリー

^[43]^[44]^[45]

制限付きローゼンブロック関数と制限付きグローバル最適解を用いた2集団EA探索
制約付きローゼンブロック関数上の 2 つの集団の EA 検索。グローバル最適値は制限されていません。
キーン関数上の分布アルゴリズムの推定
シミオネスク関数の有界最適解の2集団EA探索

参考文献

^ Vikhar, PA (2016). 「進化的アルゴリズム: 批判的レビューと将来の展望」2016 信号処理、情報コンピューティング、通信のグローバルトレンドに関する国際会議 (ICGTSPICC) 。ジャルガオン。pp. 261–265。doi :10.1109/ ICGTSPICC.2016.7955308。ISBN 978-1-5090-0467-6. S2CID 22100336。{{cite book}}: CS1 maint: location missing publisher (link)
^ abc Cohoon, JP; Karro, J.; Lienig, J. (2003). 「VLSI 回路の物理設計のための進化的アルゴリズム」『進化的コンピューティングの進歩: 理論と応用』(PDF)。ロンドン: Springer Verlag。pp. 683–712。ISBN 978-3-540-43330-9。
^ ab Slowik, Adam; Kwasnicka, Halina (2020). 「進化的アルゴリズムとエンジニアリング問題への応用」.ニューラルコンピューティングとアプリケーション. 32 (16): 12363–12379. doi : 10.1007/s00521-020-04832-8 . ISSN 0941-0643. S2CID 212732659.
^ ab Mika, Marek; Waligóra, Grzegorz; Węglarz, Jan ( 2011). 「ワークフローアプリケーションのためのネットワークリソースを使用したグリッドリソース割り当て問題のモデル化と解決」。Journal of Scheduling。14 (3): 291–306。doi : 10.1007 /s10951-009-0158-0。ISSN 1094-6136。S2CID 31859338 。
^ ab 「進化的計算の応用に関する国際会議」。この会議はEvo*シリーズの一部です。会議の議事録はSpringerから出版されています。2022年12月23日閲覧。
^ ニッセン、フォルカー; Krause, Matthias (1994)、「Constrained Combinatorial Optimization with an Evolution Strategy」、Reusch、Bernd (編)、Fuzzy Logik、Informatik aktuell、ベルリン、ハイデルベルク: Springer、pp. 33–40、doi :10.1007/978- 3-642-79386-8_5、ISBN 978-3-642-79386-8
^ バーモント州コエリョ;イミダチ州コエリョ。ソウザ、MJF。 TA、オリベイラ。コタ、LP;ミネソタ州ハダッド;ムラデノビッチ、N.シルバ、RCP。フロリダ州ギマランイス（2016）。「組み合わせ最適化問題のための近傍構造によって導かれるハイブリッド自己適応進化戦略」。エボルコンピューティング。24 (4): 637–666。土井：10.1162/EVCO_a_00187。PMID 27258842。S2CID 13582781 。
^ マ、シャオリアン;リー・シャオドン。張、清府。唐、柯。梁正平。謝偉信。 Zhu、Zexuan (2019)、「協力的共進化アルゴリズムに関する調査。」、進化的計算に関する IEEE トランザクション、23 (3): 421–441、doi :10.1109/TEVC.2018.2868770、S2CID 125149900 、取得2023-05-22
^ Popovici, Elena; Bucci, Anthony; Wiegand, R. Paul; De Jong, Edwin D. (2012). 「共進化の原理」。Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (編)。自然コンピューティングハンドブック。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。pp. 987–1033。doi : 10.1007 /978-3-540-92910-9_31。ISBN 978-3-540-92910-9。
^ Pugh, Justin K.; Soros, Lisa B.; Stanley, Kenneth O. (2016-07-12). 「品質の多様性: 進化的計算の新たなフロンティア」. Frontiers in Robotics and AI . 3 . doi : 10.3389/frobt.2016.00040 . ISSN 2296-9144.
^ Lehman, Joel; Stanley, Kenneth O. (2011-07-12). 「新規性探索と局所的競争による仮想生物の多様性の進化」。遺伝的および進化的計算に関する第 13 回年次会議の議事録。米国ニューヨーク: ACM。pp. 211–218。doi : 10.1145 / 2001576.2001606。ISBN 9781450305570.S2CID 17338175 。
^ Cully, Antoine; Clune, Jeff; Tarapore, Danesh; Mouret, Jean-Baptiste (2015-05-27). 「動物のように適応できるロボット」. Nature . 521 (7553): 503–507. arXiv : 1407.3501 . Bibcode :2015Natur.521..503C. doi :10.1038/nature14422. ISSN 0028-0836. PMID 26017452. S2CID 3467239.
^ ab Davis, Lawrence (1991). 遺伝的アルゴリズムハンドブック. ニューヨーク: Van Nostrand Reinhold. ISBN 0-442-00173-8. OCLC 23081440.
^ Lienig, Jens; Brandt, Holger (1994)、Davidor, Yuval; Schwefel, Hans-Paul; Männer, Reinhard (編)、「マルチチップモジュールのルーティングのための進化的アルゴリズム」、Parallel Problem Solving from Nature — PPSN III、vol. 866、ベルリン、ハイデルベルク：Springer、pp. 588–597、doi：10.1007/3-540-58484-6_301、ISBN 978-3-540-58484-1、2022-10-18取得
^ Neri, Ferrante; Cotta, Carlos; Moscato, Pablo, 編 (2012). ミームアルゴリズムハンドブック. 計算知能研究. 第379巻. ベルリン、ハイデルベルク: Springer Berlin Heidelberg. doi :10.1007/978-3-642-23247-3. ISBN 978-3-642-23246-6。
^ Leung, Yee; Gao, Yong; Xu, Zong-Ben (1997). 「集団多様性の度合い - 遺伝的アルゴリズムにおける早期収束とそのマルコフ連鎖分析の観点」IEEE Transactions on Neural Networks . 8 (5): 1165–1176. doi :10.1109/72.623217. ISSN 1045-9227. PMID 18255718.
^ Gorges-Schleuter、Martina (1998)、Eiben、Agoston E.;バック、トーマス。マーク・シェーナウアー。 Schwefel、Hans-Paul (編)、「進化戦略におけるグローバル選択とローカル選択の比較研究」、自然からの並列問題解決 — PPSN V、コンピューターサイエンスの講義ノート、vol. 1498 年、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp. 367–377、doi :10.1007/bfb0056879、ISBN 978-3-540-65078-2、2022-10-21取得
^ Dorronsoro, Bernabe; Alba, Enrique ( 2008 ). セルラー遺伝的アルゴリズム。オペレーションズ・リサーチ/コンピュータサイエンス・インターフェース・シリーズ。第42巻。ボストン、マサチューセッツ州: Springer US。doi :10.1007 / 978-0-387-77610-1。ISBN 978-0-387-77609-5。
^ Goldberg, David E. (1990)、Schwefel, Hans-Paul、Männer, Reinhard (編)、「仮想アルファベットの理論」、Parallel Problem Solving from Nature、Lecture Notes in Computer Science、vol. 496、ベルリン/ハイデルベルク: Springer-Verlag (1991 年発行)、pp. 13–22、doi :10.1007/bfb0029726、ISBN 978-3-540-54148-6、 2022年10月22日取得
^ Stender, J.; Hillebrand, E.; Kingdon, J. (1994). 最適化、シミュレーション、モデリングにおける遺伝的アルゴリズム。アムステルダム: IOS Press。ISBN 90-5199-180-0. OCLC 47216370.
^ Michalewicz, Zbigniew (1996). 遺伝的アルゴリズム + データ構造 = 進化プログラム (第 3 版). ベルリンハイデルベルク: Springer. ISBN 978-3-662-03315-9. OCLC 851375253.
^ GS HornbyとJB Pollack。「身体と脳の進化のための生成表現による高レベルコンポーネントの作成」。人工生命、8(3):223–246、2002年。
^ Jeff Clune、Benjamin Beckmann、Charles Ofria、Robert Pennock。「HyperNEAT Generative Encoding による協調四足歩行の進化」Wayback Machineに 2016-06-03 にアーカイブ。IEEE進化コンピューティング会議進化ロボティクス特別セクションの議事録、2009 年。ノルウェー、トロンハイム。
^ J. Clune、C. Ofria、および RT Pennock、「問題の規則性が減少するにつれて生成エンコーディングがどのように機能するか」、PPSN (G. Rudolph、T. Jansen、SM Lucas、C. Poloni、および N. Beume 編)、 Lecture Notes in Computer Scienceの第 5199 巻、pp. 358–367、Springer、2008 年。
^ Ferreira, C.、2001 年、「遺伝子発現プログラミング: 問題解決のための新しい適応アルゴリズム」。Complex Systems、第 13 巻、第 2 号: 87–129 ページ。
^シュウェフェル、ハンス・ポール（1995年）。進化と最適探索。第6世代コンピュータ技術シリーズ。ニューヨーク： ワイリー。p.109。ISBN 978-0-471-57148-3。
^ Fogel, David B.; Bäck, Thomas; Michalewicz, Zbigniew 編 (2000). Evolutionary Computation 1. ブリストル; フィラデルフィア: Institute of Physics Publishing. pp. xxx および xxxvii (用語集). ISBN 978-0-7503-0664-5. OCLC 44807816.
^ Sanchez, Ernesto; Squillero, Giovanni; Tonda, Alberto ( 2012 ). 進化アルゴリズムの産業応用。インテリジェントシステムリファレンスライブラリ。第34巻。ベルリン、ハイデルベルク：Springer Berlin Heidelberg。doi ：10.1007 / 978-3-642-27467-1。ISBN 978-3-642-27466-4。
^ Miettinen, Kaisa; Neittaanmäki, Pekka; Mäkelä, MM; Périaux, Jacques 編 (1999)。工学とコンピュータサイエンスにおける進化的アルゴリズム: 遺伝的アルゴリズム、進化戦略、進化的プログラミング、遺伝的プログラミング、および産業用アプリケーションにおける最近の進歩。チチェスター: Wiley and Sons。ISBN 0-585-29445-3. OCLC 45728460.
^ ゲン・ミツオ、チェン・ルンウェイ (1999-12-17)。遺伝的アルゴリズムとエンジニアリング最適化。Wiley シリーズエンジニアリングデザインとオートメーション。ホーボーケン、ニュージャージー州、米国: John Wiley & Sons、Inc. doi :10.1002 / 9780470172261。ISBN 978-0-470-17226-1。
^ Dahal, Keshav P.; Tan, Kay Chen; Cowling, Peter I. (2007). 進化的スケジューリング. ベルリン: Springer. doi :10.1007/978-3-540-48584-1. ISBN 978-3-540-48584-1. OCLC 184984689.
^ Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe; Süß, Wolfgang (2013-04-22). 「マルチ基準ミームコンピューティングを使用した、制約のある異種リソースへの複数のワークフローの高速再スケジュール」。アルゴリズム 。6 ( 2 ) : 245–277。doi : 10.3390/a6020245。ISSN 1999-4893。
^ Mayer, David G. (2002). 進化的アルゴリズムと農業システム。ボストン、マサチューセッツ州: Springer US. doi :10.1007/978-1-4615-1717-7. ISBN 978-1-4613-5693-6。
^ ブルーム、クリスチャン (2000)、カグノーニ、ステファノ (編)、「進化型ソフトウェア GLEAM による最適化された衝突のないロボット移動ステートメント生成」、進化型コンピューティングの実世界アプリケーション、LNCS 1803、vol. 1803、ベルリン、ハイデルベルク: シュプリンガー、pp. 330–341、doi :10.1007/3-540-45561-2_32、ISBN 978-3-540-67353-8、2022-12-28取得
^ Aranha, Claus; Iba, Hitoshi (2008)、Wobcke, Wayne; Zhang, Mengjie (編)、「ポートフォリオ最適化問題へのミームアルゴリズムの適用」、AI 2008: 人工知能の進歩、コンピュータサイエンスの講義ノート、vol. 5360、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp. 512–521、doi :10.1007/978-3-540-89378-3_52、ISBN 978-3-540-89377-6、2022-12-23取得
^ 陳淑恒編 (2002)。経済と金融における進化的計算。あいまいさとソフトコンピューティングの研究。第 100 巻。ハイデルベルク: Physica-Verlag HD。doi : 10.1007 / 978-3-7908-1784-3。ISBN 978-3-7908-2512-1。
^ Lohn, JD; Linden, DS; Hornby, GS; Kraus, WF (2004 年 6 月)。「NASA のスペーステクノロジー 5 ミッション向け X バンドアンテナの進化的設計」IEEE アンテナおよび伝播学会シンポジウム、2004 年。第 3 巻。pp. 2313–2316 第 3 巻。doi : 10.1109/ APS.2004.1331834。hdl : 2060 / 20030067398。ISBN 0-7803-8302-8。
^フォゲル、ゲイリー、コルネ、デイビッド（2003）。 バイオインフォマティクスにおける進化的計算。エルゼビア。doi :10.1016/ b978-1-55860-797-2.x5000-8。ISBN 978-1-55860-797-2。
^ ab Jakob, Wilfried (2021)、「進化的アルゴリズムの成功への適用 - 現実世界のアプリケーションから得たガイド」、KIT Scientific Working Papers、vol. 170、カールスルーエ、FRG：KIT Scientific Publishing、arXiv：2107.11300、doi：10.5445/IR/1000135763、S2CID 236318422 、 2022年12月23日取得
^ Whitley, Darrell (2001). 「進化的アルゴリズムの概要: 実用的な問題とよくある落とし穴」.情報およびソフトウェア技術. 43 (14): 817–831. doi :10.1016/S0950-5849(01)00188-4. S2CID 18637958.
^ Eiben, AE; Smith, JE (2015). 「進化的アルゴリズムの活用」。進化的コンピューティング入門。ナチュラルコンピューティングシリーズ (第 2 版)。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。pp. 147–163。doi :10.1007/ 978-3-662-44874-8。ISBN 978-3-662-44873-1. S2CID 20912932。
^ Gent, Edd (2020年4月13日). 「人工知能はそれ自体で進化している」. Science | AAAS . 2020年4月16日時点のオリジナルよりアーカイブ。2020年4月16日閲覧。
^ Simionescu, PA; Dozier, GV; Wainwright, RL (2006). 「制約付き最適化問題のための 2 集団進化アルゴリズム」。2006 IEEE 国際進化計算会議。バンクーバー、ブリティッシュコロンビア州、カナダ: IEEE。pp. 1647–1653。doi : 10.1109 / CEC.2006.1688506。ISBN 978-0-7803-9487-2.S2CID 1717817 。
^ Simionescu, PA; Dozier, GV; Wainwright, RL (2006). 「制約付き最適化問題のための 2 集団進化アルゴリズム」(PDF) . 2006 IEEE 国際進化計算会議 . Proc 2006 IEEE 国際進化計算会議。バンクーバー、カナダ。pp. 1647–1653。doi :10.1109/ CEC.2006.1688506。ISBN 0-7803-9487-9. S2CID 1717817 . 2017年1月7日閲覧。{{cite book}}: CS1 maint: location missing publisher (link)
^ Simionescu, PA (2014). AutoCAD ユーザーのためのコンピュータ支援グラフ作成およびシミュレーションツール(第 1 版). フロリダ州ボカラトン: CRC プレス. ISBN 978-1-4822-5290-3。

外部リンク

進化的アルゴリズムの歴史と特徴の概要

文献

Ashlock, D. (2006)、「モデリングと最適化のための進化的計算」、Springer、ニューヨーク、doi:10.1007/0-387-31909-3 ISBN 0-387-22196-4。
Bäck, T. (1996)、「理論と実践における進化アルゴリズム：進化戦略、進化プログラミング、遺伝的アルゴリズム」、オックスフォード大学出版局、ニューヨーク、ISBN 978-0-19-509971-3。
Bäck, T.、Fogel, D.、Michalewicz, Z. (1999)、「進化的計算 1: 基本的なアルゴリズムと演算子」、CRC Press、ボカラトン、米国、ISBN 978-0-7503-0664-5。
Bäck, T.、Fogel, D.、Michalewicz, Z. (2000)、「進化的計算 2: 高度なアルゴリズムと演算子」、CRC Press、ボカラトン、米国、doi:10.1201/9781420034349 ISBN 978-0-3678-0637-8。
Banzhaf, W.、Nordin, P.、Keller, R.、Francone, F. (1998)、『Genetic Programming - An Introduction』、Morgan Kaufmann、サンフランシスコ、ISBN 978-1-55860-510-7。
Eiben, AE, Smith, JE (2003)、「進化コンピューティング入門」、Springer、ハイデルベルグ、ニューヨーク、doi:10.1007/978-3-662-44874-8 ISBN 978-3-662-44873-1。
Holland, JH (1992)、「自然システムと人工システムにおける適応」、MIT Press、ケンブリッジ、MA、ISBN 978-0-262-08213-6。
Michalewicz, Z.; Fogel, DB (2004)、「How To Solve It: Modern Heuristics」、Springer、ベルリン、ハイデルベルク、ISBN 978-3-642-06134-9、doi:10.1007/978-3-662-07807-5。
Benko, Attila; Dosa, Gyorgy; Tuza, Zsolt (2010)。「ビンパッキング/カバーリングとデリバリー、アルゴリズムの進化で解決」。2010 IEEE第 5 回バイオインスパイアードコンピューティング国際会議: 理論とアプリケーション (BIC-TA)。pp. 298–302。doi :10.1109 / BICTA.2010.5645312。ISBN 978-1-4244-6437-1. S2CID 16875144。
Poli, R.; Langdon, WB; McPhee, NF (2008)。遺伝的プログラミングのフィールドガイド。Lulu.com、インターネットから無料で入手可能。ISBN 978-1-4092-0073-4. 2016年5月27日時点のオリジナルよりアーカイブ。2011年3月5日閲覧。^{[自費出版ソース]}
Price, K., Storn, RM, Lampinen, JA, (2005). Differential Evolution: A Practical Approach to Global Optimization、Springer、ベルリン、ハイデルベルク、ISBN 978-3-642-42416-8、doi:10.1007/3-540-31306-0。
Ingo Rechenberg (1971)、進化戦略 - 生物進化の最適化技術システム(博士論文)。 Fromman-Holzboog (1973) によって再版されました。ISBN 3-7728-1642-8
Hans-Paul Schwefel (1974)、コンピュータモデレンの最適化(博士論文)。 Birkhäuser によって再版されました (1977)。
ハンス・ポール・シュヴェフェル（1995）「進化と最適の探求」ワイリー・アンド・サンズ、ニューヨーク。ISBN 0-471-57148-2
Simon, D. (2013)、進化的最適化アルゴリズム、 Wayback Machineで 2014-03-10 にアーカイブ、Wiley & Sons、ISBN 978-0-470-93741-9
クルーゼ、ルドルフ。ボーゲルト、クリスチャン。フランク・クラウォン。モエヴェス、クリスチャン。スタインブレッチャー、マティアス;開催、Pascal (2013)、Computational Intelligence: A Methodological Introduction。スプリンガー、ロンドン。ISBN 978-1-4471-5012-1、doi:10.1007/978-1-4471-5013-8。
Rahman, Rosshairy Abd.; Kendall, Graham; Ramli, Razamin; Jamari, Zainoddin; Ku-Mahamud, Ku Ruhana (2017). 「制約を処理するためのパワーヒューリスティックを備えた進化的アルゴリズムによるエビ飼料配合」。複雑性。2017 : 1–12。doi : 10.1155 /2017/7053710。

[EVOALG-1] Vikhar, PA (2016). 「進化的アルゴリズム: 批判的レビューと将来の展望」2016 信号処理、情報コンピューティング、通信のグローバルトレンドに関する国際会議 (ICGTSPICC) 。ジャルガオン。pp. 261–265。doi :10.1109/ ICGTSPICC.2016.7955308。ISBN 978-1-5090-0467-6. S2CID 22100336。{{cite book}}: CS1 maint: location missing publisher (link)

[VLSI-2] Cohoon, JP; Karro, J.; Lienig, J. (2003). 「VLSI 回路の物理設計のための進化的アルゴリズム」『進化的コンピューティングの進歩: 理論と応用』(PDF)。ロンドン: Springer Verlag。pp. 683–712。ISBN 978-3-540-43330-9。

[:0-3] Slowik, Adam; Kwasnicka, Halina (2020). 「進化的アルゴリズムとエンジニアリング問題への応用」.ニューラルコンピューティングとアプリケーション. 32 (16): 12363–12379. doi : 10.1007/s00521-020-04832-8 . ISSN 0941-0643. S2CID 212732659.

[:1-4] Mika, Marek; Waligóra, Grzegorz; Węglarz, Jan ( 2011). 「ワークフローアプリケーションのためのネットワークリソースを使用したグリッドリソース割り当て問題のモデル化と解決」。Journal of Scheduling。14 (3): 291–306。doi : 10.1007 /s10951-009-0158-0。ISSN 1094-6136。S2CID 31859338 。

[:2-5] 「進化的計算の応用に関する国際会議」。この会議はEvo*シリーズの一部です。会議の議事録はSpringerから出版されています。2022年12月23日閲覧。

[6] ニッセン、フォルカー; Krause, Matthias (1994)、「Constrained Combinatorial Optimization with an Evolution Strategy」、Reusch、Bernd (編)、Fuzzy Logik、Informatik aktuell、ベルリン、ハイデルベルク: Springer、pp. 33–40、doi :10.1007/978- 3-642-79386-8_5、ISBN 978-3-642-79386-8

[7] バーモント州コエリョ;イミダチ州コエリョ。ソウザ、MJF。 TA、オリベイラ。コタ、LP;ミネソタ州ハダッド;ムラデノビッチ、N.シルバ、RCP。フロリダ州ギマランイス（2016）。「組み合わせ最適化問題のための近傍構造によって導かれるハイブリッド自己適応進化戦略」。エボルコンピューティング。24 (4): 637–666。土井：10.1162/EVCO_a_00187。PMID 27258842。S2CID 13582781 。

[8] マ、シャオリアン;リー・シャオドン。張、清府。唐、柯。梁正平。謝偉信。 Zhu、Zexuan (2019)、「協力的共進化アルゴリズムに関する調査。」、進化的計算に関する IEEE トランザクション、23 (3): 421–441、doi :10.1109/TEVC.2018.2868770、S2CID 125149900 、取得2023-05-22

[9] Popovici, Elena; Bucci, Anthony; Wiegand, R. Paul; De Jong, Edwin D. (2012). 「共進化の原理」。Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (編)。自然コンピューティングハンドブック。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。pp. 987–1033。doi : 10.1007 /978-3-540-92910-9_31。ISBN 978-3-540-92910-9。

[10] Pugh, Justin K.; Soros, Lisa B.; Stanley, Kenneth O. (2016-07-12). 「品質の多様性: 進化的計算の新たなフロンティア」. Frontiers in Robotics and AI . 3 . doi : 10.3389/frobt.2016.00040 . ISSN 2296-9144.

[11] Lehman, Joel; Stanley, Kenneth O. (2011-07-12). 「新規性探索と局所的競争による仮想生物の多様性の進化」。遺伝的および進化的計算に関する第 13 回年次会議の議事録。米国ニューヨーク: ACM。pp. 211–218。doi : 10.1145 / 2001576.2001606。ISBN 9781450305570.S2CID 17338175 。

[12] Cully, Antoine; Clune, Jeff; Tarapore, Danesh; Mouret, Jean-Baptiste (2015-05-27). 「動物のように適応できるロボット」. Nature . 521 (7553): 503–507. arXiv : 1407.3501 . Bibcode :2015Natur.521..503C. doi :10.1038/nature14422. ISSN 0028-0836. PMID 26017452. S2CID 3467239.

[Davis91-13] Davis, Lawrence (1991). 遺伝的アルゴリズムハンドブック. ニューヨーク: Van Nostrand Reinhold. ISBN 0-442-00173-8. OCLC 23081440.

[14] Lienig, Jens; Brandt, Holger (1994)、Davidor, Yuval; Schwefel, Hans-Paul; Männer, Reinhard (編)、「マルチチップモジュールのルーティングのための進化的アルゴリズム」、Parallel Problem Solving from Nature — PPSN III、vol. 866、ベルリン、ハイデルベルク：Springer、pp. 588–597、doi：10.1007/3-540-58484-6_301、ISBN 978-3-540-58484-1、2022-10-18取得

[15] Neri, Ferrante; Cotta, Carlos; Moscato, Pablo, 編 (2012). ミームアルゴリズムハンドブック. 計算知能研究. 第379巻. ベルリン、ハイデルベルク: Springer Berlin Heidelberg. doi :10.1007/978-3-642-23247-3. ISBN 978-3-642-23246-6。

[16] Leung, Yee; Gao, Yong; Xu, Zong-Ben (1997). 「集団多様性の度合い - 遺伝的アルゴリズムにおける早期収束とそのマルコフ連鎖分析の観点」IEEE Transactions on Neural Networks . 8 (5): 1165–1176. doi :10.1109/72.623217. ISSN 1045-9227. PMID 18255718.

[17] Gorges-Schleuter、Martina (1998)、Eiben、Agoston E.;バック、トーマス。マーク・シェーナウアー。 Schwefel、Hans-Paul (編)、「進化戦略におけるグローバル選択とローカル選択の比較研究」、自然からの並列問題解決 — PPSN V、コンピューターサイエンスの講義ノート、vol. 1498 年、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp. 367–377、doi :10.1007/bfb0056879、ISBN 978-3-540-65078-2、2022-10-21取得

[18] ^ Dorronsoro, Bernabe; Alba, Enrique ( 2008 ). セルラー遺伝的アルゴリズム。オペレーションズ・リサーチ/コンピュータサイエンス・インターフェース・シリーズ。第42巻。ボストン、マサチューセッツ州: Springer US。doi :10.1007 / 978-0-387-77610-1。ISBN 978-0-387-77609-5。

[19] Goldberg, David E. (1990)、Schwefel, Hans-Paul、Männer, Reinhard (編)、「仮想アルファベットの理論」、Parallel Problem Solving from Nature、Lecture Notes in Computer Science、vol. 496、ベルリン/ハイデルベルク: Springer-Verlag (1991 年発行)、pp. 13–22、doi :10.1007/bfb0029726、ISBN 978-3-540-54148-6、 2022年10月22日取得

[20] Stender, J.; Hillebrand, E.; Kingdon, J. (1994). 最適化、シミュレーション、モデリングにおける遺伝的アルゴリズム。アムステルダム: IOS Press。ISBN 90-5199-180-0. OCLC 47216370.

[21] Michalewicz, Zbigniew (1996). 遺伝的アルゴリズム + データ構造 = 進化プログラム (第 3 版). ベルリンハイデルベルク: Springer. ISBN 978-3-662-03315-9. OCLC 851375253.

[22] GS HornbyとJB Pollack。「身体と脳の進化のための生成表現による高レベルコンポーネントの作成」。人工生命、8(3):223–246、2002年。

[23] Jeff Clune、Benjamin Beckmann、Charles Ofria、Robert Pennock。「HyperNEAT Generative Encoding による協調四足歩行の進化」Wayback Machineに 2016-06-03 にアーカイブ。IEEE進化コンピューティング会議進化ロボティクス特別セクションの議事録、2009 年。ノルウェー、トロンハイム。

[24] J. Clune、C. Ofria、および RT Pennock、「問題の規則性が減少するにつれて生成エンコーディングがどのように機能するか」、PPSN (G. Rudolph、T. Jansen、SM Lucas、C. Poloni、および N. Beume 編)、 Lecture Notes in Computer Scienceの第 5199 巻、pp. 358–367、Springer、2008 年。

[25] Ferreira, C.、2001 年、「遺伝子発現プログラミング: 問題解決のための新しい適応アルゴリズム」。Complex Systems、第 13 巻、第 2 号: 87–129 ページ。

[26] ^シュウェフェル、ハンス・ポール（1995年）。進化と最適探索。第6世代コンピュータ技術シリーズ。ニューヨーク： ワイリー。p.109。ISBN 978-0-471-57148-3。

[27] Fogel, David B.; Bäck, Thomas; Michalewicz, Zbigniew 編 (2000). Evolutionary Computation 1. ブリストル; フィラデルフィア: Institute of Physics Publishing. pp. xxx および xxxvii (用語集). ISBN 978-0-7503-0664-5. OCLC 44807816.

[28] ^ Sanchez, Ernesto; Squillero, Giovanni; Tonda, Alberto ( 2012 ). 進化アルゴリズムの産業応用。インテリジェントシステムリファレンスライブラリ。第34巻。ベルリン、ハイデルベルク：Springer Berlin Heidelberg。doi ：10.1007 / 978-3-642-27467-1。ISBN 978-3-642-27466-4。

[29] Miettinen, Kaisa; Neittaanmäki, Pekka; Mäkelä, MM; Périaux, Jacques 編 (1999)。工学とコンピュータサイエンスにおける進化的アルゴリズム: 遺伝的アルゴリズム、進化戦略、進化的プログラミング、遺伝的プログラミング、および産業用アプリケーションにおける最近の進歩。チチェスター: Wiley and Sons。ISBN 0-585-29445-3. OCLC 45728460.

[30] ゲン・ミツオ、チェン・ルンウェイ (1999-12-17)。遺伝的アルゴリズムとエンジニアリング最適化。Wiley シリーズエンジニアリングデザインとオートメーション。ホーボーケン、ニュージャージー州、米国: John Wiley & Sons、Inc. doi :10.1002 / 9780470172261。ISBN 978-0-470-17226-1。

[31] Dahal, Keshav P.; Tan, Kay Chen; Cowling, Peter I. (2007). 進化的スケジューリング. ベルリン: Springer. doi :10.1007/978-3-540-48584-1. ISBN 978-3-540-48584-1. OCLC 184984689.

[32] Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe; Süß, Wolfgang (2013-04-22). 「マルチ基準ミームコンピューティングを使用した、制約のある異種リソースへの複数のワークフローの高速再スケジュール」。アルゴリズム 。6 ( 2 ) : 245–277。doi : 10.3390/a6020245。ISSN 1999-4893。

[33] Mayer, David G. (2002). 進化的アルゴリズムと農業システム。ボストン、マサチューセッツ州: Springer US. doi :10.1007/978-1-4615-1717-7. ISBN 978-1-4613-5693-6。

[34] ブルーム、クリスチャン (2000)、カグノーニ、ステファノ (編)、「進化型ソフトウェア GLEAM による最適化された衝突のないロボット移動ステートメント生成」、進化型コンピューティングの実世界アプリケーション、LNCS 1803、vol. 1803、ベルリン、ハイデルベルク: シュプリンガー、pp. 330–341、doi :10.1007/3-540-45561-2_32、ISBN 978-3-540-67353-8、2022-12-28取得

[35] Aranha, Claus; Iba, Hitoshi (2008)、Wobcke, Wayne; Zhang, Mengjie (編)、「ポートフォリオ最適化問題へのミームアルゴリズムの適用」、AI 2008: 人工知能の進歩、コンピュータサイエンスの講義ノート、vol. 5360、ベルリン、ハイデルベルク: Springer Berlin Heidelberg、pp. 512–521、doi :10.1007/978-3-540-89378-3_52、ISBN 978-3-540-89377-6、2022-12-23取得

[36] 陳淑恒編 (2002)。経済と金融における進化的計算。あいまいさとソフトコンピューティングの研究。第 100 巻。ハイデルベルク: Physica-Verlag HD。doi : 10.1007 / 978-3-7908-1784-3。ISBN 978-3-7908-2512-1。

[37] Lohn, JD; Linden, DS; Hornby, GS; Kraus, WF (2004 年 6 月)。「NASA のスペーステクノロジー 5 ミッション向け X バンドアンテナの進化的設計」IEEE アンテナおよび伝播学会シンポジウム、2004 年。第 3 巻。pp. 2313–2316 第 3 巻。doi : 10.1109/ APS.2004.1331834。hdl : 2060 / 20030067398。ISBN 0-7803-8302-8。

[38] ^フォゲル、ゲイリー、コルネ、デイビッド（2003）。 バイオインフォマティクスにおける進化的計算。エルゼビア。doi :10.1016/ b978-1-55860-797-2.x5000-8。ISBN 978-1-55860-797-2。

[:3-39] Jakob, Wilfried (2021)、「進化的アルゴリズムの成功への適用 - 現実世界のアプリケーションから得たガイド」、KIT Scientific Working Papers、vol. 170、カールスルーエ、FRG：KIT Scientific Publishing、arXiv：2107.11300、doi：10.5445/IR/1000135763、S2CID 236318422 、 2022年12月23日取得

[40] Whitley, Darrell (2001). 「進化的アルゴリズムの概要: 実用的な問題とよくある落とし穴」.情報およびソフトウェア技術. 43 (14): 817–831. doi :10.1016/S0950-5849(01)00188-4. S2CID 18637958.

[41] Eiben, AE; Smith, JE (2015). 「進化的アルゴリズムの活用」。進化的コンピューティング入門。ナチュラルコンピューティングシリーズ (第 2 版)。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。pp. 147–163。doi :10.1007/ 978-3-662-44874-8。ISBN 978-3-662-44873-1. S2CID 20912932。

[42] Gent, Edd (2020年4月13日). 「人工知能はそれ自体で進化している」. Science | AAAS . 2020年4月16日時点のオリジナルよりアーカイブ。2020年4月16日閲覧。

[43] Simionescu, PA; Dozier, GV; Wainwright, RL (2006). 「制約付き最適化問題のための 2 集団進化アルゴリズム」。2006 IEEE 国際進化計算会議。バンクーバー、ブリティッシュコロンビア州、カナダ: IEEE。pp. 1647–1653。doi : 10.1109 / CEC.2006.1688506。ISBN 978-0-7803-9487-2.S2CID 1717817 。

[44] Simionescu, PA; Dozier, GV; Wainwright, RL (2006). 「制約付き最適化問題のための 2 集団進化アルゴリズム」(PDF) . 2006 IEEE 国際進化計算会議 . Proc 2006 IEEE 国際進化計算会議。バンクーバー、カナダ。pp. 1647–1653。doi :10.1109/ CEC.2006.1688506。ISBN 0-7803-9487-9. S2CID 1717817 . 2017年1月7日閲覧。{{cite book}}: CS1 maint: location missing publisher (link)

[45] Simionescu, PA (2014). AutoCAD ユーザーのためのコンピュータ支援グラフ作成およびシミュレーションツール(第 1 版). フロリダ州ボカラトン: CRC プレス. ISBN 978-1-4822-5290-3。

実装

種類