Преждевременная конвергенция

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

Стратегии предотвращения преждевременной конвергенции

Стратегии восстановления генетической изменчивости могут быть следующими:

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

Генетическая вариация также может быть восстановлена путем мутации , хотя этот процесс является весьма случайным.

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

Выявление возникновения преждевременной конвергенции

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

Причины преждевременной конвергенции

Существует ряд предполагаемых или предполагаемых причин возникновения преждевременной конвергенции.

Самоадаптивные мутации

Рехенберг ввел идею самоадаптации распределения мутаций в стратегиях эволюции . ^[7] По мнению Рехенберга, параметры управления этими распределениями мутаций развивались внутри организма посредством самоадаптации, а не предопределения. Он назвал это правилом успеха 1/5 эволюционных стратегий (1 + 1)-ES: параметр контроля размера шага будет увеличен в некоторый раз, если относительная частота положительных мутаций в течение определенного периода времени превышает 1/ 5, и наоборот, если оно меньше 1/5. Самоадаптивные мутации вполне могут быть одной из причин преждевременной конвергенции. ^[6] Точное обнаружение оптимумов можно улучшить за счет самоадаптивной мутации, а также ускорить поиск этих оптимумов. Это широко признано, хотя механизмы, лежащие в основе этого процесса, плохо изучены, поскольку часто неясно, обнаруживается ли оптимум локально или глобально. ^[6] Самоадаптивные методы могут вызвать глобальную конвергенцию к глобальному оптимуму при условии, что используемые методы отбора используют элитарность , а также если правило самоадаптации не мешает распределению мутаций, которое обладает свойством обеспечивать положительный минимум. вероятность попадания в случайное подмножество. ^[8] Это для невыпуклых целевых функций с наборами, которые включают ограниченные нижние уровни ненулевых измерений. Исследование Рудольфа предполагает, что механизмы самоадаптации среди стратегий элитарной эволюции действительно напоминают правило успеха 1/5 и вполне могут попасть в ловушку локального оптимума, включающего положительную вероятность. ^[6]

Панмиктические популяции

Большинство ЭА используют неструктурированные или панмиктические популяции, где практически каждая особь в популяции имеет право на выбор партнера на основе приспособленности. ^[9]^[10] Таким образом, генетическая информация лишь немного лучшей особи может распространиться в популяции в течение нескольких поколений, при условии, что за это время не будет произведено другое лучшее потомство. Это может быстро привести к потере генотипического разнообразия и, следовательно, к преждевременной конвергенции, особенно в сравнительно небольших популяциях. ^[1] Хорошо известной контрмерой является переход к альтернативным популяционным моделям , которые вводят в популяцию подструктуры. ^[11]^[12] которые сохраняют генотипическое разнообразие в течение более длительного периода времени и, таким образом, противодействуют тенденции к преждевременной конвергенции. Это было показано для различных советников, таких как генетические алгоритмы, ^[11] стратегия развития, ^[13] другие советники ^[14] или меметические алгоритмы . ^[14]^[15]

Ссылки

