Классификация прикладных методов комбинаторной оптимизации
Розглянуто найбільш розповсюджені підходи до створення прикладних методів комбінаторної оптимізації. Запропоновано ряд характеристик та критеріїв, за якими здійснюється класифікація наближених алгоритмів. Викладена класифікація є розвитком досліджень у галузі комбінаторної оптимізації та дозволяє ви...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/44402 |
| 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: | Классификация прикладных методов комбинаторной оптимизации / И.В. Сергиенко, Л.Ф. Гуляницкий, С.И. Сиренко // Кибернетика и системный анализ. — 2009. — № 5. — С. 71-83. — Бібліогр.: 74 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-44402 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-444022013-06-02T03:02:55Z Классификация прикладных методов комбинаторной оптимизации Сергиенко, И.В. Гуляницкий, Л.Ф. Сиренко, С.И. Системный анализ Розглянуто найбільш розповсюджені підходи до створення прикладних методів комбінаторної оптимізації. Запропоновано ряд характеристик та критеріїв, за якими здійснюється класифікація наближених алгоритмів. Викладена класифікація є розвитком досліджень у галузі комбінаторної оптимізації та дозволяє виділяти ключові компоненти обчислювальних схем, що використовуються як інструментарій при побудові нових ефективних гібридних метаевристик. This paper reviews mostly used approaches to the development of applied combinatorial optimization methods. A number of characteristics and criteria are proposed that underlie the classification of approximate algorithms. The classification is an elaboration of previous investigations in the field of combinatorial optimization and allows one to determine key components of computational schemes used in constructing efficient hybrid metaheuristics. 2009 Article Классификация прикладных методов комбинаторной оптимизации / И.В. Сергиенко, Л.Ф. Гуляницкий, С.И. Сиренко // Кибернетика и системный анализ. — 2009. — № 5. — С. 71-83. — Бібліогр.: 74 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/44402 519.8 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 |
2009 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/44402 |
| citation_txt |
Классификация прикладных методов комбинаторной оптимизации / И.В. Сергиенко, Л.Ф. Гуляницкий, С.И. Сиренко // Кибернетика и системный анализ. — 2009. — № 5. — С. 71-83. — Бібліогр.: 74 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT sergienkoiv klassifikaciâprikladnyhmetodovkombinatornojoptimizacii AT gulânickijlf klassifikaciâprikladnyhmetodovkombinatornojoptimizacii AT sirenkosi klassifikaciâprikladnyhmetodovkombinatornojoptimizacii |
| first_indexed |
2025-07-04T02:49:43Z |
| last_indexed |
2025-07-04T02:49:43Z |
| _version_ |
1836682978803056640 |
| fulltext |
È.Â. ÑÅÐÃÈÅÍÊÎ, Ë.Ô. ÃÓËßÍÈÖÊÈÉ, Ñ.È. ÑÈÐÅÍÊÎ
ÓÄÊ 519.8 ÊËÀÑÑÈÔÈÊÀÖÈß ÏÐÈÊËÀÄÍÛÕ ÌÅÒÎÄÎÂ
ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, êëàññèôèêàöèÿ ìåòîäîâ, ïðè-
áëèæåííûå àëãîðèòìû, ìåòàýâðèñòèêè, ãèïåðýâðèñòèêè.
ÂÂÅÄÅÍÈÅ
Ðàçâèòèå ìåòîäîâ êîìáèíàòîðíîé îïòèìèçàöèè (ÊÎ) ïîñëå ýòàïà ïåðâè÷íîãî íà-
êîïëåíèÿ çíàíèé èäåò ïóòåì îáîáùåíèÿ è ñèñòåìàòèçàöèè ïîëó÷åííûõ ðå-
çóëüòàòîâ. Îò ðàññìîòðåíèÿ îòäåëüíûõ ìåòîäîâ ÊÎ è àíàëèçà èõ ñâîéñòâ ïåðå-
õîäÿò ê èññëåäîâàíèþ êîíöåïòóàëüíûõ îñíîâàíèé è ìåòîäîëîãèè ïîñòðîåíèÿ àã-
ðåãèðîâàííûõ àëãîðèòìîâ (ìåòàýâðèñòèê, ãèïåðýâðèñòèê), ïóòåé äîñòèæåíèÿ
àäàïòèâíîñòè è ïîâûøåííîé ýôôåêòèâíîñòè ïðè ðåøåíèè êàê êîíêðåòíûõ çàäà÷
ÊÎ, òàê è öåëûõ èõ êëàññîâ.
 ðÿäå ðàáîò ðàññìàòðèâàþòñÿ âîïðîñû êëàññèôèêàöèè àëãîðèòìîâ ÊÎ â öå-
