Бюджетті оңтайлы есептеу - Optimal computing budget allocation

Бюджетті оңтайлы есептеу (OCBA) бұл тұтасты максимизациялау тәсілі модельдеу оңтайлы шешім табудың тиімділігі.[1] Тұжырымдама 1990 жылдардың ортасында енгізілді Доктор Чун-Хен Чен. Қарапайым тілмен айтқанда, OCBA - бұл берілген параметрлер жиынтығында қолайлы немесе жақсы нәтиже алу үшін қайталанулар санын немесе модельдеу уақытын анықтауға көмектесетін модельдеуге көзқарас.[2] Бұл оңтайлы бөлудің құрылымын талдау үшін асимптотикалық негізді қолдану арқылы жүзеге асырылады.[3] OCBA сонымен қатар бөлімге негізделген кездейсоқтықты жақсартуда тиімді болып шықты іздеу алгоритмдері шешу үшін детерминирленген жаһандық оңтайландыру мәселелер.[4]

Интуитивті түсіндіру

OCBA-ның мақсаты - ең жақсы баламаны таңдау үшін тек сыни баламаларды қоса, көптеген модельдеуді жүргізуге жүйелі тәсілді қамтамасыз ету. Басқаша айтқанда, ол ең маңызды баламалардың бір бөлігіне ғана назар аударады, бұл есептеу уақытын азайтады және осы сыни бағалаушылардың дисперсияларын азайтады. Күтілетін нәтиже аз жұмыс көлемін талап ете отырып, қажетті дәлдіктің деңгейін сақтайды.[5] Мысалы, біз 5 балама арасында қарапайым модельдеу жасай аламыз. Мақсат - ең төменгі орташа кідіріс уақытымен балама таңдау. Төмендегі суретте модельдеудің алдын-ала нәтижелері көрсетілген (яғни, модельдеу репликаларының қажетті санының тек бір бөлігін ғана орындау керек). 2 және 3 баламаларының кідіріс уақыты едәуір аз екенін (қызыл түспен көрсетілген) көруге болады. Есептеу құнын үнемдеу үшін (уақытты, ресурстар мен ақшаны модельдеу процесіне жұмсау керек) OCBA 2 және 3 баламалары үшін көбірек репликалар қажет деп болжайды, ал модельдеуді 1, 4 және 5-ке әлдеқайда ертерек тоқтатуға болады нәтижелерге зиян келтірмей.

Жоғарыда келтірілген графиканы сақтай отырып, 2 және 3 баламаларының ең төменгі құны екені анық. OCBA есептеу құнын азайту үшін тек 2 және 3 баламалары бойынша одан әрі модельдеу жүргізуді ұсынады

Мәселе

OCBA-ның негізгі мақсаты - дұрыс таңдау ықтималдығын арттыру (PCS). ДК іріктеудің белгілі бір кезеңінің іріктеу бюджетіне бағынадыτ.

Бұл жағдайда жалпы есептеу құнын білдіреді.[6]

OCBA кейбір кеңейтімдері

Сала мамандары кейбір мәселелерде таңдаманың ішіндегі ең жақсы баламаны ғана емес, сонымен қатар 5, 10 немесе тіпті 50-ді білу маңызды деп түсіндіреді, өйткені шешім қабылдаушы шешім қабылдауға әсер етуі мүмкін басқа да алаңдаушылық туғызуы мүмкін. модельдеуде модельденген. Сехтман мен Юцесанның (2008) пікірінше,[7] OCBA техникалық-экономикалық негіздеу мәселелерінде де пайдалы. Бұл жерде шешім қабылдаушылар мүмкін болатын баламаларды мүмкін емес нұсқалардан ажыратуға ғана мүдделі. Одан әрі қарапайым, бірақ өнімділігі жағынан ұқсас баламаны таңдау басқа шешім қабылдаушылар үшін өте маңызды. Бұл жағдайда ең жақсы таңдау - ең қажетті қарапайым альтернатива болып табылады, олардың өнімділігі қажетті деңгейден жоғары.[8] Сонымен қатар, Trailovic[9] және Пао[10] (2004) OCBA тәсілін көрсетеді, мұнда ең жақсы орташаға емес, минималды дисперсияға балама табамыз. Мұнда біз OCBA ережесін жойып, белгісіз дисперсияларды қабылдаймыз (дисперсиялар белгілі болған жағдайда). 2010 жылы t үлестіріміне негізделген OCBA алгоритмі бойынша зерттеулер жүргізілді. Нәтижелер t-үлестірімі мен қалыпты таралуы арасындағы айырмашылықты айтарлықтай байқатпайды. Жоғарыда көрсетілген OCBA кеңейтімдері толық тізім болып табылмайды және әлі толық зерттеліп, жинақталуы керек.[11]

