Эволюционные алгоритмы

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Министерство образования и науки РФ

Государственное образовательное учреждение высшего профессионального образования Тверской Государственный Технический Университет

(ГОУ ВПО ТГТУ)

Кафедра программного обеспечения.

Реферат по курсу «Нечеткая логика»

Тема: «Эволюционные алгоритмы»

Выполнил: Кузнецов Д.А.

Группа ФИТ ПИН 1106

Проверил: Мальков А.А.

Тверь, 2014



Введение

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

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение Видов", в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как "эволюционный синтез" укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, "спуск с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.

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

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.



Эволюционные алгоритмы

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

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

Конечно, на практике мы не можем разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

Конечно, эволюция биологических систем не единственный "источник вдохновения" создателей новых методов, моделирующих природные процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.

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

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

Однако нередки случаи, когда Генетический Алгоритм работает не так эффективно, как ожидалось.

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

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

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

Эволюционные алгоритмы -- направление в искусственном интеллекте (раздел эволюционного моделирования), которое использует и моделирует процессы естественного отбора.

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

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

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

Виды алгоритмов:

1) генетические алгоритмы -- эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров;

2) эволюционные стратегии -- похожи на генетические алгоритмы, но в следующее поколение передаются только положительные мутации;

3) системы классификаторов;

4) генетическое программирование -- автоматическое создание или изменение программ с помощью генетических алгоритмов;

5) эволюционное программирование -- аналогично генетическому программированию, но структура программы постоянна, изменяются только числовые значения;

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

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

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

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

Возможность использования эволюционных алгоритмов в музыке активно исследуется в Австрии, в первую очередь при попытках моделирования игры на музыкальных инструментах известными людьми разных эпох.

Генетимческий алгоримтм (англ. genetic algorithm) -- это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Генетические алгоритмы применяются для решения следующих задач:

1) Оптимизация функций

2) Оптимизация запросов в базах данных

3) Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)

4) Настройка и обучение искусственной нейронной сети

5) Задачи компоновки

6) Составление расписаний

7) Игровые стратегии

8) Теория приближений

9) Искусственная жизнь

10) Биоинформатика (фолдинг белков)

Генетический алгоритм -- это в первую очередь эволюционный алгоритм, другими словами, основная фишка алгоритма -- скрещивание (комбинирование). Как несложно догадаться идея алгоритма наглым образом взята у природы, благо она не подаст на это в суд. Так вот, путем перебора и самое главное отбора получается правильная «комбинация».

Алгоритм делится на три этапа:

1) Скрещивание

2) Селекция (отбор)

3) Формирования нового поколения

Если результат нас не устраивает, эти шаги повторяются до тех пор, пока результат нас не начнет удовлетворять или произойдет одно из ниже перечисленных условий:

a) Количество поколений (циклов) достигнет заранее выбранного максимума

b) Исчерпано время на мутацию

Стратегии отбора (selection strategies)

ГА представляет из себя итерационный процесс, в котором особи сначала отбираются для скрещивания, потом скрещиваются, затем из их потомков формируется новое поколение и все начинается сначала. Стратегии отбора являются составной частью ГА и определяют "достойных" для скрещивания особей. Ниже рассматриваются несколько наиболее распространенных стратегий.

Пропорциональный отбор (Proportional selection)

При данном виде отбора сначала подсчитывается присособленность каждой особи fi. После этого находят среднюю приспособленность в популяции fср как среднее арифметическое значений приспособленности всех особей. Затем для каждой особи вычисляется отношение fi/fср. Если это отношение больше 1, то особь считается хорошо приспособленной и допускается к скрещиванию, в противном случае особь, скорее всего, останется "за бортом". Например, если дробь равна 2.36, то данная особь имеет двойной шанс на скрещивание и будет иметь вероятность равную 0.36 третьего скрещивания. Если же приспособленность равна 0.54, то особь примет участие в единственном скрещивании с вероятностью 0.54.

Реализовать это можно, например, так.

