Задача коммивояжера icon

Задача коммивояжера


Смотрите также:
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах...
Решение задачи коммивояжера методом...
Построение маршрута (задача коммивояжера)...
Задача коммивояжера классический пример труднорешаемой задачи. Известно...
Задача коммивояжера постановка задачи и ее прикладное значение...
Задача выбора подходящего маршрута очень актуальна...
Курс IV семестр 7, 8 лекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет...
Задача на границах периодической системы 4 Задача кот шредингера и химия 5...
Тема Основные классы экстремальных задач...
С временными окнами и ее решение...
Смерть коммивояжера (премьера)...
1 семестр. Геометрические и аналитические методы...



Загрузка...
скачать

СЕКЦИЯ 7

Л.Б. ЛИТИНСКИЙ, А.А. МУРАШКИН

Институт оптико-нейронных технологий РАН, Москва

Московский физико-технический институт (государственный университет)

litin@iont.ru, murashkin@fromru.com


ПРИМЕНЕНИЕ НЕЙРОСЕТЕВЫХ МЕТОДОВ

ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА


Аннотация

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


Введение


Для решения широкого класса оптимизационных задач можно применять методы нейронных сетей. В работах [1], [2] был предложен подход к отысканию глубоко лежащего локального минимума квадратичного по бинарным переменным функционала, опирающийся на свойства собственных векторов и собственных значений матрицы связей. Мы решили применить развиваемый авторами [1], [2] подход для решения классической NP-полной задачи – задачи коммивояжера (TSP – Traveling Salesman Problem).


^ Задача коммивояжера


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

В [3] был предложен способ решения задачи TSP при помощи сети Хопфилда. При этом возможному маршруту коммивояжера сопоставлен -мерный вектор с бинарными координатами где индекс кодирует город, а индекс – номер города в маршруте (все N городов изначально пронумерованы). Значение означает, что i-й город встречается в маршруте на месте . Таким образом, если представить в виде матрицы, то допустимыми маршрутами будут являться только те, матрица которых имеет ровно одну 1 в каждой строке и в каждом столбце.

Обозначим через расстояние между i-м и j-м городами. Тогда минимизация маршрута коммивояжера сводится к нахождению минимума следующего квадратичного функционала:

(1)

при дополнительных ограничениях:

, (2)

. (3)

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


^ Формализация задачи


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

(4)

где множитель Лагранжа регулирует строгость соблюдения условий (2) и (3) в окончательном решении.

Перепишем функционал (4) в спиновых переменных , сделав замену :

(5)

Сравним (5) с общим выражением для энергии состояния в сети Хопфилда:

. (6)

В нашем случае размерность задачи , а вектор и матрица межсвязей J имеют следующую структуру:

,

, (7)

где элементы отвечают учету квадратичных членов в (5), а – учету линейных членов.


Выбор значения параметра


Для того, чтобы окончательно определить элементы матрицы J (7) и приступить к минимизации функционала (5), необходимо зафиксировать значение множителя Лагранжа . В литературе описано множество способов выбора этого параметра, но ни один из них не гарантирует отыскания оптимального решения. Хопфилд и Танк в своей работе [3] предлагали брать этот параметр равным по порядку величины среднему значению расстояния между городами, то есть

.

В работе [4] предлагается адаптивный метод подбора параметра . Идея состоит в том, чтобы на каждом шаге эволюции сети изменять так, чтобы переворот соответствующего спина приводил к понижению энергии. Однако, следуя рассуждениям авторов, мы обнаружили, что предложенный алгоритм неустойчив: в процессе функционирования система попадала в предельные циклы (при асинхронной динамике!). Кроме того, оказалось невозможным получить допустимый маршрут на выходе такой нейронной сети с автоподстройкой , когда в основе ее работы лежит только принцип понижения значения функционала (7). Мы немного изменили алгоритм так, чтобы он гарантированно давал на выходе допустимый маршрут. Оказалось, однако, что результирующие значения получаются при этом довольно высокими. Их можно рассматривать как верхнюю границу для значений множителя Лагранжа – . В качестве нижней границы , как показал эксперимент, можно взять значение , предложенное Хопфилдом.


^ Описание эксперимента


Нами был проделан следующий эксперимент. Города располагались случайным образом на окружности радиуса R = 100. Таким образом, приближенно известна длина оптимального маршрута – (эксперимент проводился для числа городов N = 10). Отрезок разбивался на 20 равных частей, затем для каждого из двадцати проводились следующие расчеты:

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

2) вычислялись собственные значения и собственные векторы матрицы J ( упорядочены по убыванию);

3) производился запуск построенной сети с трёх различных типов стартовых векторов ( стартов для каждого типа):

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

со случайных конфигурационных векторов;

со случайных конфигурационных векторов, являющихся допустимыми маршрутами;

4) по каждому типу стартовых векторов фиксировались энергии стартовых векторов и полученных локальных минимумов, число найденных допустимых маршрутов, минимальная длина найденного маршрута и то, сколько раз был достигнут глобальный минимум.


Результаты


Полученные результаты отражены на рис. 1, 2 и в табл. 1.

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

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




Рис. 1


Таблица 1





Соб. векторы

Случ. векторы

Маршруты



950

975

1040



40

29

22



620

620

620



10

1

2










Минимальная достигнутая Сколько раз был достигнут

длина маршрута оптимум (из 100 стартов)

Рис. 2

На рис. 2 приведены интегральные характеристики по всем проделанным экспериментам в интервале . По горизонтальной оси отложен параметр . На рисунках слева показана минимальная достигнутая длина маршрута для различных типов стартовых векторов (сверху вниз: собственные векторы, случайные векторы, маршруты). На рисунках справа – сколько раз был получен кратчайший маршрут.

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

Следует отметить, что в эксперименте использовалась максимальная динамика сети (в каждый момент времени переворачивается самый неудовлетворенный спин).


Выводы


Эксперимент показал, что при помощи сети Хопфилда можно решать оптимизационные задачи с ограничениями, однако при этом остается открытым вопрос о выборе параметра , значение которого сильно влияет на решение задачи. Кроме того, независимо от того, использовать или не использовать собственные значения и векторы, вычислительная сложность алгоритма ~, в предположении, что необходимо выполнить по крайней мере стартов. Таким образом, при N > 20 этот метод решения становится непродуктивным.


Работа выполнена при финансовой поддержке грантами РФФИ 04-07-90038 и 03-01-00355.


Список литературы


1. Крыжановский Б.В., Литинский Л.Б. Отыскание глобального минимума одного многоэкстремального функционала // Искусственный интеллект. 2003. № 3. С. 116-120.

2. Крыжановский Б.В., Литинский Л.Б. Отыскание глобального минимума в моделях Хопфилдова типа. «НЕЙРОИНФОРМАТИКА-2004». Сб. научных трудов. Ч. 1. С. 17-24.

3. Hopfield J.J and Tank D.W. Neural computation of decisions in optimization problems.

4. Rong Long Wang, Zheng Tang, Qi Ping Cao. A learning method in Hopfield neural network for combinatorial optimization problem // Neurocomputing. 2002. V. 48. Р. 1021-1024.


УДК 004.032.26(06) Нейронные сети




Скачать 81.36 Kb.
оставить комментарий
Дата02.10.2011
Размер81.36 Kb.
ТипЗадача, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх