Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска
Розроблено новий, оснований на використанні методу глобального рівноважного пошуку (ГРП) алгоритм розв’язання задачі бульового квадратичного програмування без обмежень. Проведено його порівняльне дослідження з кращими на даний час алгоритмами розв’язання цієї задачі. Показано переваги алгоритму ГРП...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84252 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска / В.П. Шило, О.В. Шило // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 68-78. — Бібліогр.: 23 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859836687967846400 |
|---|---|
| author | Шило, В.П. Шило, О.В. |
| author_facet | Шило, В.П. Шило, О.В. |
| citation_txt | Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска / В.П. Шило, О.В. Шило // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 68-78. — Бібліогр.: 23 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розроблено новий, оснований на використанні методу глобального рівноважного пошуку (ГРП) алгоритм розв’язання задачі бульового квадратичного програмування без обмежень. Проведено його порівняльне дослідження з кращими на даний час алгоритмами розв’язання цієї задачі. Показано переваги алгоритму ГРП як за швидкодією, так і за можливістю отримання кращих розв’язків.
A new algorithm based on the global equilibrium search (GES) is developed to solve the unconstrained binary quadratic programming (UBQP) problem. It is compared with currently the best techniques for the solution of this problem. The GES algorithm is shown to be better both in the speed and solution quality.
|
| first_indexed | 2025-12-07T15:35:15Z |
| format | Article |
| fulltext |
Â.Ï. ØÈËÎ, Î.Â. ØÈËÎ
ÓÄÊ 519.854 ÐÅØÅÍÈÅ ÇÀÄÀ×È ÁÓËÅÂÀ ÊÂÀÄÐÀÒÈ×ÍÎÃÎ
ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß ÁÅÇ ÎÃÐÀÍÈ×ÅÍÈÉ
ÌÅÒÎÄÎÌ ÃËÎÁÀËÜÍÎÃÎ ÐÀÂÍÎÂÅÑÍÎÃÎ
ÏÎÈÑÊÀ
Êëþ÷åâûå ñëîâà: áóëåâî êâàäðàòè÷íîå ïðîãðàììèðîâàíèå, ïðèáëèæåííûå ìå-
òîäû, ìåòîä ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà, âû÷èñëèòåëüíûé ýêñïåðèìåíò,
ñðàâíèòåëüíîå èññëåäîâàíèå àëãîðèòìîâ.
ÂÂÅÄÅÍÈÅ
Îáúåêòîì èññëåäîâàíèÿ íàñòîÿùåé ñòàòüè ÿâëÿåòñÿ èçâåñòíûé êëàññ öåëî÷èñ-
ëåííûõ îïòèìèçàöèîííûõ çàäà÷ âèäà
max ( ) |{ }f x q x x x Bij i j
j
n
n
i
n
� �
��
��
11
,
(1)
ãäå qij — ýëåìåíòû ñèììåòðè÷íîé äåéñòâèòåëüíîé ìàòðèöû Q ïîðÿäêà n,
B n — ìíîæåñòâî n-ìåðíûõ âåêòîðîâ ñ êîìïîíåíòàìè 0 èëè 1. Òàêàÿ çàäà÷à
íàçûâàåòñÿ çàäà÷åé áóëåâà êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ áåç îãðàíè÷åíèé
(UBQP). Ïîñêîëüêó x xi i
2 � äëÿ âñåõ ïåðåìåííûõ x i ni � �{ , }, , ,0 1 1 � , ëèíåé-
íàÿ ôóíêöèÿ cx (ïðè åå íàëè÷èè) ìîæåò áûòü ïåðåíåñåíà â êâàäðàòè÷íóþ
÷àñòü öåëåâîé ôóíêöèè â (1). Ê (1) ñâîäèòñÿ òàêæå êâàäðàòè÷íàÿ çàäà÷à âèäà
max | ,{ }xQx Dx b x B n� � , ãäå Q — ìàòðèöà èç (1), D R m n� � , b R n� , R n —
ìíîæåñòâî n-ìåðíûõ äåéñòâèòåëüíûõ âåêòîðîâ.
Ìíîãèå ôóíäàìåíòàëüíûå çàäà÷è èç îáëàñòè íàóêè, èíæåíåðèè, ôèíàíñîâ,
ìåäèöèíû è äð. ìîãóò áûòü ñôîðìóëèðîâàíû êàê çàäà÷è áóëåâà êâàäðàòè÷íîãî
ïðîãðàììèðîâàíèÿ. Êâàäðàòè÷íûå ôóíêöèè ñ áóëåâûìè ïåðåìåííûìè åñòåñòâåí-
íî âîçíèêàþò ïðè ìîäåëèðîâàíèè îòáîðîâ è âçàèìîäåéñòâèé. Ðàññìîòðèì ìíî-
æåñòâî èç n îáúåêòîâ, êàæäûé èç êîòîðûõ ìîæåò áûòü îòîáðàí èëè íå îòîáðàí.
Êàæäîé ïàðå ( , )i j îáúåêòîâ ñîîòâåòñòâóåò âåñ qij , êîòîðûé èçìåðÿåò âçàèìîäåé-
ñòâèå ìåæäó òî÷êàìè i è j. Ñ÷èòàåì xi �1, åñëè îáúåêò îòîáðàí, è xi � 0 â ïðîòèâ-
íîì ñëó÷àå. Ñóììà âñåõ âçàèìîäåéñòâèé ìåæäó îòîáðàííûìè òî÷êàìè, òàê íàçû-
âàåìîå ãëîáàëüíîå âçàèìîäåéñòâèå, ìîæåò áûòü ïðåäñòàâëåíà êàê êâàäðàòè÷íàÿ
áóëåâà ôóíêöèÿ q x xij i j
j
n
i
n
��
��
11
. Êëàññ òàêèõ çàäà÷ èññëåäîâàëñÿ â ôèçèêå òâåðäîãî
òåëà. Êðîìå òîãî, ïðèëîæåíèÿ âåðñèé çàäà÷è (1) ñ îãðàíè÷åíèÿìè è áåç îãðàíè÷å-
íèé ìîãóò áûòü íàéäåíû â ìíîãî÷èñëåííûõ îòðàñëÿõ, âêëþ÷àÿ ìåäèöèíó, ìà-
68 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
© Â.Ï. Øèëî, Î.Â. Øèëî, 2011
øèííîå ïðîåêòèðîâàíèå, ïëàíèðîâàíèå, óïðàâëåíèå ñîîáùåíèÿìè, õèìèþ [1, 2].
Ìíîãèå çàäà÷è ïî òåîðèè ãðàôîâ ìîãóò áûòü ïðåäñòàâëåíû â òåðìèíàõ êâàäðà-
òè÷íîãî áóëåâà ïðîãðàììèðîâàíèÿ, âêëþ÷àÿ õîðîøî èçó÷åííûå çàäà÷è íàõîæäå-
íèÿ ìàêñèìàëüíîé êëèêè è ìàêñèìàëüíîãî ðàçðåçà [3]. Êðîìå òîãî, çàäà÷à UBQP
ÿâëÿåòñÿ îáùåé ìîäåëüþ äëÿ øèðîêîãî êðóãà äèñêðåòíûõ çàäà÷ îïòèìèçàöèè [4].
 ðàáîòå [5] äàíû ïðèìåðû åå èñïîëüçîâàíèÿ ïðè ðàññìîòðåíèè çàäà÷ ðàñêðàñêè
