Loading article…
進化アルゴリズム(EA)の集団モデルは、そのメンバーが従う集団の構造特性を記述します。集団とは、 1 回の反復で検討される EA のすべての提案されたソリューションの集合であり、生物学的ロール モデルでは個体とも呼ばれます。集団の個体は、手順の遺伝的演算子の助けを借りて、子孫としてさらに個体を生成することができます。
EA で最も単純で広く使用されている集団モデルは、構造化されていない集団に対応するグローバルモデルまたはパンミクティックモデルです。[1] [2]このモデルでは、各個体が交叉によって子孫を生み出すパートナーとして集団内の他の個体を選択できます。この場合、個体の適応度が重要な役割を果たす限り、選択の詳細は関係ありません。グローバル配偶者選択により、この段階で他のより優れた子孫が出現しない限り、数世代後 ( EA の反復) には、わずかに優れた個体の遺伝情報が集団内で優勢になる可能性があります。このようにして見つかった解が求められている最適値でない場合、それは早期収束と呼ばれます。[3]この効果は、パンミクティック集団でより頻繁に観察されます。[4]
自然界では、地球規模の交配プールはほとんど見られません。空間的な距離による、一定かつ限定的な隔離が優勢です。結果として生じる局所的な近隣地域は、最初は独立して進化し、突然変異体が数世代にわたって存続する可能性が高くなります。その結果、遺伝子プールの遺伝子型の多様性は、汎交配集団よりも長く保存されます。
したがって、以前は全体的だった集団をサブ構造で分割することは明らかです。この目的のために、2つの基本モデルが導入されました。1つは、集団を固定されたサブ集団に分割し、そのサブ集団が随時個体を交換することに基づく島モデルです。 [1] [5]と、個体を重複する近隣に割り当てる近隣モデルです。 [4] [6]は、細胞遺伝学的アルゴリズムまたは進化的アルゴリズム(cGA または cEA)とも呼ばれます。 [7] [8]関連する集団の分割は、対応する手順の並列化も示唆しています。このため、文献では、EA の並列化に関連して集団モデルのトピックも頻繁に議論されています。[1] [2] [4] [5] [9] [10]
島のモデル
島モデルは、移住モデルや粗粒度モデルとも呼ばれ、進化は厳密に分割された集団で起こる。これらはパンミクティックに組織化することもできるが、そうである必要はない。時々、個体の交換が行われ、これを移住と呼ぶ。[2] [5]交換の間の時間はエポックと呼ばれ、その終了はさまざまな基準によって引き起こされる。例えば、所定の時間または所定の世代数の完了後、または停滞の発生後などである。停滞は、例えば、島で所定の世代数にわたって適応度の向上が起こっていないという事実によって検出できる。島モデルは、さまざまな新しい戦略パラメータを導入する。[11] [12] [13] [14]
- サブポピュレーションの数
- サブポピュレーションのサイズ
- 島間の近隣関係: どの島が隣接しているかを決定し、個体を交換できるようにします。単純な一方向リング (黒い矢印) と、追加の双方向近隣関係 (追加の緑の矢印) によるその拡張の図を参照してください。
- エポック、同期、非同期移行の終了基準
- 移住率: 移住に関わる個人の数または割合。
- 移住者の選択: これには多くの選択肢があります。たとえば、最も優れた個体が、最も劣った個体やランダムに選択された個体と入れ替わることがあります。移住率に応じて、一度に 1 つ以上の個体に影響を与える可能性があります。
これらのパラメータにより、選択圧は相当な程度まで影響される可能性があります。たとえば、選択圧は島々の相互接続性に応じて増加し、亜集団の数やエポックの長さに応じて減少します。
近傍モデルまたは細胞進化アルゴリズム
近傍モデルは、拡散モデルまたは細粒度モデルとも呼ばれ、個体群の個体間の位相的な近傍関係を、個体の表現型特性とは無関係に定義する。このモデルの基本的な考え方は、EA 個体群に、各頂点が最も近い近傍と通信する個体である連結グラフとして定義される特別な構造を提供することである。[2] [6]特に、個体は概念的にトーラス メッシュ内に配置され、近い個体とのみ再結合することが許可される。これにより、距離による隔離と呼ばれる一種の局所性が生じる。[6] [7]個体の潜在的な配偶者の集合は、近傍またはデームと呼ばれる。隣の図は、黄色でマークされた 2 つの個体のわずかに重なり合う 2 つの近傍を示し、これを通じて 2 つのデーム間で遺伝情報が拡散する様子を示している。この種のアルゴリズムでは、類似の個体がクラスターを形成し、デーム境界とは無関係なニッチを形成し、特にデームよりも大きくなる可能性があることが知られている。[6] [7]隣接するグループ間には明確な境界線はなく、近いニッチは競合するニッチによって容易に植民地化され、その過程でソリューションの内容が統合される可能性があります。同時に、遠いニッチはよりゆっくりと影響を受ける可能性があります。[6] [7]このタイプの集団を持つEAは、細胞EA（cEA）[8] [15]または細胞遺伝的アルゴリズム（cGA）としても知られています。[7] [16]
集団の個体を配置するために一般的に使用される構造は2Dのトロイダルグリッドですが、[1] [2] [15]次元の数は簡単に拡張（3Dに）または縮小（1D、たとえばリングに、[6] [15]右の図を参照）できます。グリッド内の特定の個体の近傍は、集団内の他の個体までのマンハッタン距離で定義されます。基本的なアルゴリズムでは、すべての近傍は同じサイズと同一の形状です。2次元cEAで最も一般的に使用される2つの近傍は、L5とC9です（左の図を参照）。ここで、Lは線形、Cはコンパクトを表します。各デーム（deme）は汎ミクティックなサブポピュレーションを表し、その中で配偶者選択と子孫の受け入れが親の入れ替えによって行われます。子孫を受け入れるためのルールは、本質的にローカルであり、近隣に基づいています。たとえば、最良の子孫は、置き換えられる親よりも優れている必要があると指定できます。または、より緩く、デーム内の最悪の個体よりも優れているだけです。[2] [6]最初のルールはエリート主義的であり、 2番目の非エリート主義的ルールよりも高い選択圧を生み出します。エリート主義的なEAでは、集団の最良の個体が常に生き残ります。この点で、それらは生物学的モデルから逸脱しています。
近傍領域の重なりにより、近傍領域の境界を越えた遺伝情報の拡散は主にゆっくりと進むため、拡散モデルと呼ばれています。より優れた子孫が集団に拡散するには、汎混合性の場合よりも多くの世代が必要になります。これにより、局所的なニッチの出現とその局所的な進化が促進され、より長い期間にわたって遺伝子型の多様性が維持されます。その結果、実行中に検索空間に適応した幅と深さの探索間のより適切で動的なバランスが実現します。深さの探索はニッチ内で行われ、幅の探索はニッチ境界内と、集団全体のさまざまなニッチの進化を通じて行われます。[17]同じ近傍サイズの場合、遺伝情報の拡散は、C9などのブロックよりもL9などの細長い図形の方が大きく、リングよりも大幅に大きくなります。[18]これは、リング近傍が、比較的長い実行時間を必要とする場合でも、高品質の結果を達成するのに適していることを意味します。一方、主に高速で良好な結果を求めているが、最適ではない可能性がある場合は、2D トポロジの方が適しています。
比較
両方の集団モデルを遺伝的アルゴリズム[5] [6] 、進化戦略[18] [19]、およびその他のEA [20] [21]に適用する場合、全集団をサブ集団に分割すると、通常、早期収束のリスクが軽減され、汎ミクティックEAで予想されるよりも信頼性が高く、全体的に優れた結果が得られます。
島モデルは近傍モデルと比較して、多数の新しい戦略パラメータを導入するという欠点がある。文献にはこのテーマに関する既存の研究があるが、[11] [22] [23]、ユーザーにとって不利な設定のリスクが残っている。一方、近傍モデルでは近傍のサイズのみを指定すればよく、2次元モデルの場合は近傍の数字の選択が追加される。
並列処理
両方の集団モデルは集団分割を意味するため、EA を並列化するための基盤として非常に適しています。[5] [10] [24]これは、セルラー EA にさらに当てはまります。セルラー EA は、それぞれのデームのメンバーに関するローカルで利用可能な情報のみに依存しているからです。したがって、極端な場合、独立した実行スレッドを各個体に割り当てることができるため、cEA 全体を並列ハードウェア プラットフォームで実行できます。[6] [25] [26]アイランド モデルは、たとえば各アイランドにプロセッサを割り当てることによって、並列化もサポートします。アイランドのサブ集団がパンミティックに編成されている場合、世代の子孫のすべての評価を追加で並列化できます。[9] [14] [27]実際のアプリケーションでは、通常、評価が最も時間のかかる部分です。 もちろん、アイランドのサブ集団を cEA として設計して、cEA の並列化に関する前述の説明を適用することもできます。 このようにして、適切な並列化を備えた階層的な集団構造を作成できます。[9]比較的高価なコンピュータクラスタだけでなく、安価なグラフィックカード（GPU）も並列化に使用できます。[28] [29]
ただし、cEA、つまり島々に分布する集団を持つ EA は、従来の EA とは多くの点で異なる検索モデルを表すことを強調することが重要です。さらに、cEA はシーケンシャル プラットフォームと並列プラットフォームの両方で実行できるため、モデルと実装は 2 つの異なる概念であるという事実が強調されます。
文献
- エリック・カントゥ・パス (2001):効率的で正確な並列遺伝的アルゴリズム(博士論文、イリノイ大学アーバナ・シャンペーン校、米国)。Springer、ニューヨーク、NY。ISBN 978-1-4613-6964-6 doi : 10.1007 /978-1-4615-4369-5
- Martina Gorges-Schleuter (1990):遺伝的アルゴリズムと人口構造 - 大規模並列アルゴリズム。博士論文、ドルトムント大学、ドイツ情報学部。
- エンリケ・アルバ、ベルナベ・ドロンソロ (2008):細胞遺伝アルゴリズム。ニューヨーク州ニューヨーク州スプリンガー。ISBN 978-0-387-77609-5土居:10.1007/978-0-387-77610-1
- Dirk Sudholt (2015):並列進化アルゴリズム。Janusz Kacprzyk、Witold Pedrycz (編) 並列進化アルゴリズム。Springer、ベルリン、ハイデルベルク、pp. 929–959 ISBN 978-3-662-43504-5 doi :10.1007/978-3-662-43505-2 46
- ガブリエル・ルケ、エンリケ・アルバ (2011):並列遺伝的アルゴリズム。ベルリン、ハイデルベルクのシュプリンガー。ISBN 978-3-642-22083-8土居：10.1007/978-3-642-22084-5
参照
参考文献
- ^ abcd Cantú-Paz、エリック (1998)。 「並列遺伝的アルゴリズムの調査」(PDF)。電卓パラレル。10 (2): 141–171。
- ^ abcdef Gordon, VS; Whitley, D. (1993), Forrest, S. (ed.)、「関数最適化装置としてのシリアルおよび並列遺伝的アルゴリズム」(PDF)、第 5 回国際遺伝的アルゴリズム会議の議事録、サンマテオ、カリフォルニア州: Morgan Kaufmann、pp. 177–183、ISBN 978-1-55860-299-1
- ^ 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.
- ^ abc 峡谷シュロイター、マルティナ (1990)。遺伝的アルゴリズムと集団構造 - 大規模並列アルゴリズム(PhD)。ドルトムント大学、情報学部、ドイツ。
- ^ abcde Cantú-Paz, Erik (1999). 効率的で正確な並列遺伝的アルゴリズム (博士論文、イリノイ大学アーバナ・シャンペーン校、米国). 遺伝的アルゴリズムと進化的計算。第 1 巻。Springer、ニューヨーク、NY。doi : 10.1007 / 978-1-4615-4369-5。ISBN 978-1-4613-6964-6。
- ^ abcdefghi Gorges-Schleuter、Martina (1991)、Schwefel、Hans-Paul; Männer、Reinhard (編)、「人口構造による遺伝的アルゴリズムの明示的な並列処理」、自然からの並列問題解決、コンピューター サイエンスのレクチャー ノート、vol. 496、ベルリン/ハイデルベルク: Springer-Verlag、pp. 150–159、doi :10.1007/bfb0029746、ISBN 978-3-540-54148-6、 2022-12-15取得
- ^ abcde Gordon, V. Scott; Mathias, Keith; Whitley, Darrell (1994). 「関数最適化装置としてのセルラー遺伝的アルゴリズム」。1994 ACMシンポジウム応用コンピューティング - SAC '94 の議事録。アリゾナ州フェニックス、米国: ACM プレス。pp. 237–241。doi : 10.1145 /326619.326732。ISBN 978-0-89791-647-9. S2CID 6418773。
- ^ ab ジャコビニ、M.;トマッシーニ、M.テッタマンジ、AGB;アルバ、E. (2005 年 10 月)。 「正格子のセル進化アルゴリズムにおける選択強度」。進化的計算に関するIEEEトランザクション。9 (5): 489–505。土井：10.1109/TEVC.2005.850298。ISSN 1089-778X。S2CID 3184685。
- ^ abc Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02). 「ポピュレーションベースのメタヒューリスティックの階層的並列化のための汎用的で柔軟かつスケーラブルなフレームワーク」。デジタルエコシステム管理に関する第12回国際会議の議事録。バーチャルイベントアラブ首長国連邦：ACM。pp. 124–131。doi ：10.1145/ 3415958.3433041。ISBN 978-1-4503-8115-4. S2CID 227179748。
- ^ ab Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (eds.)、「並列進化アルゴリズム」(PDF)、Springer Handbook of Computational Intelligence、ベルリン、ハイデルベルク: Springer、pp. 929–959、doi :10.1007/978-3-662-43505-2_46、ISBN 978-3-662-43504-5、 2023-02-13取得
- ^ ab Cantú-Paz, Erick (1999)、「トポロジー、移行率、および複数集団並列遺伝的アルゴリズム」、遺伝的および進化的計算に関する第 1 回年次会議 (GECCO) の議事録、pp. 91–98
- ^ Belkadi, K.; Gourgand, M.; Benyettou, M. (2006-11-08). 「ハイブリッドフローショップスケジューリング問題のための移行機能を備えた並列遺伝的アルゴリズム」Journal of Applied Mathematics and Decision Sciences . 2006 : 1–17. doi : 10.1155/JAMDS/2006/65746 . ISSN 1173-9126.
- ^ Abdelhafez, Amr; Alba, Enrique; Luque, Gabriel (2019 年 9 月)。「 マルチプロセッサ上の同期および非同期分散遺伝的アルゴリズムのパフォーマンス分析」。Swarm and Evolutionary Computation。49 : 147–157。doi :10.1016/j.swevo.2019.06.003。S2CID 196193164 。
- ^ ab Adar, N.; Kuvat , G. (2016). 「クラスターコンピューティングを使用した動的トポロジーによる並列遺伝的アルゴリズム」。 電気およびコンピューター工学の進歩。16 (3): 73–80。doi : 10.4316 /AECE.2016.03011。ISSN 1582-7445。
- ^ abc Alba, Enrique; Troya, José Ma (2000), Schoenauer, Marc; Deb, Kalyanmoy; Rudolph, Günther; Yao, Xin (eds.)、「細胞進化アルゴリズム: 比率の影響の評価」、Parallel Problem Solving from Nature PPSN VI、vol. 1917、ベルリン、ハイデルベルク: Springer、pp. 29–38、doi :10.1007/3-540-45356-3_3、ISBN 978-3-540-41056-0、 2023-02-11取得
- ^ Folino, G.; Pizzuti, C.; Spezzano, G. (1998). 「セルラー遺伝的アルゴリズムとローカルサーチの組み合わせによる充足可能性問題の解決」。第 10 回 IEEE国際人工知能ツール会議議事録 (カタログ番号 98CH36294)。台北、台湾: IEEE。pp. 192–198。doi :10.1109 / TAI.1998.744842。ISBN 978-0-7803-5214-8. S2CID 8048158。
- ^ アルバ、エンリケ;ドロンソロ、ベルナベ (2008)。セルラー遺伝的アルゴリズム。ニューヨーク：スプリンガー。 p. 12.ISBN 978-0-387-77610-1. OCLC 370728730.
- ^ ab Gorges-Schleuter, Martina (1998)、Eiben, Agoston E.、Bäck, Thomas、Schoenauer, Marc、Schwefel, Hans-Paul (編)、「進化戦略におけるグローバル選択とローカル選択の比較研究」、Parallel Problem Solving from Nature — PPSN V、Lecture Notes in Computer Science、vol. 1498、ベルリン、ハイデルベルク: Springer、pp. 367–377、doi :10.1007/bfb0056879、ISBN 978-3-540-65078-2、 2023-02-11取得
- ^ Sprave, Joachim (1994)、「線形近傍進化戦略」(PDF)、進化プログラミングに関する第3回年次会議の議事録、シンガポール：World Scientific、pp. 42–51 、 2022年11月5日取得
- ^ Jakob, Wilfried (2010-09-01). 「マルチミームアルゴリズムのための一般的なコスト便益ベースの適応フレームワーク」. Memetic Computing . 2 (3). p. 207: 201–218. doi :10.1007/s12293-010-0040-9. ISSN 1865-9292. S2CID 167807.
- ^ Alba, Enrique; Dorronsoro, Bernabé; Alfonso, Hugo (2005). 「Cellular Memetic Algorithms」. Journal of Computer Science and Technology . 5 (4): 257–263 . 2022年11月4日閲覧。
- ^ Wen-Yang Lin、Tzung-Pei Hong、Shu-Min Liu (2004)。「マルチポピュレーション遺伝的アルゴリズムの移行パラメータの適応について」。2004 IEEE国際システム・人間・サイバネティクス会議 (IEEE Cat. No.04CH37583)。第 6 巻。ハーグ、オランダ: IEEE。pp. 5731–5735。doi : 10.1109 /ICSMC.2004.1401108。ISBN 978-0-7803-8567-2. S2CID 31844333。
- ^ Hong, Tzung-Pei; Lin, Wen-Yang; Liu, Shu-Min; Lin, Jiann-Horng (2007-04-20). 「複数個体群遺伝的アルゴリズムにおける移行率の動的調整」. Journal of Advanced Computational Intelligence and Intelligent Informatics . 11 (4): 410–415. doi : 10.20965/jaciii.2007.p0410 . ISSN 1883-8014.
- ^ ルケ、ガブリエル、アルバ、エンリケ (2011)。並列遺伝的アルゴリズム。計算知能の研究。第367巻。ベルリン、ハイデルベルク：シュプリンガー。doi : 10.1007 / 978-3-642-22084-5。ISBN 978-3-642-22083-8。
- ^ Luque, Gabriel; Alba, Enrique; Dorronsoro, Bernabé (2009 年 7 月)。「組み合わせ最適化のためのセルラー遺伝的アルゴリズムの非同期並列実装」。遺伝的および進化的計算に関する第11 回年次会議の議事録。モントリオール、ケベック、カナダ: ACM。pp. 1395–1402。doi :10.1145 / 1569901.1570088。ISBN 978-1-60558-325-9. S2CID 14113702。
- ^ Zhongwen Luo、Hongzhi Liu (2006)。「グラフィック ハードウェアでの 3-SAT 問題に対するセルラー遺伝的アルゴリズムとローカル検索」。2006 IEEE 国際進化計算会議。バンクーバー、ブリティッシュ コロンビア州、カナダ: IEEE。pp. 2988–2992。doi : 10.1109 / CEC.2006.1688685。ISBN 978-0-7803-9487-2. S2CID 8142372。
- ^ Cahon, S.; Melab, N.; Talbi, E.-G. (2004 年 5 月). 「ParadisEO: 並列および分散メタヒューリスティックの再利用可能な設計のためのフレームワーク」. Journal of Heuristics . 10 (3): 357–380. doi :10.1023/B:HEUR.0000026900.92269.ec. ISSN 1381-1231. S2CID 14972999.
- ^ ポール・イェーネ (2016).マイヤー、ハインリヒ・クリスチャン。ピンツガー、マーティン (編)。グラフィック カード上の進化的アルゴリズムの並列化に関する研究の現状の概要(PDF)。ボン: Gesellschaft für Informatik、FRG。ISBN 978-3-88579-653-4. OCLC 962381748.
{{cite book}}:|work=無視されました (ヘルプ) - ^ ガルシア＝カルボ、ラウル;ギサド、Jl;ディアス・デル・リオ、フェルナンド。コルドバ、アントニオ。ヒメネス・モラレス、フランシスコ（2018年1月）。 「グラフィックス処理ユニット – 遺伝子制御ネットワークの時間的ダイナミクスを解決するための強化された遺伝的アルゴリズム」。進化的バイオインフォマティクス。１４．土井：10.1177/1176934318767889。ISSN 1176-9343。PMC 5898668。PMID 29662297。