Optimal hisoblash byudjetini taqsimlash - Optimal computing budget allocation

Optimal hisoblash byudjetini taqsimlash (OCBA) bu umumiylikni maksimal darajaga ko'tarish uchun yondashuv simulyatsiya maqbul qarorni topish uchun samaradorlik.[1] Kontseptsiya 1990-yillarning o'rtalarida tomonidan taqdim etilgan Doktor Chun-Xen Chen. Oddiy qilib aytganda, OCBA - bu berilgan parametrlar to'plamida maqbul yoki eng yaxshi natijalarni olish uchun zarur bo'lgan takrorlanishlar sonini yoki simulyatsiya vaqtini aniqlashga yordam beradigan simulyatsiyaga yondashuv.[2] Bunga optimal taqsimot strukturasini tahlil qilish uchun asimptotik ramka yordamida erishiladi.[3] OCBA shuningdek, bo'limlarga asoslangan tasodifiylikni oshirishda samarali ekanligi ko'rsatilgan qidirish algoritmlari hal qilish uchun deterministik global optimallashtirish muammolar.[4]

Intuitiv tushuntirish

OCBA-ning maqsadi eng yaxshi alternativani tanlash uchun juda muhim simulyatsiyalarni o'z ichiga olgan ko'plab simulyatsiyalarni bajarishga tizimli yondashuvni ta'minlashdir. Boshqacha qilib aytganda, u eng muhim alternativalarning faqat bir qismiga e'tiborni qaratadi, bu hisoblash vaqtini minimallashtiradi va ushbu tanqidiy taxminchilarning farqlarini kamaytiradi. Kutilayotgan natija kerakli darajada aniqlikni saqlaydi, shu bilan birga oz miqdordagi ishni talab qiladi.[5] Masalan, biz 5 ta alternativ o'rtasida oddiy simulyatsiya yaratishimiz mumkin. Maqsad o'rtacha kechikish vaqti bilan alternativani tanlashdir. Quyidagi rasm dastlabki simulyatsiya natijalarini ko'rsatadi (ya'ni kerakli miqdordagi simulyatsiya takrorlanishining faqat bir qismini bajargan holda). Muqobil 2 va 3 ning kechikish vaqti ancha past (qizil rang bilan belgilangan) ekanligini ko'rish aniq. Hisoblash xarajatlarini tejash uchun (bu simulyatsiya jarayoniga sarflanadigan vaqt, mablag 'va mablag') OCBA 2 va 3 alternativalari uchun ko'proq takrorlanishlarni talab qiladi va simulyatsiya 1, 4 va 5 uchun ancha oldin to'xtatilishi mumkin natijalarga putur etkazmasdan.

Yuqoridagi grafikani kuzatgan holda, 2 va 3 alternativalari eng past narxga ega ekanligi aniq. OCBA hisoblash narxini minimallashtirish uchun faqat 2 va 3 alternativalari bo'yicha qo'shimcha simulyatsiyalarni taklif qiladi

Muammo

OCBA-ning asosiy maqsadi to'g'ri tanlash (PCS) ehtimolligini maksimal darajaga ko'tarishdir. Shaxsiy kompyuterlar namuna olishning ma'lum bir bosqichi uchun byudjetga bo'ysunadiτ.

Ushbu holatda umumiy hisoblash narxini anglatadi.[6]

OCBA-ning ba'zi kengaytmalari

