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

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

(ГОУ ВПО ТГТУ) Кафедра программного обеспечения Реферат по курсу «Системы искусственного интеллекта»

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

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

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

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

Тверь, 2015

Предыстория

Первые работы по симуляции эволюции были проведены в 1954 году Нильсом Баричелли на компьютере находившемся в Институте перспективных исследований Принстонского университета. Его работа, опубликованная в том же году, привлекла большое внимание общественности. С 1957 года, австралийский генетик Алекс Фразер опубликовал серию работ по симуляции искусственного отбора среди организмов с множественным контролем измеримых характеристик. Данный шаг позволил компьютерной симуляции эволюционных процессов и методам, указанным в трудах Фразера и Барнелла (1970) и Кросби (1973), с 1960;х годов стать более распространенным видом научного изыскания среди биологов. Симуляции Фразера включали все важнейшие элементы современных генетических алгоритмов. Немногим позже Ганс-Иоахим Бремерманн в 1960;х опубликовал свою серию работ, которые также использовали подход использования популяции решений, подвергаемой рекомбинации, мутации и селекции, в задачах оптимизации. Исследования Бремерманна также включали различные элементы современных генетических алгоритмов. Среди прочих основоположников следует выделить Ричарда Фридберга, Джорджа Фридмана и Майкла Конрада. Огромное количество ранних работ были переизданы Давидом Б. Фогелем (1998).

Несмотря на то, что Баричелли в своих работах 1963 года симулировал попытки машины играть в элементарную игру, искусственная эволюция стала общепризнанным методом оптимизации только после работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960;х и начале 1970;х годов двадцатого века — научная группа Рехенсберга сумела решить некоторые инженерные проблемы следуя стратегиям эволюции. Иным подходом была техника эволюционного программирования Лоренса Дж. Фогеля, которую он предложил с целью создания искусственного интеллекта. Эволюционное программирование изначально использовавшее конечные автоматы для предсказывания обстоятельств, и использовавшее разнообразие и отбор для оптимизации логики предсказания. Генетические алгоритмы стали в особенности популярны во многом благодаря работе Джона Холланда в начале 70-х годов и его книге «Адаптация в естественных и искусственных системах» (1975). Его исследование опиралось на эксперименты с клеточными автоматами, проводившимися Холландом и на его трудах написанных в университете Мичигана. Холланд ввел формализованный подход для предугадывания качества следующего поколения, известный многим теперь не иначе как Теорема схем. Исследования в области генетических алгоритмов оставались по большей части теоретическими вплоть до середины 80-х годов, когда была, проведена Первая международная конференция по генетическим алгоритмам в Питтсбурге, Пенсильвания (США).

С ростом научного интереса значительно выросла и вычислительная мощь настольных компьютеров, что дало шанс использовать новую вычислительную технику на практике без больших усилий. В конце 80-х, компания General Electric наладила производство первого в мире продукта, основанного на использовании генетического алгоритма. Им стал набор промышленных вычислительных средств. В 1989, другая компания Axcelis, Inc. выпустила Evolver — первый в мире коммерческий продукт на генетическом алгоритме для настольных компьютеров. Журналист The New York Times в технологической сфере Джон Маркофф писал об Evolver в 1990 году.

Эволюционные алгоритмы — это вид алгоритмов, созданных в Германии в качестве методов решения многих оптимизационных задач и основанный на принципах теории природной эволюции.

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

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

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

Основные понятия генетических алгоритмов

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

Популяция — это конечное множество особей.

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

Хромосомы (другие названия — цепочки или кодовые последовательности) — это упорядоченные последовательности генов.

Ген (также называемый свойством, знаком или детектором) — это атомарный элемент генотипа, в частности, хромосомы.

Проиллюстрируем примеры хромосомы и генов для двоичного способа кодирования параметров задачи:

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

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

Каждая хромосома может кодировать только один параметр задачи. Но так как в одном генотипе может быть несколько хромосом, то один генотип может закодировать несколько параметров. Например: генотип включает в себя две хромосомы, каждая хромосома состоит из 3 генов, значит, первые 3 гена генотипа кодируют один параметр, а вторые 3 гена — второй параметр. Проиллюстрируем пример генотипа и фенотипа:

Аллель — это значение конкретного гена.

Локус или позиция указывает место размещения данного гена в хромосоме (цепочке).

Локи — это множество позиций генов.

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

Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков».

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

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

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

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

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

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

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

Классический генетический алгоритм

Постановка задачи и функция приспособленности

Пусть перед нами стоит задача оптимизации, например:

· Задача наилучшего приближения

o Если рассматривать систему n линейных уравнений с m неизвестными

