Змiст

Змiст

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

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

Щоб розплавити матеріал, потрібна велика кількість енергії. При зниженнi температури зменшується і кількість енергії. Аби краще уявити процес відновлення, розглянемо наступний приклад. «Збовтування» при високій температурі супроводжується високою молекулярною активністю у фізичній системі. Уявіть собі, що ви збовтувати ємність, в якій знаходиться якась поверхню складної форми. Усередині ємності також є кулька, який намагається знайти точку рівноваги. При високій температурі кулька може вільно переміщатися по поверхні, а при низькій температурі «збовтування» стає менш інтенсивним і пересування кульки сокращаются. Завдання полягає в тому, щоб знайти точку мінімального перемещенія при сильному «збовтуванні». При зниженні температури зменшується вероятность того, що кулька вийде з точки рівноваги. Саме в такому вигляді процес пошуку запозичується з відновлення [2].













Однак якщо робоче рішення гірше, ніж поточне рішення, ми визначаємо критерій допуску, щоб з'ясувати, що слід зробити з поточним робочим рішенням. Імовірність допуску грунтується на рівнянні 1 (яке, в свою чергу, базується на законі термодинаміки):

P(Значення цієї формули візуально показано на рис. 2. При високій температурі (понад 60 ° С) погані рішення приймаються частіше, ніж відкидаються. Якщо енергія менше, ймовірність прийняття рішення вище. При зниженні температури ймовірність прийняття гіршого рішення також знижується. При цьому більш високий рівень енергії також сприяє зменшенню ймовірності прийняття гіршого рішення.

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

Зниження температури

Після ряду ітерацій за алгоритмом при даній температурі ми ненабагато знижуємо її. Існує безліч варіантів зниження температури. В даному пріме¬ре використовується проста геометрична функція (див. Рівняння 2):

Ti + 1 = αTi (2)

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

Повтор

При одній температурі виконується кілька ітерацій. Після завершення ітерацій температура буде знижена. Процес продовжиться, поки температура не досягне нуля [4].

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

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

Нейронні мережі в біологічної перспективі

Нейронні мережі (Neural network) представляють собою спрощену модель людського мозку. Мозок складається з нейронів, які є індівідуальни¬мі процесорами. Нейрони з'єднуються один з одним за допомогою нервових окон¬чаній двох типів: синапсів, через які в ядро ​​надходять сигнали, і аксонів, через які нейрон передає сигнал далі. Людський мозок складається приблизно з 1011 нейронів. Кожен нейрон пов'язаний приблизно від 1000 інших нейронів (це не відноситься до кори головного мозку, де щільність нейронних зв'язків набагато вище). Структура мозку високоціклічна, але її можна розглядати і як мно-гослойную (рис. 3). У дуже спрощеному вигляді роботу мозку можна змалювати таку картину: зовнішній шар мережі передає імпульси від сенсорів із зовнішнього середовища, середній шар (або кора головного мозку) обробляє імпульси, а «вихідний» шар видає результат (дія) назад в зовнішнє середовище.

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



Одношарові перцептрони

Одношаровий перцептрон (Single layer perceptron - SLP) являє собою концептуальну модель, яка складається з одного процесора. Кожне з'єднання від входу до ядра включає коефіцієнт, який показує фактор ваги, і позначається за допомогою ваги wi, який визначає вплив осередку ui на іншу клітинку. Позитивні ваги показують посилення, а негативні - заборона. Спільно з входами в осередок вони визначають поведінку мережі. Схема одношарового перцептрона представлена ​​на рис. 4.

Осередок на рис. 4 включає три входи (u1, u2 і u3). Крім цього, є вхід зміщення (ω0), про яке буде розказано пізніше. Кожне вхідне з'єднання має вагу (w1, w2 і w3). Нарешті, існує єдиний вихід, O. Стан нейрона позначено як γ і визначається рівнянням 3.


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

(4)

0)

Якщо значення стану більше нуля, то вихідне значення дорівнюватиме 1. Інакше воно складе -1.Моделювання булевих виразів за допомогою SLP

Хоча одношаровий перцептрон є дуже простою моделлю, її можливості досить великі. Наприклад, можна легко сконструювати базові логічні функції, як показано на рис. 5.
Згадайте, що функція І має значення 1, якщо обидва входи рівні 1, в іншому випадку функція повертає значення 0. Тому якщо задані обидва входи (вектор u = (1,1)), то, використовуючи активаційну функцію з рівняння 4 в якості порога , отримаємо наступний результат: = зміщення+ u

Тепер спробуємо підставити вектор u = (0,1):

Як показують обидва приклади, модель простого перцептрону правильно реалі¬зует логічну функцію І (а також функції АБО і НЕ). Однак одношаровий перцептрон не може змоделювати таку логічну функцію, як виключне АБО (XOR). Ця нездатність до моделювання функції XOR відома як проблема отделимости і вирішується шляхом додавання шарів.

У цьому розділі розглядається цікавий алгоритм, заснований на застосуванні декількох агентів, за допомогою якого можна вирішувати найрізноманітніші завдання. Алгоритми мурашки (Ant algorithms), або оптимізація за принципом мурашиної колонії (ця назва була придумана винахідником алгоритму, Марко Дориго (Marco Dorigo)), мають специфічні властивості, властивими мурашкам, і використовують їх для орієнтації у фізичному просторі. Алгоритми мурашки особливо цікаві тому, що їх можна використовувати для вирішення не тільки статичних, але і динамічних проблем, наприклад, проблем маршрутизації в мінливих мережах [6,7,8].

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

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

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

Детальніше алгоритм буде розглянуто в розділі 2.

Біологічне спонукання
Генетичний алгоритм (Genetic algorithm) являє собою техніку оптимізації, яка моделює феномен природної еволюції (вперше відкритий Чарльзом Дарвіном). При природної еволюції виживають і дають саме численне потомство особини, найбільш адаптовані до складних умов навколишнього середовища. Ступінь адаптації, в свою чергу, залежить від набору хромосом конкретної особи, отриманим від батьків. Це основа виживання найсильнішого - не тільки процес виживання, а й участь у формуванні наступного покоління. У природі виживання є визначальною і основною функцією.
Генетичний алгоритм
Генетичний алгоритм не намагається оптимізувати єдине рішення. Він працює з групою рішень, які кодуються, подібно хромосомами. Окремі гени хромосоми представляють собою унікальні змінні для досліджуваної проблеми (рис. 6).

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

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

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

Виконання генетичного алгоритму включає три основні кроки (причому для кожного кроку передбачений великий розкид можливих варіантів). Ці кроки показані на рис. 7.

Генетичний алгоритм виконується в три етапи (якщо не враховувати початкове створення популяції). Під час оцінки визначається здоров'я популяції. Далі проводиться відбір підгрупи хромосом на підставі попередньо заданого критерію. Нарешті, вибран¬ная підгрупа рекомбинируют, в результаті чого виходить нова популяція. Алгоритм виконується заново з новою популяцією. Процес триває до тих пір, поки не буде досягнутий певний межа. Тоді робота алгоритму вважається завершеною.
Iніціалізація

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

Етап оцінки (Evaluation) дає можливість визначити, як кожна хромосома (рішення) справляється з даною проблемою. Алгоритм декодує хромосому стосовно до проблеми і перевіряє результат вирішення проблеми c використанням нових параметрів. Потім на підставі результату розраховується «здоров'я» хромосоми (рис. 9).
Відбір



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

Існує безліч алгоритмів відбору. На рис. 9 показаний алгоритм, відомий як «Відбір по методу рулетки», або імовірнісний відбір. При використанні цього методу відбір з популяції грунтується на здоров'я хромосоми. Чим краще здоров'я хромосоми, тим більша ймовірність того, що вона буде обрана (або повторно обрано) для формування наступного покоління. Таким чином, ймовірність вибору пропорційна здоров'ю хромосоми. На рис. 10 хромосома 2 була обрана для подальшого використання два рази, хромосома 3 - теж два рази, а хромосома 5 - тільки один раз. Хромосоми 1 і 4 не були відібрані жодного разу, тому вони зникають з подальшою популяції.Рекомбинування

При рекомбiнуваннi (Recombination) частини хромосом переміщаються, може бути, навіть змінюються, а отримані нові хромосоми повертаються назад в популяцію для формування наступного покоління. Перша група хромосом зазвичай називається батьками, а друга - дітьми. З однаковою ймовірністю можуть застосовуватися один або кілька генетичних операторів. Доступні оператори включають мутацію і перехресне схрещування, які є причиною аналогами одноіменних генетичних процесів. У наступному розділі розглядаються приклади генетичних операторів. Процес рекомбинирования представлений на рис. 11.В результаті рекомбинирования утворюється нова популяція хромосом. Процес повторюється заново з етапу оцінки доти, поки проблема не буде вирішена або поки не буде виконано будь-яке інше умова завершення алгоритму (наприклад, максимально можливу кількість поколінь).

Комбінаторна оптимізація і завдання комівояжера
В задачах комбінаторної оптимізації потрібно знайти найкраще з кінцевого, але зазвичай дуже великого числа можливих рішень. Якщо завдання характеризується характерним числом елементів (розмірністю задачі), то типове число можливих рішень, з яких належить зробити вибір, зростає експоненційна - як a n або ще швидше - як N! (Нагадаємо, що згідно з відомою формулою Стірлінга N! ≅ (N / e,) n для досить великих N.

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

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

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

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

Все NP-повна задали однаково складні {оскільки всі вони зводяться один до одного за поліноміальний час), і методи вирішення будь-якої з них можна застосовувати також і до інших місій комбінаторної оптимізації Тому нам в цьому розділі досить зосередитися на одній такай завданню Історично найбільш дослідженою і популярної завданням такого роду (свого роду "мушкою дрозофіли" комбінаторної оптимізації), яка використовується для порівняння різних алгоритмів, постало завдання комівояжера

У класичній постановці, комівояжер повинен об'їхати N гооод по замкнутому маршруту, відвідавши кожен з них лише один раз, таким чином, щоб загальна довжина його маршруту була мінімальною Якщо вирішувати завдання комівояжера 'в лоб "- перебором всіх замкнутих шляхів, що зв'язують N міст то доведеться перевірити все (Nl)! / 2 можливих маршрутів Будучи NP -повної, завдання комівояжера не має практично реалізованого точного рішення На прикладі цієї задачі ми нижче і розглянемо різні методи її наближеного рішення за допомогою нейромереж.
Iмітація відпалу
У попередньому розділі ми помітили, що перехід від бінарних нейронів до аналогових значно поліпшив властивості рішення Аналогічного ефекту можна добитися використовуючи, як і раніше бінарні нейрони, але замінивши детерміністську динаміку стохастичною, що характеризується деякою ефективною температурою T. При цьому середнє значення стану нейрона також буде лежати в допустимому інтервалі [0,1]

Позитивна роль температури полягає в тому. що шум дозволяє системі залишати локальні мінімуми енергії і рухатися в бік більш глибоких енергетичних мінімумів Відповідний (НЕ нейрооетевой) алгоритм оптимізації був запропонований в 1953 р і отримав назву імітації відпалу (Metropolis et а). 1953). Цей термін походить oт назви способу випалювання дефектів в кристалічній решітці Атоми, що займає в ній неправильне місце, при низькій температурі не можуть зміститися в потрібне положення - їм не вистачає кінетичної енергії для подолання потенційного бар'єру При цьому система в цілому знаходиться в стані локального енергетичного мінімуму. Для виходу з нього метал нагрівають до високої температури, а потім повільно охолоджують. дозволяючи атомам зайняти правильні положення в решітці, відповідне глобального мінімуму енергії.

Субоптимальне рішення деякої задачі оптимізації, наприклад, завдання комівояжера, також може розглядатися як рішення в якому є дефекти - неправильні частини маршруту Лін і Керніген (Urι & Kemigan. 1973) ввели елементарні операції зміни поточного рішення, такі як перенесення (частина маршруту вирізається і вставляється в інше місце) і звернення (вибирається фрагмент маршруту і порядок проходження міст в ньому змінюється на зворотний). При застосуванні однієї з цих операцій відбувається зміна маршруту з M на M і значення минимизируемого про функціоналу змінюється на Δ E = E (M̕) - E (M). Відповідно до принципів термодинаміки, це зміна приймається з імовірністю

Pr {M → M̕} = Pr {M → M̕} = {1, ΔE≤0 або exp (-ΔE / T), ΔE> 0}

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

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

Алгоритм розв'язання задачі випливає з оригінальної схеми Кохонена. в яку вносяться лише невеликі зміни Використовується мережу, що складається з двох одновимірних шарів нейронів (ті. що містить лише один спай синаптичних ваг). Вхідний шар Відбудеться з трьох нейронів, а s вихідний - з N (по числу міст) Кожен нейрон вхідного шару пов'язаний з кожним вихідним і нейроном Все зв'язку спочатку ініціюються випадковими значеннями Для кожного міста вхідний 3-мірний вектор формується з двох його координат на площині, а третій компонент вектора вдає із себе нормирующий параметр, який вираховується так. щоб все вхідні вектора мали однакову Евклидову довжину і ніякі два вектора не були б колінеарні. Це еквівалентно розгляду двовимірних координат міст, як проекцій тривимірних з вектор се. лежать на сфері Позначимо через wj-мірний вектоp синаптичних зв'язків, 3 зв'язують j-й вихідний нейрон з вхідними нейронами Якщо сi - тривимірний вхідний вектор, який визначає i -й місто, то активація j-го вихідного нейрона при подачі сi на вхід визначається скалярним твором (c jw). Вихідний нейрон, для якого цей твір максимально називається чином міста □ Алгоритм формування маршруту формулюється наступному образам Вибираються значення 1 для параметра посилення а й радіуса взаємодії р Наступний цикл виконується аж 3 до виконання умови α ≤ 0.
1) Вибирається випадковий місто c.