Көп мақсатты OCBA

Көп мақсатты бюджетті оңтайлы бөлу (MOCBA) - бұл көп мақсатты мәселелерге қолданылатын OCBA тұжырымдамасы. Әдеттегі MOCBA-да ДК ретінде анықталады

онда

  • байқалады Парето қойылды,
  • Pareto емес жиынтығы, яғни ,
  • бұл жобалаушы оқиға барлық басқа дизайндар басым емес,
  • бұл жобалаушы оқиға кем дегенде бір дизайнмен басым болады.

I типті қате екенін байқаймыз және II типтік қате дұрыс Pareto жиынтығын анықтау үшін сәйкесінше

және .

Сонымен қатар, мұны дәлелдеуге болады

және

қайда мақсаттар саны, және артқы таралуы жүреді Бұл атап өтті және бұл мақсатқа арналған нәтиже өлшемдерінің орташа және стандартты ауытқуы дизайн , және бақылаулар саны.

Осылайша, максимизациялаудың орнына , біз оның төменгі шекарасын барынша арттыра аламыз, яғни. Болжалды , келесі ережелерді жасау үшін Лагранж әдісін қолдануға болады:

онда

  • дизайн үшін , ,
  • дизайн үшін , ,

және

Шектелген оңтайландыру

Алдыңғы бөлімге ұқсас, бірнеше өнімділік өлшемдері бар көптеген жағдайлар бар. Егер тиімділіктің бірнеше шаралары бірдей маңызды болса, шешім қабылдаушылар MOCBA-ны қолдана алады. Басқа жағдайларда, шешім қабылдаушылар тиімділіктің бір негізгі өлшемін оңтайландыруы керек, ал екінші дәрежелі көрсеткіштер белгілі бір шектеулермен шектеледі. Өнімділіктің негізгі өлшемін негізгі мақсат деп атауға болады, ал екінші дәрежелі көрсеткіштер бұлтартпау шаралары деп аталады. Бұл шектеулі оңтайландыру проблемасына түседі. Альтернатива саны бекітілгенде, проблема шектеулі рейтинг және таңдау деп аталады, мұндағы мақсат ең басты жобаны таңдау болып табылады, өйткені басты мақсат пен шектеу шараларын стохастикалық модельдеу арқылы бағалау қажет. Шектелген оңтайландырудың OCBA әдісін (OCBA-CO деп атайды) Пуджовидианто және басқаларында табуға болады. (2009) [12] және Ли т.б. (2012).[13]

Негізгі өзгеріс ДК-нің анықтамасында. Шектелген оңтайландыруда екі компонент бар, яғни оңтайлылық және орындылық. Нәтижесінде модельдеу бюджеті әр үздік емес дизайнға оңтайлылық немесе орындылық негізінде бөлінуі мүмкін. Басқаша айтқанда, ең жақсы емес дизайн, егер ол орындалмайтын немесе шынайы мүмкін дизайннан нашар болса, ең жақсы мүмкін дизайн ретінде қате таңдалмайды. Идеясы, егер дизайн айқындалғаннан гөрі нашар болса, орындылығын анықтау үшін бюджеттің көп бөлігін жұмсаудың қажеті жоқ. Дәл сол сияқты, егер біз жобалау қазірдің өзінде негізгі мақсат тұрғысынан жақсырақ болса, орындылыққа негізделген қаражат бөлу арқылы бюджетті үнемдей аламыз.

Техникалық-экономикалық негіздеу

Бұл мәселенің мақсаты - жобалаудың альтернативті нұсқаларының ақырғы жиынтығынан барлық мүмкін болатын жобаларды анықтау, мұндағы орындалатын дизайндар белгіленген бақылау талаптарын (шектеулерін) қанағаттандыратын олардың орындау өлшемдерімен жобалар ретінде анықталған. Барлық ықтимал жобаларды таңдаған кезде шешім қабылдаушы басқа шешімдерді (мысалы, шығындар немесе математикалық бағалау қиын сапалық критерийлер сияқты детерминистік критерийлер) басқа нәтижелерді ескере отырып, соңғы шешімді оңай қабылдай алады. Техника-экономикалық негіздеу проблемасы стохастикалық шектеулерді де қамтығанымен, ол жоғарыда келтірілген оңтайландырудың шектеулі мәселелерінен ерекшеленеді, өйткені ол ең жақсы мүмкін болатын біреуінің орнына барлық мүмкін дизайндарды анықтауға бағытталған.

