Преждевременная сходимость — это нежелательное явление в эволюционных алгоритмах (ЭА), метаалгоритмах, которые имитируют основные принципы биологической эволюции в виде компьютерного алгоритма для решения задач оптимизации. Этот эффект означает, что популяция в эволюционном алгоритме сошлась слишком рано, приводя к субоптимальным результатам. В таком случае родительские решения не способны с помощью генетических операторов[англ.] не способны породить потомство, превосходящее своих родителей. Преждевременная сходимость — распространенная проблема в эволюционных алгоритмах, поскольку она приводит к потере или сходимости большого количества аллелей что впоследствии значительно затрудняет поиск конкретного гена, в котором присутствовали аллели[1][2]. Аллель считается потерянным, если в популяции присутствует ген, для которого все особи имеют одинаковое значение. Аллель, по определению Де Йонга, считается сошедшимся, когда 95% популяции имеют одинаковое значение для определенного гена[3].
Стратегии предотвращения преждевременной сходимости
правитьСтратегии восстановления генетического разнообразия могут включать:
- стратегию спаривания, известную как предотвращение инбридинга[4],
- равномерное скрещивание[англ.],
- имитацию полового отбора[5],
- предпочтительное замещение схожих особей (предварительный отбор или скученность),
- сегментацию особей со схожей приспособленностью (разделение по приспособленности),
- увеличение размера популяции
- нишевание и видообразование
Генетическая изменчивость также может быть восстановлена путем мутации, хотя этот процесс крайне случаен.
Общая стратегия снижения риска преждевременной сходимости заключается в использовании структурированных популяций[англ.] вместо обычно применяемых панмиктических.
Выявление преждевременной сходимости
правитьОпределить, когда произошла преждевременная сходимость, сложно, и столь же трудно предсказать её в будущем[2][1]. Одним из способов является использование разницы между средним и максимальным значениями приспособленности, как это сделали Патнаик и Шринивас, для последующего изменения вероятностей скрещивания и мутации[6]. Разнообразие популярности — ещё один показатель, который широко используется в исследованиях для измерения преждевременной сходимости. Однако, хотя общепризнано, что снижение разнообразия популяции напрямую ведёт к преждевременной сходимости, исследований по анализу разнообразия популяции проведено мало. Другими словами, используя термин «разнообразие популяции», аргументация в пользу исследования по предотвращению преждевременной сходимости не является убедительной, если не уточнено, что именно подразумевается под разнообразием популяции[7].
Существуют модели, призванные противостоять преждевременной сходимости и связанным с ней рискам, при этом сохраняя основные параметры генетических алгоритмов, такие как размер популяции, скорость мутации и другие ключевые механизмы. Эти модели были вдохновлены биологической экологией, где генетические взаимодействия ограничиваются внешними факторами , например, пространственной топологией или видообразованием[8][9]. Такие экологические модели, как Eco-GA, используют стратегии, основанные на диффузии, для повышения устойчивости работы генетических алгоритмов и увеличения вероятности достижения близких к глобальным оптимальных решений[10].
Причины преждевременной сходимости
правитьСуществует ряд предполагаемых или гипотетических причин преждевременной сходимости..
Самоадаптивные мутации
правитьРехенберг предложил концепцию самоадаптации распределений мутаций в эволюционных стратегиях[11]. Согласно Рехенбергу управляющие параметры этих распределений мутаций развиваются внутренне осредством самоадаптации, а не предопределяются. Он назвал это правилом 1/5 успеха эволюционных стратегий (1 + 1)-ES[a]: Параметр управления размером шага увеличивается на определенный коэффициент, если относительная частота положительных мутаций за заданный период времени превышает 1/5, и уменьшается, если она меньше 1/5. Самоадаптивные мутации вполне могут быть одной из причин преждевременной сходимости[7]. Точное нахождение оптимумов может быть улучшено с помощью самоадаптивной мутации, а также может быть ускорен поиск оптимума. Это широко признано, хотя механизмы, лежащие в основе этого, плохо изучены, поскольку часто неясно, найден ли оптимум локально или глобально[7]. Самоадаптивные методы могут приводить к сходимости к глобальному оптимуму, при условии, что используемые методы отбора применяют элитизм, а также что правило самоадаптации не мешает распределению мутаций, которое обеспечивает положительную минимальную вероятность при попадании в случайное подмножество[12]. Это применимо для невыпуклых целевых функций с множествами, включающими ограниченные нижние уровни ненулевых измерений. Исследование Рудольфа предполагает, что механизмы самоадаптации среди элитарных эволюционных стратегий напоминают правило 1/5 успеха и вполне могут быть захвачены локальным оптимумом, который включает положительную вероятность.[7].
Панмиктические популяции
правитьБольшинство эволюционных алгоритмов используют неструктурированные или панмиктические популяции , где практически каждая особь имеет возможность выбора партнера для спаривания, основываясь на приспособленности[13][14]. Таким образом, генетическая информация даже незначительно более приспособленной особи может распространиться в популяции за несколько поколений, при условии, что за это время не появится другое, более приспособленное потомство. Особенно в относительно небольших популяциях это может быстро привести к потере генотипического разнообразия и, как следствие, к преждевременной сходимости[1]. Известной мерой противодействия является переход к альтернативным моделям популяции[англ.], которые вводят в популяцию подструктуры[15][16], сохраняющие генотипическое разнообразие в течение более длительного периода времени и тем самым препятствующие тенденции к преждевременной сходимости. Это было продемонстрировано для различных эволюционных алгоритмов, таких как генетические алгоритмы[15], эволюционные стратегии[17], другие эволюционные алгоритмы[18] или меметические алгоритмы[18][19].
См. также
правитьПримечания
править- ↑ Стратегия (1+1)-ES: В этом варианте создается только один потомок для каждого родителя, и лучшее решение из двух становится родителем для следующего поколения. Этот простой и быстрый метод может быть эффективным для некоторых задач, но менее эффективным при оптимизации сложных задач. Алгоритм (1+1)-ES был создан в 1960-х годах и является одним из простейших методов оптимизации через эволюционные стратегии. Он заключается в генерации случайного вектора, который затем изменяется на случайный шаг. Если измененный вектор оказывается лучше, он заменяет исходный, иначе исходный вектор остается неизменным. Этот процесс повторяется до достижения оптимума
- ↑ 1 2 3 Leung, Gao, Xu, 1997, с. 1165–1176.
- ↑ 1 2 Baker, 1985, с. 101–111.
- ↑ De Jong, 1975.
- ↑ Michalewicz, 1996, с. 58.
- ↑ Simões, Lourenço, Machado, 2023, с. 276–291.
- ↑ Srinivas, Patnaik, 1994, с. 656–667.
- ↑ 1 2 3 4 Rudolph, 2001, с. 410–414.
- ↑ Davidor, Ben-Kiki, 1991, с. 1-9.
- ↑ Davidor, 1991, с. 510–517.
- ↑
A Naturally Occurring Niche & Species Phenomenon: The Model and First Results // Proceedings of the Fourth International Conference on Genetic Algorithms / R. K. Belew, L. B. Booker (Eds.). — Morgan Kaufmann, 1991. — С. 257–263.
- Davidor Y. The ECOlogical Framework II: Improving GA Performance with Virtually Zero Cost // Proceedings of the Fifth International Conference on Genetic Algorithms and Their Applications.. — 1993.
- Davidor Y. An Ecological Model for Evolutionary Computing. // Systems, Control and Information,. — 1993. — Т. 37, вып. 8.
- Davidor Y. Free the Spirit of Evolutionary Computing: The Ecological Genetic Algorithm Paradigm // Computing with Biological Metaphors / R. Paton (Ed.). — Chapman & Hall, 1994.
- ↑ Rechenberg, 1973.
- ↑ Rudolph, 1999, с. 646–651.
- ↑ Gordon, Whitley, 1993, с. 177–183.
- ↑ Cantú-Paz, 1998, с. 141–171.
- ↑ 1 2 Gordon, Mathias, Whitley, 1994, с. 237–241.
- ↑ Cantú-Paz, 1999.
- ↑ Gorges-Schleuter, 1998, с. 367–377.
- ↑ 1 2 Jakob, 2010, с. 207.
- ↑ Alba, Dorronsoro, Alfonso, 2005, с. 257–263.
Литература
править- Yee Leung, Yong Gao, Zong-Ben Xu. Degree of population diversity - a perspective on Преждевременная сходимость in genetic algorithms and its Markov chain analysis // IEEE Transactions on Neural Networks. — 1997. — Т. 8, вып. 5. — ISSN 1045-9227. — doi:10.1109/72.623217. — PMID 18255718.
- James E. Baker. Adaptive Selection Methods for Genetic Algorithms // Proceedings of the First International Conference on Genetic Algorithms and their Applications. — Hillsdale, NJ: L. Erlbaum, 1985. — ISBN 9780805804263.
- Kenneth A. De Jong. An analysis of the behavior of a class of genetic adaptive systems. — Ann Arbor, MI: University of Michigan, 1975. Диссертация
- Zbigniew Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edition. — Springer-Verlag, 1996. — ISBN 3-540-60676-9.
- José Maria Simões, Nuno Lourenço, Penousal Machado. All You Need is Sex for Diversity // Genetic Programming (англ.). — Springer Nature Switzerland, 2023. — Vol. 13986. — (Lecture Notes in Computer Science). — ISBN 978-3-031-29572-0. — doi:10.1007/978-3-031-29573-7_18.
- Srinivas M., Patnaik L.M. Adaptive probabilities of crossover and mutation in genetic algorithms // IEEE Transactions on Systems, Man, and Cybernetics. — 1994. — Апрель (т. 24, вып. 4). — doi:10.1109/21.286385.
- Günther Rudolph. Self-adaptive mutations may lead to Преждевременная сходимость // IEEE Transactions on Evolutionary Computation. — 2001. — Август (т. 5, вып. 4). — doi:10.1109/4235.942534. — Bibcode:2001ITEC....5..410R.
- Davidor Y., Ben-Kiki O. Local ecological-like evolutionary computing framework for global robustness. // Emergent Computing Methods in Engineering Design. — Springer, 1991.
- Davidor Y. An Adaptation Anomaly of a Genetic Algorithm // First International Conference on Simulation of Adaptive Behavior / J. A. Meyer, S. W. Wilson (Eds.). — MIT Press, 1991.
- Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. — Stuttgart: Frommann-Holzboog Verlag, 1973.
- Günther Rudolph. Self-adaptation and global convergence: A counter-example // Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406). — 1999. — P. 646–651. — ISBN 978-0-7803-5536-1. — doi:10.1109/CEC.1999.781994.
- Gordon V.S., Whitley D. Serial and Parallel Genetic Algorithms as Function Optimizers // Proceedings of the Fifth International Conference on Genetic Algorithms / Forrest S.. — San Mateo, CA, 1993.
- Erik Cantú-Paz. A survey of parallel genetic algorithms // Calculateurs Paralleles. — 1998. — Т. 10, вып. 2.
- V. Scott Gordon, Keith Mathias, Darrell Whitley. Cellular genetic algorithms as function optimizers // Proceedings of the 1994 ACM symposium on Applied computing - SAC '94 (англ.). — Phoenix, Arizona, United States: ACM Press, 1994. — ISBN 978-0-89791-647-9. — doi:10.1145/326619.326732.
- Erick Cantú-Paz. Efficient and Accurate Parallel Genetic Algorithms (англ.). — University of Illinois, Urbana-Champaign, USA: =Springer, New York, NY, 1999. — Vol. 1. — (Genetic Algorithms and Evolutionary Computation). — ISBN 978-1-4613-6964-6. — doi:10.1007/978-1-4615-4369-5. Тезисы диссертации
- Martina Gorges-Schleuter. A comparative study of global and local selection in evolution strategies // Parallel Problem Solving from Nature — PPSN V / (ed) Agoston E. Eiben, Thomas Bäck, Marc Schoenauer, Hans-Paul Schwefel. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. — Т. 1498. — (Lecture Notes in Computer Science). — ISBN 978-3-540-65078-2. — doi:10.1007/bfb0056879.
- Wilfried Jakob. A general cost-benefit-based adaptation framework for multimeme algorithms (англ.) // Memetic Computing. — 2010. — Vol. 2, iss. 3. — P. 201–218. — ISSN 1865-9292. — doi:10.1007/s12293-010-0040-9.
- Enrique Alba, Bernabé Dorronsoro, Hugo Alfonso. Cellular Memetic Algorithms // Journal of Computer Science and Technology. — 2005. — Т. 5, вып. 4.
