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

Для журнала см. Эволюционные вычисления (журнал).
Часть серии по
Эволюционная биология
Зяблики Дарвина, автор Gould.jpg

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

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

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

История

Использование эволюционных принципов для автоматического решения проблем возникло в 1950-х годах. Лишь в 1960-х годах три различных интерпретации этой идеи начали развиваться в трех разных местах.

Эволюционное программирование был представлен Лоуренс Дж. Фогель в США, а Джон Генри Холланд назвал свой метод генетический алгоритм. В Германии Инго Рехенберг и Ханс-Пауль Швефель представил стратегии эволюции. Эти направления развивались отдельно около 15 лет. С начала девяностых годов они объединяются как разные представители («диалекты») одной технологии, называемые эволюционные вычисления. Также в начале девяностых появился четвертый поток, следующий за общими идеями - генетическое программирование. С 1990-х годов природные алгоритмы становятся все более важной частью эволюционных вычислений.

Эти термины обозначают область эволюционных вычислений и рассматривают эволюционное программирование, стратегии эволюции, генетические алгоритмы и генетическое программирование как под-области.

Самые ранние компьютерные моделирование эволюция с помощью эволюционные алгоритмы и искусственная жизнь техники были выполнены Нильс Алл Барричелли в 1953 г.,[1] первые результаты были опубликованы в 1954 г.[2] Еще одним пионером 1950-х годов был Алекс Фрейзер, опубликовавший серию работ по моделированию искусственный отбор.[3] Искусственная эволюция стал широко признанным методом оптимизации в результате работы Инго Рехенберг в 1960-х и начале 1970-х годов, которые использовали стратегии эволюции для решения сложных инженерных задач.[4] Генетические алгоритмы в частности стал популярным благодаря написанию Джон Холланд.[5] По мере роста академического интереса резкое увеличение мощности компьютеров сделало возможным практическое применение, включая автоматическое развитие компьютерных программ.[6] Эволюционные алгоритмы теперь используются для решения многомерных задач более эффективно, чем программное обеспечение, созданное людьми-разработчиками, а также для оптимизации проектирования систем.[7][8]

Методы

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

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

Основная статья: Эволюционный алгоритм

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

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

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

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

Основная статья: Эволюционный алгоритм

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

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

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

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

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

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

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

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

Конференции

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

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

внешняя ссылка

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

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

  1. ^ Тейлор, Тим; Дорин, Алан (2020). Восстание саморепликаторов: ранние представления о машинах, искусственном интеллекте и роботах, которые могут воспроизводиться и развиваться. Чам: Издательство Springer International. Дои:10.1007/978-3-030-48234-3. ISBN  978-3-030-48233-6. S2CID  220855726. Сложить резюме.
  2. ^ Барричелли, Нильс Алл (1954). "Esempi Numerici di processi di evoluzione". Методосы: 45–68.
  3. ^ Фрейзер А.С. (1958). «Монте-Карло анализ генетических моделей». Природа. 181 (4603): 208–9. Bibcode:1958Натура.181..208F. Дои:10.1038 / 181208a0. PMID  13504138. S2CID  4211563.
  4. ^ Рехенберг, Инго (1973). Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (кандидатская диссертация) (на немецком). Фромман-Хольцбуг.
  5. ^ Голландия, Джон Х. (1975). Адаптация в естественных и искусственных системах. Пресса Мичиганского университета. ISBN  978-0-262-58111-0.
  6. ^ Коза, Джон Р. (1992). Генетическое программирование: программирование компьютеров посредством естественного отбора. MIT Press. ISBN  978-0-262-11170-6.
  7. ^ Г. К. Онвуболу и Б. В. Бабу, Onwubolu, Godfrey C .; Бабу Б.В. (21 января 2004 г.). Новые методы оптимизации в машиностроении. ISBN  9783540201670. Получено 17 сентября, 2016.
  8. ^ Джамшиди М (2003). «Инструменты интеллектуального управления: нечеткие контроллеры, нейронные сети и генетические алгоритмы». Философские труды Королевского общества A. 361 (1809): 1781–808. Bibcode:2003RSPTA.361.1781J. Дои:10.1098 / rsta.2003.1225. PMID  12952685. S2CID  34259612.
  9. ^ «Биологическая информация». Стэнфордская энциклопедия философии. Лаборатория метафизических исследований Стэнфордского университета. 2016 г.
  10. ^ J.G. Диас Очоа (2018). «Упругие многомасштабные механизмы: вычисления и биологическая эволюция». Журнал молекулярной эволюции. 86 (1): 47–57. Bibcode:2018JMolE..86 ... 47D. Дои:10.1007 / s00239-017-9823-7. PMID  29248946. S2CID  22624633.
  11. ^ А. Данчин (2008). «Бактерии как компьютеры, делающие компьютеры». FEMS Microbiol. Ред. 33 (1): 3–26. Дои:10.1111 / j.1574-6976.2008.00137.x. ЧВК  2704931. PMID  19016882.
  12. ^ Бургин, Марк; Эбербах, Юджин (2013). «Рекурсивно генерируемые эволюционные машины Тьюринга и эволюционные автоматы». В Синь-Шэ Ян (ред.). Искусственный интеллект, эволюционные вычисления и метаэвристика. Исследования в области вычислительного интеллекта. 427. Springer-Verlag. С. 201–230. Дои:10.1007/978-3-642-29694-9_9. ISBN  978-3-642-29693-2.
  13. ^ Бургин М., Эбербах Э. (2010) Ограниченные и периодические эволюционные машины, в сб. Конгресс по эволюционным вычислениям 2010 г. (CEC'2010), Барселона, Испания, 2010 г., стр. 1379-1386
  14. ^ а б Burgin, M .; Эбербах, Э. (2012). «Эволюционные автоматы: выразительность и сходимость эволюционных вычислений». Компьютерный журнал. 55 (9): 1023–1029. Дои:10.1093 / comjnl / bxr099.
  15. ^ Эбербах Э. (2002) О выразительности эволюционных вычислений: алгоритмична ли EC ?, Proc. 2002 Всемирный конгресс по вычислительному интеллекту WCCI’2002, Гонолулу, Гавайи, 2002, 564-569.
  16. ^ Эбербах, Э. (2005) К теории эволюционных вычислений, BioSystems, т. 82, стр. 1-19.
  17. ^ Эбербах, Евгений; Бургин, Марк (2009). «Эволюционные автоматы как основа эволюционных вычислений: Ларри Фогель был прав». 2009 IEEE Конгресс по эволюционным вычислениям. IEEE. С. 2149–2156. Дои:10.1109 / CEC.2009.4983207. ISBN  978-1-4244-2958-5. S2CID  2869386.
  18. ^ Хопкрофт, Дж. Э., Р. Мотвани и Дж. Д. Ульман (2001) Введение в теорию автоматов, языки и вычисления, Аддисон Уэсли, Бостон / Сан-Франциско / Нью-Йорк
  19. ^ J.J. Мерело и К. Котта (2007). «Кто является исследователем ЕС с лучшими связями? Анализ центральности сложной сети авторов в эволюционных вычислениях». arXiv:0708.2021 [cs.CY ].