Анықтаңыз

  • : жобалардың жалпы саны;
  • : өнімділік өлшемдерінің жалпы саны;
  • : бақылау талабы барлық дизайн үшін шектеулер, ;
  • : мүмкін болатын дизайн жиынтығы;
  • : орындалмайтын дизайн жиынтығы;
  • : модельдеу үлгілерінің орташа мәні бұлтартпау шарасы және дизайны ;
  • : модельдеу үлгілерінің дисперсиясы бұлтартпау шарасы және дизайны ;
  • : жобалауға бөлінген жалпы модельдеу бюджетінің үлесі ;
  • : модельдеу үлгілерінің орташа мәні бұлтартпау шарасы және дизайны .

Барлық шектеулер формада берілген делік , . Барлық мүмкін дизайндарды дұрыс таңдау ықтималдығы

және ТЭН-ді анықтау үшін бюджетті бөлу мәселесін Гао мен Чен келтіреді (2017)[14]

Келіңіздер және . Бюджетті бөлудің асимптотикалық оңтайлы ережесі

Интуитивті түрде айтатын болсақ, жоғарыда көрсетілген бөлу ережесінде (1) мүмкін болатын дизайн үшін барлық шектеулердің ішіндегі ең маңыздысы - бұл ең қиын деген сөз; және (2) мүмкін емес дизайн үшін басым шектеулер барлық шектеулер арасында дұрыс анықталатын ең қарапайым болып табылады.

Болжалды шығындармен OCBA

Түпнұсқа OCBA ең жақсы дизайнды дұрыс таңдау ықтималдығын жоғарылатады (PCS). Іс жүзінде тағы бір маңызды шара - бұл таңдалған дизайнның орташа мәні ең жақсы көрсеткіштен қаншалықты алыс болатындығын көрсететін күтілетін мүмкіндік құны (EOC). Бұл шара өте маңызды, өйткені EOC-ті оңтайландыру ең жақсы дизайнды таңдау мүмкіндігін жоғарылатып қана қоймай, сонымен қатар таңдалған дизайнның орташа мәні ең жақсы дизайннан алшақ болмауын қамтамасыз етеді, егер ол ең жақсы дизайнды таба алмаса. ДК-мен салыстырғанда, ЭОК әсіресе нашар таңдауды сәл дұрыс емес таңдаудан гөрі жазалайды, сондықтан тәуекелге бейтарап практиктер мен шешім қабылдаушылар оны таңдайды.

Нақтырақ айтсақ, болжамды шығындар болып табылады

қайда,

  • - дизайнның жалпы саны;
  • бұл ең жақсы дизайн;
  • - бұл кездейсоқ шама, оның орындалуы байқалған ең жақсы дизайн болып табылады;
  • - бұл модельдеу үлгілерінің орташа мәні , ;
  • .

EOC-тің объективті шараларымен бюджетті бөлу проблемасын Гао және басқалар келтіреді. (2017)[15]

қайда бұл жобалауға бөлінген жалпы модельдеу бюджетінің үлесі .Егер біз болжасақ барлығына , бұл проблемаға арналған бюджетті бөлудің асимптотикалық оңтайлы ережесі

қайда - бұл модельдеу үлгілерінің дисперсиясы . Бұл бөлу ережесі есептің асимптотикалық оңтайлы шешімімен бірдей (1). Яғни, асимптотикалық түрде ДК-ді максималдау және EOC-ті азайту бірдей нәрсе.

Кіріс белгісіздігімен OCBA

Жоғарыда айтылған OCBA әдістері туралы нақты болжам - бұл нақты үлестірімдер және олардың параметрлері белгілі, ал іс жүзінде олар әдетте белгісіз және шектеулі тарихи деректер бойынша бағалануы керек. Бұл таңдаудың сапасына (қатты) әсер етуі мүмкін болжамды үлестірім мен олардың параметрлерінің белгісіздігіне әкелуі мүмкін. Белгісіздік жиынтығында негізгі кіріс үлестірімдері мен параметрлеріне арналған сценарийлердің ақырғы саны бар деп есептесек, Гао және басқалар. (2017)[16] бекітілген модельдеу бюджеті бойынша ең жақсы дизайнды дұрыс таңдау ықтималдығын арттыру арқылы жаңа OCBA тәсілін енгізеді, мұнда дизайн өнімділігі белгісіздік жиынтығындағы барлық ықтимал сценарийлер арасындағы ең нашар көрсеткіштерімен өлшенеді.

