Цифрові пристрої зі зворотним зв"язком

РЕФЕРАТ на тему:

" Цифрові пристрої зі зворотним зв’язком" .

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

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

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

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

На рис. 1 показана мережа із зворотними зв’язками, що складається з двох прошарків. Спосіб представлення дещо відрізняється від використаного в роботі Хопфілда і іншого, але еквівалентний йому з функціональної точки зору, а також добре пов’язаний з мережами, розглянутими в попередніх розділах. Нульовий прошарок, як і на попередніх рисунках, не виконує обчислювальної функції, а лише розподіляє виходи мережі зворотно на входи. Кожний нейрон першого прошарку обчислює зважену суму своїх входів, даючи сигнал NET, який за допомогою нелінійної функції F перетворюється в сигнал OUT. Ці операції схожі з нейронами інших мереж.

Бінарні системи

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

(1).

OUTі = 1, якщо NETj>Тj,.

OUTі = 0, якщо NETj<Тj,.

OUT не змінюється, якщо NETj = Тj,.

Рис. 1. Одношарова мережа із зворотними зв’язками. Пунктирні лінії означають нульові ваги Стан мережі - це просто множина поточних значень сигналів OUT від всіх нейронів. У первинній мережі Хопфілда стан кожного нейрона змінювався в дискретні випадкові моменти часу, в подальшій роботі стани нейронів могли змінюватись одночасно. Оскільки виходом бінарного нейрона може бути тільки нуль або одиниця (проміжних рівнів немає), то поточний стан мережі є двійковим числом, кожний біт якого є сигналом OUT деякого нейрона.

2. Аналогово-цифровий перетворювач

У недавніх роботах розглядалася електрична схема, заснована на мережі із зворотним зв’язком, що реалізує чотирибітовий аналогово-цифровий перетворювач. На рис. 2 показана блок-схема цього пристрою з підсилювачами, що виконують роль штучних нейронів. Опори, що виконують роль ваги, з'єднують вихід кожного нейрона з входами всіх інших. Щоб задовольнити умові стійкості, вихід нейрона не сполучався опором з його власним входом, а ваги бралися симетричними, тобто опір від виходу нейрона i до входу нейрона j мало ту ж величину, що і опір від виходу нейрона j до входу нейрона i.

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

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

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

РИС. 2. Чотирибітовий аналогово-цифровий перетворювач, що використовує мережу Хопфілда Метою є такою вибір опорів (ваг), що безперервне зростаюче напруження X, до одновходового термінала, породжує множину з чотирьох виходів, що представляють двійковий запис числа, величина якого приблизно рівна вхідній напрузі (рис. 3). Визначимо спочатку функцію енергії таким чином:

(2).

де X — вхідна напруга.

Коли Е мінімізоване, то виходять потрібні виходи. Перший вираз в дужках мінімізується, коли двійкове число, утворене виходами, найбільш близько (в середньоквадратичному значенні) до аналогової величини входу X. Другий вираз в дужках звертається в нуль, коли всі виходи рівні 1 або 0, тим самим накладаючи обмеження, що виходи приймають тільки двійкові значення.

Якщо рівняння (2) перегрупувати, тоді отримаємо наступний вираз для ваги:

Wij = -2i+j, yi = 2i,(3).

