Хайкин С. - Нейронные сети (778923), страница 181
Текст из файла (страница 181)
2. Комбинаторные задачи оптимизации (сошЫпагопа1 орбш!ха!!оп ргоЫеш), которые считаются в математике самыми сложными. Этот класс задач оптимизации включает в себя известную задачу коммивояжера (Тгаче!1!пя Ба!езшап РгоЫеш— ТЗР), считаюшуюся классической. При заданном расположении известного числа городов (предполагается, что они лежат на плоскости) стоит задача поиска 910 Глава 14. Нейродинамикв кратчайшего маршрута обхода всех городов, который начинается и заканчивается в одном и том же городе.
Задача ТЯР просто формулируется, но крайне сложно решается, поскольку не существует известного метода поиска оптимального маршрута, ищущего все возможные маршруты и затем выбирающего кратчайший из них. Эта задача называется ХР-полной (ХР-сошр!еге) [474]. В новаторской работе [482] было продемонстрировано, как аналоговая сеть, основанная на системе дифференциальных уравнений первого порядка (14.20), может использоваться для представления решения задачи ТБР. В частности, синаптические веса этой сети определялись расстоянием между отдельными городами, а оптимальное решение являлось фиксированной точкой нейродинамических уравнений (14.20). Здесь и сосредоточены сложности, связанные с "отображением" комбинаторных задач оптимизации на непрерывные (аналоговые) сети Хопфилда.
Эта сеть стремится минимизировать одну функцию энергии (Ляпунова), в то время как типичная комбинаторная задача оптимизации требует оптимизации некоторой целевой функции при наличии ряда жестких ограничений [340]. Если нарушается какое-либо из этих ограничений, решение считается неверным. Первые процедуры такого отображения основывались на функции Ляпунова, сконструированной специальным методом, обычно использующим по одному слагаемому для каждого условия: Е = Еепс + с~ Е, ~' + сз Ез ~' +...
(14.96) Первое слагаемое, Ео"т, является минимизируемой целевой функцией (например, длиной маршрута в задаче ТЗР). Эта функция определяется рассматриваемой задачей. Оставшиеся слагаемые, Е,'~', Езо~',..., представляют собой штрафные функции, минимизация которых удовлетворяет ограничениям. Скаляры с„сз,... являются постоянными весами, которые назначены соответствующим штрафным функциям Е,~', Езо~',.... Они обычно определяются методом проб и ошибок.
К сожалению, многочисленные слагаемые в функции Ляпунова (14.96) имеют тенденцию вытеснять друг друга, и успех сети Хопфилда в огромной мере зависит от относительных значений сз, сз,... [340]. Учитывая это, неудивительно, что такая сеть зачастую производит большое количество неверных решений [63], [1160]. В [340] рассматривалось множество основных вопросов, касающихся использования непрерывных сетей Хопфилда как инструмента разрешения комбинаторных задач оптимизации; основные ее выводы приведены ниже. ° Для заданной задачи комбинаторной оптимизации, представленной в терминах квадратичного 0-1 программирования, равно как и для коммивояжера, существует простой метод программирования сети, приводящий к ее решению, при этом найденное решение не будет нарушать ни одно из ограничений задачи. 14.1б.
Резюме и обсуждение 911 ° На основании результатов теории сложности (сошр!ехйу бтеогу) и математического программирования было показано, что за исключением случая, когда ограничения задачи имеют особые свойства, определяющие интегральный политоп или многогранник, невозможно заставить сеть сойтись к корректному, интерпретируемому решению. В геометрических терминах политоп, т.е. ограниченный многогранник, называется интегральным политопом, если все его грани являются точками 0-1. Даже когда речь идет об интегральном поли- топе, если целевая функция .Ео"т. является квадратичной, то задача является Ъ[Р-подвой и иет никакой гарантии, что сеть найдет оптимальное решение. К классу этих задач относится и задача коммивояжера. Однако допустимое решение все равно может быть найдено, и в зависимости от природы используемого процесса спуска к этому решению существует шанс, что это решение окажется достоверным.
Модель Хопфилда, которая рассматривалась в настоящей главе, использовала симметричные связи между своими нейронами. Динамика такой структуры аналогична динамике градиентного спуска, что гарантирует сходимость к фиксированной точке. Однако динамика мозга отличается от динамики модели Хопфилда в двух основных вопросах. ° Взаимосвязи между нейронами мозга являются ассимметричиыми. ° В мозге наблюдается осциллирующее и сложное непериодическое поведение.
Естественно, причиной этого явяются особые свойства мозга, которые вызвали незатухающий интерес при изучении ассимметричиых сетей, предшествовавших модели Хопфилда. Если отказаться от требования симметрии, следующей простейшей моделью является сеть возбуждения-торможеиия (ехс1[а[огу-[пЬйт|гогу пети от[с), нейроны которой разбиваются иа две категории: с возбуждающими и тормозящими выходами. Сииаптические связи между двумя этими популяциями являются ассимметричиыми, в то время как связи в каждой из популяций симметричны.
В [9661 рассматривалась динамика именно такой сети. Представленный в этой работе анализ использует сходство между динамикой сети возбуждения-торможения и динамикой градиентного спуска— градиентного подъема (йгайеп[ с[езсепг — йгатйеп[ азсеп[ с[упаштсз), в которой уравиеиия движения для некоторых переменных состояния имели форму градиентного спуска, а для остальных — форму градиентного подъема. Следовательно, в отличие от динамики градиентного спуска, которая характеризует сеть Хопфилда, динамика модели, предложенной в этой работе, может сходиться к некоторой фиксированной а Трактовка биологических нейронных сетей как нелинейных динамических систем, обладающих оспиллируюшим поведением, имеет долгую историю [30], [31), [34), [176[, [1161[.
912 Глава 14. Нейродинамика точке или предельному циклу, в зависимости от выбора параметров сети. Таким образом, антисимметричная модель, предложенная в (9661, имеет преимущество перед симметричной моделью Хопфилда. Задачи Динамические системы 14.1. Переформулируйте теорему Ляпунова для случая, когда вектор состояния х(0) является равновесным в динамической системе.
14.2. Сверьте блочные диаграммы на рис. 14.8, а и 14.8, б с уравнениями (14.18) и (14.19). 14.3. Рассмотрим нейродинамическую систему общего вида с неопределенной зависимостью от внутренних динамических параметров, внешних динамических возбудителей и переменных состояния. Эта система определяется следующей системой уравнений: Ых, — ~ = Ет (ЪУ, н, х), г = 1, 2,, )т', Ш где матрица 1т' представляет внутренние динамические параметры системы; вектор н — внешние динамические возбудители; х — вектор состояний, гчй элемент которого обозначается символом х ..
Предположим, что траектории этой системы сходятся к точечным аттракторам для значений %, н и начальных состояний х(0), находящихся в некоторой рабочей области пространства состояний (839). Обсудите, как описанная система может использоваться для следующих приложений. а) Непрерывный оператор, в котором н — вход, а х(оо) — выход. б) Ассоциативная память, в которой х(0) — вход, а х(оо) — выход. Модели Хопфилда 14.4. Рассмотрим сеть Хопфилда, состоящую из пяти нейронов, в которой требуется сохранить следующие три ячейки фундаментальной памяти: [+1 +1 +1 +1 +1[т Рг = [+1,— 1,— 1,+1,— Ц 1 +1 1 +1 +11т Задачи 913 а) Вычислите матрицу синаптических весов размерностью 5 х 5. б) С помощью асинхронной коррекции покажите, что все три ячейки фунда- ментальной памяти, «„«з и «з, удовлетворяют условию выравнивания.
в) Исследуйте производительность этой сети по извлечению данных, когда ей подается на вход зашумлениая версия «м в которой полярность второго элемента изменена. 14.6. а) Покажите, что цт «2 = [ — 1, +1, +1, — 1, +1) т, «3 = [+1~ 1~+1~ 1~ 1] также являются ячейками фундаментальной памяти сети Хопфилда, опи- санной в условиях задачи 14.4. Как эти ячейки связаны с ячейками, опи- санными в задаче 14.4? б) Предположим, что первый элемент ячейки фундаментальной памяти «з в задаче 14.4 замаскирован (т.е.
принят равным нулю). Определите результирующий образ, который создаст модель Хопфилда. Сравните полученный результат с исходной формой «з. 14.7. Рассмотрим сеть Хопфилда, состоящую из двух нейронов. Матрица синаптических весов имеет следующий вид: к нейронам, равно нулю. Четырьмя воз- быть Внешнее смещение, применяемое можными состояниями сети могут [+1 +1]т 1 +1]т цт [+1 1]т хг = 14.5. Исследуйте возможность использования синхронной коррекции для измерения производительности извлечения информации в сети Хопфилда при условиях задачи 14.4. 914 Глава 14. Нейродинамика а) Покажите, что состояния хз и ха являются устойчивыми, а состояния хз и хз представляют собой предельные циклы.
При этом используйте следующий инструментарий: (1) условие выравнивания (устойчивости) и (2) функция энергии. б) Какова длина предельного цикла, характеризующего состояния хз и хз? 14.8. В этой задаче выведем формулу (14.55) емкости хранения практически без ошибок для модели Хопфилда, использующейся в качестве ассоциативной памяти. а) Асимптотическое поведение функции ошибок приближенно описывается следующим выражением: 2 е к его(у) 1 — — для больших у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
