Диссертация (1150593), страница 10
Текст из файла (страница 10)
Îäíàêî âåëè÷èíà îïòèìàëüíîãî ðàçìåðà øàãà óïðàâëÿþùåãî ïðîòîêîëà äëÿ ñèñòåìû,ðàáîòàþùåé â ðàçëè÷íûõ óñëîâèÿõ, áóäåò ðàçëè÷íîé, â ñâÿçè ñ ÷åì âñòàåò çàäà÷à âûáîðà îïòèìàëüíîé âåëè÷èíû ðàçìåðà øàãà äëÿ ïîâûøåíèÿïðîèçâîäèòåëüíîñòè ñèñòåìû. Îöåíèì ýôôåêòèâíîñòü äîñòèæåíèÿ êîíñåíñóñà â ñèñòåìå, ôóíêöèîíèðóþùåé ïî óïðàâëÿþùåìó ïðîòîêîëó, çàâðåìåííîé èíòåðâàë T ñ ïîìîùüþ ôóíêöèîíàëà(3.1)F(γ) = Eãäå F̄ (γ, X0,l , wl ) =1TTZ0L1XF̄ (γ, X0,l , wl ),F (γ, X0,l , wl ) ≈Ll=1PT? 2− Xt,l|| . X0,l îáîçíà÷àåò âåêòîð íà÷àëüíûõ ñîñòîÿíèé àãåíòîâ, Xt âåêòîð ñîñòîÿíèé àãåíòîâ â ìîìåíò âðåìåíè t, Xt? âåêòîð, ñîñòîÿùèé èç îäèíàêîâûõ ýëåìåíòîâ ðàâíûõ ñðåäíåìóçíà÷åíèþ çàãðóçêè àãåíòîâ ïî âñåé ñèñòåìå â ìîìåíò âðåìåíè t, wl îáîçíà÷àåò ïîìåõè.
Çàìåòèì, ÷òî F îäíîâðåìåííî õàðàêòåðèçóåò êàê ñêîðîñòü ñõîäèìîñòè, òàê è ñòåïåíü ñõîäèìîñòè óñðåäíåííîå îòêëîíåíèåñîñòîÿíèé àãåíòîâ â ñèñòåìå îò êîíñåíñóñíîãî çíà÷åíèÿ.Íà Ðèñ. 3.4 è Ðèñ. 3.5 ïðåäñòàâëåíû ãðàôèêè çàâèñèìîñòè F îò γ ,t=1 ||Xt,l68600500400F300200100000.10.2γ0.30.4Ðèñ. 3.4: Çàâèñèìîñòü F îò γ äëÿ òîïîëîãèè ¾äâîéíîå êîëüöî¿.12001000800F600400200000.10.2γ0.30.4Ðèñ. 3.5: Çàâèñèìîñòü F îò γ äëÿ òîïîëîãèè ¾ïîëíûé ãðàô¿.69700600500F̄400300200100000.10.2γ0.30.4Ðèñ.
3.6: Çàâèñèìîñòü F̄ îò γ äëÿ òîïîëîãèè ¾äâîéíîå êîëüöî¿.ïîëó÷åííûå óñðåäíåíèåì ãðàôèêîâ, ïðèâåäåííûõ íà Ðèñ. 3.6 è 3.7 ñîîòâåòñòâåííî. Ãðàôèêè íà Ðèñ. 3.4 è Ðèñ. 3.6 õàðàêòåðèçóþò çàâèñèìîñòüF îò γ äëÿ òîïîëîãèè íåîðèåíòèðîâàííîå ¾äâîéíîå êîëüöî¿, ïîëó÷åííîéñîåäèíåíèåì êàæäîãî óçëà â òîïîëîãèè ¾êîëüöî¿ ñî ñâîèìè ñîñåäÿìèâòîðîãî ïîðÿäêà.Ãðàôèêè íà Ðèñ. 3.5 è Ðèñ. 3.7 õàðàêòåðèçóþò çàâèñèìîñòü F îò γ äëÿòîïîëîãèè ñèñòåìû, ãðàô ñâÿçåé êîòîðîé ÿâëÿåòñÿ ïîëíûì ãðàôîì.
Âèäãðàôèêîâ, â ÷àñòíîñòè íàëè÷èå âûðàæåííîé îáëàñòè ìèíèìóìà, ïðåäïîëàãàåò ýôôåêòèâíîå èñïîëüçîâàíèå ïîèñêîâîãî àëãîðèòìà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè ñ ðàíäîìèçàöèåé íà âõîäå äëÿ ïîèñêà îïòèìàëüíîéâåëè÷èíû ðàçìåðà øàãà óïðàâëÿþùåãî ïðîòîêîëà.70140012001000F̄800600400200000.10.2γ0.30.4Ðèñ. 3.7: Çàâèñèìîñòü F̄ îò γ äëÿ òîïîëîãèè ¾ïîëíûé ãðàô¿.3.4Ïîèñêîâûé àëãîðèòì ñòîõàñòè÷åñêîéàïïðîêñèìàöèè ñ ðàíäîìèçàöèåé íàâõîäå äëÿ àäàïòàöèè ðàçìåðà øàãàïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿÂûøå áûëè ïîëó÷åíû ôîðìóëû äëÿ ðàñ÷åòà îïòèìàëüíîé âåëè÷èíûøàãà ïðîòîêîëà ïåðåðàñïðåäåëåíèÿ çàäàíèé. Äëÿ âû÷èñëåíèÿ ñ èõ ïîìîùüþ îïòèìàëüíîé âåëè÷èíû øàãà íåîáõîäèìî çíàòü òàêèå ïàðàìåòðûôóíêöèîíèðîâàíèÿ ñèñòåìû, êàê äèñïåðñèÿ ïîìåõ èëè ñðåäíÿÿ ñëîæíîñòü ïðèõîäÿùèõ â ñèñòåìó çàäàíèé.
Íà ïðàêòèêå òàêèå ïàðàìåòðûôóíêöèîíèðîâàíèÿ ñèñòåìû çà÷àñòóþ íåèçâåñòíû è, áîëåå òîãî, ìîãóòìåíÿòüñÿ ñî âðåìåíåì.  òàêîé ñèòóàöèè àêòóàëüíîé ñòàíîâèòñÿ çàäà÷à àäàïòèâíîãî âûáîðà ðàçìåðà øàãà äëÿ àëãîðèòìà ïåðåðàñïðåäåëåíèÿçàäàíèé.  ñëó÷àå, êîãäà ñêîðîñòü (âðåìÿ) ñõîäèìîñòè ïðåäñòàâëÿåò ñîáîé âûïóêëóþ ôóíêöèþ îò øàãà àëãîðèòìà, âûáîð îïòèìàëüíîãî øàãàñâîäèòñÿ ê çàäà÷å ãðàäèåíòíîãî ñïóñêà.  óñëîâèÿõ íåèçâåñòíîé öåëåâîé ôóíêöèè ïîäáîð ðàçìåðà øàãà ìîæåò ýôôåêòèâíî îñóùåñòâëÿòüñÿ ñïîìîùüþ àëãîðèòìà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè.Ðàçâèòèå ïñåâäîãðàäèåíòíûõ àëãîðèòìîâ ñòîõàñòè÷åñêîé àïïðîêñè71ìàöèè ðàññìîòðåíî â [28]. Àëãîðèòì ñòîõàñòè÷åñêîé àïïðîêñèìàöèè (ÑÀ)áûë ïðåäëîæåí Ðîááèíñîì è Ìîíðî â 1951 ã.
[103], â 1952 â ñòàòüå Êèôåðà è Âîëüôîâèöà îí ïîëó÷èë ðàçâèòèå äëÿ ðåøåíèÿ çàäà÷ îïòèìèçàöèè [89].  1954 ã. Áëþì ðàñïðîñòðàíèë àëãîðèòì ÑÀ íà ìíîãîìåðíûéñëó÷àé [69].  òðàäèöèîííîé ïðîöåäóðå ÑÀ, îñíîâàííîé íà àïïðîêñèìàöèè âåêòîð-ãðàäèåíòà öåëåâîé ôóíêöèè, èñïîëüçóåòñÿ ïî äâà èçìåðåíèÿäëÿ ïðèáëèæåíèÿ êàæäîé êîìïîíåíòû âåêòîð-ãðàäèåíòà (2d èçìåðåíèéâ ñëó÷àå ïðîñòðàíñòâà ðàçìåðíîñòè d).  êîíöå 80-õ íà÷àëå 90-õ ãã. XXâåêà Ãðàíè÷èíûì â [25,26] è Ïîëÿêîì ñ Öûáàêîâûì â [40,97] áûëè ïðåäëîæåíû ïîèñêîâûå àëãîðèòìû ñòîõàñòè÷åñêîé àïïðîêñèìàöèè ñ ðàíäîìèçàöèåé íà âõîäå, òðåáóþùèå íà êàæäîé èòåðàöèè âñåãî îäíî çíà÷åíèå(èëè äâà çíà÷åíèÿ) öåëåâîé ôóíêöèè.
Íàïðàâëåíèå ïðè ýòîì, ïîäîáíîàëãîðèòìó ñëó÷àéíîãî ïîèñêà [41], âûáèðàåòñÿ ñëó÷àéíî âäîëü ëèíèè,ïðîõîäÿùåé ÷åðåç îöåíêó îïòèìèçèðóåìîé ôóíêöèè íà ïðåäûäóùåì øàãå.  àíãëîÿçû÷íîé ëèòåðàòóðå ïîäîáíûå àëãîðèòìû, ïîëó÷èâøèå íàçâàíèå SPSA (simultaneous perturbation stochastic approximation) áûëèïðåäëîæåíû Ñïàëîì [106, 107]. àëãîðèòìàõ ÑÀ òðàäèöèîííî øàã àëãîðèòìà âûáèðàëñÿ óáûâàþùèì äî íóëÿ ñ òå÷åíèåì âðåìåíè. Ñåé÷àñ àêòèâíî èññëåäóþòñÿ âîçìîæíîñòè ïðèìåíåíèÿ àëãîðèòìîâ ÑÀ äëÿ îïòèìèçàöèè íåñòàöèîíàðíûõ ôóíêöèîíàëîâ êà÷åñòâà [28].
Ïðè ýòîì â çàäà÷àõ òðåêèíãà (îòñëåæèâàíèÿäðåéôà (èçìåíåíèé) ïàðàìåòðîâ) ÷àñòî èñïîëüçóþò íåóáûâàþùèé (ïîñòîÿííûé) ðàçìåð øàãà (äîñòàòî÷íî ìàëûé) [20, 70, 77, 78, 90, 110]. Ðàñïðåäåëåííûå àñèíõðîííûå àëãîðèòìû ÑÀ ðàññìàòðèâàëèñü â [109].  [17]àëãîðèòì ÑÀ ñ ïîñòîÿííûì ðàçìåðîì øàãà èñïîëüçîâàëñÿ â ìóëüòèàãåíòíûõ ñèñòåìàõ äëÿ áàëàíñèðîâêè çàãðóçêè óçëîâ âû÷èñëèòåëüíîé ñåòè âóñëîâèÿõ ñòàòèñòè÷åñêèõ ïîìåõ â íàáëþäåíèÿõ, ïåðåìåííîé òîïîëîãèèè çàäåðæåê.  [24, 27, 76, 80] ïîêàçàíû ïðèìåíåíèÿ àëãîðèòìà ÑÀ äëÿðåøåíèÿ çàäà÷ ïðè ïî÷òè ïðîèçâîëüíûõ ïîìåõàõ.Çàôèêñèðóåì âîçìîæíûé èíòåðâàë èçìåíåíèÿ ðàçìåðà øàãà ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ [γmin ; γmax ].
Íàïðèìåð, ìîæíî âçÿòü γmin =0,001indegmax Bav ,γmax =1indegmax Bav− γmin . Ðàññìîòðèì ïîñëåäîâàòåëüíûå âðå72ìåííûå èíòåðâàëû äëèíû T òàêòîâ ðàáîòû ñèñòåìû è ïåðåíóìåðóåì èõl = 1, 2, . . .. Äëÿ êàæäîãî èíòåðâàëà áóäåì âûáèðàòü ñâîé ðàçìåð øàãààëãîðèòìà è îöåíèâàòü ýôôåêòèâíîñòü ðàáîòû óïðàâëÿþùåãî àëãîðèòìàFl íà èíòåðâàëå l áóäåì ïî ôîðìóëå1Fl =T(3.2)lTXt=(l−1)T +1||Xt − Xt? ||2 .Òèïè÷íûé âèä ãðàôèêîâ íà Ðèñ. 3.6, 3.7 ïîäñêàçûâàåò èäåþ î âîçìîæíîì èñïîëüçîâàíèè ïîèñêîâîãî àëãîðèòìà ñòîõàñòè÷åñêîé àïïðîêñèìàöèè ñ ðàíäîìèçàöèåé íà âõîäå [28] äëÿ àäàïòàöèè ðàçìåðà øàãà ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ.Âûáåðåì ñëó÷àéíî íà÷àëüíîå çíà÷åíèå γ̂0 èç èíòåðâàëà [γmin ; γmax ].Áóäåì ïåðåñ÷èòûâàòü ðàçìåð øàãà ñëåäóþùèì îáðàçîì.
Ïî îêîí÷àíèèâðåìåííîãî èíòåðâàëà l, l = 1, 2, . . . äëèíû T îöåíèì ýôôåêòèâíîñòüðàáîòû Fl óïðàâëÿþùåãî ïðîòîêîëà â òå÷åíèå âðåìåííîãî èíòåðâàëà ïîôîðìóëå (3.2). Ðàçìåð øàãà áóäåì ïåðåñ÷èòûâàòü ïî îêîí÷àíèè âðåìåííîãî èíòåðâàëà l, l = 1, 2, . . ., ðàç â T òàêòîâ ðàáîòû ñèñòåìû.Àëãîðèòì àäàïòàöèè ðàçìåðà øàãà.1) Èíèöèàëèçàöèÿ. Óñòàíîâèì çíà÷åíèå ñ÷åò÷èêà èòåðàöèè àëãîðèòìà ïåðåñ÷åòà îöåíêè ðàçìåðà øàãà l = 0. Óñòàíîâèì ñ÷åò÷èê òàêòîâ â ñèñòåìå t = 0.
Îïðåäåëèì äîïóñòèìûé èíòåðâàë äëÿ ðàçìåðàøàãà [γmin ; γmax ]. Âûáåðåì èç èíòåðâàëà íà÷àëüíîå çíà÷åíèå ðàçìåðà øàãà γ0 è óñòàíîâèì îöåíêó ðàçìåðà øàãà γ̂l = γ0 . Çàäàäèìðàçìåð âðåìåííîãî èíòåðâàëà T (÷èñëî òàêòîâ, ñîâåðøàåìûõ ñèñòåìîé çà âûáðàííûé ïðîìåæóòîê âðåìåíè). Âûáåðåì çíà÷åíèÿ ïàðàìåòðîâ α è β . Óñòàíîâèì íà÷àëüíóþ çàãðóçêó óçëîâ âñåé ñèñòåìûX0 = [xi0 ]ni=1 .2) Èòåðàöèÿ àëãîðèòìà âûáîðà ðàçìåðà øàãà l → l + 1. Óñòàíîâèìl := l + 1.3) Âûáîð ðàçìåðà øàãà äëÿ íå÷åòíîãî âðåìåííîãî èíòåðâàëà. Óñòà73íîâèì γ2l−1 = γ2l−2 .4) Çàïóñê ñèñòåìû ñ âûáðàííûì ïàðàìåòðîì γ .4.1) Èòåðàöèÿ ðàáîòû ñèñòåìû t → t + 1. Óñòàíîâèì t := t + 1.4.2) Âûõîä èç öèêëà ðàáîòû ñèñòåìû.
Åñëè t > (2l − 1)T , ïåðåéòè êïóíêòó 5.4.3) Ðàáîòà ñèñòåìû.à) Ïîñòóïëåíèå çàäàíèé â ñèñòåìó íà èñïîëíåíèå. Íîâûå çàäàíèÿ Zt = [zti ]ni=1 ïîñòóïàþò â ñèñòåìó íà âûáðàííûå ñëó÷àéíîâû÷èñëèòåëüíûå óçëûXt := Xt + Zt .á) Âûïîëíåíèå çàäàíèé.
Âû÷èñëèòåëüíûå óçëû â ñèñòåìå âûáèðàþò çàäàíèÿ èç ñâîèõ î÷åðåäåé è, â ñîîòâåòñòâèè ñ ïðîèçâîäèòåëüíîñòÿìè Rt = [rti ]ni=1 , âûïîëíÿþò èõXt := Xt − Rt .â) Îáìåí èíôîðìàöèåé î çàãðóçêå. Êàæäûé óçåë i ïîñûëàåò ñâîèì ñîñåäÿì çíà÷åíèå ñâîåé çàãðóçêè xit , ïîëó÷àåò çàøóìëåíi,jíóþ èíôîðìàöèþ î ñîñòîÿíèÿõ ñâîèõ ñîñåäåé yt , j ∈ Nti .ã) Íàõîæäåíèå êîëè÷åñòâà çàäàíèé äëÿ ïåðåñûëêè. Íà îñíîâàíèè ïîëó÷åííîé èíôîðìàöèè î çàãðóçêå ñâîèõ ñîñåäåé êàæäûé óçåë âû÷èñëÿåò êîëè÷åñòâî çàäàíèé äëÿ ïåðåñûëêè ñâîèì ñîñåäÿì ñîãëàñíî ïðîòîêîëó ëîêàëüíîãî ãîëîñîâàíèÿ (1.4)Ut = [uit ]ni=1 .ä) Ïåðåñûëêà çàäàíèé. Óçëû â ñèñòåìå îáìåíèâàþòñÿ çàäàíèÿìèñî ñâîèìè ñîñåäÿìè â êîëè÷åñòâå, âû÷èñëåííîì íà ïðåäûäóùåì øàãåXt := Xt + Ut . Ïåðåéòè ê ïóíêòó 4.1.5) Ñáîð èíôîðìàöèè î çàãðóçêå.
Ñîáåðåì èíôîðìàöèþ î çàãðóçêå àãåíòîâ â ñèñòåìå Xt .746) Ðàñ÷åò ýìïèðè÷åñêîãî ôóíêöèîíàëà êà÷åñòâà. Âû÷èñëèì ïî ôîðìóëå (3.2) çíà÷åíèå ýìïèðè÷åñêîãî ôóíêöèîíàëà êà÷åñòâà F2l−1 , ïîêàçûâàþùåãî ýôôåêòèâíîñòü ðàáîòû ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ (1.4) ñ ðàçìåðîì øàãà γ .7) Ãåíåðèðîâàíèå çíà÷åíèÿ ∆l . Ñãåíåðèðóåì çíà÷åíèå áåðíóëëèåâñêîéñëó÷àéíîé âåëè÷èíû ∆l , ïðèíèìàþùåé çíà÷åíèÿ ±1 ñ âåðîÿòíî-ñòüþ 1/2.8) Ïåðåñ÷åò îöåíêè ðàçìåðà øàãà äëÿ èñïîëüçîâàíèÿ íà 2l-ì èíòåð-âàëå. Óñòàíîâèì îöåíêó ðàçìåðà øàãà ñ ó÷åòîì äîïóñòèìûõ çíà÷åíèé ðàçìåðà øàãà [γmin ; γmax ]:(3.3)γ̂2l = P r[γmin ;γmax ] (γ̂2l−1 + ∆l β) ,ãäå P r[γmin ;γmax ] ïðîåêòèðîâàíèå íà èíòåðâàë [γmin ; γmax ]. Óñòàíîâèì íà âñåõ óçëàõ â ñèñòåìå íîâûé ðàçìåð øàãà àëãîðèòìà ïåðåðàñïðåäåëåíèÿ çàäàíèé γ2l .9) Çàïóñê ñèñòåìû ñ âûáðàííûì ïàðàìåòðîì γ .9.1) Èòåðàöèÿ ðàáîòû ñèñòåìû t → t + 1.
Óñòàíîâèì t := t + 1.9.2) Âûõîä èç öèêëà ðàáîòû ñèñòåìû. Åñëè t > 2lT , ïåðåéòè ê ïóíêòó 10.9.3) Ðàáîòà ñèñòåìû.à) Ïîñòóïëåíèå çàäàíèé â ñèñòåìó íà èñïîëíåíèå. Íîâûå çàäàíèÿ Zt = [zti ]ni=1 ïîñòóïàþò â ñèñòåìó íà âûáðàííûå ñëó÷àéíîâû÷èñëèòåëüíûå óçëûXt := Xt + Zt .á) Âûïîëíåíèå çàäàíèé. Âû÷èñëèòåëüíûå óçëû â ñèñòåìå âûáèðàþò çàäàíèÿ èç ñâîèõ î÷åðåäåé è, â ñîîòâåòñòâèè ñ ïðîèçâîäèòåëüíîñòÿìè Rt = [rti ]ni=1 , âûïîëíÿþò èõXt := Xt − Rt .75â) Îáìåí èíôîðìàöèåé î çàãðóçêå. Êàæäûé óçåë i ïîñûëàåò ñâîèì ñîñåäÿì çíà÷åíèå ñâîåé çàãðóçêè xit , ïîëó÷àåò çàøóìëåíi,jíóþ èíôîðìàöèþ î ñîñòîÿíèÿõ ñâîèõ ñîñåäåé yt , j ∈ Nti .ã) Íàõîæäåíèå êîëè÷åñòâà çàäàíèé äëÿ ïåðåñûëêè. Íà îñíîâàíèè ïîëó÷åííîé èíôîðìàöèè î çàãðóçêå ñâîèõ ñîñåäåé êàæäûé óçåë âû÷èñëÿåò êîëè÷åñòâî çàäàíèé äëÿ ïåðåñûëêè ñâîèì ñîñåäÿì ñîãëàñíî ïðîòîêîëó ëîêàëüíîãî ãîëîñîâàíèÿ (1.4)Ut = [uit ]ni=1 .ä) Ïåðåñûëêà çàäàíèé.
Óçëû â ñèñòåìå îáìåíèâàþòñÿ çàäàíèÿìèñî ñâîèìè ñîñåäÿìè â êîëè÷åñòâå, âû÷èñëåííîì íà ïðåäûäóùåì øàãåXt := Xt + Ut . Ïåðåéòè ê ïóíêòó 4.1.10) Ñáîð èíôîðìàöèè î çàãðóçêå. Ñîáåðåì èíôîðìàöèþ î çàãðóçêå àãåíòîâ â ñèñòåìå Xt .11) Îöåíêà ýôôåêòèâíîñòè ðàáîòû àëãîðèòìà. Îöåíèì ýôôåêòèâíîñòü ðàáîòû ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ (1.4) ñ ðàçìåðîìøàãà, ðàâíûì γ̂2l , F2l , ïî ôîðìóëå (3.2).12) Ïåðåñ÷åò îöåíêè ðàçìåðà øàãà äëÿ èñïîëüçîâàíèÿ íà 2l + 1-ì èí-òåðâàëå. Ó÷èòûâàÿ îãðàíè÷åíèÿ íà ðàçìåð øàãà [γmin ; γmax ], ïîñòðîèì îöåíêó ðàçìåðà øàãà ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿäëÿ èñïîëüçîâàíèÿ íà èíòåðâàëå 2l + 1 ïî ôîðìóëå(3.4)γ̂2l+1F2l − F2l−1,= P r[γmin ;γmax ] γ̂2l − α∆lβãäå ∆l çíà÷åíèå áåðíóëëèåâñêîé ñëó÷àéíîé âåëè÷èíû, ñãåíåðèðîâàííîå íà øàãå 7, F2l−1 îöåíêà ðàáîòû àëãîðèòìà íà èíòåðâàëå2l − 1, ïîëó÷åííàÿ íà øàãå 6, F2l îöåíêà ðàáîòû àëãîðèòìà íàèíòåðâàëå 2l, ïîëó÷åííàÿ íà øàãå 10. Óñòàíîâèì íà âñåõ àãåíòàõâ ñèñòåìå íîâûé ðàçìåð øàãà γ̂2l+1 àëãîðèòìà ïåðåðàñïðåäåëåíèÿçàäàíèé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
