Эволюционные вычисления
Решатели проблем методом проб и ошибок с метаэвристическим или стохастическим оптимизационным характером
Эволюция популяции случайных изображений. Каждый кадр в анимации — это поколение, показывающее лучшую по приспособленности особь с геномом, составленным из уровня серой шкалы каждого участка. Эволюция следует следующим образом: 1. оценивает приспособленность, 2. ранжирует особей и 3. включает гены от следующей по приспособленности особи. Приспособленность — это ошибка разности с изображением Чарльза Дарвина .
Часть серии статей о
Эволюционная биология
Вьюрки Дарвина , Джон Гулд
Процессы и результаты
Естественная история
История эволюционной теории
Fields and applications
Social implications
Part of a series on the
Evolutionary algorithm
Genetic algorithm
Genetic programming

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

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

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

История

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

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

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

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

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

К 1990-м годам появился новый подход к эволюционным вычислениям, который стал называться генетическим программированием , за который выступал Джон Коза и другие. [3] В этом классе алгоритмов предметом эволюции была сама программа, написанная на языке программирования высокого уровня (предыдущие попытки использовать машинный код предпринимались еще в 1958 году, но они не увенчались успехом). Для Коза программы представляли собой Lisp S-выражения , которые можно рассматривать как деревья подвыражений. Такое представление позволяет программам менять поддеревья, представляя собой своего рода генетическое смешивание. Программы оцениваются на основе того, насколько хорошо они выполняют определенную задачу, и оценка используется для искусственного отбора. Индукция последовательности, распознавание образов и планирование были успешными применениями парадигмы генетического программирования.

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

Методы

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

Полный каталог со многими другими недавно предложенными алгоритмами был опубликован в Evolutionary Computation Bestiary. [11] Важно отметить, что многие недавние алгоритмы, однако, имеют плохую экспериментальную проверку. [12]

Эволюционные алгоритмы

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

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

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

Эволюционные алгоритмы и биология

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

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

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

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

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

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

Известные практики

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

Журналы

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

Конференции

Основные конференции в области эволюционных вычислений включают в себя:

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

  • Статья в Стэнфордской энциклопедии философии о биологической информации (на английском языке)

Библиография

  • Т. Бэк, Д. Б. Фогель и З. Михалевич (редакторы), Справочник по эволюционным вычислениям, 1997, ISBN  0750303921
  • Th. Bäck и H.-P. Schwefel. Обзор эволюционных алгоритмов для оптимизации параметров. Архивировано 12 июля 2018 г. в Wayback Machine Evolutionary Computation, 1(1):1–23, 1993.
  • W. Banzhaf, P. Nordin, RE Keller и FD Francone. Генетическое программирование — Введение. Morgan Kaufmann, 1998.
  • С. Каньони и др., Реальные приложения эволюционных вычислений, Springer-Verlag Lecture Notes in Computer Science , Берлин, 2000.
  • R. Chiong, Th. Weise, Z. Michalewicz (редакторы), Variants of Evolutionary Algorithms for Real-World Applications, Springer , 2012, ISBN 3642234232 
  • KA De Jong, Эволюционные вычисления: унифицированный подход. MIT Press , Кембридж, Массачусетс, 2006
  • AE Eiben и JE Smith, От эволюционных вычислений к эволюции вещей, Nature, 521:476-482, doi:10.1038/nature14544, 2015
  • AE Eiben и JE Smith, Введение в эволюционные вычисления, Springer, Первое издание, 2003; Второе издание, 2015
  • DB Fogel. Эволюционные вычисления. К новой философии машинного интеллекта. IEEE Press, Piscataway, NJ, 1995.
  • Л. Дж. Фогель, А. Дж. Оуэнс и М. Дж. Уолш. Искусственный интеллект через имитацию эволюции. Нью-Йорк: John Wiley, 1966.
  • Д. Э. Голдберг. Генетические алгоритмы в поиске, оптимизации и машинном обучении. Эддисон Уэсли, 1989.
  • Дж. Х. Холланд. Адаптация в естественных и искусственных системах. Издательство Мичиганского университета , Энн-Арбор, 1975.
  • P. Hingston, L. Barone и Z. Michalewicz (редакторы), Design by Evolution, Natural Computing Series, 2008, Springer , ISBN 3540741097 
  • Дж. Р. Коза. Генетическое программирование: о программировании компьютеров посредством естественной эволюции. MIT Press, Массачусетс, 1992.
  • FJ Lobo, CF Lima, Z. Michalewicz (редакторы), Установка параметров в эволюционных алгоритмах, Springer , 2010, ISBN 3642088929 
  • З. Михалевич , Генетические алгоритмы + структуры данных – программы эволюции, 1996, Springer , ISBN 3540606769 
  • З. Михалевич и Д. Б. Фогель, Как это решить: современная эвристика, Springer , 2004, ISBN 978-3-540-22494-5 
  • И. Рехенберг. Стратегия эволюции: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution. Fromman-Hozlboog Verlag, Штутгарт, 1973 г. (на немецком языке)
  • Х.-П. Швефель. Численная оптимизация компьютерных моделей. John Wiley & Sons, Нью-Йорк, 1981. 1995 – 2-е издание.
  • Д. Саймон. Эволюционные алгоритмы оптимизации. Архивировано 10 марта 2014 г. в Wayback Machine . Wiley, 2013.
  • M. Sipper; W. Fu; K. Ahuja; JH Moore (2018). «Исследование пространства параметров эволюционных алгоритмов». BioData Mining . 11 : 2. doi : 10.1186/s13040-018-0164-x . PMC  5816380. PMID  29467825 .
  • Y. Zhang; S. Li. (2017). "PSA: новый алгоритм оптимизации, основанный на правилах выживания porcellio scaber". arXiv : 1709.09840 [cs.NE].

