Проектирование ИТ-инфраструктуры
Предложена методика проектирования ИТ-инфраструктуры в условиях ограниченных ресурсов. Методика базируется на свойствах алгебры графов, генетических алгоритмах, сетях Петри и особенностях ограничений. Рассмотрены два подхода к решению задачи балансирования нагрузок в ИТ-инфраструктуре....
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , , , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/161457 |
| 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: | Проектирование ИТ-инфраструктуры / С.Л. Крывый, С.Д. Погорелый, Н.Н. Глибовец, Ю.В. Бойко, Н.Н. Сидорова // Кибернетика и системный анализ. — 2018. — Т. 54, № 6. — С. 141-158. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-161457 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1614572019-12-10T01:26:31Z Проектирование ИТ-инфраструктуры Крывый, С.Л. Погорелый, С.Д. Глибовец, Н.Н. Бойко, Ю.В. Сидорова, Н.Н. Програмно-технічні комплекси Предложена методика проектирования ИТ-инфраструктуры в условиях ограниченных ресурсов. Методика базируется на свойствах алгебры графов, генетических алгоритмах, сетях Петри и особенностях ограничений. Рассмотрены два подхода к решению задачи балансирования нагрузок в ИТ-инфраструктуре. Запропоновано методику проектування ІТ-інфраструктури в умовах обмежених ресурсів. Методика ґрунтується на властивостях алгебри графів, генетичних алгоритмів, мереж Петрі та особливостях обмежень. Розглянуто два підходи до розв’язання задачі балансування навантажень в ІТ-інфраструктурі. A metodology for development of IT infrastructure under conditions of constraints resources is proposed. This metodology is based on the properties of graph algebra, genetic algorithms, Petri nets, and specific features of the constraints. Two approaches to solving load-balancing problems in IT infrastructure are considered. 2018 Article Проектирование ИТ-инфраструктуры / С.Л. Крывый, С.Д. Погорелый, Н.Н. Глибовец, Ю.В. Бойко, Н.Н. Сидорова // Кибернетика и системный анализ. — 2018. — Т. 54, № 6. — С. 141-158. — Бібліогр.: 10 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/161457 51.681.3 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 |
2018 |
| topic_facet |
Програмно-технічні комплекси |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/161457 |
| citation_txt |
Проектирование ИТ-инфраструктуры / С.Л. Крывый, С.Д. Погорелый, Н.Н. Глибовец, Ю.В. Бойко, Н.Н. Сидорова // Кибернетика и системный анализ. — 2018. — Т. 54, № 6. — С. 141-158. — Бібліогр.: 10 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT kryvyjsl proektirovanieitinfrastruktury AT pogorelyjsd proektirovanieitinfrastruktury AT glibovecnn proektirovanieitinfrastruktury AT bojkoûv proektirovanieitinfrastruktury AT sidorovann proektirovanieitinfrastruktury |
| first_indexed |
2025-07-14T14:01:37Z |
| last_indexed |
2025-07-14T14:01:37Z |
| _version_ |
1837631220734754816 |
| fulltext |
Ñ.Ë. ÊÐÛÂÛÉ, Ñ.Ä. ÏÎÃÎÐÅËÛÉ, Í.Í. ÃËÈÁÎÂÅÖ, Þ.Â. ÁÎÉÊÎ, Í.Í. ÑÈÄÎÐÎÂÀ
ÓÄÊ 51.681.3 ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ ÈÒ-ÈÍÔÐÀÑÒÐÓÊÒÓÐÛ
Àííîòàöèÿ. Ïðåäëîæåíà ìåòîäèêà ïðîåêòèðîâàíèÿ ÈÒ-èíôðàñòðóêòóðû
â óñëîâèÿõ îãðàíè÷åííûõ ðåñóðñîâ. Ìåòîäèêà áàçèðóåòñÿ íà ñâîéñòâàõ àë-
ãåáðû ãðàôîâ, ãåíåòè÷åñêèõ àëãîðèòìàõ, ñåòÿõ Ïåòðè è îñîáåííîñòÿõ îãðà-
íè÷åíèé. Ðàññìîòðåíû äâà ïîäõîäà ê ðåøåíèþ çàäà÷è áàëàíñèðîâàíèÿ íà-
ãðóçîê â ÈÒ-èíôðàñòðóêòóðå.
Êëþ÷åâûå ñëîâà: àëãåáðà ãðàôîâ, òîïîëîãèÿ, ÈÒ-èíôðàñòðóêòóðà, ãåíåòè-
÷åñêèå àëãîðèòìû, ñåòè Ïåòðè.
ÂÂÅÄÅÍÈÅ
Ïðîåêòèðîâàíèå ÈÒ-èíôðàñòðóêòóðû, êàê ïðàâèëî, íà÷èíàåòñÿ ñ ðàçðàáîòêè ìà-
òåìàòè÷åñêîé ìîäåëè åå òîïîëîãèè, ò.å. ìîäåëè îðãàíèçàöèè âíóòðåííèõ
è âíåøíèõ ñâÿçåé ìåæäó âõîäÿùèìè â åå ñîñòàâ îáúåêòàìè [1]. Âûáîð òîïîëî-
ãèè ÈÒ-èíôðàñòðóêòóðû âûïîëíÿåòñÿ ïî ðåçóëüòàòàì àíàëèçà ðàçëè÷íûõ ìîäåëåé
òàêîé òîïîëîãèè. Íàèáîëåå ïîäõîäÿùèìè ìîäåëÿìè òîïîëîãèè ÈÒ-èíôðàñòðóêòó-
ðû â äàííîì ñëó÷àå âûñòóïàþò ãðàôîâûå ìîäåëè, â êîòîðûõ îáúåêòû àññîöèèðó-
þòñÿ ñ âåðøèíàìè ãðàôà, à ñâÿçè — ñ ðåáðàìè ãðàôà. Ïðè ýòîì ïðåäïî÷òåíèå
îòäàåòñÿ íåîðèåíòèðîâàííûì ãðàôàì, ïîñêîëüêó ñ÷èòàåòñÿ, ÷òî ðåáðî íåîðèåíòè-
ðîâàííîãî ãðàôà ìîäåëèðóåò äâóñòîðîííþþ ñâÿçü ìåæäó îáúåêòàìè. Ìîäåëü, îá-
ëàäàþùàÿ íåîáõîäèìûìè ñâîéñòâàìè, âûáèðàåòñÿ äëÿ ðåàëèçàöèè îïèñûâàåìîé
åþ òîïîëîãèè ïðîåêòèðóåìîé ÈÒ-èíôðàñòðóêòóðû. Îñíîâíûìè ñâîéñòâàìè òîïî-
ëîãèè ÿâëÿþòñÿ åå óñòîé÷èâîñòü ê ïîâðåæäåíèÿì ëèíèé ñâÿçè è/èëè ñîñòàâëÿþ-
ùèõ åå îáúåêòîâ. Ïðàâèëüíî ñïðîåêòèðîâàííàÿ òîïîëîãèÿ äîëæíà áûòü ïðåäñòàâ-
ëåíà ñâÿçíûì ãðàôîì, ïîñêîëüêó åãî ñâÿçíîñòü ãàðàíòèðóåò äîñòóï ê êàæäîìó
îáúåêòó ÈÒ-èíôðàñòðóêòóðû. Åñëè òîïîëîãèÿ ÈÒ-èíôðàñòðóêòóðû ïðåäñòàâëåíà
ñâÿçíûì ãðàôîì, òî òàêóþ ñòðóêòóðó áóäåì íàçûâàòü æèâîé.
Ñëîæíîñòü âûáîðà ïîäõîäÿùåé òîïîëîãèè ñîñòîèò â òîì, ÷òî ýòà çàäà÷à íî-
ñèò ïðîòèâîðå÷èâûé õàðàêòåð. Ïðîòèâîðå÷èâîñòü çàêëþ÷àåòñÿ â òîì, ÷òî âûáîð
íàèëó÷øåé ìîäåëè çàâèñèò îò ðÿäà îãðàíè÷åíèé, êîòîðûå íàêëàäûâàþò âîçìîæ-
íîñòè ðåàëèçàöèè. Îäíè îãðàíè÷åíèÿ íîñÿò ôèíàíñîâûé õàðàêòåð (îãðàíè÷åíèÿ
ôèíàíñèðîâàíèÿ, íå ïîçâîëÿþùèå ïðèîáðåñòè ëèíèè ñâÿçè ñ õîðîøåé ïðîïóñê-
íîé ñïîñîáíîñòüþ), äðóãèå îãðàíè÷åíèÿ èìåþò îáúåêòèâíûé õàðàêòåð è ñâÿçàíû
ñ îñîáåííîñòüþ ìåñòíîñòè, ïî êîòîðîé äîëæíû ïðîõîäèòü ëèíèè ñâÿçè (âîäíûå
ïðåïÿòñòâèÿ, ãîðîäñêèå êîììóíèêàöèè, íå ïîçâîëÿþùèå ïðîòÿíóòü ëèíèè ñâÿçè,
óðîâåíü êà÷åñòâà èìåþùèõñÿ êàíàëîâ è äðóãèå ïðè÷èíû).  ñâÿçè ñ ýòèì íàèëó÷-
øóþ òîïîëîãèþ íåëüçÿ ðåàëèçîâàòü â óñëîâèÿõ èìåþùèõñÿ îãðàíè÷åíèé.
Âîçíèêàåò âîïðîñ: êàê â óñëîâèÿõ äàííûõ îãðàíè÷åíèé âûáðàòü íàèëó÷øóþ
(îïòèìàëüíóþ) òîïîëîãèþ? Â íàñòîÿùåé ñòàòüå ïðåäëàãàþòñÿ ïîäõîäû ê ðåøå-
íèþ ýòîé çàäà÷è.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 141
© Ñ.Ë. Êðûâûé, Ñ.Ä. Ïîãîðåëûé, Í.Í. Ãëèáîâåö, Þ.Â. Áîéêî, Í.Í. Ñèäîðîâà, 2018
1. ÑÒÅÏÅÍÜ ÑÂßÇÍÎÑÒÈ ÑÂßÇÍÎÃÎ ÃÐÀÔÀ
Íåîðèåíòèðîâàííûì ãðàôîì íàçûâàåòñÿ ïàðà G V E� ( , ), ãäå V — ìíîæåñòâî
âåðøèí ãðàôà, E — ìíîæåñòâî ðåáåð, ñîñòîÿùåå èç íåóïîðÿäî÷åííûõ ïàð ýëå-
ìåíòîâ èç V (ò.å. ïàðû ( , )u � è ( , )� u ñ÷èòàþòñÿ îäèíàêîâûìè). Ãðàô G íàçûâà-
åòñÿ êîíå÷íûì, åñëè êîíå÷íî ìíîæåñòâî åãî âåðøèí V . Åñëè ( , )u E� � , òî âåð-
øèíû u, � íàçûâàþòñÿ êîíöàìè ýòîãî ðåáðà. Ðåáðî e E� íàçûâàåòñÿ èíöèäåí-
òíûì âåðøèíå u V� , åñëè ýòà âåðøèíà ÿâëÿåòñÿ êîíöîì ðåáðà e. Ñòåïåíüþ
âåðøèíû u V� íàçûâàåòñÿ ÷èñëî ðåáåð, èíöèäåíòíûõ ýòîé âåðøèíå. Ñòåïåíü
âåðøèíû u îáîçíà÷èì n u( ). Åñëè ñòåïåíü âåðøèíû ðàâíà íóëþ, òî òàêàÿ âåð-
øèíà íàçûâàåòñÿ èçîëèðîâàííîé, à åñëè ñòåïåíü âåðøèíû ðàâíà åäèíèöå, òî
òàêàÿ âåðøèíà íàçûâàåòñÿ êîíöåâîé èëè âèñÿ÷åé. Äâå âåðøèíû u, � �V ãðàôà
G V E( , ) ñâÿçàíû ìàðøðóòîì, åñëè ñóùåñòâóåò òàêàÿ ïîñëåäîâàòåëüíîñòü åãî âåð-
øèí u u uk1 2, , ,� , ÷òî u u� 1, � � uk è ( , )u u Ei i� �1 äëÿ âñåõ i k� �1 2 1, , ,� .
×èñëî k �1 íàçûâàåòñÿ äëèíîé ýòîãî ìàðøðóòà. Ìàðøðóò, ïåðâàÿ è ïîñëåäíÿÿ
âåðøèíû êîòîðîãî ñîâïàäàþò, íàçûâàåòñÿ öèêëîì. Ãðàô áåç öèêëîâ íàçûâàåò-
ñÿ àöèêëè÷åñêèì.
Ãðàô G V E� ( , ) íàçûâàåòñÿ ñâÿçíûì, åñëè ëþáûå äâå âåðøèíû ýòîãî ãðàôà
ñâÿçàíû ìàðøðóòîì. Ñâÿçíûé àöèêëè÷åñêèé ãðàô íàçûâàåòñÿ äåðåâîì. Âåðøèíà
äåðåâà íàçûâàåòñÿ âíóòðåííåé, åñëè ñòåïåíü ýòîé âåðøèíû áîëüøå åäèíèöû.
Ïðîâåðêà ñâÿçíîñòè ãðàôà âûïîëíÿåòñÿ àëãîðèòìîì ïîèñêà â ãëóáèíó (DFS-àëãî-
ðèòì), êîòîðûé ïîäðîáíî îïèñàí â [2].
1.1. Àëãåáðà ãðàôîâ. Ïóñòü U — íåêîòîðîå óíèâåðñàëüíîå ìíîæåñòâî, ýëå-
ìåíòû êîòîðîãî èñïîëüçóþòñÿ äëÿ îáîçíà÷åíèÿ âåðøèí. Îáû÷íî U � N, ãäå N —
ìíîæåñòâî íàòóðàëüíûõ ÷èñåë.
Îñíîâíûå îïåðàöèè íà êîíå÷íûõ ãðàôàõ íàä ìíîæåñòâîì U :
� � � � �( , ) — àáñîëþòíî ïóñòîé ãðàô;
� G e V E e� � ( , \ ){ } — óäàëåíèå ðåáðà e èç ãðàôà G V E� ( , );
� G V E i� �� � � �( \ , \ , ){ } { } — óäàëåíèå âåðøèíû � èç ãðàôà G V E� ( , );
� G e V E e �
( , ){ } — ââåäåíèå ðåáðà e â ãðàô G V E� ( , );
� G V E� �
� �( , ){ } — ââåäåíèå âåðøèíû � â ãðàô G V E� ( , ).
Ýòè îïåðàöèè ñîñòàâëÿþò ïîëíîå ìíîæåñòâî îïåðàöèé àëãåáðû êîíå÷íûõ ãðà-
ôîâ AG B U� � �( ( ), , , , , ){ }� � [3].
Ïîñêîëüêó îïåðàöèè è � ñâîäÿòñÿ ê îïåðàöèÿì îáúåäèíåíèÿ ñîîòâåòñòâóþ-
ùèõ ìíîæåñòâ, òî â ñèëó àññîöèàòèâíîñòè è êîììóòàòèâíîñòè îïåðàöèè îáúåäèíå-
íèÿ èñïîëüçóåì ñîêðàùåíèÿ G e e ek { }1 2, , ,� äëÿ ïîñëåäîâàòåëüíîñòè îïåðàöèé
G e e ek { } { } { }1 2 � . Àíàëîãè÷íîå ñîêðàùåíèå áóäåì èñïîëüçîâàòü è äëÿ
îïåðàöèè ââåäåíèÿ âåðøèí â ãðàô. Çàìåòèì òàêæå, ÷òî îïåðàöèÿ � è îïåðàöèÿ �
ÿâëÿþòñÿ êîììóòàòèâíûìè ïî âòîðîìó àðãóìåíòó, ò.å. ( )G e e� �{ } { }1 �
� ( )G e e� �{ } { }1 è ( ) ( )G G� � � � �{ } { } { } { }� � � �1 1 . Ýòî îçíà÷àåò, ÷òî ïîðÿäîê
óäàëåíèÿ ðåáåð è âåðøèí èç ãðàôà íåñóùåñòâåíåí.
Îïåðàöèÿ óäàëåíèÿ ðåáðà e u� ( , )� â ãðàôå G V E� ( , ) ìîæåò ïðèâåñòè ê ãðà-
ôó, êîòîðûé íå ÿâëÿåòñÿ ñâÿçíûì. Àíàëîãè÷íàÿ ñèòóàöèÿ è îòíîñèòåëüíî îïåðà-
öèè óäàëåíèÿ âåðøèíû. Ïîñêîëüêó âìåñòå ñ âåðøèíàìè óäàëÿþòñÿ è âñå èíöè-
äåíòíûå åé ðåáðà, òî âîçíèêàåò âîïðîñ, ñêîëüêî ðåáåð ìîæíî óäàëèòü èç ñâÿçíî-
ãî ãðàôà G V E� ( , ), ÷òîáû ïîñëå âûïîëíåíèÿ ýòèõ îïåðàöèé ïîëó÷åííûé ãðàô
îñòàâàëñÿ ñâÿçíûì.
Âåðøèíà ãðàôà íàçûâàåòñÿ òî÷êîé ñî÷ëåíåíèÿ, åñëè åå óäàëåíèå ïðèâîäèò
ê íåñâÿçíîìó ãðàôó. Ðåáðî ãðàôà íàçûâàåòñÿ ìîñòîì èëè ñóùåñòâåííûì ðåáðîì,
åñëè åãî óäàëåíèå ïðèâîäèò ê íåñâÿçíîìó ãðàôó. Îòñþäà ñëåäóåò, ÷òî ñëàáûìè
çâåíüÿìè â ëþáîé òîïîëîãèè ïðîåêòèðóåìîé ÈÒ-èíôðàñòðóêòóðû ÿâëÿþòñÿ
ìîñòû è òî÷êè ñî÷ëåíåíèÿ. Ââåäåì òàêîå îïðåäåëåíèå.
Îïðåäåëåíèå 1. Ñòåïåíüþ ñâÿçíîñòè ñâÿçíîãî ãðàôà íàçûâàåòñÿ ìàêñèìàëü-
íîå ÷èñëî d ðåáåð, óäàëåíèå êîòîðûõ èç ãðàôà íå âûâîäèò åãî èç êëàññà ñâÿçíûõ
ãðàôîâ, à óäàëåíèå ( )d �1 -ãî ðåáðà ïðèâîäèò ê íåñâÿçíîìó ãðàôó.
142 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
Èçâåñòíî, ÷òî óäàëåíèå ðåáðà, ïðèíàäëåæàùåãî íåêîòîðîìó öèêëó ãðàôà
G V E� ( , ), íå íàðóøàåò ñâÿçíîñòè ãðàôà, à ñòåïåíü ñâÿçíîñòè ðàâíà åãî öèêëîìà-
òè÷åñêîìó ÷èñëó d E V� � �| | | | 1 (ñì. [2]). Ñëåäîâàòåëüíî, ÷èñëî âîçìîæíûõ
îïåðàöèé óäàëåíèÿ ðåáðà â ñâÿçíîì ãðàôå G V E� ( , ), íå âûâîäÿùèõ ãðàô èç
êëàññà ñâÿçíûõ, ðàâíî d, à îïåðàöèÿ óäàëåíèÿ âåðøèíû â ñâÿçíîì ãðàôå íå íàðó-
øàåò åãî ñâÿçíîñòè, åñëè âñå ðåáðà, èíöèäåíòíûå ýòîé âåðøèíå, ïðèíàäëåæàò
íåêîòîðûì öèêëàì ýòîãî ãðàôà èëè ýòà âåðøèíà êîíöåâàÿ.
Èç ñêàçàííîãî ñëåäóåò, ÷òî íàèáîëåå óÿçâèìà òîïîëîãèÿ, ãðàôîì êîòîðîé ÿâ-
ëÿåòñÿ äåðåâî, à íàèìåíåå óÿçâèìàÿ òîïîëîãèÿ èìååò ãðàô ïîëíûé. Äåéñòâèòåëüíî,
â äåðåâå êàæäàÿ âíóòðåííÿÿ âåðøèíà ÿâëÿåòñÿ òî÷êîé ñî÷ëåíåíèÿ, à êàæäîå ðåá-
ðî ÿâëÿåòñÿ ìîñòîì. Åñëè â ïîëíîì ãðàôå n-ãî ïîðÿäêà ïðè óäàëåíèè âåðøèíû îí
îñòàåòñÿ ïîëíûì ãðàôîì n�1-ãî ïîðÿäêà, òî ñòåïåíü åãî ñâÿçíîñòè ðàâíà
n n2 3 2
2
� �
. Òàê, äëÿ ïîëíîãî ãðàôà ïÿòîãî ïîðÿäêà ñòåïåíü åãî ñâÿçíîñòè ðàâíà
øåñòè.
1.2. Ïðîèçâîäíûå îïåðàöèè àëãåáðû ãðàôîâ. Ðàññìîòðåííûå âûøå îïåðà-
öèè àëãåáðû ãðàôîâ AG ÿâëÿþòñÿ îñíîâíûìè â ñìûñëå îïðåäåëåíèÿ óíèâåðñàëü-
íîé àëãåáðû [3]. Êðîìå ýòèõ îïåðàöèé íà ãðàôàõ îïðåäåëÿþòñÿ è òàêèå, êîòîðûå
âûðàæàþòñÿ ïîñðåäñòâîì îñíîâíûõ îïåðàöèé. Ðàññìîòðèì òå èç íèõ, êîòîðûå
äàëåå èñïîëüçóþòñÿ â ðàáîòå.
Ïóñòü G V E� ( , ) è G V E1 1 1� ( , ) — êîíå÷íûå ãðàôû, òîãäà
— îáúåäèíåíèåì ãðàôîâ G è G1 íàçûâàåòñÿ ãðàô G G V V E V
�
1 1 1( , );
— ïåðåñå÷åíèåì ãðàôîâ G è G1 íàçûâàåòñÿ ãðàô G G V V E V� � � �1 1 1( , );
— ñîåäèíåíèåì ãðàôîâ G è G1 òàêèõ, ÷òî V V� ��1 , íàçûâàåòñÿ ãðàô
G G V V E� �
1 1( , ), ãäå
�
� � �E E E u u V V1 1{ }( , ) | ,� � ;
— äåêàðòîâûì ïðîèçâåäåíèåì ãðàôîâ G è G1 íàçûâàåòñÿ ãðàô
G G V V E� � �
1 1( , ), ãäå (( , ), ( , )) ( ( , ) ) (( , )u u E u u E u u� � � �1 1 1 1 1 1�
� � � � � �
� � �E ( ))� �1 ;
— äîïîëíåíèåì ãðàôà G íàçûâàåòñÿ ãðàô G V V V E iV� �
( , \ { }), ãäå
i u u u VV � �{ }( , ) | — äèàãîíàëü ìíîæåñòâà V .
Íåïîñðåäñòâåííî èç îïðåäåëåíèé îïåðàöèé ñëåäóåò ñïðàâåäëèâîñòü òàêèõ
ñâîéñòâ: � �G H Q AG, , èìååò ìåñòî
G G G G G G H Y G G H Q G H Q
�
�
�
�
� , , , ( ) ( ) ;
G G G G G H H G G H Q G H Q� � � � � � � � � � � �� �, , , ( ) ( ) ;
G H G G H G G�
�
� �( ) ( ) ;
G G H H G G H Q G H Q� � � � � � � � � �� �, , ( ) ( ) ;
G H Q G H G Q G H Q G H G Q�
� �
� � � � � � �( ) , ( ) ;
G G H H G G H Q G H Q� � � � � � � � � �� �, , ( ) ( ) ;
G H Q G H G Q G H Q G H G Q�
� �
� � � � � � �( ) ( ) ( ), ( ) ( ) ( ).
Èç ïåðâûõ òðåõ ãðóïï ñâîéñòâ îïåðàöèé ñëåäóåò, ÷òî îòíîñèòåëüíî îïåðàöèé
ïåðåñå÷åíèÿ è îáúåäèíåíèÿ àëãåáðà AG ÿâëÿåòñÿ ðåøåòêîé ñ íóëåì, â ðîëè êî-
òîðîãî âûñòóïàåò àáñîëþòíî ïóñòîé ãðàô �. Ïîñêîëüêó íîñèòåëü ðåøåòêè —
÷àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî, îïðåäåëÿåìîå ñîîòíîøåíèåì G H� �
� � �G H G èëè äâîéñòâåííûì îáðàçîì G H G H H� �
� , òî èç G H� �
� � � � �G V V E E V E( , ) ( , )1 1 ñëåäóåò, ÷òî ãðàô G ÿâëÿåòñÿ ïîäãðàôîì ãðàôà H .
Íåòðóäíî ïîíÿòü, ÷òî àòîìàìè â äàííîé ðåøåòêå, ò.å. ìèíèìàëüíûìè ñâÿçíûìè
ãðàôàìè, áóäóò äåðåâüÿ ñ äâóìÿ âåðøèíàìè, ñîåäèíåííûìè ðåáðîì.
Àëãåáðó AG , ñèãíàòóðà îïåðàöèé êîòîðîé ðàñøèðåíà ââåäåííûìè âûøå
îïåðàöèÿìè, íàçîâåì ðàñøèðåííîé àëãåáðîé ãðàôîâ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 143
2. ÕÀÐÀÊÒÅÐÈÑÒÈÊÈ ÒÎÏÎËÎÃÈÉ
Ðàññìîòðèì íåêîòîðûå ÷àñòî èñïîëüçóåìûå òîïîëî-
ãèè, â îñíîâå êîòîðûõ ëåæàò îïðåäåëåííûå òèïû ãðà-
ôîâ (ñì. [4]), è îõàðàêòåðèçóåì ýòè òîïîëîãèè, èñõîäÿ
èç îïðåäåëåííîé âûøå àëãåáðû AG.
2.1. Îäíîêàíàëüíàÿ ìàãèñòðàëü (äåðåâî). Äëÿ
ïðåäñòàâëåíèÿ ÈÒ-èíôðàñòðóêòóðû ñ ýòîé òîïîëîãèåé
ìàãèñòðàëü áóäåì ðàññìàòðèâàòü êàê îáúåêò, èçîáðàæà-
åìûé âåðøèíîé ãðàôà. Òîãäà ãðàô, ëåæàùèé â îñíîâå
ýòîé òîïîëîãèè, èìååò âèä çâåçäû (à ïî ñóòè äåðåâà),
ïîêàçàííîé íà ðèñ. 1, ãäå s s sr1 2, , ,� , k k kn1 2, , ,� —
îáúåêòû, à M — ìàãèñòðàëü. Ýòîò ãðàô èìååò îäíó
âíóòðåííþþ âåðøèíó (ìàãèñòðàëü) ñòåïåíè n M r n( ) � � è r n� êîíöåâûõ âåð-
øèí. Âûðàæåíèå ýòîé òîïîëîãèè â àëãåáðå ãðàôîâ AG èìååò âèä
G s s k k M s M s M kr n r� � ( , , , , , ) ( , ), , ( , ), ( , ), ,� { } {1 1 1 1� � � � ( , )M kn }.
 òåðìèíàõ îïåðàöèé ðàñøèðåííîé AG àëãåáðàè÷åñêîå âûðàæåíèå ïðèíèìàåò âèä
