ミームアルゴリズム

パブロ・モスカートは、MAを次のように特徴づけています。「ミームアルゴリズムは、集団ベースのグローバル探索と、各個体が行うヒューリスティックなローカル探索の融合です。...ローカル探索を行うメカニズムは、ローカル最適解に到達するか、(目的コスト関数に関して) 所定のレベルまで改善することです。」そして彼は、「私はMAを遺伝的表現に限定しているわけではありません」と強調しています。 ^{[ 1 ]： 19-20}このMAの元の定義は、探索サイクルにおける文化的進化の特徴(ローカル改良の形で)を包含していますが、遺伝/ミーム伝達、変異、選択のすべてのコア原理が欠けているため、普遍的ダーウィニズムに従って真の進化システムとして適格とは言えないかもしれません。これが、MAという用語が最初に導入されたときに研究者の間で批判と論争を引き起こした理由を示しています。^{[ 1 ]}次の擬似コードは、このMAの一般的な定義に対応します。

擬似コード

手順ミームアルゴリズム 初期化:初期集団を生成し、個体を評価して品質値を割り当てます。 停止条件が満たされるまで、確率的探索演算子を使用して新しい集団 を進化させます。集団内のすべての個体を評価して品質値を割り当てます。 個体のサブセットを選択し、$\displaystyle \Omega _{il}}$個人改善手続きを受けるべき 個人。$\displaystyle \Omega _{il}}$ ミームを使用して、頻度または確率で個別学習を実行します。${\displaystyle f_{il}}$強度は$til$ ラマルク的学習またはボールドウィン的学習 を進める。end for end while

この文脈におけるラマルク的学習とは、個々の学習ステップで発見された改善された解に従って染色体を更新することを意味し、一方、ボールドウィン的学習は染色体を変更せず、改善された適応度のみを使用する。この擬似コードでは、どのステップが個体の適応度に基づいているか、どのステップがそうでないかは明確にされていない。問題となるのは、新しい集団の進化と選択である。$\displaystyle \Omega _{il}}$。

ほとんどの MA 実装は EA に基づいているため、Krasnogor に従って、第 1 世代の対応する代表の擬似コードもここに示します。^{[ 10 ]}

擬似コード

EA初期化に基づくミームアルゴリズムの 手順：${\displaystyle t=0}$; // 世代カウンタの初期化 初期集団をランダムに生成する${\displaystyle P(t)}$; 適応度を計算する${\displaystyle f(p)\ \ \forall p\in P(t)}$; 停止条件が満たされない間、選択を 実行します。${\displaystyle f(p)}$サブセットを選択する${\displaystyle P(t)}$そして保管する${\displaystyle M(t)}$子孫：個体を組み換え、突然変異させる${\displaystyle p\in M(t)}$そして保管する${\displaystyle M'(t)}$学習：改善${\displaystyle p'}$ローカル検索またはヒューリスティックによる${\displaystyle \forall p'\in M'(t)}$評価 :適応度を計算する${\displaystyle f(p')\ \ \forall p'\in M'(t)}$; ラマルク学習の場合、染色体を更新します${\displaystyle p'}$改善によると${\displaystyle \forall p'\in M'(t)}$; fi新世代:生成${\displaystyle P(t+1)}$から数名を選ぶ${\displaystyle P(t)}$そして${\displaystyle M'(t)}$;${\displaystyle t=t+1}$; // 世代カウンタをインクリメントする whileループ終了 最良の個体を返す${\displaystyle p\in P(t-1)}$その結果;

このMAスキームにはいくつかの代替案があります。例えば：

