Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации
Запропоновано огляд генетичних алгоритмів утворення ніш для розв’язку задач багатоекстремальної оптимізації. Ці алгоритми наведено згідно їх просторово-часової класифікації. Дано докладний опис методів на основі розподілу рівня пристосованості та методів витискання як найбільш поширених. За відсутно...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2013 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/86286 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации / Н.Н. Глибовец, Н.М. Гулаева // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 15-22. — Бібліогр.: 40 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859788433944215552 |
|---|---|
| author | Глибовец, Н.Н. Гулаева, Н.М. |
| author_facet | Глибовец, Н.Н. Гулаева, Н.М. |
| citation_txt | Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации / Н.Н. Глибовец, Н.М. Гулаева // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 15-22. — Бібліогр.: 40 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано огляд генетичних алгоритмів утворення ніш для розв’язку задач багатоекстремальної оптимізації. Ці алгоритми наведено згідно їх просторово-часової класифікації. Дано докладний опис методів на основі розподілу рівня пристосованості та методів витискання як найбільш поширених. За відсутності усталеної термінології запропоновано російськомовні відповідники англомовних термінів.
In this paper, a comprehensive review of approaches to solve multimodal function optimization problems via genetic algorithms is provided. Niching genetic algorithms are presented according to their space–time classification. Methods based on fitness sharing and crowding methods are described in detail as they are the most frequently used. In the absence of established terminology, Russian-language equivalents of English terms are proposed.
|
| first_indexed | 2025-12-02T10:45:42Z |
| format | Article |
| fulltext |
ÓÄÊ 004.023
Í.Í. ÃËÈÁÎÂÅÖ, Í.Ì. ÃÓËÀÅÂÀ
ÎÁÇÎÐ ÃÅÍÅÒÈ×ÅÑÊÈÕ ÀËÃÎÐÈÒÌΠÎÁÐÀÇÎÂÀÍÈß ÍÈØ
ÄËß ÐÅØÅÍÈß ÇÀÄÀ× ÌÍÎÃÎÝÊÑÒÐÅÌÀËÜÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Êëþ÷åâûå ñëîâà: ãåíåòè÷åñêèé àëãîðèòì, çàäà÷à ìíîãîýêñòðåìàëüíîé îïòè-
ìèçàöèè, ìåòîäû îáðàçîâàíèÿ íèø.
ÂÂÅÄÅÍÈÅ
Ãåíåòè÷åñêèå àëãîðèòìû, îñíîâàííûå íà èäåÿõ ýâîëþöèîííîé òåîðèè,
ýôôåêòèâíû ïðè ðåøåíèè øèðîêîãî êðóãà îïòèìèçàöèîííûõ çàäà÷. Êàê
ïðàâèëî, ñ ïîìîùüþ òðàäèöèîííûõ ãåíåòè÷åñêèõ àëãîðèòìîâ íàõîäÿò òîëüêî
îäèí îïòèìóì çàäàííîé öåëåâîé ôóíêöèè.  òî æå âðåìÿ ñóùåñòâóþò çàäà÷è,
â êîòîðûõ òðåáóåòñÿ íàéòè íå îäèí, à k îïòèìóìîâ ìíîãîýêñòðåìàëüíîé
ôóíêöèè, ÷òî, âî-ïåðâûõ, ïîâûøàåò âåðîÿòíîñòü íàõîæäåíèÿ ãëîáàëüíîãî
îïòèìóìà, è, âî-âòîðûõ, äàåò âîçìîæíîñòü ëèöó, ïðèíèìàþùåìó ðåøåíèå,
äåëàòü âûáîð èç ìíîæåñòâà àëüòåðíàòèâíûõ ðåøåíèé [1].
Íàèáîëåå ïðîñòîé ïîäõîä ê íàõîæäåíèþ ìíîæåñòâà îïòèìóìîâ ìíîãîýêñòðå-
ìàëüíîé ôóíêöèè ñ ïîìîùüþ ãåíåòè÷åñêèõ àëãîðèòìîâ çàêëþ÷àåòñÿ â ïðîâåäåíèè
ìíîãîêðàòíûõ íåçàâèñèìûõ ïðîãîíîâ òðàäèöèîííîãî ãåíåòè÷åñêîãî àëãîðèòìà
ñ ñîõðàíåíèåì ðåçóëüòàòîâ î÷åðåäíîãî ïðîãîíà â ñëó÷àå ïîëó÷åíèÿ íîâîãî ðåøå-
íèÿ ïðè ñëåäóþùåì ïðîãîíå. Àíàëîãîì òàêîãî ïîäõîäà ÿâëÿåòñÿ îñóùåñòâëåíèå îä-
íîâðåìåííûõ ïðîãîíîâ òðàäèöèîííîãî ãåíåòè÷åñêîãî àëãîðèòìà íà ðàçíûõ ïðîöåñ-
ñîðàõ, ïðè ýòîì êàæäûé èç íèõ ðàáîòàåò ñî ñâîåé ñóáïîïóëÿöèåé è îíè íå âçàèìî-
äåéñòâóþò. Îïèñàííûå ïîäõîäû íàçûâàþòñÿ ñåêöèîíèðîâàííûìè ãåíåòè÷åñêèìè
àëãîðèòìàìè (partitioned genetic algorithms). Èõ íåäîñòàòîê — ïîâòîðíûé ïîèñê íà
îäíèõ è òåõ æå ó÷àñòêàõ ïðîñòðàíñòâà.
Áîëåå ýôôåêòèâíûìè àëãîðèòìàìè ÿâëÿþòñÿ ãåíåòè÷åñêèå àëãîðèòìû îáðàçî-
âàíèÿ íèø (niching genetic algorithms), ñïîñîáñòâóþùèå ôîðìèðîâàíèþ ñòàáèëüíûõ
ñóáïîïóëÿöèé â ïðîñòðàíñòâå ïîèñêà òàêèì îáðàçîì, ÷òî êàæäàÿ ñóáïîïóëÿöèÿ ôîð-
ìèðóåòñÿ âîêðóã îäíîãî èç èñêîìûõ îïòèìóìîâ. Â ñâÿçè ñ òåì, ÷òî èíôîðìàöèÿ îá
ýòèõ àëãîðèòìàõ ñîäåðæèòñÿ âî ìíîãèõ ïóáëèêàöèÿõ è íå ñîáðàíà âîåäèíî, ïðåäñòà-
âèì îáçîð èçâåñòíûõ â íàñòîÿùåå âðåìÿ ìåòîäîâ îáðàçîâàíèÿ íèø.
ÎÁÙÀß ÕÀÐÀÊÒÅÐÈÑÒÈÊÀ ÃÅÍÅÒÈ×ÅÑÊÈÕ ÀËÃÎÐÈÒÌΠÎÁÐÀÇÎÂÀÍÈß ÍÈØ
 îñíîâó ãåíåòè÷åñêèõ àëãîðèòìîâ îáðàçîâàíèÿ íèø ïîëîæåíî ÿâëåíèå
