Автореферат (Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах)

Íà ïðàâàõ ðóêîïèñèÌàëüêîâñêèé Íèêîëàé Âëàäèìèðîâè÷ÐÀÍÄÎÌÈÇÈÐÎÂÀÍÍÛÅ ÀËÃÎÐÈÒÌÛ ÐÀÑÏÐÅÄÅËÅÍÈßÐÅÑÓÐÑΠÂÀÄÀÏÒÈÂÍÛÕ ÌÓËÜÒÈÀÃÅÍÒÍÛÕ ÑÈÑÒÅÌÀÕ01.01.09 Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêàÿ êèáåðíåòèêàÀÂÒÎÐÅÔÅÐÀÒäèññåðòàöèè íà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÑàíêò-Ïåòåðáóðã2017Ðàáîòà âûïîëíåíà â Ñàíêò-Ïåòåðáóðãñêîì ãîñóäàðñòâåííîì óíèâåðñèòåòå.Íàó÷íûé ðóêîâîäèòåëü:äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîð Ãðàíè÷èí Îëåã Íèêîëàåâè÷Îôèöèàëüíûå îïïîíåíòû:ÕËÅÁÍÈÊΠÌèõàèë Âëàäèìèðîâè÷,äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîð ÐÀÍ, ÔÃÁÓÍ ¾Èíñòèòóò ïðîáëåìóïðàâëåíèÿ èì. Â.À. Òðàïåçíèêîâà Ðîññèéñêîéàêàäåìèè íàóê¿, çàâåäóþùèéëàáîðàòîðèåé àäàïòèâíûõ è ðîáàñòíûõñèñòåì èì.

ß.Ç. ÖûïêèíàÓÑÈÊ Åãîð Âëàäèìèðîâè÷,êàíäèäàò ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ÇÀÎ Ïðîåêòíî-êîíñòðóêòîðñêîå áþðî ¾ÐÈο,âåäóùèé èíæåíåð-ïðîãðàììèñòÂåäóùàÿ îðãàíèçàöèÿ:Ôåäåðàëüíîå ãîñóäàðñòâåííîå áþäæåòíîåîáðàçîâàòåëüíîå ó÷ðåæäåíèå âûñøåãî îáðàçîâàíèÿ¾Ìîñêîâñêèé ôèçèêî-òåõíè÷åñêèé èíñòèòóò(ãîñóäàðñòâåííûé óíèâåðñèòåò)¿Çàùèòà ñîñòîèòñÿ 2017 ãîäà â÷àñîâ íà çàñåäàíèè äèññåðòà-öèîííîãî ñîâåòà Ä 212.232.29 íà áàçå Ñàíêò-Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïî àäðåñó: 198178, Ñàíêò-Ïåòåðáóðã, 10 ëèíèÿ Â.Î., ä. 33/35, àóä. 74.Ñ äèññåðòàöèåé ìîæíî îçíàêîìèòüñÿ â Íàó÷íîé áèáëèîòåêå èì.

Ì. Ãîðüêîãî ÑàíêòÏåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà ïî àäðåñó: 199034, Ñàíêò-Ïåòåðáóðã,Óíèâåðñèòåòñêàÿ íàá., ä. 7/9 è íà ñàéòådisser/h7ytZqrhBk.pdfÀâòîðåôåðàò ðàçîñëàí https://disser.spbu.ru/files/disser2/2017 ã.Ó÷åíûé ñåêðåòàðüäèññåðòàöèîííîãî ñîâåòà Ä 212.232.29,äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîðÂ.

