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

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

Процедура выбора для разведения, используемой на ранней стадии ^{[ 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 ]} Это может быть особенно полезно в приложениях с ограничениями, поскольку это облегчает преодоление ограничения в нескольких промежуточных этапах, т.е. через последовательность нескольких человек, оцениваемых плохо из -за нарушений ограничений.

Устойчивый отбор состояния

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

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

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

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

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

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

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

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

Ссылки

^ Голландия, Джон Х. (1992). Адаптация в естественных и искусственных системах . Докторская диссертация, Мичиганский университет, 1975. Кембридж, штат Массачусетс: MIT Press. ISBN 0-585-03844-9 Полем OCLC 42854623 .
^ Back, T. (1994). «Селективное давление в эволюционных алгоритмах: характеристика механизмов отбора» . Материалы первой конференции IEEE по эволюционным вычислениям. IEEE Всемирный конгресс по вычислительному интеллекту . Орландо, Флорида, США: IEEE. С. 57–62. doi : 10.1109/icec.1994.350042 . ISBN 978-0-7803-1899-1 Полем S2CID 195867383 .
^ Голдберг, Дэвид Э.; Deb, Kalyanmoy (1991), «Сравнительный анализ схем отбора, используемых в генетических алгоритмах» , Основы генетических алгоритмов , Vol. 1, Elsevier, pp. 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 , получен 2023-01-09
^ Эйбен, аэ; Смит, JE (2015). «Фитнес, отбор и управление населением». Введение в эволюционные вычисления . Серия натуральных вычислений. Берлин, Гейдельберг: Спрингер. С. 79–98. doi : 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), Грефенстетт, Джон Дж. (Ред.), «Методы адаптивного отбора для генетических алгоритмов», конф. Прокурор 1 -го инт. Конфликт О генетических алгоритмах и их приложениях (ICGA) , Хиллсдейл, новый. Джерси: L. Erlbaum Associates, с. 101–111, ISBN 0-8058-0426-9
^ Baker, James E. (1987), Grefenstette, John J. (Ed.), «Снижение смещения и неэффективности в алгоритме отбора», Conf. Прокурор 2 -го инт. Конфликт О генетических алгоритмах и их приложениях (ICGA) , Хиллсдейл, новый. Джерси: L. Erlbaum Associates, с. 14–21, ISBN 0-8058-0158-8
^ Whitley, Darrell (1989), Schaffer, JD (Ed.), «Алгоритм Genitor и давление отбора: почему является лучшим распределением репродуктивных испытаний»,- Материалы Третьей международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско , CA, USA: Morgan Kaufmann Publishers Inc., с. 116–121, ISBN 978-1-55860-066-9
^ Сиванандам, SN (2013). Принципы мягких вычислений . Дипа, SN New Delhi: Wiley. ISBN 978-1-118-54680-2 Полем OCLC 891566849 .

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

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

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

[3] Голдберг, Дэвид Э.; Deb, Kalyanmoy (1991), «Сравнительный анализ схем отбора, используемых в генетических алгоритмах» , Основы генетических алгоритмов , Vol. 1, Elsevier, pp. 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 , получен 2023-01-09

[4] Эйбен, аэ; Смит, JE (2015). «Фитнес, отбор и управление населением». Введение в эволюционные вычисления . Серия натуральных вычислений. Берлин, Гейдельберг: Спрингер. С. 79–98. doi : 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), Грефенстетт, Джон Дж. (Ред.), «Методы адаптивного отбора для генетических алгоритмов», конф. Прокурор 1 -го инт. Конфликт О генетических алгоритмах и их приложениях (ICGA) , Хиллсдейл, новый. Джерси: L. Erlbaum Associates, с. 101–111, ISBN 0-8058-0426-9

[7] Baker, James E. (1987), Grefenstette, John J. (Ed.), «Снижение смещения и неэффективности в алгоритме отбора», Conf. Прокурор 2 -го инт. Конфликт О генетических алгоритмах и их приложениях (ICGA) , Хиллсдейл, новый. Джерси: L. Erlbaum Associates, с. 14–21, ISBN 0-8058-0158-8

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

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

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