О сходимости модифицированного алгоритма ускоренного вероятностного моделирования
Розглянуто питання збіжності алгоритмів прискореного ймовірнісного моделювання (G-алгоритми). Запропоновано модифікацію G-алгоритму, побудовану на базі нового ймовірнісного механізму, який використовується для відсіву точок в околі поточного розв'язку. Для даної модифікації одержано теоретично...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/71980 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О сходимости модифицированного алгоритма ускоренного вероятностного моделирования / Д.А. Гобов // Кибернетика и системный анализ. — 2008. — № 1. — С. 173-179. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-71980 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-719802014-12-16T03:02:10Z О сходимости модифицированного алгоритма ускоренного вероятностного моделирования Гобов, Д.А. Системный анализ Розглянуто питання збіжності алгоритмів прискореного ймовірнісного моделювання (G-алгоритми). Запропоновано модифікацію G-алгоритму, побудовану на базі нового ймовірнісного механізму, який використовується для відсіву точок в околі поточного розв'язку. Для даної модифікації одержано теоретично обгрунтовану оцінку швидкості збіжності, що не залежить від початкового наближення. Наведено результати обчислювального експерименту, що демонструють порівняльну ефективність класичного та модифікованого G-алгоритмів. 2008 Article О сходимости модифицированного алгоритма ускоренного вероятностного моделирования / Д.А. Гобов // Кибернетика и системный анализ. — 2008. — № 1. — С. 173-179. — Бібліогр.: 14 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/71980 519.854 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Гобов, Д.А. О сходимости модифицированного алгоритма ускоренного вероятностного моделирования Кибернетика и системный анализ |
| description |
Розглянуто питання збіжності алгоритмів прискореного ймовірнісного моделювання (G-алгоритми). Запропоновано модифікацію G-алгоритму, побудовану на базі нового ймовірнісного механізму, який використовується для відсіву точок в околі поточного розв'язку. Для даної модифікації одержано теоретично обгрунтовану оцінку швидкості збіжності, що не залежить від початкового наближення. Наведено результати обчислювального експерименту, що демонструють порівняльну ефективність класичного та модифікованого G-алгоритмів. |
| format |
Article |
| author |
Гобов, Д.А. |
| author_facet |
Гобов, Д.А. |
| author_sort |
Гобов, Д.А. |
| title |
О сходимости модифицированного алгоритма ускоренного вероятностного моделирования |
| title_short |
О сходимости модифицированного алгоритма ускоренного вероятностного моделирования |
| title_full |
О сходимости модифицированного алгоритма ускоренного вероятностного моделирования |
| title_fullStr |
О сходимости модифицированного алгоритма ускоренного вероятностного моделирования |
| title_full_unstemmed |
О сходимости модифицированного алгоритма ускоренного вероятностного моделирования |
| title_sort |
о сходимости модифицированного алгоритма ускоренного вероятностного моделирования |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2008 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/71980 |
| citation_txt |
О сходимости модифицированного алгоритма ускоренного вероятностного моделирования / Д.А. Гобов // Кибернетика и системный анализ. — 2008. — № 1. — С. 173-179. — Бібліогр.: 14 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT gobovda oshodimostimodificirovannogoalgoritmauskorennogoveroâtnostnogomodelirovaniâ |
| first_indexed |
2025-07-05T20:51:52Z |
| last_indexed |
2025-07-05T20:51:52Z |
| _version_ |
1836841657919602688 |
| fulltext |
ÓÄÊ 519.854
Ä.À. ÃÎÁÎÂ
Î ÑÕÎÄÈÌÎÑÒÈ ÌÎÄÈÔÈÖÈÐÎÂÀÍÍÎÃÎ ÀËÃÎÐÈÒÌÀ
ÓÑÊÎÐÅÍÍÎÃÎ ÂÅÐÎßÒÍÎÑÒÍÎÃÎ ÌÎÄÅËÈÐÎÂÀÍÈß
Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, ñõîäèìîñòü, àëãîðèòìû âå-
ðîÿòíîñòíîãî ìîäåëèðîâàíèÿ, G-àëãîðèòì.
ÂÂÅÄÅÍÈÅ
Çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè âñòðå÷àþòñÿ âî ìíîãèõ îáëàñòÿõ ïðàêòè÷åñ-
êîé äåÿòåëüíîñòè (íàïðèìåð, â çàäà÷àõ ïðîãíîçèðîâàíèÿ, ñîñòàâëåíèÿ ïëàíîâ,
óïðàâëåíèÿ ðåñóðñàìè è òðàíñïîðòíûìè ñðåäñòâàìè, ñîñòàâëåíèÿ áþäæåòà, ñåòå-
âîé ìàðøðóòèçàöèè è ìíîãîå äðóãîå). Â íàñòîÿùåå âðåìÿ ïåðñïåêòèâíûì íàïðàâ-
ëåíèåì â ñîçäàíèè ìåòîäîâ äèñêðåòíîé îïòèìèçàöèè ÿâëÿåòñÿ èñïîëüçîâàíèå òåõ
èëè èíûõ âåðîÿòíîñòíûõ ìåõàíèçìîâ. Ðàññìîòðèì îäèí èç èçâåñòíåéøèõ ïðèìå-
ðîâ àëãîðèòìîâ òàêîãî êëàññà — ìåòîäû ñòîõàñòè÷åñêîãî ëîêàëüíîãî ïîèñêà, â
÷àñòíîñòè ìåòîä èìèòàöèîííîãî îòæèãà [1]. Êðîìå îöåíêè ýôôåêòèâíîñòè äàííîãî
ìåòîäà ïóòåì ïðîâåäåíèÿ âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ, âàæíîå çíà÷åíèå èìåþò
òåîðåòè÷åñêèå èññëåäîâàíèÿ åãî ñõîäèìîñòè. Òàê, â ðàáîòàõ [2–4] îïðåäåëåíû äîñ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 173
© Ä.À. Ãîáîâ, 2008
òàòî÷íûå óñëîâèÿ äëÿ ïîñëåäîâàòåëüíîñòè òåìïåðàòóð, ïðè âûïîëíåíèè êîòîðûõ
â àëãîðèòìàõ îòæèãà ïîñëåäîâàòåëüíîñòü ðåøåíèé, ïîëó÷àåìûõ íà êàæäîé èòåðà-
öèè, ñõîäèòñÿ ê îïòèìàëüíîìó âåêòîðó ïî âåðîÿòíîñòè. Â [5, 6] ïðåäëîæåíû òåì-
ïåðàòóðíûå ðàñïèñàíèÿ, êîòîðûå óäîâëåòâîðÿþò íåîáõîäèìûì è äîñòàòî÷íûì
óñëîâèÿì äëÿ ñõîäèìîñòè ïî âåðîÿòíîñòè ê ìíîæåñòâó ãëîáàëüíûõ ðåøåíèé. Äðó-
ãîé ïîäõîä ïðåäëîæåí â [7], ãäå èññëåäîâàíà ñõîäèìîñòü àëãîðèòìà èìèòàöèîííî-
ãî îòæèãà, êîòîðûé ãàðàíòèðóåò íàõîæäåíèÿ èìåííî ãëîáàëüíîãî ðåøåíèÿ. Áëèçêè-
ìè ïî ñõåìå ê ìåòîäó èìèòàöèîííîãî îòæèãà ÿÿâëÿþòñÿ àëãîðèòìû óñêîðåííîãî
âåðîÿòíîñòíîãî ìîäåëèðîâàíèÿ (G-àëãîðèòìû) (ñì. [8] è ëèòåðàòóðó ê íåé). Â [9]
ðàññìîòðåí âîïðîñ ñõîäèìîñòè êëàññè÷åñêîãî G-àëãîðèòìà.  äàííîé ðàáîòå ïðåä-
ëàãàåòñÿ íîâàÿ ìîäèôèêàöèÿ àëãîðèòìà óñêîðåííîãî âåðîÿòíîñòíîãî ìîäåëèðîâàíèÿ
è èññëåäóåòñÿ åãî ñõîäèìîñòü.
1. ÌÎÄÈÔÈÊÀÖÈß ÀËÃÎÐÈÒÌÀ ÓÑÊÎÐÅÍÍÎÃÎ ÂÅÐÎßÒÍÎÑÒÍÎÃÎ
ÌÎÄÅËÈÐÎÂÀÍÈß È ÅÃÎ ÑÕÎÄÈÌÎÑÒÜ
Çàäà÷à êîìáèíàòîðíîé îïòèìèçàöèè õàðàêòåðèçóåòñÿ òðåìÿ îñíîâíûìè àñïåê-
òàìè [10]:
• ïðîñòðàíñòâî ïîèñêà�, ñîñòîÿùåå èç êîíå÷íîãî ÷èñëà òî÷åê (èçðåäêà ñ÷åòíîãî);
• öåëåâàÿ ôóíêöèÿ f x( ), êîòîðàÿ îïðåäåëåíà íà ïðîñòðàíñòâå ïîèñêà�;
• îãðàíè÷åíèÿ íà ïðîñòðàíñòâî ïîèñêà.
Áîëåå ôîðìàëüíî îíà çàêëþ÷àåòñÿ â ñëåäóþùåì: íåîáõîäèìî íàéòè òàêóþ òî÷êó
x * ��, ÷òî x f xx
* ( )� �arg min � . Íå îãðàíè÷èâàÿ îáùíîñòè, áóäåì ïîëàãàòü, ÷òî
f x( ) � 0, à � — êîíå÷íîå ìåòðè÷åñêîå ïðîñòðàíñòâî ñ ìåòðèêîé d.
Îïðåäåëåíèå 1. Îêðåñòíîñòüþ òî÷êè x �� ïðîèçâîëüíîãî ðàäèóñà � � 0 íà-
çûâàåòñÿ ìíîæåñòâî N x y d x y( ) , ( , )� � �{ }� � , ãäå d x y( , ) — îïðåäåëåííàÿ íà
ïðîñòðàíñòâå � ìåòðèêà.
Ïðèâåäåì îáùóþ ñõåìó G-àëãîðèòìà [8]:
procedure G-search (x);
begin
�0 0 0: ; :� �h ;
while (íå âûïîëíåí êðèòåðèé îñòàíîâà) do
begin
while (íå âûïîëíåíî óñëîâèå ðàâíîâåñèÿ) do
begin
y : � î÷åðåäíàÿ òî÷êà îêðåñòíîñòè x;
� : ( ) ( )� �f y f x ;
p x y
z f x
( , ) : min ,
( )
� �
�
�
�
�
1 1
�
;
� � �: [ , ] ( )� � �h hrandom 0 1 1 ;
if (p � �) then
begin
x y: � ;
end
end;
� �h hG� �1 ( );
h h: � � 1;
end;
return x;
end.
Çäåñü G :[ , ) [ , )0 1 0 1� — íåêîòîðàÿ ñòðîãî ìîíîòîííàÿ ôóíêöèÿ,
à random[0,1] — äàò÷èê ñëó÷àéíûõ ÷èñåë èç îòðåçêà [0,1]. Äëÿ òàêîé ôîðìû G-àë-
ãîðèòìà íåëüçÿ òåîðåòè÷åñêè äîêàçàòü ñõîäèìîñòü ê ãëîáàëüíîìó îïòèìóìó, íà-
ïðèìåð, â îòëè÷èå îò àëãîðèòìà èìèòàöèîííîãî îòæèãà. Ðàññìîòðèì ñëåäóþùèé
ñëó÷àé. Ïóñòü �h w� � 0, à x * — ëîêàëüíûé îïòèìóì, äëÿ êîòîðîãî âûïîëíÿåò-
ñÿ: � �y N x( )* f y f x w z( ) ( ) [ ( ) ]*� � �1 1 . Îòñþäà
� �y N x( )* p x y
f x w z f x
zf x
w w( , )
( )[ ( ) ] ( )
( )
.*
* *
*
� �
� � �
� � � �1
1 1
1 1
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
Òàêèì îáðàçîì, p y N x� � �� ( )* . Ýòî îçíà÷àåò, ÷òî â ïðèâåäåííîì âûøå
ñëó÷àå àëãîðèòì íå ñìîæåò âûéòè èç ëîêàëüíîãî îïòèìóìà. Ïîýòîìó äàëüøå
ïðåäëàãàåòñÿ ìîäèôèêàöèÿ óêàçàííîãî G-àëãîðèòìà, êîòîðàÿ ïîçâîëÿåò òåîðåòè-
÷åñêè îáîñíîâàòü ñêîðîñòü ñõîäèìîñòè ê ãëîáàëüíîìó îïòèìóìó. Ñóòü ìîäèôè-
êàöèè çàêëþ÷àåòñÿ â íîâîì âåðîÿòíîñòíîì ìåõàíèçìå, êîòîðûé ïðèìåíÿåòñÿ äëÿ
îòñåâà òî÷åê â îêðåñòíîñòè òåêóùåãî ðåøåíèÿ. Ïðåäëàãàåòñÿ ðàññ÷èòûâàòü âåðîÿò-
íîñòü ïåðåõîäà îò òî÷êè x ê ïðîèçâîëüíîé òî÷êå y îêðåñòíîñòè N x( ) ïî ôîðìóëå
p x y
g
( , ) min , ( ) ( ( ))� � � � �
�
�
�
�
1 1 1
2
1
�
��
�
sgn ,
ãäå �sgn ( ) , ,x x x� �� �1 01 0, g z f� , f f x x� � �( ) �.
Áóäåì ñ÷èòàòü, ÷òî èçâåñòíà âåðõíÿÿ ãðàíèöà f öåëåâîé ôóíêöèè f x( ): ïî-
ñêîëüêó ïðîñòðàíñòâî � êîíå÷íî, òî îíà ìîæåò áûòü ðàññ÷èòàíà ñ ïîìîùüþ ìå-
òîäîâ îöåíêè äëÿ êîíêðåòíîãî âèäà çàäà÷è ( íàïðèìåð, äëÿ êâàäðàòè÷íîé çàäà÷è
î íàçíà÷åíèÿõ [11, 12]). Ðàññìîòðèì çíà÷åíèå âåðîÿòíîñòè ïðè � � 0 è � � 0.
1. Ïóñòü � � 0, òîãäà
p x y
g
( , ) min , ( ) ( ( ))� � � � �
�
�
�
�
�1 1 1
2
1
�
��
�
sgn
� � � �
�
�
�
�
� �
�
�
�
�
�
� �
�
�
�
�
min , min , ( )1 1 1 1 1
� � �
g g g
� � � .
2. Åñëè � � 0, òî èìååì
p x y
g g
( , ) min , ( ) ( ( )) min ,� � � � �
�
�
�
�
� �1 1 1
2
1 1 1
�
�
�
�
�
sgn ( )1�
�
�
�
�
� .
Èç òîãî, ÷òî � � 0 è 1 0� �� , ñëåäóåò 1 1 1� � �
�
g
( )� . Òàêèì îáðàçîì,
p x y
g
( , ) min , ( )� � �
�
�
�
�
�1 1 1 1
�
� . Âàæíî îòìåòèòü, ÷òî â ìîäèôèöèðîâàííîì àë-
ãîðèòìå ñëó÷àéíàÿ âåëè÷èíà ��[ , ]0 1 .
Âû÷èñëèòåëüíóþ ñõåìó ñ èñïîëüçîâàíèåì óêàçàííîãî âåðîÿòíîñòíîãî ìåõà-
íèçìà íàçîâåì G *-àëãîðèòìîì è ïðåäñòàâèì â ñëåäóþùåì âèäå:
procedure G*-search (x);
begin
�0 0 0: ; :� �h ;
while (íå âûïîëíåí êðèòåðèé îñòàíîâà) do
begin
while(íå âûïîëíåíî óñëîâèå ðàâíîâåñèÿ) do
begin
y : � ñëó÷àéíàÿ òî÷êà îêðåñòíîñòè x;
� : ( ) ( )� �f y f x ;
p x y
g
( , ) : min , ( ) ( ( ))� � � � �
�
�
�
�
1 1 1
2
1
�
��
�
sgn
� : [ , ]� random 0 1 ;
if ( )p � � then
begin
x y: � ;
end
end;
� �h hG� �1 ( );
h h: � � 1;
end;
return x;
end.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 175
Ïóñòü � ( , )V E — îðèåíòèðîâî÷íûé ãðàô, êîòîðûé ñîîòíîñèòñÿ ñ çàäà÷åé
îïòèìèçàöèè ñëåäóþùèì îáðàçîì: âåðøèíà i â � — ýòî òî÷êà xi ��, à ðåáðà ñîå-
äèíÿþò âåðøèíó i ñ òî÷êàìè, êîòîðûå âõîäÿò â çàäàííóþ îêðåñòíîñòü xi . Òîãäà
ìîæíî ñ÷èòàòü, ÷òî G *-àëãîðèòì ñòðîèò ñëó÷àéíûé ìàðøðóò íà ýòîì ãðàôå. Ïå-
ðåõîä èç îäíîé òî÷êè ïðîñòðàíñòâà � â äðóãóþ çàâèñèò òîëüêî îò òåêóùåãî ñî-
ñòîÿíèÿ. Ýòî ïîçâîëÿåò ðàññìàòðèâàòü òðàåêòîðèþ G *-àëãîðèòìà êàê öåïü Ìàð-
êîâà, à ïðè ôèêñèðîâàííîì çíà÷åíèè � — êàê îäíîðîäíóþ öåïü Ìàðêîâà.
Ðàññìîòðèì ñëó÷àé, êîãäà ãðàô � ñèëüíî ñâÿçàííûé, ò.å. äëÿ äâóõ ïðîèçâîëü-
íûõ âåðøèí i è j â V ñóùåñòâóåò îðèåíòèðîâàííàÿ öåïü èç i äî j. Òàêîé ñëó÷àé, â
÷àñòíîñòè, ìîäåëèðóåò ðîáîòó íà ïðîñòðàíñòâå ïåðåñòàíîâîê. Äëÿ ëþáîé âåðøèíû i
â � îáîçíà÷èì M i( ) ìíîæåñòâî èíöèäåíòíûõ åé âåðøèí. Åñëè ñ÷èòàòü, ÷òî êîãäà
öåïü Ìàðêîâà íàõîäèòñÿ â ñîñòîÿíèè i, êàæäîå ñîñòîÿíèå èç åãî M i( ) ìîæåò áûòü
ñãåíåðèðîâàíî G *-àëãîðèòìîì ñ îäèíàêîâîé âåðîÿòíîñòüþ, êîòîðàÿ ðàâíÿåòñÿ
1 / | ( ) |M i , òî âåðîÿòíîñòü ïåðåõîäà èç i â j ïðè çàäàííîì çíà÷åíèè � ðàññ÷èòûâàåòñÿ
ñëåäóþùèì îáðàçîì:
P
j M i j i
M i g
ij ( )
, ( ), ,
| ( ) |
min , ( ) (
�
�
��
� �
� � �
0
1
11 1
2
1
åñëè
�
�
�
�
�
�
� �
�
�
sgn åñëè( )) , ( ), ,� j M i j i
P Pii
j M i
ij( ) ( )
( )
� �� �
�
!1 .
Èñïîëüçóåì ýòó ìîäåëü äëÿ äîêàçàòåëüñòâà ñõîäèìîñòè G *-àëãîðèòìà.
Îïðåäåëåíèå 2 [7]. Àëãîðèòì îïòèìèçàöèè ñõîäèòñÿ, åñëè öåïü Ìàðêîâà ñî-
äåðæèò ãëîáàëüíî îïòèìàëüíîå ñîñòîÿíèå. Åñòü è äðóãèå îïðåäåëåíèÿ ñõîäèìîñ-
òè, íàïðèìåð ñõîäèìîñòü ïî âåðîÿòíîñòè âåêòîðà ñîñòîÿíèÿ ê îïòèìàëüíîìó âåê-
òîðó [2], íî äëÿ íàøèõ èññëåäîâàíèé íàèáîëåå àäåêâàòíî èìåííî ïðèâåäåííîå
îïðåäåëåíèå.
Ïóñòü èìååì öåëåâóþ ôóíêöèþ f x( ), ãðàô � ( , )V E , ïîñòðîåííûé ñîãëàñíî ïðèâå-
äåííûì âûøå ïðàâèëàì. Ïóñòü �� — ìàêñèìàëüíîå çíà÷åíèå ïàðàìåòðà �,
� � �
� �
max ( ) ( )
, ( )i V j M i
i jf x f x{ }. Èç òîãî, ÷òî� — êîíå÷íîå ìíîæåñòâî, à ôóíêöèÿ
f îãðàíè÷åíà âåëè÷èíîé f , èìååì �� ", �� 0. Îáîçíà÷èì ñòåïåíü è äèàìåòð � ( , )V E
êàê d è D ñîîòâåòñòâåííî. Î÷åâèäíî, ÷òî äëÿ ëþáîãî i V� âåëè÷èíà pij ïðè ëþáîì çíà-
÷åíèè � íå ìåíüøå âåëè÷èíû ( )*1 1� �
�
�
�
�
�
��
�
g
, åñëè j M i� ( ).
Ñîãëàñíî [7] äëÿ àëãîðèòìà, êîòîðûé ñòðîèò ñëó÷àéíûé ìàðøðóò íà ñèëüíî
ñâÿçàííîì ãðàôå � ( , )V E , ïîñòðîåííîì ñîãëàñíî ïðèâåäåííûì âûøå ïðàâèëàì,
òðàåêòîðèþ êîòîðîãî ðàññìàòðèâàòü êàê öåïü Ìàðêîâà è äëÿ ëþáûõ i j V, � âåðî-
ÿòíîñòü ïåðåõîäà èç âåðøèíè i â âåðøèíó j áîëüøå 0 ïðè j M i� ( ), òî ìàòåìàòè-
÷åñêîå îæèäàíèå êîëè÷åñòâà øàãîâ, íåîáõîäèìûõ äëÿ òîãî, ÷òîáû ïîñåòèòü ñîñòîÿ-
íèå, îòâå÷àþùåå ãëîáàëüíîìó îïòèìóìó (opt) ïðè ïðîèçâîëüíîì íà÷àëüíîì ñîñòîÿ-
íèè X , íå ïðåâûøàåò âåëè÷èíû
1
d
p
D
#�
�
�
�
�
�
�
, ãäå p p i j Vij# � �min ( ), , .
G *-àëãîðèòì óäîâëåòâîðÿåò ýòèì óñëîâèÿì. Òàêèì îáðàçîì ïîëó÷àåì, ÷òî ìàòå-
ìàòè÷åñêîå îæèäàíèå êîëè÷åñòâà øàãîâ, íåîáõîäèìûõ äëÿ òîãî, ÷òîáû ïîñåòèòü
ñîñòîÿíèå opt äëÿ G *-àëãîðèòìà, íå ïðåâûøàåò âåëè÷èíû d
g
g
D
( )( )*1� �
�
�
�
�
�
�
�
�
$
%
&
&
'
(
)
)� �
.
Òåîðåìà 1. G *-àëãîðèòì ñõîäèòñÿ çà êîëè÷åñòâî øàãîâ, êîòîðîå íå ïðåâû-
øàåò âåëè÷èíû 2
1
k d
g
g
D
( )( )*� �
$
%
&
&
'
(
)
)� �
, ñ âåðîÿòíîñòüþ íå ìåíüøå ( )1 2� � k ïðè
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
ëþáîì íà÷àëüíîì ñîñòîÿíèè, ãäå k — íàòóðàëüíîå ÷èñëî.
Äîêàçàòåëüñòâî. Ïóñòü E d
g
g
D
�
� �
$
%
&
&
'
(
)
)
2
1( )( )*� �
.
Äîêàçàòåëüñòâî òîãî, ÷òî âåðîÿòíîñòü íå ïîñåùåíèÿ ñîñòîÿíèÿ opt íà ïðîòÿ-
æåíèè kE øàãîâ ìåíüøå èëè ðàâíà âåëè÷èíå 2� k , ïðîâåäåì ñ ïîìîùüþ ìàòåìà-
òè÷åñêîé èíäóêöèè.
Øàã 1. k �1. Ïóñòü B — êîëè÷åñòâî øàãîâ àëãîðèòìà äî òîãî ìîìåíòà, êîãäà
ñîñòîÿíèå opt áóäåò ïîñåùåíî.
Ñîãëàñíî íåðàâåíñòâó Ìàðêîâà ïîëó÷àåì
P B d
g
g
d
g
g
D
�
� �
$
%
&
&
'
(
)
)
$
%
&
&
'
(
)
)
� �
� �
2
1
1
1
( )( )
( )( )
*
*
� �
� �
$
%
&
&
'
(
)
)
� �
$
%
&
&
'
(
)
)
� � �
D
D
d
g
g
2
1
1
1
2
1
2
( )( )*� �
.
Øàã 2. Ïóñòü òåîðåìà âûïîëíÿåòñÿ äëÿ âñåõ k r� �( )1 .
Øàã 3. Äîêàæåì òåîðåìó äëÿ k r� .
Ïóñòü X X XE E r E, , , ( )2 1� � — ìíîæåñòâà ñîñòîÿíèé öåïè Ìàðêîâà, êîòî-
ðûå áûëè ïîñåùåíû íà ïðîòÿæåíèè øàãîâ E, 2E,..., ( )r E�1 ñîîòâåòñòâåííî. Ðàñ-
ñìîòðèì äâà ñîáûòèÿ.
Ñîáûòèå A: ñîñòîÿíèå opt íå áûëî ïîñåùåíî íà ïðîòÿæåíèè ïåðâûõ E øàãîâ.
Ñîáûòèå B: ñîñòîÿíèå opt íå áûëî ïîñåùåíî íà ïðîòÿæåíèè ñëåäóþùèõ
( )r E�1 øàãîâ.
Òîãäà âåðîÿòíîñòü P òîãî, ÷òî opt íå áóäåò ïîñåùåí çà rE øàãîâ, ðàññ÷èòû-
âàåòñÿ ñëåäóþùèì îáðàçîì: P P B A P A� [ / ]* [ ], ãäå P A[ ] — âåðîÿòíîñòü íà-
ñòóïëåíèÿ ñîáûòèÿ A, P B A[ / ] — âåðîÿòíîñòü íàñòóïëåíèÿ ñîáûòèÿ B ïðè óñëî-
âèè, ÷òî íàñòàëî ñîáûòèå A.
Âåëè÷èíà P B A[ / ] çàâèñèò òîëüêî îò ñîñòîÿíèÿ öåïè Ìàðêîâà íà øàãå E
è êîëè÷åñòâà øàãîâ ( )r E�1 . Îòñþäà P P A P B X i P X i
i V
E E� � �
�
![ ] [ / ] [ ] , íî
P A[ ] /� 1 2 è P B X iE
r[ / ] ( )� � � �2 1 äëÿ êàæäîãî i V� (ñîãëàñíî ãèïîòåçå èí-
äóêöèè).
Òàêèì îáðàçîì, èìååì
1
2
2 21� � ��( )r r .
Òåîðåìà äîêàçàíà.
Ðàññìîòðèì çàäà÷è îïòèìèçàöèè, îïðåäåëåííûå íà ïðîñòðàíñòâå � ïåðåñòà-
íîâîê ðàçìåðíîñòè n.
Îïðåäåëåíèå 3. Ðàññòîÿíèåì d a b( , ) ìåæäó äâóìÿ ïðîèçâîëüíûìè ïåðåñòà-
íîâêàìè a è b, a b, ��, áóäåì íàçûâàòü ìèíèìàëüíîå êîëè÷åñòâî òðàíñïîçèöèé,
êîòîðûå ïðåâðàùàþò ïåðåñòàíîâêó a â b.
Íàïîìíèì, ÷òî ïîä òðàíñïîçèöèåé ïîíèìàåòñÿ îáìåí ìåñòàìè äâóõ ýëåìåí-
òîâ ïåðåñòàíîâêè [13].
Ðàññìîòðèì ñëó÷àé îêðåñòíîñòè ñ ðàäèóñîì 1:
d C
n
n
n n
n� �
�
�
�2
2 2
1
2
!
( ) ! !
( )
, D n� �1.
Ñ ó÷åòîì ýòîãî èìååì î÷åðåäíîé ðåçóëüòàò.
Ñëåäñòâèå 1. G*
-àëãîðèòì íà ïðîñòðàíñòâå � ïåðåñòàíîâîê ðàçìåðíîñòè n
ñ ðàäèóñîì îêðåñòíîñòè 1 ñõîäèòñÿ çà êîëè÷åñòâî øàãîâ, êîòîðîå íå ïðåâûøàåò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 177
âåëè÷èíû 2
1
2 1
1
k
n n g
g
n
( )
( )( )*
�
� �
$
%
&
&
'
(
)
)
�
� �
ñ âåðîÿòíîñòüþ, íå ìåíüøåé ( )1 2� � k
ïðè ïðîèçâîëüíîì íà÷àëüíîì ñîñòîÿíèè, ãäå k — íàòóðàëüíîå ÷èñëî.
2. ÂÛ×ÈÑËÈÒÅËÜÍÛÉ ÝÊÑÏÅÐÈÌÅÍÒ
Äëÿ ñðàâíåíèÿ ýôôåêòèâíîñòè G *- è G-àëãîðèòìà ðåøàëèñü êâàäðàòè÷íûå çàäà÷è
î íàçíà÷åíèÿõ (ÊÇÍ), äëÿ êîòîðûõ èçâåñòíû èëè òî÷íûå ðåøåíèÿ, èëè ëó÷øèå èç
èçâåñòíûõ. Ðåàëüíûå è òåñòîâûå çàäà÷è âçÿòû èç áèáëèîòåêè [14].
Âû÷èñëåíèÿ âûïîëíÿëèñü íà ðàáî÷åé ñòàíöèè ñî ñëåäóþùèìè õàðàêòåðèñ-
òèêàìè: ïðîöåññîð AMD Turion 2,19 Ghz, RAM 512 Máàéò. Äëÿ ïîëó÷åíèÿ ñòàòè-
÷åñêè îáîñíîâàííûõ ðåçóëüòàòîâ ïî êàæäîé çàäà÷å ïðîâîäèëàñü ñåðèÿ ýêñïåðè-
ìåíòîâ ñ îäèíàêîâûìè ïàðàìåòðàìè àëãîðèòìà è ðàçíûìè íà÷àëüíûìè ïðèáëè-
æåíèÿìè öåëåâîé ôóíêöèè. Íåêîòîðûå ðåçóëüòàòû ðÿäà èçâåñòíûõ çàäà÷
ïðèâåäåíû â òàáë. 1, ãäå n — ðàçìåðíîñòü çàäà÷è, q — ñðåäíåå óëó÷øåíèå çíà÷å-
íèé öåëåâîé ôóíêöèè îòíîñèòåëüíî íà÷àëüíîãî âàðèàíòà ðåøåíèÿ, êîòîðîå ðàñ-
ñ÷èòûâàåò ïî ôîðìóëå
q
C
f f
fi
C
i i
i
�
�
�
*
*
!1
100
1
íà
íà
*
%,
ãäå f i íà* — íà÷àëüíîå ïðèáëèæåíèå öåëåâîé ôóíêöèè â ýêñïåðèìåíòå i, ïîëó÷åí-
íîå ìåòîäîì Ìîíòå-Êàðëî, f i
* — çíà÷åíèå öåëåâîé ôóíêöèè â ýêñïåðèìåíòå i, êî-
òîðîå îòâå÷àåò íàéäåííîìó äàííûì àëãîðèòìîì ðåøåíèþ; t — âðåìÿ ðàáîòû ñîîò-
âåòñòâóþùåãî àëãîðèòìà (â ñ), C — îáúåì ñåðèè ýêñïåðèìåíòîâ ïî ðåøåíèþ çàäà-
÷è (äëÿ âñåõ çàäà÷ âûáèðàëîñü C � 50).
Ðåçóëüòàòû âû÷èñëèòåëüíîãî ýêñïåðèìåíòà ñâèäåòåëüñòâóþò, ÷òî äëÿ çàäà÷
ïðàêòè÷åñêè âñåõ ðàçìåðíîñòåé â ñðåäíåì ýôôåêòèâíîñòü G *-àëãîðèòìà áûëà íå
õóæå ýôôåêòèâíîñòè G-àëãîðèòìà.
 òàáë. 2 ïðèâåäåíû çíà÷åíèÿ ñðåäíåêâàäðàòè÷íîãî îòêëîíåíèÿ (�) è âåëè-