Ì. ÍåæèíñêèéÎáùàÿ õàðàêòåðèñòèêà ðàáîòûÀêòóàëüíîñòü òåìû. Ñåòåâûå òåõíîëîãèè íà÷àëè ðàçâèâàòüñÿ áîëåå ïîëóâåêà íàçàä, à â ïîñëåäíèå äåñÿòèëåòèÿ ýòà ñôåðà ïîäâåðãëàñü çíà÷èòåëüíîìó ðàñøèðåíèþ.Ðàçâèòèå Èíòåðíåòà è ëîãèñòèêè, çàìåäëåíèå ñêîðîñòè ðîñòà âû÷èñëèòåëüíûõ ìîùíîñòåé ýòè è äðóãèå ôàêòîðû ïîâëèÿëè íà óâåëè÷åíèå èíòåðåñà ê ðàñïðåäåëåííûìâû÷èñëåíèÿì, ñåòåâûì òåõíîëîãèÿì è ñìåæíûì îáëàñòÿì.  ñâîþ î÷åðåäü ìóëüòèàãåíòíûå òåõíîëîãèè ñòàëè ïîïóëÿðíûìè òîëüêî â ïîñëåäíèå 10-20 ëåò, íî ïðè ýòîìçàíÿëè ñâîþ íèøó â îáëàñòè ðàñïðåäåëåííûõ âû÷èñëåíèé. Îñíîâíûì íàïðàâëåíèåìýòîé ðàáîòû ÿâëÿåòñÿ èçó÷åíèå ñâîéñòâ íåñêîëüêèõ ìîäåëåé çàäà÷ ðàñïðåäåëåíèÿðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ ñ óïîðîì íà ñåòåâûå ïîòîêîâûå çàäà÷è. Îñíîâíîåòåîðåòè÷åñêîå íàïðàâëåíèå èññëåäîâàíèå ñòîõàñòè÷åñêèõ ïîòîêîâûõ ïðîöåññîâ,ïðàêòè÷åñêîå ðàñïðåäåëåíèå çàãðóçêè â âû÷èñëèòåëüíûõ ñåòÿõ è ïåðåäà÷à äàííûõ â ãðóïïàõ ìîáèëüíûõ ðîáîòîâ.Âñå ðàññìàòðèâàåìûå â ðàáîòå ìîäåëè ïîäðàçóìåâàþò îòûñêàíèå íåêîòîðîãîîïòèìàëüíîãî ïî âðåìåíè ïðîöåññà (âûïîëíåíèå ãðóïïû çàäàíèé çà íàèìåíüøååâðåìÿ, ïåðåäà÷à íàáîðà ñîîáùåíèé â ãðóïïå ìîáèëüíûõ ðîáîòîâ çà íàèìåíüøååâðåìÿ).

 òåîðèè óïðàâëåíèÿ, îñíîâíàÿ ìàññà ðàáîò ïî ïîñòðîåíèþ îïòèìàëüíûõäèíàìè÷åñêèõ ïðîöåññîâ îñíîâàíà íà ïðèíöèïå äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿè ïðèíöèïå ìàêñèìóìà Ïîíòðÿãèíà.  ñëó÷àå îòñóòñòâèÿ íåîïðåäåëåííîñòåé è èçìåíåíèé ïàðàìåòðîâ ñèñòåìû âî âðåìåíè, ðàññìàòðèâàåìûå çàäà÷è âûðîæäàþòñÿ âçàäà÷è ìàòåìàòè÷åñêîé îïòèìèçàöèè.  îáùåì âèäå òàêèå çàäà÷è ðàññìàòðèâàëèñüÊàíòîðîâè÷åì (îáùàÿ òåîðèÿ ëèíåéíîãî ïðîãðàììèðîâàíèÿ), Õà÷èÿíîì (ìåòîä ýëëèïñîèäîâ), Ïîëÿêîì (îáùàÿ òåîðèÿ âûïóêëîé îïòèìèçàöèè), Êàðìàðêàðîì (ïîëèíîìèàëüíûé ìåòîä âíóòðåííåé òî÷êè äëÿ çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ),Íåñòåðîâûì è Íåìèðîâñêèì (ïîëèíîìèàëüíûå ìåòîäû äëÿ çàäà÷ íåëèíåéíîé âûïóêëîé îïòèìèçàöèè), Áîéäîì è Âàíäåíáåðãå (ñîâðåìåííàÿ òåîðèÿ îïòèìèçàöèè) èìíîãèìè äðóãèìè.Äëÿ äèññåðòàöèîííîé ðàáîòû îñîáóþ ðîëü èãðàþò ñâîéñòâà çàäà÷ ïîòîêîâîãîòèïà, áîëüøîå çíà÷åíèå èìååò çàäà÷à î ìàêñèìàëüíîì ïîòîêå è çàäà÷à î ïîòîêåìèíèìàëüíîé ñòîèìîñòè (Ôîðä è Ôàëêåðñîí), çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå(Ãàëëî, Ãðèãîðèàäèñ è Òàðüÿí).