G M s s s M k k k M s s s k kr n r� �
� � �{ } { } {1 2 1 2 1 2 1, , , , , , , , , , ,� � � 2 , ,� kn }.
Êàê âèäíî èç ïðèâåäåííûõ âûðàæåíèé, âàæíûì ñâîéñòâîì äàííîé òîïîëîãèè
ÿâëÿåòñÿ åå óñòîé÷èâîñòü îòíîñèòåëüíî óäàëåíèÿ ëþáîãî
÷èñëà êîíå÷íûõ âåðøèí, íåóñòîé÷èâîñòü îòíîñèòåëüíî
óäàëåíèÿ âíóòðåííåé âåðøèíû (ìàãèñòðàëè) è óäàëåíèÿ
õîòÿ áû îäíîãî ðåáðà. Ñëåäîâàòåëüíî, ïðè ïðèìåíåíèè
ýòîé òîïîëîãèè íåîáõîäèìî èñïîëüçîâàòü íàäåæíûå ëè-
íèè ñâÿçè è íàäåæíóþ ìàãèñòðàëü.
2.2. Ìíîãîêàíàëüíàÿ ìàãèñòðàëü (ïîëíûé òðåõ-
äîëüíûé ãðàô). Óñîâåðøåíñòâîâàíèåì îäíîêàíàëüíîé
ìàãèñòðàëè äëÿ ïîâûøåíèÿ íàäåæíîñòè ÈÒ-èíôðàñòðóê-
òóðû ÿâëÿåòñÿ ìíîãîêàíàëüíàÿ ìàãèñòðàëü. Ãðàô, ëåæà-
ùèé â îñíîâå ýòîé òîïîëîãèè, åñòü òðåõäîëüíûé ãðàô
(ðèñ. 2), ãäå s s sr1 2, , ,� , k k kn1 2, , ,� — îáúåêòû,
M M m1, ,� — ìàãèñòðàëè.
Ñòåïåíü ñâÿçíîñòè äàííîãî ãðàôà ñîñòàâëÿåò d E V rm nm r� � � � � � �| | | | 1
� � � � � � �n m r n m1 1 1( )( ). Åñëè ýòó òîïîëîãèþ ñðàâíèâàòü ñ ïðåäûäóùåé, ãäå
m �1 è d � 0, òî ñòåïåíü íàäåæíîñòè òàêîé ÈÒ-èíôðàñòðóêòóðû óâåëè÷èâàåòñÿ â
m�1 ðàç. Àëãåáðàè÷åñêîå âûðàæåíèå äëÿ ýòîé òîïîëîãèè èìååò âèä
G s s k k M M M s M sr n m r� � ( , , , , , , , ( , ), , ( , ),,� { } {1 1 1 1 1 1� � � � �
� � � � �, ( , ), , ( , ), ( , ), , ( , ), , ( , ), ,M s M s M k M k M km m r n m1 1 1 1 1 ( , )M km n }.
 òåðìèíàõ îïåðàöèé ðàñøèðåííîé àëãåáðû ãðàôîâ ýòà òîïîëîãèÿ èìååò âèä
G M M M s s k km r n� �{ } { }1 2 1 1, , , , , , , ,� � � .
Îòñþäà ñëåäóåò, ÷òî âûõîä èç ñòðîÿ ëþáîé m�1 ìàãèñòðàëè îñòàâëÿåò ÈÒ-èíôðà-
ñòðóêòóðó æèâîé (â ýòîì ñëó÷àå îíà ðåäóöèðóåòñÿ ê îäíîêàíàëüíîé ìàãèñòðàëè).
Àíàëîãè÷íîå óòâåðæäåíèå ñïðàâåäëèâî è äëÿ ðåáåð.
2.3. Øåñòèãðàííèê (êóá). Ãðàô, ëåæàùèé â îñíîâå ýòîé òîïîëîãèè, ÿâëÿåò-
ñÿ øåñòèãðàííèêîì (ðèñ. 3). Ñòåïåíü ñâÿçíîñòè äëÿ ýòîãî ãðàôà ñîñòàâëÿåò
d � � � �12 8 1 5. Àëãåáðàè÷åñêîå âûðàæåíèå äëÿ ýòîãî ãðàôà èìååò âèä
G � � ( , , , , , , , ) ( , ), ( , ), ( , ), ( , ), (� { } {1 2 3 4 5 6 7 8 1 2 1 4 1 5 2 3 2 6, ),
( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , )3 4 3 7 4 8 5 6 5 8 6 7 7 8 }. (1)
144 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
s1 s2 … sr
k1 k2 … kn
M
Ðèñ. 1. Îäíîêàíàëüíàÿ ìà-
ãèñòðàëü
s1 s2 … sr
k1 k2 … kn
M2M1 Mm
…
Ðèñ. 2. Ìíîãîêàíàëüíàÿ
ìàãèñòðàëü
 òåðìèíàõ îïåðàöèé ðàñøèðåííîé àëãåáðû ãðàôîâ àëãåáðàè÷åñêîå âûðàæå-
íèå ýòîãî ãðàôà ïðèíèìàåò âèä äåêàðòîâîãî ïðîèçâåäåíèÿ äâóõ ãðàôîâ:
G V E V E� � � � � �( , , ( , ) ) ( , , , , ( , ), ( ,{ } { } { } {1 2 1 2 3 4 5 6 3 4 4 51 1 ), ( , ), ( , )5 6 6 3 }). (2)
Ïîñòðîåííûå ïî ýòèì âûðàæåíèÿì ãðàôû ÿâëÿþò-
ñÿ èçîìîðôíûìè, â ÷åì ìîæíî óáåäèòüñÿ íåïîñðåä-
ñòâåííî.
Èç ïðåäñòàâëåíèÿ (1) ñëåäóåò, ÷òî äàííàÿ òîïîëî-
ãèÿ óñòîé÷èâà ê óäàëåíèþ ëþáûõ äâóõ âåðøèí è ëþ-
áûõ äâóõ ðåáåð, à òàêæå ÷òî èç ïåðâîãî àðãóìåíòà ìîæ-
íî óäàëèòü ÷åòûðå ðåáðà, à èç âòîðîãî àðãóìåíòà —
îäíî ðåáðî è íàîáîðîò. Îòñþäà òàêæå âûòåêàåò, ÷òî èç
äàííîãî ãðàôà ìîæíî óäàëèòü âñå âåðøèíû, ïðèíàäëå-
æàùèå îäíîé ãðàíè, è ðåçóëüòèðóþùàÿ ñòðóêòóðà
áóäåò æèâîé.
Èç ïðåäñòàâëåíèÿ (2) äëÿ ýòîãî ãðàôà î÷åâèäíûì îáðàçîì ìîæíî ïîñòðîèòü
ãèïåðøåñòèãðàííèê.
2.4. Ãèïåðøåñòèãðàííèê. Ãðàô, ëåæàùèé â îñíîâå ýòîé òîïîëîãèè, íàçûâà-
åòñÿ ãèïåðøåñòèãðàííèêîì (ðèñ. 4).
Áîëåå òî÷íóþ õàðàêòåðèñòèêó ìîæíî ïîëó÷èòü, ïðîàíàëèçèðîâàâ àëãåáðà-
è÷åñêîå âûðàæåíèå äëÿ ýòîãî ãðàôà, êîòîðîå èìååò âèä
( ) (, , , , ,T T T T T1 2 2 3 3 4 4 1 5 6
�
T T T6 7 7 8 8 5, , , ),
ãäå Ti j, — äåðåâî ñ äâóìÿ âåðøèíàìè i j, , ñîåäèíåííûìè ðåáðîì (ìèíèìàëü-
íûé ñâÿçíûé ãðàô).
Èç ýòîãî ïðåäñòàâëåíèÿ ñëåäóåò, ÷òî óäàëåíèå ëþáûõ äâóõ ñìåæíûõ âåðøèí
â ëþáîì àðãóìåíòå ïðèâîäèò ê ñâÿçíîìó ãðàôó, êîòîðûé èçîìîðôåí øåñòèãðàííè-
êó. Îòñþäà âûòåêàåò, ÷òî óäàëåíèå ëþáûõ äâóõ ãðàíåé (èëè âåðøèí ýòèõ ãðàíåé)
è ëþáûõ äâóõ ðåáåð íå íàðóøàåò ñâÿçíîñòè ãèïåðøåñòèãðàííèêà. Êðîìå òîãî, óäà-
ëåíèå ðåáðà â ëþáîì àðãóìåíòå â ïðèâåäåííîì âûøå âûðàæåíèè îñòàâëÿåò ãðàô
ñâÿçíûì. À ýòî çíà÷èò, ÷òî â ðåçóëüòèðóþùåì ãðàôå ìîæíî óäàëèòü âîñåìü ðåáåð,
êîòîðûå ñîîòâåòñòâóþò óäàëåííîìó ðåáðó.
Ìàêñèìàëüíîå ÷èñëî ðåáåð, êîòîðûå ìîæíî óäàëèòü èç ýòîãî ãðàôà, ñîñòàâ-
ëÿåò d E V� � � � � � �| | | | 1 36 16 1 21. Îòñþäà ñëåäóåò, ÷òî ýòîò ãðàô áîëåå óñòîé-
÷èâ ïî îòíîøåíèþ ê îïåðàöèè óäàëåíèÿ ðåáðà, ÷åì øåñòèãðàííèê.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 145
1
2 3
5 8
4
6 7
Ðèñ. 3. Øåñòèãðàííèê
1
2 3
4 5
6 7
8
� �
8,1 8,4
8,2 8,3
7,1 7,4
7,2
7,3
5,1 5,4
5,2 5,3
6,1
6,2 6,3
6,4
Ðèñ. 4. Ãèïåðøåñòèãðàííèê
2.5. Ðåøåòêà. Â îñíîâå ýòîé òîïîëîãèè ëåæèò n-ìåðíàÿ ðåøåòêà (ðèñ. 5, äâó-
ìåðíàÿ ðåøåòêà — íàèáîëåå ïðîñòîé âàðèàíò).
Àëãåáðàè÷åñêîå âûðàæåíèå äëÿ ýòîãî ãðàôà èìååò âèä
[( ) ( ), , , ,T T T T1 2 2 3 4 5 5 6
�
,
ãäå Ti j, — äåðåâüÿ, àíàëîãè÷íûå
ïðåäñòàâëåííûì â ï. 2.4. Îòñþäà
ñëåäóåò, ÷òî èç àðãóìåíòîâ íåëüçÿ
óäàëèòü íè îäíîãî ðåáðà, ïîñêîëü-
êó ðåçóëüòèðóþùèé ãðàô ñòàíåò íå-
ñâÿçíûì, ò.å. àðãóìåíòû ýòîãî ïðî-
èçâåäåíèÿ áóäóò íåðåäóöèðóåìû ê
áîëåå ïðîñòûì ñâÿçíûì ãðàôàì, êî-
òîðûå ïîðîæäàþò òàêóþ ðåøåòêó.
Èç ñêàçàííîãî âûòåêàåò, ÷òî àëãåáðà ãðàôîâ ïîçâîëÿåò ïðîåêòèðîâàòü ÈÒ-èí-
ôðàñòðóêòóðó ìåòîäîì ñíèçó–ââåðõ, èñõîäÿ èç èìåþùèõñÿ ñðåäñòâ è âîçìîæíîñòåé,
â òî âðåìÿ êàê îïåðàöèè ðàñøèðåííîé àëãåáðû ïîçâîëÿþò ïðîåêòèðîâàòü òîïîëîãèþ
ÈÒ-èíôðàñòðóêòóðû ìåòîäîì ñâåðõó–âíèç. Ýòî îçíà÷àåò, ÷òî âíà÷àëå âûáèðàåòñÿ
ìàêñèìàëüíî íàäåæíàÿ òîïîëîãèÿ, à çàòåì íà îñíîâàíèè ýòîé òîïîëîãèè óäàëÿþòñÿ
òå ýëåìåíòû, ðåàëèçàöèÿ êîòîðûõ â ñèëó èìåþùèõñÿ îãðàíè÷åíèé íåâîçìîæíà.
 ðåçóëüòàòå ïðîåêòèðîâàíèÿ áóäåò âûáðàíà òîïîëîãèÿ, êîòîðàÿ ðåàëèçóåìà èìåþ-
ùèìèñÿ ñðåäñòâàìè.
3. ÏÐÈÌÅÐ ÏÐÎÅÊÒÈÐÎÂÀÍÈß ÒÎÏÎËÎÃÈÈ
Çàäà÷à ñîñòîèò â ïðîåêòèðîâàíèè òîïîëîãèè ÈÒ-èíôðàñòðóêòóðû íåêîòîðîé
îðãàíèçàöèè, ñîñòîÿùåé èç äåñÿòè îáúåêòîâ: o o o1 2 10, , ,� , ãåîãðàôè÷åñêè ðàñ-
ïîëîæåííûõ â ðàìêàõ îäíîãî ãîðîäà ñ ìàêñèìàëüíîé îòäàëåííîñòüþ íà d îáú-
åêòîâ îäèí îò äðóãîãî.
3.1. Ïðîåêòèðîâàíèå ìåòîäîì ñíèçó–ââåðõ. Íà ïåðâîì øàãå ïðîåêòèðîâà-
íèÿ òîïîëîãèè ñòðîèì ãðàô G o o o� �� { }1 2 10, , ,� (ðèñ. 6, à). Èç ýòèõ âåðøèí
âûäåëÿåì îñíîâíûå, ÷åðåç êîòîðûå äîëæíû ïðîõîäèòü âñå èëè á�ëüøàÿ ÷àñòü èí-
ôîðìàöèîííûõ ïîòîêîâ, íàïðèìåð âåðøèíû o o o1 8 4, , . Òàêîå âûäåëåíèå íåîáõî-
äèìî äëÿ ïðåäñòàâëåíèÿ âîçìîæíîé òîïîëîãèè.
Äàëåå ñòðîèì äåðåâî èç èìåþùèõñÿ âåðøèí, ÷òî ïðèâîäèò, íàïðèìåð, ê ãðà-
ôó G G o o o o o o1 1 8 2 8 8 10� { }( , ), ( , ), , ( , )� . Èç ðèñ. 6, a âèäíî, ÷òî îñíîâíàÿ
ñâÿçü äîëæíà áûòü ìåæäó îáúåêòàìè o1– o8– o4 . Òîãäà òàêàÿ ëèíèÿ ÿâëÿåòñÿ ìî-
äåëüþ îäíîêàíàëüíîé ìàãèñòðàëè, ïðåäñòàâëåííîé âåðøèíîé o8 , ê êîòîðîé ïîä-
êëþ÷åíû âñå îñòàëüíûå îáúåêòû. Ïîëó÷àåì ãðàô, ïðèâåäåííûé íà ðèñ. 6, á. Ïðè
ýòîì ëèíèè ñâÿçè o1– o8 , o8– o4 äîëæíû áûòü íàèáîëåå íàäåæíûìè â ïðîåêòèðó-
åìîé èíôðàñòðóêòóðå. Äàëåå ïðîèñõîäèò îöåíêà ñòîèìîñòè ëèíèé ñâÿçè è âîç-
ìîæíîñòè èõ ðåàëèçàöèè (÷òî ìîæåò èçìåíèòü ïðèîðèòåòû), à çàòåì îïðåäåëÿþò-
ñÿ äîïîëíèòåëüíûå ëèíèè ñâÿçè, âûáîð êîòîðûõ ïðîäèêòîâàí âíóòðåííèìè ïî-
òðåáíîñòÿìè ñ ó÷åòîì èìåþùèõñÿ
îãðàíè÷åíèé (íàïðèìåð, ñâÿçü o4– o9).
Åñëè ïîëó÷åííóþ òîïîëîãèþ ïðè-
íÿòü çà îñíîâó, òî äëÿ îáåñïå÷åíèÿ åå
íàäåæíîñòè ïðåäñòàâèì òîïîëîãèþ êî-
ëåñà, íàèáîëåå áëèçêóþ ê ïîëó÷åííîé.
Ñòåïåíü ñâÿçíîñòè äàííîãî ãðàôà
ðàâíà äåâÿòè. Êàê âèäíî èç ðèñ. 7, à, òà-
êàÿ òîïîëîãèÿ óñòîé÷èâà íå òîëüêî
â ñëó÷àå âûõîäà ëèíèé ñâÿçè, íî è ïðè
âûõîäå èç ñòðîÿ äâóõ èç îñíîâíûõ âåð-
146 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
1 2 3
�
4 5 6
�
1, 4 1, 5 1, 6
3, 4 3, 5 3, 6
2, 4
2, 5
2, 6
Ðèñ. 5. Ðåøåòêà
o1 o6
o2 o7
o3 o8
o4 o9
o5 o10
O1 o6
o2
o7
o3 o9
o5 o10
O8
O4
Ðèñ. 6. Èñõîäíûå ãðàôû
à á
øèí. Åñëè òàêóþ òîïîëîãèþ
ìîæíî ðåàëèçîâàòü â óñëîâèÿõ
èìåþùèõñÿ îãðàíè÷åíèé, òî îíà
ïðèíèìàåòñÿ ê ðåàëèçàöèè. Ïîñëå
ýòîãî îêîí÷àòåëüíî îïðåäåëÿåòñÿ
ñòîèìîñòü çàòðàò. Åñëè ýòè îãðà-
íè÷åíèÿ íå ïîçâîëÿþò ðåàëèçî-
âàòü òàêóþ òîïîëîãèþ, òî îíà
îïòèìèçèðóåòñÿ ê âèäó, êîòîðûé
óäîâëåòâîðÿåò óñëîâèÿì îãðàíè-
÷åíèé.
3.2. Ïðîåêòèðîâàíèå ìåòî-
äîì ñâåðõó–âíèç. Ïðîåêòèðîâàíèå öåëåñîîáðàçíî íà÷àòü ñ òîïîëîãèè êîëåñà èëè
äðóãîé ïîäõîäÿùåé òîïîëîãèè (íàïðèìåð, ïîëíîãî ãðàôà äåñÿòîãî ïîðÿäêà), à çàòåì
îïòèìèçèðîâàòü åå ê âèäó, êîòîðûé óäîâëåòâîðÿåò óñëîâèÿì îãðàíè÷åíèé. Åñëè òà-
êèì ñïîñîáîì îïòèìèçèðîâàòü òîïîëîãèþ êîëåñà (ñì. ðèñ. 7, à) ñ ó÷åòîì îãðàíè÷å-
íèé, òî ïðèõîäèì ê òîïîëîãèè, ïðèâåäåííîé íà ðèñ. 7, á.  ðåçóëüòàòå ïîëó÷àåì
ñâÿçíûé ãðàô, ñòåïåíü ñâÿçíîñòè êîòîðîãî ðàâíà ïÿòè, à òîïîëîãèÿ íà ýòîì ãðàôå ÿâ-
ëÿåòñÿ óñòîé÷èâîé ê óäàëåíèþ ëþáîé âåðøèíû, êðîìå îñíîâíîé âåðøèíû o8 .
4. ÏÅÐÅÐÀÑÏÐÅÄÅËÅÍÈß ÍÀÃÐÓÇÎÊ Â ÊÀÍÀËÀÕ
Ñëåäóþùåé âàæíîé çàäà÷åé ÿâëÿåòñÿ çàäà÷à ïåðåðàñïðåäåëåíèÿ íàãðóçîê â êà-
íàëàõ ÈÒ-èíôðàñòðóêòóð. Áóäåì ðåøàòü ýòó çàäà÷ó ñ ïîìîùüþ ãåíåòè÷åñêèõ
àëãîðèòìîâ (ÃÀ), êîòîðûå â îáùåì ñëó÷àå äàþò ïðèáëèæåííîå ðåøåíèå, è ñå-
òåâûìè ìåòîäàìè, êîòîðûå äàþò òî÷íîå ðåøåíèå çàäà÷è ïåðåðàñïðåäåëåíèÿ
íàãðóçêè. Ïåðâûå ìåòîäû èìåþò ïîëèíîìèàëüíûå îöåíêè ñëîæíîñòè, è ýòî
ïðîÿâëÿåòñÿ íà ãðàôàõ áîëüøèõ ðàçìåðîâ, à âòîðûå ìåòîäû ýôôåêòèâíî ðàáî-
òàþò íà ãðàôàõ íåáîëüøèõ ðàçìåðîâ.
4.1. Ãåíåòè÷åñêèå àëãîðèòìû êàê ìåòîä áàëàíñèðîâàíèÿ íàãðóçêè â êà-
íàëàõ. Âàæíîñòü çàäà÷è ðàñïðåäåëåíèÿ íàãðóçêè â ÈÒ-èíôðàñòðóêòóðàõ ñâÿçàíà
ñ îáåñïå÷åíèåì êà÷åñòâà îáñëóæèâàíèÿ ïîëüçîâàòåëåé. Âîçíèêíîâåíèå íîâûõ
ïîäõîäîâ ê ðàñïðåäåëåííûì âû÷èñëåíèÿì (îáëà÷íûå âû÷èñëåíèÿ) è ñîçäàíèå
íîâûõ ñåðâèñîâ â ÈÒ-èíôðàñòðóêòóðàõ íå òîëüêî íàêëàäûâàþò äîïîëíèòåëüíûå
òðåáîâàíèÿ ê íàäåæíîñòè è ñêîðîñòè ðàáîòû àëãîðèòìîâ òðàíñïîðòèðîâêè äàí-
íûõ, íî è òðåáóþò ñîçäàíèÿ ýôôåêòèâíûõ ìåòîäîâ áàëàíñèðîâàíèÿ íàãðóçîê íà
ðåñóðñû èíôðàñòðóêòóðû (êàíàëû ñâÿçè, âû÷èñëèòåëüíûå ýëåìåíòû è äð.). Êëàñ-
ñè÷åñêèå àëãîðèòìû ðåøåíèÿ çàäà÷ òðàíñïîðòà äàííûõ îïåðèðóþò òîëüêî îäíèì
ïàðàìåòðîì îïòèìèçàöèè — âåñîì (öåíîé) ïóòè, êîòîðûé âûðàæàåò ñîâîêóï-
íîñòü åãî àääèòèâíûõ õàðàêòåðèñòèê. Îäíàêî, êàê ïðàâèëî, ñóùåñòâóåò íåñêîëü-
êî ïàðàìåòðîâ, õàðàêòåðèçóþùèõ êàæäóþ âåòâü ñåòè (íàïðèìåð, ïðîïóñêíàÿ ñïî-
ñîáíîñòü, çàäåðæêà, ñêîðîñòü ïåðåäà÷è, íàäåæíîñòü), êîòîðûå ìîæíî ðàçäåëèòü
íà àääèòèâíûå è íåàääèòèâíûå. Â ñîâðåìåííûõ ÈÒ-èíôðàñòðóêòóðàõ âîçíèêàåò
íåîáõîäèìîñòü ðåøåíèÿ çàäà÷è î êðàò÷àéøèõ ïóòÿõ ñ íåñêîëüêèìè êðèòåðèÿìè
îïòèìèçàöèè. Êëàññè÷åñêèå àëãîðèòìû íåïðèìåíèìû ê çàäà÷àì òàêîãî òèïà, ïî-
ñêîëüêó îíè ïðèíàäëåæàò êëàññó NP-ñëîæíûõ ïðîáëåì. Âû÷èñëèòåëüíûå çàòðà-
òû íà ðåøåíèå òàêèõ çàäà÷ ýêñïîíåíöèàëüíî âîçðàñòàþò ñ óâåëè÷åíèåì ðàçìåð-
íîñòè îáðàáàòûâàåìûõ ãðàôîâ. Ïîýòîìó âîçíèêàåò íåîáõîäèìîñòü ôîðìèðîâà-
íèÿ íîâûõ ïîäõîäîâ è àëãîðèòìîâ ðåøåíèÿ çàäà÷ ïîèñêà îïòèìàëüíûõ ïóòåé ñî
ìíîãèìè êðèòåðèÿìè. Èññëåäîâàíèÿ ïîñëåäíèõ äåñÿòèëåòèé ñôîðìèðîâàëè íî-
âóþ îòðàñëü ýâîëþöèîííûõ âû÷èñëåíèé, èç êîòîðûõ âàæíîå ìåñòî çàíèìàþò
ãåíåòè÷åñêèå àëãîðèòìû [8, 9].
4.1.1. Ïðåèìóùåñòâà ãåíåòè÷åñêîãî àëãîðèòìà. Ðàññìîòðèì îñíîâíûå
ïðåèìóùåñòâà ÃÀ â ñðàâíåíèè ñ êëàññè÷åñêèìè ìåòîäàìè [8].
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 147
O1 o6
o2 o7
o3 o9
o5 o10
O8
O4
O1 o6
o2 o7
o3
o9
o5 o10
O8
O4
Ðèñ. 7. Êîëåñî è ðåçóëüòàò åãî îïòèìèçàöèè
à á
— ÃÀ ïðèñóù ïàðàëëåëèçì. Áîëüøèíñòâî äðóãèõ àëãîðèòìîâ ïîèñêà è îïòè-
ìèçàöèè ñòðîãî ïîñëåäîâàòåëüíû è ìîãóò èññëåäîâàòü ïðîñòðàíñòâî ðåøåíèé çà-
äà÷è òîëüêî â îäíîì íàïðàâëåíèè. Åñëè íàéäåííîå ðåøåíèå îêàæåòñÿ íåîïòè-
ìàëüíûì, åäèíñòâåííûì âàðèàíòîì ÿâëÿåòñÿ îòêàç îò âñåõ ïîëó÷åííûõ ðåçóëüòà-
òîâ è ïîâòîð ðàáîòû àëãîðèòìà ñ ñàìîãî íà÷àëà. Ïîñêîëüêó ÃÀ ñîõðàíÿþò
èíôîðìàöèþ î ñâîèõ ïîòîìêàõ, îíè ìîãóò èññëåäîâàòü ïðîñòðàíñòâî ðåøåíèé
â íåñêîëüêèõ íàïðàâëåíèÿõ îäíîâðåìåííî. Åñëè îäèí ïóòü îêàæåòñÿ òóïèêîâûì,
ÃÀ ìîãóò ëåãêî óäàëèòü ðåøåíèå è ïðîäîëæèòü ðàáîòó â áîëåå ïåðñïåêòèâíûõ
íàïðàâëåíèÿõ, ÷òî äàåò áîëüøå øàíñîâ íàéòè îïòèìàëüíîå ðåøåíèå äëÿ êàæäîãî
çàïóñêà àëãîðèòìà.
— Âûïîëíèìîñòü îãðàíè÷åíèé çàäà÷è îïòèìèçàöèè ïðîèñõîäèò çà ñ÷åò
âêëþ÷åíèÿ èõ â ìåòîä êîäèðîâàíèÿ õðîìîñîì.
— Ñóùåñòâóåò âîçìîæíîñòü ðåøåíèÿ çàäà÷ ìíîãîöåëåâîé (ìíîãîêðèòåðè-
àëüíîé) îïòèìèçàöèè. Ìíîãèå ðåàëüíûå çàäà÷è íå ìîãóò áûòü ñâåäåíû ê îïòèìè-
çàöèè îäíîé âåëè÷èíû, à òîëüêî ê êîìïëåêñó âçàèìíî çàâèñèìûõ ïàðàìåòðîâ.
Äîêàçàíà ýôôåêòèâíîñòü ïðèìåíåíèÿ ÃÀ ïðè ðåøåíèè òàêîãî êëàññà çàäà÷.
— ÃÀ äàþò âîçìîæíîñòü îïòèìèçàöèè òîïîëîãèè èëè ñòðóêòóðû ïàðàëëåëü-
íî ñ îïòèìèçàöèåé ïàðàìåòðîâ ðåøåíèÿ äëÿ êîíêðåòíîé çàäà÷è.
4.1.2. Ôîðìèðîâàíèå ÃÀ ðåøåíèÿ
çàäà÷è ïîèñêà êðàò÷àéøèõ ïóòåé. Ãå-
íåòè÷åñêèé àëãîðèòì ìàðøðóòèçàöèè
áàçèðóåòñÿ íà àëãîðèòìå ïîèñêà òàêîãî
ïóòè ïî ìíîãèì êðèòåðèÿì íà ãðàôå
G V E� ( , ) [10].
Ôîðìóëèðîâêà çàäà÷è ïîèñêà
êðàò÷àéøåãî ïóòè íà ãðàôå.  îáùåì
ñëó÷àå èìååì íåñêîëüêî âåñîâûõ ôóíê-
öèé w wk1, , :� E R� , êàæäàÿ èç êîòî-
ðûõ ñîîòâåòñòâóåò îïðåäåëåííîìó êðè-
òåðèþ îïòèìèçàöèè (k — êîëè÷åñòâî
òàêèõ êðèòåðèåâ). Ïðîèçâîëüíûé ïóòü p i j� �� � ñîñòîèò èç ïîñëåäîâàòåëüíîñ-
òè ðåáåð ( , ), , ( , )� � � �i l k j E� � è ìîæåò áûòü ïðåäñòàâëåí â âèäå ïîñëåäîâà-
òåëüíîñòè âåðøèí ãðàôà, êîòîðûå ïðèíàäëåæàò ïóòè p i l j� ( , , , )� � �� . Êàæäàÿ
èç âåðøèí � � �i l j V, , ,� � äîëæíà ïðèíàäëåæàòü ïóòè òîëüêî îäèí ðàç. Íàïðè-
ìåð, íà ðèñ. 8 ïîñëåäîâàòåëüíîñòü (1, 4), (4, 5), (5, 6), (6, 9) ÿâëÿåòñÿ ïóòåì èç âåð-
øèíû 1 ê âåðøèíå 9 è ñîîòâåòñòâóåò ïðåäñòàâëåíèþ (1, 4, 5, 6, 9).
Ïóñòü èíäåêñ s ñîîòâåòñòâóåò íà÷àëüíîé, à l — êîíå÷íîé âåðøèíàì èñêîìîãî
ïóòè: p s l� �� � . Îïðåäåëèì xij :
x
i j
ij �
1
0
, ( , ) ,åñëè ðåáðî ïðèíàäëåæèò ïóòè
â ïðîòèâíîì ñëó�àå.
�
�
�
Ïóñòü òàêæå k — îáùåå êîëè÷åñòâî êðèòåðèåâ îïòèìèçàöèè çàäà÷è. Ïî êàæ-
äîìó êðèòåðèþ ìîæíî âû÷èñëèòü îïðåäåëåííûé ôóíêöèîíàë — öåëåâóþ
ôóíêöèþ, êîòîðàÿ ñîîòâåòñòâóåò êà÷åñòâó ïóòè, èñõîäÿ èç àëãîðèòìà ìàðøðó-
òèçàöèè, è îïðåäåëÿåòñÿ êàê
C p F w i j x m k i j Em m m ij( ) ( ( , ), ), , , , ( , )� � �1 � ,
ãäå w i jm ( , ) — âåñîâàÿ ôóíêöèÿ ðåáðà ( , )i j .
Äëÿ àääèòèâíûõ õàðàêòåðèñòèê ïóòè (çàäåðæêà, äëèíà), èñïîëüçóåìûõ êàê ìåò-
ðèêó ñîâðåìåííûõ àëãîðèòìîâ ìàðøðóòèçàöèè, Fm ÿâëÿåòñÿ ñóììîé çíà÷åíèé âåñî-
âîé ôóíêöèè ðåáåð, ñîñòàâëÿþùèõ ïóòü. Äëÿ íåàääèòèâíîé õàðàêòåðèñòèêè ïóòè
(íàãðóçêè, ïðîïóñêíàÿ ñïîñîáíîñòü, íàäåæíîñòü) ôóíêöèîíàë ÿâëÿåòñÿ ñëîæíîé
ôóíêöèåé îò ìíîãèõ ïàðàìåòðîâ è ìîæåò ó÷èòûâàòü íå òîëüêî ñîñòîÿíèå ñîåäèíå-
íèé, íî è ñîñòîÿíèå ìàðøðóòèçàòîðîâ ñåòè, èçìåíåíèå ñðåäû ïåðåäà÷è äàííûõ è ò.ï.
148 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
7
5
8
3
96
1 4
2
Ðèñ. 8. Ïóòü (1, 4, 5, 6, 9)
Îáîçíà÷èì P ìíîæåñòâî âñåõ âîçìîæíûõ ïóòåé ìåæäó âåðøèíàìè � i è � j .
 îáùåì ñëó÷àå çàäà÷ó ïîèñêà êðàò÷àéøåãî ïóòè ïî ìíîãèì êðèòåðèÿì ìåæäó
äâóìÿ îïðåäåëåííûìè âåðøèíàìè íà ãðàôå ìîæíî ñôîðìóëèðîâàòü ñëåäóþùèì
îáðàçîì:
min ( ) ( ( , ) ), , , , ( , )
P
m m m ijN p F w i j x m k i j E� � �1 � ; (3)
j s j i
d
ij
j s j i
d
jix x
i s
i l
� � � �
� �� �
�
� �
, ,
, ,
, ,
1
1
0
åñëè
åñëè
èíà å;�
�
�
�
�
�
(4)
j s j i
d
ijx
i l
i l� �
� �
�
�
�
�
�,
, ,
, .
1
0
åñëè
åñëè
(5)
Óñëîâèÿ (4) è (5) òðåáóþò, ÷òîáû èñêîìûé ïóòü íå ñîäåðæàë öèêëîâ. Óñëî-
âèå (3) òðåáóåò, ÷òîáû öåëåâàÿ ôóíêöèÿ ïî êàæäîìó êðèòåðèþ îïòèìèçàöèè ïî
âñåì âîçìîæíûì ïóòÿì p Ps d� � �� � äîñòèãàëà íàèìåíüøåãî çíà÷åíèÿ íà èñ-
êîìîì ïóòè. Çàäà÷à (3) ÿâëÿåòñÿ NP-ñëîæíîé; èñõîäÿ èç ýòîãî ðàññìîòðèì
ôîðìèðîâàíèå ÃÀ äëÿ åå ðåøåíèÿ.
Îñîáåííîñòè ìåòîäà êîäèðîâàíèÿ ðåøåíèé àëãîðèòìà. Ðàññìîòðèì îïðåäå-
ëåííûé ïóòü p s i j d� ( , , , , )� � � �� , ãäå � � � �s i j d V, , , ,� � , êîòîðûé ÿâëÿåòñÿ
ïðîìåæóòî÷íûì ðåøåíèåì çàäà÷è. Õðîìîñîìà ãåíåòè÷åñêîãî àëãîðèòìà, êîòîðàÿ
ïðåäñòàâëÿåò ðåøåíèå p, ñîñòîèò èç ïîñëåäîâàòåëüíîñòè öåëûõ ïîëîæèòåëüíûõ
÷èñåë, ñîîòâåòñòâóþùèõ èäåíòèôèêàòîðàì âåðøèí
ãðàôà, ÷åðåç êîòîðûå ïðîõîäèò ïóòü p. Êàæäûé ëî-
êóñ (ïîëîæåíèå) õðîìîñîìû îïðåäåëÿåò ïîðÿäêîâûé
íîìåð âåðøèíû ïóòè (åå èäåíòèôèêàòîð ñîâïàäàåò
ñî çíà÷åíèåì ñîîòâåòñòâóþùåãî ãåíà). Ãåíû ïåðâîãî
è ïîñëåäíåãî ëîêóñîâ õðîìîñîìû çàðåçåðâèðîâàíû
çà íà÷àëüíîé è êîíå÷íîé âåðøèíàìè ïóòè ñîîòâåò-
ñòâåííî. Îáùèé âèä õðîìîñîìû èçîáðàæåí íà ðèñ. 9
(òî÷êà â ëîêóñå îçíà÷àåò ïîìå÷åííûé ãåí).
Âîçâðàòèìñÿ ê ðèñ. 8. Ïóñòü s �1, d � 9.
Íà ðèñ. 10 èçîáðàæåíà õðîìîñîìà, êîòîðàÿ ñîîòâåò-
ñòâóåò ïóòè (1, 4, 5, 6, 9). Äëèíà õðîìîñîìû ìîæåò
âàðüèðîâàòüñÿ îò äâóõ äî | |V . Òàêîå ïðåäñòàâëåíèå
ðåøåíèÿ çàäà÷è íåñêîëüêî çàòðóäíÿåò ôîðìèðîâàíèå
ãåíåòè÷åñêèõ îïåðàöèé êðîññîâåðà è ìóòàöèè, îäíàêî ïîçâîëÿåò îäíîçíà÷íî îïðå-
äåëèòü ïóòü ïî åãî ïðåäñòàâëåíèþ è íàîáîðîò — ïî åãî ïðåäñòàâëåíèþ îïðåäå-
ëèòü ïóòü.
Ìåòîäû ãåíåðàöèè íà÷àëüíîé ïîïóëÿöèè. Ïåðâûì ýòàïîì ðàáîòû ÃÀ ÿâëÿåòñÿ
âûáîð íà÷àëüíîé ïîïóëÿöèè è åå ðàçìåðà. Íà÷àëüíàÿ ïîïóëÿöèÿ, ñîñòîÿùàÿ èç áîëü-
øîãî êîëè÷åñòâà õðîìîñîì, ïîçâîëÿåò íàìíîãî áûñòðåå íàéòè ðåøåíèå äîñòàòî÷íîé
òî÷íîñòè. Îäíàêî òàêîé ïîäõîä òðåáóåò çíà÷èòåëüíûõ âû÷èñëèòåëüíûõ çàòðàò äëÿ
ðåàëèçàöèè àëãîðèòìà: ÷åì áîëüøå ðàçìåð ïîïóëÿöèè, òåì áîëüøå ïàìÿòè âû÷èñëè-
òåëüíîé ñèñòåìû áóäåò çàòðà÷åíî è âðåìÿ âûïîëíåíèÿ âñåõ ãåíåòè÷åñêèõ îïåðàöèé
(êðîññîâåð, ìóòàöèÿ, îòáîð) áóäåò âîçðàñòàòü. Ðàçìåð ïîïóëÿöèè áóäåò ýêñïîíåíöè-
àëüíî ðàñòè â çàâèñèìîñòè îò ñëîæíîñòè ïîñòàâëåííîé çàäà÷è äëÿ ïîëó÷åíèÿ äîñòà-
òî÷íî õîðîøåãî ðåçóëüòàòà. Îäíàêî ïîñëåäíèå èññëåäîâàíèÿ â îáëàñòè ÃÀ ïîêàçàëè,
÷òî õîðîøèé ðåçóëüòàò çà ïðèåìëåìîå âðåìÿ ìîæíî ïîëó÷èòü, èñïîëüçóÿ ïîïóëÿöèè
çíà÷èòåëüíî ìåíüøåãî ðàçìåðà. Ýêñïåðèìåíò ïîêàçûâàåò, ÷òî äëÿ çàäà÷è î êðàò÷àé-
øåì ïóòè â ãðàôå äîñòàòî÷íûé ðàçìåð ïîïóëÿöèè ñîñòàâëÿåò N V� 2| | . Âàæíûì
òàêæå ÿâëÿåòñÿ âûáîð ñïîñîáà ôîðìèðîâàíèÿ íà÷àëüíîé ïîïóëÿöèè. Ñóùåñòâóþò
äâà îñíîâíûõ ïîäõîäà ðåøåíèÿ ýòîé çàäà÷è:
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 149
s i j d…
Ãåíû
Ðèñ. 9. Îáùèé âèä õðîìîñîìû
1 4 5 9
Ãåíû
6
Ðèñ. 10. Âèä õðîìîñîìû, ñîîò-
âåòñòâóþùåé ïóòè (1, 4, 5, 6, 9)
1) ãåíåðàöèÿ ñëó÷àéíûõ õðîìîñîì;
2) ôîðìèðîâàíèå íà÷àëüíîé ïîïóëÿöèè ñ èñïîëüçîâàíèåì êëàññè÷åñêîãî ìå-
òîäà [7].
Ïåðâûé âàðèàíò ïîçâîëÿåò çíà÷èòåëüíî óïðîñòèòü ïðîöåññ ñîçäàíèÿ íà÷àëü-
íîé ïîïóëÿöèè àëãîðèòìà, óìåíüøàÿ, òàêèì îáðàçîì, âðåìÿ ðàáîòû àëãîðèòìà
â öåëîì. Òàêîé ïîäõîä òàêæå öåëåñîîáðàçåí â ñëó÷àå îòñóòñòâèÿ êëàññè÷åñêîãî
àëãîðèòìà ðåøåíèÿ èñõîäíîé çàäà÷è.
Âòîðîé ïîäõîä òðåáóåò çíà÷èòåëüíûõ âû÷èñëèòåëüíûõ çàòðàò, îäíàêî ïîçâî-
ëÿåò äîñòè÷ü æåëàåìîãî ðåçóëüòàòà ðàáîòû ÃÀ ïðè çíà÷èòåëüíî ìåíüøåì
êîëè÷åñòâî èòåðàöèé.
Äëÿ îïèñàííîé èñõîäíîé çàäà÷è ïî êîëè÷åñòâó ïàðàìåòðîâ îïòèìèçàöèè
k � 2 â îáùåì ñëó÷àå íå ñóùåñòâóåò íå òîëüêî êëàññè÷åñêîãî àëãîðèòìà ðåøåíèÿ,
íî è òî÷íîãî ðåøåíèÿ â öåëîì. Ïîýòîìó äëÿ çàäà÷è ïîèñêà êðàò÷àéøèõ ïóòåé ñî
ìíîãèìè ïàðàìåòðàìè îïòèìèçàöèè öåëåñîîáðàçíî ôîðìèðîâàòü íà÷àëüíóþ ïî-
ïóëÿöèè ñëó÷àéíûì îáðàçîì. Îäíàêî ïðèìåíåíèå êëàññè÷åñêîãî àëãîðèòìà ïî-
èñêà êðàò÷àéøèõ ïóòåé ïî îäíîìó èç êðèòåðèåâ ïîçâîëèò çíà÷èòåëüíî ñîêðàòèòü
âðåìÿ ðàáîòû àëãîðèòìà è óëó÷øèòü ïàðàìåòðû ñõîäèìîñòè.
Âîçâðàòèìñÿ ê ôîðìóëèðîâêå ïåðâîãî ïîäõîäà çàäà÷è. Äëÿ îáîçíà÷åíèÿ âåñà
êàæäîãî êðèòåðèÿ îïòèìèçàöèè ââåäåì êîýôôèöèåíòû �i i k, , ,�1 � . Äëÿ ôîðìèðî-
âàíèÿ íà÷àëüíîãî ïîêîëåíèÿ õðîìîñîì ïðèìåíÿåòñÿ àëãîðèòì Äåéêñòðû ïî îäíîìó
èç êðèòåðèåâ îïòèìèçàöèè çàäà÷è, âåñîâîé êîýôôèöèåíò êîòîðîãî íàèáîëüøèé.
Îñóùåñòâèì âûáîð ðîäèòåëüñêîé ïàðû õðîìîñîì. Ñóùåñòâóþò íåñêîëüêî
ïîäõîäîâ ê âûáîðó ðîäèòåëüñêîé ïàðû õðîìîñîì. Íàèáîëåå ïðîñòîé èç íèõ —
ïàíìèêñèÿ. Ýòîò ïîäõîä ïðåäñòàâëÿåò ñîáîé ñëó÷àéíûé âûáîð ðîäèòåëüñêîé
ïàðû.  ýòîì ñëó÷àå îñîáü ìîæåò ñòàòü ÷ëåíîì íåñêîëüêèõ ïàð. Íåñìîòðÿ íà ïðî-
ñòîòó, òàêîé ïîäõîä ñ÷èòàþò óíèâåðñàëüíûì äëÿ ðåøåíèÿ ðàçëè÷íûõ êëàññîâ çà-
äà÷. Îäíàêî îí äîñòàòî÷íî êðèòè÷åí ïî îòíîøåíèþ ê ÷èñëåííîñòè ïîïóëÿöèè,
ïîñêîëüêó ýôôåêòèâíîñòü àëãîðèòìà, ðåàëèçóþùåãî òàêîé ïîäõîä, ñíèæàåòñÿ
ñ ðîñòîì ÷èñëåííîñòè ïîïóëÿöèè. Ïðè ñåëåêòèâíîì ñïîñîáå îòáîðà îñîáåé â ðî-
äèòåëüñêóþ ïàðó ñëåäóåò ó÷èòûâàòü, ÷òî «ðîäèòåëÿìè» ìîãóò ñòàòü òîëüêî òå
îñîáè, çíà÷åíèå ïðèñïîñîáëåííîñòè êîòîðûõ íå ìåíüøå ñðåäíåãî çíà÷åíèÿ ïðè-
ñïîñîáëåííîñòè â ïîïóëÿöèè. Òàêîé ïîäõîä îáåñïå÷èâàåò áîëåå áûñòðóþ ñõîäè-
ìîñòü àëãîðèòìà. Îäíàêî ââèäó áûñòðîé ñõîäèìîñòè ñåëåêòèâíûé îòáîð ðîäèòå-
ëüñêîé ïàðû ñ÷èòàåòñÿ íåïðèåìëåìûì, åñëè çàäà÷à ñîñòîèò â îïðåäåëåíèè íå-
ñêîëüêèõ ýêñòðåìóìîâ, ïîñêîëüêó äëÿ òàêèõ çàäà÷ àëãîðèòì îáû÷íî áûñòðî
ñõîäèòñÿ ê îäíîìó èç ðåøåíèé. Êðîìå òîãî, äëÿ íåêîòîðîãî êëàññà çàäà÷ ñî
ñëîæíûì ëàíäøàôòîì ïðèñïîñîáëåííîñòè áûñòðàÿ ñõîäèìîñòü ìîæåò ïðèâåñòè
ê ïðåæäåâðåìåííîé ñõîäèìîñòè ê êâàçèîïòèìàëüíîìó ðåøåíèþ. Ýòîò íåäîñòà-
òîê â ïðåäëîæåííîé ìîäåëè ñêîìïåíñèðîâàí áëàãîäàðÿ èñïîëüçîâàíèþ ñîîòâåò-
ñòâóþùåãî ìåõàíèçìà îòáîðà — òóðíèðíîãî.
Ìåòîäèêà ïðèìåíåíèÿ ãåíåòè÷åñêèõ îïåðàöèé è èõ îñîáåííîñòè.
Îïåðàöèÿ êðîññîâåð. Ãåíåòè÷åñêàÿ îïåðàöèÿ êðîññîâåðà ôîðìèðóåò íîâîå
ïîêîëåíèå ðåøåíèé çàäà÷è ñ èñïîëüçîâàíèåì ãåíîâ ïðåäûäóùåãî ïîêîëåíèÿ.  çà-
äà÷å î êðàò÷àéøåì ïóòè êðîññîâåð ïðåäñòàâëÿåò ñîáîé îáìåí îòäåëüíûìè ïóòÿìè
èçáðàííûõ õðîìîñîì äëÿ ôîðìèðîâàíèÿ íîâîãî ïóòè. Ïðèìåíåíèå êëàññè÷åñêîé
îïåðàöèè êðîññîâåðà íåâîçìîæíî, ïîñêîëüêó äëèíà õðîìîñîìû èçìåíÿåòñÿ, à êàæ-
äûé ãåí íå ñîîòâåòñòâóåò îïðåäåëåííîé õàðàêòåðèñòèêå ðåøåíèÿ çàäà÷è.
Àëãîðèòì êðîññîâåðà äëÿ îïèñàííîãî âûøå ïðåäñòàâëåíèÿ òðåáóåò íàëè÷èÿ
õîòÿ áû îäíîãî îáùåãî ãåíà (âåðøèíû) â õðîìîñîìàõ, êîòîðûå ñêðåùèâàþòñÿ.
Îáùèå ãåíû ÿâëÿþòñÿ òî÷êàìè êðîññîâåðà, à îòäåëüíûå ïóòè, ñîåäèíÿþùèå èõ
ìåæäó ñîáîé, ïîäëåæàò îáìåíó ìåæäó õðîìîñîìàìè-ðîäèòåëÿìè. Ïðèìåíåíèå
îïåðàöèè êðîññîâåðà íå òðåáóåò, ÷òîáû îáùèå ãåíû õðîìîñîì íàõîäèëèñü â îäè-
íàêîâûõ ëîêóñàõ õðîìîñîìû.  òàêîì ñëó÷àå îïåðàöèÿ êðîññîâåðà íå çàâèñèò îò
ïîëîæåíèÿ îáùèõ âåðøèí â ïóòè.
150 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
Âîçâðàòèìñÿ ê ãðàôó, èçî-
áðàæåííîìó íà ðèñ. 8.  êà÷åñ-
òâå íà÷àëüíîé è êîíå÷íîé âåð-
øèí âûáåðåì âåðøèíû ïîä íî-
ìåðàìè 1 è 9 ñîîòâåòñòâåííî.
Ïðè ýòîì ñëó÷àéíûì îáðàçîì
ñôîðìèðóåì ïåðâîíà÷àëüíîå ïî-
êîëåíèå ðåøåíèé çàäà÷è. Äëÿ
îïåðàöèè ñêðåùèâàíèÿ (êðîññî-
âåðà) âûáåðåì äâà ïðîèçâîëü-
íûõ ïóòè èç ìíîæåñòâà ðåøå-
íèé. Ðàññìîòðèì õðîìîñîìû,
êîòîðûå ïîäëåæàò îïåðàöèè
êðîññîâåðà. Õðîìîñîìà À ñîîò-
âåòñòâóåò ïóòè (1, 2, 5, 6, 9)
(ðèñ. 11, æèðíàÿ ëèíèÿ). Õðîìî-
ñîìà Á ñîîòâåòñòâóåò ïóòè (1, 4,
5, 7, 8, 9) (ðèñ. 11, øòðèõîâàÿ ëè-
íèÿ). Êàê âèäíî èç ðèñóíêà, õðî-
ìîñîìû À è Á èìåþò îáùèé ãåí, îòâå÷àþùèé âåðøèíå ïîä íîìåðîì 5. Ãåí,
îòâå÷àþùèé îáùåé âåðøèíå, ÿâëÿåòñÿ òî÷êîé êðîññîâåðà.
Ïðîöåäóðà îáìåíà ÷àñòè÷íûìè ïóòÿìè è ôîðìèðîâàíèÿ ñëåäóþùåãî ïîêî-
ëåíèÿ ðåøåíèé èçîáðàæåíà íà ðèñ. 12.  çàâèñèìîñòè îò êîëè÷åñòâà ñîâìåñòíûõ
âåðøèí â ðîäèòåëüñêèõ õðîìîñîìàõ ìîæíî âûäåëèòü îäíîòî÷å÷íûé è ìíîãîòî÷å÷-
íûé îïåðàòîðû êðîññîâåðà. Ïðèìåð ìíîãîòî÷å÷íîãî êðîññîâåðà èçîáðàæåí íà
ðèñ. 13. Ïóòè (1, 2, 4, 5, 7, 8, 9) è (1, 3, 4, 6, 5, 9) èìåþò äâå îáùèå âåðøèíû: 4 è 5
(êðîìå íà÷àëüíîé è êîíå÷íîé âåðøèí ïóòè). Ýòè âåðøèíû ÿâëÿþòñÿ òî÷êàìè
êðîññîâåðà ñîîòâåòñòâóþùèõ õðîìîñîì.
 ðåçóëüòàòå îïåðàöèè êðîññîâåðà âîçìîæíî ôîðìèðîâàíèå ïóòåé, ñîäåðæà-
