Отбор (генетический алгоритм)

Отбор — это этап генетического алгоритма или более общего эволюционного алгоритма , в котором отдельные геномы выбираются из популяции для последующего разведения (например, с помощью оператора скрещивания ). Механизмы отбора также используются для выбора решений-кандидатов (индивидуалов) для следующего поколения. Сохранение лучших особей поколения неизменными в следующем поколении называется элитизмом или элитарным отбором . Это удачный (незначительный) вариант общего процесса построения новой популяции.

Процедура отбора для разведения, использованная на ранних этапах ^[1] может быть реализовано следующим образом:

Вычисленные значения приспособленности ( функция приспособленности ) нормализуются так, что сумма всех полученных значений приспособленности равна 1.
Вычисляются накопленные нормализованные значения приспособленности: накопленное значение приспособленности индивидуума представляет собой сумму его собственного значения приспособленности плюс значений приспособленности всех предыдущих особей; накопленная приспособленность последнего индивидуума должна быть равна 1, иначе на этапе нормализации что-то пошло не так.
случайное число R от 0 до 1. Выбирается
чье накопленное нормализованное значение больше или равно R. Выбранный индивидуум является первым ,

Для многих задач приведенный выше алгоритм может потребовать больших вычислительных ресурсов. Более простая и быстрая альтернатива использует так называемое стохастическое принятие.

Если эта процедура повторяется до тех пор, пока не будет выбрано достаточное количество особей, этот метод отбора называется пропорциональным отбором по приспособленности или отбором в рулетке . Если вместо одного указателя, вращающегося несколько раз, на колесе, которое вращается один раз, имеется несколько указателей, находящихся на равном расстоянии друг от друга, это называется стохастической универсальной выборкой .Многократный выбор лучшего человека из случайно выбранной подгруппы — это турнирный отбор . Отбор лучшей половины, трети или другой части особей — это усеченный отбор .

Существуют и другие алгоритмы отбора, которые рассматривают для отбора не всех особей, а только тех, значение приспособленности которых превышает заданную (произвольную) константу. Другие алгоритмы выбирают из ограниченного пула, куда допускается только определенный процент людей, в зависимости от значения пригодности.

Методы отбора (эволюционный алгоритм)

Перечисленные методы различаются главным образом давлением отбора, ^[2]^[3] который можно установить с помощью параметра стратегии при выборе ранга, описанного ниже. Чем выше давление отбора, тем быстрее популяция сходится к определенному решению, и пространство поиска может быть недостаточно исследовано. Дополнительные методы выбора и дополнительную информацию см. ^[4]^[5]

Выбор колеса рулетки

При выборе колеса рулетки вероятность выбора особи для разведения следующего поколения пропорциональна ее приспособленности: чем лучше приспособленность, тем выше вероятность того, что эта особь будет выбрана.Выбор индивидуумов можно изобразить как вращение рулетки, в которой столько карманов, сколько индивидуумов в текущем поколении, причем размеры зависят от вероятности их появления.Вероятность выбора индивидуального $i$ равно $p_{i}={\frac {f_{i}}{\Sigma _{j=1}^{N}f_{j}}}$ , где $f_{i}$ это фитнес $i$ и $N$ — размер текущего поколения (обратите внимание, что в этом методе одну особь можно нарисовать несколько раз).

Выбор ранга

При ранговом отборе вероятность выбора зависит не напрямую от приспособленности, а от ранга приспособленности особи в популяции. Это позволяет увидеть большие различия в физической подготовке; при этом не обязательно должны быть известны сами точные значения приспособленности, а лишь сортировка особей по качеству.

Линейное ранжирование, восходящее к Бейкеру, ^[6]^[7] часто используется. Это позволяет устанавливать давление выбора с помощью параметра $sp$ , который может принимать значения от 1,0 (нет давления отбора) до 2,0 (высокое давление отбора). Вероятность $P$ на ранговые должности $R_{i}$ получается следующим образом:

P(R_{i})={\frac {1}{n}}{\Bigl (}sp-(2sp-2){\frac {i-1}{n-1}}{\Bigr )}\quad \quad 1\leq i\leq n,\quad 1\leq sp\leq 2\quad {\mathsf {with}}\quad P(R_{i})\geq 0,\quad \sum _{i=1}^{n}P(R_{i})=1

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

