Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа
Розроблено новий, оснований на використанні методу глобального рівноважного пошуку (ГРП) алгоритм розв’язання задачі про максимальний зважений розріз графу. Проведено його порівняльне дослідження з найкращими на даний час алгоритмами розв’язання цієї задачі. Показано переваги алгоритму ГРП як за шви...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2012 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84128 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа / В.П. Шило, О.В. Шило, В.А. Рощин // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 101-105. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859951875329097728 |
|---|---|
| author | Шило, В.П. Шило, О.В. Рощин, В.А. |
| author_facet | Шило, В.П. Шило, О.В. Рощин, В.А. |
| citation_txt | Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа / В.П. Шило, О.В. Шило, В.А. Рощин // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 101-105. — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розроблено новий, оснований на використанні методу глобального рівноважного пошуку (ГРП) алгоритм розв’язання задачі про максимальний зважений розріз графу. Проведено його порівняльне дослідження з найкращими на даний час алгоритмами розв’язання цієї задачі. Показано переваги алгоритму ГРП як за швидкодією, так і за можливістю отримання кращих розв’язків.
A new algorithm based on the global equilibrium search (GES) is developed to solve the weighted MAXCUT problem. A comparison study of the algorithm and currently the best algorithm for solving this problem was conducted. The advantages of the GES algorithm both in the performance and the possibility of finding the best solutions are shown.
|
| first_indexed | 2025-12-07T16:17:47Z |
| format | Article |
| fulltext |
ÓÄÊ 519.854
Â.Ï. ØÈËÎ, Î.Â. ØÈËÎ, Â.À. ÐÎÙÈÍ
ÌÅÒÎÄ ÃËÎÁÀËÜÍÎÃÎ ÐÀÂÍÎÂÅÑÍÎÃÎ ÏÎÈÑÊÀ ÐÅØÅÍÈß
ÇÀÄÀ×È Î ÌÀÊÑÈÌÀËÜÍÎÌ ÂÇÂÅØÅÍÍÎÌ ÐÀÇÐÅÇÅ ÃÐÀÔÀ
Êëþ÷åâûå ñëîâà: ìàêñèìàëüíûé âçâåøåííûé ðàçðåç ãðàôà, ìåòîä ãëîáàëüíîãî
ðàâíîâåñíîãî ïîèñêà, âû÷èñëèòåëüíûé ýêñïåðèìåíò, ýôôåêòèâíîñòü àëãîðèòìà.
Çàäà÷à î ìàêñèìàëüíîì âçâåøåííîì ðàçðåçå ãðàôà èìååò ìíîãî÷èñëåííûå ïðàê-
òè÷åñêèå ïðèëîæåíèÿ [1]. Ïîñêîëüêó îíà ÿâëÿåòñÿ êëàññè÷åñêîé ïðîáëåìîé äèñ-
êðåòíîé îïòèìèçàöèè, åé ïîñâÿùåíî ìíîãî ïóáëèêàöèé, íàïðèìåð [1–6].
 ïîñëåäíèå ãîäû âñå áîëüøå âíèìàíèÿ ïðèâëåêàåò ìåòîä ãëîáàëüíîãî ðàâíîâåñ-
íîãî ïîèñêà (ÃÐÏ) [7, 8]. Äëÿ ðåøåíèÿ çàäà÷è î ìàêñèìàëüíîì ðàçðåçå ãðàôà ðàçðàáîòà-
íû [9, 10] ñïåöèàëüíûå àëãîðèòìû GES (ÃÐÏ) Tabu è GES Pr_LocS, îñíîâàííûå íà èñ-
ïîëüçîâàíèè ýòîãî ìåòîäà è ñïåöèôèêè çàäà÷è. Àíàëèç ðåçóëüòàòîâ ïðîâåäåííûõ ýêñïå-
ðèìåíòàëüíûõ èññëåäîâàíèé ïîêàçàë, ÷òî îíè ïðåâîñõîäÿò èçâåñòíûå àëãîðèòìû êàê ïî
ñêîðîñòè ïîëó÷åíèÿ íàèëó÷øèõ ðåøåíèé, òàê è ïî èõ êà÷åñòâó. Òàê, ïðè ðåøåíèè 44
òåñòîâûõ çàäà÷ íàéäåíî 12 íîâûõ ðåêîðäîâ, äëÿ âñåõ îñòàëüíûõ òåñòîâ (êðîìå îäíîãî)
áûëè ïîëó÷åíû èçâåñòíûå ðåêîðäû. Ñëåäóåò çàìåòèòü, ÷òî ïî ñâîåé ïðàêòè÷åñêîé ýô-
ôåêòèâíîñòè ìåòîä ÃÐÏ ÿâíî âûäåëÿåòñÿ ñðåäè ìåòîäîâ äèñêðåòíîé îïòèìèçàöèè.
 íàñòîÿùåé ñòàòüå äëÿ ðåøåíèÿ ðàññìàòðèâàåìîé çàäà÷è ïðåäëàãàåòñÿ ìî-
