Формирование начальной популяции

Как правило, начальная популяция формируется случайным образом. При этом гены инициализируются случайными значениями.

Пример подобной инициализации представлен ниже:

i = 0;

ПОКА (i < РАЗМЕР_ПОПУЛЯЦИИ) {

j = 0;

ПОКА (j < ЧИСЛО_ГЕНОВ) {

ОСОБЬ[i].ГЕН[j] = СЛУЧАЙНАЯ_ВЕЛИЧИНА;

j = j+1;}

i = i+1;}

Оценивание популяции необходимо для того, чтобы выявить в более приспособленных и менее приспособленных особей.

Для подсчета приспособленности каждой особи используется функция приспособленности (целевая функция, фитнес функция)

fi = f(Gi),

где Gi = { gik | k = 1,2,...,N } – хромосома i-й особи, gik – значение k-го гена i-й особи, N – количество генов в хромосоме.

Стандартные операторы для всех типов генетических алгоритмов это:

– селекция,

– скрещивание и

– мутация.

Селекция

Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности.

Существуют как минимум два популярных типа оператора селекции: рулетка и турнир.

Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Psel(i) вычисляемой по формуле:

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

Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

Скрещивание

Оператор скрещивание (crossover) осуществляет обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции.

Может быть одноточечным или многоточечным. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва.

Точка разрыва - участок между соседними битами в строке.

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

Мутация

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

На рис. оператор мутации (четвертый ген мутировал)