414. Алгоритм методу мурашки. (Ant algorithms), оптимізація, за принципом мурашиної колонії (алгоритму (Marco Dorigo)).

Базова ідея алгоритму мурахи – оптимізація рішень шляхом непрямого зв‘язку між автономними агентами. Він використовується для вирішення як статичних, так і динамічних проблем. Алгоритми мурахи працюють за тим же принципом, що і самі мурахи. Це виражається в тому, що змодельовані мурахи разом вирішують проблему і допомагають іншим мурахам в подальшій оптимізації рішення. Мураха – програмний агент, який є членом великої колонії та використовується для вирішення будь-якої проблеми. Мураха забезпечується набором простих правил, які дозволяють йому обирати шлях у графі. Він підтримує список табу, тобто список вузлів, які він вже відвідав. Таким чином, мураха повинен проходити через кожний вузол тільки один раз. Шлях між двома вузлами графу, яким мураха відвідав кожний вузол тільки один раз, називається шляхом Гамільтона. Вузли у списку ―поточної подорожі‖ розміщуються в тому порядку, в якому мураха відвідував їх. Пізніше список використовується для визначення протяжності шляху між вузлами. Рух мурахи засновується на дуже простому імовірнісному рівнянні. Після того, як шлях мурахи завершився, грані оновлені у відповідності з довжиною шляху і відбулося випаровування ферменту на всіх гранях, алгоритм запускається повторно. Список табу очищається, і довжина шляху обнуляється. Цей процес може виконуватись для постійної кількості шляхів або до моменту, коли на протязі декількох запусків не було відмічено повторних змін. Потім визначається найкращий шлях, котрий і є рішенням. Приклад використання алгоритму мурахи - задача комівояжера (знаходження найкоротшого шляху між містами, при якому кожне місто буде відвідане лише один раз). Тобто треба знайти найкоротший Гамільтонів шлях у графі, де в якості вузлів виступають міста, а в якості граней – дороги, що їх з‘єднують. Існує ряд комбінацій параметрів алгоритму, які дозволяють знаходити гарні результати за незначний час. Параметр α асоціюється з кількістю ферменту, а параметр β - з видимістю (довжиною грані). Чим більше значення параметру, тим він важливіший для імовірнісного рівняння, яке використовується при виборі грані. Найкращий результат досягається в тому випадку, коли кількість мурах дорівнює кількості міст. Області застосування: 1. Розподіл ресурсів – необхідно задати групу ресурсів n для ряду адресатів m і при цьому мінімізувати витрати на перерозподіл. 2. Розподіл роботи – група машин M і завдань J повинні бути розподілені таким чином, щоб всі завдання виконувалися за мінімальний час. 3. Прокладка маршрутів для автомобілів. 4. Розрахунок кольорів для графіків. 5. Маршрутизація в мережах.

418. Алгоритм програми сортування на базі дерева висновків. Дерева прийняття рішень зазвичай використовуються для вирішення задач класифікації даних або, інакше кажучи, для завдання апроксимації заданої булевої функції. Ситуація, в якій варто застосовувати дерева прийняття рішень, зазвичай виглядає так: є багато випадків, кожен з яких описується деяким кінцевим набором дискретних атрибутів, і в кожному з випадків дано значення деякої (невідомої) булевой функції, що залежить від цих атрибутів. Завдання - створити досить економічну конструкцію, яка б описувала цю функцію і дозволяла класифікувати нові, що надходять ззовні дані. Дерево прийняття рішень - це дерево, на ребрах якого записані атрибути, від яких залежить цільова функція, в листі записані значення цільової функції, а в інших вузлах - атрибути, за якими розрізняються випадки. Щоб класифікувати новий випадок, треба спуститися по дереву до листа і видати відповідне значення. Алгоритми побудови дерева Загальна схема побудови дерева прийняття рішень за тестовими прикладів виглядає наступним чином: Вибираємо черговий атрибут Q, поміщаємо його в корінь. Для всіх його значень i: Залишаємо з тестових прикладів тільки ті, у яких значення атрибута Q одно i Рекурсивно будуємо дерево в цьому нащадку Основне питання: як вибирати черговий атрибут? Є різні способи вибирати черговий атрибут: Алгоритм ID3 - один з алгоритмів для побудови дерева прийняття рішень. Розроблено Джоном Р. Квінланом (англ. John R. Quinlan). Загалом, алгоритм ID3 наступний: Взяти всі невикористані ознаки і порахувати їх ентропію щодо тестових зразків Вибрати ознака, для якого ентропія мінімальна (а інформаційна вигода відповідно максимальна) Зробити вузол дерева, що містить ця ознака Алгоритм наступний: ID3 (Таблиця прикладів, Цільовий ознака, Ознаки) Якщо всі приклади позитивні, то повернути вузол з міткою «+». Якщо всі приклади негативні, то повернути вузол з міткою «-».

Якщо безліч ознак пусте, то повернути вузол з міткою, яка більше за інших зустрічається в значеннях цільового ознаки в прикладах. Інакше: A - ознака, яка найкраще класифікує приклади (з максимальною вигодою інформаційної). Створити корінь дерева рішення; ознакою в корені буде A. Для кожного можливого значення A (vi): Додати нову гілку дерева нижче кореня з вузлом зі значенням A = vi Виділити підмножина Examples (vi) прикладів, у яких A = vi. Якщо підмножина прикладів порожньо, то нижче цієї нової гілки додати вузол з міткою, яка більше за інших зустрічається в значеннях цільового ознаки в прикладах. Інакше, нижче цієї нової гілки додати піддерево, викликаючи рекурсивно ID3 (Examples (vi), Цільовий ознака, Ознаки) Повернути корінь.

