В области искусственного интеллекта эволюционный алгоритм (ЭА) является подмножеством из вычислений общего количества населения на основе метаэвристической оптимизации. ЭА использует механизмы, вдохновленные биологическим развитием, такие как размножение, мутация, рекомбинация и отбор. Кандидатское решение в задаче эволюционных алгоритмов оптимизации играет роль индивидов в популяции. А также функция пригодности определяет качество ответов.
Эволюционные алгоритмы часто хорошо аппроксимируют решения всех типов проблем. Потому что в идеале они не делают каких-либо предположений о базовом фитнес-ландшафте. Методы, применяемые для эволюционного моделирования и генетических алгоритмов, обычно ограничиваются исследованиями микроэволюционных процессов и моделями планирования, основанными на клеточных этапах. В большинстве реальных приложений советников сложность вычислений является фактором запрещающим.
Фактически эта проблема связана с оценкой фитнес-функции. Фитнес-аппроксимация является одним из решений для преодоления этой трудности. Однако, казалось бы, простой ЭА может решить часто сложные проблемы. Следовательно, не может быть прямой связи между сложностью последовательности и проблемы. Более подробно можно прочитать в книгах «Эволюционные алгоритмы».
Реализация
Шаг первый - создание первоначального населения из индивидуумов в случайном порядке.
Шаг второй - оценка пригодности каждого индивидуума в этой группе (ограничение по времени, достаточная подготовленность и т. д.).
Шаг третий - повторение следующих пунктов регенерации до завершения:
- Выбрать наиболее подходящих людей для размножения (родители).
- Вывести новых особей, которые прошли эволюционный алгоритм c помощью кроссовера и мутации, чтобы получить потомство.
- Оценить индивидуальную пригодность новых людей.
- Заменить наименее приспособленное население ими.
Типы
Генетический алгоритм — это эволюционная последовательность, самый популярный тип советника. Ищется решение проблемы в виде строк чисел (традиционно двоичных, хотя наилучшими представлениями обычно являются те, которые отражают большее в решаемой задаче) путем применения таких операторов, как рекомбинация и мутация (иногда одного, в отдельных случаях обоих). Этот тип советника часто используется в задачах оптимизации. Другое название для этого — fetura (от латинского «рождение»):
- Генетическое программирование. В нем решения представлены в виде компьютерных кодов, и их пригодность определяется способностью выполнять вычислительные задачи.
- Эволюционное программирование. Аналогично эволюционно генетическому алгоритму, но структура фиксирована и ее числовые параметры могут изменяться.
- Программирование экспрессии генов. Развивает компьютерные приложения, но исследует систему генотип-фенотип, где проекты разных размеров кодируются в линейных хромосомах фиксированной длины.
- Стратегия. Работает с векторами действительных чисел как представлениями решений. Обычно использует самоадаптивные эволюционные алгоритмы скорости мутаций.
- Дифференциальное развитие. Создано на основе векторных разностей и, следовательно, в первую очередь подходит для задач численной оптимизации.
- Нейроэволюция. Аналогично эволюционному программированию и генетическим алгоритмам. Но последние представляют собой искусственные нейронные сети, описывая структуру и вес соединений. Кодировка генома может быть прямой или косвенной.
Сравнение с биологическими процессами
Возможное ограничение многих эволюционных алгоритмов — отсутствие четкого различия между генотипом и фенотипом. В природе оплодотворенная яйцеклетка подвергается сложному процессу, известному как эмбриогенез, чтобы стать зрелой. Считается, что это косвенное кодирование делает генетический поиск более надежным (то есть уменьшает вероятность фатальных мутаций), а также может улучшить способность организма развиваться. Такие косвенные (иначе говоря, порождающие или развивающие) кодировки также позволяют эволюции эксплуатировать регулярность в окружающей среде.
Последние работы в области искусственного эмбриогенеза или системы развития стремятся решить эти проблемы. При программировании экспрессии генов успешно исследуется область генотип-фенотипа, где первый состоит из линейных мультигенных хромосом фиксированной длины, а второй из множества деревьев экспрессии или компьютерных программ различных размеров и форм.
Связанные техники
Алгоритмы включают в себя:
- Оптимизацию колонии муравьев. Она основана на идеях поиска пищи насекомыми с помощью связи с феромонами для формирования путей. В первую очередь подходит для комбинаторной оптимизации и задач с графами.
- Алгоритм бегунка-корня. Создатель был вдохновлен функцией корней растений в природе.
- Алгоритм искусственных пчелосемей. Основан на поведении медоносных пчел. В первую очередь предлагается для численной оптимизации и расширен для решения комбинаторных, ограниченных и многоцелевых задач. Алгоритм пчел основан на фуражирующем поведении насекомых. Он был применен во многих приложениях, таких как маршрутизация и планирование.
- Оптимизация роя частиц — на основе идей поведения стада животных. И также в первую очередь подходит для задач численного процесса.
Другие популяционные метаэвристические методы
- Охотничий поиск. Метод, основанный на групповой ловле некоторыми животными, таких как, например, волки, которые распределяют свои обязанности, чтобы окружить добычу. Каждые из членов эволюционного алгоритма относятся к другим каким-либо образом. Особенно это касается вожака. Это метод непрерывной оптимизации, адаптированный как способ комбинаторного процесса.
- Поиск по измерениям. В отличие от метаэвристических методов, основанных на природе, алгоритм по адаптивным процессам не использует метафору в качестве основного принципа. Скорее он применяет простой ориентированный на производительность метод, основанный на обновлении параметра отношения размерности поиска на каждой итерации. Алгоритм Firefly вдохновлен поведением светлячков, притягивающих друг друга мигающим светом. Это особенно полезно для мультимодальной оптимизации.
- Поиск гармонии. Основан на идеях поведения музыкантов. В данном случае эволюционные алгоритмы — это способ, который подходит для комбинаторной оптимизации.
- Гауссовская адаптация. На основе теории информации. Используется для максимизации производительности и средней пригодности. Пример эволюционных алгоритмов в данной ситуации: энтропия в термодинамике и теории информации.
Меметический
Гибридный метод, основанный на идее Ричарда Докинза о меме. Он обычно принимает форму алгоритма на основе совокупности в сочетании с индивидуальными процедурами обучения, способными выполнять локальные уточнения. Подчеркивает использование проблемно-специфических знаний и пытается организовать точеный и глобальный поиск синергетическим способом.
Эволюционные алгоритмы представляют собой эвристический подход к проблемам, которые не могут быть легко решены за полиномиальное время, таких как классически NP-сложные задачи и все остальное, что займет слишком много для исчерпывающей обработки. При самостоятельном использовании они обычно применяются для комбинаторных задач. Однако генетические алгоритмы часто употребляются в тандеме с другими методами, действуя как быстрый способ нахождения несколько оптимальных начальных мест для работы.
Предпосылка эволюционного алгоритма (известного как советник) довольно проста, учитывая, что вы знакомы с процессом естественного отбора. Она содержит четыре основных этапа:
- инициализация;
- выбор;
- генетические операторы;
- завершение.
Каждый из этих шагов примерно соответствует определенному аспекту естественного отбора и предоставляет простые способы модульной реализации этой категории алгоритмов. Проще говоря, в ЭА более приспособленные члены выживут и размножатся, в то время как непригодные участники умрут и не внесут свой вклад в генофонд последующих поколений.
Инициализация
Чтобы начать алгоритм, необходимо сначала создать совокупность решений. Население будет содержать произвольное количество возможных постановлений проблемы, часто называемых участниками. Они часто создаются случайным образом (в рамках ограничений задачи) или, если известны некоторые предварительные знания, ориентировочно сосредоточены вокруг того, который считается идеальным. Важно, чтобы популяция охватывала широкий спектр решений, потому что она, по существу, представляет собой генофонд. Следовательно, если необходимо исследовать множество различных возможностей в рамках алгоритма, нужно стремиться иметь много разных генов.
Выбор
После того как популяция создана, ее члены должны теперь оцениваться в соответствии с функцией пригодности. Фитнес-функция принимает характеристики члена и выдает числовое представление о том, насколько он жизнеспособен. Их создание часто может быть очень трудным. Важно найти хорошую систему, которая точно представляет данные. Это очень специфично для проблемы. Теперь необходимо рассчитывать пригодность всех участников и отбирать часть лучших членов.
Несколько целевых функций
Советники также могут быть расширены для использования данных систем. Это несколько усложняет процесс, потому что, вместо того чтобы идентифицировать одну оптимальную точку, получается набор при их использовании. Множество решений называется границей Парето и содержит элементы, которые одинаково пригодны в том смысле, что ни одно из них не доминирует над любым другим.
Генетические операторы
Этот шаг включает в себя два подэтапа: кроссовер и мутация. После выбора лучших членов (обычно 2 верхних, но это число может варьироваться), они теперь используются для создания следующего поколения в алгоритме. Применяя характеристики выбранных родителей, создаются новые дети, которые представляют собой смесь качеств. Это часто может быть затруднено в зависимости от типа данных, но обычно в комбинаторных задачах вполне реально смешивать и выводить действительные комбинации.
Теперь необходимо ввести новый генетический материал в поколение. Если не сделать этого важного шага, то ученый очень быстро застрянет в локальных экстремумах и не получит оптимальных результатов. Этот шаг является мутацией, и делается он довольно просто, изменяя небольшую часть детей таким образом, чтобы они преимущественно не отражали подмножеств генов родителей. Мутация обычно происходит вероятностно, поскольку возможность того, что ребенок ее получит, а также ее серьезность, определяются распределением.
Прекращение
В конце концов алгоритм должен закончиться. Обычно это происходит в двух случаях: либо он достиг некоторого максимального времени выполнения, либо порога производительности. На этом этапе окончательное решение выбирается и возвращается.
Пример эволюционных алгоритмов
Теперь, чтобы проиллюстрировать результат этого процесса, необходимо просмотреть советника в действии. Для этого можно вспомнить, как несколько поколений динозавров учились ходить (постепенно осваивая сушу), оптимизируя структуру своего тела и прикладывая мышечные силы. Несмотря на то что рептилии раннего поколения не могли ходить, советник смог со временем эволюционировать их посредством мутации и кроссовера в форму, способную ходить.
Данные алгоритмы становятся все более актуальными в современном мире, поскольку решения на их основе все шире используются в таких отраслях, как цифровой маркетинг, финансы и здравоохранение.
Где используются ЭА?
В более широком смысле эволюционные алгоритмы применяются в самых разных приложениях, таких как обработка изображений, маршрутизация транспортных средств, оптимизация мобильной связи, разработка программного обеспечения и даже обучение искусственным нейронным сетям. Эти инструменты лежат в основе многих приложений и веб-сайтов, которые люди используют ежедневно, включая Google Maps и даже такие игры, как The Sims. Кроме того, медицинская сфера использует ЭА для помощи в принятии клинических решений относительно лечения рака. На самом деле эволюционные алгоритмы настолько надежны, что их можно использовать для решения практически любых задач оптимизации.
Закон Мура
Растущая распространенность ЭО обусловлена двумя основными факторами: доступной вычислительной мощностью и накоплением больших наборов данных. Первый может быть описан Законом Мура, который, по сути, гласит, что объем вычислительной мощности компьютера удваивается примерно каждые два года. Этот прогноз держится на протяжении десятилетий. Второй фактор связан с растущей зависимостью от технологий, которая позволяет учреждениям собирать невероятно большое количество данных, что дозволяет им анализировать тенденции и оптимизировать продукты.
Как эволюционные алгоритмы могут помочь маркетологам?
Конъюнктура рынка быстро меняется и очень конкурентоспособна. Это заставило менеджеров по маркетингу соперничать за счет лучшего принятия решений. Увеличение доступной вычислительной мощности привело работников к использованию ЭА для постановления задач.
Оптимизация конверсии
Одна из главных целей — повысить коэффициент посетителей на сайте. Эта проблема сводится к оптимизации количества пользователей, которые делают то, что маркетолог хочет. Например, если компания продает ноутбуки, в идеале необходимо увеличить количество посетителей сайта, которые в конечном итоге покупают продукт. В этом суть оптимизации коэффициента конверсии.
Одним из удивительно важных аспектов является выбор пользовательского интерфейса. Если веб-дизайн не очень удобен для пользователей, есть те, которые в конечном итоге не покупают продукт по той или иной причине. Тогда цель состоит в том, чтобы уменьшить количество пользователей, которые в конечном итоге не конвертируются, что увеличивает общую прибыль.
