Автореферат (1150608), страница 3
Текст из файла (страница 3)
Ðåçóëüòàòû òåîðåì 2.1 è 2.2 ìîæíî èíòåðïðåòèðîâàòü = 0, òî ýòî îçíà÷àåò, ÷òî+ñîñòîÿíèÿ x ìîæíî ïîñòðîèòüñëåäóþùèì îáðàçîì: åñëè òåîðåìà 1 âûïîëíÿåòñÿ è ïðèäëÿ ëþáîãî íà÷àëüíîãî ñîñòîÿíèÿx−è êîíå÷íîãîïðîöåññ, îòëè÷àþùèéñÿ ïî âðåìåíè îò îïòèìàëüíîãî íà íåêîòîðóþ íåçàâèñèìóþx+ êîíñòàíòó T (0). ×åì áîëüøå ðàçíèöà ìåæäó x− è x+ , òåì ìåíüøå ýòàçàäåðæêà T (0) âëèÿåò íà îáùåå âðåìÿ ðàáîòû ñèñòåìû.
Ïðåäïîëîæåíèå î òîì, ÷òîòåîðåìà 1 âûïîëíÿåòñÿ ïðè = 0 íå âåðíî â îáùåì ñëó÷àå äëÿ óñðåäíÿåìûõ ôóíêîòx−èöèé, îäíàêî äëÿ òåîðåìû 2 ýòîãî è íå íóæíî. ïóíêòå 2.1.3 ïðèâåäåí ïðèìåð ïîñòðîåíèÿ îöåíîê çàäåðæêè äëÿ ñëó÷àéíûõïðîöåññîâ. ðàçäåëå 2.2 îïèñàíû ðàçðàáîòàííûå àäàïòèâíûå ìóëüòèàãåíòíûå àëãîðèòìûðåøåíèÿ çàäà÷è î ìàêñèìàëüíîì ïîòîêå. Íà îñíîâå ýòèõ ìåòîäîâ ñòðîèòñÿ àäàï-12òèâíûé ìåòîä ðåøåíèÿ (6). Îñíîâíàÿ èäåÿ ýòèõ ìåòîäîâ ñîñòîèò â òîì, ÷òî çàäà÷àî ìàêñèìàëüíîì ïîòîêå ñâîäèòñÿ ê ñëåäóþùåé çàäà÷å (ïîäðîáíåå â ïóíêòå 2.2.5)f (x) = 12 xT B 0T B 0 x + xT B 0T b,0 ≤ x e ≤ ce , e ∈ E 0 ,ìèíèìèçèðîâàòüïðè óñëîâèèãäåE0 ìíîæåñòâî äóã, íå èíöèäåíòíûõ âåðøèíàì èñòîêà è ñòîêàèíöèäåíòíîñòè ãðàôàG0 = hV, E 0 i,ñòè, îòíîñÿùèåñÿ òîëüêî ê äóãàì,(8)s, t, B 0 ìàòðèöàb = Bc00 , ãäå c00 ïðîïóñêíûå ñïîñîáíîèíöèäåíòíûì s èëè t. Äëÿ ýòîé çàäà÷è ñòðîèòñÿâåêòîðäâà àäàïòèâíûõ ìóëüòèàãåíòíûé àëãîðèòìà: íà îñíîâå ïðîåêòèâíîãî ãðàäèåíòíîãîñïóñêà è ðàíäîìèçèðîâàííîé âåðñèè ñòîõàñòè÷åñêîé àïïðîêñèìàöèè.
Ðàíäîìèçèðîâàííûé àëãîðèòì îêàçûâàåòñÿ ëó÷øå çà ñ÷åò áîëåå ïðîñòîé ðåàëèçàöèè è óñòîé÷èâîñòè ê ïîìåõàì â íàáëþäåíèè. Àëãîðèòì íà êàæäîì øàãå ïðîèçâîäèò èçìåðåíèÿïðîïóñêíûõ ñïîñîáíîñòåé, íà îñíîâàíèè êîòîðûõ ñòðîèòñÿ óëó÷øåííàÿ îöåíêà ðåøåíèÿ çàäà÷è (8).  ñòàòè÷åñêîì ñëó÷àå ïðîïóñêíûå ñïîñîáíîñòè íå èçìåíÿþòñÿ,à çíà÷èò íå ìåíÿåòñÿ âåêòîðb,â ýòîì ñëó÷àå àëãîðèòì ïîëó÷àåò ïîñëåäîâàòåëü-íîñòü îöåíîê, ýêñïîíåíöèàëüíî ñõîäÿùèõñÿ ê ðåøåíèþ (8).  äèíàìè÷åñêîì ñëó÷àåâåêòîðbè âìåñòå ñ íèì ôóíêöèÿfèçìåíÿþòñÿ, àëãîðèòì àäàïòèðóåòñÿ ê ýòèìèçìåíåíèÿì, íî ïðè ýòîì ñõîäèòñÿ òîëüêî â íåêîòîðóþ îêðåñòíîñòü ðåøåíèÿ (8).fk (x) = 21 xT B 0T B 0 x + xT B 0T bk , ∆k èòåðàöèè k , îïðåäåëÿåìîå ïî ïðàâèëóÅñëè îáîçíà÷èòüâîçìóùåíèå íà∆k = ±eimñ.
â.ðàíäîìèçèðîâàííîå ïðîáíîåpi,2(9)0T keim m-ìåðíûé i-ûé îðò. Äàëåå, Ak = ∆k ∆Tk B 0T B 0 , A = EAi , wik = eim eiTmB b ,wk = Ewik , yk+ = fk (xk + α∆k ) + ξ2k è yk− = fk (xk − α∆k ) + ξ2k+1 çàøóìëåííûåèçìåðåíèÿ íà èòåðàöèè k , ïðè ýòîì ξ2k , ξ2k+1 ïîãðåøíîñòè, âîçíèêàþùèå ïðè èçìåkðåíèè b (êîòîðûé â ñâîþ î÷åðåäü çàâèñèò îò ïðîïóñêíûõ ñïîñîáíîñòåé), ξk ñëómk÷àéíàÿ âåëè÷èíà, ðàñïðåäåëåíèå êîòîðîé íåèçâåñòî, Qk = {x ∈ R | 0 ≤ xe ≤ ce }. Âýòèõ îáîçíà÷åíèÿõ RandomizedArcBalancing ãåíåðèðóåò ïîñëåäîâàòåëüíîñòü îöåíîêãäåïî ïðàâèëóxk+1= PQ ky + − yk−x − ∆k k4αk.(10)Îñíîâíîé ðåçóëüòàò î ñõîäèìîñòè àëãîðèòìà ñôîðìóëèðîâàí â ñëåäóþùåé òåîðåìå:Ò å î ð å ì à 3.Ïóñòü xk ïîñëåäîâàòåëüíîñòü, ãåíåðèðóåìàÿ ïî ïðàâèëó13(10)ñëþáûì íà÷àëüíûì ïðèáëèæåíèåì x0 ∈ Q0 , Eξk2 ≤ σ 2 , âûáîð ∆k íå çàâèñèò îò ξ2k èξ2k+1 , ìíîæåñòâî ∪k Qk îãðàíè÷åíî è γ = supx∈Q,k ||Ax+wk ||, ||ck −ck+1 ||≤ β , λ2 (A) ìèíèìàëüíîå îòëè÷íîå îò íóëÿ ñîáñòâåííîå ÷èñëî ìàòðèöû A, q = 1 −α > 0, ν = β(1 +||B 0T B 00 ||λ2 (B 0T B 0 )), R = ν +σ√,2 αλ2 (A)2,òîãäà1.
Åñëè x∗k ëþáàÿ òî÷êà ìèíèìóìà fk íà Qk , òîE dist(xk − x∗k , Ω) ≤ q k/2 (||x0 − x∗0 || − R) + R.2. Åñëè x∗k ëþáàÿ òî÷êà ìèíèìóìà fk íà Qk , òîE{f (xk ) − f (x∗k )} ≤ γ(q k/2 (||x0 − x∗0 || − R) + R).3. Åñëè ïîìåõè â èçìåðåíèÿõ îòñóòñòâóþò, à ïðîïóñêíûå ñïîñîáíîñòè íå èçìåíÿþòñÿ (ò.å. R = 0, Qk = Qk+1 , fk ≡ fk+1 ) è xk ñõîäèòñÿ ê x∗ , òîE||xk − x∗ || ≤q k/4 pγ||x0 − x∗ ||√1− 4q ðàçäåëå 2.2.6 îïèñàíû ðåàëèçàöèè ìåòîäîâ â ìóëüòèàãåíòíûõ ñèñòåìàõ.Âòðåòüåé ãëàâå îïèñàíû ðåçóëüòàòû ýêñïåðèìåíòîâ, ïðîâåäåííûõ äëÿ ðàçðà-áîòàííûõ àëãîðèòìîâ. ðàçäåëå 3.1 ïðèâåäåíî îïèñàíèå ïàêåòà ïðèêëàäíûõ ïðîãðàìì, ðàçðàáîòàííîãî äëÿ ñèìóëÿöèè ïðîöåññà ðàñïðåäåëåíèÿ çàãðóçêè â ñåòè [10]. Ïàêåò ñîäåðæèòñëåäóþùèå îñíîâíûå êîìïîíåíòû•Ñèìóëÿòîð ìóëüòèàãåíòíîé (ðàñïðåäåëåííîé) âû÷èñëèòåëüíîé ñåòè.•Ýôôåêòèâíàÿ ðåàëèçàöèÿ ðåøåíèÿ çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå è îñíîâàííûé íà íåé ïðîòîêîë ðàñïðåäåëåíèÿ çàãðóçêè â ñåòè.•Ðåàëèçàöèÿ àäàïòèâíûõ ïðîòîêîëîâ ðàñïðåäåëåíèÿ çàãðóçêè.•Ðåàëèçàöèÿ ïðîòîêîëà ðàñïðåäåëåíèÿ çàãðóçêè íà îñíîâå ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ.Îñîáåííîñòè ðåàëèçàöèè ðåøåíèÿ çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå è å¼ ñðàâíåíèå ñ áèáëèîòåêîé paraF (https://www.microsoft.com/en-us/download/details.14aspx?id=52400)îïèñàíû â ðàçäåëå 3.2.
Ïî ðåçóëüòàòàì ýêñïåðèìåíòàëüíîãî ñðàâ-íåíèÿ áûëî âûÿâëåíî, ÷òî ñîáñòâåííàÿ ðåàëèçàöèÿ ïî ýôôåêòèâíîñòè íå óñòóïàåòýòîé áèáëèîòåêå, áîëåå òîãî óäàëîñü íåìíîãî óëó÷øèòü áèáëèîòåêó paraF, â ðåçóëüòàòå ÷åãî ýôôåêòèâíîñòü èñõîäíîãî àëãîðèòìà íà âñåõ òåñòàõ óñòóïàëà ëèáîìîäèôèöèðîâàííîé âåðñèè, ëèáî ñîáñòâåííîé ðåàëèçàöèè. ðàçäåëå 3.3 ïðèâåäåíû ðåçóëüòàòû ñèìóëèðîâàíèÿ ïðîöåññîâ ðàñïðåäåëåíèÿçàãðóçêè ñ èñïîëüçîâàíèåì ðàçðàáîòàííûõ ìåòîäîâ è ìåòîäà, îñíîâàííîãî íà ïðîòîêîëå ëîêàëüíîãî ãîëîñîâàíèÿ. Ïðèâîäÿòñÿ ðåçóëüòàòû ýêñïåðèìåíòîâ íà äâóõ òîïîëîãèÿõ ñåòè: êîëüöî ñî ñëó÷àéíûìè ñâÿçÿìè è çâåçäà.
 ðåçóëüòàòå ýêñïåðèìåíòîâ ìîæíî çàêëþ÷èòü, ÷òî áàëàíñèðîâàíèå çàãðóçêè, îñíîâàííîå íà àäàïòèâíîìðàíäîìèçèðîâàííîì àëãîðèòìå, îáëàäàåò ïîëîæèòåëüíûìè êà÷åñòâàìè ïðîòîêîëîâáàëàíñèðîâàíèÿ çàãðóçêè, îñíîâàííûõ íà óñðåäíåíèè (âðåìÿ ðàáîòû ñèñòåìû áëèçêî ê îïòèìàëüíîìó) è ïðîòîêîëå ëîêàëüíîãî ãîëîñîâàíèÿ (àäàïòèâíîñòü è ïðîñòàÿìóëüòèàãåíòíàÿ ðåàëèçàöèÿ).Âçàêëþ÷åíèèäèññåðòàöèè ïîäâåäåíû èòîãè ïðîâåäåííîãî è çàâåðøåííîãî âðàìêàõ ïîñòàâëåííûõ çàäà÷ èññëåäîâàíèÿ.Ïóáëèêàöèè àâòîðà ïî òåìå äèññåðòàöèè æóðíàëàõ èç ïåðå÷íÿ ðåöåíçèðóåìûõ íàó÷íûõ èçäàíèé, â êîòîðûõäîëæíû áûòü îïóáëèêîâàíû îñíîâíûå íàó÷íûå ðåçóëüòàòû äèññåðòàöèéíà ñîèñêàíèå ó÷åíîé ñòåïåíè êàíäèäàòà íàóê, íà ñîèñêàíèå ó÷åíîéñòåïåíè äîêòîðà íàóê, ñôîðìèðîâàííûé Ìèíîáðíàóêè ÐîññèèÀêòóàëüíîñòü çàäà÷è ìàêñèìàëüíîãî ïîòîêà âïðèìåíåíèè ê ñîâðåìåííûì âû÷èñëèòåëüíûì ñåòÿì // Êîìïüþòåðíûå[1] Ìàëüêîâñêèé Í.
Â.èíñòðóìåíòû â îáðàçîâàíèè. 2014. 4. C. 3-9.Ðàíäîìèçèðîâàííûé ðàñïðåäåëåííûé àäàïòèâíûé àëãîðèòì ðåøåíèÿ çàäà÷è î ìàêñèìàëüíîì ïîòîêå // Êîìïüþ-[2] Ìàëüêîâñêèé Í. Â.òåðíûå èíñòðóìåíòû îáðàçîâàíèÿ. 2016. 5. C. 46-61. èçäàíèÿõ, èíäåêñèðóåìûõ â ðåôåðàòèâíûõ áàçàõ Scopus è Web OfScienceSimultaneousperturbation stochastic approximation in decentralized load balancingproblem // IFAC-PapersOnLine. 2015. Vol.
48, 11, P. 936-941.[3] Amelina N., Erofeeva V., Granichin O., Malkovskii N.15Asymptotically Optimal Solution for TransportationProblem with Almost Arbitrary Capacities // IFAC-PapersOnLine. 2016.[4] Malkovskii N. Vol. 48. 11. P. 936-941.Optimal static network load balancing using parametricow approach // IFAC-PapersOnLine. 2015. Vol. 48. 11, P. 668-673.[5] Malkovskii N. äðóãèõ èçäàíèÿõ[6]Ãðàíè÷èí Î. Í., Ìàëüêîâñêèé Í. Â. Çàäà÷à ðàñïðåäåëåíèÿ ðåñóðñîâ â êîíòåêñòå ìóëüòèàãåíòíûõ ñèñòåì // Ñòîõàñòè÷åñêàÿ îïòèìèçàöèÿ â èíôîðìàòèêå. 2013. T. 9.
2. C. 41-53.[7]Ìàëüêîâñêèé Í. Â. Î ÷èñëå Ôèäëåðà è àñèìïòîòè÷åñêîé ñêîðîñòè ñõîäèìîñòèëàïëàñèàíîâûõ ñèñòåì // Ñòîõàñòè÷åñêàÿ îïòèìèçàöèÿ â èíôîðìàòèêå 2015. Ò. 11. 2. Ñ. 30-35.[8]Ìàëüêîâñêèé Í. Â.Ìîäåëü áàëàíñèðîâêè çàãðóçêè â âû÷èñëèòåëüíîé ñåòè ñèñïîëüçîâàíèåì çàäà÷è ïàðàìåòðè÷åñêîãî ïîòîêà // Ñòîõàñòè÷åñêàÿ îïòèìèçàöèÿ â èíôîðìàòèêå. 2014. Ò. 10. 1. Ñ. 39-62.[9]Àìåëèí Ê.
Ñ., Ãðàíè÷èí Î. Í., Ìàëüêîâñêèé Í. Â.Ðàñïðåäåëåíèå ðåñóðñîââ êîíòåêñòå ìóëüòèàãåíòíûõ ñèñòåì // Ñáîðíèê òðóäîâ 12 âñåðîññèéñêîãî ñîâåùàíèÿ ïî ïðîáëåìàì óïðàâëåíèÿ ÂÑÏÓ-2014. 2014. C. 9003-9013.[10] Ñèñòåìà ìîäåëèðîâàíèÿ ïîòîêâûõ ïðîöåññîâ â âû÷èñëèòåëüíîé ñåòè [Ýëåêòðîííûé ðåñóðñ], URL: https://github.com/Malkovsky/load-balancing16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