2) Визначається номер образу міста в вихідному шарі - jc.

3) Вектори зв'язків w. з'єднують нейрон ic, і всіх їло 2 r прилеглих сусідів праворуч і ліворуч: j = jc-r, де || x|| - Евклидова норма вектора х. Для усунення кінцевих ефектів шар вихідних нейронів вважається кільцевим, так що N'-й нейрон примикає до першого.

4) Радіус взаємодії поступово зменшується відповідно до деякому правилу {наприклад, спочатку можна покласти г - 0.1 N, потім за перші 10% циклів знизити його до значення 1. яке далі підтримується постійним).

5) Параметр посилення про поступово знижується на невелику величину (наприклад, в експериментах Фавата і Уолкера він лінійно зменшувався до нуля)
Конкретний вид законів зміни радіуса взаємодії і параметра посилення, як правило, не має великого значення

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

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

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

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

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

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

Метод мурашиних колоній
Ентомологи встановили, що мурахи здатні швидко знаходити найкоротший шлях від мурашника до джерела їжі Більш того, вони можуть адаптуватися до умов, що змінюються. знаходячи новий найкоротший шлях Розглянемо Малюнок 5: мурахи рухаються по прямій, що з'єднує мурашник з місцем, в якому знаходиться їжа При русі мураха мітить свій шлях спеціальними речовинами - феромонами, і ця інформація використовується іншими мурахами для вибору шляху А саме, мурахи воліють стежки найбільш збагачені феромонами Це елементарне правило поведінки мурах і визначає їх здатність знаходити нові шляхи, якщо старий виявляється перерізаним перепоною Дійсно, досягнувши цієї перепони, мурахи вже н зможуть продовжити свій шлях і з однаковою ймовірністю будуть обходити її справа і зліва Те ж саме буде відбуватися і на зворотному боці перешкоди. Однак, ті мурахи, які випадково виберуть найкоротший шлях (ліворуч від перешкоди і направо - на зворотному шляху), будуть швидше проходити свій шлях і він з більшою швидкістю стане збагачуватися феромонами Тому такі мурахи будуть віддавати перевагу саме цей н АІ найкоротший шлях, прагнуть посісти його і далі Очевидна позитивний зворотний зв'язок швидко призведе до того, що найкоротший шлях стане єдиним маршрутом руху комах.