• ミームによって、当初の個人の一部または全部が改善される可能性がある。
• 子孫ではなく、親株を局所的に改良することも可能だ。
• すべての子孫ではなく、ランダムに選択された、または適応度に依存する一部の子孫のみが局所的な改善を受ける可能性がある。後者では、子孫の評価が必要となる。${\displaystyle M'(t)}$学習ステップの前に。

マルチミーム^{[ 11 ]} 、ハイパーヒューリスティック^{[ 12 ] [ 13 ]}、メタラマルクMA ^{[ 2 ] [ 3 ]}は、その設計においてミーム伝達と選択の原理を示す第2世代MAと呼ばれています。マルチミームMAでは、ミーム素材は遺伝子型の一部としてエンコードされます。その後、各個体/染色体のデコードされたミームを使用して、局所的な改良が実行されます。ミーム素材は、単純な遺伝メカニズムを介して親から子孫に伝達されます。一方、ハイパーヒューリスティックMAとメタラマルクMAでは、考慮される候補ミームのプールは、報酬メカニズムを介して局所的な改良を生成する過去のメリットに基づいて競合し、将来の局所的な改良に進むために選択されるミームを決定します。報酬が高いミームは、引き続き使用される可能性が高くなります。第2世代MAのレビューについては、すなわち、進化システム内の複数の個々の学習方法を考慮したMAについては、読者は^{[ 14 ]を参照されたい。}

共進化^{[ 15 ]}と自己生成MA ^{[ 16 ]}は、基本的な進化システムの定義を満たす3つの原理すべてが考慮された第3世代MAとみなすことができます。使用するミームが事前にわかっていると仮定する第2世代MAとは対照的に、第3世代MAはルールベースの局所探索を利用して進化システム内の候補解を補完し、問題空間で規則的に繰り返される特徴やパターンを捉えます。

連続最適化の文脈では、個別学習は局所ヒューリスティックまたは従来の厳密な列挙法の形で存在します。^{[ 19 ]}個別学習戦略の例としては、ヒルクライミング、シンプレックス法、ニュートン/準ニュートン法、内点法、共役勾配法、線探索、その他の局所ヒューリスティックなどがあります。一般的な個別学習法のほとんどは決定論的であることに注意してください。

一方、組み合わせ最適化においては、個々の学習手法は、特定の問題に合わせて調整されたヒューリスティック（決定論的または確率論的）の形で一般的に存在します。代表的なヒューリスティック手法やスキームには、k遺伝子交換、エッジ交換、第一改善法など、多数あります。

ミームアルゴリズムの設計に関連する最初の課題の1つは、個々の学習をどのくらいの頻度で適用するか、つまり個々の学習頻度を検討することです。あるケースでは、^{[ 17 ]}個々の学習頻度がMA探索のパフォーマンスに与える影響が検討され、MA探索のさまざまな段階での個々の学習頻度のさまざまな構成が調査されました。逆に、別の場所では^{[ 20 ]}、個々の学習の計算複雑性が比較的低い場合は、すべての個体に個々の学習を適用することが有益である可能性があることが示されています。

EA集団の中から個体学習を受けるべき適切な個体を選択する問題に関して、Land ^{[ 21 ]}は、連続パラメトリック探索問題における染色体の集団に個体学習を適用する確率を適応させるために、適応度ベースおよび分布ベースの戦略を研究し、その研究を組み合わせ最適化問題に拡張した。Bambha らは、パラメータ化された個体学習を進化アルゴリズムに体系的に統合して最大の解品質を達成するためのシミュレート加熱技術を導入した。^{[ 22 ]}

個々の学習強度、$til$は、個々の学習の反復に割り当てられる計算予算の量です。つまり、個々の学習が単一の解を改善するために費やすことができる最大計算予算です。

発見された改善が、より良い適応度（ボールドウィン学習）によってのみ機能するのか、それとも個体もそれに応じて適応する（ラマルク学習）のかを決定する必要がある。EA の場合、これは遺伝子型の調整を意味する。この問題は、1990 年代にはすでに文献で EA に関して議論されており、特定のユースケースが重要な役割を果たすとされている。^{[ 23 ] [ 24 ] [ 25 ]}議論の背景には、ゲノム適応が早すぎる収束を促進する可能性があるという点がある。このリスクは、構造化された集団の使用など、探索の幅と深さのバランスをより良く取るための他の手段によって効果的に軽減できる。^{[ 3 ]}