М.В.Бураков. Генетический алгоритм. 2008

Нужно заметить, что существует множество решений рассмотренной задачи, поэтому можно конкретизировать решение, напри-

мер: a + b + c + d → min.

Вопросы для самопроверки

1.В каких инженерных задачах может использоваться ГА?

2.Какой метод оптимизации является наиболее простым?

3.Чем отличается мультимодальная целевая функция от унимо-

дальной?

4.Какие особенности объединяют различные методы глобаль-

ной оптимизации?

5.Чем отличается оптимальное решение от субоптимального?

6.Чем отличаются детерминированные методы глобальной оп-

тимизации от стохастических?

7.В чем заключается идея метода мультистарта в глобальной оптимизации?

8.Какие физические аналогии использует метод имитации от-

жига?

9.Как изменяется искусственная температура в алгоритме ими-

тации отжига?

10.Какая формула описывает количество вариантов в задаче коммивояжера для n городов?

11.Сформулируйте основные отличия ГА от других методов гло-

бальной оптимизации.

12.Имеет ли смысл использование ГА совместно с другими ме-

тодами оптимизации?

13.Что такое естественный отбор?

14.В чем заключается гипотеза пангенеза?

15.Могут ли наследоваться приобретенные признаки?

16.Почему генетика дала новый импульс дарвинизму?

17.Что представляет собой хромосома живого организма?

18.Чем отличаются половые клетки от соматических?

19.Насколько велики генетические отличия человека от выс-

ших приматов?

20.Почему у одних и тех же предков могут быть непохожие по-

томки?

21.Что является причиной появления новых биологических ви-

дов в соответствии с дарвиновской теорией эволюции?

22.Сформулируйте основные возражения против теории эволю-

ции по Дарвину.

23.Что такое популяция?

24.Что такое фенотип и генотип?

31

25.Как называются составные части хромосомы?

26.Что такое локус и аллель?

27.Перечислите основные генетические операции.

28.Назовите дополнительные генетические операции.

29.Как называется в ГА целевая функция?

30.Что может выступать в качестве целевой функции при при-

менении ГА в инженерных задачах?

31.Какой алфавит можно использовать при описании хромосом

винженерных задачах?

32.Как называются шаблоны, разделяющие пространство поис-

ка?

33.Сколько схем существует в задаче, где хромосома состоит из

4-х битов?

34.Как генерируется первоначальная популяция в ГА?

35.На основании чего происходит отбор хромосом в промежу-

точную популяцию?

36.Какие существуют варианты для выполнения операции от-

бора (селекции) в классическом ГА?

37.Опишите метод колеса рулетки для отбора в промежуточную популяцию.

38.Как выполняется операция скрещивания в классическом ГА?

39.Как выполняется операция мутации в классическом ГА?

40.Как формируется хромосома при решении диофантова урав-

нения?

41.Как рассчитывается относительная пригодность при поиске решения диофантова уравнения?

42.Как выполняются генетические операции при решении дио-

фантова уравнения?

32

2. Механизмы работы генетического алгоритма

2.1. Строительные блоки в генетическом алгоритме

Теория строительных блоков была предложена Д. Голдбергом [3]. Она позволяет понять механизмы видоизменения популяции под действием генетических операторов. Рассмотрим влияние операции селекции на преобразование схем популяции.

Введем обозначения:

P(k) – популяция на k-м шаге (итерации); N – мощность популяции;

сhi – i-я хромосома;

F(chi) – пригодность i-й хромосомы; S – схема;

F(chiS) – значение ОП i-й хромосомы, включающей схему S; n(S, k) – количество хромосом, соответствующих схеме S на k-м

шаге (т. е. n(S, k)=card { P(k) ∩ S });

F(S, k) – пригодность схемы k-й итерации или среднее значение пригодности хромосом из популяции P(k), которые соответствуют схеме S.

Очевидно:

n(S, k)

∑ F(chiS)

F(S, k) = i=n(S, k) .

Рассмотрим суммарную пригодность хромосом из популяции

P(k)

N

F(k) = ∑F(chi )

i=

и среднее значение пригодности

F = FN(k).

Вероятностьвыборанекоторойхромосомы chi вродительскийпул (промежуточную популяцию) M(k) определяется соотношением

Pi = FF(ch(k)i).

Следовательно, ожидаемое количество хромосом chi в M(k) будет равно

33

Ni = NPi = N FF(ch(k)i) = FF(ch(k)i).

Ожидаемое количество хромосом со схемой S в родительском пуле

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

Для того чтобы оценить влияние операции скрещивания на распространение схем, введем обозначения:

p(S) – порядок схемы, т. е. количество закрепленных позиций в схеме;

d(S) – длина (охват) схемы – расстояние между последним и первым закрепленным символами.

Например:

p(01***0**1) = 4; d(01***0**1) = 9 – 2 = 7.

Если в схеме одна закрепленная позиция, то ее охват равен 0. Пусть хромосома с длиной L битов соответствует схеме S, тогда вероятность того, что ни один из ее потомков не будет соответство-

вать этой схеме, равна

PS = dL(−S).

(внизу стоит L–1, так как точка скрещивания находится внутри хромосомы).

Если Pi – вероятность выбора хромосомы в родительский пул (см. выше), то вероятность уничтожения схемы

PS = Pi dL(−S).

Соответственно, вероятность выживания схемы

PS = −Pi dL(−S).

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

Рассмотрим влияние мутации на распространение схем в родительском пуле.

34

Хромосома со схемой S останется в этой схеме только тогда, когда ни один символ не мутирует. Вероятность этого события

