Выбор турнира - Tournament selection

Выбор турнира это метод выбора индивидуума из популяции особей в генетический алгоритм.[1] Выбор турнира включает проведение нескольких «турниров» среди нескольких человек (или «хромосомы ") выбирается случайным образом из совокупности. Победитель каждого турнира (тот, кто лучше всех подходит) выбирается для кроссовер. Давление отбора, вероятностная мера вероятности участия хромосомы в турнире, основанная на размере пула выбора участников, легко корректируется путем изменения размера турнира, причина в том, что если размер турнира больше, у слабых людей меньше шансов быть выбранными. потому что, если для участия в турнире выбран слабый человек, существует более высокая вероятность того, что более сильный человек также будет участвовать в этом турнире.

Метод выбора турнира может быть описан псевдокодом:

случайным образом выбрать k (размер турнира) человек из популяции; выбрать лучшего человека из турнира с вероятностью p; выбрать второго лучшего человека с вероятностью p * (1-p); выбрать третьего лучшего человека с вероятностью p * ((1-p) ^ 2) и так далее

Детерминированный отбор турнира выбирает лучшего участника (когда п = 1) в любом турнире. Односторонний турнир (k = 1) выбор эквивалентен случайному выбору. Возможны два варианта выбора: с участием и без замена. Вариант без замены гарантирует, что при выборе N человек из популяции N элементы, каждый человек участвует ровно k турниры. Алгоритм предложен в [2]. Обратите внимание, что в зависимости от количества выбранных элементов выбор без замена делает не гарантия того, что ни один человек не будет выбран более одного раза. Это просто гарантирует, что у каждого человека будут равные шансы принять участие в одинаковом количестве турниров.

По сравнению с (стохастическим) фитнес пропорциональный отбор На практике выбор турнира часто реализуется из-за отсутствия стохастического шума.[3]

Турнирный отбор имеет несколько преимуществ перед альтернативными методами отбора для генетических алгоритмов (например, фитнес пропорциональный отбор и отбор на основе вознаграждения ): кодирование эффективно, работает с параллельными архитектурами и позволяет легко регулировать давление выбора.[1] Также было показано, что отбор турнира не зависит от масштабирования генетического алгоритма. фитнес-функция (или 'целевая функция ') в некоторых системах классификаторов.[4][5]

Смотрите также

использованная литература

  1. ^ а б Миллер, Брэд; Голдберг, Дэвид (1995). «Генетические алгоритмы, турнирный отбор и влияние шума» (PDF). Сложные системы. 9: 193–212. S2CID  6491320.
  2. ^ Голдберг, Дэвид Э .; Корб, Брэдли; Деб, Калянмой (1989). «Беспорядочные генетические алгоритмы: мотивация, анализ и первые результаты» (PDF). Сложные системы. 3 (5): 493–530.
  3. ^ Бликл, Тобиас; Тиле, Лотар (декабрь 1996 г.). «Сравнение схем выбора, используемых в эволюционных алгоритмах». Эволюционные вычисления. 4 (4): 361–394. CiteSeerX  10.1.1.15.9584. Дои:10.1162 / evco.1996.4.4.361. S2CID  42718510.
  4. ^ Миллера, под редакцией Эрика Кант-Паса, Джеймса А. Фостера, Кальянмоя Деб, Лоуренса Дэвида Дэвиса, Раджкумара Роя, Уна-Мэй О.Рейли, Ганса-Георга Бейера, Рассела Стэндиша, Грэма Кендалла, Стюарта Уилсона, Марка Хармана, Иоахима Вегенера, Дипанкара Дасгупта, Митч А. Поттер, Алан К. Шульц, Кэтрин А. Доусленд, Наташа Йоноска, Джулиан (2003). Генетические и эволюционные вычисления GECCO 2003 00 Конференция по генетическим и эволюционным вычислениям Чикаго, штат Иллинойс, США, июль 1216, 2003 Труды, часть II. Берлин: Springer-Verlag Berlin Heidelberg. ISBN  978-3-540-45110-5.CS1 maint: дополнительный текст: список авторов (ссылка на сайт)
  5. ^ Гольдберг, Дэвид; Деб, Калянмой (1991). «Сравнительный анализ схем отбора, используемых в генетических алгоритмах» (PDF). Основы генетических алгоритмов. 1: 69–93. Дои:10.1016 / b978-0-08-050684-5.50008-2. ISBN  9780080506845. S2CID  938257.