âèäîîáðàçîâàíèÿ è ñïåöèàëèçàöèè â ïðèðîäíûõ ýêîñèñòåìàõ. Â ýêîëîãèè ïîä
íèøåé ïîíèìàþò êîìïëåêñ ñïåöèôè÷åñêèõ óñëîâèé ïðîæèâàíèÿ,
ïîäìíîæåñòâî ðåñóðñîâ îêðóæàþùåé ñðåäû, à ïîä âèäîì — ìíîæåñòâî
îñîáåé, ïîòðåáëÿþùèõ ðåñóðñû êîíêðåòíîé íèøè. Òàêèì îáðàçîì, íèøè
ÿâëÿþòñÿ ÷àñòüþ îêðóæàþùåé ñðåäû, à âèäû — ÷àñòüþ ìíîæåñòâà âñåõ
âîçìîæíûõ îñîáåé. Ïî àíàëîãèè â ãåíåòè÷åñêîì àëãîðèòìå íèøåé (niche)
íàçûâàåòñÿ îáëàñòü ïðîñòðàíñòâà ïîèñêà, à âèäîì (species) — ìíîæåñòâî
îñîáåé ñ ïîõîæèìè õàðàêòåðèñòèêàìè.
 ãåíåòè÷åñêèõ àëãîðèòìàõ îáðàçîâàíèÿ íèø îñîáè ïîïóëÿöèè äåëÿòñÿ íà
