Генетичні алгоритми та емерджентне навчання
Міністерство освіти і науки
України
Тернопільський національний
технічний університет імені
Івана Пулюя
Кафедра комп’ютерних систем
та мереж
РЕФРЕАТ
з дисципліни: «Засоби
машинного навчання»
на тему:
Генетичні алгоритми та
емерджентне навчання
Виконав: Куровський Р.А.
студент групи СІд-2
Прийняв: Тиш Є.В.
Тернопіль - 2015
ЗМІСТ
ВСТУП
. Емерджентне
навчання
. Генетичні алгоритми
ВИСНОВКИ
СПИСОК ВИКОРИСТАНИХ
ДЖЕРЕЛ
ВСТУП
У сучасні часи, коли комп’ютер став невід’ємним помічником,
людина потребує все більше можливостей від машини. Але це складно досягнути
шляхом зовнішнього керування. За для пришвидшення функціонування, комп’ютер
повинен самотужки себе програмувати на потрібні задачі та передбачати наступні
завдання. Таку можливість машині може надати штучний інтелект.
Успіх розвитку штучного інтелекту залежить від принципів
машинного навчання. Машинне навчання - це процес, в результаті якого машина
(комп'ютер) здатна показувати поведінку, яку в неї не було явно закладено
(запрограмовано). Машинне навчання використовує розділи математичної
статистики, чисельних методів оптимізації, теорії ймовірностей, дискретного
аналізу виділяє знання з даних.
До методів оптимізації відноситься емерджентне навчання, яке
основане на принципах дії еволюції у природі. Реалізацією такого навчання є
генетичний алгоритм. Цей алгоритм може створювати рішення задачі так само як у
природі створюються популяції живих організмів, а потім знайти більш вдалі
рішення по принципу природнього відбору.
В даному рефераті висвітлюються основні принципи
емерджентного навчання, емерджентні погляди на біологічні закони та інтелект.
Також розглядається історія та робота генетичного алгоритму.
1.
Емерджентне навчання
З розвиненням сучасних технологій та ростом виробничої потужності,
людина все більше намагається створити машину яка буде помічником у здоланні
все більш складних задач. Але для цього машина повинна мати власний інтелект,
який дасть їй змогу керувати собою, а не за допомогою людини. Щоб досягнути
такого результату, штучний інтелект повинен аналізувати власний досвід та
навчатись завдяки йому. Тому існує великій підрозділ штучного інтелекту який
відповідає за навчання - машинне навчання.
Машинне навчання основане на біологічних принципах, а саме
закону природного відбору, називається емерджентне. Емерджентні, або
проявляються, моделі навчання імітують найбільш елегантну і потужну форму
адаптації - еволюцію форм життя рослинного і тваринного світу. Як зазначив
Чарльз Дарвін, немає "меж цієї енергії, яка повільно, але вірно адаптує
кожне створення до найскладнішим життєвим відносинам". У процесі простого
варіювання деяких властивостей найбільш життєздатних поколінь і вибіркового
відсіву менш вдалих примірників підвищуються адаптаційні здібності і
проявляються відмінності між особинами популяції. Еволюція і зародження нових
властивостей відбуваються в популяціях матеріальних особин, які діють один на
одного і піддаються зовнішньому впливу.
Приклади навчання, що представляє собою соціальну взаємодію з
метою виживання, можна знайти в таких іграх, як "Життя".
Рис 1.1 Гра Життя
Правила гри:
• «Життя» розігрується на нескінченному картатому полі.
• У кожної клітини 8 сусідніх клітин.
• У кожній клітині може жити істота.
• Істота з двома або трьома сусідами виживає в наступному
поколінні, інакше гине від самотності чи перенаселеності.
•У порожній клітці з трьома сусідами в наступному поколінні
народжується істота.
Ця гра спочатку була розроблена математиком Джоном Хортоном
Конвеем та представлена широкої громадськості Мартіном Гарднером в журналі
"Scientific American" в 1970 роках. У цій грі народження, життя і
смерть особин - це функція їх власного стану та стану їх найближчих сусідів.
Зазвичай для визначення гри досить невеликої кількості правил - трьох або
чотирьох. Як показали експерименти з грою "Життя", незважаючи на цю
простоту, в її рамках можуть еволюціонувати надзвичайно складні структури, у
тому числі багатоклітинні організми, що мають функцію самореплікації.
Один з важливих підходів до штучного життя полягає в
моделюванні умов біологічної еволюції за рахунок взаємодії кінцевих автоматів,
заданих наборами станів і правил переходу. Ці автомати можуть приймати
інформацію із зовнішнього середовища, зокрема, від найближчих сусідів. Правила
переходів містять інструкції з народженням, продовженню життя і смерті. Якщо
популяція таких автоматів вільно діє у своїй предметній області, і її особини
можуть взаємодіяти як паралельні асинхронні агенти, то іноді можна спостерігати
еволюцію практично незалежних "форм життя".
Цей приклад має два загальних аспекти. По-перше, коріння
інтелекту пов'язані з культурою і суспільством, а отже, розум є емерджентним.
По-друге, розумна поведінка формується спільними діями великого числа дуже
простих взаємодіючих напівавтономних індивідуумів, або агентів. Є агенти
нервовими клітинами, індивідуальними особинами біологічного виду або ж окремими
особистостями в суспільстві, їх взаємодія створює інтелект. Отже, кожен агент
має певне коло малих задач, причому він розташовує малим знанням (або зовсім не
розташовує знанням) про те, що роблять інші агенти або як вони це роблять.
Кожен агент виконує свою незалежну частину вирішення проблеми і видає власне
результат або повідомляє результат. Агенти відчувають свою середу існування,
взаємодіють за для вирішення задач. Працюючи на вирішенням кожний агент робить
своє завдання та може корегувати роботу інших агентів. У такій середі існування
створюється інтелект і така середа є емерджентною.
Керуючись такими принципами машина починає отримувати досвід.
Види створюються в процесі біологічної еволюції за рахунок відбору найбільш
сприятливих змін геному. Аналогічно в процесі культурної еволюції при передачі
соціально оброблених і модифікованих одиниць інформації формуються знання. Генетичні
алгоритми та інші формальні еволюційні аналоги обумовлюють більш точне рішення
задачі за рахунок операцій над популяціями кандидатів на роль рішення.
2.
Генетичні алгоритми
Генетичний алгоритм - це алгоритм пошуку, який
використовується для пошуку рішень, моделювання та оптимізації шляхом схожим на
природний відбір Чарльза Дарвіна - "виживає найбільш пристосований".
Як еволюціонують живі організми в природі, так і алгоритм здатен
"розвивати" вирішення реальних завдань, якщо ті відповідним чином закодовані.
Таким чином використання генетичних алгоритмів дуже практично в оточуючому нас
світі. Алгоритми використовуються у різних програмних продуктах, які дозволяють
автоматично розрахувати оптимальну частоту за для якості зв’язку або
спроектувати споруду, що буде відповідати вимогам міцності, та ваги.
Перші роботи з симуляції еволюції були проведені в 1954 році
Нільсом Баричелла на комп'ютері , встановленому в Інституті перспективних
досліджень Прінстонського університету. Перша його робота опублікована у 1957
році, викликала великий інтерес у світової спільноти. І вже з 1963 року
генетичні алгоритми, не зважаючи, на свій початковий стан, стають загально
визнаним методом оптимізації.
У 1970 роках двадцятого століття - група Інго Рехенсберга
змогла вирішити складні інженерні проблеми згідно стратегіям еволюції. Та в цей
період часу з’являється інший підхід до алгоритму. Лоренс Дж. Фогель розробив
техніку еволюційного програмування машини, яка була запропонована для створення
штучного інтелекту. Також в ці роки генетичні алгоритми популяризував Джон
Холланд у своїй книзі «Адаптація в природних і штучних системах » (1975). Він
ввів формалізований підхід для прогнозування якості наступного покоління,
відомий як «Теорема схем».
До середини 1980 рокі генетичні алгоритми залишались тільки в
теорії. Але з ростом обчислювальної потужності комп’ютерів, їх стали
впроваджувати у практику. Так General Electric почала продаж першого в світі
продукту , який працював з використанням генетичного алгоритму - промисловий обчислювальний
прибор.
Ось в ці часи і були сформований основний код генетичного
алгоритму:
ПОЧАТОК /* генетичний алгоритм */
Створити початкову популяцію
Оцінити пристосованість кожної особи
зупинка := FALSE
ПОКИ НЕ зупинка ВИКОНУВАТИ
ПОЧАТОК /* створити популяцію нового покоління */
ПОВТОРИТИ (розмір_популяції/2) РАЗ
ПОЧАТОК /* цикл відтворення*/
Вибрати дві особи з високою пристосованістю з попереднього
покоління для схрещування
Схрестити вибрані особи і отримати двох нащадків
Оцінити пристосованість нащадків
Помістити нащадків у нове покоління
КІНЕЦЬ
ЯКЩО популяція зійшлася ТО зупинка := TRUE
КІНЕЦЬ
КІНЕЦЬ
емерджентний біологічний генетичний алгоритм
В генетичному алгоритмі виділяють три основні етапи:
· Схрещування.
· Селекція (відбір).
· Формування нового покоління.
Ці кроки можуть повторюватися доки, поки відбудеться одне з
нижче перерахованих умов:
· Кількість поколінь (циклів) досягне заздалегідь
обраного максимуму.
· Вичерпано час на мутацію.
Ці кроки потрібно висвітлити більш детально.
Створення нової популяції. На цьому кроці створюється
початкова популяція, яка, цілком можливо, виявиться неконкурентоспроможною,
проте велика ймовірність, що алгоритм цю проблему виправить. Головне, щоб вона
відповідала «формату» і була «пристосовані до розмноження».
Селекція. Розмноження в генетичних алгоритмах зазвичай
статеве - щоб утворився нащадок, потрібні кілька батьків, зазвичай два.
Виділяють кілька операторів селекції:
Панміксія - обидва батьки вибираються випадково, кожна
особина популяції має рівні шанси виграти.
Інбридинг - перша батьківська особина вибирається випадково,
а другим вибирається таким, який найбільш схожий на першу батьківську особину.
Турнірна селекція - спочатку випадково вибирається
встановлену кількість особин (зазвичай дві), а потім з них вибирається особина
з кращим значенням функції пристосованості.
Метод рулетки - ймовірність вибору особини тим імовірніше,
чим краще її значення функції пристосованості
де 
- ймовірність вибору i особини,
- значення функції пристосованості для i особини,
N - кількість особин в популяції.
Метод ранжирування - ймовірність вибору залежить від місця в
списку особин відсортованому за значенням функції пристосованості
,
де a 
[1, 2],
b = 2-a, i - порядковий номер особини в списку
особин відсортованому за значенням функції пристосованості (тобто 
- якщо мінімізувати значення функції
пристосованості).
Рівномірний ранжування - ймовірність вибору особини
визначається виразом:
,
де µ ≤ N параметр методу.
Сигма відсікання - для запобігання передчасної збіжності
генетичного алгоритму використовуються методи які масштабують значення цільової
функції. Імовірність вибору особини тим більше, чим оптимальніше значення
масштабованої цільової функції
,
де 
,
- середнє значення цільової функції для всієї популяції,
σ - середньоквадратичне
відхилення значення цільової функції.
Розмноження (Схрещування). Розмноження в генетичних
алгоритмах залежить від представлення даних. Головна вимога до розмноження -
щоб нащадок або нащадки мали можливість успадкувати риси обох батьків,
«змішавши» їх. На початку обирається точка схрещування, після цього створюється
хромосома-нащадок шляхом комбінування сегмента першої батьківської особи, яка
стоїть зліва від обраної точки схрещування, з сегментом другої батьківської
особи, яка розташована по праву сторону від точки схрещування.
Рис. 2.1 Операція схрещування
Цей метод працює дуже добре, якщо хромосоми являють собою
бітові рядки. Крім того продуктивність всього генетичного алгоритму в першу
чергу залежить від продуктивності використовуваної операції схрещування.
Операція мутації. Мутація - це фонова операція, яка виробляє
випадкові зміни в різних хромосомах. Найпростіший варіант мутації полягає в
випадковій зміні одного або більше генів. У генетичному алгоритмі мутація
відіграє важливу роль для відновлення генів, що випали з популяції в ході
операції вибору, так що вони можуть бути випробувані в нових комбінаціях,
також, формування генів, які не були представлені в вихідної популяції.
Інтенсивність мутацій визначається коефіцієнтом мутацій - 
. Він являє собою частку генів, що
піддаються мутації на даній ітерації, в розрахунку на їх загальне число.
Занадто мале значення призводить до того, що багато генів, які могли б бути
корисними, ніколи не будуть розглянуті. У той же час занадто велике значення
коефіцієнта мутацій призведе до великих випадкових обурень. Нащадки перестануть
бути схожими на батьків і алгоритм втратить можливість навчатися, зберігаючи
спадкові ознаки.
Відбір. На етапі відбору потрібно з усієї популяції вибрати
певну її частку, яка залишиться «в живих» на цьому етапі еволюції. Є різні
способи проводити відбір. Імовірність виживання особини h повинна залежати від
значення функції пристосованості Fitness (h). Частка особин що вижили - s,
зазвичай, є параметром генетичного алгоритму, і її просто задають заздалегідь.
За підсумками відбору з N особин популяції H повинні залишитися sN особин, які
увійдуть в підсумкову популяцію H'. Решта особини гинуть.
Ця модель еволюційного розвитку, застосовувана в генетичному
алгоритмі, сильно спрощена в порівнянні зі своїм природним аналогом, проте ця
технологія є досить потужним засобом і може з успіхом застосовуватися для
широкого класу прикладних задач, включаючи ті, які важко, а іноді й зовсім
неможливо, вирішити іншими методам.
ВИСНОВКИ
Машинне навчання яке включає у себе емерджентні та соціальні
принципи, дозволяє штучному інтелекту вирішувати задачі таким самим методом, як
у природі біологічні організми діють по закону природного відбору.
Генетичний алгоритм не має значних математичних вимог до
видів цільових функцій і обмежень. Дослідник не повинен спрощувати модель
об'єкта, втрачаючи її адекватність, і штучно добиваючись можливості
застосування доступних математичних методів. При цьому можуть використовуватися
найрізноманітніші цільові функції і види обмежень (лінійні і нелінійні),
визначені на дискретних, безперервних і змішаних універсальних множинах. Тобто
генетичні алгоритми можливо використовувати у розв’язанні задач, навіть, якщо
для вирішення нема спеціально розробленої методології.
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
1.
Джордж Ф. Люгер Штучний інтелект. Стратегії та методи вирішення складних
проблем. Четверте видання. - М., СПБ., К.: Вільямс 2003. - С.483-513
.
Ісаєв Сергій Популярно о генетичних алгоритмах: [Електрон. ресурс]
.
Ротштейн А.П. Інтелектуальні технології ідентифікації: [Електрон. ресурс]
.
Wikipedia Машинне навчання: [Електрон. ресурс]
.
Wikipedia Генетичний алгоритм: [Електрон. ресурс]