ミームアルゴリズム

コンピュータサイエンスとオペレーションズリサーチにおけるミームアルゴリズム（MA）は、従来の遺伝的アルゴリズム（GA）またはより一般的な進化的アルゴリズム（EA）の拡張版です。最適化問題に対して十分に優れたソリューションを提供することができます。適切なヒューリスティックまたはローカルサーチ手法を使用して、EAによって生成されたソリューションの品質を向上させ、早期収束の可能性を減らします。^[1]

ミームアルゴリズムは、進化的計算における近年の成長研究分野の 1 つです。MA という用語は現在、進化的アプローチまたは集団ベースのアプローチと、問題探索のための個別の個別学習または局所的改善手順との相乗効果として広く使用されています。文献では、MA はボールドウィン進化アルゴリズム(EA)、ラマルク EA、文化アルゴリズム、または遺伝的局所探索とも呼ばれることがよくあります。

ダーウィンの自然進化の原理とドーキンスのミームの概念の両方に触発されて、ミームアルゴリズム（MA）という用語は、1989年の技術レポート^[2]でパブロ・モスカートによって導入されました。モスカートは、MAを、局所的な改良を実行できる個々の学習手順と組み合わせた、集団ベースのハイブリッド遺伝的アルゴリズム（GA）の一種に近いものと見なしました。一方ではダーウィンの進化との比喩的な類似点、他方ではミームとドメイン固有（ローカル検索）ヒューリスティックスとの類似点がミームアルゴリズム内で捉えられ、一般性と問題の特殊性のバランスが取れた方法論となっています。この2段階の性質により、ミームアルゴリズムは二段階進化の特殊なケースとなっています。

複雑な最適化の文脈では、幅広い応用分野にわたってミームアルゴリズムのさまざまなインスタンス化が報告されており、一般的に、従来の進化的アルゴリズムよりも効率的に高品質のソリューションに収束します。^[3]

一般に、計算フレームワーク内でミーム学の考え方を使用することは、ミーム計算またはミーム計算(MC) と呼ばれます。^{[4] [5]} MC では、普遍的なダーウィニズムの特徴がより適切に捉えられます。 この観点から見ると、MA は MC のより制約された概念です。 より具体的には、MA は MC の 1 つの領域をカバーし、特に最適化問題を解決するための他の決定論的改良手法と組み合わせた進化アルゴリズムの領域を扱います。 MC は、ミームの概念を拡張して、知識強化手順または表現の概念的エンティティをカバーします。

最適化と探索のノーフリーランチ定理[ ^{6] [7]}は、すべての最適化戦略は、すべての最適化問題の集合に対して同等に効果的であると述べています。逆に言えば、これは次のことが期待できることを意味します。アルゴリズムが問題または問題のクラスを効率的に解決するほど、そのアルゴリズムは一般性が低くなり、問題固有の知識に基づいて構築されます。この洞察は、一般的に適用可能なメタヒューリスティックをアプリケーション固有の方法またはヒューリスティックで補完するという推奨に直接つながり、^[8] MAの概念とよく一致しています。

パブロ・モスカートは MA を次のように特徴づけている。「ミームアルゴリズムは、集団ベースのグローバル検索と各個体によるヒューリスティックなローカル検索を組み合わせたものである。... ローカル検索を行うメカニズムは、局所最適に到達するか、（客観的なコスト関数に関して）所定のレベルまで改善することである。」そして彼は、「私は MA を遺伝的表現に制限しているわけではない」と強調している。^[9]この MA の本来の定義は、検索サイクルにおける文化的進化の特徴（局所的改良の形で）を包含しているが、普遍的ダーウィニズムによれば、遺伝/ミーム伝達、変異、選択という中核原理がすべて欠落しているため、真の進化システムとは言えないかもしれない。これは、MA という用語が最初に導入されたときに研究者の間で批判と論争を巻き起こした理由を示唆している。^[2]次の擬似コードは、MA のこの一般的な定義に対応する。

疑似コード

   手順ミームアルゴリズム
   初期化:初期集団を生成し、個体を評価して、それらに品質値を割り当てます。
   停止条件が満たされていない場合は、確率的検索演算子を使用して新しい集団を進化させます。
       集団内
       のすべての個体を
       評価して、それらに品質値を割り当てます。個体改善手順を実行する必要がある個体のサブセットを選択します。
       の各個体に対して、頻度または確率が、強度が のミームを使用して個体学習を実行します。ラマルク学習またはボールドウィン学習に
       進みます。終了終了 その間${\displaystyle \Omega_{il}}$${\displaystyle \Omega_{il}}$ 
           ${\displaystyle f_{il}}$${\displaystyle t_{il}}$
           
   

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

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

疑似コード

   EA
   初期化に基づく Memetic アルゴリズムの 手順: ; // 生成カウンターの初期化${\displaystyle t=0}$
                   初期集団をランダムに生成します。${\displaystyle P(t)}$
                   適応度を計算します。
   停止条件が満たされていない場合は、選択:  に従って のサブセットを選択し、 に保存します。子孫:個体を再結合して突然変異させ、 に保存します。学習:ローカル検索またはヒューリスティックによって改善します。
       評価:適応度を計算します。ラマルク学習の場合は、の染色体を改善に従って更新します。fi新世代:およびからいくつかの個体を選択して生成します。 ; ; //世代カウンターを増分します
   。end while結果として
