В генетических алгоритмах термин « преждевременная конвергенция» означает, что популяция для задачи оптимизации сошлась слишком рано, что привело к неоптимальной конвергенции . В этом контексте родительские решения с помощью генетических операторов не способны производить потомство, которое превосходит своих родителей или превосходит их. Преждевременная конвергенция - распространенная проблема, обнаруживаемая в генетических алгоритмах, поскольку она приводит к потере или конвергенции большого количества аллелей, что впоследствии очень затрудняет поиск конкретного гена, в котором присутствовали аллели. [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]
Рекомендации
- ^ a b Leung, Y., et al. (1997). Степень разнообразия населения - взгляд на преждевременную конвергенцию генетических алгоритмов и их цепочки Маркова, IEEE Transactions on Neural Networks , vol. 8. С. 1165 - 1176.
- ^ Б Бейкер, JE & Grefenstette, J. (2014). Труды Первой Международной конференции по генетическим алгоритмам и их приложениям . Хобокен: Тейлор и Фрэнсис, стр. 101-105.
- Перейти ↑ De Jong, KA (1975). Анализ поведения одного класса генетических адаптивных систем, канд. докторскую диссертацию в Мичиганском университете.
- ^ Михалевич, Збигнев (1996). Генетические алгоритмы + структуры данных = программы эволюции, 3-е издание . Springer-Verlag. п. 58. ISBN 3-540-60676-9.
- ^ Патнайк, Л.М. & Шринивас, М. (1994). Адаптивные вероятности кроссовера и мутации в генетических алгоритмах. IEEE Trans. Syst. Человек Киберн. , т. 24. С. 656-667.
- ^ а б в г Гюнтер, Р. (2001). Самоадаптация может привести к преждевременной конвергенции, Fachbereich Informatik, LS XI, Universität Dortmund, стр. 1–13.
- ^ Rechenberg, И. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag , Штутгарт.
- Перейти ↑ Rudolph, G. (1999). Глобальная конвергенция и самоадаптация: контрпример. В Трудах Конгресса эволюционных вычислений 1999 г. (CEC 1999) . IEEE Press, Нью-Джерси, стр. 646–651.