^ Jump up to: ^а ^б ^с Люнг, Йи; Гао, Юн; Сюй, Цзун-Бен (1997). «Степень разнообразия населения - взгляд на преждевременную конвергенцию генетических алгоритмов и анализ цепей Маркова» . Транзакции IEEE в нейронных сетях . 8 (5): 1165–1176. дои : 10.1109/72.623217 . ISSN 1045-9227 . ПМИД 18255718 .
^ Jump up to: ^а ^б Бейкер, Джеймс Э. (1985), Грефенстетт, Джон Дж. (редактор), «Методы адаптивного отбора для генетических алгоритмов», Труды Первой международной конференции по генетическим алгоритмам и их приложениям , Хиллсдейл, Нью-Джерси: Л. Эрлбаум, стр. . 101–111, ISBN. 9780805804263
^ Де Йонг, Кеннет А. (1975). Анализ поведения класса генетических адаптивных систем (доктор философии). Анн-Арбор, Мичиган: Мичиганский университет. hdl : 2027.42/4507 .
^ Михалевич, Збигнев (1996). Генетические алгоритмы + структуры данных = программы эволюции, 3-е издание . Берлин, Гейдельберг: Springer-Verlag. п. 58. ИСБН 3-540-60676-9 .
^ Шринивас, М.; Патнаик, LM (апрель 1994 г.). «Адаптивные вероятности скрещивания и мутации в генетических алгоритмах» . Транзакции IEEE по системам, человеку и кибернетике . 24 (4): 656–667. дои : 10.1109/21.286385 .
^ Jump up to: ^а ^б ^с ^д Рудольф, Гюнтер (август 2001 г.). «Самоадаптивные мутации могут привести к преждевременной конвергенции» (PDF) . Транзакции IEEE в эволюционных вычислениях . 5 (4): 410–414. дои : 10.1109/4235.942534 . HDL : 2003/5378 .
^ Рехнерберг, И. (1973). Стратегия эволюции: Оптимизация технических систем в соответствии с принципами биологической эволюции. Фромманн-Хольцбуг Верлаг , Штутгарт.
^ Рудольф, Гюнтер (1999). «Самоадаптация и глобальная конвергенция: контрпример» (PDF) . Материалы Конгресса по эволюционным вычислениям-CEC99 1999 г. (Кат. № 99TH8406) . Вашингтон, округ Колумбия: IEEE. стр. 646–651. дои : 10.1109/CEC.1999.781994 . HDL : 2003/5368 . ISBN 978-0-7803-5536-1 . S2CID 569395 .
^ Гордон, В.С.; Уитли, Д. (1993), Форрест, С. (ред.), «Последовательные и параллельные генетические алгоритмы как оптимизаторы функций» (PDF) , Материалы Пятой международной конференции по генетическим алгоритмам , Сан-Матео, Калифорния: Морган Кауфманн, стр. 177–183
^ Канту-Пас, Эрик (1998). «Обзор параллельных генетических алгоритмов» (PDF) . Калькуляторы Параллели . 10 (2): 141–171.
^ Jump up to: ^а ^б Гордон, В. Скотт; Матиас, Кейт; Уитли, Даррелл (1994). «Клеточные генетические алгоритмы как оптимизаторы функций» . Материалы симпозиума ACM 1994 года по прикладным вычислениям - SAC '94 . Финикс, Аризона, США: ACM Press. стр. 237–241. дои : 10.1145/326619.326732 . ISBN 978-0-89791-647-9 . S2CID 6418773 .
^ Канту-Пас, Эрик (1999). «Эффективные и точные параллельные генетические алгоритмы» (докторская диссертация, Университет Иллинойса, Урбана-Шампейн, США). Генетические алгоритмы и эволюционные вычисления. Том. 1. Спрингер, Нью-Йорк, штат Нью-Йорк. дои : 10.1007/978-1-4615-4369-5 . ISBN 978-1-4613-6964-6 .
^ Горж-Шлейтер, Мартина (1998), Эйбен, Агостон Э.; Назад, Томас; Шенауэр, Марк; Сульфур, Ханс-Пол (ред.), «Сравнительное исследование глобального и локального отбора в стратегиях эволюции» , «Параллельное решение проблем из природы» - PPSN V , Конспект лекций по информатике, том. 1498, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 367–377, doi : 10.1007/bfb0056879 , ISBN 978-3-540-65078-2 , получено 4 декабря 2022 г.
^ Jump up to: ^а ^б Якоб, Вильфрид (01 сентября 2010 г.). «Общая структура адаптации мультимемных алгоритмов, основанная на затратах и выгодах» . Меметические вычисления . 2 (3). п. 207: 201–218. дои : 10.1007/s12293-010-0040-9 . ISSN 1865-9292 . S2CID 167807 .
^ Альба, Энрике; Дорронсоро, Бернабе; Альфонсо, Хьюго (2005). «Клеточные меметические алгоритмы» . Журнал компьютерных наук и технологий . 5 (4): 257–263 . Проверено 4 ноября 2022 г.

См. также

[Leu97-1] Jump up to: ^а ^б ^с Люнг, Йи; Гао, Юн; Сюй, Цзун-Бен (1997). «Степень разнообразия населения - взгляд на преждевременную конвергенцию генетических алгоритмов и анализ цепей Маркова» . Транзакции IEEE в нейронных сетях . 8 (5): 1165–1176. дои : 10.1109/72.623217 . ISSN 1045-9227 . ПМИД 18255718 .

[:1-2] Jump up to: ^а ^б Бейкер, Джеймс Э. (1985), Грефенстетт, Джон Дж. (редактор), «Методы адаптивного отбора для генетических алгоритмов», Труды Первой международной конференции по генетическим алгоритмам и их приложениям , Хиллсдейл, Нью-Джерси: Л. Эрлбаум, стр. . 101–111, ISBN. 9780805804263