Пусть имеется массив двоичных строк (популяция) и дополнительный массив для особей допущенных к скрещиванию. Определим для каждой особи популяции значение описанного выше отношения. Далее, будем записывать строки в промежуточный массив согласно следующему правилу: возьмем целую часть понятно-какого-отношения и ровно столько раз запишем данную строку во вспомогательный массив, после этого с помощью случайной величины (СВ) определим, будем ли мы записывать данную строку ещё раз: если СВ больше дробной части отношения, то "да", если нет, то "нет". В дальнейшем, особи для скрещивания выбираются только из промежуточного массива случайным образом, так что, если строка присутствует в нем в нескольких экземплярах, то у нее больше шансов "наследить" в истории;). Для уже рассмотренных примеров с числами 2.36 и 0.51 ситуация будет выглядеть следующим образом: первая строка запишется в промежуточный массив два раза и с вероятностью 0.36 запишется в третьй раз. Вторая же строка имеет вероятность равную 0.51 того, что она вообще будет присутствовать во вспомогательном массиве.

Данная стратегия отбора знаменита тем, что именно для неё создана классическая теорема шим (вот откуда там дробь).

Турнирный отбор (Tournament selection)

Турнирный отбор может быть описан следующим образом: из популяции, содержащей N строк, выбирается случайным образом t строк и лучшая строка записывается в промежуточный массив (между выбранными строками проводится турнир). Эта операция повторяется N раз. Строки в полученном промежуточном массиве затем используются для скрещивания (также случайным образом). Размер группы строк, отбираемых для турнира часто равен 2. В этом случае говорят о двоичном/парном турнире (binary tournament). Вообще же t называется численностью турнира (tournament size). Чем больше турнир, тем более жесткий вариант селекции, т.е. тем меньше шансов у особей, "кому за, или кто просто плохо".

Преимуществом данной стратегии является то, что она не требует дополнительных вычислений и упорядочивания строк в популяции по возрастанию приспособленности. Также, на мой взгляд, такой вариант селекции ближе к реальности, т.к. успешность той или иной особи во многом определяется ее окружением, насколько оно лучше или хуже ее. А иначе получилось бы, что бац! появился где-нибудь в Бразилии супер-таракан, а в России все усатые собратья тараканьи взяли (тоже бац!) и вымерли, от осознания своей неприспособленности.;)

Отбор усечением (Truncation selection)

Данная стратегия использует отсортированную по возрастанию популяцию. Число особей для скрещивания выбирается в соответствии с порогом TО[0; 1]. Порог определяет какая доля особей, начиная с самой первой (=самой приспособленной) будет принимать участие в отборе. В принципе, порог можно задать и числом больше 1, тогда он будет просто равен числу особей из текущей популяции, допущенных к отбору. Среди особей, попавших "под порог" случайным образом N раз выбирается самая везучая и записывается в промежуточный массив, из которого затем выбираются особи непосредственно для скрещивания.

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

Существуют и другие стратегии отбора, например, с линейным и экспоненциальным ранжированием, но о них как-нибудь потом. Можно только отметить, что у Исаева С.А. описан интересный алгоритм селекции, при котором формируются фиксированные брачные пары, которые и скрещиваются. От себя могу добавить, что аналогичный способ отбора особей для скрещивания есть в СНС модели генетического алгоритма.

Стратегии формирования нового поколения

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

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

Создается промежуточная популяция, которая включает в себя как родителей, так и их потомков. Члены этой популяции оцениваются, а затем из них выбираются N самых лучших, которые и войдут в следующее поколение.

Если вы знакомы с эволюционными стратегиями, то с этими способами вы уже встречались. Что из этих двух вариантов лучше - выбирать вам. На мой взгляд второй вариант практичнее (т.к. не позволяет заменять приспособленных родителей на "неизвестно кого"), но тут может быть больше проблем с преждевременной сходимостью, чем в первом варианте. К тому же он требует сортировки массива размером (как минимум) 2*N.

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

Принцип "элитизма"

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

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

Эволюционная стратегия (англ. Evolution strategy) -- эвристический метод оптимизации в разделе эволюционных алгоритмов, основанный на адаптации и эволюции. Метод разработан в 1964 году немецким ученым Инго Рехенбергом и развит в дальнейшем Ханс-Полом Швефелом и другими.

Эволюционная стратегия схожа с генетическим алгоритмом, но существует несколько существенных различий.

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

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

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

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

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

Выбор способа кодирования программы в генетическом алгоритме -- один из основных вопросов генетического программирования. Программа должна быть закодирована в таком виде, чтобы легко было автоматически вносить случайные изменения (оператор мутации) и объединять два алгоритма в один (оператор скрещивания).

