Диссертация (Рандомизированные алгоритмы в задачах мультиагентного взаимодействия)

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 Áàëàíñèðîâêà çàãðóçêè óçëîâ âû÷èñëèòåëüíîé ñåòè ñ ïîìîùüþ ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ151.11.21.31.4Ïðåäâàðèòåëüíûå ñâåäåíèÿ . . . . . . . . . . . . . . . . . .Çàäà÷à áàëàíñèðîâêè çàãðóçêè . . . . . . . . . . . . . . . .Ïðîòîêîë ïåðåðàñïðåäåëåíèÿ çàäàíèé . . . . .

. . . . . . .Èñïîëüçîâàíèå ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ íà ïðàêòèêå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212224282 Îïòèìèçàöèÿ ïðîöåññà áàëàíñèðîâêè çàãðóçêè óçëîâ âû÷èñëèòåëüíîé ñåòè ñ çàäà÷àìè ðàçíûõ ïðèîðèòåòîâ332.12.22.32.4Áàëàíñèðîâêè çàãðóçêè ñåòè, âûïîëíÿþùåé çàäàíèÿ ñ ðàçíûìè ïðèîðèòåòàìè . . .

. . . . . . . . . . . . . . . . . . .Äèôôåðåíöèðîâàííûé êîíñåíñóñ . . . . . . . . . . . . . . .Îöåíêà îïòèìàëüíîãî ðàçìåðà øàãà àëãîðèòìà . . . . . . .Ñòîèìîñòíûå îãðàíè÷åíèÿ íà èñïîëüçîâàíèå ñâÿçåé . . . .2.4.1 Ðàíäîìèçàöèÿ èñïîëüçîâàíèÿ ñâÿçåé . . . . . . . . .2.4.2 Óñëîâèÿ äîñòèæèìîñòè äèôôåðåíöèðîâàííîãî êîíñåíñóñà . . . . . . . . . . . . . . . . .

. . . . . . . . .2.4.3 Îïòèìèçàöèÿ ðàçìåðà øàãà àëãîðèòìà . . . . . . . .333648505051603 Èìèòàöèîííîå ìîäåëèðîâàíèå è àäàïòàöèÿ ðàçìåðà øàãààëãîðèòìà623.13.2Ìîäåëèðîâàíèå ïîâåäåíèÿ ñåòåâîé ñèñòåìû, âûïîëíÿþùåéçàäàíèÿ íåñêîëüêèõ êëàññîâ, ïåðåðàñïðåäåëåííûõ ïî ïðîòîêîëó ëîêàëüíîãî ãîëîñîâàíèÿ (2.4) â óñëîâèÿõ ïîìåõ, çàäåðæåê, èçìåíÿþùåéñÿ ñòðóêòóðû ñâÿçåé ñåòè . . . . .

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

. . . . . . . . . . . . . . . . 71Çàêëþ÷åíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Ëèòåðàòóðà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37880Ââåäåíèå ïîñëåäíåå âðåìÿ âñå áîëüøåå âíèìàíèå óäåëÿåòñÿ çàäà÷àì ðàñïðåäåëåííîãî âçàèìîäåéñòâèÿ â ñåòÿõ è óïðàâëåíèÿ â ñåòåâûõ äèíàìè÷åñêèõñèñòåìàõ. Èíòåðåñ ê òåìàòèêå óïðàâëåíèÿ â äèíàìè÷åñêèõ ñåòÿõ âûçâàíïðèëîæåíèÿìè â ðàçëè÷íûõ îáëàñòÿõ, âêëþ÷àÿ, íàïðèìåð, ìíîãîïðîöåññîðíûå ñåòè, ëîãèñòè÷åñêèå ñåòè, ïðîèçâîäñòâåííûå ñåòè, ñåíñîðû è áåñïðîâîäíûå ñåòè, ñêîîðäèíèðîâàííîå äâèæåíèå ÁÏËÀ, ïîäâîäíûõ îáúåêòîâ è ìîáèëüíûõ ðîáîòîâ, ðàñïðåäåëåííûå ñèñòåìû óïðàâëåíèÿ ýëåêòðè÷åñêèìè ñåòÿìè, ñëîæíûå êðèñòàëëè÷åñêèå ðåøåòêè è íàíîñòðóêòóðíûåîáúåêòû.

 ðàáîòàõ ×. Àáäàëëû (C. Abdallah) [48], Ð. Ï. Àãàåâà [45],Á. Ð. Àíäðèåâñêîãî [50, 75], Ï. Àíòñàêëèñà (P. Antsaklis) [64], Ä. Áàèëëåóëà (J. Baillieul) [64], Ð. Â. Áåðäà (R. W. Beard) [100102], Ô. Áóëëî(F. Bullo) [71], Ò. Âèêñåêà (T. Vicsek) [68, 111], Â. À. Âèòòèõà [21], ×. Âó(C. Wu) [113], Â.

