Автореферат (1150608), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Ðàçðàáîòàíû äâà ìåòîäà íàõîæäåíèÿ îïòèìàëüíîãî äèíàìè÷åñêîãî ïîòîêîâîãî ïðîöåññà: íåàäàïòèâíûé íà îñíîâå ðåøåíèÿ ñòàòè÷åñêîé ïîòîêîâîé çàäà÷èîïòèìèçàöèè è àäàïòèâíûé íà îñíîâå ïðèìåíåíèÿ ðàíäîìèçèðîâàííîé ñòîõàñòè÷åñêîé àïïðîêñèìàöèè. Ïðåäëîæåíû ñïîñîáû ìóëüòèàãåíòíîé ðåàëèçàöèèýòèõ ìåòîäîâ.3. Äîêàçàíà àñèìïòîòè÷åñêàÿ îïòèìàëüíîñòü ïåðâîãî ðàçðàáîòàííîãî ìåòîäà âñëó÷àå óñðåäíÿåìûõ ïðîïóñêíûõ ñïîñîáíîñòåé (òåîðåìû 1 è 2) è ïîëó÷åíûîöåíêè ñêîðîñòè ñõîäèìîñòè äëÿ âòîðîãî ìåòîäà (òåîðåìà 3).4. Ðàçðàáîòàíà ïðîãðàììíàÿ ðåàëèçàöèÿ ïðåäëîæåííûõ ìåòîäîâ.Îáîñíîâàííîñòü ïîëó÷åííûõ ðåçóëüòàòîâ îáåñïå÷èâàåòñÿ ìàòåìàòè÷åñêèìè òåîðåìàìè è ýêñïåðèìåíòàëüíûì ñðàâíåíèåì ìåòîäîâ, îïèñàííûõ â ýòîé ðàáîòå,ñ ìåòîäàìè, ïðèìåíÿåìûìè â ñõîæèõ çàäà÷àõ.Íàó÷íàÿ íîâèçíà.Âñå îñíîâíûå íàó÷íûå ðåçóëüòàòû äèññåðòàöèè ÿâëÿþòñÿíîâûìè.6Òåîðåòè÷åñêàÿ öåííîñòü è ïðàêòè÷åñêàÿ çíà÷èìîñòü.

Òåîðåòè÷åñêàÿ öåííîñòü ðàáîòû ñîñòîèò â îïèñàíèè è ðåøåíèè îáùåé çàäà÷è ñòîõàñòè÷åñêîãî ïîòîêîâîãî ïðîöåññà è ïîñòàíîâêó çàäà÷ áàëàíñèðîâàíèÿ íàãðóçêè â ñåòè è ñáîðà èíôîðìàöèè â ãðóïïå ìîáèëüíûõ ðîáîòîâ â âèäå çàäà÷ íàõîæäåíèÿ îïòèìàëüíîãîïîòîêîâîãî ïðîöåññà. Ïðåäëîæåíû äâà ìåòîäà ïîñòðîåíèÿ îïòèìàëüíîãî ïðîöåññà:ìåòîä íà îñíîâå óñðåäíåííîé ìîäåëè è àäàïòèâíûé ðàíäîìèçèðîâàííûé ìåòîä.Àïïðîáàöèÿ ðàáîòû.Ìàòåðèàëû äèññåðòàöèè äîêëàäûâàëèñü íà ñåìèíàðàõêàôåäðû ñèñòåìíîãî ïðîãðàììèðîâàíèÿ, êàôåäðû òåîðåòè÷åñêîé êèáåðíåòèêèÑÏáÃÓ, íà ðîññèéñêèõ è ìåæäóíàðîäíûõ êîíôåðåíöèÿõ ïî ïðîãðàììèðîâàíèþ,èíôîðìàòèêå, îïòèìèçàöèè è òåîðèè óïðàâëåíèÿ: âñåðîññèéñêîå ñîâåùàíèå ïî ïðîáëåìàì óïðàâëåíèÿ ÂÑÏÓ-2014, VI, VII, VIII òðàäèöèîííûõ âñåðîññèéñêèõ ìîëîäåæíûõ ëåòíèõ øêîëàõ Óïðàâëåíèå, èíôîðìàöèÿ è îïòèìèçàöèÿ (2014, 2015,2016), 1st Conference on Modelling, Identication and Control of Nonlinear Systems(MICNON, 2015), 12th IFAC International Workshop on Adaptation and Learning inControl and Signal Processing (ALCOSP, 2016).

