Генетичні алгоритми турнірного витиснення з гаусовою мутацією
Для розв’язання задач багатоекстремальної оптимізації запропоновано новий генетичний алгоритм утворення ніш — генетичний алгоритм турнірного витиснення з гаусовою мутацією. Проведено порівняльний аналіз його з іншими алгоритмами витиснення та з паралельним алгоритмом сходження на вершини, який показ...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2020 |
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/190362 |
| 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: | Генетичні алгоритми турнірного витиснення з гаусовою мутацією / В.П. Шило, М.М. Глибовець, Н.М. Гулаєва, К.В. Нікіщіхіна // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 75–88. — Бібліогр.: 11 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860096056236179456 |
|---|---|
| author | Шило, В.П. Глибовець, М.М. Гулаєва, Н.М. Нікіщіхіна, К.В. |
| author_facet | Шило, В.П. Глибовець, М.М. Гулаєва, Н.М. Нікіщіхіна, К.В. |
| citation_txt | Генетичні алгоритми турнірного витиснення з гаусовою мутацією / В.П. Шило, М.М. Глибовець, Н.М. Гулаєва, К.В. Нікіщіхіна // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 75–88. — Бібліогр.: 11 назв. — укр. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Для розв’язання задач багатоекстремальної оптимізації запропоновано новий генетичний алгоритм утворення ніш — генетичний алгоритм турнірного витиснення з гаусовою мутацією. Проведено порівняльний аналіз його з іншими алгоритмами витиснення та з паралельним алгоритмом сходження на вершини, який показав переваги розробленого алгоритму у багатьох випадках. Введено критерій оцінювання ступеня розпорошеності елементів популяції та показано, що обчислення цього критерію є доцільним для оцінювання якості роботи алгоритмів пошуку глобальних та локальних максимумів.
Для решения задач многоэкстремальной оптимизации предложен новый генетический алгоритм образования ниш — генетический алгоритм турнирного вытеснения с гауссовой мутацией. Проведенный сравнительный анализ предложенного алгоритма с другими алгоритмами вытеснения и с параллельным алгоритмом поиска с восхождением к вершинам показал преимущества разработанного алгоритма во многих случаях. Введен критерий оценки степени разброса элементов популяции. Показано, что вычисление этого критерия является целесообразным для оценки качества работы алгоритмов поиска глобальных и локальных максимумов.
To solve multimodal optimization problems, a new niching genetic algorithm named tournament crowding genetic algorithm based on Gauss mutation is proposed. A comparative analysis of this algorithm to other crowding algorithms and to parallel hill-climbing algorithm has shown the advantages of the proposed algorithm in many cases. The FPR criterion to estimate the distribution of population elements is proposed and it is shown that computation of this criterion is advisable to estimate algorithms solving multimodal problems of finding global and local maxima.
|
| first_indexed | 2025-12-07T17:26:06Z |
| format | Article |
| fulltext |
ÓÄÊ 004.023
Â.Ï. ØÈËÎ, Ì.Ì. ÃËÈÁÎÂÅÖÜ, Í.Ì. ÃÓËÀªÂÀ, Ê.Â. ͲʲٲղÍÀ
ÃÅÍÅÒÈ×Ͳ ÀËÃÎÐÈÒÌÈ ÒÓÐͲÐÍÎÃÎ ÂÈÒÈÑÍÅÍÍß
Ç ÃÀÓÑÎÂÎÞ ÌÓÒÀÖ²ªÞ
Àíîòàö³ÿ. Äëÿ ðîçâ’ÿçàííÿ çàäà÷ áàãàòîåêñòðåìàëüíî¿ îïòèì³çàö³¿ çàïðîïî-
íîâàíî íîâèé ãåíåòè÷íèé àëãîðèòì óòâîðåííÿ í³ø — ãåíåòè÷íèé àëãîðèòì
òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìóòàö³ºþ. Ïðîâåäåíî ïîð³âíÿëüíèé
àíàë³ç éîãî ç ³íøèìè àëãîðèòìàìè âèòèñíåííÿ òà ç ïàðàëåëüíèì àëãîðèò-
ìîì ñõîäæåííÿ íà âåðøèíè, ÿêèé ïîêàçàâ ïåðåâàãè ðîçðîáëåíîãî àëãîðèòìó
ó áàãàòüîõ âèïàäêàõ. Ââåäåíî êðèòåð³é îö³íþâàííÿ ñòóïåíÿ ðîçïîðîøåíîñò³
åëåìåíò³â ïîïóëÿö³¿ òà ïîêàçàíî, ùî îá÷èñëåííÿ öüîãî êðèòåð³þ º
äîö³ëüíèì äëÿ îö³íþâàííÿ ÿêîñò³ ðîáîòè àëãîðèòì³â ïîøóêó ãëîáàëüíèõ òà
ëîêàëüíèõ ìàêñèìóì³â.
Êëþ÷îâ³ ñëîâà: çàäà÷à áàãàòîåêñòðåìàëüíî¿ îïòèì³çàö³¿, ãåíåòè÷í³ àëãîðèò-
ìè óòâîðåííÿ í³ø, àëãîðèòìè âèòèñíåííÿ, ïàðàëåëüíèé àëãîðèòì ñõîäæåííÿ
íà âåðøèíè, ÷àñòêà õèáíèõ ï³ê³â.
ÂÑÒÓÏ
Çàäà÷à áàãàòîåêñòðåìàëüíî¿ (ìóëüòèìîäàëüíî¿) îïòèì³çàö³¿ ïîëÿãຠó çíàõîä-
æåíí³ ê³ëüêîõ åêñòðåìóì³â áàãàòîåêñòðåìàëüíî¿ ôóíêö³¿. Âèä³ëÿþòü òàê³ òèïè
öèõ çàäà÷: çíàéòè âñ³ ãëîáàëüí³ åêñòðåìóìè; çíàéòè âñ³ ãëîáàëüí³ òà âñ³ ëî-
êàëüí³ åêñòðåìóìè; çíàéòè ïðèíàéìí³ k ãëîáàëüíèõ åêñòðåìóì³â; çíàéòè k íàé-
êðàùèõ åêñòðåìóì³â òîùî.
Äëÿ ðîçâ’ÿçàííÿ çàäà÷ áàãàòîåêñòðåìàëüíî¿ îïòèì³çàö³¿ ðîçðîáëÿþòü
ñïåö³àëüí³ àëãîðèòìè. Ñåðåä íèõ îñîáëèâîþ ïîïóëÿðí³ñòþ êîðèñòóþòüñÿ ãåíå-
òè÷í³ àëãîðèòìè óòâîðåííÿ í³ø, â îñíîâó ÿêèõ ïîêëàäåíî ÿâèùå âèäîóòâîðåííÿ
òà ñïåö³àë³çàö³¿ â ïðèðîäíèõ åêîñèñòåìàõ. Ö³ àëãîðèòìè ñïðèÿþòü ôîðìóâàííþ
ñòàá³ëüíèõ ñóáïîïóëÿö³é (âèä³â) ó ïðîñòîð³ ïîøóêó â òàêèé ñïîñ³á, ùî êîæíà ç
ñóáïîïóëÿö³é ôîðìóºòüñÿ íàâêîëî îäíîãî ç øóêàíèõ åêñòðåìóì³â. Íà ñüîãîäí³
ðîçðîáëåíî ê³ëüêà äåñÿòê³â ð³çíèõ ìåòîä³â óòâîðåííÿ í³ø òà â³äîìî ê³ëüêà
âàð³àíò³â êëàñèô³êàö³¿ öèõ ìåòîä³â [1, 2].
Çàçíà÷èìî, ùî ãåíåòè÷í³ àëãîðèòìè çíàéøëè òàêîæ çàñòîñóâàííÿ äëÿ ðîçâ’ÿ-
çàííÿ áàãàòüîõ çàäà÷ äèñêðåòíîãî ïðîãðàìóâàííÿ (íàïðèêëàä, [3–5]). Õî÷à âîíè
çà øâèäêî䳺þ ïîñòóïàþòüñÿ ³íøèì â³äîìèì ìåòîäàì äèñêðåòíî¿ îïòèì³çàö³¿,
àëå ïðîäîâæóþòü àêòèâíî ðîçâèâàòèñÿ ³ öÿ ñèòóàö³ÿ ìîæå çì³íèòèñÿ.
Ó ö³é ðîáîò³ ðîçãëÿíóòî çàäà÷³ áàãàòîåêñòðåìàëüíî¿ îïòèì³çàö³¿, çîêðåìà: çàäà-
÷à çíàõîäæåííÿ âñ³õ ãëîáàëüíèõ ìàêñèìóì³â; çàäà÷à ïîøóêó âñ³õ ãëîáàëüíèõ òà âñ³õ
ëîêàëüíèõ ìàêñèìóì³â. Äëÿ ¿õíüîãî ðîçâ’ÿçàííÿ çàïðîïîíîâàíî íîâèé ãåíåòè÷íèé
àëãîðèòì óòâîðåííÿ í³ø, à ñàìå ãåíåòè÷íèé àëãîðèòì òóðí³ðíîãî âèòèñíåííÿ ç ãàó-
ñîâîþ ìóòàö³ºþ (çáóðåííÿì), ÿêèé êëàñèô³êóâàòèìåìî ÿê ìåòîä âèòèñíåííÿ.
ϳä ìåòîäàìè âèòèñíåííÿ (crowding) ðîçóì³þòü ãåíåòè÷í³ àëãîðèòìè ç³
ñò³éêèì òèïîì ðåïðîäóêö³¿, ÿê³ ó ðàç³ äîäàâàííÿ íîâîãî åëåìåíòà â ïîïóëÿö³þ
âèøòîâõóþòü ³ç ïîïóëÿö³¿ ñõîæèé íà íüîãî åëåìåíò [1, 6]. Íàéâ³äîì³øèìè ñåðåä
öèõ ìåòîä³â º àëãîðèòìè ñòàíäàðòíîãî, äåòåðì³íîâàíîãî, éìîâ³ðí³ñíîãî, áàãà-
òîí³øåâîãî âèòèñíåííÿ òà ¿õí³ ìîäèô³êàö³¿. Îñîáëèâîñòÿìè ïðîïîíîâàíîãî àëãî-
ðèòìó òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìóòàö³ºþ º ïðåäñòàâëåííÿ ðîçâ’ÿçê³â
ä³éñíèìè çì³ííèìè òà âèêîðèñòàííÿ äëÿ ïîðîäæåííÿ íàùàäê³â ò³ëüêè îïåðàòîðà
ãàóñîâî¿ ìóòàö³¿ (îïåðàòîð êðîñèíãîâåðó — îáì³íó ð³çíèõ ðîçâ’ÿçê³â ñâî¿ìè
÷àñòèíàìè — íå çàñòîñîâóºòüñÿ).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 75
© Â.Ï. Øèëî, Ì.Ì. Ãëèáîâåöü, Í.Ì. Ãóëàºâà, Ê.Â. ͳê³ù³õ³íà, 2020
Äëÿ àíàë³çó åôåêòèâíîñò³ çàïðîïîíîâàíîãî àëãîðèòìó çàñòîñîâàíî åêñïåðè-
ìåíòàëüíèé ï³äõ³ä, ñóòü ÿêîãî ïîëÿãຠâ îö³íþâàíí³ äàíèõ, ç³áðàíèõ ó ðåçóëüòàò³
çä³éñíåííÿ âåëèêî¿ ê³ëüêîñò³ íåçàëåæíèõ ïðîãîí³â àëãîðèòìó íà çàäàíîìó íàáîð³
òåñòîâèõ çàäà÷ [6]. Ðîçðîáëåíèé àëãîðèòì ïîð³âíþºòüñÿ ç ïàðàëåëüíèì àëãîðèò-
ìîì ñõîäæåííÿ íà âåðøèíè, îñíîâíà ³äåÿ ÿêîãî º òàêîþ: êîæíà îñîáèíà ïîïó-
ëÿö³¿ íàìàãàºòüñÿ ä³ñòàòèñÿ íàéáëèæ÷îãî àòðàêòîðà øëÿõîì âèêîíàííÿ íåâåëè÷-
êèõ êðîê³â ó ð³çíèõ íàïðÿìêàõ. Öåé àëãîðèòì ÷àñòî ñëóãóº åòàëîíîì äëÿ
ïîð³âíÿííÿ ç ³íøèìè àëãîðèòìàìè. Òàêîæ çàïðîïîíîâàíèé àëãîðèòì òóðí³ðíîãî
âèòèñíåííÿ ç ãàóñîâîþ ìóòàö³ºþ ïîð³âíþºòüñÿ ç àëãîðèòìàìè äåòåðì³íîâàíîãî
òà éìîâ³ðí³ñíîãî âèòèñíåííÿ.
Ðîçãëÿíåìî îïòèì³çàö³éíó çàäà÷ó òàêîãî âèãëÿäó: çíàéòè
max ( ),f x x X R n� � , (1)
äå R n — ìíîæèíà n-âèì³ðíèõ ä³éñíèõ âåêòîð³â. Ìîæíà ïîêàçàòè, ùî ðîçâ’ÿçó-
âàííÿ äîâ³ëüíî¿ (â ò.÷. áàãàòîåêñòðåìàëüíî¿) îïòèì³çàö³éíî¿ çàäà÷³ âèãëÿäó (1)
çâîäèòüñÿ äî ðîçâ’ÿçóâàííÿ ãåíåòè÷íèì àëãîðèòìîì îïòèì³çàö³éíî¿ çàäà÷³ òàêî-
ãî âèãëÿäó: çíàéòè
max ( ),F s s S� , (2)
äå S — ìíîæèíà çàêîäîâàíèõ çíà÷åíü åëåìåíò³â x X� . Ïðè öüîìó áóäü-ÿêèé
äîïóñòèìèé ðîçâ’ÿçîê çàäà÷³ (2) íàçèâàºòüñÿ îñîáèíîþ ïîïóëÿö³¿. Îñîáèíè êî-
äóþòüñÿ ó âèãëÿä³ õðîìîñîì òà çà àíàëî㳺þ ç äâî¿ñò³ñòþ ãåíîòèïó òà ôåíîòè-
ïó æèâèõ îðãàí³çì³â ãîâîðÿòü ïðî ãåíîòèï (s) òà ôåíîòèï (x) îñîáèí ïîïó-
ëÿö³¿. Ö³ëüîâà ôóíêö³ÿ F íàçèâàºòüñÿ ôóíêö³ºþ ïðèñòîñîâàíîñò³ îñîáèí ïîïó-
ëÿö³¿, à çíà÷åííÿ ôóíêö³¿ ïðèñòîñîâàíîñò³ â òî÷ö³ s íàçèâàþòü êîåô³ö³ºíòîì
ïðèñòîñîâàíîñò³ â³äïîâ³äíî¿ îñîáèíè.
ÀËÃÎÐÈÒÌ ÒÓÐͲÐÍÎÃÎ ÂÈÒÈÑÍÅÍÍß Ç ÃÀÓÑÎÂÎÞ ÌÓÒÀÖ²ªÞ
Ó ïðîïîíîâàíîìó â ö³é ðîáîò³ ãåíåòè÷íîìó àëãîðèòì³ âèòèñíåííÿ çàñòîñî-
âóºòüñÿ êîäóâàííÿ â ä³éñíèõ ÷èñëàõ: ó õðîìîñîì³
�
�X x x x Rn
n� �( , , , )1 2
êîæíà ä³éñíà çì³ííà x Ri � ïðåäñòàâëÿº â³äïîâ³äíó ö³ëüîâó çì³ííó. Âèêîðèñòî-
âóºòüñÿ ñò³éêèé òèï ðåïðîäóêö³¿, ïðè÷îìó äî ïîðîäæåííÿ íàùàäê³â äîïóñêà-
þòüñÿ âñ³ îñîáèíè ïîïóëÿö³¿ (â³äá³ð áàòüê³â íå ïðîâîäèòüñÿ), à äëÿ â³äáîðó
îñîáèí ó íîâå ïîêîë³ííÿ çàñòîñîâóºòüñÿ äåòåðì³íîâàíèé òóðí³ðíèé â³äá³ð:
ïðîâîäÿòüñÿ òóðí³ðè ì³æ êîæíèì áàòüêîì òà âñ³ìà éîãî íàùàäêàìè, íàéêðàùà
îñîáèíà ïåðåõîäèòü ó íàñòóïíå ïîêîë³ííÿ. ²íøèìè ñëîâàìè, â íàñòóïíå ïî-
êîë³ííÿ ïðîõîäèòü íàéá³ëüø ïðèñòîñîâàíà îñîáèíà — áàòüêî àáî éîãî íàéêðà-
ùèé íàùàäîê.
Äëÿ ïîðîäæåííÿ íàùàäê³â âèêîðèñòîâóºòüñÿ ãàóñîâà ìóòàö³ÿ, ÿêà çì³íþº
çíà÷åííÿ êîæíîãî ãåíà êîæíî¿ õðîìîñîìè íà íîðìàëüíî ðîçïîä³ëåíó âèïàäêîâó
âåëè÷èíó
x x Ni i i� � ( , )0 � , (3)
äå N i ( , )0 � — ñòàíäàðòíà íîðìàëüíî ðîçïîä³ëåíà âèïàäêîâà âåëè÷èíà (î÷³êó-
âàííÿ 0, ñòàíäàðòíå â³äõèëåííÿ �). ßêùî ï³ñëÿ âèêîíàííÿ îïåðàòîðà ìóòàö³¿
ðåçóëüò³âíå çíà÷åííÿ ãåíà âèõîäèòü çà äîïóñòèì³ ìåæ³, éîãî îáð³çóþòü äî äî-
ïóñòèìîãî. Êðîñèíãîâåð äëÿ ïîðîäæåííÿ íàùàäê³â íå âèêîðèñòîâóºòüñÿ.
Íàâåäåìî çàãàëüíó ñõåìó àëãîðèòìó òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìó-
òàö³ºþ. Âîíà ì³ñòèòü òàê³ êðîêè.
1. Ãåíåðàö³ÿ ïî÷àòêîâî¿ ïîïóëÿö³¿ çà ð³âíîì³ðíèì ðîçïîä³ëîì.
2. Îá÷èñëåííÿ êîåô³ö³ºíòà ïðèñòîñîâàíîñò³ âñ³õ îñîáèí ïîïóëÿö³¿.
76 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
3. Ïîðîäæåííÿ L íàùàäê³â êîæíîþ îñîáèíîþ øëÿõîì çàñòîñóâàííÿ îïåðà-
òîðà ãàóñîâî¿ ìóòàö³¿ (3) äî êîæíîãî ãåíà îñîáèíè.
4. Îá÷èñëåííÿ êîåô³ö³ºíòà ïðèñòîñîâàíîñò³ îòðèìàíèõ íàùàäê³â.
5. Ôîðìóâàííÿ íîâî¿ ïîïóëÿö³¿ çà äîïîìîãîþ òóðí³ðíîãî â³äáîðó; ãðóïà äëÿ
êîæíîãî òóðí³ðó ôîðìóºòüñÿ ç áàòüêà òà óñ³õ éîãî íàùàäê³â.
6. Ïåðåõ³ä íà êðîê 3 àáî çàâåðøåííÿ ðîáîòè àëãîðèòìó.
Íàâåäåíà ñõåìà ïîòðåáóº óòî÷íåííÿ êðîêó 3: âèçíà÷åííÿ ïàðàìåòðà êðîêó
ìóòàö³¿ � . Íàäàë³ çàëåæíî â³ä ñïîñîáó éîãî âèçíà÷åííÿ ðîçãëÿäàòèìåìî òðè
âàð³àíòè àëãîðèòìó òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìóòàö³ºþ.
S1: àëãîðèòì ç îá÷èñëåííÿì � íà îñíîâ³ àíàë³çó ïî÷àòêîâî¿ ïîïóëÿö³¿. Ó öüî-
ìó âèïàäêó çíà÷åííÿ � âèçíà÷àºòüñÿ ÿê 1/ k â³ä ñåðåäíüî¿ â³äñòàí³ ì³æ îñîáèíàìè
ïî÷àòêîâî¿ ïîïóëÿö³¿, k �1 — ö³ëå ÷èñëî.
S2: àëãîðèòì ç ïåð³îäè÷íèì ïåðåîá÷èñëåííÿì �. Ó íüîìó çíà÷åííÿ � âèçíà-
÷àºòüñÿ ÿê 1/ k â³ä ñåðåäíüî¿ â³äñòàí³ ì³æ îñîáèíàìè ïîïåðåäíüî¿ ïîïóëÿö³¿, k �1 —
ö³ëå ÷èñëî. Îñê³ëüêè öåé âàð³àíò º äîñèòü ðåñóðñîºìíèì, òî ïåðåîá÷èñëåííÿ çíà÷åí-
íÿ � ìîæíà ïðîâîäèòè êîæí³ m ³òåðàö³é.
S.evol: àëãîðèòì ³ç ñàìîàäàïòèâíèì êåðóâàííÿì ïàðàìåòðîì � . ²äåþ ö³º¿
ìóòàö³¿ âçÿòî ç åâîëþö³éíèõ ñòðàòåã³é (íåêîðåëüîâàíà ìóòàö³ÿ ç n ðîçì³ðàìè êðî-
êó ìóòàö³¿ àáî ìóòàö³ÿ-2) [6]. Ó öüîìó âèïàäêó â õðîìîñîì³ ðàçîì ³ç çíà÷åííÿìè
ö³ëüîâèõ çì³ííèõ xi çáåð³ãàþòüñÿ çíà÷åííÿ ñòàíäàðòíèõ â³äõèëåíü � i , ÿê³ òàêîæ
åâîëþö³îíóþòü. ²íøèìè ñëîâàìè, îñîáèíà ïîïóëÿö³¿ ïðåäñòàâëÿºòüñÿ ïàðîþ
( , )
� �
X � , äå
�
�X x x x Rn
n� �( , , , )1 2 — âåêòîð ïàðàìåòð³â îá’ºêòà,
�
�� � ( , ,� �1 2
� , )� n
nR� � — âåêòîð ïàðàìåòð³â ñòðàòå㳿. Ìåõàí³çì 䳿 îïåðàòîðà ìóòàö³¿
çàäàºòüñÿ ó òàêèé ñïîñ³á:
� � � � � � � �i i iN Nexp ( ( , ) ( , ))0 1 0 1 ,
� � � � x x Ni i i i� ( , )0 1 .
Òóò N ( , )0 1 — ñòàíäàðòíà íîðìàëüíî ðîçïîä³ëåíà âèïàäêîâà âåëè÷èíà, ãåíå-
ðóºòüñÿ îäíà äëÿ êîæíîãî íàùàäêà; N i ( , )0 1 — ñòàíäàðòíà íîðìàëüíî ðîç-
ïîä³ëåíà âèïàäêîâà âåëè÷èíà, ãåíåðóºòüñÿ äëÿ êîæíî¿ çì³ííî¿ êîæíîãî íàùàä-
êà; �� òà � — â³äïîâ³äíî ñï³ëüíèé òà ïîêîîðäèíàòíèé êîåô³ö³ºíòè íàâ÷àííÿ.
ÀËÃÎÐÈÒÌÈ, ÎÁÐÀͲ ÄËß ÏÎвÂÍßÍÍß
Àëãîðèòì äåòåðì³íîâàíîãî âèòèñíåííÿ (deterministic crowding) [7] º îäíèì ç
íàéêðàùèõ ó êëàñ³ àëãîðèòì³â âèòèñíåííÿ [8–10] òà ÷àñòî âèêîðèñòîâóºòüñÿ
äëÿ ïîð³âíÿííÿ ç ³íøèìè àëãîðèòìàìè óòâîðåííÿ í³ø.
Àëãîðèòì éìîâ³ðí³ñíîãî âèòèñíåííÿ (probabilistic crowding) º ìîäèô³êàö³ºþ
àëãîðèòìó äåòåðì³íîâàíîãî âèòèñíåííÿ [11]. Éîãî ñóòü ïîëÿãຠó çàïîá³ãàíí³
âòðàò³ âèä³â, ñôîðìîâàíèõ íàâêîëî íèæ÷èõ ï³ê³â.
Ïàðàëåëüíèé àëãîðèòì ñõîäæåííÿ íà âåðøèíè (parallel hill-climbing) áóäåìî
ðîçãëÿäàòè ó âàð³àíò³, ïîäàíîìó â [7].
Âèá³ð ïàðàìåòð³â º îäí³ºþ ç íàéñêëàäí³øèõ ïðîáëåì ïðàêòè÷íîãî çàñòîñó-
âàííÿ ãåíåòè÷íèõ àëãîðèòì³â. Â³ä ¿õíüîãî âäàëîãî âèáîðó çàëåæèòü ÿê³ñòü çíàé-
äåíèõ àëãîðèòìîì ðîçâ’ÿçê³â òà øâèäê³ñòü ðîáîòè àëãîðèòìó. Çàçâè÷àé, ÷àñòèíó
ïàðàìåòð³â îáèðàþòü, êåðóþ÷èñü ïåâíèìè ðåêîìåíäàö³ÿìè àáî âëàñíèì
äîñâ³äîì, à ÷àñòèíó — íà îñíîâ³ ïîð³âíÿëüíîãî àíàë³çó ðåçóëüòàò³â ðîáîòè àëãî-
ðèòìó çà ð³çíèõ çíà÷åíü ïàðàìåòð³â (äëÿ öüîãî çáèðàþòü ñòàòèñòèêó,
´ðóíòóþ÷èñü íà ÷èñëåííèõ íåçàëåæíèõ ïðîãîíàõ àëãîðèòìó).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 77
Ïàðàìåòðè àëãîðèòì³â. Ïàðàìåòðè àëãîðèòìó òóðí³ðíîãî âèòèñíåííÿ ç ãà-
óñîâîþ ìóòàö³ºþ º òàêèìè.
L — ê³ëüê³ñòü íàùàäê³â îñîáèíè, ïîðîäæåíèõ ó ðåçóëüòàò³ çàñòîñóâàííÿ îïå-
ðàòîðà ìóòàö³¿; ï³äáèðàºòüñÿ åêñïåðèìåíòàëüíî (ðîçãëÿíóòî çíà÷åííÿ 1; 2; 3).
� — âèçíà÷åíèé âèùå ïàðàìåòð ìóòàö³¿. Çíà÷åííÿ 1/ k ï³äáèðàþòüñÿ åêñïå-
ðèìåíòàëüíî (ðîçãëÿíóòî çíà÷åííÿ1 2/ ;1 4/ ;1 8/ ;1 16/ ); ïðè öüîìó â àëãîðèòì³ S2
çíà÷åííÿ � ïåðåîá÷èñëþþòüñÿ êîæí³ 60 ³òåðàö³é. Ïî÷àòêîâ³ çíà÷åííÿ � i â àëãî-
ðèòì³ S.evol îá÷èñëþþòüñÿ ÿê N i ( , )0 � , äå � �1/ k â³ä ñåðåäíüî¿ â³äñòàí³ ì³æ îñî-
áèíàìè ïî÷àòêîâî¿ ïîïóëÿö³¿ (ðîçãëÿíóòî çíà÷åííÿ 1 2/ ; 1 4/ ; 1 8/ ; 1 16/ ). Çíà÷åííÿ
êîåô³ö³ºíò³â íàâ÷àííÿ â àëãîðèòì³ S.evol çàô³êñîâàíî òàê: � �
( )2 1N ,
� �
� ( )2 1N , äå N — ðîçì³ð ïîïóëÿö³¿.
Âèá³ð çíà÷åíü L òà � îá´ðóíòîâóºòüñÿ íàìàãàííÿì â³äíàéòè áàëàíñ ì³æ
øâèäê³ñòþ ðîáîòè àëãîðèòìó òà éîãî åôåêòèâí³ñòþ.
 àëãîðèòìàõ äåòåðì³íîâàíîãî òà éìîâ³ðí³ñíîãî âèòèñíåííÿ âèêîðèñòàíî:
