Эволюционные алгоритмы: что это такое и для чего они нужны

В области искусственного интеллекта эволюционный алгоритм (ЭА) является подмножеством из вычислений общего количества населения на основе метаэвристической оптимизации. ЭА использует механизмы, вдохновленные биологическим развитием, такие как размножение, мутация, рекомбинация и отбор. Кандидатское решение в задаче эволюционных алгоритмов оптимизации играет роль индивидов в популяции. А также функция пригодности определяет качество ответов.

Эволюционные алгоритмы часто хорошо аппроксимируют решения всех типов проблем. Потому что в идеале они не делают каких-либо предположений о базовом фитнес-ландшафте. Методы, применяемые для эволюционного моделирования и генетических алгоритмов, обычно ограничиваются исследованиями микроэволюционных процессов и моделями планирования, основанными на клеточных этапах. В большинстве реальных приложений советников сложность вычислений является фактором запрещающим.

Вам будет интересно:Ряженые - это кто такие?

Фактически эта проблема связана с оценкой фитнес-функции. Фитнес-аппроксимация является одним из решений для преодоления этой трудности. Однако, казалось бы, простой ЭА может решить часто сложные проблемы. Следовательно, не может быть прямой связи между сложностью последовательности и проблемы. Более подробно можно прочитать в книгах «Эволюционные алгоритмы».

Реализация

Вам будет интересно:Отребье — это что такое? Толкование и синонимы

Шаг первый - создание первоначального населения из индивидуумов в случайном порядке.

Шаг второй - оценка пригодности каждого индивидуума в этой группе (ограничение по времени, достаточная подготовленность и т. д.).

Шаг третий - повторение следующих пунктов регенерации до завершения:

Типы

Генетический алгоритм — это эволюционная последовательность, самый популярный тип советника. Ищется решение проблемы в виде строк чисел (традиционно двоичных, хотя наилучшими представлениями обычно являются те, которые отражают большее в решаемой задаче) путем применения таких операторов, как рекомбинация и мутация (иногда одного, в отдельных случаях обоих). Этот тип советника часто используется в задачах оптимизации. Другое название для этого — fetura (от латинского «рождение»):

Сравнение с биологическими процессами

Вам будет интересно:Излишество – это недостаток или опасность?

Возможное ограничение многих эволюционных алгоритмов — отсутствие четкого различия между генотипом и фенотипом. В природе оплодотворенная яйцеклетка подвергается сложному процессу, известному как эмбриогенез, чтобы стать зрелой. Считается, что это косвенное кодирование делает генетический поиск более надежным (то есть уменьшает вероятность фатальных мутаций), а также может улучшить способность организма развиваться. Такие косвенные (иначе говоря, порождающие или развивающие) кодировки также позволяют эволюции эксплуатировать регулярность в окружающей среде.

Последние работы в области искусственного эмбриогенеза или системы развития стремятся решить эти проблемы. При программировании экспрессии генов успешно исследуется область генотип-фенотипа, где первый состоит из линейных мультигенных хромосом фиксированной длины, а второй из множества деревьев экспрессии или компьютерных программ различных размеров и форм.

Связанные техники

Алгоритмы включают в себя:

Другие популяционные метаэвристические методы

Меметический

Вам будет интересно:Франция в Первой мировой войне: дата и причина вступления, планы, цели, итоги и последствия

Гибридный метод, основанный на идее Ричарда Докинза о меме. Он обычно принимает форму алгоритма на основе совокупности в сочетании с индивидуальными процедурами обучения, способными выполнять локальные уточнения. Подчеркивает использование проблемно-специфических знаний и пытается организовать точеный и глобальный поиск синергетическим способом.

Эволюционные алгоритмы представляют собой эвристический подход к проблемам, которые не могут быть легко решены за полиномиальное время, таких как классически NP-сложные задачи и все остальное, что займет слишком много для исчерпывающей обработки. При самостоятельном использовании они обычно применяются для комбинаторных задач. Однако генетические алгоритмы часто употребляются в тандеме с другими методами, действуя как быстрый способ нахождения несколько оптимальных начальных мест для работы.

Предпосылка эволюционного алгоритма (известного как советник) довольно проста, учитывая, что вы знакомы с процессом естественного отбора. Она содержит четыре основных этапа:

• инициализация;
• выбор;
• генетические операторы;
• завершение.

Каждый из этих шагов примерно соответствует определенному аспекту естественного отбора и предоставляет простые способы модульной реализации этой категории алгоритмов. Проще говоря, в ЭА более приспособленные члены выживут и размножатся, в то время как непригодные участники умрут и не внесут свой вклад в генофонд последующих поколений.

Инициализация

Чтобы начать алгоритм, необходимо сначала создать совокупность решений. Население будет содержать произвольное количество возможных постановлений проблемы, часто называемых участниками. Они часто создаются случайным образом (в рамках ограничений задачи) или, если известны некоторые предварительные знания, ориентировочно сосредоточены вокруг того, который считается идеальным. Важно, чтобы популяция охватывала широкий спектр решений, потому что она, по существу, представляет собой генофонд. Следовательно, если необходимо исследовать множество различных возможностей в рамках алгоритма, нужно стремиться иметь много разных генов.