Ïî ðåçóëüòàòàì ðàáîòû áûëà çàðåãèñòðèðîâàíà ïðîãðàììà äëÿ ðàçðàáîòêè è òåñòèðîâàíèÿ àëãîðèòìîâ ðàñïðåäåëåíèÿçàãðóçêè âû÷èñëèòåëüíîé ñåòè 2016661548 [10].Ïóáëèêàöèè.Îñíîâíûå ðåçóëüòàòû ðàáîòû îïóáëèêîâàíû â [1-9] èç íèõ äâåïóáëèêàöèè â æóðíàëàõ, âõîäÿùèõ â ïåðå÷åíü ðåöåíçèðóåìûõ íàó÷íûõ æóðíàëîâ,â êîòîðûõ äîæíû áûòü îïóáëèêîâàíû îñíîâíûå íàó÷íûå ðåçóëüòàòû äèññåðòàöèéíà ñîèñêàíèå ó÷åíîé ñòåïåíè êàíäèäàòà íàóê [1,2], òðè ïóáëèêàöèè â ïåðèîäè÷åñêèõ èçäàíèÿõ, âõîäÿùèõ â áàçó SCOPUS [3, 4, 5]. Ðàáîòû [3, 6, 9] íàïèñàíû â ñîàâòîðñòâå.

 [3] àâòîðó ïðèíàäëåæèò îïèñàíèå ñâÿçè ñïëåòåí, çàäà÷è êîíñåíñóñàèSimultaneous Perturbation Stochastic Approximation (SPSA)ìåòîäà.  [6,9] àâòîðóïðèíàäëåæèò îáùåå ìàòåìàòè÷åñêîå îïèñàíèå çàäà÷ ðàñïðåäåëåíèÿ ðåñóðñîâ.Ñòðóêòóðà è îáúåì äèññåðòàöèè.Äèññåðòàöèÿ ñîñòîèò èç ââåäåíèÿ, òðåõãëàâ, çàêëþ÷åíèÿ, ñïèñêà ëèòåðàòóðû, âêëþ÷àþùåãîìàåò103ñòðàíèöû, ñîäåðæèò12105èñòî÷íèêîâ.

Òåêñò çàíè-ðèñóíêîâ è îäíó òàáëèöó.Ñîäåðæàíèå ðàáîòûÂîââåäåíèèîáîñíîâûâàåòñÿ àêòóàëüíîñòü èññëåäîâàíèé, ïðîâîäèìûõ â ðàì-êàõ ýòîé äèññåðòàöèîííîé ðàáîòû, ïðèâîäèòñÿ îáçîð íàó÷íîé ëèòåðàòóðû ïî èçó÷à-7åìîé ïðîáëåìå, ôîðìóëèðóåòñÿ öåëü, íàó÷íàÿ íîâèçíà è ïðàêòè÷åñêàÿ çíà÷èìîñòüïðåäñòàâëÿåìîé ðàáîòû, ñòàâÿòñÿ çàäà÷è ðàáîòû.Âïåðâîé ãëàâåïðèâîäÿòñÿ îáùèå ñâåäåíèÿ î ïîòîêîâûõ çàäà÷àõ ëèíåéíîãîïðîãðàììèðîâàíèÿ: çàäà÷å î ìàêñèìàëüíîì ïîòîêå, çàäà÷å î ïàðàìåòðè÷åñêîì ïîòîêå; ñôîðìóëèðîâàíà îáùàÿ çàäà÷à îïòèìàëüíîãî ïîòîêîâîãî äèíàìè÷åñêîãî ïðîöåññà, ïîäðîáíî îïèñàíû èñïîëüçóåìûå àëãîðèòìû. ïóíêòå 1.1 ïðåäñòàâëåíà îáùàÿ ñïåöèôèêà ïîòîêîâûõ ïðîöåññîâ, îïèñàíî, êàêýòà ñïåöèôèêà èíòåðïðåòèðóåòñÿ â ðàçëè÷íûõ ïðàêòè÷åñêèõ ñèòóàöèÿõ, ïåðå÷èñëåíû îñíîâíûå ìàòåìàòè÷åñêèå ìîäåëè è çàäà÷è, ñõîæèå ñ òåìè, êîòîðûå ðàññìàòðèâàþòñÿ â äèññåðòàöèîííîé ðàáîòå.

 ïóíêòå 1.1.1 îïèñàíà îáùàÿ çàäà÷à íàõîæäåíèÿ îïòèìàëüíîãî ïðîöåññà (çàäà÷à áûñòðîäåéñòâèÿ). Îñíîâíàÿ ñòàòè÷åñêàÿ çàäà÷à, ðàññìàòðèâàåìàÿ â ðàáîòå èìååò âèäìèíèìèçèðîâàòüïðè óñëîâèèãäåX, Uτ,ẋ = Bu, x(0) = x− ; x(τ ) = x+ ,x(t) ∈ X, u(t) ∈ U, íåêîòîðûå âûïóêëûå ìíîæåñòâà,B(1) ëèíåéíûé îïåðàòîð (ìàòðèöà).Ýòó çàäà÷ó ìîæíî ñôîðìóëèðîâàòü ñëîâàìè ñëåäóþùèì îáðàçîì: çà êàêîå ìèíèìàëüíîå âðåìÿ ìîæíî ïåðåâåñòè ñîñòîÿíèå ñèñòåìû èçóïðàâëåíèÿBuïðè ýòîì îñòàâàÿñü â ìíîæåñòâåX?x−âx+ïîä âîçäåéñòâèåì êðàòêîì âèäå ïðåäñòàâëåíûïðèíöèï ìàêñèìóìà è ïðèíöèï äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, îáû÷íî ïðèìåíÿåìûå äëÿ àíàëèçà è íàõîæäåíèÿ îïòèìàëüíûõ ïðîöåññîâ.

