トーナメント選択は、進化アルゴリズムにおいて個体の集団から個体を選択する方法である。[1] [2]トーナメント選択では、集団からランダムに選ばれた少数の個体（または「染色体」）の間で複数の「トーナメント」を実行する。各トーナメントの勝者（最も適応度の高い個体）が交差のために選択される。 選択圧は、参加者選択プールのサイズに基づいた、トーナメントへの染色体参加の可能性の確率的尺度であり、トーナメントサイズを変更することで簡単に調整できる。その理由は、トーナメントサイズが大きいほど、弱い個体が選択される機会が少なくなるためである。なぜなら、弱い個体がトーナメントに参加するように選択されると、より強い個体もそのトーナメントに参加する可能性が高くなるからである。
疑似コード
トーナメント選択方法は擬似コードで記述できます。
集団からk（トーナメントサイズ）の個体をランダムに選択する トーナメントから確率pで最優秀の個体を選択する 確率p*(1-p)で2番目に良い個体を選択する 確率p*((1-p)^2)で3番目に良い個体を選択する 等々
変種
決定論的なトーナメント選択では、どのトーナメントでも 最良の個体 ( p = 1 の場合) を選択します。
一方向トーナメント（k = 1）選択はランダム選択と同等です。
選択には、置換ありと置換なしの2つのバリエーションがあります。置換なしのバリエーションでは、N個の要素からなる集団からN個の個体を選択する際に、各個体が正確にk回のトーナメントに参加することが保証されます。アルゴリズムは[3]で提案されています。選択する要素の数によっては、置換なしの選択では、どの個体も複数回選択されることが保証されないことに注意してください。これは、各個体が同じ数のトーナメントに参加する機会が均等であることを保証するだけです。
利点
（確率的）適応度比例選択法と比較すると、トーナメント選択は確率的ノイズが少ないため、実際にはよく実施される。[4]
トーナメント選択は、遺伝的アルゴリズムの他の選択方法（例えば、適応度比例選択や報酬ベースの選択）に比べていくつかの利点がある。コーディングが効率的で、並列アーキテクチャ上で動作し、選択圧を容易に調整できる。[2]また、トーナメント選択は、いくつかの分類システムにおいて、遺伝的アルゴリズムの適応度関数（または「目的関数」） のスケーリングとは独立していることが示されている。[5] [6]
参考文献
- ^ ZHANG, Byoung-Tak; KIM, Jung-Jib (2000). 「進化的最適化における選択手法の比較」.進化的最適化.
- ^ ab Miller, Brad; Goldberg, David (1995). 「遺伝的アルゴリズム、トーナメント選択、そしてノイズの影響」(PDF) . Complex Systems . 9 : 193–212 . S2CID 6491320. 2019年8月31日時点のオリジナル(PDF)からアーカイブ。
- ^ Goldberg, David E.; Korb, Bradley; Deb, Kalyanmoy (1989). 「メッシー遺伝的アルゴリズム：動機、分析、そして最初の結果」(PDF) . Complex Systems . 3 (5): 493– 530.
- ^ Blickle, Tobias; Thiele, Lothar (1996年12月). 「進化アルゴリズムで使用される選択スキームの比較」.進化計算. 4 (4): 361– 394. CiteSeerX 10.1.1.15.9584 . doi :10.1162/evco.1996.4.4.361. S2CID 42718510.
- ^ Cantú-Paz, Erick編 (2003).遺伝的・進化的計算 -- GECCO 2003 : Genetic and Evolutionary Computation Conference Chicago, IL, USA, July 12-16, 2003 Proceedings, Part II . ベルリン、ハイデルベルク: Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-45110-5。
- ^ ゴールドバーグ、デイビッド、デブ、カリヤンモイ (1991). 「遺伝的アルゴリズムにおける選択スキームの比較分析」(PDF) .遺伝的アルゴリズムの基礎. 1 : 69–93 . doi :10.1016/b978-0-08-050684-5.50008-2. ISBN 9780080506845. S2CID 938257. 2018年7月17日時点のオリジナル（PDF）からアーカイブ。