Ýòè çàäà÷è ÿâëÿþòñÿ áàçîâûìè ñòàòè÷åñêèìè ïîòîêîâûìè çàäà÷àìè. Âî ìíîãèõ ñëó÷àÿõ èçó÷åíèå ïðîòåêàþùèõ âî âðåìåíè ïîòîêîâûõ ïðîöåññîâ ìîæåò áûòü ñâåäåíî ê ðàññìîòðåíèþ ñòàöèîíàðíûõ ïîòîêîâûõ çàäà÷.3Òàê, íàïðèìåð, â ðàáîòàõ Òåîäîðîâè÷à è Âóêàäèíîâè÷à, Õîëëà, Êàññåòà, Ãàñíèêîâàðàññìîòðåíû ñòàòè÷åñêèå ìåòîäû ìîäåëèðîâàíèÿ òðàíñïîðòíûõ ïîòîêîâ, â ðàáîòàõÔîðäà è Ôàëêåðñîíà, Ñêóòåëëû ðàññìîòðåíû äèíàìè÷åñêèå ïîòîêîâûå ïðîöåññû,çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî ïðîöåññà ñî ñòàòè÷åñêèìè ïðîïóñêíûìè ñïîñîáíîñòÿìè è âðåìåíàìè ïåðåõîäà ñâåäåíû ê ñòàòè÷åñêèì ïîòîêîâûì çàäà÷àì. Íåñìîòðÿ íà áîëåå ïîëóâåêà ñ ìîìåíòà ïîÿâëåíèÿ, ïîñòàíîâêè ýòèõ çàäà÷, äîïóñêàþùèåíåîïðåäåëåííîñòè íåêîòîðûõ õàðàêòåðèñòèê, ïîÿâèëèñü îòíîñèòåëüíî íåäàâíî â ðàáîòàõ Ãëîêíåðà è Íåìõàóçåðà, Õàíà, Ïåíãà è Âàíãà, Øåíãà è Ãàî. Ïðè ýòîì, íàäàííûé ìîìåíò îòñóòñòâóþò ðàáîòû, èçó÷àþùèå ïîòîêîâûå çàäà÷è â óñëîâèÿõ äèíàìè÷åñêè èçìåíÿþùèõñÿ ïàðàìåòðîâ è âíåøíèõ íåêîíòðîëèðóåìûõ âîçìóùåíèé.Çàäà÷è, ðàññìàòðèâàåìûå â äèññåðòàöèîííîé ðàáîòå, ìîòèâèðîâàííû èçìåí÷èâîñòüþ è ñòîõàñòè÷åñêîé ïðèðîäîé ðåàëüíûõ ôèçè÷åñêèõ ïðîöåññîâ.

