Смекни!
smekni.com

Нейрокомпьютерные системы (стр. 17 из 32)

Ek=NETk - qk ,

где NETk - выход NET нейрона k, qk - порог нейрона k, и

pk = 1/ [1 + ехр(-dEk/ T)],

(отметьте вероятностную функцию Больцмана в знаменате­ле), где Т - искусственная температура. В стадии функционирования искусственной температу­ре Т приписывается большое значение, нейроны устанавли­ваются в начальном состоянии, определяемом входным вектором, и сети предоставляется возможность искать минимум энергии в соответствии с нижеследующей процеду­рой:

1. Приписать состоянию каждого нейрона с вероят­ностью р значение единица, а с вероятностью 1 – рk - нуль.

2. Постепенно уменьшать искусственную температуру и повторять шаг 1, пока не будет достигнуто равновесие.

Обобщенные сети

Принцип машины Больцмана может быть перенесен на сети практически любой конфигурации, хотя устойчивость не гарантируется. Для этого достаточно выбрать одно множество нейронов в качестве входов и другое множество в качестве выходов. Затем придать входному множеству значения входного вектора и предоставить сети возмож­ность релаксировать в соответствии с описанными выше правилами 1 и 2. Процедура обучения для такой сети, описанная в [5], состоит из следующих шагов: 1. Вычислить закрепленные вероятности.

а) придать входным и выходным нейронам значения обучающего вектора;

б) предоставить сети возможность искать равнове­сие;

в) записать выходные значения для всех нейронов;

г) повторить шаги от а до в для всех обучающих векторов;

д) вычислить вероятность Р+ij, т.е. по всему мно­жеству обучающих векторов вычислить вероятность того, что значения обоих нейронов равны единице.

2. Вычислить незакрепленные вероятности.

а) предоставить сети возможность «свободного дви­жения» без закрепления входов или выходов, начав со случайного состояния;

б) повторить шаг 2а много раз, регистрируя значе­ния всех нейронов;

в) вычислить вероятность Р-ij, т.е. вероятность того, что значения обоих нейронов равны единице.

3. Скорректировать веса сети следующим образом:

dwij = h [ P+ij – P-ij ] ,

где dwij. - изменение веса wij, h - коэффициент скорости обучения.

ПРИЛОЖЕНИЯ

Аналого-цифровой преобразователь.

В недавних работах [8,10] рассматривалась электри­ческая схема, основанная на сети с обратной связью, реализующая четырехбитовый аналого-цифровой преобразо­ватель. На рис. 6.4 показана блок-схема этого устройст­ва с усилителями, выполняющими роль искусственных ней­ронов. Сопротивления, выполняющие роль весов, соединяют выход каждого нейрона с входами всех остальных. Чтобы удовлетворить условию устойчивости, выход нейрона не соединялся сопротивлением с его собственным входом, а веса брались симметричными, т.е. сопротивление от выхо­да нейрона i к входу нейрона j имело ту же величину, что и сопротивление от выхода нейрона j к входу нейрона i. Заметим, что усилители имеют прямой и инвертиро­ванный выходы. Это позволяет с помощью обычных положи­тельных сопротивлений реализовывать и те случаи, когда веса должны быть отрицательными. На рис. 6.4 показаны все возможные сопротивления, при этом никогда не возни­кает необходимости присоединять как прямой, так и ин­вертированный выходы нейрона к входу другого нейрона. В реальной системе каждый усилитель обладает ко­нечным входным сопротивлением и входной емкостью, что должно учитываться при расчете динамической характерис­тики. Для устойчивости сети не требуется равенства этих параметров для всех усилителей и их симметричности. Так как эти параметры влияют лишь на время получения реше­ния, а не на само решение, для упрощения анализа они исключены. Предполагается, что используется пороговая функция (предел сигмоидальной функции при X, стремящемся к бесконечности). Далее, все выходы изменяются в начале дискретных интервалов времени, называемых эпохами. В начале каждой эпохи исследуется сумма входов каждого нейрона. Если она больше порога, выход принимает единичное значение, если меньше - нулевое. На протяжении эпохи выходы нейронов не изменяются.

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

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

(6.7)

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

wij=-2i+j, yi=2i

где wij - проводимость (величина, обратная сопротивле­нию) от выхода нейрона i к входу нейрона j (равная также проводимости от выхода нейрона j к входу нейрона 0); ij. - проводимость от входа Х к входу нейрона i. Чтобы получить схему с приемлемыми значениями сопротивлений и потребляемой мощности, все веса должны быть промасштабированы.

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

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

Задача коммивояжера является оптимизационной зада­чей, часто возникающей на практике. Она может быть сформулирована следующим образом: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут с посещением каждого города один раз и с возвращением в исходную точку. Было дока­зано, что эта задача принадлежит большому множеству задач, называемых «NP-полными» (недетерминистски поли­номиальными) [3]. Для NP-полных задач не известно луч­шего метода решения, чем полный перебор всех возможных вариантов, и, по мнению большинства математиков, мало­вероятно, чтобы лучший метод был когда либо найден. Так как такой полный поиск практически неосуществим для большого числа городов, то эвристические методы исполь­зуются для нахождения приемлемых, хотя и неоптимальных решений. Описанное в работе [8] решение, основанное на сетях с обратными связями, является типичным в этом отношении. Все же ответ получается так быстро, что в определенных случаях метод может оказаться полезным. Допустим, что города, которые необходимо посетить, помечены буквами А, В, С и D, а расстояния между парами городов есть dab, dbc и т.д. Решением является упорядоченное множество из n городов. Задача состоит в отображении его в вычисли­тельную сеть с использованием нейронов в режиме с боль­шой крутизной характеристики (l приближается к бесконе­чности). Каждый город представлен строкой из n нейро­нов. Выход одного и только одного нейрона из них равен единице (все остальные равны нулю). Этот равный единице выход нейрона показывает порядковый номер, в котором данный город посещается при обходе. На рис. 6.6 показан случай, когда город С посещается первым, город А - вторым, город D - третьим и город В - четвертым. Для такого представления требуется n2 нейронов - число, которое быстро растет с увеличением числа городов. Длина такого маршрута была бы равна dca + dad + ddb + dbc. Так как каждый город посещается только один раз и в каждый момент посещается лишь один город, то в каждой строке и в каждом столбце имеется по одной единице. Для задачи с п городами всего имеется п! различных маршрутов обхода. Если п = 60, то имеется 69 34155 х 1078 возможных маршрутов. Если принять во внимание, что в нашей галактике (Млечном Пути) имеете) лишь 1011 звезд, то станет ясным, что полный перебор всех возможных маршрутов для 1000 городов даже и. самом быстром в мире компьютере займет время, сравнимо с геологической эпохой. Продемонстрируем теперь, как сконструировать сет: для решения этой NP-полной проблемы. Каждый нейрон снабжен двумя индексами, которые соответствуют городу порядковому номеру его посещения в маршруте. Например OUTxj = 1 показывает, что город х был j-ым по порядку j - ым городом маршрута.

функция энергии должна удовлетворять двум требованиям: во-первых, должна быть малой только для тех решений, которые имеют по одной единице в каждой строке и каждом столбце; во-вторых, должна оказывать предпочтение решениям с короткой длиной маршрута. Первое требование удовлетворяется введением следующей, состоящей из трех сумм, функции энергии:

(6.9)

где А, В и С- некоторые константы. Этим достигается выполнение следующих условий:

1. Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы.