Генетические алгоритмы в интеллектуальных системах. Генетические алгоритмы или как учебник по биологии может помочь в функциональной оптимизации

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

Другой пример: вы едете по скользкой дороге, и вдруг ваш автомобиль начинает заносить, справа в нескольких метрах от вас столб, а по встречной полосе едет грузовик. Внимание вопрос: как выйти из ситуации с наименьшими потерями, а лучше вообще без них. Факторов, которые нужно учитывать много: ваша скорость и скорость встречного автомобиля, расстояние до столба, «крутость» заноса и т.д. Что нужно делать? Давать газу, пытаясь выйти из заноса, или тормозить, или, может, попытаться аккуратно съехать в кювет, так чтобы не попасть в столб. Вариантов много, и для того чтобы определить оптимальный — нужно попробовать их все. Будь это компьютерной игрой – вы могли бы сохраниться и переигрывать до тех пор, пака результат вас не удовлетворит. Это и есть поиск оптимального решения.

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

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

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

Причём тут биология?

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

Особь – одно решение задачи.

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

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

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

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

Определения качества решений

Функция пригодности – функция определяющая качество особей популяции. В нашем примере это будет сумма расстояний от точки до точки в выбранном маршруте.

ФП = Р(1)+Р(2)+Р(3)+Р(4)+Р(5)+Р(6),

где Р(1) … Р(6) – расстояние между точками в соответствующем переходе из матрицы расстояний

Нам необходимо найти минимальное расстояние, поэтому, чем меньше значение ФП для особи, тем лучше.

Давайте посчитаем функции пригодности. Для первой особи:

Для остальных особей таким же образом получаем.

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

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

2. Устанавливается t= t+1. Производится выбор двух родителей (хромосом) для реализации оператора кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.

3. Формируется генотип потомков. Для этого с заданной вероятностью производится оператор кроссинговера над генотипами выбранных хромосом. Далее с вероятностью 0,5 выбирается один из потомков P i (t) и сохраняется как член новой популяции. После этого к P i (t) последовательно применяется оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохраняется как P k (t).

4. Определяется количество хромосом для исключения их из популяции, чтобы ее размер оставался постоянным. Текущая популяция обновляется заменой отобранных хромосом на потомков P k (t).

5. Производится определение приспособленности (целевой функции) и пересчет средней приспособленности всей полученной популяции.

6. Если t = t заданному, то переход к 7, если нет, то переход к 2.

7. Конец работы.

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

Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Его механизм несложен. Предварительно ПГА случайно генерирует популяцию последовательностей – хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем производится копирование последовательности хромосом и перестановка их частей. Далее ПГА реализует множество простых операций к начальной популяции и генерирует новые решения.

ПГА состоит из трех операторов:

репродукция;

кроссинговер;

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

Рассмотрим пример Д. Гольдберга: необходимо найти значение максимума функции f(x)=x 2 на целочисленном интервале . Традиционными методами можно изменять значения переменной x, пока не получим максимальное значение f(x).

Для объяснения и реализации ПГА построим следующую таблицу:

В столбце 2 табл. расположены 4 хромосомы (представленные в двоичном коде), сгенерированные случайным образом. Значение ЦФ для каждой хромосомы (столбец 4) определяется как квадрат значения десятичного кода двоичного числа, которое приведено для хромосом во втором столбце таблицы. Тогда суммарное значение ЦФ всех хромосом равно 890. Для селекции хромосом используется оператор репродукции на основе колеса рулетки. На рисунке поля колеса рулетки соответствуют значению ЦФ каждой хромосомы в процентах. В одной генерации колесо рулетки вращается, и после останова ее указатель определяет хромосому, выбранную для реализации следующего оператора. Очевидно, не всегда хромосома с большим значением ЦФ в результате ОР будет выбрана для дальнейших преобразований.

Колесо рулетки для примера

На основе реализации ОР выбираются хромосомы для применения ОК. Оператор кроссинговера, как правило, выполниться в 3 шага, одним из ОК описанным выше. Точка разрыва kвыбирается случайно между 1 и числом равным длине хромосомы минус единица, то есть в интервале (1, L-1). Длина хромосомы L – это число значащих цифр в ее коде. В рассматриваемом примере таблицы длина каждой хромосомы равна пяти (L=5). На основе ОК создаются две новые хромосомы, путем обмена их частей между позициями (k+1) и L соответственно.

Например, рассмотрим хромосомы 1 и 2 из начальной популяции. Пусть k=1. Тогда получим:

P 1 0 | 1 1 0 0 До применения оператора кроссинговера

