Аптымальнае размеркаванне бюджэту вылічэнняў (OCBA)

Source: http://seor.vse.gmu.edu/~cchen9/ocba.html

У нас ёсць самы сучасны падыход да разумнага размеркавання вылічальнага бюджэту для эфектыўнай аптымізацыі мадэлявання. Мэта складаецца ў тым, каб знайсці найлепшы дызайн з мінімальным часам мадэлявання. Многія з нашых суаўтараў і сяброў уносяць свой уклад у пашырэнне гэтай вобласці.

Мадэляванне з'яўляецца папулярным інструментам для распрацоўкі вялікіх, складаных, стахастычных сістэм, паколькі аналітычныя рашэнні закрытай формы звычайна не існуюць для такіх задач. Нягледзячы на тое, што развіццё новых тэхналогій рэзка павялічыла вылічальную магутнасць, эфектыўнасць па-ранейшаму выклікае вялікую заклапочанасць пры выкарыстанні мадэлявання для праектавання вялікіх сістэм, і ў гэтым выпадку неабходна мадэляваць шмат альтэрнатыўных канструкцый. Што яшчэ горш, некалькі прагонаў мадэлявання павінны быць выкананы для кожнай канструкцыі, каб злавіць выпадковыя паводзіны ў сістэмах. Як рэзка скараціць агульны час вылічэнняў - ключавое пытанне ў гэтай тэме.

Ключавым кампанентам нашых метадалогій з'яўляецца наш новы метад мадэлявання тэарэтыкі кіравання пад назвай Аптымальнае размеркаванне бюджэту вылічэнняў (OCBA). Падыход OCBA можа інтэлектуальна вызначыць найбольш эфектыўныя лічбы рэплікацыі мадэлявання або даўжыню мадэлявання для ўсіх мадэляваных альтэрнатыў. Мэта складаецца ў тым, каб атрымаць найвышэйшую якасць рашэнняў мадэлявання з выкарыстаннем фіксаванага бюджэту вылічэнняў або дасягнуць жаданай якасці рашэнняў мадэлявання з выкарыстаннем мінімальнага бюджэту вылічэнняў. Лічбавае тэсціраванне паказвае, што наш падыход можа атрымаць аднолькавую якасць мадэлявання, выдаткаваўшы толькі адну дзясятую намаганняў на мадэляванне.

OCBA таксама ідэальна падыходзіць для аптымізацыі стахастычнага мадэлявання. Асноўнай прычынай таго, што аптымізацыя мадэлявання складаная, з'яўляецца выпадковы характар ацэнкі мэтавай функцыі, што азначае, што існуе асноўны кампраміс паміж выдаткаваннем вылічальных намаганняў на пошук прасторы для новых рашэнняў-кандыдатаў (даследаванне) і атрыманнем больш дакладных ацэнак мэтавай функцыі пры перспектыўных у цяперашні час рашэннях (эксплуатацыі). Іншымі словамі, колькі бюджэту мадэлявання трэба вылучыць на дадатковыя рэплікацыі ва ўжо наведаных кропках і колькі на рэплікацыі ў зноў створаных кропках пошуку, з'яўляецца важным момантам з пункту гледжання эфектыўнасці вылічэнняў. У працэдуры OCBA паслядоўна вызначае, якія альтэрнатывы дызайну патрабуюць дадатковага мадэлявання і колькі дадатковых рэплікацый неабходна.