Èç íåñêîëüêèõ ïðîñòûõñîîáðàæåíèé âèäíî, ÷òî îáà ïðèíöèïà íå äàþò ïîëåçíîé èíôîðìàöèè î çàäà÷å, òàêêàê îíà èìååò âûðîæäåííûé âèä. Âìåñòî ýòîãî ïðåäëàãàåòñÿ èñïîëüçîâàòü áîëååïðîñòîå ñîîáðàæåíèå: âñåãäà ìîæíî èñêàòü îïòèìàëüíûé ïðîöåññ â âèäå ïðÿìîéòðàåêòîðèè, ò. å. ñ ïîñòîÿííûì óïðàâëåíèåìu(t) ≡ ū, â ðåçóëüòàòå ÷åãî (1) ñâîäèò-ñÿ ê ðåøåíèþ îáû÷íîé çàäà÷è îïòèìèçàöèèìèíèìèçèðîâàòüτ,(ïðè óñëîâèè8τ Bu = x+ − x− ,u ∈ U,(2)èëè ê ðåøåíèþ ýêâèâàëåíòíîé åé çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿìàêñèìèçèðîâàòüλ,(ïðè óñëîâèèBu = λ(x+ − x− ),u ∈ U. ïóíêòå 1.1.2 îïèñàíà ñïåöèôèêà çàäà÷ íàõîæäåíèÿ îïòèìàëüíûõ ïîòîêîâûõ ïðîöåññîâ: ÌíîæåñòâîXÿâëÿåòñÿ ïîëîæèòåëüíûì îðòàíòîì (X= {x ∈ Rn | xi ≥0, 1 ≤ i ≤ n}), ìíîæåñòâî U ïðåäñòàâëÿåò îãðàíè÷åíèÿ íà ïðîïóñêíûå ñïîñîáíîñòèmè èìååò âèä U = {u ∈ R| 0 ≤ ui ≤ ci }, à B ìàòðèöà èíöèäåíòíîñòè ãðàôà, ò.å.åñëè G = hV, Ei, |V | = n, |E| = m, òî B ìàòðèöà ðàçìåðà n × m òàêàÿ, ÷òîe âûõîäèò èç i, 1,Bie =−1, e âõîäèò â i,0â îñòàëüíûõ ñëó÷àÿõ.Ñ ýòèìè ïðåäïîëîæåíèÿìè çàäà÷à (1) ïåðåïèñûâàåòñÿ â âèäåìèíèìèçèðîâàòüïðè óñëîâèèτ,ẋ = Bu, x(0) = x− ; x(τ ) = x+ ,x(t) ≥ 0, 0 ≤ u (t) ≤ c ,ee(3)à çàäà÷à (2) â âèäåìàêñèìèçèðîâàòüλ,(ïðè óñëîâèèBu = λ(x+ − x− ),0 ≤ ue ≤ ce .(4) ïóíêòå 1.2 ïîäðîáíî îïèñàíû çàäà÷à î ìàêñèìàëüíîì ïîòîêå, çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå è ýôôåêòèâíûå àëãîðèòìû ðåøåíèÿ ýòèõ çàäà÷. ïóíêòå 1.3 îïèñàíû äâå ïðàêòè÷åñêèå çàäà÷è ìóëüòèàãåíòíîãî ðàñïðåäåëåíèÿðåñóðñîâ: ðàñïðåäåëåíèå çàãðóçêè â ìóëüòèàãåíòíûõ ñèñòåìàõ è ñáîð èíôîðìàöèèâ ãðóïïàõ áåñïèëîòíûõ ëåòàòåëüíûõ àïïàðàòîâ (ÁÏËÀ).

Ñâåäåíèå ýòèõ çàäà÷ ê(3) è (6) ïðÿìîëèíåéíî. Çàäà÷à ðàñïðåäåëåíèÿ çàãðóçêè ñòàâèòñÿ â ñëåäóþùåì âè-9aaτp aabqτcvaτcbqsbτp btbvqvτcvτpvНачальнаяПередачазагрузказадач посетиÐèñ. 1:ВыполнениезадачÃðàô äëÿ çàäà÷è áàëàíñèðîâàíèÿ íàãðóçêèäå: èçíà÷àëüíî â ñåòè åñòü íåêîòîðûé íàáîð çàäà÷, êîòîðûé êàê-òî ðàñïðåäåëåí ïîóçëàì ñåòè. Çà êàêîå ìèíèìàëüíî âðåìÿ âîçìîæíî âûïîëíèòü âñå çàäà÷è (è êàê äîáèòüñÿ ýòîãî âðåìåíè)?  çàäà÷å ïðåäïîëàãàåòñÿ òîëüêî òî, ÷òî çàðàíåå èçâåñòíûëèøü ñðåäíèå çíà÷åíèÿ ñëîæíîñòè çàäà÷è (îáúåì âû÷èñëåíèé, íåîáõîäèìûé äëÿâûïîëíåíèå çàäà÷è) è å¼ êîíòåêñòà (èíôîðìàöèÿ, íåîáõîäèìàÿ äëÿ ïåðåäà÷è çàäà÷è äðóãîìó óçëó ñåòè).

 ýòèõ ïðåäïîëîæåíèÿõ ìîæíî ñ÷èòàòü, ÷òî âñå çàäà÷èîäèíàêîâû (â òîì ñìûñëå, ÷òî ðåàëüíûå çíà÷åíèÿ óêàçàííûõ âåëè÷èí ýòî ðåàëèçàöèÿ îäíîãî è òîãî æå ðàñïðåäåëåíèÿ), ÷òî ïîçâîëÿåò òðàêòîâàòü âûïîëíåíèåçàäà÷è êàê ïåðåäà÷ó ïî êàíàëó ñâÿçè íà íåêîòîðûé ôèêòèâíûé óçåë.  èòîãå çàäà÷àðàñïðåäåëåíèÿ çàãðóçêè ôîðìóëèðóåòñÿ íàïîäîáèå (3)ìèíèìèçèðîâàòüïðè óñëîâèèãäåqìåíè âåêòîð íà÷àëüíîé çàãðóçêè,t, piτ,ẋ = Bu − p̃, x(0) = q; x(τ ) = 0n ,x(t) ≥ 0,0 ≤ p̃i (t) ≤ pi ,0 ≤ uij (t) ≤ cij (t),p̃i (t)ïðîèçâîäèòåëüíîñòü óçëà(5)iâ ìîìåíò âðå- ìàêñèìàëüíàÿ ïðîèçâîäèòåëüíîñòü óçëà i. Ñâåäåíèå ê (3) ïðåäñòàâëÿåòñîáîé íåñëîæíóþ òåõíè÷åñêóþ ðàáîòó.

Ãðàô, íà êîòîðîì íóæíî íàéòè îïòèìàëüíûé ïîòîêîâûé ïðîöåññ ïîêàçàí íà ðèñóíêå 1. Çàäà÷à î ñáîðå èíôîðìàöèè â ãðóïïå10ÁÏËÀ òàêæå ñòàâèòñÿ äîâîëüíî ïðîñòî: èçíà÷àëüíî â ãðóïïå íà êàæäîì ÁÏËÀõðàíèòñÿ íåêîòîðàÿ èíôîðìàöèÿ, íåîáõîäèìî çà ìèíèìàëüíîå âðåìÿ ñîáðàòü âñþèíôîðìàöèþ íà îäíîì èç íèõ (èëè æå íà áàçîâîé ñòàíöèè). Ýòà çàäà÷à òàêæå áåçîñîáûõ óñèëèé ñâîäèòñÿ ê (6), îñíîâíîé äèíàìè÷åñêîé ñîñòàâëÿþùåé ýòîé çàäà÷èÿâëÿåòñÿ äâèæåíèå ÁÏËÀ â ïðîñòðàíñòâå, èç-çà ÷åãî îíè ìîãóò ïåðåäàâàòü èíôîðìàöèþ òîëüêî â îïðåäåëåííûå ïðîìåæóòêè âðåìåíè.Âîâòîðîé ãëàâå îïèñàíû äâà ìåòîäà ïîñòðîåíèÿ ïîòîêîâûõ ïðîöåññîâ.  ïóíê-òå 2.1 îïèñàí îáùèé ìåòîä óñðåäíåíèÿ: âìåñòî ñëîæíîé äèíàìè÷åñêîé çàäà÷è ðàññìàòðèâàåòñÿ ïðîñòàÿ ñòàòè÷åñêàÿ, ïîñëå ÷åãî ðåøåíèå àäàïòèðóåòñÿ ïîä äèíàìè÷åñêèé ñëó÷àé. Ñôîðìóëèðîâàíà è äîêàçàíà îñíîâíàÿ òåîðåìà îá àñèìïòîòè÷åñêîéýêâèâàëåíòíîñòè èñõîäíîé çàäà÷è è å¼ óñðåäíåííîãî âàðèàíòà.

Åñëè ïðåäïîëîæèòü, ÷òî â çàäà÷å (6) ìíîæåñòâîUèçìåíÿåòñÿ âî âðåìåíè, òî çàäà÷à ñòàíîâèòñÿíà ïîðÿäîê ñëîæíåå, íå ïîëó÷àåòñÿ ñâåñòè çàäà÷ó íàõîæäåíèÿ îïòèìàëüíîãî ïðîöåññà ê çàäà÷å ìàòåìàòè÷åñêîé îïòèìèçàöèè. Ðàññìàòðèâàåòñÿ îáîáùåíèå çàäà÷è(3), ó÷èòûâàþùåå çàïàçäûâàíèå è èçìåíåíèå ïàðàìåòðîâ ñèñòåìû ñî âðåìåíåì:ìèíèìèçèðîâàòüïðè óñëîâèèτ,ẋ = B(σ)u, x(0) = x− ; x(τ ) = x+ , x(t) ≥ 0n , 0 ≤ u (t) ≤ c (t).ijijce ∈ L1loc ([0; +∞)), σ = (σ1 , . . .

, σm )T , σi çàïàçäûâàíèåäóãå i, B(σ) îáîçíà÷àåò ñëåäóþùèé îïåðàòîð:ãäå[B(σ)u]i (t) =Xue (t − σe ) −e∈in(i)X(6)èëè âðåìÿ ïåðåõîäà ïîue (t).(7)e∈out(i) ðàçäåëå 2.1.1 ðàññìàòðèâàåòñÿ êëàññ ñëåäóþùèé êëàññ ôóíêöèéÎ ï ð å ä å ë å í è å 1.Ëîêàëüíî èíòåãðèðóåìàÿ ïî Ëåáåãó ôóíêöèÿ f ∈L1loc ([0; +∞)) íàçûâàåòñÿ óñðåäíÿåìîé, åñëè ñóùåñòâóåò ñëåäóþùèé ïðåäåë1avg(f ) = limτ →+∞ τZτf dµ < +∞.0Îñíîâíàÿ èäåÿ âñåé ãëàâû çàêëþ÷àåòñÿ â òîì, ÷òî åñëè ïðîïóñêíûå ñïîñîáíîñòè11â ñåòè èçìåíÿþòñÿ âî âðåìåíè êàê óñðåäíÿåìûå ôóíêöèè, òî ìîæíî ïîñòðîèòüáëèçêèé ê îïòèìàëüíîìó ïðîöåññ è ïîêàçàòü åãî àñèìïòîòè÷åñêóþ îïòèìàëüíîñòü.Äîêàçàíû äâå òåîðåìû î çàäà÷å (6) ñ óñðåäíÿåìûìè ïðîïóñêíûìè ñïîñîáíîñòÿìè.Îáîçíà÷èì ÷åðåçτ ∗ (x− , x+ , σ, c)îïòèìàëüíîå âðåìÿ (6) ñ âõîäíûìè ïàðàìåòðàìèx− , x+ , σ, c.Ò å î ð å ì à 1.

Ðàññìîòðèì (6) ñ ôèêñèðîâàííûìè óñðåäíÿåìûìè íåîòðèöàòåëüíûìè ôóíêöèÿìè ïðîïóñêíûõ ñïîñîáíîñòåé ce (t) è íåêîòîðûì íåîòðèöàòåëüíûìâåêòîðîì σ . Äëÿ ëþáîãî 0 < < 1 ñóùåñòâóåò T () > 0 òàêîå, ÷òî äëÿ ëþáûõx− , x+ âûïîëíÿåòñÿ∗−+τ (x , x , σ, c) ≤1+1−n−1τ ∗ (x− , x+ , 0m , avg(c)) + T ().Ò å î ð å ì à 2. Ðàññìîòðèì (6) ñ ôèêñèðîâàííûìè óñðåäíÿåìûìè íåîòðèöàòåëüíûìè ôóíêöèÿìè ïðîïóñêíûõ ñïîñîáíîñòåé ce (t), íåêîòîðûì íåîòðèöàòåëüíûì+ ∞∞âåêòîðîì σ è ïîñëåäîâàòåëüíîñòÿìè {x−k }k=1 , {xk }k=1 , äëÿ êîòîðûõ âûïîëíÿåòñÿ+lim τ ∗ (x−k , xk , σ, c) = +∞,k→∞òîãäà+τ ∗ (x−k , xk , σ, c)= 1.−+k→∞ τ ∗ (x , x , 0m , avg(c))kklimÒåîðåìà 2.1 äàåò ñïîñîá ïîñòðîåíèå ñóáîïòèìàëüíîãî ïðîöåññà â äèíàìè÷åñêîìñëó÷àå. Òåîðåìà 2.2 ïîêàçûâàåò àñèìïòîòè÷åñêóþ îïòèìàëüíîñòü ïðîöåññà, ïîñòðîåííîãî íà îñíîâå òåîðåìû 2.1.

Характеристики

Список файлов диссертации