Зростаючі нейронні мережі
Запропонована ними модель відноситься до класу зростаючих нейронних мереж. Такі мережі по-своєму вирішують задачу адаптації своєї структури до вимог розв'язуваної задачі. Згадаймо багатошарові персептрони, для яких кількості прихованих шарів і нейронів у них часто вибираються методом проб і помилок. Як вже зазначалося в зв'язку з цим, є два підходи до адаптивного вибору архітектури нейромереж. У першому підході явно надлишкова нейросеть проріджується до потрібного ступеня складності. Зростаючі мережі, навпаки, стартують з дуже простих і невеликих структур, які розростаються і ускладнюються в міру необхідності.
Фрітцке і Вільке розробили цілий клас систем, що самоорганізуються (і тих, хто навчається з учителем) мереж зі змінною структурою, такі як Зростаючі Клітинні Структури, Зростаючий Нейронний Газ і Зростаючі Сітки. Перші і були використані ними для вирішення завдання комівояжера (і інших задач комбінаторної оптимізації).
Зростаюча клітинна структура для завдання комівояжера представляє з себе спочатку кільце з трьох осередків нейронів. Кожен нейрон характеризується двовимірним вектором, що визначає його положення на площині. Кожному нейрону в кільці приписується також своя величина похибки, яка спочатку покладається рівною нулю. Подальша послідовність дій включає дві наступні основні елементарні операції: зміщення і додавання нового нейрона. Зсув (див. Рисунок 6.2)
- вибирається випадковий місто
- визначається нейрон-переможець, найближчий до цього міста
- становище нейрона і його двох найближчих в кільці сусідів зміщується в бік міста на певну частку відстані до нього.
Ці операції дуже близькі до використовуваних в моделі Кохонена. Різниця полягає в тому, що в останній радіус, в якому визначається сусідство і параметр адаптації зменшуються з часом.
Мал. 6.2. Процедура зсуву переміщує нейрон-переможець і його найближчих сусідів в сторону випадково обраного міста
Додавання нового нейрона.
Згодом після декількох циклів зсувів накопичується інформація, на підставі якої приймається рішення про місце, в якому повинен бути доданий новий нейрон. Кожен раз, коли для випадково вибраного міста визначається найближчий до нього нейрон, локальна помилка для останнього бере зріст. Велике значення цієї помилки служить вказівкою на те, що відповідний нейрон лежить в області, де відношення (число нейронів) / (число міст) невелика. Саме в таких областях слід додавати нові нейрони, оскільки для отримання правильного осмисленого маршруту біля кожного міста повинен перебувати свій найближчий нейрон. Маршрут і визначається шляхом переходу вздовж кільця до нейрона, що є найближчим до деякого місту. Алгоритм пошуку оптимального маршруту, який використовує дві описані операції, формулюється в такий спосіб
- Ініціалізація: генерується кільцева структура, що складається з трьох нейронів, що мають випадкове положення на площині.
- Здійснюється фіксоване число кроків поширення. На кожному кроці перераховується значення локальної помилки.
- Визначається "найгірше" ланка в кільці, що зв'язує два нейрона і, для яких сума максимально. Новий нейрон вставляється в середину ланки зв'язує нейрони і, і його помилка инициализируется величиною. У той же час значення помилок для нейронів і зменшується таким чином, щоб сумарна помилка збереглася:,
- Якщо для будь-яких двох міст найближчі до них нейрони різні між собою, то маршрут знайдений. В протилежному випадку повертаємося до кроку 1.
Очевидно, що рішення задачі може бути знайдено не раніше того, як число нейронів в кільці досягне числа міст. Насправді для його досягнення потрібно мережу з нейронами. Виходячи з цього емпіричного спостереження, згідно з яким число ітерацій має порядок, можна оцінити загальну складність алгоритму. На кроці 1 потрібно інспекція всіх нейронів для пошуку найближчого до даного місту. Вона проводиться раз і, оскільки це число постійно, повне число інспекцій також має порядок. На кроці 2 необхідно перевірити кожну ланку ланцюга, щоб знайти те, якому відповідає максимальна сумарна помилка кінцевих нейронів. Оскільки число ланок дорівнює числу нейронів, то число дій знову має порядок. На кроці 3 для кожного міста необхідно знайти найближчий нейрон, що, як мінімум, вимагає дій. Таким чином, так як кроки 1-3 вимагають щонайменше операцій, а цикл повторюється раз, то тимчасова складність алгоритму як мінімум дорівнює. Просторова складність алгоритму становить, так як необхідно резервувати пам'ять для міст, нейронів і деяких локальних змінних.
Для поліпшення квадратичної тимчасової складності описаного алгоритму Фрітцке і Вільке модифікували кроки 1-3. Вони врахували, що згідно чисельним експериментам спочатку кільцева структура нейронів швидко розподіляється по всій області розміщення міст, і потім з ростом числа нейронів зміни набувають локальний характер. Така поведінка наштовхнуло їх на ідею замінити глобальний пошук нейрона-переможця на кроці 1 наближеною локальної процедурою. А саме: для кожного міста запам'ятовується той нейрон, який найбільш часто опинявся до нього найближчим, і якщо місто обраний знову, то пошук найближчого до нього нейрона обмежується цим нейроном і його найближчими по кільцю сусідами аж до порядку k. Оскільки k є константа, то складність пошуку виявляється в цьому випадку.
Мал. 6.3. Локальний пошук найкращого нейрона: -попередні нейрон; найближчі його сусіди аж до 2 порядку є кандидатами в переможці на наступному кроці
Для усунення на етапі 2 лінійного пошуку ланки з максимальною помилкою використовується той факт, що таким ланкою є те, що пов'язує нейрони, часто стають побідиту.
Третій крок теж можна модифікувати: якщо деякий нейрон кілька разів виявляється найближчим для даного міста, значить для цього міста структура кільця вже стабілізувалася і нейрон "приклеюється" до даного пункту маршруту. Це означає, що він поєднується зі своїм містом і більше вже не рухається. Місто ж віддаляється зі списку міст, що розігруються на етапі розподілу. Коли цей список стає порожнім процес пошуку маршруту закінчується.
Таким чином, кожен крок в циклі тепер вимагає постійне число операцій і тимчасова складність всього алгоритму стає порядку.
Описаний ефективний нейросетевой підхід (FLEXMAP) був протестований на різних розподілах міст числом до 200 і незмінно знаходив маршрути, що відрізняються не більше ніж на 9% від оптимального.