Эволюционный алгоритм - Evolutionary algorithm
Часть серии о |
Искусственный интеллект |
---|
В вычислительного интеллекта (КИ), эволюционный алгоритм ( EA ) является подмножеством из эволюционных вычислений , общей численности населения на основе метаэвристического оптимизации алгоритма . EA использует механизмы, вдохновленные биологической эволюцией , такие как воспроизводство , мутации , рекомбинация и отбор . Кандидатское решение к задаче оптимизации играет роль особей в популяции, а функция пригодности определяет качество решений (смотрите также функцию потерь ). Затем после повторного применения вышеуказанных операторов происходит эволюция популяции.
Эволюционные алгоритмы часто хорошо приближают решения всех типов проблем, потому что в идеале они не делают никаких предположений о лежащей в основе ландшафте пригодности . Методы эволюционных алгоритмов, применяемые к моделированию биологической эволюции, обычно ограничиваются исследованием микроэволюционных процессов и моделей планирования, основанных на клеточных процессах. В большинстве реальных приложений советников вычислительная сложность является препятствующим фактором. Фактически, эта вычислительная сложность связана с оценкой функции пригодности. Аппроксимация пригодности - одно из решений, позволяющих преодолеть эту трудность. Однако, казалось бы, простой советник может решать часто сложные задачи; следовательно, может не быть прямой связи между сложностью алгоритма и сложностью проблемы.
Реализация
Ниже приводится пример универсального одноцелевого генетического алгоритма .
Шаг первый: создание первоначального населения из индивидуумов в случайном порядке. (Первое поколение)
Шаг второй: повторяйте следующие этапы регенерации до завершения:
- Оцените приспособленность каждого человека в популяции (ограничение по времени, достигнутая пригодность и т. Д.)
- Выберите наиболее приспособленных особей для размножения . (Родители)
- Выращивайте новых особей с помощью операций скрещивания и мутации, чтобы дать потомство .
- Замените наименее приспособленных особей населения новыми особями.
Типы
Подобные методы различаются генетическим представлением и другими деталями реализации, а также характером конкретной прикладной проблемы.
- Генетический алгоритм - это самый популярный тип советников. Решение проблемы ищется в виде цепочек чисел (традиционно двоичных, хотя наилучшими представлениями обычно являются те, которые отражают что-то о решаемой проблеме), применяя такие операторы, как рекомбинация и мутация (иногда один, иногда оба) . Советник этого типа часто используется в задачах оптимизации .
- Генетическое программирование - здесь решения представлены в виде компьютерных программ, и их пригодность определяется их способностью решать вычислительную задачу. Существует множество вариантов генетического программирования, включая декартово генетическое программирование , программирование экспрессии генов , грамматическую эволюцию , линейное генетическое программирование , программирование множественных выражений и т. Д.
- Эволюционное программирование - похоже на генетическое программирование, но структура программы фиксирована, а ее числовые параметры могут изменяться.
- Стратегия эволюции - работает с векторами действительных чисел как с представлениями решений и обычно использует самоадаптивные скорости мутации.
- Дифференциальная эволюция - основана на векторных различиях и поэтому в первую очередь подходит для задач численной оптимизации .
- Нейроэволюция - похоже на генетическое программирование, но геномы представляют собой искусственные нейронные сети, описывая структуру и веса связей. Кодирование генома может быть прямым или косвенным.
- Система обучающих классификаторов - здесь решение представляет собой набор классификаторов (правил или условий). Michigan-LCS развивается на уровне отдельных классификаторов, тогда как Pittsburgh-LCS использует совокупности наборов классификаторов. Первоначально классификаторы были только двоичными, но теперь они включают реальные типы, типы нейронной сети или S-выражения . Пригодность обычно определяется с помощью обучения с подкреплением на основе силы или точности или обучения с учителем .
Сравнение с биологическими процессами
Возможным ограничением многих эволюционных алгоритмов является отсутствие четких различий между генотипом и фенотипом . В природе оплодотворенная яйцеклетка претерпевает сложный процесс, известный как эмбриогенез, чтобы стать зрелым фенотипом . Считается, что это косвенное кодирование делает генетический поиск более надежным (т.е. снижает вероятность фатальных мутаций), а также может улучшить эволюционируемость организма. Такие косвенные (также известные как генеративные или связанные с развитием) кодирования также позволяют эволюции использовать регулярность окружающей среды. Недавние работы в области искусственного эмбриогенеза или искусственных систем развития направлены на решение этих проблем. И экспрессия генов программирования успешно исследует систему генотип-фенотип, где генотип состоит из линейных мультигенных хромосом фиксированной длины и фенотип состоит из нескольких деревьев выражений или компьютерных программ , различных размеров и форм.
Связанные методы
Алгоритмы Swarm включают
- Оптимизация муравьиной колонии основана на идее поиска пищи муравьями с помощью феромонной коммуникации для формирования тропинок. В первую очередь подходит для комбинаторной оптимизации и задач с графами .
- Алгоритм "бегун-корень" (RRA) основан на функции побегов и корней растений в природе.
- Алгоритм искусственной пчелиной колонии основан на поведении медоносных пчел при кормлении. В первую очередь предлагается для численной оптимизации и расширен для решения задач комбинаторной, ограниченной и многокритериальной оптимизации.
- Алгоритм пчел основан на поведении медоносных пчел при кормлении. Он применялся во многих приложениях, таких как маршрутизация и планирование.
- Поиск кукушки вдохновлен задумчивым паразитизмом видов кукушек . Он также использует полеты Леви и поэтому подходит для задач глобальной оптимизации .
- Оптимизация роя частиц основана на идеях поведения стаи животных. Также в первую очередь подходит для задач численной оптимизации .
Другие популяционные метаэвристические методы
- Охотничий поиск - метод, вдохновленный групповой охотой на некоторых животных, таких как волки, которые организуют свою позицию, чтобы окружить добычу, каждое из них относительно положения других, и особенно положения их лидера. Это метод непрерывной оптимизации, адаптированный как метод комбинаторной оптимизации.
- Адаптивный размерный поиск - в отличие от метаэвристических методов, вдохновленных природой, алгоритм адаптивного размерного поиска не реализует никаких метафор в качестве основного принципа. Скорее, он использует простой ориентированный на производительность метод, основанный на обновлении параметра коэффициента размерности поиска (SDR) на каждой итерации.
- Алгоритм Firefly основан на поведении светлячков, которые привлекают друг друга мигающим светом. Это особенно полезно для мультимодальной оптимизации.
- Поиск гармонии - основан на представлениях о поведении музыкантов в поисках лучших гармоний. Этот алгоритм подходит как для комбинаторной оптимизации, так и для оптимизации параметров.
- Адаптация по Гауссу - на основе теории информации. Используется для максимизации выхода продукции, средней пригодности или средней информации . См., Например, энтропию в термодинамике и теории информации .
- Меметический алгоритм . Гибридный метод, вдохновленный идеей Ричарда Докинза о меме, он обычно принимает форму популяционного алгоритма в сочетании с индивидуальными процедурами обучения, способными выполнять локальные уточнения. Подчеркивает использование специфических для проблемы знаний и пытается организовать локальный и глобальный поиск синергетическим образом.
Примеры
В 2020 году Google заявил, что их AutoML-Zero может успешно заново открыть для себя классические алгоритмы, такие как концепция нейронных сетей.
Компьютерное моделирование Tierra и Avida пытается смоделировать макроэволюционную динамику.
Галерея
Двухпопуляционный поиск EA по ограниченной функции Розенброка с ограниченным глобальным оптимумом.
Двухпопуляционный поиск EA по ограниченной функции Розенброка . Глобальный оптимум не ограничен.
Двухпопуляционный поиск ограниченного оптимума функции Симионеску с помощью EA .
использованная литература
внешние ссылки
Библиография
- Эшлок, Д. (2006), Эволюционные вычисления для моделирования и оптимизации , Springer, ISBN 0-387-22196-4 .
- Бэк Т. (1996), Эволюционные алгоритмы в теории и практике: стратегии эволюции, эволюционное программирование, генетические алгоритмы , Oxford Univ. Нажмите.
- Бек Т., Фогель Д., Михалевич З. (1997), Справочник по эволюционным вычислениям , Oxford Univ. Нажмите.
- Банцаф В., Нордин П., Келлер Р., Франкоун Ф. (1998), Генетическое программирование - Введение , Морган Кауфманн, Сан-Франциско
- Эйбен, А.Е., Смит, Д.Е. (2003), Введение в эволюционные вычисления , Springer.
- Холланд, Дж. Х. (1992), Адаптация в естественных и искусственных системах , Издательство Мичиганского университета, Анн-Арбор
- Михалевич З., Фогель ДБ (2004). Как это решить: современная эвристика, Springer.
- Бенко, Аттила; Доса, Дьердь; Туза, Жолт (2010). «Упаковка / закрытие бункеров с доставкой, решаемая эволюцией алгоритмов». 2010 Пятая международная конференция IEEE по биоинженерным вычислениям: теории и приложения (BIC-TA) . С. 298–302. DOI : 10.1109 / BICTA.2010.5645312 . ISBN 978-1-4244-6437-1. S2CID 16875144 .
- Poli, R .; Лэнгдон, ВБ; Макфи, Н.Ф. (2008). Полевое руководство по генетическому программированию . Lulu.com, свободно доступный в Интернете. ISBN 978-1-4092-0073-4. Архивировано из оригинала на 2016-05-27 . Проверено 5 марта 2011 .
- Прайс, К., Сторн, Р.М., Лампинен, Дж. А. (2005). «Дифференциальная эволюция: практический подход к глобальной оптимизации» , Спрингер.
- Инго Рехенберг (1971): Стратегия эволюции - Оптимизация технической системы на принципах биологической эволюции (кандидатская диссертация). Перепечатано Фромман-Хольцбугом (1973).
- Ханс-Пауль Швефель (1974): Numerische Optimierung von Computer-Modellen (докторская диссертация). Перепечатано Биркхойзером (1977).
- Саймон Д. (2013): Алгоритмы эволюционной оптимизации , Wiley.
- Вычислительный интеллект: методологическое введение Крузе, Боргельта, Клавона, Моуэса, Штайнбрехера, Хельда, 2013 г., Springer, ISBN 978-1-4471-5012-1
- Rahman, Rosshairy Abd .; Кендалл, Грэм; Рамли, Разамин; Джамари, Зайноддин; Ку-Махамуд, Ку Рухана (2017). «Составление корма для креветок с помощью эволюционного алгоритма с эвристикой мощности для обработки ограничений» . Сложность . 2017 : 1–12. DOI : 10.1155 / 2017/7053710 .