Безперервні генетичні алгоритми

Трохи історії

Генетичні алгоритми (ГА) – це потужний інструмент на вирішення складних завдань. Вони знайшли застосування в оптимізації, штучному інтелекті, інженерії та інших галузях. В основі ГА лежать принципи, запозичені з біології та генетики. Нагадаємо: основна ідея ГА полягає у створенні популяції особин (індивідів), кожна з яких представляється у вигляді хромосоми. Будь-яка хромосома є можливим рішенням оптимізаційної задачі. Для пошуку кращих рішень необхідно лише значення цільової функції або функції пристосованості. Значення функції пристосованості особини показує, наскільки добре підходить особина, описана хромосомою, для вирішення задачі. Хромосома складається з кінцевої кількості генів, представляючи генотип об'єкта, тобто. сукупність його спадкових ознак. Процес еволюційного пошуку ведеться лише на рівні генотипу. До популяції застосовуються основні біологічні оператори: схрещування, мутації, інверсії та інших. У процесі еволюції діє відомий принцип " виживає сильний " . Популяція постійно оновлюється з допомогою генерації нових особин і знищення старих, і кожна нова популяція стає кращим і залежить від попередньої.

Спочатку безперервні гени почали використовувати у специфічних додатках (наприклад, хемометрика, оптимальний підбір параметрів операторів стандартних ГА та інших.). Пізніше вони починають застосовуватися для вирішення інших завдань оптимізації у безперервних просторах (роботи дослідників Wright, Davis, Michalewicz, Eshelman, Herrera у 1991-1995 рр.). Оскільки до 1991 року теоретичних обґрунтувань роботи безперервних ГА не існувало, використання цього нового підвиду було спірним; вчені, знайомі зфундаментальною теорією еволюційних обчислень, у якій було доведено перевагу двійкового алфавіту над іншими, критично сприймали успіхи реально-кодованих алгоритмів. Після того, як через деякий час з'явилося теоретичне обґрунтування, безперервні ГА повністю витіснили двійкові хромосоми при пошуку в безперервних просторах.

Далі в тексті за аналогією з англомовною термінологією для ГА з двійковим кодуванням використовуватиметься абревіатура BGA (Binary coded), для ГА з безперервними генами – RGA (Real coded).

Переваги та недоліки двійкового кодування

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

Як відомо, висока ефективність відшукання глобального мінімуму або максимуму генетичним алгоритмом з двійковим кодуванням теоретично обґрунтована в фундаментальній теоремі генетичних алгоритмів ("теорема про шаблон"), доведена Холландом. Її докладне освітлення та доказ можна знайти у відповідних джерелах. Її суть у тому, що двійковий алфавіт дозволяє обробляти максимальну кількість інформації, порівняно з іншими схемами кодування.

Однак двійкове уявлення хромосом спричиняє певні труднощі при пошуку в безперервних просторах великої розмірності, і коли потрібна висока точність знайденого рішення. У BGA для перетворення генотипу на фенотип використовується спеціальний прийом, заснований на тому, що весь інтервал допустимих значень ознаки об'єкта $ [a_i, b_i] $ розбивається на ділянки з необхідною точністю. Задана точність $p$ визначається виразом

де $N$ – кількість розрядів для кодування рядка біта.

Ця формула показує, що $p$сильно залежить від $N$, тобто. точність уявлення визначається кількістю розрядів, що використовуються для кодування однієї хромосоми. Тому зі збільшенням $N$ простір пошуку розширюється і стає величезним. Відомий книжковий приклад: нехай для $100$ змінних, що змінюються в інтервалі $[-500; 500]$, потрібно знайти екстремум з точністю до шостого знака після коми. У цьому випадку при використанні ГА з двійковим кодуванням довжина рядка становитиме $3000$ елементів, а простір пошуку – близько $10^1000$ хромосом.

Ефективність BGA у цьому випадку буде невисокою. На перших ітераціях алгоритм витратить багато зусиль оцінку молодших розрядів числа, закодованих у фрагменті двійкової хромосоми. Але оптимальне значення перших ітераціях залежатиме від старших розрядів числа. Отже, поки в процесі еволюції алгоритм не вийде на значення старшого розряду на околиці оптимуму, операції з молодшими розрядами виявляться марними. З іншого боку, коли це станеться, стануть не потрібні операції зі старшими розрядами – необхідно покращувати точність розв'язання пошуком у молодших розрядах. Така "ідеальна" поведінка не забезпечує сімейство алгоритмів BGA, т.к. ці алгоритми оперують бітовим рядком цілком, і перших епохах молодші розряди чисел " застигають " , приймаючи випадкове значення. У класичних ГА розроблено спеціальні прийоми щодо виходу з цієї ситуації. Наприклад, послідовний запуск ансамблю генетичних алгоритмів із поступовим звуженням простору пошуку.

Є й інша проблема: зі збільшенням довжини бітового рядка потрібно збільшувати чисельність популяції.

Математичний апарат безперервних ГА

Як зазначалося, під час роботи з оптимізаційними завданнями у безперервних просторах цілком природнопредставляти гени безпосередньо речовими числами. І тут хромосома є вектор речових чисел. Їх точність визначатиметься виключно розрядною сіткою тієї ЕОМ, де реалізується real-coded алгоритм. Довжина хромосоми буде збігатися з довжиною вектора-рішення оптимізаційної задачі, інакше кажучи, кожен ген відповідатиме за одну змінну. Генотип об'єкта стає ідентичним його фенотипу.

