Системи штучного інтелекту

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

пов'язаної з нею селекції (природнього відбору) популяцій живих істот.

— початку сімдесятих років XX століття.
Він працював над алгоритмами, що

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

пошуку, засновані на механізмах природного відбору і спадкоємства. У них

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

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

них множинами параметрів задачі, тобто рішень, які інакше називаються точками в просторі пошуку (search points). У деяких роботах особини називаються організмами.
Хромосоми (інші назви — ланцюжки або кодові послідовності) — це впорядковані послідовності генів.
Ген (який також називається властивістю, знаком чи детектором) — це атомарний елемент генотипу, зокрема, хромосоми.
Генотип або структура — це набір хромосом даної особини. Отже, особинами популяції можуть бути генотипи або одиничні хромосоми (в досить поширеному випадку, коли генотип складається з однієї хромосоми).
Фенотип — це набір значень, які відповідає даному генотипу, тобто декодована структура або безліч параметрів задачі (розв’язок, точка простору пошуку).
Алель — це значення конкретного гена, також визначається як значення властивості або варіант властивості.
Локус чи позиція вказує місце розміщення даного гена в хромосомі (ланцюжку). Множина позицій генів — це локи.

пристосованості (fitness function), яка інакше називається функцією оцінки. Вона являє міру

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

функції полягає в переміщені в просторі, який складається з 16

точок зі значеннями 0, 1, …,15 для виявлення тієї точки, в якій функція приймає максимальне (або мінімальне) значення.

змінна х. Множина {0,1,..., 15} складає простір пошуку та одночасно

— множину потенціальних розв’язків задачі. Кожне з 16 чисел, які належать цій множині, називається точкою простору пошуку, розв’язком, значенням параметра, фенотипом. Розв’язок, який оптимізує функцію, називається найкращим або оптимальним розв’язком. Значення параметра х від 0 до 15 можна закодувати наступним чином:
0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1110 1111
Пристосованість окремих хромосом в популяції визначається значенням цієї функції для значень х, які відповідають цим хромосомам, тобто для фенотипів, які відповідають певним генотипам.

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

популяції хромосом;
оцінка пристосованості хромосом в популяції;
перевірка умови зупинки алгоритму;
селекція хромосом;
застосування генетичних операторів;
формування нової популяції;
вибір «найкращої» хромосоми.

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

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

другому етапі значеннями функції пристосованості) тих хромосом, які братимуть участь

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

хромосом розглянутої популяції. Кожній хромосомі, що позначається chi для і

=1,2, …, N (де N позначає чисельність популяції) відповідає сектор колеса V(сhj), виражений у відсотках згідно з формулою

рулетки, оскільки хромосома «яка виграла» (тобто обрана) відноситься до сектору

цього колеса, що випав.
Очевидно, що чим більше сектор, тим більше вірогідність «перемоги» відповідної хромосоми. Тому ймовірність вибору даної хромосоми виявляється пропорційною значенню її функції пристосованості. Якщо все коло колеса рулетки представити у вигляді цифрового інтервалу [0, 100], то вибір хромосоми можна ототожнити з вибором числа з інтервалу [a, b], де а і b позначають відповідно початок і закінчення фрагмента кола, відповідного цьому сектору колеса; очевидно, що 0 <а < b <100.

популяція, також звана батьківським пулом (matingpool) з чисельністю N, що

дорівнює чисельності поточної популяції.
Застосування генетичних операторів до хромосом, відібраних за допомогою селекції, призводить до формування нової популяції нащадків від створеної на попередньому кроці батьківської популяції.
У класичному генетичному алгоритмі застосовуються два основних генетичних оператора: оператор схрещування (сrossover) та оператор мутації (mutation). Однак слід зазначити, що оператор мутації грає явно другорядну роль в порівнянні з оператором схрещування. Це означає, що схрещування в класичному генетичному алгоритмі здійснюється практично завжди, тоді як мутація — досить рідко. Вірогідність схрещування, як правило, досить велика (звичайно 0,5 <рc <1), тоді як імовірність мутації встановлюється дуже малою (найчастіше 0 <рm <0,1). Це випливає з аналогії зі світом живих організмів, де мутації відбуваються надзвичайно рідко.

батьківського популяції (батьківського пулу). Це тимчасова популяція, що складається з

хромосом, відібраних в результаті селекції та призначених для подальших перетворень операторами схрещування і мутації з метою формування нової популяції нащадків. На даному етапі хромосоми з батьківського популяції об'єднуються в пари.
Це здійснюється випадковим способом відповідно до ймовірністю схрещування Pс. Далі для кожної пари відібраних таким чином батьків розігрується позиція гена (локус) у хромосомі, що визначає так звану точку схрещування. Якщо хромосома кожного з батьків складається з L генів, то очевидно, що точка схрещування Lк представляє собою натуральне число, менше L. Тому фіксація точки схрещування зводиться до випадкового вибору числа з інтервалу [1, L-1] У результаті схрещування пари батьківських хромосом виходить така пара нащадків:
нащадок, хромосома якого на позиціях від 1 до Lк складається з генів першого з батьків, а на позиціях від Lк + 1 до L — із генів другого з батьків;
нащадок, хромосома якого на позиціях від 1 до Lк складається з генів другого з батьків, а на позиціях від Lк + 1 до L — з генів першого з батьків.

в хромосомі на протилежне (тобто з 0 на 1 або

навпаки). Наприклад, якщо в хромосомі [100110101010] мутації піддається ген на позиції 7, то його значення, рівне 1, змінюється на 0. що призводить до утворення хромосоми [100110001010]. Як вже згадувалося вище, ймовірність мутації зазвичай дуже мала, і саме від неї залежить, чи буде цей ген мутувати чи ні. Вірогідність рm мутації може емулюватися, наприклад, випадковим вибором числа з інтервалу [0, 1] для кожного гена і відбором для виконання цієї операції тих генів, для яких розігране число виявляється меншим або рівним значенню рm.

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

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