Подібний процес може здійснюватися і в комп'ютерному світі населеному Штучними Мурахами (ІМ). Такі мурахи можуть вирішити і наше завдання комівояжера У цьому випадку вони рухаються від міста до міста по ребрах відповідного графа. При цьому спи обирають напрямок руху, використовуючи вірогідну опцію залежно як від попередніх спроб руху по даному ребру, так і від евристичного значення, що є функцією довжини ребра ІМ з більшою ймовірністю будуть надавати перевагу найближчі міста і міста, пов'язані ребрами, найбільш багатими феромонами. Спочатку Λ, штучних мурах розміщуються в випадково обраних містах В кожний наступний момент часу вони переміщаються в сусідні міста і змінюють концентрацію феромона на своєму шляху (локальна модифікація) Після того, як всі ІМ завершать руху по замкнутому маршруту, той з них. який виконав найкоротший шлях, додає до його ланкам кількість феромону, назад пропорційне довжині цього шляху (глобальна модифікація) На відміну від живих мурашок, ІМ мають здатність визначати відстань до сусідніх міст і пам'ятають, які міста вони вже відвідали Виявляється, метод штучних мурашиних колоній може давати результати кращі ніж при використанні імітації відпалу, нейронних мереж, і генетичних алгоритмів.

Розглянемо приклад, представлений на рис. 14. Два мурашки з мурашника повинні дістатися до їжі, яка знаходиться за перешкодою. Під час переміщення кожен мураха виділяє трохи ферменту, використовуючи його в якостi маркера.
За інших рівних кожен мураха вибере свій шлях. Перший мураха вибирає верхній шлях, а другий - нижній. Так як нижній шлях в два рази коротше верхнього, другий мураха досягне мети за час T1. Перший мураха в цей момент пройде тільки половину шляху (рис. 15).Коли один мураха досягає їжі, він бере один з об'єктів і повертається до мурашника тим самим шляхом. За час T2 другий мураха повернувся в мурашник з їжею, а перший мураха досяг їжі (рис. 16).Згадайте, що при переміщенні кожного мурашки на шляху залишається трохи ферменту. Для першого мурашки за час T0-T2 шлях був покритий ферментом тільки один раз. У той же самий час другої мураха покрив шлях ферментом двічі. За час T4 перший мураха повернувся в мурашник, а другий мураха вже встиг ще раз сходити до їжі і повернутися. При цьому концентрація ферменту на нижньому шляху буде в два рази вище, ніж на верхньому. Тому перший мураха наступного разу вибере нижній шлях, оскільки там концентрація ферменту вище.В цьому і полягає базова ідея алгоритму мурахи - оптимізація шляхом непрямої зв'язку між автономними агентами.
Алгоритм мурашки

