Применения сети Хопфилда к задачам комбинаторной оптимизации.

Ассоциативность памяти нейронной сети Хопфилда не является единственным ее достоинством, которое используется на практике. Другим важным свойством этой архитектуры является уменьшение ее функции Ляпунова в процессе нейродинамики. Следовательно, нейросеть Хопфилда можно рассматривать, как алгоритм оптимизации целевой функции в форме энергии сети.

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

Исследования возможности использования нейронных сетей для решения таких задач сегодня сформировали новую научную дисциплину - нейроматематику.

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

Многие задачи оптимального размещения и планирования ресурсов, выбора маршрутов, задачи САПР и иные, при внешней кажущейся простоте постановки имеют решения, которые можно получить только полным перебором вариантов. Часто число вариантов быстро возрастает с числом структурных элементов N в задаче (например, как N! - факториал N), и поиск точного решения для практически полезных значений N становится заведомо неприемлимо дорогим. Такие задачи называют неполиномиально сложными или NP-полными. Если удается сформулировать такую задачу в терминах оптимизации функции Ляпунова, то нейронная сеть дает весьма мощный инструмент поиска приближенного решения.

Рассмотрим классический пример NP-полной проблемы - так называемую задачу комивояжера (бродячего торговца). На плоскости расположены N городов, определяемые парами их географических координат: (x_i,y_i), i=1..N. Некто должен, начиная с произвольного города, посетить все эти города, при этом в каждом побывать ровно один раз. Проблема заключается в выборе маршрута путешествия с минимально возможной общей длиной пути.

Полное число возможных маршрутов равно , и задача поиска кратчайшего из них методом перебора весьма трудоемка. Приемлимое приближенное решение может быть найдено с помощью нейронной сети, для чего, как уже указывалось, требуется переформулировать задачу на языке оптимизации функции Ляпунова (J.J.Hopfield, D.W.Tank, 1985).

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

Таб. 9.1. Маршрут B-A-C-D...

Сопоставим теперь клетке таблицы на пересечении строки X и столбца i нейрон S_xi из {0,1}. Возбужденное состояние данного нейрона сигнализирует о том, что город X в маршруте следует посещать в i-тую очередь. Составим теперь целевую функцию E(S) задачи поиска оптимального маршрута. Она будет включать 4 слагаемых:

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

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

Здесь за d_XY обозначено расстояние между городами X и Y. Заметим, что отрезок пути X-Y включается в сумму только тогда, когда город Y является относительно города X либо предыдущим, либо последующим. Множители a, b, g и h имеют смысл относительных весов слагаемых.

Общий вид функции Ляпунова сети Хопфилда дается выражением (см. предыдущую лекцию):

Полученная целевая функция из четырех слагаемых представляется в форме функции Ляпунова, если выбрать значения весов и порогов сети в следующем виде:

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

Хопфилдом и Тэнком изложенная модель была опробована в вычислительном эксперименте. Нейронной сети удавалось находить близкие к оптимальным решения за приемлимые времена даже для задач с несколькими десятками городов. В дальнешем последовало множество публикаций о разнообразных применениях нейросетевых оптимизаторов. В завершении лекции рассмотрим одно из таких применений - задачу о расшифровке символьного кода.

Пусть имеется некоторое (достаточно длинное) текстовое сообщение, написанное на некотором языке с использованием алфавита A, B, C... z и символа “пробел”, отвечающего за промежуток между словами. Данное сообщение закодировано таким образом, что каждому символу, включая пробел, сопоставлен некоторый символ из ряда i,j,k,.... Требуется расшифровать сообщение.

Данная задача также относится к числу NP-полных, общее число ключей шифра имеет факториальную зависимость от числа символов в алфавите. Приближенное нейросетевое решение может быть основано на том факте, что частоты появления отдельных символов и конкретных пар символов в каждом языке имеют вполне определенные значения (например, в русском языке частота появления буквы “а” заметно превосходит частоту появления буквы “у”, слог “во” появляется довольно часто, а, например, сочетание “йщ” вовсе не возможно).

Частоты появления символов P_i и их пар P_ij в закодированном сообщении можно вычислить непосредственно. Имея, далее, в распоряжении значения P_A частот появления символов языка и их пар P_AB, следует отождествить их с вычисленными значениями для кода. Наилучшее совпадение и даст требуемый ключ.

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

Полное выражение для целевой функции имеет вид:

Целевая функция также, как и для задачи комивояжера, приводится к виду функции Ляпунова, после чего нейронная сеть выполняет требуемую расшифровку.

Задачи

1. Непосредственным вычислением убедиться, что все образы обучающей выборки являются устойчивыми состояниями сети с ортогонализацией матрицы Хебба.

2. Для задачи комивояжера получить представление E(S) целевой функции в форме функции Ляпунова.

3. Вывести энергетическую функцию сети Хопфилда для задачи оптимального размещенния смесей кода и данных в многопроцессорной архитектуре “гиперкуб”.

Решение (Терехов С.А., Олейников П.В., 1994). В многопроцессорной ЭВМ этой архитектуры процессоры расположены в вершинах многомерного куба. Каждый процессор связан с ближайшими к нему узлами. На каждый процессор назначается некоторый фрагмент кода программы и локальные данные. В процессе вычислений процессоры обмениваются информацией, при этом скорость выполнения программ замедляется. Время, затрачиваемое на пересылку сообщения тем больше, чем дальше обменивающиеся процессоры расположены друг от друга.Требуется так разместить смеси кода и данных по реальным процессорам, чтобы максимально снизить потери на обмены информацией.

Как и в задаче комивояжера, обозначим процессоры заглавными буквами, а номера смесей - латинскими индексами. Если d_XY - расстояние между процессорами, измеренное вдоль ребер гиперкуба (Хеммингово расстояние), а D_ij - объем передаваемой информации между смесями i и j, то искомое решение должно минимизировать сумму SUM d_XYD_ij. Поэтому целевая функция представляется в виде:

E(S) = E₁ + E₂ + E₃ + (h/2) SUM _i SUM _j SUM _X SUM _Y (S_XiS_Yj d_XY D_ij)

Это выражение далее приводится к форме функции Ляпунова. Численные эксперименты с гиперкубами размерности 3, 4 и 5 показывают, что применение нейросетевого подхода позволяет получить умешение числа информационных обменов (и, соотвественно, повысить производительность ЭВМ) для некоторых задач до 1,5 раз.

© 1994, С. А. Терехов, оригинальный текст
© 1998, С. А. Терехов, электронная версия