Выбор

После того как популяция создана, ее члены должны теперь оцениваться в соответствии с функцией пригодности. Фитнес-функция принимает характеристики члена и выдает числовое представление о том, насколько он жизнеспособен. Их создание часто может быть очень трудным. Важно найти хорошую систему, которая точно представляет данные. Это очень специфично для проблемы. Теперь необходимо рассчитывать пригодность всех участников и отбирать часть лучших членов.

Несколько целевых функций

Советники также могут быть расширены для использования данных систем. Это несколько усложняет процесс, потому что, вместо того чтобы идентифицировать одну оптимальную точку, получается набор при их использовании. Множество решений называется границей Парето и содержит элементы, которые одинаково пригодны в том смысле, что ни одно из них не доминирует над любым другим.

Генетические операторы

Этот шаг включает в себя два подэтапа: кроссовер и мутация. После выбора лучших членов (обычно 2 верхних, но это число может варьироваться), они теперь используются для создания следующего поколения в алгоритме. Применяя характеристики выбранных родителей, создаются новые дети, которые представляют собой смесь качеств. Это часто может быть затруднено в зависимости от типа данных, но обычно в комбинаторных задачах вполне реально смешивать и выводить действительные комбинации.

Вам будет интересно:Противостояние планет: определение, особенности. Какие планеты могут находиться в противостоянии?

Теперь необходимо ввести новый генетический материал в поколение. Если не сделать этого важного шага, то ученый очень быстро застрянет в локальных экстремумах и не получит оптимальных результатов. Этот шаг является мутацией, и делается он довольно просто, изменяя небольшую часть детей таким образом, чтобы они преимущественно не отражали подмножеств генов родителей. Мутация обычно происходит вероятностно, поскольку возможность того, что ребенок ее получит, а также ее серьезность, определяются распределением.

Прекращение

В конце концов алгоритм должен закончиться. Обычно это происходит в двух случаях: либо он достиг некоторого максимального времени выполнения, либо порога производительности. На этом этапе окончательное решение выбирается и возвращается.

Пример эволюционных алгоритмов

Теперь, чтобы проиллюстрировать результат этого процесса, необходимо просмотреть советника в действии. Для этого можно вспомнить, как несколько поколений динозавров учились ходить (постепенно осваивая сушу), оптимизируя структуру своего тела и прикладывая мышечные силы. Несмотря на то что рептилии раннего поколения не могли ходить, советник смог со временем эволюционировать их посредством мутации и кроссовера в форму, способную ходить.

Данные алгоритмы становятся все более актуальными в современном мире, поскольку решения на их основе все шире используются в таких отраслях, как цифровой маркетинг, финансы и здравоохранение.

Где используются ЭА?

В более широком смысле эволюционные алгоритмы применяются в самых разных приложениях, таких как обработка изображений, маршрутизация транспортных средств, оптимизация мобильной связи, разработка программного обеспечения и даже обучение искусственным нейронным сетям. Эти инструменты лежат в основе многих приложений и веб-сайтов, которые люди используют ежедневно, включая Google Maps и даже такие игры, как The Sims. Кроме того, медицинская сфера использует ЭА для помощи в принятии клинических решений относительно лечения рака. На самом деле эволюционные алгоритмы настолько надежны, что их можно использовать для решения практически любых задач оптимизации.

Закон Мура

Растущая распространенность ЭО обусловлена двумя основными факторами: доступной вычислительной мощностью и накоплением больших наборов данных. Первый может быть описан Законом Мура, который, по сути, гласит, что объем вычислительной мощности компьютера удваивается примерно каждые два года. Этот прогноз держится на протяжении десятилетий. Второй фактор связан с растущей зависимостью от технологий, которая позволяет учреждениям собирать невероятно большое количество данных, что дозволяет им анализировать тенденции и оптимизировать продукты.

Как эволюционные алгоритмы могут помочь маркетологам?

Конъюнктура рынка быстро меняется и очень конкурентоспособна. Это заставило менеджеров по маркетингу соперничать за счет лучшего принятия решений. Увеличение доступной вычислительной мощности привело работников к использованию ЭА для постановления задач.

Оптимизация конверсии

Одна из главных целей — повысить коэффициент посетителей на сайте. Эта проблема сводится к оптимизации количества пользователей, которые делают то, что маркетолог хочет. Например, если компания продает ноутбуки, в идеале необходимо увеличить количество посетителей сайта, которые в конечном итоге покупают продукт. В этом суть оптимизации коэффициента конверсии.

Одним из удивительно важных аспектов является выбор пользовательского интерфейса. Если веб-дизайн не очень удобен для пользователей, есть те, которые в конечном итоге не покупают продукт по той или иной причине. Тогда цель состоит в том, чтобы уменьшить количество пользователей, которые в конечном итоге не конвертируются, что увеличивает общую прибыль.