Детально розглянемо алгоритм мурашки, щоб зрозуміти, як він працює при вирішенні конкретної проблеми.
Граф

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

Мураха - це програмний агент, який є членом великої колонії і використовується для вирішення будь-якої проблеми. Мураха забезпечується набором простих правил, які дозволяють йому вибирати шлях в графі. Він підтримує список табу (tabu list), тобто список вузлів, які він вже відвідав. Таким обра¬зом, мураха повинен проходити через кожний вузол тільки один раз. Шлях між двома вузлами графа, за яким мураха відвідав кожен вузол тільки один раз, називається шляхом Гамільтона (Hamiltonian path), по імені математика сера Вільяма Гамільтона (Sir William Hamilton).

Вузли в списку «поточного подорожі» розташовуються в тому порядку, в кото-ром мураха відвідував їх. Пізніше список використовується для визначення протяжен¬ності шляху між вузлами.

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

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

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

Приклад ітерації

Давайте розберемо функціонування алгоритму на простому прикладі, щоб побачити, як працюють рівняння. Згадайте (рис. 14) простий сценарій з двома мурашками, які вибирають два різних шляхи для досягнення однієї мети. На рис. 18 показаний цей приклад з двома гранями між двома вузлами (V0 і V1). Кожна грань инициализируется і має однакові шанси на те, щоб виграти.