Выбор устойчивого состояния

В каждом поколении отбирается несколько хромосом (хороших — с высокой приспособленностью) для создания нового потомства. Затем некоторые (плохие – с низкой приспособленностью) хромосомы удаляются и на их место помещается новое потомство. Остальная часть населения доживает до нового поколения.

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

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

Элитарный отбор

Часто для получения лучших результатов используются стратегии с частичным воспроизводством. Один из них — элитизм, при котором небольшая часть лучших особей прошлого поколения переносится (без каких-либо изменений) в следующее поколение.

Выбор Больцмана

При выборе Больцмана постоянно меняющаяся температура контролирует скорость отбора в соответствии с заранее заданным графиком. Изначально температура высокая, а это означает, что давление отбора низкое. Температура постепенно снижается, что постепенно увеличивает давление отбора, тем самым позволяя ГА сузиться ближе к лучшей части пространства поиска, сохраняя при этом соответствующую степень разнообразия. ^[9]

См. также

Ссылки

^ Холланд, Джон Х. (1992). Адаптация в естественных и искусственных системах . Докторская диссертация, Мичиганский университет, 1975. Кембридж, Массачусетс: MIT Press. ISBN 0-585-03844-9 . OCLC 42854623 .
^ Бэк, Т. (1994). «Селективное давление в эволюционных алгоритмах: характеристика механизмов отбора» . Материалы первой конференции IEEE по эволюционным вычислениям. Всемирный конгресс IEEE по вычислительному интеллекту . Орландо, Флорида, США: IEEE. стр. 57–62. дои : 10.1109/ICEC.1994.350042 . ISBN 978-0-7803-1899-1 . S2CID 195867383 .
^ Голдберг, Дэвид Э.; Деб, Калянмой (1991), «Сравнительный анализ схем отбора, используемых в генетических алгоритмах» , «Основы генетических алгоритмов », том. 1, Elsevier, стр. 69–93, CiteSeerX 10.1.1.101.9494 , doi : 10.1016/b978-0-08-050684-5.50008-2 , ISBN. 978-0-08-050684-5 , S2CID 938257 , получено 9 января 2023 г.
^ Эйбен, А.Е.; Смит, Дж. Э. (2015). «Фитнесс, отбор и управление популяцией». Введение в эволюционные вычисления . Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 79–98. дои : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1 . S2CID 20912932 .
^ Де Йонг, Кеннет А. (2006). Эволюционные вычисления: единый подход . Кембридж, Массачусетс: MIT Press. ISBN 978-0-262-25598-1 . OCLC 69652176 .
^ Бейкер, Джеймс Э. (1985), Грефенстетт, Джон Дж. (редактор), «Методы адаптивного отбора для генетических алгоритмов», Conf. Учеб. 1-го Межд. Конф. «Генетические алгоритмы и их приложения» (ICGA) , Хиллсдейл, Нью-Йорк. Джерси: L. Erlbaum Associates, стр. 101–111, ISBN. 0-8058-0426-9
^ Бейкер, Джеймс Э. (1987), Грефенстетт, Джон Дж. (редактор), «Уменьшение систематической ошибки и неэффективности алгоритма выбора», Conf. Учеб. 2-го Межд. Конф. «Генетические алгоритмы и их приложения» (ICGA) , Хиллсдейл, Нью-Йорк. Джерси: L. Erlbaum Associates, стр. 14–21, ISBN. 0-8058-0158-8
^ Уитли, Даррелл (1989), Шаффер, Дж. Д. (редактор), «Алгоритм GENITOR и давление отбора: почему ранговое распределение репродуктивных испытаний является лучшим», Труды Третьей Международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско , Калифорния, США: Morgan Kaufmann Publishers Inc., стр. 116–121, ISBN. 978-1-55860-066-9
^ Шиванандам, С.Н. (2013). Принципы мягких вычислений . Дипа, С.Н. Нью-Дели: Wiley. ISBN 978-1-118-54680-2 . OCLC 891566849 .

Внешние ссылки