OCBA-ның веб-демонстрациясы

Келесі сілтеме қарапайым мысалды қолдана отырып OCBA демонстрациясын ұсынады. Көрсетілімде сіз OCBA-ның есептеу бюджетін қалай орындайтынын және бөлетінін дәстүрлі тең бөлу тәсілімен салыстырғанда басқаша көресіз.

Пайдаланылған әдебиеттер

  1. ^ Фу, М, C. Х. Чен және Л. Ши, «Имитацияны оңтайландыруға арналған кейбір тақырыптар, ”2008 жылғы қысқы модельдеу конференциясының материалдары, 27–38 б., Майами, Флорида, 2008 ж.
  2. ^ Чен және Лу Х.Ли. Стохастикалық модельдеуді оңтайландыру бюджетті оңтайлы есептеу. Сингапур Hackensack, NJ: World Scientific, 2011. Басып шығару ..
  3. ^ Chen, C. H. «Дискретті оқиғаларды модельдеу үшін есептеу бюджетін ақылды түрде бөлудің тиімді тәсілі, «Шешімдер мен бақылау бойынша 34-ші IEEE конференциясының материалдары, 2598–2605 бб., 1995 ж.
  4. ^ Чен, В., С. Гао, Ч. Х. Чен және Л. Ши, «Бөлімге негізделген кездейсоқ іздеуге арналған үлгіні бөлудің оңтайлы стратегиясы, «Автоматика ғылымы мен техникасы бойынша IEEE транзакциялары, 11 (1), 177–186, 2014 ж.
  5. ^ Чен, Чун-Хунг. «Белгісіздік жағдайында модельдеу негізінде шешім қабылдау үшін бюджетті оңтайлы бөлу (OCBA)». Архивтелген түпнұсқа 2013 жылғы 1 қазанда. Алынған 9 шілде 2013.
  6. ^ Чен және Лу Х.Ли. Стохастикалық модельдеуді оңтайландыру бюджетті оңтайлы есептеу. Singapore Hackensack, NJ: World Scientific, 2011. Басып шығару.
  7. ^ Sececman R, Yücesan E (2008) Техникалық-экономикалық негіздеудің жаңа перспективасы. 2008 жылғы Қысқы Симул Конф. 273–280
  8. ^ Jia QS, Чжоу Е, Чен CH (2012). қарапайым қарапайым дизайнды табуға бюджетті тиімді бөлу. IIE Trans, пайда болу үшін.
  9. ^ Трайловик Текин Е, Сабунджиоглу I (2004) Имитациялық оңтайландыру: Теория мен қолданбаларға жан-жақты шолу. IIE Транс 36: 1067–1081
  10. ^ Trailovic L, Pao LY (2004) Мақсатты қадағалау алгоритміне қосымшамен ауытқуларды таңдау және тиімді таңдау үшін бюджетті бөлуді есептеу, IEEE Trans Autom Control 49: 58–67.
  11. ^ Chen, C. H., M. Fu, L. Shi және L. H. Lee, “Стохастикалық жүйелерді модельдеуді оңтайландыру”, Қытайдағы электрлік және электронды техниканың шекаралары, 6 (3), 468-480, 2011
  12. ^ Pujowidianto NA, Lee LH, Chen Chen, Yap CM (2009) Шектелген оңтайландыру үшін бюджетті оңтайлы бөлу. 2009 жылғы қысқы Simul Conf 584–589 нұсқасы.
  13. ^ Ли ЛХ, Пуджовианто Н.А., Ли Л.В., Чен Ч., Яп CM (2012) Стохастикалық шектеулер болған кезде ең жақсы дизайнды таңдауға арналған бюджетті жуықтау модельдеу, IEEE Trans Autom Control 57: 2940–2945.
  14. ^ Гао, С. және В. Чен »Өнімділік өлшемдерінің бірнеше шектеулерімен тиімді экономикалық негіздеу, «Автоматты басқарудағы IEEE транзакциялары, 62, 113–122, 2017 ж.
  15. ^ Гао, С., В. Чен және Л. Ши, «Күтілетін мүмкіндік құнына бюджетті бөлудің жаңа негізі, «Операциялық зерттеулер, 63, 787–803, 2017 ж.
  16. ^ Гао, С., Х. Сяо, Э. Чжоу және В. Чен »Есептік бюджетті оңтайлы бөлумен сенімді рейтинг және таңдау, «Automatica, 81, 30–36, 2017 ж.

Сыртқы сілтемелер