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

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

Рекомендации

  1. ^ а б Люнг, Ю., и другие. (1997). Степень популяционного разнообразия - точка зрения на преждевременную конвергенцию генетических алгоритмов и их марковской цепи IEEE-транзакции в нейронных сетях, т. 8. С. 1165 - 1176.
  2. ^ а б Бейкер Дж. Э. и Грефенстетт Дж. (2014). Труды Первой Международной конференции по генетическим алгоритмам и их приложениям. Хобокен: Тейлор и Фрэнсис, стр. 101-105.
  3. ^ Де Йонг, К.А. (1975). Анализ поведения одного класса генетических адаптивных систем, канд. диссертация, Мичиганский университет.
  4. ^ Михалевич, Збигнев (1996). Генетические алгоритмы + структуры данных = программы эволюции, 3-е издание. Springer-Verlag. п. 58. ISBN  3-540-60676-9.
  5. ^ Патнаик, Л.М. и Шринивас, М. (1994). Адаптивные вероятности кроссовера и мутации в генетических алгоритмах. IEEE Trans. Syst. Человек Киберн., т. 24. С. 656-667.
  6. ^ а б c d Гюнтер, Р. (2001). Самоадаптация может привести к преждевременной конвергенции, Fachbereich Informatik, LS XI, Universität Dortmund, стр. 1 - 13.
  7. ^ Рехенберг, И. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Штутгарт.
  8. ^ Рудольф, Г. (1999). Глобальная конвергенция и самоадаптация: контрпример. В трудах Конгресса по эволюционным вычислениям 1999 г. (CEC 1999). IEEE Press, Нью-Джерси, стр. 646–651.

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