Loading article…
細胞進化アルゴリズム（cEA）は、個体が任意に交配することはできず、それぞれが近隣の個体と相互作用し、基本的な進化アルゴリズム（選択、変異、置換）が適用される進化アルゴリズム（EA）の一種です。
セルラーモデルは、暫定的な最適化、学習、または探索問題の解を符号化する個体の視点から自然進化をシミュレートします。このモデルの基本的な考え方は、EA集団に連結グラフとして定義される特別な構造を与えることです。このグラフでは、各頂点が最も近い隣接個体と通信する個体です。具体的には、個体は概念的にトーラス状のメッシュに配置され、近い個体とのみ再結合が許可されます。これは、「距離による隔離」として知られる一種の局所性につながります。個体の潜在的な交配相手の集合は、その個体の近傍と呼ばれます。この種のアルゴリズムでは、類似した個体がクラスターを形成してニッチを作る傾向があり、これらのグループはまるで別々の亜集団（島）のように機能することが知られています。隣接するグループ間に明確な境界はなく、近いニッチは競合するニッチによって容易に「植民地化」され、その過程で解の内容が融合する可能性があります。
細胞進化アルゴリズム（cEA）は通常、構造化された2次元グリッド状の個体群を進化させるが、他のトポロジーも可能である。このグリッド内では、進化の過程で類似した個体のクラスターが自然に形成され、それによって境界内での探索が促進される。探索は主に、クラスター内での直接的な競争と融合によって行われる。
グリッドは通常2次元のトーラス構造ですが、次元数は簡単に拡張または縮小できます（1次元、つまりリング状）。グリッドの特定の点（個体が配置される場所）の近傍は、その点から集団内の他の点までのマンハッタン距離によって定義されます。グリッドの各点には、近くの個体の近傍と重なる近傍があります。基本アルゴリズムでは、すべての近傍は同じサイズと同一の形状です。最も一般的に使用される2つの近傍は、フォン・ノイマン近傍またはNEWS（北、東、西、南）近傍とも呼ばれるL5と、ムーア近傍とも呼ばれるC9です。ここで、Lは「線形」、Cは「コンパクト」を表します。
cEAでは、個体は変異演算子が適用される生殖サイクルにおいてのみ、近隣個体と相互作用することができます。この生殖サイクルは各個体の近傍内で実行され、一般的には、特定の基準に従って近隣個体の中から2つの親個体を選択し、それらに変異演算子（例えば、組換えと突然変異）を適用し、特定の基準（例えば、子孫個体が対象個体よりも優れた解である場合に置換する）に従って、対象個体を新たに生成された子孫個体に置き換えることから構成されます。
通常の同期型cEAでは、アルゴリズムは左上の最初の個体から右へ、そして複数の行へと進み、集団内の情報を用いて新しい一時集団を作成します。右下の最後の個体の処理が完了すると、一時集団は新しく計算された個体で満たされ、置換ステップが開始されます。このステップでは、何らかの基準に従って、古い集団が新しく計算された集団と完全に同期的に置き換えられます。通常、置換では最良の個体が両方の集団で同じ位置に保持されます。つまり、エリート主義が用いられます。
使用される個体群の更新ポリシーに従って、非同期セルオートマトンも定義することができ、これはセルオートマトンにおけるよく知られた問題である。非同期セルオートマトンでは、グリッド内の個体が更新される順序は、基準の選択（ラインスイープ、固定ランダムスイープ、新規ランダムスイープ、均一選択）によって変化する。これら4つの基準はすべて、新しく計算された個体（またはより良い場合は元の個体）を使用して、その近傍の個体の計算を進める。
近傍の重複は、cEAへの解の移行を暗黙的に促進するメカニズムを提供する。最良の解は集団全体にスムーズに拡散するため、集団の遺伝的多様性は非構造化EAよりも長く維持される。集団全体への最良の解の緩やかな拡散は、 cEAが探索中に行う探索 と活用の良好なトレードオフにおける主要な要素の一つである。このトレードオフは、（例えば）使用する近傍のサイズを変更することで調整できる（ひいては進化に伴う遺伝的多様性のレベルも調整できる）。なぜなら、近傍間の重複度は近傍のサイズに応じて増加するからである。
cEAは、確率的な書き換え規則を持つセルオートマトン（CA）と見なすことができ、CAのアルファベットは問題の潜在的な解の数に相当します。したがって、CAの研究から得られた知見をcEAに適用することができます。
セルラー進化アルゴリズム（cEA）は並列処理に非常に適しているため、並列メタヒューリスティクスの文献によく見られます。特に、きめ細かい並列処理を用いることで、各個体に独立した実行スレッドを割り当てることができ、cEA全体を並列処理可能なハードウェアプラットフォーム上で実行できます。このようにして、FPGAやGPU上でcEAを実行する際に、大幅な時間短縮を実現できます。
しかし、cEAは探索モデルであり、多くの点で従来のEAとは異なることを強調しておくことが重要です。また、cEAはシーケンシャルプラットフォームとパラレルプラットフォームの両方で実行できるため、モデルと実装は2つの異なる概念であることが改めて示されます。
cEAの理解、設計、および応用に関する基礎知識の完全な説明については、こちらをご覧ください。