Преждевременная сходимость — это нежелательное явление в эволюционных алгоритмах (ЭА), метаалгоритмах, которые имитируют основные принципы биологической эволюции в виде компьютерного алгоритма для решения задач оптимизации. Этот эффект означает, что популяция в эволюционном алгоритме сошлась слишком рано, приводя к субоптимальным результатам. В таком случае родительские решения не способны с помощью не способны породить потомство, превосходящее своих родителей. Преждевременная сходимость — распространенная проблема в эволюционных алгоритмах, поскольку она приводит к потере или сходимости большого количества аллелей что впоследствии значительно затрудняет поиск конкретного гена, в котором присутствовали аллели. Аллель считается потерянным, если в популяции присутствует ген, для которого все особи имеют одинаковое значение. Аллель, по определению Де Йонга, считается сошедшимся, когда 95% популяции имеют одинаковое значение для определенного гена.
Стратегии предотвращения преждевременной сходимости Стратегии восстановления генетического разнообразия могут включать: стратегию спаривания, известную как предотвращение инбридинга, , имитацию полового отбора, предпочтительное замещение схожих особей (предварительный отбор или скученность), сегментацию особей со схожей приспособленностью (разделение по приспособленности), увеличение размера популяции нишевание и видообразование
Генетическая изменчивость также может быть восстановлена путем мутации, хотя этот процесс крайне случаен.
Общая стратегия снижения риска преждевременной сходимости заключается в использовании вместо обычно применяемых панмиктических.
Выявление преждевременной сходимости Определить, когда произошла преждевременная сходимость, сложно, и столь же трудно предсказать её в будущем. Одним из способов является использование разницы между средним и максимальным значениями приспособленности, как это сделали Патнаик и Шринивас, для последующего изменения вероятностей скрещивания и мутации. Разнообразие популярности — ещё один показатель, который широко используется в исследованиях для измерения преждевременной сходимости. Однако, хотя общепризнано, что снижение разнообразия популяции напрямую ведёт к преждевременной сходимости, исследований по анализу разнообразия популяции проведено мало. Другими словами, используя термин «разнообразие популяции», аргументация в пользу исследования по предотвращению преждевременной сходимости не является убедительной, если не уточнено, что именно подразумевается под разнообразием популяции.
Существуют модели, призванные противостоять преждевременной сходимости и связанным с ней рискам, при этом сохраняя основные параметры генетических алгоритмов, такие как размер популяции, скорость мутации и другие ключевые механизмы. Эти модели были вдохновлены биологической экологией, где генетические взаимодействия ограничиваются внешними факторами , например, пространственной топологией или видообразованием. Такие экологические модели, как Eco-GA, используют стратегии, основанные на диффузии, для повышения устойчивости работы генетических алгоритмов и увеличения вероятности достижения близких к глобальным оптимальных решений.
Причины преждевременной сходимости Существует ряд предполагаемых или гипотетических причин преждевременной сходимости..
Самоадаптивные мутации Рехенберг предложил концепцию самоадаптации распределений мутаций в эволюционных стратегиях. Согласно Рехенбергу управляющие параметры этих распределений мутаций развиваются внутренне осредством самоадаптации, а не предопределяются. Он назвал это правилом 1/5 успеха эволюционных стратегий (1 + 1)-ES: Параметр управления размером шага увеличивается на определенный коэффициент, если относительная частота положительных мутаций за заданный период времени превышает 1/5, и уменьшается, если она меньше 1/5. Самоадаптивные мутации вполне могут быть одной из причин преждевременной сходимости. Точное нахождение оптимумов может быть улучшено с помощью самоадаптивной мутации, а также может быть ускорен поиск оптимума. Это широко признано, хотя механизмы, лежащие в основе этого, плохо изучены, поскольку часто неясно, найден ли оптимум локально или глобально. Самоадаптивные методы могут приводить к сходимости к глобальному оптимуму, при условии, что используемые методы отбора применяют элитизм, а также что правило самоадаптации не мешает распределению мутаций, которое обеспечивает положительную минимальную вероятность при попадании в случайное подмножество. Это применимо для невыпуклых целевых функций с множествами, включающими ограниченные нижние уровни ненулевых измерений. Исследование Рудольфа предполагает, что механизмы самоадаптации среди элитарных эволюционных стратегий напоминают правило 1/5 успеха и вполне могут быть захвачены локальным оптимумом, который включает положительную вероятность..
Панмиктические популяции Большинство эволюционных алгоритмов используют неструктурированные или панмиктические популяции , где практически каждая особь имеет возможность выбора партнера для спаривания, основываясь на приспособленности. Таким образом, генетическая информация даже незначительно более приспособленной особи может распространиться в популяции за несколько поколений, при условии, что за это время не появится другое, более приспособленное потомство. Особенно в относительно небольших популяциях это может быстро привести к потере генотипического разнообразия и, как следствие, к преждевременной сходимости. Известной мерой противодействия является переход к альтернативным , которые вводят в популяцию подструктуры, сохраняющие генотипическое разнообразие в течение более длительного периода времени и тем самым препятствующие тенденции к преждевременной сходимости. Это было продемонстрировано для различных эволюционных алгоритмов, таких как генетические алгоритмы, эволюционные стратегии, другие эволюционные алгоритмы или меметические алгоритмы.
См. также Эволюционное моделирование Эволюция
Примечания
Литература
Диссертация
Тезисы диссертации
Категория:Эволюционная биологи Категория:Эволюционные алгоритмы Категория:Сходимость