Вестник БГУ. Математика, информатика
Библиографическое описание:
ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ ГИБРИДНОГО АЛГОРИТМА ГЛОБАЛЬНОГО ПОИСКА В ГЕКСАМАТРИЧНЫХ ИГРАХ // Вестник БГУ. Математика, информатика. - 2023. №2. . - С. 14-29.
Заглавие:
ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ ГИБРИДНОГО АЛГОРИТМА ГЛОБАЛЬНОГО ПОИСКА В ГЕКСАМАТРИЧНЫХ ИГРАХ
Финансирование:
Работа выполнена в рамках базового проекта фундаментальных исследо- ваний Минобрнауки РФ «Теоретические основы, методы и высокопроизводи- тельные алгоритмы непрерывной и дискретной оптимизации для поддержки междисциплинарных научных исследований» (Номер гос. регистрации: 121041300065-9, код проекта FWEW-2021-0003).
Коды:
Аннотация:
В статье представлен гибридный подход к разработке мето- дов отыскания ситуаций равновесия по Нэшу в полиматричных играх трех лиц (гексаматричных играх). С одной стороны, он базируется на теории гло- бального поиска в невыпуклых задачах оптимизации c d.c. функциями (пред- ставимыми в виде разности двух выпуклых функций), созданной А. С. Стре- каловским, с другой - для реализации одного из ключевых этапов глобаль- ного поиска (построения аппроксимации поверхности уровня) используют- ся операторы генетических алгоритмов. После описания гибридного подхо- да подробно рассказывается об организации и проведении вычислительного эксперимента по сравнению гибридного алгоритма с «базовым» алгоритмом глобального поиска, разработанным ранее. Приведены результаты экспери- мента на сериях случайно сгенерированных задач, свидетельствующие об эф- фективности предложенного гибридного подхода к решению гексаматричных игр.
Ключевые слова:
полиматричные игры трех лиц, гексаматричные игры, равновесие Нэша, теория глобального поиска, локальный поиск, алгоритм глобального поиска, аппроксимация поверхности уровня, генетические операторы, гибридный алгоритм, вычислительный эксперимент.
Список литературы:
Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. Москва: Высш. школа, 1998. 304 c. Текст: непосредственный.
Pang J.-S. Three modeling paradigms in mathematical programming // Mathematical Programming, Ser. B. 2010. Vol. 124, №2. P. 297–323. DOI: 10.1007/s10107-010-0395-1.
Орлов А. В., Стрекаловский А. С. О поиске ситуаций равновесия в би- матричных играх // Автоматика и телемеханика. 2004. № 2. С. 55–68. Текст: непосредственный.
Стрекаловский А. С., Орлов А. В. Биматричные игры и билинейное программирование. Москва: ФИЗМАТЛИТ, 2007. 224 c. Текст: непосред- ственный.
Стрекаловский А. С., Энхбат Р. Полиматричные игры и задачи оп- тимизации // Автоматика и телемеханика. 2014. № 4. С. 51–66. DOI: 10.1134/S0005117914040043. Текст: непосредственный.
Орлов А. В., Батбилэг С. Олигополистический банковский сектор Мон- голии и полиматричные игры трех лиц // Известия Иркутского государ- ственного университета. Сер. Математика. 2015. Т. 11. С. 80–95. Текст: непосредственный.
Orlov A. V., Strekalovsky A. S., Batbileg S. On computational search for Nash equilibrium in hexamatrix games // Optimization Letters. 2016. V. 10(2). P. 369–381. DOI: 10.1007/s11590-014-0833-8.
Orlov A. V. Finding the Nash equilibria in randomly generated hexamatrix games // Proc. of the 14th Intern. Symposium on Operational Research (SOR’17, Bled, Slovenia, September 27-29, 2017) / Ed. by L. Zadnik Stirn et. al. Ljubljana: Slovenian Society Informatika, Section for Operational Research, 2017. P. 507–512.
Strekalovsky A. S. On Solving Optimization Problems with Hidden Nonconvex Structures // Optimization in Science and Engineering / Ed. by T.M. Rassias et al. New-York: Springer, 2014. P. 465–502. DOI: 10.1007/978- 1-4939-0808-0_23.
Strekalovsky A. S. On a Global Search in D.C. Optimization Problems // Optimization and Applications. OPTIMA 2019. Communications in Computer and Information Science / Ed. by M. Jacimovic et al. Cham: Springer, 2020. V. 1145. P. 222–236. DOI: 10.1007/978-3-030-38603-0_17.
Васильев Ф. П. Методы оптимизации. Москва: Факториал-пресс, 2002. 824 c. Текст: непосредственный.
Bonnans J.-F., Gilbert J. C., Lemarechal C., Sagastizabal C. A. Numerical optimization: theoretical and practical aspects. Berlin-Heidelberg: Springer, 2006. 494 p.
Стрекаловский А. С., Орлов А. В. Линейные и квадратично-линейные задачи двухуровневой оптимизации. Новосибирск: Изд-во СО РАН, 2019. 262 c. Текст: непосредственный.
Orlov A. V. The global search theory approach to the bilevel pricing problem in telecommunication networks // Computational Aspects and Applications in Large Scale Networks / Ed. by V.A. Kalyagin et al. Cham: Springer, 2018. P. 57–73. DOI: 10.1007/978-3-319-96247-4_5
Strekalovsky A. S., Orlov A. V. Global Search for Bilevel Optimization with Quadratic Data // Springer Optimization and Its Applications. Bilevel optimization: advances and next challenges / Ed. by S. Dempe, A. Zemkoho. Cham: Springer, 2020. V. 161. P. 313–334. DOI: 10.1007/978-3-030-52119- 6_11
Audet C., Belhaiza S., Hansen, P. Enumeration of all the extreme equilibria in game theory: bimatrix and polymatrix games // Journal of Optimization Theory and Applications. 2006. Vol. 129, № 3. P. 349–372.
Golshteyn E., Malkov U., Sokolov N. The Lemke-Howson Algorithm Solving Finite Non-Cooperative Three-Person Games in a Special Setting // DEStech Transactions on Computer Science and Engineering. 2019. Suppl. vol. P. 265– 272.
Orlov A. V. Hybrid Global Search Algorithm with Genetic Blocks for Solving Hexamatrix Games // Известия Иркутского государственного универ- ситета. Серия Математика. 2022. Т. 41. C. 40–56. DOI: 10.26516/1997- 7670.2022.41.40.
Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. New York: Springer-Verlag, 1994. 340 p.
Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. Москва: ФИЗМАТЛИТ, 2010. 368 c. Текст: непосредственный.
Орлов А. В. Гибридный генетический алгоритм глобального поиска опти- мистических решений в задачах двухуровневой оптимизации // Вестник Бурятского гос. ун-та. 2013. Вып. 9. С. 25–32. Текст: непосредственный.
Orlov A. V., Strekalovsky A. S. On a Local Search for Hexamatrix Games // CEUR Workshop Proceedings. DOOR-SUP 2016. 2016. V. 1623. P. 477–488. https://ceur-ws.org/Vol-1623/
Pang J.-S. Three modeling paradigms in mathematical programming // Mathematical Programming, Ser. B. 2010. Vol. 124, №2. P. 297–323. DOI: 10.1007/s10107-010-0395-1.
Орлов А. В., Стрекаловский А. С. О поиске ситуаций равновесия в би- матричных играх // Автоматика и телемеханика. 2004. № 2. С. 55–68. Текст: непосредственный.
Стрекаловский А. С., Орлов А. В. Биматричные игры и билинейное программирование. Москва: ФИЗМАТЛИТ, 2007. 224 c. Текст: непосред- ственный.
Стрекаловский А. С., Энхбат Р. Полиматричные игры и задачи оп- тимизации // Автоматика и телемеханика. 2014. № 4. С. 51–66. DOI: 10.1134/S0005117914040043. Текст: непосредственный.
Орлов А. В., Батбилэг С. Олигополистический банковский сектор Мон- голии и полиматричные игры трех лиц // Известия Иркутского государ- ственного университета. Сер. Математика. 2015. Т. 11. С. 80–95. Текст: непосредственный.
Orlov A. V., Strekalovsky A. S., Batbileg S. On computational search for Nash equilibrium in hexamatrix games // Optimization Letters. 2016. V. 10(2). P. 369–381. DOI: 10.1007/s11590-014-0833-8.
Orlov A. V. Finding the Nash equilibria in randomly generated hexamatrix games // Proc. of the 14th Intern. Symposium on Operational Research (SOR’17, Bled, Slovenia, September 27-29, 2017) / Ed. by L. Zadnik Stirn et. al. Ljubljana: Slovenian Society Informatika, Section for Operational Research, 2017. P. 507–512.
Strekalovsky A. S. On Solving Optimization Problems with Hidden Nonconvex Structures // Optimization in Science and Engineering / Ed. by T.M. Rassias et al. New-York: Springer, 2014. P. 465–502. DOI: 10.1007/978- 1-4939-0808-0_23.
Strekalovsky A. S. On a Global Search in D.C. Optimization Problems // Optimization and Applications. OPTIMA 2019. Communications in Computer and Information Science / Ed. by M. Jacimovic et al. Cham: Springer, 2020. V. 1145. P. 222–236. DOI: 10.1007/978-3-030-38603-0_17.
Васильев Ф. П. Методы оптимизации. Москва: Факториал-пресс, 2002. 824 c. Текст: непосредственный.
Bonnans J.-F., Gilbert J. C., Lemarechal C., Sagastizabal C. A. Numerical optimization: theoretical and practical aspects. Berlin-Heidelberg: Springer, 2006. 494 p.
Стрекаловский А. С., Орлов А. В. Линейные и квадратично-линейные задачи двухуровневой оптимизации. Новосибирск: Изд-во СО РАН, 2019. 262 c. Текст: непосредственный.
Orlov A. V. The global search theory approach to the bilevel pricing problem in telecommunication networks // Computational Aspects and Applications in Large Scale Networks / Ed. by V.A. Kalyagin et al. Cham: Springer, 2018. P. 57–73. DOI: 10.1007/978-3-319-96247-4_5
Strekalovsky A. S., Orlov A. V. Global Search for Bilevel Optimization with Quadratic Data // Springer Optimization and Its Applications. Bilevel optimization: advances and next challenges / Ed. by S. Dempe, A. Zemkoho. Cham: Springer, 2020. V. 161. P. 313–334. DOI: 10.1007/978-3-030-52119- 6_11
Audet C., Belhaiza S., Hansen, P. Enumeration of all the extreme equilibria in game theory: bimatrix and polymatrix games // Journal of Optimization Theory and Applications. 2006. Vol. 129, № 3. P. 349–372.
Golshteyn E., Malkov U., Sokolov N. The Lemke-Howson Algorithm Solving Finite Non-Cooperative Three-Person Games in a Special Setting // DEStech Transactions on Computer Science and Engineering. 2019. Suppl. vol. P. 265– 272.
Orlov A. V. Hybrid Global Search Algorithm with Genetic Blocks for Solving Hexamatrix Games // Известия Иркутского государственного универ- ситета. Серия Математика. 2022. Т. 41. C. 40–56. DOI: 10.26516/1997- 7670.2022.41.40.
Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. New York: Springer-Verlag, 1994. 340 p.
Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. Москва: ФИЗМАТЛИТ, 2010. 368 c. Текст: непосредственный.
Орлов А. В. Гибридный генетический алгоритм глобального поиска опти- мистических решений в задачах двухуровневой оптимизации // Вестник Бурятского гос. ун-та. 2013. Вып. 9. С. 25–32. Текст: непосредственный.
Orlov A. V., Strekalovsky A. S. On a Local Search for Hexamatrix Games // CEUR Workshop Proceedings. DOOR-SUP 2016. 2016. V. 1623. P. 477–488. https://ceur-ws.org/Vol-1623/
Статья.pdf