ùèõ öèêëû. Ïîñêîëüêó òàêèå ïóòè íå óäîâëåòâîðÿþò óñëîâèþ (4) çàäà÷è, òî èõ
íåîáõîäèìî èñêëþ÷èòü èç ìíîæåñòâà ðåøåíèé. Ïîýòîìó ïîñëå îïåðàöèè êðîññî-
âåðà âñå õðîìîñîìû-ïîòîìêè ïîäëåæàò ïðîâåðêå íà íàëè÷èå öèêëîâ â ñîîòâåò-
ñòâóþùèõ èì ïóòÿõ íà ãðàôå. Õðîìîñîìû, íå ïðîøåäøèå ïðîâåðêó, èñêëþ÷àþòñÿ
è íå ó÷àñòâóþò â îïåðàöèè îòáîðà.
Îïåðàöèÿ ìóòàöèè. Îñíîâíàÿ çàäà÷à îïåðàöèè ìóòàöèè â ãåíåòè÷åñêîì àë-
ãîðèòìå — ñëó÷àéíîå èçìåíåíèå ðåøåíèé çàäà÷è â öåëÿõ ðàñøèðåíèÿ ìíîæåñòâà
ïîèñêà öåëåâîé ôóíêöèè.  êëàññè÷åñêîì èñïîëíåíèè îïåðàöèÿ ìóòàöèè ïðåä-
ñòàâëÿåò ñëó÷àéíîå èçìåíåíèå îäíîãî èëè íåñêîëüêèõ ãåíîâ. Ââèäó îñîáåííîñòè
êîäèðîâàíèÿ â çàäà÷å î êðàò÷àéøåì ïóòè êëàññè÷åñêèé ìåõàíèçì îïåðàöèè ìóòà-
öèè íåïðèìåíèì.
Îïèøåì àëãîðèòì îäíîòî÷å÷íîé ìóòàöèè íà ïðèìåðå ãðàôà, ðàññìîòðåííîãî
âûøå. Âûáåðåì ïðîèçâîëüíûé ïóòü p � ( , , , , , )1 2 4 6 8 9 íà ãðàôå, êîòîðûé ÿâëÿåòñÿ
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 151
7
5
8
3
96
1 4
2
1 2 5 96 À
Á1 4 5 87 9
Ðèñ. 11. Õðîìîñîìû À, Á è ñîîòâåòñòâóþùèå ïóòè íà ãðàôå
1 2 5 96 À
Á1 4 5 87 9
Òî÷êà êðîññîâåðà
Ðîäèòåëüñêèå õðîìîñîìû
1 2 5 96
1 4 5 87 9
Õðîìîñîìû-ïîòîìêè
Ðèñ. 12. Îäíîòî÷å÷íûé êðîññîâåð õðîìîñîì À è Á
1 3 4 56 9
Ðîäèòåëüñêèå õðîìîñîìû Õðîìîñîìû-ïîòîìêè
1 2 4 75 8 9
1 3 4 75 8 9
1 2 4 56 7 8 9
Ðèñ. 13. Äâóõòî÷å÷íûé êðîññîâåð õðîìîñîì À è Á
ðåøåíèåì çàäà÷è íà îïðåäåëåííîì
ýòàïå ðàáîòû ãåíåòè÷åñêîãî àëãî-
ðèòìà (ðèñ. 14). Ýòîò ïóòü ñîîòâåò-
ñòâóåò õðîìîñîìå Â îïðåäåëåííîãî
ïîêîëåíèÿ ãåíåòè÷åñêîãî àëãîðèòìà.
Äëÿ ôîðìèðîâàíèÿ îïåðàöèè
ìóòàöèè ïðîèçâîëüíûì îáðàçîì
âûáèðàþòñÿ äâå âåðøèíû: � i è � j
ïóòè p. Ïóñòü P i j( , ) — ìíîæåñòâî
âñåõ âîçìîæíûõ ïóòåé ìåæäó âåð-
øèíàìè � i è � j . Âûáåðåì ïðîèç-
âîëüíûé ïóòü p Pi j i j. ( , )� , êîòîðûì
çàìåíèì ïðîìåæóòî÷íûé ïóòü
ìåæäó âåðøèíàìè � i è � j íà ïóòè p. Ñôîðìèðîâàííîå òàêèì îáðàçîì àëüòåðíà-
òèâíîå ðåøåíèå óäîâëåòâîðÿåò óñëîâèÿì çàäà÷è è ìîæåò áûòü âêëþ÷åíî â ñëåäó-
þùåå ïîêîëåíèå ãåíåòè÷åñêîãî àëãîðèòìà. Ñ òî÷êè çðåíèÿ ïðåäñòàâëåíèÿ îïåðà-
öèÿ ìóòàöèè ñîîòâåòñòâóåò çàìåíå ïîñëåäîâàòåëüíîñòè ãåíîâ â õðîìîñîìå ìåæäó
ïîëîæåíèÿìè � i è � j àëüòåðíàòèâíîé ïîñëåäîâàòåëüíîñòüþ, ñîîòâåòñòâóþùåé
ïóòè p P i ji j, ( , )� . Âûáåðåì â õðîìîñîìå  ïðîèçâîëüíûì îáðàçîì òî÷êè ìóòà-
öèè — âåðøèíû 4 è 8. Îäíèì èç àëüòåðíàòèâíûõ ïóòåé ìåæäó ýòèìè âåðøèíàìè
áóäåò ïóòü (4, 5, 7, 8, 9). Ïðèìåíèâ åãî äëÿ îïåðàöèè ìóòàöèè, ïîëó÷èì ïóòü
(1, 2, 4, 5, 7, 8, 9). Îáùèé âèä îïåðàöèè ìóòàöèè äëÿ õðîìîñîìû Â èçîáðàæåí
íà ðèñ. 15.
Êàê è â ñëó÷àå îïåðàöèè
êðîññîâåðà, ðåçóëüòàò îïåðàöèè
ìóòàöèè ìîæåò íå óäîâëåòâîðÿòü
óñëîâèþ (5) çàäà÷è. Ïî àíàëîãèè
ñ ïðåäûäóùèì ñëó÷àåì ââîäèòñÿ
îïåðàöèÿ ïðîâåðêè ðåçóëüòàòà,
à ðåøåíèÿ, ñîäåðæàùèå öèêëû, èñ-
êëþ÷àþòñÿ.
Îïåðàöèÿ îòáîðà. Îïåðàöèÿ îòáîðà (âîñïðîèçâåäåíèÿ) íàïðàâëåíà íà óëó÷-
øåíèå êà÷åñòâà ïîïóëÿöèè ãåíåòè÷åñêîãî àëãîðèòìà. Òàêàÿ âîçìîæíîñòü äîñòèãà-
åòñÿ çà ñ÷åò òîãî, ÷òî íàèáîëåå ïðèñïîñîáëåííûå îñîáè èìåþò áîëüøå øàíñîâ ïå-
ðåõîäà ê ñëåäóþùåìó ïîêîëåíèþ. Ïðåäëîæåííûé ãåíåòè÷åñêèé àëãîðèòì èñïîëü-
çóåò ìåòîä òóðíèðíîãî îòáîðà.
Ïóñòü N — êîëè÷åñòâî îñîáåé ïîïóëÿöèè. Õàðàêòåðèñòèêà êàæäîé i-é îñîáè
ïîïóëÿöèè (ôåíîòèï) âûðàæàåòñÿ çíà÷åíèåì ôóíêöèè ïðèñïîñîáëåííîñòè F i( )
ê óñëîâèÿì äàííîé ñèòóàöèè. Äëÿ îòáîðà îïðåäåëåííîãî èíäèâèäà ñîçäàåòñÿ
ãðóïïà èç M � 2 ñëó÷àéíî âûáðàííûõ îñîáåé. Èíäèâèä ñ íàèáîëüøåé ïðèñïîñîá-
ëåííîñòüþ â ãðóïïå îòáèðàåòñÿ, îñòàëüíûå — îòâåðãàþòñÿ. Ïðåèìóùåñòâà òàêî-
ãî ïîäõîäà çàêëþ÷àåòñÿ â îòñóòñòâèè:
— ñõîäèìîñòè ê ëîêàëüíîìó ýêñòðåìóìó;
— ñòàãíàöèè;
— ãëîáàëüíîãî óïîðÿäî÷åíèÿ âñåõ îñîáåé ïîêîëåíèÿ;
— ÿâíîãî ðàñ÷åòà ôóíêöèè ïðèñïîñîáëåííîñòè.
Îòêëîíåííèå ðåøåíèÿ ÃÀ. Îïðåäåëèì îòêëîíåíèå îïðåäåëåííîãî ðåøåíèÿ
çàäà÷è îò òî÷íîãî ðåøåíèÿ êàê âçâåøåííóþ Lh -íîðìó:
r C h C C C Cj
h
j
k
j j
h
h
( ; , ) | | | | | |*
/
� �� � � �
�
�
�
�
�
!
!
�
�
�
1
1
, (6)
152 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
7
5
8
3
96
4
2
1
Ðèñ. 14. Ïóòü íà ãðàôå, ñîîòâåòñòâóþùèé õðîìîñîìå Â
1 3 4 86 9 Õðîìîñîìà Â äî ìóòàöèè
1 2 4 75 8 9
Õðîìîñîìà Â
ïîñëå ìóòàöèè
Ðèñ. 15. Îïåðàöèè ìóòàöèè õðîìîñîìû Â
ãäå � � �� ( , ),1 � k , C C Ck� ( , , )1 � , C C Ck
� � �� ( , , )1 � — òî÷íîå ðåøåíèå çà-
äà÷è. Ïàðàìåòð h îïðåäåëÿåò õàðàêòåð âëèÿíèÿ îòêëîíåíèé ïî êàæäîìó îò-
äåëüíîìó êðèòåðèþ. Ïðè h �1 íà îáùåå îòêëîíåíèå â îñíîâíîì âëèÿåò ñóììà
îòêëîíåíèé ðåøåíèÿ ïî âñåì êðèòåðèÿì, ïðè ñòðåìëåíèè çíà÷åíèÿ ïàðàìåòðà h
ê áåñêîíå÷íîñòè (h � ") ïîâûøàåòñÿ ñòåïåíü îòêëîíåíèÿ ïî êàæäîìó êðèòå-
ðèþ îòäåëüíî. Òàêîé ïîäõîä ïîçâîëÿåò ãèáêî ìåíÿòü íå òîëüêî âëèÿíèå êàæ-
äîãî îòäåëüíîãî êðèòåðèÿ, íî è èõ êîððåëÿöèþ.
Äëÿ íåáîëüøîãî êîëè÷åñòâà ïàðàìåòðîâ îïòèìèçàöèè çàäà÷è òî÷íîå ðåøå-
íèå íàéòè ìîæíî, à â ñëó÷àå k � 2 öåëåñîîáðàçíî èñïîëüçîâàòü ëó÷øåå ïðîìåæó-
òî÷íîå ðåøåíèå
�
C C Ñk( , , )1 � , ò.å. òî÷íîå ðåøåíèå, ñîîòâåòñòâóåùåå òåêóùåé
ïîïóëÿöèè ãåíåòè÷åñêîãî àëãîðèòìà, à íå çàäà÷è â öåëîì. Òàêèì îáðàçîì, ïîèñê
ýêñòðåìóìà îïòèìèçàöèè ïðîèñõîäèò íà îòäåëüíîì ìíîæåñòâå ðåøåíèé. Â ïðî-
öåññå ðàçâèòèÿ ïîïóëÿöèè ãåíåòè÷åñêîãî àëãîðèòìà îòäåëüíîå ëó÷øåå ðåøåíèå
áóäåò ïðèáëèæàòüñÿ ê òî÷íîìó, åñëè òàêîâîå âîîáùå ñóùåñòâóåò.
Ïóñòü P — ìíîæåñòâî îñîáåé òåêóùåé ïîïóëÿöèè. Çíà÷åíèå ëó÷øåãî ïðî-
ìåæóòî÷íîãî ðåøåíèÿ îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
� � �C C p p P i ki imin ( ) | , , ,{ } 1 � . (7)
Ïîäñòàâèâ âûðàæåíèå (7) â ôîðìóëó (6), ïîëó÷èì çíà÷åíèå îòêëîíåíèÿ îñîáè p:
r p C p Cj
h
j
k
j j
h
h
( ) | ( ) |
/
� �
�
�
�
�
�
!
!�
� �
1
1
.
Ïîñêîëüêó äëÿ ëó÷øèõ îñîáåé çíà÷åíèå îòêëîíåíèÿ áóäåò ìèíèìàëüíûì, òî
ñëåäóåò çàìåíèòü çíà÷åíèå îòêëîíåíèÿ íà çíà÷åíèå ôóíêöèè ïðèñïîñîáëåííîñòè.
Îáîçíà÷èì rmin íàèìåíüøåå è rmax íàèáîëüøåå îòêëîíåíèå â òåêóùåé ïîïóëÿ-
öèè. Îïðåäåëèì çíà÷åíèå ôóíêöèè ïðèñïîñîáëåííîñòè îñîáè p:
F p
r r p
r r
( )
( )max
max min
�
�
�
.
Ïîñêîëüêó äëÿ îïåðàöèè îòáîðà èñïîëüçóåòñÿ òóðíèðíûé ìåòîä, òî íåò íå-
îáõîäèìîñòè ðàññ÷èòûâàòü ôóíêöèè ïðèñïîñîáëåííîñòè â öåëîì, ÷òî çíà÷èòåëü-
íî óïðîùàåò íåïîñðåäñòâåííî ïðîöåäóðó îòáîðà. Äëÿ ñðàâíåíèÿ îñîáåé â ãðóïïå
äîñòàòî÷íî ñðàâíèòü çíà÷åíèå îòêëîíåíèÿ êàæäîé èç íèõ è îñòàâèòü â ãðóïïå
îäíó õðîìîñîìó ñ ìèíèìàëüíûì îòêëîíåíèåì.
Îòìåòèì, ÷òî ñôîðìèðîâàííûå îïåðàöèè ìóòàöèè è êðîññîâåðà ãåíåòè÷åñ-
êîãî àëãîðèòìà öåëåñîîáðàçíî èñïîëüçîâàòü â çàäà÷å ïîèñêà àëüòåðíàòèâíûõ ïó-
òåé ìåæäó îïðåäåëåííûìè ïàðàìè âåðøèí íà ãðàôå.
4.2. Ìîäåëèðîâàíèå êàíàëîâ ñâÿçè ñåòüþ Ïåòðè. Ïðåäïîëîæèì, ÷òî êàíà-
ëû ñâÿçè ðàñïðåäåëåíû ïî áëîêàì. Âíà÷àëå ðàññìîòðèì áëîê ñ îäíîñòîðîííèì
äåéñòâèåì ìåæäó êàíàëàìè ñâÿçè è ïðåäñòàâèì åãî â âèäå ãðàôà (ðèñ. 16, à). Âåð-
øèíàì äàííîãî ãðàôà ïîñòàâèì â ñîîòâåòñòâèå ìåñòà ñåòè Ïåòðè (ÑÏ), à êàæäî-
ìó ðåáðó ãðàôà ïîñòàâèì â ñîîòâåòñòâèå ïåðåõîäû ti ñåòè (ðèñ. 16, á).
Ïóñòü ÈÒ-èíôðàñòðóêòóðà ñîñòîèò èç áëîêîâ, êàæäûé èç êîòîðûõ âêëþ÷àåò
n êàíàëîâ, à êàæäûé êàíàë áëîêà èìååò ïðîïóñêíóþ ñïîñîáíîñòü k. Ýòî îçíà÷àåò,
÷òî êàæäûé êàíàë áëîêà ìîæåò îáñëóæèâàòü íå áîëåå k çàäàíèé. Åñëè áëîê èìååò
n êàíàëîâ, òî åãî ïðîïóñêíàÿ ñïîñîáíîñòü îãðàíè÷åíà âåëè÷èíîé n k# .
Ðàññìîòðèì ñëó÷àé, êîãäà m n k� # . Ïóñòü m — ÷èñëî ïîñòóïèâøèõ îò ïî-
ëüçîâàòåëåé çàïðîñîâ, êîòîðîå íå ïðåâîñõîäèò ïðîïóñêíóþ ñïîñîáíîñòü áëîêà,
ò.å. m n k� # .  ýòîì ñëó÷àå ïåðåðàñïðåäåëåíèå íàãðóçêè ìîæíî âûïîëíèòü âíóò-
ðè áëîêà. Íàïðèìåð, åñëè áëîê èìååò n � 6 êàíàëîâ ñ ïðîïóñêíîé ñïîñîáíîñòüþ
êàæäîãî êàíàëà k � 3, òî ïðîïóñêíàÿ ñïîñîáíîñòü òàêîãî áëîêà ðàâíà
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 153
n k# � # �3 6 18. Åñëè êàíàëû áëîêà íàãðóæåíû òàê, ÷òî èìåþò 5, 2, 5, 1, 0, 1 çàäà-
íèé (çàïðîñîâ) ê ïåðâîìó, âòîðîìó, ... , øåñòîìó óçëàì ñîîòâåòñòâåííî, òî ïåðå-
ðàñïðåäåëèòü íàãðóçêè âíóòðè áëîêà ìîæíî ñëåäóþùèì îáðàçîì: 3, 3, 3, 3, 1, 1,
ïîñêîëüêó 5 2 5 1 1 14 18� � � � � $ .
Íåîáõîäèìî îïðåäåëèòü, ÷åðåç êàêèå êàíàëû â áëîêå êðàò÷àéøèì ïóòåì
ìîæíî ïåðåðàñïðåäåëèòü íàãðóçêó. Äëÿ ýòîãî âîñïîëüçóåìñÿ ÑÏ, êîòîðàÿ ïîêàçà-
íà íà ðèñ. 16, á. Îíà ïðåäñòàâëÿåò ñîáîé îðäèíàðíóþ è îãðàíè÷åííóþ ìàøèíó
ñîñòîÿíèé, ïðè ýòîì âñå ðàçìåòêè â íåé äîñòèæèìû èç íà÷àëüíîé [5].
Äëÿ îïðåäåëåíèÿ ïóòåé ïåðåðàñïðåäåëåíèÿ íàãðóçêè âîñïîëüçóåìñÿ óðàâíå-
íèåì ñîñòîÿíèÿ, êîòîðîå äëÿ ïåðâîé ÑÏ èìååò âèä A x# (÷àñòíûé âèä ñåòè Ïåòðè
íå îãðàíè÷èâàåò îáùíîñòè ðàññìîòðåíèÿ):
A x
t t t t t t
# �
�
�
�
�
1 2 3 4 5 6
1 1 0 0 0 0 1
2 1 1 0 0 0 0
3 0 1 1 0 0 0
4 0 0 1 1 0 0
5 0 0 0 1 1 0
6 0 0 0 0 0 1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
!
!
!
!
!
!
!
!
!
# �x d . (8)
Çäåñü d M M� � 0 , M 0 — íà÷àëüíàÿ ðàçìåòêà ÑÏ, à M — êîíå÷íàÿ ðàçìåòêà.
Ïîäñòàâëÿÿ â (8) çíà÷åíèå äëÿ M 0 , M è ðåøàÿ ýòî óðàâíåíèå, ïîëó÷àåì ïîñëå-
äîâàòåëüíîñòè ñðàáàòûâàíèÿ ïåðåõîäîâ, êîòîðûå è ñîñòàâëÿþò ïóòè ïåðåðàñïðåäå-
ëåíèÿ íàãðóçêè. Íàïðèìåð, n � 6, k � 3 , M 0 5 5 2 0 1 1� ( , , , , , ), M � ( , , , , , )3 3 3 3 1 1 , òî
A x# �
�
�
�
�
�
�
�
�
�
�
1 0 0 0 0 1
1 1 0 0 0 0
0 1 1 0 0 0
0 0 1 1 0 0
0 0 0 1 1 0
0 0 0 0 0 1
�
�
�
�
�
�
!
!
!
!
!
!
!
# �
�
�
�
�
�
�
�
�
�
�
�
�
!
!
!
!
!
!
!
x
2
2
1
3
0
0
.
Åäèíñòâåííûì ðåøåíèåì ýòîãî óðàâíåíèÿ ÿâëÿåòñÿ x � ( , , , , , )2 4 3 0 0 0 . Ýòî ðå-
øåíèå ïîêàçûâàåò, ÷òî êðàò÷àéøèé ïóòü ïåðåðàñïðåäåëåíèÿ íàãðóçêè ñîñòîèò â
ñðàáàòûâàíèè äâàæäû ïåðåõîäà t1, ÷åòûðå ðàçà ïåðåõîäà t2 è òðè ðàçà ïåðåõî-
äà t3 . Äåéñòâèòåëüíî,
M t t0 1 25 5 2 0 1 1 2 3 7 2 0 1 1 4 3 3 6 0 1� � � � �( , , , , , ) ( , , , , , ) ( , , , , , 1) �
� �3 3 3 3 3 1 13t ( , , , , , ).
154 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
1 2
5 4
36
t1
t4
t2
t5
1 2
5 4
36
t6
t1
t7
t3
t9
1 2
5 4
36
t11
t3 t5
t2
t10
t8
t6
t4
t12
Ðèñ. 16. Ãðàô áëîêà è åãî ñåòü Ïåòðè: îðãðàô îäíîãî áëîêà êàíàëîâ ñâÿçè (à); ñåòü îäíîñòîðîí-
íÿÿ (á); ñåòü äâóñòîðîííÿÿ (â)
à á â
Ýòî îçíà÷àåò, ÷òî ïðè ïîñëåäîâàòåëüíîì ñîåäèíåíèè êàíàëîâ ïåðåíàïðàâëÿþòñÿ
èç ïåðâîãî êàíàëà äâà çàäàíèÿ âî âòîðîé êàíàë, à èç âòîðîãî êàíàëà ÷åòûðå çàäà-
íèÿ — â òðåòèé êàíàë, èç òðåòüåãî êàíàëà òðè çàäàíèÿ — â ÷åòâåðòûé êàíàë.
 äàëüíåéøåì áóäåì ïðåäïîëàãàòü, ÷òî ðàñïðåäåëåíèå íàãðóçêè ïî êàíàëàì
