Рис. 9. Структурна схема мережі Хемінга

На стадії ініціалізації ваговим коефіцієнтам першого шару і порогові активаційної функції присвоюються наступні значення:

xk

wik = 2i ; i = 0,...,n −1; k = 0,...,m −1

Tk = n / 2; k = 0,...,m −1

(5)

(6)

Тут xki – i-ий елемент k-ого зразка.

Вагові коефіцієнти гальмуючих синапсів у другому шарі вважають рівними деякій величині 0 < E < 1/ m . Синапс нейрона, пов’язаний з його ж аксоном має вагу +1.

47

Алгоритм функціонування мережі Хемінга наступний:

1. На входи мережі подається невідомий вектор X = {xi:i=0...n-1}, виходячи з якого розраховуються стани нейронів першого шару (верхній індекс у дужках вказує номер шару):

y(j1)	= s(j1)	n−1
		= åwijxi + Tj; j = 0,...,m -1	(7)
		i =0

Після цього отриманими значеннями ініціалізуються значення аксонів другого шару:

y(i

2) =y(i

1); j =0,...,m −1

(8)

2. Обчислити нові стани нейронів другого шару:

m −1

s(j2) (p +1) = y j (p) -e å y(k2) (p); k ¹ j; j = 0,...,m -1 k =0

(9)

і значення їхніх аксонів:

y (2)	(p +1) =f [s(2)	(p +1)]; j =0,..., m −1
j	j

(10)

Активаційна функція f має вид порогу (Рис.2б), причому величина F повинна бути досить великою, щоб будь-які можливі

значення аргументу не приводили до насичення.

3. Перевірити, чи змінилися виходи нейронів другого шару за останню ітерацію. Якщо так – перейди до кроку 2. Інакше – кінець.

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

Лабораторна робота № 9

Тема: Генетичні алгоритми.

Мета: Ознайомитися з генетичними алгоритмами та принципами їх роботи. Створити програмну реалізацію генетичного алгоритму.

Теоретичні відомості

48

Основними принципами еволюційної теорії є природний відбір та мінливість організмів. На основі цих принципів і будуються еволюційні алгоритми.

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

Схема генетичного алгоритму

1.Генерація випадкового початкового стану.

Перше покоління створюється з довільно обраних рішень (хромосом). Це відрізняється від стандартних методів, коли початковий стан завжди той самий.

2. Обчислення коефіцієнта виживаності (fitness).

Кожному рішенню (хромосомі) відповідає деяке чисельне значення, що залежить від його близькості до відповіді.

3. Відтворення.

Хромосоми, що мають велику виживаємість (fitness), попадають до кола нащадків (які потім можуть мутувати) з більшою імовірністю. Нащадок, результат злиття 'батька' і 'матері', є комбінацією їх генів. Цей процес називається 'кросінговер' (crossing over).

4. Наступне покоління.

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

Розглянемо детальніше комп'ютерну модель еволюції популяції штучних "особів". Кожна осіб характеризується своєю

хромосомою Sk , хромосома є "геном" особі. Хромосома визначає

пристосованість	особі f (Sk ) ;	k =1,...,n ; n – чисельність
популяції.	Хромосома	є	ланцюжком	символів
Sk = (Sk1,Sk2,...,Sk) , N –			довжина ланцюжка.	Символи

49

інтерпретуються як "гени" особі, розташовані в хромосомі Sk . Завдання алгоритму полягає в максимізації функції пристосованості f (Sk ) . Еволюція складається з послідовності поколінь. Для кожного

покоління відбираються особі з великими значеннями пристосовуваності. Хромосоми відібраних особів рекомбінуються і піддаються малим мутаціям. Формально схема ГА може бути представлена в такий спосіб (популяція t-го покоління позначається як

{Sk(t)} ):

Крок 0 . Створити випадкову початкову популяцію

{Sk(0)} .

Необхідно перетворити незалежні змінні у хромосоми, що будуть містити всю необхідну інформацію про кожну створювану осіб.

Єдва варіанти кодування параметрів:

-у двійковому форматі;

-у форматі з плаваючою комою.

Увипадку, якщо ми використовуємо двійкове кодування, ми

використовуємо N біт для кожного параметра, причому N може бути різним для кожного параметра. Якщо параметр може змінюватися між

мінімальним значенням MIN і максимальним MAX, використовуємо наступні формули для перетворення:

r =g × (MAX -MIN) /(2N -1) +MIN ;

g =(r -MIN) /(MAX -MIN) × (2N -1) ,

де g – цілочисельні двійкові гени, r – еквівалент генів у форматі з

плаваючою комою.

Хромосоми у форматі з плаваючою комою створюються за допомогою розміщення закодованих параметрів один за іншим.

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

Крок 1. Обчислити пристосованість f (Sk ) кожної особі Sk популяції {Sk(t)} .

Крок 2. Роблячи відбір особів Sk відповідно до їх пристосовуваності f (Sk ) і застосовуючи генетичні оператори

