Решение задачи коммивояжера сетью Хопфилда

Рассмотрим задачу коммивояжера для

$Решение задачи коммивояжера сетью Хопфилда$

городов. Известны расстояния

$Решение задачи коммивояжера сетью Хопфилда$

между каждой парой городов

$Решение задачи коммивояжера сетью Хопфилда$

; коммивояжер, выходя из одного города, должен посетить

$Решение задачи коммивояжера сетью Хопфилда$

других городов, заходя по одному разу в каждый, и вернуться в исходный. Требуется определить порядок обхода городов, при котором общее пройденное расстояние минимально.

Пусть сеть Хопфилда состоит из

$Решение задачи коммивояжера сетью Хопфилда$

нейронов, а состояние нейронов описывается двойными индексами

$Решение задачи коммивояжера сетью Хопфилда$

, где индекс

$Решение задачи коммивояжера сетью Хопфилда$

связан с именем города,

$Решение задачи коммивояжера сетью Хопфилда$

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

1) должна поддерживать устойчивое состояние в форме матрицы

$Решение задачи коммивояжера сетью Хопфилда$

(1)

в которой строки соответствуют городам, столбцы - их номерам в маршруте; в каждой строке и каждом столбце только одна единица, остальные нули;

2) из всех решений вида (1) функция энергии должна поддерживать те, которые соответствуют коротким маршрутам.

Таким требованиям удовлетворяет функция энергии в виде:

$Решение задачи коммивояжера сетью Хопфилда$

(2)

где первые три члена поддерживают первое требование, четвертый член — второе. Первый член равен нулю, если каждая строка

$Решение задачи коммивояжера сетью Хопфилда$

содержит не более одной единицы. Второй равен нулю, если каждый столбец

$Решение задачи коммивояжера сетью Хопфилда$

содержит не более одной единицы. Третий равен нулю, если в матрице всего

$Решение задачи коммивояжера сетью Хопфилда$

единиц. Короткие маршруты поддерживает четвертый член. В нем индексы

$Решение задачи коммивояжера сетью Хопфилда$

берутся по модулю

$Решение задачи коммивояжера сетью Хопфилда$

для того, чтобы показать, что

$Решение задачи коммивояжера сетью Хопфилда$

-й город соседствует в маршруте с

$Решение задачи коммивояжера сетью Хопфилда$

, т.е.

$Решение задачи коммивояжера сетью Хопфилда$

. Четвертый член численно равен длине маршрута. Каноническое выражение для функции вычислительной энергии имеет вид

$Решение задачи коммивояжера сетью Хопфилда$

(3)

Из (2) и (3) получаем веса сети Хопфилда:

$Решение задачи коммивояжера сетью Хопфилда$

Здесь

$Решение задачи коммивояжера сетью Хопфилда$

- символ Кронекера.

Моделирование работы сети Хопфилда показало, что лучшее по качеству решение дает сеть, нейроны которой имеют сигмовидную характеристику, а сеть, в которой нейроны имеют ступенчатые переходы, приходила к финальным состояниям, соответствующим маршрутам немного лучшим, чем случайные. Многочисленные исследования показывают, что качество решения задачи минимизации функции энергии (2) существенно зависит от выбора производной сигмовидной униполярной функции активации нейрона в окрестности нуля. При малой величине производной минимумы энергии оказываются в центре гиперкуба решений (некорректное решение), при большой величине производной сеть Хопфилда попадает в вершину гиперкуба, соответствующую локальному минимуму функции энергии. Кроме того, на качество решения существенное влияние оказывает выбор коэффициентов

$Решение задачи коммивояжера сетью Хопфилда$

. Поиск методов оптимального выбора этих коэффициентов является в настоящее время предметом интенсивных исследований.

Содержание раздела

Главная сайта