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

Еnd.

End while

While not termination do

Begin

Мобильные ГА

В мобильных ГА длина хромосома может быть переменной (имеют дело со строками переменной длины). Строки могут быть переопределены (хромосома несёт избыточную информацию) или недоопределены (хромосома другой информацией).

В мобильных ГА используются два дополнительных оператора:

· Cut (разрезание)

· Splice (сцепление)

<номер гена: значение гена>

t =0; //начальный момент времени эволюции

init_population (P_r^t); // инициализация популяции

// r – число хромосом, t - время

p^p_preparing-population; // насыщение популяции

p_r^p; //селекция хромосом

p_r^cr = cut or splice (p_r^s); //разрезание

p_r^m = mutation (p_r^cr); // мутация

p^t+1 =gen (p ^p, p_r^cr, p_r^m);

t=t +1;

Отличия мобильного ГА от классического ГА:

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

2. Возможность формирования хромосом в популяции на каждом этапе оптимизации.

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

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

Схема (шаблон) – описывает набор строк (подмножество всех возможных строк) с подобными значениями в некоторых позициях. Схема представляет собой строку длиной l, состоящую из символов алфавита {0, 1, *}.

Пример: 0*10 = {0010, 0110}

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

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

Фиксированные позиции в схеме – позиции, в которых находятся 0 или 1.

Для каждой схемы определяется два параметра:

1. порядок схемы – определяется количеством фиксированных позиций в схеме;
2. длина схемы – расстояние между самыми дальними фиксированными позициями.

=4

=6

=2

=0

=1

Теорема схем:

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

Использование оператора кроссинговера приводит к меньшему разрушению схем с малой длиной. Это позволяет сохранить представительство хромосом, соответствующих данной схеме, в следующих поколениях.

Оператор мутации реже разрушает схемы с низким порядком.

Холланд доказал, что если ГА явным образом обрабатывает n строк в каждом поколении, то в то же время не явным образом, использую строительные блоки, он обрабатывает n ³ строк с высокой функцией фитнесса.

Строительные блоки – схемы с высокой функцией фитнесса, короткой длиной и малым порядком.

Запись теоремы схем в формальном виде:

m (H, t) – число представителей схемы H на шаге t.

Вычислим ожидаемое число представителей схемы H в следующем поколении (на шаге t +1) m (H, t +1):

Каждой схеме ставится в соответствие значение вероятности её выживания в следующем поколении:

где fit (H) – приспособленность данной схемы;

fit_ср – средняя приспособленность в данной популяции.

Вероятность того, что схема не будет разрушена оператором кроссинговера, равна:

, где l – количество бит в строке.

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

Схема переживёт мутацию, если выполняется условие:

.

Формальное описание теоремы схем:

.

Выводы:

1. Значения функций приспособленности fit (H) и fit_ср изменяются в процессе эволюции, поэтому чем больше отношение , тем больше вероятность попадания схемы в популяцию.

мера давления отбора.

2. Увеличение значений приводит к расширению пространства поиска, но не к увеличению количества хороших схем. С уменьшением значений увеличивается использование хороших схем, но тормозится исследование пространства. Поэтому необходимо соблюдать баланс между пространством используемых схем и пространством поиска.

3. Теорема схем даёт качественную картину функционирования ГА, снабжает разработчика знаниями о хороших способах кодирования, реализации и применении операторов ГА.

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

Дата добавления: 2014-01-15