5.2.5.       Реализация блоков ПГА

Генерация первого поколения.

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

Значения байтовых параметров, представляющих собой битовую строку-хромосому, определяются с помощью генератора псевдослучайных чисел, равномерно распределенных на интервале [0; 255]. Для этого используется по следовательно сть Равномерно, описанная в объекте констант функций и по следовательно стей. Значения остальных параметров создаваемых ресурсов-особей равны нулю, за исключением следующих: номер поколения устанавливается равным 1, номер особи устанавливается равным текущему значению счетчика особей, параметр Статус приобретает значение «Не_рассмотрен» (для первого поколения это не имеет значения, поскольку этот параметр используется при подборе пар для скрещивания, поэтому можно было бы присвоить любое значение из возможных), значение функции пригодности устанавливается равным —1,0, это является признаком того, что функция пригодности для данной особи еще не вычислялась. Значение параметра Количество потомков будет определено при воспроизведении, параметров Значение_ФП, Сумма_до и Сумма_после — в блоке расчета функции пригодности. Параметры Родитель_1, Родитель_2, Скрещивание байт, Скрещивание бит, Мутация байт и Мутация_бит, описывающие обстоятельства появления данной особи, для первого поколения не имеют смысла.

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

параметров Среднее_значение_ФП, Минимальное_значение_ФП, Мак- симальное_значение_ФПв блоке расчета функции пригодности, параметра. Количествоскрещиваний— в блоке скрещивания, параметра. Количество _мутаций — в блоке мутаций.

Расшифровка битов и расчет функции пригодности.

Этот блок описывают два. образца-правила. Расшифровка _битов_ и __ расчет ФП и 0бразец_Конец_ расшифровки. Первое правило вычисляет значение функции пригодности и выполняет ряд других действий для каждой особи поколения, увеличивая счетчик особей. Когда, поколение обработано, второе правило переключает режим (следующим блоком является воспроизведение), обнуляет счетчик особей, определяет значение вспомогательного параметра. Система.Число, необходимое при воспроизведении для розыгрыша, родителя (см. далее), вычисляет среднее значение функции пригодности для поколения, которое является одной из важнейших характеристик поколения и отражает эффективность работы ПГА. Среднее значение функции пригодности вычисляется как сумма, значений функции пригодности (накапливается первым правилом), деленная на. количество особей в поколении.

Рассмотрим подробнее образец Расшифровка _битов_ и расчетФ П. Он имеет четыре релевантных ресурса.:

•    Общий, представляющий в образце ресурс Система;

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

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

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

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

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

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

•    подготовка, данных для взвешенного розыгрыша, родителя в блоке воспроизведения;

•    расшифровка битовой строки для определения значений Х\ и Х2, вычисление координат точки, изображающей особь в пространстве поиска.

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

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

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

где Ві — г-й байт строки-хромосомы (первый параметр); п — номер бита, с которого начинается подстрока; I — длина подстроки.

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

Вызов функции I    IfEQZero для подсчета, например, количества битов,

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

Функцией пригодности является сама оптимизируемая функция /, для вычисления ее значения используется алгоритмическая функция Вычис- ление ФП, параметрами которой являются расшифрованные значения Х\ и Х2.

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

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

ного ресурса Особь). Параметр Сумма_ после вычисляется прибавлением значения функции пригодности данной особи к накопленной ранее сумме.

Воспроизведение

Воспроизведение является первым этапом генерации нового поколения. Этот блок также реализован двумя правилами: Образец^ Воспроизведение

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

Центральной проблемой при воспроизведении является выбор особей для включения в следующее поколение с вероятностью, пропорциональной значению функции пригодности. Это реализовано следующим образом. Значения всех функций пригодности суммируются в блоке вычисления функции пригодности. Последовательностью Розыгрыш_ родителя генерируется псевдослучайное число, равномерно распределенное на интервале от нуля до суммы значений функции пригодности для всех особей. Каждой особи на этом интервале соответствует подинтервал, границы которого задаются параметрами Сумма до и Сумма_после, которые вычисляются таким образом, что подынтервалы для разных особей примыкают друг к другу, но не пересекаются, а. длина интервала равна значению функции пригодности данной особи. Потомка получает особь, которой соответствует подынтервал, на который попало псевдослучайное число. Поскольку при равномерном распределении вероятность попадания случайного числа на некоторый интервал пропорциональна длине этого интервала, то вероятность выбора особи для воспроизведения пропорциональна значению функции пригодности этой особи.

Предусловие выбора родителя записывается в образце так:

Choice from Родитель.Номер_поколения=Общий.Номер поколения and

Родитель. Сум ма_ до <= Общий.Число and

Родитель. Сум ма_ после >= Общий.Число

Битовая строка-хромосома, переносится в особь-потомок из особи-роди- теля. Параметры, описывающие происхождение особи-потомка, обнуляются за исключением параметра Родитель _1, которому присваивается номер особи-родителя. Такое сочетание значений этих параметров обозначает, что данная особь получена в результате простого воспроизведения из родителя с номером Потомок. Род и тел ь_ 1 (при выполнении скрещивания и мутации значения этих параметров могут быть изменены).

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

поскольку конверторы в РДО выполняются после проверки предусловий для всех релевантных ресурсов).

