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

Метод отбора в генетических алгоритмах

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

Псевдокод

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

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

Варианты

Детерминированный турнирный отбор выбирает лучшего участника (при p = 1) в любом турнире.

Выбор в одностороннем турнире ( k = 1) эквивалентен случайному выбору.

Существует два варианта выбора: с заменой и без замены. Вариант без замены гарантирует, что при выборе N особей из популяции из N элементов каждая особь участвует ровно в k турнирах. Алгоритм предложен в. ^[3] Обратите внимание, что в зависимости от количества выбранных элементов выбор без замены не гарантирует, что ни одна особь не будет выбрана более одного раза. Он просто гарантирует, что каждая особь имеет равные шансы участвовать в одинаковом количестве турниров.

Преимущества

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

Турнирный отбор имеет несколько преимуществ по сравнению с альтернативными методами отбора для генетических алгоритмов (например, пропорциональный отбор по приспособленности и отбор на основе вознаграждения ): он эффективен для кодирования, работает на параллельных архитектурах и позволяет легко регулировать давление отбора. ^[2] Также было показано, что турнирный отбор не зависит от масштабирования функции приспособленности генетического алгоритма (или « целевой функции ») в некоторых системах классификаторов. ^[5]^[6]

Ссылки

^ ЧЖАН, Бён-Так; КИМ, Чон-Джиб (2000). «Сравнение методов отбора для эволюционной оптимизации». Эволюционная оптимизация. Международный журнал в Интернете .
^ ab Миллер, Брэд; Голдберг, Дэвид (1995). «Генетические алгоритмы, отбор турниров и эффекты шума» (PDF) . Complex Systems . 9 : 193–212 . S2CID 6491320. Архивировано из оригинала (PDF) 2019-08-31.
^ Голдберг, Дэвид Э.; Корб, Брэдли; Деб, Кальянмой (1989). «Беспорядочные генетические алгоритмы: мотивация, анализ и первые результаты» (PDF) . Сложные системы . 3 (5): 493–530 .
^ Blickle, Tobias; Thiele, Lothar (декабрь 1996 г.). «Сравнение схем выбора, используемых в эволюционных алгоритмах». Evolutionary Computation . 4 (4): 361– 394. CiteSeerX 10.1.1.15.9584 . doi :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 . doi :10.1016/b978-0-08-050684-5.50008-2. ISBN 9780080506845. S2CID 938257. Архивировано из оригинала (PDF) 17 июля 2018 г.

[1] ЧЖАН, Бён-Так; КИМ, Чон-Джиб (2000). «Сравнение методов отбора для эволюционной оптимизации». Эволюционная оптимизация. Международный журнал в Интернете .

[miller-goldberg-2] Миллер, Брэд; Голдберг, Дэвид (1995). «Генетические алгоритмы, отбор турниров и эффекты шума» (PDF) . Complex Systems . 9 : 193–212 . S2CID 6491320. Архивировано из оригинала (PDF) 2019-08-31.

[3] Голдберг, Дэвид Э.; Корб, Брэдли; Деб, Кальянмой (1989). «Беспорядочные генетические алгоритмы: мотивация, анализ и первые результаты» (PDF) . Сложные системы . 3 (5): 493–530 .

[4] Blickle, Tobias; Thiele, Lothar (декабрь 1996 г.). «Сравнение схем выбора, используемых в эволюционных алгоритмах». Evolutionary Computation . 4 (4): 361– 394. CiteSeerX 10.1.1.15.9584 . doi :10.1162/evco.1996.4.4.361. S2CID 42718510.

[5] Канту-Пас, Эрик, ред. (2003). Генетические и эволюционные вычисления -- GECCO 2003 : Конференция по генетическим и эволюционным вычислениям Чикаго, Иллинойс, США, 12-16 июля 2003 г. Труды, часть II . Берлин, Гейдельберг: Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-45110-5.

[6] Голдберг, Дэвид; Деб, Кальянмой (1991). "Сравнительный анализ схем отбора, используемых в генетических алгоритмах" (PDF) . Основы генетических алгоритмов . 1 : 69–93 . doi :10.1016/b978-0-08-050684-5.50008-2. ISBN 9780080506845. S2CID 938257. Архивировано из оригинала (PDF) 17 июля 2018 г.