416. Алгоритм моделювання штучного життя (Artifical life) Еволюційні алгоритми — напрям в штучному інтелекті (розділ еволюційного моделювання), що використовує і моделює біологічну еволюцію. Розрізняють різні алгоритми: генетичні алгоритми, еволюційне програмування, еволюційні стратегії, системи класифікаторів, генетичне програмування тощо. Всі вони моделюють базові положення в теорії біологічної еволюції — процеси відбору, мутації і відтворення. Поведінка агентів визначається довкіллям. Множину агентів прийнято називати популяцією. Така популяція еволюціонує відповідно до правил відбору відповідно до цільової функції, що задається довкіллям. Таким чином, кожному агентові (індивідуумові) популяції призначається значення його придатності в довкіллі. Розмножуються лише найбільш придатні види. Рекомбінація і мутація дозволяють агентам змінюватись і пристосовуватися до середовища. Такі алгоритми відносяться до адаптивних пошукових механізмів.Моделювання еволюції можна розділити на дві категорії Системи, які використовують лише еволюційні принципи. Вони успішно використовувалися для завдань виду функціональної оптимізації і можуть легко бути описані на математичній мові. До них відносяться еволюційні алгоритми, такі як еволюційне програмування, генетичні алгоритми, еволюційні стратегії. Системи, які є біологічно реалістичніші, але які не виявилися корисними в прикладному сенсі. Вони більше схожі на біологічні системи і менш направлені на вирішення технічних завдань. Вони володіють складною і цікавою поведінкою, і, мабуть, незабаром отримають практичне вживання. До цих систем відносять так зване штучне життя. Еволюційні алгоритми, в сучасному вигляді, з'явились в кінці 1960-тих на початку 1970-тих (існують посилання на попердні дослідження). Еволюційні алгоритми можна поділити на три групи: Еволюційне програмування: фокусується більше на адаптації індивідів, аніж на еволюції генетичної інформації. Зазвичай, еволюційне програмування застосовує безстатеве розмноження та мутації, тобто, внесення невеликих змін в поточний розв'язок та методи селекції основані на прямій конкуренції. Еволюційні стратегії (ЕС): Важливою особливістю еволюційних стратегій є використання само-адаптивних механізмів для контролю процесу мутації. Ці механізми зосереджені не лише на еволюції шуканих розв'язків, а й на еволюції параметрів мутації. Генетичні алгоритми (ГА): Основною особливістю генетичних алгоритмів є використання оператора рекомбінації (схрещення) в якості основного механізму пошуку. Це ґрунтується на припущенні, що частини оптимального розв'язку можуть бути знайдені незалежно та рекомбіновані для отримання кращого розв'язку. Еволюційні алгоритми знайшли широке застосування. Однією з найпоширеніших галузей застосування є комбінаторна оптимізація. Так, еволюційні алгоритми з успіхом було застосовано для розв'язання класичних NP-повних проблем, таких як задача комівояжера, задача пакування рюкзака, розбиття чисел, максимальна незалежна множина та розфарбовування графів. До інших не класичних, але важливих, задач, для розв'язання яких застосовано еволюційні алгоритми, належать планування, складання розкладів, обчислення маршрутів, задачі розташування та транспортування. Також еволюційні алгоритми використовують для оптимізації структур та електронних схем, в медицині та в економіці.

419. Багатошаровий персептрон (Розпізнавання образів і навчання) Френк Розенблат в 1958 році запропонував алгоритм навчання для одного типу одношарової нейронної мережі, отримавшої назву персептрон. Вхідні значення персептрона являються біополярними. Рівень активації пресептрона вираховується як зважена сума його входів. Вихідні значення персептрона вираховуються за допомогою строгої порогової функції: якщо рівень активації перевищує, або дорівнює пороговому значенню, вихід персептрона приймаєтьс рівним 1 , в протилежному випадку – 1. Таким чином вхідні значення персептрона вичисляються на основі його вхідних значень, вагових коефіцієнтів і порога. Для настройки вагів персептрона використовується простий алгоритм навчання з учителем. Персептрон намагається вирішити запропоновану задачу, після чого йому запропоновуєтьс корректний результат. Потім ваги персептрона змінюються таким чином, щоб зменшити похибку на його виході. Якщо значення бажаного і реального співпадають то нічого не стається. Якщо реальне вихідне значення дорівнює -1, а бажане 1 , то ваговий коефіцієнт входа збільшується, а якщо реальне вихідне значення дорівнює 1, а бажане - , то ваговий коефіцієнт входа зменшується. При викоричтанні такої процедури получається вага, мінімізуюча середню помилку на всій навчаючій множині. І якщо існує набор вагових коефіцієнтів, забезпечуючий коректне вихідне значення для кожного елемента навчаючої множини, то така побудова персептрона дозволяє його отримати. Зпочатку поява персептрона була зустріта з великим ентузіазмом, але потім вчені виявили ограниченість моделі персептрона. Вони показали, що персептрон не вирішує цілий клас складних задач, в яких дані не являютьс лінійно незалежними. Навіть удосконалені моделі персептрона, втому числі і багатошаровий персептрон не могли вирішити проблему лінійної роздільності. В результаті виявлення проблеми лінійної роздільності направлення досліджень змістилось в сторону архітектур основаних на символьному представленні, а прогрес в області нейромережевої технології значно зменшився. Поки дослідження в 1970-х 1980-х роках не показали, що цю проблему можна вирішити за допомогою методу навчання по правилу зворотнього розпізнання, який являється узагальненням алгоритма навчання персептрона для багатошарових мереж.