Численное исследование гибридного алгоритма глобального поиска в гексаматричных играх
Автор: Орлов А.В.
Журнал: Вестник Бурятского государственного университета. Математика, информатика @vestnik-bsu-maths
Рубрика: Вычислительная математика
Статья в выпуске: 2, 2023 года.
Бесплатный доступ
В статье представлен гибридный подход к разработке методов отыскания ситуаций равновесия по Нэшу в полиматричных играх трех лиц (гексаматричных играх). С одной стороны, он базируется на теории глобального поиска в невыпуклых задачах оптимизации с d.c. функциями (представимыми в виде разности двух выпуклых функций), созданной А. С. Стрекаловским, с другой - для реализации одного из ключевых этапов глобального поиска (построения аппроксимации поверхности уровня) используются операторы генетических алгоритмов. После описания гибридного подхода подробно рассказывается об организации и проведении вычислительного эксперимента по сравнению гибридного алгоритма с «базовым» алгоритмом глобального поиска, разработанным ранее. Приведены результаты эксперимента на сериях случайно сгенерированных задач, свидетельствующие об эффективности предложенного гибридного подхода к решению гексаматричных игр.
Полиматричные игры трех лиц, гексаматричные игры, равновесие нэша, теория глобального поиска, локальный поиск, алгоритм глобального поиска, аппроксимация поверхности уровня, генетические операторы, гибридный алгоритм, вычислительный эксперимент
Короткий адрес: https://sciup.org/148327258
IDR: 148327258 | DOI: 10.18101/2304-5728-2023-2-14-29
Список литературы Численное исследование гибридного алгоритма глобального поиска в гексаматричных играх
- Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. Москва: Высш. школа, 1998. 304 с. Текст: непосредственный.
- 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 с. Текст: непосредственный.
- Стрекаловский А. С., Энхбат Р. Полиматричные игры и задачи оптимизации // Автоматика и телемеханика. 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 с. Текст: непосредственный.
- 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. 265272.
- Orlov A. V. Hybrid Global Search Algorithm with Genetic Blocks for Solving Hexamatrix Games // Известия Иркутского государственного университета. Серия Математика. 2022. Т. 41. C. 40-56. DOI: 10.26516/19977670.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/