50

(рекомбінації і мутації) до відібраних особів, сформувати популяцію наступного покоління {Sk(t +1)} .

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

001100101110010|11000	→	00110010111001011100
110101101101000|11100

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

00110010111001011000

→

00110010111001111000

Інверсія інвертує (змінює) порядок біт у хромосомі шляхом циклічної перестановки (випадкова кількість разів). Багато модифікацій ГА обходяться без даного генетичного оператора.

00110010111001011000

→

11000001100101110010

Крок 3. Повторювати кроки 1, 2 для t = 0, 1, 2, ... доти, поки не виконається деяка умова закінчення еволюційного пошуку (припиняється ріст максимальної пристосованості в популяції, число поколінь t досягає заданої межі і т.д.).

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

В останні роки, реалізовано багато генетичних алгоритмів і в більшості випадків вони мало схожі на цей ГА. З цієї причини в даний час під терміном "генетичні алгоритми" мають на увазі не одну модель, а досить широкий клас алгоритмів, часом мало схожих один на одного.

51

Найбільш традиційний варіант генетичного алгоритму базується на наступній конкретній схемі:

1)ланцюги символів у хромосомах бінарні (символи Sk i приймають значення 0 або 1), довжина ланцюгів постійна (

N = const ),

2)метод добору пропорційно - імовірнісний (див. нижче),

3)рекомбінації виконуються за схемою однократного

кросінговера.

Пропорційно-імовірнісний відбір означає, що на кроці 2 відбір відбувається з імовірностями, пропорційними пристосовуваностям

fk особів ( fk =f (Sk) ) .

Схему можна представити, як вибір особі за допомогою рулетки, відносні площі секторів якої рівні qk = fk[S1 f1] −1 .

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

Одноточковий кросінговер організовується за аналогією з

біологічною	рекомбінацією.	А	саме, якщо є два батьки
S1 =(S11, S12,...,S1N)		і S2 =(S21, S22,..., S2N) , то
їхні нащадки є	(S11, ..., S1m,		S2,m +1,..., S2N)

і (S21, ..., S2m, S1,m +1,...,S1N) ; тобто "голова" і "хвіст"

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

розташовується між m-м та m+1-м "генами". Аналогічним чином може бути організований двоточковий і "декілька-точковий" кросінговер. Тип рекомбінації за схемою кросінговера часто доповнюється інверсіями, тобто зміною порядку проходження символів у ділянках хромосом; це аргументується, як необхідність підібрати істотні для пристосованості комбінації символів у хромосомі.

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

Наприклад, два нащадки батьків S1 =(S11, S12,..., S1N) і S2 =(S21, S22,..., S2N) , можуть мати наступні хромосоми

(S11, S22, S13, S14...,S2N)	і
(S21, S12, S23, S24..., S1N) .

52

Як метод оптимізації, ГА має внутрішній паралелізм (implicit parallelism): різні частки комбінації генів – їх часто називають "схематами" (“schemata”) – відшукуються паралельним чином, одночасно для всіх комбінацій.

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

За рахунок чого ГА на кілька порядків перевершує по швидкості випадковий пошук у багатьох задачах? Справа в тому, що більшість систем мають досить незалежні підсистеми. Внаслідок цього, при обміні генетичним матеріалом, часто може зустрітися ситуація, коли від кожного з батьків беруться гени, що відповідають найбільш вдалому варіанту визначеної підсистеми (інші "виродки" поступово вимирають). Іншими словами, ГА дозволяє накопичувати вдалі рішення для систем, що складаються з відносно незалежних підсистем (більшість сучасних складних технічних систем, і усі відомі живі організми). Відповідно можна сказати і коли ГА швидше за все дасть збій (чи, принаймні, не покаже особливих переваг перед методом Монте-Карло) — це відбувається у випадку роботи з системами, які складно розбити на підсистеми (вузли, модулі), а так само у випадку невдалого порядку розташування генів (поруч розташовані параметри, що відносяться до різних підсистем), при якому переваги обміну генетичним матеріалом зводяться до нуля.

Приклад ГА: Вирішення Діофантового рівняння

Розглянемо діофантове (тільки цілі рішення) рівняння: a+2b+3c+4d=30, де a, b, c і d - деякі додатні цілі. Застосування ГА за

дуже короткий час знаходить шукане рішення (a, b, c, d).

Для початку виберемо 5 випадкових рішень: 1 ≤ a,b,c,d ≤ 30 .

Таблиця 1- Перші покоління хромосом та їх вміст

Хромосома	(a,b,c,d)
1	(1,28,15,3)
2	(14,9,2,4)
3	(13,5,7,3)
4	(23,8,16,19)
5	(9,13,5,2)

53

Щоб обчислити коефіцієнти виживання (fitness), підставимо кожне рішення у вираз a+2b+3c+4d. Відстань від отриманого

значення до 30 і буде потрібним значенням.

