→ Пошук по сайту       Увійти / Зареєструватися
Знання Генетичні алгоритми

Генетичні алгоритми. Ключові поняття і методи реалізації

1.1. Вступ

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

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

Ідею генетичних алгоритмів висловив Дж. Холланд у кінці шістдесятих — початку сімдесятих років XX століття. Він зацікавився властивостями процесів природної еволюції (в тому числі фактом, що еволюціонують хромосоми, а не самі живі істоти). Холланд був упевнений у можливості скласти і реалізувати у вигляді комп'ютерної програми алгоритм, який буде вирішувати складні задачі так, як це робить природа — шляхом еволюції.

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

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

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

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

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

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

1.2. Генетичні алгоритми і традиційні методи оптимізації

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

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

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

1.3. Основні поняття генетичних алгоритмів

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

Популяція — це кінцева множина особин.

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

Хромосоми (інші назви — ланцюжки або кодові послідовності) — це впорядковані послідовності генів.

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

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

Фенотип — це набір значень, які відповідає даному генотипу, тобто декодована структура або безліч параметрів задачі (розв’язок, точка простору пошуку).

Алель — це значення конкретного гена, також визначається як значення властивості або варіант властивості.

Локус чи позиція вказує місце розміщення даного гена в хромосомі (ланцюжку). Множина позицій генів — це локи.

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

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

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

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

Приклад 1.1

Розглянемо функцію

f(х) = 2х2 +1 (1.1) і припустимо, що х приймає ціле значення з інтервалу від 0 до 15. Задача оптимізації цієї функції полягає в переміщені в просторі, який складається з 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

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

Популяція складається із особин, що вибираються серед цих 16 хромосом. Прикладом популяції з чисельністю, рівною 6, може бути, наприклад, множина хромосом {0010, 0101, 0111, 1001, 1100, 1110}, які представляють собою закодовану форму наступних фенотипів: {2, 5, 7, 9, 12, 14}. Функція пристосованості в цьому прикладі задається виразом (1.1).

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

Приклад 1.2

Розглянемо наступний приклад постановки оптимізаційної задачі. Для системи, що зображена на рисунку, слід знайти

де к1 к2є [кmin, кmax].

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

При цьому значенню кmin зпівставлена кодова послідовність, що складається з одних нулів, а значенню кmax — кодова послідовність, що складається з одних одиниць. Довжина цих кодових послідовностей залежить від значень к1 і к2, а також від частоти дискретизації інтервалу [кminmax].

Припустимо, що кmin = -25, акmax = 25 і для кожного із параметрів к1 і к2 застосовуються кодові послідовності довжиною 10. Приклад популяції, що складається з 10 особин, наведено в таблиці 1.1. Перші 10 генів кожного генотипу відповідають параметру к1, а останні 10 генів — параметру к2. Таким чином, довжина хромосом дорівнює 20. Спосіб кодування значень параметрів к1 і к2 у вигляді хромосом буде докладно викладено в розд. 1.6..

Рис. 1.1. Схема оптимізаційної двопараметричної системи.

Генотипи Фенотипи
00000000000000000000 -25,00 -25,00
10100010010011001011 6,72 -15,08
01101000101111010010 -4,57 22,8
11011010011110000111 17,67 19,13
00011011000000010001 -19,72 -24,17
00110000101011111010 -15,52 12,24
11111111111111111111 25,00 25,00

Приклад 1.3

Розглянемо нейронну мережу, представлену на рис. 1.2, для якої необхідно підібрати оптимальні ваги W11, W12, W21, W22, W31, W32 и W10, W20, и W30, які мінімізують значення похибки

Це мережа, яка реалізує систему ХОR, тому значення и1,і і и2,і, а також , для і=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. ініціалізація, або вибір вихідної популяції хромосом;
  2. оцінка пристосованості хромосом в популяції;
  3. перевірка умови зупинки алгоритму;
  4. селекція хромосом;
  5. застосування генетичних операторів;
  6. формування нової популяції;
  7. вибір «найкращої» хромосоми.

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

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

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

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

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

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

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

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

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

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

загрузка...
Сторінки, близькі за змістом