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