カッコウ探し
最適化アルゴリズム

オペレーションズリサーチにおいて、カッコウ探索は2009年にXin-She YangとSuash Debによって開発された最適化 アルゴリズムです。[1] [2]これはよく知られている(μ + λ)進化戦略の特殊なケースであることが示されています。[3]これは、一部のカッコウ種が他種の宿主鳥の巣に卵を産むという絶対托卵行動からヒントを得ました。一部の宿主鳥は侵入したカッコウと直接衝突することができます。たとえば、宿主鳥は卵が自分のものではないと発見すると、これらの外来卵を捨てるか、単に巣を放棄して別の場所に新しい巣を作ります。新世界に生息する托卵性のカッコウのTaperaなどの一部のカッコウ種は進化しており、托卵するメスは、選ばれた少数の宿主種の卵の色と模様を模倣することに非常に特化したものになっています。[4]カッコウ探索はこのような繁殖行動を理想化したものであり、さまざまな最適化問題に適用できます。

比喩

カッコウ検索 (CS) では次の表現が使用されます。

巣の中の卵はそれぞれ1つの解を表し、カッコウの卵は新しい解を表します。このアルゴリズムの目的は、新しく、より良い可能性のある解（カッコウ）を使って、巣の中のそれほど良くない解を置き換えることです。最も単純な形では、各巣には1つの卵があります。このアルゴリズムは、各巣に複数の卵があり、それらが複数の解の集合を表すような、より複雑なケースにも拡張できます。

CS は次の 3 つの理想的なルールに基づいています。

  1. カッコウは一度に 1 個の卵を産み、ランダムに選んだ巣にその卵を捨てます。
  2. 高品質の卵を産む最良の巣は次の世代に引き継がれます。
  3. 利用可能な宿主の巣の数は一定であり、カッコウが産んだ卵は確率 で宿主鳥に発見される。この場合、宿主鳥は卵を捨てたり巣を放棄したりして、全く新しい巣を作ることができる。 p 1つの ∈ （ 0 、 1 ） {\displaystyle p_{a}\in (0,1)}

さらに、Yang と Deb は、ランダム ウォーク スタイルの検索は、単純なランダム ウォークよりもLévy フライトによって実行される方がよいことを発見しました。

アルゴリズム

疑似コードは次のように要約できます。 

目的関数:宿主巣 

の初期集団を生成する。 (t<MaxGeneration)または(停止基準)の間
  
    
      
        f
        （
        
          ×
        
        ）
        、
        
        
          ×
        
        ＝
        （
        
          ×
          
            1
          
        
        、
        
          ×
          
            2
          
        
        、
        …
        、
        
          ×
          
            d
          
        
        ）
        ;
        
      
    
    {\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},\dots ,x_{d});\,}
  

  
    
      
        n
      
    
    {\displaystyle n}
  

    カッコウをランダムに 1 羽 (i とします) 取得し、その解をレヴィ飛行を実行して置き換えます。
    品質/適合性を評価する
        [最大化のため、]
  
    
      
        
          F
          
            私
          
        
      
    
    {\displaystyle F_{i}}
  

  
    
      
        
          F
          
            私
          
        
        ∝
        f
        （
        
          
            ×
          
          
            私
          
        
        ）
      
    
    {\displaystyle F_{i}\propto f(\mathbf {x} _{i})}
  

    n 個（例えば、j 個）の中からランダムにネストを選択します。
    もし（）、
  
    
      
        
          F
          
            私
          
        
        >
        
          F
          
            j
          
        
      
    
    {\displaystyle F_{i}>F_{j}}
  

        j を新しい解に置き換えます。
    劣悪な巣の
    一部（ ）が放棄され、新しい巣が作られれば終了。
  
    
      
        
          p
          
            1つの
          
        
      
    
    {\displaystyle p_{a}}
  

    最善の解決策/巣を維持します。
    ソリューション/ネストをランク付けし、現時点での最適なものを見つけます。
    現在の最善のソリューションを次の世代に引き継ぐ。
終了しながら