íåñêîëüêî ñóáïîïóëÿöèé – âèäîâ, êàæäûé èç êîòîðûõ çàíèìàåò ñâîþ íèøó,
ñâÿçàí ñ íåþ âî âðåìÿ ðàáîòû àëãîðèòìà è ñïåöèàëèçèðóåòñÿ íà ðåøåíèè
îïðåäåëåííîé ïîäçàäà÷è èñõîäíîé ïðîáëåìû (âûïîëíÿåò ïîèñê îïòèìóìà
â ñâîåé íèøå). Òàêîé ïîäõîä ñïîñîáñòâóåò ñîõðàíåíèþ ðàçíîîáðàçèÿ îñîáåé
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 15
� Í.Í. Ãëèáîâåö, Í.Ì. Ãóëàåâà, 2013
â ïîïóëÿöèè, ïîçâîëÿÿ ãåíåòè÷åñêîìó àëãîðèòìó îäíîâðåìåííî èññëåäîâàòü
íåñêîëüêî îïòèìóìîâ. Â áîëüøèíñòâå àëãîðèòìîâ óêàçàííûé ýôôåêò
äîñòèãàåòñÿ çà ñ÷åò ìîäèôèêàöèè ïðîöåññà îòáîðà îñîáåé, ïðè êîòîðîì
ó÷èòûâàåòñÿ íå òîëüêî çíà÷åíèå ôóíêöèè ïðèñïîñîáëåííîñòè, íî è ðàñïðåäåëå-
íèå îñîáåé â ïðîñòðàíñòâå ãåíîòèïîâ èëè ôåíîòèïîâ. Îòìåòèì, ÷òî â àëãîðèòìàõ
îáðàçîâàíèÿ íèø âàæíî è íàéòè íåîáõîäèìûå îïòèìóìû, è íå ïîòåðÿòü èõ
â ïðîöåññå ðàáîòû àëãîðèòìà, ò.å. íóæíî íå òîëüêî ñôîðìèðîâàòü íèøè, íî è
ñîõðàíÿòü èõ äëèòåëüíîå âðåìÿ. Òàêîå òðåáîâàíèå îáúÿñíÿåòñÿ íåîáõîäèìîñòüþ
ðàçëè÷àòü ñëó÷àè, êîãäà íàéäåííîå ðåøåíèå ïðåäñòàâëÿåò íîâóþ, à òàêæå ðàíåå
ëîêàëèçîâàííóþ íèøó.
Íàèáîëåå ðàñïðîñòðàíåííàÿ êëàññèôèêàöèÿ ìåòîäîâ îáðàçîâàíèÿ íèø — ïðî-
ñòðàíñòâåííî-âðåìåííàÿ, ñîãëàñíî êîòîðîé ýòè ìåòîäû ðàçäåëåíû íà äâà êëàññà:
— ïðîñòðàíñòâåííûå (spatial) èëè ïàðàëëåëüíûå (parallel), ñîçäàþùèå
è ïîääåðæèâàþùèå ìíîæåñòâî ñóáïîïóëÿöèé (âèäîâ) îäíîâðåìåííî
â ïðîñòðàíñòâå åäèíîé ïîïóëÿöèè (â òàêèõ àëãîðèòìàõ ðåçóëüòàò äîñòèãàåòñÿ
áëàãîäàðÿ øèðîêîìó ðàçáðîñó ïîïóëÿöèè â ïðîñòðàíñòâå ïîèñêà);
— âðåìåííûå (temporal) èëè ïîñëåäîâàòåëüíûå (sequential), êîòîðûå íàõîäÿò
ìíîæåñòâî ñóáïîïóëÿöèé (âèäîâ) èòåðàòèâíî, ñ òå÷åíèåì âðåìåíè.
Îòìåòèì, ÷òî ïðèâåäåííàÿ êëàññèôèêàöèÿ íå ñâÿçàíà ñ êîëè÷åñòâîì
çàäåéñòâîâàííûõ ïðîöåññîðîâ.
Ðàññìîòðèì ïðîñòðàíñòâåííî-âðåìåííóþ êëàññèôèêàöèþ èçâåñòíûõ â íà-
ñòîÿùåå âðåìÿ ìåòîäîâ îáðàçîâàíèÿ íèø:
— âðåìåííûå, âêëþ÷àþùèå ìåòîä ïîñëåäîâàòåëüíîãî îáðàçîâàíèÿ íèø è
ìåòîäû îáðàçîâàíèÿ èåðàðõè÷åñêèõ íèø;
— ïðîñòðàíñòâåííûå, âêëþ÷àþùèå ìåòîäû íà îñíîâå ðàçäåëåíèÿ óðîâíÿ
ïðèñïîñîáëåííîñòè, ìåòîäû î÷èñòêè, êëàñòåðèçàöèè, âûòåñíåíèÿ, îãðàíè÷åíèé
íà ôîðìèðîâàíèå ðîäèòåëüñêîé ïàðû, à òàêæå ìåòîäû îáðàçîâàíèÿ
èåðàðõè÷åñêèõ íèø.
ÌÅÒÎÄ ÏÎÑËÅÄÎÂÀÒÅËÜÍÎÃÎ ÎÁÐÀÇÎÂÀÍÈß ÍÈØ
Ìíîãîêðàòíûå ïîñëåäîâàòåëüíûå çàïóñêè òðàäèöèîííîãî ãåíåòè÷åñêîãî
àëãîðèòìà âûïîëíÿåò ìåòîä ïîñëåäîâàòåëüíîãî îáðàçîâàíèÿ íèø (sequential
niching, sequential location of niches, SN) [2]. Ïîñëå êàæäîãî ïðîãîíà ýòîãî
àëãîðèòìà íàéäåííîå èì íàèëó÷øåå ðåøåíèå çàíîñèòñÿ â ãëîáàëüíûé áàíê
ðåøåíèé; â ïîñëåäóþùèõ ïðîãîíàõ óðîâåíü ïðèñïîñîáëåííîñòè âñåõ îñîáåé,
íàõîäÿùèõñÿ â îêðåñòíîñòè ýòîãî ðåøåíèÿ, ñíèæàåòñÿ. Òàêàÿ ìîäèôèêàöèÿ
óðîâíÿ ïðèñïîñîáëåííîñòè ïðè ïîñëåäóþùèõ ïðîãîíàõ ãåíåòè÷åñêîãî
àëãîðèòìà ïðåäîòâðàùàåò ïîâòîðíîå ðàññìîòðåíèå òîé æå îáëàñòè ïîèñêîâîãî
ïðîñòðàíñòâà è, ñëåäîâàòåëüíî, ñõîäèìîñòü àëãîðèòìà ê óæå èçâåñòíûì
îïòèìóìàì. Ìîäèôèöèðîâàííóþ ôóíêöèþ ïðèñïîñîáëåííîñòè f m ÷àñòî
îïðåäåëÿþò èòåðàòèâíî:
f X f Xm , ( ) ( )0 � ;
f X f X g X Sm i m i i, ,( ) ( )* ( , )� �1 ;
f X f Xm m n( ) ( ),� .
Çäåñü f X( ) — èñõîäíàÿ íåìîäèôèöèðîâàííàÿ ôóíêöèÿ ïðèñïîñîáëåííîñòè,
S i — íàèëó÷øàÿ îñîáü, íàéäåííàÿ â ðåçóëüòàòå i-ãî ïðîãîíà àëãîðèòìà, n —
íîìåð òåêóùåãî ïðîãîíà àëãîðèòìà. Ôóíêöèþ g X S i( , ) íàçûâàþò ôóíêöèåé
ïîíèæåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè (fitness derating function); â êà÷åñòâå
ýòîé ôóíêöèè ÷àñòî èñïîëüçóþò ñòåïåííóþ èëè ýêñïîíåíöèàëüíóþ ôóíêöèþ.
Îäíîé èç ìîäèôèêàöèé ìåòîäà ïîñëåäîâàòåëüíîãî îáðàçîâàíèÿ íèø
ÿâëÿåòñÿ ñîõðàíåíèå ïîñëå êàæäîãî ïðîãîíà íå îäíîãî, à âñåõ íàéäåííûõ
16 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
ãåíåòè÷åñêèì àëãîðèòìîì óíèêàëüíûõ ðåøåíèé [3]. Äðóãàÿ ïðåäñòàâëÿþùàÿ
èíòåðåñ ìîäèôèêàöèÿ — ðàñïðîñòðàíåíèå ýôôåêòà ïîíèæåíèÿ óðîâíÿ
ïðèñïîñîáëåííîñòè çà ïðåäåëû ðàäèóñà íèøè è ïðèìåíåíèå ïðîöåäóðû î÷èñòêè
äëÿ óñòðàíåíèÿ ðåøåíèé â ïðåäåëàõ ðàäèóñà [4].
ÌÅÒÎÄÛ ÍÀ ÎÑÍÎÂÅ ÐÀÇÄÅËÅÍÈß ÓÐÎÂÍß ÏÐÈÑÏÎÑÎÁËÅÍÍÎÑÒÈ
Èäåÿ ïîñòðîåíèÿ ìåòîäîâ íà îñíîâå ðàçäåëåíèÿ îñíîâàíà íà òîì ôàêòå, ÷òî
â êàæäîé ýêîëîãè÷åñêîé íèøå äîñòóïíî òîëüêî îãðàíè÷åííîå êîëè÷åñòâî òîãî
èëè èíîãî âîçîáíîâëÿåìîãî ðåñóðñà (âîäà, ïèùà, ñîëíå÷íûé ñâåò), ñëåäîâàòåëü-
íî, îñîáè, çàíèìàþùèå ýòó íèøó, ñîðåâíóþòñÿ çà âîçìîæíîñòü èñïîëüçîâàòü
îäíè è òå æå ðåñóðñû è äîëæíû äåëèòü èõ ìåæäó ñîáîé. Â êîíòåêñòå ãåíåòè-
÷åñêîãî àëãîðèòìà ðåøåíèÿ çàäà÷ îïòèìèçàöèè ðåñóðñîì, âûäåëåííûì íèøå,
ÿâëÿåòñÿ çíà÷åíèå öåëåâîé ôóíêöèè — óðîâåíü ïðèñïîñîáëåííîñòè îñîáåé.
Îñíîâíàÿ èäåÿ ìåòîäà ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè (fitness sharing,
FS) [5] çàêëþ÷àåòñÿ â ðàçäåëåíèè êîýôôèöèåíòà ïðèñïîñîáëåíèÿ ìåæäó ïîõîæèìè
îñîáÿìè ïîïóëÿöèè. Äëÿ ýòîãî â ãåíåòè÷åñêîì àëãîðèòìå ïåðåä ýòàïîì îòáîðà
ïðîâîäèòñÿ ïåðåîöåíêà óðîâíÿ ïðèñïîñîáëåííîñòè êàæäîé îñîáè â çàâèñèìîñòè îò
êîëè÷åñòâà îñîáåé, ðàñïîëîæåííûõ ñ äàííîé îñîáüþ â îäíîé íèøå: ÷åì áîëüøå
îñîáåé â îäíîé íèøå, òåì ñèëüíåå ñîçäàâàåìîå èìè îäíà íà äðóãóþ äàâëåíèå.
Îáîçíà÷èì dij ìåðó ðàññòîÿíèÿ (distance metric) èëè ìåðó íåñõîæåñòè
(dissimilarity measure) ìåæäó õðîìîñîìàìè X i è X j â ïðîñòðàíñòâå ãåíîòèïîâ
(íàïðèìåð, ðàññòîÿíèå Õåììèíãà) èëè ôåíîòèïîâ (íàïðèìåð, åâêëèäîâî ðàññòîÿ-
íèå). Ôóíêöèåé ñîó÷àñòèÿ èëè ôóíêöèåé ðàçäåëåíèÿ (sharing function) S dij( ) íà-
çûâàåòñÿ ôóíêöèÿ, îïðåäåëÿþùàÿ ñòåïåíü áëèçîñòè (ñîó÷àñòèÿ) õðîìîñîì â ïî-
ïóëÿöèè. Îíà äîëæíà óäîâëåòâîðÿòü ñëåäóþùèì ñâîéñòâàì: � � �d S dij ij: ( )0 1;
S — óáûâàþùàÿ; S ( )0 1� (âîçâðàùàåò 1, åñëè ýëåìåíòû îäèíàêîâû);
lim
d
ij
ij
S d
�
�( ) 0. Ïîñëåäíåå ñâîéñòâî èíîãäà çàïèñûâàþò �
�d S dij ij� share: ( ) 0.
Ïàðàìåòð � share íàçûâàþò ðàçìåðîì, ðàäèóñîì ëèáî îòñ÷åòîì íèøè, ðàäèóñîì ñî-
ó÷àñòèÿ, ïîðîãîì íåñõîæåñòè (niche size, niche radius, share radius, sharing radius,
threshold of dissimilarity, distance cutoff). Îñîáè X i è X j , íàõîäÿùèåñÿ íà ðàññòîÿ-
íèè dij îäíà îò äðóãîé, ñ÷èòàþòñÿ ïîõîæèìè è äîëæíû ðàçäåëÿòü óðîâåíü ïðèñïî-
ñîáëåííîñòè, åñëè dij � � share (S dij( ) � 0). ×àñòî ôóíêöèÿ ñîó÷àñòèÿ S dij( )
çàäàåòñÿ òàê:
S d
d
d
ij
ij
ij( ) , ,�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
0
�
�
�
share
shareåñëè
(1)
ãäå � — êîíñòàíòà, îïðåäåëÿþùàÿ ôîðìó ôóíêöèè ñîó÷àñòèÿ. Îòìåòèì, ÷òî
âëèÿíèå ïàðàìåòðà � íà ðàáîòó àëãîðèòìà îñíîâàòåëüíî íå èññëåäîâàëîñü,
à âûáîð çíà÷åíèÿ ïàðàìåòðà � share ÿâëÿåòñÿ ïðèíöèïèàëüíûì äëÿ óñïåøíîé
ðàáîòû àëãîðèòìà. Ðåêîìåíäàöèè îòíîñèòåëüíî îïðåäåëåíèÿ çíà÷åíèÿ
ïàðàìåòðà � share ïðèâåäåíû â [6–8].
Îïðåäåëèâ ôóíêöèþ ñîó÷àñòèÿ ïî ôîðìóëå (1), ïåðåîöåíêó óðîâíÿ
ïðèñïîñîáëåííîñòè îñîáåé ìîæíî ïðîâåñòè ñëåäóþùèì îáðàçîì:
f X
f X i S d
f X
m
i S d
s j
j ij
j
j
ij
( )
( ), : ( ) ,
( )
, : ( )
�
� �
�
åñëè
åñëè
0
�
�
�
�
�
� 0,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 17
â ïðîòèâíîì ñëó÷àå,
ãäå m S dj ij
i
N
�
�
� ( )
1
— ÷èñëî íèøè (niche count), N — êîëè÷åñòâî îñîáåé
â ïîïóëÿöèè. Ïðè ýòîì îðèãèíàëüíóþ ôóíêöèþ ïðèñïîñîáëåííîñòè f
íàçûâàþò ïðåäâàðèòåëüíîé (prior fitness, raw fitness) èëè öåëåâîé (objective fit-
ness), à ôóíêöèþ ïåðåîöåíêè óðîâíÿ ïðèñïîñîáëåííîñòè f s — ýôôåêòèâíîé
(effective fitness) èëè ðàçäåëÿåìîé (shared fitness).
Ñðåäè îñíîâíûõ íåäîñòàòêîâ ìåòîäà ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè
ïðèíÿòî âûäåëÿòü âûñîêóþ âû÷èñëèòåëüíóþ ñëîæíîñòü àëãîðèòìà è òðóäíîñòè
ïðè âûáîðå çíà÷åíèÿ ïàðàìåòðà � share. Èç ìíîæåñòâà ìîäèôèêàöèé àëãîðèòìà
ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè îòìåòèì ñëåäóþùèå:
— èñïîëüçîâàíèå âûáîðêè ðàçìåðà ��� N äëÿ îöåíêè ÷èñëà íèøè [5];
— ïðîâåäåíèå ïðåäâàðèòåëüíîãî ðàñïðåäåëåíèÿ îñîáåé ïî íèøàì ñ ïî-
ìîùüþ àëãîðèòìà êëàñòåðèçàöèè [9, 10];
— ìàñøòàáèðîâàíèå ôóíêöèè ïðèñïîñîáëåííîñòè [11, 12];
— ââåäåíèå îãðàíè÷åíèé íà ôîðìèðîâàíèå ðîäèòåëüñêîé ïàðû [7, 13, 14];
— íàäåëåíèå îñîáåé ïîïóëÿöèè ñîáñòâåííûìè ýíåðãåòè÷åñêèìè ðåñóðñàìè [15];
— êîìáèíèðîâàíèå ìåòîäà ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè
ñ äðóãèìè îïòèìèçàöèîííûìè ìåòîäàìè [3, 16].
Ïåðñïåêòèâíîé ÿâëÿåòñÿ ðàçðàáîòêà òåõíèêè àäàïòèâíîãî çàäàíèÿ ðàçìåðà
íèøè. Çäåñü îòìåòèì ìåòîä ñîçäàíèÿ íèø êîýâîëþöèåé (ñoevolutionary shared
niching, CSN) [17], â êîòîðîì àäàïòàöèÿ ðàñïîëîæåíèÿ è ðàçìåðà íèø
äîñòèãàåòñÿ çà ñ÷åò ñîâìåñòíîé ýâîëþöèè äâóõ ïîïóëÿöèé, à òàêæå
ìíîãîíàöèîíàëüíûé ãåíåòè÷åñêèé àëãîðèòì (multinational genetic algorithm,
MGA) [18], â êîòîðîì ðàñïðåäåëåíèå îñîáåé ïî ñóáïîïóëÿöèÿì ïðîâîäèòñÿ áåç
èñïîëüçîâàíèÿ ïîíÿòèÿ ðàäèóñà íèøè íà îñíîâå èìåþùåéñÿ èíôîðìàöèè
î òîïîëîãèè ëàíäøàôòà ôóíêöèè ïðèñïîñîáëåííîñòè.
ÌÅÒÎÄ Î×ÈÑÒÊÈ
Êàê è ìåòîä ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè, ìåòîä î÷èñòêè (clearing)
[19] îñíîâàí íà êîíöåïöèè îãðàíè÷åííîñòè ðåñóðñîâ â îêðóæàþùåé ñðåäå è íå-
îáõîäèìîñòè ðàçäåëÿòü èõ ìåæäó ïîõîæèìè îñîáÿìè. Îäíàêî â îòëè÷èå îò ìåòî-
äà ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè ìåòîä î÷èñòêè íå äåëèò ðåñóðñû ïîðîâ-
íó ìåæäó âñåìè îñîáÿìè äàííîé ñóáïîïóëÿöèè, à ïðåäîñòàâëÿåò èõ òîëüêî ëó÷-
øèì åå ïðåäñòàâèòåëÿì. Äëÿ ýòîãî â êàæäîé ñóáïîïóëÿöèè îïðåäåëÿåòñÿ îñîáü
ñ íàèëó÷øèì óðîâíåì ïðèñïîñîáëåííîñòè, íàçûâàåìàÿ äîìèíèðóþùåé (dominant
individual), îñòàëüíûå îñîáè ýòîé ñóáïîïóëÿöèè íàçûâàþòñÿ äîìèíèðóåìûìè
(dominated individuals). Ïîñëå îïðåäåëåíèÿ âñåõ äîìèíèðóþùèõ îñîáåé íåïîñðå-
äñòâåííî ïåðåä îòáîðîì ïðèìåíÿåòñÿ ïðîöåäóðà î÷èñòêè, ïðèñâàèâàþùàÿ çíà÷å-
íèå íóëü çäîðîâüþ âñåõ äîìèíèðóåìûõ îñîáåé ñóáïîïóëÿöèé.
Ïîïóëÿðíîé ìîäèôèêàöèåé ìåòîäà î÷èñòêè ÿâëÿåòñÿ èñïîëüçîâàíèå íå îä-
íîé, à k äîìèíèðóþùèõ îñîáåé. Ñóùåñòâóåò òàêæå ìîäèôèêàöèÿ — ñäâèã äîìè-
íèðóåìûõ îñîáåé çà ïðåäåëû îêðåñòíîñòè îñîáè-ïîáåäèòåëÿ äëÿ íàõîæäåíèÿ íî-
âûõ ïåðñïåêòèâíûõ îáëàñòåé ïîèñêîâîãî ïðîñòðàíñòâà [20].
ÌÅÒÎÄÛ ÊËÀÑÒÅÐÈÇÀÖÈÈ
Äëÿ ðàñïðåäåëåíèÿ ýëåìåíòîâ ïîïóëÿöèè ïî íèøàì òàêæå èñïîëüçóþòñÿ èçâåñ-
òíûå ìåòîäû êëàñòåðèçàöèè ÷àñòî â ñî÷åòàíèè ñ òàêèìè ìåòîäàìè îáðàçîâàíèÿ
íèø, êàê ìåòîä ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè èëè ìåòîä î÷èñòêè. Íàï-
ðèìåð, â ñõåìå Yin è Germay (Yin and Germay’s scheme) [10] ðàñïðåäåëåíèå
îñîáåé ïî íèøàì (êëàñòåðàì) ïðîâîäèòñÿ íà îñíîâå àëãîðèòìà k-ñðåäíèõ, ïîñëå
÷åãî óðîâåíü ïðèñïîñîáëåííîñòè îñîáåé ïåðåâû÷èñëÿåòñÿ ïî ôîðìóëå
f X
f X
n
d
d
s i
i
c
ic
( )
( )
max
�
�
�
�
��
�
�
��
�
�
�
�
�
�
�
�
1
2
�
,
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
ãäå nc — êîëè÷åñòâî îñîáåé â íèøå ñ öåíòðîèäîì c; dic — ðàññòîÿíèå ìåæäó
îñîáüþ X i è öåíòðîèäîì c; dmax — íàèáîëüøåå äîïóñòèìîå ðàññòîÿíèå
ìåæäó îñîáüþ è öåíòðîèäîì êëàñòåðà, êîòîðîìó îíà ïðèíàäëåæèò; � —
êîíñòàíòà (ïðåäïîëàãàåòñÿ, ÷òî îñîáü X i ïðèíàäëåæèò êëàñòåðó ñ öåíòðîèäîì c).
Ñðåäè äðóãèõ ìåòîäîâ óêàçàííîãî òèïà îòìåòèì ìåòîäû êîëëåêòèâíîãî ðàç-
äåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè (collective sharing) [21], äèíàìè÷åñêîãî ðàç-
äåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè (dynamic fitness sharing, DFS) [22], ðàçäåëå-
íèÿ óðîâíÿ ïðèñïîñîáëåííîñòè â äèíàìè÷åñêèõ íèøàõ (dynamic niche sharing)
[9], êëàñòåðèçàöèè äèíàìè÷åñêèõ íèø (dynamic niche clustering, DNC) [23, 24],
òåõíèêó èåðàðõè÷åñêîé êëàñòåðèçàöèè (hierarchical clustering technique) [25].
Ïðåäñòàâëÿåò èíòåðåñåí òàêæå ãåíåòè÷åñêèé àëãîðèòì ñîõðàíåíèÿ âèäîâ (species
conserving genetic algorithm, SCGA) [26], â êîòîðîì ïîñëå ðàçäåëåíèÿ ïîïóëÿöèè
íà ñóáïîïóëÿöèè ëó÷øèå îñîáè êàæäîãî âèäà, íàçâàííûå ñåìåíàìè âèäà (species
seeds), ñîõðàíÿþòñÿ äëÿ èõ ïåðåíîñà â ñëåäóþùåå ïîêîëåíèå. Òàêîé ïîäõîä
ïðåäîòâðàùàåò èñ÷åçíîâåíèå âèäîâ. Ñðåäè ìîäèôèêàöèé äàííîãî ìåòîäà îòìå-
òèì ýâîëþöèîííûé àëãîðèòì ñ âèäîñïåöèôè÷åñêèì âçðûâîì (evolutionary
algorithm with species-specific explosion, EASE) [27] è òîïîëîãè÷åñêèé àëãîðèòì
ñîõðàíåíèÿ âèäîâ TSC è TSC2 (topological species conservation algorithm) [28, 29].
ÌÅÒÎÄÛ ÂÛÒÅÑÍÅÍÈß
Ïîä ìåòîäàìè âûòåñíåíèÿ (crowding) èëè ìåòîäàìè îãðàíè÷åííîãî çàìåùåíèÿ
(restricted replacement) ïîíèìàþò ãåíåòè÷åñêèå àëãîðèòìû ñ ÷àñòè÷íîé çàìåíîé
ïîïóëÿöèè, â êîòîðûõ ïðè äîáàâëåíèè íîâîãî ýëåìåíòà â ïîïóëÿöèþ èç
ïîñëåäíåé âûòåñíÿåòñÿ ýëåìåíò, ïîõîæèé íà äîáàâëÿåìûé. Â îñíîâå òàêîãî
ïîäõîäà ëåæèò ñîîòâåòñòâóþùåå ýêîëîãè÷åñêîå ÿâëåíèå — ñîðåâíîâàíèå
ìåæäó ïîõîæèìè îñîáÿìè ïîïóëÿöèè çà èñïîëüçîâàíèå îãðàíè÷åííûõ
ðåñóðñîâ: ïîõîæèå îñîáè ïîïóëÿöèè, ïûòàÿñü çàíÿòü îäíó è òó æå íèøó,
âûíóæäåíû ñîðåâíîâàòüñÿ çà îáëàäàíèå ðåñóðñàìè ýòîé íèøè, ñëåäîâàòåëüíî,
ïðè äîñòèæåíèè ïîòåíöèàëüíîé åìêîñòè íèøè ñëàáûå îñîáè áóäóò âûòåñíåíû
èç ïîïóëÿöèè áîëåå ñèëüíûìè åå ÷ëåíàìè.
 ìåòîäå ñòàíäàðòíîãî âûòåñíåíèÿ (standard crowding) èëè ìåòîäå