最良の個体を返します。${\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)}$
       
        ${\displaystyle P(t+1)}$${\displaystyle P(t)}$${\displaystyle M'(t)}$
       ${\displaystyle t=t+1}$
   ${\displaystyle p\in P(t-1)}$

この MA スキームにはいくつかの代替手段があります。たとえば、次のとおりです。

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

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

共進化^[17]と自己生成MA ^[18]は、基本的な進化システムの定義を満たす3つの原則すべてが考慮された第3世代MAと見なすことができます。使用されるミームが事前にわかっていると想定する第2世代MAとは対照的に、第3世代MAはルールベースのローカルサーチを利用して進化システム内の候補ソリューションを補完し、問題空間内で定期的に繰り返される特徴やパターンを捉えます。

使用される学習方法/ミームによって改善結果に大きな影響があるため、特定の最適化問題にどのミームを使用するかは慎重に決定する必要があります。^{[12] [16] [19]}個体学習の頻度と強度は、与えられた固定された限られた計算予算に対する MA 検索における個体学習 (活用) に対する進化 (探索) の度合いを直接定義します。明らかに、個体学習が強度が高いほど局所最適値への収束の可能性が高くなりますが、過度の計算リソースを消費することなく費やせる進化の量は制限されます。したがって、これらの 2 つのパラメータを設定する際には、最大の検索パフォーマンスを達成するために利用できる計算予算のバランスを取るように注意する必要があります。個体集団の一部だけが学習する場合、MA 検索の効用を最大化するには、どの個体のサブセットを改善するかという問題を考慮する必要があります。最後に、それぞれの個体を学習の成功によって変更するかどうか (ラマルク学習) を決定する必要があります。したがって、次の5つの設計上の質問^{[15] [19] [20]に答える必要があり、最初の質問はMA実行中に上記の第2世代の代表者全員によって対処されるが、 [15]}のメタラマルク学習の拡張形式では、これを最初の4つの設計上の決定に拡張する。

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

一方、組み合わせ最適化では、個々の学習方法は、特定の関心のある問題に合わせて調整されたヒューリスティック (決定論的または確率的) の形で一般的に存在します。一般的なヒューリスティック手順とスキームには、k 遺伝子交換、エッジ交換、最初の改善などがあります。

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

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

個別学習の強度は、個別学習の反復に割り当てられる計算予算の量、つまり、単一のソリューションを改善するために個別学習に費やすことができる最大の計算予算です。 ${\displaystyle t_{il}}$

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

ミームアルゴリズムは、現実世界のさまざまな問題にうまく適用されてきました。ミームアルゴリズムに密接に関連する技術を採用する人は多くいますが、ハイブリッド遺伝的アルゴリズムなどの別名も使用されています。

研究者は、多くの古典的なNP問題に取り組むためにミーム アルゴリズムを使用しています。そのいくつかを挙げると、グラフ分割、多次元ナップザック、巡回セールスマン問題、二次割り当て問題、集合被覆問題、最小グラフ彩色、最大独立集合問題、ビン パッキング問題、一般化割り当て問題などです。

最近の応用としては、ビジネス分析とデータサイエンス、^[3]人工ニューラルネットワークのトレーニング、^[29] パターン認識、^[30]ロボットの動作計画、^[31] ビーム方向付け、^[32] 回路設計、^[33]電力サービスの復旧、^[34]医療エキスパートシステム、^[35] 単一マシンのスケジューリング、^[36]自動タイムテーブル作成（特にNHLのタイムテーブル）、^[37] 人員スケジューリング、^[38] 看護師勤務表の最適化、^[39]プロセッサ割り当て、^[40]保守スケジューリング（たとえば、配電網の保守）、^[41] 制約のある異種リソースへの複数のワークフローのスケジューリング、 ^[42]多次元ナップサック問題、^[43] VLSI設計、^[44]遺伝子発現プロファイルのクラスタリング、^[45]特徴/遺伝子の選択、^{[46] [47]}ハードウェア障害注入のパラメータ決定、^[48]およびマルチクラスなどがあります。多目的特徴選択[ ^{49] [50]}

• IEEE ミームアルゴリズムワークショップ (WOMA 2009)。プログラム委員長: Jim Smith、英国ウェスト オブ イングランド大学、Yew-Soon Ong、シンガポール南洋理工大学、Gustafson Steven、英国ノッティンガム大学、Meng Hiot Lim、シンガポール南洋理工大学、Natalio Krasnogor、英国ノッティンガム大学
• Memetic Computing Journal の創刊号は 2009 年 1 月に発行されました。
• 2008 IEEE 世界計算知能会議 (WCCI 2008)、香港、ミームアルゴリズムに関する特別セッション。
• 「ソフトコンピューティングの新たなトレンド - ミームアルゴリズム」特別号、Wayback Machineに 2011-09-27 にアーカイブ、Soft Computing Journal、完了 & 印刷中、2008 年。
• IEEE 計算知能学会 ミームコンピューティングに関する新興技術タスクフォース 2011-09-27ウェイバックマシンにアーカイブ
• IEEE 進化計算会議 (CEC 2007)、シンガポール、ミームアルゴリズムに関する特別セッション。
• トムソンサイエンティフィックのエッセンシャルサイエンス指標による「ミームコンピューティング」は、新たな最前線の研究領域として位置づけられています。
• ミームアルゴリズム特集号、IEEE Transactions on Systems, Man, and Cyber​​netics - Part B: Cyber​​netics、第37巻第1号、2007年2月。
• ミームアルゴリズムの最近の進歩、シリーズ：ファジーとソフトコンピューティングの研究、第166巻、ISBN  978-3-540-22904-9、2005年。
• ミームアルゴリズム特集号、進化計算2004年秋、第12巻第3号：v-vi。