Автоматика и телемеханика, № 3, 2015
© 2015 г. С.И. СЕРГЕЕВ, д-р физ.-мат. наук (abra_888@mail.ru) (Московский государственный университет экономики, статистики и информатики)
ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА. II
Предлагаются некоторые приближенные алгоритмы решения дискретных задач. Так, для задачи коммивояжера на минимум устанавливаются оценки функционалов для симметричной задачи на величину, большую, чем (99,0-99,70) %, а для несимметричной задачи — большую, чем (99,0-99,23) % (экспериментальные оценки). Кроме того, предлагается другой алгоритм получения задачи коммивояжера на минимум, использующий помимо двухиндексной и одноиндексную модель.
1. Введение
Известно, что задача коммивояжера (ЗК) (минисуммный и максисуммный варианты) — NP-трудная проблема, и потому интерес к разработке эффективных приближенных алгоритмов ее решения существует давно [1—3]. Эффективность точных и приближенных алгоритмов оценивается либо на основании численного эксперимента по сравнению результатов решения на однотипных тестовых задачах, либо на основании гарантированных оценок точности по функционалу [1—3]. Последние являются достаточно грубыми (даже для ЗК на минимум), и это обстоятельство является в основном свойством оценок, а не качества решений, получаемых с помощью приближенных алгоритмов. В настоящей статье предлагаются новые приближенные алгоритмы решения ЗК (на минимум и максимум) с оценками точности по функционалу. Оценки эти — апостериорные и базируются часто на известном в теории оптимального управления аппарате оценок по функционалу приближенных решений [4-7].
2. Приближенные алгоритмы решения ЗК
Существует несколько близких формулировок ЗК [1-3]. Выберем среди них формализацию, использованную в [8, ч. III, IV]:
(2.1) I = ^ ^ öijUij — min,
i&N j&N
(2.2a) =1 j € N,
i&N
(2.2б) J2uij =1 i € N,
j&N
(2.3) Uij = {0, 1}, i,j € N,
(2.4) Z С N,
^ з
где N = {1,?г}, Е и 2 = N, с^ ^ 0 — действительные числа и условия (2.4) справедливы для любых подмножеств 2 таких, что 2 ^ |2| ^ п — 2, а сим-
вол |Z| обозначает число элементов в подмножестве Z. Связи (2.4) означают, что для любого подмножества Z С N должна найтись пара городов i € Z, j € Z такая, что участок пути из i-го города в j-й содержится в пути коммивояжера.
Для ЗК на минимум (ЗК (мин)) и максимум (ЗК (макс)) существует несколько алгоритмов решения (в том числе и приближенных) разной степени точности по функционалу.
Рассмотрим сначала алгоритм решения ЗК (мин). Известно, что наилучшие результаты этого алгоритма получены в [1; 8, ч. III, IV; 9, 10] с применением двухиндексной модели. Нижняя граница при этом составляет для симметричной ЗК ~ (99,0-99,70) % (экспериментальная оценка) [1, с. 373], а для несимметричной ЗК ~ (99,0-99,23) % (экспериментальная оценка) [1, с. 367]. Такие границы получены как результат увеличения размерности задачи назначения, являющейся одной из первых нижних границ ЗК. Полученные нижние границы используются в рамках линейного задания разрешающей функции p(t,y). Применение нелинейного задания разрешающей функции с введением одноиндексной модели ЗК [11, 12] увеличивает указанные проценты.
Так же строится алгоритм решения ЗК (макс) [13]. Полученные при этом алгоритмы дают экспериментальные оценки [1]. Точные оценки для ЗК (макс) отличаются от симметричной задачи на величину ~ 75 % от оптимального решения [14-16] и на ~ 57 % от несимметричной задачи [14].
Перейдем теперь к ЗК (мин). Поскольку описание алгоритма решения ЗК (2.1)-(2.4) дает достаточно высокую нижнюю границу 99,0 % от точного решения задачи [8, ч. III, IV; 10], экспериментальные оценки), то поступаем следующим образом. Решаем ЗК в форме (2.1)-(2.4) алгоритмами, предложенными в [8, ч. III, IV; 12, разделы 3-5]. Эта двухиндексная модель обеспечивает часто только высокую нижнюю границу. Далее следует для получения решения ЗК применять блок ветвления методом ветвей и границ. Нижние границы для этой двухиндексной модели могут быть улучшены без блока ветвления за счет применения одноиндексной модели [11, 12]. Теперь переходим к детальному изложению последнего алгоритма.
Пусть X — множество городов в ЗК с элементами i = 0,1,... ,T. Тогда задача оптимального управления с одномерным аргументом ЗК (мин) записывается в виде:
(2.5)
(2.6) (2.7)
Zi(t + l) = Zi(t)+ßi(u(t)) (t = 0,1,...,Т-1, ?; = 1,Т);
y(t + 1)= u(t) (t = 0,1 ,...,T - 1), y(0)= yo, y(T)= yo;
(2.8)
(2.9)
2i(0) = 0, Zi(T) = 1 У г = 1,T,
T-1
(2.10)
J = Y1 °y(t)u(t) ^ min •
Здесь у0 = у(0) — начальный город, у(Ь + 1) — номер города, включаемого в решение на шаге Ь +1 процесса; и(Ь) — город, в который переходит коммивояжер на шаге Ь + 1; + 1) отслеживает шаг процесса и количество городов, в которых побывал коммивояжер к данному шагу процесса (без отслеживания порядка, в котором посещались эти города) — на это указывает индекс в круглых скобках; индекс г внизу указывает на город, в котором находится коммивояжер на данном шаге процесса; Су^^ — расстояние между двумя соседними городами.
Пусть П — класс функций р(Ь, у, г) € П, отображающих прямое произведение Т х У х 2 в У, 2 и заданных в виде
Т 1
(2.11) ф,,у,х)=р1{1)у + ^М)гг + 72^)у\
г=1
где г = 21, гт-
Тогда функции Я(Ь, у, г, и) и С[у, г(Ь € Б)] согласно (3.6) из [12] принимают вид:
Т
2/
(2.12)
Я(Ь, у, г, и) = р1(Ь + 1)и + ^ * [р2(Ь + 1) - р2(Ь)] +
г=1
Т 1 1 + + + -а(1 + 1)и2 - р1(1)у - -а(1)у2 -Су«№),
2 ' 1 4 2 г=1
С [у, г(Т)] = у [р1(Т) - р1(0)] +
(213) т _
+ №№ + т/ ИТ) - <7(0)] .
г=1
Условия существования = шт^у« Я(Ь, у, и, г) из (3.6) в [12] накладывают на р € П следующие условия:
(2.14) Рг^ + 1) =рЦг) =Р1 V г = 1,3", ¿ = 0,1,...,Т-1. Учитывая (2.14), получим из (2.12)
Т
Е(г,у,и) = р1(Ь + 1)и + ^ р2/Зг(и(Ь)) +
(2.15) г=1
+ 1 )и2 - рН^у - \а{г)у2 - Су{г)и(г) ■
Вместе с тем если в (2.13) положить в силу произвольности функции р(Ь, у, г)
(2.16) Р2г(Т)=Р2г( 0), г = 17Т, то из (2.13) получим
(2.17) С[у] = у[р\Т) - р\0)] + \у2[а{Т) ~ <7(0)].
Таким образом, в силу (2.14) и (2.16) функции R и G не зависят от z.
Условия существования minyeyt R(t, y, u) накладывают условия Ryy ^ 0, откуда получаем ограничения на выбор функции <(t) в виде
(2.18) <(t) < 0 V t = 0,1 ,...,T — 1.
Соответственно условия существования maxyew G(y) накладывают свои условия Gyy ^ 0, откуда получим дополнительное ограничение на выбор <(t) в виде
(2.19) <(T) - <г(0) < 0. Итак, из (2.17) получим
(2.20) 0 = у1[р\Т) - ^(0)] + \у2[а{Т) - а{0)],
где y = argmaxyew G [y (TT)] при дополнительных ограничениях (2.16) и (2.19) на выбор pf(t) (i = 1, Т) и a(t) в концевых точках. Из (2.15) получим
T
ß(t) = p1(t + 1)u + Y, Pißi(u(t)) +
(2.21) i=i
+-cr(t + l)ü2 - pHtfy - -a{t)f - cy{t)ü{t),
где y = arg minyeyy R(t,y,u), u = argmaxueyu R(t,y,u) при дополнительных
ограничениях (2.14) и (2.18) на выбор (i = 1 , Т) и a(t) при t = 0,1,...
... ,T — 1. С учетом (2.20) и (2.21) окончательное значение l-функционала в соответствии с (3.6) из [12] будет
Т-1
(2.22) l(p,<) = е — ^ Mt),
t=0
где p = (p1,p1,... ,pT). В силу теоремы 1 из [12] при любом наборе (p,<) l('p,<) ^ minD J, где D — множество допустимых (y,u), удовлетворяющих ограничениям (2.1)—(2.4). Итак, основные конструкции, входящие в (3.6) из [12], для модели (2.5)-(2.10) построены.
Теперь приведем собственно итерационный алгоритм улучшения сверху [6, 17]. Тривиальные вычисления производных типа Qy.§y ., Эу &у 3Десь опускаются.
1. Задается допустимое управление u0(t,y) = u0(t). В качестве u0(t) может быть взято любое допустимое управление, полученное, например, алгоритмом ближайшей точки или согласно выражению
(2.23) u0(t, y) = arg max R(t, y, u).
Здесь Я(Ь,у,п) определяется выражением (2.15), а алгоритму ближайшей точки и некоторым его модификациям соответствует свое задание функции
2. Интегрируются уравнения:
(2.24а) у°(г + 1)= п°(г) (* = 0,1,...,Т - 1),
(2.24б) у0(0) = уо, у°(Т) = Уо;
(2.25а) z^t + 1) = zV(t)+Pi(uu(t)) (t = 0,1,..., 3 - 1, i = l,T),
1, если i = uo(t),
(2.25б) &(и°(*)) = { ,, — . ,
у 7 у у " у 0, если г = «°(£);
(2.25в) ¿9(0) = 0, (Г) = 1 V?: = Т/Г.
Определяются значения (у°(£), и°(£)) = и° и затем вычисляется по формуле (2.10) Л(и°).
3. Составляется гамильтониан
н (г,р(г + 1),у(г),п(г)) = + 1)и +
(2.26) ^
+ Pi(í + 1)&(1) + вг(м(^))] - бу(4)„(4).
г=1
Из уравнений
(2.27а) ?<,(*) = + !),*/(*), Л*)) = ,
(2.27б) р°(3) = 0,
д
(2 28а) = + 1), ?/(*), Л*)) = + 1)
= 0,1,..., Г-1, ¿=170,
(2.286) j9i(T) = 0 (-¿ = 1,3),
определяется вектор = (po{t),Pi{t)) (г = 1, Т). 4. Решаются уравнения:
(2.29а) -0to(t) = ¿o(t) (t = 0,1,...,T - 1),
(2.296) <7ii(i + 1) = <Tii(i) + 5i(t) (i = 0,1,..., 3 — 1; i= Т/Г),
(2.30а) aoo(TT) - aoo(0) = -ao,
(2.306) &u(T) - агг(0) = -a, (i = 1, 3),
где ¿о(^) и ^г(^) ('- = 1)3) — заданные неотрицательные функции, од и щ (г = 1,3) — заданные неотрицательные числа. Для определенности можно положить, как в [17], все 8о(1), равными некоторым не зависящим
от времени постоянным 8о(1) = 8о, 8^1) = 8 = 0,1,..., 3 — 1, г = 1,3), а все щ (г = 1,3) — некоторым числам. Из решения уравнений (2.29)
5 Автоматика и телемеханика, № 3 129
и (2.30) находятся = (<тоо(£), сгц(1)) (г,;) = 1 , Т) и строится новая функ-
ция ^(Ь,у) € П по формуле
т 1 т
(2.31) ф,у) = + ^ Е ак1(№Ук(г)АУ1(г),
г=1 к,1=1
где Аук(г) = ук(г) - уЦг), = (к = 1 ,Т) — траектория, соответ-
ствующая допустимому управлению и0(£).
5. Для новой функции у) € П повторяем шаги 1 и 2, находим г = = (у(£),и(£)) и 3(ад). Если функционал не улучшился, то увеличиваем 50, 5 и ао, а и возвращаемся к шагу 4. Описание одной итерации алгоритма завершено. Алгоритм заканчивает работу, если в процессе реализации шага 5 изменения 8о(1), ао и оц (г = 1 , Т) не приводят к улучшению функцио-
нала, т.е. 3(г3) = 3где в — номер итерации улучшения. В этом случае алгоритм дает следующую информацию: г) = (у(£),и(£)) и 3(г)).
Представленный алгоритм является наиболее общим среди итеративных алгоритмов, осуществляющих приближение сверху к оптимальному значению функционала и использующих результаты теории
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.