Пример 4.5

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

Выбор исходной популяции связан с представлением парамет­ров задачи в форме хромосом, т.е. с так называемым хромосомным представлением. Это представление определяется способом кодиро­вания. В классическом генетическом алгоритме применяется двоич­ное кодирование, т.е. аллели всех генов в хромосоме равны 0 или 1. Длина хромосом зависит от условий задачи, точнее говоря - от коли­чества точек в пространстве поиска.

Генетические алгоритмы находят применение главным обра­зом в задачах оптимизации. Пример 4.5 демонстрирует выполнение классического генетического алгоритма, аналогичного рассмотренно-

J. Генетические алгоритмы

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

му в примере 4.4, но для случая оптимизации функции. Для простоты примем, что это функция одной переменной. В новом примере хромо­сомы выступают в роли закодированной формы соответствующих фенотипов, а оптимизируется сама функция приспособленности. В примере 4.6 оптимизируется та же функция, однако внимание чита­теля акцентируется на другом способе кодирования хромосом для иной области определения переменной х.

Рассмотрим очень простой пример - задачу нахождения макси­мума функции, заданной выражением (4.1) для целочисленной пере­менной х, принимающей значения от 0 до 31

Для применения генетического алгоритма необходимо прежде веего закодировать значения переменной х в виде двоичных последо­вательностей. Очевидно, что целые числа из интервала [0, 31] можно представить последовательностями нулей и единиц, используя их представление в двоичной системе счисления. Число 0 при этом за­писывается как 00000, а число 31 - как 11111. В данном случае хро­мосомы приобретают вид двоичных последовательностей, состоящих из 5 битов, т.е. цепочками длиной 5 (аналогично примеру 4.1).

Также очевидно, что в роли функции приспособленности будет выступать целевая функция f(x), заданная выражением (4.1). Тогда приспособленность хромосомы ch,-, /=1,2,..., N будет определяться значением функции f(x) для х, равного фенотипу, соответствующему генотипу ch/. Обозначим эти фенотипы ch/*. В таком случае зна чение функции приспособленности хромосомы ch/ (т.е. F(ch/)) будет равно f(ch/*).

Выберем случайным образом исходную популяцию, состоящую
из 6 кодовых последовательностей (например, можно 30 раз подбро­
сить монету); при этом N = 6. Допустим, что выбраны хромосомы
ch, = [10011] ch₄ = [10101]

ch₂ = [00011] ch₅ = [01000]

ch₃ = [00111] ch₆ = [11101]

Соответствующие им фенотипы - это представленные ниже числа из интервала от 0 до 31:

= 21

chg= chg = 29

ch^= 3 ch|= 7

По формуле (4.1) рассчитываем значения функции приспособ­
ленности для каждой хромосомы в популяции и получаем
/=(*,) = 723 F(ch₄)= 883

F(ch₂)= 19 F(ch₅)= 129

F(ch₃)= 99 F(ch₆) = 1683

Селекция хромосом Методом рулетки (также, как и в примере 4.4), выбираем 6 хромосом для репродукции Колесо рулетки пред­ставлено на рис. 4.7.

I

Допустим, что выбраны числа

97 26 54 13 31 88. Это означает выбор хромосом

ch6 ch₄ ch₆ ch., ch₄ ch₆

Пусть скрещивание выполняется с вероятностью jd_c = 1. Допус­тим, что для скрещивания сформированы пары ch₁ и ch₄ ch₄ и ch₆ ch₆ и ch₆

Кроме того, допустим, что случайным образом выбрана точка скрещивания, равная 3 для хромосом ch., и ch₄, а также точка скрещи-

(ch₂)

Рис. 4.7. Колесо рулетки для селекции в гримере 4.5.

А, = [10011]) <Лц = [10101])	*■ [10111]
1к=Ъ
ch^ [10101]) dfc-[11101]/	Скрещивание [ЮЮ1] ^ [11101]
lk=2

Рис. 4.8. Процесс скрещивания хромосом в примере 4.5.

Глава 4. Генетические алгоритм

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

вания, равная 2 для хромосом ch₄ и ch₆ (рис.4.8). При условии, что ве­роятность мутации рт - 0, в новую популяцию включаются хромосо­мы

₄ = [11101] ₅ = [11101] ₆ = [11101]

Сп., = [10001] С₂ = [10111] [10101]

Ch₂ = [10111]' Chg =

Ch₃ = [10101] Ch₆ = [11101]

Для расчета значений функции приспособленности этих хромо­сом необходимо декодировать представляющие их двоичные после­довательности и получить соответствующие им фенотипы. Обозна­чим их Сп,-. В результате декодирования получаем числа (из интер­вала от 0 до 31)

Ch?=17 Ch| = 29

ChJ = 23 ChЈ = 29

Сп! = 21 Chg = 29

Соответственно, значения функции приспособленности хромо­
сом новой популяции, рассчитанные по формуле (4.1), составят
F(Ch₁)= 579 F(Ch₄)=1683

F(Cti₂)=1059 F(Ch₅) = 1683

F(Ch₃)= 883 F(Ch₆)=1683

Легко заметить, что в этом случае среднее значение приспо­собленности возросло с 589 до 1262.

Обратим внимание, что если на следующей итерации будут сформированы для скрещивания пары хромосом, например, Ch₄ и Ch₂, Ch₅ и Ch₂ или Ch₆ и Сп₂ с точкой скрещивания 2 или 3, то сре­ди прочих будет получена хромосома [11111] с фенотипом, равным числу 31, при котором оптимизируемая функция достигает своего максимума. Значение функции приспособленности для этой хромосо­мы оказывается наибольшим и составляет 1923. Если такое сочета­ние пар в данной итерации не произойдет, то можно будет ожидать образования хромосомы с наибольшим значением функции приспо­собленности на следующих итерациях. Хромосома [11111] могла быть получена и на текущей итерации в случае формирования для скрещи­вания пары Сп., и Сп₆ с точкой скрещивания 3.

Отметим, что при длине хромосом, равной 5 битам, простран­ство поиска очень мало и насчитывает всего 2⁵ = 32 точки. Представ­ленный пример имеет исключительно демонстрационный характер. Применение генетического алгоритма для такого простого примера практически нецелесообразно, поскольку его оптимальное решение может быть получено мгновенно. Однако этот пример пригоден для изучения функционирования генетического алгоритма.

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

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

Также обратим внимание на возможность реализации генети­ческого микроалгоритма, описываемого в п. 4.8.8. Он работает с ма­лой популяцией и вероятностями скрещивания и мутации такими, как и в примерах 4.4 и 4.5, но одновременно хорошо противостоит преж­девременной сходимости. Этот факт иллюстрируется примером 4.12, в котором с помощью этого алгоритма находится минимум функции, заданной формулой (4.1).

Дата добавления: 2015-06-04