qweqweqe123123

Основные принципы

В литературе генетический алгоритм Холланда обычно называется простым генетическим алгоритмом (simple genetic algorithmSGA). В основе SGA лежит популяция двоичных строк. Каждая такая строка, состоящая из нулей и единиц, кодирует решение задачи оптимизации. По сути, она эквивалентна конфигурации в методе модельной закалки. Алгоритм начинает работу с определенного количества строк, которые называются популяцией первого поколения. При помощи генетических операторов (мутации и кроссовера) алгоритм создает следующее поколение из строк текущей популяции. Преимущество в воспроизводстве имеют более совершенные строки, так что в следующем поколении преобладает их «потомство». Цикл воспроизводства повторяется до тех пор, пока не выполнится заданный критерий завершения. Общую схему генетического алгоритма демонстрирует рис. 9.12. Подробное описание важных составляющих этой схемы дается в последующих разделах.

 

Механизм кодирования

Структура генетического алгоритма во многом определяется механизмом кодирования, используемым для представления переменных задачи оптимизации. Эти переменные (называемые генами) объединяются вместе и образуют строку значений (называемую хромосомой). Например, если мы должны найти максимум функции трех переменных F(x, у, z), мы можем представить каждую переменную 10-разрядным двоичным числом (при условии правильного выбора масштаба). При этом хромосома будет содержать три гена, а ее длина будет равна 30 двоичным разрядам (битам).

Основные принципы

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

Переменные оптимизации представляются строкой или хромосомой, несмотря на то что они могут принимать непрерывный ряд вещественных значений. Широко используется метод кодирования через целочисленное представление. Сначала к переменным применяется линейное отображение на подмножество целых чисел, после чего целое число кодируется фиксированным числом битов. Предположим, например, что непрерывная переменная оптимизации определена на отрезке [-1,28; 1,28]. Мы можем закодировать такую переменную с точностью до двух знаков после запятой, умножив ее вещественное значение на 100 и отбросив дробную часть результата. Таким образом, значение переменной будет отображено на целые числа от -128 до +128. Двоичное представление целого числа вычислить очень легко (листинг 9.3) [33].

Листинг 9.3. Общий вид генетического алгоритма BEGIN /* Генетический алгоритм */

Создать начальную популяцию:

Рассчитать приспособленность каждого индивидуума:

WHILE NOT расчет закончен DD

BEGIN /* порождение нового поколения */

FOR размер популяции/2 DD BEGIN /* Цикл воспроизводства */

Выбрать двух индивидуумов из предыдущего поколения для размножения;

/* Преимущество у более приспособленных */

Рекомбинировать хромосомы индивидуумов:

Рассчитать приспособленность потомка:

Добавить потомка в новую популяцию;

END

IF популяция конвергировала THEN расчет закончен TRUE:

END

END

 

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

Для оценки приспособленности строк должна использоваться целевая (оптимизируемая) функция. Однако диапазон значений этой функции зависит от конкретной задачи. Для обеспечения однородности алгоритма по отношению к различным задачам мы выбираем функцию пригодности, нормирующую целевую функцию на удобный отрезок [0, 1]. Нормированное значение целевой функции считается коэффициентом пригодности строки, который используется механизмом отбора для сравнения строк, составляющих популяцию [33]. Целевая функция нормируется таким образом, что максимальная пригодность соответствует оптимальной ситуации.

 

Механизм отбора

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

Основные принципы

В нашем примере вторая строка получит одного потомка, а вероятность получить второго будет равна 0,99. Четвертая строка также получит одного потомка, а с вероятностью 0,22 — и второго. Итак, вторая и четвертая строки точно получают по одному потомку. Остается выбрать, какая именно получит двух оставшихся потомков. Мы выбираем первую строку (0,58) и вторую строку (0,99), потому что вероятности у них больше, чем у третьей и четвертой строк (0,22 и 0,21 соответственно). Заметьте, что для второй и четвертой строк вероятности были уменьшены на 1, потому что эти строки уже получили по одному потомку. Таким путем создается новая популяция, в которой среднее значение приспособленности оказывается выше.

 

Воспроизводство

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

Хромосомы двух выбранных родительских особей рекомбинируются. Обычно это осуществляется механизмами кроссовера и мутации. При кроссовере берутся два индивидуума, хромосомы которых разрезаются на части в случайных местах, в результате чего получаются два «головных» сегмента и два «хвостовых» сегмента. Затем «хвостовые» сегменты меняются местами, в результате чего получается две хромосомы нормальной длины (рис. 9.13). Это называется кроссовером в одной точке (single-point crossover) [33]. В каждой из двух хромосом оказываются гены обоих родителей.

Основные принципы

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

Мутация применяется индивидуально к каждому потомку после кроссовера. Оператор мутации случайным образом изменяет каждый ген с малой вероятностью (обычно 0,001), причем 0 заменяется на 1 и наоборот. Реализуется это при помощи генератора случайных чисел, так же как и при кроссовере. 9-й и 17-й гены мутированной хромосомы показаны на рис. 9.14. В генетических алгоритмах мутация рассматривается как вторичный оператор, предназначенный для возвращения утраченного генетического материала. Представьте, например, что все строки популяции имеют в какой-то позиции значение 0, тогда как оптимальное решение должно в этой же позиции иметь значение 1. Только мутация, но не кроссовер, может восстановить эту единицу.

Основные принципы

 

Конвергенция

При правильной реализации генетического алгоритма популяция развивается от поколения к поколению таким образом, что приспособленность лучшего и среднего индивидуума в каждой популяции стремится к глобальному оптимуму. Конвергенцией называется развитие в направлении возрастания однородности. Считается, что по конкретному гену достигнута конвергенция, если он имеет одно и то же значение у 95% индивидуумов популяции [56].

Смотрите также