âåðøèí ãðàôà, óïàêîâêè, ðàçáèåíèÿ, ëèíåéíîãî óïîðÿäî÷èâàíèÿ è ò.ï.
Çàäà÷à UBQP ïðèíàäëåæèò ê êëàññó NP-òðóäíûõ çàäà÷ äèñêðåòíîé îïòèìè-
çàöèè. Ñóùåñòâóåò îãðàíè÷åííîå êîëè÷åñòâî åå ïîäêëàññîâ, î êîòîðûõ èçâåñòíî,
÷òî îíè ïîëèíîìèíàëüíî ðàçðåøèìû (íàïðèìåð, [6]). Òàêæå èçâåñòíî, ÷òî çàäà÷à
«èìååò ëè çàäà÷à UBQP åäèíñòâåííîå ðåøåíèå?» — NP-òðóäíàÿ [7]. Êðîìå òîãî,
çàäà÷à áóëåâà êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ îñòàåòñÿ NP-òðóäíîé, äàæå åñëè
èçâåñòíî, ÷òî ãëîáàëüíûé îïòèìóì åäèíñòâåííûé [7].
Ïîñêîëüêó çàäà÷à (1) — NP-òðóäíàÿ, òî÷íûå àëãîðèòìû (íàïðèìåð, [8, 9])
ìîãóò áûòü ïðèìåíèìû äëÿ íåå òîëüêî ïðè ðàçìåðíîñòè íåñêîëüêî ñîòåí ïåðå-
ìåííûõ è óìåðåííî ðàçðåæåííîé ìàòðèöå Q. Äëÿ çàäà÷ áîëüøèõ ðàçìåðíîñòåé
ñ ïëîòíûìè ìàòðèöàìè ïðèãîäíû òîëüêî ïðèáëèæåííûå ìåòîäû, ïîçâîëÿþùèå
íàõîäèòü ïî÷òè îïòèìàëüíûå ðåøåíèÿ çà ïðèåìëåìîå âðåìÿ. Ñðåäè íèõ ñëåäóåò
îòìåòèòü àëãîðèòìû, îñíîâàííûå íà ìåòîäàõ òàáó [4, 10–12], îòæèãà [11, 13, 14].
Êðîìå òîãî, õîðîøî çàðåêîìåíäîâàëè ñåáÿ òàêèå àëãîðèòìû, èñïîëüçóþùèå ïî-
ïóëÿöèè: ýâîëþöèîííûå [15–18], ìåìåòè÷åñêèå [19], ðàññåèâàíèÿ (scatter) [20].
Äëÿ çàäà÷è UBQP â ðàáîòå [21] ïðåäëîæåí àëãîðèòì ãëîáàëüíîãî ðàâíîâåñíî-
ãî ïîèñêà (ÃÐÏ), ïðîâåäåíî åãî ñðàâíåíèå ñ ëó÷øèì íà òîò ìîìåíò àëãîðèòìîì
MST2 [12]. Õîòÿ ýòî ñðàâíåíèå è ïîêàçàëî ïðåèìóùåñòâî àëãîðèòìà ÃÐÏ (GES),
íî ââèäó ïðîãðàììíîé îøèáêè îíî áûëî ïðîâåäåíî íå íà îáùåïðèíÿòûõ òåñòàõ
(â íèõ áûëè îøèáî÷íî îáíóëåíû äèàãîíàëüíûå ýëåìåíòû ìàòðèöû). Çà âðåìÿ, ïðî-
øåäøåå ñ ìîìåíòà îïóáëèêîâàíèÿ ñòàòüè [21], ïîÿâèëèñü íîâûå èíòåðåñíûå àëãîðèò-
ìû (íàïðèìåð [4]), èçìåíèëñÿ íàø ïîäõîä ê ïîñòðîåíèþ è ñðàâíåíèþ àëãîðèòìîâ.
 íàñòîÿùåé ñòàòüå íà áàçå ìåòîäà ÃÐÏ ðàçðàáîòàí íîâûé àëãîðèòì ðåøå-
íèÿ çàäà÷è UBQP, ïðîâåäåíî åãî èññëåäîâàíèå è ñðàâíåíèå ñ èçâåñòíûìè àëãî-
ðèòìàìè ñ èñïîëüçîâàíèåì îáùåïðèíÿòûõ òåñòîâ (ïðè óâåëè÷åíèè èõ
ðàçìåðíîñòè äî n �10000).
ÀËÃÎÐÈÒÌ ÃÐÏ
Öåëåâàÿ ôóíêöèÿ çàäà÷è (1) äëÿ ðàçëè÷íûõ òåñòîâ ïîðîæäàåò ñõîäíûé ëàíä-
øàôò. Îí õàðàêòåðèçóåòñÿ íàëè÷èåì îòäåëüíûõ ïèêîâ ïðèáëèçèòåëüíî îäíîé
âûñîòû, ïðè÷åì ðàññòîÿíèå ìåæäó íèìè äîâîëüíî çíà÷èòåëüíîå. Åñëè íàçû-
âàòü îáëàñòü ïðèòÿæåíèÿ ýòèõ ïèêîâ ãîðíîé ñèñòåìîé, òî âñå îíè ïðèíàäëå-
æàò ðàçíûì ãîðíûì ñèñòåìàì, ÷òî èñêëþ÷àåò âîçìîæíîñòü ïåðåõîäà èç îäíîãî
ïèêà â äðóãîé ñðåäñòâàìè ëîêàëüíîãî ïîèñêà. Ýòî ñâèäåòåëüñòâóåò î ÷ðåçâû÷àé-
íîé ñëîæíîñòè çàäà÷ UBQP, îñîáåííî åñëè â êà÷åñòâå êðèòåðèÿ îöåíêè êà÷å-
ñòâà îïòèìèçàöèè âûáðàòü îáÿçàòåëüíîå íàõîæäåíèå íàèëó÷øåãî èçâåñòíîãî
ðåøåíèÿ (æåëàòåëüíî çà âîçìîæíî ìåíüøåå âðåìÿ). Ïîýòîìó äëÿ ñîçäàíèÿ õîðî-
øåãî àëãîðèòìà ðåøåíèÿ ýòèõ çàäà÷ ñëåäóåò ó÷èòûâàòü èõ îñîáåííîñòè. Ðàññìîò-
ðèì ìîäèôèêàöèþ îñíîâíîé ñõåìû ìåòîäà ÃÐÏ [22, 23] äëÿ çàäà÷è (1).
Îáùàÿ ñõåìà ìåòîäà ÃÐÏ âêëþ÷àåò äâà ýòàïà: ãåíåðàöèþ ðåøåíèÿ è ïîèñê
ëîêàëüíîãî ìàêñèìóìà â îêðåñòíîñòè ýòîãî ðåøåíèÿ.
Ïðåäïîëîæèì, ÷òî ìíîæåñòâî S ÿâëÿåòñÿ ïîäìíîæåñòâîì ìíîæåñòâà äîïó-
ñòèìûõ ðåøåíèé çàäà÷è (1), íàéäåííûõ ìåòîäîì ÃÐÏ, è
S x S xj j
1 1� � �{ }| , S x S xj j
0 0� � �{ }| , j n�1, , .�
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 69
Îñíîâíûì â ñòðóêòóðå ìåòîäà ÃÐÏ ÿâëÿåòñÿ «òåìïåðàòóðíûé» öèêë. Â íåì
ïðîâîäèòñÿ ñåðèÿ ñòàðòîâ ïîèñêà íàèëó÷øåãî ðåøåíèÿ äëÿ âîçðàñòàþùèõ çíà÷å-
íèé òåìïåðàòóðû. Äàííûé öèêë è åãî ïîâòîðåíèÿ ïîçâîëÿþò ãèáêî ÷åðåäîâàòü
ðåæèìû äèâåðñèôèêàöèè è èíòåíñèôèêàöèè îáëàñòè ïîèñêà ðåøåíèÿ, ÷òî â èòî-
ãå ïðèâîäèò ê âûñîêîé ýôôåêòèâíîñòè ìåòîäà ÃÐÏ. Äëÿ òåìïåðàòóðíîãî öèêëà
íåîáõîäèìî çàäàòü K — ÷èñëî åãî âûïîëíåíèé è � � �0 1� ��� K — çíà÷åíèÿ
òåìïåðàòóðû ñ èíäåêñàìè, êîòîðûå ñîîòâåòñòâóþò íîìåðàì òåìïåðàòóðíîãî öèê-
ëà. Äëÿ k K j n� � � �0 1, , , , , , u �{ }01, äîïîëíèòåëüíî îïðåäåëèì òàêèå
âåëè÷èíû:
E
S
f x f x f x
kj
u
j
u
x S
k
j
u�
� �
�
�
0, ,
( )exp ( ( ) ( ))
ex
åñëè
{ }� max
p ( ( ) ( ))
, .
{ }
åñëè
�k max
x S
j
u
f x f x
S
j
u
�
�
�
�
�
�
(2)
 ìåòîäå ÃÐÏ ìíîæåñòâî S èñïîëüçóåòñÿ ïðè ñëó÷àéíîé ãåíåðàöèè íà÷àëü-
