Выбор турнира
Турнирный отбор — это метод отбора особи из популяции особей с помощью генетического алгоритма . [1] Отбор турниров предполагает проведение нескольких «турниров» среди нескольких людей (или « хромосом »), выбранных случайным образом из популяции. Победитель каждого турнира (тот, кто обладает лучшей физической подготовкой) выбирается для кроссовера . Давление отбора — вероятностная мера вероятности участия хромосомы в турнире, основанная на размере пула отбора участников, — легко корректируется путем изменения размера турнира. Причина в том, что если размер турнира больше, у слабых людей меньше шансов быть выбранными, потому что, если для участия в турнире выбран слабый человек, существует более высокая вероятность того, что более сильный человек также будет участвовать в этом турнире.
Метод выбора турнира можно описать псевдокодом:
choose k (the tournament size) individuals from the population at random choose the best individual from the tournament with probability p choose the second best individual with probability p*(1-p) choose the third best individual with probability p*((1-p)^2) and so on
Детерминированный отбор турниров выбирает лучшего человека (при p = 1) в любом турнире. Выбор в одностороннем турнире ( k = 1) эквивалентен случайному выбору. Возможны два варианта подбора: с заменой и без . Вариант без замены гарантирует, что при выборе N особей из популяции из N элементов каждая особь примет участие ровно в k турнирах. Алгоритм предложен в. [2] Обратите внимание, что в зависимости от количества выбранных элементов выбор без замены не гарантирует, что ни один человек не будет выбран более одного раза. Это просто гарантирует, что каждый человек имеет равные шансы на участие в одинаковом количестве турниров.
По сравнению со (стохастическим) методом пропорционального отбора по фитнесу , турнирный отбор часто реализуется на практике из-за отсутствия стохастического шума. [3]
Турнирный отбор имеет несколько преимуществ по сравнению с альтернативными методами отбора для генетических алгоритмов (например, отбор, пропорциональный пригодности и отбор на основе вознаграждения ): он эффективен в кодировании, работает на параллельных архитектурах и позволяет легко регулировать давление отбора. [1] Также было показано, что выбор турнира не зависит от масштабирования функции приспособленности генетического алгоритма (или « целевой функции ») в некоторых системах классификаторов. [4] [5]
Ссылки
[ редактировать ]- ^ Jump up to: а б Миллер, Брэд; Гольдберг, Дэвид (1995). «Генетические алгоритмы, выбор турниров и эффекты шума» (PDF) . Сложные системы . 9 : 193–212. S2CID 6491320 . Архивировано из оригинала (PDF) 31 августа 2019 г.
- ^ Голдберг, Дэвид Э.; Корб, Брэдли; Деб, Калянмой (1989). «Грязные генетические алгоритмы: мотивация, анализ и первые результаты» (PDF) . Сложные системы . 3 (5): 493–530.
- ^ Бликль, Тобиас; Тиле, Лотар (декабрь 1996 г.). «Сравнение схем отбора, используемых в эволюционных алгоритмах». Эволюционные вычисления . 4 (4): 361–394. CiteSeerX 10.1.1.15.9584 . дои : 10.1162/evco.1996.4.4.361 . S2CID 42718510 .
- ^ Канту-Пас, Эрик, изд. (2003). Генетические и эволюционные вычисления - GECCO 2003: Конференция по генетическим и эволюционным вычислениям Чикаго, Иллинойс, США, 12-16 июля 2003 г. Материалы, Часть II . Берлин, Гейдельберг: Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-45110-5 .
- ^ Гольдберг, Дэвид; Деб, Калянмой (1991). «Сравнительный анализ схем отбора, используемых в генетических алгоритмах» (PDF) . Основы генетических алгоритмов . 1 : 69–93. дои : 10.1016/b978-0-08-050684-5.50008-2 . ISBN 9780080506845 . S2CID 938257 . Архивировано из оригинала (PDF) 17 июля 2018 г.