Інтуітыўна зразумела, каб пераканацца, што лепшая альтэрнатыва выбрана правільна, большая частка вылічальнага бюджэту павінна быць размеркавана на тыя альтэрнатывы, якія маюць вырашальнае значэнне ў працэсе вызначэння лепшай альтэрнатывы. Іншымі словамі, большая колькасць мадэлявання павінна быць праведзена з гэтымі крытычнымі альтэрнатывамі, каб паменшыць дысперсіі крытычных ацэншчыкаў. Агульная эфектыўнасць мадэлявання павышаецца, паколькі менш вылічальных намаганняў затрачваецца на мадэляванне некрытычных альтэрнатыў і больш - на крытычныя альтэрнатывы. Ідэі тлумачацца на наступным простым прыкладзе. Выкажам здагадку, што мы выконваем мадэляванне для 5 альтэрнатыў, каб вызначыць альтэрнатыву з мінімальнай сярэдняй затрымкай. Перш за ўсё, мы праводзім папярэдняе мадэляванне для ўсіх 5 альтэрнатыў. На малюнку 1-(a) дадзены прыклад іх 99% даверных інтэрвалаў, атрыманых у выніку папярэдняга мадэлявання. Звярніце ўвагу, што нявызначанасць ацэнкі звязана са стахастычнымі характарыстыкамі сістэмы і выкарыстаннем мадэлявання метадам Монтэ-Карла.

Як відаць на малюнку 1-(a), хоць існуе нявызначанасць у ацэнцы прадукцыйнасці кожнай альтэрнатывы, відавочна, што альтэрнатывы 2 і 3 значна лепшыя за іншыя альтэрнатывы, калі мы маем намер знайсці альтэрнатыву з мінімальным сярэднім затрымка. І таму толькі альтэрнатывы 2 і 3 неабходна дадаткова змадэляваць, каб паменшыць нявызначанасць ацэнкі, каб правільна вызначыць лепшую альтэрнатыву. Спыніўшы мадэляванне для варыянтаў 1, 4 і 5 раней, мы можам зэканоміць шмат выдаткаў на вылічэнні.

Аднак тое, што на самой справе адбываецца ў большасці выпадкаў, не так трывіяльна, як паказана на малюнку 1-(a). Часцей сустракаюцца такія выпадкі, як іншы прыклад, паказаны на малюнку 1-(b), калі некаторыя альтэрнатывы здаюцца лепшымі, але відавочна не лепшымі за іншыя. У такіх выпадках няпроста вызначыць, якія альтэрнатывы можна выдаліць з імітацыйнага эксперыменту і калі іх трэба спыніць. OCBA забяспечвае сістэмны падыход для вырашэння гэтай праблемы і размеркавання мадэлявання на альтэрнатывы такім чынам, каб эфектыўнасць мадэлявання была максімальнай.

Каб даведацца больш пра OCBA, наступныя два дакументы з'яўляюцца добрай адпраўной кропкай:

Прадстаўленне ідэй OCBA

Chen, CH і LH Lee, Аптымізацыя стахастычнага мадэлявання: аптымальнае размеркаванне бюджэту вылічэнняў . World Scientific Publishing Co., 2011.

Xu, J., E. Huang, L. Hsieh, LH Lee, QS Jia і CH Chen, «Аптымізацыя мадэлявання ў эпоху Industrial 4.0 і прамысловага Інтэрнэту», 10(4), 310-320, Journal of Simulation , 2016 год.

Xu, J., E. Huang, CH Chen і LH Lee, "Simulation Optimization: A Review and Exploration in the New Era of Cloud Computing and Big Data", Asia-Pacific Journal of Operational Research , 32 (3), Чэрвень 2015 год

Chen, CH, M. Fu, and L. Shi, "Simulation and Optimization," Tutorials in Operations Research , pp. 247-260, Informs, Hanover, MD, 2008.

Fu, M, CH Chen і L. Shi, "Некаторыя тэмы для аптымізацыі мадэлявання", Працы зімовай канферэнцыі па мадэляванні 2008 г. , стар. 27-38, Маямі, штат Фларыда, снежань 2008 г.

Вось яшчэ некалькі рэпрэзентатыўных публікацый пра метады OCBA.

Адзін з самых папулярных дакументаў OCBA

Chen, CH, J. Lin, E. Yucesan і SE Chick, "Размеркаванне бюджэту мадэлявання для далейшага павышэння эфектыўнасці парадкавай аптымізацыі", Journal of Discrete Event Dynamic Systems: Theory and Applications , Vol. 10, стар. 251-270, ліпень 2000 г.

Больш ранняя распрацоўка OCBA