Ushbu soha mutaxassislari ba'zi muammolarda nafaqat namunalar orasida eng yaxshi alternativani, balki 5, 10 yoki hatto 50 ta eng yaxshi alternativani bilish muhimdir, chunki qaror qabul qiluvchining qarorga ta'sir qilishi mumkin bo'lgan boshqa xavotirlari bo'lishi mumkinligini tushuntiradi. simulyatsiyada modellashtirilgan. Sechtman and Yücesan (2008) ma'lumotlariga ko'ra,[7] OCBA texnik-iqtisodiy asoslash muammolarini hal qilishda ham yordam beradi. Bu erda qaror qabul qiluvchilar faqatgina mumkin bo'lgan alternativalarni amalga oshirilmaydigan variantlardan farqlashdan manfaatdor. Bundan tashqari, sodda, ammo ishlashga o'xshash alternativani tanlash boshqa qaror qabul qiluvchilar uchun juda muhimdir. Bunday holda, eng yaxshi tanlov eng yaxshi variantlardan biri bo'lib, ularning ishlashi kerakli darajadan yuqori.[8] Bundan tashqari, Trailovich[9] va Pao[10] (2004) OCBA yondashuvini namoyish etadi, bu erda eng yaxshi o'rtacha o'rniga minimal dispersiyali alternativalarni topamiz. Bu erda biz OCBA qoidasini bekor qilgan holda nomuvofiq dispersiyalarni qabul qilamiz (dispersiyalar ma'lum deb taxmin qilamiz). 2010 yil davomida t taqsimotiga asoslangan OCBA algoritmi ustida izlanishlar olib borildi. Natijalar t-taqsimot va normal taqsimot o'rtasidagi farqlar o'rtasida hech qanday farq yo'q. Yuqorida keltirilgan OCBA kengaytmalari to'liq ro'yxat emas va u hali to'liq o'rganilmagan va tuzilmagan.[11]

Ko'p ob'ektiv OCBA

Ko'p ob'ektiv optimal hisoblash byudjetini taqsimlash (MOCBA) - bu ko'p ob'ektiv muammolarga taalluqli OCBA kontseptsiyasi. Odatda MOCBA-da, PCS quyidagicha ta'riflanadi

unda

  • kuzatilmoqda Pareto o'rnatildi,
  • Pareto bo'lmagan to'plamdir, ya'ni ,
  • loyihalashtiradigan voqea boshqa barcha dizaynlar ustunlik qilmaydi,
  • loyihalashtiradigan voqea kamida bitta dizayn ustunlik qiladi.

Biz shuni payqadikki, I toifa xatosi va II toifa xatosi to'g'ri Pareto to'plamini aniqlash uchun mos ravishda

va .

Bundan tashqari, buni isbotlash mumkin

va

qayerda maqsadlar soni va orqa tarqalishiga rioya qiladi Shuni ta'kidladi va kuzatilgan samaradorlik o'lchovlarining o'rtacha va standart og'ishidir dizayn va kuzatuvlar soni.

Shunday qilib, maksimal darajaga ko'tarish o'rniga , biz uning pastki chegarasini maksimal darajada oshirishimiz mumkin, ya'ni. Faraz qiling , quyidagi qoidalarni tuzish uchun Lagrange usuli qo'llanilishi mumkin:

unda

  • dizayn uchun , ,
  • dizayn uchun , ,

va

Cheklangan optimallashtirish

Oldingi bo'limga o'xshash, bir nechta ishlash ko'rsatkichlari bilan bog'liq vaziyatlar ko'p. Agar bir nechta ishlash ko'rsatkichlari bir xil darajada muhim bo'lsa, qaror qabul qiluvchilar MOCBA-dan foydalanishlari mumkin. Boshqa vaziyatlarda, qaror qabul qiluvchilar optimallashtirilishi kerak bo'lgan bitta asosiy ko'rsatkichga ega, ikkilamchi ko'rsatkichlar esa ma'lum chegaralar bilan cheklangan. Birlamchi ishlash ko'rsatkichini asosiy maqsad deb atash mumkin, ikkilamchi ko'rsatkichlarni cheklash choralari deb atashadi. Bu cheklangan optimallashtirish muammosiga tushadi. Muqobil variantlar soni aniqlanganda, muammo cheklangan tartiblash va tanlov deb ataladi, bu erda asosiy maqsad va cheklov choralarini stoxastik simulyatsiya yordamida baholash zarurligini hisobga olib, eng yaxshi loyihani tanlash maqsad qilingan. Cheklangan optimallashtirish uchun OCBA usulini (OCBA-CO deb nomlanadi) Pujowidianto va boshq. (2009) [12] va Li va boshq. (2012).[13]

