Основные этапы и блок-схема ГА

Этап 2: Оценка пригодности (Fitness evaluation)

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

После того, как каждый член популяции оценен, переходим к следующему шагам (3 и 4).

Этап3: Селекция (Selection)

Сформируем промежуточную популяцию (an intermediate population) (называемую также как «пул для спаривания» (mating pool), или множество возможных «родителей») с помощью оператора репродукции или селекции (reproduction, или selection operator).

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

Вероятность того, что индивидуум будет копирован в следующую генерацию, зависит от отношения величины его пригодности к общей суммарной величине функции пригодности всех индивидуумов популяции F. Это отношение называется ( / F) относительной пригодностью (a relative fitness).

Репродукция производится посредством серии случайных попыток (random trials), в которых каждая хромосома копируется в промежуточную популяцию такое число раз, которое пропорционально ее относительной пригодности. Эта случайная процедура, например, может быть подобна известной случайной процедуре Монте-Карло, называемой также «колесом фортуны» (или рулеткой) (Monte Carlo random procedure, или “wheel of fortune” (Roulette wheel)).

На рис.2.22 показана процедура метода Монте-Карло.

Каждая хромосома в процедуре «рулетки» занимает площадь пропорциональную ее относительной пригодности. Ожидаемое число раз (= ) того, что хромосома будет отобрана (selected) в серии попыток (обычно равных размеру популяции) определяется следующим образом:

, (2.10)

где N – размер популяции и

. (2.11)

Рис. 2.22. Иллюстрация процедуры Монте-Карло

Примечание 1. Мы аппроксимируем число в формуле (2.10) до ближайшего целого.

Примечание 2. Помимо процедуры «рулетки» могут использоваться другие методы селекции. Например, такие, как:

· uniform selection: каждая хромосома имеет равный шанс быть выбранной независимо от ее пригодности;

· tournament selection: небольшое число хромосом выбираются некоторым способом, после чего они соревнуются друг с другом на основе пригодности;

· Selection with elitism: лучшие хромосомы переводятся в следующее поколение без изменения. Остальные хромосомы участвуют в селекции.

В отсутствие любого другого механизма, процедура селекции со временем «заставит» «лучших» индивидуумов занимать все большую долю в популяции.

Этап 4: Кроссинговер (скрещивание) и мутация (Crossover and Mutation) На этом этапе происходит генерация следующей популяции с помощью применения к промежуточной популяции генетических операторов. При этом выбранные хромосомы обмениваются генами, образуя новое множество индивидуумов – новую популяцию. Рассмотрим два основных генетических оператора поиска: кроссинговер и мутация.

Кроссинговер оператор

Кроссинговер является первичным. Он осуществляет следующие функции:

1. выбирает двух «родителей»,

2. комбинирует гены (черты) родителей,

3. формирует двух «похожих детей», т.е. потомков (offspring).

Существует много типов кроссинговера. Простейший из них описывается следующим образом. Пара родителей выбирается случайным образом. Для каждой пары также случайным образом выбирается так называемая «точка кроссовера» (a point of crossover) (одна, или две, или несколько). Эта точка указывает, какое число бит с правого конца каждой хромосомы (строки битов) должно обменяться друг с другом. Например, если пара родителей представляется в виде следующих строк-хромосом: и . Пусть точка кроссовера = 3 и пусть эта точка показывается символом “ “. Тогда имеем следующую схему обмена:

и .

Кроссовер оператор сгенерирует следующих «потомков»:

и .

Можно видеть, что непрерывные группы бит с правого конца хромосом обмениваются своими значениями.

Примечание. Существуют другие типы оператора скрещивания, например, такие как:

a) Uniform crossover:

Чтобы обобщить процесс кроссовера, в этом случае используется специальная строка, называемая a crossover mask. 1 в строке-маскеозначает, что соответствующие биты в хромосомах должны обменяться своими значениями. 0 означает, что обмена не происходит.

b) Linear interpolation 2-point crossover:

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

Оператор мутации

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

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

Этап 5: Критерий останова (Checking of the End_Test)

t = t+ 1; IF NOT (End_Test) THEN go to Step2; else stop.

Критерий останова (“End_Test”) описывает условия окончания ГА. Обычно это либо заданное общее число генераций поколений (например, 200), либо общее время работы (например, 3 часа) и т.д. По окончанию работы ГА, индивидуумы последней популяции представляют решение заданной задачи оптимизации. Рассмотрим простой пример оптимизации с помощью ГА.

Пример: Оптимизация на основе ГА.

Поставим следующую задачу: найти максимум функции на интервале целых чисел [0-31] с помощью механизма поиска ГА. Итак, имеем следующую проблему для ГА:

найти величину , которая дает максимум функции пригодности .

Прежде всего, ГА работает с хромосомами (закодированными параметрами проблемы, которую оптимизируем). Следовательно, параметры нашей задачи, а именно числа интервала [0-31] должны быть закодированы. Будем использовать бинарное кодирование. Рассмотрим строки, состоящие из пяти бит: от {00000} до {11111}.

Примечание. Бинарная строка длины может представлять индивидуумов. Следовательно, строки длиной могут представлять числа 1,2,3,...,32 (25 = 32). Пусть начальная популяция сформирована случайным образом, например, так, как показано в Таблице 2.2.