È. Ãîðîäåöêîãî [22, 23], È. À. Êàëÿåâà [34], Ä. Êîðòåñà (J. Cortes) [71], Ô. Ëüþèñà (F. Lewis) [91], À. Ñ. Ìàòâååâà [94],À. Ñ. Ìîðñà (A.S. Morse) [86], Ð. Ì. Ìþððåÿ (R. M. Murray) [95, 96],Ð. Îëôàòè-Ñàáåðà (R. Olfati-Saber) [95, 96], Â. Ðåíà (W. Ren) [100102],Ã. À. Ðæåâñêîãî [63, 104], Ã. Òàííåðà (H. Tanner) [48], À. Ë. Ôðàäêîâà [1517,5457,75], Ì. Õóàíãà (M. Huang) [81,82], Ï. Þ. ×åáîòàðåâà [45]è äðóãèõ çàëîæåíû îñíîâû òåîðåòè÷åñêîãî îïèñàíèÿ ìåòîäîâ àíàëèçàè ñèíòåçà äåöåíòðàëèçîâàííîãî àäàïòèâíîãî ìóëüòèàãåíòíîãî óïðàâëåíèÿ, îáñóæäàþòñÿ ìíîãî÷èñëåííûå ïîòåíöèàëüíûå ïðàêòè÷åñêèå ïðèëîæåíèÿ â óïðàâëåíèè ñëîæíûìè ïðîèçâîäñòâåííûìè, ýíåðãåòè÷åñêèìèñèñòåìàìè.Í. Î. Àìåëèíà [1,317,4962,77,85], Ä.

Àðìáðóñòåð (D. Armbruster) [65],À. Ãëàøåíêî [105], È. Ãðà÷åâ [63,105], Ñ. Èíîçåìöåâ [63,83,105], È. À. Êàëÿåâ [34], À. Ñ. Ìèõàéëîâ [65], Ñ. Ý. Ïàðñåãîâ [3638], À. Â. Ïðîñêóðíèêîâ [94, 98], Ï. Î. Ñêîáåëåâ [21, 42, 43, 63, 79, 104, 105], Ï. Ñ. Ùåðáàêîâ [38, 46, 47] è äð. àêòèâíî èçó÷àëè àëãîðèòìû óïðàâëåíèÿ â ñåòÿõ, óçëû êîòîðûõ âûïîëíÿþò îïðåäåëåííûå äåéñòâèÿ ïàðàëëåëüíî.

Ïîäîáíûåñåòåâûå ñèñòåìû ïðèìåíÿþòñÿ â âû÷èñëèòåëüíûõ, ïðîèçâîäñòâåííûõ ñå4òÿõ, ñåòÿõ îáñëóæèâàíèÿ, òðàíñïîðòíûõ è ëîãèñòè÷åñêèõ ñåòÿõ. Íåñìîòðÿ íà îáúåì ðàáîò ïî òåìàòèêå óïðàâëåíèÿ äåöåíòðàëèçîâàííûìè ñèñòåìàìè, óäîâëåòâîðèòåëüíûå ðåøåíèÿ ïðåäëîæåíû äëÿ îãðàíè÷åííîãîêëàññà çàäà÷. Òàêèå ôàêòîðû, êàê ïåðåêëþ÷åíèÿ òîïîëîãèè ñâÿçåé, ïîìåõè è çàäåðæêè ïðè èçìåðåíèè ñîñòîÿíèé àãåíòîâ çíà÷èòåëüíî ïîâûøàþòñëîæíîñòü ðåøåíèÿ çàäà÷.

