Диссертация (Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах), страница 12
Описание файла
Файл "Диссертация" внутри архива находится в папке "Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах". PDF-файл из архива "Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст 12 страницы из PDF
Êàê óæåáûëî ñêàçàíî â ãëàâå 1, ýôôåêòèâíûå ðåàëèçàöèè çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå îñíîâàíû íà ýôôåêòèâíîé ðåàëèçàöèè çàäà÷è î ìàêñèìàëüíîì ïîòîêå. Ñ÷èòàåòñÿ, ÷òî íàèáîëåå ýôôåêòèâíàÿ ðåàëèçàöèÿ îïèñàíàâ [56] è äîñòóïíà íà [35] (Ãîëüäáåðã è ×åðêàññêè). Âàæíî îòìåòèòü, ÷òîòåîðåòè÷åñêàÿ ñëîæíîñòü çàäà÷è áûëà óëó÷øåíà â 2013ã. â ðàáîòå Ìàäðè [84]. ïàêåòå èñïîëüçóåòñÿ ñâîÿ ðåàëèçàöèÿ çàäà÷è î ìàêñèìàëüíîì ïîòîêå è çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå, èñïîëüçóþùóþ àíàëîãè÷íûåýâðèñòèêè äëÿ ñõåìû push-relabel (Max height, Global relabeling, Gap).Òàêæå, â áèáëèîòåêå paraF áûë âûÿâëåí íåäî÷åò, êîòîðûé íåçíà÷èòåëüíî çàìåäëÿë ðàáîòó àëãîðèòìà â íåêîòîðûõ ñëó÷àÿõ.Äëÿ ñðàâíèòåëüíîãî àíàëèçà èñïîëüçîâàëèñü ñòàíäàðòíûå òîïîëîãèèñåòåé: 2-D ðåøåòêà, çâåçäà, îðèåíòèðîâàííîå / íåîðèåíòèðîâàííîå êîëüöî, îðèåíòèðîâàííûé / íåîðèåíòèðîâàííûé ïóòü, îðèåíòèðîâàííîå êîëüöî ñî ñëó÷àéíûìè ñâÿçÿìè (èñõîäÿùàÿ ñòåïåíü êàæäîé âåðøèíû ðàâíà3), êîðíåâîå äåðåâî (ñòðóêòóðíîå îïèñàíèå íà ðèñ.
3.1). Âî âñåõ ñëó÷àÿõãðàô ñîñòîÿë èç 100000 âåðøèí (100489 äëÿ 2-D ðåøåòêè). Òåñòèðîâàëèñü ñîáñòâåííàÿ ðåàëèçàöèÿ, áèáëèîòåêà paraF è å¼ ìîäèôèöèðîâàííàÿâåðñèÿ. Ñðåäíèå âðåìåíà ðàáîòû (â ñåêóíäàõ) óêàçàíû â òàáëèöå 3.1. Èçýòîé òàáëèöû âèäíî, ÷òî ñîáñòâåííàÿ ðåàëèçàöèÿ èìååò ñõîæóþ ïðîèçâîäèòåëüíîñòü, ìîäèôèöèðîâàííàÿ âåðñèÿ paraF âî âñåõ òîïîëîãèÿõ êðîìå çâåçäû âûèãðûâàåò ó îðèãèíàëà, à îðèãèíàëüíàÿ âåðñèÿ paraf õîòü èíåçíà÷èòåëüíî, íî ïðîèãðûâàåò ìîäèôèöèðîâàííîé âåðñèè èëè ñîáñòâåííîé ðåàëèçàöèè âî âñåõ òîïîëîãèÿõ.3.3Òåñòèðîâàíèå àëãîðèòìîâáàëàíñèðîâàíèÿ çàãðóçêè ýòîì ðàçäåëå îïèñàíû ðåçóëüòàòû òåñòèðîâàíèÿ àëãîðèòìîâ ðàçðàáîòàííûõ àëãîðèòìîâ ðàñïðåäåëåíèÿ çàãðóçêè, à òàêæå àëãîðèòìîâ ðàñ85(b) Êîðíåâîå äåðåâî(a) 2D ðåøåòêà(c) Êîëüöî ñ äâóìÿ ñëó÷àéíûìè äóãàìè(d) Çâåçäà(e) Íåîðèåíòèðîâàííûé (f) Îðèåíòèðîâàííûéïóòüïóòü(g) Íåîðèåíòèðîâàííîå (h) ÎðèåíòèðîâàííîåêîëüöîêîëüöîÐèñ.
3.1: Òîïîëîãèè ñåòè, èñïîëüçóåìûå äëÿ òåñòèðîâàíèÿ86ÐåàëèçàöèÿparaFìîä. paraFÑâîÿ ðåàë.paraFìîä. paraFÑâîÿ ðåàë.2-D ðåø.0.7326600.6818001.749560çâåçäà0.4887000.5036700.256040îð. ïóòü îð. êîëüöî êîëüöî+2 äóãè0.648990 0.6482103.8151600.629410 0.6148003.4989200.676780 0.6379803.088300äåðåâî íåîð. ïóòü íåîð. êîëüöî0.673630 1.0105400.9838800.662090 0.9598600.9282500.202470 1.3198501.214020Òàáëèöà 3.1: Ñðåäíåå âðåìÿ ðàáîòû àëãîðèòìîâ íà ñòàíäàðòíûõ òîïîëîãèÿõ ñåòè.ïðåäåëåíèÿ íà îñíîâå ïðîòîêîëîâ êîíñåíñóñà. Àëãîðèòìû ðàñïðåäåëåíèÿçàãðóçêè, îñíîâàííûå íà êîíñåíñóñå [5, 6] íå ó÷èòûâàþò îãðàíè÷åíèÿ íàïðîïóñêíûå ñïîñîáíîñòè êàíàëîâ ñâÿçè. Òåì íå ìåíåå, ïðîòîêîë ìîæíîëåãêî àäàïòèðîâàòü ñëåäóþùèì îáðàçîì:xi (t + 1) = xi (t) −ãäånXj=1ϕij (aij (xj (t) − xi (t))) +nXj=1ϕji (aji (xi (t) − xj (t))), cij , x > cij ,x, 0 ≤ x ≤ cij ,ϕij (x) =0, x < 0.Íà Ðèñóíêàõ 3.2 è 3.3 èçîáðàæåíû ðåçóëüòàòû ñèìóëÿöèè íà òîïîëîãèÿõçâåçäà è êîëüöî ñî ñëó÷àéíûìè ñâÿçÿìè ñîîòâåòñòâåííî.
Äëÿ ñèìóëÿöèèáûë âûáðàí îäèí è òîò æå ãðàô ñ îäíèìè è òåìè æå âõîäíûìè äàííûìèâ êàæäîì ñëó÷àå (ïàðàìåòðû êàæäîé îòäåëüíîé çàäà÷è ãåíåðèðîâàëèñüíåçàâèñèìî â êàæäîì òåñòå), íà ãðàôèêàõ èçîáðàæåíî ñðåäíåå êîëè÷åñòâî âûïîëíåííûõ çàäàíèé ê ñîîòâåòñòâóþùåìó ìîìåíòó âðåìåíè.Íåèçìåííûìè âõîäíûìè äàííûìè ÿâëÿþòñÿ:• Ãðàô âçàèìîäåéñòâèÿ.• Ïðîèçâîäèòåëüíîñòè âû÷èñëèòåëüíûõ óçëîâ.• Íà÷àëüíàÿ çàãðóçêà (êîë-âî çàäàíèé) êàæäîãî óçëà.• Ïðîïóñêíûå ñïîñîáíîñòè êàíàëîâ ñâÿçè.Èçìåíÿåìûìè âõîäíûìè äàííûìè ÿâëÿþòñÿ:87340 · 104255 · 104170 · 10485 · 10424487296Ðèñ.
3.2: Ãðàôèê êîëè÷åñòâà âûïîëíåííûõ çàäàíèé â ñðåäíåì ïðè ñèìóëÿöèè íà çâåçäå. Ñèíÿÿ êðèâàÿ ñîîòâåòñòâóåò ñèìóëÿöèè ñ èñïîëüçîâàíèåì ïàðàìåòðè÷åñêîãî ïîòîêà, çåëåíàÿ ñ èñïîëüçîâàíèåì ïðîòîêîëàëîêàëüíîãî ãîëîñîâàíèÿ, ãîëóáàÿ ñ èñïîëüçîâàíèåì ìóëüòèàãåíòíûõïîòîêîâûõ ìåòîäîâ.
Âåðòèêàëüíàÿ ïóíêòèðíàÿ ëèíèÿ èäåàëüíîå âðåìÿ.• Êîëè÷åñòâî âû÷èñëåíèé, íóæíîå äëÿ âûïîëíåíèÿ êàæäîãî îòäåëüíîãî çàäàíèÿ. Äëÿ êàæäîé çàäà÷è âûáèðàåòñÿ ñëó÷àéíîå öåëîå ÷èñëî ðàâíîìåðíî íà èíòåðâàëå [1, 2k − 1] (ïàðàìåòð k ñîãëàñîâàí ñïðîèçâîäèòåëüíîñòüþ óçëîâ).• Ðàçìåð êîíòåêñòà êàæäîãî îòäåëüíîãî çàäàíèÿ. Äëÿ êàæäîé çàäà÷è âûáèðàåòñÿ ñëó÷àéíîå öåëîå ÷èñëî ðàâíîìåðíî íà èíòåðâàëå[1, 2k − 1] (ïàðàìåòð k ñîãëàñîâàí ñ ïðîïóñêíîé ñïîñîáíîñòüþ êàíàëîâ ñâÿçè).Íà Ðèñóíêå 3.2 èçîáðàæåíû ðåçóëüòàòû ñèìóëÿöèè äëÿ çâåçäû èç 105 âåðøèí, 34·105 èçíà÷àëüíî ðàñïîëîæåíû â öåíòðå çâåçäû. Äðóãèìè ñëîâàìè,ýòà ñèòóàöèÿ ýêâèâàëåíòíà öåíòðàëèçîâàííîìó âàðèàíòó ðàñïðåäåëåíèÿçàäàíèé: âñå çàäàíèÿ ïîñòóïàþò íà îäèí óçåë, êîòîðûé ðàñïðåäåëÿåòçàäàíèÿ ïî ðàáî÷èì óçëàì. Äëÿ ýòîãî òåñòà ðåøåíèå çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå äàåò èäåàëüíîå âðåìÿ â 9 òàêòîâ (áåç ó÷åòà çàäåðæåê âêîììóíèêàöèè), ïðè ýòîì èç-çà äèñïåðñèè ñèìóëÿöèÿ â ñðåäíåì çàíèìàåò8825 · 10618 · 10612 · 1066 · 10667135202270Ðèñ.
3.3: Ãðàôèê êîëè÷åñòâà âûïîëíåííûõ çàäàíèé â ñðåäíåì ïðè ñèìóëÿöèè íà êîëüöå ñî ñëó÷àéíûìè ñâÿçÿìè. Ñèíÿÿ êðèâàÿ ñîîòâåòñòâóåò ñèìóëÿöèè ñ èñïîëüçîâàíèåì ïàðàìåòðè÷åñêîãî ïîòîêà, çåëåíàÿ ñèñïîëüçîâàíèåì ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ, ãîëóáàÿ ñ èñïîëüçîâàíèåì ìóëüòèàãåíòíûõ ïîòîêîâûõ ìåòîäîâ. Âåðòèêàëüíûé ïóíêòèð èäåàëüíîå âðåìÿ.22.0 òàêòà, à ïîäñ÷åò ïëàíà (ðåøåíèå çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå)çàíèìàåò 0.09 ñåêóíä. Ïðè èñïîëüçîâàíèè ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ ñèìóëÿöèÿ çàíèìàëà â ñðåäíåì 83.6 òàêòà, 6.7 ñåêóíä ïîòðà÷åíûíà ïðîìåæóòî÷íûå âû÷èñëåíèÿ.  îáîèõ ñëó÷àÿõ îòìå÷àåòñÿ ïëîõîå ïîâåäåíèå, êîãäà â ñèñòåìå îñòàåòñÿ ìàëî çàäàíèé (÷òî, â òîì ÷èñëå, ìîæåòáûòü ñâÿçàíî ñ îñîáåííîñòÿìè ðåàëèçàöèè), îäíàêî æå èç ãðàôèêà âèäíî,÷òî ó ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ ïðîèçâîäèòåëüíîñòü íà÷èíàåòïàäàòü ðàíüøå.
Ïðè èñïîëüçîâàíèè áàëàíñèðîâàíèÿ íà îñíîâå ìóëüòèàãåíòíîãî àäàïòèâíîãî ïîòîêîâîãî ìåòîäà ñðåäíåå âðåìÿ ñèìóëÿöèè ñîñòàâëÿëî 18 òàêòîâ, íà ïðîìåæóòî÷íûå âû÷èñëåíèÿ â ñðåäíåì óõîäèëî0.4 ñåêóíäû, íà ãðàôèêå òàêæå âèäíî, ÷òî ðåçóëüòàòû ñèìóëÿöèè ïðè èñïîëüçîâàíèè àäàïòèâíîãî ìóëüòèàãåííîãî ïîäõîäà è ïðè èñïîëüçîâàíèèçàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå ïî÷òè íå îòëè÷àþòñÿ, íî ïðè ýòîì çàñ÷åò àäàïòèâíîñòè ïîëó÷àåòñÿ áîëåå ýôôåêòèâíîå ëîêàëüíîå ïîâåäåíèå,÷òî è ïðèâîäèò ê áîëåå áûñòðîìó çàâåðøåíèþ âûïîëíåíèÿ çàäàíèé.Íà ðèñóíêå 3.3 èçîáðàæåíû ðåçóëüòàòû ñèìóëÿöèè äëÿ êîëüöà ñî ñëó89÷àéíûìè ñâÿçÿìè èç 105 âåðøèí, 25 · 106 çàäàíèé ðàñïðåäåëåíû ñëó÷àéíûì îáðàçîì ïî êîëüöó. Ðåøåíèå çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå äàåòèäåàëüíîå âðåìÿ â 249 òàêòîâ, ïðè ýòîì ñèìóëÿöèÿ â ñðåäíåì çàíèìàåò254.8 òàêòà, à ïîäñ÷åò ïëàíà (ðåøåíèå çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå)çàíèìàåò 1.39 ñåêóíä. Ïðè èñïîëüçîâàíèè ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ ñèìóëÿöèÿ çàíèìàåò â ñðåäíåì 255.1 òàêòà, 34.1 ñåêóíäû ïîòðà÷åíû íà ïðîìåæóòî÷íûå âû÷èñëåíèÿ.
Íà ýòîì ïðèìåðå ìîæíî íàáëþäàòüîáðàòíóþ êàðòèíó äëÿ ãðàôèêîâ: ïðîòîêîë ëîêàëüíîãî ãîëîñîâàíèÿ ïîêàçûâàåò ëó÷øóþ ïðîèçâîäèòåëüíîñòü â íà÷àëå ðàáîòû (ïðèìåðíî äî 200òàêòà), îäíàêî ïðè èñïîëüçîâàíèè ïàðàìåòðè÷åñêîãî ïîòîêà ñèìóëÿöèÿçàêàí÷èâàåòñÿ ðàíüøå. Ýòî ñâÿçàíî ñ òåì, ÷òî â ýòîì ïðèìåðå íàèáîëüøåå âðåìÿ óõîäèò íà âûïîëíåíèå íåáîëüøîãî îáúåì çàäàíèé íà ó÷àñòêåêîëüöà ñ ìàëîé ïðîïóñêíîé ñïîñîáíîñòüþ è ïðîèçâîäèòåëüíîñòüþ (ïðîùå ãîâîðÿ, ñëàáûì çâåíîì). Áàëàíñèðîâàíèå ñ èñïîëüçîâàíèåì àäàïòèâíîãî ìóëüòèàãåíòíîãî ïîòîêîâîãî ìåòîäà äàåò ñðåäíåå âðåìÿ ñèìóëÿöèèâ 251.5 òàêòà, â ñðåäíåì 26.7 ñåêóíä çàòðà÷åíû íà ïðîìåæóòî÷íûå âû÷èñëåíèÿ è ïðè ýòîì ïî êîëè÷åñòâó ðåøåííûõ çàäàíèé ïðîèñõîäèò ëèøüíåçíà÷èòåëüíîå îòñòàâàíèå îò ïðîòîêîëà êîíñåíñóñà, êîòîðûé íà ýòîìòåñòå ïîêàçûâàåò ëó÷øèé ðåçóëüòàò, ÷åì ïàðàìåòðè÷åñêèé ïîòîê.Òåñòû òàêæå ïðîâîäèëèñü è äëÿ äðóãèõ òîïîëîãèé, îäíàêî íà ýòèõäâóõ ïðèìåðàõ ÷åòêî âèäíà ðàçíèöà ìåæäó ïîâåäåíèåì ðàçëè÷íûõ àëãîðèòìîâ.
Èç ïðîâåäåííûõ ýêñïåðèìåíòîâ ìîæíî çàêëþ÷èòü, ÷òî ðàçðàáîòàííûå àäàïòèâíûå ìóëüòèàãåíòíûå ïîòîêîâûå ìåòîäû îáëàäàþò ïîëåçíûìè ñâîéñòâàìè êàê è ìåòîäà, îñíîâàííîãî íà çàäà÷å î ïàðàìåòðè÷åñêîì ïîòîêå, òàê è ïðîòîêîëîâ êîíñåíñóñà.90Çàêëþ÷åíèå äèññåðòàöèîííîé ðàáîòå áûëè ïîëó÷åíû ñëåäóþùèå ðåçóëüòàòû:1.
Ðàçðàáîòàíû ìåòîäû ðåøåíèÿ çàäà÷ áàëàíñèðîâàíèÿ çàãðóçêè ââû÷èñëèòåëüíîé ñåòè è ìàðøðóòèçàöèè ïàêåòîâ äàííûõ â çàäà÷åñáîðà èíôîðìàöèè ãðóïïîé ÁÏËÀ íà îñíîâå ðåøåíèÿ ìàòåìàòè÷åñêèõ çàäà÷ îïòèìèçàöèè ïîòîêîâîãî òèïà.2. Ðàçðàáîòàíû äâà ìåòîäà ðåøåíèÿ ðàññìàòðèâàåìûõ ïîòîêîâûõ çàäà÷ â ñëó÷àå íåîïðåäåëåííîñòåé è èçìåíÿþùèõñÿ âî âðåìåíè ïàðàìåòðîâ îêðóæàþùåé ñðåäû: íåàäàïòèâíûé íà îñíîâå óñðåäíåíèÿè àäàïòèâíûé íà îñíîâå ïðèìåíåíèÿ ðàíäîìèçèðîâàííîé ñòîõàñòè÷åñêîé àïïðîêñèìàöèè.3. Äëÿ íåàäàïòèâíîãî ìåòîäà äîêàçàíà àñèìïòîòè÷åñêàÿ îïòèìàëüíîñòü ïîëó÷àåìîãî ïðèáëèæåííîãî ðåøåíèÿ, äëÿ àäàïòèâíîãî ìåòîäà ïîëó÷åíû ýôôåêòèâíûå îöåíêè ñêîðîñòè ñõîäèìîñòè ê îïòèìàëüíîìó ðåøåíèþ.4.