ëîì è îòäåëüíûõ èõ êëàññîâ [1–8]. Â íàñòîÿùåé ñòàòüå ïðåäëàãàåòñÿ îáîáùåíèå è
ðàçâèòèå èçâåñòíûõ â ëèòåðàòóðå ïîäõîäîâ ê êëàññèôèêàöèè. Ââèäó áîëüøîãî êî-
ëè÷åñòâà ïðåäëîæåííûõ ìåòîäîâ è àëãîðèòìîâ åäâà ëè ïðåäñòàâëÿåòñÿ âîçìîæíûì
äëÿ âñåõ ñóùåñòâóþùèõ ïîäõîäîâ ê ðåøåíèþ çàäà÷ ÊÎ óêàçàòü èõ ìåñòî â êëàññè-
ôèêàöèè. Ïîýòîìó â ðàáîòå óïîìèíàþòñÿ íàèáîëåå èçâåñòíûå è øèðîêî èñïîëüçóå-
ìûå ïðèêëàäíûå ìåòîäû, êîòîðûå áîëåå ïîëíî èëëþñòðèðóþò ñîîòâåòñòâóþùèé
êëàññ èëè õàðàêòåðèñòèêó, à òàêæå ìîãóò âûñòóïàòü â êà÷åñòâå òåõíîëîãè÷åñêèõ
ìîäóëåé ïðè ñîçäàíèè àãðåãèðîâàííûõ àëãîðèòìîâ. Îòìåòèì, ÷òî äàííàÿ êëàññèôè-
êàöèÿ, ïðåæäå âñåãî, ïîä÷åðêèâàåò ðàçëè÷èÿ ìåæäó àëãîðèòìàìè, íî ïðè ýòîì íå
ëèøàåò èõ îáùíîñòè.
ÎÏÐÅÄÅËÅÍÈÅ ÇÀÄÀ×È ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Îáúåêòàìè, ðàññìàòðèâàåìûìè â çàäà÷àõ ÊÎ, îáû÷íî ÿâëÿþòñÿ ðàçìåùåíèÿ, ïå-
ðåñòàíîâêè, ïîäìíîæåñòâà, ãðàôû, öåëûå ÷èñëà è äðóãèå ñòðóêòóðû, îáîáùåíèåì
êîòîðûõ ÿâëÿåòñÿ ïîíÿòèå êîìáèíàòîðíîãî îáúåêòà [9]. Ïóñòü çàäàíû
Y m� { , , }1� , Z — íå áîëåå ÷åì ñ÷åòíîå ïðîñòðàíñòâî, êîòîðîå íàçîâåì áàçîâûì,
� — ãîìîìîðôèçì, �:Y Z� , óäîâëåòâîðÿþùèé îãðàíè÷åíèÿì, çàäàííûì íåêîòî-
ðûì ïðåäèêàòîì � .
Îïðåäåëåíèå 1. Ïîä êîìáèíàòîðíûì îáúåêòîì � áóäåì ïîíèìàòü òðèàäó
�� ��� �� �� , à ïîä åãî ðàçìåðíîñòüþ — ìîùíîñòü íóìåðóþùåãî ìíîæåñòâà Y .
Äëÿ îïðåäåëåíèÿ çàäà÷è ÊÎ ïîíàäîáèòñÿ ïîíÿòèå ëîêàëüíî-êîíå÷íîãî ïðî-
ñòðàíñòâà. Ïóñòü X X d� ( , ) — íåêîòîðîå ïðîñòðàíñòâî ñ ìåòðèêîé d. Îáîçíà÷èì
Od
ìåòðè÷åñêóþ îêðåñòíîñòü ðàäèóñà � � � �0: ( ) { | ( , ) }O x y X d x yd .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 71
� È.Â. Ñåðãèåíêî, Ë.Ô. Ãóëÿíèöêèé, Ñ.È. Ñèðåíêî, 2009
Îïðåäåëåíèå 2. Ìåòðè÷åñêîå ïðîñòðàíñòâî X ñ ìåòðèêîé d íàçûâàåòñÿ ëî-
êàëüíî-êîíå÷íûì, åñëè äëÿ ëþáîãî � ( , )0 è x X� âûïîëíÿåòñÿ | ( )|O xd
, ãäå
| |C — ìîùíîñòü ìíîæåñòâà C.
Íåñëîæíî óáåäèòüñÿ, ÷òî ëþáîå êîíå÷íîå ïðîñòðàíñòâî X ÿâëÿåòñÿ ëîêàëü-
íî-êîíå÷íûì ïðè ïðîèçâîëüíîì âûáîðå ìåòðèêè.
Îïðåäåëåíèå 3. Çàäà÷åé ÊÎ íàçûâàåòñÿ ïðîáëåìà íàõîæäåíèÿ òàêîãî
x D X
*
� � , ÷òî
x f x
x D X
* arg min ( )�
� �
, (1)
ãäå X — ëîêàëüíî-êîíå÷íîå ïðîñòðàíñòâî ðåøåíèé çàäà÷è, ýëåìåíòàìè êîòîðîãî
ÿâëÿþòñÿ êîìáèíàòîðíûå îáúåêòû, D X� — ïîäïðîñòðàíñòâî äîïóñòèìûõ ðå-
øåíèé, îïðåäåëÿåìîå çàäàííûì ïðåäèêàòîì �, f X: � R1 — öåëåâàÿ ôóíêöèÿ.
Îòìåòèì, ÷òî â îáùåì ñëó÷àå ïðîñòðàíñòâî X ìîæåò ñîñòîÿòü èç êîìáèíàòîð-
íûõ îáúåêòîâ ðàçíîé ðàçìåðíîñòè.
Îïðåäåëåíèå 4. Ñèñòåìà îêðåñòíîñòåé, îïðåäåëåííàÿ íà ìåòðè÷åñêîì ïðî-
ñòðàíñòâå ( , )X d ðåøåíèé çàäà÷è (1) — òàêîå îòîáðàæåíèå N : | |X X� 2 , êîòîðîå
êàæäîìó ðåøåíèþ x X� ñòàâèò â ñîîòâåòñòâèå íåêîòîðîå ìíîæåñòâî N x( ) òàêîå,
÷òî
�x X | ( )|N x � 1, x N x� ( ) è � � � ( , ): ( ) ( )0 N x O xd .
Ìíîæåñòâî N x( ) íàçûâàåòñÿ îêðåñòíîñòüþ âàðèàíòà ðåøåíèÿ x, à åãî ýëåìåí-
òû íàçûâàþòñÿ ñîñåäíèìè ñ x. Ñèñòåìà îêðåñòíîñòåé N îïðåäåëÿåò òàê íàçûâàåìûé
ãðàô ñîñåäñòâà G X VN N� ( , ), V x y y N xN � �{( , ): ( )}.
Îïðåäåëåíèå 5. Äîïóñòèìîå ðåøåíèå x D� íàçûâàåòñÿ ëîêàëüíûì ìèíèìóìîì
çàäà÷è (1) ïî îòíîøåíèþ ê ñèñòåìå îêðåñòíîñòåé N, åñëè äëÿ ïðîèçâîëüíîãî
y N x� ( ) âûïîëíÿåòñÿ íåðàâåíñòâî f x f y( ) ( )� .
Îïðåäåëåíèå 6. Åñëè îïðåäåëåíà çàäà÷à ÊÎ â ñìûñëå (1) è íåêîòîðàÿ ñèñòåìà
îêðåñòíîñòåé N, òî ëàíäøàôòîì ïîèñêà íàçûâàåòñÿ òðîéêà ( , , )X f N .
Íà ïðàêòèêå ðÿä àëãîðèòìîâ ðàáîòàåò íå â ïðîñòðàíñòâå X , à â íåêîòîðîì åãî
ðàñøèðåíèè. Ìíîãèå àëãîðèòìû èñïîëüçóþò ñïåöèàëüíóþ îöåíî÷íóþ ôóíêöèþ
âìåñòî öåëåâîé äëÿ óïðàâëåíèÿ ïðîöåññîì ïîèñêà. Ýòè äâà ïîíÿòèÿ ôîðìèðóþò
ñïåöèàëüíîå ïðåäñòàâëåíèå çàäà÷è ÊÎ, êîòîðîå ÿâëÿåòñÿ àëãîðèòìî-îðèåíòèðîâàí-
íûì è ââîäèòñÿ äëÿ àäàïòàöèè ïîñòàíîâêè çàäà÷è ê àëãîðèòìó åå ðåøåíèÿ. Ïî-
ñêîëüêó òàêîå ïðåäñòàâëåíèå çàäà÷è ÊÎ òàêæå ìîæíî ðàññìàòðèâàòü êàê îòäåëüíóþ
çàäà÷ó ÊÎ, åñëè íå áóäåò îãîâîðåíî ïðîòèâíîå, äàëåå áóäåì ñ÷èòàòü, ÷òî ðàññìàò-
ðèâàåìûé àëãîðèòì ðåøàåò íåïîñðåäñòâåííî çàäà÷ó ÊÎ â âèäå (1).
ÎÁÙÀß ÊËÀÑÑÈÔÈÊÀÖÈß ÌÅÒÎÄÎÂ ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Ðàññìîòðèì àëãîðèòì ðåøåíèÿ çàäà÷ ÊÎ êàê ïðîöåäóðó, êîòîðàÿ âîçâðàùàåò íà
âûõîäå ëèáî ïîäìíîæåñòâî (âîçìîæíî, ïóñòîå) äîïóñòèìûõ ðåøåíèé, ëèáî ïðè-
çíàê òîãî, ÷òî çàäà÷à íåðàçðåøèìà.
Àëãîðèòìû ÊÎ ìîæíî êëàññèôèöèðîâàòü ïî ìíîãèì õàðàêòåðèñòèêàì. Îäíîé
èç ñàìûõ âàæíûõ ÿâëÿåòñÿ òèï ïîëó÷àåìîãî ðåøåíèÿ. Ïî òèïó ðåøåíèÿ ìîæíî âû-
äåëèòü òî÷íûå, ïðèáëèæåííûå è ýâðèñòè÷åñêèå àëãîðèòìû.
Òî÷íûå àëãîðèòìû çà êîíå÷íîå âðåìÿ ãàðàíòèðîâàííî âîçâðàùàþò îïòèìàëü-
íîå ðåøåíèå èëè äåëàþò âûâîä, ÷òî åãî íå ñóùåñòâóåò, åñëè çàäà÷à íåðàçðåøèìà.
Ýòè àëãîðèòìû ìîæíî ðàçäåëèòü íà äâà êëàññà: îáùèå è ñïåöèàëüíûå ìåòîäû.
Îáùèå ìåòîäû ìîãóò áûòü ïðèìåíåíû ê âåñüìà øèðîêîìó êðóãó çàäà÷. Íàèáîëü-
øåå ðàñïðîñòðàíåíèå ïîëó÷èëè ìåòîä ïîëíîãî ïåðåáîðà, ìåòîä âåòâåé è ãðàíèö,
ìåòîä âåòâåé è ñå÷åíèé, ïîñëåäîâàòåëüíûé àíàëèç è îòñåèâàíèå âàðèàíòîâ, äèíà-
ìè÷åñêîå ïðîãðàììèðîâàíèå [10–13]. Ñïåöèàëüíûå ìåòîäû ñòðîÿòñÿ äëÿ êîíêðåò-
íûõ çàäà÷ ñ ó÷åòîì èõ ñïåöèôèêè, êàê, íàïðèìåð, ìåòîä Áàëàøà («âåíãåðñêèé
ìåòîä») äëÿ ðåøåíèÿ ëèíåéíîé çàäà÷è î íàçíà÷åíèÿõ.
72 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Ïðèáëèæåííûå àëãîðèòìû — ýòî àëãîðèòìû, ãàðàíòèðîâàííî âîçâðàùàþùèå
âàðèàíò ðåøåíèÿ çà êîíå÷íîå âðåìÿ (åñëè îíî ñóùåñòâóåò), è äëÿ êîòîðûõ ìîæåò
áûòü ïîëó÷åíà îöåíêà òî÷íîñòè íàéäåííûõ âàðèàíòîâ ðåøåíèÿ. Îöåíêè òî÷íîñòè
áûâàþò äâóõ òèïîâ: àïðèîðíûå è àïîñòåðèîðíûå. Àïðèîðíàÿ îöåíêà òî÷íîñòè —
ãàðàíòèðîâàííàÿ îöåíêà, çàäàâàåìàÿ äî íà÷àëà ðåøåíèÿ çàäà÷è. Àïîñòåðèîðíûå
îöåíêè âû÷èñëÿþò íåïîñðåäñòâåííî âî âðåìÿ ïðîöåññà ðåøåíèÿ èëè ïîñëå åãî
îêîí÷àíèÿ, ó÷èòûâàÿ ïðè ýòîì è ñàìî ïîëó÷åííîå ðåøåíèå.
Ïîä ýâðèñòè÷åñêèìè àëãîðèòìàìè («ýâðèñòèêàìè») ÷àùå âñåãî ïîíèìàþò àë-
ãîðèòìû, äëÿ êîòîðûõ îòñóòñòâóåò ëèáî íåèçâåñòíà îöåíêà òî÷íîñòè. Ýòî îçíà÷àåò
îòñóòñòâèå ãàðàíòèé òîãî, ÷òî äëÿ êîíêðåòíîé ðåøàåìîé çàäà÷è àëãîðèòì íå âåðíåò
êàê óãîäíî «ïëîõîå» (â ñìûñëå öåëåâîé ôóíêöèè) ðåøåíèå èëè ÷òî îí âåðíåò ðåøå-
íèå âîîáùå. Â òî æå âðåìÿ ýâðèñòèêè êîððåêòíû â òîì ñìûñëå, ÷òî íå âîçâðàùàþò
âàðèàíòû ðåøåíèÿ, êîòîðûå íå ÿâëÿþòñÿ äîïóñòèìûìè ðåøåíèÿìè çàäà÷è. Äëÿ
ìíîãèõ ïðàêòè÷åñêèõ çàäà÷ òàêèå àëãîðèòìû ïîêàçàëè ñâîþ ýôôåêòèâíîñòü, è áî-
ëåå òîãî, íåðåäêî ýâðèñòèêè ìîãóò áûòü åäèíñòâåííûì ñïîñîáîì ïîëó÷èòü
«õîðîøåå» ðåøåíèå çà ïðèåìëåìîå âðåìÿ.
Ïðèáëèæåííûìè àëãîðèòìàìè ÷àñòî íàçûâàþò âñå «íåòî÷íûå» àëãîðèòìû —
êàê àëãîðèòìû ñ îöåíêîé òî÷íîñòè, òàê è ýâðèñòè÷åñêèå àëãîðèòìû (èñïîëüçóåì
ýòî ïîíÿòèå â äàëüíåéøåì). Ââèäó ñëîæíîñòè ìíîãèõ ïðàêòè÷åñêè âàæíûõ çàäà÷
ÊÎ ïðèìåíèìîñòü òî÷íûõ àëãîðèòìîâ îãðàíè÷åíà (íàïðèìåð, çàäà÷àìè íåáîëüøîé
ðàçìåðíîñòè èëè îòäåëüíûõ, ñðàâíèòåëüíî íåáîëüøèõ êëàññîâ) è ìàëîâåðîÿòíî,
÷òî óäàñòñÿ ðàçðàáîòàòü ýôôåêòèâíûå òî÷íûå ìåòîäû, ïðèìåíÿåìûå ê ðåàëüíûì çà-
äà÷àì. Êðîìå òîãî, ñõåìà òî÷íûõ àëãîðèòìîâ ÷àñòî íå ïîçâîëÿåò ðåøàòü ñ èõ ïî-
ìîùüþ íåêîòîðûå òèïû çàäà÷ ÊÎ, òàêèå êàê äèíàìè÷åñêèå çàäà÷è èëè çàäà÷è ñ íå-
îïðåäåëåííîñòÿìè. Ïîýòîìó èìåííî ïðèáëèæåííûå àëãîðèòìû íàõîäÿò âñÿ áîëåå
øèðîêîå ïðèìåíåíèå íà ïðàêòèêå, à èõ êëàññèôèêàöèÿ áóäåò ãëàâíûì ïðåäìåòîì
ðàññìîòðåíèÿ.
Ïî ñóòè, âñå âû÷èñëèòåëüíûå ïîäõîäû ê ðåøåíèþ ñëîæíûõ çàäà÷ ÊÎ ìîãóò
áûòü îïèñàíû êàê ïîèñêîâûå ïðîöåäóðû, èäåÿ êîòîðûõ ñîñòîèò â èòåðàöèîííîì
ïîðîæäåíèè/ãåíåðèðîâàíèè âàðèàíòîâ ðåøåíèé è èõ îöåíèâàíèè. Òàêîé ïîäõîä
ê îïèñàíèþ ìåòîäîâ ðåøåíèÿ çàäà÷ ÊÎ ÿâëÿåòñÿ îáùèì, õîòÿ è íå îòðàæàåò ìíîãèõ
õàðàêòåðèñòèê ñòðóêòóðû, íî â ðàìêàõ äàííîé ðàáîòû åãî áóäåò äîñòàòî÷íî.
Ïðèáëèæåííûå àëãîðèòìû ÷àñòî ñòðîÿòñÿ èñõîäÿ èç êàêèõ-ëèáî ïðàâäîïîäîá-
íûõ èäåé (ýâðèñòèê). Íà ðèñ. 1 óêàçàíû îñíîâíûå ïàðàäèãìû, èñïîëüçóåìûå ïðè
ñîçäàíèè ïðèêëàäíûõ ïðèáëèæåííûõ ìåòîäîâ ÊÎ, è ïðèâåäåíû íàèáîëåå
òèïè÷íûå ïðèìåðû ñîîòâåòñòâóþùèõ ìåòîäîâ.
Ïåðâûå òðè êëàññà èìåþò äëèòåëüíóþ èñòîðèþ ïðèìåíåíèÿ è äîñòàòî÷íî
ïîëíî îïèñàíû â ëèòåðàòóðå [7, 10, 11, 14–17].
Ýâîëþöèîííûå ìåòîäû ÿâëÿþòñÿ øèðîêèì è ðàçíîîáðàçíûì êëàññîì àëãîðèò-
ìîâ, èñïîëüçóþùèõ ïðèíöèïû áèîëîãè÷åñêîé ýâîëþöèè äëÿ ðåøåíèÿ
îïòèìèçàöèîííûõ çàäà÷ [18, 19].
Ðîåâîé èíòåëëåêò â êîíòåêñòå ÊÎ ïðåäñòàâëåí êëàññîì àëãîðèòìîâ, êîòîðûå
ÿâëÿþòñÿ äåöåíòðàëèçîâàííûìè ñèñòåìàìè ïðîñòûõ àãåíòîâ, ëîêàëüíî âçàèìî-
äåéñòâóþùèõ ñî ñðåäîé è ìåæäó ñîáîé. Íåñìîòðÿ íà îòñóòñòâèå öåíòðàëèçîâàííîé
ñòðóêòóðû óïðàâëåíèÿ àãåíòàìè, ëîêàëüíîå âçàèìîäåéñòâèå ìåæäó íèìè ïðèâîäèò
ê ïðîÿâëåíèþ ãëîáàëüíîãî ïîâåäåíèÿ âñåé ñèñòåìû â öåëîì [20].
 ìåòîäàõ ñêàíèðîâàíèÿ ïðîñòðàíñòâà, ïðèíàäëåæàùèõ ê ÷èñëó ïîïóëÿöèîí-