Äîñòàòî÷íî ïðîñòûå àäàïòèâíûå àëãîðèòìû÷àñòî äåìîíñòðèðóþò óäîâëåòâîðèòåëüíóþ ïðîèçâîäèòåëüíîñòü, íî îñòàþòñÿ îòêðûòûìè âîïðîñû èõ òåîðåòè÷åñêîãî îáîñíîâàíèÿ è äîñòèæåíèÿîïòèìàëüíîé ïðîèçâîäèòåëüíîñòè. Êàê ïðàâèëî, ïðè ïîñòàíîâêå çàäà÷è ïðåäïîëàãàåòñÿ, ÷òî âñå çàäàíèÿ, âûïîëíÿåìûå ñèñòåìîé, îäèíàêîâîâàæíû äëÿ èñïîëíåíèÿ.Òåõíîëîãèÿ ìóëüòèàãåíòíûõ ñèñòåì (ÌÀÑ) ýòî íîâàÿ ïàðàäèãìàðàçâèòèÿ ÈÒ, îðèåíòèðîâàííàÿ íà ñîâìåñòíîå èñïîëüçîâàíèå òåõíîëîãè÷åñêèõ è òåõíè÷åñêèõ äîñòèæåíèé è ïðåèìóùåñòâ, êîòîðûå ïðåäîñòàâëÿþò âîçìîæíîñòè è ìåòîäû èñêóññòâåííîãî èíòåëëåêòà (ÈÈ), àïïàðàòíûåè ïðîãðàììíûå ñðåäñòâà ïîääåðæêè ðàñïðåäåëåííîñòè è îòêðûòîñòè.

Âñâÿçè ñ ýòèì, â íàñòîÿùåå âðåìÿ àêòèâíî ðàçâèâàþòñÿ ìåòîäû ôîðìèðîâàíèÿ è ïîñòðîåíèÿ ñëîæíûõ àäàïòèâíûõ ñèñòåì íà áàçå ìóëüòèàãåíòíûõìåòîäîâ è òåõíîëîãèé [22, 23, 34, 104]. Òàêèå ñèñòåìû ÷àñòî ïðèìåíÿþòñÿäëÿ óïðàâëåíèÿ àíñàìáëÿìè (ðîÿìè, swarms; ñòàÿìè, ocks) äèíàìè÷åñêèõ îáúåêòîâ [68,92,108], âûïîëíÿþùèõ îáùóþ çàäà÷ó èëè çàäà÷ó ñ ðàçäåëÿþùèìèñÿ öåëÿìè â óñëîâèÿõ íåîïðåäåëåííîñòè [18].  êà÷åñòâå èñïîëíèòåëüíûõ ýëåìåíòîâ òàêèõ ñèñòåì èñïîëüçóþòñÿ ðîáîòîòåõíè÷åñêèåóñòðîéñòâà ðàçëè÷íîãî íàçíà÷åíèÿ, êîòîðûå ìîãóò äåéñòâîâàòü â ðàçëè÷íûõ ñðåäàõ: íà çåìëå (ñòàöèîíàðíûå, êîëåñíûå è ãóñåíè÷íûå óñòðîéñòâà), ïîä âîäîé (ìèíèàòþðíûå áåñïèëîòíûå ïîäâîäíûå ëîäêè, ÁÏÏË) èâ âîçäóõå (áåñïèëîòíûå ëåòàòåëüíûå àïïàðàòû, ÁÏËÀ). Îäèí èç íîâûõïîäõîäîâ ðîåâîå óïðàâëåíèå èçó÷àåò âîçìîæíîñòè ïîñòðîåíèÿ ñèñòåìû èç ñîâîêóïíîñòè àâòîíîìíûõ èíòåëëåêòóàëüíûõ àãåíòîâ (ðîáîòîâ)äëÿ äîñòèæåíèÿ êîëëåêòèâíûõ öåëåé, êîòîðûå íå ìîãóò áûòü äîñòèãíóòû îòäåëüíûì ðîáîòîì èëè äëÿ êîòîðûõ êîëëåêòèâíîå âûïîëíåíèå ïîñòàâëåííîé çàäà÷è áîëåå ýôôåêòèâíî.

