Работа 3. Реализация генетических алгоритмов на примерах решения математических задач

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

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

Приведем некоторые понятия и определения из теории ГА. Все ГА работают на основе начальной информации, в качестве которой выступает популяция альтернативных решений Р. Популяция P_t={P₁, P₂, .. . , P_i, .. .P_Np} есть множество элементов

Р_i, i = 0, 1, 2… – это номер генерации генетического алгоритма, Np – размер популяции. Каждый элемент этой популяции Р_i, как правило, представляет собой одну или несколько хромосом или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов Р_i= {g₁, g₂,…, g_v} (элементы, части закодированного решения), и позиции генов в хромосоме называются лоции или локус для одной позиции, то есть ген – подэлемент (элемент в хромосоме), локус – позиция в хромосоме, аллель – функциональное значение гена.

Гены могут иметь числовые или функциональные значения. Обычно

эти числовые значения берутся из некоторого алфавита. Генетический

материал элементов обычно кодируется на основе двоичного алфавита {0,1}, хотя можно использовать буквенные, а также десятичные и другие алфавиты.

Примером закодированной хромосомы длины девять на основе двоичного алфавита может служить хромосома Р_i= (001001101).

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

популяцию. Генерация, то есть процесс реализации одной итерации

алгоритма, называется поколением.

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

max { f (i) | i{0,1}n }.

