АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
О РУВИКИ

Эволюционное моделирование

Эволюционное моделирование (англ. Evolutionary computation) — семейство алгоритмов для глобальной оптимизации, вдохновлённых биологической эволюцией, а также направление искусственного интеллекта и мягких вычислений, изучающее эти алгоритмы[1]. С технической точки зрения, это семейство основанных на популяции решателей задач методом проб и ошибок, обладающих метаэвристическим или стохастическим характером.

В эволюционном моделировании изначально создаётся набор кандидатных решений, который затем итеративно обновляется. Каждое новое поколение формируется путём случайного исключения наименее эффективных решений и внесения незначительных случайных изменений, а также, в зависимости от метода, рекомбинации родительской информации. В биологических терминах это означает, что популяция решений подвергается естественному (или искусственному) отбору, мутации и, возможно, рекомбинации. В результате популяция постепенно эволюционирует, увеличивая приспособленность (fitness) согласно выбранной функции приспособленности алгоритма.

Методы эволюционного моделирования позволяют получать высоко оптимизированные решения для самого широкого круга задач, что обеспечило их популярность в информатике. Существует множество разновидностей и расширений для определения специфических семейств задач и структур данных. Эволюционное моделирование также используется в эволюционной биологии как способ проведения компьютерных экспериментов для изучения общих характеристик эволюционных процессов.

undefined

История

Идея имитации эволюционных процессов для решения задач возникла ещё до появления компьютеров. В частности, Алан Тьюринг предложил метод генетического поиска в 1948 году[1]. Разработанные им машины типа B походили на примитивные нейронные сети, в которых связи между нейронами обучались по принципу, напоминающему генетический алгоритм. Машины типа P у Тьюринга напоминали подходы к обучению с подкреплением, где сигналы удовольствия и наказания управляли обучением определённого поведения. Однако его статья была опубликована только в 1968 году, а сам Тьюринг погиб в 1954 году, поэтому его работы практически не повлияли на развитие эволюционных методов[2].

Эволюционное моделирование как самостоятельная область активно развивалось с 1950-х—1960-х годов[1]. В этот период в разных странах независимо появились три подхода: эволюционные стратегии, эволюционное программирование и генетические алгоритмы. Позднее, в начале 1990-х, появилось генетическое программирование. Эти классы различались по методам отбора, способам мутаций и способу представления генетических данных. К 1990-м границы между направлениями размылись, и в 1991 году был введён общий термин «эволюционное моделирование», охватывающий все четыре парадигмы[3].

В 1962 году Лоренс Дж. Фогель начал исследование эволюционного программирования в США как направления искусственного интеллекта. В этой системе конечные автоматы подвергались мутациям (добавление/удаление состояний, изменение переходов), а наиболее успешные варианты подвергались дальнейшей эволюции. Итоговый автомат применяли для решения задач предсказания, идентификации систем и автоматического управления. Метод впоследствии был расширен для работы с временными рядами и в эволюции игровых стратегий.

В 1964 году Ингo Рехенберг и Ганс-Пауль Швефель предложили в Германии концепцию эволюционных стратегий. Так как классические градиентные методы часто застревали в локальных минимумах, Рехенберг и Швефель предложили использовать случайные мутации всех параметров вектора решения для движения к глобальному экстремуму. Детские решения эволюционировали из родительских, а для следующих поколений выбирались наиболее успешные варианты. Первые эксперименты были проведены без использования компьютеров с помощью кубиков, а с 1965 года вычисления полностью автоматизировали[4].

Джон Хенри Холланд разработал генетические алгоритмы в 1960-х, а в 1970-х они были дополнительно развиты в Университете Мичигана[5]. В отличие от других подходов, Холланд изначально преследовал исследование механизмов адаптации. Популяции кодировались битовыми строками, подвергались искусственному отбору, мутациям и рекомбинациям. В то время как другие методы отслеживали одну оптимальную особь (дети конкурировали с родителями), генетические алгоритмы Холланда работали с большими популяциями, в которых конкуренция шла в каждом поколении по всей выборке.

В 1990-х появился новый подход — генетическое программирование, активно развиваемый Джоном Козой[1]. Здесь объекты эволюции — программы на языке высокого уровня (часто на Lisp), представленные в виде древовидных S-выражений, что позволяло эффективно перестраивать их структуру (например, посредством обмена поддеревьями). Программы оценивались по качеству решения задачи, а эта оценка использовалась для искусственного отбора. Генетическое программирование успешно применялось в распознавании образов, индукции последовательностей и автоматическом планировании.

