Решебник_МО

Чтобы вычислить функцию приспособленности, подставив каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет считать целевым значением:

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

Для выбора пяти пар родителей представим, что у нас есть 10 000-сторонняя игральная кость, на 880 сторонах которой отмечена хромосома 1, на 3080 – хромосома 2, на 2640 сторонах – хромосома 3, на 556 – хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару, кидаем кость два раза и выбираем выпавшие хромосомы. Таким же образом выбирая остальных, получаем:

Моделирование выбора родителей

91

Каждый потомок должен содержать информацию о родительских генах. Вообще говоря, это можно обеспечить различными способами. В нашем примере используем простейший одноточечный кроссинговер. Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец – a2,b2,c2,d2, тогда возможно 6 различных кроссинговеров (| = разделительная линия разрыва):

Скрещивания между родителями

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

Моделирование скрещиваний хромосом родителей

Вычислим функции приспособленности потомков:

Среднее значение функции качества потомков оказалась 38,8 (у родителей – 59,4). Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30.

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

92

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

ГЕНЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

В 90-х появилась разновидность ЭА, ориентированная, в основном, на решение задач автоматического синтеза программ.

Алгоритм ГП включает следующие шаги.

Ш а г 1. Инициализация модели предусматривает случайную генерацию популяции P(0), состоящей из μ древовидных программ. Причем корневой вершиной дерева всегда является функция, аргументы которой выбираются случайно из множеств function set или terminal set. Концевыми вершинами дерева должны быть переменные или константы, в противном случае процесс генерации необходимо рекурсивно продолжить. Если структура дерева становится сложной, то заранее устанавливается максимальная глубина дерева. Она равна числу ребер дерева, которое содержит самый длинный путь от корневой вершины до некоторой концевой вершины. Обычно в экспериментах максимальная глубина дерева колеблется от шести для популяции P(0) и до 17 в более поздних популяциях P(t). Для обеспечения многообразия популяции P(0) в ходе инициализации может применяться так называемый half-ramping способ, согласно которому деревья разной высоты генерируются с одинаковой частотой. Правда, этот способ не лишен недостатка, связанного с не совсем случайным характером генерируемых деревьев. Поэтому существуют альтернативные методы псевдослучайной генерации деревьев начальной популяции P(0), причем дупликация идентичных хромосом в P(0) считается недопустимой.

93

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

Ша г 3. Генерация новой популяции, которая предусматривает следующие шаги:

1)выбор операторов эволюции, основными из которых для ГП являются репродукция и кроссинговер, применяемые с

вероятностью pr и pk соответственно, причем pr + pk = 1 (чаще всего pr = 0,1, pk = 0,9);

2)селекция и репликация, выполняемая по аналогии с ГА;

3)образование новой популяции. Если к некоторой программе применяют оператор репродукции, то эта программа копируется в новую популяцию. Для проведения кроссинговера выбираются две родительские хромосомы. Случайным образом определяются точки кроссинговера и путем обмена образуются два потомка. При программной реализации на языке Лисп кроссинговер сводится к обмену списками между двумя программами при сохранении синтаксической корректности вновь получаемых программ.

Ш а г 4. Проверка критерия остановки. Процедура ГП является

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

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

94

подобрать такую функцию (регрессию), которая отображает зависимость Y от Х с минимальной погрешностью.

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

Применим ГП для решения задачи символьной регрессии. Пусть, например, регрессионная модель – квадратный полином вида Y = X2–X+2, где X принимает значения в диапазоне [–1, 1]. Проблема состоит в том, чтобы автоматически создать компьютерную программу, реализующую данную регрессию.

Для программного вычисления регрессии будем использовать математические операции сложения (+), вычитания (–), умножения (*) и деления (%), множество переменных Х, а также множество числовых констант из некоторого диапазона, например, от –2 до +2. Оценку программ различной величины и сложности, автоматически генерируемых с помощью генетических операторов, будем осуществлять в зависимости от того, насколько близки к целевому значению указанного полинома полученные программой результаты. Например, чем меньше среднеквадратичная ошибка, тем лучше программа. В качестве иллюстрации возьмем три случайных хромосомы. представленных на рис. 9 в виде древовидных структур.

Например, структура, представленная на рис. 9 в виде дерева слева, была образована путем случайного выбора операции вычитания в качестве корневой вершины дерева. Затем случайно в качестве аргументов были выбраны операция деления (%) и константа ( 1). Для операции деления случайно была выбрана одна переменная Х. Программа реализует функцию Y1 = 2. Аналогично были построены два других дерева, реализующих функции Y2 = 2Х и Y3 = Х2 + 2 соответственно.