Chen, CH "Эфектыўны падыход да разумнага размеркавання вылічальнага бюджэту для мадэлявання дыскрэтных падзей", Працы 34-й канферэнцыі IEEE па прыняцці рашэнняў і кіраванні , стар. 2598-2605, снежань 1995 г.

Chen, CH "Ніжняя мяжа для правільнай верагоднасці выбару падмноства і яе прымяненне да мадэлявання сістэмы дыскрэтных падзей", IEEE Transactions on Automatic Control , Vol. 41, № 8, стар. 1227-1231, жнівень 1996 г.

Chen, CH, E. Yucesan, L. Dai і HC Chen, "Эфектыўнае вылічэнне аптымальнага размеркавання бюджэту для эксперыменту мадэлявання дыскрэтных падзей", IIE Transactions , Vol. 42, № 1, с. 60-70, студзень 2010 г.

OCBA для праблем з некалькімі мэтамі

Лі, Л. Х., Э. П. Чу, С. І. Тэнг і Д. Голдсман, "Аптымальнае размеркаванне бюджэту вылічэнняў для шматаб'ектыўных імітацыйных мадэляў", Працы зімовай канферэнцыі па мадэляванні 2004 г. , с. 586-594, 2004 г.

Э. Дж. Чэнь і Л. Г. Лі, "Працэдура шматаб'ектыўнага выбару для вызначэння набору Парэта", Кампутары і даследаванне аперацый, 36 (6) , : 1872-1879, 2009.

С. Тэнг, Л. Х. Лі і Э. П. Чу, "Інтэграцыя зоны абыякавасці з размеркаваннем бюджэту шматмэтавых вылічэнняў", Еўрапейскі часопіс аперацыйных даследаванняў, 203 (2): 419-429, 2010.

LH Lee, EP Chew, SY Teng і D. Goldsman (2010). Знаходжанне набору Парэта для шматаб'ектыўных імітацыйных мадэляў, якія з'явяцца ў транзакцыях IIE .

OCBA для выбару аптымальнага падмноства лепшых дызайнаў (скажам, топ-5)

Chen, CH, D. He, M. Fu і LH Lee, "Эфектыўнае размеркаванне бюджэту мадэлявання для выбару аптымальнага падмноства", паведамляе Journal on Computing , Vol. 20, № 4, стар. 579-595, 2008.

Zhang, S., LH Lee, EP Chew, J. Xu і CH Chen, "A Simulation Budget Allocation Procedure for Enhancing the Efficiency of Optimal Subset Selection", IEEE Transactions on Automatic Control , 61(1), 62-75, Студзень 2016 года.

OCBA для выбару лепшай альтэрнатывы, калі ўзоры карэлююць

Fu, MC, JQ Hu, CH Chen і X. Xiong, "Размеркаванне мадэлявання для вызначэння найлепшага дызайну пры наяўнасці карэляванай выбаркі", паведамляе Journal on Computing , Vol. 19, № 1, с. 101-111, 2007.

OCBA для мадэлявання і аптымізацыі

Zhang, S., J. Xu, LH Lee, EP Chew, WP Wong і CH Chen, "Optimal Computing Budget Allocation for Particle Swarm Optimization in Stochastic Optimization", IEEE Transactions on Evolutionary Computation , 21(2), 206-219 , 2017 год.

Нікалас, П., "Алгарытм раздзялення прастакутнікаў для аптымізацыі стахастычнага мадэлявання", Працы 14-й канферэнцыі вылічальнага грамадства INFORMS , Рычманд, штат Вірджынія, студзень 2015 г.

He, D., LH Lee, CH Chen, M. Fu і S. Wasserkrug , "Аптымізацыя мадэлявання з выкарыстаннем метаду крос-энтрапіі з аптымальным размеркаваннем бюджэту вылічэнняў", ACM Transactions on Modeling and Computer Simulation , 2009.