íûõ ðåøåíèé äëÿ ïðèìåíÿåìîãî ïîèñêîâîãî ìåòîäà. Âåêòîð òåìïåðàòóðíûõ ïà-
ðàìåòðîâ � � �� � �( )0 � K , � � �0 1� � �� K , ïîçâîëÿåò óïðàâëÿòü áëèçîñòüþ
ðàññòîÿíèÿ ãåíåðèðóåìûõ íà÷àëüíûõ ðåøåíèé ê ëó÷øåìó ðåøåíèþ xmax â ìíî-
æåñòâå S . Ýòî ïðîèñõîäèò âñëåäñòâèå òîãî, ÷òî ãåíåðèðóåìîå íà÷àëüíîå ðåøåíèå
ïîëó÷àåòñÿ ñëó÷àéíûì èçìåíåíèåì êîìïîíåíò âåêòîðà xmax ïî ñëåäóþùåìó ïðà-
âèëó: åñëè j-ÿ êîìïîíåíòà âåêòîðà xmax ðàâíà íóëþ, îíà èçìåíÿåòñÿ ñ âåðîÿòíî-
ñòüþ p j k( )� , â ïðîòèâíîì ñëó÷àå — ñ âåðîÿòíîñòüþ 1 p j k( )� . Âåðîÿòíîñòè
ïðåäëàãàåìîé âåðñèè àëãîðèòìà ðàññ÷èòûâàëèñü ïî ôîðìóëàì
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
)
,
j n k K� � � �1 1, , , , , . (3)
Èç (2) ñëåäóåò, ÷òî âåëè÷èíû E
kj
u ðàâíû âçâåøåííîé ñóììå çíà÷åíèé
öåëåâîé ôóíêöèè ïî ìíîæåñòâó èçâåñòíûõ ðåøåíèé, j-å êîìïîíåíòû êîòîðûõ
ðàâíû u . Âåñ êàæäîãî ðåøåíèÿ çàâèñèò îò çíà÷åíèÿ åãî öåëåâîé ôóíêöèè è âåëè-
÷èíû òåìïåðàòóðíîãî ïàðàìåòðà �k . Íàéäåííîå íîâîå ðåøåíèå íå çàïîìèíàåòñÿ,
à èñïîëüçóåòñÿ äëÿ ïåðåñ÷åòà âåëè÷èí E
kj
u .
Ïóñòü g f x x S j nj
u
j
u� � � �max ( ) | , , ,{ }, 1 u �{ }01, . Èç (2), (3) ñëåäóåò, ÷òî
lim ( )
�
�
k
p j k
��
�1 ïðè g j
0 � g j
1 , â ïðîòèâíîì ñëó÷àå lim ( )
�
�
k
p j k
��
� 0. Ñîîòíî-
øåíèÿ (2), (3) ïîëó÷åíû èç àïïðîêñèìàöèè ðàñïðåäåëåíèÿ Áîëüöìàíà [21–23].
Êîìïîíåíòû �k òåìïåðàòóðíîãî âåêòîðà � âû÷èñëÿþòñÿ ïî ôîðìóëàì �0 0� ,
� ��k k� �1 , k K� � 1 1, , .
Ðàññìîòðèì ñõåìó àëãîðèòìà ÃÐÏ ðåøåíèÿ çàäà÷è UBQP.
Âõîäíûå äàííûå: � — âåêòîð òåìïåðàòóðíûõ ïàðàìåòðîâ, K — ÷èñëî âû-
ïîëíåíèé òåìïåðàòóðíîãî öèêëà, maxnfail — ïàðàìåòð ðåñòàðòà, ngen — êîëè÷å-
ñòâî ðåøåíèé, ãåíåðèðóåìûõ â êàæäîì öèêëå.
70 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Procedure GES:
1. EliteSet = �
2. while (stopping criterion = FALSE) do
3. x � construct random solution
4. x x x xmax best� �;
5. S x� { }max ; nfail � 0; nrep = 0
6. while (nfail maxnfail� AND f x f xbest max( ) ( )� ) do
7. x xold max� ; nrep nrep� � 1
8. for k � 0 to K 1 do
9. calculate generation probabilities ( ( ), , )p Sk k� �
10. for g � 0 to ngen do
11. x � generate initial solution ( , ( ), )x p EliteSetmax
k�
12. R x gains x EliteSet� Tabu search method ( , ( ), )
13. S S R� �
14. x f x x Smax � �arg max{ }( ) |
15. if f x f xmax best( ) ( )� then x xbest max�
16. end for
17. end for
18. S x� { }max
19. if f x f xmax old( ) ( )� then nfail nfail� � 1
20. else nfail � 0
21. end while
22. EliteSet EliteSet xmax� �
23. end while
24. return xbest
Îñíîâíîé öèêë ñõåìû (ñòðîêè 2–23) ïîâòîðÿåòñÿ äî âûïîëíåíèÿ íåêîòîðîãî
êðèòåðèÿ îñòàíîâà. Ïðè ïðîâåäåíèè ýêñïåðèìåíòîâ àëãîðèòì ïðåêðàùàë ðàáîòó,
êîãäà äëèòåëüíîñòü åãî ðàáîòû ïðåâûøàëà íåêîòîðîå ïðåäåëüíîå çíà÷åíèå. Êàê
îòìå÷àëîñü âûøå, îñíîâíîé ýëåìåíò â ñòðóêòóðå ìåòîäà ÃÐÏ — òåìïåðàòóðíûé
öèêë (ñòðîêè 8–17). ×èñëî K åãî âûïîëíåíèé è âåêòîð òåìïåðàòóðíûõ ïàðàìåò-
ðîâ � � �� �( , , )0 K îïðåäåëåíû çàðàíåå. Âûáîð � � 0 è �1 äîëæåí áûòü ñäåëàí
òàêèì îáðàçîì, ÷òîáû âåêòîð âåðîÿòíîñòè p K( )� áûë áëèçîê ê ëó÷øåìó
ðåøåíèþ èç ìíîæåñòâà S .
Âåðîÿòíîñòè, ñ êîòîðûìè ãåíåðèðóþòñÿ íîâûå ðåøåíèÿ, âû÷èñëÿþòñÿ ñ èñ-
ïîëüçîâàíèåì (2), (3) â íà÷àëå êàæäîãî òåìïåðàòóðíîãî öèêëà (ñòðîêà 9). Äëÿ
êàæäîãî âåêòîðà âåðîÿòíîñòè ãåíåðèðóåòñÿ ngen ðåøåíèé (ñòðîêà 11). Îíè èñ-
ïîëüçóþòñÿ â êà÷åñòâå íà÷àëüíûõ ðåøåíèé äëÿ ïðîöåäóðû Tabu search method
(ñòðîêà 12). Ìíîæåñòâî R ðåøåíèé, íàéäåííûõ ñ ïîìîùüþ ýòîé ïðîöåäóðû, èñ-
ïîëüçóåòñÿ äëÿ ïîïîëíåíèÿ ìíîæåñòâà S (ñòðîêà 13). Êàê ñêàçàíî âûøå, ìíîæå-
ñòâî S èñïîëüçóåòñÿ â ïñåâäîêîäå äëÿ óïðîùåíèÿ îïèñàíèÿ àëãîðèòìà. Ïðè
ðåàëèçàöèè àëãîðèòìà îíî íå çàïîìèíàåòñÿ, õðàíÿòñÿ òîëüêî çíà÷åíèÿ E
kj
u .
Åäèíñòâåííûå ðåøåíèÿ, êîòîðûå çàïîìèíàþòñÿ àëãîðèòìîì, — òàê íàçûâàå-
ìûå ýëèòíûå ðåøåíèÿ, ñîñòàâëÿþùèå ìíîæåñòâî EliteSet (ñòðîêà 22). Ïðåäïîëà-
ãàåòñÿ, ÷òî âñëåäñòâèå öèêëà èíòåíñèôèêàöèè ïîèñêà (ñòðîêè 6–21) èõ îêðåñò-
íîñòè õîðîøî èññëåäîâàíû è â íèõ íåò óëó÷øàþùèõ ðåøåíèé. Òàêèì îáðàçîì,
äàëüíåéøèé ïîèñê ïðîâîäèòñÿ òîëüêî ñðåäè ðåøåíèé, äëÿ êîòîðûõ ðàññòîÿíèå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 71
Õåììèíãà îò ìíîæåñòâà EliteSet ñîñòàâëÿåò íå ìåíåå d p . Ïîýòîìó àëãîðèòì íå
âåäåò ïîèñê â óæå èññëåäîâàííûõ îáëàñòÿõ.
 àëãîðèòìå òàáó, ïðèìåíÿåìîì ïðè ðåàëèçàöèè âòîðîãî ýòàïà àëãîðèòìà