Ссылки

  1. ^ ab Eiben, AE; Smith, JE (2015), Эволюционные вычисления: Истоки, Серия естественных вычислений, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 13–24, doi :10.1007/978-3-662-44874-8_2, ISBN 978-3-662-44873-1, получено 6 мая 2022 г.
  2. ^ Бергин, Марк; Эбербах, Юджин (12 апреля 2013 г.). «Эволюционный Тьюринг в контексте эволюционных машин». arXiv : 1304.3762 [cs.AI].
  3. ^ abcde Эволюционные вычисления: летопись окаменелостей. Дэвид Б. Фогель. Нью-Йорк: IEEE Press. 1998. ISBN 0-7803-3481-7. OCLC  38270557.{{cite book}}: CS1 maint: others (link)
  4. ^ Фишер, Томас (1986), «Kybernetische Systemanalyse Einer Tuchfabrik zur Einführung Eines Computergestützten Dispositionssystems der Fertigung», DGOR , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 120, номер домена : 10.1007/978-3-642-71161-9_14, ISBN 978-3-642-71162-6, получено 6 мая 2022 г.
  5. ^ Митчелл, Мелани (1998). Введение в генетические алгоритмы. MIT Press. doi :10.7551/mitpress/3927.001.0001. ISBN 978-0-262-28001-3.
  6. ^ Барричелли, Нильс Аалл (1954). «Эксемпи числовые процессы эволюции». Методы : 45–68.
  7. ^ Фрейзер AS (1958). «Анализ генетических моделей методом Монте-Карло». Nature . 181 (4603): 208–9. Bibcode :1958Natur.181..208F. doi :10.1038/181208a0. PMID  13504138. S2CID  4211563.
  8. ^ Коза, Джон Р. (1992). Генетическое программирование: о программировании компьютеров с помощью естественного отбора . MIT Press . ISBN 978-0-262-11170-6.
  9. ^ GC Onwubolu и BV Babu, Onwubolu, Godfrey C.; Babu, BV (21 января 2004 г.). Новые методы оптимизации в машиностроении. Springer. ISBN 9783540201670. Получено 17 сентября 2016 г. .
  10. ^ Джамшиди М (2003). «Инструменты для интеллектуального управления: нечеткие контроллеры, нейронные сети и генетические алгоритмы». Philosophical Transactions of the Royal Society A. 361 ( 1809): 1781–808. Bibcode : 2003RSPTA.361.1781J. doi : 10.1098/rsta.2003.1225. PMID  12952685. S2CID  34259612.
  11. ^ Кампело, Фелипе; Аранья, Клаус (20 июня 2018 г.). «Ec Bestiary: A Bestiary Of Evolutionary, Swarm And Other Metaphor-Based Algorithms». doi :10.5281/ZENODO.1293035. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  12. ^ Кудела, Якуб (12 декабря 2022 г.). «Критическая проблема в сравнительном анализе и бенчмаркинге методов эволюционных вычислений». Nature Machine Intelligence . 4 (12): 1238–1245. arXiv : 2301.01984 . doi :10.1038/s42256-022-00579-0. ISSN  2522-5839. S2CID  254616518.
  13. ^ «Биологическая информация». Стэнфордская энциклопедия философии . Лаборатория метафизических исследований, Стэнфордский университет. 2016.
  14. ^ JG Diaz Ochoa (2018). «Эластичные многомасштабные механизмы: вычисления и биологическая эволюция». Журнал молекулярной эволюции . 86 (1): 47–57. Bibcode : 2018JMolE..86...47D. doi : 10.1007/s00239-017-9823-7. PMID  29248946. S2CID  22624633.
  15. ^ А. Данчин (2008). «Бактерии как компьютеры, создающие компьютеры». FEMS Microbiol. Rev. 33 (1): 3–26. doi :10.1111/j.1574-6976.2008.00137.x. PMC 2704931 . PMID  19016882.  
  16. ^ Burgin, Mark; Eberbach, Eugene (2013). «Рекурсивно сгенерированные эволюционные машины Тьюринга и эволюционные автоматы». В Xin-She Yang (ред.). Искусственный интеллект, эволюционные вычисления и метаэвристика . Исследования по вычислительному интеллекту. Том 427. Springer-Verlag. С. 201–230. doi :10.1007/978-3-642-29694-9_9. ISBN 978-3-642-29693-2.
  17. ^ Burgin, M. и Eberbach, E. (2010) Ограниченные и периодические эволюционные машины, в Трудах Конгресса по эволюционным вычислениям 2010 г. (CEC'2010), Барселона, Испания, 2010 г., стр. 1379-1386
  18. ^ ab Burgin, M.; Eberbach, E. (2012). «Эволюционные автоматы: выразительность и сходимость эволюционных вычислений». The Computer Journal . 55 (9): 1023–1029. doi :10.1093/comjnl/bxr099.
  19. ^ Эбербах Э. (2002) О выразительности эволюционных вычислений: является ли EC алгоритмическим?, Труды Всемирного конгресса по вычислительному интеллекту WCCI'2002, Гонолулу, Гавайи, 2002, 564-569.
  20. ^ Эбербах, Э. (2005) К теории эволюционных вычислений, BioSystems, т. 82, стр. 1-19.
  21. ^ Эбербах, Юджин; Бергин, Марк (2009). «Эволюционные автоматы как основа эволюционных вычислений: Ларри Фогель был прав». Конгресс IEEE по эволюционным вычислениям 2009 г. IEEE. стр. 2149–2156. doi :10.1109/CEC.2009.4983207. ISBN 978-1-4244-2958-5. S2CID  2869386.
  22. ^ Хопкрофт, Дж. Э., Р. Мотвани и Дж. Д. Ульман (2001) Введение в теорию автоматов, языки и вычисления, Эддисон Уэсли, Бостон/Сан-Франциско/Нью-Йорк
  23. ^ JJ Merelo и C. Cotta (2007). «Кто является лучшим исследователем EC? Анализ центральности сложной сети авторов в эволюционных вычислениях». arXiv : 0708.2021 [cs.CY].


Retrieved from "https://en.wikipedia.org/w/index.php?title=Evolutionary_computation&oldid=1244965199"