Розробка програми навчання нейронної мережі на основі таблиць маршрутизації в пакеті Microsoft Excel

Маршрутизатори працюють на мережному рівні моделі OSI: можуть пересилати пакети з однієї мережі до іншої. Для того, щоб надіслати пакети в потрібному напрямку, маршрутизатор використовує таблицю маршрутизації, що зберігається у пам’яті. Таблиця маршрутизації може складатися засобами статичної або динамічної маршрутизації.

Крім того, маршрутизатори можуть здійснювати трансляцію адреси відправника й одержувача (англ. NAT, Network Address Translation), фільтрацію транзитного потоку даних на основі певних правил з метою обмеження доступу, шифрування/дешифрування передаваних даних тощо.

Маршрутизатори не можуть здійснювати передачу широкомовних повідомлень, таких як ARP-запит.

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

Мною  був обраний маршрутизатор Cisco RV016-G5.

Рисунок 13 – Маршрутизатор Cisco RV016-G5.

 

Таблиця 1 – Описання технічних характеристик маршрутизатора.

Виробник	Cisco Inc.
Артикул	RV016-G5
Тип пристрою	Маршрутизатор
Основні специфікації
Порти	16 10/100 портів з роз’ємами RJ-45

Продовження таблиці 1

Типи портів	2 WAN Internet порти 1 DMZ порт 8 LAN портів 5 портів які можуть бути налаштовані як WAN (Internet) або LAN порти.
Стандарти	802.3, 802.3u, IPv4 (RFC 791) RIP версий 1 и 2.
Мережеві протоколи	DHCP сервер, клієнт, агент; статичні IP, PPPoE, PPTP, transparent bridge, DNS relay, DynDNS.
Протоколи маршрутизації	Статична, RIP v1 and v2.
NAT	PAT, NAPT, NAT traversal, one-to-one NAT.
DMZ	Виділений DMZ порт, DMZ хост.
Безпека	Firewall, контроль доступу, переадресація і триггерінг портів, фільтрація контенту и Web-фільтрація
Забезпечення безпеки	HTTPS, доступ по паролю.
VPN	100 IPsec тунелів 50 QuickVPN тунелів для віддаленого клієнтського доступу 10 PPTP тунелів для віддаленого доступу
Шифрування	DES, 3DES AES: AES-128, AES-192, AES-256.
Автентифікація	MD5, SHA1
Пропускна здатність	200 Мбіт/с (NAT) 97 Мбіт/с (IPsec VPN)
Керування	Web браузер, SNMP v1 і 2, Bonjour.
Фізичні характеристики
Живлення	100~240 В змінного току, 50~60 Гц.
Габарити	279 x 44 x 241 мм
Температурні режими	робочий: от 0° до 40°C збереження: от 0 ° до 70°C
Вологість	робочий: 10 - 85% збереження: 5 - 90 %

 

2 РОЗРАХУНОК  ОПТИМАЛЬНОГО МАРШРУТУ

2.1 Матричний  алгоритм пошуку найменших шляхів

Матричний метод визначення найкоротших шляхів дозволяє знайти довжини (ранги) найкоротших шляхів між всіма вершинами графа одночасно, ґрунтується на застосуванні алгебраїчних операцій над матрицею довжин L (матрицею рангів R).

Нехай задана мережа комп’ютерного  зв’язку у вигляді графа, зображеного на рисунку 14, числа біля ребер якого відповідають довжинам гілок (ліній) мережі. Тоді матриця довжин L буде мати вигляд показаний в таблиці 2.

Таблиця 2 – Матриця довжин.

 

Власне кажучи, матриця L – це матриця відстаней безпосередніх зв’язків, тобто шляхів першого рангу. Позначимо матрицю . Зведемо матрицю у квадрат: . Елемент матриці визначається за правилом:

(5)