95

Рис, 9, Исходная популяция хромосом-программ

На рис. 10 представлены ошибки регрессии для каждой из трех случайно выбранных хромосом начальной популяции (область между кривыми на интервале [-1, 1]).

Рис, 10, Ошибка регрессии для трех программ

Вчастности, для программы, реализующей функцию Y1, область на интервале [-1, 1] между параболической кривой Y=Х2-Х+2

ипрямой Y1 графически иллюстрирует величину ошибки (величина интеграла абсолютной ошибки равна 1,0). Интеграл абсолютной ошибки для прямой Y2 равен 1,33, а для параболы Y3 – 1,0.

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

программы-потомки. Произведем мутацию для Y1 и кроссинговер между Y2 и Y3. Получаем деревья, представленные на рис. 11.

96

Рис. 11. Новая популяция хромосом-программ

Оператор мутации случайно заменяет в дереве, соответствующем Y1, вершину «%» на вершину «*», а правую вершину «Х» на вершину «–1». Перед выполнением одноточечного оператора кроссинговера случайным образом определяются точки кроссинговера в хромосомах, соответствующих Y2 и Y3. Пусть для родительской хромосомы Y2 это будет вершина «–», а для Y3 – правая вершина «Х» на дереве, представленном на рис. 9.

Оператор кроссинговера образует два потомка (–Х) и (Х2–Х+2) путем обмена списками между двумя программами при сохранении синтаксической корректности вновь получаемых программ, которые представлены на рис. 11.

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

ЭВОЛЮЦИОННЫЕ СТРАТЕГИИ

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

97

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

Без ограничения общности будем считать, что задача ЭС в терминах математического программирования состоит в минимизации целевой функции F(x1,x2,…,xn), где xi вещественные переменные (i=1,…, n). Каждому индивиду ЭС соответствует вектор в n-мерном пространстве, который представляет собой некоторое решение поставленной задачи. Кроме того, каждый индивид характеризуется некоторым среднеквадратичным отклонением σj (j=1,…,m; 1≤m≤n), которое для оператора мутации означает среднюю величину наследственной изменчивости. Величина σj является параметром, характеризующим адаптивные свойства ЭС. Будем считать, что, если 1<m<n, то σ1,…, σm-1 жестко связаны с переменными x1,…, xm-1, а величина σj для остальных переменных xm,…, xn является свободной. Отметим, что в большинстве практических приложений m = 1 или m = n.

Тогда алгоритм ЭС включает следующие шаги.

Ш а г 1. Инициализация модели предусматривает генерацию

начальной популяции P(t = 0) из μ индивидов вида ak (xk , k ) , где k = 1,…,μ.

98

Ш а г 3. Генерация потомков. Задача состоит в получении λ потомков из μ родителей. Для этого необходимо выбрать родителей, провести их рекомбинацию и репликацию (копирование и передача фенотипа родителей потомкам), а затем мутацию потомков.

промежуточной популяции.

Ша г 5. Селекция.

Ша г 6. Проверка условий остановки алгоритма ЭС. Критериями остановки алгоритма ЭС являются максимальное число шагов эволюции tmax, отсутствие прогресса в смысле заметного улучшения значений целевой функции, малая разница между лучшим

ихудшим значением функции для текущей популяции и т.п.

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

Решение. Вначале оценим вероятность получения необходимой строки песенного текста случайным способом. Для каждой позиции текста возможны 32 различные буквы русского алфавита. Таких позиций в заданном выражении 12. Тогда искомая вероятность равна (1/32)**12 ≈ 1,27*10**(-18).

В таблице ASCII строка «По Дону гуляет» преобразуется в следующую хромосому:

[207, 238, 196, 238, 237, 243, 227, 243, 235, 255, 229, 242],

Сгенерируем исходную популяцию, например из 10 случайных фраз:

99

Если преобразовать эти хромосомы в строки символов, то получится 10 бессмысленных фраз:

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

Лучшее значение целевой функции, равное 3, в исходной популяции дает строка символов <щимерфгужфют>. Запустим ЭА. В таблице приведен список хромосом, которые были наилучшими на каждой из 32-х итераций ЭА.

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

Решение. Формально эта задача сводится к поиску оптимальной перестановки, при заданных значениях затрат ciψ(i) на установку i-й машины на j-е место, затратах aik на транспортировку

100