Ax = b

в случае, когда она переопределена (n > m), то иногда оказывается естественной задача о нахождении вектора x, который «удовлетворяет этой системе наилучшим образом», т. е. из всех «не решений» является лучшим.

· Задача о рационе.

o Пусть имеется n различных пищевых продуктов, содержащих m различных питательных веществ. Обозначим через a_ij содержание (долю) j-го питательного вещества в i-ом продукте, через b_j — суточную потребность организма в j-ом питательном веществе, через c_i — стоимость единицы i-го продукта. Требуется составить суточный рацион питания минимальной стоимости, удовлетворяющий потребность во всех питательных веществах

· Транспортная задача.

o Эта задача — классическая задача линейного программирования. К ней сводятся многие оптимизационные задачи. Формулируется она так. На m складах находится груз, который нужно развезти n потребителям. Пусть a_i (i = 1, …, n) — количество груза на i-ом складе, а b_j (j = 1, …, m) — потребность в грузе j-го потребителя, c_ij — стоимость перевозки единицы груза с i-го склада j-му потребителю. Требуется минимизировать стоимость перевозок.

· Задачи о распределении ресурсов.

o Общий смысл таких задач — распределить ограниченный ресурс между потребителями оптимальным образом. Рассмотрим простейший пример — задачу о режиме работы энергосистемы. Пусть m электростанций питают одну нагрузку мощности p. Обозначим через x_j активную мощность, генерируемую j-ой электростанцией. Техническими условиями определяются возможный минимум m_j и максимум M_j вырабатываемой j-ой электростанцией мощности. Допустим затраты на генерацию мощности x на j-ой электростанции равны e_j(x). Требуется сгенерировать требуемую мощность p при минимальных затратах.

Переформулируем задачу оптимизации как задачу нахождения максимума некоторой функции f(x₁, x₂, …, x_n), называемой функцией приспособленности (fitness function). Она должна принимать неотрицательные значения на ограниченной области определения (для того, чтобы мы могли для каждой особи считать её приспособленность, которая не может быть отрицательной), при этом совершенно не требуются непрерывность и дифференцируемость.

Каждый параметр функции приспособленности кодируется строкой битов.

Особью будет называться строка, являющаяся конкатенацией строк упорядоченного набора параметров:

1010 10 110 101 … 10 101

| x1 | x2 | x3 | … | xn |

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

Принцип работы

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

С помощью функции приспособленности среди всех особей популяции выделяют:

· наиболее приспособленные (более подходящие решения), которые получают возможность скрещиваться и давать потомство

· наихудшие (плохие решения), которые удаляются из популяции и не дают потомства

Таким образом, приспособленность нового поколения в среднем выше предыдущего.

В классическом ГА:

· начальная популяция формируется случайным образом

· размер популяции (количество особей N) фиксируется и не изменяется в течение работы всего алгоритма

· каждая особь генерируется как случайная L-битная строка, где L — длина кодировки особи

· длина кодировки для всех особей одинакова

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

Алгоритм работы

На рисунке изображена схема работы любого генетического алгоритма:

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

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

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

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

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

Шаг алгоритма состоит из трех стадий:

1. генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения

2. скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения

3. мутация нового поколения

Первые две стадии (отбор и скрещивание):

Отбор

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

В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т. е. работает пропорциональный отбор (proportional selection).

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

Существует несколько способов реализации данного отбора:

§ stochastic sampling. Метод рулетки, который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки Все колесо рулетки соответствует сумме значений функции приспособленности всех хромосом рассматриваемой популяции. Пусть особи располагаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности. N раз запуская рулетку, выбираем требуемое количество особей для записи в промежуточную популяцию. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности.

§ remainder stochastic sampling. Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная показывает её вероятность попасть туда ещё раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N, причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию. Такой способ иллюстрируется следующим рисунком:

В результате процесса селекции создается родительская популяция, также называемая родительским пулом с численностью N, равной численности текущей популяции.

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

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

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

Скрещивание

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

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

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

В классическом ГА применяется одноточечный оператор кроссовера (1-point crossover): для родительских строк случайным образом выбирается точка раздела, потомки получаются путём обмена отсечёнными частями.

11 010.01010001101 -> 111 100.01010001101

111 100.10011101001 11 010.10011101001

Мутация

Оператор мутации с вероятностью, изменяет значение гена в хромосоме на противоположное (т.е. с 0 на 1 или наоборот).

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

Каждый бит каждой особи популяции с некоторой вероятностью инвертируется. Эта вероятность обычно очень мала, менее 1%.

1 011 001 100 101 101 -> 1 011 001 101 101 101

Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N.