P 2 1 | 0 0 0 0,

-----------------

P 1 0 0 0 0 0 После применения оператора кроссинговера

P 2 1 1 1 0 0.

Работа ПГА начинается с репродукции. Хромосомы для следующей генерации выбираются путем вращения колеса рулетки. В примере колесо рулетки вращается 4 раза. Это число соответствуют мощности начальной популяции.

Величину отношения
называют вероятностью выбора копий (хромосом) при реализации оператора репродукции и обозначают:

где f i (x)значение ЦФ i-й хромосомы в популяции, sum f(x)суммарное значение ЦФ всех хромосом в популяции. Величину
также называют нормализованной вероятностью выбора. Ожидаемое число копий

i-й хромосомы после реализации ОР определяются по формуле:

где
число анализируемых хромосом, причемN G включается вN.

Ожидаемое число копий хромосомы P i , переходящее в следующее поколение, также иногда определяют на основе выражения:

.

где
среднее значение ЦФ по всей популяции.

Тогда для рассматриваемого примера, ожидаемое число копий для первой хромосомы из таблицы равно 0,164=0,64 копий, для второй0,294=1,16 копий, для третьей0,054 = 0,2 и наконец для четвертой0,54=2. Используя модель «бросание монеты» можно определить число полученных копий. Например, (см. столбец 7 таблицы) хромосомы P 1 и P 2 получают 1 копию, хромосома P 4 – 2 копии, и хромосома 3 не получает копий. Сравнивая этот результат с ожидаемым числом копий, получаем то, что «лучшие» хромосомы дают большее число копий, «средние» остаются и «плохие» удаляются после реализации оператора репродукции.

Для рассматриваемого примера построим таблицу. В столбце 2 приведен вид 4 хромосом после выполнения оператора репродукции. В столбце 3 приведены списки пар хромосом, которые выбраны случайным образом для реализации оператора кроссинговера. В столбце 4 указан номер позиции для точки разреза хромосом. В столбце 5 приведен вид 4 хромосом после выполнения оператора кроссинговера. В столбце 6 приведены значения десятичного кода двоичного числа каждой хромосомы столбца 5. В столбце 7 приведено значение f(x) для каждой из 4 хромосом новой популяции. В строке 5 приведено суммарное значение ЦФ хромосом новой популяции, в строке 6 –среднее значение их ЦФ, а в строке 7- максимальное значение ЦФ хромосомы из новой популяции.

Применяя к популяции полученной после реализации оператора репродукции (столбец 2 табл.) оператор кроссинговера, получим новую популяцию хромосом (5 столбец таблицы). В принципе оператор кроссинговера можно применять любое число раз. После проведения одной генерации ПГА улучшились все показатели: среднее и максимальное значение ЦФ.

Далее, согласно схеме выполнения ПГА, реализуется оператор мутации. Существует большое количество видов операторов мутации. Заметим, что эти операторы соответствуют перестановкам элементов внутри заданного множества. Очевидно, что при небольшой длине хромосомы L (порядка 1020) можно выполнить полный перебор за приемлемое время и найти наилучшие решения. При увеличении L до 50200 и выше, полный перебор произвести затруднительно, и необходимы другие механизмы поиска. Здесь как раз и приходит на помощь направленно-случайный поиск, который реализуется на основе ПГА.

Отметим, что глобальный максимум можно было найти еще на этапе реализации кроссинговера. Для этого необходимо было увеличить пространство поиска. Например, если в столбце 5 табл. выбрать хромосомы P 2 и P 4 и между ними выполнить оператор кроссинговера (точка ОК выбрана случайно и равна 3), то получим:

P 2: 1 0 1 | 1 1 (ЦФ-23)

P 4: 1 1 1 | 0 0 (ЦФ-28)

P 2 : 1 0 1 0 0 (ЦФ-20)

P 4 : 1 1 1 1 1 (ЦФ-31).

Решение P 4 , полученное в результате применения ОК случайным образом, является наилучшим результатом (глобальным оптимумом).

Как отмечалось выше, в генетических алгоритмах можно выделять два основных механизма воспроизводства хромосом:

потомки являются точными копиями родителей (неполовое воспроизводство без мутации);

потомки имеют «большие» отличия от родителей.

В генетических алгоритмах в основном используют комбинации этих механизмов. Отметим, что в инженерных задачах начальная популяция может выбираться любым образом, например, моделированием «бросания монеты» (орел = 1, решка = 0). Тогда оператор репродукции выполняется через моделирование движения колеса рулетки. Оператор кроссинговера в задачах вычислительного характера обычно выполняется через двоичное декодирование двух положений монеты. Часто применяют другие типы ОК и другие технологии его выполнения. Вероятность ОК допускается равной Рr(ОК) = 1.0 и меньше, вероятность ОМ допускается равной Рr(ОМ) = 0.01 и больше. В общем случае вероятность применения оператора мутации зависит от знаний о решаемой задаче.