äèôèêàöèÿ àëãîðèòìà GES Tabu, ïðèâîäÿòñÿ ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ èñ-
ñëåäîâàíèé íà ðàñøèðåííîì ìíîæåñòâå òåñòîâûõ çàäà÷, ïîäòâåðæäàþùèå
ïðåèìóùåñòâà ìåòîäà ÃÐÏ.
Ïðåäïîëîæèì, ÷òî çàäàí íåîðèåíòèðîâàííûé ãðàô G G V E� ( , ) ñ ìíîæåñòâà-
ìè âåðøèíV è ðåáåð E. Êàæäîìó ðåáðó ( , )i j E� ãðàôà ñîîòâåòñòâóåò âåñ wij � 0 .
Ðàçðåçîì ãðàôà G íàçûâàåòñÿ ðàçáèåíèå ( , )V V1 2 ìíîæåñòâà åãî âåðøèí V íà äâà
íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà: V1 è V2 , òàêèå, ÷òî i V� 1 , j V� 2 . Î÷åâèäíî,
÷òî ëþáîå òàêîå ðàçáèåíèå ïîðîæäàåò ðàçðåç ãðàôà.
Çàäà÷à î ìàêñèìàëüíîì âçâåøåííîì ðàçðåçå íåîðèåíòèðîâàííîãî ãðàôà
(MAX-CUT) G ñîñòîèò â íàõîæäåíèè ðàçðåçà ìàêñèìàëüíîãî ñóììàðíîãî âåñà
w V V wij
i V j V i j E
( , )
, , ( , )
1 2
1 2
�
� � �
� .
Ðàññìàòðèâàåìàÿ çàäà÷à ÿâëÿåòñÿ NP-òðóäíîé äàæå â ñëó÷àå, êîãäà âñå ðåáðà
èìåþò åäèíè÷íûé âåñ. Îñíîâíîé òðóäíîñòüþ ïðè åå ðåøåíèè ÿâëÿåòñÿ ýêñïîíåí-
öèàëüíûé ðîñò âû÷èñëèòåëüíûõ çàòðàò ïðè óâåëè÷åíèè ðàçìåðíîñòè çàäà÷è. Ïî-
ýòîìó ïðè èññëåäîâàíèè ýòîãî êëàññà çàäà÷ áîëüøèõ ðàçìåðíîñòåé ýôôåêòèâíû
òîëüêî ïðèáëèæåííûå ìåòîäû.
Çàäà÷ó î ìàêñèìàëüíîì âçâåøåííîì ðàçðåçå ãðàôà ìîæíî çàïèñàòü â
âèäå çàäà÷è áóëåâà êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ áåç îãðàíè÷åíèé
(UBQP). Ñîïîñòàâèì êàæäîé âåðøèíå ðàçáèåíèÿ ( , )V V1 2 ãðàôà G áóëåâó ïå-
ðåìåííóþ xi . Åñëè i V� 1 , òî xi � 0 , â ïðîòèâíîì ñëó÷àå xi �1 , i V� 2 . Òîãäà çà-
äà÷à ïðèíèìàåò âèä: íàéòè
max ( ) ( )
{ , } ( , )x
ij
i j E
i j
i
f x w x x
� �
� �
�
�
�
�
�
0 1
2 . (1)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 101
© Â.Ï. Øèëî, Î.Â. Øèëî, Â.À. Ðîùèí, 2012
Îäíàêî ñâåäåíèå èñõîäíîé çàäà÷è ê ìîäåëè (1) è ïðèìåíåíèå ê íåé èçâåñòíûõ àë-
ãîðèòìîâ [11, 12] íå áûëî áû ñòîëü ýôôåêòèâíûì. Ïîýòîìó äëÿ çàäà÷è î ìàêñè-
ìàëüíîì ðàçðåçå ãðàôà áûëè ðàçðàáîòàíû, êàê îòìå÷àëîñü âûøå, ñïåöèàëüíûå àë-
ãîðèòìû ÃÐÏ, äàëüíåéøåìó ðàçâèòèþ êîòîðûõ è ïîñâÿùåíà íàñòîÿùàÿ ðàáîòà.
Êëþ÷åâûìè ìîìåíòàìè ìåòîäà ÃÐÏ ÿâëÿþòñÿ ãåíåðàöèÿ ðåøåíèÿ è ïîèñê
ëîêàëüíîãî ìàêñèìóìà â îêðåñòíîñòè ýòîãî ðåøåíèÿ. Ðàññìîòðèì îñîáåííîñòè
ïðèìåíåíèÿ ýòîãî ìåòîäà íà ïåðâîì ýòàïå.
Ïðåäïîëîæèì, ÷òî
S x S xj j
1 1� � �{ | } , S x S xj j
0 0� � �{ | } , j n�1, ..., ,
ãäå S — ïîäìíîæåñòâî ìíîæåñòâà äîïóñòèìûõ ðåøåíèé çàäà÷è (1), íàéäåí-
íûõ ìåòîäîì ÃÐÏ. Ïîñêîëüêó «òåìïåðàòóðíûé» öèêë ÿâëÿåòñÿ îñíîâíûì â
ñòðóêòóðå ìåòîäà ÃÐÏ, òî äëÿ íåãî ñëåäóåò çàäàòü òàêèå ïàðàìåòðû: K — ÷èñ-
ëî âûïîëíåíèé òåìïåðàòóðíîãî öèêëà; � � �� � �( )0 � K , � � �0 1� � �� K , —
âåêòîð òåìïåðàòóðíûõ ïàðàìåòðîâ, èíäåêñû êîìïîíåíòîâ êîòîðîãî îòâå÷àþò
íîìåðàì òåìïåðàòóðíîãî öèêëà. Âåêòîð � äàåò âîçìîæíîñòü óïðàâëÿòü áëè-
çîñòüþ ãåíåðèðóåìîãî íà÷àëüíîãî ðåøåíèÿ ê ëó÷øåìó ðåøåíèþ ~ (~ ~ )x x xn� � �1 �
èç ìíîæåñòâà S , òàê êàê ýòî ðåøåíèå ïîëó÷àåòñÿ ñëó÷àéíûì èçìåíåíèåì êîìïî-
íåíòîâ âåêòîðà ~x ïî òàêîìó ïðàâèëó: åñëè ~x j � 0 , òî ýòîò êîìïîíåíò èçìåíÿåòñÿ
ñ âåðîÿòíîñòüþ p j k( )� , â ïðîòèâíîì ñëó÷àå — ñ âåðîÿòíîñòüþ 1� p j k( )� .
Âåðîÿòíîñòè p j k( )� ãåíåðèðîâàíèÿ íà÷àëüíûõ ðåøåíèé âû÷èñëÿþòñÿ, èñ-
õîäÿ èç ïîíÿòèé, çàèìñòâîâàííûõ èç ìåòîäà îòæèãà [13], è çàâèñÿò îò òåêóùåé
òåìïåðàòóðû �k è íàéäåííîãî ðàíåå ïîäìíîæåñòâà S ìíîæåñòâà äîïóñòèìûõ ðå-
øåíèé. Îíè ðàññ÷èòûâàþòñÿ äëÿ j n�1, ..., , k K�1, ..., ïî îäíîé èç ôîðìóë:
p
p
p
E E
j k
j
j
i i ij i j
( )
( )
( )
exp ( )(
�
�
�
� �
�
�
�
� �� �
1
1
1 1
2
0
0
1
0
1
0 � �
�
�
�
�
�
�
�
� E Eij i j
i
k
1
1
1
0
1
)
,
ãäå
E
S u
f x f x f x
k j
u
j
u
k
x�
� � �
�
�
0 0 1, , { , },
( )exp{ ( ( ) (~ ))}
åñëè
�
S
k
x S
j
uj
u
j
u
f x f x
S
�
� �
� �
�
�
�
exp{ ( ( ) (~ ))}
,
�
, åñëè
èëè
p
f x
f x
j k
k
x S
k
x S
j
( )
exp( ( ))
exp( ( ))
�
�
�
�
�
�
�
�
�
�
1
,
èëè
p
p
p
f f
j k
j
j
k j j
( )
( )
( )
exp{( )}( )
�
�
�
� �
�
�
�
� �
1
1
1 0
0
0
0 1
, (2)
ãäå f f xj
u
x S j
u
�
�
max ( ) , u �{ , }0 1 .
 ðàññìàòðèâàåìîé ìîäèôèêàöèè àëãîðèòìà ÃÐÏ êîìïîíåíòû âåêòîðà âåðî-
