Полиномиальные эвристики в задаче коммивояжера

Полиномиальные эвристики в задаче коммивояжера.

, студ. 3 курса

Научный руководитель - к. ф-м. н., доц.

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

Ключевые слова: задача коммивояжера, эвристики, сравнительный анализ эвристик.

Задача коммивояжера является одной из наиболее известных NP-полных задач [1]. Так как для таких задач не существует эффективных точных методов, принципиально отличающихся от полного перебора, то в практических приложениях на передний план выходят эвристики небольшой степени сложности. При существующих в настоящее время аппаратных средствах они позволяют решать экземпляры задачи размерности несколько тысяч.

Сравнительный анализ эвристик был весьма популярной темой исследований в 60-70х годах прошлого века [2, 3]. Однако, аппаратные возможности компьютеров, значительно возросшие за последние несколько десятилетий, могут привести к переоценке роли различных эвристик. В тоже время, в литературе практически отсутствуют сведения о сравнении погрешности приближенного решения в среднем случае с известными теоретическими оценками в худшем случае. В качестве примера приведем известную оценку для эвристики типа Insertion.

Теорема [3]: Для графа задачи коммивояжера справедливо соотношение:

Здесь INSERT – решение, получаемое с помощью эвристики Nearest Insertion, OPTIMAL – оптимальное решение, n – порядок графа.

Основной целью данной работы стал статистический анализ качества нескольких детерминированных эвристик, степень сложности которых не превышает. Для исследования были отобраны экземпляры задачи из библиотеки TSPLIB [4] различной размерности.

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

В работе обсуждаются три типа детерминированных эвристик: Construction, Insertion и Saving. Все они позволяют за итерацию построить приближенное решение. Хотя некоторые из этих эвристик в базовой реализации достаточно очевидны, оценка их качества в учебной литературе встречается крайне редко. Как будет показано ниже, по ряду важных параметров наиболее качественной является эвристика типа Saving. Она была предложена ещё в середине 60-х годов прошлого века для решения одного класса задач транспортировки грузов [5]. Адаптация основных идей, заложенных в эту эвристику, приводит к удивительно хорошему качеству приближенного решения, несмотря на низкую сложность алгоритма.

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

·  EUC2 – элементы матрицы весов графа задаются, как евклидовы расстояния между двумя точками плоскости,

·  GEO – веса рассчитываются, как кратчайшие расстояния между двумя точками на поверхности шара, радиус которого равен 6371 км,

·  lower_diag_row – веса задаются в явном виде нижней диагональной матрицей.

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

•  Экземпляры маленькой размерности: ,

•  Экземпляры средней размерности: 90,

•  Экземпляры большой размерности: .

Логарифмическая зависимость точности решения в худшем случае от порядка графа делает избыточным наличие большого количества групп.

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

Таблица 1. Среднее значение максимальной погрешности.

Размерность	Тип эвристики
задач	Construction	Insertion	Saving
Маленькая	1.343	1.204	1.093
Средняя	1.405	1.290	1.238
Большая	1.383	1.334	1.165

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

Более подробно результаты расчетов для задач последней группы показаны в таблицах 2, 3, 4. Сравнительный анализ на основе величины средней погрешности, как и ранее, указывает на более высокое качество эвристики типа Saving. Отдать предпочтение какой-либо из двух оставшихся эвристик крайне затруднительно.

Таблица 2. Экземпляры задачи порядка . Эвристика Nearest Neighbor

name	min	max	average	deviation	span	type
a280	1.145	1.299	1.225	0.026	0.153	EUC2
pr299	1.208	1.443	1.304	0.046	0.217	EUC2
lin318	1.169	1.399	1.251	0.023	0.299	EUC2
gr431	1.209	1.411	1.268	0.038	0.202	GEO
pr439	1.186	1.364	1.265	0.028	0.178	EUC2

Таблица 3. Экземпляры задачи порядка . Эвристика Nearest Insertion

name	min	max	average	deviation	span	type
a280	1.275	1.379	1.342	0.014	0.104	EUC2
pr299	1.282	1.338	1.311	0.009	0.056	EUC2
lin318	1.344	1.411	1.379	0.010	0.067	EUC2
gr431	1.205	1.245	1.216	0.007	0.039	GEO
pr439	1.206	1.298	1.274	0.006	0.041	EUC2

Таблица 4. Экземпляры задачи порядка . Эвристика Saving

name	min	max	average	deviation	span	Type
a280	1.054	1.147	1.096	0.015	0.094	EUC2
pr299	1.057	1.145	1.099	0.015	0.089	EUC2
lin318	1.059	1.144	1.088	0.013	0.086	EUC2
gr431	1.073	1.223	1.128	0.023	0.150	GEO
pr439	1.069	1.167	1.117	0.017	0.097	EUC2

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

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

1.  Вычислительные машины и труднорешаемые задачи. М: Мир, 1982.

2.  Bellmore M., Nemhauser G. L. The traveling salesman problem: a survey. // Operations Research, 1968, v.16, No.3, pp.538-558.

3.  Rosenkrantz D. J., Stearns R. E., Lewis II P. M. Analysis of several heuristics for the traveling salesman problem. // SIAM Journal on Computing, 1977, v.6, No.3, pp.563-581.

4.  Reinelt G. The Traveling putational Solutions for TSP Applications. Berlin: Springer-Verlag, 1994.

5.  Clarke G., Wright J. W. Scheduling of vehicles from a central depot to a number of delivery points. // Operations Research, 1964, v.12, No.4, pp.568-581.