Необхідно випадковим чином згенерувати 8 двійкових послідовностей довжиною 12 бітів.

Це можна досягти, наприклад, підкиданням монети (96 разів, при випаданні «орла» приписується значення 1, а у разі «решки» — 0). Таким чином можна сформувати вихідну популяцію
ch1 = [111001100101] ch5 = [010001100100]
ch2= [001100111010] ch6 = [010011000101]
ch3 = [011101110011] ch7 = [101011011011]
ch4 = [001000101000] ch8 = [000010111100]

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

містить найбільшу кількість одиниць. Тому функція пристосованості визначає кількість одиниць у хромосомі. Позначимо функцію пристосованості символом F. Тоді її значення для кожної хромосоми з вихідної популяції будуть такі:
F(ch1) = 7 F(ch5)= 4
F(ch2) = 6 F(ch6) = 5
F(ch3) = 8 F(ch7) = 8
F(ch4) = 3 F(ch8) = 5

Хромосоми ch3 і ch7 характеризуються найбільшими значеннями функції приналежності. У цій популяції вони вважаються найкращими кандидатами на рішення задачі. 

На підставі формул (1.2) і (1.3) для кожної з 8

хромосом поточної популяції (у нашому випадку — вихідної популяції, для якої N = 8) отримуємо сектори колеса рулетки, виражені у відсотках
v(ch1) = 15,22 v(ch2) = 13,04 v(ch3) = 17,39 v(ch4) =6,52
v(ch5) =8,70 v(ch6) = 10,87 v(ch7) = 17,39 v(ch8) = 10,87

до випадкового вибору числа з інтервалу [0, 100], що вказує

на відповідний сектор на колесі, тобто на конкретну хромосому. Припустимо, що розіграні наступні 8 чисел:
79 44 9 74 44 86 48 23
Це означає вибір хромосом
ch7 ch3 ch1 ch7 ch3 ch7 ch4 ch2

у процесі селекції хромосом не піддається мутації, і всі вони

складають популяцію хромосом, призначених для схрещування. Це означає, що ймовірність схрещування Pс = 1, а ймовірність мутації рm = 0. Припустимо, що з цих хромосом випадковим чином сформовані пари батьків
ch2 и ch7 ch1 и ch7 ch3 и ch4 ch3 и ch7

точка схрещування lk = 4, для другої lk = 3, для третьої

lk = 11, для четвертої lk = 5. В результаті виконання оператора схрещування виходять 4 пари нащадків.

схрещування ми отримуємо наступну популяцію нащадків:
Ch1 = [001111011011] Ch5 =

[011101110010]
Ch2 = [101000111010] Ch6 = [001000101001]
Ch3 = [111011011011] Ch7 = [011101011011]
Ch4 = [101001100101] Ch8 = [101011110011]

яка стає поточною. Значення функцій пристосованості хромосом цієї популяції складають:

F(Ch1)

= 8 F(Ch5) = 7
F(Ch2) = 6 F(Ch6) = 4
F(Ch3) = 9 F(Ch7) = 8
F(Ch4) = 6 F(Ch8) = 8

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

при цьому неявно відбувається обробка шим (“sheme”), що представляють шаблони

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

довжині будь-якого рядка популяції), що складається зі знаків алфавіту {0;1;*},

де {*} - невизначений символ.

l, що мають у відповідних позиціях або 0, або 1,

у залежності від того, який біт знаходиться у відповідній позиції самої шими.
Наприклад, шима, 1**01, визначає собою множину з чотирьох п’ятибітових рядків {10001; 10101; 11001; 11101}.
У шим виділяють дві властивості - порядок і визначена довжина. Порядок шими - це число визначених бітів ("0" чи "1") у шимі.

у шимі. Наприклад, вищезгадана шима має порядок o(1**01)=3, а визначена

довжина d(1**01) = 4. Кожен рядок у популяції являється прикладом 2l шим.

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

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

t-ому поколінні. Обчислимо очікуване число прикладів H у наступному поколінні

m(H,t+1) у термінах m(H,t). Простий ГА кожному рядку ставить у відповідність імовірність її "виживання" при відбиранні пропорційно її пристосованості. Очікується, що шима H може бути обрана m(H,t)*(f(H)/fср.) разів, де fср. - середня пристосованість популяції, а f(H) - середня пристосованість тих рядків у популяції, що є прикладами H.

f(x) процедуру переходу з евклідова простору параметрів в простір представлень.

f(x) = 10 + x cos(x), на відрізку [0, 10].

3. Тобто відрізок [0,10] потрібно розбити на 23 = 8

підінтервалів, кожному з яких буде відповідати унікальна двійкова комбінація, одержувана перекладом номера підінтервала, рахуючи зліва направо, у двійковій позиційній системі. Довжина кожного такого інтервалу буде h=10:8=1,25.

2. Таких шим 2o(H)Cl=22C3=12: {00*, 01*, 10*, 11*, 0*0, 0*1,

1*0, 1*1, *00, *01, *10, *11}. Геометрично, усі такі шаблони описують поверхні, розмірність яких на одиницю перевершує розмірність крапки - вершини куба, тобто шими порядку 2 довжини 3 відповідають ребрам куба

куба. порядку 0 и довжини 3 – цілий куб

граням куба

порядків будуть відповідати таким просторам (наприклад, для шим: 11*, 00*

та 0**, 1**)

поверхні відповіді;
розриви, існуючі на поверхні відповіді мають незначний ефект

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

- приклад розв’язку задачі