Способы кодирования можно разделить на два класса:

· Прямое кодирование -- генетический алгоритм работает с программой в явном виде.

· Косвенное кодирование -- генетический алгоритм работает не с самим кодом программы, а с правилами его построения. То есть генетический алгоритм работает с программой, которая генерирует нужную нам программу.

Эволюционное программирование было изобретено доктором Лоуренсом Дж. Фогелем в Национальном Научном Фонде в 1960 году. В то время искусственный интеллект был ограничен двумя основными направлениями исследований: моделированием человеческого мозга (нейронные сети) и моделированием решения проблем поведения человека (эвристическое программирование). Достоинства эволюционного программирования были изучены д-ром Фогелем после его возвращения в Сан-Диего в июле 1961 при обращении к проблемам прогнозирования системы идентификации и контроля в серии исследований, возглавляемых тогда Фогелем и его коллегами, ведущими учеными в области эволюционных вычислениях. Изучение эволюционного программирования было продолжено в 1980-х в использовании произвольных представлений данных и применялось к обобщенной проблеме оптимизации. Эволюционное программирование, основанное на случайной изменчивости и отборе, было применено к таким структурам, как вещественные векторы, перестановки, матрицы, векторы переменные длины, бинарные строки и так далее. Эволюционное программирование было применено к различным инженерным задачам, включая маршрутизацию трафика и планирование, фармацевтические дизайны, эпидемиологию, выявление рака, военное планирование, системы управления, системы идентификации, обработки сигналов, энергетику, обучение в играх и т. д.

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

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

Роевой интеллект

Роевой интеллект (англ. Swarm intelligence) описывает коллективное поведение децентрализованной самоорганизующейся системы. Рассматривается в теории искусственного интеллекта как метод оптимизации. Термин был введен Херардо Бени и Ван Цзином в 1989 году, в контексте системы клеточных роботов.

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

Примеры алгоритмов

Аппроксимационные алгоритмы, представленные ниже, относятся к классу метаэвристик. Существуют их вариации как для задач одно-, так и многокритериальной оптимизации.

1) Муравьиный алгоритм (англ. Ant colony optimization).

2) Метод роя частиц (англ. Particle swarm optimization).

3) Пчелиный алгоритм (англ. Bees algorithm).

4) Оптимизация передвижением бактерий (англ. Bacterial foraging optimization).

5) Стохастический диффузионный поиск (англ. Stochastic diffusion search).

6) Алгоритм гравитационного поиска (англ. Gravitational search algorithm).

7) Алгоритм капель воды (англ. Intelligent Water Drops algorithm).

8) Светляковый алгоритм (англ. Firefly algorithm).

Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, англ. ant colony optimization, ACO) -- один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также аналогичных задач поиска маршрутов на графах. Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к источнику питания и представляет собой метаэвристическую (англ. metaheuristic, meta -- «за пределами» и heuristic -- «найти») оптимизацию. Первая версия алгоритма, предложенная доктором наук Марко Дориго в 1992 году, была направлена на поиск оптимального пути в графе.

В основе алгоритма лежит поведение муравьиной колонии -- маркировка более удачных путей большим количеством феромона. Работа начинается с размещения муравьёв в вершинах графа (городах), затем начинается движение муравьёв -- направление определяется вероятностным методом, на основании формулы вида:

,

где: вероятность перехода по пути , величина, обратная весу (длине) -ого перехода, количество феромона на -ом переходе, величина, определяющая «жадность» алгоритма, величина, определяющая «стадность» алгоритма и

Решение не является точным и даже может быть одним из худших, однако, в силу вероятностности решения, повторение алгоритма может выдавать (достаточно) точный результат.

В литературе было предложено несколько метаэвристических моделей ACO. Среди них три наиболее успешные:

· 1) ant system (Dorigo 1992, Dorigo et al. 1991, 1996)

· 2) ant colony system (ACS) (Dorigo & Gambardella 1997)

· 3) MAX-MIN ant system (MMAS) (Stutzle & Hoos 2000)

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

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

1) Первый муравей находит источник пищи (F) любым способом (а), а затем возвращается к гнезду (N), оставив за собой тропу из феромонов (b).

2) Затем муравьи выбирают один из четырёх возможных путей, затем укрепляют его и делают привлекательным.

