Приклад 1.3

Розглянемо нейронну мережу, представлену на рис. 1.2, для якої необхідно підібрати оптимальні ваги W₁₁, W₁₂, W₂₁, W₂₂, W₃₁, W₃₂ и W₁₀, W₂₀, и W₃₀, які мінімізують значення похибки

Це мережа, яка реалізує систему ХОR, тому значення и₁,і і и₂,і, а також , для і=1, …, 4 приймають значення, які приведені в табл. 1.1.

Як параметри розглянутої задачі виступають перераховані вище ваги, тобто завдання має 9 параметрів. У даному прикладі набір з цих 9 параметрів визначає точку простору пошуку і, отже, являє собою можливий розв’язок. Припустимо, що ваги можуть приймати значення з інтервалу [-10, 10]. Тоді кожна хромосома буде комбінацією з 9 двійкових послідовностей, що кодують конкретні ваги. Це, очевидно, і є генотипи.

Відповідні їм фенотипи представлені значеннями окремих ваг, тобто множинами відповідних дійсних чисел з інтервалу [-10, 10]. У наведених прикладах (1.1 - 1.3) хромосоми і генотипи позначають одне й те саме – фенотипи особин популяції, закодовані у формі упорядкованих послідовностей генів зі значеннями (алелями), рівними 0 або 1.

У генетиці генотип задає генетичну структуру особини, яка може включати більше однієї хромосоми. Наприклад, клітини людина містять 46 хромосом. У генетичних алгоритмах генотип визначається аналогічним чином, однак найчастіше він складається всього з однієї хромосоми, яка і виступає в ролі особини популяції. Довжина хромосом залежить від умов завдання (див. розд. 1.6). Слід зауважити, що в природних організмах хромосома може складатися з декількох сотень і навіть тисяч генів У людини є близько 100 000 генів, хоча їхня точна кількість досі невідома.

Рис.1.2. Нейронна мережа, яка реалізує операцію XOR

1.4.

Основний (класичний) генетичний алгоритм (який також називається елементарним чи простим генетичним алгоритмом) складається з наступних кроків:

• ініціалізація, або вибір вихідної популяції хромосом;

• оцінка пристосованості хромосом в популяції;

• перевірка умови зупинки алгоритму;

• селекція хромосом;

• застосування генетичних операторів;

• формування нової популяції;

• вибір «найкращої» хромосоми.

Блок – схема основного генетичного алгоритму зображена на рис. 1.3. Розглянемо конкретні етапи цього алгоритму більш докладно з використанням додаткових подробиць, представлених на рис. 1.4.

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

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

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

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

Рис.1.3. Блок-схема генетичного алгоритму

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

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

Рис.1.4 Схема виконання генетичного алгоритму

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

(1.2)

Де (1.3)

причому

– значення функції пристосованості хромосоми

– вірогідність селекції хромосоми.

Селекція хромосоми може бути представлена як результат повороту колеса рулетки, оскільки хромосома «яка виграла» (тобто обрана) відноситься до сектору цього колеса, що випав.

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