Asosiy o'zgarish PCS ta'rifida. Cheklangan optimallashtirishda ikkita komponent mavjud, ya'ni maqbullik va maqsadga muvofiqlik. Natijada, simulyatsiya byudjeti har bir eng yaxshi bo'lmagan dizaynga optimallik yoki maqsadga muvofiqlik asosida taqsimlanishi mumkin. Boshqacha qilib aytadigan bo'lsak, eng yaxshi loyiha, agar u amalga oshirilmaydigan yoki haqiqiy eng yaxshi dizayndan yomonroq bo'lib qolsa, eng yaxshi amalga oshiriladigan dizayn sifatida noto'g'ri tanlanmaydi. Ushbu g'oya shundan iboratki, agar dizayn eng yaxshisidan yomonroq bo'lsa, maqsadga muvofiqligini aniqlash uchun byudjetning katta qismini sarflash kerak emas. Xuddi shunday, agar biz loyihalash asosiy maqsadimiz bo'yicha eng yaxshisidan yaxshiroq bo'lsa, maqsadga muvofiq ravishda ajratish orqali byudjetni tejashimiz mumkin.

Texnik-iqtisodiy asoslash

Ushbu muammoning maqsadi - dizaynning muqobil variantlarining cheklangan to'plamidan barcha amalga oshiriladigan loyihalarni aniqlash, bu erda amalga oshiriladigan dizaynlar belgilangan nazorat talablariga (cheklovlariga) javob beradigan ishlash ko'rsatkichlari bilan dizaynlashtirilgan deb ta'riflanadi. Barcha mumkin bo'lgan loyihalar tanlangan holda, qaror qabul qiluvchi boshqa samaradorlik mulohazalarini (masalan, xarajat yoki matematik baholash qiyin bo'lgan sifat mezonlari kabi deterministik mezonlarni) qo'shib yakuniy qarorni bemalol qabul qilishi mumkin. Imkoniyatlarni aniqlash muammosi stoxastik cheklovlarni ham o'z ichiga olgan bo'lsa-da, u yuqorida keltirilgan cheklangan optimallashtirish muammolaridan ajralib turadi, chunki u eng yaxshi amalga oshiriladigan loyihalar o'rniga barcha mumkin bo'lgan loyihalarni aniqlashga qaratilgan.

Aniqlang

  • : dizaynlarning umumiy soni;
  • : ishlash o'lchovlari cheklovlarining umumiy soni;
  • : ning nazorat talabi barcha dizaynlar uchun cheklov, ;
  • : amalga oshiriladigan dizaynlar to'plami;
  • : amalga oshirib bo'lmaydigan dizaynlar to'plami;
  • : ning simulyatsiya namunalarining o'rtacha qiymati cheklov o'lchovi va dizayni ;
  • : ning simulyatsiya namunalarining dispersiyasi cheklov o'lchovi va dizayni ;
  • : loyihalash uchun ajratilgan jami simulyatsiya byudjetining ulushi ;
  • : simulyatsiya namunalarining namunaviy o'rtacha qiymati cheklov o'lchovi va dizayni .

Deylik, barcha cheklovlar , . Barcha mumkin bo'lgan dizaynlarni to'g'ri tanlash ehtimoli

va texnik-iqtisodiy aniqlash uchun byudjetni taqsimlash muammosi Gao va Chen tomonidan berilgan (2017)[14]

Ruxsat bering va . Asimptotik optimal byudjetni taqsimlash qoidasi

Intuitiv ravishda aytganda, yuqoridagi ajratish qoidasida (1) amalga oshiriladigan dizayn uchun dominant cheklov barcha cheklovlar orasida to'g'ri aniqlanishi qiyin bo'lganligi aytiladi; va (2) amalga oshirib bo'lmaydigan dizayn uchun dominant cheklov barcha cheklovlar orasida eng oson aniqlangan.

Kutilayotgan imkoniyat narxi bilan OCBA

Asl OCBA eng yaxshi dizaynni to'g'ri tanlash (PCS) ehtimolini maksimal darajada oshiradi. Amalda, yana bir muhim o'lchov - bu tanlangan dizaynning o'rtacha qiymati eng yaxshi ko'rsatkichdan qanchalik uzoqligini aniqlaydigan kutilgan imkoniyatlar qiymati (EOC). Ushbu chora muhim ahamiyatga ega, chunki EOCni optimallashtirish nafaqat eng yaxshi dizaynni tanlash imkoniyatini oshiradi, balki eng yaxshisini topolmasa, tanlangan dizaynning o'rtacha qiymati eng yaxshi dizayndan uzoqroq bo'lishini ta'minlaydi. PCS bilan taqqoslaganda, EOC, ayniqsa noto'g'ri tanlovni biroz noto'g'ri tanlovdan ko'proq jazolaydi va shuning uchun xavf-xatarga duch kelmaydigan amaliyotchilar va qaror qabul qiluvchilar tomonidan afzal ko'riladi.

Xususan, kutilayotgan imkoniyat narxi

qayerda,

  • dizaynlarning umumiy soni;
  • haqiqiy eng yaxshi dizayn;
  • tasodifiy o'zgaruvchidir, uni amalga oshirish kuzatilgan eng yaxshi dizayndir;
  • dizaynning simulyatsiya namunalarining o'rtacha qiymati , ;
  • .

EOC ob'ektiv choralari bilan byudjetni taqsimlash muammosi Gao va boshq. (2017)[15]

qayerda loyihalash uchun ajratilgan umumiy simulyatsiya byudjetining ulushi .Agar biz taxmin qilsak Barcha uchun , ushbu muammo uchun byudjetni assimtotik optimal taqsimlash qoidasi

qayerda dizaynning simulyatsiya namunalarining farqidir . Ushbu ajratish qoidasi (1) masalaning asimptotik optimal echimi bilan bir xil. Ya'ni, asimptotik tarzda aytganda, shaxsiy kompyuterlarni maksimal darajaga ko'tarish va EOCni minimallashtirish bir xil narsadir.

Kirish noaniqligi bilan OCBA

Yuqorida aytib o'tilgan OCBA usullari uchun aniq taxmin shundan iboratki, haqiqiy kirish taqsimotlari va ularning parametrlari ma'lum, amalda ular odatda noma'lum va cheklangan tarixiy ma'lumotlarga qarab baholanishi kerak. Bu tanlovning sifatiga (jiddiy) ta'sir ko'rsatishi mumkin bo'lgan taxminiy taqsimotlarda va ularning parametrlarida noaniqlikka olib kelishi mumkin. Noaniqlik to'plamida asosiy kirish taqsimotlari va parametrlari uchun cheklangan sonli stsenariylar mavjud deb faraz qilsak, Gao va boshq. (2017)[16] qat'iy simulyatsiya byudjeti bo'yicha eng yaxshi dizaynni to'g'ri tanlash ehtimolini maksimal darajaga ko'tarish orqali yangi OCBA yondashuvini joriy etadi, bu erda dizaynning ishlashi uning noaniqlik to'plamidagi barcha mumkin bo'lgan stsenariylar orasida eng yomon ishlashi bilan o'lchanadi.

OCBA-ning veb-namoyishi

Quyidagi havola oddiy misol yordamida OCBA namoyishini taqdim etadi. Demo-da OCBA an'anaviy byudjetga taqqoslaganda hisoblash byudjetini qanday bajarishini va taqsimlashini ko'rasiz.

Adabiyotlar

  1. ^ Fu, M, C. H. Chen va L. Shi, “Simulyatsiya optimallashtirish uchun ba'zi mavzular, ”2008 yilgi qishki simulyatsiya konferentsiyasining materiallari, 27-38 betlar, Mayami, FL, 2008 yil dekabr.
  2. ^ Chen va Loo H. Li. Stoxastik simulyatsiyani optimallashtirish, byudjetni hisoblash uchun eng maqbul mablag'ni ajratish. Singapore Hackensack, NJ: World Scientific, 2011. Chop etish ..
  3. ^ Chen, C. H. "Diskret hodisalarni simulyatsiya qilish uchun hisoblash byudjetini oqilona ajratish bo'yicha samarali yondashuv, "Qaror va nazorat bo'yicha 34-IEEE konferentsiyasi materiallari, 2598–2605 betlar, 1995 yil dekabr.
  4. ^ Chen, W., S. Gao, C. H. Chen va L. Shi, "Bo'limlarga asoslangan tasodifiy qidirish uchun maqbul namunalarni ajratish strategiyasi, "Avtomatlashtirish fanlari va muhandisligi bo'yicha IEEE operatsiyalari, 11 (1), 177-186, 2014.
  5. ^ Chen, Chun-Xang. "Ishonchsizlik ostida simulyatsiya asosida qaror qabul qilish uchun byudjetni maqbul taqsimlash (OCBA)". Arxivlandi asl nusxasi 2013 yil 1 oktyabrda. Olingan 9 iyul 2013.
  6. ^ Chen va Loo H. Li. Stoxastik simulyatsiyani optimallashtirish, byudjetni hisoblash uchun eng maqbul mablag'ni ajratish. Singapore Hackensack, NJ: World Scientific, 2011. Chop etish.
  7. ^ Sechtman R, Yücesan E (2008) Texnik-iqtisodiy asoslashni aniqlashning yangi istiqbollari. 2008 yilgi qishki Simul Conf 273-280
  8. ^ Jia QS, Chjou E, Chen CH (2012). eng sodda yaxshi dizaynlarni topish uchun byudjet mablag'larini samarali hisoblash. IIE Trans, paydo bo'lish uchun.
  9. ^ Trailovic Tekin E, Sabuncuoglu I (2004) Simulyatsiyani optimallashtirish: nazariya va qo'llanmalar bo'yicha keng qamrovli sharh. IIE Trans 36: 1067-1081
  10. ^ Trailovich L, Pao LY (2004) Maqsadlarni kuzatib borish algoritmlarini qo'llash bilan xilma-xillikni samarali saralash va tanlash uchun byudjet ajratmalarini hisoblash, IEEE Trans Autom Control 49: 58–67.
  11. ^ Chen, C. H., M. Fu, L. Shi va L. H. Li, "Stoxastik tizimlarni simulyatsiya optimallashtirish", Xitoyda elektr va elektron muhandislik chegaralari, 6 (3), 468-480, 2011
  12. ^ Pujowidianto NA, Li LH, Chen CH, Yap CM (2009) Cheklangan optimallashtirish uchun byudjetni optimal hisoblash. 2009 yilgi qishki Simul Conf 584-589.
  13. ^ Li LH, Pujovidianto NA, Li LW, Chen CH, Yap CM (2012) Stoxastik cheklovlar mavjud bo'lganda eng yaxshi dizaynni tanlash uchun taxminiy simulyatsiya byudjetini taqsimlash, IEEE Trans Autom Control 57: 2940-2945.
  14. ^ Gao, S. va V. Chen "Ko'p ko'rsatkichlarni cheklashlari bilan samarali texnik-iqtisodiy aniqlash, "Avtomatik boshqarish bo'yicha IEEE operatsiyalari, 62, 113–122, 2017 y.
  15. ^ Gao, S., V. Chen va L. Shi "Kutilayotgan imkoniyat xarajatlari uchun yangi byudjet ajratish doirasi, "Operatsion tadqiqotlar, 63, 787-803, 2017 yil.
  16. ^ Gao, S., X. Xiao, E. Chjou va V. Chen "Optimal hisoblash byudjetini taqsimlash bilan ishonchli tartib va ​​tanlov, "Automatica, 81, 30-36, 2017 yil.

Tashqi havolalar