3) Муравьи выбирают кратчайший маршрут, так как у более длинных феромоны сильнее испарились.

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

1) Муравей (так называемый «Блиц») проходит случайным образом от колонии

2) Если он находит источник пищи, то возвращается в гнездо, оставляя за собой след из феромона

3) Эти феромоны привлекают других муравьёв находящихся вблизи, которые вероятнее всего пойдут по этому маршруту

4) Вернувшись в гнездо они укрепят феромонную тропу

5) Если существует 2 маршрута, то по более короткому, за то же время, успеют пройти больше муравьёв, чем по длинному

6) Короткий маршрут станет более привлекательным

7) Длинные пути, в конечном итоге, исчезнут из-за испарения феромонов

эволюционный генетический вычислительный алгоритм

Муравьи используют окружающую среду как средство общения. Они обмениваются информацией косвенным путём, через феромоны, в ходе их «работы». Обмен информации имеет локальный характер, только те муравьи, которые находятся в непосредственной близости, где остались феромоны -- могут узнать о них. Такая система называется «Stigmergy» и справедлива для многих социальных животных (был изучен в случае строительства столбов в гнёздах термитов). Данный механизм решения проблемы очень сложен и является хорошим примером самоорганизации системы. Такая система базируется на положительной (другие муравьи укрепляют феромонную тропу) и отрицательной (испарение феромонной тропы) обратной связи. Теоретически, если количество феромонов будет оставаться неизменным с течением времени по всем маршрутам, то невозможно будет выбрать путь. Однако из-за обратной связи, небольшие колебания приведут к усилению одного из маршрутов и система стабилизируется к кратчайшему пути.

Метод роя частиц

Метод роя частиц (МРЧ) -- метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции. МРЧ был доказан Кеннеди, Эберхартом и Ши[1] [2] и изначально предназначался для имитации социального поведения. Алгоритм был упрощён, и было замечено, что он пригоден для выполнения оптимизации. Книга Кеннеди и Эберхарта [3] описывает многие философские аспекты МРЧ и так называемого роевого интеллекта. Обширное исследование приложений МРЧ сделано Поли [4] [5]. МРЧ оптимизирует функцию, поддерживая популяцию возможных решений, называемых частицами, и перемещая эти частицы в пространстве решений согласно простой формуле. Перемещения подчиняются принципу наилучшего найденного в этом пространстве положения, которое постоянно изменяется при нахождении частицами более выгодных положений.

Алгоритм

Для каждой частицы i = 1, …, S сделать:

· Сгенерировать начальное положение частицы с помощью случайного вектора x_i ~ U(b_lo, b_up), имеющего многомерное равномерное распределение. b_lo и b_up -- нижняя и верхняя границы пространства решений соответственно.

· Присвоить лучшему известному положению частицы его начальное значение: p_i < x_i.

· Если (f(p_i) < f(g)), то обновить наилучшее известное состояние роя: g < p_i.

· Присвоить значение скорости частицы: v_i ~ U(-(b_up-b_lo), (b_up-b_lo)).

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

· Для каждой частицы i = 1, …, S сделать:

· Сгенерировать случайные векторы r_p, r_g ~ U(0,1).

· Обновить скорость частицы: v_i < щ v_i + ц_p r_p ? (p_i-x_i) + ц_g r_g ? (g-x_i), где операция ? означает покомпонентное умножение.

· Обновить положение частицы переносом x_i на вектор скорости: x_i < x_i + v_i. Заметим, что этот шаг выполняется вне зависимости от улучшения значения целевой функции.

· Если (f(x_i) < f(p_i)), то делать:

· Обновить лучшее известное положение частицы: p_i < x_i.

· Если (f(p_i) < f(g)), то обновить лучшее известное состояние роя в целом: g < p_i.

· Теперь g содержит лучшее из найденных решений.

Параметры щ, ц_p, и ц_g выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований



Список используемой литературы

1. Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. -- Запоріжжя: ЗНТУ, 2009. -- 375 с.

2. http://www.victoria.lviv.ua/html/sss/ev_algorithm.html

3. Genetic and Evolutionary Algorithms G. Jones - Wiley

4. Back T. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms

5. http://www.gotai.net/documents/doc-ga-005.aspx

Размещено на Allbest.ru