Чу, Э.П., Л.Х. Лі, С.Й. Тэнг і Ч.Х. Ко, "Аптымізацыя інвентарызацыі дыферэнцыраваных службаў з выкарыстаннем укладзеных раздзелаў і MOCBA", Кампутары і даследаванні аперацый , 36(5), : 1703-1710, 2009.

Lee, LH, EP Chew, SY Teng і YK Chen, "Эвалюцыйны алгарытм на аснове шматмэтавага мадэлявання для праблемы размеркавання запасных частак самалёта", Еўрапейскі часопіс аперацыйных даследаванняў , 189 (2): 476-491, 2008.

Shi, L. і CH Chen, "Новы алгарытм для стахастычнай дыскрэтнай аптымізацыі размеркавання рэсурсаў", Journal of Discrete Event Dynamic Systems: Theory and Applications , Vol. 10, стар. 271-294, ліпень 2000 г.

Прыкладанні OCBA

Се, Л., Э. Хуанг і Ч. Ч. Чэнь, "Павышэнне выкарыстання абсталявання ў галіне фоталітаграфіі праз дынамічнае кіраванне сістэмай з выкарыстаннем аптымізацыі мадэлявання з некалькімі дакладнасцямі з дапамогай тэхнікі вялікіх дадзеных", Рашэнне аб транзакцыях IEEE па вытворчасці паўправаднікоў, 30 (2) , 166 -175, 2017.

Арыстоцеліс, Т., М. Бастані, Н. Чэлік і Ч. Ч. Чэнь, "Сродак адаптыўнага мадэлявання на аснове дынамічных дадзеных для аўтаматызаванага кіравання ў мікрасетках", Транзакцыі IEEE па разумнай сетцы , 8(1), 209-218, 2017 .

Се, Л., Э. Хуанг, С. Чжан, К. Х. Чанг, К. Х. Чэнь, "Прымяненне мадэлявання Multi-Fidelity для ўпакоўкі інтэгральных схем", Міжнародны часопіс мадэлявання і мадэлявання працэсаў , 28 (2), 195-208, Вясна 2016 года.

Hsieh, BW, CH Chen, SC Chang, "Эфектыўнае мадэляванне на аснове кампазіцыі дыспетчарскіх палітык шляхам інтэграцыі парадкавай аптымізацыі з дызайнам эксперыменту", IEEE Transactions on Automation Science and Engineering , Vol. 4, № 4, стар. 553-568, кастрычнік 2007 г.

Рамэра, VJ, DV Ayon, CH Chen, "Дэманстрацыя канцэпцый імавернаснай парадкавай аптымізацыі для бесперапыннай зменнай аптымізацыі ва ўмовах нявызначанасці", Аптымізацыя і праектаванне , Vol. 7, № 3, стар. 343-365, верасень 2006 г.

Chen, CH, і D. He, "Інтэлектуальнае мадэляванне для параўнання альтэрнатыў і прымянення ў кіраванні паветраным рухам", Journal of System Science and System Engineering , Vol. 14, № 1, стар. 37-51, сакавік 2005 г.

Chen, CH, K. Donohue, E. Yucesan і J. Lin, "Аптымальнае размеркаванне вылічальнага бюджэту для мадэлявання Монтэ-Карла з прымяненнем да дызайну прадукту", Journal of Simulation Practice and Theory , Vol. 11, № 1, стар. 57-74, сакавік 2003 г.

Hsieh, BW, CH Chen і SC Chang, "Планаванне вырабу паўправадніковых пласцін з выкарыстаннем парадкавай аптымізацыі на аснове мадэлявання", IEEE Transactions on Robotics and Automation , Vol. 17, № 5, стар. 599-608, кастрычнік 2001 г.

Chen, CH, SD Wu і L. Dai, "Парадкавае параўнанне эўрыстычных алгарытмаў з выкарыстаннем стахастычнай аптымізацыі", IEEE Transactions on Robotics and Automation , Vol. 15, № 1, с. 44-56, люты 1999 г.

Асацыяцыя з парадкавай аптымізацыяй