ÿòíîñòè ðàññ÷èòûâàþòñÿ ïî ôîðìóëå (2).
Çíà÷åíèÿ �k , k K� 0, ,� , îïðåäåëÿþùèå êðèâóþ îòæèãà, îáû÷íî âû÷èñëÿ-
þòñÿ ïî ôîðìóëàì �0 0� , � ��k k� �1 , k K� �1 1, ..., . Âåëè÷èíû �1 è � �1 ïîä-
áèðàþòñÿ òàê, ÷òîáû âåêòîð âåðîÿòíîñòè p K( )� äëÿ ïîñëåäíåãî òåìïåðàòóðíîãî
102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
öèêëà áûë ïðèáëèçèòåëüíî ðàâåí ðåêîðäíîìó ðåøåíèþ èç ìíîæåñòâà S . Êðèâàÿ
îòæèãà óíèâåðñàëüíà è èñïîëüçóåòñÿ ïðè ðåøåíèè âñåõ çàäà÷. Ìàñøòàáèðóþòñÿ
òîëüêî êîýôôèöèåíòû öåëåâîé ôóíêöèè òàêèì îáðàçîì, ÷òîáû çíà÷åíèå îæèäàå-
ìîãî ðåêîðäà ðàâíÿëîñü çàäàííîé âåëè÷èíå. Ñëåäóåò îòìåòèòü, ÷òî íà âòîðîì
ýòàïå ìåòîäà ÃÐÏ â êà÷åñòâå ïîèñêîâîãî âûáðàí àëãîðèòì òàáó è ó÷òåíà ñïåöè-
ôèêà ðàññìàòðèâàåìîé çàäà÷è.
Äëÿ ñðàâíèòåëüíîãî èññëåäîâàíèÿ ýôôåêòèâíîñòè ðàçðàáîòàííîãî è ñóùåñò-
âóþùèõ àëãîðèòìîâ áûëè ïðîâåäåíû ýêñïåðèìåíòàëüíûå ðàñ÷åòû ïî ðåøåíèþ
òåñòîâûõ çàäà÷ èç [14] è óâåëè÷åíî èõ êîëè÷åñòâî. Òàêèå çàäà÷è îáû÷íî èñïîëü-
çóþòñÿ äëÿ òåñòîâûõ ðàñ÷åòîâ è âêëþ÷àþò òîðîèäàëüíûå, ïëàíàðíûå è ñëó÷àé-
íûå ãðàôû. Êàê è â ðàáîòå [6], ðàññìàòðèâàëèñü ïåðâûå 54 çàäà÷è.
Àëãîðèòì ÃÐÏ ðåàëèçîâàí íà ÿçûêå Ñ++, âñå âû÷èñëèòåëüíûå ýêñïåðèìåíòû
ïðîâîäèëèñü ñ èñïîëüçîâàíèåì PC ñ Intel® Core QUAD CPU Q9550 2.83GHz è
8.0GB îïåðàòèâíîé ïàìÿòè. Êàæäàÿ çàäà÷à ðåøàëàñü 20 ðàç, âûäåëåííûé äëÿ íåå
ëèìèò âðåìåíè ñîñòàâëÿë îäèí ÷àñ. Ïàðàìåòðû àëãîðèòìà ÃÐÏ áûëè îïðåäåëåíû
òàêèì îáðàçîì.  íà÷àëå êàæäîãî òåìïåðàòóðíîãî öèêëà p j ( ) /�0 1 2� ,
j n�1, ..., . Äëÿ òåìïåðàòóðíîãî ðàñïèñàíèÿ èñïîëüçîâàíû ñëåäóþùèå çíà÷å-
íèÿ: �0 0� , �1 � 7*10 coef-7 / , � �
�
k k�
�
�1
110
48
log( / ) logcoef
ïðè k K� �2, , ,
K � 50 , coef �18 108. * / ( )f x BKS , x BKS — èçâåñòíîå ðåêîðäíîå ðåøåíèå çàäà÷è.
Íåêîòîðûå ðåçóëüòàòû ýòèõ èññëåäîâàíèé ïðèâåäåíû â òàáë. 1. Ïîñêîëüêó ïðè
ïðîâåäåíèè ðàñ÷åòîâ êàæäàÿ çàäà÷à ðåøàëàñü 20 ðàç ïðè äâàäöàòè ðàçëè÷íûõ íà÷àëü-
íûõ ïðèáëèæåíèÿõ, òî ñëåäóåò ðàññìàòðèâàòü ñðåäíèå âåëè÷èíû, êàñàþùèåñÿ öåëå-
âîé ôóíêöèè è âðåìåíè ðåøåíèÿ çàäà÷.  òàáëèöå ïðèíÿòû ñëåäóþùèå îáîçíà÷åíèÿ:
BKS — èçâåñòíûé èç ëèòåðàòóðû ðåêîðä äëÿ çàäà÷è, Best GES è BFS — ëó÷øèå ðå-
çóëüòàòû, ïîëó÷åííûå ñîîòâåòñòâåííî àëãîðèòìàìè ÃÐÏ [9,10] è èññëåäóåìûì àëãî-
ðèòìîì (â ñêîáêàõ óêàçàíî ÷èñëî íàéäåííûõ ðåêîðäîâ ïðè äâàäöàòè ïîïûòêàõ ðåøå-
íèÿ), Value — ñðåäíåå çíà÷åíèå öåëåâîé ôóíêöèè; tmin è tñð — ñîîòâåòñòâåííî ìè-
íèìàëüíîå è ñðåäíåå âðåìÿ (â ñåê) íàõîæäåíèÿ ðåêîðäà,
~
tñð — ñðåäíåå âðåìÿ (â ñåê)
ðåøåíèÿ îäíîé çàäà÷è. Óëó÷øåííûé ñ ïîìîùüþ àëãîðèòìà ÃÐÏ èçâåñòíûé èç ëèòå-
ðàòóðû ðåêîðä âûäåëåí ïîëóæèðíûì êóðñèâîì.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 103
Òàáëèöà 1
Çàäà÷à
×èñëî âåðøèí
ãðàôà
BKS Best GES BFS Value t min tñð
~
tñð
1 2 3 4 5 6 7 8 9
G1 800 11624 11624 11624(20) 11624,00 0,47 3,25 3,25
G2 800 11620 11620 11620(20) 11620,00 1,98 8,04 8,04
G3 800 11622 11622 11622(20) 11622,00 2,09 4,91 4,91
G4 800 11646 11646(20) 11646,00 0,39 7,83 7,83
G5 800 11631 11631(20) 11631,00 0,44 5,39 5,39
G6 800 2178 2178(20) 2178,00 2,89 5,76 5,76
G7 800 2003 2006(20) 2006,00 2,86 7,07 7,07
G8 800 2003 2005(20) 2005,00 4,02 12,15 12,15
G9 800 2048 2054(20) 2054,00 1,95 6,22 6,22
G10 800 1994 2000(20) 2000,00 2,19 10,84 10,84
G11 800 564 564 564(20) 564,00 0,61 0,98 0,98
G12 800 556 556 556(20) 556,00 0,78 1,53 1,53
G13 800 582 582 582(20) 582,00 0,88 1,39 1,39
G14 800 3063 3064 3064(20) 3064,00 7,58 337,00 337,00
G15 800 3050 3050 3050(20) 3050,00 2,25 16,33 16,33
G16 800 3052 3052 3052(20) 3052,00 2,22 18,91 18,91
G17 800 3043 3047(20) 3047,00 7,25 97,68 97,68
G18 800 988 992(20) 992,00 1,86 127,40 127,40
104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4
1 2 3 4 5 6 7 8 9
G19 800 903 906(20) 906,00 1,88 17,10 17,10
G20 800 941 941(20) 941,00 1,17 1,59 1,59
G21 800 931 931(20) 931,00 1,88 6,79 6,79
G22 2000 13358 13359 13359(20) 13359,00 21,81 92,60 92,60
G23 2000 13354 13342 13342(20) 13342,00 15,53 266,42 266,42
G24 2000 13331 13337 13337(20) 13337,00 36,09 391,13 391,13
G25 2000 13326 13340(20) 13340,00 20,22 306,81 306,81
G26 2000 13314 13328(19) 13327,90 17,69 1069,62 1026,01
G27 2000 3318 3341(20) 3341,00 38,75 393,68 393,68
G28 2000 3285 3298(20) 3298,00 39,66 630,14 630,14
G29 2000 3389 3405(20) 3405,00 17,27 189,53 189,53
G30 2000 3403 3413(20) 3413,00 15,77 140,97 140,97
G31 2000 3288 3310(20) 3310,00 42,31 336,01 336,01
G32 2000 1402 1410 1410(20) 1410,00 5,2 46,38 46,38
G33 2000 1376 1382 1382(20) 1382,00 26,95 239,26 239,26
G34 2000 1372 1384 1384(20) 1384,00 4,91 56,65 56,65
G35 2000 7672 7686 7686(12) 7685,55 186,78 996,26 1066,24
G36 2000 7670 7677 7680(1) 7676,65 3100,63 3100,63 1242,00
G37 2000 7681 7691 7691(3) 7690,10 611,14 1803,06 1561,45
G38 2000 7681 7687(20) 7687,00 13,05 381,45 381,45
G39 2000 2395 2408(20) 2408,00 21,83 191,86 191,86
G40 2000 2387 2400(11) 2399,55 465,92 1738,83 1033,28
G41 2000 2398 2405(20) 2405,00 10,42 43,45 43,45
G42 2000 2469 2481(20) 2481,00 6,02 212,21 212,21
G43 1000 6660 6660 6660(20) 6660,00 7,69 18,61 18,61
G44 1000 6650 6650 6650(20) 6650,00 4,95 10,89 10,89
G45 1000 6654 6654 6654(20) 6654,00 10,02 62,29 62,29
G46 1000 6645 6649(20) 6649,00 6,52 27,68 27,68
G47 1000 6656 6657(20) 6657,00 7,55 26,52 26,52
G48 3000 6000 6000 6000(20) 6000,00 0,01 0,05 0,05
G49 3000 6000 6000 6000(20) 6000,00 0 0,16 0,16
G50 3000 5880 5880 5880(20) 5880,00 0,02 0,08 0,08
G51 1000 3846 3848(20) 3848,00 3,25 117,45 117,45
G52 1000 3849 3851(20) 3851,00 12,61 158,16 158,16
G53 1000 3846 3850(18) 3849,90 73,76 908,81 827,05
G54 1000 3846 3852(20) 3852,00 19,58 329,19 329,19
sg3dl101000 1000 896 896 896(20) 896,00 2,15 8,09 8,09
sg3dl102000 1000 900 900 900(20) 900,00 1,2 2,13 2,13
sg3dl103000 1000 892 892 892(20) 892,00 1,58 6,33 6,33
sg3dl104000 1000 898 898 898(20) 898,00 1,59 7,96 7,96
sg3dl105000 1000 886 886 886(20) 886,00 2,17 27,99 27,99
sg3dl106000 1000 888 888 888(20) 888,00 1,34 2,04 2,04
sg3dl107000 1000 900 900 900(20) 900,00 1,92 68,04 68,04
sg3dl108000 1000 882 882 882(20) 882,00 2,04 15,10 15,10
sg3dl109000 1000 902 902 902(20) 902,00 1,72 7,84 7,84
sg3dl1010000 1000 894 894 894(20) 894,00 1,25 3,07 3,07
sg3dl141000 2744 2446 2446 2446(19) 2445,90 16,74 577,25 573,96
sg3dl142000 2744 2458 2458 2458(20) 2458,00 9,95 93,52 93,52
sg3dl143000 2744 2442 2442 2442(20) 2442,00 149,01 1125,69 1125,69
sg3dl144000 2744 2450 2450 2450(15) 2449,50 43,58 1135,02 998,35
sg3dl145000 2744 2446 2446 2446(20) 2446,00 8,94 104,75 104,75
sg3dl146000 2744 2450 2450 2452(15) 2451,50 54,98 1372,25 1069,78
sg3dl147000 2744 2444 2444 2444(20) 2444,00 14,54 354,47 354,47
sg3dl148000 2744 2446 2448 2448(15) 2447,50 15,51 1186,50 986,67
sg3dl149000 2744 2424 2426 2426(20) 2426,00 9,66 208,53 208,53
sg3dl1410000 2744 2458 2458 2458(19) 2457,90 12,56 1109,46 1060,13
(Ïðîäîëæåíèå òàáë. 1)
Íà îñíîâàíèè àíàëèçà ðåçóëüòàòîâ ýêñïåðèìåíòàëüíûõ ðàñ÷åòîâ ìîæíî ñäå-
ëàòü âûâîä î âûñîêîé ýôôåêòèâíîñòè è êîíêóðåíòîñïîñîáíîñòè ìåòîäà ÃÐÏ ïðè
ðåøåíèè ýòîãî êëàññà çàäà÷. Ñ åãî ïîìîùüþ óëó÷øåíû ðåêîðäû äëÿ 37 çàäà÷, äëÿ
îñòàëüíûõ — íàéäåíû èçâåñòíûå ðåêîðäû. Ïî áûñòðîäåéñòâèþ ìåòîä ÃÐÏ òàêæå
ïðåâîñõîäèò èçâåñòíûå ìåòîäû. Òàêèì îáðàçîì, íà ñåãîäíÿøíèé äåíü îí, áåññïîð-
íî, ÿâëÿåòñÿ ëó÷øèì ìåòîäîì ðåøåíèÿ çàäà÷ î ìàêñèìàëüíîì ðàçðåçå ãðàôà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. P o l j a k S . , T u z a Z . Maximum cuts and large bipartite subgraphs // DIMACS Series in Discrete
Mathematics and Theoretical Computer Science. — 1995. — 20. — P. 181–244.
2. B u r e r S . , M o n t e i r o R . D . C . , Z h a n g Y . Rank-two relaxation heuristics for MAX-CUT and
other binary quadratic programs // SIAM J. on Optimization. — 2002. — 12. — P. 503–521.
3. F e s t a P . , P a r d a l o s P . M . , R e s e n d e M . G . C . , R i b e i r o C . C . Randomized heuristics for
the maxcut problem // Optimization Methods and Software. — 2002. — 17. — P. 1033 — 1058.
4. G o e m a n s M . X . , W i l l i a m s o n D . P . Improved approximation algorithms for maximum cut and
satisfiability problems using semidefinite programming // J. of ACM. — 1995. — 42. — P. 1115–1145.
5. P a l u b e c k i s G . , K r i v i c k i e n e V . Application of multistart tabu search to the MAX-CUT prob-
lem // Information Technology and Control. — Kaunas: Technologija. — 2004. — 2(31). — P. 29–35.
6. M a r t i R . , D u a r t e A . , L a g u n a M . Advanced scatter search for the MAX-CUT problem //
INFORMS J. on Computing. — 2009. — 21, N 1. — P. 26–38.
7. Ø è ë î Â . Ï . Ìåòîä ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
1999. — ¹ 1. — Ñ. 74–81.
8. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû
ðåøåíèÿ, èññëåäîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 2003. — 264 ñ.
9. Ø è ë î  . Ï . , Ø è ë î Î .  . Ðåøåíèå çàäà÷è î ìàêñèìàëüíîì ðàçðåçå ãðàôà ìåòîäîì ãëîáàëüíîãî
ðàâíîâåñíîãî ïîèñêà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 5. — Ñ. 68–79.
10. S h y l o V . P . , S h y l o O . V . Path relinking scheme for the MAX-CUT problem within global
equilibrium search // International Journal of Swarm Intelligence Research (IJSIR) — 2011. — 2,
N 2. — P. 42–51.
11. P a r d a l o s P . , P r o k o p y e v O . , S h y l o O . , S h y l o V . Global equilibrium search applied to
the unconstrained binary quadratic optimization problem // Optimization Methods and Software. —
2008. — 23. — P. 129–140.
12. Ø è ë î  . Ï . , Ø è ë î Î .  . Ðåøåíèå çàäà÷è áóëåâà êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ áåç
îãðàíè÷åíèé ìåòîäîì ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà // Êèáåðíåòèêà è ñèñòåìíûé àíà-
ëèç. — 2011. — ¹ 6. — Ñ. 68–78.
13. K i r k p a t r i c k S . , G e l a t t i C . D . , V e c c h i M . P . Optimization by simulated annealing // Sci-
ence. — 1983. — 220. — P. 671–680.
14. H e l m b e r g C . , R e n d l F . A spectral bundle method for semidefinite programming // SIAM J.
on Optimization. — 2000. — 10. — P. 673–696.
Ïîñòóïèëà 05.10.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 4 105
|
| id | nasplib_isofts_kiev_ua-123456789-84128 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T16:17:47Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шило, В.П. Шило, О.В. Рощин, В.А. 2015-07-03T09:16:51Z 2015-07-03T09:16:51Z 2012 Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа / В.П. Шило, О.В. Шило, В.А. Рощин // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 101-105. — Бібліогр.: 14 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84128 519.854 Розроблено новий, оснований на використанні методу глобального рівноважного пошуку (ГРП) алгоритм розв’язання задачі про максимальний зважений розріз графу. Проведено його порівняльне дослідження з найкращими на даний час алгоритмами розв’язання цієї задачі. Показано переваги алгоритму ГРП як за швидкодією, так і за можливістю отримання кращих розв’язків. A new algorithm based on the global equilibrium search (GES) is developed to solve the weighted MAXCUT problem. A comparison study of the algorithm and currently the best algorithm for solving this problem was conducted. The advantages of the GES algorithm both in the performance and the possibility of finding the best solutions are shown. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа Метод глобального рівноважного пошуку розв’язання задачі про максимальний зважений розріз графу Solving the weighted MAXCUT problem by the global equilibrium search Article published earlier |
| spellingShingle | Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа Шило, В.П. Шило, О.В. Рощин, В.А. Системный анализ |
| title | Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа |
| title_alt | Метод глобального рівноважного пошуку розв’язання задачі про максимальний зважений розріз графу Solving the weighted MAXCUT problem by the global equilibrium search |
| title_full | Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа |
| title_fullStr | Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа |
| title_full_unstemmed | Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа |
| title_short | Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа |
| title_sort | метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84128 |
| work_keys_str_mv | AT šilovp metodglobalʹnogoravnovesnogopoiskarešeniâzadačiomaksimalʹnomvzvešennomrazrezegrafa AT šiloov metodglobalʹnogoravnovesnogopoiskarešeniâzadačiomaksimalʹnomvzvešennomrazrezegrafa AT roŝinva metodglobalʹnogoravnovesnogopoiskarešeniâzadačiomaksimalʹnomvzvešennomrazrezegrafa AT šilovp metodglobalʹnogorívnovažnogopošukurozvâzannâzadačípromaksimalʹniizvaženiirozrízgrafu AT šiloov metodglobalʹnogorívnovažnogopošukurozvâzannâzadačípromaksimalʹniizvaženiirozrízgrafu AT roŝinva metodglobalʹnogorívnovažnogopošukurozvâzannâzadačípromaksimalʹniizvaženiirozrízgrafu AT šilovp solvingtheweightedmaxcutproblembytheglobalequilibriumsearch AT šiloov solvingtheweightedmaxcutproblembytheglobalequilibriumsearch AT roŝinva solvingtheweightedmaxcutproblembytheglobalequilibriumsearch |