(â ñëó÷àå, åñëè íåêîòîðûå èç íèõ èìåþò íàãðóçêó áîëüøóþ, ÷åì èõ ïðîïóñêíàÿ ñïî-
ñîáíîñòü) âûïîëíÿåòñÿ òàêèì îáðàçîì, ÷òî ïåðâûå êàíàëû ïîëó÷àþò ìàêñèìàëüíóþ
íàãðóçêó.  äàííîì ïðèìåðå êàíàëû 1, 2, 3, 4 ïîëó÷èëè ìàêñèìàëüíóþ íàãðóçêó.
Òàêèì îáðàçîì, ïðèõîäèì ê àëãîðèòìó ïåðåðàñïðåäåëåíèÿ íàãðóçêè äëÿ áëî-
êà ñ n êàíàëàìè è ñ ïðîïóñêíîé ñïîñîáíîñòü k ïðè íà÷àëüíîé ðàçìåòêå M 0 .
Àëãîðèòì ÐÀÂÍÎÌ-ÍÀÃÐ( , , )k n M 0
Âõîä: Áëîê èç n êàíàëîâ, ïðîïóñêíàÿ ñïîñîáíîñòü óçëà k è íà÷àëüíàÿ ðàçìåò-
êà M 0 .
Âûõîä: Ìíîæåñòâî ìèíèìàëüíûõ ðåøåíèé óðàâíåíèÿ ñîñòîÿíèÿ.
Ìåòîä:
1. Âû÷èñëèòü M èñõîäÿ èç M 0 .
2. Ïîñòðîèòü óðàâíåíèå ñîñòîÿíèÿ A x M M# � � 0 .
3. Ðåøèòü óðàâíåíèå ñîñòîÿíèÿ TSS -ìåòîäîì [6].
4. Âûáðàòü ñðåäè ðåøåíèé îïòèìàëüíîå.
5. Ïåðåðàñïðåäåëèòü íàãðóçêó â ñîîòâåòñòâèè ñ îïòèìàëüíûì ðåøåíèåì.
6. Ñòîï.
Åñëè êàíàëû â áëîêàõ ìîãóò ðàáîòàòü â îáîèõ íàïðàâëåíèÿõ (äâóñòîðîííèå)
ìåæäó ñîñåäíèìè áëîêàìè, òî ñèòóàöèÿ àíàëèçèðóåòñÿ òåì æå ñïîñîáîì, ÷òî è
ðàññìîòðåííàÿ âûøå.
Ïðåäñòàâèì ìîäåëü áëîêà ñ äâóñòîðîííèì äåéñòâèåì ìåæäó êàíàëàìè â áëî-
êå (ðèñ. 16, â). Òîãäà ñåòü Ïåòðè îñòàåòñÿ ìàøèíîé ñîñòîÿíèé, íî ïðè ýòîì ÷èñëî
íåèçâåñòíûõ â óðàâíåíèè ñîñòîÿíèÿ óâåëè÷èâàåòñÿ â äâà ðàçà. Îäíàêî àëãîðèòì
ïåðåðàñïðåäåëåíèÿ íàãðóçêè íå èçìåíÿåòñÿ. Íàïðèìåð, åñëè n � 6, k � 3,
M 0 5 2 5 1 5 0� ( , , , , , ), òî îòñþäà 5 2 5 1 5 18� � � � � ; òîãäà M � ( , , , , , )3 3 3 3 3 3 , òàê êàê
18 3 6: � äëÿ ÑÏ ñîãëàñíî ðèñ. 16, â. Óðàâíåíèå ñîñòîÿíèÿ äëÿ ýòîé ÑÏ èìååò âèä
A x# �
� �
� �
� �
1 1 0 0 0 0 0 0 0 0 1 1
1 1 1 1 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 � �
� �
� �
�
�
�
�
�
�
�
�
�
�
!
1 1 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 1 1 1 1
!
!
!
!
!
!
# �
�
�
�
�
�
�
�
�
�
�
�
�
�
!
!
!
!
!
!
!
x
2
1
2
2
2
3
.
Ìíîæåñòâî ìèíèìàëüíûõ ðåøåíèé ïðåäñòàâëÿåò
x x1 20 1 2 0 0 0 0 2 0 0 0 3 1 0 0 0 0 2 0 0 2� �( , , , , , , , , , , , ), ( , , , , , , , , , , , )0 0 1 ,
x x3 40 0 1 0 0 1 0 1 1 0 0 2 2 0 0 1 0 3 1 0 3� �( , , , , , , , , , , , ), ( , , , , , , , , , , , )0 0 0 .
Èç íèõ îïòèìàëüíûìè ÿâëÿþòñÿ ðåøåíèÿ x2 è x3 (ñóììà èõ êîîðäèíàò ðàâíà
øåñòè, ïðè ýòîì ñóììû äëÿ x1 è x4 ðàâíû 8 è 10 ñîîòâåòñòâåííî). Ëþáîå èç
ýòèõ ðåøåíèé ìîæíî âûáèðàòü äëÿ çàäà÷è ïåðåðàñïðåäåëåíèÿ íàãðóçêè.
Ñëîæíîñòü àëãîðèòìà è åãî ïðàâèëüíîñòü. Ïðè ðåøåíèè óðàâíåíèÿ ñî-
ñòîÿíèÿ â äàííîì àëãîðèòìå èñïîëüçóåòñÿ TSS-àëãîðèòì äëÿ âû÷èñëåíèÿ ìíî-
æåñòâà T-èíâàðèàíòîâ [6]. Ýòîò àëãîðèòì èìååò ýêñïîíåíöèàëüíóþ îöåíêó âðå-
ìåííîé ñëîæíîñòè, îäíàêî ñïåöèôèêà äàííîãî êëàññà ÑÏ ñîñòîèò â òîì, ÷òî ìàò-
ðèöà èíöèäåíòíîñòè ÑÏ ÿâëÿåòñÿ ðàçðåæåííîé.  ýòîì ñëó÷àå TSS-àëãîðèòì
ðàáîòàåò ïîëèíîìèàëüíîå âðåìÿ.
Äëÿ îáîñíîâàíèÿ àëãîðèòìà ïåðåðàñïðåäåëåíèÿ íàãðóçêè çàìåòèì, ÷òî TSS-àëãî-
ðèòì îáîñíîâàí, è ïîñêîëüêó îí ÿâëÿåòñÿ îñíîâíûì ïðè ïîèñêå ìàðøðóòà ïåðåðàñ-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 155
ïðåäåëåíèÿ íàãðóçêè, òî ýòèì
ïîäòâåðæäàåòñÿ è ïðàâèëüíîñòü
àëãîðèòìà ÐÀÂÍÎÌ-ÍÀÃÐ.
Êðîìå òîãî, äàííûé àëãîðèòì
íàõîäèò ìèíèìàëüíûå ðåøåíèÿ,
ïîñêîëüêó ëþáîå äðóãîå ðåøå-
íèå ÿâëÿåòñÿ íåîòðèöàòåëüíîé
ëèíåéíîé êîìáèíàöèåé ýòèõ ðå-
øåíèé.
Îòìåòèì, ÷òî âû÷èñëåíèå
ðàçìåòêè M èñõîäÿ èç
M m m mn0 1 2� ( , , , )� è k âû-
ïîëíÿåòñÿ ñëåäóþùèì îáðà-
çîì. Íàõîäèì ðàçëîæåíèå
S m k b bi
i
n
� � # �
�
�
1
1 ïóòåì äå-
ëåíèÿ S íà k; òîãäà M áóäåò èìåòü b êîìïîíåíò, êîòîðûå ðàâíû k, à îñòàëüíûå
êîìïîíåíòû ìîãóò ïðèíèìàòü ïðîèçâîëüíûå çíà÷åíèÿ, ìåíüøèå k.
Ðàññìîòðèì ñëó÷àé, êîãäà m n k� # . Ïðèâåäåííûé âûøå àëãîðèòì ðàáîòàåò
ïðè îãðàíè÷åíèè, êîãäà êîëè÷åñòâî çàäàíèé â êàíàëàõ áëîêà íå ïðåâûøàþò åãî
ïðîïóñêíîé ñïîñîáíîñòè. Åñëè ýòî óñëîâèå íå âûïîëíÿåòñÿ, òî ïåðåðàñïðåäåëå-
íèå íàãðóçêè îñóùåñòâëÿåòñÿ ñ ó÷åòîì çàãðóæåííîñòè ñîñåäíèõ áëîêîâ. Ðàññìîò-
ðèì ïðèìåð. Ïóñòü èìååòñÿ äâà ñîåäèíåííûõ ìåæäó ñîáîé áëîêà (ðèñ. 17). Åñëè
îäèí èç íèõ íåäîãðóæåí, à âòîðîé ïåðåãðóæåí, òî ïðè m n k� � #( )2 2 ðåøåíèå çà-
äà÷è ïåðåðàñïðåäåëåíèÿ íàãðóçêè âûïîëíÿåòñÿ àëãîðèòìîì ÐÀÂÍÎÌ-ÍÀÃÐ.
Íàïðèìåð, åñëè n � 6, k � 3, M 0 7 5 4 2 1 2 0 2 1 1� ( , , , , , , , , , ), òî ñëåäîâàòåëüíî, ïåðâûé
áëîê ïåðåãðóæåí è íåîáõîäèìî ïåðåðàñïðåäåëåíèå íàãðóçêè çà ñ÷åò ñîñåäíåãî
áëîêà, êîòîðûé â äàííîì ñëó÷àå íåäîãðóæåí. Ïðèíèìàåì
M � ( , , , , , , , , , )3 3 3 3 3 3 3 3 0 1 è ïîëó÷àåì óðàâíåíèå ñîñòîÿíèÿ äëÿ äàííîé ÑÏ:
A x# �
� �
� �
1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1
� � �
� � �
� �
� �
1
0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0
0 0
� �
� �
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
� �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
!
!
!
!
!
!
!
!
!
!
!
!
!
# �
�
�
�
�
�
�
�
�
�
�
�
x
4
2
1
1
2
1
3
1
1
0
�
�
�
�
�
�
�
�
�
!
!
!
!
!
!
!
!
!
!
!
!
!
.
Èìååì ìíîæåñòâî ðåøåíèé äàííîé ñèñòåìû:
x1 0 0 2 0 0 0 0 1 0 3 0 4 3 0 0 0 0 1 0 0 0 0� ( ), x2 3 0 5 0 3 0 2 0 0 0 0 1 3 0 0 0 0 1 0 0 0 0� ( ),
x3 0 2 0 0 0 2 0 3 0 5 0 6 3 0 0 0 0 1 0 0 0 0� ( ), x4 1 0 3 0 1 0 0 0 0 2 0 3 3 0 0 0 0 1 0 0 0 0� ( ),
x5 4 0 6 0 4 0 3 0 1 0 0 0 3 0 0 0 0 1 0 0 0 0� ( ), x6 3 0 5 0 6 0 2 0 0 0 0 1 0 0 0 3 0 4 0 3 0 3� ( ),
x7 0 2 0 0 1 0 0 3 0 5 0 6 0 0 0 3 0 4 0 3 0 3� ( ), x8 0 2 0 0 0 0 0 3 0 5 0 6 1 0 0 2 0 3 0 2 0 2� ( ),
x9 0 3 0 1 0 0 0 4 0 6 0 7 0 0 0 3 0 4 0 3 0 3� ( ), x10 0 0 2 0 3 0 0 1 0 3 0 4 0 0 0 3 0 4 0 3 0 3� ( ),
x11 1 0 3 0 4 0 0 0 0 2 0 3 0 0 0 3 0 4 0 3 0 3� ( ), x12 4 0 6 0 7 0 3 0 1 0 0 0 0 0 0 3 0 4 0 3 0 3� ( ),
x13 1 0 3 0 0 0 0 0 0 2 0 3 4 0 1 0 0 0 1 0 1 0� ( ), x14 0 0 2 0 0 1 0 1 0 3 0 4 4 0 1 0 0 0 1 0 1 0� ( ),
156 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
t1
t7
t3
t9
1 2
5
4
6
t11
t5
t2
t10
t8
t6
t4
t12
t13
t19
t15
t21
7
10 9
8
t17
t14
t22
t20
t18
t16
3
Ðèñ. 17. Ñåòü Ïåòðè äëÿ äâóõ áëîêîâ
x15 0 2 0 0 0 3 0 3 0 5 0 6 4 0 1 0 0 0 1 0 1 0� ( ) , x16 4 0 6 0 0 0 3 0 1 0 0 0 7 0 4 0 3 0 4 0 4 0� ( ) ,
x17 4 0 6 0 3 0 3 0 1 0 0 0 4 0 1 0 0 0 1 0 1 0� ( ), x18 3 0 5 0 0 0 2 0 0 0 0 1 6 0 3 0 2 0 3 0 3 0� ( ),
x19 3 0 5 0 2 0 2 0 0 0 0 1 4 0 1 0 0 0 1 0 1 0� ( ).
Èç ýòèõ ðåøåíèé îïòèìàëüíûìè áóäóò, íàïðèìåð, ïåðâîå è ÷åòâåðòîå. Âûáè-
ðàÿ ïåðâîå ðåøåíèå â êà÷åñòâå îïòèìàëüíîãî è àíàëèçèðóÿ åãî, ïîëó÷àåì
îïòèìàëüíûé ìàðøðóò.  ýòîì ñëó÷àå ïåðåíàïðàâëÿþòñÿ:
— äâà çàäàíèÿ èç êàíàëà 2 â êàíàë 3 (äâóêðàòíîå ñðàáàòûâàíèå ïåðåõîäà t3),
— îäíî çàäàíèå èç êàíàëà 5 â êàíàë 4 (ñðàáàòûâàíèå ïåðåõîäà t8),
— òðè çàäàíèÿ èç êàíàëà 6 â êàíàë 5 (òðè ñðàáàòûâàíèÿ ïåðåõîäà t10),
— ÷åòûðå çàäàíèÿ èç êàíàëà 1 â êàíàë 6 (÷åòûðå ñðàáàòûâàíèÿ ïåðåõîäà t12),
— òðè çàäàíèÿ èç êàíàëà 3 â êàíàë 7 (òðè ñðàáàòûâàíèÿ ïåðåõîäà t13),
— îäíî çàäàíèå èç êàíàëà 9 â êàíàë 8 (ñðàáàòûâàíèå ïåðåõîäà t18).
Òàêèì îáðàçîì, ïîëó÷àåì ìàðøðóò ïåðåðàñïðåäåëåíèÿ íàãðóçêè:
2 3 7
2 33 13t t
% �% % �%% , 1 6 5 4
4 312 10 8t t t
% �%% % �%% % �% , 9 818t
% �% .
Äàëüíåéøåå íàðàùèâàíèå áëîêîâ è êàíàëîâ â áëîêàõ íå âëèÿåò íà àëãîðèòì
ïåðåðàñïðåäåëåíèÿ íàãðóçêè. Îäíàêî ïðè ýòîì âîçðàñòàåò ðàçìåð ìàòðèöû â
óðàâíåíèè ñîñòîÿíèÿ, ÷òî ñóùåñòâåííûì îáðàçîì âëèÿåò íà ñëîæíîñòü åãî ðåøå-
íèÿ. Ïîýòîìó åñëè îãðàíè÷èòü êîëè÷åñòâî ñìåæíûõ áëîêîâ (íàïðèìåð, ÷åòûðå
áëîêà, â êîòîðûõ íå áîëåå ÷åì 20 êàíàëîâ), òî ïîëó÷èì ïðèåìëåìûå âðåìåííûå
îãðàíè÷åíèÿ ñëîæíîñòè ïðè âû÷èñëåíèè îïòèìàëüíûõ ìàðøðóòîâ ïåðåðàñïðåäå-
ëåíèÿ íàãðóçêè â òàêîé ÈÒ-èíôðàñòðóêòóðå.
ÇÀÊËÞ×ÅÍÈÅ
Ñîãëàñíî ïðåäëîæåííîìó ìåòîäó ïðîåêòèðîâàíèÿ ÈÒ-èíôðàñòóêòóð íåîáõîäè-
ìî âûïîëíèòü ïîñëåäîâàòåëüíîñòü ýòàïîâ.
— Ôîðìèðîâàíèå ÑÏ â öåëÿõ èññëåäîâàíèÿ ñâîéñòâ (êàê ñòàòè÷åñêîãî, òàê
è äèíàìè÷åñêîãî õàðàêòåðà).
— Èñïðàâëåíèå îøèáîê ïðîåêòèðîâàíèÿ è ìîäåëèðîâàíèÿ (â òîì ÷èñëå ÃÀ)
íà îñíîâå ðåçóëüòàòîâ àíàëèçà ñâîéñòâ, ïîëó÷åííûõ íà ïåðâîì ýòàïå.
— Âûáîð êîíêðåòíîé ïëàòôîðìû äëÿ ðåàëèçàöèè ðàçðàáîòàííîé ÈÒ-èí-
ôðàñòóêòóðû (â çàâèñèìîñòè îò ñóùåñòâóþùèõ ñðåäñòâ, ïîòåíöèàëüíûõ ïîëüçî-
âàòåëåé, óñëîâèé ýêñïëóàòàöèè è ò.ä.).
— Ïîäõîä ðàñïðîñòðàíÿåòñÿ íà ìîäåëè, â êîòîðûõ ÿâíî ôèãóðèðóåò âðåìÿ (âðå-
ìåííûå àâòîìàòû è âðåìåííûå ÑÏ, ãèáðèäíûå àâòîìàòû è ãèáðèäíûå ÑÏ è ò.ä.)
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Áîéêî Þ.Â., Âîëîõîâ Â.Ì., Ãëèáîâåöü Ì.Ì., ªðøîâ Ñ.Â., Êðèâèé Ñ.Ë. Ïîãîð³ëèé Ñ.Ä.,
Ðîë³ê Î.²., Òåëåíèê Ñ.Ô., ßñî÷êà Ì.Â. Ìåòîäè òà íîâ³òí³ ï³äõîäè äî ïðîåêòóâàííÿ, óïðàâë³ííÿ
³ çàñòîñóâàííÿ âèñîêîïðîäóêòèâíèõ ²Ò-³íôðàñòðóêòóð. Êè¿â: Âèäàâí.-ïîë³ãðàô. öåíòð «Êè¿â-
ñüêèé óí³âåðñèòåò», 2016. 447 ñ.
2. Êðèâèé Ñ.Ë. Äèñêðåòíà ìàòåìàòèêà. ×åðí³âö³; Êè¿â: Áóêðåê, 2017. 567 ñ.
3. Ñåð㳺íêî ².Â., Êðèâèé Ñ.Ë., Ïðîâîòàð Î.². Àëãåáðà¿÷í³ àñïåêòè ³íôîðìàö³éíèõ òåõíîëîã³é.
Êè¿â: Íàóê. äóìêà, 2011. 399 ñ.
4. Kryvyi S., Hajder M., Dymora P., Mazurek M. Designing of the computer network topologies and
coherent graphs algebra. Annales Universitatis Mariae Curie-Sklodowska, Sectia A1. Informatica.
Lublin, 2006. Vol. 5. P. 379–391.
5. Murata T. Petri nets: Properties, analysis and applications. Proc. of the IEEE. 1989. Vol. 77, N 4.
P. 541–580.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6 157
6. Êðèâèé Ñ.Ë. Ëiíiéíi äiîôàíòîâi îáìåæåííÿ òà ¿õ çàñòîñóâàííÿ. ×åðíiâöi; Êè¿â: Áóêðåê, 2015.
224 ñ.
7. Ãëèáîâåöü Ì.Ì., Ãóëàºâà Í.Ì. Åâîëþöiéíi àëãîðèòìè. Êè¿â: Êèºâî-Ìîãèëÿíñüêà àêàäåìiÿ,
2013. 826 ñ.
8. Ïîãîðiëèé Ñ.Ä., Áiëîóñ Ð.Â., Áiëîêîíü ².Â. Çàñòîñóâàííÿ ãåíåòè÷íèõ àëãîðèòìiâ ó êîìï’þòåð-
íèõ ñèñòåìàõ. Çà ðåä. Ïîãîðiëîãî Ñ.Ä. Êè¿â: Âèäàâí.-ïîë³ãðàô. öåíòð «Êè¿âñüêèé óí³âåðñè-
òåò», 2014. 320 ñ
9. Ïîãîð³ëèé Ñ.Ä., Á³ëîóñ Ð.Â. Ãåíåòè÷íèé àëãîðèòì ðîçâ’ÿçàííÿ çàäà÷³ ìàðøðóòèçàö³¿ â ìåðå-
æàõ. Ïðîáëåìè ïðîãðàìóâàííÿ. 2010. ¹ 2–3. C. 171–178.
10. Potebnia A., Pogorilyy S. Innovative GPU accelerated algorithm for fast minimum convex hulls
computation. Proc. of the Federated Conference on Computer Science and Information Systems
(FedCSIS). 2015. Vol. 5. P. 555–561.
Íàä³éøëà äî ðåäàêö³¿ 30.01.2018
Ñ.Ë. Êðèâèé, Ñ.Ä. Ïîãîð³ëèé, Ì.Ì. Ãëèáîâåöü, Þ.Â. Áîéêî, Í.Ì. Ñèäîðîâà
ÏÐÎÅÊÒÓÂÀÍÍß ²Ò-²ÍÔÐÀÑÒÐÓÊÒÓÐÈ
Àíîòàö³ÿ. Çàïðîïîíîâàíî ìåòîäèêó ïðîåêòóâàííÿ ²Ò-³íôðàñòðóêòóðè â óìî-
âàõ îáìåæåíèõ ðåñóðñ³â. Ìåòîäèêà ´ðóíòóºòüñÿ íà âëàñòèâîñòÿõ àëãåáðè
ãðàô³â, ãåíåòè÷íèõ àëãîðèòì³â, ìåðåæ Ïåòð³ òà îñîáëèâîñòÿõ îáìåæåíü. Ðîç-
ãëÿíóòî äâà ï³äõîäè äî ðîçâ’ÿçàííÿ çàäà÷³ áàëàíñóâàííÿ íàâàíòàæåíü
â ²Ò-³íôðàñòðóêòóð³.
Êëþ÷îâ³ ñëîâà: àëãåáðà ãðàô³â, òîïîëîã³ÿ, ²Ò-³íôðàñòðóêòóðà, ãåíåòè÷í³ àëãî-
ðèòìè, ìåðåæ³ Ïåòð³.
S.L. Kryvyy, S.D. Pogorilyy, M.M. Glybovets, Y.V. Boyko, N. Sydorova
DEVELOPMENT OF THE IT INFRASTRUCTURE
Abstract. A metodology for development of IT-infrastructure under conditions
of constraints resources is proposed. This metodology is based on the properties
of graph algebra, genetic algorithms, Petri nets, and specific features of the
constraints. Two approaches to solving load-balancing problems in IT
infrastructure are considered.
Keywords: graph algebra, topology, IT infrastructure, genetic algorithms, Petri
nets.
Êðûâûé Ñåðãåé Ëóêüÿíîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè
Òàðàñà Øåâ÷åíêî, e-mail: sl.krivoi@gmail.com.
Ïîãîðåëûé Ñåðãåé Äåìüÿíîâè÷,
äîêòîð òåõí. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè
Òàðàñà Øåâ÷åíêî, e-mail: sdp77@i.ua.
Ãëèáîâåö Íèêîëàé Íèêîëàåâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû Íàöèîíàëüíîãî óíèâåðñèòåòà «Êèåâî-Ìîãè-
ëÿíñêàÿ àêàäåìèÿ», e-mail: glib@ukma.kiev.ua.
Áîéêî Þðèé Âëàäèìèðîâè÷,
êàíäèäàò òåõí. íàóê, äîöåíò, äîöåíò êàôåäðû Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà
Øåâ÷åíêî, e-mail: Boyko@univ.kiev.ua.
Ñèäîðîâà Íèêà Íèêîëàåâíà,
àñïèðàíòêà Íàöèîíàëüíîãî àâèàöèîííîãî óíèâåðñèòåòà, Êèåâ, e-mail: nika.sidorova@gmai.com.
158 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 6
|