[1] Холланд, Джон Х. (1992). Адаптация в естественных и искусственных системах . Докторская диссертация, Мичиганский университет, 1975. Кембридж, Массачусетс: MIT Press. ISBN 0-585-03844-9 . OCLC 42854623 .

[2] Бэк, Т. (1994). «Селективное давление в эволюционных алгоритмах: характеристика механизмов отбора» . Материалы первой конференции IEEE по эволюционным вычислениям. Всемирный конгресс IEEE по вычислительному интеллекту . Орландо, Флорида, США: IEEE. стр. 57–62. дои : 10.1109/ICEC.1994.350042 . ISBN 978-0-7803-1899-1 . S2CID 195867383 .

[3] Голдберг, Дэвид Э.; Деб, Калянмой (1991), «Сравнительный анализ схем отбора, используемых в генетических алгоритмах» , «Основы генетических алгоритмов », том. 1, Elsevier, стр. 69–93, CiteSeerX 10.1.1.101.9494 , doi : 10.1016/b978-0-08-050684-5.50008-2 , ISBN. 978-0-08-050684-5 , S2CID 938257 , получено 9 января 2023 г.

[4] Эйбен, А.Е.; Смит, Дж. Э. (2015). «Фитнесс, отбор и управление популяцией». Введение в эволюционные вычисления . Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 79–98. дои : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1 . S2CID 20912932 .

[5] Де Йонг, Кеннет А. (2006). Эволюционные вычисления: единый подход . Кембридж, Массачусетс: MIT Press. ISBN 978-0-262-25598-1 . OCLC 69652176 .

[6] Бейкер, Джеймс Э. (1985), Грефенстетт, Джон Дж. (редактор), «Методы адаптивного отбора для генетических алгоритмов», Conf. Учеб. 1-го Межд. Конф. «Генетические алгоритмы и их приложения» (ICGA) , Хиллсдейл, Нью-Йорк. Джерси: L. Erlbaum Associates, стр. 101–111, ISBN. 0-8058-0426-9

[7] Бейкер, Джеймс Э. (1987), Грефенстетт, Джон Дж. (редактор), «Уменьшение систематической ошибки и неэффективности алгоритма выбора», Conf. Учеб. 2-го Межд. Конф. «Генетические алгоритмы и их приложения» (ICGA) , Хиллсдейл, Нью-Йорк. Джерси: L. Erlbaum Associates, стр. 14–21, ISBN. 0-8058-0158-8

[8] Уитли, Даррелл (1989), Шаффер, Дж. Д. (редактор), «Алгоритм GENITOR и давление отбора: почему ранговое распределение репродуктивных испытаний является лучшим», Труды Третьей Международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско , Калифорния, США: Morgan Kaufmann Publishers Inc., стр. 116–121, ISBN. 978-1-55860-066-9

[9] Шиванандам, С.Н. (2013). Принципы мягких вычислений . Дипа, С.Н. Нью-Дели: Wiley. ISBN 978-1-118-54680-2 . OCLC 891566849 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v т и Эволюционные вычисления
Основные темы	Эволюционный алгоритм Эволюционный анализ данных Эволюционная мультимодальная оптимизация Человеческие эволюционные вычисления Интерактивные эволюционные вычисления
Алгоритмы	Алгоритм клеточной эволюции Стратегия эволюции адаптации ковариационной матрицы (CMA-ES) Культурный алгоритм Дифференциальная эволюция Эволюционное программирование Генетический алгоритм Генетическое программирование Программирование экспрессии генов Стратегия эволюции Стратегия естественной эволюции Нейроэволюция Система классификаторов обучения
Связанные методы	Роевой интеллект Оптимизация колонии муравьев Алгоритм пчел Поиск кукушки Оптимизация роя частиц Оптимизация бактериальных колоний
Метаэвристические методы	Алгоритм Светлячка Поиск гармонии Гауссова адаптация Меметический алгоритм
Связанные темы	Искусственное развитие Искусственный интеллект Искусственная жизнь Цифровой организм Эволюционная робототехника Фитнес-функция Фитнес-ландшафт Приближение фитнеса Генетические операторы Интерактивные эволюционные вычисления Никаких бесплатных обедов в поиске и оптимизации Машинное обучение Брачный пул Синтез программы
Журналы	Эволюционные вычисления (журнал)