| Часть серии по |
| Эволюционная биология |
|---|
 |
|
Категория
| Часть серии о |
| Эволюционный алгоритм |
|---|
|
| Генетический алгоритм |
|
| Генетическое программирование |
|
В информатике , эволюционные вычисления представляют собой семейство алгоритмов для глобальной оптимизации вдохновленной биологической эволюции , и подпола искусственного интеллекта и мягких вычислений изучения этих алгоритмов. С технической точки зрения, они представляют собой семейство средств решения проблем методом проб и ошибок, основанных на популяционных методах, с характером метаэвристической или стохастической оптимизации .
При эволюционных вычислениях создается и итеративно обновляется начальный набор возможных решений. Каждое новое поколение создается путем случайного удаления менее желаемых решений и внесения небольших случайных изменений. В биологической терминологии популяция растворов подвергается естественному отбору (или искусственному отбору ) и мутации . В результате популяция будет постепенно развиваться в сторону увеличения приспособленности , в данном случае выбранной функции приспособленности алгоритма.
Методы эволюционных вычислений могут давать высокооптимизированные решения в широком диапазоне задач, что делает их популярными в компьютерных науках . Существует множество вариантов и расширений, подходящих для более конкретных семейств проблем и структур данных. Эволюционные вычисления также иногда используются в эволюционной биологии как экспериментальная процедура 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].
- Калянмой Деб
- Кеннет А Де Йонг
- Питер Дж. Флеминг
- Дэвид Б. Фогель
- Стефани Форрест
- Дэвид Э. Голдберг
- Джон Генри Холланд
- Тео Янсен
- Джон Коза
- Збигнев Михалевич
- Мелани Митчелл
- Питер Нордин
- Риккардо Поли
- Инго Рехенберг
- Ханс-Пауль Швефель
Конференции [ править ]
Основные конференции в области эволюционных вычислений включают:
- Конференция ACM по генетическим и эволюционным вычислениям (GECCO),
- Конгресс IEEE по эволюционным вычислениям (CEC),
- EvoStar , в который входят четыре конференции: EuroGP, EvoApplications, EvoCOP и EvoMUSART,
- Параллельное решение задач с натуры (PPSN).
См. Также [ править ]
- Адаптивный размерный поиск
- Искусственное развитие
- Автоконструктивный
- Биология развития
- Цифровой организм
- Оценка алгоритма распределения
- Эволюционная робототехника
- Развитая антенна
- Приближение фитнеса
- Функция фитнеса
- Фитнес-пейзаж
- Генетические операторы
- Грамматическая эволюция
- Человеческие эволюционные вычисления
- Логическое программирование
- Интерактивные эволюционные вычисления
- Список цифровых симуляторов организма
- Мутационное тестирование
- Никаких бесплатных обедов в поиске и оптимизации
- Программный синтез
- Тестовые функции для оптимизации
- Универсальный дарвинизм
Внешние ссылки [ править ]
- Статья в Стэнфордской энциклопедии философии о биологической информации (на английском языке)
Библиография [ править ]
- Чт. Бек, Д.Б. Фогель и З. Михалевич (редакторы), Справочник по эволюционным вычислениям , 1997 г., ISBN 0750303921
- Чт. Бэк и Х.-П. Schwefel. Обзор эволюционных алгоритмов оптимизации параметров . [ мертвая ссылка ] Эволюционные вычисления, 1 (1): 1-23, 1993.
- W. Banzhaf, P. Nordin, RE Keller и FD Francone. Генетическое программирование - Введение. Морган Кауфманн, 1998.
- С. Каньони и др., Реальные приложения эволюционных вычислений , Лекционные заметки Springer-Verlag по компьютерным наукам , Берлин, 2000.
- R. Chiong, Th. Вайсе, З. Михалевич (редакторы), Варианты эволюционных алгоритмов для реальных приложений , Springer , 2012, ISBN 3642234232
- К. А. Де Йонг, Эволюционные вычисления: унифицированный подход. 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, Пискатауэй, Нью-Джерси, 1995.
- LJ Fogel, AJ Owens и MJ Walsh. Искусственный интеллект посредством моделирования эволюции . Нью-Йорк: Джон Вили, 1966.
- Д. Е. Гольдберг. Генетические алгоритмы в поиске, оптимизации и машинном обучении. Эддисон Уэсли, 1989.
- JH Holland. Адаптация в естественных и искусственных системах. Издательство Мичиганского университета , Анн-Арбор, 1975.
- П. Хингстон, Л. Бароне и З. Михалевич (редакторы), Дизайн Evolution, Natural Computing Series , 2008, Springer , ISBN 3540741097
- JR Koza. Генетическое программирование: программирование компьютеров посредством естественной эволюции. MIT Press, Массачусетс, 1992.
- Ф. Дж. Лобо, К. Ф. Лима, З. Михалевич (редакторы), Установка параметров в эволюционных алгоритмах , Springer , 2010, ISBN 3642088929
- З. Михалевич , Генетические алгоритмы + структуры данных - программы эволюции , 1996, Springer , ISBN 3540606769
- З. Михалевич и Д.Б. Фогель, Как его решить: современная эвристика , Springer , 2004, ISBN 978-3-540-22494-5
- И. Рехенберг. Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution. Fromman-Hozlboog Verlag, Штутгарт, 1973 г. (на немецком языке)
- Х.-П. Schwefel. Численная оптимизация компьютерных моделей. John Wiley & Sons, Нью-Йорк, 1981. 1995 - 2-е издание.
- Д. Саймон. Алгоритмы эволюционной оптимизации . Wiley, 2013.
- М. Сиппер, В. Фу, К. Ахуджа и Дж. Х. Мур (2018). «Исследование пространства параметров эволюционных алгоритмов» . BioData Mining . 11 : 2. DOI : 10,1186 / s13040-018-0164-х . PMC 5816380 . PMID 29467825 .CS1 maint: использует параметр авторов ( ссылка )
- Ю. Чжан и С. Ли. (2017). «PSA: новый алгоритм оптимизации, основанный на правилах выживания porcellio scaber». arXiv : 1709.09840 [ cs.NE ].CS1 maint: использует параметр авторов ( ссылка )
Ссылки [ править ]
- ^ Тейлор, Тим; Дорин, Алан (2020). Восстание самовоспроизводящихся: ранние видения машин, искусственного интеллекта и роботов, которые могут воспроизводиться и развиваться . Чам: Издательство Springer International. DOI : 10.1007 / 978-3-030-48234-3 . ISBN 978-3-030-48233-6. S2CID 220855726 . Выложите резюме .
- ^ Barricelli, Nils Aall (1954). "Esempi Numerici di processi di evoluzione". Methodos : 45-68.
- Перейти ↑ Fraser AS (1958). «Монте-Карло анализ генетических моделей». Природа . 181 (4603): 208–9. Bibcode : 1958Natur.181..208F . DOI : 10.1038 / 181208a0 . PMID 13504138 . S2CID 4211563 .
- ^ Rechenberg, Инго (1973). Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (кандидатская диссертация) (на немецком языке). Фромман-Хольцбуг.
- ^ Голландия, Джон Х. (1975). Адаптация в естественных и искусственных системах . Пресса Мичиганского университета . ISBN 978-0-262-58111-0.
- ^ Коза, Джон Р. (1992). Генетическое программирование: о программировании компьютеров посредством естественного отбора . MIT Press . ISBN 978-0-262-11170-6.
- ^ GC Onwubolu и BV Babu, Onwubolu, Godfrey C .; Бабу Б.В. (21 января 2004 г.). Новые методы оптимизации в машиностроении . ISBN 9783540201670. Проверено 17 сентября 2016 года .
- ^ Jamshidi M (2003). «Инструменты интеллектуального управления: нечеткие контроллеры, нейронные сети и генетические алгоритмы». Философские труды Королевского общества А . 361 (1809): 1781–808. Bibcode : 2003RSPTA.361.1781J . DOI : 10,1098 / rsta.2003.1225 . PMID 12952685 . S2CID 34259612 .
- ^ «Биологическая информация» . Стэнфордская энциклопедия философии . Лаборатория метафизических исследований Стэнфордского университета. 2016 г.
- ^ JG Диас Очоа (2018). «Упругие многомасштабные механизмы: вычисления и биологическая эволюция». Журнал молекулярной эволюции . 86 (1): 47–57. Bibcode : 2018JMolE..86 ... 47D . DOI : 10.1007 / s00239-017-9823-7 . PMID 29248946 . S2CID 22624633 .
- ^ А. Даншен (2008). «Бактерии как компьютеры, делающие компьютеры» . FEMS Microbiol. Откр. 33 (1): 3–26. DOI : 10.1111 / j.1574-6976.2008.00137.x . PMC 2704931 . PMID 19016882 .
- ^ Бургин, Марк; Эбербах, Евгений (2013). «Рекурсивно генерируемые эволюционные машины Тьюринга и эволюционные автоматы». В Синь-Шэ Ян (ред.). Искусственный интеллект, эволюционные вычисления и метаэвристика . Исследования в области вычислительного интеллекта. 427 . Springer-Verlag. С. 201–230. DOI : 10.1007 / 978-3-642-29694-9_9 . ISBN 978-3-642-29693-2.
- ↑ Burgin, M. и Eberbach, E. (2010) Ограниченные и периодические эволюционные машины, в Proc. Конгресс по эволюционным вычислениям 2010 г. (CEC'2010), Барселона, Испания, 2010 г., стр. 1379-1386
- ^ a b Burgin, M .; Эбербах, Э. (2012). «Эволюционные автоматы: выразительность и сходимость эволюционных вычислений». Компьютерный журнал . 55 (9): 1023–1029. DOI : 10.1093 / comjnl / bxr099 .
- ^ Эбербах Э. (2002) О выразительности эволюционных вычислений: является ли EC алгоритмической ?, Proc. 2002 Всемирный конгресс по вычислительному интеллекту WCCI'2002, Гонолулу, Гавайи, 2002, 564-569.
- ↑ Eberbach, E. (2005) К теории эволюционных вычислений, BioSystems, т. 82, стр. 1-19.
- ^ Эбербах, Евгений; Бургин, Марк (2009). «Эволюционные автоматы как основа эволюционных вычислений: Ларри Фогель был прав». 2009 Конгресс IEEE по эволюционным вычислениям . IEEE. С. 2149–2156. DOI : 10,1109 / CEC.2009.4983207 . ISBN 978-1-4244-2958-5. S2CID 2869386 .
- ↑ Hopcroft, JE, R. Motwani, and JD Ullman (2001) Введение в теорию автоматов, языки и вычисления, Аддисон Уэсли, Бостон / Сан-Франциско / Нью-Йорк
- ^ JJ Merelo и С. Котта (2007). «Кто является исследователем ЕС с лучшими связями? Анализ центральности сложной сети авторов в эволюционных вычислениях». arXiv : 0708.2021 [ cs.CY ].