Примерами служат задачи размещения, стандартизации, выполнимости и другие. Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции I₀= {i₁, i₂, …, i_N} – конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов. Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование "хорошей" начальной популяции (например, из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума.

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

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

1. Выбрать начальную популяцию I₀и положить    f*  = max { f (i) |i I₀},k := 0.

2. Пока не выполнен критерий остановки делать следующее.

2.1. Выбрать родителей i₁,i₂из популяцииI_k.         2.2. Построитьi'поi₁,i₂.         2.3. Модифицироватьi' .         2.4. Еслиf*<f (i' ), тоf*:=f (i' ).         2.5. Обновить популяцию и положить k := k+1.

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

в предположении, что f (i) > 0 для всехi ÎI. При турнирной селекции формируется случайное подмножество из элементов популяции и среди них выбирается один элемент с наибольшим значением целевой функции. Турнирная селекция имеет определенные преимущества перед пропорциональной селекцией, так как не теряет своей избирательности, когда в ходе эволюции все элементы популяции становятся примерно равными по значению целевой функции. Операторы селекции строятся таким образом, чтобы с ненулевой вероятностью любой элемент популяции мог бы быть выбран в качестве одного из родителей. Более того, допускается ситуация, когда оба родителя представлены одним и тем же элементом популяции.

Как только два решения выбраны, к ним применяется вероятностный оператор скрещивания (crossover). Существует много различных версий этого оператора, среди которых простейшим, по-видимому, является однородный оператор. По решениямi₁,i₂он строит решениеi' присваивая каждой координате этого вектора с вероятностью 0,5 соответствующее значение одного из родителей. Если вектораi₁,i₂совпадали скажем по первой координате, то векторi'  "унаследует" это значение. Геометрически, оператор скрещивания случайным образом выбирает в гиперкубе вершинуi' , которая принадлежит минимальной грани, содержащей вершиныi₁,i₂. Можно сказать, что оператор скрещивания старается выбрать новое решениеi' где-то междуi₁,i₂полагаясь на удачу. Более аккуратная  процедура могла бы выглядеть таким образом. Новым решениемi' является оптимальное решение исходной задачи на соответствующей грани гиперкуба. Конечно, если расстояние Хемминга междуi₁,i₂равноn, то задача оптимального скрещивания совпадает с исходной задачей. Тем не менее, даже приближенное решение этой задачи вместо случайного выбора заметно улучшает работу генетического алгоритма. По аналогии с однородным оператором скрещивания легко предложить и другие операторы, использующие не только два, но и произвольное число решений из популяции

Оператор мутации, применяемый к решению i'  в п. 2.3. генетического алгоритма, с заданной вероятностьюp_mÎ(0, 1) меняет значение каждой координаты на противоположное. Например, вероятность того, чтоi' = (0, 0, 0, 0, 0) в ходе мутации перейдет вj'= (1, 1, 1, 0, 0), равнаp_m´p_m´p_m´(1 –p_m)´(1 –p_m) >0. Таким образом, с ненулевой вероятностью решениеi' может перейти в любое другое решение. Отметим, что модификация решенияi' может состоять не только в случайной мутации, но и в частичной перестройке решения алгоритмами локального поиска. Применение локального спуска позволяет генетическому алгоритму сосредоточиться только на локальных оптимумах. Множество локальных оптимумов может оказаться экспоненциально большим и на первый взгляд кажется, что такой вариант алгоритма не будет иметь больших преимуществ. Однако экспериментальные исследования распределения локальных оптимумов свидетельствуют о высокой концентрации их в непосредственной близости от глобального оптимума. Это наблюдение известно как гипотеза о существовании "большой долины" для задач на минимум или "центрального горного массива" для задач на максимум.

Гипотеза 1.

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

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

Практика на основе изложенной теории

Пусть нам дана нелинейная система уравнений:

F1=Х²+Х*У–10=0 (1)

F2=(У+Х)*(X–Y)+5=0

Необходимо найти значения Х^*и У^*, которые удовлетворяли бы решению системы (1) с заданной степенью точности. Вообще говоря, такая формулировка задачи не совсем корректна, т.к. в пределах диапазона, заданного точностью, может находиться несколько экстремумов. Здесь речь идет о вопросе различения задач поиска локального и глобального экстремумов (см. выше).

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

Наиболее очевидным решением представляется следующая структура хромосомы: первый ген отвечает за значение Х^*, а второй – за значение. предположим, что значения Х^*и У^* не выходят за пределы числа 7, а точность не превышает значения 0,1. Тогда можно предложить следующую структуру хромосомы:

Z

Z

Z

Z

Z

Z

Z

Z

Z

Z

Z

Z

Z

Z

Z

Z

Знак Х^* Значение Х^* Знак У^* Значение У^*

Х^* Z^*

где Z€ {0,1}.

Используя выбранную структуру хромосомы, состоящую из двух генов, необходимо реализовать выше предложенный ГА с целью нахождения Х^*и У^*. Наиболее сложным этапом в этом процессе является этап отбора или селекции. Селекция осуществляется по критерию качества, значения которого вычисляются с помощью функции полезности – ЦФ. ЦФ может иметь произвольный характер (естественно при этом придерживаться критериев простоты и наглядности), однако в основе ее синтеза должна лежать мера, отражающая степень близости результатов работы ГА к истинному решению задачи. В нашем случае такой мерой для каждойi-той особи (хромосомы) может служить величина

δ_i = | Х^* – Х | + | У^* – У |. (2)

Но, поскольку значения Х^*и У^*нам заранее неизвестны, то необходимо для ЦФ ввести в рассмотрение (3) величину

δ_i = | F₁ | + | F₂ |, (3)

что и было сделано в ниже рассматриваемом примере.

Если в процессе работы ГА для некоторой хромосомы мы получим результат

δ_i = 0, (4)

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

Достижение результата (4) возможно без увеличения вычислительной сложности, если решение системы (1) лежит в области целочисленных значений. Сделаем здесь акцент на тот момент, что условие (4) может быть и недостигнуто, если ГА зациклится в области локального экстремума.

Выражение (2) для ЦФ можно модифицировать, введя в рассмотрение новую функцию

f_i = 1/ δ_i, (5)

которая будет стремиться к максимуму, при стремлении δ_iк минимуму, т.е. к нулю. Такое несложное преобразование для ЦФ необходимо для увеличения наглядности ГА, т.к. интуитивно качество работы алгоритма на каждом шаге удобней оценивать, если производить сопоставление «лучших» хромосом с бо'льшими согласно (5) значениями ЦФ. Такой подход позволит, произведя сортировку хромосом по убыванию значения ЦФ «отбросить» нижнюю (худшую) половину популяции.

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

1. Выбор структуры генотипа (хромосомы) с учетом возможности несложных преобразований из генотипа в фенотип;

2. Подбор ЦФ, отражающей степень близости фенотипа к искомому решению.

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

f_i = 1/ L_i.