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

Основы искусственного интеллекта зм Лекция 4 Генетические алгоритмы Генетические алгоритмы – ГА (Genetic Algorithm) можно рассматривать как вариант стохастического информированного поиска, в котором состояния-преемники формируются путем комбинирования родительских состояний. ГА представлют собой эвристические методы решения задач оптимизации, это процедуры поиска, основанные на механизмах естественного отбора и наследования. В них используется эволюционный принцип выживания наиболее приспособленных особей. Идея ГА заимствована в ходе изучения процессов эволюции и связанной с ней селекции (естественного отбора) популяций живых существ. Этот подход использует свойство естественной эволюции, заключающееся в том, что изменениям подвергаются хромосомы, определяющие степень приспособленности особей. Каждое решение задачи (например, путь от начального до целевого состояния среды) кодируется и представляется в виде символьной строки, называемой в ГА хромосомой. Так же, как и в природе, ГА осуществляют поиск «хороших» хромосом без использования какой-либо информации о характере решаемой задачи. Требуется только некая оценка каждой хромосомы, отражающая ее «приспособленность». Механизм селекции заключается в выборе наиболее «приспособленных» хромосом с наилучшей оценкой, которые репродуцируют чаще, чем менее «приспособленные» особи (решения) с более низкой оценкой. Репродукция означает создание новых хромосом в результате рекомбинации генов родительских хромосом. Рекомбинация – это процесс, в результате которого возникают новые комбинации генов. Для этого используют две операции: скрещивание, позволяющее создать две совершенно новые хромосомы потомков путем комбинирования генетического материала пары родителей, а также мутация, которая может вызывать изменения в отдельных хромосомах. ГА отличаются от традиционных методов оптимизации несколькими базовыми свойствами. В частности, они:  обрабатывают не значения параметров самой задачи, а их закодированную форму;  осуществляют поиск решения исходя не из единственной точки, а из их некоторой популяции;  используют только целевую функцию, а не ее производные или иную дополнительную информацию;  применяют вероятностные, а не детерминированные правила отбора. Перечисленные свойства: кодирование параметров, операции на популяциях, использование минимума информации о задаче и рандомизация операций приводят в Основы искусственного интеллекта зм результате к устойчивости ГА и определяют их преимущества перед другими широко применяемыми методами. При описании ГА используются определения, заимствованные из генетики. Например, речь идет о популяции особей, а в качестве базовых понятий применяются ген, хромосома, генотип, фенотип, приспособленность. Наряду с этим используются соответствующие этим терминам определения из технического лексикона, в частности, цепь, двоичная последовательность, структура. Популяция – это конечное множество особей. Особи, входящие в популяцию, в ГА представляются хромосомами с закодированными в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска. Хромосомы (цепочки или кодовые последовательности) – это упорядоченные последовательности генов. Ген – это атомарный элемент (бит) генотипа (хромосомы или хромосомного набора). Генотип (структура) – это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы или единичные хромосомы (в довольно распространенном случае, когда генотип состоит из одной хромосомы). Фенотип – это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (точка пространства поиска). Локус (позиция) указывает место размещения данного гена в хромосоме (цепочке). Очень важным понятием в ГА считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также заимствует свое название из генетики. Эта функция оказывает сильное влияние на работу ГА и должна иметь точное и корректное определение. В задачах оптимизации проблема, как правило, сводится к поиску максимума функции приспособленности. На каждой итерации ГА приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющая множество потенциальных решений задачи оптимизации. Очередная популяция в ГА называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков». Постановка задачи Рассматриваться задача оптимизации целевой функции f(X) от N переменных: max f(X), X  D , где D = {X = (X1, X2, :, XN) | Xi на [ai, bi], i=1, 2,:N} (9.1) Основы искусственного интеллекта зм Прямоугольная область D называется областью поиска (D - подмножество RN). Оптимизируемая скалярная многопараметрическая функция f(x) может иметь несколько глобальных экстремумов (максимумов или минимумов). Предполагается, что о функции f(x) известно лишь то, что она определена в любой точке области D. Никакая дополнительная информация о характере функции и ее свойствах (дифференцируемость, непрерывность и т.д.) не учитывается в процессе поиска. Решением задачи (9.1) является x* = (x1, x2, :, xN) – точка в N – мерном пространстве из области поиска D, в которой целевая функция f(x) принимает оптимальное значение. Решение может быть не единственным. Параметры xi обычно кодируются бинарной строкой s. Используя целевую функцию f(x) можно построить функцию приспособленности F(s), отобразив, при необходимости, f(x) в область положительныхзначений. Таким образом, каждое возможное решение s, имеющее соответствующую приспособленность F(s) представляет решение x. Переход из пространства параметров X в хемминингово пространство бинарных строк s осуществляется кодированием переменных X1, X2, :, XN в двоичные целочисленные строки. Длина бинарной строки определяется желаемой точностью решения задачи. Для этого пространство параметров Xi должно быть дискретизировано таким образом, чтобы расстояние между узлами дискретизации соответствовало требуемой точности. Предположим, что по условию задачи функция от двух переменных X1 и X2, определена на прямоугольной области D = {0 < X1 <1; 0< X2 <1}, требуется локализовать решение x* с точностью по каждому из параметров 10-6. Для достижения такой точности пространство параметров дискретизуется равномерной сеткой с (bi-ai)/(10-6)= 1/10-6 = 1000000 узлами по каждой координате. Закодировать такое количество узлов можно l = 20 битами, где l определяется из условия 2l+1>106. Общая длина бинарной строки кодировки для двумерной задачи составит 2х20 = 40 бит. Чтобы провести дискретизацию пространства D и закодировать каждое возможное решение строкой s нужно"погрузить" равномерную сетку в пространство параметров X. Для этого каждый интервал [ai, bi] разбиваем на k отрезков равной длины: hi = (bi - ai) / k, i = 1, 2, …N. Этом самым покроем i-ый интервал [ai, bi] сетью si из (k+1) узла с постоянным шагом hi. : xi,j = ai + j.hi, j = 0, 1, … k. Используя двоичный алфавит {0,1} каждому узлу сетки si можно присвоить уникальный бинарный код длины q. Длина кода q выбирается таким образом, чтобы k = 2q1. Тогда символьная запись j-ого узла по i-ой координатной оси в двоичном коде можно представить в виде следующей бинарной конструкции: sij=bij1 b ij2 …. bijq На рис. 9.1. показан пример бинарного кодирования узлов сетки для функции одного переменного. Пространство поиска – интервал [0, 10] разбит на 8 отрезков при длине кода q=3 Основы искусственного интеллекта зм Рис. 9.1 Кодирование интервалов для функции одного переменного. Проведя дискретизацию по всем N координатным осям, получим в N-мерном параллелепипеде D пространственную решетку S с (k+1)N узлом, где каждый узел s можно представить в виде линейной последовательности таких записей (хромосом). На рис.9.2 приведен пример бинарного кодирования узлов сетки для функции двух переменных. Пространство поиска по каждой координате разбито на 16 отрезков при длине кода q=4. Рис.9.2. Кодирование интервалов для функции двух переменных. Таким образом, чтобы построить символьную модель оптимизационной задачи на гиперкубе D нужно представить множество узлов пространственной решетки S с помощью бинарных последовательностей (хромосом). Такая кодировка соответствует разбиению пространства параметров на гиперкубы, которым соответствуют уникальные комбинации битов в строке - хромосоме. Для установления соответствия между гиперкубами разбиения области и бинарными строками, описывающими номера таких гиперкубов, кроме обычной двоичной кодировки используется рефлексивный код Грея. Код Грея предпочтительнее обычного двоичного тем, что обладает свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменению кодовой комбинации только в одном разряде Идея ГА состоит в том, чтобы манипулируя имеющейся совокупностью бинарных представлений, с помощью ряда генетических операторов получать новые строки, т.е. Основы искусственного интеллекта зм перемещаться в новые гиперкубы. Получив бинарную комбинацию для нового решения, формируется вектор (операция декодирования ), с вещественными значениями из соответствующего гиперкуба. Таким образом, каждое решение генетического алгоритма будет иметь следующую структуру: 1. Фенотип. Точка в пространстве параметров: x = (x1, x2, … xN) принадлежит D из RN; 2. Генотип. Бинарная строка s фиксированной длины, однозначно идентифицирующая гиперкуб разбиения пространства параметров : s = (b1, b2, :, bl) принадлежит S, где S - пространство представлений - бинарных строк длины l. 3. Приспособленность. Скалярная величина F(x), соответствующая значению целевой функции f(x) в точке х: Такую структуру принято называть особью. Совокупность особей называется популяцией. В общем виде ГА можно представить следующей схемой (рис. 9.3): Рис.9.3 Упрощенная схема ГА Основы искусственного интеллекта зм Способы реализация операторов ГА определяются особенностями решаемой задачи, поэтому возможны различные вариации. Начальная популяция может быть инициализирована как случайными значениями xi, так и некоторыми готовыми решениями. Оператор скрещивания служит для создания потомков на основе родительских пар особей текущей популяции. Скрещивание с определенной вероятностью Pc реализует обмен генетического материала между двумя родителями для получения потомков. Простейшее одноточечное скрещивание (кроссинговер) производит обмен частями, на которые хромосома разбивается точкой кроссинговера, выбираемой случайно (рис.9.4). Двухточечный кроссинговер обменивает кусок строки, попавшей между двумя точками. Рис. 9.4. Оператор скрещивания Оператор мутации применяется для расширения пространства поиска за счет использования методов стохастического поиска. Оператор применяется к каждому потомку с небольшой вероятностью PM. Случайно выбранная позиция в хромосоме (аллель) изменяет значение на противоположное (рис.9.5). Существует также оператор мутации, называемый инверсией, который заключается в реверсировании бит между двумя случайными позициями в хромосоме. Рис. 9.5. Оператор мутации. Оператор редукции (отбора) служит для создания следующей популяции. В новую популяцию копируются хромосомы из текущей популяции в соответствии с их приспособленностью. Существуют различные схемы отбора, самая популярная из них – пропорциональный отбор способом «рулетки» или «турнира». Вероятность перехода особи в следующее поколение пропорциональна значению ее приспособленности. Основы искусственного интеллекта зм Пропорциональный отбор не гарантирует сохранности только лучших результатов, достигнутых в какой-либо популяции. Для отбора особей только с наилучшими значениями приспособленности используется элитный отбор. Пример реализации простого ГА Продемонстрируем работу ГА на очень простом примере – задаче нахождения экстремума целевой функции одной переменной, принимающей целочисленные значения. Определим целевую функцию в виде f(x)=|x-16|-5. Допустим, что x принимает целые значения из интервала от 0 до 31. Задача оптимизации этой функции заключается в перемещении по пространству, состоящему из 32 точек со значениями 0, 1, …32 для обнаружения точки, в которой функция принимает наименьшее значение. В этом случае в качестве параметра задачи выступает переменная x. Множество {0,1,2,…,31} составляет пространство поиска и одновременно – множество потенциальных решений задачи. Каждое из 32 чисел, принадлежащих этому множеству, называется точкой пространства поиска, решением или фенотипом. Решение, при котором функция принимает минимальное (максимальное) значение, называется наилучшим или оптимальным решением. По условиям данного примера оптимальным будет считаться решение, при котором целевая функция f(x) принимает минимальное значение. Тогда функция приспособленности F(x) должна принимать только положительные значения и возрастать при убывании целевой функции. Например, F(x) = - f(x)+15 (рис.9.6). Рис.9.6 целевая функция f(x) и функция приспособленности F(x) Основы искусственного интеллекта зм Значения параметра x можно закодировать следующим образом: Таблица 9.1 Кодирование хромосом x - фенотип Г(x) (двоичный код) Г(x) (код Грея) 00000 00000 1 00001 00001 2 00010 00011 3 00011 00010 4 00100 00110 … … … 31 11111 10000 Кодовые последовательности Г(x) называются хромосомами и в рассматриваемом примере они выступают в роли генотипов. Каждая хромосома состоит из пяти генов (битов). Значения гена в конкретной позиции называется аллелью, принимающей значения 0 или 1. Популяция состоит из особей, выбираемых их этих 32 хромосом. Формирование начальной популяции. Пусть начальная популяция состоит из шести особей (N=6), выбранных случайным образом: Таблица 9.2 Начальная популяция x - фенотип Г(x) – хромосома (двоичный код) Целевая функция f(x) Приспособленность F(x) 1 19 10011 -2 17 2 3 00011 8 7 3 7 00111 4 11 4 21 10101 15 5 8 01000 3 12 6 29 11101 8 7 номер особи Формирование родительских пар и скрещивание. Выбираем случайным образом пары родительских особей. Допустим, пары сформировались следующим образом: {x1, x3}, {x4, x5}, {x2, x6}. Определим вероятность скрещивания на уровне Pc=0,9. Для каждой пары Основы искусственного интеллекта зм генерируется случайное число s из диапазона [0, 1]. При sF(xl). Особь - победитель xw помещается в список особей нового поколения. В результате N турниров формируется новое поколение. Критерий останова эволюции. Решение может быть получено после завершения очередного цикла эволюции. Условием окончания может быть:  выполнение заданного количества циклов эволюции.  малое значение (меньше заданного порога) относительного приращения суммарной приспособленности популяции dF. Приращение приспособленности определяется для двух последовательных поколений: dF = (Fs(n) – Fs(n-1))/Fs(n) , где Fs(n) - суммарная приспособленность популяции после n циклов эволюции, Fs(n-1) - суммарная приспособленность предыдущей популяции. Например, если dF < 0,1%, то алгоритм завершает работу. Однако в этом случае Основы искусственного интеллекта зм существует опасность раннего завершения вычислений в области локального экстремума целевой функции. Решение задачи коммивояжера средствами ГА Задача коммивояжера (Travelling Salesman Problem -TSP) является классической задачей поиска оптимального пути. Без существенных изменений в постановочной части эта задача используется для проектирования разводки коммуникаций, разработки архитектуры вычислительных сетей и т.п. Кроме того, задача TSP используется для отработки различных эвристических алгоритмов поиска, которые затем применяются для решения более сложных задач комбинаторной оптимизации. В неформальной постановке задача о коммивояжере трактуется следующим образом: коммивояжеру необходимо посетить n городов, не заезжая в один город дважды, и вернуться в исходный пункт по маршруту с минимальной стоимостью. Формальная постановка задачи выглядит следующим образом: дан граф G=(B,C), где B – множество вершин (городов) мощностью n, C – множество ребер (путей между городами) мощностью m. Стоимость перемещения из вершины bi в bj задается числовой матрицей R(i,j), где i, j – 1,2, … n. Решение заключается в нахождении кратчайшего гамильтонова цикла в графе. Требуется найти перестановку φ из элементов множества B такую, чтобы минимизировать значение целевой функции: f ( )  R( (1), (n))   {R( (i), (i  1))}  min i Если граф не является полным, то вводятся дополнительные ограничения на величину φ, учитывающие принадлежность каждого перемещения между двумя городами множеству ребер C :  (i), (i  1)  C, i 1,2,...n  1 и  (1), (n)  C Данные ограничения учитываются в матрице R(i,j) путем установки метки бесконечности (∞) в ячейках, соответствующих отсутствующим ребрам графа. В дальнейшем при решении задачи о коммивояжере будем рассматривать полные графы с весами на ребрах. Пусть матрица весов R графа G =(B, C), где n=7, m=21 (рис. 9.9). Для маршрута x1=<1,2,3,4,5,6,7> (хромосома Г1) имеем значение целевой функции f(x1) = 1+1+1+1+1+1+1=7, а для маршрута x2=<7,2,5,4,3,6,1> (хромосома Г2) имеем значение целевой функции f(x2) = 3+6+1+1+5+3+1=20. Следовательно, маршрут x1 предпочтительнее, чем маршрут x2. Основы искусственного интеллекта зм Рис.9.9 Граф G В графе существует большое число равнозначных маршрутов, поскольку значение целевой функции не зависит, в частном случае, от выбора вершины – начала маршрута. Например, f(x3)= f(x2) = 7 , где маршрут x3=<2,3,4,5,6,7,1> (хромосома Г3) является одним из вариантов, получаемых из x1 путем циклического сдвига начальной вершины. 0 1 2 7 6 3 1 1 0 1 3 6 5 3 2 1 0 1 3 5 6 R 7 3 1 0 1 3 6 6 6 3 1 0 1 4 3 5 5 3 1 0 1 1 3 6 6 4 1 0 Фиксация начальной вершины сужает пространство поиска, которое в этом случае имеет размерность (n-1)!. Рассмотрим генетические операторы, ориентированные на решение рассматриваемой задачи. Можно выделить два основных варианта представления хромосом: кодирование в виде последовательности посещаемых вершин или кодирование в виде последовательности использованных ребер графа. Более простым является первый способ, ставящий на позицию i-го гена в хромосоме маршрута номер i-й посещаемой вершины. Для графа (рис. 9.9) два возможных маршрута (решения) можно записать следующим образом: Таблица9.7 Хромосома Г4 1 4 2 3 5 7 6 Г5 6 4 2 3 1 5 7 Основы искусственного интеллекта зм Характерной особенностью задачи коммивояжера, наряду с другими задачами, является ограничение на возможные комбинации значений генов в хромосоме. Оно вытекает из условий задачи: один о тот же город не может быть посещен дважды и все города должны быть посещены. Использование стандартных генетических операторов скрещивания и мутации приводит к большому числу недопустимых решений. Например, применим стандартный оператор скрещивания для хромосом Г4 и Г5. Пусть точка разрыва находится между третьим и четвертым геном. Тогда получим следующие два потомка: Г6=(1423157) и Г7=(6423576). Очевидно, что эти решения являются недопустимыми, так как в Г6 повторяется ген 1 и отсутствует ген 6, а в Г7 повторяется ген 6 и отсутствует ген 1. Иначе говоря, в решении задачи содержатся вершины посещаемые дважды и вершины, не посещаемые ни разу. Для задачи коммивояжера и других подобных задач необходимо использовать адаптированные операторы скрещивания и мутации, позволяющие гарантированно получать допустимые решения. Это могут быть, например, упорядоченный или «жадный» операторы скрещивания. В упорядоченном операторе скрещивания точка разрыва хромосом также выбирается случайно. Далее происходит копирование левого фрагмента первого родителя Г6 в хромосому потомка Г6’. Остальные гены потомка заполняются из хромосомы второго родителя Г7 в упорядоченном виде слева направо, исключая гены, уже попавшие в Г6’. Например: Таблица9.8 Хромосома 1 2 3 4 место разрыва 5 6 7 Родитель Г6 1 4 2 3 5 7 6 Родитель Г7 6 4 2 3 1 5 7 Потомок Г6’ 1 4 2 3 6 5 7 Потомок Г7’ 6 4 2 3 1 5 7 «Жадными» называются алгоритмы поиска, которые на каждом шаге делают локально оптимальный выбор, в надежде, что итоговое решение также окажется оптимальным. «Жадный» оператор скрещивания – это циклическая процедура. Она позволяющая создавать новые хромосомы на основе выбора на каждом шаге вершины, имеющей локально оптимальное значение целевой функции. «Жадные» операторы скрещивания, основанные на знаниях о задаче, увеличивают скорость сходимости решения, однако часто препятствуют выходу из локальных минимумов. Рассмотрим один из вариантов реализации этого оператора. 1. Назначить текущим родителем первого родителя и выбрать случайным образом стартовую вершину в его хромосоме. 2. Основной цикл оператора. Выбрать соседнюю вершину, ближайшую к Основы искусственного интеллекта зм текущей (соседними являются вершины, расположенные в хромосоме слева и справа от текущей). Ближайшая из них, еще не вошедшая в хромосому потомка, становится текущей вершиной. Если только одна из двух соседних вершин не вошла в хромосому потомка, то она становится текущей. Если обе соседние вершины уже вошли в хромосому потомка, то в качестве текущей выбирается ближайшая вершина из числа не рассмотренных ранее вершин. 3. Повторять цикл оператора, пока все вершины не будут включены в хромосому потомка. Хромосома потомка формируется в виде последовательности текущих вершин. Рассмотрим пример работы алгоритма для графа (рис. 9.9). Пусть хромосомы двух родителей имеют вид: Г8=(1423576) и Г9=(6354217). Для Г8 значение целевой функции f(Г8)=22, а для Г9 значение f(Г9)=15. Текущая вершина в хромосоме выделяется жирным шрифтом. Пусть на первом этапе случайным образом стартовой выбрана вершина 5. Она является текущей для обоих родителей. Родитель Г8 1 4 2 3 7 5 6 Родитель Г9 6 3 4 2 1 7 5 Согласно алгоритму, следующей вершиной выбирается вершина 3, соседняя с 5. Получаем первый фрагмент хромосомы потомка Г10’=(53). Родитель Г8 1 4 2 5 7 6 3 Родитель Г9 6 5 4 2 1 7 3 На следующем шаге выбирается вершина 2, т.к. вес ребра (32) - f(32)=1, а вес ребра (36) - f(36)=5. Хромосома потомка на этом этапе приобретает вид Г10’=(532). Родитель Г8 1 4 3 5 7 6 2 Родитель Г9 6 3 5 4 1 7 2 Далее выбирается вершина 1, затем 7 и 6. Процесс выбора вершин показан на рис.9.10 Рис.9.10 Оператор точечной мутации может быть реализован путем перестановки местами двух рядом расположенных генов, выбранных случайным образом. Например, мутация хромосомы потомка Г10, полученного в результате «жадного» скрещивания, может быть осуществлена следующим образом. Допустим выбраны 3-й и 4-й ген в хромосоме, тогда переставляя их местами получим преобразованную хромосому-мутанта Г10=(5312764) со значением целевой функции f(Г10)=3+2+1+3+1+1+3=15. Основы искусственного интеллекта зм Эффективность использования ГА зависит как от правильной настройки параметров алгоритма, так и от размерности решаемой задачи. Для решения простых задач поиска небольшой размерности будет достаточно использование эвристических итерационных алгоритмов. При решении сложных NP-полных задач комбинаторной оптимизации ГА доказали свою эффективность. На сегодняшний день ГА широко применяются для решения задач проектирования цифровой и аналоговой техники, задач построения интеллектуальных систем, решения задач оптимизации и т.д.