íûõ àëãîðèòìîâ, íà êàæäîé èòåðàöèè ïðîèñõîäèò ôîðìèðîâàíèå íàïðàâëåíèÿ ïîèñ-
êà â ïðîñòðàíñòâå ðåøåíèé íà îñíîâå íåñêîëüêèõ èìåþùèõñÿ âàðèàíòîâ [7–9].
Äîâîëüíî ðàñïðîñòðàíåííûì ïîäõîäîì ê ñîçäàíèþ ïðèáëèæåííûõ àëãîðèòìîâ
ÊÎ ÿâëÿåòñÿ ïîñòðîåíèå èõ âû÷èñëèòåëüíîé ñõåìû íà îñíîâå ëèáî èçâåñòíûõ òî÷-
íûõ ìåòîäîâ, ëèáî ìàêñèìàëüíîãî ó÷åòà ñïåöèôèêè êîíêðåòíîé çàäà÷è, ÷òî ïîçâî-
ëÿåò ïîâûñèòü ýôôåêòèâíîñòü, õîòÿ è ïðèâîäèò ê ñóæåíèþ ïðèìåíèìîñòè òàêèõ
àëãîðèòìîâ [10–12].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 73
Ïðåäëàãàåòñÿ êëàññèôèöèðîâàòü ïðèáëèæåííûå ìåòîäû ÊÎ ïî òàêèì õàðàêòåðèñ-
òèêàì: ïðèíöèï ïðèíÿòèÿ ðåøåíèé; ñëîæíîñòü ñòðóêòóðû; òèï èñïîëüçóåìûõ ïðî-
ñòðàíñòâ; òèï ôîðìèðóåìîé òðàåêòîðèè; âëèÿíèå íà ëàíäøàôò ïîèñêà; èñïîëüçîâàíèå
ïàìÿòè; íàëè÷èå àäàïòàöèè/îáó÷åíèÿ; íàëè÷èå ñïåöèàëüíîé ìîäåëè çàäà÷è.
ÏÐÈÍÖÈÏ ÏÐÈÍßÒÈß ÐÅØÅÍÈÉ
 ïðèáëèæåííûõ ìåòîäàõ, ïðåæäå âñåãî, áóäåì ðàçëè÷àòü ïî íàëè÷èþ ðàíäîìèçà-
öèè äâà ïðèíöèïà ïðèíÿòèÿ ðåøåíèé — äåòåðìèíèðîâàííûé è ñòîõàñòè÷åñêèé.
Ïðèìåðîì äåòåðìèíèðîâàííîãî ìåòîäà ÿâëÿåòñÿ ïðîñòîé ëîêàëüíûé ïîèñê — àëãî-
ðèòì, êîòîðûé íà÷èíàÿ ñ íåêîòîðîãî íà÷àëüíîãî ðåøåíèÿ èòåðàöèîííî ïûòàåòñÿ åãî
çàìåíèòü ëó÷øèì (â ñìûñëå öåëåâîé ôóíêöèè) èç îêðåñòíîñòè [10, 11]. Îäèí èç íà-
èáîëåå èçâåñòíûõ ñòîõàñòè÷åñêèõ àëãîðèòìîâ — àëãîðèòì èìèòàöèîííîãî îòæèãà
[29, 30]. Ýòîò ïîäõîä ÿâëÿåòñÿ ðàçâèòèåì ëîêàëüíîãî ïîèñêà — ðàçðåøàåòñÿ ïðèíÿ-
òèå â êà÷åñòâå òåêóùåãî ðåøåíèÿ íå òîëüêî ëó÷øåãî èç îêðåñòíîñòè, íî è õóäøåãî
ïî çíà÷åíèþ öåëåâîé ôóíêöèè ðåøåíèÿ. Âûáîð ðåøåíèÿ îïðåäåëÿåòñÿ âåðîÿòíîñ-
òíûì ìåõàíèçìîì íà îñíîâå çíà÷åíèé öåëåâîé ôóíêöèè.
 íàñòîÿùåå âðåìÿ çíà÷èòåëüíàÿ ÷àñòü ðàçðàáîòàííûõ è óñïåøíî ïðèìåíÿåìûõ íà
