Перспективні прикладні системи підтримки прийняття рішень. Генетичні алгоритми

 

1. Історія розвитку генетичних алгоритмів
2. Сутність генетичних алгоритмів 
3. Основні поняття генетичних алгоритмів 
4. Класичний генетичний алгоритм

 

 

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

На світогляд людей сильно вплинула теорія еволюції Чарльза Дарвіна, представлена в роботі "Походження Видів", в 1859 році. Безліч областей наукового знання багатьом зобов'язана революції, викликаною теорією еволюції і розвитку. Але Дарвін, подібно багатьом сучасникам, що передбачає, що в основі розвитку лежить природний відбір, не міг не помилятися. Наприклад, він не зміг показати механізм успадкування, при якому підтримується мінливість. Однак Дарвін виявив головний механізм розвитку: відбір у поєднанні з мінливістю. У багатьох випадках, специфічні особливості розвитку через мінливість і відбір все ще не безперечні, однак, основні механізми пояснюють неймовірно широкий спектр явищ, що спостерігаються в природі. Тому не дивно, що вчені, які займаються комп'ютерними дослідженнями, у пошуках натхнення звернулися до теорії еволюції. Можливість того, що обчислювальна система, наділена простими механізмами мінливості і відбору, могла б функціонувати за аналогією з законами еволюції в природних системах, була дуже привабливою. Ця надія є причиною появи ряду обчислювальних систем, побудованих на принципах природного відбору. 

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

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

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

 

 

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

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

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

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

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

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

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

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