NEURONET (Нейрокомпьютерные системы), страница 12
Описание файла
Документ из архива "Нейрокомпьютерные системы", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "NEURONET"
Текст 12 страницы из документа "NEURONET"
Металл отжигают, нагревая его до температуры, превышающей точку его плавления, а затем давая ему медленно остыть. При высоких температурах атомы, обладая высокими энергиями и свободой перемещения, случайным образом принимают все возможные конфигурации. При постепенном снижении температуры энергии атомов уменьшаются, и система в целом стремится принять конфигурацию с минимальной энергией. Когда охлаждение завершено, достигается состояние глобального минимума энергии.
Рис 6.3. Линии энергетических уровней.
При фиксированной температуре распределение энергий системы определяется вероятностным фактором Больцмана.
ехр(-E / kT),
где Е - энергия системы; k - постоянная Больцмана; Т -температура. Отсюда можно видеть, что имеется конечная вероятность того, что система обладает высокой энергией даже при низких температурах. Сходным образом имеется небольшая, но вычисляемая вероятность, что чайник с водой на огне замерзнет, прежде чем закипеть. Статистическое распределение энергий позволяет системе выходить из локальных минимумов энергии. В то же время вероятность высокоэнергетических состояний быстро уменьшается со снижением температуры. Следовательно, при низких температурах имеется сильная тенденция занять низкоэнергетическое состояние.
Статистические сети Хопфилда
Если правила изменения состояний для бинарной сети Хопфилда заданы статистически, а не детерминировано, как в уравнении (6.1), то возникает система, имитирующая отжиг. Для ее реализации вводится вероятность изменения веса как функция от величины, на которую выход нейрона OUT превышает его порог. Пусть
Ek=NETk - k ,
где NETk - выход NET нейрона k, k - порог нейрона k, и
pk = 1/ [1 + ехр(-Ek/ T)],
(отметьте вероятностную функцию Больцмана в знаменателе), где Т - искусственная температура. В стадии функционирования искусственной температуре Т приписывается большое значение, нейроны устанавливаются в начальном состоянии, определяемом входным вектором, и сети предоставляется возможность искать минимум энергии в соответствии с нижеследующей процедурой:
1. Приписать состоянию каждого нейрона с вероятностью р значение единица, а с вероятностью 1 – рk - нуль.
2. Постепенно уменьшать искусственную температуру и повторять шаг 1, пока не будет достигнуто равновесие.
Обобщенные сети
Принцип машины Больцмана может быть перенесен на сети практически любой конфигурации, хотя устойчивость не гарантируется. Для этого достаточно выбрать одно множество нейронов в качестве входов и другое множество в качестве выходов. Затем придать входному множеству значения входного вектора и предоставить сети возможность релаксировать в соответствии с описанными выше правилами 1 и 2. Процедура обучения для такой сети, описанная в [5], состоит из следующих шагов: 1. Вычислить закрепленные вероятности.
а) придать входным и выходным нейронам значения обучающего вектора;
б) предоставить сети возможность искать равновесие;
в) записать выходные значения для всех нейронов;
г) повторить шаги от а до в для всех обучающих векторов;
д) вычислить вероятность Р+ij, т.е. по всему множеству обучающих векторов вычислить вероятность того, что значения обоих нейронов равны единице.
2. Вычислить незакрепленные вероятности.
а) предоставить сети возможность «свободного движения» без закрепления входов или выходов, начав со случайного состояния;
б) повторить шаг 2а много раз, регистрируя значения всех нейронов;
в) вычислить вероятность Р-ij, т.е. вероятность того, что значения обоих нейронов равны единице.
3. Скорректировать веса сети следующим образом:
wij = [ P+ij – P-ij ] ,
где wij. - изменение веса wij, - коэффициент скорости обучения.
ПРИЛОЖЕНИЯ
Аналого-цифровой преобразователь.
В недавних работах [8,10] рассматривалась электрическая схема, основанная на сети с обратной связью, реализующая четырехбитовый аналого-цифровой преобразователь. На рис. 6.4 показана блок-схема этого устройства с усилителями, выполняющими роль искусственных нейронов. Сопротивления, выполняющие роль весов, соединяют выход каждого нейрона с входами всех остальных. Чтобы удовлетворить условию устойчивости, выход нейрона не соединялся сопротивлением с его собственным входом, а веса брались симметричными, т.е. сопротивление от выхода нейрона i к входу нейрона j имело ту же величину, что и сопротивление от выхода нейрона j к входу нейрона i. Заметим, что усилители имеют прямой и инвертированный выходы. Это позволяет с помощью обычных положительных сопротивлений реализовывать и те случаи, когда веса должны быть отрицательными. На рис. 6.4 показаны все возможные сопротивления, при этом никогда не возникает необходимости присоединять как прямой, так и инвертированный выходы нейрона к входу другого нейрона. В реальной системе каждый усилитель обладает конечным входным сопротивлением и входной емкостью, что должно учитываться при расчете динамической характеристики. Для устойчивости сети не требуется равенства этих параметров для всех усилителей и их симметричности. Так как эти параметры влияют лишь на время получения решения, а не на само решение, для упрощения анализа они исключены. Предполагается, что используется пороговая функция (предел сигмоидальной функции при X, стремящемся к бесконечности). Далее, все выходы изменяются в начале дискретных интервалов времени, называемых эпохами. В начале каждой эпохи исследуется сумма входов каждого нейрона. Если она больше порога, выход принимает единичное значение, если меньше - нулевое. На протяжении эпохи выходы нейронов не изменяются.
Рис. 6.4. Четырехбитовый аналого-цифровой преобразователь, использующий сеть Хопфилда.
Целью является такой выбор сопротивлений (весов), что непрерывно растущее напряжение X, приложенное к одновходовому терминалу, порождает множество из четырех выходов, представляющих двоичную запись числа, величина которого приближенно равна входному напряжению (рис. 6.5). Определим сначала функцию энергии следующим образом:
где Х - входное напряжение. Когда Е минимизировано, то получаются нужные выходы. Первое выражение в скобках минимизируется, когда двоичное число, образованное выходами, наиболее близко (в среднеквадратичном смысле) к аналоговой величине входа 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 городов. Задача состоит в отображении его в вычислительную сеть с использованием нейронов в режиме с большой крутизной характеристики ( приближается к бесконечности). Каждый город представлен строкой из n нейронов. Выход одного и только одного нейрона из них равен единице (все остальные равны нулю). Этот равный единице выход нейрона показывает порядковый номер, в котором данный город посещается при обходе. На рис. 6.6 показан случай, когда город С посещается первым, город А - вторым, город D - третьим и город В - четвертым. Для такого представления требуется n2 нейронов - число, которое быстро растет с увеличением числа городов. Длина такого маршрута была бы равна dca + dad + ddb + dbc. Так как каждый город посещается только один раз и в каждый момент посещается лишь один город, то в каждой строке и в каждом столбце имеется по одной единице. Для задачи с п городами всего имеется п! различных маршрутов обхода. Если п = 60, то имеется 69 34155 х 1078 возможных маршрутов. Если принять во внимание, что в нашей галактике (Млечном Пути) имеете) лишь 1011 звезд, то станет ясным, что полный перебор всех возможных маршрутов для 1000 городов даже и. самом быстром в мире компьютере займет время, сравнимо с геологической эпохой. Продемонстрируем теперь, как сконструировать сет: для решения этой NP-полной проблемы. Каждый нейрон снабжен двумя индексами, которые соответствуют городу порядковому номеру его посещения в маршруте. Например OUTxj = 1 показывает, что город х был j-ым по порядку j - ым городом маршрута.
функция энергии должна удовлетворять двум требованиям: во-первых, должна быть малой только для тех решений, которые имеют по одной единице в каждой строке и каждом столбце; во-вторых, должна оказывать предпочтение решениям с короткой длиной маршрута. Первое требование удовлетворяется введением следующей, состоящей из трех сумм, функции энергии:
(6.9)
где А, В и С- некоторые константы. Этим достигается выполнение следующих условий:
-
Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы.
2. Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы.
3. Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно п единиц.
Второе требование - предпочтение коротким маршрутам - удовлетворяется с помощью добавления следующего члена к функции энергии:
(6.10)
Заметим, что этот член представляет собой длину любого допустимого маршрута. Для удобства индексы определяются по модулю п, т.е. OUTn+j = OUTj, a D - некоторая константа. При достаточно больших значениях А, В и С низкоэнергетические состояния будут представлять допустимые маршруты, а большие значения D гарантируют, что будет найден короткий маршрут. Теперь зададим значения весов, т.е. установим соответствие между членами в функции энергии и членами общей формы (см. уравнение 6.2)).
Получаем
Wxi,yi = -Axy (1-ij) - Bij (1- xy ) - C - Dxy(j,i+1 + j,i-1)
где ij = 1, если i = j, в противном случае ij = 0. Кроме того, каждый нейрон имеет смещающий вес хi, соединенный с +1 и равный Сп. В работе [8] сообщается об эксперименте, в котором задача коммивояжера была решена для 10 городов. В этом случае возбуждающая функция была равна
OUT = 1/ 2[1 + th(NET/ u0)].
Как показали результаты, 16 и 20 прогонов сошлись к допустимому маршруту и около 50% решений оказались кратчайшими маршрутами, как это было установлено с помощью полного перебора. Этот результат станет более впечатляющим, если осознать, что имеется 181440 допустимых маршрутов. Сообщалось, что сходимость решений, полученных по методу Хопфилда для задачи коммивояжера, в сильной степени зависит от коэффициентов, и не имеется систематического метода определения их значений [II]. В этой работе предложена другая функция энергии с единственным коэффициентом, значение которого легко определяется. В дополнение предложен новый сходящийся алгоритм. Можно ожидать, что новые более совершенные методы будут разрабатываться, так как полностью удовлетворительное решение нашло бы массу применений.
ОБСУЖДЕНИЕ
Локальные минимумы
Сеть, выполняющая аналого-цифровое преобразование, всегда находит единственное оптимальное решение. Это обусловлено простой природой поверхности энергии в этой задаче. В задаче коммивояжера поверхность энергии сильно изрезана, изобилует склонами, долинами и локальными минимумами и нет гарантии, что будет найдено глобальное оптимальное решение и что полученное решение будет допустимым. При этом возникают серьезные вопросы относительно надежности сети и доверия к ее решениям. Эти недостатки сети смягчаются тем обстоятельством, что нахождение глобальных минимумов для NP-полных задач является очень трудной задачей, которая не может быть решена в приемлемое время никаким другим методом. Другие методы значительно более медленны и дают не лучшие результаты.