Приведем другой стандартный тип генетического алгоритма, описанный Л.Девисом:

Инициализация популяции хромосом.

Оценка значения каждой хромосомы в популяции.

Создание новых хромосом посредством скрещивания текущих хромосом; применение операторов мутации и рекомбинации.

Устранение хромосом из популяции, чтобы освободить место для новых хромосом.

Оценка значений новых хромосом и вставка их в популяцию.

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

Конец работы алгоритма.

Сравнивая описание ПГА Д. Гольдберга, Д. Холланда и Л. Девиса, видно, что в них реализована одна основная идея моделирования эволюции с некоторыми модификациями. Однако заметим, что эти изменения могут существенно влиять на окончательное качество решения.

Приведем пример модифицированного ПГА:

1. Создание начальной популяции решений.

2. Моделирование популяции (определение ЦФ для каждой хромосомы).

3. Пока не проведено необходимое число генераций или не закончилось время, заданное на реализацию алгоритма или не найдено оптимальное значение ЦФ (если оно известно):

а) выбор элементов для репродукции;

Применение:

б) оператора кроссинговера для создания потомков;

в) оператора мутации;

г) оператора инверсии;

д) оператора транспозиции;

е) оператора транслокации;

ж) оператора сегрегации;

з) оператора удаления вершин;

и) оператора вставки вершин;

к) рекомбинация родителей и потомков для создания новой генерации;

л) оператора редукции.

4. Реализация новой генерации.

Новые модификации ГА могут строиться путем объединения, например, пунктов «б – л» или их частичного устранения, или их перестановок, а также на основе применения адаптационных принципов управления эволюционным поиском.

Введение в аксиоматическую теорию генетических алгоритмов

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

Пусть каждому исходному понятию и отношению аксиоматической теории ГА поставлен в соответствие некоторый конкретный математический объект. Совокупность таких объектов называется полем интерпретации . Всякому утверждению U теории ГА ставится в соответствие некоторое высказывание U* об элементах поля интерпретации, которое может быть истинным или ложным. Тогда можно сказать, что утверждение U теории ГА соответственно истинно или ложно в данной интерпретации. Поле интерпретации и его свойства сами обычно являются объектом рассмотрения другой теории ПГА, которая в частности может быть аксиоматической. Этот метод позволяет доказывать суждения типа: если теория ГА непротиворечива, то непротиворечива и теория ПГА.

Пусть теория ГА проинтерпретирована в теории ПГА таким образом, что все аксиомы A i теории ГА интерпретируются истинными суждениями A i * теории ПГА. Тогда всякая теорема теории ГА, то есть всякое утверждение А, логически выведенное из аксиом A i в ГА, интерпретируется в ПГА некоторым утверждением A * , выводимым в ПГА из интерпретаций A i * аксиом A i и, следовательно, истинным.

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

Язык системы ГА: аппарат алгебры логики; теория множеств; теория графов, теория алгоритмов, основные положения биологии и теории систем.

1. Алфавит – перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.

   Правила образования (синтаксис), по которым из элементарных символов строятся формулы теории ГА:

построение моделей эволюций;

конструирования популяций;

построения ЦФ;

разработки генетических операторов;

репродукции популяций;

рекомбинации популяций;

редукции;

адаптации.

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

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

Популяция конструируется случайным образом.

Выполнение оператора репродукции производится на основе «колеса рулетки».

Обязательное использование операторов кроссинговера и мутации.

Размер популяции после каждой генерации остается постоянным.

Размер популяции меняется.

Число копий (решений), переходящих в следующую генерацию меняется.

Целевая функция определяется на основе принципа «Выживание сильнейших».

Правила вывода ГА. Фиксируется конечная совокупность предикатов П 1 , П 2 ,…, П k на множестве всех формул системы. Пусть П (x 1 ,…,x ni +1) – какой-либо из этих предикатов (n i 0) если, для данных формулF 1 ,…,F ni +1 утверждение П (F 1 ,…,F ni +1) истинно, то говорят, что формулаF ni +1 непосредственно следует из формулF 1 ,…,F ni +1 по правилу П i .

Заданием 1,2,3 исчерпывается задание формальной системы ГА как точного математического объекта. При этом степень точности определяется уровнем точности задания алфавита, правил образования и правил вывода. Выводом системы ГА называется всякая конечная последовательность формул, в которой каждая формула либо является аксиомой системы ГА, либо непосредственно следует из каких-либо предшествующих ей (этой последовательности) формул по одному из правил вывода П i системы.

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

Предлагается ряд основных стратегий взаимодействия методов эволюционного и локального поиска:

«поиск – эволюция»;

«эволюция – поиск»;

«поиск – эволюция - поиск»;

«эволюция – поиск - эволюция».

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

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

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

Выводы

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

Существует четыре основных отличия ГА от оптимизационных методов:

прямое преобразование кодов;

поиск из популяции, а не из единственной точки;

поиск через элементы (слепой поиск);

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

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

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

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение Видов", в 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) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.

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

Эволюционный поиск

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

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

Зачем нужны генетические алгоритмы

ГА преследуют следующие цели:

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

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

Особенности ГА

Перечислим главные отличия ГА от большинства других методов поиска оптимального решения.

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

Критерии работы

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

1. Выполнение заданного числа итераций.
2. Качество найденного решения соответствует требованиям.

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

Базовая терминология

Ввиду того, что ГА основаны на генетике, то и большая часть терминологии соответствует ей. Любой генетический алгоритм работает исходя из начальной информации. Множество начальных значений есть популяция П t = {п 1 , п 2 , ..., п n }, где п i = {г 1 , ..., г v }. Разберем подробнее:

• t - это номер итерации. t 1 , ..., t k - означает итерации алгоритма с номера 1 по k, и на каждой итерации создается новая популяция решений.
• n - размер популяции П t .
• п 1 , ..., п i - хромосома, особь, или организм. Хромосома или цепочка - это закодированная последовательность генов, каждый из которых имеет порядковый номер. При этом следует иметь в виду, что хромосома может быть частным случаем особи (организма).
• г v - это гены, являющиеся частью закодированного решения.
• Локус - это порядковый номер гена в хромосоме. Аллель - значение гена, которое может быть как числовым, так и функциональным.

Что значит "закодированный" в контексте ГА? Обычно любое значение кодируется на основе какого-либо алфавита. Простейшим примером является перевод чисел из десятеричной системы счисления в двоичное представление. Таким образом алфавит представляется как множество {0, 1}, а число 157 10 будет кодироваться хромосомой 10011101 2 , состоящей из восьми генов.

Родители и потомки

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

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

Функция приспособленности

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

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

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

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

Базовый генетический алгоритм

Разложим по шагам наиболее простой (классический) ГА.

1. Инициализация начальных значений, то есть определение первичной популяции, того множества особей, с которыми будет происходить эволюция.
2. Установление первичной приспособленности каждой особи в популяции.
3. Проверка условий прекращения итераций алгоритма.
4. Использование функции селекции.
5. Применение генетических операторов.
6. Создание новой популяции.
7. Шаги 2-6 повторяются в цикле до выполнения необходимого условия, после чего происходит выбор наиболее приспособленной особи.

Пройдемся вкратце по мало очевидным частям алгоритма. Условий прекращения работы может быть два:

1. Количество итераций.
2. Качество решения.

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

1. Для каждой пары родителей, содержащих L генов, случайным образом выбирается точка скрещивания Тск i .
2. Первый потомок составляется путем присоединения к генам первого родителя [Тск i+1 ; L] генов второго родителя.
3. Второй потомок составляется обратным путем. Теперь к генам второго родителя добавляется гены первого родителя на позициях [Тск i+1 ; L].

Тривиальный пример

Решим задачу генетическим алгоритмом на примере поиска особи с максимальным числом единиц. Пусть особь состоит из 10 генов. Зададим первичную популяцию в количестве восьми особей. Очевидно, наилучшей особью должна быть 1111111111. Составим для решения ГА.

• Инициализация. Выберем 8 случайных особей:

Из таблицы видно, что особи 3 и 7 имеют наибольшее число единиц, а значит являются наиболее подходящими членами популяции для решения задачи. Так как на данный момент решения требуемого качества нет, алгоритм продолжает работу. Необходимо провести селекцию особей. Для простоты объяснения пусть селекция происходит случайным образом, и мы получаем выборку особей {п 7 , п 3 , п 1 , п 7 , п 3 , п 7 , п 4 , п 2 } - это родители для новой популяции.

• Использование генетических операторов. Снова для простоты положим, что вероятность мутаций равна 0. Иными словами все 8 особей передают свои гены такими, какие есть. Для проведения скрещивания, составим пары особей случайным образом: (п 2 , п 7), (п 1 , п 7), (п 3 , п 4) и (п 3 , п 7). Так же случайным способом выбираются точки скрещивания для каждой пары:

