Решение задачи о максимальном разрезе графа методом глобального равновесного поиска
Запропоновано підхід до розв’язання задачі про максимальний розріз неорієнтованого графа. Він базується на використанні методу глобального рівноважного пошуку, який на даний час є одним із найефективніших методів дискретного програмування. Досліджено ефективність запропонованого алгоритму....
Gespeichert in:
| Datum: | 2010 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/45627 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Решение задачи о максимальном разрезе графа методом глобального равновесного поиска / В.П. Шило, О.В. Шило // Кибернетика и системный анализ. — 2010. — № 5. — С. 68-79. — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-45627 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-456272013-06-17T03:15:13Z Решение задачи о максимальном разрезе графа методом глобального равновесного поиска Шило, В.П. Шило, О.В. Системный анализ Запропоновано підхід до розв’язання задачі про максимальний розріз неорієнтованого графа. Він базується на використанні методу глобального рівноважного пошуку, який на даний час є одним із найефективніших методів дискретного програмування. Досліджено ефективність запропонованого алгоритму. An approach is proposed to the solution of the max-cut problem. It is based on the use of the global equilibrium search method that is one of the most efficient discrete programming methods at the present time. The efficiency of the proposed algorithm is investigated. 2010 Article Решение задачи о максимальном разрезе графа методом глобального равновесного поиска / В.П. Шило, О.В. Шило // Кибернетика и системный анализ. — 2010. — № 5. — С. 68-79. — Бібліогр.: 14 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45627 519.854 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Шило, В.П. Шило, О.В. Решение задачи о максимальном разрезе графа методом глобального равновесного поиска Кибернетика и системный анализ |
| description |
Запропоновано підхід до розв’язання задачі про максимальний розріз неорієнтованого графа. Він базується на використанні методу глобального рівноважного пошуку, який на даний час є одним із найефективніших методів дискретного програмування. Досліджено ефективність запропонованого алгоритму. |
| format |
Article |
| author |
Шило, В.П. Шило, О.В. |
| author_facet |
Шило, В.П. Шило, О.В. |
| author_sort |
Шило, В.П. |
| title |
Решение задачи о максимальном разрезе графа методом глобального равновесного поиска |
| title_short |
Решение задачи о максимальном разрезе графа методом глобального равновесного поиска |
| title_full |
Решение задачи о максимальном разрезе графа методом глобального равновесного поиска |
| title_fullStr |
Решение задачи о максимальном разрезе графа методом глобального равновесного поиска |
| title_full_unstemmed |
Решение задачи о максимальном разрезе графа методом глобального равновесного поиска |
| title_sort |
решение задачи о максимальном разрезе графа методом глобального равновесного поиска |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/45627 |
| citation_txt |
Решение задачи о максимальном разрезе графа методом глобального равновесного поиска / В.П. Шило, О.В. Шило // Кибернетика и системный анализ. — 2010. — № 5. — С. 68-79. — Бібліогр.: 14 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šilovp rešeniezadačiomaksimalʹnomrazrezegrafametodomglobalʹnogoravnovesnogopoiska AT šiloov rešeniezadačiomaksimalʹnomrazrezegrafametodomglobalʹnogoravnovesnogopoiska |
| first_indexed |
2025-07-04T04:29:37Z |
| last_indexed |
2025-07-04T04:29:37Z |
| _version_ |
1836689299624427520 |
| fulltext |
ÓÄÊ 519.854
Â.Ï. ØÈËÎ, Î.Â. ØÈËÎ
ÐÅØÅÍÈÅ ÇÀÄÀ×È Î ÌÀÊÑÈÌÀËÜÍÎÌ ÐÀÇÐÅÇÅ ÃÐÀÔÀ
ÌÅÒÎÄÎÌ ÃËÎÁÀËÜÍÎÃÎ ÐÀÂÍÎÂÅÑÍÎÃÎ ÏÎÈÑÊÀ
Êëþ÷åâûå ñëîâà: ðàçðåç ãðàôà, ïðèáëèæåííûå ìåòîäû, ìåòîä ãëîáàëüíîãî
ðàâíîâåñíîãî ïîèñêà, âû÷èñëèòåëüíûé ýêñïåðèìåíò, ýôôåêòèâíîñòü àëãîðèòìà.
Çàäà÷à î ìàêñèìàëüíîì ðàçðåçå ãðàôà (MAXCUT), âûçûâàþùàÿ â ïîñëåäíèå äâà
äåñÿòèëåòèÿ áîëüøîé èíòåðåñ ó èññëåäîâàòåëåé, ÿâëÿåòñÿ êëàññè÷åñêîé ïðîáëå-
ìîé äèñêðåòíîé îïòèìèçàöèè ñ ìíîãî÷èñëåííûìè ïðàêòè÷åñêèìè ïðèëîæåíèÿìè
[1–3]. Äëÿ åå ðåøåíèÿ â äàííîé ðàáîòå ïðåäëàãàåòñÿ àëãîðèòì, îñíîâàííûé íà
èñïîëüçîâàíèè ìåòîäà ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà (ÃÐÏ) [4], êîòîðûé íà-
øåë ïðèìåíåíèÿ ïðè ðåøåíèè ðàçëè÷íûõ êëàññîâ çàäà÷ äèñêðåòíîé îïòèìèçàöèè
ñëîæíîé ïðèðîäû [5–8]. Ïðîâåäåíî ñðàâíèòåëüíîå èññëåäîâàíèå ýôôåêòèâíîñòè
ïðåäëîæåííîãî àëãîðèòìà è ëó÷øèõ, èçâåñòíûõ íà äàííûé ìîìåíò, ïðèáëèæåí-
íûõ àëãîðèòìîâ ðåøåíèÿ ðàññìàòðèâàåìîé çàäà÷è, ïîäòâåðäèâøåå ïðåèìóùåñòâà
àëãîðèòìà ÃÐÏ êàê ïî áûñòðîäåéñòâèþ, òàê è ïî êà÷åñòâó ïîëó÷àåìûõ ðåøåíèé.
Ïóñòü çàäàí íåîðèåíòèðîâàííûé ãðàô G G V E� ( , ) ñ ìíîæåñòâîì âåðøèí V,
ìíîæåñòâîì ðåáåð E è êàæäîìó ðåáðó ( , )i j E� ãðàôà ïîñòàâëåíî â ñîîòâåòñòâèå
÷èñëî w
ij
, íàçûâàåìîå âåñîì ðåáðà ( , )i j . Ïðåäïîëîæèì, ÷òî ( , )V V1 2 — ðàçáèåíèå
ìíîæåñòâà V âåðøèí ãðàôà G íà äâà íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà — V1 è V2 .
Òîãäà ïîäìíîæåñòâî ðåáåð ( , )i j E� , îáëàäàþùèõ ñâîéñòâîì i V�
1
, j V� 2 , íàçûâà-
åòñÿ ðàçðåçîì ( , )V V1 2 ãðàôà G. Î÷åâèäíî, ÷òî ëþáîå òàêîå ðàçáèåíèå ïîðîæäàåò
ðàçðåç ãðàôà.
Çàäà÷à î ìàêñèìàëüíîì ðàçðåçå íåîðèåíòèðîâàííîãî ãðàôà G ñîñòîèò â îòûñ-
êàíèè òàêîãî ðàçáèåíèÿ ìíîæåñòâà V âåðøèí íà íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà
V
1
è V2 , ÷òîáû ñóììà âåñîâ w V V w
i V j V i j E
ij
( , )
, ,( , )
1 2
1 2
�
� � �
� ðåáåð ñîîòâåòñòâóþùåãî
ðàçðåçà áûëà ìàêñèìàëüíîé.
Îñòàíîâèìñÿ êðàòêî íà àíàëèçå ñîâðåìåííîãî ñîñòîÿíèÿ ìåòîäîâ ðåøåíèÿ ðàñ-
ñìàòðèâàåìîé çàäà÷è, êîòîðàÿ ÿâëÿåòñÿ NP-òðóäíîé äàæå â ñëó÷àå, êîãäà âñå ðåáðà
èìåþò åäèíè÷íûé âåñ. Ïîýòîìó îáúåì âû÷èñëåíèé â òî÷íûõ àëãîðèòìàõ îáû÷íî
ýêñïîíåíöèàëüíî ðàñòåò ñ ðîñòîì ðàçìåðíîñòè çàäà÷è, ÷òî äàåò èì âîçìîæíîñòü
ïðàêòè÷åñêè ðåøàòü òîëüêî çàäà÷è ìàëûõ èëè ñðåäíèõ ðàçìåðíîñòåé.
Äëÿ çàäà÷ áîëüøèõ ðàçìåðíîñòåé ýôôåêòèâíû ïðèáëèæåííûå ìåòîäû, êîòî-
ðûì ïîñâÿùåíî ìíîãî ïóáëèêàöèé, íàïðèìåð [3, 9–11]. Â ðàáîòå [9] ïðåäëîæåí àë-
ãîðèòì CirCut. Ïðîâåäåííûå ñ ýòèì àëãîðèòìîì ýêñïåðèìåíòàëüíûå ðàñ÷åòû ïîêà-
çàëè, ÷òî ïî êà÷åñòâó ïîëó÷àåìûõ ðåøåíèé è âðåìåíè èõ íàõîæäåíèÿ îí ïðåâîñõî-
äèò âñå èçâåñòíûå íà ìîìåíò åãî ïîÿâëåíèÿ ïðèáëèæåííûå àëãîðèòìû.
Ïðåäëîæåííûå â [10] øåñòü àëãîðèòìîâ áàçèðóþòñÿ íà ìåòîäîëîãèè ïîèñêà
ðåøåíèÿ ñ ïåðåìåííîé îêðåñòíîñòüþ (VNS), æàäíîé àäàïòèâíîé ïîèñêîâîé ïðîöå-
äóðû (GRASP) è ïðîöåäóðû ñîåäèíåíèÿ ïîëó÷åííûõ ðåøåíèé ïóòÿìè (Path
Relinking). Ïîêàçàíî, ÷òî ñ ïîìîùüþ àëãîðèòìà VNSPR [10] îòûñêèâàþòñÿ êà÷åñ-
òâåííûå ðåøåíèÿ çà ñ÷åò î÷åíü áîëüøèõ âû÷èñëèòåëüíûõ çàòðàò.  ðàáîòå [12] ðàñ-
ñìîòðåí ðàíäîìèçèðîâàííûé àëãîðèòì, ãàðàíòèðîâàííàÿ òî÷íîñòü êîòîðîãî ïðè
68 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
© Â.Ï. Øèëî, Î.Â. Øèëî, 2010
ïîëîæèòåëüíûõ âåñàõ ñîñòàâëÿåò 0,878 îò îïòèìàëüíîãî çíà÷åíèÿ öåëåâîé ôóíê-
öèè. Îäíàêî ýòîò àëãîðèòì òðåáóåò áîëüøîãî îáúåìà âû÷èñëåíèé. Òàê, äëÿ ðåøå-
íèÿ çàäà÷è ñ ÷èñëîì âåðøèí n � 200 åìó íåîáõîäèìî îêîëî òðåõ ÷àñîâ ìàøèííîãî
âðåìåíè. Äâå ìîäèôèêàöèè, RRT è MST, ìóëüòèñòàðòíîãî àëãîðèòìà òàáó îïèñàíû
â [11]. Â ðàáîòå [13] ïðåäëîæåí àëãîðèòì SS, áàçèðóþùèéñÿ íà èñïîëüçîâàíèè ìå-
òîäà ðàçáðîñà. Âñå ýòè àëãîðèòìû íà íàñòîÿùèé ìîìåíò ÿâëÿþòñÿ ëó÷øèìè. Ìíîãî
âàæíûõ ðåçóëüòàòîâ, êàñàþùèõñÿ ðåøåíèÿ çàäà÷è î ìàêñèìàëüíîì ðàçðåçå ãðàôà,
ïðèâåäåíî â îáçîðå [3].
Ââåäåì ñëåäóþùèå ïåðåìåííûå:
x
i V
i V i n
i �
�
� �
�
�
�
0
1 1
1
2
, ,
, , , , .
åñëè
åñëè �
Òîãäà çàäà÷ó î ìàêñèìàëüíîì ðàçðåçå ãðàôà ìîæíî ñôîðìóëèðîâàòü êàê çàäà÷ó
áóëåâà êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ áåç îãðàíè÷åíèé (UBQP): íàéòè
max ( ) ( )
,
( , )
x
ij
i j E
i j
i
f x w x x
� �
� �
�
�
�
�
�
�
{ }0 1
2 . (1)
 òî æå âðåìÿ çàäà÷à î ìàêñèìàëüíîì ðàçðåçå ãðàôà ñâîäèòñÿ ê âçâåøåííîé çàäà÷å