[3] Де Йонг, Кеннет А. (1975). Анализ поведения класса генетических адаптивных систем (доктор философии). Анн-Арбор, Мичиган: Мичиганский университет. hdl : 2027.42/4507 .

[zhigl1991-4] Михалевич, Збигнев (1996). Генетические алгоритмы + структуры данных = программы эволюции, 3-е издание . Берлин, Гейдельберг: Springer-Verlag. п. 58. ИСБН 3-540-60676-9 .

[5] Шринивас, М.; Патнаик, LM (апрель 1994 г.). «Адаптивные вероятности скрещивания и мутации в генетических алгоритмах» . Транзакции IEEE по системам, человеку и кибернетике . 24 (4): 656–667. дои : 10.1109/21.286385 .

[:2-6] Jump up to: ^а ^б ^с ^д Рудольф, Гюнтер (август 2001 г.). «Самоадаптивные мутации могут привести к преждевременной конвергенции» (PDF) . Транзакции IEEE в эволюционных вычислениях . 5 (4): 410–414. дои : 10.1109/4235.942534 . HDL : 2003/5378 .

[7] Рехнерберг, И. (1973). Стратегия эволюции: Оптимизация технических систем в соответствии с принципами биологической эволюции. Фромманн-Хольцбуг Верлаг , Штутгарт.

[8] Рудольф, Гюнтер (1999). «Самоадаптация и глобальная конвергенция: контрпример» (PDF) . Материалы Конгресса по эволюционным вычислениям-CEC99 1999 г. (Кат. № 99TH8406) . Вашингтон, округ Колумбия: IEEE. стр. 646–651. дои : 10.1109/CEC.1999.781994 . HDL : 2003/5368 . ISBN 978-0-7803-5536-1 . S2CID 569395 .

[9] Гордон, В.С.; Уитли, Д. (1993), Форрест, С. (ред.), «Последовательные и параллельные генетические алгоритмы как оптимизаторы функций» (PDF) , Материалы Пятой международной конференции по генетическим алгоритмам , Сан-Матео, Калифорния: Морган Кауфманн, стр. 177–183

[10] Канту-Пас, Эрик (1998). «Обзор параллельных генетических алгоритмов» (PDF) . Калькуляторы Параллели . 10 (2): 141–171.

[:0-11] Jump up to: ^а ^б Гордон, В. Скотт; Матиас, Кейт; Уитли, Даррелл (1994). «Клеточные генетические алгоритмы как оптимизаторы функций» . Материалы симпозиума ACM 1994 года по прикладным вычислениям - SAC '94 . Финикс, Аризона, США: ACM Press. стр. 237–241. дои : 10.1145/326619.326732 . ISBN 978-0-89791-647-9 . S2CID 6418773 .

[12] Канту-Пас, Эрик (1999). «Эффективные и точные параллельные генетические алгоритмы» (докторская диссертация, Университет Иллинойса, Урбана-Шампейн, США). Генетические алгоритмы и эволюционные вычисления. Том. 1. Спрингер, Нью-Йорк, штат Нью-Йорк. дои : 10.1007/978-1-4615-4369-5 . ISBN 978-1-4613-6964-6 .

[13] Горж-Шлейтер, Мартина (1998), Эйбен, Агостон Э.; Назад, Томас; Шенауэр, Марк; Сульфур, Ханс-Пол (ред.), «Сравнительное исследование глобального и локального отбора в стратегиях эволюции» , «Параллельное решение проблем из природы» - PPSN V , Конспект лекций по информатике, том. 1498, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 367–377, doi : 10.1007/bfb0056879 , ISBN 978-3-540-65078-2 , получено 4 декабря 2022 г.

[:3-14] Jump up to: ^а ^б Якоб, Вильфрид (01 сентября 2010 г.). «Общая структура адаптации мультимемных алгоритмов, основанная на затратах и выгодах» . Меметические вычисления . 2 (3). п. 207: 201–218. дои : 10.1007/s12293-010-0040-9 . ISSN 1865-9292 . S2CID 167807 .

[15] Альба, Энрике; Дорронсоро, Бернабе; Альфонсо, Хьюго (2005). «Клеточные меметические алгоритмы» . Журнал компьютерных наук и технологий . 5 (4): 257–263 . Проверено 4 ноября 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]