âûòåñíÿþùåãî ìíîæèòåëÿ (crowding factor model) [30] íà êàæäîé èòåðàöèè
ðàáîòû àëãîðèòìà äëÿ ïîðîæäåíèÿ ïîòîìêîâ èç ïîïóëÿöèè îòáèðàþòñÿ îñîáè
(ïðîïîðöèîíàëüíûé îòáîð), êîëè÷åñòâî êîòîðûõ îïðåäåëÿåòñÿ ïàðàìåòðîì
GG — ðàçðûâîì ïîêîëåíèÿ (generation gap). Ïîòîìîê âûòåñíÿåò èç ïîïóëÿöèè
íàèáîëåå ïîõîæóþ íà íåãî îñîáü èç ñëó÷àéíûì îáðàçîì âûáðàííîé ãðóïïû
îñîáåé òåêóùåé ïîïóëÿöèè; ðàçìåð ýòîé ãðóïïû îïðåäåëÿåòñÿ ïàðàìåòðîì ñf —
âûòåñíÿþùèì ìíîæèòåëåì (crowding factor).
Íåäîñòàòîê ìåòîäà ñòàíäàðòíîãî âûòåñíåíèÿ — îøèáêè çàìåùåíèÿ,
êîòîðûå õàðàêòåðèçóþòñÿ âûòåñíåíèåì îñîáüþ èç îäíîé íèøè îñîáè èç äðóãîé
íèøè è ÿâëÿþòñÿ ïðè÷èíîé ïîòåðè ïîïóëÿöèåé ÷àñòè îïòèìóìîâ. Äëÿ
ïðåîäîëåíèÿ óêàçàííîé ïðîáëåìû áûë ðàçðàáîòàí ðÿä ìîäèôèêàöèé ìåòîäà
ñòàíäàðòíîãî âûòåñíåíèÿ.  ÷àñòíîñòè, â [31, 32] ïðåäëîæåíî èñïîëüçîâàòü
ñòðàòåãèè çàìåùåíèÿ ñ äîïîëíèòåëüíûì äàâëåíèåì îòáîðà. Â ìåòîäå
äåòåðìèíèðîâàííîãî âûòåñíåíèÿ (deterministic crowding, DC) [3, 33]
ê ïîðîæäåíèþ ïîòîìêîâ äîïóñêàþòñÿ âñå îñîáè ïîïóëÿöèè, à äëÿ ðåøåíèÿ
âîïðîñà îá èçúÿòèè îñîáåé èç ïîïóëÿöèè ïðîâîäÿòñÿ áèíàðíûå òóðíèðû ìåæäó
ðîäèòåëÿìè è ïîòîìêàìè, ïðè÷åì ïîòîìîê ñòàâèòñÿ â ïàðó ñ òåì ðîäèòåëåì, íà
êîòîðîãî îí áîëüøå ïîõîæ. Ìåòîä âåðîÿòíîñòíîãî âûòåñíåíèÿ (probabilistic
crowding, PC) [34] — ìîäèôèêàöèÿ ìåòîäà äåòåðìèíèðîâàííîãî âûòåñíåíèÿ,
â êîòîðîé ðåçóëüòàòû òóðíèðîâ ìåæäó ðîäèòåëÿìè è ïîòîìêàìè îïðåäåëÿþòñÿ
âåðîÿòíîñòíûì ïðàâèëîì: êàæäûé ó÷àñòíèê òóðíèðà ìîæåò âûèãðàòü
ñ âåðîÿòíîñòüþ, ïðîïîðöèîíàëüíîé åãî óðîâíþ ïðèñïîñîáëåííîñòè. Ìåòîä
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 19
îãðàíè÷åííîãî òóðíèðíîãî îòáîðà (restricted tournament selection, RTS) [35]
ÿâëÿåòñÿ ìîäèôèêàöèåé ìåòîäà ñòàíäàðòíîãî âûòåñíåíèÿ, â êîòîðîé ðàçðûâ
ïîêîëåíèÿ (ïàðàìåòð GG) ñîñòàâëÿåò äâå îñîáè, à äëÿ ðåøåíèÿ îá èçúÿòèè îñîáè
èç ïîïóëÿöèè èñïîëüçóåòñÿ àäàïòàöèÿ ñòàíäàðòíîãî òóðíèðíîãî îòáîðà.
 ìåòîäå ìíîãîíèøåâîãî âûòåñíåíèÿ (multi-niche crowding, MNC) [36, 37] ïðè