î ìàêñèìàëüíîé âûïîëíèìîñòè WMAX-2-SAT. Äåéñòâèòåëüíî, ïîñòàâèì â ñîîòâåò-
ñòâèå êàæäîìó ðåáðó ( , )i j äâå ëîãè÷åñêèå ôîðìóëû: x x
i j
è x xi j
ñ âåñîì wij .
Òåïåðü ìîæíî ïîêàçàòü, ÷òî ðàññìàòðèâàåìûé â çàäà÷å MAXCUT ãðàô G èìååò
ðàçðåç âåñà w* òîãäà è òîëüêî òîãäà, êîãäà ñîîòâåòñòâóþùàÿ âçâåøåííàÿ çàäà÷à
î ìàêñèìàëüíîé âûïîëíèìîñòè èìååò ðåøåíèå ñ ñóììàðíûì âåñîì w wij
i j E
*
( , )
�
�
� .
 ðàáîòàõ [7, 8] íà îñíîâå îáùåé ñõåìû ìåòîäà ÃÐÏ ïðåäëîæåíû àëãîðèòìû
ðåøåíèÿ çàäà÷è áóëåâà êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ è âçâåøåííîé çàäà÷è
î ìàêñèìàëüíîé âûïîëíèìîñòè (WMAX-SAT), êîòîðûå ïîêàçàëè âûñîêóþ ýôôåê-
òèâíîñòü ïðè ðåøåíèè ýòèõ çàäà÷. Ïîëó÷åííûå ðåçóëüòàòû ïîçâîëÿþò íàäåÿòüñÿ íà
óñïåõ è ïðè èñïîëüçîâàíèè ìåòîäà ÃÐÏ äëÿ çàäà÷è î ìàêñèìàëüíîì ðàçðåçå
íåîðèåíòèðîâàííîãî ãðàôà.
Î÷åâèäíî, ÷òî ñâåäåíèå ðàññìàòðèâàåìîé çàäà÷è ê íàçâàííûì äâóì ìîäåëÿì è
ïðèìåíåíèå ê íèì èçâåñòíûõ àëãîðèòìîâ ÃÐÏ [7, 8] íå áûëî áû ñòîëü ýôôåêòèâ-
íûì, ïîýòîìó äëÿ çàäà÷è î ìàêñèìàëüíîì ðàçðåçå íåîðèåíòèðîâàííîãî ãðàôà ðàçðà-
áîòàí ñïåöèàëüíûé àëãîðèòì, îñíîâàííûé íà èñïîëüçîâàíèè ìåòîäà ÃÐÏ è
ñïåöèôèêè ýòîé çàäà÷è.
Íàèëó÷øåå èç âñåõ äîïóñòèìûõ ðåøåíèé çàäà÷è, ðàññìîòðåííûõ ê äàííîìó
øàãó âû÷èñëèòåëüíîãî ïðîöåññà, áóäåì íàçûâàòü ðåêîðäíûì, à ñîîòâåòñòâóþùåå
åìó çíà÷åíèå öåëåâîé ôóíêöèè — ðåêîðäîì.
Ïîñêîëüêó îáùàÿ ñõåìà ìåòîäà ÃÐÏ (GES) ïîäðîáíî îïèñàíà â [5], ïðåäñòà-
âèì áàçèðóþùèéñÿ íà åå èñïîëüçîâàíèè àëãîðèòì ðåøåíèÿ ðàññìàòðèâàåìîé çàäà-
÷è â âèäå ñëåäóþùåé ïðîöåäóðû:
procedure GES
1 initialization algorithm s parameters ngen maxnfai_ ' _ ( , l K, , )� ,
� — vector of temperature values, K — number of temperature stages,
maxnfail — restart parameter, ngen — # of solutions generated during
each stage, P �� — set of forbidden solutions, xbest � 0 (zero vector)
2 while (stopping criterion = FALSE) do
3 if (
~
S �� ) then {
~
S — ìíîæåñòâî èçâåñòíûõ ðåøåíèé}
4 x construct random solution� _ _
5 x xmax � ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 69
6
~
maxS x� (set of found solutions)
7 end if
8 nfail � 0
9 while (nfail maxnfail� AND f x f xbest( ) ( )max � ��) do
10 x xoldmax � max
11 for k � 0 to K do
12 calculate generation probabilities pr Sk_ _ ( ,
~
)
13 for g � 0 to ngen do
14 x generate solution x pr max distk
k� _ ( , , _ )max
15 R search method x� _ ( )
16 R R P� \
17
~ ~
S S R� �
18 x f xgood
x S
�
�
arg max
~
( )
19 if f x f xgood( ) ( )max� then
20 x xgoodmax �
21 if f x f xbest( ) ( )max � then x xbest � max
22 end if
23 end for
24 end for
25 if ( f old x f x( _ ) ( )max max� ) then nfail nfail� �1
26 else nfail � 0
27
~
maxS x�{ }
28 end while
29 P P x� � max
30
~
S ��
31 end while
end GES
stopping criterion ={ processing time sec� 360 . OR f x record fbest( ) _� }
Ðàññìîòðèì áîëåå äåòàëüíî ýòó ïðîöåäóðó. Âíåøíèé öèêë (öèêë èòåðàöèé,
ñòðîêè 2–31) îáåñïå÷èâàåò ïîâòîðÿåìîñòü ïîèñêà íàèëó÷øåãî ðåøåíèÿ.  íåì ëèáî
ïðîâîäèòñÿ çàäàííîå êîëè÷åñòâî ïîâòîðîâ, ëèáî îí âûïîëíÿåòñÿ äî óñòàíîâëåíèÿ
èñòèííîñòè íåêîòîðîãî êðèòåðèÿ îñòàíîâà (íàïðèìåð, íàõîæäåíèÿ ðåêîðäà, íå
õóæå èçâåñòíîãî).
Îñíîâíûì â ñòðóêòóðå àëãîðèòìà ÃÐÏ ÿâëÿåòñÿ «òåìïåðàòóðíûé» öèêë (ñòðî-
êè 11–24), äëÿ êîòîðîãî íåîáõîäèìî çàäàòü çíà÷åíèÿ âåëè÷èí K è «òåìïåðàòóðû»
�k , k K� 0, ,� . Â ýòîì öèêëå ïðîâîäèòñÿ ñåðèÿ ñòàðòîâ ïîèñêà íàèëó÷øåãî ðåøå-
íèÿ äëÿ âîçðàñòàþùèõ çíà÷åíèé «òåìïåðàòóðû». «Òåìïåðàòóðíûé» öèêë è åãî ïî-
âòîðåíèÿ ïîçâîëÿþò ãèáêî ÷åðåäîâàòü ðåæèìû ñóæåíèÿ è ðàñøèðåíèÿ îáëàñòè
ïîèñêà ðåøåíèÿ, ÷òî â èòîãå ïðèâîäèò ê âûñîêîé ýôôåêòèâíîñòè ìåòîäà ÃÐÏ.
Ïóñòü
~
S — ïîäìíîæåñòâî ìíîæåñòâà S äîïóñòèìûõ ðåøåíèé ðàññìàòðèâàå-
ìîé çàäà÷è, íàéäåííûõ àëãîðèòìîì ÃÐÏ,
~
|
~
,S x x S xj j
1 1� � �{ },
~
|
~
,S x x S xj j
0 0� � �{ }, j n�1, ,� .
Åñëè ìíîæåñòâî
~
S ïóñòî, òî îïåðàòîðû ñòðîê 4–6 ïîçâîëÿþò íàéòè ïåðâîå ðå-
øåíèå è èíèöèàëèçèðîâàòü íåîáõîäèìûå äàííûå. Ñëåäóåò îòìåòèòü, ÷òî íàéäåí-
íûå àëãîðèòìîì ÃÐÏ ðåøåíèÿ íå çàïîìèíàþòñÿ, à èñïîëüçóþòñÿ äëÿ âû÷èñëåíèÿ
òàêèõ âåëè÷èí:
~
( )exp ( )
exp ( )
~
~
E
f x f x
f xkj
l
k
x S
k
x S
j
l
j
l
�
�
�
�
�
�
�
{ }
{ }
�
�
, k K� 0, ,� , l � 0 1, , j n�1, ,� .
70 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
Ýòè âåëè÷èíû ïîçâîëÿþò îïðåäåëèòü êîìïîíåíòû âåêòîðà âåðîÿòíîñòè
~ ( ~ , , ~ )p p pk k
n
k�
1
� â ñîîòâåòñòâèè ñî ñëåäóþùåé ôîðìóëîé (ñì., íàïðèìåð, [5]):
~
~
~
exp , (
~ ~ ~ ~
p
p
p
E E E E
j
k
k
k ij i j ij i
�
�
�
� � � �
� �
1
1
1
0 50
0
0
1
0 1
1
1
0
1
1j
i
k
i i)( )
�
�
�� �
�
�
�
�
�
� �
. (2)
Î÷åâèäíî, ÷òî âåðîÿòíîñòè ~pk ãåíåðèðîâàíèÿ íà÷àëüíûõ ðåøåíèé (ñòðîêà 12)
äëÿ ïðîöåäóðû ãåíåðàöèÿ_ðåøåíèÿ ( )x (ñòðîêà 14) âû÷èñëÿþòñÿ èñõîäÿ èç ïîíÿòèé,
çàèìñòâîâàííûõ èç ìåòîäà îòæèãà, è çàâèñÿò îò òåêóùåé «òåìïåðàòóðû» �k è íàé-
äåííîãî ðàíåå ìíîæåñòâà
~
S äîïóñòèìûõ ðåøåíèé.
Îïðåäåëÿþùèå êðèâóþ îòæèãà çíà÷åíèÿ �k , k K� 0, ,� , îáû÷íî âû÷èñëÿþòñÿ ïî
ôîðìóëàì � � ��
�
� ��0 1, k k , k K� �1 1, ,� . Âåëè÷èíû �1 è � �1ïîäáèðàþòñÿ òàê,
÷òîáû | | ~ | |~maxx pK� � 0 , ãäå xmax — ðåêîðäíîå ðåøåíèå. Êðèâàÿ îòæèãà óíèâåðñàëüíà è
íå íàñòðàèâàåòñÿ íà îòäåëüíóþ çàäà÷ó, à èñïîëüçóåòñÿ ïðè ðåøåíèè âñåõ çàäà÷. Ìàñøòà-
áèðóþòñÿ òîëüêî êîýôôèöèåíòû öåëåâîé ôóíêöèè òàêèì îáðàçîì, ÷òîáû çíà÷åíèå ðå-
êîðäà ðàâíÿëîñü çàäàííîé âåëè÷èíå. Âñå êîìïîíåíòû âåêòîðà ~p0 îäèíàêîâû.
Óëó÷øàþùèé öèêë (ñòðîêè 9–28) âûïîëíÿåòñÿ äî òåõ ïîð, ïîêà maxnfail ðàç íå
ïðîèçîéäåò óëó÷øåíèÿ ðåøåíèÿ xmax . Ïðîöåäóðà calculate generation probabilities_ _
(ñòðîêà 12) ïîçâîëÿåò âû÷èñëÿòü âåðîÿòíîñòè ñëó÷àéíîãî âîçìóùåíèÿ ðåøåíèÿ xmax
ïî ôîðìóëå (2). Öèêë íàõîæäåíèÿ íîâûõ ðåøåíèé (ñòðîêè 13–23) ïîâòîðÿåòñÿ çàäàí-
íîå ÷èñëî ngen ðàç. Ñ ïîìîùüþ ïðîöåäóðû ãåíåðàöèÿ_ðåøåíèÿ ñëó÷àéíûì îáðàçîì
ãåíåðèðóåòñÿ ðåøåíèå x , êîòîðîå ÿâëÿåòñÿ íà÷àëüíûì äëÿ ïðîöåäóðû ìåòîä_ïîèñêà
(ñòðîêà 16). Ïðè ìàëûõ «òåìïåðàòóðàõ» �k âîçìóùåíèå ðåøåíèÿ xmax íîñèò ñëó÷àé-
íûé, ðàâíîâåðîÿòíûé õàðàêòåð, ïðè áîëüøèõ «òåìïåðàòóðàõ» çíà÷åíèÿ êîìïîíåíòîâ,
îäèíàêîâûõ äëÿ ëó÷øèõ íàéäåííûõ ðåøåíèé, èçìåíÿþòñÿ ìàëî. «Òåìïåðàòóðíûé»
öèêë ïîçâîëÿåò îñóùåñòâëÿòü äèâåðñèôèêàöèþ ïîèñêà ðåøåíèÿ (ïðè ìàëûõ «òåìïå-
ðàòóðàõ») è åãî èíòåíñèôèêàöèþ (ïðè áîëüøèõ «òåìïåðàòóðàõ»). Òàêèì îáðàçîì, ïî
ìåðå ïîâûøåíèÿ «òåìïåðàòóðû» ãåíåðèðóåìûå ðåøåíèÿ ïðèîáðåòàþò ïðèçíàêè,
ïðèñóùèå ðåêîðäíûì ðåøåíèÿì, è â èòîãå ñõîäÿòñÿ ê ðåøåíèþ xmax .
Ïðèâåäåì ïðîöåäóðó ãåíåðàöèÿ_ðåøåíèÿ:
procedure ãåíåpàöèÿ påøåíèÿ x pr max distk
k_ ( , , _ )max
1 x x� max ; dist � 0 ; j �1
2 while ( j n� )
3 if x j �1 then
4 if ( ~ [ , ]p randomj
k � 01 ) then
5 x j � 0 ; dist dist� �1
6 g x( ) � ïåðåñ÷åò_âåêòîðà_ gains x( )
7 end if
8 end if
9 else
10 if ( ~ [ , ]p randomj
k � 01 ) then
11 x j �1; dist dist� �1
12 g x( ) � ïåðåñ÷åò_âåêòîðà_ gains x( )
13 end if
14 end else
15 j j� �1
16 if (dist max dist k� _ ) then break
17 ånd while
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 71
 ñòðîêå 1 ýòîé ïðîöåäóðû ïðîèñõîäèò ïðèñâîåíèå íà÷àëüíûõ çíà÷åíèé âåêòî-
