Генетическое программирование: разница между ранком рулетки и выбором турнира

Question

Я читаю слайд о генетическом программировании. На этом слайде сказано, что на этапе выбора есть несколько методов, таких как Roulette, Rank или же Tournament без каких-либо объяснений. Я пробовал Google, но нигде не говорится четко об этих условиях.

Пожалуйста, скажите мне, в чем разница между ними.

Answer 1

Выбор колеса рулетки (aka Fitness пропорциональный выбор)

Пригодность используется, чтобы связать вероятность выбора с каждым человеком.

Если f_i - приспособленность индивидуума i в популяции, вероятность его выбора:

p_i = f_i / Σ _j(f_j) для j = 1 … N (N - количество особей в популяции)

Он называется колесом рулетки, потому что в казино его можно рассматривать как колесо рулетки:

Это может быть смоделировано следующим (наивным) алгоритмом:

1. Рассчитать сумму всех численности населения в популяции (сумма S).
2. Генерация случайного числа r в интервале [0; S].
3. Пройди по населению и суммируйся. Когда сумма s больше чем r, остановитесь и верните человека, где вы находитесь.

Для возможных реализаций смотрите:

• Алгоритм выбора колеса рулетки
• Выбор рулетки в генетических алгоритмах

---

Выбор ранга аналогичен выбору колеса рулетки, за исключением того, что вероятность выбора пропорциональна относительной пригодности, а не абсолютной пригодности.

Не имеет значения, подходит ли наиболее подходящий кандидат в десять раз лучше, чем следующий, или 0,001%. В обоих случаях вероятности выбора будут одинаковыми.

Все, что имеет значение, это ранжирование по отношению к другим лицам.

Выбор ранга легко осуществить, если вы уже знаете, как выбрать колесо рулетки. Вместо того, чтобы использовать пригодность в качестве вероятности для выбора, вы используете ранг. Таким образом, для совокупности из N решений наилучшее решение получает ранг N, второе наилучшее ранг N-1 и т. Д. У худшего человека ранг 1.

( Ранжирование выбора в коде генетического алгоритма)

---

Выбор турнира

1. Выберите несколько человек наугад из населения (турнир).
2. Человек с лучшим фитнесом (победитель) выбирается для кроссовера.

Как вы можете видеть, это эффективно для кода. Он также работает на параллельных архитектурах и позволяет легко регулировать давление выбора (изменение количества участников в турнире).

Конечно, есть много вариантов этих алгоритмов.

Для сравнения вы можете прочитать:

Сравнение эффективности между различными стратегиями отбора на простых генетических алгоритмах (Jinghui Zhong, Xiaomin Hu, Min Gu, Jun Zhang - 2005)