Интеллектуальный анализ данных в менеджменте. Кричевский М.Л. - 153 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

153
соме является ключевой проблемой применения ГА. Проблема ис"
следована с различных сторон, например, по характеру отображения
пространства генотипов в пространство фенотипов, когда отдельные
особи декодируются в решения, и по свойствам преобразования, ког"
да хромосомы регулируются с помощью операторов.
В классической работе Д. Холланда кодирование выполняется с
использованием бинарных строк. Такое кодирование для задач оп"
тимизации имеет несколько недостатков вследствие существования
хеммингова сдвига для пары закодированных значений, имеющих
большое хеммингово расстояние, в то время, как эти величины при"
надлежат к точкам с минимальным расстоянием в фенотипическом
пространстве. Например, пара 01111111111 и 10000000000 при"
надлежит соседним точкам в фенотипическом пространстве (точки с
минимальным евклидовым расстоянием), но имеют максимальное
хеммингово расстояние в генотипическом пространстве. Для преодо"
ления хеммингова сдвига все биты должны изменяться одновремен"
но, но вероятность такого события очень мала.
Для многих задач, встречающихся в современных проблемах,
достаточно трудно представить их решения с помощью только би"
нарного кодирования. В течение последних десяти лет были раз"
работаны различные методы кодирования для обеспечения эффек"
тивного выполнения ГА, которые могут быть разделены на следу"
ющие классы [4]:
– бинарное кодирование;
– кодирование действительными числами;
– целочисленное кодирование;
– кодирование общей структуры данных.
Более подробно рассмотрим бинарное кодирование, которое исполь"
зуется в классическом подходе Д. Холланда. Пусть вектор допусти"
мого решения
хD1
1
, где D – область поиска решений. Каждый ком"
понент вектора
12
(,,..., )
n
xxx x1
1
можно закодировать с помощью це"
лого неотрицательного числа
12
0,
ii
K34
,
1,in1
; (
i
K – число возмож"
ных дискретных значений i"й переменной).
Введем бинарный алфавит B
2
= {0;1}. Для представления цело"
численного вектора b = (b
1
,…,b
n
) в алфавите B
2
необходимо опреде"
лить максимальное число двоичных символов q, которое достаточно
для отображения в двоичном коде любого значения b
i
из области его
допустимых значений [0,K
i
]. Нетрудно видеть, что параметр q дол"
жен удовлетворять неравенству
2K 1
, (3.1)

Страницы