Îñíîâîïîëàãàþùåé èäååé ðîåâîãî5óïðàâëåíèÿ ÿâëÿåòñÿ ¾ðîåâîé èíòåëëåêò¿ (ÐÈ, Swarm Intelligence), øèðîêî íàáëþäàåìûé â ïðèðîäíîì ìèðå: â êîëîíèÿõ ï÷åë, ìóðàâüåâ, ïðèäâèæåíèè êîñÿêîâ ðûá, ïòè÷èõ ñòàé è ò. ï. Òåðìèí ¾ðîåâîé èíòåëëåêò¿áûë ââåäåí â 1989 ãîäó â êîíòåêñòå èññëåäîâàíèÿ ñèñòåìû êëåòî÷íûõ¾ðîáîòîâ¿ [67]. Ðîåâîé èíòåëëåêò ñèñòåìà, ðåàëèçóþùàÿ óïðàâëåíèåêîëëåêòèâíûì ïîâåäåíèåì äåöåíòðàëèçîâàííîé ñàìîîðãàíèçóþùåéñÿ ñîâîêóïíîñòüþ îäíîðîäíûõ îáúåêòîâ. Ðîåâîé èíòåëëåêò ðàññìàòðèâàåòñÿâ òåîðèè èñêóññòâåííîãî èíòåëëåêòà êàê ìåòîä ¾íå äî êîíöà ôîðìàëèçóåìîé îïòèìèçàöèè¿.Çàäà÷à ñîãëàñîâàíèÿ (êîíñåíñóñà) íà ãðàôàõ ïðè ïîìåõàõ â èçìåðåíèÿõ ñîñòîÿíèé ñîñåäåé è íåòî÷íûõ ñâÿçÿõ ðàññìàòðèâàëàñü â [82, 99] ñïðèìåíåíèåì àëãîðèòìîâ òèïà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè ñ óáûâàþùèì äî íóëÿ ðàçìåðîì øàãà. Ñõîäèìîñòü ïðè øóìàõ è íåóáûâàþùåìðàçìåðå øàãà èçó÷àëàñü â [112], íî ïðè ýòîì ïàðàìåòðû ðàçìåðà øàãàâûáèðàëèñü ðàçëè÷íûìè äëÿ ðàçíûõ àãåíòîâ è ðàññìàòðèâàëñÿ ñïåöèôè÷åñêèé ñöåíàðèé ïîñòðîåíèÿ ñåòè.

Ìåòîäû ñòîõàñòè÷åñêîãî ãðàäèåíòà(ñòîõàñòè÷åñêîé àïïðîêñèìàöèè, SA) òàêæå èñïîëüçîâàëèñü ïðè íàëè÷èèñòîõàñòè÷åñêèõ íåîïðåäåëåííîñòåé [93, 96, 100, 109].  ëèíåéíîì ñëó÷àåáåç îáðàòíûõ ñâÿçåé â ñòîõàñòè÷åñêîé ñåòè ïðîáëåìû äîñòèæåíèÿ ïðèáëèçèòåëüíîãî êîíñåíñóñà ðàññìàòðèâàëèñü â [66].Íà ïðàêòèêå âî âðåìÿ ðàáîòû ñèñòåìû îäíè çàäàíèÿ ìîãóò èìåòüáîëåå âûñîêóþ âàæíîñòü, ÷åì äðóãèå. Ýòî ìîæåò áûòü âûçâàíî íåîáõîäèìîñòüþ âûïîëíåíèÿ ñèñòåìíûõ çàïðîñîâ äëÿ ïîääåðæàíèÿ ðàáîòûâñåé ñèñòåìû; íåêîòîðûå çàäàíèÿ ìîãóò èìåòü áîëåå âûñîêóþ ñðî÷íîñòü,â òî âðåìÿ êàê äëÿ äðóãèõ çàäàíèé âðåìÿ èõ âûïîëíåíèÿ â ñèñòåìå íåòàê êðèòè÷íî; ó ñèñòåìû ìîãóò áûòü íåñêîëüêî ãðóïï ïîëüçîâàòåëåé, êîòîðûì òðåáóåòñÿ ðàçíûé óðîâåíü îáñëóæèâàíèÿ.

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

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