Скрещивание (кроссингоеер).

Блок скрещивания имеет ряд особенностей в реализации общей схемы вычислений, связанных с тем, что не каждая пара особей подвергается скрещиванию и количество пар-кандидатов на скрещивание заранее неизвестно. Первая особенность состоит в том, что для реализации этого блока используются три образца-правила, а не два: 0бразец_Скрещивание, выполняющий собственно скрещивание, т. е. создание двух гибридов из пары отобранных особей в случае, если скрещивание данной пары происходит; 0бразец_Подбор_пар, подбирающий пары особей и определяющий, произойдет ли скрещивание данной пары, и 0бразец_Конец_скрещивания, завершающий блок и переключающий режим. Вторая особенность — это то, что параметр Система.Счетчик считает в этом блоке не особи, а пары. Третья особенность заключается в модификации предусловия образца, заканчивающего скрещивание. Оно не содержит проверки значения счетчика, поскольку количество пар-кандидатов на скрещивание заранее не известно. Скрещивание завершается тогда, когда образец 0бразец_Подбор_пар не смог подобрать очередной пары.

Взаимодействие образцов происходит с использованием параметра Си- стема.Число. При завершении блока воспроизведения ему присваивается значение 2,0. В предусловии образца Образец Скрещиваниезначение этого параметра сравнивается с вероятностью скрещивания, хранящейся в параметре Система.Вероятность_скрещивания. Правило применяется лишь в том случае, если значение параметра Система.Число меньше вероятности скрещивания (т. е. если оно попало на интервал от нуля до вероятности скрещивания), а такое значение ему может быть присвоено только в образце 0бразец_Подбор_пар. Таким образом, сначала подбирается пара особей и параметру Система.Число присваивается псевдослучайное значение, равномерно распределенное на интервале [0,1]. Затем, если предусловие применения образца 0бразец_Скрещивание выполняется, производится скрещивание данной пары особей и параметру Система.Число присваивается значение 2,0, что предотвращает повторное применение образца. Если же сгенерированное случайное число оказалось больше вероятности скрещивания, то скрещивания данной пары особей не происходит. Такое предусловие в сочетании с тем, что параметру Система.Число присваиваются равномерно распределенные на интервале [0,1] псевдослучайные значения, обеспечивает заданную вероятность скрещивания.

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

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

Подбор пар происходит следующим образом.

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

В этом же образце разыгрывается, произойдет ли скрещивание, номера особей подобранной пары заносятся в параметры ресурса Система для возможного использования в образце 0бразец_Скрещивание и определяется потенциальное место скрещивания — номер байта и номер бита, которые также заносятся в параметры ресурса Система. Номер байта вычисляется как равномерно распределенное на интервале от одного до количества байтов в строке-хромосоме псевдослучайное целое число, номер бита — как псевдослучайное целое число, равномерно распределенное на интервале от одного до восьми, если байт не последний в строке-хромосоме и на интервале от одного до количества битов в последнем байте минус 1 для последнего байта. Разрыв битовой строки при скрещивании происходит за битом, номер которого сгенерирован.

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

Л

+

Функция имеет три параметра: номер байта в строке-хромосоме и два байта, представляющие собой соответствующие байты в битовых строках двух родителей. Результатом функции является байт, содержащий биты второго параметра функции для битов, находящихся левее места скрещивания, и биты третьего параметра для битов, находящихся правее места скрещивания. Значение функции вычисляется следующим образом. Если первый параметр меньше номера байта, в котором происходит скрещивание (байт находится левее), то результатом функции является значение второго параметра, если больше — то значение третьего параметра. Если первый параметр равен номеру байта, в котором происходит скрещивание, а номер бита ш, определяющий место скрещивания, равен 8, то скрещивание происходит на границе байтов за данным байтом и значение функции равно значению второго параметра. Наконец, если скрещивание происходит в текущем байте, а т меньше 8, то для формирования результата необходимо взять т первых бит из второго параметра функции и остальные 8 — т бит — из второго параметра. Для этого используется уже обсуждавшаяся функция Извлечь.

Параметрам гибридов Родитель_1 и Родитель_2 присваиваются номера о собей-родите лей, параметрам СкрещиваниебайтиСкрещиваниебит присваиваются номер байта и номер бита, определяющие место скрещивания. Значения этих параметров позволяют проследить происхождение особи. Наконец, для статистики накапливается количество скрещиваний в данном поколении (параметр Поколение.Количество_скрещиваний).

Мутация.

Блок мутации завершает генерацию поколения, он реализован двумя образцами-правилами: 0бразец_ мутация и 0бразец_Конец_мутации. Первый образец последовательно рассматривает все особи, определяя, произойдет ли мутация в данной особи, и генерируя потенциальное место мутации. Для реализации мутаций с заданной вероятностью использована

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

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

Собственно вычисление битовой строки мутанта производит алгоритмическая функция П ара метр _ мутанта, текст которой приведен ниже.

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

Расположение особей популяции в пространстве поиска в начале про™ десса оптимизации и на 20 шаге представлено на рисунках (рис. 5.8-5.12). Напомним, что оптимальное значение функции пригодности находится в верхнем правом углу пространства поиска.