де wij — провідність (величина, зворотна опору) від виходу нейрона i до входу нейрона j (рівна також провідність від виходу нейрона j до входу нейрона i-yi — провідність від входу Х до входу нейрона i.

Щоб отримати схему з прийнятними значеннями опорів і споживаної потужності, все ваги повинні бути промасштабовані.

Рис. 3 Ідеальна характеристика чотирибітового аналогово-цифрового перетворювача.

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

Задача комівояжера є оптимізаційною задачею, що часто виникає на практиці. Вона може бути сформульована таким чином: для деякої групи міст із заданими відстанями між ними потрібно знайти найкоротший маршрут з відвідуванням кожного міста один раз і з поверненням в початкову точку. Було доведено, що ця задача належить великої множини задач, званих «NP-повними» (недетерміновано поліноміальними). Для NP-повних задач не відомо кращого методу рішення, ніж повний перебір всіх можливих варіантів, і, на думку більшості математиків, малоймовірно, щоб кращий метод був колись знайдений. Оскільки такий повний пошук практично нездійсненний для великого числа міст, то евристичні методи використовуються для знаходження прийнятних, хоч і неоптимальних рішень.

Описане в роботі рішення, засноване на мережах із зворотними зв’язками, є типовим в цьому відношенні. Все ж відповідь виходить так швидко, що в певних випадках метод може виявитися корисним.

Допустимо, що міста, які необхідно відвідати, помічені буквами А, В, С і D, а відстані між парами міст є dab, dbc і т.д.

Рішенням є впорядкована множина з n міст. Задача складається у відображенні його в обчислювальну мережу з використанням нейронів в режимі з великою крутизною характеристики (наближається до нескінченності). Кожне місто представлене рядком з n нейронів. Вихід одного і тільки одного нейрона з них рівний одиниці (всі інші рівні нулю). Цей рівний одиниці вихід нейрона показує порядковий номер, в якому дане місто відвідується при обході. На рис. 6.6 показаний випадок, коли місто С відвідується першим, місто, А — другим, місто D — третім і місто В — четвертим. Для такого представлення потрібно n2 нейронів — число, яке швидко росте із збільшенням числа міст. Довжина такого маршруту була б рівна dca + dad + ddb + dbc. Оскільки кожне місто відвідується тільки один раз і в кожний момент відвідується лише одне місто, то в кожному рядку і в кожному стовпці є по одній одиниці. Для задачі з n містами всього є n! різних маршрутів обходу. Якщо n = 60, то є 6 934 155×1078 можливих маршрутів. Якщо брати до уваги, що в нашій галактиці (Чумацькому Шляху) є лише 1011 зірок, то стане ясним, що повний перебір всіх можливих маршрутів для 1000 міст навіть на самому швидкому в світі комп’ютері займе час, порівнянний з геологічною епохою.

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

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

Перша вимога задовольняється введенням наступної, що складається з трьох сум, функції енергії:

(4).

де А, В і С — деякі константи. Цим досягається виконання наступних умов:

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

2. 2.Друга потрійна сума рівна нулю в тому і тільки в тому випадку, якщо кожний стовпець (порядковий номер відвідування) містить не більше однієї одиниці.

3. 3.Третя сума рівна нулю в тому і тільки в тому випадку, якщо матриця містить рівне n одиниць.

Рис. 4. Маршрут комівояжера Друга вимога — перевага коротким маршрутам — задовольняється за допомогою додавання наступного члена до функції енергії:

(5).

Помітимо, що цей член являє собою довжину будь-якого припустимого маршруту. Для зручності індекси визначаються по модулі n, тобто OUTn+j = OUTj, a D — деяка константа.

При досить великих значеннях A, B і C низькоенергетичні стани будуть представляти припустимі маршрути, а великі значення D гарантують, що буде знайдений короткий маршрут.

Тепер задамо значення ваг, тобто встановимо відповідність між членами у функції енергії і членами загальної форми).

Одержуємо.

wxi, yi =.

— Adxy (1 — dij) (не допускає більш однієї одиниці в рядку).

— B dij (1 — dxy) (не допускає більш однієї одиниці в стовпці).

— С (глобальне обмеження).

— Ddxy (dj, i+1 + dj,і-1) (член, відповідальний за довжину циклу),.

де dij = 1, якщо i = j, у противному випадку dij = 0. Крім того, кожен нейрон має зміщену вагу хі, з'єднаний з +1 і рівний Сn.

У роботі [8] повідомляється про експеримент, у якому задача комівояжера була вирішена для 10 міст. У цьому випадку збуджуюча функція дорівнює.

OUT = Ѕ [1 + th (NET/U0)].

Як показали результати, 16 з 20 прогонів зійшлися до припустимого маршруту і близько 50% рішень виявилися найкоротшими маршрутами, як це було встановлено за допомогою повного перебору. Цей результат стане більш вражаючим, якщо усвідомити, що є 181 440 припустимих маршрутів.

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

Висновки

Мережі зі зворотними зв’язками є перспективним об'єктом для подальших досліджень. Їх динамічна поведінка відкриває нові цікаві можливості і ставить специфічні проблеми. Як відзначається в розділі 9, ці можливості і проблеми зберігаються при реалізації нейронних мереж у виді оптичних систем.