Среди других исследователей, повлиявших на развитие эволюционных методов, был Нильс Олл Барричелли, выполнивший первые вычислительные эксперименты с искусственной эволюцией в 1953 году и опубликовавший результаты в 1954 году[6]. Ещё одним пионером был Алекс Фрейзер, который опубликовал ряд работ по симуляции искусственного отбора[7]. По мере роста интереса и увеличения вычислительных мощностей стали появляться практические применения, например, автоматическая эволюция программ[8]. Сегодня эволюционные алгоритмы решают задачи высокой размерности эффективнее традиционных методов и применяются для оптимизации сложных систем[9].

Технические особенности

Методы эволюционного моделирования, как правило, представляют собой метаэвристические оптимизационные алгоритмы. К области относятся:

В последние годы появилось множество сомнительных алгоритмов, зачастую являющихся лишь повторениями существующих методов (например, оптимизации роя частиц) с изменёнными метафорами, но без новых идей. Подробный каталог таких алгоритмов опубликован в Evolutionary Computation Bestiary[10]. Важно отметить, что новый метод не обязательно означает строго новую эволюционную идею; многие из «новых» алгоритмов имеют слабую экспериментальную проверку[11].

Алгоритмы и реализации

Эволюционные алгоритмы — это подмножество эволюционного моделирования, реализующее механизмы, вдохновлённые биологической эволюцией: воспроизведение, мутации, рекомбинации и естественный отбор. Каждый кандидат-решение играет роль особи в популяции, а функция затрат определяет «окружение», в котором они выживают (см. также Функция приспособленности). Эволюция популяции происходит при повторном применении этих операторов.

В процессе задействованы две главные силы: рекомбинация (например, кроссовер) и мутация порождают разнообразие, способствуя появлению новых признаков, а отбор увеличивает эффективность популяции.

Многие элементы эволюционного моделирования носят стохастический характер. Изменения в результате рекомбинаций и мутаций осуществляются случайным образом. Оператор отбора может быть как детерминированным, так и стохастическим: особи с большей приспособленностью чаще выбираются для размножения, однако даже слабые индивиды сохраняют шанс стать родителями или выжить.

Взаимосвязь с биологией

Генетические алгоритмы предоставляют методы для моделирования биологических систем и системной биологии в рамках теории динамических систем, позволяя предсказывать будущие состояния системы. Это образный, хотя и не полностью точный способ привлечь внимание к структурированности развития в природе.

Тем не менее, применение вычислительных и информационных концепций, особенно из теории вычислимости, важно и для понимания самой эволюции. Сильной стороной этого подхода является признание децентрализованной природы биологического развития: организмы формируются в результате локальных взаимодействий между клетками. Наиболее продуктивные параллели между развитием программ и организмов проводят между внутриклеточными процессами и работой современных компьютеров[12]. Поэтому биологические системы ближе к вычислительным машинам, которые обрабатывают входную информацию и рассчитывают следующее состояние, чем, например, к традиционной динамической системе[13].

Далее, согласно теории вычислимости, микропроцессы в организме могут быть принципиально неразрешимыми и неполными, что усиливает аналогичность между компьютерами и клетками с биологической точки зрения[14].

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

Эволюционные автоматы, обобщение эволюционных машин Тьюринга, были введены для более точного исследования свойств биологических и эволюционных вычислительных процессов. В частности, они позволяют получать новые результаты по выразительности эволюционных методов, что подтверждает первоначальные выводы о неразрешимости как естественной эволюции, так и алгоритмов эволюционного моделирования. Эволюционные конечные автоматы, простейший подкласс эволюционных автоматов, работающих в терминальном режиме, могут распознавать любые языки над алфавитом, включая неразрешимые и частично разрешимые языки (например, язык универсальной машины Тьюринга)[15].

Известные исследователи

Список ведущих специалистов области постоянно обновляется. Анализ сети научного сообщества по эволюционному моделированию был опубликован в 2007 году[16].

  • Кальянмой Деб
  • Кеннет А. Де Йонг
  • Питер Дж. Флеминг
  • Дэвид Б. Фогель
  • Стефани Форрест
  • Дэвид Э. Голдберг
  • Джон Хенри Холланд
  • Тео Янсен
  • Джон Коза
  • Збигнев Михалевич
  • Мелани Митчелл
  • Питер Нордин
  • Риккардо Поли
  • Инго Рехенберг
  • Ганс-Пауль Швефель

Публикации

Журналы

