2. 1-§. Taqsimlangan tizimlar arxitekturasi 1

2.2-§. Tarqalgan tizimlar uchun maxmin tipidagi masalalarni yechish algoritmlar

Taqsimlangan tizimlar - umumiy maqsadga erishish uchun bir-biri bilan aloqa qiladigan va muvofiqlashtiruvchi bir nechta o'zaro bog'langan kompyuterlardan tashkil topgan kompyuter tizimlari. Ushbu tizimlar odatda bulutli hisoblash, ma'lumotlar markazlari va sensorli tarmoqlar kabi turli xil ilovalarda qo'llaniladi. Taqsimlangan tizimlardagi muhim vazifalardan biri resurslarni samarali taqsimlash, aloqa xarajatlarini minimallashtirish va o'tkazish qobiliyatini oshirish orqali ularning ish faoliyatini optimallashtirishdir.
Maxmin tipidagi optimallashtirish muammolari taqsimlangan tizimlarda keng tarqalgan optimallashtirish masalalari sinfidir. Maqsad ma'lum bir domen bo'yicha funktsiyalar to'plamining minimal qiymatini maksimal darajada oshirish bo'lsa, bu muammolar paydo bo'ladi. Taqsimlangan tizimlardagi maxmin tipidagi muammolarga misol sifatida resurslarni taqsimlash kiradi, bunda maqsad har bir agentning adolatli ulushini olishini ta'minlagan holda bir nechta agentlar o'rtasida resurslarni taqsimlash va tarmoq oqimini optimallashtirish, bunda maqsad to'plamning minimal sig'imini maksimal darajada oshirishdir. tarmoqdagi havolalar.
Taqsimlangan tizimlarda maxmin tipidagi muammolarni hal qilish muammoning taqsimlangan tabiati va agentlar o'rtasida muvofiqlashtirish zarurati tufayli qiyin bo'lishi mumkin. Agentlar maqsad funktsiyasi haqida cheklangan ma'lumotlarga ega bo'lishi mumkin va ma'lumot almashish va o'z harakatlarini muvofiqlashtirish uchun bir-biri bilan muloqot qilishlari kerak bo'lishi mumkin. Shuning uchun taqsimlangan tizimlarda maxmin tipidagi muammolarni echish uchun samarali algoritmlarni loyihalash faol tadqiqot yo'nalishi hisoblanadi.
Shu nuqtai nazardan, taqsimlangan tizimlarda maxmin tipidagi muammolarni echish uchun turli xil algoritmlar taklif qilingan, jumladan, ko'paytiruvchilarning o'zgaruvchan yo'nalishi usuli (ADMM), taqsimlangan subgradient usuli va Frank-Vulf algoritmi. Bu algoritmlar taqsimlangan tizimlarda maxmin tipidagi masalalarni yechish uchun turli yondashuvlarni taqdim etadi va algoritmni tanlash aniq masala va taqsimlangan tizimning xususiyatlariga bog'liq.
Umuman olganda, taqsimlangan tizimlarda maxmin tipidagi muammolarni hal qilish ushbu tizimlarning ishlashini optimallashtirish uchun muhim vazifadir. Ushbu muammolarni hal qilish uchun samarali algoritmlarni ishlab chiqish turli xil ilovalarda taqsimlangan tizimlarni keng qo'llashni ta'minlash uchun muhim ahamiyatga ega.
Maxmin tipidagi optimallashtirish muammolari - bu ma'lum bir domen bo'yicha funktsiyalar to'plamining minimal qiymatini maksimallashtirish bo'lgan muammolar sinfidir. Ushbu muammolar ko'plab ilovalarda, jumladan, resurslarni taqsimlash, tarmoq oqimini optimallashtirish va o'yin nazariyasida paydo bo'ladi. Tarqalgan tizimda maxmin tipidagi muammolarni hal qilish muammoning taqsimlangan tabiati va agentlar o'rtasida muvofiqlashtirish zarurati tufayli qiyin bo'lishi mumkin. Bu erda taqsimlangan tizimlarda maxmin tipidagi muammolarni hal qilish uchun ishlatilishi mumkin bo'lgan uchta algoritm mavjud:
Ko'paytirgichlarning o'zgaruvchan yo'nalishi usuli (ADMM): ADMM taqsimlangan optimallashtirish muammolarini hal qilish uchun mashhur algoritmdir. U muammoni agentlar tomonidan mustaqil ravishda hal qilinishi mumkin bo'lgan kichik muammolarga ajratish orqali ishlaydi. Keyin agentlar o'zlarining echimlarini yangilash va cheklovlar to'plamini qondirishlarini ta'minlash uchun bir-biri bilan muloqot qilishadi. ADMM taqsimlangan tizimlarda maxmin tipidagi muammolarni hal qilishda samarali ekanligi ko'rsatildi, ayniqsa muammo qavariq bo'lsa va agentlar maqsad funktsiyasi haqida mahalliy ma'lumotlarga ega bo'lsa.
Tarqalgan subgradient usuli: taqsimlangan subgradient usuli taqsimlangan tizimlarda qavariq optimallashtirish masalalarini echish uchun oddiy algoritmdir. U har bir agentga mahalliy ma'lumotlardan foydalangan holda maqsad funksiyasining subgradientini hisoblashi va keyin subgradient va qadam o'lchamiga qarab o'z yechimini yangilash orqali ishlaydi. Agentlar o'zlarining yechimlari haqida ma'lumot almashish va ularning umumiy yechimga yaqinlashishini ta'minlash uchun bir-biri bilan muloqot qilishadi. Taqsimlangan subgradient usuli funksiyalar to‘plamining minimal qiymatini topish uchun subgradient hisobini o‘zgartirish orqali maxmin tipidagi muammolarni hal qilish uchun kengaytirilishi mumkin.
Frank-Vulf algoritmi: Frank-Vulf algoritmi qavariq optimallashtirish masalalarini hal qilish uchun gradientga asoslangan algoritmdir. Qavariq to'plamda chiziqli maqsad funktsiyasining minimalini iterativ ravishda topish va keyin qadam o'lchamiga qarab yechimni yangilash orqali ishlaydi. Frank-Vulf algoritmi chiziqli funktsiyalar to'plamining maksimalini topish uchun maqsad funktsiyasini o'zgartirish orqali maxmin tipidagi muammolarni hal qilish uchun moslashtirilishi mumkin. Algoritm taqsimlangan tizimda har bir agent mahalliy ma'lumotlarga asoslangan chiziqli funktsiyani hisoblashi va keyin chiziqli funktsiyalar to'plamining maksimalini topish uchun boshqa agentlar bilan bog'lanishi orqali amalga oshirilishi mumkin.
Ushbu algoritmlar taqsimlangan tizimlarda maxmin tipidagi muammolarni hal qilish uchun turli yondashuvlarni taqdim etadi. Algoritmni tanlash muayyan muammoga va tarqatilgan tizimning xususiyatlariga, masalan, aloqa cheklovlari va agentlar uchun mavjud bo'lgan ma'lumotlarning miqdoriga bog'liq.