ïðàêòèêå ïðèáëèæåííûõ ìåòîäîâ ÊÎ ïðèíàäëåæàò èìåííî ê ñòîõàñòè÷åñêèì [7, 14, 15, 17].
Òàêèå ìåòîäû ïîêàçàëè ñâîþ ýôôåêòèâíîñòü ïðè ðåøåíèè ñëîæíûõ ïðèêëàäíûõ çàäà÷ ÊÎ.
74 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Ãåíåòè÷åñêèå àëãîðèòìû [39, 18, 19]
Ìåìåòè÷åñêèå àëãîðèòìû [40, 41]
Èììóííûå àëãîðèòìû [42, 43]
Ðàññåÿííûé ïîèñê [44]
Àëãîðèòìû âû÷èñëåíèÿ îöåíîê ðàñïðåäåëåíèé
[45, 46]
Ïîñëåäîâàòåëüíûå
àëãîðèòìû
Ñòîõàñòè÷åñêèé
ëîêàëüíûé ïîèñê
Ýâîëþöèîííûå
àëãîðèòìû
Ðîåâûå
àëãîðèòìû
Äåòåðìèíèðîâàííûé
ëîêàëüíûé ïîèñê
Ñïåöèàëüíûå
ìåòîäû
Êîíñòðóêòèâíûå àëãîðèòìû (â ò.÷. «æàäíûå»)
[10, 21]
Ñòàíäàðòíûé ëîêàëüíûé ïîèñê [10, 11, 22, 23]
Ïîèñê â èçìåíÿþùèõñÿ îêðåñòíîñòÿõ [24–26]
Óïðàâëÿåìûé ëîêàëüíûé ïîèñê [27]
Ïîèñê ïåðåìåííîé ãëóáèíû [7, 28]
Àëãîðèòì èìèòàöèîííîãî îòæèãà [29, 30]
G-àëãîðèòì [31]
Ïîâòîðÿåìûé ëîêàëüíûé ïîèñê [32]
Òàáó-ïîèñê [33, 34]
Àëãîðèòì ãëîáàëüíîãî ðàâíîâåñíîãî ïîèñêà [17]
Àëãîðèòì êâàíòîâîãî îòæèãà [35]
GRASP [36, 37]
Ìåòîä ñóæàþùèõñÿ îêðåñòíîñòåé [38]
Îïòèìèçàöèÿ ìóðàâüèíûìè êîëîíèÿìè [47, 48]
Îïòèìèçàöèÿ ðîåì ÷àñòèö [49, 50]
Îïòèìèçàöèÿ ï÷åëèíûìè êîëîíèÿìè [51]
Ñòîõàñòè÷åñêèé äèôôóçíûé ïîèñê [52]
Ìåòîä äåôîðìèðîâàííûõ ìíîãîãðàííèêîâ [53]
Í-ìåòîä [9]
Àëãîðèòìû, èñïîëüçóþùèå ñòðàòåãèþ
ïåðåêîìïîíîâêè ìàðøðóòîâ [44]
Àëãîðèòìû íà áàçå òî÷íûõ ìåòîäîâ (ìåòîäà âåòâåé
è ãðàíèö èëè ïîñëåäîâàòåëüíîãî àíàëèçà è
îòñåèâàíèÿ âàðèàíòîâ)
Ìåòîäû
ñêàíèðîâàíèÿ
Ï
ð
è
á
ë
è
æ
å
í
í
û
å
à
ë
ã
î
ð
è
ò
ì
û
Ê
Î
Ðèñ. 1. Êëàññèôèêàöèÿ àëãîðèòìîâ ÊÎ ïî èñïîëüçóåìîé ïàðàäèãìå
ÑËÎÆÍÎÑÒÜ ÑÒÐÓÊÒÓÐÛ
Ïî ñëîæíîñòè ñòðóêòóðû áóäåì ðàçëè÷àòü ïðîñòûå àëãîðèòìû, ãèáðèäíûå àëãî-
ðèòìû, ìåòàýâðèñòèêè, ãèáðèäíûå ìåòàýâðèñòèêè è ãèïåðýâðèñòêè. Êëàññèôèêàöèÿ
ïî ñòðóêòóðå âåñüìà âàæíà, íî, ïîñêîëüêó, íåñìîòðÿ íà øèðîêîå óïîòðåáëåíèå ïî-
íÿòèé ýâðèñòèêè, ìåòàýâðèñòèêè è ãèïåðýâðèñòèêè, îòñóòñòâóþò èõ îáùåïðèíÿòûå
ôîðìàëüíûå îïðåäåëåíèÿ, çàòðóäíèòåëüíî ÷åòêî ðàçãðàíè÷èòü àëãîðèòìû ñîãëàñíî
ýòîé õàðàêòåðèñòèêå. Íàïðèìåð, àëãîðèòì èìèòàöèîííîãî îòæèãà ðàçíûå àâòîðû
îòíîñÿò êàê ê ìåòàýâðèñòèêàì, òàê è ê ïðîñòûì àëãîðèòìàì, ó÷èòûâàÿ òî, ÷òî åãî
îòëè÷èå îò ëîêàëüíîãî ïîèñêà ÿâëÿåòñÿ íåçíà÷èòåëüíûì, äàæå ïî ñðàâíåíèþ ñ òà-
êîé «ïðîñòîé» ìåòàýâðèñòè÷åñêîé êîíöåïöèåé, êàê ïîâòîðÿåìûé ëîêàëüíûé ïî-
èñê [32]. Òåðìèí «ìåòàýâðèñòèêà» ââåäåí â ðàáîòå [33], è óïðîùåííî ìåòàýâðèñ-
òè÷åñêèå ìåòîäû ìîæíî ïîíèìàòü êàê îáùóþ òåõíèêó èëè ïîäõîä, êîòîðûé èñ-
ïîëüçóåòñÿ äëÿ óïðàâëåíèÿ âñòðîåííûìè ïðîáëåìíî-çàâèñèìûìè ïðîöåäóðàìè
(ìåòîäàìè) ñ öåëüþ ïîâûñèòü èõ ýôôåêòèâíîñòü èëè ðîáàñòíîñòü [7]. Òàêèå ïðî-
öåäóðû ÷àñòî ÿâëÿþòñÿ îòäåëüíûìè àëãîðèòìàìè ðåøåíèÿ òîé æå çàäà÷è, ÷òî
è ìåòîä â öåëîì. Ìåòàýâðèñòè÷åêèå ìåòîäû îïèñûâàþòñÿ êàê îáùèå ïîäõîäû, êî-
òîðûå êîíêðåòèçàöèåé ïðîáëåìíî-çàâèñèìûõ êîìïîíåíòîâ ìîãóò áûòü àäàïòèðîâà-
íû ê êîíêðåòíîé çàäà÷å èëè ïîäêëàññó çàäà÷.
Ïîä ãèáðèäíûìè àëãîðèòìàìè ïîíèìàþò òàêîå îáúåäèíåíèå ïðîñòûõ àëãîðèò-
ìîâ, êîòîðîå åùå íå ïîðîæäàåò ìåòàýâðèñòè÷íûé àëãîðèòì. Íàïðèìåð, ýòî ìîæåò
áûòü ïðîñòîå ïîñëåäîâàòåëüíîå èëè ïàðàëëåëüíîå âûïîëíåíèå íåñêîëüêèõ àëãîðèòìîâ
[54, 55]. Íà ïðàêòèêå ïðîñòûå (êàê è ãèáðèäíûå) àëãîðèòìû èñïîëüçóþòñÿ âñå ðåæå,
ïîñêîëüêó ðàçâèòèå ìåòàýâðèñòè÷åñêèõ ïîäõîäîâ ïîçâîëÿåò ïîëó÷àòü ëó÷øèå ðåçóëü-
òàòû, à òåìïû ðîñòà ïðîèçâîäèòåëüíîñòè âû÷èñëèòåëüíûõ ñèñòåì äàþò âîçìîæíîñòü
ïðèìåíÿòü âñå áîëåå ñëîæíûå àëãîðèòìû ê çàäà÷àì ïîâûøåííîé ðàçìåðíîñòè. Èñêëþ-
÷åíèå ñîñòàâëÿþò ñëó÷àè, êîãäà óäàåòñÿ ðàçðàáîòàòü óäà÷íûé ñïåöèàëèçèðîâàííûé àë-
ãîðèòì äëÿ îòäåëüíîé çàäà÷è èëè óçêîãî êëàññà çàäà÷ (ýôôåêòèâíî ó÷åñòü ïðè ðàçðà-
áîòêå àëãîðèòìà îñîáåííîñòè êîíêðåòíîé çàäà÷è), à òàêæå àëãîðèòìû äëÿ çàäà÷ ïîâû-
øåííîé ðàçìåðíîñòè èëè çàäà÷ ñ òðóäîåìêèì âû÷èñëåíèåì öåëåâîé ôóíêöèè.
Ãèáðèäíûìè ìåòàýâðèñòèêàìè áóäåì íàçûâàòü ïðèáëèæåííûå àëãîðèòìû ÊÎ,
êîòîðûå êîìáèíèðóþò â ñåáå êîìïîíåíòû èç äâóõ è áîëåå îòäåëüíûõ ìåòàýâðèñ-
òèê, òî÷íûõ ìåòîäîâ, ñïåöèàëèçèðîâàííûõ àëãîðèòìîâ è ò.ä. Ê ãèáðèäíûì ìåòàýâ-
ðèñòèêàì òàêæå îòíåñåì ìíîãîàãåíòíûå ñèñòåìû, â êîòîðûõ àãåíòû ïðåäñòàâëÿþò
îòäåëüíûå àëãîðèòìû (íàïðèìåð, ìåòàýâðèñòèêè, òî÷íûå èëè ñïåöèàëèçèðîâàííûå
àëãîðèòìû), âçàèìîäåéñòâóþùèå ìåæäó ñîáîé. Êëàññèôèêàöèÿ ãèáðèäíûõ ìåòàýâ-
ðèñòèê ïðåäëîæåíà è äåòàëüíî ðàññìîòðåíà â ðàáîòå [8]. Ïî àíàëîãèè ñ ïîñëåäíåé
âîçìîæíî êëàññèôèöèðîâàòü ãèáðèäíûå àëãîðèòìû ïî ñòåïåíè ãèáðèäèçàöèè,
ïîðÿäêó âûïîëíåíèÿ è ñòðàòåãèè óïðàâëåíèÿ.
Ãèïåðýâðèñòèêà — ìåòîä, àâòîìàòèçèðóþùèé ïðîöåññ âûáîðà, êîìáèíèðîâà-
íèÿ, ãåíåðèðîâàíèÿ èëè àäàïòàöèè ðÿäà ïðîñòûõ àëãîðèòìîâ (ýâðèñòèê) èëè èõ
êîìïîíåíòîâ ñ öåëüþ ýôôåêòèâíîãî ðåøåíèÿ çàäà÷è. Óïðîùåííî ïîä ãèïåðýâðèñ-
òèêîé ìîæíî ïîíèìàòü (ìåòà-)ýâðèñòèêè äëÿ âûáîðà/êîíñòðóèðîâàíèÿ (ìåòà-)ýâ-
ðèñòèê [56]. Îäíà èç öåëåé ñîçäàíèÿ ãèïåðýâðèñòèê — ðàçðàáîòêà îïòèìèçàöèîí-
íûõ ñèñòåì, ñïîñîáíûõ ðåøàòü êëàññû ðàçíûõ çàäà÷, à íå òîëüêî îòäåëüíûå çàäà÷è.
Äåòàëüíî ãèïåðýâðèñòèêè ðàññìàòðèâàþòñÿ, â ÷àñòíîñòè, â [56, 57].
ÒÈÏ ÈÑÏÎËÜÇÓÅÌÛÕ ÏÐÎÑÒÐÀÍÑÒÂ
Ïî òàêîìó êðèòåðèþ, ïðåæäå âñåãî, âûäåëèì êëàññ ïîñëåäîâàòåëüíûõ, èëè
êîíñòðóêòèâíûõ àëãîðèòìîâ. Èõ ñóòü ñîñòîèò â ïîñëåäîâàòåëüíîì ïîñòðîåíèè
ðåøåíèÿ èç îòäåëüíûõ ÷àñòåé ïî îïðåäåëåííûì ïðàâèëàì. Ýòè àëãîðèòìû ðàáî-
òàþò â íåêîòîðîì ðàñøèðåííîì ïðîñòðàíñòâå S X� . Âî ìíîãèõ ñëó÷àÿõ òàêîå
ïðîñòðàíñòâî ìîæíî ïðåäñòàâèòü â òåðìèíàõ îïðåäåëåíèé 1 è 3 â âèäå
S X Z Y Z Y Ys s s
s s� � � � � �{ ( , , ): ( : )}� � �� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 75
Ïðîñòåéøèì ïðèìåðîì ïîñëåäîâàòåëüíîãî àëãîðèòìà ÿâëÿåòñÿ ýâðèñòèêà, íà-
çûâàåìàÿ «æàäíîé», ðåàëèçàöèÿ êîòîðîé äëÿ çàäà÷è êîììèâîÿæåðà èçâåñòíà êàê
«èäè â áëèæíèé (ãîðîä)» [7, 21].
Äðóãîé âàæíûé êëàññ àëãîðèòìîâ — èòåðàöèîííûå. Òàêèå àëãîðèòìû ðàáîòà-
þò â ïðîñòðàíñòâå ðåøåíèé èñõîäíîé çàäà÷è. Èòåðàöèîííûå ìåòîäû ðàçäåëÿþòñÿ
ïî ÷èñëó âàðèàíòîâ ðåøåíèé, êîòîðûìè àëãîðèòì îäíîâðåìåííî îïåðèðóåò [1]
(ãåíåðèðóåò è îöåíèâàåò), íà äâà êëàññà: â ñëó÷àå îäíîýëåìåíòíîãî ìíîæåñòâà àëãî-
ðèòìû íàçûâàþò îäíîòî÷å÷íûìè, à â ñëó÷àå, êîãäà ìíîæåñòâî òåêóùèõ âàðèàíòîâ
ðåøåíèé ñîäåðæèò áîëüøå îäíîãî ýëåìåíòà, — ïîïóëÿöèîííûìè. Îäíîòî÷å÷íûå
àëãîðèòìû ÷àñòî íàçûâàþò òðàåêòîðíûìè, ïîñêîëüêó ïðîöåññ èõ ðàáîòû ìîæíî
ïðåäñòàâèòü â âèäå íåïðåðûâíîé òðàåêòîðèè (ïóòè) íà ãðàôå ñîñåäñòâà (ïîíÿòèå
òðàåêòîðíîé íåïðåðûâíîñòè ðàññìàòðèâàåòñÿ íèæå). Àëãîðèòìû ñòîõàñòè÷åñêîãî
ëîêàëüíîãî ïîèñêà, òàêèå êàê, íàïðèìåð, èìèòàöèîííûé îòæèã, óïðàâëÿåìûé ëî-
êàëüíûé ïîèñê [27] è GRASP [37], ÿâëÿþòñÿ îäíîòî÷å÷íûìè. Íàçâàíèå «ïîïóëÿöè-
îííûå àëãîðèòìû» ââåäåíî ïî àíàëîãèè ñ òåðìèíîëîãèåé, èñïîëüçóåìîé â ýâîëþ-
öèîííûõ ìåòîäàõ. Ýâîëþöèîííûå ìåòîäû, òàêèå êàê ãåíåòè÷åñêèå àëãîðèòìû [39],
áûëè îäíèìè èç ïåðâûõ, îïåðèðîâàâøèõ ìíîæåñòâîì âàðèàíòîâ ðåøåíèé îäíîâðå-
ìåííî. Ê ÷èñëó ðàííèõ ïîïóëÿöèîííûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷ ÊÎ îòíîñÿòñÿ è
ôðîíòàëüíûå àëãîðèòìû [58].
Êîíñòðóêòèâíûå ìåòîäû îáû÷íî ÿâëÿþòñÿ íàèáîëåå áûñòðûìè ìåòîäàìè ðå-
øåíèÿ çàäà÷ ÊÎ, íî, â îáùåì ñëó÷àå, ïðîèãðûâàþò èòåðàöèîííûì ìåòîäàì â «êà-
÷åñòâå» ðåøåíèé. Íà ïðàêòèêå êîíñòðóêòèâíûå àëãîðèòìû ÷àùå âñåãî èñïîëüçóþò-
ñÿ ëèáî äëÿ çàäà÷ ïîâûøåííîé ðàçìåðíîñòè èëè çàäà÷ ñ çàòðàòíûì âû÷èñëåíèåì
öåëåâîé ôóíêöèè, ëèáî äëÿ ãåíåðèðîâàíèÿ íà÷àëüíûõ ðåøåíèé äëÿ äðóãèõ ìåòî-
äîâ. Èíîãäà îíè âñòðîåíû â ìåòîä áîëåå ñëîæíûì îáðàçîì. Íàïðèìåð, â îïòè-
ìèçàöèè ìóðàâüèíûìè êîëîíèÿìè [48] êîíñòðóêòèâíûé áëîê — äåÿòåëüíîñòü
èñêóññòâåííûõ ìóðàâüåâ — èãðàåò êëþ÷åâóþ ðîëü.
ÒÈÏ ÔÎÐÌÈÐÓÅÌÎÉ ÒÐÀÅÊÒÎÐÈÈ
Âàæíûì îòëè÷èåì ìåæäó ðàçíûìè èòåðàöèîííûìè ìåòîäàìè ÿâëÿåòñÿ òî, ôîðìèðó-
þò ëè îíè îäíó òðàåêòîðèþ ïîèñêà, ÷òî îòâå÷àåò «íåïðåðûâíûì» ïåðåõîäàì íà
ãðàôå ñîñåäñòâà, èëè îñóùåñòâëÿþò áîëüøèå «ïðûæêè» íà ýòîì ãðàôå [3]. Ïðåäëà-
ãàåòñÿ ñëåäóþùåå ôîðìàëüíîå îïðåäåëåíèå òðàåêòîðíî-íåïðåðûâíîãî ìåòîäà.
Îïðåäåëåíèå 7. Ïóñòü äàíà ñîâîêóïíîñòü ñèñòåì îêðåñòíîñòåé { , , }N N L1 � è
àëãîðèòì, îïåðèðóþùèé íà êàæäîé èòåðàöèè i ìíîæåñòâîì âàðèàíòîâ ðåøåíèé X i .
Àëãîðèòì íàçûâàåòñÿ òðàåêòîðíî-íåïðåðûâíûì îòíîñèòåëüíî ñèñòåì îêðåñòíîñòåé
{ , , }N N L1 � , åñëè äëÿ âñåõ i � 2 âûïîëíÿåòñÿ
X N xi j i
x Xj
L
i i
� �
�� � �
( )1
1 1 1
�� . (2)
Åñëè ìíîæåñòâî X i ñîñòîèò èç îäíîãî ýëåìåíòà xi (íàïðèìåð, àëãîðèòì
ÿâëÿåòñÿ îäíîòî÷å÷íûì), òî óñëîâèå (2) ýêâèâàëåíòíî óñëîâèþ � �N Ni { ,1 �
� , }: ( )N x N xL i
i
i� �1 .
Îïðåäåëåíèå 8. Àëãîðèòìû, íå óäîâëåòâîðÿþùèå óñëîâèþ (2), íàçûâàþòñÿ
òðàåêòîðíî-ðàçðûâíûìè îòíîñèòåëüíî ñèñòåì îêðåñòíîñòåé { , , }N N L1 � .
Òðàåêòîðíî-íåïðåðûâíîñòü àëãîðèòìà îòíîñèòåëüíî ñèñòåì îêðåñòíîñòåé
{ , , }N N L1 � îçíà÷àåò, ÷òî äëÿ êàæäîãî ñãåíåðèðîâàííîãî àëãîðèòìîì ðåøåíèÿ
x X i� ñóùåñòâóåò ïóòü â àãðåãèðîâàííîì ãðàôå ñîñåäñòâà GN N L1 , ,� �
�
�
( , )
{ , , }
X VN
i L
i
1 �
� , êîòîðûé ñîåäèíÿåò íåêîòîðîå íà÷àëüíîå ðåøåíèå è x.  ñëó÷àå
îäíîòî÷å÷íîãî òðàåêòîðíî-íåïðåðûâíîãî ìåòîäà ïðîöåññ ïîèñêà ÿâëÿåòñÿ ïîñòðîå-
íèåì òðàåêòîðèè (ïóòè) íà ñîîòâåòñòâóþùåì àãðåãèðîâàííîì ãðàôå ñîñåäñòâà.
76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Èìèòàöèîííûé îòæèã è òàáó-ïîèñê [34] — òèïè÷íûå ïðèìåðû òðàåêòîðíî-íåïðå-
ðûâíûõ ìåòîäîâ. Àëãîðèòìû, îñóùåñòâëÿþùèå áîëåå ñëîæíûå ïåðåõîäû, íî êîòîðûå
ïðåäñòàâèìû â âèäå áîëåå ïðîñòûõ øàãîâ, òàêæå ìîæíî èíòåðïðåòèðîâàòü êàê òðàåê-
òîðíî-íåïðåðûâíûå [1]. Ê òàêèì àëãîðèòìàì îòíîñÿòñÿ, íàïðèìåð, àëãîðèòìû ìåòîäà
ïîèñêà ïåðåìåííîé ãëóáèíû [7], â ÷àñòíîñòè àëãîðèòì Ëèíà–Êåðíèãàíà [28], èëè àëãî-
ðèòìû, êîòîðûå áàçèðóþòñÿ íà «âûáðàñûâàíèè öåïåé» (ejection chains) [59].
Áîëüøèíñòâî ïîïóëÿöèîííûõ àëãîðèòìîâ ÿâëÿþòñÿ òðàåêòîðíî-ðàçðûâíûìè îòíî-
ñèòåëüíî ëþáîé îäíîé ôèêñèðîâàííîé ñèñòåìû îêðåñòíîñòåé. Ñðåäè èñêëþ÷åíèé —
ôðîíòàëüíûé àëãîðèòì. Â ìîäèôèêàöèè ýòîãî àëãîðèòìà, êîòîðàÿ áàçèðóåòñÿ íà ëîêàëü-
íîì ïîèñêå, íà êàæäîé èòåðàöèè îñóùåñòâëÿþòñÿ ïàðàëëåëüíûå ëîêàëüíûå óëó÷øàþ-
ùèå øàãè îòíîñèòåëüíî íåêîòîðîé íàïåðåä çàäàííîé ñèñòåìû îêðåñòíîñòåé [58].
Ïîíÿòèå òðàåêòîðíî-íåïðåðûâíîñòè àëãîðèòìà òàêæå ñâÿçàíî ñ êîëè÷åñòâîì
ñèñòåì îêðåñòíîñòåé, êîòîðûå èñïîëüçóþòñÿ â ìåòîäå: àëãîðèòìû, èñïîëüçóþùèå
áîëüøå îäíîé ñèñòåìû îêðåñòíîñòåé, áóäóò òðàåêòîðíî-ðàçðûâíûìè îòíîñèòåëüíî
ëþáîé îäíîé ñèñòåìû îêðåñòíîñòåé.
ÂËÈßÍÈÅ ÍÀ ËÀÍÄØÀÔÒ ÏÎÈÑÊÀ
Âûäåëèì â îòäåëüíûé êëàññ ìåòîäû ÊÎ, êîòîðûå èçìåíÿþò ëàíäøàôò ïîèñêà
â ïðîöåññå ñâîåé ðàáîòû. Âîçìîæíû ñëåäóþùèå òèïû èçìåíåíèé: ïðîñòðàíñòâà
ïîèñêà, öåëåâîé/îöåíî÷íîé ôóíêöèè è ñèñòåìû îêðåñòíîñòåé. Ðàññìîòðèì êàæ-
äûé èç íèõ â îòäåëüíîñòè.
Èçìåíåíèå ïðîñòðàíñòâà ïîèñêà. Ïîä èçìåíåíèåì ïðîñòðàíñòâà ïîèñêà ïî-
íèìàåòñÿ âêëþ÷åíèå/èñêëþ÷åíèå ýëåìåíòîâ â/èç íåãî.  òàáó-ïîèñêå çàïðåùåíî
âîçâðàùåíèå ê íåäàâíî ðàññìîòðåííûì âàðèàíòàì ðåøåíèÿ, ÷òî ñîîòâåòñòâóåò èõ
âðåìåííîìó èñêëþ÷åíèþ èç ïðîñòðàíñòâà ïîèñêà. Áîëüøèíñòâî ìåòîäîâ ÊÎ íå èç-
ìåíÿþò ïðîñòðàíñòâî ïîèñêà.
Èçìåíåíèå öåëåâîé/îöåíî÷íîé ôóíêöèè. Íåêîòîðûå àëãîðèòìû ìîäèôèöè-
ðóþò îöåíèâàíèå îòäåëüíûõ ñîñòîÿíèé ïðîöåññà ïîèñêà âî âðåìÿ âûïîëíåíèÿ àë-
ãîðèòìà [1]. Îäíèì èç ïðèìåðîâ ÿâëÿåòñÿ ìåòîä «âûëàìûâàíèÿ» (breakout) [60], áà-
çîâîé èäååé êîòîðîãî ÿâëÿåòñÿ ââåäåíèå øòðàôîâ íà âêëþ÷åíèå îòäåëüíûõ êîìïî-
íåíòîâ â ðåøåíèå, èçìåíÿþùèõ çíà÷åíèå öåëåâîé ôóíêöèè.  êà÷åñòâå ðàçâèòèÿ
ýòîãî ïîäõîäà áûë ïðåäëîæåí óïðàâëÿåìûé ëîêàëüíûé ïîèñê [27].
Òàáó-ïîèñê ìîæíî èíòåðïðåòèðîâàòü êàê òàêîé, êîòîðûé èñïîëüçóåò äèíàìè÷åñ-
êóþ öåëåâóþ ôóíêöèþ: â àëãîðèòìå íåêîòîðûå òî÷êè ïðîñòðàíñòâà ïîèñêà çàïðåùà-
þòñÿ, ÷òî ðàâíîöåííî ïðèñâîåíèþ áåñêîíå÷íî áîëüøèõ çíà÷åíèé îöåíî÷íîé ôóíê-
öèè. Íî òàêàÿ èíòåðïðåòàöèÿ îòëè÷àåòñÿ îò áàçîâîé àëãîðèòìè÷åñêîé èäåè ìåòîäà.
Èçìåíåíèå ñèñòåìû îêðåñòíîñòåé. Ìíîãèå èç ïðèáëèæåííûõ àëãîðèòìîâ ÊÎ
èñïîëüçóþò â ïðîöåññå ïîèñêà îäíó ñèñòåìó îêðåñòíîñòåé. Ýòî, íàïðèìåð, òàêèå
àëãîðèòìû, êàê èìèòàöèîííûé îòæèã, òàáó-ïîèñê, G-àëãîðèòìû [31]. Â ïîâòîðÿå-
ìîì ëîêàëüíîì ïîèñêå èñïîëüçóåòñÿ ïî êðàéíåé ìåðå äâå ñèñòåìû îêðåñòíîñòåé:
âíà÷àëå îñóùåñòâëÿåòñÿ ëîêàëüíûé ïîèñê äî äîñòèæåíèÿ ëîêàëüíîãî ìèíèìóìà,
ïîñëå ýòîãî — âîçìóùåíèå íàéäåííîãî ëîêàëüíîãî ìèíèìóìà. Ôàêòè÷åñêè, âîçìó-
ùåíèå ìîæåò ðàññìàòðèâàòüñÿ êàê øàã â äðóãîé ñèñòåìå îêðåñòíîñòåé, îòëè÷íîé îò
òîé, ïî îòíîøåíèþ ê êîòîðîé áûë íàéäåí ëîêàëüíûé ìèíèìóì. Ýòè ñîîáðàæåíèÿ,
â ÷àñòíîñòè, ðàçâèòû íåçàâèñèìî â ìåòîäàõ ïîèñêà â ïóëüñèðóþùèõ îêðåñòíîñòÿõ
[24] è ïîèñêà â èçìåíÿåìûõ îêðåñòíîñòÿõ [25, 26] — â ýòèõ ïîäõîäàõ èñïîëüçóåìûå
îêðåñòíîñòè ñèñòåìàòè÷åñêè èçìåíÿþòñÿ â ïðåäåëàõ çàâåäîìî çàäàííîãî èõ ïåðå÷íÿ.
ÈÑÏÎËÜÇÎÂÀÍÈÅ ÏÀÌßÒÈ
Î÷åíü âàæíîé õàðàêòåðèñòèêîé, ïî êîòîðîé áóäåì ðàçëè÷àòü ïðèáëèæåííûå àë-
ãîðèòìû ÊÎ, ÿâëÿåòñÿ èñïîëüçîâàíèå ïàìÿòè. Ïàìÿòü — ýòî íàáîð ñïåöèàëüíûõ
ïåðåìåííûõ, â êîòîðûõ îòîáðàæàåòñÿ îïûò (èíôîðìàöèÿ), íàêîïëåííûé â ïðî-
öåññå ïîèñêà (ðàáîòû àëãîðèòìà). Â ìåòîäàõ ÊÎ èìååòñÿ íåñêîëüêî ôóíêöèé ïà-
ìÿòè. Âî-ïåðâûõ, ïàìÿòü ìîæåò èñïîëüçîâàòüñÿ äëÿ õðàíåíèÿ èíôîðìàöèè, êîòî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 77
ðàÿ áóäåò èñïîëüçîâàíà íà âûõîäå àëãîðèòìà (íàïðèìåð, íàèëó÷øåå íàéäåííîå
ðåøåíèå). Âî-âòîðûõ, ïàìÿòü ìîæåò èñïîëüçîâàòüñÿ äëÿ óïðàâëåíèÿ ïðîöåññîì
ïîèñêà. Ýòîò òèï ïàìÿòè ìîæåò áûòü êðàòêîâðåìåííûì èëè äîëãîâðåìåííûì.
Êðàòêîâðåìåííàÿ ïàìÿòü ïîäðàçóìåâàåò çàïîìèíàíèå îïðåäåëåííîãî êîëè÷åñòâà
ïîñëåäíèõ ñãåíåðèðîâàííûõ ðåøåíèé, ÷àñòåé ðåøåíèé è ïðèíÿòûõ ðåøåíèé. Çà-
ïîìèíàíèå â òàáó-ïîèñêå ïîñëåäíèõ ñãåíåðèðîâàííûõ ðåøåíèé ÿâëÿåòñÿ ïðèìå-
ðîì êðàòêîâðåìåííîé ïàìÿòè. Äîëãîâðåìåííàÿ ïàìÿòü — íàáîð ñïåöèàëüíûõ äî-
ïîëíèòåëüíûõ ïåðåìåííûõ, â êîòîðûõ çàïîìèíàåòñÿ èíôîðìàöèÿ îáî âñåì îñó-
ùåñòâëåííîì ïðîöåññå ïîèñêà. Âåëè÷èíû øòðàôîâ â àëãîðèòìå óïðàâëÿåìîãî
ëîêàëüíîãî ïîèñêà ÿâëÿþòñÿ ïðèìåðîì äîëãîâðåìåííîé ïàìÿòè. Ôóíêöèÿ óïðàâ-
ëåíèÿ ïîèñêîì òåñíî ñâÿçàíà ñ âëèÿíèåì íà ëàíäøàôò ïîèñêà: àëãîðèòìû ñ ýòîé
ôóíêöèåé ïàìÿòè èçìåíÿþò ëàíäøàôò ïîèñêà. Ïîñëåäíÿÿ è íàèáîëåå âàæíàÿ
ôóíêöèÿ ïàìÿòè — àäàïòàöèÿ.
ÍÀËÈ×ÈÅ ÀÄÀÏÒÀÖÈÈ/ÎÁÓ×ÅÍÈß
Ñðåäè ïðèáëèæåííûõ ìåòîäîâ ÊÎ ñ ïàìÿòüþ âûäåëèì òàêèå, êîòîðûå îáëàäàþò
ñâîéñòâîì àäàïòèðîâàòüñÿ/îáó÷àòüñÿ (èçìåíÿòü çíà÷åíèÿ ñâîèõ ïàðàìåòðîâ
â ïðîöåññå ðàáîòû íà îñíîâå ñîñòîÿíèÿ ïàìÿòè). Àäàïòàöèÿ âêëþ÷àåò äèíàìè-
÷åñêóþ íàñòðîéêó çíà÷åíèé ïàðàìåòðîâ, àâòîìàòè÷åñêèé âûáîð ïîä÷èíåííûõ
ïðîöåäóð è íàëè÷èå ìîäåëè çàäà÷è. Àäàïòèâíûå ìåòîäû ÊÎ — ýòî íîâàÿ ðàçâè-
âàþùàÿñÿ îáëàñòü, è ïîêà îíà ÿâëÿåòñÿ ñêîðåå íàáîðîì îòäåëüíûõ ïîäõîäîâ.
Ðàññìîòðèì íåêîòîðûå èç íèõ.
Ðåàêòèâíûé/ðåàãèðóþùèé ïîèñê [61] ïðåäîñòàâëÿåò ìåõàíèçì äëÿ âêëþ÷åíèÿ
â àëãîðèòì íàñòðîéêè âàðüèðóåìûõ ïàðàìåòðîâ: çíà÷åíèÿ ïàðàìåòðîâ íàñòðàèâàþò-
ñÿ â àâòîìàòèçèðîâàííîì öèêëå îáðàòíîé ñâÿçè ñîîòâåòñòâåííî «êà÷åñòâó» íàéäåí-
íûõ ðåøåíèé, èñòîðèè ïîèñêà è äðóãèì õàðàêòåðèñòèêàì. Â ðåàêòèâíîì òàáó-ïîèñ-
êå [62], îäíîì èç ïåðâûõ ðåàêòèâíûõ àëãîðèòìîâ, ïåðèîä çàïðåùåíèÿ
àâòîìàòè÷åñêè íàñòðàèâàåòñÿ â ïðîöåññå ïîèñêà.
Ïðîöåññ îáó÷åíèÿ àêòèâíî èñïîëüçóåòñÿ äëÿ àâòîìàòèçèðîâàííîãî âûáîðà
êîìïîíåíòîâ, îñóùåñòâëÿåìîãî â àëãîðèòìàõ, êîòîðûå ïðèíàäëåæàò ê îïèñàííîìó
êëàññó ãèïåðýâðèñòèê.
Àäàïòàöèÿ ìîæåò äîñòèãàòüñÿ ïóòåì èñïîëüçîâàíèÿ ñïåöèàëüíîé ñòðóêòóðû
ïàìÿòè — ìîäåëè çàäà÷è, î ÷åì ïîéäåò ðå÷ü äàëåå.
Êîíêðåòíûå òåõíèêè àäàïòàöèè ðàçâèâàþòñÿ è â ðàìêàõ îòäåëüíûõ êëàññîâ ìå-
òîäîâ. Íàïðèìåð, â êëàññå ìåìåòè÷åñêèõ àëãîðèòìîâ [41] ðàçâèâàåòñÿ íàïðàâëåíèå
àäàïòèâíûõ ìåòîäîâ [63], â êîòîðûõ ñîâåðøàåòñÿ äèíàìè÷åñêèé âûáîð òèïà
àëãîðèòìà âñòðîåííîãî ëîêàëüíîãî ïîèñêà.
Ðàññìîòðåííûå ïîäõîäû ê ðàçðàáîòêå àäàïòèâíûõ àëãîðèòìîâ ÊÎ, åñòåñòâåí-
íî, íå îõâàòûâàþò âñåõ ïðåäëîæåííûõ ìåòîäîâ è òåõíèê, à ëèøü îòîáðàæàþò íàè-
áîëåå çíà÷èìûå òåíäåíöèè.
ÍÀËÈ×ÈÅ ÑÏÅÖÈÀËÜÍÎÉ ÌÎÄÅËÈ ÇÀÄÀ×È
Ïî îòñóòñòâèþ èëè íàëè÷èþ â àëãîðèòìå ñïåöèàëüíîé ìîäåëè çàäà÷è ìîæíî âû-
äåëèòü êëàññ çàäà÷å-îðèåíòèðîâàííûõ ìåòîäîâ è êëàññ ìîäåëå-îðèåíòèðîâàííûõ
àëãîðèòìîâ [64]. Áîëüøèíñòâî ìåòîäîâ ÊÎ ÿâëÿþòñÿ çàäà÷å-îðèåíòèðîâàííûìè,
òàê êàê îíè ãåíåðèðóþò íîâûå âàðèàíòû ðåøåíèé òîëüêî íà îñíîâå òåêóùåãî
ðåøåíèÿ èëè ìíîæåñòâà òåêóùèõ âàðèàíòîâ ðåøåíèé. Ýòî òàêèå ìåòîäû, êàê ãå-
íåòè÷åñêèå àëãîðèòìû, ïîâòîðÿåìûé ëîêàëüíûé ïîèñê è äð.  ìîäåëå-îðèåíòèðî-
âàííûõ ìåòîäàõ âàðèàíòû ðåøåíèé ãåíåðèðóþòñÿ ñ èñïîëüçîâàíèåì ïàðàìåòðèçè-
ðîâàííîé âåðîÿòíîñòíîé ìîäåëè, êîòîðàÿ îáíîâëÿåòñÿ íà îñíîâå ðàíåå ðàññìîò-
ðåííûõ âàðèàíòîâ ðåøåíèé òàê, ÷òîáû ïîèñê êîíöåíòðèðîâàëñÿ â îáëàñòÿõ ñ
âàðèàíòàìè ðåøåíèé «âûñîêîãî êà÷åñòâà» [64]. Øèðîêî èçâåñòíûìè ìîäåëå-îðè-
åíòèðîâàííûìè ìåòîäàìè ÿâëÿþòñÿ ìåòîä îïòèìèçàöèè ìóðàâüèíûìè êîëîíèÿìè
[48], ìåòîä êðîññ-ýíòðîïèè [65] è ìåòîä âû÷èñëåíèÿ îöåíîê ðàñïðåäåëåíèé [46].
78 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
 [66] ïðåäëîæåíî â îäíîì ìåòîäå èñïîëüçîâàòü íåñêîëüêî âñòðîåííûõ ìíîãî-