Формирование новой популяции

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

Критерии останова

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

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

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

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

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

Пример применения генетического алгоритма

Постановка задачи

Выбор исходной популяции для генетического алгоритма связан с представлением параметров задачи в форме хромосом, т. е. с так называемым хромосомным представлением. Это представление определяется способом кодирования. В классическом генетическом алгоритме применяется двоичное кодирование, т. е. аллели всех генов в хромосоме равны 0 или 1. Длина хромосом зависит от условий задачи, точнее говоря — от количества точек в пространстве поиска.

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

Формула 1 для целочисленной переменной X, принимающей значения от 0 до 31.

Для применения генетического алгоритма необходимо, прежде всего, закодировать значения переменной X в виде двоичных последовательностей. Очевидно, что целые числа из интервала от 0 до 31 можно представить последовательностями нулей и единиц, используя их представление в двоичной системе счисления. Число 0 при этом записывается как 0, а число 31 — как 11 111. В данном случае хромосомы приобретают вид двоичных последовательностей, состоящих из 5 битов, т. е. цепочками длиной 5.

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

Отбор

Выберем случайным образом исходную популяцию, состоящую из 6 кодовых последовательностей (например, можно 30 раз подбросить монету); при этом. Допустим, что выбраны хромосомы:

Соответствующие им фенотипы — это представленные ниже числа:

По формуле 1 рассчитываем значения функции приспособленности для каждой хромосомы в популяции:

Селекцию хромосом проводим методом рулетки. Для этого выбираем 6 хромосом для репродукции. Колесо рулетки представлено на рисунке.

Допустим, что выбраны числа: 97 26 54 13 31 88

Это означает выбор хромосом:

Скрещивание

Пусть скрещивание выполняется с вероятностью. Допустим, что для скрещивания сформированы пары:

Кроме того, допустим, что случайным образом выбрана точка скрещивания, равная 3 для пары, а также точка скрещивания, равная 2 для пар

При условии, что вероятность мутации, в новую популяцию включаются хромосомы:

Для расчета значений функции приспособленности этих хромосом необходимо декодировать представляющие их двоичные последовательности и получить соответствующие им фенотипы. Обозначим их. В результате декодирования получаем:

Соответственно, значения функции приспособленности хромосом новой популяции, рассчитанные по формуле 1, составят:

Оценка итогов

Легко заметить, что в этом случае среднее значение приспособленности возросло с 589 до 1262. Обратим внимание, что если на следующей итерации будут сформированы для скрещивания пары хромосом, например, и с точкой скрещивания 2 или 3, то среди прочих будет получена хромосома 11 111 с фенотипом, равным числу 31, при котором оптимизируемая функция достигает своего максимума. Значение функции приспособленности для этой хромосомы оказывается наибольшим и составляет 1923. Если такое сочетание пар в данной итерации не произойдет, то можно ожидать образования хромосомы с наибольшим значением функции приспособленности на поздних итерациях. Хромосома 11 111 могла быть получена и на текущей итерации в случае формирования для скрещивания пары с точкой скрещивания 3.

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

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

Современные возможности и перспективы применения генетических и эволюционных алгоритмов оптимизации

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

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

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

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

В настоящее время скорость работы современных процессоров даже персональных компьютеров выросла как минимум в 10−20 раз по сравнению с концом 1990х годов, а многоядерность процессоров позволяет эффективно распараллеливать вычисления внутри поколения генетического алгоритма. Более того, в 1999 г появилась статья с рецептом аппроксимации вычислений функции exp (), нужной при вычислении значения гиперболического тангенса (наиболее часто используемой сигмоидной нелинейной функции нейронов для многослойных нейронных сетей) — аппроксимация ускоряет вычисление гиперболического тангенса в 4.4 раза и время срабатывания (именно срабатывания — генетическому алгоритму нужно именно оно, а не результат работы алгоритма обратного распространения) нейронной сети — в 1.5−2 и более раза в зависимости от размера нейросети (экспериментальные результаты приведены в заметке про ускорение вычислений гиперболического тангенса). Т. е. не только компьютеры стали работать быстрее, но и многие используемые нейросетевые модели (например, разные варианты многослойных персептронов) можно существенно ускорить.

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

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

http://www.aiportal.ru/articles/genetic-algorithms/gen-evo-algorithms.html

http://neuropro.ru/memo314.shtml

А.В. Еремеев Генетические Алгоритмы и оптимизация

http://algolist.manual.ru/ai/ga/ga3.php

Л.А. Гладков, В. В. Курейчик, В. М. Курейчик Генетические алгоритмы

Т.В. Панченко Генетические алгоритмы