ôîðìèðîâàíèè ðîäèòåëüñêîé ïàðû è îïðåäåëåíèè îñîáåé íà âûòåñíåíèå
ïîòîìêîì ïðåäïî÷òåíèå îòäàåòñÿ îñîáÿì èç îäíîé íèøè.
ÌÅÒÎÄÛ ÎÃÐÀÍÈ×ÅÍÈÉ ÍÀ ÔÎÐÌÈÐÎÂÀÍÈÅ ÐÎÄÈÒÅËÜÑÊÎÉ ÏÀÐÛ
Îãðàíè÷åíèÿ íà ïîðîæäåíèå ïîòîìêîâ ðîäèòåëÿìè, ïðèíàäëåæàùèìè ðàçíûì
íèøàì, íàëàãàþò ìåòîäû îãðàíè÷åíèé íà ôîðìèðîâàíèå ðîäèòåëüñêîé ïàðû
(mating restriction methods). Ââåäåíèå ýòèõ îãðàíè÷åíèé îïðàâäàíî, ïîñêîëüêó
ñêðåùèâàíèå òàêèõ ðîäèòåëåé ìîæåò ïðèâåñòè ê ïîðîæäåíèþ î÷åíü ñëàáûõ
ïîòîìêîâ. Áèîëîãè÷åñêèì îáîñíîâàíèåì òàêèõ îãðàíè÷åíèé ÿâëÿåòñÿ
ãåîãðàôè÷åñêàÿ èçîëÿöèÿ âèäîâ, ñîçäàþùàÿ áàðüåð äëÿ îáìåíà ãåíàìè. Äëÿ
ïðèìåíåíèÿ îãðàíè÷åíèé íà ôîðìèðîâàíèå ðîäèòåëüñêîé ïàðû ïåðâûé
ðîäèòåëü ÷àñòî âûáèðàåòñÿ ñëó÷àéíî, à âòîðîé — ñ ó÷åòîì ìåõàíèçìà
îãðàíè÷åíèé (íàïðèìåð, ðàññòîÿíèå âòîðîãî ðîäèòåëÿ îò ïåðâîãî íå äîëæíî
ïðåâûøàòü çàðàíåå çàäàííîé âåëè÷èíû �). Èíîãäà ðåàëèçàöèÿ îãðàíè÷åíèé íà
ôîðìèðîâàíèå ðîäèòåëüñêîé ïàðû ïðîâîäèòñÿ ñ ïîìîùüþ ìàðêèðîâêè (tag-
ging) îñîáåé, ÷òî ïîçâîëÿåò îïðåäåëÿòü ïðèíàäëåæíîñòü îñîáè ê òîé èëè èíîé
íèøå íå íà îñíîâàíèè âû÷èñëåíèÿ ðàññòîÿíèé, à ïóòåì ó÷åòà èíôîðìàöèè
î åå íàñëåäñòâåííîñòè [14]. Îòìåòèì ìåòîä îãðàíè÷åííîãî ñîðåâíîâàíèÿ
(restricted competition) [3], â êîòîðîì ïðè òóðíèðíîì îòáîðå ðîäèòåëåé
íàëàãàþòñÿ îãðàíè÷åíèÿ íà ñîðåâíîâàíèÿ ìåæäó íåïîõîæèìè îñîáÿìè.
ÃÈÁÐÈÄÍÛÅ ÀËÃÎÐÈÒÌÛ ÎÁÐÀÇÎÂÀÍÈß ÍÈØ
Çàâåðøàÿ îáçîð ñóùåñòâóþùèõ àëãîðèòìîâ îáðàçîâàíèÿ íèø, îòìåòèì ýôôåê-
òèâíîñòü ãèáðèäèçàöèè ðàçëè÷íûõ àëãîðèòìîâ, à èìåííî àëãîðèòìà ñîõðàíå-
íèÿ âèäîâ ñ ìíîãîíàöèîíàëüíûì ãåíåòè÷åñêèì àëãîðèòìîì [28, 29], ìåòîäà
äåòåðìèíèðîâàííîãî âûòåñíåíèÿ ñ ãåííî-èíâàðèàíòíûì ãåíåòè÷åñêèì àëãîðèò-
ìîì [3], ìåòîäîâ îãðàíè÷åíèé íà ôîðìèðîâàíèå ðîäèòåëüñêîé ïàðû ñ ìåòîäàìè
ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè è ìåòîäàìè êëàñòåðèçàöèè [7, 9, 10]
è äð. Ýôôåêòèâíûé ñïîñîá êîìáèíèðîâàíèÿ ðàçëè÷íûõ àëãîðèòìîâ îáðàçîâà-
íèÿ íèø äëÿ ôîðìèðîâàíèÿ àíñàìáëÿ àëãîðèòìîâ îáðàçîâàíèÿ íèø (ensemble
of niching algorithms, ENA) ïðåäëîæåí â [38].  ìîäåëè èåðàðõè÷åñêîãî ñïðà-
âåäëèâîãî ñîðåâíîâàíèÿ (Hierarchical fair competition, HFC) [39] ñîçäàíà èåðàð-
õè÷åñêàÿ ñòðóêòóðà èç ñóáïîïóëÿöèé íà îñíîâå óðîâíÿ ïðèñïîñîáëåííîñòè
îñîáåé.  ñëó÷àå èñïîëüçîâàíèÿ íà êàæäîì óðîâíå èåðàðõèè ïðîñòðàíñòâåí-
íûõ àëãîðèòìîâ îáðàçîâàíèÿ íèø ãîâîðÿò î ìåòîäå îáðàçîâàíèÿ èåðàðõè÷åñ-
êèõ íèø (hierarchical niching) [40]. Îäíèì èç óòî÷íåíèé ýòîãî ìåòîäà ÿâëÿåòñÿ
àëãîðèòì áûñòðîãî èåðàðõè÷åñêîãî ñïðàâåäëèâîãî ñîðåâíîâàíèÿ (quick hierar-
chical fair competition, QHFC) [40], èñïîëüçóþùèé àëãîðèòìû äåòåðìèíèðîâàí-
íîãî âûòåñíåíèÿ.
ÇÀÊËÞ×ÅÍÈÅ
Ïðîáëåìû ðåàëüíîãî ìèðà îáóñëîâëèâàþò ïîñòîÿííûé ðîñò èíòåðåñà ê ìåòîäàì
ðåøåíèÿ çàäà÷ ìíîãîýêñòðåìàëüíîé îïòèìèçàöèè, â ÷àñòíîñòè âñå áîëåå øèðî-
êîìó èñïîëüçîâàíèþ ãåíåòè÷åñêèõ àëãîðèòìîâ îáðàçîâàíèÿ íèø.  ñòàòüå ïðåä-
ñòàâëåí îáçîð îñíîâíûõ ãåíåòè÷åñêèõ àëãîðèòìîâ îáðàçîâàíèÿ íèø è èõ
ìîäèôèêàöèé.
Ê ñîæàëåíèþ, âîïðîñ î ñèñòåìàòè÷åñêîì ñðàâíèòåëüíîì àíàëèçå àëãîðèòìîâ
îáðàçîâàíèÿ íèø ïîêà íå ðåøåí. Â ðàáîòàõ, ïîñâÿùåííûõ ñðàâíèòåëüíîìó
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
àíàëèçó ýòèõ àëãîðèòìîâ, ðàññìàòðèâàþò, êàê ïðàâèëî, äâà-ïÿòü àëãîðèòìîâ,
ïðèìåíÿåìûõ ê íåêîòîðûì, à èíîãäà ëèøü ê îäíîé ôóíêöèè. Íà îñíîâàíèè
àíàëèçà èçâåñòíûõ ïóáëèêàöèé ìîæíî ñäåëàòü âûâîä, ÷òî â îáùåì ñëó÷àå
ïðîñòðàíñòâåííûå (ïàðàëëåëüíûå) ìåòîäû ýôôåêòèâíåå âðåìåííûõ
(ïîñëåäîâàòåëüíûõ). Ìíîãèå èññëåäîâàòåëè îòìå÷àþò âûñîêóþ ýôôåêòèâíîñòü
ðàçëè÷íûõ ìîäèôèêàöèé ìåòîäîâ ðàçäåëåíèÿ óðîâíÿ ïðèñïîñîáëåííîñòè,
î÷èñòêè, äåòåðìèíèðîâàííîãî âûòåñíåíèÿ, îãðàíè÷åííîãî òóðíèðíîãî îòáîðà,
à òàêæå àëãîðèòìà áûñòðîãî èåðàðõè÷åñêîãî ñïðàâåäëèâîãî ñîðåâíîâàíèÿ.
CÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Ïðîáëåìû äèñêðåòíîé îïòèìèçàöèè: ñëîæíûå çàäà÷è,
îñíîâíûå ïîäõîäû ê èõ ðåøåíèþ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 4. — Ñ. 3–25.
2. B e a s l e y D . , B u l l D . R . , M a r t i n R . R . A sequential niche technique for multimodal func-
tion optimization // Evol. Comput. — 1993. — 1, N 2. — P. 101–125.
3. M a h f o u d S . W . Niching methods for genetic algorithms: Ph.D. dis — Univ. of Illinois at Ur-
bana-Champaign, Illinois Genetic Algorithms Lab., 1995. — 251 p.
4. V i t e l a J . , C a s t a n o s O . A real-coded niching memetic algorithm for continuous multimodal
function optimization // Proc. IEEE Congr. on Evol. Comput. (CEC 2008), 22–24 July 2008. —
Washington (USA), 2008. — P. 2170–2177.
5. G o l d b e r g D . E . , R i c h a r d s o n J . Genetic algorithms with sharing for multimodal function op-
timization / J. J. Grefensette (Ed.) // Genetic Algorithms and their Applications: Proc. of the Sec. Intern.
Conf. on Genetic Algorithms (ICGA-87). — Hillsdale (NJ): Lawrence Erlbaum, 1987. — P. 41–49.
6. C i o p p a A . , S t e f a n o C . , M a r c e l l i A . On the role of population size and niche radius in
fitness sharing // IEEE Trans. Evol. Comput. — 2004. — 8, N 6. — P. 580–592.
7. D e b K . , G o l d b e r g D . E . An investigation of niche and species formation in genetic function
optimization / J. D. Schaffer (Ed.) // Proc. of the Third Intern. Conf. on Genetic Algorithms
(ICGA-89). — San Mateo (CA): Morgan Kaufmann, 1989. — P. 42–50.
8. D e b K . Genetic algorithms in multimodal function optimization: Masters thesis and TGGA: (Rep.)
/ Univ. of Alabama. — N 89002. — Tuscaloosa, 1989. — 14 p.
9. M i l l e r B . L . , S h a w M . J . Genetic algorithms with dynamic niche sharing for multimodal
function optimization // Proc. of the 1996 IEEE Intern. Conf. on Evol. Comput. (ICEC’96). — New
York (USA), 1996. — P. 786–791.
10. Y i n X . , G e r m a y N . A fast genetic algorithm with sharing scheme using cluster analysis meth-
ods in multimodal function optimization / R.F. Albrecht, C. Reeves, and N.C. Steele (Eds) // Proc. of
the Intern. Conf. on Artificial Neural Networks and Genetic Algorithms. — Berlin: Springer-Verlag,
1993. — P. 450–457.
11. D a r w e n P . , D a r w e n P . , Y a o X . A dilemma for fitness sharing with a scaling function //
Proc. 1995 IEEE Conf. Evol. Comput. — Piscataway (NJ): IEEE press, 1995. — P. 166–171.
12. G o l d b e r g D . E . , D e b K . , H o r n J . Massive multimodality, deception and genetic algo-
rithms / R. Manner and B. Manderick (Eds) // Proc. of Parallel Problem Solving from Nature. —
Amsterdam: Elsevier Sci. Publ. B.V., 1992. — 2. — P. 37–46.
13. S a r e n i B . , K r a h e n b u h l L . Fitness sharing and niching methods revisited // IEEE Tranc. On
Evol. Comput. — 1998. — 2, N 3. — P. 97–106.
14. S p e a r s W . M . Simple subpopulation schemes // Proc. of the Third Annual Conf. on Evol. Progr.
— World Sci., 1994. — P. 296–307.
15. M e n c z e r F . B e l e w K . Local selection // Proc. of 7th Ann.l Conf. on Evol. Progr. — 1998. —
P. 703–712.
16. S m i t h R . E . , F o r r e s t S . , P e r e l s o n A . S . Searching for diverse, cooperative populations
with genetic algorithms // Evol. Comput. — 1993. — 1, N 2. — P. 127–149.
17. G o l d b e r g D . Adaptive niching via coevolutionary sharing / David E. Goldberg & Liwei Wang //
Quagliarella D. Genetic Algorithms and Evol. Strategy in Eng. and Comput Sci.: Recent Adv. and
Industr. Appl. — John Wiley & Sons, Ltd. 1998. — P. 21–38.
18. U r s e m R . K . Multinational Evolutionary Algorithms // Proc. of the Congr. of Evol. Comput.
(CEC-99). — Piscataway (NJ): IEEE press, 1999. — 3. — P. 1633–1640.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 21
19. P e t r o w s k i A . A clearing procedure as a niching method for genetic algorithms // Proc. of the
Third IEEE Intern. Conf. on Evol. Comput (ICEC’96), Nagoya (Japan), 1996. — Piscataway (NJ):
IEEE press, 1996. — P. 798–803.
20. S i n g h G . , D e b K . Comparison of multi-modal optimization algorithms based on evolutionary
algorithms // Proc. of the 8th Ann. Conf. on Genetic and Evol. Comput., GECCO 2006 (Seattle, WA,
2006). — New York, (USA): ACM press, 2006. — P. 1305–1312.
21. Genetic algorithms with collective sharing for robust optimization in financial applications /
O.V. Pictet, M.M. Dacarogna, R.D. Dave at al. — Olsen & Assoc. Working Paper, 1995. – 14 p.
22. C i o p p a A . D . , S t e f a n o C . D . , M a r c e l l i A . Where are the niches? Dynamic fitness
sharing // IEEE Trans. on Evol. Comput. — 2007. — 11, N 4. — P. 453–465.
23. G a n J . , W a r w i c k K . A genetic algorithm with dynamic niche clustering for multimodal func-
tion optimisation // Proc. of the 4th Intern. Conf. on Artificial Neural Networks and Genetic Algo-
rithms. — Springer, 1998. — 3. — P. 248–255.
24. G a n J . , W a r w i c k K . Dynamic niche clustering: a fuzzy variable radius niching technique for
multimodal optimisation in Gas // Proc. of the 2001 Congr. on Evol. Comput . — IEEE, 2001. — 1.
— P. 215–222.
25. P e t r o w s k i A . An efficient hierarchical clustering technique for speciation: (Techn. rep.) / Inst.
Nat. des Telecommunications. — Evry (France), 1997. — 8 p.
26. A s p e c i e s conserving genetic algorithm for multimodal function optimization / J.-P. Li,
M.E. Balazs, G.T. Parks, P.J. Clarkson // Evol. Comput . — 2002. — 10, N 3. — P. 207–234.
27. W o n g K . C . , L e u n g K . S . , W o n g M . H . An evolutionary algorithm with species-specific
explosion for multimodal optimization // Proc. of the 11th Ann. Conf. on Genetic and Evol. Comput.
— ACM GECCO, 2009. — P. 923–930.
28. D i s b u r d e n i n g the species conservation evolutionary algorithm of arguing with radii /
C. Stoean, M. Preuss, R. Stoean, D. Dumitrescu // Proc. Genetic Evol. Comput. Conf. (GECCO). —
2007. — P. 1420–1427.
29. M u l t i m o d a l optimization by means of a topological Species conservation algorithm / C. Stoean,
M. Preuss, R. Stoean, D. Dumitrescu // IEEE Trans. on Evol. Comput . — 2010. — 14, N 6. —
P. 842–864.
30. D e J o n g K . A . An analysis of the behavior of a class of genetic adaptive systems: Ph.D. dis. —
Ann Arbor: Univ. of Michigan, 1975. 271 p.
31. S e d b r o o k T . A . , W r i g h t H . , W r i g h t R . Application of a genetic classifier for patient tri-
age // Proc. of the Fourth Intern. Conf. on Genetic Algorithms. — 1991. — P. 334–338.
32. S t a d n y k I . Schema recombination in a pattern recognition problem // Genetic Algorithms and
their Applications: Proc. of the Sec. Intern. Conf. on Genetic Algorithms. — 1987. — P. 27–35.
33. M a h f o u d S . W . Crowding and preselection revisited / R. Manner and B. Manderick (Eds) //
Proc. of Parallel Problem Solving from Nature. — Amsterdam: Elsevier Sci. Publ. B.V., 1992. — 2.
— P. 27–36.
34. M e n g s h e o l O . , G o l d b e r g D . Probabilistic crowding: deterministic crowding with probabil-
istic replacement // Proc. of Genetic and Evol. Comput Conf. (GECCO 1999), Orlando (Florida,
USA), 13–17 July 1999). — 1999. — P. 409–416.
35. H a r i k G . Finding multimodal solutions using restricted tournament selection / L.J. Eshelman
(Ed.) // Proc. 6th Int. Conf. on Genetic Algorithms (ICGA-95), Pittsburgh, July 1995. — San Mateo
(CA): Morgan Kaufmann, 1995. — P. 24–31.
36. C e d e n o W . , V e m u r i V . Dynamic multimodal function optimization using genetic algorithms
// Proc. of the XVIII Latin-Amer. Inform. Conf. — Las Palmas de Gran Canaria (Spain), 1992. —
P. 292–301.
37. C e d e n o W . , V e m u r i V . R . , S l e z a k T . Multiniche crowding in genetic algorithms and its
application to the assembly of DNA restriction-fragments // Evol. Comput . — 1994. — 2, N 4. —
P. 321–345.
38. Y u E . L . , S u g a n t h a n P . N . Ensemble of niching algorithms // Inform. Sci. — 2010. — 180,
N 15. — P. 2815–2833.
39. http://garage.cse.msu.edu/hfc/hierarchical_fair_competition.htm.
40. H u J . , G o o d m a n E . D . Robust and efficient genetic algorithms with hierarchical niching and
a sustainable evolutionary computation model // Proc. of GECCO. — 2004. — 1. — P. 1220–1232.
Ïîñòóïèëà 23.10.2012
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
|
| id | nasplib_isofts_kiev_ua-123456789-86286 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-02T10:45:42Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Глибовец, Н.Н. Гулаева, Н.М. 2015-09-12T17:33:57Z 2015-09-12T17:33:57Z 2013 Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации / Н.Н. Глибовец, Н.М. Гулаева // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 15-22. — Бібліогр.: 40 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86286 004.023 Запропоновано огляд генетичних алгоритмів утворення ніш для розв’язку задач багатоекстремальної оптимізації. Ці алгоритми наведено згідно їх просторово-часової класифікації. Дано докладний опис методів на основі розподілу рівня пристосованості та методів витискання як найбільш поширених. За відсутності усталеної термінології запропоновано російськомовні відповідники англомовних термінів. In this paper, a comprehensive review of approaches to solve multimodal function optimization problems via genetic algorithms is provided. Niching genetic algorithms are presented according to their space–time classification. Methods based on fitness sharing and crowding methods are described in detail as they are the most frequently used. In the absence of established terminology, Russian-language equivalents of English terms are proposed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации Огляд генетичних алгоритмів утворення ніш для розв’язку задач багатоекстремальної оптимізації A review of niching genetic algorithms for multimodal function optimization Article published earlier |
| spellingShingle | Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации Глибовец, Н.Н. Гулаева, Н.М. Кибернетика |
| title | Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации |
| title_alt | Огляд генетичних алгоритмів утворення ніш для розв’язку задач багатоекстремальної оптимізації A review of niching genetic algorithms for multimodal function optimization |
| title_full | Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации |
| title_fullStr | Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации |
| title_full_unstemmed | Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации |
| title_short | Обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации |
| title_sort | обзор генетических алгоритмов образования ниш для решения задач многоэкстремальной оптимизации |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86286 |
| work_keys_str_mv | AT glibovecnn obzorgenetičeskihalgoritmovobrazovaniânišdlârešeniâzadačmnogoékstremalʹnoioptimizacii AT gulaevanm obzorgenetičeskihalgoritmovobrazovaniânišdlârešeniâzadačmnogoékstremalʹnoioptimizacii AT glibovecnn oglâdgenetičnihalgoritmívutvorennâníšdlârozvâzkuzadačbagatoekstremalʹnoíoptimízacíí AT gulaevanm oglâdgenetičnihalgoritmívutvorennâníšdlârozvâzkuzadačbagatoekstremalʹnoíoptimízacíí AT glibovecnn areviewofnichinggeneticalgorithmsformultimodalfunctionoptimization AT gulaevanm areviewofnichinggeneticalgorithmsformultimodalfunctionoptimization |