Эволюционные вычисления
| Часть серии о |
| Эволюционная биология |
|---|
 |
В информатике изучающей эволюционные вычисления — это семейство алгоритмов глобальной оптимизации, вдохновленное биологической эволюцией , а также областью искусственного интеллекта и мягких вычислений, эти алгоритмы. С технической точки зрения, они представляют собой семейство средств для решения задач методом проб и ошибок, основанных на совокупности, с метаэвристическим или стохастическим оптимизационным характером.
При эволюционных вычислениях генерируется и итеративно обновляется начальный набор возможных решений. Каждое новое поколение создается путем стохастического удаления менее желательных решений и внесения небольших случайных изменений, а также, в зависимости от метода, смешивания родительской информации. В биологической терминологии популяция растворов подвергается естественному отбору (или искусственному отбору ), мутации и, возможно, рекомбинации . В результате популяция будет постепенно развиваться в сторону увеличения приспособленности , в данном случае выбранной функции приспособленности алгоритма.
Методы эволюционных вычислений позволяют создавать высокооптимизированные решения для широкого спектра задач, что делает их популярными в информатике . Существует множество вариантов и расширений, подходящих для более конкретных семейств задач и структур данных. Эволюционные вычисления также иногда используются в эволюционной биологии как экспериментальная процедура in silico для изучения общих аспектов общих эволюционных процессов.
История
[ редактировать ]Концепция имитации эволюционных процессов для решения проблем возникла еще до появления компьютеров, например, когда Алан Тьюринг предложил метод генетического поиска в 1948 году. [1] Тьюринга B-типа U-машины напоминают примитивные нейронные сети , а связи между нейронами изучались с помощью своего рода генетического алгоритма . Его 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]
- Kalyanmoy Deb
- Кеннет А Де Йонг
- Питер Дж. Флеминг
- Дэвид Б. Фогель
- Стефани Форрест
- Дэвид Э. Голдберг
- Джон Генри Холланд
- Тео Янсен
- Джон Козел
- Збигнев Михалевич
- Мелани Митчелл
- Питер Нордин
- Риккардо Поли
- Инго Рехенберг
- Ханс-Поль Сульфур
Журналы
[ редактировать ]Хотя статьи об эволюционных вычислениях или их использовании пронизывают литературу, несколько журналов посвящены эволюционным вычислениям:
- Evolutionary Computation (журнал) (основан в 1993 г.)
- Искусственная жизнь (журнал) (основан в 1993 г.)
- IEEE Transactions on Evolutionary Computing (основан в 1997 г.)
- Генетическое программирование и развивающиеся машины (основана в 2000 г.)
- Swarm Intelligence (основан в 2007 г.)
- Эволюционный интеллект (основан в 2008 г.)
- Журнал искусственной эволюции и приложений (2008–2010 гг.)
- Memetic Computing (основана в 2009 г.)
- Международный журнал прикладных эволюционных вычислений (основан в 2010 г.)
- Swarm and Evolutionary Computation (основана в 2011 г.)
- Международный журнал роевого интеллекта и эволюционных вычислений (основан в 2012 г.)
Конференции
[ редактировать ]Основные конференции в области эволюционных вычислений включают
- Конференция ACM по генетическим и эволюционным вычислениям (GECCO),
- Конгресс IEEE по эволюционным вычислениям (CEC),
- EvoStar , включающий четыре конференции: EuroGP, EvoApplications, EvoCOP и EvoMUSART,
- Параллельное решение проблем из природы (PPSN).
См. также
[ редактировать ]- Адаптивный многомерный поиск
- Искусственное развитие
- Автоконструктив
- Биология развития
- Цифровой организм
- Оценка алгоритма распределения
- Эволюционная робототехника
- Усовершенствованная антенна
- Приближение фитнеса
- Фитнес-функция
- Фитнес-ландшафт
- Генетические операторы
- Грамматическая эволюция
- Человеческие эволюционные вычисления
- Инференциальное программирование
- Интерактивные эволюционные вычисления
- Список цифровых симуляторов организма
- Мутационное тестирование
- Никаких бесплатных обедов в поиске и оптимизации
- Синтез программы
- Тестовые функции для оптимизации
- Нетрадиционные вычисления
- Универсальный дарвинизм
Внешние ссылки
[ редактировать ]Библиография
[ редактировать ]- Т.е. Бек, Д.Б. Фогель и З. Михалевич (редакторы), Справочник по эволюционным вычислениям , 1997 г., ISBN 0750303921
- Т.е. Бек и Х.-П. Швефель. Обзор эволюционных алгоритмов оптимизации параметров . Архивировано 12 июля 2018 г. в Wayback Machine Evolutionary Computation, 1 (1): 1–23, 1993.
- В. Банцхаф, П. Нордин, Р.Э. Келлер и Ф.Д. Франконе. Генетическое программирование. Введение. Морган Кауфманн, 1998.
- С. Каньони и др., Реальные применения эволюционных вычислений , Конспекты лекций Springer-Verlag по информатике , Берлин, 2000.
- Р. Чионг, Th. Вайзе, З. Михалевич (редакторы), Варианты эволюционных алгоритмов для реальных приложений , Springer , 2012, ISBN 3642234232
- К.А. Де Йонг, Эволюционные вычисления: единый подход. MIT Press , Кембридж, Массачусетс, 2006 г.
- А. Э. Эйбен и Дж. Э. Смит, От эволюционных вычислений к эволюции вещей , Nature, 521:476-482, doi:10.1038/nature14544, 2015 г.
- А. Э. Эйбен и Дж. Э. Смит, «Введение в эволюционные вычисления», Springer, первое издание , 2003 г.; Второе издание , 2015 г.
- Д.Б. Фогель. Эволюционные вычисления. К новой философии машинного интеллекта . IEEE Press, Пискатауэй, Нью-Джерси, 1995.
- Л. Дж. Фогель, Эй. Дж. Оуэнс и М. Дж. Уолш. Искусственный интеллект посредством моделирования эволюции . Нью-Йорк: Джон Уайли, 1966.
- Д.Е. Гольдберг. Генетические алгоритмы в поиске, оптимизации и машинном обучении. Эддисон Уэсли, 1989 год.
- Дж. Х. Холланд. Адаптация в естественных и искусственных системах. Издательство Мичиганского университета , Анн-Арбор, 1975.
- П. Хингстон, Л. Бароне и З. Михалевич (редакторы), Design by Evolution, серия Natural Computing , 2008, Springer , ISBN 3540741097
- Джей Ар Коза. Генетическое программирование: о программировании компьютеров посредством естественной эволюции. MIT Press, Массачусетс, 1992.
- Ф. Дж. Лобо, К. Ф. Лима, З. Михалевич (редакторы), Установка параметров в эволюционных алгоритмах , Springer , 2010, ISBN 3642088929
- З. Михалевич , Генетические алгоритмы + структуры данных – программы эволюции , 1996, Springer , ISBN 3540606769
- З. Михалевич и Д.Б. Фогель, Как решить проблему: современная эвристика , Springer , 2004, ISBN 978-3-540-22494-5
- И. Рехберг. Стратегия эволюции: Оптимизация технических систем в соответствии с принципами биологической эволюции. Fromman-Hozlboog Verlag, Штутгарт, 1973 г. (на немецком языке)
- Х.-П. Швефель. Численная оптимизация компьютерных моделей. John Wiley & Sons, Нью-Йорк, 1981. 1995 – 2-е издание.
- Д. Саймон. Алгоритмы эволюционной оптимизации. Архивировано 10 марта 2014 года в Wayback Machine . Уайли, 2013.
- М. Сиппер; В. Фу; К. Ахуджа; Дж. Х. Мур (2018). «Исследование пространства параметров эволюционных алгоритмов» . Добыча биоданных . 11 :2. дои : 10.1186/s13040-018-0164-x . ПМК 5816380 . ПМИД 29467825 .
- Ю. Чжан; С. Ли. (2017). «PSA: новый алгоритм оптимизации, основанный на правилах выживания porcellio scaber». arXiv : 1709.09840 [ cs.NE ].
Ссылки
[ редактировать ]- ^ Jump up to: а б Эйбен, А.Е.; Смит, Дж. Э. (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 г.
- ^ Бургин, Марк; Эбербах, Евгений (12 апреля 2013 г.). «Эволюционный Тьюринг в контексте эволюционных машин». arXiv : 1304.3762 [ cs.AI ].
- ^ Jump up to: а б с д и Эволюционные вычисления: летопись окаменелостей . Дэвид Б. Фогель. Нью-Йорк: IEEE Press. 1998. ISBN 0-7803-3481-7 . OCLC 38270557 .
{{cite book}}: CS1 maint: другие ( ссылка ) - ^ Фишер, Томас (1986), «Кибернетический системный анализ тканевой фабрики для внедрения автоматизированной системы планирования производства» , DGOR , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 120, номер домена : 10.1007/978-3-642-71161-9_14 , ISBN 978-3-642-71162-6 , получено 6 мая 2022 г.
- ^ Митчелл, Мелани (1998). Введение в генетические алгоритмы . Массачусетский технологический институт Пресс. дои : 10.7551/mitpress/3927.001.0001 . ISBN 978-0-262-28001-3 .
- ^ Барричелли, Нильс Аалл (1954). «Численные примеры эволюционных процессов». Методы : 45–68.
- ^ Фрейзер А.С. (1958). «Анализ генетических моделей методом Монте-Карло». Природа . 181 (4603): 208–9. Бибкод : 1958Natur.181..208F . дои : 10.1038/181208a0 . ПМИД 13504138 . S2CID 4211563 .
- ^ Коза, Джон Р. (1992). Генетическое программирование: о программировании компьютеров посредством естественного отбора . МТИ Пресс . ISBN 978-0-262-11170-6 .
- ^ GC Онвуболу и Б.В. Бабу, Онвуболу, Годфри К.; Бабу, Б.В. (21 января 2004 г.). Новые методы оптимизации в машиностроении . Спрингер. ISBN 9783540201670 . Проверено 17 сентября 2016 г.
- ^ Джамшиди М (2003). «Инструменты интеллектуального управления: нечеткие контроллеры, нейронные сети и генетические алгоритмы». Философские труды Королевского общества А. 361 (1809): 1781–808. Бибкод : 2003RSPTA.361.1781J . дои : 10.1098/rsta.2003.1225 . ПМИД 12952685 . S2CID 34259612 .
- ^ Кампело, Фелипе; Аранья, Клаус (20 июня 2018 г.). «Ec Бестиарий: Бестиарий эволюционных, роевых и других алгоритмов, основанных на метафорах» . дои : 10.5281/ZENODO.1293035 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Кудела, Якуб (12 декабря 2022 г.). «Критическая проблема сравнительного анализа и анализа эволюционных методов вычислений» . Природный машинный интеллект . 4 (12): 1238–1245. arXiv : 2301.01984 . дои : 10.1038/s42256-022-00579-0 . ISSN 2522-5839 . S2CID 254616518 .
- ^ «Биологическая информация» . Стэнфордская энциклопедия философии . Лаборатория метафизических исследований Стэнфордского университета. 2016.
- ^ Дж. Г. Диас Очоа (2018). «Упругие многомасштабные механизмы: вычисления и биологическая эволюция». Журнал молекулярной эволюции . 86 (1): 47–57. Бибкод : 2018JMolE..86...47D . дои : 10.1007/s00239-017-9823-7 . ПМИД 29248946 . S2CID 22624633 .
- ^ А. Данчин (2008). «Бактерии как компьютеры, создающие компьютеры» . ФЭМС Микробиол. Откр. 33 (1): 3–26. дои : 10.1111/j.1574-6976.2008.00137.x . ПМК 2704931 . ПМИД 19016882 .
- ^ Бургин, Марк; Эбербах, Евгений (2013). «Рекурсивно сгенерированные эволюционные машины Тьюринга и эволюционные автоматы». В Синь-Ше Ян (ред.). Искусственный интеллект, эволюционные вычисления и метаэвристика . Исследования в области вычислительного интеллекта. Том. 427. Шпрингер-Верлаг. стр. 201–230. дои : 10.1007/978-3-642-29694-9_9 . ISBN 978-3-642-29693-2 .
- ^ Бургин М. и Эбербах Э. (2010) Ограниченные и периодические эволюционные машины, в Proc. Конгресс 2010 г. по эволюционным вычислениям (CEC'2010), Барселона, Испания, 2010 г., стр. 1379-1386.
- ^ Jump up to: а б Бургин, М.; Эбербах, Э. (2012). «Эволюционные автоматы: выразительность и сходимость эволюционных вычислений». Компьютерный журнал . 55 (9): 1023–1029. дои : 10.1093/comjnl/bxr099 .
- ^ Эбербах Э. (2002) О выразительности эволюционных вычислений: является ли EC алгоритмическим?, Proc. 2002 Всемирный конгресс по вычислительному интеллекту WCCI'2002, Гонолулу, Гавайи, 2002, 564–569.
- ^ Эбербах, Э. (2005) На пути к теории эволюционных вычислений, BioSystems, т. 82, стр. 1-19.
- ^ Эбербах, Юджин; Бургин, Марк (2009). «Эволюционные автоматы как основа эволюционных вычислений: Ларри Фогель был прав». Конгресс IEEE 2009 г. по эволюционным вычислениям . IEEE. стр. 2149–2156. дои : 10.1109/CEC.2009.4983207 . ISBN 978-1-4244-2958-5 . S2CID 2869386 .
- ^ Хопкрофт, Дж. Э., Р. Мотвани и Дж. Д. Ульман (2001) Введение в теорию автоматов, языки и вычисления, Аддисон Уэсли, Бостон/Сан-Франциско/Нью-Йорк
- ^ Джей Джей Мерело и К. Котта (2007). «Кто является исследователем ЕС с лучшими связями? Анализ центральности сложной сети авторов в эволюционных вычислениях». arXiv : 0708.2021 [ cs.CY ].
| Базы данных органов управления : Национальные |
|---|
