Спосіб маршрутизації в нейронних мережах хопфілда на основі вдосконаленої функції ляпунова

Реферат: Спосіб маршрутизації в нейронних мережах Хопфілда полягає у вирішенні оптимізаційної задачі маршрутизації з використанням вдосконаленої функції Ляпунова. При цьому вводиться додатковий показник, який забезпечує мінімізацію кількості ребер в рішенні щодо маршруту. UA 85701 U (54) СПОСІБ МАРШРУТИЗАЦІЇ В НЕЙРОННИХ МЕРЕЖАХ ХОПФІЛДА НА ОСНОВІ ВДОСКОНАЛЕНОЇ ФУНКЦІЇ ЛЯПУНОВА UA 85701 U UA 85701 U 5 Корисна модель належить до системної інженерії і може бути використана в телекомунікаційних мережах для забезпечення більш якісного вирішення задач маршрутизації. Відомий "Спосіб найбільш короткого розрахунку шляху та напрямку в комп'ютерних мережах", оснований на вирішенні задачі комівояжеру з використанням нейронної мережі зі зворотнім зв'язком (нейронна мережа Хопфілда) [1]. Як функція вирішення оптимізаційної задачі використовується функція Ляпунова, що розраховується за формулою: 2     N 1 2 3  N    cij  ij  2   ij  ij  2    ij    ji  i    2 i1 j1 j1 i 1 j1 i1  j1  j1 j1 j1  j1  N N EPC  10 4 2   ij 1  ij   N N i1 j1 j1 N N 5 2 N N N   ij   ji. i1 j 1 j1 Недоліком відомого способу є те, що вирішення оптимізаційної задачі не може бути використано для телекомунікаційних мереж з великою кількістю вузлів. Найбільш близьким до запропонованого технічного рішення, вибраним як найближчий аналог (прототип), є "Спосіб оптимального напрямку мультипризначення для комунікацій нейронної мережі" [2], який полягає у вирішенні оптимізаційної задачі маршрутизації з використанням вдосконаленої функції Ляпунова, що розраховується за формулою (1): EPKN     N 1 N N    ij   1  c ik   c ij   2   2 2 i1 j1 k 1   j1 k 1  N N   ij  ij  i1 j1 j1 2     N 3 N  N   ij    ji  i   4    2 i1  j1 2 j1   j1 j1   15      ij  1  ij  25 i1 j1 N N j1     N     ,.    ij  ki  k 1 i1 j1  j1 k 1  (1) N N де ,  1 якщо зв' язок між вузлами i та j приймаєучастьв рішенні ij   0,в іншому випадку, ,  1 якщо зв' язку між вузлами i та j неіснує  ij   0,в іншому випадку.  20 25 30 Недоліком способу-прототипу є те, що вирішення оптимізаційної задачі не мінімізує кількість ребер при виробленні рішення, що, в свою чергу, підвищує завантаженість телекомунікаційної мережі. В основу корисної моделі поставлена задача створити спосіб маршрутизації в нейронних мережах Хопфілда на основі вдосконаленої функції Ляпунова, який підвищить ефективність роботи телекомунікаційної мережі. Поставлена задача вирішується за рахунок того, що в спосіб-прототип, який полягає у вирішенні оптимізаційної задачі маршрутизації з використанням вдосконаленої функції Ляпунова, яка розраховується за формулою (1), вводиться додатковий член, який забезпечить мінімізацію кількості ребер в рішенні щодо маршруту. Технічний результат, який може бути отриманий при здійсненні корисної моделі, полягає в зменшенні кількості ребер при мінімізації функції вирішення оптимізаційної задачі на основі врахування функції штрафу за кожне додатково використане ребро. На фіг. 1 наведена структура телекомунікаційної мережі. На фіг. 2 наведені результати вирішення задачі маршрутизації при 6  500 . На фіг. 3 наведені результати вирішення задачі маршрутизації при 6  1000 . 35 На фіг. 4 наведені результати вирішення задачі маршрутизації при 6  250 . На фіг. 5 наведені результати вирішення задачі маршрутизації при використанні вдосконаленої функції Ляпунова. Суть запропонованого способу маршрутизації в нейронних мережах Хопфілда на основі вдосконаленої функції Ляпунова полягає у наступному. Для вирішення оптимізаційної задачі використовується функція Ляпунова: 1 UA 85701 U E  A 2 C B  2     xi  xj  2     xi  yi  2     xi  n    x i ji i x j x   x  i   D    c xy  xi  y,i1   y,i1 , 2 x i yx (2) що дозволяє знаходити замкнутий шлях на грані, довжина якої гарантовано близька або дорівнює мінімальному шляху. Вдосконалення функції Ляпунова (енергія нейронної мережі) приводить до виразу: E  EPKN  6 2 5 N N   ij  hij, i1 j1 j1 (3) де: h ij - елемент матриці штрафів за використання ребра з вузла i в вузол j , 0, якщо i  j  H  hij , прицьомуhij  0, якщо c ij  0  h  0, якщо c  0. ij  ij V   ij При цьому нейронна мережа має N  N нейронів , які відповідають кількості вузлів в мережі. 10 Коефіцієнт 1 і відповідна складова функція (1) визначає мінімізацію вартості пересилки по маршруту з вузла s в вузол d. Складова функція при коефіцієнті  2 забезпечує використання тільки тих зв'язків, що існують. Наприклад, коли деякі ребра в графі відсутні, відповідно коефіцієнт c ij дорівнює 0. В цьому випадку ij дорівнює 1. В свою чергу, це призводить до збільшення функції (4), що не допустимо при рішенні задачі мінімізації:   gi  ij  15 1 1 e  au ij , (4) де  - коефіцієнт, що визначає крутизну активаційної функції. Так при малих значеннях  активаційна функція має пологий склон, а при більших значеннях  активаційна функція наближається до пологої функції;  ij - вихід нейрона нейронної мережі; 20 u ij - ваги зв'язку нейронної мережі. На фізичному ж рівні це визначає, що неможливо використовувати шляхи, яких не існує. Коефіцієнт  3 забезпечує виконання умови збереження потоку в вузлі в відповідності до (5): N N j1 j1 j1 j1  ij    ji  i , (5) при цьому ij  0;1. 25 Коефіцієнт  4 забезпечує виконання умови ij  0;1 і не дозволяє отримувати переваги будь-якому нейрону. Для реалізації процесу пошуку рішення задачі знаходження найкоротшого шляху визначається алгоритм зміни ваги зв'язку в нейронних мережах. Для цього визначається матриця ваги в мережі U  uij . 30 При використанні (3) визначається значення коефіцієнта  6 , який має великий вплив на швидкість збіжності нейронної мережі та якість рішення задачі маршрутизації. 35 Отримані результати стверджують, що коефіцієнт  6 необхідно встановлювати в значення 250, так як при цьому зберігається висока швидкість збіжності та зберігається висока якість рішення задачі пошуку маршруту мінімальної довжини та з найменшою кількістю ребер (фіг. 1, 2, 3, 4). При використанні виразу (3) рішення має місце тільки з 4 та 5 ребрами. При цьому нейронна мережа при знаходженні маршрутів намагається знаходити більше рішень, які мають шляхи меншої довжини з меншою кількістю ребер. 2 UA 85701 U При використанні виразу (3) для рішення задачі пошуку маршрутів мінімальної довжини не отримані рішення, які мають 6 ребер, для 4 та 5 реберних шляхів знаходять ті шляхи, які мають мінімальну довжину (фіг. 5). 5 Джерела інформації: 1. Аli М., Kamoun F. Neural networks for shortest path computation and routing in computer networks/ IEEE Trans, on Neural Networks, vol. 4, no. 6, pp. 941-953,1993. 2. Ahn C.W., Ramakrishna R. S. NeuralNetwork BasedNear-Optimal Routing Algorithm./Proc. of ICONIP, Vol. 4, pp. 1771-1776, 2002. 10 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 15 Спосіб маршрутизації в нейронних мережах Хопфілда, що полягає у вирішенні оптимізаційної задачі маршрутизації з використанням вдосконаленої функції Ляпунова, який відрізняється тим, що вводиться додатковий показник, який забезпечує мінімізацію кількості ребер в рішенні щодо маршруту. 3 UA 85701 U 4 UA 85701 U Комп’ютерна верстка І. Скворцова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5