Інтерпретуючи тепер  множення як послідовне, а додавання – як паралельне з’єднання гілок (за аналогією зі зведенням структурної матриці В у ступінь), легко зрозуміти, що добуток відповідає двохтранзитному шляху (шляху другого рангу), що проходить із вершини і у вершину j через проміжну вершину k (рисунок 15, а), а сума, наприклад, чотирьох добутків – чотирьом двохтранзитним шляхам (рисунок 15, б):

(6)

Помітимо, що добутки фактично відповідають однотранзитним шляхам (тобто шляхам першого рангу, що включають тільки одну гілку).

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

При наявності декількох  паралельних одно- і двохтранзитних шляхів (див. рисунок 14, б) для визначення довжини найкоротшого шляху необхідно операцію додавання у вираженні (5) замінити на операцію вибору мінімуму з довжин усіх одно- і двохтранзитних шляхів, тобто замість (5) будемо мати:

  (7)

 

Рисунок 14 – Граф мережі комп’ютерного зв’язку.

Рисунок 15 – а) двохтранзитний шлях; б) чотири двохтранзитних шляхи.

Таким чином, елемент  матриці дорівнює довжині шляху з і в j, найкоротшого серед всіх одно- і двохтранзитних шляхів.

При зведенні матриці у ступінь q при використанні операції (7) одержимо елемент якої (для ) визначає довжину найкоротшого шляху між вершинами i і j серед усіх шляхів першого, другого, q-го рангу.

Зведення матриці  у ступінь максимального рангу приводить до одержання матриці найкоротших по довжині шляхів між всіма парами вершин графа, або матриці оптимальних шляхів Якщо при зведенні матриці у деякий ступінь q виявиться, що

(8)

процес  обчислень варто припинити, тому що при рівності (8) завжди виконується рівність .

Таким чином,

Таблиця 3 – обчислення матриці :

#	1	2	3	4	5
1	0
2		0
3			0
4				0
5					0

 

Тому що й показник ступеня «2» < , процес обчислення

 необхідно продовжити, обчисливши .

Таблиця 4 – Обчислення матриці :

#	1	2	3	4	5
1	0
2		0
3			0
4				0
5					0

 

З порівняння й видно, що . Таким чином, . Матрицю називають також дистанційною й позначають .

 

2.2 Програма  роботи алгоритму в Microsoft Excel

Microsoft Excel (повна назва Microsoft Office Excel) – програма для роботи з електронними таблицями, створена корпорацією Microsoft для Microsoft Windows, Windows NT і Mac OS. Программа входить до складу офісного пакету Microsoft Office. Вона надає можливості економіко-статистичних розрахунків, графічні інструменти і, за винятком Excel 2008 під Mac OS X, мова макропрограмування VBA (Visual Basic для додатків). Microsoft Excel входить до складу Microsoft Office і на сьогоднішній день Excel є одним з найбільш популярних додатків в світі.

 

 

Рисунок 16 – Загальний вигляд роботи програми в Microsoft Excel.

 

 

 

 

3 РОЗРОБКА  НЕЙРОМЕРЕЖНОГО АЛГОРИТМУ

3.1 Основні  характеристики штучних нейронних  мереж

Штучні нейронні мережі (ШНМ) – математичні моделі, а також їхня програмна та апаратна реалізація, побудовані за принципом функціонування біологічних нейронних мереж – мереж нервових клітин живого організму. Системи, архітектура і принцип дії базується на аналогії з мозком живих істот. Ключовим елементом цих систем виступає штучний нейрон як імітаційна модель нервової клітини мозку – біологічного нейрона. Цей термін виник при вивченні процесів, які відбуваються в мозку, та при спробі змоделювати ці процеси. Першою такою спробою були нейронні мережі Маккалока і Піттса. Як наслідок, після розробки алгоритмів навчання, отримані моделі стали використовуватися в практичних цілях: в задачах прогнозування, для розпізнавання образів, в задачах керування та інші.