Вищесказане визначає перелік основних переваг real-coded алгоритмів:

Використання безперервних генів уможливлює пошук у великих просторах (навіть у невідомих), що важко робити у разі двійкових генів, коли збільшення простору пошуку скорочує точність рішення при незмінній довжині хромосоми.
Однією з важливих рис безперервних ГА є їхня здатність до локального настроювання рішень.
Використання RGA для подання рішень зручне, оскільки близько до постановки більшості прикладних завдань. Крім того, відсутність операцій кодування/декодування, які необхідні BGA, підвищує швидкість роботи алгоритму.

Як відомо, поява нових особин у популяції канонічного ГА забезпечують кілька біологічних операторів: відбір, схрещування та мутація. Як оператори відбору особин у батьківську пару тут підходять будь-які відомі з BGA: рулетка, турнірний, випадковий. Проте оператори схрещування та мутації не годяться: у класичних реалізаціях вони працюють із бітовими рядками. Потрібні власні реалізації, що враховують специфіку real-coded алгоритмів.

Оператор схрещування безперервного ГА, або кросовер, породжує одного чи кількох нащадків від двох хромосом. Власне кажучи, потрібно з двох векторів дійсних чисел отримати нові вектори за будь-якимизаконів. Більшість real-coded алгоритмів генерують нові вектори навколо батьківських пар. Для початку розглянемо прості та популярні кросовери.

Нехай $C_1=(c_1^1,c_2^1, \dots ,c_n^1)$ і $C_2=(c_1^2,c_2^2, \dots ,c_n^2)$ – дві хромосоми, вибрані оператором селекції для схрещування. Після формули для деяких кросоверів наводиться малюнок – геометрична інтерпретація його роботи. Передбачається, що $c_k^1 \Leftarrow c_k^2$ і $f(C_1) > = f (C_2) $.

Плоский кросовер (flat crossover): створюється нащадок $H=(h_1,\dots ,h_k, \dots ,h_n), h_k,k=1, \dots ,n$ – випадкове число з інтервалу $[ c_k^1, c_k^2]$.

Найпростіший кросовер (simple crossover): випадковим чином вибирається число $k$ з інтервалу $$ і генеруються два нащадки $H_1=(c_1^1,c_2^1,\dots ,c_k^1,c_^2 ,\dots , c_n^2)$ і $H_2=(c_1^2,c_2^2,\dots ,c_k^2,c_^1 ,\dots , c_n^2)$.

Арифметичний кросовер (arithmetical crossover): створюються два нащадка $H_1=(h_1^1,\dots ,h_n^1), H_2=(h_1^2,\dots ,h_n^2)$, де $ h_k^1=w*c_k^1+(1-w)*c_k^2$, $h_k^2=w*c_k^2+(1-w)*c_k^1$, $k=1,\dots ,n, w$ або константа (рівномірний арифметичний кросовер) з інтервалу $[0;1]$, або змінюється із збільшенням епох (нерівномірний арифметичний кросовер).

Геометричний кросовер (geometrical crossover): створюються два нащадки $H_1=(h_1^1,\dots ,h_n^1), H_2=(h_1^2,\dots ,h_n^2)$, де $ h_k^1=(c_k^1)^w * (c_k^2)^, (c_k^2)^w *(c_k^1)^$, $w$ – випадкове число з інтервалу $[0;1]$ .

Змішаний кросовер (blend, BLX-alpha crossover): генерується один нащадок $H=(h_1,\dots ,h_k,\dots ,h_n)$, де $h_k$ - випадкове число з інтервалу $[c_ –I*alpha,c_+I*alpha]$, $c_=min(c_k^1, c_k^2)$, $I=c_-c_$. BLX-0.0 кросовер перетворюється на плоский.

Лінійний кросовер (linear crossover): створюються три нащадки $H_q=(h_1^q,\dots ,h_k^q,\dots ,h_n^q), q=1,2,3$, де $ h_k^1= 0,5*(c_k^1)+ 0,5*(c_k^2)$, $h_k^2= 1,5*(c_k^1)- 0,5*(c_k^2)$ , $ h_k ^ 3 = -0,5 * (c_k ^ 1) + 1,5 * (c_k ^ 2) $. На етапі селекції в цьому кросовері відбираються два найсильніші нащадки.

Дискретний кросовер (discrete crossover): кожен ген $h_k$ вибирається випадково за рівномірним законом з кінцевої множини $$.

Розширений лінійний кросовер (extended line crossover): ген $h_k=w*(c_k^1- c_k^2)+c_k^1$, $w$ – випадкове число з інтервалу $[-0.25;1.25 ]$.

Евристичний кросовер (Wright's heuristic crossover). Нехай $C_1$ – один із двох батьків із кращою пристосованістю. Тоді $h_k=w*(c_k^1- c_k^2)+c_k^1$, $w$ – випадкове число з інтервалу $[0;1]$.

Нечіткий кросовер (fuzzy recombination, FR-d crossover): створюються два нащадки $H_1=(h_1^1,\dots ,h_n^1), H_2=(h_1^1,\dots ,h_n^2 ) $. Імовірність того, що в $i$-тому гені з'явиться число $v_i$ , задається розподілом $p(v_i)$, де $F(c_k^1), F(c_k^2)$ – розподілу ймовірностей трикутної форми (трикутні нечіткі функції приналежності) з наступними властивостями ($c_k^1\Leftarrow c_k^2$ і $I=\mid c_k^1- c_k^2 \mid$):