Çàäà÷è ìàòåìàòè÷åñêîé îïòèìèçàöèè â óñëîâèÿõ ðàçëè÷íîãî ðîäà íåîïðåäåëåííîñòåé èçó÷àëèñüâ ðàáîòàõ ðàáîòàõ Ðîááèíñà è Ìîíðî (îáùèé ìåòîä ñòîõàñòè÷åñêîé àïïðîêñèìàöèè),Êèôåðà è Âîëüôîâèöà (ìåòîä êîíå÷íûõ ðàçíîñòåé), Êàëìàíà è Áüþñè(ôèëüòð Êàëìàíà-Áüþñè), Âèíåðà è Êîëìîãîðîâà (ôèëüòð Âèíåðà-Êîëìîãîðîâà),Ãðàíè÷èíà (ðåøåíèå îïòèìèçàöèîííûõ çàäà÷ ñ íåñòàòèñòè÷åñêèìè ïîìåõàìè), Êàìïè è Êàëàôèîðå (ñöåíàðíûé ïîäõîä), Õëåáíèêîâà, Ïîëÿêà è Êóíöåâè÷à.  ðàáîòàõÁåíâåíèñòå, Ìåòèâüå è Ïðèîðî, Áîäñîíà è Äóãëàñà, Àíòàë, Ãðàíè÷èíà è Ëåâè èçó÷àþòñÿ àäàïòèâíûå àëãîðèòìû, â ðàáîòàõ Ïàðôåíîâà è Òåðåõîâà, Êîïåòöà, Ìåëüíèêîâà è Ìåëüíèêîâîé èçó÷àþòñÿ ñìåæíûå âîïðîñû î ñèñòåìàõ ðåàëüíîãî âðåìåíè.Ñëåäóþùèå ðàáîòû ðàññìàòðèâàþò ñõîæèå ñ ïîñòàâëåííûìè â äèññåðòàöèîííîé ðàáîòå ïðèêëàäíûìè çàäà÷àìè: â ðàáîòàõ Òàíòàâè è Òàóñëè, Êèìà è Êàìåäû,×îãóóíà è Êàìåäû ðàññìàòðèâàþòñÿ àëãîðèòìû îïòèìàëüíîãî ñòàòè÷åñêîãî áàëàíñèðîâàíèÿ çàãðóçêè äëÿ òèïîâûõ ñåòåé (çâåçäà, êîëüöî è ò.ï.) ñ äîñòàòî÷íî îáùèìèïðåäïîëîæåíèÿìè î ïðîïóñêíîé ñïîñîáíîñòè ñåòè.

 ðàáîòå Ãðîñó è Õðîíîïóëîñàðàññìàòðèâàþòñÿ èãðîâûå ìîäåëè çàäà÷è ðàñïðåäåëåíèÿ íàãðóçêè. Ñòîõàñòè÷åñêèåïîñòàíîâêè çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ ïîÿâèëèñü îòíîñèòåëüíî íåäàâíî è áûëèïðåäëîæåíû â ðàáîòàõ Àìåëèíîé, Àìåëèíîé è Ôðàäêîâà, Ãðàíè÷èíûì è Àìåëèíîéè äð.Áîëüøèíñòâî èç ïåðå÷èñëåííûõ ðàáîò ñîñòàâëÿþò îáùèé ìàòåìàòè÷åñêèé ôóíäàìåíò çàäà÷è ðàñïðåäåëåíèÿ ðåñóðñîâ, ëèøü íåáîëüøàÿ ÷àñòü ðàáîò èçó÷àåò îñîáåííîñòè ðåàëèçàöèè ìàòåìàòè÷åñêèõ ìåòîäîâ â ìóëüòèàãåíòíûõ ñèñòåìàõ. Îñíîâíîé ñëîæíîñòüþ òàêîé ðåàëèçàöèè ÿâëÿåòñÿ äåöåíòðàëèçîâàííîñòü. Òðàäèöèîííàÿ4ïàðàäèãìà ïàðàëëåëüíûõ âû÷èñëåíèé ïîäðàçóìåâàåò íàëè÷èå öåíòðàëüíîãî óçëà,èìåþùåãî èíôîðìàöèþ î âñåì âû÷èñëèòåëüíîì ïðîöåññå.

 ìóëüòèàãåíòíûõ ñèñòåìàõ òàêèå óçëû îáû÷íî îòñóòñòâóþò, ÷òî çíà÷èòåëüíî óïðîùàåò ïîñòðîåíèå ñèñòåìû è å¼ ìàñøòàáèðóåìîñòü, îäíàêî âî ìíîãèõ ñëó÷àÿõ çàòðóäíÿåò âû÷èñëèòåëüíûéâîçìîæíà ëè ýôôåêòèâíàÿ ðåàëèçàöèÿ êëàññè÷åñêèõ ìåòîäîâ îïòèìàëüíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñèñòåìàõ?  ðàáîòå ïîëó÷åí ïîëîæèòåëüíûéïðîöåññ. Îäèí èç îáùèõ âîïðîñîâ, èçó÷åíèþ êîòîðîãî íàïðàâëåíà ýòà ðàáîòà, îòâåò äëÿ íåñêîëüêèõ êîíêðåòíûõ çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ, îñíîâàííûõ íà ðåøåíèè ïîòîêîâûõ çàäà÷ îïòèìèçàöèè.