àãåíòíûõ ìîäåëå-îðèåíòèðîâàííûõ àëãîðèòìîâ, ïî ðåçóëüòàòàì ðàáîòû êîòîðûõ íà
êàæäîé èòåðàöèè îáùåãî ìåòîäà ôîðìèðóåòñÿ è âîçâðàùàåòñÿ âñòðîåííûì ìåòîäàì
äëÿ èñïîëüçîâàíèÿ îáîáùåííàÿ/àãðåãèðîâàííàÿ ìîäåëü çàäà÷è.
ÄÐÓÃÈÅ ÏÎÄÕÎÄÛ Ê ÊËÀÑÑÈÔÈÊÀÖÈÈ
Íåêîòîðûå àâòîðû [1, 4] ïðåäëàãàþò ðàçäåëÿòü ïðèáëèæåííûå àëãîðèòìû ïî
òîìó, áûëè ëè îíè ñîçäàíû ïî êàêîìó-íèáóäü ïðèðîäíîìó àíàëîãó, êàê, íàïðè-
ìåð, àëãîðèòìû îïòèìèçàöèè ìóðàâüèíûìè êîëîíèÿìè èëè ãåíåòè÷åñêèå àëãî-
ðèòìû. Îäíàêî ýòîò ïîêàçàòåëü íå îòðàæàåò ñóùåñòâåííûõ õàðàêòåðèñòèê àëãî-
ðèòìà, ïîýòîìó â äàííóþ êëàññèôèêàöèþ âêëþ÷åí íå áûë.
Íà ðèñ. 2 ïðèâåäåíû âàæíåéøèå õàðàêòåðèñòèêè, ïî êîòîðûì ïðåäëàãàåòñÿ
êëàññèôèöèðîâàòü ïðèêëàäíûå ïðèáëèæåííûå àëãîðèòìû ÊÎ, à òàêæå ñîîòâåòñòâó-
þùèå êëàññû, îáðàçîâàííûå íà îñíîâå ýòèõ õàðàêòåðèñòèê. Êðîìå òîãî, íà ðèñóíêå
îòîáðàæåíû âçàèìîñâÿçè ìåæäó êëàññàìè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 79
Àëãîðèòìû, íå èçìåíÿþùèå
ëàíäøàôò ïîèñêà
Ñòîõàñòè÷åñêèå àëãîðèòìû
Äåòåðìèíèðîâàííûå
àëãîðèòìû
Èòåðàöèîííûå àëãîðèòìû
Ïîñëåäîâàòåëüíûå àëãîðèòìû
Ïîïóëÿöèîííûå
àëãîðèòìû
Îäíîòî÷å÷íûå
àëãîðèòìû
Ïðîñòûå àëãîðèòìû
Çàäà÷å-îðèåíòèðîâàííûå
àëãîðèòìû
Àëãîðèòìû áåç àäàïòàöèè
Ìîäåëå-îðèåíòèðîâàííûå
àëãîðèòìû
Àëãîðèòìû ñ ïàìÿòüþ
Àëãîðèòìû áåç ïàìÿòè
Àëãîðèòìû, èçìåíÿþùèå
ëàíäøàôò ïîèñêà
Èçìåíåíèå öåëåâîé/
îöåíî÷íîé ôóíêöèè
Èçìåíåíèå
ïðîñòðàíñòâà ïîèñêà
Èçìåíåíèå ñèñòåìû
îêðåñòíîñòåé
Àëãîðèòìû ñ àäàïòàöèåé
Óïðàâëÿþùàÿ ïàìÿòü
Çàïîìèíàþùàÿ ïàìÿòü
Àäàïòèâíàÿ ïàìÿòü
Ìåòàýâðèñòèêè
Ãèáðèäíûå àëãîðèòìû Ãèáðèäíûå ìåòàýâðèñòèêè
Âûáîð êîìïîíåíòîâ
Àâòîíàñòðîéêà
ïàðàìåòðîâ
Íàëè÷èå ñïåöèàëüíîé
ìîäåëè çàäà÷è
Òèï ôîðìèðóåìîé
òðàåêòîðèè
Òðàåêòîðíî-íåïðåðûâíûå
àëãîðèòìû
Òðàåêòîðíî-ðàçðûâíûå àëãîðèòìû
Òèï
èñïîëüçóåìûõ
ïðîñòðàíñòâ
Âëèÿíèå íà
ëàíäøàôò ïîèñêà
Íàëè÷èå ïàìÿòè
Íàëè÷èå
àäàïòàöèè/
îáó÷åíèÿ
Íàëè÷èå
ñïåöèàëüíîé
ìîäåëè çàäà÷è
Ñëîæíîñòü
ñòðóêòóðû Ãèïåðýâðèñòèêè
Ïðèíöèï
ïðèíÿòèÿ
ðåøåíèé
ÕÀÐÀÊÒÅÐÈÑÒÈÊÈ ÊËÀÑÑÛ
Ðèñ. 2. Êëàññèôèêàöèÿ ïðèêëàäíûõ ïðèáëèæåííûõ àëãîðèòìîâ ÊÎ
Èñïîëüçîâàíèå
ïàìÿòè
Àñïåêòàì ïàðàëëåëüíîé ðåàëèçàöèè ïðèêëàäíûõ àëãîðèòìîâ êîìáèíàòîðíîé
îïòèìèçàöèè, ðàññìîòðåíèå êîòîðûõ íàõîäèòñÿ âíå ðàìîê äàííîé ðàáîòû, óäåëåíî
âíèìàíèå, â ÷àñòíîñòè, â [67, 68].
Îòìåòèì, ÷òî â äàííîé ðàáîòå ðàññìàòðèâàþòñÿ çàäà÷è ÊÎ â êëàññè÷åñêîé
ïîñòàíîâêå, ò.å. âíå ïîëÿ çðåíèÿ áûëè îñòàâëåíû äðóãèå òèïû çàäà÷ ÊÎ (íàïðèìåð,
äèñêðåòíîå ïðîãðàììèðîâàíèå, ìíîãîêðèòåðèàëüíûå, äèíàìè÷åñêèå, ñòîõàñòè÷åñ-
êèå çàäà÷è).
 ïîñëåäíåå âðåìÿ ïîÿâèëñÿ ðÿä íîâûõ ïàðàäèãì, íà îñíîâå êîòîðûõ ðàçðàáà-
