Оптимізація на основі моделювання (також відома як оптимізація моделювання) інтегрує методи оптимізації в цифрове моделювання та аналіз. Через складність моделювання оцінка цільової функції (функції втрат) може стати дорогою та важкою. Зазвичай базова імітаційна модель є стохастичною, тому цільову функцію необхідно оцінити за допомогою методів статистичної оцінки (в методології моделювання називають вихідним аналізом).
Після того, як система змодельована математично, комп'ютерне моделювання надає інформацію про її поведінку. Для підвищення продуктивності системи використовують методи параметричного моделювання. У цьому методі введення кожної змінної варіюється, а інші параметри залишаються постійними, і спостерігається вплив на ціль проєктування. Це трудомісткий метод, який частково покращує продуктивність. Щоб отримати оптимальне рішення з мінімальними витратами часу та обчислень, завдання вирішується ітеративно, при цьому на кожній ітерації рішення наближається до оптимального. Такі методи відомі як «чисельна оптимізація» або «оптимізація на основі моделювання».
Ціль імітаційного експерименту полягає в тому, щоб оцінити вплив різних значень вхідних змінних на систему. Хоча іноді, інтерес полягає в тому, щоб знайти оптимальне значення для вхідних змінних з погляду результатів системи. Одним зі способів пошуку оптимального значення, може бути проведення експериментів з моделювання для всіх можливих вхідних змінних. Цей підхід не завжди є практичним через кілька можливих ситуацій, також цей підхід ускладнює проведення експериментів для кожного сценарію. Наприклад, імітаційна модель може бути занадто складною та дорогою для запуску при неоптимальних значеннях вхідних змінних або може бути занадто багато можливих значень для вхідних змінних. У цих випадках ціль полягає в тому, щоб знайти оптимальні значення для вхідних змінних, а не пробувати всі можливі значення. Цей процес називається оптимізацією моделювання.
Конкретні методи оптимізації, засновані на моделюванні, можуть бути обрані відповідно до рис. 1 на основі типів змінних рішень.
Оптимізація існує у двох основних галузях дослідження операцій:
Параметрична оптимізація (статична) — полягає в тому, щоб знайти значення параметрів, які є статичними для всіх станів та максимізують або мінімізують функцію. У цьому випадку можна використовувати математичне програмування, наприклад, лінійне програмування. У цьому сценарії симуляція допомагає, коли параметри містять шум або оцінка проблеми вимагатиме надмірного комп'ютерного часу через її складність.
Управління оптимізацією (динамічне) — в основному використовується в інформатиці та електротехніці. Оптимальне керування визначається для кожного стану і результати змінюються в кожному з них. Можна використовувати математичне програмування і динамічне. У цьому сценарії моделювання може генерувати випадкові вибірки, вирішувати складні та великомасштабні проблеми.
Методи оптимізації на основі моделювання
Деякі важливі підходи до оптимізації моделювання наводяться нижче.
Статистичний рейтинг і методи відбору (R/S)
Методи ранжування та відбору призначені для завдань, у яких альтернативи фіксовані та відомі, а моделювання використовується для оцінки продуктивності системи. У налаштуванні оптимізації моделювання, застосовні методи включають підходи зони байдужості, оптимальні розподілення бюджету обчислень та алгоритми градієнта знань.
Методологія поверхні реагування (RSM)
У методі Бокса-Вілсона (англ. Response surface methodology) мета полягає в тому, щоб знайти взаємозв'язок між вхідними змінними та змінними відгуку. Процес починається зі спроби підігнати модель лінійної регресії. Якщо P-значення виявиться низьким, буде реалізована поліноміальна регресія вищого ступеня, яка є квадратичною. Процес пошуку гарного співвідношення між вхідними змінними та змінними відгуку буде виконуватися для кожного тесту моделювання. При оптимізації моделювання можна використовувати метод поверхні відгуку, щоб знайти найкращі вхідні змінні, які дають бажані результати з погляду змінних відгуків.
Евристичні методи
Евристичні методи змінюють точність на швидкість. Їхня мета — знайти гарне рішення швидше, ніж традиційні методи, коли вони надто повільні або не можуть вирішити проблему. Зазвичай замість оптимального значення знаходять локальне оптимальне; однак значення вважаються досить близькими до остаточного рішення. Приклади таких методів є пошук табу та генетичні алгоритми.
Метамоделі дозволяють дослідникам отримувати надійні наближені результати моделей без проведення дорогих та трудомістких комп'ютерних симуляцій. Отже, процес оптимізації моделі може зайняти менше часу та витрат на обчислення.
Стохастичне наближення
[en] використовується коли функція не може бути обчислена безпосередньо, лише оцінена за допомогою шумних спостережень. У цих сценаріях метод (або сімейство методів) шукає екстремуми цих функцій. Цільова функція буде:
- є випадковою величиною, яка представляє шум;
- є параметром, який мінімізує ;
- є областю визначення параметра .
Методи оптимізації без похідних
Оптимізація без похідних застосовується до задачі оптимізації, коли її похідні відсутні або ненадійні. Методи, що не використовують похідні, створюють модель на основі значень вибіркових функцій або створюють вибірковий набір значень функцій без використання докладної моделі. Оскільки метод не використовує похідні, його не можна порівнювати з методами, заснованими на похідних.
Для задач оптимізації без обмежень він має вигляд:
Обмеження оптимізації без похідних:
1. Деякі методи не можуть впоратися з завданнями оптимізації з більш ніж кількома змінними; результати зазвичай не такі точні. З усім тим, існує безліч практичних випадків, коли методи без похідних були успішними у нетривіальних задачах оптимізації моделювання, які включають випадковість, що виявляється як «шум» у цільовій функції. Наприклад, .
2. Зіткнувшись із мінімізацією невипуклих функцій, він покаже свої обмеження.
3. Методи оптимізації без похідних відносно прості й легкі, але, як і для більшості методів оптимізації, при практичної реалізації (наприклад, при виборі параметрів алгоритму) потрібна певна обережність.
Динамічне програмування та нейродинамічне програмування
Динамічне програмування
Динамічне програмування має справу з ситуаціями, коли рішення ухвалюються поетапно. Ключ до вирішення таких проблем — знайти компроміс між поточними та майбутніми витратами.
Одна динамічна базова модель має дві особливості:
1) Вона має дискретну динамічну систему за часом.
2) Функція вартості є адитивною з часом.
Для дискретних функцій динамічне програмування має вигляд:
- є індекс дискретного часу.
- це стан часу k, що містить інформацію минулого і готує її до майбутньої оптимізації.
- є контрольною змінною.
- є випадковим параметром.
Для функції вартості вона має вигляд:
це вартість у кінці процесу.
Оскільки вартість не може бути оптимізована суттєво, можна використовувати очікуване значення:
Нейродинамічне програмування
Нейродинамічне програмування аналогічне динамічному програмуванню, за винятком того, що перше має концепцію апроксимаційних архітектур. Метод поєднує в собі штучний інтелект, алгоритми на основі моделювання та методи функціонального підходу. «Нейро» в цьому терміні походить від спільноти штучного інтелекту. Це означає навчитися приймати покращені рішення на майбутнє за допомогою вбудованого механізму, що базується на поточній поведінці. Найважливіша частина нейродинамічного програмування — це побудова навченої нейромережі для вирішення оптимальної задачі.
Обмеження
Оптимізація на основі моделювання має деякі обмеження, такі як складність створення моделі, яка імітує динамічну поведінку системи таким чином, який вважається досить добрим для її представлення. Інша проблема — складність визначення неконтрольованих параметрів як реальної системи, так і моделі. На додаток, можна отримати лише статистичну оцінку реальних значень. Визначити цільову функцію непросто, оскільки вона є результатом вимірювань, що впливає на розв'язки.
Посилання
- Nguyen, Anh-Tuan, Sigrid Reiter, and Philippe Rigo. «A review on simulation-based optimization methods applied to building performance analysis.»Applied Energy 113 (2014): 1043—1058.
- Carson, Yolanda, and Anu Maria. «Simulation optimization: methods and applications.» Proceedings of the 29th Winter Simulation Conference. IEEE Computer Society, 1997.
- Jalali, Hamed, and Inneke Van Nieuwenhuyse. «Simulation optimization in inventory replenishment: a classification [ 2021-12-23 у Wayback Machine.].» IIE Transactions 47.11 (2015): 1217—1235.
- Abhijit Gosavi, Simulation‐Based Optimization: Parametric Optimization Techniques and Reinforcement Learning, Springer, 2nd Edition (2015)
- Fu, Michael, editor (2015). Handbook of Simulation Optimization. Springer.
- Spall, J.C. (2003). Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. Hoboken: Wiley.
- Rahimi Mazrae Shahi, M., Fallah Mehdipour, E. and Amiri, M. (2016), Optimization using simulation and response surface methodology with an application on subway train scheduling. Intl. Trans. in Op. Res., 23: 797—811. DOI:10.1111/itor.12150
- Yousefi, Milad; Yousefi, Moslem; Ferreira, Ricardo Poley Martins; Kim, Joong Hoon; Fogliatto, Flavio S. (2018). Chaotic genetic algorithm and Adaboost ensemble metamodeling approach for optimum resource planning in emergency departments. Artificial Intelligence in Medicine. 84: 23—33. doi:10.1016/j.artmed.2017.10.002. PMID 29054572.
- Powell, W. (2011). Approximate Dynamic Programming Solving the Curses of Dimensionality (2nd ed., Wiley Series in Probability and Statistics). Hoboken: Wiley.
- Conn, A. R.; ; Vicente, L. N. (2009). Introduction to Derivative-Free Optimization. MPS-SIAM Book Series on Optimization. Philadelphia: SIAM. Retrieved 2014-01-18.
- Fu, M.C., Hill, S.D. Optimization of discrete event systems via simultaneous perturbation stochastic approximation. IIE Transactions 29, 233—243 (1997). https://doi.org/10.1023/A:1018523313043
- Cooper, Leon; Cooper, Mary W. Introduction to dynamic programming. New York: Pergamon Press, 1981
- Van Roy, B., Bertsekas, D., Lee, Y., & (1997). Neuro-dynamic programming approach to retailer inventory management. Proceedings of the IEEE Conference on Decision and Control, 4, 4052-4057.
- Prasetio, Y. (2005). Simulation-based optimization for complex stochastic systems. University of Washington.
- Deng, G., & Ferris, Michael. (2007). Simulation-based Optimization, ProQuest Dissertations and Theses
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Optimizaciya na osnovi modelyuvannya takozh vidoma yak optimizaciya modelyuvannya integruye metodi optimizaciyi v cifrove modelyuvannya ta analiz Cherez skladnist modelyuvannya ocinka cilovoyi funkciyi funkciyi vtrat mozhe stati dorogoyu ta vazhkoyu Zazvichaj bazova imitacijna model ye stohastichnoyu tomu cilovu funkciyu neobhidno ociniti za dopomogoyu metodiv statistichnoyi ocinki v metodologiyi modelyuvannya nazivayut vihidnim analizom Pislya togo yak sistema zmodelovana matematichno komp yuterne modelyuvannya nadaye informaciyu pro yiyi povedinku Dlya pidvishennya produktivnosti sistemi vikoristovuyut metodi parametrichnogo modelyuvannya U comu metodi vvedennya kozhnoyi zminnoyi variyuyetsya a inshi parametri zalishayutsya postijnimi i sposterigayetsya vpliv na cil proyektuvannya Ce trudomistkij metod yakij chastkovo pokrashuye produktivnist Shob otrimati optimalne rishennya z minimalnimi vitratami chasu ta obchislen zavdannya virishuyetsya iterativno pri comu na kozhnij iteraciyi rishennya nablizhayetsya do optimalnogo Taki metodi vidomi yak chiselna optimizaciya abo optimizaciya na osnovi modelyuvannya Ris 1 Klasifikaciya optimizaciyi na osnovi modelyuvannya za tipami zminnih Cil imitacijnogo eksperimentu polyagaye v tomu shob ociniti vpliv riznih znachen vhidnih zminnih na sistemu Hocha inodi interes polyagaye v tomu shob znajti optimalne znachennya dlya vhidnih zminnih z poglyadu rezultativ sistemi Odnim zi sposobiv poshuku optimalnogo znachennya mozhe buti provedennya eksperimentiv z modelyuvannya dlya vsih mozhlivih vhidnih zminnih Cej pidhid ne zavzhdi ye praktichnim cherez kilka mozhlivih situacij takozh cej pidhid uskladnyuye provedennya eksperimentiv dlya kozhnogo scenariyu Napriklad imitacijna model mozhe buti zanadto skladnoyu ta dorogoyu dlya zapusku pri neoptimalnih znachennyah vhidnih zminnih abo mozhe buti zanadto bagato mozhlivih znachen dlya vhidnih zminnih U cih vipadkah cil polyagaye v tomu shob znajti optimalni znachennya dlya vhidnih zminnih a ne probuvati vsi mozhlivi znachennya Cej proces nazivayetsya optimizaciyeyu modelyuvannya Konkretni metodi optimizaciyi zasnovani na modelyuvanni mozhut buti obrani vidpovidno do ris 1 na osnovi tipiv zminnih rishen Optimizaciya isnuye u dvoh osnovnih galuzyah doslidzhennya operacij Parametrichna optimizaciya statichna polyagaye v tomu shob znajti znachennya parametriv yaki ye statichnimi dlya vsih staniv ta maksimizuyut abo minimizuyut funkciyu U comu vipadku mozhna vikoristovuvati matematichne programuvannya napriklad linijne programuvannya U comu scenariyi simulyaciya dopomagaye koli parametri mistyat shum abo ocinka problemi vimagatime nadmirnogo komp yuternogo chasu cherez yiyi skladnist Upravlinnya optimizaciyeyu dinamichne v osnovnomu vikoristovuyetsya v informatici ta elektrotehnici Optimalne keruvannya viznachayetsya dlya kozhnogo stanu i rezultati zminyuyutsya v kozhnomu z nih Mozhna vikoristovuvati matematichne programuvannya i dinamichne U comu scenariyi modelyuvannya mozhe generuvati vipadkovi vibirki virishuvati skladni ta velikomasshtabni problemi Metodi optimizaciyi na osnovi modelyuvannyaDeyaki vazhlivi pidhodi do optimizaciyi modelyuvannya navodyatsya nizhche Statistichnij rejting i metodi vidboru R S Metodi ranzhuvannya ta vidboru priznacheni dlya zavdan u yakih alternativi fiksovani ta vidomi a modelyuvannya vikoristovuyetsya dlya ocinki produktivnosti sistemi U nalashtuvanni optimizaciyi modelyuvannya zastosovni metodi vklyuchayut pidhodi zoni bajduzhosti optimalni rozpodilennya byudzhetu obchislen ta algoritmi gradiyenta znan Metodologiya poverhni reaguvannya RSM U metodi Boksa Vilsona angl Response surface methodology meta polyagaye v tomu shob znajti vzayemozv yazok mizh vhidnimi zminnimi ta zminnimi vidguku Proces pochinayetsya zi sprobi pidignati model linijnoyi regresiyi Yaksho P znachennya viyavitsya nizkim bude realizovana polinomialna regresiya vishogo stupenya yaka ye kvadratichnoyu Proces poshuku garnogo spivvidnoshennya mizh vhidnimi zminnimi ta zminnimi vidguku bude vikonuvatisya dlya kozhnogo testu modelyuvannya Pri optimizaciyi modelyuvannya mozhna vikoristovuvati metod poverhni vidguku shob znajti najkrashi vhidni zminni yaki dayut bazhani rezultati z poglyadu zminnih vidgukiv Evristichni metodi Evristichni metodi zminyuyut tochnist na shvidkist Yihnya meta znajti garne rishennya shvidshe nizh tradicijni metodi koli voni nadto povilni abo ne mozhut virishiti problemu Zazvichaj zamist optimalnogo znachennya znahodyat lokalne optimalne odnak znachennya vvazhayutsya dosit blizkimi do ostatochnogo rishennya Prikladi takih metodiv ye poshuk tabu ta genetichni algoritmi Metamodeli dozvolyayut doslidnikam otrimuvati nadijni nablizheni rezultati modelej bez provedennya dorogih ta trudomistkih komp yuternih simulyacij Otzhe proces optimizaciyi modeli mozhe zajnyati menshe chasu ta vitrat na obchislennya Stohastichne nablizhennya en vikoristovuyetsya koli funkciya ne mozhe buti obchislena bezposeredno lishe ocinena za dopomogoyu shumnih sposterezhen U cih scenariyah metod abo simejstvo metodiv shukaye ekstremumi cih funkcij Cilova funkciya bude min x 8 f x min x 8 E F x y displaystyle underset text x in theta min f bigl text x bigr underset text x in theta min mathrm E F bigl text x y y displaystyle y ye vipadkovoyu velichinoyu yaka predstavlyaye shum x displaystyle x ye parametrom yakij minimizuye f x displaystyle f bigl text x bigr 8 displaystyle theta ye oblastyu viznachennya parametra x displaystyle x Metodi optimizaciyi bez pohidnih Optimizaciya bez pohidnih zastosovuyetsya do zadachi optimizaciyi koli yiyi pohidni vidsutni abo nenadijni Metodi sho ne vikoristovuyut pohidni stvoryuyut model na osnovi znachen vibirkovih funkcij abo stvoryuyut vibirkovij nabir znachen funkcij bez vikoristannya dokladnoyi modeli Oskilki metod ne vikoristovuye pohidni jogo ne mozhna porivnyuvati z metodami zasnovanimi na pohidnih Dlya zadach optimizaciyi bez obmezhen vin maye viglyad min x R n f x displaystyle underset text x in mathbb R n min f bigl text x bigr Obmezhennya optimizaciyi bez pohidnih 1 Deyaki metodi ne mozhut vporatisya z zavdannyami optimizaciyi z bilsh nizh kilkoma zminnimi rezultati zazvichaj ne taki tochni Z usim tim isnuye bezlich praktichnih vipadkiv koli metodi bez pohidnih buli uspishnimi u netrivialnih zadachah optimizaciyi modelyuvannya yaki vklyuchayut vipadkovist sho viyavlyayetsya yak shum u cilovij funkciyi Napriklad 2 Zitknuvshis iz minimizaciyeyu nevipuklih funkcij vin pokazhe svoyi obmezhennya 3 Metodi optimizaciyi bez pohidnih vidnosno prosti j legki ale yak i dlya bilshosti metodiv optimizaciyi pri praktichnoyi realizaciyi napriklad pri vibori parametriv algoritmu potribna pevna oberezhnist Dinamichne programuvannya ta nejrodinamichne programuvannya Dinamichne programuvannya Dinamichne programuvannya maye spravu z situaciyami koli rishennya uhvalyuyutsya poetapno Klyuch do virishennya takih problem znajti kompromis mizh potochnimi ta majbutnimi vitratami Odna dinamichna bazova model maye dvi osoblivosti 1 Vona maye diskretnu dinamichnu sistemu za chasom 2 Funkciya vartosti ye aditivnoyu z chasom Dlya diskretnih funkcij dinamichne programuvannya maye viglyad x k 1 f k x k u k w k k 0 1 N 1 displaystyle x k 1 f k x k u k w k k 0 1 N 1 k displaystyle k ye indeks diskretnogo chasu x k displaystyle x k ce stan chasu k sho mistit informaciyu minulogo i gotuye yiyi do majbutnoyi optimizaciyi u k displaystyle u k ye kontrolnoyu zminnoyu w k displaystyle w k ye vipadkovim parametrom Dlya funkciyi vartosti vona maye viglyad g N X N k 0 N 1 g k x k u k W k displaystyle g N X N sum k 0 N 1 g k x k u k W k g N X N displaystyle g N X N ce vartist u kinci procesu Oskilki vartist ne mozhe buti optimizovana suttyevo mozhna vikoristovuvati ochikuvane znachennya E g N X N k 0 N 1 g k x k u k W k displaystyle E g N X N sum k 0 N 1 g k x k u k W k Nejrodinamichne programuvannya Nejrodinamichne programuvannya analogichne dinamichnomu programuvannyu za vinyatkom togo sho pershe maye koncepciyu aproksimacijnih arhitektur Metod poyednuye v sobi shtuchnij intelekt algoritmi na osnovi modelyuvannya ta metodi funkcionalnogo pidhodu Nejro v comu termini pohodit vid spilnoti shtuchnogo intelektu Ce oznachaye navchitisya prijmati pokrasheni rishennya na majbutnye za dopomogoyu vbudovanogo mehanizmu sho bazuyetsya na potochnij povedinci Najvazhlivisha chastina nejrodinamichnogo programuvannya ce pobudova navchenoyi nejromerezhi dlya virishennya optimalnoyi zadachi ObmezhennyaOptimizaciya na osnovi modelyuvannya maye deyaki obmezhennya taki yak skladnist stvorennya modeli yaka imituye dinamichnu povedinku sistemi takim chinom yakij vvazhayetsya dosit dobrim dlya yiyi predstavlennya Insha problema skladnist viznachennya nekontrolovanih parametriv yak realnoyi sistemi tak i modeli Na dodatok mozhna otrimati lishe statistichnu ocinku realnih znachen Viznachiti cilovu funkciyu neprosto oskilki vona ye rezultatom vimiryuvan sho vplivaye na rozv yazki PosilannyaNguyen Anh Tuan Sigrid Reiter and Philippe Rigo A review on simulation based optimization methods applied to building performance analysis Applied Energy 113 2014 1043 1058 Carson Yolanda and Anu Maria Simulation optimization methods and applications Proceedings of the 29th Winter Simulation Conference IEEE Computer Society 1997 Jalali Hamed and Inneke Van Nieuwenhuyse Simulation optimization in inventory replenishment a classification 2021 12 23 u Wayback Machine IIE Transactions 47 11 2015 1217 1235 Abhijit Gosavi Simulation Based Optimization Parametric Optimization Techniques and Reinforcement Learning Springer 2nd Edition 2015 Fu Michael editor 2015 Handbook of Simulation Optimization Springer Spall J C 2003 Introduction to Stochastic Search and Optimization Estimation Simulation and Control Hoboken Wiley Rahimi Mazrae Shahi M Fallah Mehdipour E and Amiri M 2016 Optimization using simulation and response surface methodology with an application on subway train scheduling Intl Trans in Op Res 23 797 811 DOI 10 1111 itor 12150 Yousefi Milad Yousefi Moslem Ferreira Ricardo Poley Martins Kim Joong Hoon Fogliatto Flavio S 2018 Chaotic genetic algorithm and Adaboost ensemble metamodeling approach for optimum resource planning in emergency departments Artificial Intelligence in Medicine 84 23 33 doi 10 1016 j artmed 2017 10 002 PMID 29054572 Powell W 2011 Approximate Dynamic Programming Solving the Curses of Dimensionality 2nd ed Wiley Series in Probability and Statistics Hoboken Wiley Conn A R Vicente L N 2009 Introduction to Derivative Free Optimization MPS SIAM Book Series on Optimization Philadelphia SIAM Retrieved 2014 01 18 Fu M C Hill S D Optimization of discrete event systems via simultaneous perturbation stochastic approximation IIE Transactions 29 233 243 1997 https doi org 10 1023 A 1018523313043 Cooper Leon Cooper Mary W Introduction to dynamic programming New York Pergamon Press 1981 Van Roy B Bertsekas D Lee Y amp 1997 Neuro dynamic programming approach to retailer inventory management Proceedings of the IEEE Conference on Decision and Control 4 4052 4057 Prasetio Y 2005 Simulation based optimization for complex stochastic systems University of Washington Deng G amp Ferris Michael 2007 Simulation based Optimization ProQuest Dissertations and Theses