このアルゴリズムの重要な利点は、そのシンプルさです。実際、粒子群最適化やハーモニーサーチといった他の集団ベースまたはエージェントベースのメタヒューリスティックアルゴリズムと比較すると、CSには本質的に1つのパラメータしかありません（集団サイズを除く）。そのため、実装は非常に容易です。 p 1つの {\displaystyle p_{a}} n {\displaystyle n}

ランダムウォークとステップサイズ

重要な問題は、新しい解を生成するための一般方程式におけるレヴィ飛行とランダムウォークの応用である。

× t + 1 ＝ × t + s E t 、 {\displaystyle \mathbf {x} _{t+1}=\mathbf {x} _{t}+sE_{t},}

ここで、は、ランダム ウォークの場合は平均 0、標準偏差 1 の標準正規分布から取得され、レヴィ飛行の場合はレヴィ分布から取得されます。明らかに、ランダム ウォークはカッコウの卵と宿主の卵の類似性とも関連付けられますが、これは実装が困難になることがあります。ここで、ステップ サイズは、ランダム ウォーカーが固定回数の反復でどこまで移動できるかを決定します。レヴィ ステップ サイズの生成は多くの場合困難であり、3 つのアルゴリズム (Mantegna の[5]を含む) の比較が Leccardi [6]によって実行され、Chambers らのアプローチ[7]の実装が必要な乱数の数が少ないため最も計算効率が高いことがわかりました。 E t {\displaystyle E_{t}} s {\displaystyle s}

sが大きすぎると、生成される新しい解は古い解から大きく離れてしまいます（あるいは境界を越えてしまうこともあります）。そのため、そのような動きは受け入れられる可能性は低くなります。sが小さすぎると、変化が小さすぎて意味をなさないため、そのような探索は効率的ではありません。したがって、探索を可能な限り効率的に維持するには、適切なステップサイズが重要です。

例えば、単純な等方性ランダムウォークの場合、d次元空間で移動する平均距離は r {\displaystyle r}

r 2 ＝ 2 d D t 、 {\displaystyle r^{2}=2dDt,}

ここで、有効拡散係数である。ここで、は各ジャンプにおけるステップサイズまたは移動距離であり、は各ジャンプにかかる時間である。上記の式は[8] D ＝ s 2 / 2 τ {\displaystyle D=s^{2}/2\tau } s {\displaystyle s} τ {\displaystyle \tau}

s 2 ＝ τ r 2 t d 。 {\displaystyle s^{2}={\frac {\tau \;r^{2}}{t\;d}}.}

関心のある次元の典型的な長さスケールLに対して、局所探索は通常、 の領域に限定されます。t=100～1000の場合には、 d=1の場合には 、 d=10の場合にはとなります。したがって、ほとんどの問題ではs/L=0.001～0.01を使用できます。ただし、正確な導出には、レヴィ飛行の挙動の詳細な分析が必要になる場合があります。[9] r ＝ L / 10 {\displaystyle r=L/10} τ ＝ 1 {\displaystyle \tau =1} s ≈ 0.01 L {\displaystyle s\approx 0.01L} s ≈ 0.001 L {\displaystyle s\approx 0.001L}

メタヒューリスティックスに関連する未解決の問題が多数あるため、アルゴリズムと収束解析は有益であろう[10]

理論分析

重要な取り組みとして、CSベースのアルゴリズムの性能を向上させるための理論的な分析が必要である。[11]

  1. CSベースのアルゴリズムの収束に関する理論的分析
  2. 制御パラメータ設定のための十分条件と必要条件を提供する
  3. 非均質な探索規則を採用して古典的なCSアルゴリズムを強化する

改良されたカッコウ探索アルゴリズム

カッコウ探索アルゴリズムの収束性は、放棄された巣を遺伝的に置き換えることで（元の方法のランダムな置き換えではなく）、大幅に改善される。[12]また、最良の（高品質の）巣を追加的に交配させることでアルゴリズムの改良も行われており[13]、このアプローチは様々な産業最適化問題に適用され、成功を収めている。[14] [15]

