Про розв'язання квадратичної задачі про призначення
Запропоновано дві модифікації повторюваного ітерованого алгоритму табу розв’язання квадратичної задачі про призначення (з технологією виділення ядра і без неї). Проведено дослідження цих модифікацій порівняно з кращими сучасними алгоритмами розв’язання цієї задачі. Показано ефективність розроблених...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2020 |
| Main Authors: | , , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/190341 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Про розв'язання квадратичної задачі про призначення / І.В. Сергієнко, В.П. Шило, С.В. Чупов, П.В. Шило // Кибернетика и системный анализ. — 2020. — Т. 56, № 1. — С. 64–69. — Бібліогр.: 17 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-190341 |
|---|---|
| record_format |
dspace |
| spelling |
Сергієнко, І.В. Шило, В.П. Чупов, С.В. Шило, П.В. 2023-05-31T13:36:28Z 2023-05-31T13:36:28Z 2020 Про розв'язання квадратичної задачі про призначення / І.В. Сергієнко, В.П. Шило, С.В. Чупов, П.В. Шило // Кибернетика и системный анализ. — 2020. — Т. 56, № 1. — С. 64–69. — Бібліогр.: 17 назв. — укр. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190341 519.854 Запропоновано дві модифікації повторюваного ітерованого алгоритму табу розв’язання квадратичної задачі про призначення (з технологією виділення ядра і без неї). Проведено дослідження цих модифікацій порівняно з кращими сучасними алгоритмами розв’язання цієї задачі. Показано ефективність розроблених алгоритмів, зокрема, для задач великої розмірності, для яких з їхньою допомогою знайдено нові рекорди. Предложены две модификации повторяемого итерированного алгоритма табу решения квадратичной задачи о назначениях (с технологией выделения ядра и без неё). Проведено исследование этих модификаций сравнительно с лучшими современными алгоритмами решения этой задачи. Показана эффективность разработанных алгоритмов, в частности, для задач большой размерности, для которых с их помощью найдены новые рекорды. This paper focuses on the development and improvement of the iterated repeated tabu algorithms for solving the quadratic assignment problem using core allocation technology. The comparative analysis of the empirical computational performance is presented, comparing the modern algorithms from the literature and the algorithms proposed in this paper. The results confirm the efficiency of the modified algorithms in terms of the solution quality and time especially for large-scale problems. uk Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Про розв'язання квадратичної задачі про призначення О решении квадратичной задачи о назначениях Solving the quadratic assignment problem Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Про розв'язання квадратичної задачі про призначення |
| spellingShingle |
Про розв'язання квадратичної задачі про призначення Сергієнко, І.В. Шило, В.П. Чупов, С.В. Шило, П.В. Системний аналіз |
| title_short |
Про розв'язання квадратичної задачі про призначення |
| title_full |
Про розв'язання квадратичної задачі про призначення |
| title_fullStr |
Про розв'язання квадратичної задачі про призначення |
| title_full_unstemmed |
Про розв'язання квадратичної задачі про призначення |
| title_sort |
про розв'язання квадратичної задачі про призначення |
| author |
Сергієнко, І.В. Шило, В.П. Чупов, С.В. Шило, П.В. |
| author_facet |
Сергієнко, І.В. Шило, В.П. Чупов, С.В. Шило, П.В. |
| topic |
Системний аналіз |
| topic_facet |
Системний аналіз |
| publishDate |
2020 |
| language |
Ukrainian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
О решении квадратичной задачи о назначениях Solving the quadratic assignment problem |
| description |
Запропоновано дві модифікації повторюваного ітерованого алгоритму табу розв’язання квадратичної задачі про призначення (з технологією виділення ядра і без неї). Проведено дослідження цих модифікацій порівняно з кращими сучасними алгоритмами розв’язання цієї задачі. Показано ефективність розроблених алгоритмів, зокрема, для задач великої розмірності, для яких з їхньою допомогою знайдено нові рекорди.
Предложены две модификации повторяемого итерированного алгоритма табу решения квадратичной задачи о назначениях (с технологией выделения ядра и без неё). Проведено исследование этих модификаций сравнительно с лучшими современными алгоритмами решения этой задачи. Показана эффективность разработанных алгоритмов, в частности, для задач большой размерности, для которых с их помощью найдены новые рекорды.
This paper focuses on the development and improvement of the iterated repeated tabu algorithms for solving the quadratic assignment problem using core allocation technology. The comparative analysis of the empirical computational performance is presented, comparing the modern algorithms from the literature and the algorithms proposed in this paper. The results confirm the efficiency of the modified algorithms in terms of the solution quality and time especially for large-scale problems.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/190341 |
| citation_txt |
Про розв'язання квадратичної задачі про призначення / І.В. Сергієнко, В.П. Шило, С.В. Чупов, П.В. Шило // Кибернетика и системный анализ. — 2020. — Т. 56, № 1. — С. 64–69. — Бібліогр.: 17 назв. — укр. |
| work_keys_str_mv |
AT sergíênkoív prorozvâzannâkvadratičnoízadačípropriznačennâ AT šilovp prorozvâzannâkvadratičnoízadačípropriznačennâ AT čupovsv prorozvâzannâkvadratičnoízadačípropriznačennâ AT šilopv prorozvâzannâkvadratičnoízadačípropriznačennâ AT sergíênkoív orešeniikvadratičnoizadačionaznačeniâh AT šilovp orešeniikvadratičnoizadačionaznačeniâh AT čupovsv orešeniikvadratičnoizadačionaznačeniâh AT šilopv orešeniikvadratičnoizadačionaznačeniâh AT sergíênkoív solvingthequadraticassignmentproblem AT šilovp solvingthequadraticassignmentproblem AT čupovsv solvingthequadraticassignmentproblem AT šilopv solvingthequadraticassignmentproblem |
| first_indexed |
2025-11-25T21:04:26Z |
| last_indexed |
2025-11-25T21:04:26Z |
| _version_ |
1850547475812712448 |
| fulltext |
².Â. ÑÅÐòªÍÊÎ, Â.Ï. ØÈËÎ, Ñ.Â. ×ÓÏÎÂ, Ï.Â. ØÈËÎ
ÓÄÊ 519.854 ÏÐÎ ÐÎÇÂ’ßÇÀÍÍß ÊÂÀÄÐÀÒÈ×Íί ÇÀÄÀײ
ÏÐÎ ÏÐÈÇÍÀ×ÅÍÍß
Àíîòàö³ÿ. Çàïðîïîíîâàíî äâ³ ìîäèô³êàö³¿ ïîâòîðþâàíîãî ³òåðîâàíîãî àëãî-
ðèòìó òàáó ðîçâ’ÿçàííÿ êâàäðàòè÷íî¿ çàäà÷³ ïðî ïðèçíà÷åííÿ (ç òåõíîëî㳺þ
âèä³ëåííÿ ÿäðà ³ áåç íå¿). Ïðîâåäåíî äîñë³äæåííÿ öèõ ìîäèô³êàö³é ïîð³âíÿ-
íî ç êðàùèìè ñó÷àñíèìè àëãîðèòìàìè ðîçâ’ÿçàííÿ ö³º¿ çàäà÷³. Ïîêàçàíî
åôåêòèâí³ñòü ðîçðîáëåíèõ àëãîðèòì³â, çîêðåìà, äëÿ çàäà÷ âåëèêî¿ ðîçì³ð-
íîñò³, äëÿ ÿêèõ ç ¿õíüîþ äîïîìîãîþ çíàéäåíî íîâ³ ðåêîðäè.
Êëþ÷îâ³ ñëîâà: êâàäðàòè÷íà çàäà÷à ïðî ïðèçíà÷åííÿ, ïîâòîðþâàíèé ³òåðî-
âàíèé òàáó-ïîøóê, òåõíîëîã³ÿ âèä³ëåííÿ ÿäðà ðîçâ’ÿçêó, âèïàäêîâå çáóðåííÿ
êîìïîíåíò ðîçâ’ÿçêó, åôåêòèâí³ñòü àëãîðèòì³â.
ÂÑÒÓÏ
Êâàäðàòè÷íà çàäà÷à ïðî ïðèçíà÷åííÿ (Quadratic Assigning Problem, QAP) º âàæ-
ëèâîþ ó ïðàêòè÷íîìó ñåíñ³. Äî íå¿ çâîäÿòüñÿ çàäà÷³ ðîçì³ùåííÿ ëîã³÷íèõ ìî-
äóë³â íà ì³êðîñõåì³, ðîçïîä³ë ìåäè÷íèõ ñëóæá ó âåëèêîìó ãîñï³òàëüíîìó
öåíòð³, áàëàíñóâàííÿ òóðá³í, àíàë³çó çîáðàæåíü òà ³í. Ðîçâ’ÿçàííÿ QAP ïîòðå-
áóº çä³éñíåííÿ çíà÷íîãî îáñÿãó îá÷èñëåíü, çîêðåìà îäíå çíà÷åííÿ ¿¿ ö³ëüîâî¿
ôóíêö³¿ çíàõîäèòüñÿ ç òðóäîì³ñòê³ñòþ O n( )2 . Ïðè÷îìó îáñÿã îá÷èñëåíü åêñïî-
íåíö³àëüíî çðîñòàº ç³ çðîñòàííÿì ðîçì³ðíîñò³ çàäà÷³. Ïðàêòè÷íå çíà÷åííÿ òà îá-
÷èñëþâàëüíà ñêëàäí³ñòü ö³º¿ çàäà÷³ ï³äòâåðäæóºòüñÿ õðîíîëî㳺þ äîñë³äæåííÿ.
Çàäà÷ó áóëî ñôîðìóëüîâàíî ó 1957 ð. [1]. Ó 1961 ð. çàïðîïîíîâàíî íàá³ð ³ç
òðüîõ çàäà÷ ðîçì³ðí³ñòþ 36 [2]. Ó 1968 ð. ïðåäñòàâëåíî òåñòîâ³ çàäà÷³,
ðîçì³ðí³ñòü ÿêèõ êîëèâàºòüñÿ â³ä 12 äî 30 [3]. Ó 1976 ð. áóëî äîâåäåíî [4], ùî
öÿ çàäà÷à íàëåæèòü êëàñó NP-ñêëàäíèõ çàäà÷. Ó ðîáîò³ [5] â 1984 ð. áóëî
â³äçíà÷åíî, ùî íå ìîæíà ïîáóäóâàòè òî÷íèõ ìåòîä³â äëÿ åôåêòèâíîãî ðîçâ’ÿ-
çàííÿ QAP ðîçì³ðí³ñòþ, á³ëüøîþ çà 20. ² ò³ëüêè ç ê³íöÿ 80-õ ðîê³â ìèíóëîãî
ñòîð³÷÷ÿ ðîçïî÷àâñÿ áóðõëèâèé ðîçâèòîê íàáëèæåíèõ ìåòîä³â çíàõîäæåííÿ
ÿê³ñíèõ ðîçâ’ÿçê³â êâàäðàòè÷íî¿ çàäà÷³ ïðî ïðèçíà÷åííÿ. Öå ïîâ’ÿçàíî, çîêðåìà,
ç³ ñòð³ìêèì ðîçâèòêîì òåõí³÷íèõ ìîæëèâîñòåé îá÷èñëþâàëüíî¿ òåõí³êè. Âîäíî-
÷àñ áóëè ïîáóäîâàí³ òåñòîâ³ çàäà÷³, ùî ìàþòü ðîçì³ðí³ñòü, çíà÷íî á³ëüøó í³æ
ðîçì³ðí³ñòü íàÿâíèõ çàäà÷. Íèí³ ìàêñèìàëüíà ðîçì³ðí³ñòü òåñòîâèõ QAP
ó á³áë³îòåö³ OR Lib� [6] ñòàíîâèòü 150.
Ñüîãîäí³ á³ëüø³ñòü åôåêòèâíèõ íàáëèæåíèõ àëãîðèòì³â äëÿ QAP ´ðóí-
òóºòüñÿ íà âèêîðèñòàíí³ ð³çíîìàí³òíèõ ñõåì ìåòîäó òàáó-ïîøóêó (Tabu
Search, TS), çàïðîïîíîâàíîãî ó 1989–1990 ðð. [7, 8]. Âàðòî çãàäàòè òàê³ âåðñ³¿ ìå-
òîäó, ÿê íàä³éíèé òàáó-ïîøóê [9] (Robust Tabu Search, RoTS), ðåàêòèâíèé
òàáó-ïîøóê [10] (Reactive Tabu Search, ReTS), ³òåðîâàíèé òàáó-ïîøóê [11]
(Iterated Tabu Search, ITS). Ïðîòÿãîì îñòàíí³õ ðîê³â íàéá³ëüø ÿê³ñí³ ðåçóëüòàòè
îòðèìàíî òàêèìè íàáëèæåíèìè àëãîðèòìàìè ÿê Breakout Local Search (BLS) [12],
64 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1
© ².Â. Ñåð㳺íêî, Â.Ï. Øèëî, Ñ.Â. ×óïîâ, Ï.Â. Øèëî, 2020
Memetic Algorithm for QAP (BMA) [13], Improved Hybrid Genetic Algorithm
(IHGA) [14], ITS for QAP [15] òà áàãàòüìà ³íøèìè.
Ó ö³é ñòàòò³ íàáóëè ïîäàëüøîãî ðîçâèòêó ðåçóëüòàòè ðîçâ’ÿçàííÿ QAP
³ç [16]. Ðîçðîáëåíî äâ³ ìîäèô³êàö³¿ ïîâòîðþâàíîãî ³òåðîâàíîãî àëãîðèòìó òàáó
(ç òåõíîëî㳺þ âèä³ëåííÿ ÿäðà ðîçâ’ÿçêó [17] òà âèïàäêîâèì çáóðåííÿì ïåâíî¿
ê³ëüêîñò³ éîãî êîìïîíåíò). Ïðîâåäåíå ïîð³âíÿëüíå åêñïåðèìåíòàëüíå äîñë³äæåí-
íÿ êðàùèõ â³äîìèõ äëÿ ö³º¿ çàäà÷³ òà ðîçðîáëåíèõ àëãîðèòì³â ï³äòâåðäèëî åôåê-
òèâí³ñòü îñòàíí³õ.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀײ
Êâàäðàòè÷íà çàäà÷à ïðî ïðèçíà÷åííÿ ïîëÿãຠâ îïòèìàëüíîìó ðîçì³ùåíí³ n
îá’ºêò³â íà n ïîçèö³ÿõ àáî ëîêàö³ÿõ. Á³ëüø òî÷íî ¿¿ ôîðìóëþþòü ó òàêèé
ñïîñ³á. Íåõàé A aij� [ ] òà B bij� [ ] — äâ³ êâàäðàòí³ ìàòðèö³ ïîðÿäêó n ç íå-
â³ä’ºìíèìè åëåìåíòàìè. Ìàòðèöÿ A çàäຠâåëè÷èíè ïîòîê³â, ÿê³ öèðêóëþþòü
ì³æ îá’ºêòàìè, òà íàçèâàºòüñÿ ìàòðèöåþ ïîòîê³â (flow matrix), à ìàòðèöÿ B
âèçíà÷ຠâ³äñòàí³ ì³æ óñ³ìà îá’ºêòàìè ³ ìຠíàçâó ìàòðèö³ â³äñòàíåé (distance
matrix). Ïîòð³áíî ó òàêèé ñïîñ³á ðîçïîä³ëèòè îá’ºêòè ïî ëîêàö³ÿõ, ùîá ñóìà
â³äñòàíåé, ïîìíîæåíèõ íà â³äïîâ³äí³ ïîòîêè, áóëà ì³í³ìàëüíîþ.
Íåõàé � i — íîìåð ëîêàö³¿ îá’ºêòà i, à �n — ìíîæèíà óñ³õ ïåðåñòàíîâîê
( , , )1 � n .
Ìàòåìàòè÷íà ìîäåëü ö³º¿ çàäà÷³ ìຠòàêèé âèãëÿä: çíàéòè
min
�
� �
�
� ��
�
�
�
�
�
��
�n
i j
f a bij
j
n
i
n
( )
11
.
Çàçíà÷èìî, ùî â îäíèõ äæåðåëàõ A — ìàòðèöÿ â³äñòàíåé, à B — ìàòðèöÿ ïî-
òîê³â (íàïðèêëàä [9]), à â ³íøèõ — íàâïàêè (íàïðèêëàä [13]). Öå ñòîñóºòüñÿ ³ òåñ-
òîâèõ çàäà÷ ç á³áë³îòåêè OR Lib� [6]. Íàïðèêëàä, ó òåñòîâ³é çàäà÷³ tai a100 ïåðøà
çà ïîðÿäêîì ìàòðèöÿ — ìàòðèöÿ â³äñòàíåé, äðóãà — ìàòðèöÿ ïîòîê³â, à â çàäà÷³
tai a80 — âñå íàâïàêè. Öå ïîÿñíþºòüñÿ ñïðàâåäëèâ³ñòþ ñï³ââ³äíîøåííÿ
a b a bij
j
n
i
n
ij
j
n
i
n
i j i j� � � �
�� ��
�� ���
11 11
äëÿ QAP,
äå � � �� ( , , )n � 1 — ³íâåðñ³éíà äî � ïåðåñòàíîâêà.
ÏÎÂÒÎÐÞÂÀÍÈÉ ²ÒÅÐÎÂÀÍÈÉ ÒÀÁÓ-ÏÎØÓÊ (RITSR, RITSK)
Àâòîðàìè ðîçðîáëåíî òà åêñïåðèìåíòàëüíî äîñë³äæåíî äâ³ ìîäèô³êàö³¿ íàáëè-
æåíîãî àëãîðèòìó ðîçâ’ÿçàííÿ QAP, íàçâàíîãî RITS (Repeated Iterated Tabu
Search) [16]: àëãîðèòìè RITSR òà RITSK. Íà ðèñ. 1 ïðåäñòàâëåíî ôîðìàëüíó
ñõåìó îäíîãî êðîêó öèõ àëãîðèòì³â.
Çàçâè÷àé ñõåìè ñó÷àñíèõ íàáëèæåíèõ ìåòîä³â ðîçâ’ÿçàííÿ çàäà÷ îïòèì³çàö³¿
ì³ñòÿòü äâ³ ôàçè: ³íòåíñèô³êàö³ÿ ïîøóêó òà äèâåðñèô³êàö³ÿ ïîøóêó. Íà ïåðø³é ôàç³
çä³éñíþºòüñÿ ïîøóê ëîêàëüíîãî åêñòðåìóìó çàäà÷³, à íà äðóã³é — ðîáèòüñÿ ñïðîáà
âèéòè ç éîãî îêîëó òà ïåðåéòè â ³íøó, ùå íå äîñë³äæåíó, îáëàñòü ìíîæèíè äîïóñ-
òèìèõ ðîçâ’ÿçê³â çàäà÷³. Ó ïîäàí³é íà ðèñ. 1 áëîê-ñõåì³ àëãîðèòì³â RITSR
³ RITSK ïåðøó ôàçó ïîøóêó ïðåäñòàâëÿþòü áëîêè | |_ _ ( )f detailed ITS search� �
òà | |_ _ ( )f investigative ITS search� � . Îáèäâà ö³ áëîêè ðåàë³çóþòü îäíàêîâó
ñõåìó ³òåðîâàíîãî ëîêàëüíîãî òàáó-ïîøóêó (ITSL). ³äð³çíÿþòüñÿ âîíè ëèøå ïà-
ðàìåòðàìè ïîøóêó. ϳä ÷àñ äåòàëüíîãî ïîøóêó ëîêàëüíîãî ì³í³ìóìó ê³ëüê³ñòü ³òå-
ðàö³é ñòàíîâèòü 9 2n , à ï³ä ÷àñ äîñë³äíèöüêîãî — 3 2n . Äîñë³äíèöüêèé ïîøóê
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1 65
ïðèçíà÷åíèé äëÿ âèÿâëåííÿ êðàùèõ ðîçâ’ÿçê³â, ùî ì³ñòÿòüñÿ íà íåçíà÷í³é â³äñòàí³
â³ä ìåæ³ ïîòî÷íîãî îêîëó ëîêàëüíîãî ì³í³ìóìó. Ïðîöåäóðà äîñë³äíèöüêîãî ïîøó-
êó ïîâòîðþºòüñÿ ïåâíó ê³ëüê³ñòü ðàç³â, ùî âèçíà÷àºòüñÿ ïàðàìåòðîì àëãîðèòìó
max_ repeated. ßêùî îòðèìàíî êðàùèé ðîçâ’ÿçîê, â³í çàïàì’ÿòîâóºòüñÿ òà ïî÷è-
íàºòüñÿ äåòàëüíèé ïîøóê íîâîãî, êðàùîãî çà çíàéäåíèé, ðîçâ’ÿçêó â îêîë³ çíàéäå-
íî¿ ïåðåñòàíîâêè. ϳñëÿ öüîãî öèêë ïîâòîðåíü ó ðåæèì³ äîñë³äíèöüêîãî ïîøóêó
ðîçïî÷èíàºòüñÿ çàíîâî. Äðóãà ôàçà ïîøóêó — ôàçà äèâåðñèô³êàö³¿ — âèêîíóºòüñÿ
ùîðàçó ïåðåä ïî÷àòêîì íîâîãî äîñë³äíèöüêîãî ïîøóêó ó öèêë³ ïîâòîðåíü.
Íà ðèñ. 1 âîíà ïðåäñòàâëåíà áëîêîì | |_ ( , )� �� perturbation generate strength best .
Ó ö³é ôàç³ çáóðþºòüñÿ ïîòî÷íèé ëîêàëüíèé ì³í³ìóì ó òàêèé ñïîñ³á, ùîá íàñòóï-
íèé äîñë³äíèöüêèé ïîøóê â³äáóâàâñÿ íà ïåâí³é â³äñòàí³ â³ä îêîëó ïîòî÷íîãî ðîç-
â’ÿçêó. Âåëè÷èíà òàêîãî çáóðåííÿ çàäàºòüñÿ ïàðàìåòðîì strength. Öåé ïàðàìåòð
âèçíà÷ຠê³ëüê³ñòü åëåìåíò³â ó ïåðåñòàíîâö³, ÿêà áóäå çáóðþâàòèñü. Ó ïðîöåñ³ åê-
ñïåðèìåíòàëüíèõ äîñë³äæåíü ç’ÿñóâàëîñÿ, ùî íàéá³ëüø ïðèäàòíå çíà÷åííÿ âåëè-
÷èíè çáóðåííÿ ñòàíîâèòü 33% â³ä ðîçì³ðíîñò³ n çàäà÷³. Àëå çíà÷åííÿ strength íå çàâ-
æäè âèáèðàºòüñÿ íàïåðåä ³ º ô³êñîâàíèì. Ó ïðîöåñ³ äîñë³äæåíü âèêîðèñòàíî ñõåìè,
çã³äíî ç ÿêèìè çíà÷åííÿ strength àáî öèêë³÷íî çì³íþâàëîñÿ â³ä ïåâíî¿ ì³í³ìàëüíî¿ äî
66 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1
repeated � max_repeated
Yes
repeated � repeated � 1
Yes
No
No
f � fbest�best � �; fbest � f (�)
f � investigative_ ITS_ search(�)
� � perturbation_ generate(strength, �best )
repeated � 1
f � fbest
No
Yes
�best � �; fbest � f (�)
f � detailed_ ITS_ search(�)
� � random_ generate
�best � �; fbest � f (�)
step_ finished
Ðèñ 1. Ñõåìà îäíîãî êðîêó àëãîðèòì³â RITSR òà RITSK
ïåâíî¿ ìàêñèìàëüíî¿ âåëè÷èíè, àáî çì³íþâàëîñÿ íàâïàêè, àáî ïîñë³äîâíî íàáóâàëî
çíà÷åíü ç íàïåðåä çàäàíîãî ìàñèâó.
Ó ö³é ñòàòò³ äîñë³äæåíî äâà âàð³àíòè çáóðåííÿ: âèïàäêîâå çáóðåííÿ (àëãî-
ðèòì RITSR) òà çáóðåííÿ íà îñíîâ³ âèä³ëåííÿ ÿäðà ðîçâ’ÿçêó (àëãîðèòì RITSK).
Âèïàäêîâå çáóðåííÿ ïîëÿãຠó ïåðåñòàíîâö³ strength åëåìåíò³â � best , ùî çíàõî-
äÿòüñÿ íà âèïàäêîâî âèáðàíèõ ïîçèö³ÿõ. Ó ðåçóëüòàò³ åêñïåðèìåíòàëüíèõ
äîñë³äæåíü ç’ÿñóâàëîñÿ, ùî ñòðóêòóðè ÿê³ñíèõ ðîçâ’ÿçê³â êîíêðåòíî¿ çàäà÷³
îïòèì³çàö³¿ ñõîæ³ ì³æ ñîáîþ. Ñòîñîâíî QAP öå îçíà÷àº, ùî ó ð³çíèõ ïåðåñòàíîâ-
êàõ, äëÿ ÿêèõ çíà÷åííÿ ö³ëüîâî¿ ôóíêö³¿ áëèçüê³ äî îïòèìàëüíîãî (ÿê³ñí³ ðîçâ’ÿç-
êè), íà ïåâíèõ ïîçèö³ÿõ çíàõîäÿòüñÿ åëåìåíòè ç îäíàêîâèìè çíà÷åííÿìè. Çáóðåí-
íÿ çà òåõíîëî㳺þ âèä³ëåííÿ ÿäðà [17] ïîëÿãຠó âèçíà÷åíí³ òèõ åëåìåíò³â ïåðå-
ñòàíîâêè � best , äëÿ ÿêèõ âîíî íàéá³ëüø ³ìîâ³ðíî ìຠïåðñïåêòèâè çíàõîäæåííÿ
êðàùèõ ðîçâ’ÿçê³â. Çíàéäåí³ åëåìåíòè âïîðÿäêîâóþòüñÿ çà ñïàäàííÿì òàêèõ
éìîâ³ðíîñòåé, ï³ñëÿ ÷îãî îñòàíí³ strength åëåìåíò³â âèïàäêîâèì ÷èíîì çáóðþ-
þòüñÿ. Á³ëüø äåòàëüíèé îïèñ àëãîðèòì³â RITSR òà RITSK áóäå ïðåäñòàâëåíî
ó íàñòóïí³é ñòàòò³.
ÐÅÇÓËÜÒÀÒÈ ÅÊÑÏÅÐÈÌÅÍÒÀËÜÍÈÕ ÐÎÇÐÀÕÓÍʲÂ
ϳä ÷àñ åêñïåðèìåíòàëüíîãî äîñë³äæåííÿ åôåêòèâíîñò³ àëãîðèòì³â RITSR òà
RITSK îñíîâíó óâàãó áóëî ïðèä³ëåíî ðîçâ’ÿçàííþ òåñòîâèõ çàäà÷ òèïó
taiXXa [9], äå XX � 50, 60, 80, 100 — ðîçì³ðí³ñòü çàäà÷³, îñê³ëüêè âîíè º
íàéá³ëüø âàæêèìè ç ïîãëÿäó îáñÿãó îá÷èñëåíü. Ó ðîáîò³ [9] ïðåäñòàâëåíî àë-
ãîðèòì äëÿ ãåíåðóâàííÿ çàäà÷ òèïó taiXXa äîâ³ëüíî¿ ðîçì³ðíîñò³. Íà éîãî
îñíîâ³ ðîçðîáëåíî ïðîöåäóðó ïîáóäîâè çàäà÷ òàêîãî òèïó.
Ó òåñòîâèõ çàäà÷àõ taiXXa ìàòðèö³ â³äñòàíåé òà ïîòîê³â º ñèìåòðè÷íèìè. ¯õí³
åëåìåíòè — ö³ë³ âèïàäêîâ³ ÷èñëà, ð³âíîì³ðíî ðîçïîä³ëåí³ íà ïðîì³æêó [0, 99]
(uniform_distribution(0,99)). Îñîáëèâ³ñòþ öèõ çàäà÷ º íàÿâí³ñòü âåëèêî¿ ê³ëüêîñò³
ëîêàëüíèõ ì³í³ìóì³â ð³çíî¿ ÿêîñò³, á³ëüø³ñòü ç ÿêèõ íå çàäîâîëüíÿþòü êîðèñòóâà-
÷à. ßêùî ñòóï³íü çáóðåííÿ ïîòî÷íîãî ðîçâ’ÿçêó íà ôàç³ äèâåðñèô³êàö³¿ âèáèðàòè
íåâåëèêèì (ìåíøèì çà 30%), òî îòðèìàºìî äîâãîòðèâàëèé ïðîöåñ ïåðåõîäó â³ä îä-
íîãî ëîêàëüíîãî ì³í³ìóìó äî ³íøîãî, ÿêèé ìîæå áóòè ÿê õîðîøèì, òàê
³ íåÿê³ñíèì. Ó á³ëüøîñò³ âè-
ïàäê³â ðîçâ’ÿçîê º íåÿê³ñíèì.
 ³íøîìó âèïàäêó (äëÿ ñòó-
ïåíÿ çáóðåííÿ, ùî ïåðåâèùóº
40%), ïåâí³ îáëàñò³ ìîæóòü
áóòè íå äîñë³äæåí³, à îòæå,
ÿê³ñíèé ðîçâ’ÿçîê çàäà÷³
ìîæå áóòè ïðîïóùåíèé. Íà
ðèñ. 2 ïðåäñòàâëåíî íàáëèæå-
íå ðîçì³ùåííÿ ðîçâ’ÿçê³â çà-
äà÷ tai a100 . Íàäçâè÷àéíî âè-
ñîêà ù³ëüí³ñòü ðîçòàøóâàííÿ
ëîêàëüíèõ ì³í³ìóì³â ð³çíî¿
ÿêîñò³ íà âñ³é ìíîæèí³ ïåðå-
ñòàíîâîê ðîáèòü çàäà÷³ öüîãî
òèïó äóæå ñêëàäíèìè ç ïîãëÿ-
äó îòðèìàííÿ õîðîøèõ ðîçâ’ÿçê³â çà ïðèéíÿòíèé ÷àñ.
Óñ³ çàçíà÷åí³ àëãîðèòìè ðåàë³çîâàíî íà ìîâ³ Ñ++ ó ñåðåäîâèù³ Microsoft Visual
Studio 2017. Îá÷èñëþâàëüí³ åêñïåðèìåíòè ïðîâåäåíî ç âèêîðèñòàííÿì PC Intel®
Core™ i7-3820 CPU 3.5 GHz ³ 8.0 GB îïåðàòèâíî¿ ïàì’ÿò³. Äëÿ ïîð³âíÿííÿ åôåêòèâ-
íîñò³ àëãîðèòì³â RITSK òà RITSR ç ³íøèìè àëãîðèòìàìè áóëî âèáðàíî êðàù³ ñó÷àñí³
àëãîðèòìè ITS [11,15], BLS [12], BMA [13]. Òåêñòè ïðîãðàì àëãîðèòì³â BLS òà BMA
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1 67
Ðèñ. 2. Ñõåìàòè÷íå ðîçì³ùåííÿ ðîçâ’ÿçê³â çàäà÷ tai a100
Çí
à÷
åí
í
ÿ
ö
³ë
üî
âî
¿
ô
óí
êö
³¿
�
�
10
6
Ïåðåñòàíîâêà
âçÿòî ³ç çàãàëüíîäîñòóïíèõ äæåðåë [http://www.info. univ-angers.fr/~hao/
BLS_code.html; http://www.info.univ-angers.fr/pub/ hao/BMA.html]).
Àâòîðè âèñëîâëþþòü âåëèêó âäÿ÷í³ñòü À. ̳ñåâ³÷óñó (À. Misevicius) çà íàäàí³
òåêñòè ïðîãðàì äëÿ àëãîðèòìó ITS. Öå äàëî çìîãó ïðîâåñòè åêñïåðèìåíòàëüí³
äîñë³äæåííÿ â îäíàêîâèõ óìîâàõ òà á³ëüø îá’ºêòèâíî çä³éñíèòè ïîð³âíÿííÿ
åôåêòèâíîñò³ àëãîðèòì³â ï³ä ÷àñ ðîçâ’ÿçàííÿ îäíèõ ³ òèõ ñàìèõ çàäà÷.
Ó òàáë. 1 íàâåäåíî äåÿê³ ðåçóëüòàòè ïîð³âíÿëüíîãî äîñë³äæåííÿ öèõ àëãî-
ðèòì³â ç àëãîðèòìàìè RITSK (ç âèä³ëåííÿì ÿäðà) òà RITSR (ç âèïàäêîâèì çáó-
ðåííÿì). Ó äðóãîìó ñòîâïö³ òàáëèö³ BKS — â³äîìèé ðåêîðä. Äëÿ êîæíîãî àëãî-
ðèòìó íàâåäåíî â³äõèëåííÿ (ó â³äñîòêàõ) â³ä BKS ñåðåäíüîãî çíà÷åííÿ ö³ëüîâî¿
ôóíêö³¿, îòðèìàíîãî çà äîïîìîãîþ öüîãî àëãîðèòìó ï³ñëÿ âèêîíàííÿ 40 ñïðîá
ðîçâ’ÿçàííÿ çàäà÷³. Íàï³âæèðíèì øðèôòîì âèä³ëåíî íàéêðàù³ ðåçóëüòàòè. Äëÿ
óñ³õ àëãîðèòì³â îáìåæåííÿ çà ÷àñîì ñòàíîâèëî 2 ãîäèíè.
Äëÿ çàäà÷³ tai a100 àëãîðèòìîì RITSK çíàéäåíî êðàùèé çà â³äîìèé íà öåé
ìîìåíò ðîçâ’ÿçîê
� best � (89, 63, 41, 47, 84, 25, 91, 21, 8, 14, 0, 58, 32, 26, 75, 19, 86, 68, 64, 48,
49, 57, 42, 80, 88, 13, 78, 45, 24, 5, 97, 59, 82, 54, 38, 67, 31, 43, 6, 3, 23, 18,
74, 90, 28, 16, 36, 34, 12, 4, 1, 40, 65, 10, 44, 2, 96, 30, 85, 35, 7, 79, 69, 11,
83, 56, 50, 15, 37, 76, 22, 29, 81, 60, 95, 73, 53, 93, 70, 66, 51, 55, 20, 9, 17, 92,
87, 33, 62, 72, 99, 71, 46, 39, 61, 52, 27, 98, 94, 77) ³ç çíà÷åííÿì ö³ëüîâî¿
ôóíêö³¿ f best � 21 044 752 .
Ç òåîðåòè÷íî¿ òî÷êè çîðó íàâåäåíèé âèùå ðîçâ’ÿçîê � best íå º ïåðåñòàíîâêîþ,
îñê³ëüêè â³äë³ê ïîçèö³é ó íüîìó ïî÷èíàºòüñÿ ç íóëÿ. Òàêèé ñïîñ³á ïðåäñòàâëåííÿ
ïåðåñòàíîâêè º äóæå çðó÷íèì ç îá÷èñëþâàëüíî¿ òî÷êè çîðó. Ïðîòå, ÿêùî äî êîæ-
íîãî çíà÷åííÿ � best äîäàòè îäèíèöþ, òî îòðèìàºìî êëàñè÷íó ïåðåñòàíîâêó.
ÂÈÑÍÎÂÊÈ
Îòðèìàí³ ðåçóëüòàòè åêñïåðèìåíòàëüíèõ äîñë³äæåíü ñâ³ä÷àòü, ùî àëãîðèòìè
RITSK òà RITSR çäàòí³ êîíêóðóâàòè ç íàéêðàùèìè àëãîðèòìàìè ðîçâ’ÿçàííÿ
êâàäðàòè÷íî¿ çàäà÷³ ïðî ïðèçíà÷åííÿ. Ïîäàëüøå âèêîðèñòàííÿ òåõíîëîã³é ïà-
ðàëåëüíèõ îá÷èñëåíü, çîêðåìà ïîðòôåë³â òà êîìàíä àëãîðèòì³â, äàñòü çìîãó
ïðèøâèäøèòè ïðîöåñ â³äøóêàííÿ ÿê³ñíèõ ðîçâ’ÿçê³â QAP.
ÑÏÈÑÎÊ Ë²ÒÅÐÀÒÓÐÈ
1. Koopmans T.C., Beckmann M.J. Assignment problems and the location of economic activities.
Econometrica. 1957. Vol. 25, N 1. P. 53–76.
2. Steinberg L. The backboard wiring problem: a placement algorithm. SIAM Review. 1961. Vol. 3,
N 1. P. 37–50.
3. 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.
4. Sahni S., Gonzalez T. P-complete approximation problems. J. of the ACM. 1976. Vol. 23, N 3.
P. 555–565.
5. Burkard R.E. Quadratic assignment problems. European J. of Oper. Res. 1984. Vol. 15, N 3.
P. 283–289.
6. Beasley J.E. OR-library; distributing test problems by electronic mail. J. of Oper. Res. Society. 1990.
Vol. 41, N 11. P.1069–1072.
7. Glover F. Tabu Search — Part I. ORSA J. on Computing. 1989. Vol. 1, N 3. P. 190–206.
8. Glover F. Tabu Search — Part ²I. ORSA J. on Computing. 1990. Vol. 2, N 1. P. 4–32.
68 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1
Ò à á ë è ö ÿ 1
Çàäà÷à BKS RITSK RITSR ITS BLS BMA
tai50a 4938796 0.050 0.048 0.050 0.102 0.090
tai60a 7205962 0.144 0.154 0.135 0.295 0.193
tai80a 13499184 0.350 0.342 0.368 0.564 0.458
tai100a 21044752 0.277 0.284 0.311 0.569 0.432
9. Taillard E. Robust taboo search for the quadratic assignment problem. Parallel Computing.
1991. Vol. 17, Iss. 4-5. P. 443–455.
10. Battiti R., Tecchiolli G. The reactive tabu search. ORSA J. on Computing. 1994. Vol. 6, N 2.
P. 126–140.
11. Misevicius A., Lenkevicius A., Rubliauskas D. Iterated tabu search: An improvement to standard
tabu search. Information Technology and Control. 2006. Vol. 35, N 3. P. 187–197.
12. 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.
13. Benlic U., Hao J.K. Memetic search for the quadratic assignment problem. Expert Systems with
Applications. 2015. Vol. 42, N 1. P. 584–595.
14. 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.
15. Misevicius A. An implementation of the iterated tabu search algorithm for the quadratic assignment
problem. OR Spectrum. 2012. Vol. 34, N 3. P. 665–690.
16. Øèëî Ï.Â. Ïîâòîðÿåìûé èòåðèðîâàííûé àëãîðèòì òàáó äëÿ ðåøåíèÿ êâàäðàòè÷íîé çàäà÷è
î íàçíà÷åíèÿõ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2017. Ò. 53, ¹ 2. Ñ. 163–167.
17. Ñåðãèåíêî È.Â., Øèëî Â.Ï. Òåõíîëîãèÿ ÿäðà äëÿ ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçàöèè.
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2017. Ò. 53, ¹ 6. Ñ. 73–83.
Íàä³éøëà äî ðåäàêö³¿ 15.08.2019
È.Â. Ñåðãèåíêî, Â.Ï. Øèëî, Ñ.Â. ×óïîâ, Ï.Â. Øèëî
Î ÐÅØÅÍÈÈ ÊÂÀÄÐÀÒÈ×ÍÎÉ ÇÀÄÀ×È Î ÍÀÇÍÀ×ÅÍÈßÕ
Àííîòàöèÿ. Ïðåäëîæåíû äâå ìîäèôèêàöèè ïîâòîðÿåìîãî èòåðèðîâàííîãî
àëãîðèòìà òàáó ðåøåíèÿ êâàäðàòè÷íîé çàäà÷è î íàçíà÷åíèÿõ (ñ òåõíîëîãèåé
âûäåëåíèÿ ÿäðà è áåç íå¸). Ïðîâåäåíî èññëåäîâàíèå ýòèõ ìîäèôèêàöèé
ñðàâíèòåëüíî ñ ëó÷øèìè ñîâðåìåííûìè àëãîðèòìàìè ðåøåíèÿ ýòîé çàäà÷è.
Ïîêàçàíà ýôôåêòèâíîñòü ðàçðàáîòàííûõ àëãîðèòìîâ, â ÷àñòíîñòè, äëÿ çàäà÷
áîëüøîé ðàçìåðíîñòè, äëÿ êîòîðûõ ñ èõ ïîìîùüþ íàéäåíû íîâûå ðåêîðäû.
Êëþ÷åâûå ñëîâà: êâàäðàòè÷íàÿ çàäà÷à î íàçíà÷åíèÿõ, ïîâòîðÿåìûé èòåðè-
ðîâàííûé òàáó-ïîèñê, òåõíîëîãèÿ âûäåëåíèÿ ÿäðà ðåøåíèÿ, ñëó÷àéíîå âîç-
ìóùåíèå êîìïîíåíò ðåøåíèÿ, ýôôåêòèâíîñòü àëãîðèòìîâ.
I.V. Sergienko, V.P. Shylo, S.V. Chupov, P.V. Shylo
SOLVING THE QUADRATIC ASSIGNMENT PROBLEM
Abstract. This paper focuses on the development and improvement of the
iterated repeated tabu algorithms for solving the quadratic assignment problem
using core allocation technology. The comparative analysis of the empirical
computational performance is presented, comparing the modern algorithms from
the literature and the algorithms proposed in this paper. The results confirm the
efficiency of the modified algorithms in terms of the solution quality and time
especially for large-scale problems.
Keywords: quadratic assignment problem, repeated iterated tabu search, solution
core allocation technology, random perturbation of solution components,
algorithm efficiency.
Ñåð㳺íêî ²âàí Âàñèëüîâè÷,
äîêòîð ô³ç.-ìàò. íàóê, àêàäåì³ê ÍÀÍ Óêðà¿íè, ïðîôåñîð, äèðåêòîð ²íñòèòóòó ê³áåðíåòèêè
³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, Êè¿â, e-mail: incyb@incyb.kiev.ua.
Øèëî Âîëîäèìèð Ïåòðîâè÷,
äîêòîð ô³ç.-ìàò. íàóê, ïðîôåñîð, ïðîâ³äíèé íàóêîâèé ñï³âðîá³òíèê ²íñòèòóòó ê³áåðíåòèêè
³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, Êè¿â, e-mail: v.shylo@gmail.com.
×óïîâ Ñåðã³é ³êòîðîâè÷,
êàíäèäàò ô³ç.-ìàò. íàóê, äîöåíò êàôåäðè Äåðæàâíîãî âèùîãî íàâ÷àëüíîãî çàêëàäó «Óæãîðîäñüêèé
íàö³îíàëüíèé óí³âåðñèòåò», e-mail: serhii.chupov@uzhnu.edu.ua, sergey.chupov@gmail.com.
Øèëî Ïåòðî Âîëîäèìèðîâè÷,
êàíäèäàò ô³ç.-ìàò. íàóê, íàóêîâèé ñï³âðîá³òíèê ²íñòèòóòó ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ
Óêðà¿íè, Êè¿â, e-mail: petershylo@gmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 1 69
|