Dai, L., CH Chen і JR Birge, "Вялікія ўласцівасці канвергенцыі двухэтапнага стахастычнага праграмавання", Journal of Optimization Theory and Applications , Vol. 106, № 3, стар. 489-510, верасень 2000 г.

Ho, YC, CG Cassandras, CH Chen і L. Dai, "Ordinal Optimization and Simulation", Journal of Operational Research Society , Vol. 51, № 4, стар. 490-500, красавік 2000 г.

Dai, L. і CH Chen, "Хуткасць канвергенцыі для парадкавага параўнання залежнага мадэлявання ў дыскрэтных падзеях дынамічных сістэм," Часопіс тэорыі аптымізацыі і прыкладанняў , Vol. 94, № 1, стар. 29-54, ліпень 1997 г.

Некаторыя іншыя абагульненні і звязаныя з імі працы

Blanchet, J., J. Liu, і B. Zwart, "Вялікія адхіленні Перспектыва парадкавай аптымізацыі сістэм з цяжкімі хвастамі", Працы зімовай канферэнцыі па мадэляванні 2007 г. , стар. 489-494, 2007.

Branke, J., SE Chick і C. Schmidt. Выбар працэдуры адбору. Навука кіравання 53 1916-1932, 2007.

Чык, С. і К. Іноуэ. Новыя двухэтапныя і паслядоўныя працэдуры выбару лепшай змадэляванай сістэмы. Даследаванне аперацый 49 1609-1624, 2001.

Чык, С. і К. Іноуэ. Новыя працэдуры выбару лепшай змадэляванай сістэмы з выкарыстаннем звычайных выпадковых лікаў. Навука кіравання 47 1133-1149, 2001.

Глін, П., С. Джунея. Перспектыва вялікіх адхіленняў пры парадкавай аптымізацыі. Працы зімовай канферэнцыі па мадэляванні 2004 г. , 577-585, 2004 г.

Pujowidianto, NA, LH Lee, CH Chen, CM Yep, "Optimal Computing Budget Allocation For Constrained Optimization", з'явіцца ў Proceedings of 2009 Winter Simulation Conference , pp. 584-589, Осцін, Тэхас, снежань 2009 г.

Trailovic , L. і LY Pao. 2004. Разлік размеркавання бюджэту для эфектыўнага ранжыравання і адбору адхіленняў з прымяненнем да мэтавых алгарытмаў адсочвання. IEEE Transactions on Automatic Control 49 58-67, 2004.

Кнігі OCBA

1.Новая кніга пра OCBA была апублікавана ў 2011 годзе. Назва кнігі - "Аптымізацыя стахастычнага мадэлявання: аптымальнае размеркаванне бюджэту вылічэнняў". Гэтая кніга дае поўнае і шырокае асвятленне гэтай эфектыўнай метадалогіі аптымізацыі мадэлявання, ад асноўнай ідэі, фармальнай распрацоўкі да сучаснага стану. Вы можаце замовіць яго на Amazon.com .

2.Яшчэ адна новая кніга, якая разглядае значна больш шырокую перспектыву парадкавай аптымізацыі, - " Аптымізацыя стахастычнага мадэлявання для сістэм з дыскрэтнымі падзеямі - аналіз абурэнняў, парадкавая аптымізацыя і не толькі " , апублікаваная ў 2013 годзе.

Кампутарныя зыходныя коды для OCBA

-Код OCBA C , які таксама змяшчаецца на старонках 214-218 кнігі OCBA .

-Код OCBA C++ , прадастаўлены прафесарам Нурчынам Чэлікам з Універсітэта Маямі

-Код OCBA JAVA , прадастаўлены прафесарам Нурчынам Чэлікам з Універсітэта Маямі

Дэманстрацыя OCBA (і код JAVA)

Дэманстрацыя OCBA з дапамогай вэб-браўзера . Гэта дэманстрацыя OCBA рэалізавана А. Джонсанам, Чэол Ю. Паркам і Нін Лінам. У дэманстрацыі вы ўбачыце, як OCBA дынамічна выбірае годныя праекты для далейшага мадэлявання.