参考文献

  1. ^ X.-S. Yang; S. Deb (2009年12月).レヴィ飛行によるカッコウ探索. 自然と生物学に着想を得たコンピューティングに関する世界会議 (NaBIC 2009). IEEE出版物. pp.  210– 214. arXiv : 1003.1594v1 .
  2. ^ Inderscience (2010年5月27日). 「カッコウが春をデザインする」. Alphagalileo.org. 2010年6月29日時点のオリジナルよりアーカイブ。 2010年5月27日閲覧。
  3. ^ Camacho Villalón, CL; Stützle, T.; Dorigo, M. (2021年3月). 「カッコウ探索≡(μ+λ)–進化戦略」(PDF) . 2021年7月2日閲覧。 {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  4. ^ RB Payne、MD Sorenson、K. Klitz著『The Cuckoos』オックスフォード大学出版局（2005年）。
  5. ^ RN Mantegna, レヴィ安定確率過程の数値シミュレーションのための高速で正確なアルゴリズム[リンク切れ]、Physical Review E、Vol.49、4677-4683 (1994)。
  6. ^ M. Leccardi、「Levy ノイズ生成のための 3 つのアルゴリズムの比較」、第 5 回 EUROMECH 非線形ダイナミクス会議の議事録 (2005 年)。
  7. ^ Chambers, JM; Mallows, CL; Stuck, BW (1976). 「安定した確率変数をシミュレートする方法」. Journal of the American Statistical Association . 71 (354): 340– 344. doi :10.1080/01621459.1976.10480344.
  8. ^ X.-S. Yang、「自然にインスパイアされたメタヒューリスティックアルゴリズム」、第2版、Luniver Press、(2010)。
  9. ^ M. Gutowski、「グローバル最適化アルゴリズムの基礎となるメカニズムとしてのレヴィフライト」、ArXiv Mathematical Physics e-Prints、6 月、(2001 年)。
  10. ^ XS Yang、「メタヒューリスティック最適化：アルゴリズム分析と未解決の問題」、Experimental Algorithms（SEA2011）、編集者（PM Pardalos および S. Rebennack）、LNCS 6630、pp.21-32（2011）。
  11. ^ Cheung, NJ; Ding, X.; Shen, H. (2016-01-21). 「量子メカニズムに基づく実パラメータ最適化のための非均質カッコウ探索アルゴリズム」. IEEE Transactions on Cyber​​netics . 47 (2): 391– 402. doi :10.1109/TCYB.2016.2517140. PMID  26812745. S2CID  7706150.
  12. ^ de Oliveira, Victoria YM; de Oliveira, Rodrigo MS; Affonso, Carolina M. (2018-07-31). 「放棄された巣の遺伝的置換によるカッコウ探索アプローチの強化と分散型発電ユニットの最適配置への適用」IET Generation, Transmission & Distribution . 12 (13): 3353– 3362. doi : 10.1049/iet-gtd.2017.1992 . ISSN  1751-8687.
  13. ^ Walton, S.; Hassan, O.; Morgan, K.; Brown, MR (2011-09-01). 「修正カッコウ探索：新しい勾配フリー最適化アルゴリズム」 . Chaos, Solitons & Fractals . 44 (9): 710– 718. Bibcode :2011CSF....44..710W. doi :10.1016/j.chaos.2011.06.004. ISSN  0960-0779.
  14. ^ Naumann, DS; Evans, B.; Walton, S.; Hassan, O. (2016-04-01). 「修正カッコウ探索法を用いた計算空気力学的形状最適化の新たな実装」.応用数学モデリング. 40 ( 7–8 ): 4543– 4559. doi : 10.1016/j.apm.2015.11.023 . ISSN  0307-904X.
  15. ^ Zhao, J.; Liu, S.; Zhou, M.; Guo, X.; Qi, L. (2018年7月). 「経済的な電力配分最適化問題を解くための修正カッコウ探索アルゴリズム」. IEEE/CAA Journal of Automatica Sinica . 5 (4): 794– 806. doi :10.1109/JAS.2018.7511138. ISSN  2329-9274. S2CID  46935795.
「https://en.wikipedia.org/w/index.php?title=Cuckoo_search&oldid=1307751229」より取得