ðó x è ïåðåìåííûì dist è j , â öèêëå ñòðîê 2–17 — âîçìóùåíèå âåêòîðà xmax . Ñëó-
÷àéíàÿ, ðàâíîìåðíî ðàñïðåäåëåííàÿ íà îòðåçêå [0,1] âåëè÷èíà random[ , ]01 (ñòðîêè 4
è 10) èñïîëüçóåòñÿ äëÿ ìîäåëèðîâàíèÿ ñëó÷àéíûõ ñîáûòèé, âåäóùèõ ê èçìåíåíèþ
ðåøåíèÿ xmax . Åñëè ðàññòîÿíèå ïî Õýììèíãó ìåæäó xmax è âîçìóùåííûì ðåøåíè-
åì x ñòàíîâèòñÿ ðàâíûì çàäàííîìó ïàðàìåòðó max dist k_ (ñòðîêà 16), öèêë âîçìó-
ùåíèÿ (ñòðîêè 2–17) çàêàí÷èâàåòñÿ. Ïàðàìåòð max dist k_ ìîæåò çàäàâàòüñÿ äèíàìè-
÷åñêè è çàâèñåòü îò «òåìïåðàòóðíîãî» èíäåêñà k .
Ïðè âûáîðå àëãîðèòìà äëÿ ïðîöåäóðû ìåòîä_ïîèñêà ó÷èòûâàåòñÿ ñïåöèôèêà
ðåøàåìîé çàäà÷è. Èñïîëüçóåòñÿ àëãîðèòì, ïîçâîëÿþùèé èíòåíñèôèöèðîâàòü ïîèñê
è ýôôåêòèâíî èññëåäîâàòü îêðåñòíîñòè íà÷àëüíîãî ðåøåíèÿ â öåëÿõ åãî óëó÷øå-
íèÿ. Â ïðîöåäóðå ìåòîä_ïîèñêà èñïîëüçîâàëèñü ðàíäîìèçèðîâàííûå àëãîðèòìû
òàáó è ëîêàëüíîãî ïîèñêà LocS. Ñ ïîìîùüþ ýòîé ïðîöåäóðû íàõîäèòñÿ ìíîæåñòâî
ëîêàëüíûõ (â îêðåñòíîñòè îïðåäåëåííîãî ðàäèóñà) ðåøåíèé, êîòîðûå ôîðìèðóþò
ìíîæåñòâî R. Ïðè ðåàëèçàöèè ðàññìàòðèâàåìîãî àëãîðèòìà ïîèñê çàïðåùåííûõ ðå-
øåíèé áëîêèðóåòñÿ, à ïåðåñ÷åò îñóùåñòâëÿåòñÿ ïî ìåðå íàõîæäåíèÿ íîâûõ ðåøå-
íèé x R� . Â ñòðîêå 20 îïðåäåëÿåòñÿ ðåøåíèå xmax , â ñòðîêå 21 — ëó÷øåå ðåøåíèå
xbest , íàéäåííîå àëãîðèòìîì ÃÐÏ. Ïîñëå îêîí÷àíèÿ óëó÷øàþùåãî öèêëà (ñòðî-
êè 9–28) ê ìíîæåñòâó P çàïðåùåííûõ òî÷åê äîáàâëÿåòñÿ òî÷êà xmax (ñòðîêà 29).
Ðàññìîòðèì àëãîðèòìû, èñïîëüçóåìûå â ïðîöåäóðå ìåòîä_ïîèñêà.
Ðåàëèçîâàíû è èññëåäîâàíû äâå âåðñèè ìåòîäà ëîêàëüíîãî ïîèñêà. Îíè îñíîâàíû
íà èñïîëüçîâàíèè îïåðàòîðà èíâåðñèè, êîòîðûé èçìåíÿåò çíà÷åíèå îòäåëüíîé áóëåâîé
ïåðåìåííîé xi íà åå îòðèöàíèå �xi , ò.å. xi íà 1�xi äëÿ i n�{ }1, ,� . Òàêèì îáðàçîì,
â ýòèõ àëãîðèòìàõ èñïîëüçîâàëàñü îêðåñòíîñòü åäèíè÷íîãî (ïî Õýììèíãó) ðàäèóñà.
Ñëåäóåò îòìåòèòü, ÷òî ïîñëå êàæäîãî èçìåíåíèÿ âåêòîðà x ïåðåñ÷èòûâàåòñÿ n -ìåð-
íûé âåêòîð g x( ) , îïðåäåëåííûé â îêðåñòíîñòè åäèíè÷íîãî ðàäèóñà ñ öåíòðîì
â òî÷êå x : g x f x x x x x f x x xj j j j n j n( ) ( , , , , , , ) ( , , , , )� � �� �1 1 1 11� � � � . Ïåðåñ-
÷åò ýòîãî âåêòîðà ñîîòâåòñòâóåò èäåîëîãèè ìåòîäà âåêòîðà ñïàäà [5] è ïîçâîëÿåò äëÿ
ìíîãèõ çàäà÷ ýêîíîìèòü çíà÷èòåëüíûå âû÷èñëèòåëüíûå ðåñóðñû. Òàê, äëÿ çàäà÷è áóëå-
âà êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ áåç îãðàíè÷åíèé âèäà (1) âû÷èñëåíèå öåëåâîé
ôóíêöèè òðåáóåò O n( )2 àðèôìåòè÷åñêèõ îïåðàöèé, à ïåðåñ÷åò âåêòîðà g x( ) — òîëüêî
O n( ) òàêèõ îïåðàöèé.
Ñàìûé ïðîñòîé àëãîðèòì ëîêàëüíîãî òèïà, èñïîëüçóåìûé â ïðîâåäåííûõ èññëå-
äîâàíèÿõ, — ëîêàëüíûé ïîèñê LocS. Ïðåäñòàâèì åãî â âèäå ñëåäóþùåé ïðîöåäóðû:
procedure LocS(x g x, ( ))
1 repeat
2 Generate random permutation RP of the set {1,…,n }
3 � � 0
4 for k �1 to n do
5 j RP k� [ ]
6 if g xj ( ) � 0 then
7 � �� � g xj ( )
8 x xj j� �1
9 g x x( ) ( )� recalculate gains
10 end if
11 end for
12 until � � 0 OR � � � �j j n g xj, : ( )1 0
13 return x
Èç ñòðîê 2, 5 äàííîé ïðîöåäóðû âûòåêàåò, ÷òî êîìïîíåíòû âåêòîðà x âûáèðà-
þòñÿ ñëó÷àéíûì îáðàçîì, à èç ñòðîêè 6 ñëåäóåò, ÷òî ïåðåõîä îñóùåñòâëÿåòñÿ è
â òî÷êè, íå óëó÷øàþùèå çíà÷åíèå öåëåâîé ôóíêöèè.
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
Âòîðûì àëãîðèòìîì ïîèñêà, èññëåäîâàííûì â ðàáîòå, ÿâëÿåòñÿ àëãîðèòì
òàáó [8], êîòîðûé ìîæíî ïðåäñòàâèòü â âèäå ñëåäóþùåé ïðîöåäóðû:
procedure Tabu(x g x n tabubad, ( ), , )
1 x xmax � ; step � 0 ; nfail � 0 ;
2 while (( ( ) ( ))maxnfail f x f x nfailbest� � �9 3AND OR ) do
3 �max � 0 ; �cur � 0 ; step stepimpr �
4 M n�{ }1, ,� ; last used j_ ( ) � ��, j M�
5 repeat
6 repeat
7 � � 0
8 Generate random permutation RP of the set M
9 for k �1 to | |M do
10 j RP k� [ ]
11 if (step last used j tabu f x g x f xj� � � �_ ( ) ( ) ( ) ( )maxOR ) then
12 if g xj ( ) � 0 then
13 � �� � g xj ( ) ; last used j step_ ( ) � ; x xj j� �1
14 g x( ) � recalculate gains(x); step step� �1
15 end if
16 end if
17 end for
18 � � �cur cur� �
19 until � � 0
20 if � �cur � max then
21 x xmax �
22 if � �cur � max then
23 � �max � cur ; step stepimpr � ; nfail � 0 ; break;
24 end if
25 end if
26 � � ��
27 for k �1 to | |M do
28 j RP k� [ ]
29 if (step last used j tabu f x g x f xj� � � �_ ( ) ( ) ( ) ( )maxOR ) then
30 if g xj ( ) � � then
31 � � g xj ( ) ; ind jbest �
32 end if
33 end if
34 end for
35 � � �cur cur� � ; last used ind stepbest_ ( ) � ; x xind indbest best
� �1
36 g x( ) � recalculate gains(x); step step� �1
37 if � �cur � max then
38 x xmax �
39 end if
40 until step step nimpr bad� �
41 if (step step nimpr bad� � ) then
42 x x� max ; g x( ) � recalculate gains (x)
43 nfail nfail� �1
44 end if
45 end while
46 return xmax
end Tabu
Îñíîâíîé îñîáåííîñòüþ ýòîãî âàðèàíòà àëãîðèòìà òàáó ÿâëÿåòñÿ öèêë ðåñòàð-
òîâ èç íàèëó÷øåãî íàéäåííîãî ðåøåíèÿ (ñòðîêè 2–45), ÷òî ïîçâîëÿåò èíòåíñèôèöè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 73
ðîâàòü ïîèñê. Â ñòðîêå 2 xbest — ëó÷øåå íàéäåííîå ðåøåíèå. Øàãè àëãîðèòìà òàáó
âûïîëíÿþòñÿ äî òåõ ïîð, ïîêà íå áóäåò íèêàêîãî óëó÷øåíèÿ çíà÷åíèÿ öåëåâîé
ôóíêöèè íà ïîñëåäíèõ nbad èòåðàöèÿõ (ñòðîêè 5–40).
Ïåðåéäåì òåïåðü ê îïèñàíèþ âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ, ïðîâåäåííûõ
â öåëÿõ èññëåäîâàíèÿ ýôôåêòèâíîñòè ðàçëè÷íûõ ïðèáëèæåííûõ àëãîðèòìîâ.
Àëãîðèòì ÃÐÏ ðåàëèçîâàí íà ÿçûêå Ñ++, âñå ðàñ÷åòû ïðîâîäèëèñü ñ èñïîëüçîâàíè-
åì PC ñ Intel® Core QUAD CPU Q9550 2.83GHz è 3.0GB îïåðàòèâíîé ïàìÿòè. Ïà-
ðàìåòðû àëãîðèòìà ÃÐÏ áûëè îäèíàêîâûìè âî âñåõ âû÷èñëèòåëüíûõ ýêñïåðèìåí-
òàõ: K � 21 , � � 4, max dist k_ : max dist n_ ,0 0 5� , max dist i_ � max dist_ 0 +
�
�
�
�
�
�
�
�
i
max dist
K
10
1
0_
, i K� �1 2, ,� , max distK_ � �1 20 ; ngen � 81 (äëÿ àëãîðèòìà
LocS ngen � 243), maxnfail �1.  íà÷àëå êàæäîãî «òåìïåðàòóðíîãî» öèêëà âñå êîì-
ïîíåíòû âåêòîðà ~p0 ðàâíû 0,5. Äëÿ «òåìïåðàòóðíîãî» ðàñïèñàíèÿ èñïîëüçîâàëèñü
ñëåäóþùèå çíà÷åíèÿ: �0 0� , �1
63 10� ! � , � �
�
k k�
�
�1
110
48
log log
äëÿ
k � 2 20, ,� , à äëÿ àëãîðèòìà òàáó — n nbad � / 10 ; tabu � 21.
Ýêñïåðèìåíòàëüíûå ðàñ÷åòû ïðîâîäèëèñü äëÿ äâóõ ìíîæåñòâ òåñòîâûõ çàäà÷:
24 çàäà÷è G1, G2, G3, G11, … , G16, G22, G23, G24, G32, … , G37, G43, G44, G45,
G48, G49 è G50, ïðèâåäåííûå â ðàáîòå [14], à òàêæå 20 çàäà÷ sg3dl101000, …
... , sg3dl1010000, sg3dl141000, … , sg3dl1410000 èç [9]. Ýòè çàäà÷è èñïîëüçîâàëèñü
ðàíåå àâòîðàìè ðàáîò [9–13] äëÿ ïðîâåðêè ýôôåêòèâíîñòè èõ àëãîðèòìîâ, ÷òî ïî-
çâîëèëî ìàêñèìàëüíî ðàñøèðèòü ìíîæåñòâî ñðàâíèâàåìûõ àëãîðèòìîâ.
Ýêñïåðèìåíòàëüíûå ðàñ÷åòû áûëè âûïîëíåíû â äâà ýòàïà. Íà ïåðâîì ýòàïå
ñðàâíèâàëèñü äâà âàðèàíòà ìåòîäà ÃÐÏ — GES LocS è GES Òabu. Ðåçóëüòàòû ýòîãî
èññëåäîâàíèÿ ïðåäñòàâëåíû â òàáë. 1. Â íåé (è â òàáë. 2–4) ïðèíÿòû ñëåäóþùèå
îáîçíà÷åíèÿ: BKS — èçâåñòíûé èç ëèòåðàòóðû ðåêîðä äëÿ çàäà÷è, BFS — ðåêîðä,
íàéäåííûé ñîîòâåòñòâóþùèì àëãîðèòìîì. Â êîëîíêå BFS GES òàáë. 1 ñîäåðæàòñÿ
ëó÷øèå ðåêîðäû, ïîëó÷åííûå ìåòîäîì ÃÐÏ (äâóìÿ âàðèàíòàìè). Ïîëóæèðíûì
øðèôòîì âûäåëåíû ëó÷øèå ðåçóëüòàòû. Åñëè GES óëó÷øèë ðåêîðä, èçâåñòíûé
â ëèòåðàòóðå, îí âûäåëåí ïîëóæèðíûì êóðñèâîì. Value â äàííîé òàáëèöå îáîçíà÷à-
åò ñðåäíåå çíà÷åíèå ðåêîðäà, íàéäåííîå â ðåçóëüòàòå äåñÿòèêðàòíîãî ðåøåíèÿ êàæ-
äîé çàäà÷è ïðè ðàçëè÷íûõ íà÷àëüíûõ ïàðàìåòðàõ àëãîðèòìà.  äâóõ ñòðîêàõ
òàáë. 1 ñî çíàêîì � äëÿ êàæäîãî ìíîæåñòâà òåñòîâûõ çàäà÷ ïðèâåäåíû ñóììàðíûå
çíà÷åíèÿ óêàçàííûõ â ñîîòâåòñòâóþùèõ êîëîíêàõ âåëè÷èí.
Àíàëèç ïðåäñòàâëåííûõ â òàáë. 1 ðåçóëüòàòîâ ïîêàçàë, ÷òî êàæäûé âàðèàíò ìå-
òîäà ÃÐÏ èìååò ñâîè äîñòîèíñòâà. Ñ ïîìîùüþ ïåðâîãî âàðèàíòà (GES LocS)
óñïåøíî ðåøåíû çàäà÷è ïåðâîãî ìíîæåñòâà — ïðàêòè÷åñêè çà îäèíàêîâîå âðåìÿ ñî
âòîðûì âàðèàíòîì (GES Tabu) îí íàõîäèë áîëåå êà÷åñòâåííûå ðåøåíèÿ. Îäíàêî
äëÿ òåñòîâûõ çàäà÷ âòîðîãî ìíîæåñòâà âàðèàíò GES Tabu ïðåâçîøåë ïåðâûé âàðè-
àíò êàê ïî áûñòðîäåéñòâèþ, òàê è ïî êà÷åñòâó íàéäåííûõ ðåøåíèé.
Ïðîâåäåííûå íà âòîðîì ýòàïå ýêñïåðèìåíòàëüíûå èññëåäîâàíèÿ ñîñòîÿò èç
äâóõ ÷àñòåé. Èõ ðåçóëüòàòû îòîáðàæåíû â òàáë. 2–4.  ïåðâîé ÷àñòè àëãîðèòì ÃÐÏ
ñðàâíèâàëñÿ ñ àëãîðèòìàìè SS [13], CirCut [9], VNSPR [10], à âî âòîðîé —
ñ àëãîðèòìàìè RRT è MST [11].
Ïðè ïðîâåäåíèè âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ ñ àëãîðèòìàìè RRT è MST [11]
êàæäàÿ òåñòîâàÿ çàäà÷à ïåðâîãî ìíîæåñòâà ðåøàëàñü äåñÿòü ðàç, ïðè÷åì âðåìÿ ðå-
øåíèÿ áûëî îãðàíè÷åíî 1800 ñåêóíäàìè äëÿ ãðàôîâ ñ ÷èñëîì âåðøèí n � 800
è 3600 ñåêóíäàìè — äëÿ ãðàôîâ ñ n �1000. Êàæäàÿ èç çàäà÷ âòîðîãî ìíîæåñòâà ðå-
øàëàñü ïÿòü ðàç, ïðè ýòîì âðåìÿ ðåøåíèÿ îãðàíè÷èâàëîñü 3600 ñåêóíäàìè äëÿ çà-
äà÷ ìàëûõ ðàçìåðíîñòåé è 7200 ñåêóíäàìè äëÿ çàäà÷ áîëüøèõ ðàçìåðíîñòåé.
Àëãîðèòìû ðåàëèçîâàíû íà ÿçûêå Ñ ñ èñïîëüçîâàíèåì PC Pentium III 800.
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 75
Ò à á ë è ö à 1
Çàäà÷à
Ðàç-
ìåð-
íîñòü
BKS
BFS Âðåìÿ, c Value
GES
GES
Tabu
GES
LocS
GES
Tabu
GES
LocS
GES
Tabu
GES
LocS
G1 800 11624 11624 11624 11624 2.91 4.80 11624.0 11624.0
G2 800 11620 11620 11620 11620 5.46 8.03 11620.0 11620.0
G3 800 11622 11622 11622 11622 2.33 3.51 11622.0 11622.0
G11 800 564 564 564 564 0.53 3.42 564.0 564.0
G12 800 556 556 556 556 1.12 1.73 556.0 556.0
G13 800 582 582 582 582 1.99 4.98 582.0 582.0
G14 800 3063 3064 3064 3064 155.25 164.34 3063.3 3063.5
G15 800 3050 3050 3050 3050 15.86 9.36 3050.0 3050.0
G16 800 3052 3052 3052 3052 32.82 27.58 3052.0 3052.0
G22 2000 13358 13359 13359 13359 86.60 98.61 13359.0 13358.5
G23 2000 13354 13342 13342 13342 97.67 40.77 13341.6 13342.0
G24 2000 13331 13337 13337 13337 212.57 174.36 13333.8 13335.6
G32 2000 1402 1410 1410 1410 56.46 158.86 1410.0 1409.2
G33 2000 1376 1382 1382 1382 88.67 104.54 1381.2 1379.6
G34 2000 1372 1384 1384 1384 60.93 164.65 1384.0 1383.6
G35 2000 7672 7684 7684 7684 152.25 216.61 7680.3 7681.1
G36 2000 7670 7676 7676 7677 166.75 139.63 7670.8 7672.6
G37 2000 7681 7689 7689 7689 159.22 180.38 7683.6 7684.6
G43 1000 6660 6660 6660 6660 15.11 17.34 6660.0 6660
G44 1000 6650 6650 6650 6650 10.42 3.61 6650.0 6650
G45 1000 6654 6654 6654 6654 49.98 42.64 6654.0 6654
G48 3000 6000 6000 6000 6000 0.04 0.38 6000.0 6000
G49 3000 6000 6000 6000 6000 0.17 0.32 6000.0 6000
G50 3000 5880 5880 5880 5880 0.08 13.53 5880.0 5880
� 150793 150841 150841 150842 1375.1 1583.98 150821.6 150824.3
sg3dl101000 1000 896 896 896 896 6.56 110.40 896.0 895.6
sg3dl102000 1000 900 900 900 900 1.11 2.87 900.0 900.0
sg3dl103000 1000 892 892 892 892 5.87 37.73 892.0 892.0
sg3dl104000 1000 898 898 898 898 2.59 6.78 898.0 898.0
sg3dl105000 1000 886 886 886 886 20.72 54.50 886.0 886.0
sg3dl106000 1000 888 888 888 888 3.42 8.58 888.0 888.0
sg3dl107000 1000 900 900 900 900 19.53 145.07 900.0 899.8
sg3dl108000 1000 882 882 882 882 27.99 101.77 882.0 881.8
sg3dl109000 1000 902 902 902 902 9.17 18.06 902.0 902.0
sg3dl1010000 1000 894 894 894 894 5.63 17.75 894.0 894.0
sg3dl141000 2744 2446 2446 2446 2444 174.01 160.00 2443.8 2438.8
sg3dl142000 2744 2458 2458 2458 2456 152.90 204.03 2457.8 2454.8
sg3dl143000 2744 2442 2440 2440 2438 196.93 163.01 2439.2 2437.0
sg3dl144000 2744 2450 2450 2450 2444 129.74 99.80 2447.6 2443.4
sg3dl145000 2744 2446 2446 2446 2446 131.22 91.24 2445.8 2443.2
sg3dl146000 2744 2450 2450 2450 2448 133.66 175.91 2450.0 2446.4
sg3dl147000 2744 2444 2444 2444 2442 141.64 207.36 2442.2 2439.0
sg3dl148000 2744 2446 2448 2448 2444 121.17 112.46 2445.4 2442.6
sg3dl149000 2744 2424 2426 2426 2422 62.90 163.57 2424.4 2421.2
sg3dl1410000 2744 2458 2458 2458 2456 169.34 161.38 2456.0 2453.0
� 33402 33404 33404 33378 1516.10 2042.27 33390.2 33356.6
Äëÿ ñðàâíåíèÿ ñ ìîäèôèöèðîâàííûì àëãîðèòìîì ðàçáðîñà SS èñïîëüçîâàëèñü
ïðîãðàììíûå ðåàëèçàöèè àëãîðèòìîâ CirCut è VNSPR. Âñå àëãîðèòìû èìåëè íà-
ñòðîéêè, ðåêîìåíäîâàííûå àâòîðàìè. Ñ èõ ïîìîùüþ ðåøàëàñü êàæäàÿ òåñòîâàÿ çà-
äà÷à îáîèõ ìíîæåñòâ áåç îãðàíè÷åíèÿ íà ëèìèò âðåìåíè. Èñïîëüçîâàëñÿ PC
3.2 GHz Intel Xenon processor ñ 2.0 GB îïåðàòèâíîé ïàìÿòè.
Ñâîäíûå ðåçóëüòàòû âòîðîãî ýòàïà ýêñïåðèìåíòàëüíûõ ðàñ÷åòîâ ïî ðåøåíèþ
óêàçàííûõ òåñòîâûõ çàäà÷ ðàçëè÷íûìè ïðèáëèæåííûìè àëãîðèòìàìè ïðåäñòàâëå-
íû â òàáë. 2.
76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
Ò à á ë è ö à 2
Çàäà÷à
Ðàçìåð-
íîñòü
BKS
BFS
GES SS CirCut VNSPR RRT MST
G1 800 11624 11624 11624 11624 11621 11624 11624
G2 800 11620 11620 11620 11617 11615 11620 11620
G3 800 11622 11622 11622 11622 11622 11622 11622
G11 800 564 564 562 560 564 564 562
G12 800 556 556 552 552 556 556 552
G13 800 582 582 578 574 580 580 576
G14 800 3063 3064 3060 3058 3055 3042 3063
G15 800 3050 3050 3049 3049 3043 3024 3050
G16 800 3052 3052 3045 3045 3043 3026 3052
G22 2000 13358 13359 13346 13346 13295 13235 13358
G23 2000 13354 13342 13317 13317 13290 13246 13329
G24 2000 13331 13337 13303 13314 13276 13241 13327
G32 2000 1402 1410 1398 1390 1396 1384 1392
G33 2000 1376 1382 1362 1360 1376 1358 1368
G34 2000 1376 1384 1364 1368 1372 1362 1368
G35 2000 7672 7685 7668 7670 7635 7590 7672
G36 2000 7670 7677 7660 7660 7632 7577 7669
G37 2000 7681 7689 7664 7666 7643 7589 7675
G43 1000 6660 6660 6656 6656 6659 6660 6660
G44 1000 6650 6650 6648 6643 6642 6650 6650
G45 1000 6654 6654 6642 6652 6646 6654 6650
G48 3000 6000 6000 6000 6000 6000
G49 3000 6000 6000 6000 6000 6000
G50 3000 5880 5880 5880 5880 5880
sg3dl101000 1000 896 896 882 880 892 892 896
sg3dl102000 1000 900 900 894 892 900 898 900
sg3dl103000 1000 892 892 884 882 884 886 888
sg3dl104000 1000 898 898 892 894 896 896 896
sg3dl105000 1000 886 886 880 882 882 884 884
sg3dl106000 1000 888 888 870 886 880 884 888
sg3dl107000 1000 900 900 890 894 896 898 898
sg3dl108000 1000 882 882 880 874 880 880 880
sg3dl109000 1000 902 902 888 890 898 900 902
sg3dl1010000 2744 894 894 886 886 890 890 892
sg3dl141000 2744 2446 2446 2428 2410 2416 2378 2438
sg3dl142000 2744 2458 2458 2418 2416 2416 2394 2448
sg3dl143000 2744 2442 2442 2410 2408 2406 2394 2434
sg3dl144000 2744 2450 2450 2422 2414 2418 2390 2436
sg3dl145000 2744 2446 2446 2416 2406 2416 2380 2432
sg3dl146000 2744 2450 2450 2424 2412 2420 2394 2440
sg3dl147000 2744 2444 2444 2404 2410 2404 2384 2434
sg3dl148000 2744 2446 2448 2416 2418 2418 2386 2434
sg3dl149000 2744 2424 2426 2412 2388 2384 2362 2416
sg3dl1410000 2744 2458 2458 2430 2420 2422 2402 2450
Àíàëèç ðåçóëüòàòîâ òàáë. 2 ïîêàçûâàåò, ÷òî ïî êà÷åñòâó íàéäåííûõ äëÿ çàäà÷
ïåðâîãî ìíîæåñòâà ðåøåíèé àëãîðèòì ÃÐÏ ïðåâîñõîäèò îñòàëüíûå, âûáðàííûå äëÿ
ñðàâíåíèÿ àëãîðèòìû. Êðîìå òîãî, äëÿ òåñòîâûõ çàäà÷ G13, G14, G22, G24,
G32–G37 ñ ïîìîùüþ àëãîðèòìà ÃÐÏ ïîëó÷åíû íîâûå ðåêîðäû.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 77
Ò à á ë è ö à 3
Çàäà÷à BFS
Âðåìÿ, c
SS CirCut VNSPR GES
G1 11624 139 352 22732 2.17
G2 11620 167.2 283 22719 2.79
G3 11622 180.1 330 23890 3.26
G11 564 171.8 74 10084 2.39
G12 556 241.5 58 10852 3.23
G13 580 227.5 62 10749 1.9
G14 3060 186.5 128 16734 10.16
G15 3049 142.8 155 17184 8.93
G16 3045 161.9 142 16562 3.77
G22 13346 1335.8 493 197654 51.03
G23 13317 1021.7 457 193707 5
G24 13314 1191 521 195749 12.31
G32 1398 900.6 221 82345 7.94
G33 1376 925.6 198 76282 9.3
G34 1372 950.2 237 79406 2.8
G35 7670 1257.5 440 167221 25.4
G36 7660 1391.9 400 167203 40.4
G37 7666 1386.8 382 170786 18.25
G43 6659 405.8 213 35324 6.8
G44 6648 355.9 192 34519 4.7
G45 6652 354.3 210 34179 22.41
G48 6000 20.1 119 64713 0.24
G49 6000 35.1 134 64749 0.27
G50 5880 26.8 231 147132 2.1
sg3dl101000 892 406.1 106.0 20409.0 3.03
sg3dl102000 900 302.4 116.0 20873.0 7.65
sg3dl103000 884 410.4 112.0 20574.0 0.75
sg3dl104000 896 485.9 103.0 19786.0 1.66
sg3dl105000 882 400.9 106.0 19160.0 1.82
sg3dl106000 886 461.8 119.0 17872.0 5.83
sg3dl107000 896 386.2 115.0 21044.0 2.28
sg3dl108000 880 466.9 104.0 19760.0 11.44
sg3dl109000 898 493.6 121.0 20930.0 4.35
sg3dl1010000 890 352.8 111.0 20028.0 2.87
sg3dl141000 2428 1320.6 382.0 188390.0 35.28
sg3dl142000 2418 1121.1 351.0 187502.0 2.51
sg3dl143000 2410 1215.8 377.0 190028.0 3.06
sg3dl144000 2422 1237.2 356.0 198809.0 4.95
sg3dl145000 2416 1122.5 388.0 196725.0 3.55
sg3dl146000 2424 1213.9 331.0 189366.0 3.69
sg3dl147000 2410 1230.6 381.0 187902.0 2.94
sg3dl148000 2418 1132.0 332.0 194838.0 3.41
sg3dl149000 2412 1213.9 333.0 193627.0 20.47
sg3dl1410000 2430 1125.8 391.0 196454.0 5.86
� 29277.8 10767.0 3986552.0 374.95
Ðåøåíèå òåñòîâûõ çàäà÷ âòîðîãî ìíîæåñòâà ñâÿçàíî ñî çíà÷èòåëüíûìè òðóä-
íîñòÿìè, ÷òî îáúÿñíÿåòñÿ ñïåöèôèêîé ýòèõ çàäà÷. Ãðàôû äëÿ çàäà÷ ñêîíñòðóèðîâà-
íû íà îñíîâå êóáè÷åñêèõ ðåøåòîê, ìîäåëèðóþùèõ èçèíãîâñêèå ñïèíû â ñëþäå,
à ðåøåíèÿ â êîëîíêå BKS ïîëó÷åíû àëãîðèòìîì H2 [9], êîòîðûé ñïåöèàëüíî ðàçðà-
áîòàí äëÿ ïîäîáíûõ ñòðóêòóð è ïðèìåíèì òîëüêî ê íèì. Êðîìå òîãî, òàêîå õîðî-
øåå êà÷åñòâî ðåøåíèé îáåñïå÷èâàåòñÿ î÷åíü áîëüøèì âðåìåíåì ñ÷åòà (íàïðèìåð,
äëÿ ðåøåíèÿ êàæäîé èç ïîñëåäíèõ äåñÿòè çàäà÷ ïîòðåáîâàëîñü îêîëî 33000 ñåêóíä
âðåìåíè ðàáîòû ÝÂÌ SGI Origin 2000 [9]). Íåñìîòðÿ íà ýòî, ìåòîäîì ÃÐÏ äëÿ çà-
äà÷ sg3dl148000, sg3dl149000 íàéäåíû íîâûå ðåêîðäû.
78 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
Çàäà÷à BFS
Âðåìÿ, c fñð
GES to BFS RRT MST RRT MST
G1 11624 2.91 15 147 11624 11610
G2 11620 5.46 180 195 11620 11607
G3 11622 2.33 54 278 11622 11611
G11 564 0.53 819 213 564 558
G12 556 1.12 736 181 554 547
G13 580 0.49 640 414 579 571
G14 3063 117.20 785 787 3037 3059
G15 3050 15.86 581 1109 3018 3047
G16 3052 32.82 683 916 3022 3048
G22 13358 73.14 2039 1519 13221 13306
G23 13329 22.84 2162 1634 13224 13302
G24 13327 157.47 1381 1824 13223 13308
G32 1392 1.21 1498 1290 1380 1385
G33 1368 1.71 1054 812 1355 1357
G34 1368 1.34 1803 1324 1359 1359
G35 7672 27.95 1200 2863 7582 7668
G36 7669 98.19 2557 2578 7571 7661
G37 7675 36.54 1974 2384 7582 7669
G43 6660 15.11 845 733 6660 6648
G44 6650 10.42 1484 478 6650 6639
G45 6654 49.98 800 596 6653 6640
sg3dl101000 896 6.56 961 1755 888.4 889.6
sg3dl102000 900 1.11 1438 2208 896.8 896.8
sg3dl103000 888 1.84 578 1616 884.4 883.2
sg3dl104000 896 0.57 1677 913 894.4 892.4
sg3dl105000 884 1.96 2163 1722 881.6 881.2
sg3dl106000 888 3.42 1735 1808 882.4 883.6
sg3dl107000 898 1.17 1619 2203 896 894.8
sg3dl108000 880 3.37 511 712 877.2 878.4
sg3dl109000 902 9.17 1472 1391 896.4 890.8
sg3dl1010000 892 2.14 1311 297 888.4 888
sg3dl141000 2438 39.46 4833 5265 2377.6 2425.2
sg3dl142000 2448 3.78 3035 4645 2392 2436.4
sg3dl143000 2434 19.76 4286 3878 2382 2422.4
sg3dl144000 2436 8.36 3279 3665 2384.8 2430.4
sg3dl145000 2432 5.13 3701 5871 2376.4 2424.4
sg3dl146000 2440 13.46 3614 2760 2388.4 2429.6
sg3dl147000 2434 13.26 2146 5405 2377.2 2420.4
sg3dl148000 2434 5.24 2864 5726 2382 2424.8
sg3dl149000 2416 24.16 4258 4784 2360.8 2406.4
sg3dl1410000 2450 29.88 3869 5099 2392.8 2433.2
� 868.4 72640 83998
Ò à á ë è ö à 4
Òàáë. 3 îòîáðàæàåò ðåçóëüòàòû ïåðâîé ÷àñòè ýêñïåðèìåíòàëüíûõ ðàñ÷åòîâ —
ñêîðîñòü ïîëó÷åíèÿ ëó÷øèõ ðåøåíèé àëãîðèòìàìè SS, CirCut, VNSPR è GES. Âî
âòîðîé êîëîíêå ñîäåðæàòñÿ íàèëó÷øèå ðåêîðäû, íàéäåííûå óêàçàííûìè àëãîðèò-
ìàìè. Â ñëåäóþùèõ òðåõ êîëîíêàõ ïðèâåäåíî âðåìÿ, ïîíàäîáèâøååñÿ ñîîòâåòñòâó-
þùèì àëãîðèòìàì äëÿ ïîëó÷åíèÿ èõ ðåêîðäíûõ ðåøåíèé (îíî íå ïåðåñ÷èòûâàëîñü
è ïðèâîäèòñÿ äëÿ ñîîòâåòñòâóþùèõ ìàøèí). Ñ ïîìîùüþ àëãîðèòìà ÃÐÏ êàæäàÿ çà-
äà÷à ðåøàëàñü äåñÿòü ðàç.  êîëîíêå GES ïðèâåäåíî ñðåäíåå âðåìÿ, çàòðà÷åííîå íà
ïîëó÷åíèå ðåøåíèé ñ ðåêîðäîì, íå õóæå ðåêîðäà èç êîëîíêè BFS, ò.å. ðåøåíèé, êî-
òîðûå ïî çíà÷åíèþ öåëåâîé ôóíêöèè íå óñòóïàþò ðåøåíèÿì, ñîâìåñòíî ïîëó÷åí-
íûì îñòàëüíûìè àëãîðèòìàìè. Òàêèì îáðàçîì, àíàëèç ðåçóëüòàòîâ òàáë. 3 ïîäòâåð-
æäàåò ïðåèìóùåñòâà àëãîðèòìà ÃÐÏ íàä àëãîðèòìàìè SS, CirCut, VNSPR è ïî ñêî-
ðîñòè ïîëó÷åíèÿ õîðîøèõ ðåøåíèé.
Ïåðåéäåì ê ðàññìîòðåíèþ âòîðîé ÷àñòè âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ.  ñî-
îòâåòñòâèè ñ ïëàíîì ýêñïåðèìåíòîâ, îïèñàííûõ â [11], ñ ïîìîùüþ àëãîðèòìà ÃÐÏ
äåñÿòü ðàç ðåøàëàñü êàæäàÿ çàäà÷à èç îáîèõ ìíîæåñòâ. Òàêæå ðåøàëèñü ïî äåñÿòü
ðàç ýòè çàäà÷è ñ èñïîëüçîâàíèåì àëãîðèòìîâ RRT è MST.  òàáë. 4 ïðèâåäåíû ïî-
ëó÷åííûå äàííûå.  êîëîíêàõ 3–5 äëÿ êàæäîé çàäà÷è óêàçàíî ñðåäíåå âðåìÿ åå ðå-
øåíèÿ ñîîòâåòñòâóþùèì àëãîðèòìîì, à â êîëîíêàõ 6, 7 — ñðåäíåå çíà÷åíèå ðåêîð-
äà ( fcp ). Êàê âèäíî, è â ýòîì ñëó÷àå àëãîðèòì ÃÐÏ ïðåâîñõîäèò àëãîðèòìû RRT è
MST êàê ïî êà÷åñòâó ïîëó÷àåìûõ ðåøåíèé, òàê è ïî âðåìåíè èõ íàõîæäåíèÿ.
Àíàëèç ïðèâåäåííûõ ðåçóëüòàòîâ âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ ñâèäåòåëüñòâó-
åò î âûñîêîé ýôôåêòèâíîñòè è êîíêóðåíòîñïîñîáíîñòè ìåòîäà ÃÐÏ ïðè ðåøåíèè çàäà-
÷è î ìàêñèìàëüíîì ðàçðåçå íåîðèåíòèðîâàííîãî ãðàôà. Áîëåå òîãî, îïûò, íàêîïëåííûé
ïðè ðåøåíèè äðóãèõ çàäà÷ [5–8], ïîçâîëÿåò íàäåÿòüñÿ, ÷òî äëÿ çàäà÷ áîëüøåé ðàçìåð-
íîñòè ïðåèìóùåñòâà àëãîðèòìîâ ÃÐÏ áóäóò òîëüêî âîçðàñòàòü.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. B a r a h o n a F . , G r o t s c h e l M . , J u n g e r M . , R e i n e l t G . An application of combinatorial op-
timization to statistical physics and circuit layout design // Oper. Res. — 1988. — 36. — P. 493–513.
2. C h a n g K . C . , D u D . H . - C . Efficient algorithms for layer assignment problem // IEEE Trans. Com-
puter — Aided Design of Integrated Circuits and Systems. — 1987. — 6. — P. 67–78.
3. 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.
4. Ø è ë î Â . Ï . Ìåòîä ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
1999. — ¹ 1. — Ñ. 74–81.
5. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû ðåøåíèÿ,
èññëåäîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 2003. — 264 ñ.
6. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Ïðîáëåìû äèñêðåòíîé îïòèìèçàöèè: ñëîæíûå çàäà÷è,
îñíîâíûå ïîäõîäû ê èõ ðåøåíèþ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 4. — Ñ. 3–25.
7. 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 // Optim. Methods and Software. — 2008. — 23. —
P. 129–140.
8. P r o k o p y e v O . , S h y l o O . , S h y l o V . Solving weighted MAX-SAT via global equilibrium search
// Oper. Res. Lett. — 2008. — 36, N 4. — P. 434-438.
9. 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. Optim. — 2002. — 12. — P. 503–521.
10. 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 // Optim. Methods and Software. — 2002. — 17. — P. 1033–1058.
11. 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 problem //
Information Technology and Control. — Kaunas: Technologija, 2004. — 2(31). — P. 29–35.
12. 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. ACM. — 1995. — 42. — P. 1115–1145.
13. 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. Computing. — 2009. — 21, N 1. — P. 26–38.
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. Optim.
— 2000. — 10. — P. 673–696.
Ïîñòóïèëà 25.04.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 79
|