В результаті процесу селекції створюється батьківська популяція, також звана батьківським пулом (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 – з генів першого з батьків.

Дія оператора схрещування буде проілюстрована прикладами 1.4 та 1.5 (п.п. 1.5 та 1.6).

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

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

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

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

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

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

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

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

Наприклад, якщо як батьків випадковим чином вибираються дві хромосоми з батьківського популяції чисельністю N, то Pс=2/N. Аналогічно, якщо з батьківського популяції чисельністю N вибирається 2z хромосом (z <= N / 2), які утворюють z пар батьків, то Pс = 2z/N.

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

Операція мутації змінює значення генів у хромосомах із заданою вірогідністю рm способом, представленим при описі відповідного оператора. Це призводить до інвертування значень відібраних генів з 0 на 1 і навпаки. Значення рm, як правило, дуже мале, тому мутації піддається лише невелика кількість генів. Схрещування – це ключовий оператор генетичних алгоритмів, що визначає їх можливості та ефективність. Мутація грає більш обмежену роль. Вона вводить в популяцію деяку різноманітність і попереджає втрати, які могли б відбутися внаслідок виключення якого-небудь значимого гена в результаті схрещування.

Основний (класичний) генетичний алгоритм відомий у літературі в якості інструменту, в якому виділяються три види операцій: репродукція, схрещування і мутація. Терміни селекції та репродукція в даному контексті використовуються як синоніми. При цьому репродукція в даному випадку пов'язується радше з створенням копій хромосом батьківського пулу, тоді як більш поширений зміст цього поняття означає процес формування нових особин, що походять від конкретних батьків (див. розд. 1.1). Якщо ми приймаємо таке тлумачення, то оператори схрещування і мутації можуть вважатися операторами репродукції, а селекція – відбором особин (хромосом) для репродукції.

1.5.

Розглянемо виконання описаного в попередньому розділі класичного генетичного алгоритму на як можна більш простому прикладі [19]. Простежимо послідовність виконання його етапів, відповідних блок-схемі на рис. 1.3.

Приклад 1.4

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

Ініціалізація, або вибір вихідної популяції хромосом. Необхідно випадковим чином згенерувати 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.3) умова зупинки алгоритму не виконується, то на наступному кроці проводиться селекція хромосом з поточної популяції.

Селекція хромосом. Селекція проводиться методом рулетки. На підставі формул (1.2) і (1.3) для кожної з 8 хромосом поточної популяції (у нашому випадку – вихідної популяції, для якої N = 8) отримуємо сектори колеса рулетки, виражені у відсотках (рис. 1.5)

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

Як видно, хромосома ch7 була обрана тричі, а хромосома ch3 – двічі. Зауважимо, що саме ці хромосоми мають найбільше значення функції пристосованості. Проте обрана й хромосома ch4 з найменшим значенням функції пристосованості. Всі вибрані таким чином хромосоми включаються в так званий батьківський пул.

Рис. 1.5. Колесо рулетки для селекції в прикладі 1.4.

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

ch2 и ch7 ch1 и ch7 ch3 и ch4 ch3 и ch7

Для першої пари випадковим чином вибрана точка схрещування lk = 4, для другої lk = 3, для третьої lk = 11, для четвертої lk = 5. При цьому процес схрещування протікає так, як показано на рис. 1.6. В результаті виконання оператора схрещування виходять 4 пари нащадків.

Якщо б при випадковому підборі пар хромосом для схрещування були об'єднані, напрклад, ch3 с ch3 и ch4 с ch7 вместо ch3 с ch4 и ch3 с ch7, а інші пари залишились без змін, то схрещування ch3 с ch3 дало б дві такі ж хромосоми незалежно від розіграної точки схрещування. Це означало б одержання двох нащадків, ідентичних своїм батькам. Зауважимо, що така ситуація найбільш імовірна для хромосом з найбільшим значенням функції пристосованості, тобто саме такі хромосоми отримують найбільші шанси на перехід до нової популяцію.

Рис. 16. Процес схрещування хромосом у прикладі 1.4.

Формування нової популяції. Після виконання операції схрещування ми отримуємо (згідно рис. 1.6) наступну популяцію нащадків:

Ch1 = [001111011011] Ch5 = [011101110010]

Ch2 = [101000111010] Ch6 = [001000101001]

Ch3 = [111011011011] Ch7 = [011101011011]

Ch4 = [101001100101] Ch8 = [101011110011]

Щоб відрізнити від хромосом попередньої популяції позначення знову сформованих хромосом починаються з великої літери С.

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

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 з найбільшим значенням функції пристосованості, яким не володіла ні одна хромосома з батьківського популяції.

Проте могло статися і зворотне, оскільки після схрещування на першій ітерації хромосома, яка в батьківській популяції характеризувалася найбільшим значенням функції пристосованості, могла просто «загубитися». Крім цього «середня» пристосованість нової популяції все одно виявилася б вищою від попередньої, а хромосоми з великими значеннями функції пристосованості мали б шанси з'явитися в наступних поколіннях.