Àëãîðèòìû òàêîãî ðîäà îáû÷íî íàçûâàþòñÿðàñïðåäåëåííûìèèëèìóëüòèàãåíòíûìèè øèðîêî èñïîëüçóþòñÿ íà ïðàêòèêå: âðàáîòàõ Áîéäà è äð., Øàõà, Êåìïå è äð. èçó÷àþòñÿ ïðèìåíåíèå ðàñïðåäåëåííûõàëãîðèòìîâ, íàçûâàåìûõ ñïëåòíÿìè, â ðàáîòàõ Ìàããñà è äð., Õå è äð. èçó÷àþòñÿàëãîðèòìû ñèíõðîíèçàöèè âðåìåíè â ðàñïðåäåëåííûõ ñåòÿõ, â ðàáîòàõ Ìàíôðåäè,Æó è äð. èçó÷àþòñÿ àëãîðèòìû ñîãëàñîâàíèÿ ïîêàçàíèé ñåíñîðíûõ ñåòåé, â ðàáîòàõÎëôàòè-ñàáåðà è Ìþððåÿ, Ôàêñà è Ìþððåÿ, Ðåíà è äð., Ðèêîñà è äð., Àìåëèíîé,Àìåëèíîé è Ôðàäêîâà, Ïàðñåãîâà, Ïîëÿêîâà è Ùåðáàêîâà èçó÷àþòñÿ ïðîòîêîëûêîíñåíñóñà è èõ ïðèëîæåíèÿ, â ðàáîòàõ Êàëÿåâà, Ãàéäóêà è Êàïóñòÿíà, Ôàêñà èÌþððåÿ ðàññìàòðèâàþòñÿ çàäà÷è êîëëåêòèâíîãî âçàèìîäåéñòâèÿ ãðóïï ìîáèëüíûõðîáîòîâ.Êàê óæå áûëî îòìå÷åíî, îáùåå ïðåèìóùåñòâî ìóëüòèàãåíòíîãî ïîäõîäà çàêëþ÷àåòñÿ â ïðîñòîòå îðãàíèçàöèè è ìàñøòàáèðóåìîñòè ñèñòåìû. Äåòàëüíî îñîáåííîñòèòàêèõ ñèñòåì áûëè èçó÷åíû â ðàáîòàõ Âèòòèõà è Ñêîáåëåâà, Ñêîáåëåâà, Ñîëëîãóáà,Èâàùåíêî è äð., Ðæåâñêîãî, Ãîðîäåöêîãî, Ãîðîäåöêîãî, Ãðóøèíñêîãî è Õàáàëîâà.Öåëüþ äèññåðòàöèîííîé ðàáîòûÿâëÿåòñÿ ðàçðàáîòêà è îáîñíîâàíèå àëãî-ðèòìîâ ýôôåêòèâíîãî óïðàâëåíèÿ ðåñóðñàìè â ìóëüòèàãåíòíûõ ñåòÿõ â óñëîâèÿõíåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåì ïàðàìåòðîâ ñåòè è îêðóæàþùåéñðåäû.

Äëÿ äîñòèæåíèÿ öåëè áûëè ïîñòàâëåíû ñëåäóþùèå çàäà÷è:1. Èññëåäîâàòü âîçìîæíîñòü ïðèìåíåíèÿ ìåòîäîâ îïòèìèçàöèè äèíàìè÷åñêèõïðîöåññîâ ïîòîêîâîãî òèïà äëÿ ýôôåêòèâíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ.2. Ðàçðàáîòàòü è îáîñíîâàòü íîâûå àëãîðèòìû ýôôåêòèâíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ.3. Èññëåäîâàòü ðàáîòîñïîñîáíîñòü ðàçðàáîòàííûõ íîâûõ àëãîðèòìîâ ýôôåêòèâ-5íîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ â óñëîâèÿõ íåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåì ïàðàìåòðîâ ñåòè è îêðóæàþùåé ñðåäû,ðàçðàáîòàòü è îáîñíîâàòü ñîîòâåòñòâóþùèå àäàïòèâíûå ìîäèôèêàöèè, èññëåäîâàòü âîçìîæíîñòè ðàíäîìèçàöèè äëÿ óñêîðåíèÿ ïðîöåññà ðåøåíèÿ çàäà÷.4.

Ðåàëèçîâàòü èññëåäîâàííûå ìåòîäû è ïðîâåñòè èõ àïðîáàöèþ äëÿ ðåøåíèÿçàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ â ìóëüòèàãåíòíûõ ñåòÿõ â óñëîâèÿõ íåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ ñî âðåìåíåì ïàðàìåòðîâ ñåòè è îêðóæàþùåéñðåäû.Ìåòîäû èññëåäîâàíèÿ.  äèññåðòàöèîííîé ðàáîòå ïðèìåíÿþòñÿ ìåòîäû ìàòåìàòè÷åñêîé îïòèìèçàöèè, òåîðèè âåðîÿòíîñòåé è ìàòåìàòè÷åñêîé ñòàòèñòèêè, òåîðèè ãðàôîâ, òåîðèè äèíàìè÷åñêèõ ñèñòåì, èìèòàöèîííîãî ìîäåëèðîâàíèÿ, ìóëüòèàãåíòíûõ òåõíîëîãèé.Îñíîâíûå ïîëîæåíèÿ, âûíîñèìûå íà çàùèòó.1. Ïðåäëîæåíà ôîðìóëèðîâêà êëàññà çàäà÷ ìóëüòèàãåíòíîãî ðàñïðåäåëåíèÿ ðåñóðñîâ â âèäå çàäà÷è íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïðîöåññà ïîòîêîâîãî òèïà.2.