3.2 Символьна модель

Параметри xзазвичай кодуються бінарним рядкомs. Використовуючи цільову функціюf(x) можна побудувати функціюm(s) - функцію придатності (функція пристосованості), відобразивши, коли це необхідно, f на позитивну піввісь. Це робиться для того, щоб гарантувати пряме співвідношення між значення цільової функції і пристосованістю рішення, і потім така модифікована цільової функція розглядається як функція пристосованості ГА. Таким чином, кожне можливе рішенняs, що має відповідну пристосованістьm(s), представляє рішенняx.

Перехід із простору параметрів у простір бінарних рядків здійснюється кодуванням перемінних x₁,x₂, ... ,x_Nу двійкові цілочислові рядки достатньої довжини - достатньої для того, щоб забезпечити бажану точність. Для бажаної точності простір параметрів повинен бути дискретизовано таким чином, щоб відстань між вузлами дискретизації відповідала необхідній точності.

У багатьох випадках така модель може виявитися неефективною. Крім того, що вона досить громіздка, практика показує, що довге кодування підвищує імовірність "передчасного" збігання, для боротьби з яким винаходяться різні методи. До того ж застосування довгих кодувань зовсім не гарантує, що знайдене рішення буде мати необхідну точність, оскільки цього, у принципі, не гарантує сам ГА.

Ми представимо модифікацію символьної моделі, що дозволяє, не застосовуючи довгих кодувань, домагатися порівнянної точності.

Отже, щоб провести дискретизацію простору Dі закодувати кожне можливе рішення рядкомs, як і раніш використаємо рівномірну сітку у просторі параметрів. Але кожен інтервал [a_i, b_i] розбиваємо лише на k відрізків рівної довжини:

h_i= (b_i-a_i) /k,i= 1, 2, ... ,N.

Цим саме покриємо i-ий інтервал [a_i, b_i] мережеюs_iз (k+1)вузлів з постійним крокомh_i.

x_i,j = a_i + j^.h_i,  j =0, 1, ...,k.

Використовуючи двійковий алфавіт {0,1} кожному вузлу сітки s_iможна надати унікальний бінарний код довжиноюq. Довжина кодуqвибирається таким чином, щобk< 2^q. Найбільше економічно використовувати сітку зk= 2^q-1.

Тоді символьний запис j-ого вузла поi-ій координатній осі в двійковому коді можна представити у виді наступної бінарної конструкції

b₁ⁱ b₂ⁱ ... b_qⁱ

Провівши дискретизацію по всім Nкоординатним осям, одержимо вN-мірному паралелепіпедіDпросторові ґратиSз (k+1)^Nвузлами, де кожен вузолsможна представити у виді лінійної послідовності таких записів (хромосом).

s = b₁¹ b₂¹ ... b_q¹ ... b₁^N b₂^N ... bq

Таким чином, щоб побудувати символьну модель беззупинної оптимізаційної задачі на гіперкубі Dпотрібно представити безліч вузлів просторових ґратSза допомогою бінарних послідовностей (хромосом). Символьна модель, пропонованих раніше генетичних алгоритмів, передбачала дискретизацію простору параметрів із кроком, що відповідає необхідній точності. При цьому рішенням задачі міг бути тільки вузол просторових ґрат, так що між крапкою в параметричному просторі і її представленням в просторіSіснувало взаємно однозначна відповідність.

Пропонована ж нами модель не передбачає однозначності, допускаючи існування цілої безлічі рішень, що мають єдиного представника. У термінології ГА це означає, що можуть існувати особи, що володіють різними фенотипічними ознаками, але однаковими генотипами. Це дозволяє використовувати більш велику розбивку простору параметрів, звужуючи простір бінарних рядків Sі роблячи при цьому довжину хромосомного набору коротше.