Теоретические основы ГА

Математическая модель ГА может быть представлена следующим упорядоченным набором:

,

где

– система кодирования (Coding system);

– функция пригодности (Fitness function);

– начальная популяция (Initial population);

– размер начальной популяции (Population size);

– операция селекции (Selection operation);

– операция скрещивания (Crossover operation),

– вероятность скрещивания (Probability of crossover);

– операция мутации (Mutation operation),

– вероятность мутации (Probability of mutation);

– условие остановки (Termination condition).

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

,

где

- пространство вещественных векторов размерности ;

- пространство двоичных строк длины .

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

Начальная популяция есть набор равномерно распределенных в пространстве кодирования элементов. В случае двоичного кодирования - набор различных двоичных строк длины .

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

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

На рис.2.24 представлена блок-схема операций кодирования и вычисления значения функции пригодности.

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

Блок-схема реализации оператора селекции представлена на рис.2.25.

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

Рис. 2.24. Операции кодирования и вычисления объектных функций ГА

Рис. 2.25. Блок-схема реализации операции селекции методом рулетки.

Входом операции скрещивания является промежуточная популяция, получаемая после операции селекции .

Операция скрещивания (на примере бинарного кодирования ) реализуется следующими шагами:

1. Выбрать два индивидуума из промежуточной популяции;

2. Сгенерировать случайное число, равномерно распределенное на интервале [0, 1] и если полученное число меньше , выполнить операцию скрещивания, если нет, перейти к шагу 5;

3. Сгенерировать точку скрещивания, равномерно распределенное случайное число на интервале [0, l];

4. Поменять местами части выбранных индивидуумов, правее точки скрещивания;

5. Поместить выбранные хромосомы в новую популяцию;

6. Повторить шаги 1-5 до заполнения новой популяции.

Блок схема операции скрещивания представлена на рис. 2.26.

В некоторых реализациях ГА, операция скрещивания применяется несколько раз для одних и тех же хромосом. В таком случае говорят о двухточечном скрещивании (two-point crossover). Выбор числа применений операции скрещивания зависит от конкретной задачи, а также связан со значениями основных параметров ГА.

Рис. 2.26. Блок-схема реализации операции скрещивания

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

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

Алгоритм мутации реализуется следующими шагами:

1. Выбрать случайным образом индивидуум из промежуточной популяции;

2. Сгенерировать случайное число равномерно распределенное на интервале [0 1]. Если полученное число меньше , выполнить операцию мутации. В противном случае перейти к шагу 5;

3. Сгенерировать точку мутации (mutation point) - случайное число равномерно распределенное на интервале [0 l];

4. Инвертировать бит, находящийся в точке мутации;

5. Поместить выбранную хромосому в новую популяцию;

6. Повторить шаги 1-5 до заполнения популяции.

Блок – схема реализации операции мутации представлена на рис. 2.27.

Рис. 2.27. Блок-схема реализации операции мутации

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

Фундаментальная теорема Холланда

Оптимизация с помощью ГА основывается на фундаментальной теореме Холланда (Fundamental Theorem of GA).

Прежде, чем привести данную теорему, дадим необходимые определения.

Простой ГА обычно использует бинарное кодирование для хромосом (строк). Будем говорить, что такие строки генерируются в алфавите A = {0,1}. Каждый символ (бит) в строке идентифицируется своим положением (бит-позицией). Бит-позиция равная 1 означает первый левый символ в строке.

Определение: схема (a schema) S есть строка, построенная с помощью алфавита A’ = {0,1,*}, где «*» означает: «неважно какой символ» в данной позиции. Например, следующая строка является схемой:

S = * 1 * 0 * * 0 0. (2.12)

Определение: представитель схемы (a representative of a schema)

Строка, совпадающая со схемой во всех ее определенных (0 или 1) бит-позициях, называется представителем данной схемы.

Например, следующие ниже строки A, B, и C являются представителями схемы S, приведенной в (2.12).

A = 1 1 0 0 1 0 0 0

B = 0 1 1 0 0 0 0 0

C = 1 1 1 0 1 1 0 0.

Определение: порядок схемы (an order of a schema)

