Оптимизация с использованием сети Хопфилда
Оптимизация - это действие, направленное на то, чтобы сделать что-то, например дизайн, ситуацию, ресурсы и систему, максимально эффективными. Используя сходство между функцией стоимости и функцией энергии, мы можем использовать сильно взаимосвязанные нейроны для решения задач оптимизации. Такой вид нейронной сети представляет собой сеть Хопфилда, которая состоит из одного слоя, содержащего один или несколько полностью связанных рекуррентных нейронов. Это можно использовать для оптимизации.
Что следует помнить при использовании сети Хопфилда для оптимизации -
Энергетическая функция сети должна быть минимальной.
Он найдет удовлетворительное решение, а не выберет один из сохраненных шаблонов.
Качество решения, найденного сетью Хопфилда, существенно зависит от начального состояния сети.
Проблема коммивояжера
Нахождение кратчайшего пути, пройденного продавцом, - одна из вычислительных задач, которую можно оптимизировать с помощью нейронной сети Хопфилда.
Базовая концепция TSP
Задача коммивояжера (TSP) - это классическая задача оптимизации, в которой продавец должен путешествовать. nгорода, которые связаны друг с другом, при этом стоимость и пройденное расстояние минимальны. Например, продавец должен проехать группу из 4 городов A, B, C, D, и цель состоит в том, чтобы найти самый короткий круговой тур, ABC – D, чтобы минимизировать стоимость, которая также включает стоимость поездки из последний город D к первому городу A.
Матричное представление
Фактически каждый тур по ТСП n-го города можно выразить как n × n матрица, чья ith строка описывает ithрасположение города. Эта матрица,M, для 4 городов A, B, C, D можно выразить следующим образом:
$$ M = \ begin {bmatrix} A: & 1 & 0 & 0 & 0 \\ B: & 0 & 1 & 0 & 0 \\ C: & 0 & 0 & 1 & 0 \\ D: & 0 & 0 & 0 & 1 \ end {bmatrix} $$
Решение от Hopfield Network
При рассмотрении решения этой TSP сетью Хопфилда каждый узел в сети соответствует одному элементу в матрице.
Расчет функции энергии
Чтобы быть оптимизированным решением, функция энергии должна быть минимальной. На основе следующих ограничений мы можем вычислить функцию энергии следующим образом:
Ограничение-I
Первое ограничение, на основании которого мы будем вычислять функцию энергии, состоит в том, что один элемент должен быть равен 1 в каждой строке матрицы M а остальные элементы в каждой строке должны равняться 0потому что каждый город может фигурировать только в одной позиции в туре TSP. Это ограничение математически можно записать следующим образом:
$$ \ displaystyle \ sum \ limits_ {j = 1} ^ n M_ {x, j} \: = \: 1 \: для \: x \: \ in \: \ lbrace1, ..., n \ rbrace $ $
Теперь функция энергии, которая должна быть минимизирована на основе вышеуказанного ограничения, будет содержать член, пропорциональный -
$$ \ displaystyle \ sum \ limits_ {x = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {j = 1} ^ n M_ {x, j } \ end {array} \ right) ^ 2 $$
Ограничение-II
Как мы знаем, в TSP один город может находиться в любой позиции тура, следовательно, в каждом столбце матрицы. M, один элемент должен быть равен 1, а другие элементы должны быть равны 0. Это ограничение математически можно записать следующим образом:
$$ \ displaystyle \ sum \ limits_ {x = 1} ^ n M_ {x, j} \: = \: 1 \: для \: j \: \ in \: \ lbrace1, ..., n \ rbrace $ $
Теперь функция энергии, которая должна быть минимизирована на основе вышеуказанного ограничения, будет содержать член, пропорциональный -
$$ \ displaystyle \ sum \ limits_ {j = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {x = 1} ^ n M_ {x, j } \ end {array} \ right) ^ 2 $$
Расчет функции затрат
Предположим, что квадратная матрица (n × n) обозначается C обозначает матрицу затрат TSP для n города, где n > 0. Ниже приведены некоторые параметры при расчете функции стоимости.
Cx, y - Элемент матрицы стоимости обозначает стоимость проезда из города x к y.
Смежность элементов A и B может быть показана следующим соотношением -
$$ M_ {x, i} \: = \: 1 \: \: и \: \: M_ {y, i \ pm 1} \: = \: 1 $$
Как мы знаем, в Matrix выходное значение каждого узла может быть либо 0, либо 1, поэтому для каждой пары городов A, B мы можем добавить следующие члены к функции энергии:
$$ \ Displaystyle \ сумма \ пределы_ {я = 1} ^ n C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) $$
На основе приведенной выше функции стоимости и значения ограничения конечная функция энергии E может быть дано следующим образом -
$$ E \: = \: \ frac {1} {2} \ displaystyle \ sum \ limits_ {i = 1} ^ n \ displaystyle \ sum \ limits_ {x} \ displaystyle \ sum \ limits_ {y \ neq x} C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) \: + $$
$$ \: \ begin {bmatrix} \ gamma_ {1} \ displaystyle \ sum \ limits_ {x} \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {i} M_ {x, i} \ end {array} \ right) ^ 2 \: + \: \ gamma_ {2} \ displaystyle \ sum \ limits_ {i} \ left (\ begin {array} {c} 1 \: - \ : \ displaystyle \ sum \ limits_ {x} M_ {x, i} \ end {array} \ right) ^ 2 \ end {bmatrix} $$
Вот, γ1 а также γ2 - две константы взвешивания.