ÃÐÏ, èñïîëüçóåòñÿ îêðåñòíîñòü ðàäèóñà 1. Ðåøåíèå y ïðèíàäëåæèò îêðåñòíîñòè
N x1 ( ) ðàäèóñà 1 ñ öåíòðîì â òî÷êå x, åñëè ðàññòîÿíèå d x y( , ) Õåììèíãà ðàâíî
åäèíèöå. Äðóãèìè ñëîâàìè, åñëè y N x� 1 ( ), òî y xj j� 1 äëÿ íåêîòîðîãî èíäåêñà j
è y xk k� äëÿ k j
. Áóäåì ñ÷èòàòü, ÷òî òàêîå ðåøåíèå y íàéäåíî ñ èñïîëüçîâàíè-
åì õîäà m y m xj j: ( )� . Ïóñòü gains x( ) — âåêòîð, â êîòîðîì j-ÿ êîìïîíåíòà ïðåä-
ñòàâëÿåò óâåëè÷åíèå öåëåâîé ôóíêöèè, ïîëó÷åííîé ñ ïîìîùüþ õîäà m j . Îí ìî-
æåò áûòü âû÷èñëåí çà ëèíåéíîå âðåìÿ
gains x q x x q x x xj jj j j ij i j j
i i j
n
( ) ( ) ( )
,
� �
�
�2
1
, ãäå x xj j� 1 .
Ðàññìîòðèì òåïåðü ñõåìó àëãîðèòìà òàáó, êîòîðûé èñïîëüçóåòñÿ â àëãîðèò-
ìå ÃÐÏ.
Âõîäíûå äàííûå: x — íà÷àëüíîå ðåøåíèå, g x( ) — âåêòîð gains nbad, — êî-
ëè÷åñòâî èòåðàöèé áåç óëó÷øåíèÿ ðåøåíèÿ, tenure — ïàðàìåòð, x max — ëó÷øåå
ðåøåíèå â ìíîæåñòâå S , x best — ðåêîðä, íàéäåííûé àëãîðèòìîì, nrep — ÷èñëî
ïîâòîðîâ öèêëà èíòåíñèôèêàöèè ïîèñêà (ñòðîêè 6—21) â Procedure GES.
Procedure Tabu search method:
1. x x nfail stepgood � � �; ; ;0 0 R nbad n improve� � � �; / ;2 1
2. if nrep � 0 then mxnfail � 9
3. else mxnfail � 3
4. repeat
5. step step cimpr � �; 0
6. M n last used j tabu j tenure RANDO� � � � �{ }12, ,... , ; _ ( ) ; ( ) M j n( ); , ,10 1� �
7. repeat
8. Generate a random permutation RP of M
9. � � �
10. for k � 1 to n do
11. j RP k� [ ]
12. if ( _ ( ) ( ) ( ( ) ( ) ( )))step las used j tabu j OR f x g x f xj
max � � � then
13. if ( ( ) ) ( ( ( ), ) )g x AND dist move x EliteSet dj j p� �� then
14. � � �g x ind jj ( );
13. end if
14. end if
15. end for
16. if (� � 0 AND c � 0) then
17. x x cgood � �; 0
18. if f x f x( ) (� max) then
19. nbad n R R x nfail� � � �5 0; ;
20. if f x f xbest( ) ( )� then
21. mxnfail � 9
22. end if
23. improve = 1; break;
24. end if
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
25. end if
26. last used ind step( ) ;� x xind ind� 1 ; tabu ind tenure RANDOM( ) ( )� � 10
27. g x gains x c c( ) ( );� � �recalculate �; step step� � 1
28. until step step nbadimpr �
29. if step step nbadimpr � then
30. x x g x gains xgood� �; ( ) ( )recalculate
31. nfail nfail� � 1
32. end if
33. end while
34. until ( ) ( )improve nfail mxnfail� �0 OR
35. return x Rgood ,
Ðàññìîòðèì ïðîöåäóðó ãåíåðàöèè ðåøåíèé ñîãëàñíî âåðîÿòíîñòè, îïðåäå-
ëåííîé ôîðìóëîé (3).
Âõîäíûå äàííûå: x — ðåøåíèå, ê êîòîðîìó ïðèìåíÿåòñÿ ñëó÷àéíîå âîçìó-
ùåíèå, p k( )� — âåêòîð âåðîÿòíîñòè, ðàññ÷èòàííûé ïî ôîðìóëàì (2), (3).
Function:
1. dist j� �0 1;
2. while ( )j n� do
3. if x j � 1 then
4. if p randomk( ) [ , ]� � 0 1 then
5. x dist distj � � �0 1;
6. end if
7. else
8. if p randomk( ) [ , ]� � 0 1 then
9. x dist distj � � �1 1;
10. end if
11. end if
12. j j� � 1
13. if dist distmax� then return x
14. end while
15. return x
Íà îñíîâàíèè âåêòîðà x ñ ïîìîùüþ ïðîöåäóðû ãåíåðàöèè âûïîëíÿþòñÿ îïå-
ðàòîðû èíâåðñèè (ñòðîêè 2–16). Ðàâíîìåðíî ðàñïðåäåëåííàÿ â (0,1) ïåðåìåííàÿ
random[ , ]01 îïðåäåëÿåò âîçìîæíîñòü ïðèìåíåíèÿ îïåðàòîðîâ èíâåðñèè ê íåé
(ñòðîêè 4,8). Ïðîöåäóðà çàêàí÷èâàåòñÿ, êîãäà ðàññòîÿíèå Õåììèíãà ìåæäó x è
âîçìóùåííûì ðåøåíèåì ðàâíî ïàðàìåòðó distmax .
ÑÐÀÂÍÈÒÅËÜÍÎÅ ÈÑÑËÅÄÎÂÀÍÈÅ ÀËÃÎÐÈÒÌÎÂ
Ðàññìîòðèì îïèñàíèå âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ ïî ðåøåíèþ àëãîðèò-
ìîì ÃÐÏ òåñòîâûõ çàäà÷ âèäà (1) áîëüøîé ðàçìåðíîñòè, ñðàâíåíèå ïîëó÷åí-
íûõ ðåçóëüòàòîâ ñ ðåçóëüòàòàìè ëó÷øèõ èçâåñòíûõ àëãîðèòìîâ.
1. Òåñòîâûå çàäà÷è. Ïðè ïðîâåäåíèè ýêñïåðèìåíòàëüíûõ ðàñ÷åòîâ áûëè
âûáðàíû 24 ñëó÷àéíî ñãåíåðèðîâàííûå çàäà÷è p3000.1,...,p10000.3 áîëüøîé ðàç-
ìåðíîñòè (3000 10000� �n ) ñ ïëîòíîñòüþ çàïîëíåíèÿ ìàòðèöû îò 0.5 äî 1 [12].
Îáû÷íûé íàáîð òåñòîâ áûë ðàñøèðåí çàäà÷àìè ðàçìåðíîñòè n �10000, ïîñêîëüêó
îïûò, ïðèîáðåòåííûé çà ãîäû, ïðîøåäøèå ñ ìîìåíòà îïóáëèêîâàíèÿ ñòàòüè [21],
ïîçâîëèë ïîäíÿòü ïëàíêó ýôôåêòèâíîñòè äëÿ àëãîðèòìîâ. Êîäû äëÿ ãåíåðèðîâà-
íèÿ ýòèõ çàäà÷ äîñòóïíû íà ñàéòå http: //www.soften.ktu.lt/~gintaras/ubqop_its.html.
Èìåííî ýòè çàäà÷è â íàñòîÿùåå âðåìÿ àêòèâíî èñïîëüçóþòñÿ äëÿ ïðîâåðêè ýô-
ôåêòèâíîñòè ðàçðàáîòàííûõ àëãîðèòìîâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 73
Çàìåòèì, ÷òî òåñòîâûå çàäà÷è èç áèáëèîòåêè ORLIB ïðè 50 2500� �n è ïî-
äîáíûå çàäà÷è èç ñàéòà http://people.brunel.ac.uk/~mastjjb/jeb/orlib/bqpinfo.html
çäåñü íå ðàññìàòðèâàþòñÿ, òàê êàê ñ ïîìîùüþ àëãîðèòìà ÃÐÏ îíè ðåøàþòñÿ äî-
ñòàòî÷íî áûñòðî, íå èñïîëüçóÿ ïðè ýòîì âñå åãî âîçìîæíîñòè.
2. Ïëàí âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ. Àëãîðèòì ÃÐÏ ðåàëèçîâàí íà
ÿçûêå Ñ++, âñå âû÷èñëèòåëüíûå ýêñïåðèìåíòû ïðîâîäèëèñü ñ èñïîëüçîâàíèåì PC
Intel® Core QUAD CPU Q9550 2.83GHz è 3.0GB îïåðàòèâíîé ïàìÿòè. Çíà÷åíèÿ
îñíîâíûõ ïàðàìåòðîâ àëãîðèòìà ÃÐÏ ïðèâåäåíû â òàáë. 1.
Íà÷àëüíûå âåðîÿòíîñòè p j nj ( ) , , ..., ,� �0 0
1
2
1 0� � � . Äëÿ òåìïåðàòóðíîãî ðàñïè-
ñàíèÿ èñïîëüçîâàíû ñëåäóþùèå çíà÷åíèÿ: �1 � 10 7 , � �
�
k k
coef
�
1
10003
4
log log. /
ïðè k K� �2, , , coef f x BKS�1 8 108. * / ( ), ãäå f x BKS( ) — èçâåñòíûé äëÿ äàííîé
çàäà÷è ðåêîðä.
Ñëåäóåò îòìåòèòü, ÷òî ïðèâåäåííûå íèæå ðåçóëüòàòû âû÷èñëèòåëüíûõ ýêñ-
ïåðèìåíòîâ ïîëó÷åíû áåç ñïåöèàëüíîé íàñòðîéêè ïàðàìåòðîâ, ò.å. âñå èñïîëüçó-
åìûå ïàðàìåòðû ïîñòîÿííû äëÿ âñåõ òåñòîâûõ çàäà÷. Çíà÷åíèÿ ïàðàìåòðîâ tenure
è nbad àëãîðèòìà òàáó èç [4] ïîäòâåðæäàþò, ÷òî èìåííî ñõåìà ìåòîäà ÃÐÏ, à íå
ïðèìåíÿåìûå ìåòîäû ïîèñêà äåëàåò àëãîðèòì ÃÐÏ ñòîëü ýôôåêòèâíûì.
Äëÿ ñðàâíèòåëüíîãî ýêñïåðèìåíòàëüíîãî èññëåäîâàíèÿ ñ àëãîðèòìîì ÃÐÏ
âûáðàí àëãîðèòì MST2 [12], ïîñêîëüêó ïðåæäå âñåãî ðåàëèçàöèÿ MST2 àëãîðèò-
ìà òàáó íà äàííîå âðåìÿ ÿâëÿåòñÿ îäíîé èç ëó÷øèõ äëÿ ðåøåíèÿ çàäà÷è UBQP.
Îíà ïîêàçûâàåò õîðîøóþ è óñòîé÷èâóþ ðàáîòó àëãîðèòìà íà ðàçíûõ ìíîæåñòâàõ
ýòàëîííûõ òåñòîâ. Ýòî ñëåäóåò èç ñðàâíèòåëüíîãî èññëåäîâàíèÿ [12], ãäå ïðåä-
ñòàâëåíû ðåçóëüòàòû ñ èñïîëüçîâàíèåì äðóãèõ èçâåñòíûõ ïîäõîäîâ, âêëþ÷àÿ ìå-
òîäû òàáó, îòæèãà, ãåíåòè÷åñêèé ëîêàëüíûé ïîèñê. Êðîìå òîãî, èñõîäíûé òåêñò
àëãîðèòìà äîñòóïåí â ñåòè http://www.soften.ktu.lt/~gintaras/ubqop_its.html. Ýòî
ïîçâîëèëî ïðîâîäèòü âû÷èñëèòåëüíûå ýêñïåðèìåíòû, â êîòîðûõ äëÿ çàïóñêà àëãî-
ðèòìîâ èñïîëüçîâàëñÿ îäèí è òîò æå ïåðñîíàëüíûé êîìïüþòåð. Ñëåäîâàòåëüíî,
ïðåäñòàâëåííîå íèæå âðåìÿ ðåøåíèÿ çàäà÷ ìîæåò ñëóæèòü îäíèì èç ïàðàìåòðîâ
äëÿ ñðàâíåíèÿ àëãîðèòìîâ.
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Ïàðàìåòð
Ìåñòî íàõîæäåíèÿ
ïàðàìåòða
Ñìûñëîâîå çíà÷åíèå Âåëè÷èíà ïàðàìåòða
K Procedure GES (ñòðîêà 8)
×èñëî âûïîëíåíèé
òåìïåðàòóðíîãî öèêëà
6
ngen Procedure GES (ñòðîêà 10)
Êîëè÷åñòâî ãåíåðèðóåìûõ
íà÷àëüíûõ ðåøåíèé
45 0
80 0
,
,
nrep
nrep
�
�
�
�
�
maxnfail Procedure GES (ñòðîêà 6)
Ïåðåìåííàÿ öèêëà
èíòåíñèôèêàöèè ïîèñêà
(ñòðîêè 6–21)
1
tenure
Procedure Tabu search
method (ñòðîêè 6, 26)
Íà÷àëüíîå çíà÷åíèå
ïåðåìåííîé çàïðåòà
â àëãîðèòìå òàáó
n/150
d p
Procedure Tabu search
method (ñòðîêà 13),
Procedure generate initial
solution (ñòðîêè 4, 8)
Ìèíèìàëüíîå ðàçðåøåííîå
ðàññòîÿíèå äî ìíîæåñòâà
ýëèòíûx ðåøåíèé EliteSet
200
distmax
Procedure generate initial
solution (ñòðîêà 12)
Ìàêñèìàëüíîå êîëè÷åñòâî
ñëó÷àéíûõ âîçìóùåíèé
n nrep
d nrepp
,
,
�
�
�
�
�
0
0
Ò à á ë è ö à 1
Êàæäàÿ çàäà÷à èç ïðåäñòàâëåííîãî ìíîæåñòâà òåñòîâûõ çàäà÷ ðåøàëàñü îáî-
èìè àëãîðèòìàìè 20 ðàç ïðè ðàçëè÷íûõ íà÷àëüíûõ çíà÷åíèÿõ äàò÷èêà ñëó÷àé-
íûõ ÷èñåë. Àëãîðèòì MST2 âûïîëíÿë 1000 èòåðàöèé; çàòðà÷åííîå èì íà ðåøå-
íèå çàäà÷è âðåìÿ (ñì. òàáë. 2) ñëóæèëî êðèòåðèåì îñòàíîâà äëÿ àëãîðèòìà GES.
Òàêîé ïëàí ýêñïåðèìåíòîâ òàêæå ïîçâîëÿåò ïðîâåñòè ñðàâíåíèå ñ ðàçðàáîòàí-
íûì â ïîñëåäíåå âðåìÿ ïåðñïåêòèâíûì àëãîðèòìîì ÍÌÀ [4].
3. Ðåçóëüòàòû ýêñïåðèìåíòàëüíûõ ðàñ÷åòîâ.  òàáë. 2 ïðåäñòàâëåíû ðå-
çóëüòàòû âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ ïî ðåøåíèþ òåñòîâûõ çàäà÷ âèäà (1)
àëãîðèòìàìè MST2 è ÃÐÏ.
Ïóñòü x imax ( ) è t imax ( ) (ñåê) ñîîòâåòñòâåííî ëó÷øåå ðåøåíèå, íàéäåííîå àëãî-
ðèòìîì, è âðåìÿ åãî íàõîæäåíèÿ ïðè i-é, i � �1 20, , , ïîïûòêå ðåøåíèÿ. Â òàáë. 2, 3
èñïîëüçîâàíû ñëåäóþùèå îáîçíà÷åíèÿ: g f x f x iavr
BKS max
i
�
�
�( ) ( ( ))
1
20 1
20
;
t t iavr
max
i
�
�
�1
20 1
20
( ); t t ibest
i
max�
� �
min ( )|
1 20
{ f x i f xmax BKS( ( )) ( )� }; I imax � { | f x imax( ( )) �
� f x BKS( )}; success I max� | | — ÷èñëî íàéäåííûõ àëãîðèòìîì ðåøåíèé çàäà÷è ñî
çíà÷åíèåì öåëåâîé ôóíêöèè, íå ìåíüøèì ðåêîðäà f x BKS( ) ; tmax — ìàêñèìàëü-
íîå âðåìÿ, âûäåëåííîå íà ðåøåíèå çàäà÷è.
Èç òàáë. 2 âèäíî, ÷òî àëãîðèòì ÃÐÏ ïî âñåì ïîêàçàòåëÿì ïðåâîñõîäèò àëãî-
ðèòì MST2. Îòìåòèì òîëüêî ïîëíóþ «íåóäà÷ó» àëãîðèòìà MST2 íà òåñòîâûõ çà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 75
Ò à á ë è ö à 2
Çàäà÷à f xBKS( )
tmax ,
ñåê
success gavr tavr tbest
MST2 GES MST2 GES MST2 GES MST2 GES
p3000.1 3931583 580 20 20 0.0 0.0 19.5 7.60 4.17 2.83
p3000.2 5193073 890 20 20 0.0 0.0 21.4 6.98 7.69 0.36
p3000.3 5111533 890 20 20 0.0 0.0 130.7 9.70 7.69 0.44
p3000.4 5761822 1120 20 19 0.0 19.25 40.4 9.12 12.92 0.47
p3000.5 5675625 1120 18 20 2.7 0.0 416.6 75.75 18.53 7.03
p4000.1 6181830 930 20 20 0.0 0.0 19.8 9.59 7.83 1.11
p4000.2 7801355 1400 20 20 0.0 0.0 262.1 86.40 16.44 6.55
p4000.3 7741685 1400 20 20 0.0 0.0 95.7 36.12 19.23 1.39
p4000.4 8711822 1720 20 20 0.0 0.0 119.5 16.67 24.13 0.97
p4000.5 8908979 1720 20 20 0.0 0.0 430.1 72.90 48.25 17.11
p5000.1 8559680 1320 0 6 396.9 234.75 408.37 391.70 – 325.27
p5000.2 10836019 1960 1 19 552.9 29.1 234.5 519.53 1228.11 25.14
p5000.3 10489137 1960 17 20 37.8 0.0 916.0 413.16 42.7 21.49
p5000.4 12252318 2360 1 8 700.3 291 1099.1 927.61 1778.45 219.45
p5000.5 12731803 2360 13 20 307.1 0.0 885.5 227.62 46.75 11.19
p6000.1 11384976 1740 20 19 0.0 12.15 232.8 125.21 68.23 28.11
p6000.2 14333855 2550 8 17 58.8 15.2 717.8 915.80 74.25 38.13
p6000.3 16132915 3060 10 20 1024.6 0.0 1566.9 738.75 253.48 17.08
p7000.1 14478676 2210 2 16 1447.6 123.5 1150.7 1196.4 1094.31 184.83
p7000.2 18249948 3170 0 6 1399.8 251.25 1481.40 1617.6 – 616.95
p7000.3 20446407 3170 20 20 0.0 0.0 296.8 215.37 109.26 50.33
p10000.1 24197906 3740 0 9 4023.9 1427.2 1719.08 2219.1 – 487.88
p10000.2 30627637 5260 0 3 4635.7 1068.85 2030.64 2584.0 – 2105.00
p10000.3 34690255 6330 0 1 3100,7 2326,85 3016.58 3253.25 – 5400,78
Ñðåäíåå
çíà÷åíèå
12.1 16.0 681.9 189.3 721.3 652.8 1033.1 399.00
äà÷àõ ïðè n �10000, ïîñêîëüêó îí íå ñìîã äàæå ïðèáëèçèòüñÿ ê ðåçóëüòàòàì àë-
ãîðèòìà ÃÐÏ. Äàëåå äëÿ ñðàâíåíèÿ áûë ïîäêëþ÷åí íåäàâíî ðàçðàáîòàííûé àëãî-
ðèòì HMA. Êàê îòìå÷åíî â ðàáîòå [4], ãëàâíîå äîñòîèíñòâî ýòîãî àëãîðèòìà
ñîñòîèò â íàõîæäåíèè ëó÷øåãî ðåøåíèÿ äëÿ êàæäîé òåñòîâîé çàäà÷è. Îïðåäåëèì
âàæíîñòü ýòîãî ïîêàçàòåëÿ. Â íåäàëåêîì ïðîøëîì ïðè ðàçðàáîòêå è èññëåäîâà-
íèè ïîñëåäîâàòåëüíûõ àëãîðèòìîâ îïòèìèçàöèè ãëàâíûìè èõ õàðàêòåðèñòèêàìè
áûëè âåëè÷èíû gavr è tavr . Öåëåñîîáðàçíî áûëî èìåòü àëãîðèòì, îáëàäàþùèé
ìèíèìàëüíûìè çíà÷åíèÿìè ýòèõ ïàðàìåòðîâ, ÷òî, â ñâîþ î÷åðåäü, òðåáîâàëî îò
íåãî íåêîòîðîé óñòîé÷èâîñòè — ðåãóëÿðíî íàõîäèòü çà íåáîëüøîå âðåìÿ ðåøå-
íèÿ, áëèçêèå ïî çíà÷åíèþ öåëåâîé ôóíêöèè ê ðåêîðäàì. Èíûìè ñëîâàìè, îò õî-
ðîøåãî àëãîðèòìà íå òðåáîâàëîñü íàõîäèòü ðåøåíèå x BKS èëè èìåòü ÷ðåçâû÷àé-
íî ìàëîå âðåìÿ t imax ( ).  êà÷åñòâå ïðèìåðà ðàññìîòðèì ðåçóëüòàòû ðåøåíèÿ çà-
äà÷è p5000.1. Íåñìîòðÿ íà òî, ÷òî àëãîðèòì MST2 íå íàøåë èçâåñòíîãî ðåêîðäà,
äëÿ íåãî gavr � 396 9. , à äëÿ àëãîðèòìà HMA èìååì gavr � 5068. .
Ñ íàøåé òî÷êè çðåíèÿ, âîçìîæåí äðóãîé ïîäõîä ê ñðàâíåíèþ àëãîðèòìîâ,
êîòîðûé ñòàíîâèòñÿ âñå áîëåå âàæíûì â ñâåòå ðàçâèòèÿ ìíîãîïðîöåññîðíûõ êîì-
ïëåêñîâ. Ïðîÿñíèì èäåþ òàêîãî ïîäõîäà íà ñëåäóþùåì ïðèìåðå. Ïóñòü èìååòñÿ
P ïðîöåññîðîâ è ñëåäóåò ðåøàòü òåñòîâûå çàäà÷è íåêîòîðûì àëãîðèòìîì, ðàçìå-
ùàÿ åãî êîïèè [23] íà êàæäîì ïðîöåññîðå. Áóäåì ñ÷èòàòü çàäà÷ó ðåøåííîé, åñëè
íàéäåíî åå ðåøåíèå ñî çíà÷åíèåì öåëåâîé ôóíêöèåé, íå ìåíüøèì f x BKS( ). Åñëè
çàäà÷à ðåøåíà íà îäíîì èç ïðîöåññîðîâ, òî ðåøåíèå çàêàí÷èâàåòñÿ íà âñåõ ïðî-
öåññîðàõ. Î÷åâèäíî, ÷òî ðåçóëüòàòû òàêîãî ýêñïåðèìåíòà áóäóò âî ìíîãîì àíà-
ëîãè÷íû ðåçóëüòàòàì, ïîëó÷åííûì ïðè ðåøåíèè êàæäîãî òåñòà P ðàç íà îäíîì
76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
Çàäà÷à
success tbest
HMA MST2 GES HMA MST2 GES
p3000.1 20 20 20 3,63 5.88 3.99
p3000.2 20 20 20 5,52 10.84 0.51
p3000.3 17 20 20 8,58 10.84 0.62
p3000.4 20 20 19 7,78 18.22 0.66
p3000.5 15 18 20 22,60 26.13 9.91
p4000.1 20 20 20 4,99 11.04 1.57
p4000.2 17 20 20 34,40 23.18 9.24
p4000.3 19 20 20 35,40 27.11 1.96
p4000.4 18 20 20 53,10 34.02 1.37
p4000.5 12 20 20 89,70 68.03 24.13
p5000.1 4 0 6 153,20 > 1200 458.63
p5000.2 6 1 14 98,70 > 1200 35.45
p5000.3 14 17 17 364,50 60.21 30.30
p5000.4 3 1 5 789,60 > 1200 309.42
p5000.5 16 13 20 212,30 65.92 15.78
p6000.1 12 20 19 727,70 96.20 39.64
p6000.2 6 8 12 965,30 104.69 53.76
p6000.3 3 10 16 676,50 357.41 24.08
p7000.1 5 2 15 987,30 1542.98 260.61
p7000.2 2 0 5 1254,70 > 3000 869.90
p7000.3 7 20 20 1868,50 154.06 70.97
Ñðåäíåå
çíà÷åíèå
12.2 12.1 15.0 398.3 438.9 105.80
Ò à á ë è ö à 3
ïðîöåññîðå. Íàïðèìåð, âðåìåíåì ðåøåíèÿ òåñòîâîé çàäà÷è áóäåò ñîîòâåòñòâóþ-
ùåå tbest . Îòìåòèì, ÷òî ïðè òàêîì ïîäõîäå îò àëãîðèòìà òðåáóåòñÿ õîòÿ áû îäèí
ðàç ðåøèòü çàäà÷ó ïðè P ïîïûòêàõ, ïîýòîìó íàèáîëåå âàæíûìè ïîêàçàòåëÿìè
äëÿ àëãîðèòìà ñòàíîâÿòñÿ ïîêàçàòåëè success è tbest . Íåäîñòàòî÷íî ëèøü îäèí ðàç
ðåøèòü çàäà÷ó çà ïðèåìëåìîå âðåìÿ, èñïîëüçóÿ îñòàëüíûå ïîïûòêè äëÿ äèâåðñè-
ôèêàöèè/èíòåíñèôèêàöèè ïîèñêà, ïîñêîëüêó ýòî ìåíÿåò îòíîøåíèå
ê êîíñòðóèðîâàíèþ àëãîðèòìîâ.
Àâòîðàìè áûë ïðîòåñòèðîâàí ñâîé êîìïüþòåð è êîìïüþòåð Pentium 2.66GHz
CPU with 512M RAM, èñïîëüçóåìûé â
[4], òåñòîâîé ïðîãðàììîé èç ñàéòà
http://www.cs.qub.ac.uk/itc2007/benchmar
king/benchmark machine.zip. Óñòàíîâëå-
íî, ÷òî ñîîòíîøåíèå ñêîðîñòåé ýòèõ
êîìïüþòåðîâ ñîñòàâëÿåò 1,41. Âðåìÿ,
âûäàííîå ýòîé ïðîãðàììîé äëÿ íàøåãî
êîìïüþòåðà, ñîñòàâèëî 315 ñåê. Äàëåå
áûëè ïåðåñ÷èòàíû ðåçóëüòàòû òàáë. 2 è
ñâåäåíû â òàáë. 3 âìåñòå ñ ðåçóëüòàòà-
ìè èç ðàáîòû [4]. Èç òàáë. 3 ñëåäóåò, ÷òî àëãîðèòì ÃÐÏ ïðåâîñõîäèò àëãîðèòìû
HMA è MST2 êàê ïî ïîêàçàòåëþ success, òàê è ïî âðåìåíè tbest äëÿ áîëüøèíñòâà
òåñòîâûõ çàäà÷.
 òàáë. 4 ïðåäñòàâëåíû ñâîäíûå ðåçóëüòàòû ïî ðåøåíèþ òåñòîâûõ çàäà÷, ò.å.