Порядком схемы, o (S), называется число определенных (0 или 1) бит-позиций

Например, схема S, приведенная в (2.12), имеет порядок o (S) = 4.

Определение: определяющая длина схемы (a defining length of a schema)

Определяющей длиной схемы, (S), называется расстояние между самой левой определенной (0 или 1) бит-позицией () и самой правой определенной (0 или 1) бит-позицией (). (S) вычисляется как: .

Например, схема S, приведенная в (2.12), имеет следующую определяющую длину:

(S) = = 8 2 = 6.

Скрытый параллелизм ГА

Предположим, что имеем дело со строками длины . Каждая строка представляет схем.

Например, строка 1101 имеет длину 4, и, следовательно, представляет 2⁴ =16 следующих схем:

1100, 110*, 11*0, 11**, 1*00, 1*0*, 1**0, 1***, *100, *10*, *1*0, *1**, **00, **0*, ***0, 0***, ****.

Популяция из строк удовлетворяет следующему неравенству:

,

где - общее число схем.

Так как каждая строка может представлять много схем, то это значит, что ГА операторы, работающие с популяцией строк, тем самым работают с еще большим числом схем. Это свойство называется свойством скрытого параллелизма ГА (implicit parallelism of GA).

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

=?

Это число зависит от ГА операторов репродукции, кроссовера и мутации. Ответ на этот вопрос дается в следующей фундаментальной теореме Холланда.

Теорема схем (Schema Theorem): фундаментальная теорема ГА

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

где:

- число представителей схемы S в момент времени t;

- среднее значение функции пригодности для схемы S;

- среднее значение функции пригодности для всей популяции;

- вероятность оператора кроссовера; - длина строки (хромосомы);

- определяющая длина схемы S; - порядок схемы S;

- вероятность мутации.

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

Обсудим характерные особенности ГА

1. Замечательная черта ГА состоит в том, что они выполняют множество изощренных манипуляций с решениями задачи без малейшего представления о том, что же при этом происходит. Процедура кроссинговера берет два решения и создает из них два новых решения, смешивая части первого и второго. Все, что для этого нужно, - выбор случайной позиции в битовой строке и перестановка двух подстрок. Единственное, что нужно также знать, - длину двоичной хромосомы. То же самое относится и к процедурам мутации, и даже создания начальной популяции. Благодаря этому свойству достаточно один раз программно реализовать ГА, а потом использовать его для решения множества самых разнообразных задач без сколько-нибудь серьезного изменения кода.

2. Конструирование хромосомы является самым важным этапом создания ГА.

3. Функция пригодности (ФП) - это единственная часть программы, которая должна понимать, что же на самом деле кодирует хромосома. Поэтому для каждого приложения надо писать новые ФП.

4. Объем пространства поиска - важнейший, хотя и не единственный фактор, влияющий на качество работы ГА. Большие пространства труднее "обыскать", и шансы найти оптимальное или просто хорошее решение уменьшаются.

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

Рис. 2.28. Различные пространства поиска для ГА

В заключение этого параграфа обсудим также основные различия между классическими методами оптимизации и ГА.

Основные различия между классическими методами оптимизации и ГА

1. Классические методы оптимизации представляют собой класс методов, базирующихся на вычислении производной оптимизируемой функции (derivative based methods). В отличие от них ГА-оптимизация не требует производных значений (derivative free optimization) функции пригодности. Таким образом, ГА могут использоваться как для непрерывных, так и для дискретных оптимизационных проблем.

2. Классические методы оптимизации работают с параметрами данной задачи оптимизации. ГА оперирует с популяцией закодированных параметров. Таким образом, параметры проблемы (оптимизации) должны быть закодированы строками конечной длины. Строки могут представлять последовательности из любых символов. Обычно в ГА используются бинарные символы (0 или 1). Выбор метода кодирования параметров – очень важен.

3. ГА-оптимизация осуществляется на множестве строк с использованием вероятностного механизма и вычисления значений пригодности строк.

4. ГА может работать без привлечения каких-либо знаний о пространстве поиска и является проблемно независимым алгоритмом.

5. ГА обеспечивает средствами поиска оптимального решения в плохо структурированных областях (in poorly understood and irregular spaces).