Таблиця 2 - Коефіцієнти виживання першого покоління хромосом (набору рішень)

Хромосома	Коефіцієнт виживання
1	|114-30|=84
2	|54-30|=24
3	|56-30|=26
4	|163-30|=133
5	|58-30|=28

У нашому випадку великі чисельні значення коефіцієнтів виживання не підходять. Щоб створити систему, де хромосоми з більш придатними значеннями мають великі шанси виявитися батьками, ми повинні обчислити, з якою імовірністю (Р %) може бути обрана кожна. Візьмемо суму обернених значень коефіцієнтів, і виходячи з цього обчислимо відсотки.

Таблиця 3 - Імовірність виявитися батьком

Хромосома	Наскільки підходить
1	(1/84)/0.135266 = 8.80%
2	(1/24)/0.135266 = 30.8%
3	(1/26)/0.135266 = 28.4%
4	(1/133)/0.135266 = 5.56%
5	(1/28)/0.135266 = 26.4%

Для вибору 5-и пар батьків (кожна з яких буде мати 1 нащадка, усього - 5 нових рішень), представимо, що в нас є 10000-сторонній гральний кубик, на 880 сторонах відзначена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 і на 2640 сторонах відзначена хромосома 5. Щоб вибрати першу пару кидаємо кубик два рази і вибираємо хромосоми, що випали. У такий же спосіб вибираючи інших, одержуємо:

Таблиця 4 - Симуляція вибору батьків

Хромосома батька	Хромосома матері
3	1

54

Хромосома батька	Хромосома матері
5	2
3	5
2	5
5	3

Кожен нащадок містить інформацію про гени і батька і матері. Це можна забезпечити різними способами, однак у нашому випадку можна використовувати т.зв. "кросінговер" (cross-over). Нехай мати

містить наступний набір рішень: a1,b1,c1,d1, а батько - a2,b2,c2,d2, тоді можливо 6 різних кросінговерів (| = розділова лінія):

Таблиця 5 - Кросінговери між батьками Хромосома- Хромосома-мати Хромосома-нащадок

батько

a1 | b1,c1,d1	a2 | b2,c2,d2	a1,b2,c2,d2 or a2,b1,c1,d1
a1,b1 | c1,d1	a2,b2 | c2,d2	a1,b1,c2,d2 or a2,b2,c1,d1
a1,b1,c1 | d1	a2,b2,c2 | d2	a1,b1,c1,d2 or a2,b2,c2,d1

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

А тепер спробуємо проробити це з нащадками.

Таблиця 6 - Симуляція кросінговерів хромосом батьків

Хромосома-	Хромосома-	Хромосома-
батько	мати	нащадок
(13 | 5,7,3)	(1 | 28,15,3)	(13,28,15,3)
(9,13 | 5,2)	(14,9 | 2,4)	(9,13,2,4)
(13,5,7 | 3)	(9,13,5 | 2)	(13,5,7,2)
(14 | 9,2,4)	(9 | 13,5,2)	(14,13,5,2)
(13,5 | 7, 3)	(9,13 | 5, 2)	(13,5,5,2)

Тепер ми можемо обчислити коефіцієнти виживання (fitness)

нащадків.

Таблиця 7 - Коефіцієнти виживання нащадків (fitness)

55

Хромосома-	Коефіцієнт
нащадок	виживання
(13,28,15,3)	|126-30|=96
(9,13,2,4)	|57-30|=27
(13,5,7,2)	|57-30|=22
(14,13,5,2)	|63-30|=33
(13,5,5,2)	|46-30|=16

Середня пристосованість (fitness) нащадків виявилася 38.8, у той час як у батьків цей коефіцієнт дорівнював 59.4. Наступне покоління може мутувати. Наприклад, ми можемо замінити одне зі значень якоїнебудь хромосоми на випадкове ціле від 1 до 30.

Продовжуючи таким чином, одна хромосома зрештою досягне коефіцієнта виживання 0, тобто стане розв’язком. Системи з більшою популяцією (наприклад, 50 замість 5-и сходяться до бажаного рівня (0) більш швидко і стабільно.

Контрольні питання

1.Що таке генетичний алгоритм?

2.Класичний підхід до побудови ГА.

3.Кросінговер, мутація, інверсія, їх реалізація.

Варіанти завдань

Знайти розв’язок Діофантова рівняння згідно варіанту:

1.a+2b+3c+4d+7е=39

2.a+2b+3c=30

3.a+12b+32c+41d=23170

4.11a+22b+33c+44d=123430

5.98a+72b+63c+54d=432132

6.4a+42b+43c=4430

7.2a+22b+23c+24d=22230

8.12a+92b+3c=37650

9.5a+2b+3c+4d=30

10.4a+42b+43c+14d=345670

Вимоги до звіту

Звіт повинен містити детальний опис алгоритму для вирішення задачі, його програмну реалізацію та декілька варіантів результатів роботи алгоритму.

56