stringtranslate.com

Эволюционные вычисления

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

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

Методы эволюционных вычислений позволяют создавать высокооптимизированные решения для широкого спектра задач, что делает их популярными в информатике . Существует множество вариантов и расширений, подходящих для более конкретных семейств задач и структур данных. Эволюционные вычисления также иногда используются в эволюционной биологии как экспериментальная процедура 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 году предпринимались некоторые попытки использовать машинный код, но они не увенчались успехом). Для Козы программы представляли собой S-выражения Lisp , которые можно рассматривать как деревья подвыражений. Такое представление позволяет программам менять поддеревья местами, что представляет собой своего рода генетическое смешивание. Программы оцениваются на основе того, насколько хорошо они выполняют определенную задачу, и эта оценка используется для искусственного отбора. Индукция последовательностей, распознавание образов и планирование — все это были успешные применения парадигмы генетического программирования.

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

Техники

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

Сквозной каталог многих других недавно предложенных алгоритмов был опубликован в Бестиарии эволюционных вычислений. [11] Важно отметить, что многие новейшие алгоритмы, однако, не имеют плохой экспериментальной проверки. [12]

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

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

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

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

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

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

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

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

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

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

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

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

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

Журналы

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

Конференции

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

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

Внешние ссылки

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

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

  1. ^ Аб Эйбен, AE; Смит, Дж. Э. (2015), Эволюционные вычисления: истоки, серия Natural Computing, Берлин, Гейдельберг: 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. ОСЛК  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). Введение в генетические алгоритмы. Массачусетский технологический институт Пресс. дои : 10.7551/mitpress/3927.001.0001. ISBN 978-0-262-28001-3.
  6. ^ Барричелли, Нильс Аалл (1954). «Эксемпи числовые процессы эволюции». Методы : 45–68.
  7. ^ Фрейзер А.С. (1958). «Анализ генетических моделей методом Монте-Карло». Природа . 181 (4603): 208–9. Бибкод : 1958Natur.181..208F. дои : 10.1038/181208a0. PMID  13504138. S2CID  4211563.
  8. ^ Коза, Джон Р. (1992). Генетическое программирование: о программировании компьютеров посредством естественного отбора . МТИ Пресс . ISBN 978-0-262-11170-6.
  9. ^ GC Онвуболу и Б.В. Бабу, Онвуболу, Годфри К.; Бабу, Б.В. (21 января 2004 г.). Новые методы оптимизации в машиностроении. Спрингер. ISBN 9783540201670. Проверено 17 сентября 2016 г.
  10. ^ Джамшиди М (2003). «Инструменты интеллектуального управления: нечеткие контроллеры, нейронные сети и генетические алгоритмы». Философские труды Королевского общества А. 361 (1809): 1781–808. Бибкод : 2003RSPTA.361.1781J. дои : 10.1098/rsta.2003.1225. PMID  12952685. S2CID  34259612.
  11. ^ Кампело, Фелипе; Аранья, Клаус (20 июня 2018 г.). «Ec Бестиарий: Бестиарий эволюционных, роевых и других алгоритмов, основанных на метафорах». дои : 10.5281/ZENODO.1293035. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  12. ↑ Кудела, Якуб (12 декабря 2022 г.). «Критическая проблема сравнительного анализа и анализа эволюционных методов вычислений». Природный машинный интеллект . 4 (12): 1238–1245. arXiv : 2301.01984 . дои : 10.1038/s42256-022-00579-0. ISSN  2522-5839. S2CID  254616518.
  13. ^ «Биологическая информация». Стэнфордская энциклопедия философии . Лаборатория метафизических исследований Стэнфордского университета. 2016.
  14. ^ Дж. Г. Диас Очоа (2018). «Упругие многомасштабные механизмы: вычисления и биологическая эволюция». Журнал молекулярной эволюции . 86 (1): 47–57. Бибкод : 2018JMolE..86...47D. дои : 10.1007/s00239-017-9823-7. PMID  29248946. S2CID  22624633.
  15. ^ А. Данчин (2008). «Бактерии как компьютеры, создающие компьютеры». ФЭМС Микробиол. Откр. 33 (1): 3–26. дои : 10.1111/j.1574-6976.2008.00137.x. ПМК 2704931 . ПМИД  19016882.  
  16. ^ Бургин, Марк; Эбербах, Евгений (2013). «Рекурсивно сгенерированные эволюционные машины Тьюринга и эволюционные автоматы». В Синь-Ше Ян (ред.). Искусственный интеллект, эволюционные вычисления и метаэвристика . Исследования в области вычислительного интеллекта. Том. 427. Шпрингер-Верлаг. стр. 201–230. дои : 10.1007/978-3-642-29694-9_9. ISBN 978-3-642-29693-2.
  17. ^ Бургин М. и Эбербах Э. (2010) Ограниченные и периодические эволюционные машины, в Proc. Конгресс 2010 г. по эволюционным вычислениям (CEC'2010), Барселона, Испания, 2010 г., стр. 1379-1386.
  18. ^ аб Бургин, М.; Эбербах, Э. (2012). «Эволюционные автоматы: выразительность и сходимость эволюционных вычислений». Компьютерный журнал . 55 (9): 1023–1029. doi : 10.1093/comjnl/bxr099.
  19. ^ Эбербах Э. (2002) О выразительности эволюционных вычислений: является ли EC алгоритмическим?, Proc. 2002 Всемирный конгресс по вычислительному интеллекту WCCI'2002, Гонолулу, Гавайи, 2002, 564–569.
  20. ^ Эбербах, Э. (2005) На пути к теории эволюционных вычислений, BioSystems, т. 82, стр. 1-19.
  21. ^ Эбербах, Юджин; Бургин, Марк (2009). «Эволюционные автоматы как основа эволюционных вычислений: Ларри Фогель был прав». Конгресс IEEE 2009 г. по эволюционным вычислениям . IEEE. стр. 2149–2156. дои : 10.1109/CEC.2009.4983207. ISBN 978-1-4244-2958-5. S2CID  2869386.
  22. ^ Хопкрофт, Дж. Э., Р. Мотвани и Дж. Д. Ульман (2001) Введение в теорию автоматов, языки и вычисления, Аддисон Уэсли, Бостон/Сан-Франциско/Нью-Йорк
  23. ^ Джей Джей Мерело и К. Котта (2007). «Кто является исследователем ЕС с лучшими связями? Анализ центральности сложной сети авторов в эволюционных вычислениях». arXiv : 0708.2021 [cs.CY].