Эволюционные вычисления - Evolutionary computation
Часть серии по |
Эволюционная биология |
---|
В информатике , эволюционные вычисления представляют собой семейство алгоритмов для глобальной оптимизации вдохновленной биологической эволюции , и подпола искусственного интеллекта и мягких вычислений изучения этих алгоритмов. С технической точки зрения, они представляют собой семейство средств решения проблем методом проб и ошибок, основанных на популяционных методах, с характером метаэвристической или стохастической оптимизации .
При эволюционных вычислениях создается и итеративно обновляется начальный набор возможных решений. Каждое новое поколение создается путем случайного удаления менее желаемых решений и внесения небольших случайных изменений. В биологической терминологии популяция растворов подвергается естественному отбору (или искусственному отбору ) и мутации . В результате популяция будет постепенно развиваться в сторону увеличения приспособленности , в данном случае выбранной функции приспособленности алгоритма.
Методы эволюционных вычислений могут давать высокооптимизированные решения в широком диапазоне задач, что делает их популярными в информатике . Существует множество вариантов и расширений, подходящих для более конкретных семейств проблем и структур данных. Эволюционные вычисления также иногда используются в эволюционной биологии как экспериментальная процедура in silico для изучения общих аспектов общих эволюционных процессов.
История
Использование эволюционных принципов для автоматического решения проблем зародилось в 1950-х годах. Только в 1960-х годах три различных интерпретации этой идеи начали развиваться в трех разных местах.
Эволюционное программирование было введено Лоуренсом Дж. Фогелем в США, а Джон Генри Холланд назвал свой метод генетическим алгоритмом . В Германии Инго Рехенберг и Ханс-Пауль Швефель представили стратегии эволюции . Эти направления развивались отдельно около 15 лет. С начала девяностых годов они объединены как разные представители («диалекты») одной технологии, называемой эволюционными вычислениями . Также в начале девяностых появилось четвертое направление, следующее за общими идеями, - генетическое программирование . С 1990-х годов природные алгоритмы становятся все более важной частью эволюционных вычислений.
Эти термины обозначают область эволюционных вычислений и рассматривают эволюционное программирование, стратегии эволюции, генетические алгоритмы и генетическое программирование как подобласти.
Самое раннее компьютерное моделирование эволюции с использованием эволюционных алгоритмов и методов искусственной жизни было выполнено Нильсом Аллом Барричелли в 1953 году, а первые результаты были опубликованы в 1954 году. Еще одним пионером 1950-х годов был Алекс Фрейзер , опубликовавший серию статей по моделированию искусственного отбора . Искусственная эволюция стала широко признанным методом оптимизации в результате работы Инго Рехенберга в 1960-х и начале 1970-х годов, который использовал стратегии эволюции для решения сложных инженерных задач. В частности, генетические алгоритмы стали популярными благодаря трудам Джона Холланда . По мере роста академического интереса резкое увеличение мощности компьютеров сделало возможным практическое применение, включая автоматическое развитие компьютерных программ. Эволюционные алгоритмы теперь используются для решения многомерных задач более эффективно, чем программное обеспечение, созданное людьми-разработчиками, а также для оптимизации проектирования систем.
Методы
Методы эволюционных вычислений в основном включают алгоритмы метаэвристической оптимизации . Вообще говоря, это поле включает:
- Агентное моделирование
- Оптимизация колонии муравьев
- Искусственная иммунная система
- Искусственная жизнь (см. Также цифровой организм )
- Культурные алгоритмы
- Дифференциальная эволюция
- Двухфазная эволюция
- Оценка алгоритмов распределения
- Эволюционные алгоритмы
- Эволюционное программирование
- Стратегия эволюции
- Программирование экспрессии генов
- Генетический алгоритм
- Генетическое программирование
- Грамматическая эволюция
- Обучаемая модель эволюции
- Системы обучающих классификаторов
- Меметические алгоритмы
- Нейроэволюция
- Оптимизация роя частиц
- Самоорганизация, такая как самоорганизующиеся карты , соревновательное обучение
- Рой интеллект
Эволюционные алгоритмы
Эволюционные алгоритмы образуют подмножество эволюционных вычислений, поскольку они обычно включают только методы, реализующие механизмы, вдохновленные биологической эволюцией, такие как воспроизводство , мутация , рекомбинация , естественный отбор и выживание наиболее приспособленных . Возможные решения проблемы оптимизации играют роль отдельных лиц в популяции, а функция стоимости определяет среду, в которой решения «живут» (см. Также функцию приспособленности ). Затем после повторного применения вышеуказанных операторов происходит эволюция популяции.
В этом процессе есть две основные силы, которые составляют основу эволюционных систем: рекомбинационная мутация и кроссовер создают необходимое разнообразие и тем самым способствуют новизне, в то время как отбор действует как сила, повышающая качество.
Многие аспекты такого эволюционного процесса являются стохастическими . Части информации, измененные из-за рекомбинации и мутации, выбираются случайным образом. С другой стороны, операторы выбора могут быть детерминированными или стохастическими. В последнем случае люди с более высокой подготовкой имеют больше шансов быть отобраны, чем люди с более низкой подготовкой , но обычно даже у слабых людей есть шанс стать родителями или выжить.
Эволюционные алгоритмы и биология
Генетические алгоритмы предоставляют методы для моделирования биологических систем и системной биологии , которые связаны с теорией динамических систем , поскольку они используются для прогнозирования будущих состояний системы. Это просто яркий (но, возможно, вводящий в заблуждение) способ привлечь внимание к упорядоченному, хорошо контролируемому и высоко структурированному характеру развития в биологии.
Однако использование алгоритмов и информатики, в частности теории вычислений , помимо аналогии с динамическими системами, также важно для понимания самой эволюции.
Эта точка зрения имеет достоинство признания отсутствия централизованного контроля за развитием; организмы развиваются в результате локальных взаимодействий внутри клеток и между ними. Наиболее многообещающие идеи о параллелях разработки программ кажутся нам теми, которые указывают на очевидную близкую аналогию между процессами внутри клеток и низкоуровневой работой современных компьютеров. Таким образом, биологические системы подобны вычислительным машинам, которые обрабатывают входную информацию для вычисления следующих состояний, так что биологические системы ближе к вычислению, чем классическая динамическая система.
Кроме того, следуя концепциям теории вычислений , микропроцессы в биологических организмах принципиально неполны и неразрешимы ( полнота (логика) ), подразумевая, что «за аналогией между клетками и компьютерами стоит нечто большее, чем грубая метафора.
Аналогия с вычислением распространяется также на отношения между системами наследования и биологической структурой, которые, как часто думают, раскрывают одну из самых насущных проблем в объяснении происхождения жизни.
Эволюционные автоматы , обобщение эволюционных машин Тьюринга , были введены для более точного исследования свойств биологических и эволюционных вычислений. В частности, они позволяют получить новые результаты по выразительности эволюционных вычислений. Это подтверждает первоначальный результат о неразрешимости естественной эволюции и эволюционных алгоритмов и процессов. Эволюционные конечные автоматы , простейший подкласс эволюционных автоматов, работающих в терминальном режиме, могут принимать произвольные языки по заданному алфавиту, включая нерекурсивно перечислимые (например, язык диагонализации) и рекурсивно перечисляемые, но не рекурсивные языки (например, язык универсальной машины Тьюринга). ).
Известные практики
Список активных исследователей, естественно, динамичен и не является исчерпывающим. Сетевой анализ сообщества был опубликован в 2007 году.
- Калянмой Деб
- Кеннет А Де Йонг
- Питер Дж. Флеминг
- Дэвид Б. Фогель
- Стефани Форрест
- Дэвид Э. Голдберг
- Джон Генри Холланд
- Тео Янсен
- Джон Коза
- Збигнев Михалевич
- Мелани Митчелл
- Питер Нордин
- Риккардо Поли
- Инго Рехенберг
- Ханс-Пауль Швефель
Конференции
Основные конференции в области эволюционных вычислений включают:
- Конференция 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: использует параметр авторов ( ссылка )
Рекомендации