исследуется сумма входов каждого нейрона. Если она больше порога, выход принимает единичное значение, если меньше - нулевое. На протяжении эпохи выходы нейронов не изменяются.

Рис. 6.4. Четырехбитовый аналого-цифровой преобразователь, использующий сеть Хопфилда

Целью является такой выбор сопротивлений (весов), что непрерывно растущее напряжение X приложенное к одновходовому терминалу, порождает множесство из четырех выходов, представляющих двоичную запись числа, величина которого приближенно равна входному напряжению (рис. 6.5). Определим сначала функцию энергии следующим образом:

E

22j-1OUTj(1-OUTj),(6.7)

где X - входное напряжение.

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

Если уравнение (6.7) перегруппировать и сравнить с уравнением (6.2), то получим следующее выражение для весов:

Wij = -2i+J, yi = 2i,(6.8)

где wij - проводимость (величина, обратная сопротивлению) от выхода нейрона i к входу нейрона j (равная также проводимости от выхода нейрона j к входу нейрона /; yi -проводимость от входа Х к входу нейрона

Чтобы получить схему с приемлемыми значениями сопротивлений и потребляемой мощности, все веса должны быть промасштабированы.

OOT3OOT2OOTfOOT0

110 1-

110 0-

10 11-

л / О 1 о-

10 0 1-

Винарный 1 0 0 0-

6ШР0 0 11/

0 1/0-

0 10 0-

0 0 11-

0 0 10-

0 0 0 1-

0 0 0 0 - -

О 1 Z 5 4 5 6 7 8 9 10 11 11 /3 14 15 Вход, В

Рис. 6.5. Идеальная характеристика четырехбитового аналого-цифрового

преобразователя

Идеальная выходная характеристика, изображенная на рис. 6.5, будет реализована лишь в том случае, если входы устанавливаются в нуль перед выполением преобразования. Если этого не делать, сеть может попасть в локальный минимум энергии и дать неверный выход.

Задача коммивояжера

Задача коммивояжера является оптимизационной задачей, часто возникающей на практике. Она может быть сформулирована следующим образом: для некоторой

группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут с посещением каждого города один раз и с возвращением в исходную точку. Было доказано, что эта задача принадлежит большому множеству задач, называемых «NP-полными» (недетерминистски полиномиальными) [З]. Для NP-полных задач не известно лучшего метода решения, чем полный перебор всех возможных вариантов, и, по мнению большинства математиков, маловероятно, чтобы лучший метод был когда либо найден. Так как такой полный поиск практически неосуществим для большого числа городов, то эвристические методы используются для нахождения приемлемых, хотя и неоптимальных решений.

Описанное в работе [8] решение, основанное на сетях с обратными связями, является типичным в этом отношении. Все же ответ получается так быстро, что в определенных случаях метод может оказаться полезным.

Допустим, что города, которые необходимо посетить, помечены буквами A, B, C и D, а расстояния между парами городов есть dab, dbc и т. д.

Решением является упорядоченное множество из n городов. Задача состоит в отображении его в вычислительную сеть с использованием нейронов в режиме с большой крутизной характеристики (X приближается к бесконечности). Каждый город представлен строкой из n нейронов. Выход одного и только одного нейрона из них равен единице (все остальные равны нулю). Этот равный единице выход нейрона показывает порядковый номер, в котором данный город посещается при обходе. На рис. 6.6 показан случай, когда город C посещается первым, город A - вторым, город D - третьим и город B - четвертым. Для такого представления требуется п2 нейронов -число, которое быстро растет с увеличением числа городов. Длина такого маршрута была бы равна dca + dad + ddb + dbc. Так как каждый город посещается только один раз и в каждый момент посещается лишь один город, то в каждой строке и в каждом столбце имеется по одной единице. Для задачи с п городами всего имеется п! различных маршрутов обхода. Если п = 60, то имеется 6934155х1078 возможных маршрутов. Если принять во внимание, что в нашей галактике (Млечном Пути) имеется лишь 1011 звезд, то станет ясным, что полный перебор всех возможных маршрутов для 1000 городов даже на самом быстром в мире компьютере займет время, сравнимое с геологической эпохой.

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

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