Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

2.7
. Примеры кодирования параметров задачи в 
генетическом алгоритме

---

А.Е. Кононюк Дискретно-непрерывная математика 
98 
Выбор исходной популяции связан с представлением параметров задачи 
в форме хромосом, т.е. с так называемым хромосомным 
представлением. 
Это 
представление 
определяется 
способом 
кодирования. В классическом генетическом алгоритме применяется 
двоичное кодирование, т.е. аллели всех генов в хромосоме равны 0 или 
1. Дпина хромосом зависит от условий задачи, точнее говоря - от 
количества точек в пространстве поиска. 
Генетические алгоритмы находят применение главным образом в 
задачах оптимизации. Пример 2.2 демонстрирует выполнение
классического генетического алгоритма, аналогичного рассмотренному 
в примере 2.1, но для случая оптимизации функции. Для простоты 
примем, что это функция одной переменной. В новом примере хромо-
сомы выступают в роли закодированной формы соответствующих 
фенотипов, а оптимизируется сама функция приспособленности. В 
примере 2.3 оптимизируется та же функция, однако внимание читателя 
акцентируется на другом способе кодирования хромосом для иной 
области определения переменной х. 
Пример 2.2
Рассмотрим очень простой пример - задачу нахождения максимума 
функции, заданной выражением (2.1) для целочисленной переменной 
х
, 
принимающей значения от 0 до 31. 
Для применения генетического алгоритма необходимо прежде всего 
закодировать значения переменной 
х
в виде двоичных последо-
вательностей. Очевидно, что целые числа из интервала [0, 31] можно 
представить последовательностями нулей и единиц, используя их 
представление в двоичной системе счисления. Число 0 при этом за-
писывается как 00000, а число 31 - как 11111. В данном случае хро-
мосомы приобретают вид двоичных последовательностей, состоящих из 
5 битов, т.е. цепочками длиной 5. 
Также очевидно, что в роли функции приспособленности будет 
выступать целевая функция 
f(x), 
заданная выражением (2.1). Тогда 
приспособленность хромосомы ch
i
, 
i
= 1,2.....N будет определяться 
значением функции 
f(x)
для 
х
, равного фенотипу, соответствующему 
генотипу ch
i
. Обозначим эти фенотипы ch
i
*. В таком случае значение 
функции приспособленности хромосомы ch
i
(т.е. F(ch
i
)) будет равно 
f(ch
i
*). 
Выберем случайным образом исходную популяцию, состоящую из 6 
кодовых последовательностей (например, можно 30 раз подбросить 
монету); при этом N=6. Допустим, что выбраны хромосомы 
ch
1
= [10011]

---

А.Е. Кононюк Дискретно-непрерывная математика 
99 
ch
2
= [00011]
ch
3
= [00111]
ch
4
= [10101] 
ch
5
= [01000] 
ch
6
= [11101] 
Соответствующие им фенотипы - это представленные ниже числа из 
интервала от 0 до 31: 
ch
1
* = 19
ch
2
* =3
ch
3
*= 7
ch
4
* = 21 
ch
5
*, = 8 
ch
6
* = 29 
По формуле (2.1) рассчитываем значения функции приспособленности 
для каждой хромосомы в популяции и получаем 
F(ch
1
) = 723
F(ch
2
)= 19
F(ch
3
) = 99
F(ch
4
) = 883 
F(ch
5
) = 129 
F(ch
6
)=1683