Генетичні алгоритми

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Львівський національний університет імені Івана Франка

Економічний факультет

Кафедра економічної кібернетики

Реферат

на тему: Генетичні алгоритми

Виконав

Студент групи Екк-21

Чебикін Антон Федорович

Перевірив

Антонів Василь Богданович

Львів - 2018

ВСТУП

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

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

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

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

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

1. Історія розвитку генетичних алгоритмів

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

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

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

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

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

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

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

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

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

інтелект нейронний генетичний алгоритм

2. Сутність генетичних алгоритмів

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

· обробляють не значення параметрів самого завдання, а їх закодовану форму;

· здійснюють пошук рішення виходячи не з єдиної точки, а з їх деякої популяції;

· використовують тільки цільову функцію, а не її похідні або іншу додаткову інформацію;

· застосовують імовірнісні, а не детерміновані правила вибору.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основний (класичний) ГА складається з наступних кроків

· Ініціалізація, або вибір початкової популяції хромосом.

· Оцінювання пристосованості хромосом в популяції

· Перевірка умови закінчення алгоритму.

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

· Використання генетичних операторів

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

· Вибір найкращої хромосоми

Розглянемо ГА більш детально:

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

2. Оцінювання пристосованості хромосом в популяції полягає у розрахунку функції пристосованості для кожної хромосоми.

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

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

5. Використання генетичних операторів до відібраних у результаті селекції батьківських хромосом приводить до створення популяції нащадків. В класичному га використовують два основних генетичних оператора: оператор схрещування (crossover) і оператор мутації (mutation). Як і живих організмах, ймовірність мутації звичайно дуже мала (рм<0,1).

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

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

Оператор мутації з малою ймовірністю змінює значення гену в хромосомі на протилежне.

6. Формування нової популяції. Хромосоми, отримані у результаті генетичних операторів до популяції предків, утворюють нову популяцію. Така популяція стає поточною для даної ітерації k ГА. На кожній ітерації розраховується значення функції пристосованості для всіх хромосом. В результаті перевірки умови закінчення ітерацій відбувається або зупинка алгоритму, або перехід до нового кроку ГА - селекції. В результаті селекції вся попередня популяція замінюється популяцією нащадків з кількістю N.

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

Висновки

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

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

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

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

Список використаної літератури

1. Єремєєв А.В. Розробка та аналіз генетичних і гібридних алгоритмів для вирішення задач дискретної оптимізації, 2012.

2. Коршунов Ю.М. «Математичні основи кібернетики. Для студентів вузів», 2007.

3. Вентцель Є.С. «Дослідження операцій»,1992.

4. Завада О.П. «Алгоритмізація і програмування», 2004.

Размещено на Allbest.ru