• Составление новой популяции, состоящей из потомков:

Дальнейшие действия очевидны. Самое интересное в ГА открывается в случае, если оценить среднее количество единиц в каждой популяции. В первой популяции в среднем на каждую особь приходилось 5,375 единиц, в популяции потомков - 6,25 единиц на особь. И такая особенность будет наблюдаться даже в случае, если в ходе мутаций и скрещивания особь с наибольшим числом единиц в первой популяции потеряется.

План реализации

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

1. Определение представления (алфавита).
2. Определение операторов случайных изменений.
3. Определение выживания особей.
4. Генерация первичной популяции.

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

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

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

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

Эффективность

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

1. Создание полной популяции, что будет включать всевозможные варианты особей в некоторой заданной области.
2. Случайное создание особей на основе всех допустимых значений.
3. Точечное случайное создание особей, когда среди допустимых значений выбирается диапазон для генерации.
4. Комбинирование первых трех способов создания популяции.

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

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

Энциклопедичный YouTube

1 / 5

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

✪ 20: Введение в генетические алгоритмы (1 из 2)

✪ C# - Морской Бой - Самый лучший алгоритм ИИ

✪ 15 09 2018 Лекция «Генетические алгоритмы для поиска оптимальных структур» Ульянцев В. И.

✪ Генетический алгоритм. Размещение графа на линейке

Субтитры

История

Первые работы по симуляции эволюции были проведены в 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 году.

Описание алгоритма

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

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

Применение генетических алгоритмов

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

1. Оптимизация функций
2. Разнообразные задачи на графах (задача коммивояжера , раскраска, нахождение паросочетаний)
3. Настройка и обучение искусственной нейронной сети
4. Задачи компоновки
5. Игровые стратегии
6. Биоинформатика (фолдинг белков)
7. Синтез конечных автоматов
8. Настройка ПИД регуляторов

Пример простой реализации на C++

Поиск в одномерном пространстве, без скрещивания.

#include #include #include #include #include int main () { srand ((unsigned int ) time (NULL )); const size_t N = 1000 ; int a [ N ] = { 0 }; for ( ; ; ) { //мутация в случайную сторону каждого элемента: for (size_t i = 0 ; i < N ; ++ i ) a [ i ] += ((rand () % 2 == 1 ) ? 1 : - 1 ); //теперь выбираем лучших, отсортировав по возрастанию std :: sort (a , a + N ); //и тогда лучшие окажутся во второй половине массива. //скопируем лучших в первую половину, куда они оставили потомство, а первые умерли: std :: copy (a + N / 2 , a + N , a ); //теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше. std :: cout << std :: accumulate (a , a + N , 0 ) / N << std :: endl ; } }

Пример простой реализации на Delphi

Поиск в одномерном пространстве с вероятностью выживания, без скрещивания. (проверено на Delphi XE)

program Program1 ; {$APPTYPE CONSOLE} {$R *.res} uses System . Generics . Defaults , System . Generics . Collections , System . SysUtils ; const N = 1000 ; Nh = N div 2 ; MaxPopulation = High (Integer ) ; var A : array [ 1 .. N ] of Integer ; I , R , C , Points , BirthRate : Integer ; Iptr : ^ Integer ; begin Randomize ; // Частичная популяция for I := 1 to N do A [ I ] := Random (2 ) ; repeat // Мутация for I := 1 to N do A [ I ] := A [ I ] + (- Random (2 ) or 1 ) ; // Отбор, лучшие в конце TArray . Sort < Integer > (A , TComparer < Integer >. Default ) ; // Предустановка Iptr := Addr (A [ Nh + 1 ]) ; Points := 0 ; BirthRate := 0 ; // Результаты скрещивания for I := 1 to Nh do begin Inc (Points , Iptr ^ ) ; // Случайный успех скрещивания R := Random (2 ) ; Inc (BirthRate , R ) ; A [ I ] := Iptr ^ * R ; Iptr ^ := 0 ; Inc (Iptr , 1 ) ; end ; // Промежуточный итог Inc (C ) ; until (Points / N >= 1 ) or (C >= MaxPopulation ) ; Writeln (Format ("Population %d (rate:%f) score:%f" , [ C , BirthRate / Nh , Points / N ])) ; end .

В культуре

• В фильме 1995 года «Виртуозность » мозг главного злодея выращен генетическим алгоритмом с использованием воспоминаний и поведенческих черт преступников.