Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях
Розроблено новий алгоритм повторюваного табу для розв’язання квадратичної задачі про призначення. Проведене порівняльне дослідження цього алгоритму з найкращими на даний час алгоритмами розв’язання цієї задачі показало його конкурентоспроможність як за швидкодією, так і за можливістю отримання кращи...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2017 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/144721 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях / П.В. Шило // Кибернетика и системный анализ. — 2017. — Т. 53, № 2. — С. 163–167. — Бібліогр.: 18 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859591190188392448 |
|---|---|
| author | Шило, П.В. |
| author_facet | Шило, П.В. |
| citation_txt | Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях / П.В. Шило // Кибернетика и системный анализ. — 2017. — Т. 53, № 2. — С. 163–167. — Бібліогр.: 18 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розроблено новий алгоритм повторюваного табу для розв’язання квадратичної задачі про призначення. Проведене порівняльне дослідження цього алгоритму з найкращими на даний час алгоритмами розв’язання цієї задачі показало його конкурентоспроможність як за швидкодією, так і за можливістю отримання кращих розв’язків.
Разработан новый алгоритм повторяемого табу для решения квадратичной задачи о назначениях. Проведенное сравнительное исследование данного алгоритма с лучшими в настоящее время алгоритмами решения этой задачи показало его конкурентоспособность как по быстродействию, так и по возможности получения лучших решений.
A novel Repeated Iterated Tabu Search for quadratic assignment problem is presented. We compare our approach to the state-of-the-art techniques and demonstrate its advantages with respect to run times and solution quality.
|
| first_indexed | 2025-11-27T14:27:46Z |
| format | Article |
| fulltext |
ÓÄÊ 519.854
Ï.Â. ØÈËÎ
ÏÎÂÒÎÐßÅÌÛÉ ÈÒÅÐÈÐÎÂÀÍÍÛÉ ÀËÃÎÐÈÒÌ ÒÀÁÓ
ÄËß ÐÅØÅÍÈß ÊÂÀÄÐÀÒÈ×ÍÎÉ ÇÀÄÀ×È Î ÍÀÇÍÀ×ÅÍÈßÕ
Àííîòàöèÿ. Ðàçðàáîòàí íîâûé àëãîðèòì ïîâòîðÿåìîãî òàáó äëÿ ðåøåíèÿ
êâàäðàòè÷íîé çàäà÷è î íàçíà÷åíèÿõ. Ïðîâåäåííîå ñðàâíèòåëüíîå èññëåäîâà-
íèå äàííîãî àëãîðèòìà ñ ëó÷øèìè â íàñòîÿùåå âðåìÿ àëãîðèòìàìè ðåøå-
íèÿ ýòîé çàäà÷è ïîêàçàëî åãî êîíêóðåíòîñïîñîáíîñòü êàê ïî áûñòðîäåé-
ñòâèþ, òàê è ïî âîçìîæíîñòè ïîëó÷åíèÿ ëó÷øèõ ðåøåíèé.
Êëþ÷åâûå ñëîâà: êâàäðàòè÷íàÿ çàäà÷à î íàçíà÷åíèÿõ, òàáó, âû÷èñëèòåëü-
íûé ýêñïåðèìåíò, ñðàâíèòåëüíîå èññëåäîâàíèå àëãîðèòìîâ.
Êâàäðàòè÷íàÿ çàäà÷à î íàçíà÷åíèÿõ (quadratic assignment problem, QAP) âïåð-
âûå ñôîðìóëèðîâàíà â ðàáîòå [1]. Îíà èìååò ìíîãî÷èñëåííûå ïðàêòè÷åñêèå
ïðèëîæåíèÿ, ñâÿçàííûå ñ ðàçìåùåíèåì ðàçëè÷íûõ îáúåêòîâ, áàëàíñèðîâàíèåì
òóðáèí, àíàëèçîì èçîáðàæåíèé è äð. [1–7].
Ðàññìàòðèâàåìàÿ QAP ÿâëÿåòñÿ NP-ñëîæíîé çàäà÷åé äèñêðåòíîé îïòèìèçà-
öèè, ê òîìó æå î÷åíü òðóäíîé â âû÷èñëèòåëüíîì îòíîøåíèè. Îòìåòèì òàêæå,
÷òî åå ÷àñòíûì ñëó÷àåì åñòü çàäà÷à êîììèâîÿæåðà.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ñîäåðæàòåëüíàÿ ïîñòàíîâêà çàäà÷è QAP òàêîâà. Äàíî n îáúåêòîâ, êîòîðûå
íåîáõîäèìî ðàçìåñòèòü â n ðàçëè÷íûõ ëîêàöèÿõ (ìåñòàõ íàçíà÷åíèÿ). Èçâåñò-
íû âåëè÷èíû ïîòîêîâ ðåñóðñîâ aij ìåæäó îáúåêòàìè i è j, i j n, , ,� �1 ,
è ðàññòîÿíèÿ brs ìåæäó ëîêàöèÿìè r è s, r s n, , ,� �1 . Òðåáóåòñÿ íàéòè òàêîå
ðàñïðåäåëåíèå îáúåêòîâ ïî ëîêàöèÿì, ÷òîáû ñóììà ðàññòîÿíèé, óìíîæåííàÿ
íà ñîîòâåòñòâóþùèå ïîòîêè, áûëà ìèíèìàëüíîé.
Ñëåäîâàòåëüíî, ìàòåìàòè÷åñêóþ ïîñòàíîâêó çàäà÷è QAP ìîæíî ñôîðìóëè-
ðîâàòü ñëåäóþùèì îáðàçîì: íàéòè
min ( )
�
� ��
�
��
� ��
�n
i j
f a bij
j
n
i
n
11
,
ãäå A aij[ ]� è B brs[ ]� — êâàäðàòíûå ìàòðèöû ïîðÿäêà n, �n — ìíîæåñòâî
âñåõ ïåðåñòàíîâîê { , , }1 � n è � i çàäàåò íîìåð ëîêàöèè îáúåêòà i.
Êâàäðàòè÷íûå çàäà÷è î íàçíà÷åíèÿõ óäàåòñÿ òî÷íî ðåøèòü òîëüêî äëÿ ìà-
ëûõ ðàçìåðíîñòåé. Ïðåäëîæåííàÿ â [7] òåñòîâàÿ çàäà÷à ñ 36 ïåðåìåííûìè òî÷íî
íå ðåøåíà äî ñèõ ïîð. Â ñâÿçè ñ ýòèì àêòóàëüíû ðàçðàáîòêà, èññëåäîâàíèå íîâûõ
è óñîâåðøåíñòâîâàíèå ñóùåñòâóþùèõ ïðèáëèæåííûõ àëãîðèòìîâ ðåøåíèÿ
çàäà÷è QAP.
ÏÐÅÄËÀÃÀÅÌÛÉ ÀËÃÎÐÈÒÌ
Âû÷èñëèòåëüíàÿ ñëîæíîñòü çàäà÷è QAP îáóñëîâëåíà áîëüøèì îáúåìîì âû-
÷èñëåíèé, íåîáõîäèìûõ äëÿ ïîëó÷åíèÿ çíà÷åíèÿ öåëåâîé ôóíêöèè (ïîðÿäêà
O n( )2 ) è èññëåäîâàíèÿ îêðåñòíîñòè òåêóùåãî ðåøåíèÿ. Îòìåòèì, ÷òî â àëãî-
ðèòìàõ äëÿ çàäà÷è QAP ðåøåíèå îáû÷íî ïðåäñòàâëÿåòñÿ â âèäå íåêîòîðîé ïå-
ðåñòàíîâêè � ��n , à åãî îêðåñòíîñòü N ( )� âêëþ÷àåò âñå ïåðåñòàíîâêè, ïîëó-
÷åííûå ïóòåì îáìåíà ëîêàöèÿìè ìåæäó âñåìè ïàðàìè îáúåêòîâ. Òàêèì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 2 163
© Ï.Â. Øèëî, 2017
îáðàçîì, îêðåñòíîñòü ñîäåðæèò Cn
2 1� ïåðåñòàíîâêó, à âû÷èñëåíèå çíà÷åíèé èõ
öåëåâûõ ôóíêöèé òðåáóåò ïîðÿäêà O n( )4 îáúåìà âû÷èñëåíèé. Ïðè n � 100
ïðîâåäåíèå õîòÿ áû n2 èòåðàöèé ëîêàëüíîãî ïîèñêà óæå ñòàíîâèòñÿ òðóäíîé
âû÷èñëèòåëüíîé çàäà÷åé. Ïîýòîìó âàæíî ïðèìåíÿòü ïðåäëîæåííûå â [8, 9]
ñïîñîáû ïåðåñ÷åòà ïðèðàùåíèé öåëåâîé ôóíêöèè ïðè îáìåíå ëîêàöèÿìè. Ýòî
ïîçâîëÿåò ñíèçèòü äî O n( )3 îáúåì âû÷èñëåíèé, íåîáõîäèìûõ äëÿ èññëåäîâà-
íèÿ îêðåñòíîñòè. Åãî ìîæíî óìåíüøèòü åùå áîëüøå â ñëó÷àå ðàçðåæåííûõ è
ñèììåòðè÷íûõ ìàòðèö.
Äàííûå ðàññóæäåíèÿ ñêîðåå îòíîñÿòñÿ ê âû÷èñëèòåëüíîé ñëîæíîñòè, ÷åì
ê îïòèìèçàöèîííîé. Îïðåäåëåííûé âêëàä â îïòèìèçàöèîííóþ ñëîæíîñòü çàäà÷è
QAP âíîñèò âûáîð õîäîâ ëîêàëüíûõ àëãîðèòìîâ — îáìåí ìåæäó îáúåêòàìè ñâî-
èìè ëîêàöèÿìè. ßñíî, ÷òî òàêîé âûáîð èñêóññòâåííûé, ñëàáî ñâÿçàí ñ ðåøàåìîé
çàäà÷åé è ñ÷èòàåòñÿ õóäøèì äëÿ çàäà÷è êîììèâîÿæåðà. Îäíàêî áîëüøèíñòâî çà-
äà÷ QAP â îïòèìèçàöèîííîì ïëàíå ïðîñòû è ðåøàþòñÿ ñîâðåìåííûìè àëãîðèò-
ìàìè. Òåñòîâûå çàäà÷è taiXX [8] â ñèëó èõ ãåíåðàöèè ïðåäñòàâëÿþò îñîáóþ
ñëîæíîñòü.
Èç èññëåäîâàíèÿ òåñòîâûõ çàäà÷ â [10] ñëåäóåò, ÷òî äëÿ áîëüøèíñòâà çàäà÷
taiXX «ëàíäøàôò» öåëåâîé ôóíêöèè õàðàêòåðèçóåòñÿ ìíîæåñòâîì íåñâÿçàííûõ ëî-
êàëüíûõ îïòèìóìîâ, îòðèöàòåëüíîé êîððåëÿöèåé ìåæäó çíà÷åíèåì öåëåâîé ôóíê-
öèè ëîêàëüíîãî îïòèìóìà è åãî ðàññòîÿíèåì äî ãëîáàëüíîãî îïòèìóìà. Ïîýòîìó íå-
îáõîäèì àëãîðèòì ñ ñèëüíîé äèâåðñèôèêàöèåé ïîèñêà, ÷òî ïîçâîëèò áûñòðî íàõî-
äèòü îòäåëüíî ðàñïîëîæåííûå îáëàñòè ëîêàëüíûõ îïòèìóìîâ è òùàòåëüíî èõ
èññëåäîâàòü. Â ðàáîòå [11] ïðåäëîæåíà ñõåìà âîçìóùåíèÿ ïåðåìåííûõ, íàçâàííàÿ
âïîñëåäñòâèè èòåðèðîâàííîñòüþ. Îíà óñïåøíî èñïîëüçóåòñÿ äëÿ äèâåðñèôèêàöèè
ïîèñêà ðåøåíèÿ. Äëÿ òùàòåëüíîãî èññëåäîâàíèÿ ðàéîíà ëîêàëüíîãî îïòèìóìà ðàç-
ðàáîòàí ïîâòîðÿåìûé àëãîðèòì òàáó, ðàçíîâèäíîñòü êîòîðîãî ïîêàçàëà õîðîøèå ðå-
çóëüòàòû ïðè ðåøåíèè çàäà÷ WMaxCut [12]. Ýòè ïðåäëîæåíèÿ îáúåäèíåíû â ðàñ-
ñìàòðèâàåìîì àëãîðèòìå RITS (ïîâòîðÿåìûé èòåðèðîâàííûé òàáó-ïîèñê).
Äàëåå ïðèâåäåí àëãîðèòì RITS â âèäå òàêîé ïðîöåäóðû:
procedure RITS (xbest , ntm_ar, dd_ar)
1. f best � ; çàäàíèå íà÷àëüíûõ äàííûõ
2. while (íå âûïîëíåí êðèòåðèé îñòàíîâà){
3. fmin impr� �; false;
4. for (� � 0; � �
max ; � � �){
5. tmax tm ar� _ [ ];�
6. for (t � 0; t tmax
; t � �){
7. x � disturbation solution(xbest , dd[ ]� )
8. x x� ReTS( )
9. if ( f x fbest( )
){ fbest f� ; x xbest � ; break;}
10. }
11. }
12. }
Çäåñü çíà÷åíèå tm ar_ [ ]0 � . Ïîýòîìó öèêë èòåðèðîâàííîñòè (ñòðîêè 4–12)
áóäåò âûïîëíÿòüñÿ ïðè � � 0 òîëüêî ïðè êàæäîì óëó÷øåíèè xbest (ñòðîêà 9). Åñëè
çàìåíèòü ñòðîêó 7 ñòðîêîé «x � disturbation solution (xmin , dd [�])», à ñòðîêó 9 —
ñòðîêîé «if ( ( ) )f x fmin
{ fmin f� ; x xmin � ; break;}», òî ïîëó÷èì áîëåå îáùóþ
ñõåìó, êîãäà öèêë èòåðèðîâàííîñòè âûïîëíÿåòñÿ ïðè êàæäîì óëó÷øåíèè xmin .
 ñòðîêå 7 ïðîèñõîäèò âîçìóùåíèå ðåøåíèÿ xbest . Áóäåì ñ÷èòàòü, ÷òî âîçìóùàå-
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 2
ìîå ðåøåíèå çàïèñàíî â ìàññèâ â ÿ÷åéêàõ 0 1, ,�
n , ãäå n — ðàçìåðíîñòü ðåøàå-
ìîé çàäà÷è. Òîãäà èç ÷èñåë, çàïèñàííûõ â ÿ÷åéêàõ 0, , [ ]� dd � , ñëó÷àéíî ãåíåðè-
ðóåòñÿ ïåðåñòàíîâêà, ðàâíîìåðíî ðàñïðåäåëåííàÿ íà ìíîæåñòâå âñåõ òàêèõ ïåðå-
ñòàíîâîê è âõîäÿùàÿ â âîçìóùåííîå ðåøåíèå.
Îïèøåì òåïåðü ïðåäëàãàåìûé ïîâòîðÿåìûé àëãîðèòì òàáó ReTS.
procedure ReTS(x)
1. x xm � ; istep step� � 0; M m i Ci n� � �{ , , , , }1 2 2 ;
2. nfail � 0; Çàäàíèå nbstep.
3. istep step� ; x xm� ; ch i( ) �
, i n� �1 2 2, , , ; Çàäàíèå ìàññèâà tn i k[ , ], i k n, , ,� �1 2;
4. while ( )nfail maxnfail
{
5. � � ;
6. for k � 1 to | |M {
7. i nl k� 1[ ]; j nl k� 2[ ]
8. if (( step ch i x j tn i x j
[ , [ ]] [ , [ ]]AND step ch j x i tn j x i
[ , [ ]] [ , [ ]]) OR
f x g x f xk m( ) ( ) ( )�
){
9. if (g xk ( )
�) {� � g xk ( ) ; kk k� }
10. }
11. }
12. i nl kk� 1[ ]; j nl kk� 2[ ]
13. ch i x i step[ , [ ]] � ; ch j x j step[ , [ ]] � ; Çàäàíèå âåëè÷èí tn i x i ch j x j[ , [ ]], [ , [ ]].
14. k x i� [ ]; x i x j[ ] [ ]� ; x j k[ ] � ;
15. if ( ( ) (f x f xm
){x xm � ; goto to line2;}
16. step step� � 1;
17. if (step istep nbstep
� ){nfail nfail� � 1; goto to line3;}
18. }
19. x xm� ;
20. return x ;
Çäåñü èñïîëüçîâàíû òàêèå îáîçíà÷åíèÿ:
� M — ìíîæåñòâî õîäîâ àëãîðèòìà òàáó, ñîñòîÿùåå èç âñåõ ïàð ëîêàöèé.
 ïðîöåññå õîäà îáúåêòû, íàõîäÿùèåñÿ â ýòèõ ëîêàöèÿõ, ìåíÿþòñÿ ìåñòàìè;
� ch i r[ , ] — ïîñëåäíèé øàã àëãîðèòìà òàáó, êîãäà â ëîêàöèè i íàõîäèëñÿ îáú-
åêò r;
� tn i r[ , ] — êîëè÷åñòâî øàãîâ àëãîðèòìà òàáó, â òå÷åíèå êîòîðûõ çàïðåùåí
âîçâðàò îáúåêòà r â ëîêàöèþ i, tn i r tmin[ , ] � � �� �, i r n, , ,� �1 2 , � — ñëó÷àéíàÿ
âåëè÷èíà, ðàâíîìåðíî ðàñïðåäåëåííàÿ íà èíòåðâàëå [0, 1];
� nbstep — ìàêñèìàëüíîå êîëè÷åñòâî øàãîâ àëãîðèòìà òàáó áåç óëó÷øåíèÿ
ðåøåíèÿ xm , çàäàåòñÿ ñëåäóþùèì îáðàçîì: if ( f x f xm best( ) ( )� ) nbstep nbstep� 1;
else nbstep nbstep� 2, ãäå xbest — íàéäåííîå íàèëó÷øåå ðåøåíèå;
� maxnfail — ìàêñèìàëüíîå êîëè÷åñòâî ïîïûòîê óëó÷øåíèÿ ðåøåíèÿ xm ,
çàäàåòñÿ ñëåäóþùèì îáðàçîì: if ( f x f xm best( ) ( )� ) maxnfail nf� 1; else
maxnfail nf� 2;
� nl k1[ ] è nl k2[ ] — íîìåðà ëîêàöèé â õîäå k.
ÐÅÇÓËÜÒÀÒÛ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÝÊÑÏÅÐÈÌÅÍÒÎÂ
 ðàáîòå [8] èìååòñÿ îáøèðíûé íàáîð òåñòîâûõ çàäà÷ QAP, êîòîðûé âåñüìà
ïîïóëÿðåí ñðåäè èññëåäîâàòåëåé è øèðîêî èñïîëüçóåòñÿ èìè.
 îïòèìèçàöèîííîì ïëàíå çàäà÷è òèïà taiÕÕà íàèáîëåå òðóäíûå, ïîýòîìó
èìåííî ñ íèìè ïðîâåäåíû âû÷èñëèòåëüíûå ýêñïåðèìåíòû.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 2 165
Ïðåäëàãàåìûé àëãîðèòì ðåàëèçîâàí íà ÿçûêå Ñ++, ñðåäà Microsoft Visual
Studio 2012, âñå âû÷èñëèòåëüíûå ýêñïåðèìåíòû ïðîâîäèëèñü ñ èñïîëüçîâàíèåì
PC ñ Intel® Core QUAD CPU Q9550 2.83GHz è 8.0GB îïåðàòèâíîé ïàìÿòè. Êàæ-
äàÿ çàäà÷à ðåøàëàñü 10 ðàç (íåçàâèñèìûå èñïûòàíèÿ ïðè ðàçëè÷íûõ çíà÷åíèÿõ
äàò÷èêà ïñåâäîñëó÷àéíûõ ÷èñåë), âûäåëåííûé ëèìèò âðåìåíè äëÿ îäíîé ïîïûò-
êè ðåøåíèÿ ñîñòàâëÿë 2 ÷àñà. Äàëåå ïðèâåäåíû çíà÷åíèÿ ïàðàìåòðîâ àëãîðèòìà
RITS, êîòîðûå èñïîëüçîâàëèñü â ýêñïåðèìåíòàõ: tm ar_ [ ] ,0 � tm ar_ [ ]� � 9,
� �� �
1 1, , max ; �max �10; dd n[ ]0 1�
, dd n[ ] /� �� � 10, � �� �
1 1, , max ;
tmin n� �007. ; � � �0 15. n; nbstep1 27� ; nbstep n2 2
� ; nf 1 27� ; nf 2 81� .
 ðàáîòå [10] ïðîâåäåíû ïîäîáíûå ýêñïåðèìåíòàëüíûå èññëåäîâàíèÿ, ïîýòî-
ìó îíè èñïîëüçîâàíû äëÿ ñðàâíåíèÿ ñ ïðåäëàãàåìûì àëãîðèòìîì. Âûáðàíî
øåñòü ñîâðåìåííûõ àëãîðèòìîâ, êîòîðûå ïîêàçûâàþò õîðîøèå ðåçóëüòàòû:
� Cooperative Parallel Tabu Search (CPTS) [13];
� Iterated Tabu Search (ITS) [14];
� Improved Hybrid Genetic Algorithm (IHGA) [15];
� Breakout Local Search (BLS) [16];
� Breakout Memetic Algorithm (BMA) [10];
� Population-based Iterated Local Search (PILS) [17].
Îòìåòèì, ÷òî àëãîðèòì èç [18] íå âêëþ÷åí äëÿ ñðàâíåíèÿ, òàê êàê îí èññëå-
äîâàëñÿ ïðè äðóãèõ óñëîâèÿõ.
 òàáë. 1 ïðèâåäåíû ðåçóëüòàòû ñðàâíèòåëüíîãî èññëåäîâàíèÿ óïîìÿíóòûõ
àëãîðèòìîâ ñ ïðåäëîæåííûì àëãîðèòìîì RITS, ãäå BKS — èçâåñòíûé èç ðàáî-
òû [14] ðåêîðä (íàèìåíüøåå çíà÷åíèå öåëåâîé ôóíêöèè), �avg — îòêëîíåíèå
(â ïðîöåíòàõ) ñðåäíåãî çíà÷åíèÿ öåëåâîé ôóíêöèè, ïîëó÷åííîãî ñ ïîìîùüþ äàí-
íîãî àëãîðèòìà èç 10 íåçàâèñèìûõ ïðîñ÷åòîâ, îò BKS.  ñêîáêàõ ðÿäîì ñî çíà÷å-
íèåì �avg óêàçàíî ÷èñëî íàéäåííûõ ðåêîðäîâ ïðè 10 ïîïûòêàõ ðåøåíèÿ çàäà÷è.
Èç àíàëèçà ðåçóëüòàòîâ ýêñïåðèìåíòàëüíûõ ðàñ÷åòîâ ìîæíî ñäåëàòü âûâîä
î âûñîêîé ýôôåêòèâíîñòè è êîíêóðåíòîñïîñîáíîñòè ïîâòîðÿåìîãî èòåðèðîâàí-
íîãî àëãîðèòìà òàáó äëÿ ðåøåíèÿ êâàäðàòè÷íîé çàäà÷è î íàçíà÷åíèÿõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Koopmans T.C., Beckmann M.J. Assignment problems and the location of economic activities.
Econometrica. 1957. Vol. 25. P. 53–76.
2. Burkard R.E. Quadratic assignment problems. European J. of Oper. Res. 1984. Vol. 15. P. 283–289.
3. Eiselt H.A., Laporte G. A Combinatorial optimization problem arising in dartboard design. J. of the
Oper. Res. Society. 1991. Vol. 42. P. 113–118.
4. Elshafei A.E. Hospital layout as a quadratic assignment problem. Oper. Res. Quarterly. 1977.
Vol. 28. P. 167–179.
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 2
Ò à á ë è ö à 1
Çàäà÷à BKS
Çíà÷åíèå �avg äëÿ àëãîðèòìîâ
RITS CPTS ITS IHGA BLS BMA PILS
tai40a 3139370 0.03(6) 0.148(1) 0.210(1) 0.209(1) 0.022(7) 0.059(2) 0.28(0)
tai50a 4938796 0.04(6) 0.440(0) 0.373(0) 0.262(0) 0.157(2) 0.131(2) 0.663(0)
tai60a 7205962 0.142(1) 0.476(0) 0.330(1) 0.583(0) 0.251(1) 0.144(2) 0.82(0)
tai80a 13499184 0.41(0) 0.691(0) 0.494(0) 0.756(0) 0.517(0) 0.426(0) 0.927(0)
tai100a 21052466 0.33(0) 0.589(0) 0.427(0) 0.606(0) 0.430(0) 0.405(0) 1.027(0)
Ñðåäíåå
çíà÷åíèå
— 0.231 0.469 0.367 0.483 0.275 0.233 0.413
5. Nugent Ch.E., Vollmann Th.E., Ruml J. An experimental comparison of techniques for the
assignment of facilities to locations. Oper. Res. 1968. Vol. 16. P. 150–173.
6. Finke G., Burkard R.E., Rendl F. Quadratic assignment problems. Annals of Discrete Math. 1987.
Vol. 31. P. 61–82.
7. Steinberg L. The backboard wiring problem: a placement algorithm. SIAM Review. 1961. Vol. 3.
P. 37–50.
8. Taillard E. Robust taboo search for the quadratic assignment problem. Parallel Computing. 1991.
Vol. 17. P. 443–455.
9. Podolsky S., Zorin Yu. O(1) delta part computation technique for the quadratic assignment problem.
System Research & Information Technologies. 2015. Vol. 2. P. 112–121.
10. Benlic U., Hao J.K. Memetic search for the quadratic assignment problem. Expert Systems with
Applications. 2015. Vol. 42, N 1. P. 584–595.
11. Shylo V.P. The method of global equilibrium search. Cybernetics and Systems Analysis. 1999.
Vol. 35, N 1. P. 68–74.
12. Øèëî Â.Ï., Øèëî Î.Â., Ðîùèí Â.À. Ìåòîä ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà ðåøåíèÿ çàäà÷è
î ìàêñèìàëüíîì âçâåøåííîì ðàçðåçå ãðàôà. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2012. ¹ 4.
Ñ. 101–105.
13. James T., Rego C., Glover F. A cooperative parallel tabu search algorithm for the quadratic
assignment problem. European J. of Oper. Res. 2009. Vol. 195, N 3. P. 810–826.
14. Misevicius A., Kilda B. Iterated tabu search: An improvement to standard tabu search. Information
Technology and Control. 2006. Vol. 35, N 3. P. 187–197.
15. Misevicius A. An improved hybrid genetic algorithm: New results for the quadratic assignment
problem. Knowledge Based Systems. 2004. Vol. 17, N 2–4. P. 65–73.
16. Benlic U., Hao J.K. Breakout local search for the quadratic assignment problem. Applied Math. and
Computation. 2013. Vol. 219, N 9. P. 4800–4815.
17. Stutzle T. Iterated local search for the quadratic assignment problem. European J. of Oper. Res.
2006. Vol. 174, N 3. P. 1519–1539.
18. Øèëî Â.Ï., Êîðåíêåâè÷ Ä.ª., Ëÿøêî Â.². Ïðî îïòèì³çàö³éíó çàäà÷ó íà ïåðåñòàíîâêàõ. Íàóêîâ³
çàïèñêè ÍàÓÊÌÀ. Ñåð.: Êîìï’þòåðí³ íàóêè. 2008. Ò. 86. Ñ. 21–24.
Íàä³éøëà äî ðåäàêö³¿ 22.12.2016
Ï.Â. Øèëî
ÏÎÂÒÎÐÞÂÀÍÈÉ ²ÒÅÐÎÂÀÍÈÉ ÀËÃÎÐÈÒÌ ÒÀÁÓ ÄËß ÐÎÇÂ’ßÇÀÍÍß ÊÂÀÄÐÀÒÈ×Íί
ÇÀÄÀײ ÏÐÎ ÏÐÈÇÍÀ×ÅÍÍß
Àíîòàö³ÿ. Ðîçðîáëåíî íîâèé àëãîðèòì ïîâòîðþâàíîãî òàáó äëÿ ðîçâ’ÿçàííÿ
êâàäðàòè÷íî¿ çàäà÷³ ïðî ïðèçíà÷åííÿ. Ïðîâåäåíå ïîð³âíÿëüíå äîñë³äæåííÿ
öüîãî àëãîðèòìó ç íàéêðàùèìè íà äàíèé ÷àñ àëãîðèòìàìè ðîçâ’ÿçàííÿ ö³º¿
çàäà÷³ ïîêàçàëî éîãî êîíêóðåíòîñïðîìîæí³ñòü ÿê çà øâèäêî䳺þ, òàê ³ çà
ìîæëèâ³ñòþ îòðèìàííÿ êðàùèõ ðîçâ’ÿçê³â.
Êëþ÷îâ³ ñëîâà: êâàäðàòè÷íà çàäà÷à ïðî ïðèçíà÷åííÿ, òàáó, îá÷èñëþâàëü-
íèé åêñïåðèìåíò, ïîð³âíÿëüíå äîñë³äæåííÿ àëãîðèòì³â.
P.V. Shylo
SOLVING THE QUADRATIC ASSIGNMENT PROBLEM BY THE REPEATED ITERATED
TABU SEARCH METHOD
Abstract. A novel Repeated Iterated Tabu Search for quadratic assignment
problem is presented. We compare our approach to the state-of-the-art techniques
and demonstrate its advantages with respect to run times and solution quality.
Keywords: quadratic assignment problem, tabu search, computing experiment,
a comparative study of algorithms.
Øèëî Ïåòð Âëàäèìèðîâè÷,
ìëàäøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, Êèåâ,
e-mail: petershylo@gmail.com.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 2 167
|
| id | nasplib_isofts_kiev_ua-123456789-144721 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-27T14:27:46Z |
| publishDate | 2017 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шило, П.В. 2019-01-02T16:25:37Z 2019-01-02T16:25:37Z 2017 Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях / П.В. Шило // Кибернетика и системный анализ. — 2017. — Т. 53, № 2. — С. 163–167. — Бібліогр.: 18 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/144721 519.854 Розроблено новий алгоритм повторюваного табу для розв’язання квадратичної задачі про призначення. Проведене порівняльне дослідження цього алгоритму з найкращими на даний час алгоритмами розв’язання цієї задачі показало його конкурентоспроможність як за швидкодією, так і за можливістю отримання кращих розв’язків. Разработан новый алгоритм повторяемого табу для решения квадратичной задачи о назначениях. Проведенное сравнительное исследование данного алгоритма с лучшими в настоящее время алгоритмами решения этой задачи показало его конкурентоспособность как по быстродействию, так и по возможности получения лучших решений. A novel Repeated Iterated Tabu Search for quadratic assignment problem is presented. We compare our approach to the state-of-the-art techniques and demonstrate its advantages with respect to run times and solution quality. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях Повторюваний ітерований алгоритм табу для розв’язання квадратичної задачі про призначення Solving the quadratic assignment problem by the Repeated Iterated Tabu Search method Article published earlier |
| spellingShingle | Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях Шило, П.В. Системний аналіз |
| title | Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях |
| title_alt | Повторюваний ітерований алгоритм табу для розв’язання квадратичної задачі про призначення Solving the quadratic assignment problem by the Repeated Iterated Tabu Search method |
| title_full | Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях |
| title_fullStr | Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях |
| title_full_unstemmed | Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях |
| title_short | Повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях |
| title_sort | повторяемый итерированный алгоритм табу для решения квадратичной задачи о назначениях |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/144721 |
| work_keys_str_mv | AT šilopv povtorâemyiiterirovannyialgoritmtabudlârešeniâkvadratičnoizadačionaznačeniâh AT šilopv povtorûvaniiíterovaniialgoritmtabudlârozvâzannâkvadratičnoízadačípropriznačennâ AT šilopv solvingthequadraticassignmentproblembytherepeatediteratedtabusearchmethod |