Кодування параметрів, що оптимізуються

Будь-який організм може бути представлений своїм фенотипом, що фактично визначає, чим є об'єкт у реальному світі, і генотипом, що містить всю інформацію про об'єкт на рівні хромосомного набору. При цьому кожний ген, тобто елемент інформації генотипу, має своє відображення у фенотипі. Таким чином, для розв’язку задач необхідно представити кожну ознаку об'єкта у формі, що підходить для використання в генетичному методі. Все подальше функціонування механізмів генетичного методу відбувається на рівні генотипу, що дозволяє обходитися без інформації про внутрішню структуру об'єкту, що й обумовлює широке застосування генетичного пошуку в самих різних задачах.

За методами представлення генів хромосоми можна умовно розділити на три групи:

1. Бінарні хромосоми – хромосоми, гени яких можуть приймати значення 0, або 1.

2. Числові хромосоми – гени можуть приймати значення в заданому інтервалі.

Числові хромосоми можна розділити на гомологічні та негомологічні.

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

У негомологічних хромосомах гени можуть приймати значення в заданому інтервалі; при цьому інтервал однаковий для всіх генів, але в хромосомі не може бути двох генів з однаковим значенням. Для негомологічних хромосом застосовуються різні спеціальні генетичні оператори, що не створюють неприпустимих рішень. Негомологічні хромосоми, як правило, застосовуються при розв’язку задач комбінаторної оптимізації.

3. Векторні хромосоми – хромосоми, гени яких представляють собою вектор цілих чисел.

Ген у векторних хромосомах має властивості негомологічної хромосоми, тобто числа у векторі можуть приймати значення в заданому інтервалі, і вектор не може містити двох однакових чисел. Проте, хоча гени у векторних хромосомах негомологічні, самі векторні хромосоми є гомологічними.

Процес кодування параметрів, що оптимізуються, можна виконати в наступній послідовності кроків.

Крок 1. Визначення параметрів, що оптимізуються, – генів.

Крок 2. Вибір числа розрядів у кожному гені.

Крок 3. Вибір методу кодування.

Варто врахувати, що занадто велика довжина кодування прискорює процес збіжності всіх членів популяції до кращого знайденого рішення. Часто такий ефект є небажаним, оскільки при цьому більша частина простору пошуку залишається недослідженою. Передчасна збіжність може не привести до оптимального рішення, крім того, швидка збіжність до однієї області не гарантує виявлення декількох рівних екстремумів. До того ж застосування довгих кодувань зовсім не гарантує, що знайдене рішення буде мати необхідну точність, оскільки цього, в принципі, не гарантує сам генетичний метод.

Тому в питанні вибору оптимальної довжини кодування потрібно досягти деякого компромісного рішення – з одного боку довжина хромосоми повинна бути досить великою, щоб все-таки забезпечити швидкий пошук, з іншого боку – по можливості малою, щоб не допускати передчасної збіжності й залишити методу шанс відшукати кілька оптимальних значень.

Наведемо варіанти кодування генів у деяких задачах, розв'язуваних за допомогою генетичних методів:

– оптимізація функцій: гени – незалежні змінні;

– апроксимація: гени – параметри-константи апроксимуючих функцій;

– задача відбору інформативних ознак: гени ідентифікують значимість відповідних ним ознак (наприклад, якщо значення гену дорівнює одиниці, то відповідна йому ознака вважається інформативною);

– настроювання ваг штучної нейронної мережі: гени відповідають синоптичним вагам нейронів;

– штучне життя (Artificial Life): гени відповідають характеристикам особини (сила, швидкість, і т.ін.), також повинні бути незмінні гени, що позначають тип особини (рослина або тварина);

– задача про найкоротший шлях: гени – пункти пересування. Вся хромосома представляє собою маршрут з початкової точки в кінцеву, причому не завжди існуючий.

Невдалий вибір упорядкування та кодування бітів у хромосомі може викликати передчасну збіжність до локального оптимуму. Для подолання цього недоліку можна вибирати спосіб кодування, ґрунтуючись на додаткової інформації про задачу.

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

Кількість розрядів r у гені для кодування ознаки визначається за формулою:

де ceil(x) – найближче більше або рівне х ціле число;

w_max і w_min – максимально й мінімально можливі значення ознаки (параметра, незалежної змінної);

ε – задана похибка визначення оптимального значення ознаки.

Розрядність хромосоми L визначається як сума розрядностей генів. У випадку, якщо задані однакові значення w_max, w_min і ε для всіх n генів, розрядність хромосоми може бути обчислена за формулою:

L = n · r.

Після того, як обрані параметри, їх кількість та розрядність, необхідно вирішити, як безпосередньо записувати дані, тобто вибрати метод кодування. Можна використати звичайне кодування або коди Грея. Незважаючи на те, що використання кодів Грея призводить до кодування/декодування даних, вони дозволяють уникнути деяких проблем, які з'являються в результаті звичайного кодування.

Перевага коду Грея в тому, що якщо два числа відрізняються на 1, то і їхні двійкові коди відрізняються тільки на один розряд, а у двійкових кодах не все так просто. Так, наприклад, числа 7 і 8 у бітовому поданні відрізняються в чотирьох позиціях (7₁₀=0111₂, 8₁₀=1000₂), що затрудняє функціонування генетичного методу й збільшує час, необхідний для його збіжності, а в коді Грея ці числа відрізняються всього на одну позицію (7₁₀=0100_Г, 8₁₀=1100_Г).

Варто відзначити, що кодувати й декодувати у коди Грея досить зручно. Кодування/декодування з бінарного коду в код Грея можна виконати в такий спосіб.

Крок 1. Скопіювати старший розряд кодуємого (декодуємого) числа в старший розряд декодуємого (кодуємого) числа.

Крок 2. Виконати перетворення за формулами:

– із двійкового коду в код Грея: ;

– з коду Грея у двійковий: ,

де G[i] – i-ий розряд коду Грея;

B[i]– i-ий розряд бінарного коду.

Наприклад, послідовність чисел від 0 до 15 у двійковому коді: {0000, 0001 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001 1010, 1011, 1100, 1101, 1110, 1111}, а в кодах Грея: {0000, 0001 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101 1111, 1110, 1010, 1011, 1001, 1000}.

Кодування ознак, яким відповідають числа із плаваючою комою.

Найпростіший спосіб кодування – використання бітового представлення. Однак такий варіант має ті ж недоліки, що й при кодуванні цілих чисел. Тому на практиці застосовується наступна послідовність дій.

Крок 1. Розбивається весь інтервал допустимих значень ознаки на ділянки з необхідною точністю.

Крок 2. Приймається значення гена як ціле число, що визначає номер інтервалу (використовуючи код Грея).

Крок 3. В якості значення параметра приймається число, що є серединою цього інтервалу.

<== попередня сторінка	\|	наступна сторінка ==>
Моделі генетичного пошуку	\|	Завдання цільової функції

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.015 сек.