Два мурашки знаходяться в вузлі V0 і позначаються як A0 і A1. Так як ймовірність вибору будь-якого шляху однакова, в цьому циклі ми проіґноруймо рівняння вибору шляху. На рис. 4.6 кожен мураха вибирає свій шлях (мураха A0 йде по верхньому шляху, а мураха А1 - по нижньому).

У таблиці на рис. 19 показано, що мураха А0 зробив 20 кроків, а мураха А1 - тільки 10. Ми розраховуємо кількість ферменту, яке повинно бути «нанесено».

Далі по розраховується кількість ферменту, яке буде застосовано. Для мурашки A0 результат становить:

= 0,1 + (0,5 х 0,6) = 0,4.


Для мурашки A1 результат становить:= 0,1 + (1,0 X 0,6) = 0,7.

Далі за допомогою рівняння визначається, яка частина ферменту випарується і, відповідно, скільки залишиться. Результати (для кожного шляху) складають:

= 0,4 X (1,0 - 0,6) = 0,16

= 0,7 X (1,0 - 0,6) = 0,28.

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

Імовірність того, що мураха вибере верхній шлях (представлений кількістю ферменту 0,16), становить:

(0,16) 3,0 X (0,5) 1,0 / ((0,16) 3,0 X (0,5) 1,0) + ((0,28) 3,0 X (1 , 0) 1,0) = 0,002048 / 0,024 = = P (0,085).

Імовірність того, що мураха вибере нижній шлях (представлений кількістю ферменту 0,28), становить:

(0,28) 3 ° х (1,0) 1,0 / ((0,16) 3 ° х (0,5) 1,0) + ((0,28) 3 ° х (1 , 0) 1,0) = 0,021952 / 0,024 = = P (0,915).

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

приклади запуску