Существуют научные журналы, посвящённые эволюционному моделированию:

  • Evolutionary Computation (основан в 1993, MIT Press)
  • Artificial Life (основан в 1993, MIT Press)
  • IEEE Transactions on Evolutionary Computation (основан в 1997, IEEE)
  • Genetic Programming and Evolvable Machines (основан в 2000, Springer Nature)
  • Swarm Intelligence (основан в 2007, Springer Nature)
  • Evolutionary Intelligence (основан в 2008, Springer Nature)
  • Journal of Artificial Evolution and Applications (2008—2010, Hindawi)
  • Memetic Computing (основан в 2009, Springer Nature)
  • International Journal of Applied Evolutionary Computation (основан в 2010, IGI Global)
  • Swarm and Evolutionary Computation (основан в 2011, Elsevier)
  • International Journal of Swarm Intelligence and Evolutionary Computation (основан в 2012, Walsh Medical Media)

Конференции

Ключевые конференции по эволюционному моделированию:

  • Генетическая и эволюционная конференция по вычислениям (GECCO, ACM)
  • Конгресс IEEE по эволюционным вычислениям (CEC)
  • EvoStar — объединяет четыре конференции: EuroGP, EvoApplications, EvoCOP и EvoMUSART
  • Параллельное решение задач природы (PPSN)

Примечания

  1. ↑ 1 2 3 4 Eiben, A. E. (2015). “Evolutionary Computing: The Origins”. Natural Computing Series [англ.]. Springer Berlin Heidelberg: 13—24. DOI:10.1007/978-3-662-44874-8_2. ISBN 978-3-662-44873-1. Дата обращения 2022-05-06.
  2. ↑ Burgin, Mark & Eberbach, Eugene (2013-04-12), Evolutionary Turing in the Context of Evolutionary Machines, arΧiv:1304.3762 [cs.AI]. 
  3. ↑ Fogel, David B. Evolutionary computation: the fossil record. — New York : IEEE Press, 1998. — ISBN 0-7803-3481-7.
  4. ↑ Fischer, Thomas (1986). “Kybernetische Systemanalyse Einer Tuchfabrik zur Einführung Eines Computergestützten Dispositionssystems der Fertigung”. DGOR [нем.]. Springer Berlin Heidelberg: 120. DOI:10.1007/978-3-642-71161-9_14. ISBN 978-3-642-71162-6. Дата обращения 2022-05-06. |access-date= требует |url= (справка)
  5. ↑ Mitchell, Melanie. An Introduction to Genetic Algorithms : [англ.]. — MIT Press, 1998. — ISBN 978-0-262-28001-3. — doi:10.7551/mitpress/3927.001.0001.
  6. ↑ Barricelli, Nils Aall (1954). “Esempi Numerici di processi di evoluzione”. Methodos: 45—68.
  7. ↑ Fraser, A. S. (1958). “Monte Carlo analyses of genetic models”. Nature. 181 (4603): 208—209. DOI:10.1038/181208a0. PMID 13504138. S2CID 4211563.
  8. ↑ Koza, John R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. — MIT Press, 1992. — ISBN 978-0-262-11170-6.
  9. ↑ Onwubolu, Godfrey C. New Optimization Techniques in Engineering : [англ.] / Godfrey C. Onwubolu, B. V. Babu. — Springer, 2004-01-21. — ISBN 9783540201670.
  10. ↑ Campelo, Felipe; Aranha, Claus (2018-06-20). “Ec Bestiary: A Bestiary Of Evolutionary, Swarm And Other Metaphor-Based Algorithms” [англ.]. DOI:10.5281/ZENODO.1293035.
  11. ↑ Kudela, Jakub (2022-12-12). “A critical problem in benchmarking and analysis of evolutionary computation methods”. Nature Machine Intelligence [англ.]. 4 (12): 1238—1245. arXiv:2301.01984. DOI:10.1038/s42256-022-00579-0. ISSN 2522-5839. S2CID 254616518.
  12. ↑ Biological Information // The Stanford Encyclopedia of Philosophy : [англ.]. — Metaphysics Research Lab, Stanford University, 2016.
  13. ↑ J.G. Diaz Ochoa (2018). “Elastic Multi-scale Mechanisms: Computation and Biological Evolution”. Journal of Molecular Evolution [англ.]. 86 (1): 47—57. DOI:10.1007/s00239-017-9823-7. PMID 29248946. S2CID 22624633.
  14. ↑ Danchin, A. (2008). “Bacteria as computers making computers”. FEMS Microbiol. Rev. 33 (1): 3—26. DOI:10.1111/j.1574-6976.2008.00137.x. PMC 2704931. PMID 19016882.
  15. ↑ Burgin, M.; Eberbach, E. (2012). “Evolutionary Automata: Expressiveness and Convergence of Evolutionary Computation”. The Computer Journal. 55 (9): 1023—1029. DOI:10.1093/comjnl/bxr099.
  16. ↑ J.J. Merelo and C. Cotta (2007), Who is the best connected EC researcher? Centrality analysis of the complex network of authors in evolutionary computation, arΧiv:0708.2021 [cs.CY]. 

Категории