PS =( −Pm) p(S),

где Pm – вероятность мутации бита. Таким образом, в процессе мутации разрушаются схемы, имеющие высокий порядок.

Окончательно влияние генетических операторов на выживание схем можно оценить формулой (теорема схем)

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

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

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

2.2. Кодирование параметров в генетическом алгоритме

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

Когда требуется кодировать вещественные числа двоичными, необходимо выполнить достаточно очевидные преобразования. Например, пусть рассматривается вещественная переменная

x k [x min, x max].

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

35

∆x = (x ma −x min).

(2n − )

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

Для кодирования x k бинарной строкой sk нужно использовать формулу

sk =(2n − )(x(x k −−x xmin)).

ma min

Так, допустим, что x k [20, 100] и n=8, тогда для x k =56 имеем

Если же требуется получить действительное значение для некоторого двоичного кода, то выполняется обратный перевод:

x k = sk (x ma n−−x min) +x min.

(2 )

Например, для кода sk = 001111002 = 6010 получается значение переменной

x k =60(56−20) +20 =28,4. (256− )

Использование двоичного алфавита как имеющего самое малое количество символов имеет следующие особенности.

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

Сдругой стороны, для того чтобы в текущей популяции могло сосуществовать достаточное количество разнообразных схем, размер популяции должен быть достаточно большим. Примерная оценка размера популяции составляет 10N (где N – длина хромосомы в битах) [18].

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

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

36

имеют большое расстояние по Хэммингу). Например, числа 7 и 8 различаются на 4 бита: 01112 = 710; 10002 = 810.

Мутация старшего бита, например, превращает 7 в 15, а 8 в 0. Во многих задачах могут быть нежелательны такие резкие изменения, сразу уводящие решение в другую область поиска. Поэтому обычный двоичный код может быть заменен на код Грея, в котором любые два соседних числа отличаются значением только одного бита (табл. 2.1).

Таблица 2.1. Сравнение кода Грея и двоичного кода

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

Двоичная хромосома может иметь большую длину, в такой ситуации полезным может оказаться логарифмическое кодирование [12]. При логарифмическом кодировании первый бит кодовой последовательности (α) – это бит знака показательной функции, второй бит (β) – бит знака степени этой функции, а остальные биты (bin) кодируют значение степени:

[α β bin] =(− )βe(− )α[bin]0,

где запись [bin]10 означает, что двоичную последовательность надо преобразовать в десятичное число, например:

37

[ 0 0] =(− )0e(− ) [ 0]0 = e−6 =0,0025.

Таким образом, при 5 битах логарифмического кода представимые числа принадлежат диапазону

x [e−7,e7] =[0,0009, 097].

Это намного больше, чем диапазон [0, 31], который обеспечивается обычным двоичным кодом.

2.3. Варианты оценки пригодности хромосом

Тестирование хромосом является важнейшим этапом работы ГА. В результате тестирования каждая хромосома получает фиксированный на данном шаге признак – относительную пригодность. Чаще всего ОП описывается численно. Расчет ОП зависит от решаемой конкретной задачи.

Рассмотрим, например, проблему идентификации (настройки параметров) имитационной модели (ИМ). На вход объекта и модели подается одинаковый тестовый сигнал x (t). Задача заключается в подборе таких параметров модели P, при которых выход модели y(t) как можно более близок выходу объекта z(t). Популяция хромосом кодирует различные варианты параметров модели (рис. 2.1).

Вместо непрерывных выходов y(t) и z(t) обычно рассматривается набор из n обучающих пар, каждая из которых соответствует выходу объекта и модели в дискретные моменты времени. Тогда ошибка моделирования может быть определена в виде

ГА

P

y(t)

ИМ

x(t)

z(t)

Объект

Рис. 2.1. Настройка имитационной модели

38

nn

ε= ∑(yi −zi )2 или ε = ∑yi −zi

Таким образом, с каждой хромосомой связывается численная оценка. Если эта оценка используется без изменения в операции селекции, то говорят о пропорциональном присвоении ОП.

Для анализа текущего состояния популяции могут быть введены следующие критерии:

–селективное давление – отношение ОП наилучшей хромосомы

ксредней ОП всей популяции;

–селективное отклонение (bias) – абсолютная разность между нормализованной ОП хромосомы и вероятностью ее участия в воспроизводстве;

–селективная распространенность (spread ) – ранжирование количества возможных потомков одной хромосомы;

–потеря разнообразия (loss of d iversity ) – процент хромосом популяции, которые отбрасываются и не участвуют в дальнейшей селекции.

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

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

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

Введем обозначения: N – размер популяции, S – селективное давление:

39

S = опma . опav

Пусть все хромосомы отсортированы таким образом, что номер 1 имеет хромосома с наименьшим значением ОПmin, а номер N – хро-

мосома с ОПmax.

Тогда линейное ранжирование всех хромосом может быть выполнено с помощью формулы

Рассмотрим пример. Пусть отсортированные значения ОП хромосом популяции представлены вектором (рис. 2.2):

ОП=[55, 55, 62, 68, 68, 68, 70, 78, 78, 80, 82, 96, 97, 98, 102, 103, 120, 121, 125, 138].

Выполнить линейное ранжирование (2.2) можно с помощью следующего m-файла MatLab:

K=size(X)

[B,m2]=max(X)

S=m2/mean(X) for i=1:K(2)

Y(i)=2-S+2*(S-1)*(i-1)/(K(2)-1)

end plot(Y,’+’)

Результат линейной ранговой селекции хромосом показан на рис. 2.3.

Рис. 2.2. Упорядоченный фитнес хромосом

40