òûâàþòñÿ àëãîðèòìû ÊÎ [69–74]. Îäíàêî èìåþùèõñÿ äàííûõ îá èõ ïðèìåíåíèè
äëÿ ðåøåíèÿ ïðàêòè÷åñêè âàæíûõ çàäà÷ ÊÎ åùå íåäîñòàòî÷íî äëÿ òîãî, ÷òîáû ñäå-
ëàòü îáîñíîâàííûå âûâîäû îá èõ ýôôåêòèâíîñòè.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåíû ïîäõîäû ê ôîðìàëèçàöèè çàäà÷ ÊÎ è êëàññèôèêàöèè ïðèêëàäíûõ
ìåòîäîâ ÊÎ. Ïî èñïîëüçóåìîé ïàðàäèãìå ñðåäè ïðèáëèæåííûõ àëãîðèòìîâ ðå-
øåíèÿ çàäà÷ ÊÎ âûäåëåíû êîíñòðóêòèâíûå àëãîðèòìû, àëãîðèòìû äåòåðìèíèðî-
âàííîãî ëîêàëüíîãî ïîèñêà, ñòîõàñòè÷åñêîãî ëîêàëüíîãî ïîèñêà, ýâîëþöèîííûå
ìåòîäû, ìåòîäû ðîåâîãî èíòåëëåêòà, ìåòîäû ñêàíèðîâàíèÿ è ñïåöèàëüíûå àëãî-
ðèòìû. Ñôîðìóëèðîâàíû êðèòåðèè, ïî êîòîðûì âîçìîæíî îñóùåñòâëÿòü ðàç-
íîñòîðîííþþ êëàññèôèêàöèþ áîëüøèíñòâà èçâåñòíûõ è ïðàêòè÷åñêè ïðèìåíÿå-
ìûõ ïðèáëèæåííûõ àëãîðèòìîâ ðåøåíèÿ çàäà÷ ÊÎ: ïðèíöèï ïðèíÿòèÿ ðåøåíèé,
ñëîæíîñòü ñòðóêòóðû, òèï èñïîëüçóåìûõ ïðîñòðàíñòâ, òèï ôîðìèðóåìîé òðàåê-
òîðèè, âëèÿíèå íà ëàíäøàôò ïîèñêà, èñïîëüçîâàíèå ïàìÿòè, íàëè÷èå àäàïòà-
öèè/îáó÷åíèÿ è íàëè÷èå ñïåöèàëüíîé ìîäåëè çàäà÷è.
Ðåàëèçóåìûå â íàñòîÿùåå âðåìÿ àëãîðèòìû ðåøåíèÿ ïðàêòè÷åñêèõ çàäà÷ ÊÎ
â ïîäàâëÿþùåì áîëüøèíñòâå ÿâëÿþòñÿ (ãèáðèäíûìè) ìåòàýâðèñòèêàìè, ò.å. îáúå-
äèíÿþò â ñåáå èäåè è êîìïîíåíòû èç íåñêîëüêèõ ïîäõîäîâ. Äàííàÿ êëàññèôèêàöèÿ
ðàññìàòðèâàåò êîíöåïòóàëüíûå èäåè ïîñòðîåíèÿ «áàçîâûõ» ïðèêëàäíûõ àëãîðèò-
ìîâ ÊÎ, ÷òî ïîçâîëÿåò ýôôåêòèâíî ïðèìåíÿòü è àíàëèçèðîâàòü òåõíîëîãèè ñîçäà-
íèÿ ñîâðåìåííûõ ãèáðèäíûõ ìåòàýâðèñòèê è ãèïåðýâðèñòèê.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. S t ��u t z l e T . Local search algorithms for combinatorial problems — analysis, improvements and
new applications: PhD. Thesis / Technische Univ. Darmstadt. — Darmstadt, 1998. — 214 p.
2. V a e s s e n s R . J . M . , A a r t s E . H . L . , L e n s t r a J . K . A local search template // Comput.
Oper. Res. — 1998. — 25, N 11. — P. 969–979.
3. B i r a t t a r i M . , P a q u e t e L . , S t ��u t z l e T . , V a r r e n t r a p p K . Classification of
metaheuristics and design of experiments for the analysis of components: (Techn. rep.) / Techn. Univ.
Darmstadt. — N AIDA-01-05. — Darmstadt, 2001. — 12 p.
4. B l u m C . , R o l i A . Metaheuristics in combinatorial optimization: overview and conceptual com-
parison // ACM Computing Surveys. — 2003. — 35, N 3. — P. 268–308.
5. G e n d r e a u M . , P o t v i n J . - Y . Metaheuristics in combinatorial optimization // Ann. Oper. Res.
— 2005. — 140, N 1. — P. 189–213.
6. Ë å î í ò ü å â  . Ê . Äèñêðåòíàÿ îïòèìèçàöèÿ // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. —
2007. — 47, ¹ 2. — Ñ. 338–352.
7. H o o s H . H . , S t ��u t z l e T . Stochastic local search: foundations and applications. — San Fran-
cisco: Morgan Kaufmann Publ., 2005. — 658 p.
8. R a i d l G . R . A unified view on hybrid metaheuristics // Lect. Notes Comput. Sci. — Berlin:
Springer-Verlag, 2006. — 4030. — P. 1–12.
9. à ó ë ÿ í è ö ê è é Ë . Ô . , Ñ å ð ã è å í ê î È .  . Ìåòàýâðèñòè÷åñêèé ìåòîä äåôîðìèðîâàííîãî
ìíîãîãðàííèêà â êîìáèíàòîðíîé îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. —
¹ 6. — Ñ. 70–79.
80 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
10. Ï à ï à ä è ì è ò ð è ó Õ . , Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. Àëãîðèòìû è ñëîæ-
íîñòü. — Ì.: Ìèð, 1985. — 512 ñ.
11. Ñ å ð ã è å í ê î È .  . Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòè-
ìèçàöèè. — Ê.: Íàóê. äóìêà, 1988. — 471 ñ.
12. Ì è õ à ë å â è ÷ Â . Ñ . , Ê ó ê ñ à À . È . Ìåòîäû ïîñëåäîâàòåëüíîé îïòèìèçàöèè â äèñêðåòíûõ
ñåòåâûõ çàäà÷àõ îïòèìàëüíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ. — Ì.: Íàóêà, 1983. — 208 ñ.
13. Ï à â ë î â À . À . , Ì è ñ þ ð à Å . Á . Ýôôåêòèâíûé òî÷íûé ÏÄÑ-àëãîðèòì ðåøåíèÿ çàäà÷è î
ñóììàðíîì çàïàçäûâàíèè äëÿ îäíîãî ïðèáîðà // Ñèñòåìí³ äîñë³äæåííÿ òà ³íôîðì. òåõíîëî㳿.
— 2004. — ¹ 4. — Ñ. 30–59.
14. H a n d b o o k of applied optimization (Eds. P. Pardalos, M.G.C. Resende). — Oxford: Oxford Univ.
Press, 2002. — 2026 p.
15. H a n d b o o k of approximation algorithms and metaheuristics (Ed. T.F. Gonzalez). — Boca Raton
(FL): CRC press, 2007. — 1432 p.
16. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáè-
íàòîðíûõ çàäà÷ îïòèìèçàöèè. — Ê.: Íàóê. äóìêà, 1981. — 288 ñ.
17. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè. — Ê.: Íàóê. äóìêà,
2003. — 261 ñ.
18. D e J o n g K . A . Evolutionary computation: a unified approach. — Cambridge (MA): MIT Press,
2006. — 272 p.
19. L e g u i z a m o n G . , B l u m C . , A l b a E . Evolutionary computation // Handbook of approxima-
tion algorithms and metaheuristics (Ed. T.F. Gonzalez). — Boca Raton (FL): CRC press, 2007. —
P. 372–386.
20. K e n n e d y J . , E b e r h a r t R . C . , S h i Y . Swarm intelligence. — San Francisco (CA): Morgan
Kaufmann, 2001. — 512 p.
21. K h u l l e r S . , R a g h a v a c h a r i B . , Y o u n g N . E . Greedy methods // Handbook of approxi-
mation algorithms and metaheuristics (Ed. T.F. Gonzalez). — Boca Raton (FL): CRC press, 2007. —
P. 67–80.
22. Ñ å ð ã ³ º í ê î ² .  . Îäèí ìåòîä ðîçâ’ÿçóâàííÿ çàäà÷ íà â³äøóêàííÿ åêñòðåìàëüíèõ çíà÷åíü //
Àâòîìàòèêà. — 1964. — ¹ 5. — Ñ. 15–21.
23. Ê î ÷ å ò î â Þ . À . Âû÷èñëèòåëüíûå âîçìîæíîñòè ëîêàëüíîãî ïîèñêà â êîìáèíàòîðíîé îïòè-
ìèçàöèè // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 2008. — 48, ¹ 5. — Ñ. 788–807.
24. Ã ó ë ÿ í è ö ê è é Ë . Ô . , Õ î ä ç è í ñ ê è é À . Í . Îñîáåííîñòè ðåàëèçàöèè àëãîðèòìîâ ìåòîäà
âåòâåé è ãðàíèö è ìåòîäà âåêòîðà ñïàäà â ïàêåòå ÂÅÊÒÎЖ1 // Âû÷èñëèòåëüíûå àñïåêòû â
ïàêåòàõ ïðèêëàäíûõ ïðîãðàìì. — Êèåâ: Èí-ò êèáåðíåòèêè ÀÍ ÓÑÑÐ, 1979. — Ñ. 25–30.
25. M l a d e n o v i c� N . , H a n s e n P . Variable neighbourhood search // Comput. Oper. Res. — 1997.
— N 24. — P. 1097–1100.
26. H a n s e n P . , M l a d e n o v i c� N . , M o r e n o - P e'r e z J . A . Variable neighbourhood search:
methods and applications // Quarterly J. Oper. Res. — 2008. — 6, N 4. — P. 319–360.
27. V o u d o u r i s C . , T s a n g E . P . K . Guided local search // Handbook of metaheuristics (Ed.
F. Glover). — Norwell (MA): Kluwer Acad. Publ., 2003. — P. 185–218.
28. K e r n i g h a n B . W . , L i n S . An efficient heuristic procedure for partitioning graphs // Bell Sys-
tem Techn. J. — 1970. — N 49. — P. 291–307.
29. K i r k p a t r i k S . , G e l a t t C . D . , V e c c h i M . P . Optimization by simulated annealing // Sci-
ence. — 1983. — 220, N 4598. — P. 671–680.
30. A a r t s E . , K o r s t J . , M i c h i e l s W . Simulated annealing // Handbook of approximation algo-
rithms and metaheuristics (Ed. T.F. Gonzalez). — Boca Raton (FL): CRC press, 2007. — P. 387–397.
31. Ã ó ë ÿ í è ö ê è é Ë . Ô . Ðåøåíèå çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè àëãîðèòìàìè óñêîðåííîãî
âåðîÿòíîñòíîãî ìîäåëèðîâàíèÿ // Êîìïüþòåðíàÿ ìàòåìàòèêà. — Ê.: Èí-ò êèáåðíåòèêè
èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, 2004. — ¹ 1. — Ñ. 64–72.
32. L o u r e n ñ, o H . R . , M a r t i n O . , S t ��u t z l e T . Iterated local search // Handbook of meta-
heuristics (Eds. F. Glover, G. Kochenberger). — Norwell (MA): Kluwer Acad. Publ., 2002. —
P. 321–353.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 81
33. G l o v e r F . Future paths for integer programming and links to artificial intelligence // Comput.
Oper. Res. — 1986. — N 5. — P. 533–549.
34. G l o v e r F . , L a g u n a M . Tabu search. — Norwell (MA): Kluwer Acad. Publ., 1997. — 408 p.
35. Q u a n t u m annealing and related optimization methods (Eds. A. Das, B.K. Chakrabarti) // Lect.
Notes Physics. — Heidelberg: Springer, 2005. — 679. — 377 p.
36. F e o T . A . , R e s e n d e M . G . C . A probabilistic heuristic for a computationally difficult set cov-
ering problem // Oper. Res. Letters. — 1989. — 8, N 2. — P. 67–71.
37. P i t s o u l i s L . , R e s e n d e M . G . C . Greedy randomized adaptive search procedures // Hand-
book of applied optimization (Eds. P.M. Pardalos, M.G.C. Resende). — Oxford: Oxford Univ. Press,
2002. — P. 168–181.
38. Ñ ò î ÿ í Þ . à . , ß ê î â ë å â Ñ .  . Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû
ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Ê.: Íàóê. äóìêà, 1986. — 268 ñ.
39. H o l l a n d J . H . Adaptation in natural and artificial systems. — Ann Arbor (MI): Univ. of Michigan
Press, 1975. — 183 p.
40. M o s c a t o P . On evolution, search, optimization, genetic algorithms and martial arts: Towards
memetic algorithms: (Techn. Rep.) / California Inst. of Technology. — N C3P 826. — Pasadena
(CA), 1989. — 68 p.
41. M o s c a t o P . , C o t t a C . Memetic algorithms // Handbook of approximation algorithms and
metaheuristics (Ed. T.F. Gonzalez). — Boca Raton (FL): CRC press, 2007. — P. 412–423.
42. C u t e l l o V . , N i c o s i a G . An immunological approach to combinatorial optimization problems
// Lect. Notes Comput. Sci. — 2002. — N 2527. — P. 361–370.
43. d e C a s t r o L . N . , T i m m i s J . Artificial immune systems: a new computational intelligence ap-
proach. — London: Springer, 2002. — 380 p.
44. G l o v e r F . , L a g u n a M . , M a r t i' R . Scatter search and path relinking: foundations and ad-
vanced designs // New optimization techniques in engineering (Eds. G. Onwubolu, B.V. Babu). —
Berlin: Springer-Verlag, 2004. — P. 87–100.
45. M ��u h l e n b e i n H . , P a a � � � From recombination of genes to the estimation of distributions. I.
Binary parameters // Lect. Notes Comput. Sci.: Parallel problem solving from nature. — 1996. — N 4.
— P. 178–187.
46. E s t i m a t i o n of distribution algorithms. A new tool for evolutionary computation (Eds.
P. Larra~naga, J.A. Lozano). — Boston (MA): Kluwer Acad. Publ., 2001. — 416 p.
47. D o r i g o M . , D i C a r o G . , G a m b a r d e l l a L . M . Ant algorithms for discrete optimization //
Artif. Life. — 1999. — 5, N 2. — P. 137–172.
48. D o r i g o M . , S t ��u t z l e T . Ant colony optimization. — Cambridge (MA): MIT Press, 2004. —
348 p.
49. E b e r h a r t R . C . , K e n n e d y J . Particle swarm optimization // Proc. IEEE Intern. Conf. on Neu-
ral Networks. — Piscataway (NJ): IEEE Service Center, 1995. — 4. — P. 1942–1948.
50. C l e r c M . Particle swarm optimization. — Hoboken (NJ): Wiley-Interscience, 2006. — 243 p.
51. T e o d o r o v i c D . , L u c i c P . , M a r k o v i c G . , D ’ O r c o M . Bee colony optimization: prin-
ciples and applications // 8th Seminar on Neural Network Applications in Electrical Engineering, Bel-
grade, Serbia, 2006. — P. 151–156.
52. D e M e y e r K . , N a s u t o S . J . , B i s h o p J . M . Stochastic diffusion search: partial function
evaluation in swarm intelligence dynamic optimisation // Stigmergic optimization (Eds. A. Abraham,
C. Grosam, V. Ramos). — Berlin: Springer–Verlag, 2006. — P. 185–208.
53. Ã ó ë ÿ í è ö ê è é Ë . Ô . Ìåòîä äåôîðìàöèé â äèñêðåòíîé îïòèìèçàöèè // Èññëåä. îïåðàöèé è
ÀÑÓ. — 1989. — ¹ 34. — Ñ. 30–33.
54. Æ ó ð à â ë å â Þ . È . Êîððåêòíûå àëãåáðû íàä ìíîæåñòâàìè íåêîððåêòíûõ (ýâðèñòè÷åñêèõ)
àëãîðèòìîâ // Êèáåðíåòèêà. — 1977. — ¹ 4. — Ñ. 5–17.
55. B e r t s e k a s D . P . , T s i t s i k l i s J . N . , W u C . Rollout algorithms for combinatorial optimiza-
tion // J. Heuristics. — 1997. — N 3. — P. 245–262.
56. H y p e r h e u r i s t i c s : an emerging direction in modern search technology / E. Burke, E. Hart,
G. Kendall et al. // Handbook of metaheuristics (Eds. F. Glover, G. Kochenberger). — Norwell (MA):
Kluwer Acad. Publ., 2003. — P. 457–474.
82 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
57. O z c a n E . , B i l g i n E . , K o r k m a z E . E . A comprehensive analysis of hyper-heuristics // In-
telligent Data Analysis. — 2008. — 12, N 1. — P. 3–23.
58. Ã ó ë ÿ í è ö ê è é Ë . Ô . Îá îäíîì ñåìåéñòâå èòåðàöèîííûõ àëãîðèòìîâ äèñêðåòíîé
îïòèìèçàöèè // Ðàçðàáîòêà ìàòåìàòè÷åñêèõ è òåõíè÷åñêèõ ñðåäñòâ â ÀÑÓ. — Êèåâ: ÈÊ ÀÍ
ÓÑÑÐ, 1978. — Ñ. 25–30.
59. G l o v e r F . Ejection chains, reference structures and alternating path methods for traveling salesman
problems // Discrete Appl. Math. — 1996. — N 65. — P. 223–253.
60. M o r r i s P . The breakout method for escaping from local minima // Proc. of the 11th Conf. on Artif.
Intelligence. — Cambridge (MA): MIT Press, 1993. — P. 40–45.
61. B a t t i t i R . , B r u n a t o M . Reactive search: Machine learning for memory-based heuristics:
(Techn. Rep.) / Univ. di Trento. — N DIT-05-058. — Trento, 2005. — 20 p.
62. B a t t i t i R . , T e c c h i o l l i R . The reactive tabu search // ORSA J. Computing. — 1994. — 6,
N 2. — P. 126–140.
63. O n g Y . - S . , L i m M . - H . , Z h u N . , W o n g K . - W . Classification of adaptive memetic algo-
rithms: a comparative study // IEEE Trans. Systems, Man, and Cybernetics. Part B, Cybernetics. —
2006. — 36, N 1. — P. 141–152.
64. Z l o c h i n M . , B i r a t t a r i M . , M e u l e a u N . , D o r i g o M . Model-based search for combi-
natorial optimization: a critical survey // Ann. Oper. Res. — 2004. — N 131. — P. 373–395.
65. R u b i n s t e i n R . Y . , K r o e s e D . P . The cross-entropy method: a unified approach to combina-
torial optimization, Monte-Carlo simulation, and machine learning. — New York: Springer-Verlag,
2004. — 300 p.
66. Ã ó ë ÿ í è ö ü ê è é Ë . Ô . Ðîçðîáêà êîîïåðàòèâíèõ ìåòàåâðèñòèê // Abstract of Int. Conf. «Prob-
lems of Decision Making under Uncertainties (PDMU–2009)» (April 27-30, 2009, Skhidnytsia,
Ukraine). — Kyiv, 2009. — P. 90–91.
67. P a r a l l e l combinatorial optimization (Ed. E.-G. Talbi). — Hoboken (NJ): Wiley-Interscience,
2006. — 330 p.
68. P a r a l l e l metaheuristics: a new class of algorithms (Ed. E. Alba). — Hoboken (NJ): Wiley-
Interscience, 2006. — 576 p.
69. C h o i C . , L e e J . Chaotic local search algorithm // Artif. Life Robotics. — 1998. — 2, N 1. —
P. 41–47.
70. B o e t t c h e r S . , P e r c u s A . G . Extremal optimization: Methods derived from co-evolution //
Proc. of the Genetic and Evolutionary Computation Conf. (GECCO), 1999. — P. 825–832.
71. B o u r j o t C . , C h e v r i e r V . , T h o m a s V . A new swarm mechanism based on social spiders
colonies: from web weaving to region detection // Web Intelligence and Agent Systems. — 2003. —
1, N 1. — P. 47–64.
72. W a k u y a H . A new search method for combinatorial optimization problem inspired by the spin
glass system // Intern. Congress Series. — 2006. — N 1291. — P. 201–204.
73. C o r t � s P . , G a r c i'a J . M . , M u ~n u z u r i J . , O n i e v a L . Viral systems: A new bio-inspired
optimisation approach // Comput. Oper. Res. — 2008. — N 35. — P. 2840–2860.
74. O m r a n M . G . H . , M a h d a v i M . Global-best harmony search // Appl. Math. Comput. — 2008.
— N 198. — P. 643–656.
Ïîñòóïèëà 29.04.2009
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 83
|