á³íàðíå êîäóâàííÿ (êîä Ãðåÿ) âóçëàìè äèñêðåòèçàö³¿ ç òî÷í³ñòþ òðè çíàêè ï³ñëÿ
êîìè; â³äñòàíü Ãåìì³íãà äëÿ âèçíà÷åííÿ ñõîæîñò³ îñîáèí; îäíîòî÷êîâèé êðîñèíãî-
âåð. Äîäàòêîâî ï³ñëÿ çàñòîñóâàííÿ îïåðàòîðà êðîñèíãîâåðó äî íàùàäê³â çàñòîñî-
âóºòüñÿ îïåðàòîð ìóòàö³¿ ç ïàðàìåòðàìè Pm òà Rm — éìîâ³ðíîñòÿìè çàñòîñóâàííÿ
îïåðàòîðà ìóòàö³¿ äî çàäàíî¿ õðîìîñîìè òà äî êîæíîãî ãåíà çàäàíî¿ õðîìîìîìè
â³äïîâ³äíî; çíà÷åííÿ Pm òà Rm ï³äáèðàþòü åêñïåðèìåíòàëüíî.
Ïàðàìåòðè ïàðàëåëüíîãî àëãîðèòìó ñõîäæåííÿ íà âåðøèíè: ïî÷àòêîâå çíà-
÷åííÿ ðàä³óñà îêîëó 0.05; ì³í³ìàëüíå çíà÷åííÿ ðàä³óñà îêîëó 0.0001.
ßê â³äîìî, åêñïåðèìåíòàëüíèé àíàë³ç ñòîõàñòè÷íèõ (ó òîìó ÷èñë³ ãåíåòè÷-
íèõ) àëãîðèòì³â ´ðóíòóºòüñÿ íà àíàë³ç³ ñòàòèñòè÷íèõ äàíèõ, îòðèìàíèõ â ðåçóëü-
òàò³ áàãàòüîõ íåçàëåæíèõ ïðîãîí³â àëãîðèòì³â íà îäíàêîâèõ âõ³äíèõ äàíèõ. Âè-
çíà÷åí³ ç ö³ºþ ìåòîþ íàá³ð òåñòîâèõ ôóíêö³é òà êðèòå𳿠îö³íþâàííÿ àëãîðèòì³â
îïèñàíî äàë³.
Êðèòå𳿠ïîð³âíÿííÿ. Ïåðø í³æ óâîäèòè êðèòå𳿠îö³íþâàííÿ ÿêîñò³ ðîáîòè àë-
ãîðèòì³â, ñë³ä âèçíà÷èòè óìîâè çóïèíêè àëãîðèòì³â òà âàð³àíòè ðîçòàøóâàííÿ åëå-
ìåíò³â ô³íàëüíî¿ ïîïóëÿö³¿, çà ÿêèõ áóäåìî ââàæàòè, ùî øóêàíèé ìàêñèìóì çíàéäåíî.
Ïàðàëåëüíèé àëãîðèòì ñõîäæåííÿ íà âåðøèíè çóïèíÿº ðîáîòó, ÿêùî çíà÷åí-
íÿ ðàä³óñà îêîëó ñòຠìåíøèì çà 0.0001 àáî âèêîíàíî 20000000 îá÷èñëåíü
ôóíêö³¿ ïðèñòîñîâàíîñò³. Ãåíåòè÷íèé àëãîðèòì çóïèíÿº ðîáîòó â ðàç³ âñòàíîâ-
ëåííÿ éîãî çá³æíîñò³ (ñåðåäíº çíà÷åííÿ êîåô³ö³ºíòà ïðèñòîñîâàíîñò³ îñîáèí ïî-
ïóëÿö³¿ íå çì³íþºòüñÿ îñòàíí³ ï’ÿòü ïîêîë³íü á³ëüøå í³æ íà 0.0001) àáî çä³éñíåí-
íÿ 20000000 îá÷èñëåíü ôóíêö³¿ ïðèñòîñîâàíîñò³. ²íøèìè ñëîâàìè, ÿêùî
çá³æí³ñòü íå äîñÿãíóòà, ðîáîòó àëãîðèòìó çóïèíÿþòü ï³ñëÿ âèêîíàííÿ çàäàíî¿
ê³ëüêîñò³ îá÷èñëåíü ôóíêö³¿ ïðèñòîñîâàíîñò³.
Ìàêñèìóì çíàéäåíî, ÿêùî âñòàíîâëåíî çá³æí³ñòü àëãîðèòìó òà çíàéäåòüñÿ
õî÷à á îäíà îñîáèíà ô³íàëüíî¿ ïîïóëÿö³¿, êîåô³ö³ºíò ïðèñòîñîâàíîñò³ ÿêî¿ º íå
ìåíøèì çà � â³ä çíà÷åííÿ öüîãî ìàêñèìóìó, òà ÿêà ðîçòàøîâóºòüñÿ íà â³äñòàí³ íå
á³ëüøå í³æ � â³ä öüîãî ìàêñèìóìó. Ïîêëàäåìî � � 0.01, � � 0.01 äëÿ âñ³õ íàâåäå-
íèõ íèæ÷å ôóíêö³é, êð³ì ôóíêö³¿ F7 , òà � � 0.5 äëÿ ôóíêö³¿ F7 .
Óñ³ â³äîì³ àâòîðàì êðèòå𳿠îö³íþâàííÿ ÿêîñò³ çíàéäåíèõ àëãîðèòìîì ðîç-
â’ÿçê³â [6] âèçíà÷åí³ íà îñíîâ³ ïîð³âíÿííÿ çíà÷åíü òà ðîçòàøóâàííÿ ðåàëüíèõ
ìàêñèìóì³â ³ç çíàéäåíèìè àëãîðèòìîì ìàêñèìóìàìè. Ó äåÿêèõ êðèòåð³ÿõ äîäàò-
êîâî âèìàãàºòüñÿ êîíöåíòðàö³ÿ ïåâíîãî â³äñîòêó îñîáèí ïîïóëÿö³¿ â îêîëàõ øó-
êàíèõ ìàêñèìóì³â. Íà íàøó äóìêó, òàêèé ï³äõ³ä º ïðèéíÿòíèì ëèøå äëÿ çàäà÷
ïîøóêó ãëîáàëüíèõ ìàêñèìóì³â. ϳä ÷àñ àíàë³çó àëãîðèòì³â óòâîðåííÿ í³ø ¿õ
ñë³ä ïîð³âíþâàòè íå ëèøå çà ÿê³ñòþ çíàéäåíèõ ïîïóëÿö³ºþ â³äîìèõ ðîçâ’ÿçê³â,
78 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
àëå é çà ñïîñîáàìè âçàºìíîãî ðîçòàøóâàííÿ îñîáèí ô³íàëüíî¿ ïîïóëÿö³¿.
Àëãîðèòìè ç âåëèêîþ ê³ëüê³ñòþ õèáíèõ âèä³â (í³ø) — ñêóï÷åíü îñîáèí íå â äîñ-
òàòíüî ìàëèõ îêîëàõ ðåàëüíèõ ìàêñèìóì³â — ñë³ä ââàæàòè íàéã³ðøèìè ÷åðåç íå-
ìîæëèâ³ñòü ¿õíüîãî ïðàêòè÷íîãî âèêîðèñòàííÿ. Ó çâ’ÿçêó ç âèêëàäåíèì âèùå
íàìè çàïðîïîíîâàíî ÿâíî âèçíà÷àòè ìíîæèíó âèä³â, óòâîðåíèõ ô³íàëüíîþ
ïîïóëÿö³ºþ, òà îá÷èñëþâàòè äîäàòêîâ³ êðèòå𳿠îö³íþâàííÿ ê³ëüêîñò³ çíàéäåíèõ
àëãîðèòìîì õèáíèõ ï³ê³â.
Äëÿ âèçíà÷åííÿ ìíîæèíè ñôîðìîâàíèõ àëãîðèòìîì âèä³â, ÿêîþ âèçíà-
÷àºòüñÿ ìíîæèíà í³ø àáî ìîæëèâèõ ï³ê³â ôóíêö³¿ ïðèñòîñîâàíîñò³, àíàë³çóâàòè-
ìåìî ô³íàëüíó ïîïóëÿö³þ çà òàêèì àëãîðèòìîì:
1. Ïîêëàñòè Seeds � �.
2. Âèáðàòè íàéêðàùó íåîáðîáëåíó îñîáèíó ïîïóëÿö³¿ x ; ïîçíà÷èòè ¿¿ ÿê îá-
ðîáëåíó x� .
3. Ïîêëàñòè found � FALSE.
4. ßêùî çíàéäåòüñÿ îñîáèíà s Seeds� òàêà, ùî d x s( , )�
�, òî ïîêëàñòè
found � TRUE; ³íàêøå äîäàòè îñîáèíó x� äî ìíîæèíè ï³ê³â: ïîêëàñòè Seeds �
� �Seeds x�{ }.
5. ßêùî â ïîïóëÿö³¿ çàëèøèëèñÿ íåîáðîáëåí³ îñîáèíè, òî ïåðåéòè íà ï. 2.
Òóò Seeds — ìíîæèíà íàéêðàùèõ îñîáèí êîæíîãî âèäó; d x y( , ) — åâêë³äîâà
â³äñòàíü ì³æ îñîáèíàìè x òà y; ïàðàìåòð � � 0.01.
Î÷åâèäíî, ùî â çàãàëüíîìó âèïàäêó ìíîæèíà Seeds ìîæå ì³ñòèòè ÿê ðå-
àëüí³, òàê ³ õèáí³ ï³êè; äëÿ âèçíà÷åííÿ ðåàëüíèõ ï³ê³â åëåìåíòè ç Seeds ïîð³âíþ-
þòü ³ç ðåàëüíèìè ï³êàìè ç âèêîðèñòàííÿì ïàðàìåòð³â � òà � .
Äëÿ êîæíîãî ïðîãîíó àëãîðèòìó îá÷èñëþâàòèìåìî òàê³ êðèòåð³¿:
NFE (number of fitness function evaluations) — ê³ëüê³ñòü îá÷èñëåíü ôóíêö³¿
ïðèñòîñîâàíîñò³;
NSeeds (number of seeds) — ê³ëüê³ñòü ï³ê³â (ðåàëüíèõ òà õèáíèõ);
NP (number of peaks) — ê³ëüê³ñòü ðåàëüíèõ ï³ê³â;
GP (number of global peaks) — ê³ëüê³ñòü ðåàëüíèõ ãëîáàëüíèõ ï³ê³â;
LP (number of local peaks) — ê³ëüê³ñòü ðåàëüíèõ ëîêàëüíèõ ï³ê³â.
Î÷åâèäíî, ùî NP GP LP� � .
PR (peak ratio) — â³äíîøåííÿ ê³ëüêîñò³ çíàéäåíèõ àëãîðèòìîì ðåàëüíèõ
ï³ê³â äî çàãàëüíî¿ ê³ëüêîñò³ ï³ê³â, ÿê³ íåîáõ³äíî ëîêàë³çóâàòè.
GPR (global peak ratio) — â³äíîøåííÿ ê³ëüêîñò³ çíàéäåíèõ àëãîðèòìîì ðå-
àëüíèõ ãëîáàëüíèõ ï³ê³â äî çàãàëüíî¿ ê³ëüêîñò³ ãëîáàëüíèõ ï³ê³â, ÿê³ ïîòð³áíî ëî-
êàë³çóâàòè.
LPR (local peak ratio) — â³äíîøåííÿ ê³ëüêîñò³ çíàéäåíèõ àëãîðèòìîì ðåàëü-
íèõ ëîêàëüíèõ ï³ê³â äî çàãàëüíî¿ ê³ëüêîñò³ ëîêàëüíèõ ï³ê³â, ÿê³ íåîáõ³äíî ëî-
êàë³çóâàòè.
Îñê³ëüêè â çàãàëüíîìó âèïàäêó NSeeds NP� (àëãîðèòì çíàõîäèòü õèáí³
ï³êè), ââåäåìî òàêîæ êðèòåð³é îö³íþâàííÿ ê³ëüêîñò³ õèáíèõ ï³ê³â.
FPR (fake peak ratio) — ÷àñòêà õèáíèõ ï³ê³â — â³äíîøåííÿ ê³ëüêîñò³ õèáíèõ
ï³ê³â äî çàãàëüíî¿ ê³ëüêîñò³ ñôîðìîâàíèõ àëãîðèòìîì í³ø: FPR
NSeeds NP
NSeeds
�
.
Î÷åâèäíî, 0
PR , FPR
1; àëãîðèòì º êðàùèì çà á³ëüøèõ çíà÷åíü PR òà çà
ìåíøèõ çíà÷åíü FPR.
Äëÿ àíàë³çó àëãîðèòì³â îá÷èñëþâàòèìåìî óñåðåäíåí³ çà âñ³ìà ïðîãîíàìè
çíà÷åííÿ íàâåäåíèõ êðèòåð³¿â.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 79
Òåñòîâ³ ôóíêö³¿. Äëÿ åêñïåðèìåíòàëüíîãî àíàë³çó àëãîðèòì³â îáðàíî òàê³
òåñòîâ³ ôóíêö³¿ [6].
1. Ôóíêö³ÿ îäíàêîâèõ ìàêñèìóì³â (òåñòîâà ôóíêö³ÿ Äåáà 1)
F x x x
n
xn
i
n
i1 1 2
1
61
5( , , , ) sin ( )� �
�
� � , 0 1
xi , i n�1, ,
ìຠ5n ãëîáàëüíèõ ìàêñèìóì³â, ùî çíàõîäÿòüñÿ íà îäíàêîâ³é â³äñòàí³ îäèí â³ä
îäíîãî.
2. Ôóíêö³ÿ ñïàäàþ÷èõ ìàêñèìóì³â (òåñòîâà ôóíêö³ÿ Äåáà 2)
F x x x
x
n
i
2 1 2
2
2 2
0 1
0 8
( , , , ) exp (ln )
.
.
� �
�
�
��
�
�
��
�
�
�
��
�
�
�
���
� sin ( )6
1
5�xi
i
n
, 0 1
xi , i n�1, ,
ìຠ5n ìàêñèìóì³â ð³çíî¿ âèñîòè, ðîçòàøîâàíèõ íà îäíàêîâ³é â³äñòàí³ îäèí
â³ä îäíîãî.
3. Ôóíêö³ÿ íåð³âíîì³ðíèõ ìàêñèìóì³â (òåñòîâà ôóíêö³ÿ Äåáà 3)
F x x x
n
xn i
i
n
3 1 2
6 0 75
1
1
5 0 05( , , , ) sin ( ( . )).
� �
�
� � , 0 1
xi , i n�1, ,
ìຠ5n ãëîáàëüíèõ ìàêñèìóì³â, ùî çíàõîäÿòüñÿ íà ð³çíèõ â³äñòàíÿõ îäèí â³ä
îäíîãî, ïðè÷îìó â³äñòàí³ ì³æ òî÷êàìè ìàêñèìóì³â çðîñòàþòü ³ç çá³ëüøåííÿì
çíà÷åííÿ àðãóìåíòó.
4. Ôóíêö³ÿ íåð³âíîì³ðíèõ ñïàäàþ÷èõ ìàêñèìóì³â (òåñòîâà ôóíêö³ÿ Äåáà 4)
F x x x
x
n
i
4 1 2
2
2 2
0 08
0 854
( , , , ) exp (ln )
.
.
� �
�
�
��
�
�
��
�
�
�
��
�
�
�
��
�
� sin ( ( . )).6 0 75
1
5 0 05� xi
i
n
,
0 1
xi , i n�1, ,
ìຠ5n ìàêñèìóì³â ð³çíî¿ âèñîòè, ðîçòàøîâàíèõ íà ð³çíèõ â³äñòàíÿõ îäèí â³ä
îäíîãî, ïðè÷îìó â³äñòàí³ ì³æ òî÷êàìè ìàêñèìóì³â çðîñòàþòü ³ç çá³ëüøåííÿì
çíà÷åííÿ àðãóìåíòó.
Äëÿ âñ³õ ÷îòèðüîõ ôóíêö³é â³äîìèìè º ðîçòàøóâàííÿ òà çíà÷åííÿ âñ³õ ìàê-
ñèìóì³â.
Íàá³ð òåñòîâèõ ôóíêö³é Äåáà º îäíèì ç íàéïîøèðåí³øèõ äëÿ àíàë³çó àëãî-
ðèòì³â ðîçâ’ÿçàííÿ çàäà÷ áàãàòîåêñòðåìàëüíî¿ îïòèì³çàö³¿. Äëÿ ïîð³âíÿëüíîãî
àíàë³çó ðîáîòè àëãîðèòì³â âèêîðèñòîâóâàòèìåìî òàêîæ ïîäàí³ íèæ÷å ôóíêö³¿.
5. Ôóíêö³ÿ Ðàñòðèã³íà
F x x x x x nn i i
i
n
5 1 2
2
1
10 2 10( , , , ) ( cos ( ) )� �
�
� � ,
5 12. xi 5.12, i n�1, .
¯¿ êîíòóð ñêëàäàºòüñÿ ç âåëèêî¿ ê³ëüêîñò³ ëîêàëüíèõ ìàêñèìóì³â, çíà÷åííÿ
ÿêèõ ñïàäàþòü ³ç çá³ëüøåííÿì â³äñòàí³ â³ä ãëîáàëüíîãî ìàêñèìóìó. Òàêà
ôóíêö³ÿ ìຠ10n ëîêàëüíèõ òà îäèí ãëîáàëüíèé ìàêñèìóì.
6. Ôóíêö³ÿ Ãð³âàíãà
F x x x n
x x
i
n
i i
i
n
i
n
6 1 2
2
11 4000
1( , , , ) cos� �
�
�
��
�
�
�� �
��
��
�
�
�
�
�
�
�
�
,
600 600xi , i n�1, .
80 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
Âîíà ìຠîäèí ãëîáàëüíèé òà áàãàòî ëîêàëüíèõ ìàêñèìóì³â, ïðè÷îìó ëîêàëüí³
ìàêñèìóìè º ðåãóëÿðíî ðîçïîä³ëåíèìè òà ¿õí³ çíà÷åííÿ ñïàäàþòü ³ç çá³ëüøåí-
íÿì â³äñòàí³ â³ä ãëîáàëüíîãî ìàêñèìóìó.
7. Ôóíêö³ÿ ñïèíè øåñòèãîðáîãî âåðáëþäà (òåñòîâà ôóíêö³ÿ Óðñåìà 3)
F x x x
x
x x x x x7 1 2 1
2 1
4
1
2
1 2 2
24 2 1
3
4 1( , ) . ( )�
�
�
�
�
�
�
�
�
�
� �
2
2 )
�
�
�
��
�
�
�
��
,
3 31x ,
2 22x ,
ìຠäâà ãëîáàëüíèõ òà ÷îòèðè ëîêàëüíèõ ìàêñèìóìè.
8. Ôóíêö³ÿ Õ³í-Øè ßíãà 2
F x x x x x x8 1 2 1 2 1
2
2
2( , ) (| | | | )exp ( )� �
,
10 101 2x x, ,
ìຠ÷îòèðè ãëîáàëüí³ ìàêñèìóìè, ðîçòàøîâàí³ íà íåçíà÷í³é â³äñòàí³ îäèí â³ä
îäíîãî.
ÅÊÑÏÅÐÈÌÅÍÒÀËÜÍÈÉ ÀÍÀË²Ç ÀËÃÎÐÈÒ̲Â
Àíàë³ç àëãîðèòì³â ïðîâåäåíî îêðåìî äëÿ çàäà÷³ ïîøóêó âñ³õ ëîêàëüíèõ òà
ãëîáàëüíèõ ìàêñèìóì³â (çàäà÷à 1) òà çàäà÷³ ïîøóêó âñ³õ ãëîáàëüíèõ ìàêñè-
ìóì³â (çàäà÷à 2), ïðè÷îìó ðîçãëÿíóòî îêðåìî âèïàäêè íàÿâíîñò³ â ö³ëüîâ³é
ôóíêö³¿ áàãàòüîõ ãëîáàëüíèõ òà, ìîæëèâî, ëîêàëüíèõ ìàêñèìóì³â (çàäà÷à 2.1)
òà íàÿâíîñò³ â ö³ëüîâ³é ôóíêö³¿ ò³ëüêè îäíîãî ãëîáàëüíîãî òà áàãàòüîõ ëîêàëü-
íèõ ìàêñèìóì³â (çàäà÷à 2.2).
Óñ³ ðîçãëÿíóò³ àëãîðèòìè ðåàë³çîâàíî ïðîãðàìíî; ÿê ïëàòôîðìó ðîçðîáëåí-
íÿ ïðîãðàìíîãî çàñòîñóíêó îáðàíî MATLAB.
Äëÿ îö³íþâàííÿ åôåêòèâíîñò³ àëãîðèòì³â äëÿ êîæíîãî íàáîðó âõ³äíèõ äàíèõ
âèêîíàíî ïî 10 ïðîãîí³â âñ³õ àëãîðèòì³â. ³äçíà÷èìî, ùî i-é ïðîã³í êîæíîãî àë-
ãîðèòìó ìຠñï³ëüíó ñòàðòîâó òî÷êó: âèïàäêîâî çãåíåðîâàíà ïî÷àòêîâà ïîïó-
ëÿö³ÿ º îäíàêîâîþ äëÿ âñ³õ àëãîðèòì³â íà â³äïîâ³äíîìó ïðîãîí³. Ðîçì³ð ïîïó-
ëÿö³¿ N � 500.
Äëÿ âèçíà÷åííÿ îïòèìàëüíîãî íàáîðó ïàðàìåòð³â êîæíîãî ç àëãîðèòì³â
ñôîðìîâàíî òàê³ òåñòîâ³ íàáîðè ôóíêö³é çàëåæíî â³ä êëàñó çàäà÷³.
Çàäà÷à 1, òåñòîâèé íàá³ð T1 âêëþ÷ຠôóíêö³¿ Äåáà 1, Äåáà 2, Äåáà 3, Äåáà 4.
Çàäà÷à 2.1, òåñòîâèé íàá³ð T21 ì³ñòèòü ôóíêö³¿ Äåáà 1, Äåáà 3.
Çàäà÷à 2.2, òåñòîâèé íàá³ð T22 âêëþ÷ຠôóíêö³¿ Äåáà 2, Äåáà 4.
Åêñïåðèìåíòè ïðîâîäèëèñü äëÿ òåñòîâèõ ôóíêö³é ðîçì³ðíîñòåé n �1 2 3, , .
Óñ³ òðè âàð³àíòè S1, S2, S3 àëãîðèòìó òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìó-
òàö³ºþ ïîêàçàëè íàéêðàù³ ðåçóëüòàòè äëÿ L � 3, 1 1 16/ /k � . Çàãàëîì ñïîñ-
òåð³ãàºòüñÿ òåíäåíö³ÿ äî ïîêðàùåííÿ ðîáîòè öüîãî àëãîðèòìó (çá³ëüøåííÿ PR,
çìåíøåííÿ FPR) ÿê ó ðàç³ çá³ëüøåííÿ ê³ëüêîñò³ íàùàäê³â L, òàê ³ â ðàç³ çìåíøåí-
íÿ çíà÷åííÿ � . Òàêîæ, ÿê ³ î÷³êóâàëîñÿ, ñïîñòåð³ãàºòüñÿ ïîã³ðøåííÿ ðîáîòè àëãî-
ðèòìó ³ç çá³ëüøåííÿì ðîçì³ðíîñò³ çàäà÷³: çìåíøóºòüñÿ ê³ëüê³ñòü çíàéäåíèõ àëãî-
ðèòìîì ðåàëüíèõ ï³ê³â, çðîñòຠê³ëüê³ñòü õèáíèõ ï³ê³â.
Íàäàë³ ïîñèëàòèìåìîñü íà ðîçãëÿíóò³ àëãîðèòìè çà ïåðøèìè áóêâàìè ¿õí³õ
íàçâ àíãë³éñüêîþ ìîâîþ: TCGM_S1, TCGM_S2, TCGM_S3 — â³äïîâ³äíî
âàð³àíòè S1, S2, S3 àëãîðèòì³â òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìóòàö³ºþ,
PHC — àëãîðèòì ïàðàëåëüíîãî ñõîäæåííÿ íà âåðøèíè, DC — àëãîðèòì äåòåð-
ì³íîâàíîãî âèòèñíåííÿ, PC — àëãîðèòì éìîâ³ðí³ñíîãî âèòèñíåííÿ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 81
82 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
Ò à á ë è ö ÿ 1. Ðåçóëüòàòè åêñïåðèìåíò³â: àëãîðèòì TCGM_S2, òåñòîâèé íàá³ð T1
Ïàðàìåòðè Êðèòåð³¿
L 1 / k NFE PR GPR LPR FPR
1 0.5 436792 0.5860 0.6919 0.2289 0.5420
2 0.5 601813 0.5493 0.7395 0.1649 0.4286
3 0.5 786983 0.5347 0.8099 0.1313 0.3548
1 0.25 470917 0.6611 0.7180 0.2992 0.5266
2 0.25 694388 0.6787 0.7967 0.2956 0.3948
3 0.25 823850 0.6884 0.8507 0.2924 0.3292
1 0.125 360767 0.7503 0.7304 0.3784 0.4261
2 0.125 594838 0.8017 0.7566 0.4038 0.3344
3 0.125 825733 0.8314 0.8321 0.4159 0.2896
1 0.0625 249708 0.8939 0.8373 0.4405 0.2636
2 0.0625 314463 0.9361 0.8461 0.4658 0.1989
3 0.0625 380167 0.9563 0.8908 0.4744 0.1538
Ò à á ë è ö ÿ 2 . Ðåçóëüòàòè åêñïåðèìåíò³â: àëãîðèòì TCGM_S2, ôóíêö³ÿ F2 , n �1
Ïàðàìåòðè Êðèòåð³¿
L 1 / k NFE Seeds NP GP LP PR GPR LPR FPR
1 0.5 205600 4.3 4.3 1 3.3 0.86 1 0.825 0
2 0.5 160700 2.9 2.9 1 1.9 0.58 1 0.475 0
3 0.5 157100 2.2 2.2 1 1.2 0.44 1 0.3 0
1 0.25 301200 5.9 5 1 4 1 1 1 0.1405
2 0.25 317150 5.1 5 1 4 1 1 1 0.0167
3 0.25 251900 5 5 1 4 1 1 1 0
1 0.125 112300 5 5 1 4 1 1 1 0
2 0.125 115700 5 5 1 4 1 1 1 0
3 0.125 117300 5 5 1 4 1 1 1 0
1 0.0625 77800 5 5 1 4 1 1 1 0
2 0.0625 77000 5 5 1 4 1 1 1 0
3 0.0625 82700 5 5 1 4 1 1 1 0
Ò à á ë è ö ÿ 3. Ðåçóëüòàòè åêñïåðèìåíò³â: àëãîðèòì TCGM_S2, ôóíêö³ÿ F2 , n � 3
Ïàðàìåòðè Êðèòåð³¿
L 1 / k NFE Seeds NP GP LP PR GPR LPR FPR
1 0.5 668400 381.1 2.5 0 2.5 0.02 0 0.0202 0.9935
2 0.5 1065500 277.4 4.8 0.2 4.6 0.0384 0.2 0.0379 0.9825
3 0.5 1703700 179.4 8.2 0.7 7.5 0.0656 0.7 0.0605 0.9527
1 0.25 696500 364.5 7.2 0.2 7 0.0576 0.2 0.0565 0.9795
2 0.25 1362200 229.6 14 0.6 13.4 0.112 0.6 0.1081 0.9372
3 0.25 1742700 181.3 14.8 0.7 14.1 0.1184 0.7 0.1137 0.9144
1 0.125 719800 375.8 19.8 0.1 19.7 0.1584 0.1 0.1589 0.9467
2 0.125 1210550 295 34.6 0.2 34.4 0.2768 0.2 0.2774 0.8777
3 0.125 1875100 221.7 47.9 0.8 47.1 0.3832 0.8 0.3798 0.7789
1 0.0625 443200 262.8 67.7 0.2 67.5 0.5416 0.2 0.5446 0.7397
2 0.0625 615500 198.5 90.9 0.3 90.6 0.7272 0.3 0.7307 0.5358
3 0.0625 734700 175.3 99.3 0.5 98.8 0.7944 0.5 0.7968 0.4299
Çàçíà÷èìî, ùî ó òàáë. 1–11 äëÿ âñ³õ êðèòåð³¿â íàâåäåíî óñåðåäíåí³ (ñåðåäí³) çíà-
÷åííÿ ïî âñ³õ ïðîãîíàõ. Ó òàáë. 1 ïîäàíî ðåçóëüòàòè îá÷èñëåííÿ öèõ çíà÷åíü íà ð³çíèõ
íàáîðàõ ïàðàìåòð³â äëÿ âñ³õ ôóíêö³é ç òåñòîâîãî íàáîðó T1 äëÿ àëãîðèòìó TCGM_S2
òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìóòàö³ºþ. Òàáë. 2 òà 3 ³ëþñòðóþòü ðîáîòó öüîãî àë-
ãîðèòìó äëÿ ôóíêö³¿ F2 ðîçì³ðíîñòåé n �1 òà n � 3 â³äïîâ³äíî. ²ç òàáë. 3 âèïëèâàº, ùî
àëãîðèòì òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìóòàö³ºþ íå çàâæäè íàäຠïåðåâàãó ãëî-
áàëüíèì îïòèìóìàì (ìîæóòü áóòè ñôîðìîâàí³ í³ø³ íàâêîëî ëîêàëüíèõ îïòèìóì³â,
ïðè öüîìó ãëîáàëüíèé îïòèìóì çíàéäåíèé íå áóäå).
Àëãîðèòì äåòåðì³íîâàíîãî âèòèñíåííÿ ïîêàçàâ íàéêðàù³ ðåçóëüòàòè çà òà-
êèõ çíà÷åíü ïàðàìåòð³â: Pm � 0.7, Rm � 0.3.  ö³ëîìó àëãîðèòì õàðàêòåðèçóºòüñÿ
äóæå íèçüêèì â³äñîòêîì õèáíèõ ï³ê³â, ùî º áåçñóìí³âíîþ éîãî ïåðåâàãîþ. Âîä-
íî÷àñ çà íàÿâíîñò³ ëîêàëüíèõ ï³ê³â â³í ó á³ëüøîñò³ âèïàäê³â çíàõîäèòü ëèøå îäèí
ëîêàëüíèé ï³ê àáî íå çíàõîäèòü ¿õ âçàãàë³. Àëãîðèòì çàâæäè â³ääຠïåðåâàãó ãëî-
áàëüíîìó ï³êó: íà â³äì³íó â³ä àëãîðèòìó òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìó-
òàö³ºþ â³í çàâæäè ôîðìóº í³øó íàâêîëî õî÷à á îäíîãî ãëîáàëüíîãî ï³êó.
Àëãîðèòì éìîâ³ðí³ñíîãî âèòèñíåííÿ íå äàâ ïðèéíÿòíèõ ðåçóëüòàò³â íà æîä-
íîìó íàáîð³ ïàðàìåòð³â. Õî÷à â³í ³ çíàõîäèòü áëèçüêî 40% ï³ê³â íà ñâî¿õ íàéêðà-
ùèõ êîíô³ãóðàö³ÿõ, àëå õàðàêòåðèçóºòüñÿ íàäçâè÷àéíî âåëèêîþ (ïîíàä 90%)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 83
Ò à á ë è ö ÿ 4. Ðåçóëüòàòè åêñïåðèìåíò³â: àëãîðèòì ÐÑ, òåñòîâèé íàá³ð T1
Ïàðàìåòðè Êðèòåð³¿
Pm Rm NFE PR GPR LPR FPR
0.1 0.1 1402625 0.1737 0.4865 0.0336 0.8950
0.1 0.2 1381592 0.2135 0.5115 0.0372 0.9052
0.1 0.3 1423467 0.2502 0.5766 0.0309 0.9139
0.3 0.1 1457358 0.2430 0.5797 0.0505 0.9192
0.3 0.2 2172325 0.3216 0.6117 0.0676 0.9327
0.3 0.3 2574675 0.4101 0.6283 0.1031 0.9343
0.5 0.1 2051800 0.2861 0.5422 0.0653 0.9324
0.5 0.2 2163658 0.3809 0.5111 0.1017 0.9441
0.5 0.3 1986567 0.4354 0.5097 0.1461 0.9478
0.7 0.1 1796850 0.2894 0.4778 0.0658 0.9418
0.7 0.2 2111642 0.4128 0.4821 0.1364 0.9522
0.7 0.3 2160133 0.4123 0.4548 0.1362 0.9553
Ðèñ. 1. ͳø³, çíàéäåí³ àëãîðèòìîì ÐÑ, ôóíêö³ÿ
Äåáà 1, n � 1
Ðèñ. 2. ͳø³, çíàéäåí³ àëãîðèòìîì ÐÑ, ôóíêö³ÿ
Äåáà 4, n � 1
x1
F1
x1
F4
ê³ëüê³ñòþ õèáíèõ ï³ê³â, äî òîãî æ ìຠâèñîêó ñêëàäí³ñòü (âèñîêå çíà÷åííÿ ïîêàç-
íèêà NFE). ßê ³ëþñòðàö³þ íàâåäåíî òàáë. 4 ç ðåçóëüòàòàìè îá÷èñëåííÿ óñåðåäíå-
íèõ çíà÷åíü êðèòåð³¿â íà ð³çíèõ íàáîðàõ ïàðàìåòð³â äëÿ âñ³õ ôóíêö³é ç òåñòîâîãî
íàáîðó T1. Ùå îäí³ºþ ³ëþñòðàö³ºþ º ðèñ. 1 òà ðèñ. 2, íà ÿêèõ êðóæå÷êàìè ïîçíà-
÷åíî çíàéäåí³ àëãîðèòìîì í³ø³ (Seeds) äëÿ ôóíêö³é F1 òà F4 , n �1, çà êîíô³ãó-
ðàö³¿ Pm � 0.5, Rm � 0.3 (ó ñåðåäíüîìó çà âñ³ìà ïðîãîíàìè öÿ êîíô³ãóðàö³ÿ äàº
íàéêðàùå çíà÷åííÿ êðèòåð³þ PR � 0.4354).
ϳäñóìîâóþ÷è ñêàçàíå, âèïèøåìî ðåêîìåíäîâàí³ íàáîðè ïàðàìåòð³â àëãî-
ðèòì³â äëÿ ðîçãëÿíóòèõ çàäà÷. Óñ³ òðè âàð³àíòè ðîçðîáëåíîãî àëãîðèòìó âèòèñ-
íåííÿ ç ãàóñîâîþ ìóòàö³ºþ ìàþòü òàê³ ïàðàìåòðè: äëÿ çàäà÷ 1 ³ 2.1 L � 3,
1 1 16/ /k � ; äëÿ çàäà÷³ 2.2 L � 3, 1 1 16/ /k � , 1 1 4/ /k � , 1 1 8/ /k � â³äïîâ³äíî äëÿ
âàð³àíò³â S1, S2, S3 öüîãî àëãîðèòìó. Ïàðàìåòðè àëãîðèòìó äåòåðì³íîâàíîãî âè-
òèñíåííÿ º îäíàêîâèìè äëÿ âñ³õ òðüîõ çàäà÷: Pm � 0.7, Rm � 0.3. Àëãîðèòì
éìîâ³ðí³ñíîãî âèòèñíåííÿ ìຠòàê³ ïàðàìåòðè: Pm � 0.5, Rm � 0.3 (äëÿ çàäà÷³ 1);
Pm � 0.3, Rm � 0.3 (äëÿ çàäà÷³ 2.1); Pm � 0.3, Rm � 0.1 (äëÿ çàäà÷³ 2.2).
ÏÎвÂÍßËÜÍÈÉ ÀÍÀË²Ç ÀËÃÎÐÈÒ̲Â
Ó òàáë. 5 ïîäàíî óñåðåäíåí³ çíà÷åííÿ êðèòåð³¿â, îá÷èñëåí³ çà ðåçóëüòàòàìè ïðî-
ãîí³â âñ³õ äîñë³äæóâàíèõ àëãîðèòì³â íà òåñòîâîìó íàáîð³ T1. Ìîæíà ñòâåðäæóâà-
òè, ùî ï³ä ÷àñ ðîçâ’ÿçóâàííÿ çàäà÷³ ïîøóêó âñ³õ (ãëîáàëüíèõ, ëîêàëüíèõ) ìàêñè-
ìóì³â íàéêðàùå çàðåêîìåíäóâàëè ñåáå àëãîðèòìè PHC, TCGM_S2 ³ TCGM_S1.
Àëãîðèòì DC äຠíåïîãàí³ ðåçóëüòàòè ïîøóêó ãëîáàëüíèõ ìàêñèìóì³â, àëå
â³äñîòîê çíàõîäæåííÿ ëîêàëüíèõ ìàêñèìóì³â º íåäîïóñòèìî ìàëèì. PC º íàé-
ã³ðøèì ñåðåä ðîçãëÿíóòèõ àëãîðèòì³â. ³í õàðàêòåðèçóºòüñÿ äîñèòü íåâèñîêèì
çíà÷åííÿì êðèòåð³þ PR, âåëèêîþ ñêëàäí³ñòþ òà íàäçâè÷àéíî âèñîêîþ ðîçïîðî-
øåí³ñòþ îñîáèí ô³íàëüíî¿ ïîïóëÿö³¿ â ïîøóêîâîìó ïðîñòîð³: ê³ëüê³ñòü õèáíèõ
ï³ê³â º íàäçâè÷àéíî âåëèêîþ (FPR � 0.9). Ó çâ’ÿçêó ç öèì àëãîðèòì PC áóëî âè-
ëó÷åíî ç ïîäàëüøîãî ðîçãëÿäó. Ïðîòå ñâ ìåòè — çàïîá³ãàííÿ âòðàò³ íèæ÷èõ
ï³ê³â íà êîðèñòü âèùèõ — öåé àëãîðèòì äîñÿã: çíà÷åííÿ êðèòåð³þ LPR äëÿ
íüîãî º âèùèì çà â³äïîâ³äíå çíà÷åííÿ äëÿ àëãîðèòìó DC.
84 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
Ò à á ë è ö ÿ 5. Ïîð³âíÿííÿ àëãîðèòì³â äëÿ çàäà÷³ 1, òåñòîâèé íàá³ð T1
Àëãîðèòì
Êðèòåð³¿
NFE PR GPR LPR FPR
PHC 39127 0.9881 0.9525 0.4942 0.1040
DC 77233 0.3915 0.8235 0.0323 0.0188
PC 1986567 0.4354 0.5097 0.1461 0.9478
TCGM_S1 401600 0.9559 0.9243 0.4735 0.1515
TCGM_S2 380167 0.9563 0.8908 0.4744 0.1538
TCGM_S3 564433 0.8054 0.7801 0.4005 0.9093
Ò à á ë è ö ÿ 6. Ïîð³âíÿííÿ àëãîðèòì³â äëÿ çàäà÷³ 1, ôóíêö³ÿ F7
Àëãîðèòì
Êðèòåð³¿
NFE NSeeds NP GP LP PR GPR LPR FPR
PHC 63826 6 6 2 4 1 1 1 0
DC 73900 2 2 2 0 0.3333 1 0 0
TCGM_S1 541700 5.7 5.7 2 3.7 0.95 1 0.925 0
TCGM_S2 319300 6 6 2 4 1 1 1 0
TCGM_S3 3855700 8.1 6 2 4 1 1 1 0.2367
Îñê³ëüêè òåñòîâèé íàá³ð Ò1 âèêî-
ðèñòîâóâàâñÿ äëÿ íàëàøòóâàííÿ ïàðà-
ìåòð³â ãåíåòè÷íèõ àëãîðèòì³â, ¿õíþ ðî-
áîòó áóëî äîäàòêîâî ïåðåâ³ðåíî íà
ôóíêö³¿ F7 . Öÿ ôóíêö³ÿ ìຠäâà ãëî-
áàëüí³ ³ ÷îòèðè ëîêàëüí³ ìàêñèìóìè òà
º îäí³ºþ ç íàéïîøèðåí³øèõ äëÿ
ïîð³âíÿëüíîãî àíàë³çó ãåíåòè÷íèõ àëãî-
ðèòì³â óòâîðåííÿ í³ø. ßê âèäíî
ç òàáë. 6, àëãîðèòìàìè-ïåðåìîæöÿìè
çíîâó ñòàëè àëãîðèòìè PHC òà
TCGM_S2: âîíè çíàéøëè âñ³ øóêàí³
ìàêñèìóìè, ïðè÷îìó âñ³ îñîáèíè
ô³íàëüíî¿ ïîïóëÿö³¿ ñêîíöåíòðóâàëèñÿ
íàâêîëî ï³ê³â ôóíêö³¿ (FPR � 0); òèïîâèé ðåçóëüòàò ïðîãîíó àëãîðèòìó TCGM_S2
ïîäàíî íà ðèñ. 3.
³äîìî [7], ùî àëãîðèòì PHC äຠíåïîãàí³ ðåçóëüòàòè íà íåñêëàäíèõ
ôóíêö³ÿõ. Áóëî ïðîâåäåíî éîãî ïîð³âíÿííÿ ç àëãîðèòìàìè TCGM_S2 òà
TCGM_S1 íà ñêëàäí³é ôóíêö³¿ F8 . Öÿ ôóíêö³ÿ ìຠ÷îòèðè îäíàêîâèõ ìàêñèìó-
ìè, ðîçòàøîâàíèõ íà íåçíà÷í³é â³äñòàí³ îäèí â³ä îäíîãî. Ç òàáë. 7 âèäíî, ùî àë-
ãîðèòì TCGM_S2 äàâ íàéêðàù³ ðåçóëüòàòè: â á³ëüøîñò³ ïðîãîí³â â³í çíàéøîâ
òðè ç ÷îòèðüîõ ï³ê³â, òîä³ ÿê àëãîðèòì PHC ãðóïóº ïîïóëÿö³þ íàâêîëî îäíîãî
ï³êó. Çíàéäåí³ öèìè àëãîðèòìàìè ï³êè ôóíêö³¿ F8 çîáðàæåíî íà ðèñ. 4 òà ðèñ. 5.
²ç ñêàçàíîãî âèïëèâàº, ùî äëÿ ðîçâ’ÿçóâàííÿ çàäà÷³ ïîøóêó âñ³õ (ãëîáàëü-
íèõ, ëîêàëüíèõ) ìàêñèìóì³â áàãàòîåêñòðåìàëüíî¿ ôóíêö³¿ ñë³ä ðåêîìåíäóâàòè
àëãîðèòì TCGM_S2, à äëÿ ïðîñòèõ çàäà÷ — àëãîðèòì PHC ÿê á³ëüø øâèäêèé.
Àíàë³ç òàáë. 8 òà â³äïîâ³äíèõ êðèòåð³¿â ç òàáë. 6 òà 7 ïîêàçóº, ùî ö³ àëãîðèòìè
ìîæíà ðåêîìåíäóâàòè òàêîæ äëÿ ðîçâ’ÿçóâàííÿ çàäà÷³ çíàõîäæåííÿ âñ³õ ãëîáàëü-
íèõ ìàêñèìóì³â, ÿêùî ö³ëüîâà ôóíêö³ÿ ìຠ¿õ äåê³ëüêà (òà, ìîæëèâî, ìàº
ëîêàëüí³ ìàêñèìóìè).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 85
Ðèñ. 3. ͳø³, çíàéäåí³ àëãîðèòìîì TCGM_S2,
ôóíêö³ÿ F7
Òàáëèöÿ 7. Ïîð³âíÿííÿ àëãîðèòì³â äëÿ çàäà÷³ 1, ôóíêö³ÿ F8
Àëãîðèòì
Êðèòåð³¿
NFE NSeeds NP GP� PR GPR�
PHC 51800 1 1 0.25
TCGM_S1 86200 9.4 2.7 0.675
TCGM_S2 77900 9.3 2.9 0.725
Ðèñ. 4. ϳêè ôóíêö³¿ F8, çíàéäåí³ àëãîðèòìîì
TCGM_S2
Ðèñ. 5. ϳêè ôóíêö³¿ F8, çíàéäåí³ àëãîðèòìîì
PHC
F8
x1
x2
F8
x2 x1
F4
F7
x2 x1
Ç òàáë. 9 âèäíî, ùî íàéêðàùèì àëãîðèòìîì äëÿ ðîçâ’ÿçóâàííÿ çàäà÷³ ïîøóêó
âñ³õ ãëîáàëüíèõ ìàêñèìóì³â çà óìîâè íàÿâíîñò³ ó çàäàí³é ö³ëüîâ³é ôóíêö³¿ ºäèíîãî
ãëîáàëüíîãî òà áàãàòüîõ ëîêàëüíèõ ìàêñèìóì³â º àëãîðèòì DC; íåïîãàí³ ðåçóëüòàòè
ïðîäåìîíñòðóâàëè òàêîæ àëãîðèòìè TCGM_S2 òà PHC. Ðîáîòó àëãîðèòì³â áóëî äî-
äàòêîâî ïåðåâ³ðåíî íà á³ëüø ñêëàäíèõ ôóíêö³ÿõ F5 òà F6 ; óñåðåäíåí³ ðåçóëüòàòè
ïðîãîí³â ïîäàíî â òàáë. 10 òà 11 â³äïîâ³äíî. ßê ³ î÷³êóâàëîñÿ, íà ôóíêö³ÿõ F5 òà F6
àëãîðèòì PHC ïîêàçàâ ñóòòºâî ã³ðø³ ðåçóëüòàòè, ïðè÷îìó â³ðîã³äí³ñòü çíàõîäæåííÿ
ãëîáàëüíîãî ìàêñèìóìó çìåíøóºòüñÿ ó ðàç³ çá³ëüøåííÿ ðîçì³ðíîñò³ çàäà÷³. Ðåçóëü-
òàòè ðîáîòè àëãîðèòì³â TCGM_S2 òà DC º áëèçüêèìè.
ÂÈÑÍÎÂÊÈ
Çàïðîïîíîâàíî íîâèé ãåíåòè÷íèé àëãîðèòì óòâîðåííÿ í³ø — àëãîðèòì
òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ ìóòàö³ºþ. Ðîçãëÿíóòî òðè éîãî âàð³àíòè çà-
ëåæíî â³ä ñïîñîáó âèçíà÷åííÿ âåëè÷èíè êðîêó ìóòàö³¿. Ïîð³âíÿëüíèé àíàë³ç
ðîçðîáëåíîãî àëãîðèòìó ç ³íøèìè ãåíåòè÷íèìè àëãîðèòìàìè âèòèñíåííÿ (äå-
òåðì³íîâàíèì, éìîâ³ðí³ñíèì) òà ç ïàðàëåëüíèì àëãîðèòìîì ñõîäæåííÿ íà âåð-
øèíè ïîêàçàâ, ùî âàð³àíò S2 àëãîðèòìó òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ
ìóòàö³ºþ º íàéêðàùèì äëÿ çàäà÷³ ïîøóêó âñ³õ (ãëîáàëüíèõ, ëîêàëüíèõ) ìàêñè-
86 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
Ò à á ë è ö ÿ 8. Ïîð³âíÿííÿ àëãîðèòì³â
äëÿ çàäà÷³ 2.1, òåñòîâèé íàá³ð T21
Àëãîðèòì
Êðèòåð³¿
NFE PR GPR�
PHC 39138 0.9884
DC 75383 0.6469
PC 1763067 0.4732
TCGM_S1 404500 0.9653
TCGM_S2 384600 0.9649
TCGM_S3 537667 0.8103
Ò à á ë è ö ÿ 9. Ïîð³âíÿííÿ àëãîðèòì³â
äëÿ çàäà÷³ 2.2, òåñòîâèé íàá³ð T22
Àëãîðèòì
Êðèòåð³¿
NFE PR GPR�
PHC 39115 0.9167
DC 79083 1
PC 1971783 0.8833
TCGM_S1 398700 0.8833
TCGM_S2 1095066 0.9167
TCGM_S3 447250 0.8000
Ò à á ë è ö ÿ 10. Ïîð³âíÿííÿ àëãîðèòì³â äëÿ çàäà÷³ 2.2, ôóíêö³ÿ F5
Àëãîðèòì
Êðèòåð³¿
GP n, � 1 GP n, � 2 GP n, � 3 GPR NFE
PHC 1 1 0.3 0.7666 43178
DC 1 1 1 1 36566
TCGM_S1 1 1 0.3 0.7666 2159433
TCGM_S2 1 1 0.5 0.8333 1042233
TCGM_S3 1 1 0.3 0.7666 1510833
Ò à á ë è ö ÿ 11. Ïîð³âíÿííÿ àëãîðèòì³â äëÿ çàäà÷³ 2.2, ôóíêö³ÿ F6
Àëãîðèòì
Êðèòåð³¿
GP n, � 1 GP n, � 2 GP n, � 3 GPR NFE
PHC 1 0 0 0.3333 120438
DC 1 0.4 0 0.4667 48166
TCGM_S1 1 0 0 0.3333 793300
TCGM_S2 1 0.8 0 0.6 1011033
TCGM_S3 1 0 0 0.3333 1620103
ìóì³â çàäàíî¿ ôóíêö³¿, à òàêîæ äëÿ çàäà÷³ çíàõîäæåííÿ âñ³õ ãëîáàëüíèõ ìàê-
ñèìóì³â çà óìîâè íàÿâíîñò³ ê³ëüêîõ ó ö³ëüîâ³é ôóíêö³¿. Öåé àëãîðèòì òàêîæ
ïðîäåìîíñòðóâàâ íåïîãàí³ ðåçóëüòàòè ï³ä ÷àñ ðîçâ’ÿçóâàííÿ çàäà÷³ ïîøóêó
ãëîáàëüíîãî ìàêñèìóìó ôóíêö³¿, ùî õàðàêòåðèçóºòüñÿ íàÿâí³ñòþ ºäèíîãî ãëî-
áàëüíîãî òà áàãàòüîõ ëîêàëüíèõ ìàêñèìóì³â.
Äëÿ åêñïåðèìåíòàëüíîãî àíàë³çó àëãîðèòì³â ïîøóêó âñ³õ (ãëîáàëüíèõ, ëî-
êàëüíèõ) ìàêñèìóì³â çàïðîïîíîâàíî çä³éñíþâàòè ÿâíèé ðîçïîä³ë îñîáèí ô³íàëü-
íî¿ ïîïóëÿö³¿ çà í³øàìè òà îá÷èñëþâàòè äîäàòêîâèé êðèòåð³é — ÷àñòêó õèáíèõ
ï³ê³â (FPR). Áåç òàêîãî ðîçïîä³ëó ïðàêòè÷íå âèêîðèñòàííÿ áóäü-ÿêîãî àëãîðèòìó
ïîøóêó âñ³õ ìàêñèìóì³â, íà äóìêó àâòîð³â, º íåìîæëèâèì. Îá÷èñëåííÿ êðèòåð³¿â
PR òà FPR íàäຠçìîãó îö³íèòè ïðàêòè÷íó ö³íí³ñòü àëãîðèòì³â: ÿêèé â³äñîòîê ðå-
àëüíèõ ï³ê³â çíàéäåíî àëãîðèòìîì òà ÿêèé â³äñîòîê ëîêàë³çîâàíèõ àëãîðèòìîì
í³ø íàñïðàâä³ º õèáíèìè ï³êàìè. Âðàõóâàííÿ îáîõ êðèòåð³¿â, çîêðåìà, äàëî çìîãó
çðîáèòè âèñíîâîê ùîäî íåìîæëèâîñò³ ïðàêòè÷íîãî âèêîðèñòàííÿ àëãîðèòìó
éìîâ³ðí³ñíîãî âèòèñíåííÿ äëÿ ïîøóêó ³ ãëîáàëüíèõ, ³ ëîêàëüíèõ ìàêñèìóì³â ÷å-
ðåç íàäâåëèêó ê³ëüê³ñòü óãðóïîâàíü îñîáèí ó ð³çíèõ òî÷êàõ ïîøóêîâîãî ïðîñòî-
ðó (ÿê íà ï³êàõ, òàê ³ íà ñõèëàõ ö³ëüîâî¿ ôóíêö³¿). Âîäíî÷àñ àëãîðèòì äåòåðì³íî-
âàíîãî âèòèñíåííÿ õàðàêòåðèçóºòüñÿ íàäçâè÷àéíî íèçüêèì ïîêàçíèêîì FPR
(ìåíøå äâîõ â³äñîòê³â), àëå é ê³ëüê³ñòü çíàéäåíèõ íèì ëîêàëüíèõ ï³ê³â º íåïðè-
ïóñòèìî ìàëîþ. Ïðîïîíîâàíèé àëãîðèòì òóðí³ðíîãî âèòèñíåííÿ ç ãàóñîâîþ
ìóòàö³ºþ ó âàð³àíò³ S2 äëÿ âåëèêî¿ ê³ëüêîñò³ çíàéäåíèõ ãëîáàëüíèõ òà ëîêàëüíèõ
ï³ê³â äຠâ ñåðåäíüîìó äî 20 % õèáíèõ ï³ê³â, ùî íå º íàäâèñîêèì ïîêàçíèêîì.
ÑÏÈÑÎÊ Ë²ÒÅÐÀÒÓÐÈ
1. Glybovets M.M., Gulayeva N.M. Evolutionary multimodal optimization. In: Optimization Methods and
Applications: In Honor of Ivan V. Sergienko’s 80th Birthday. Butenko S., Pardalos P.M., Shylo V.
(Eds.). Springer International Publishing, 2017. P. 129–173.
2. Preuss M. Multimodal optimization by means of evolutionary algorithms. Berlin: Springer, 2015.
175 p.
3. Reeves C. (ed.). Modern heuristic techniques for combinatorial problems. New York: Halsted Press,
1993.
4. Aickelin U. An indirect genetic algorithm for set covering problems. J. of the Oper. Res. Society.
2002. Vol. 53. P. 1118–1126.
5. Ñåðãèåíêî È.Â., Øèëî Â.Ï. Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû ðåøåíèÿ, èñ-
ñëåäîâàíèÿ. Êèåâ: Íàóê. äóìêà, 2003. 264 ñ.
6. Ãëèáîâåöü Ì.Ì., Ãóëàºâà Í.Ì. Åâîëþö³éí³ àëãîðèòìè. ϳäðó÷íèê. Êè¿â: ÍàÓÊÌÀ, 2013. 828 ñ.
7. Mahfoud S. Niching method for genetic algorithms. Ph.D. thesis. Urbana, 1995. 251 p.
8. Singh G., Deb K. Comparison of multi-modal optimization algorithms based on evolutionary
algorithms. Proc. 8th Ann. Conf. on Genetic and Evolutionary Computation (GECCO’06)
(July 8–12, 2006, Seattle, Washington, USA). Seattle, 2006. P. 1305–1312.
9. Friedrich T., Oliveto P.S., Sudholt D., Witt C. Analysis of diversity-preserving nechanisms for
global exploration. Evolutionary Computation. 2009. Vol. 17, N 4. P. 455–476. https://doi.org/
10.1162/evco.2009.17.4.17401.
10. Osuna E.C., Sudholt D. Runtime analysis of crowding mechanisms for multimodal optimization.
IEEE Trans. Evol. Comp. 2019. https://doi.org/10.1109/TEVC.2019.2914606.
11. Mengshoel O., Goldberg D. Probabilistic crowding: deterministic crowding with probabilistic
replacement. Proc. the Genetic and Evolutionary Computation Conference (GECCO-99)
(13–17 July, 1999, Orlando, FL, USA). Orlando, 1999. P. 409–416.
Íàä³éøëà äî ðåäàêö³¿ 19.03.2019
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 87
Â.Ï. Øèëî, Í.Í. Ãëèáîâåö, Í.Ì. Ãóëàåâà, Å.Â. Íèêèùèõèíà
ÃÅÍÅÒÈ×ÅÑÊÈÅ ÀËÃÎÐÈÒÌÛ ÒÓÐÍÈÐÍÎÃÎ ÂÛÒÅÑÍÅÍÈß
Ñ ÃÀÓÑÑÎÂÎÉ ÌÓÒÀÖÈÅÉ
Àííîòàöèÿ. Äëÿ ðåøåíèÿ çàäà÷ ìíîãîýêñòðåìàëüíîé îïòèìèçàöèè ïðåäëî-
æåí íîâûé ãåíåòè÷åñêèé àëãîðèòì îáðàçîâàíèÿ íèø — ãåíåòè÷åñêèé àëãî-
ðèòì òóðíèðíîãî âûòåñíåíèÿ ñ ãàóññîâîé ìóòàöèåé. Ïðîâåäåííûé ñðàâíè-
òåëüíûé àíàëèç ïðåäëîæåííîãî àëãîðèòìà ñ äðóãèìè àëãîðèòìàìè âûòåñíå-
íèÿ è ñ ïàðàëëåëüíûì àëãîðèòìîì ïîèñêà ñ âîñõîæäåíèåì ê âåðøèíàì
ïîêàçàë ïðåèìóùåñòâà ðàçðàáîòàííîãî àëãîðèòìà âî ìíîãèõ ñëó÷àÿõ. Ââå-
äåí êðèòåðèé îöåíêè ñòåïåíè ðàçáðîñà ýëåìåíòîâ ïîïóëÿöèè. Ïîêàçàíî, ÷òî
âû÷èñëåíèå ýòîãî êðèòåðèÿ ÿâëÿåòñÿ öåëåñîîáðàçíûì äëÿ îöåíêè êà÷åñòâà
ðàáîòû àëãîðèòìîâ ïîèñêà ãëîáàëüíûõ è ëîêàëüíûõ ìàêñèìóìîâ.
Êëþ÷åâûå ñëîâà: çàäà÷à ìíîãîýêñòðåìàëüíîé îïòèìèçàöèè, ãåíåòè÷åñêèå
àëãîðèòìû îáðàçîâàíèÿ íèø, àëãîðèòìû âûòåñíåíèÿ, ïàðàëëåëüíûé àëãî-
ðèòì ïîèñêà ñ âîñõîæäåíèåì ê âåðøèíàì, äîëÿ ëîæíûõ ïèêîâ.
V.P. Shylo, M.M. Glybovets, N.M. Gulayeva, K.V. Nikishchikhina
TOURNAMENT CROWDING GENETIC ALGORITHMS BASED ON GAUSS MUTATION
Abstract. To solve multimodal optimization problems, a new niching genetic
algorithm named tournament crowding genetic algorithm based on Gauss
mutation is proposed. A comparative analysis of this algorithm to other
crowding algorithms and to parallel hill-climbing algorithm has shown the
advantages of the proposed algorithm in many cases. The FPR criterion to
estimate the distribution of population elements is proposed and it is shown that
computation of this criterion is advisable to estimate algorithms solving
multimodal problems of finding global and local maxima.
Keywords: multimodal optimization problem, niching genetic algorithms,
crowding algorithms, parallel hill-climbing algorithm, fake peak ratio.
Øèëî Âîëîäèìèð Ïåòðîâè÷,
äîêòîð ô³ç.-ìàò. íàóê, ïðîôåñîð, ïðîâ³äíèé íàóêîâèé ñï³âðîá³òíèê ²íñòèòóòó ê³áåðíåòèêè
³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, Êè¿â, e-mail: v.shylo@gmail.com.
Ãëèáîâåöü Ìèêîëà Ìèêîëàéîâè÷,
äîêòîð ô³ç.-ìàò. íàóê, ïðîôåñîð, äåêàí Íàö³îíàëüíîãî óí³âåðñèòåòó «Êèºâî-Ìîãèëÿíñüêà àêàäåì³ÿ»,
Êè¿â, e-mail: glib@ukma.kiev.ua.
Ãóëàºâà Íàòàë³ÿ Ìèõàéë³âíà,
êàíäèäàò ô³ç.-ìàò. íàóê, äîöåíò êàôåäðè Íàö³îíàëüíîãî óí³âåðñèòåòó «Êèºâî-Ìîãèëÿíñüêà àêàäåì³ÿ»,
Êè¿â, e-mail: ngulayeva@yahoo.com.
ͳê³ù³õ³íà Êàòåðèíà Âÿ÷åñëàâ³âíà,
ìàã³ñòð ôàêóëüòåòó ³íôîðìàòèêè Íàö³îíàëüíîãî óí³âåðñèòåòó «Êèºâî-Ìîãèëÿíñüêà àêàäåì³ÿ», Êè¿â,
e-mail: kateryna.nikishchikhina@gmail.com.
88 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-190362 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:26:06Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шило, В.П. Глибовець, М.М. Гулаєва, Н.М. Нікіщіхіна, К.В. 2023-06-03T12:56:02Z 2023-06-03T12:56:02Z 2020 Генетичні алгоритми турнірного витиснення з гаусовою мутацією / В.П. Шило, М.М. Глибовець, Н.М. Гулаєва, К.В. Нікіщіхіна // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 75–88. — Бібліогр.: 11 назв. — укр. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190362 004.023 Для розв’язання задач багатоекстремальної оптимізації запропоновано новий генетичний алгоритм утворення ніш — генетичний алгоритм турнірного витиснення з гаусовою мутацією. Проведено порівняльний аналіз його з іншими алгоритмами витиснення та з паралельним алгоритмом сходження на вершини, який показав переваги розробленого алгоритму у багатьох випадках. Введено критерій оцінювання ступеня розпорошеності елементів популяції та показано, що обчислення цього критерію є доцільним для оцінювання якості роботи алгоритмів пошуку глобальних та локальних максимумів. Для решения задач многоэкстремальной оптимизации предложен новый генетический алгоритм образования ниш — генетический алгоритм турнирного вытеснения с гауссовой мутацией. Проведенный сравнительный анализ предложенного алгоритма с другими алгоритмами вытеснения и с параллельным алгоритмом поиска с восхождением к вершинам показал преимущества разработанного алгоритма во многих случаях. Введен критерий оценки степени разброса элементов популяции. Показано, что вычисление этого критерия является целесообразным для оценки качества работы алгоритмов поиска глобальных и локальных максимумов. To solve multimodal optimization problems, a new niching genetic algorithm named tournament crowding genetic algorithm based on Gauss mutation is proposed. A comparative analysis of this algorithm to other crowding algorithms and to parallel hill-climbing algorithm has shown the advantages of the proposed algorithm in many cases. The FPR criterion to estimate the distribution of population elements is proposed and it is shown that computation of this criterion is advisable to estimate algorithms solving multimodal problems of finding global and local maxima. uk Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Генетичні алгоритми турнірного витиснення з гаусовою мутацією Генетические алгоритмы турнирного вытеснения с гауссовой мутацией Tournament crowding genetic algorithms based on Gauss mutation Article published earlier |
| spellingShingle | Генетичні алгоритми турнірного витиснення з гаусовою мутацією Шило, В.П. Глибовець, М.М. Гулаєва, Н.М. Нікіщіхіна, К.В. Системний аналіз |
| title | Генетичні алгоритми турнірного витиснення з гаусовою мутацією |
| title_alt | Генетические алгоритмы турнирного вытеснения с гауссовой мутацией Tournament crowding genetic algorithms based on Gauss mutation |
| title_full | Генетичні алгоритми турнірного витиснення з гаусовою мутацією |
| title_fullStr | Генетичні алгоритми турнірного витиснення з гаусовою мутацією |
| title_full_unstemmed | Генетичні алгоритми турнірного витиснення з гаусовою мутацією |
| title_short | Генетичні алгоритми турнірного витиснення з гаусовою мутацією |
| title_sort | генетичні алгоритми турнірного витиснення з гаусовою мутацією |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/190362 |
| work_keys_str_mv | AT šilovp genetičníalgoritmiturnírnogovitisnennâzgausovoûmutacíêû AT glibovecʹmm genetičníalgoritmiturnírnogovitisnennâzgausovoûmutacíêû AT gulaêvanm genetičníalgoritmiturnírnogovitisnennâzgausovoûmutacíêû AT níkíŝíhínakv genetičníalgoritmiturnírnogovitisnennâzgausovoûmutacíêû AT šilovp genetičeskiealgoritmyturnirnogovytesneniâsgaussovoimutaciei AT glibovecʹmm genetičeskiealgoritmyturnirnogovytesneniâsgaussovoimutaciei AT gulaêvanm genetičeskiealgoritmyturnirnogovytesneniâsgaussovoimutaciei AT níkíŝíhínakv genetičeskiealgoritmyturnirnogovytesneniâsgaussovoimutaciei AT šilovp tournamentcrowdinggeneticalgorithmsbasedongaussmutation AT glibovecʹmm tournamentcrowdinggeneticalgorithmsbasedongaussmutation AT gulaêvanm tournamentcrowdinggeneticalgorithmsbasedongaussmutation AT níkíŝíhínakv tournamentcrowdinggeneticalgorithmsbasedongaussmutation |