ШНМ представляють собою систему з’єднаних і взаємодіючих між собою простих процесорів (штучних нейронів). Такі процесори зазвичай достатньо прості, особливо в порівнянні з процесорами, що використовуються в персональних комп’ютерах. Кожен процесор схожої мережі має справу тільки з сигналами, які він періодично отримує, і сигналами, які він періодично посилає іншим процесорам. І тим не менш, будучи з’єднаними в досить велику мережу з керованою взаємодією, такі локально прості процесори разом здатні виконувати достатньо складні завдання. З точки зору машинного навчання, нейронна мережа являє собою окремий випадок методів розпізнавання образів, дискримінантного аналізу, методів кластеризації тощо З математичної точки зору, навчання нейронних мереж – це багатопараметрична задача нелінійної оптимізації. З точки зору кібернетики, нейронна мережа використовується в задачах адаптивного управління і як алгоритми для робототехніки. З точки зору розвитку обчислювальної техніки та програмування, нейронна мережа – спосіб вирішення проблеми ефективного паралелізму. А з точки зору штучного інтелекту, ШНМ є основою філософської течії коннективізму і основним напрямком в структурному підході з вивчення можливості побудови (моделювання) природного інтелекту за допомогою комп’ютерних алгоритмів. Нейронні мережі не програмуються в звичайному розумінні цього слова, вони навчаються. Можливість навчання – одна з головних переваг нейронних мереж перед традиційними алгоритмами. Технічно навчання полягає в знаходженні коефіцієнтів зв’язків між нейронами. У процесі навчання нейронна мережа здатна виявляти складні залежності між вхідними даними і вихідними, а також виконувати узагальнення. Це означає, що у разі успішного навчання мережа зможе повернути вірний результат на підставі даних, які були відсутні в навчальній вибірці, а також неповних та/або «зашумленних», частково перекручених даних.

Рисунок 17 – Схема простої нейронної мережі. Зеленим кольором позначенні вхідні нейрони, голубим приховані нейрони, жовтим  – вихідний нейрон.

Біологічна нейронна мережа складається з групи або  декількох груп хімічно або функціонально пов’язаних нейронів. Один нейрон може бути пов’язаний з багатьма іншими нейронами, а загальна кількість нейронів та зв’язків між ними може бути дуже великою. Зв’язки, які називаються синапсами, як правило формуються від аксонів до дендритів, хоча дендро-дендритичні мікросхем та інші зв'язки є можливими. Крім електричної передачі сигналів, також є інші форми передачі, які виникають з нейротрансмітерної (хімічний передавач імпульсів між нервовими клітинами) дифузії, і мають вплив на електричну передачу сигналів. Таким чином, нейронні мережі є надзвичайно складними.

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

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

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

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

– перша – зрозуміти функціонування нервової системи людини на рівні фізіології і психології;

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

Перший крок був зроблений  у 1943 р. з появою статті нейрофізіолога Уоррена Маккалоха (Warren McCulloch) і математика Волтера Піттса (Walter Pitts) про роботу штучних нейронів і представлення моделі нейронної мережі на електричних схемах.

У 1950-ті – 1960-ті роки група дослідників, об’єднавши ці біологічні і фізіологічні підходи, створила перші штучні нейронні мережі. В 1950-х рр. з’являються програмні моделі штучних нейромереж. Перші роботи провів Натаніел Рочестер (Nathanial Rochester) з дослідної лабораторії IBM. І хоча пізніші реалізації були успішними, його модель зазнала невдачі, оскільки бурхливе зростання традиційних обчислень залишило нейронні дослідження в тіні.

Перші успіхи викликали  вибух активності й оптимізму. Мінскі, Розенблат, Відроу і інші розробили мережі, що складалися з одного прошарку штучних нейронів, які назвали перцептронами. Ці мережі застосовували для розв’язання широкого класу задач: прогноз погоди, аналіз електрокардіограм, штучний зір.