Тепер розглянемо кілька прикладів запуску алгоритму мурахи для завдання комівояжера.

При першому запуску виконується рішення задачі для 30 міст (рис. 20).

Були задані наступні параметри: а = 1,0, в = 5,0, р = 0,5, Q = 100.

При другому запуску виконується рішення задачі для 50 міст (рис. 21).

Для неї були задані ті ж параметри, що і для попередньої.

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

 

Зміна параметрів алгоритму

Марко Дориго (винахідник оптимізації за принципом мурашиної колонії) пропонує дуже цікаву дискусію по параметрам алгоритму в статті «Система мурах: оптимізація за допомогою колонії співпрацюють агентів» (The Ant System: Optimization by a Colony of Cooperating Agents). У цьому розділі розповідається про його пропозиціях щодо змін параметрів алгоритму.

Alpha (а) / Beta (в)

Був відкритий ряд комбінацій а / в, які дозволяють знаходити хороші рішення за невеликий час. Ці комбінації приведені в табл. 1.

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

Rho (р)

Параметр р представляє коефіцієнт, який застосовується до розпорошувати на шляху ферменту, а (1,0 - р) представляє коефіцієнт випаровування для існуючого ферменту. Були проведені тести при р> 0,5, і всі вони показали цікаві результати. При встановленні значення р <0,5 результати були не-задовільними.

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

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

Інші області застосування
Алгоритм мурашки може застосовуватися для вирішення багатьох завдань, таких як розподіл ресурсів і роботи.

При вирішенні задачі розподілу ресурсів (Quadratic Asigment Problem - QAP) необхідно задати групу ресурсів n для ряду адресатів m і при цьому мінімізувати витрати на перерозподіл (тобто функція повинна знайти найкращий спосіб розподілу ресурсів). Виявлено, що алгоритм мурашки дає рішення такого ж якості, як і інші, більш стандартні спо-соби.

Набагато складніше проблема розподілу роботи (Job-shop Sheduling Problem - JSP). У цьому завданні група машин M і завдань J (що складаються з послідовності дій, здійснюваних на машинах) повинні бути розподілені таким чином, щоб всі завдання виконувалися за мінімальний час. Хоча рішення, знайдені за допомогою алгоритму мурахи, не є оптимальними, застосування алгоритму для даної проблеми показує, що з його допомогою можна вирішувати аналогічні завдання.

Алгоритм мурашки застосовується для вирішення інших завдань, наприклад, прокладки маршрутів для автомобілів, розрахунку квітів для графіків і маршрутизації в мережах. Більш докладно способи використання алгоритму мурахи описуються в книзі Марко Дориго «Алгоритми мурашки для абстрактної оптимізації» (Ant Algorithms for Discrete Optimization).

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

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

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

3. Аналіз отриманих результатів показав, що метод штучних мурашиних колоній є оптимальним для вирішення даного класу задач за всіма ключовими показниками.

1. Джонс Т. Програмування Штучного інтелекту в додатках, 2011

2. Єжов А.А., Шумський С.А. Нейрокомпьютинг і його застосування в економіці і бізнесі, 1998..

3. Dorigo M., Gianni D.C., Gambardella L.M. Ant Algorithms for Discrete Optimization. Artificial life, 1999..

4. Вагман М. Процес наукового відкриття для людей і комп'ютерів: теорія і розробка в психології і штучному розумі (Wagman M. Scientific Discovery Processes in Humans and Computers: Theory and Research in Psychology and Artificial Intelligence. Praeger Publishers, 2000).

5. Кепхарт Д. Імунні системи з біологічної мотивацією для комп'ютерів // Роботи четвертого Міжнародного семінару по синтезу і симуляції живих систем (Kephart J. A Biologically Inspired Immune Systems for Computers // in Artificial Life 4: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems. - Cambridge, Mass: MIT Press).

6. S. Baluja, R. Caruana Removing the genetics from the standard genetic algorithm. In A. Prieditis and S. Russell, editors, Proceedings of the Twelfth International Conference on Machine Learning, ML-95, pages 38-46. Palo Alto, CA: Morgan Kaufmann, 1995.

7. C. M. Bishop Neural Networks for Pattern Recognition. Oxford University Press, 1995.

8. H. Bersini, M. Dorigo, S. Langerman, G. Seront, and L. M. Gambardella Results of the first international contest on evolutionary optimisation (1st ICEO). In Proceedings of IEEE International Conference on Evolutionary Computation, IEEE-EC 96, pages 611-615. IEEE Press, 1996..