Створення та оптимізація засобів штучного інтелекту на основі генетичних алгоритмів



Сторінка4/10
Дата конвертації12.04.2017
Розмір0.65 Mb.
1   2   3   4   5   6   7   8   9   10

2.2 Класичний генетичний алгоритм

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



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

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

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

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

л)Застосування генетичних операторів;

м)Формування нової популяції;

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

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

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

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

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

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


Рисунок 2.1 – Блок-схема основного генетичного алгоритму

2.3 Селекція

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

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

. (2.2)


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

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

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

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

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

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

У генетичному алгоритмі мутація хромосом може виконуватися на популяції батьків перед схрещуванням або на популяції нащадків, утворених в результаті схрещування [10].

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

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



  1. нащадок, хромосома якого на позиціях від 1 до Lк складається з генів першого з батьків, а на позиціях від Lк + 1 до L — із генів другого з батьків;

  2. нащадок, хромосома якого на позиціях від 1 до Lк складається з генів другого з батьків, а на позиціях від Lк + 1 до L — з генів першого з батьків.

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




Поділіться з Вашими друзьями:
1   2   3   4   5   6   7   8   9   10


База даних захищена авторським правом ©divovo.in.ua 2017
звернутися до адміністрації

войти | регистрация
    Головна сторінка


загрузить материал