÷èíà äîâåðèòåëüíîãî èíòåðâàëà ( ) äëÿ âåëè÷èíû óëó÷øåíèÿ çíà÷åíèÿ öåëåâîé
ôóíêöèè.
Ïðèâåäåííûå äàííûå ñâèäåòåëüñòâóþò, ÷òî äîâåðèòåëüíûå èíòåðâàëû äîñ-
òàòî÷íî ìàëû, ïîýòîìó îöåíêè ýôôåêòèâíîñòè àëãîðèòìîâ ìîæíî ñ÷èòàòü
äîñòîâåðíûìè.
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
Íàçâàíèå
çàäà÷è
n
G--àëãîðèòì G
*-àëãîðèòì
q t q t
Chr20 20 70,78 0,5 70,85 0,51
Chr20 20 71,60 0,54 71,80 0,51
Chr20 20 76,44 0,54 76,14 0,56
Lip40a 40 2,41 3,9 2,41 3,8
Lipa50 50 1,98 7,36 1,98 7,47
Esp64a 64 58,07 9,1 58,14 9,17
Sco72 72 14,80 26,4 14,93 27,1
Sco81 81 14,72 47,03 14,86 48,08
Tai90a 90 1,12 8,16 1,12 22,31
Tai100b 100 30,39 35,92 30,40 40,30
Ò à á ë è ö à 1 . Ðåçóëüòàòû ðåøåíèÿ
ÊÇÍ
Íàçâàíèå
çàäà÷è
n
G--àëãîðèòì G
*-àëãîðèòì
� � � �
Chr20 20 5,39 5,42 5,07 5,1
Chr20 20 5,32 5,35 4,45 4,47
Chr20 20 6,92 6,96 5,68 5,71
Lip40a 40 0,33 0,33 0,23 0,23
Lipa50 50 0,19 0,19 0,20 0,20
Esp64a 64 2,79 2,8 2,83 2,84
Sco72 72 0,9 0,9 0,77 0,78
Sco81 81 0,71 0,71 0,73 0,74
Tai90a 90 0,069 0,07 0,08 0,08
Tai100b 100 1,46 1,47 1,46 1,47
Ò à á ë è ö à 2 . Ñðåäíåêâàäðïòè÷íîå
îòêëîíåíèå è âåëè÷èíà äîâåðèòåëüíîãî
èíòåðâàëà
ÇÀÊËÞ×ÅÍÈÅ
Ïðèìåíåíèå àëãîðèòìîâ óñêîðåííîãî âåðîÿòíîñòíîãî ìîäåëèðîâàíèÿ äëÿ ðå-
øåíèÿ øèðîêîãî êðóãà çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè êàê îòäåëüíûõ àë-
ãîðèòìîâ èëè â ñîñòàâå ìåòàýâðèñòèê âûçâàëî íåîáõîäèìîñòü èññëåäîâàíèÿ
ñõîäèìîñòè àëãîðèòìîâ ýòîãî êëàññà.
Äëÿ ïðåäëîæåííîé ìîäèôèêàöèè G-àëãîðèòìà ïîëó÷åíà òåîðåòè÷åñêè îá-
îñíîâàííàÿ îöåíêà ñêîðîñòè ñõîäèìîñòè, êîòîðàÿ íå çàâèñèò îò íà÷àëüíîãî ïðè-
áëèæåíèÿ. Ïðîâåäåí âû÷èñëèòåëüíûé ýêñïåðèìåíò äëÿ ñðàâíåíèÿ ýôôåêòèâíîñ-
òè êëàññè÷åñêîãî è ìîäèôèöèðîâàííîãî G-àëãîðèòìîâ.
Ïîëó÷åííûå ðåçóëüòàòû ïîçâîëÿþò óòâåðæäàòü, ÷òî èçìåíåíèÿ, âíåñåííûå â
âåðîÿòíîñòíûé ìåõàíèçì, íå óõóäøàþò ýôôåêòèâíîñòü àëãîðèòìà, òàêèì îáðà-
çîì, ïðåäëîæåííûé àëãîðèòì ìîæåò èñïîëüçîâàòüñÿ äëÿ ðåøåíèÿ øèðîêîãî êðó-
ãà ïðèêëàäíûõ çàäà÷.
Äàëüíåéøèå ðàçðàáîòêè áóäóò íàïðàâëåíû íà èññëåäîâàíèå âëèÿíèÿ âèäà
ôóíêöèè G, çíà÷åíèé ïàðàìåòðîâ àëãîðèòìà è õàðàêòåðèñòèê çàäà÷è íà ýôôåê-
òèâíîñòü àëãîðèòìà, ðàçðàáîòêà ìåõàíèçìà àâòîìàòè÷åñêîãî ïîäáîðà èçìåíÿå-
ìûõ ïàðàìåòðîâ àëãîðèòìà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÈ
1. K i r k p a t r i c k S . , G e l a t t C . D . , V e c c h i M . P . Optimization by Simulated Annealing //
Science. — 1983. — N 4598. — P. 671–680.
2. G e m a n S . , G e m a n D . Stochastic relaxation, Gibbs distribution, Bayesian restoration of image
// IEEE Trans. PAMI. — 1984. — N 6. — P. 721–741.
3. A n i l y S . , F e d e r g r u e n A . Simulated annealing methods with general acceptance probabili-
ties // J. of Applied Probability. — 1987. — N 35. — P. 657–667.
4. J o h n s o n A . W . a n d J a c o b s o n S . H . On the convergence of generalized hill climbing algo-
rithms // Discrete Appl. Mathemat. — 2002. — N 119. — P. 37–57.
5. G i d a s B . Nonstationary markov chains and convergence of the annealing algorithm // J. of Statis-
tic. Physics. — 1985. — N 39 — P. 73–131
6. H a j e k B . Cooling Shedules for Optimal Annealing // Math. Oper. Res. — 1988. — N 13. — P. 311–329.
7. R a j a s e k a r a n S . On Simulated Annealing and Nested Annealing // J. of Global Optimization.
— January 2000. — N 1. — P. 43–56.
8. à ó ë ÿ í è ö ê è é Ë . Ô . Ñ å ð ã è å í ê î È .  . Ìåòàýâðèñòè÷åñêèé ìåòîä äåôîðìèðóåìîãî
ìíîãîãðàííèêà â êîìáèíàòîðíîé îïòèìèçàöèè. // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007.
— ¹ 6. — Ñ. 70–79.
9. Ò ó ð ÷ è í Î . ß . Äîñëiäæåííÿ çáiæíîñòi àëãîðèòìó ïðèñêîðåíîãî éìîâiðíiñíîãî
ìîäåëþâàííÿ, ùî ðîçâ’ÿçóº ïåâíèé êëàñ çàäà÷ êîìáiíàòîðíî îïòèìiçàöi // Âiñí. ÊèÂâ.
óí-òó. — 2003. — ¹ 1. — Ñ. 216–221.
10. Ï à ï à ä è ì è ò ð è ó Õ . , Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. — Ì.: Ìèð, 1985. — 510 ñ.
11. G i l m o r e P . C . Optimal and suboptimal algorithms for the quadratic assignment problem //
SIAM J. on Appl. Mathemat. — 1962. — N 10. — P. 305–310.
12. H a d l e y S . W . , R e n d l F . , a n d W o l k o w i c z H . A new lower bound via projection for the
quadratic assignment problem // Mathemat. of Oper. Res. — 1992. — N 17. — P. 727—739.
13. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ
êîìáèíàòîðíûõ çàäà÷ îïòèìèçàöèè. — Êèåâ: Íàóê. äóìêà, 1981. — 288 ñ.
14. Q A P L I B // http://www.opt.math.tu-graz.ac.at/qaplib
Ïîñòóïèëà 19.04.2007
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 179
|