ïðèâåäåíî âðåìÿ (â ñåêóíäàõ), çàòðà÷åííîå íà ðåøåíèå âñåõ òåñòîâûõ çàäà÷ îä-
íîé ðàçìåðíîñòè. Ïðåäïîëàãàëîñü, ÷òî çàäà÷è ðåøàëèñü êîïèÿìè ñîîòâåòñòâóþ-
ùèõ àëãîðèòìîâ íà 20 ïðîöåññîðàõ c õàðàêòåðèñòèêàìè Pentium 2.66GHz.
Àíàëèç ïðåäñòàâëåííûõ â òàáë. 3, 4 ýêñïåðèìåíòàëüíûõ ðàñ÷åòîâ ïîêàçàë, ÷òî
àëãîðèòì HMA â ðàìêàõ ïðåäëîæåííîãî ïîäõîäà ê ñðàâíåíèþ àëãîðèòìîâ õîòÿ è
íàøåë ðåêîðäû äëÿ âñåõ òåñòîâûõ çàäà÷, íî ïðîèãðàë ïî áûñòðîäåéñòâèþ íå òîëüêî
àëãîðèòìó ÃÐÏ, íî è àëãîðèòìó MST2 íà ñåðèÿõ òåñòîâ ïðè n � 4000 è n � 6000.
ÇÀÊËÞ×ÅÍÈÅ
Äëÿ ðåøåíèÿ çàäà÷è áóëåâà êâàäðàòè÷íîãî ïðîãðàììèðîâàíèÿ áåç îãðàíè÷åíèé
ðàçðàáîòàí íîâûé àëãîðèòì, áàçèðóþùèéñÿ íà èñïîëüçîâàíèè ñõåìû ìåòîäà
ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà. Ïðîâåäåííîå ñðàâíèòåëüíîå èññëåäîâàíèå
ýòîãî àëãîðèòìà ñ ëó÷øèìè íà äàííîå âðåìÿ àëãîðèòìàìè ðåøåíèÿ ýòîé çàäà-
÷è ïîêàçàëî ïðåèìóùåñòâà àëãîðèòìà ÃÐÏ êàê ïî áûñòðîäåéñòâèþ, òàê è ïî
âîçìîæíîñòè ïîëó÷åíèÿ ëó÷øèõ ðåøåíèé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A l i d a e e B . , K o c h e n b e r g e r G . , A h m a d i a n A . 0–1 quadratic programming approach
for the optimal solution of two scheduling problems // Intern. J. of Syst. Sci. — 1994. — 25. —
P. 401–408.
2. G a l l o G . , H a m m e r P . L . , S i m e o n e B . Quadratic knapsack problems // Math. Program.
— 1980. — 12. — P. 132–149.
3. P a r d a l o s P . M . , X u e J . The maximum clique problem // J. of Global Optimiz. — 1994. — 4.
— P. 301–328.
4. L ü Z . , G l o v e r F . , H a o J i n - K a o . A hybrid metaheuristic approach to solving the UBQP
problem // Eur. J. of Oper. Res. — 2010. — 207, N 3. — P. 1254–1262.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 77
Ò à á ë è ö à 4
Çàäà÷à HMA MST2 ÃÐÏ
p3000 48.11 71.91 15.69
p4000 217.59 163.39 38.25
p5000 1618.30 – 849.58
p6000 2369.50 558.30 117.48
p7000 4110.50 – 1201.48
p10000 – – 11194.77
5. A u n i f i e d modeling and solution framework for combinatorial optimization problems /
G.A. Kochenberger, F. Glover, B. Alidaee, C. Rego // Oper. Res. Spectrum. — 2004. — 26. —
P. 237–250.
6. A p o l y n o m i a l case of unconstrained zero-one quadratic optimization / K. Allemand, K. Fukuda,
T.M. Liebling and E. Steiner // Math. Program. Ser. A. — 2001. — 91. — P. 49–52.
7. P a r d a l o s P . M . , J h a S . Complexity of uniqueness and local search in quadratic 0–1
programming // Oper. Res. Letters. — 1992. — 11. — P. 119–123.
8. H e l m b e r g C . , R e n d l F . Solving quadratic (0, 1) — problems by semidefinite programs and
cutting planes // Math. Program. — 1998. — 82. — P. 291–315.
9. P a l u b e c k i s G . A . Heuristic-based branch and bound algorithm for unconstrained quadratic
zero-one programming // Computing. — 1995. — 54. — P. 283–301.
10. B e a s l e y J . E . Heuristic algorithms for the unconstrained binary quadratic programming problem.
Working paper. The Management School. — London: Imperial College, 1998.
11. G l o v e r F . , K o c h e n b e r g e r G . A . , A l i d a e e B . Adaptive memory tabu search for binary
quadratic programs // Manag. Sci. — 1998. — 44. — P. 336–345.
12. P a l u b e c k i s G . Iterated tabu search for the unconstrained binary quadratic optimization problem
// Informatica. — 2006. — 17, N 2. — P. 279–296.
13. A l k h a m i s T . M . , H a s a n M . , A h m e d M . A . Simulated annealing for the unconstrained
binary quadratic pseudo-boolean function // Eur. J. of Oper. Res. — 1998. — 108. — P. 641–652.
14. K a t a y a m a K . , N a r i h i s a H . Performance of simulated annealing-based heuristic for the
unconstrained binary quadratic programming problem // Eur. J. of Oper. Res. — 2001. — 134. —
P. 103–119.
15. L o d i A . , A l l e m a n d K . , L i e b l i n g T . M . An evolutionary heuristic for quadratic 0–1
programming // Eur. J. of Oper. Res. — 1999. — 119. — P. 662–670.
16. B o r g u l y a I . An evolutionary algorithm for the binary quadratic problems // Advances in Soft
Computing. — 2005. — 2. — P. 3–16.
17. K a t a y a m a K . , T a n i M . , N a r i h i s a H . Solving large binary quadratic programming
problems by an effective genetic local search algorithm // Proc. of the Genetic and Evolutionary
Computation Conference (GECCO99). — Morgan Kaufmann. — 2000. — P. 643–650.
18. M e r z P . , F r e i s l e b e n B . Genetic algorithms for binary quadratic programming // Proceedings
of the Genetic and Evolutionary Computation Conference (GECCO99). Morgan Kaufmann, 1999.
— P. 417–424
19. M e r z P . , K a t a y a m a K . Memetic algorithms for the unconstrained binary quadratic
programming problem // BioSystems. — 2004. — 78. — P. 99–118.
20. A m i n i M . , A l i d a e e B . , K o c h e n b e r g e r G . A . A scatter search approach to
unconstrained quadratic binary programs. New Methods in Optimization. — New York:
McGraw-Hill, 1999. — P. 317–330.
21. G l o b a l equilibrium search applied to the unconstrained binary quadratic optimization problem /
P.M. Pardalos, O.A. Prokopyev, O.V. Shylo, V.P. Shylo // Optimization Methods and Software. —
2008. — 23. — P. 129 — 140.
22. Ø è ë î Â . Ï . Ìåòîä ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç.
— 1999. — ¹ 1. — Ñ. 74–81.
23. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû ðå-
øåíèÿ, èññëåäîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 2003. — 264 ñ.
Ïîñòóïèëà 20.06.2011
78 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
|
| id | nasplib_isofts_kiev_ua-123456789-84252 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T15:35:15Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шило, В.П. Шило, О.В. 2015-07-04T14:51:23Z 2015-07-04T14:51:23Z 2011 Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска / В.П. Шило, О.В. Шило // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 68-78. — Бібліогр.: 23 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84252 519.854 Розроблено новий, оснований на використанні методу глобального рівноважного пошуку (ГРП) алгоритм розв’язання задачі бульового квадратичного програмування без обмежень. Проведено його порівняльне дослідження з кращими на даний час алгоритмами розв’язання цієї задачі. Показано переваги алгоритму ГРП як за швидкодією, так і за можливістю отримання кращих розв’язків. A new algorithm based on the global equilibrium search (GES) is developed to solve the unconstrained binary quadratic programming (UBQP) problem. It is compared with currently the best techniques for the solution of this problem. The GES algorithm is shown to be better both in the speed and solution quality. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска Розв’язання задачі бульового квадратичного програмування без обмежень методом глобального рівноважного пошуку Global equilibrium search for solving the unconstrained binary quadratic programming problem Article published earlier |
| spellingShingle | Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска Шило, В.П. Шило, О.В. Системный анализ |
| title | Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска |
| title_alt | Розв’язання задачі бульового квадратичного програмування без обмежень методом глобального рівноважного пошуку Global equilibrium search for solving the unconstrained binary quadratic programming problem |
| title_full | Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска |
| title_fullStr | Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска |
| title_full_unstemmed | Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска |
| title_short | Решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска |
| title_sort | решение задачи булева квадратичного программирования без ограничений методом глобального равновесного поиска |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84252 |
| work_keys_str_mv | AT šilovp rešeniezadačibulevakvadratičnogoprogrammirovaniâbezograničeniimetodomglobalʹnogoravnovesnogopoiska AT šiloov rešeniezadačibulevakvadratičnogoprogrammirovaniâbezograničeniimetodomglobalʹnogoravnovesnogopoiska AT šilovp rozvâzannâzadačíbulʹovogokvadratičnogoprogramuvannâbezobmeženʹmetodomglobalʹnogorívnovažnogopošuku AT šiloov rozvâzannâzadačíbulʹovogokvadratičnogoprogramuvannâbezobmeženʹmetodomglobalʹnogorívnovažnogopošuku AT šilovp globalequilibriumsearchforsolvingtheunconstrainedbinaryquadraticprogrammingproblem AT šiloov globalequilibriumsearchforsolvingtheunconstrainedbinaryquadraticprogrammingproblem |