Численное исследование гибридного алгоритма глобального поиска в гексаматричных играх

Численное нахождение равновесий в теории игр [1] является одной из актуальных проблем современной математической оптимизации [2], когда поиск равновесия может быть сведен к экстремальной задаче. Известно, что классическая матричная игра эквивалентна двум двойственным задачам линейного программирования (ЛП) [1]. Это означает, что такая игра имеет выпуклую структуру и принципиальных трудностей с ее решением не возникает. Первым расширением матричной игры является биматричная игра, которая уже представляет собой невыпуклую (билинейную) структуру [1, 3, 4]. То же самое можно сказать и о полиматричных играх [5]. Например, поиск равновесия по Нэшу в полиматричной игре трех лиц оказывается эквивалентным специальной задаче невыпуклой оптимизации с тройной билинейной структурой в целевой функции [5–8].

В нашей группе разработан оптимизационный подход к численному нахождению равновесий Нэша в таких играх, основанный на этой эквивалентности [4, 5]. При этом получающиеся оптимизационные задачи решаются с помощью теории глобального поиска (ТГП), созданной А. С. Стрекаловским для невыпуклых задач с d.c. функциями, представимыми в виде разности двух выпуклых функций [9, 10]. Одной из особенностей ТГП является возможность применения внутри алгоритмов достижений современной выпуклой оптимизации (см., например [11, 12]).

Одним из важнейших этапов при использовании ТГП [9,10] является построение аппроксимации поверхности уровня выпуклой функции, задающей базовую невыпуклость в исследуемой задаче (см. также [4,13]). Например, в ходе решения следующей задачи d.c. максимизации:

Ф(х) 4 h(x) — g(x) t max, x G S, (DC )

где g( - ), h0 — выпуклые функции, S — выпуклое множество, необходимо построить конечную аппроксимацию

A(Z, €) = {v ¹ ,..., v N | h (v i ) = € + Z, r = 1,...,N} , (1) где inf(g, S ) <  € <  sup(g, S ) фиксировано, Z ⁴ Ф(z ) — значение целевой функции задачи ( DC ) в текущей стационарной (критической) точке z. При этом аппроксимация (1) должна быть достаточно репрезентативной, чтобы можно было определить, является ли текущая точка z глобальным решением. Подробнее см. в [4, 9, 10, 13].

В настоящее время не существует общих подходов к построению репрезентативных аппроксимаций для задачи (DC). При решении конкретных невыпуклых задач решение этого вопроса основывается на накопленном численном опыте [4, 9, 13–15]. Поэтому разработка новых подходов к построению аппроксимаций является актуальной проблемой невыпуклой оптимизации. При этом алгоритмы глобального поиска (АГП), основанные на ТГП, оказываются весьма эффективными для биматричных игр высокой размерности (с плотными матрицами до 1000 стратегий у одного игрока) [4], в то же время решение гекса-матричных игр с помощью АГП ограничивается разреженными матрицами размера (100 х 100) [8].

Поиск ситуации равновесия в гексаматричных играх исследовался и другими авторами. Например, в основе подхода из [16] лежит редукция подобных игр к задачам смешанной непрерывно-целочисленной оптимизации (были решены игры до размерности 13 стратегий у каждого из игроков). А в [17] предложена специальная модификация классического метода Лемке-Хаусона (см., например, [4]) в сочетании с так называемым 3LP-методом, родственным методу локального поиска, который используется в настоящей работе (решены игры вплоть до 500 стратегий у одного игрока).

В данной работе проводится численное исследование гибридного алгоритма глобального поиска (ГАГП) в гексаматричных играх, разработанного в [18], где для построения аппроксимаций поверхности уровня используются операторы генетических алгоритмов (ГА) [19, 20]. Впервые подобная идея была применена для решения простейших двухуровневых задач в [21]. При этом как в [21], так и в [18] было решено только несколько простейших тестовых задач, а вопрос об общей эффективности подхода при решении большого количества задач различной сложности и размерности оставался открытым. Здесь мы представляем детализацию гибридного алгоритма и результаты его тестирования на широком спектре случайно сгенерированных гексаматричных игр.

1 Постановка задачи и ее редукция

Кратко напомним постановку гексаматричной игры в смешанных стратегиях [5–8]:

F i (x, y, z) = h x, A i y + A 2 z i t max, x

F 2 (x, y, z) 4 hy, B i x + B 2 z i t max, ^y

F 3 (x, y, z) = hz, C i x + C 2 yi t max, z

x G Sm С IRm, y G Sn С IRn,   > z G S1 С IRl, где x, y, z — стратегии 1, 2 и 3 игроков соответственно, A1 , A2, B1, B2, p

C 1 , C 2 — матрицы, a S p = {u = (u 1 , ..., u p ) T G IR^P | u i >  0, ^^u i = 1 } , i =1

p = m, n, l — канонические симплексы соответствующей размерности.

Цель состоит в отыскании ситуации равновесия по Нэшу в игре Г 3 = Г(А, B, C ) (A = (A i , A 2 ), B = (B i , B 2 ), C = (C i ,C 2 )) [5-8]. Находясь в этом равновесии, ни одному из игроков невыгодно в одиночку изменять свою оптимальную стратегию. При этом, согласно теореме Нэша, такое равновесие в игре Г 3 существует [5] (NE (Г 3 ) = 0 ). В [5] также доказано, что эта задача эквивалентна поиску глобального решения следующей невыпуклой оптимизационной задачи (ст 4 (x, y, z, а, в, Y))^:

Ф(ст) 4 hx, A i y+A 2 zi + hy, B i x + B 2 zi + hz, C i x +C 2 y i- а—в — Y t max,

CT e S 4 {(x,y,z,a,e,Y ) e IR ^m+n+l+3 | x e S m , y G S n , z 6 S i , A i y + A 2 Z <  ae m , B i x + B 2 Z <  ве п , C i x + С 2 У <  Ye i } , ( P ) где e p = (1,1, ..., 1) G IR p , p = m,n, l; a, в,Y — вспомогательные скалярные переменные. Тройка ( x ^* , y ^* , z ^* ), входящая в решение задачи ( P ), является ситуацией равновесия по Нэшу, кроме того, оптимальные значения переменных α _∗ , β _∗ и γ _∗ — это выигрыши игроков, а оптимальное значение задачи V ( P ) , Ф(x * ,y * ,z * , а * , в * ,Y * ) = 0. При этом справедливо:

а * = max (A i y * +A 2 z * ) i , в * = max (B i x * +B 2 z * ) j ,7 * = max (C i x * +C 2 y * ) t .

^∗ 1≤ i ≤ m                    ^∗ 1≤ j ≤ n                 ^{j ∗} 1≤ t ≤ l

Можно также показать, что в случае отыскания приближенного глобального решения задачи ( P ) мы имеем приближенное равновесие по Нэшу (NE(Г з ,е)) [5]. Отметим, что количество переменных в получившейся задаче равно (m + n + l + 3), количество ограничений — 2(m + n + l) + 3, однако для краткости, говоря ниже о размерности сгенерированных задач, будем иметь в виду количество стратегий у одного из игроков.

Для применения ТГП к задаче ( P ) [9,10] прежде всего построим явное d.c. разложение ее целевой функции на разность двух выпуклых:

^{Ф( x,} y, z,^a,^e, y ) = h(x, y, z) ^— g⁽x, y, z,^a,^e, Y),

где

h(x, у, z) = 4 ( k x + A i y k 2 + k x + A 2 z k 2 + k B i x + yk 2 + k y + B 2 z|l 2 + ^{+ k} C i x ⁺ z k ^{2 +} Ц С 2 У ⁺ z k ² ^, g ⁽ CT) = 4 ( k x ^— A i y k ^{2 +} k x ^— A 2 z ^k 2 ^{+ +} k ^{y —} B i x k ^{2 +} k y ^{— B} 2 ^z k 2 ⁺ k C i x ^{— z} k 2 ⁺ k C 2 ^{y — z} k 2 ^ ^{+ а + в +} Y .

Таким образом, мы получаем задачу d.c. максимизации вида ( DC ), где базовая невыпуклость заключена в функции h0. Далее с учетом свойств задачи (P ) и d.c. разложения (3)-(4) представим теоретические основы для построения алгоритмов ее решения на основе ТГП.

2 «Базовый» и гибридный методы глобального поиска

Фундаментом АГП являются так называемые условия глобальной оптимальности (УГО), позволяющие охарактеризовать именно глобальное решение исследуемой задачи [9, 10]. Приведем здесь УГО для задачи (P ) (в контрпозитивной форме) [6—8].

Обозначим: a(y, z) , max (A 1 y +A 2 z) i , e(x,z) , max (B 1 x+B 2 z) j , 1≤ i ≤ m                           1≤ j ≤ n

Y(x,y) , max(C 1 x + C 2 y) t . Тогда согласно свойству (2), а * = a(y * ,z * ),

в * = e(x * ,z * ), Y * = Y(x * ,y * ), если (x * ,y * ,z * ) G NE (Г 3 ).

Теорема 2.1 [6—8]. Если допустимый набор ст* = (x*, y*, z*, а*, в*, Y*) не является глобальным решением задачи (P), тогда найдутся тройка (u, v, w) G IRm+n+l, вектор (x, y, z) G Sm x Sn x Si и число € такие, что h(u, v, w) — € = Z = Ф(ст*) < 0,

g(u, v, w a(v, w), в(u, w),Y(u, v)) < € < suP(g, S), и при этом справедливо следующее неравенство:

g(x, y, z, а,в, 7) — € <  hV xyz h(u, v, w), (x, y, z) — (u, v, w) i ,     (6)

где а , a(y, z), в , e(x,z), Y , Y(x,y).

Конструктивное (алгоритмическое) свойство сформулированных УГО, которое позволяет в случае отыскания набора (u, v, w, 5с, y, 7, €), удовлетворяющего неравенству (6), сразу получить точку лучше, чем исследуемая (даже стационарная или критическая), является основой АГП, построенных на базе теории глобального поиска.

Напомним основные этапы таких алгоритмов (подробнее см. [3, 4, 6– 9, 13–15, 18]). Прежде всего осуществляется локальный поиск, принимающий во внимание специфику исследуемой задачи, который доставляет приближенно критические точки. В данном случае используется метод типа «mountain climbing» [22], заключающийся в последовательном решении задачи по группам переменных (специально сконструированных «частичных» задач ЛП), который доказал свою практическую эффективность для задач с билинейной структурой, в том числе для гексаматричных игр [4, 6–8, 13–15, 22]. Далее реализуется один из ключевых для успешного глобального поиска этапов — построение аппроксимации поверхности уровня выпуклой функции h(^). Важным элементом АГП является также решение линеаризованных по базовой невыпуклости задач (PLr) := (PL(ur, vr, wr)) (для получения хороших стартовых точек при локальном поиске):

g^(y) -h^W^- ,v r ,w r ), (x,y,z) )4 min, ст e S, (PL - ) где линеаризация проводится в точках аппроксимации (u r , v r , w r ), r = 1, ...,N . Кроме того, осуществляется одномерный поиск по параметру УГО ξ ; проводится отбор перспективных точек с поверхности уровня (с помощью неравенства из (5)), и лучшие по целевой функции критические точки оцениваются с точки зрения получения окончательного результата (как уже говорилось, ее значение в глобальном решении равно нулю). Подробное описание «базового» алгоритма глобального поиска в гексаматричных играх см. в [6–8, 18].

Построение эволюционных, генетических и гибридных (на их основе) алгоритмов обычно начинается с выбора так называемой функции приспособленности, с помощью которой можно оценить точки популяции (набор допустимых точек задачи) [19, 20]. Однако в нашем случае в качестве популяции особей на каждой итерации k глобального поиска выступают не допустимые точки, а множество точек, лежащих на текущей поверхности уровня: Pop k = { (u r , v r , w r ) | (u r , v r , w r ) e A k , r = 1,..., N } , где A k = { (u ¹ , v ¹ , w ¹ ),..., (u ^N , v ^N , w ^N ) | h(u ^r , v r , w r ) = £ + Z k , r = 1, ...,N } , Z k := Ф^), ст ^к 4 (x ^k ,y ^k , z k ,a k ,в к ,Y k ) e S — критическая точка (текущий рекорд), £ e [inf(g,S),sup(g,S)].

При этом функция приспособленности не является, как в классических вариантах ГА, просто целевой функцией задачи, поскольку точки аппроксимации могут быть в задаче недопустимыми, что влечет бессмысленность подобного их оценивания. Выбранная с этой целью функция PLoc( ^ ) представляет собой значение целевой функции в критической точке σb ^r , построенной с помощью метода локального поиска исходя из решения СТ ^r линеаризованной задачи (PL r ), которая, в свою очередь, линеаризуется в соответствующей точке аппроксимации (u r , v r , w r ), так что PLoc(u ^r , v r , w r ) 4 Ф(Ь ^Г ). Такой выбор функции приспособленности обусловлен свойствами задачи и соответствующего метода локального поиска (подробнее см. в [18]). Будем обозначать критическую точку также через ArgPLoc(^), так что СТ ^Г = ArgPLoc(u r , v r , w r ).

Точки популяции в ГА проходят специальным образом организованный процесс «развития» с помощью операторов, моделирующих процесс селекции, скрещивания (кроссовера) и мутации в течение определенного количества поколений (итераций) [19, 20]. Эти операторы были внедрены в «базовый» АГП, в результате чего в [18] был построен следующий

Гибридный алгоритм глобального поиска (ГАГП).

Пусть даны стартовая точка ст ⁰ G S, последовательности {т к } , {5 k } (т к > 0, 5 к > 0, k = 1,2,..., т к ^ 0, 5 k ^ 0 (k ^ го )), множество Dir = { (u ¹ ,v ¹ ,tv ¹ ),..., (u ^N ,v ^N , W N ) G IR ^m+^n+l | (u ^r , v r ,W ^r ) = 0, r = 1,...,N } , числа Y - 4 inf(g, S) и Y + ⁴ sup(g, S), вероятность мутации P _m , максимальное число поколений G _max и ε — точность решения задачи.

Ш^аг 0. Положить k : = 1, ст ^к := ст ⁰ , Y := Y - , 4 Y = (Y + — Y - )/N.

Ш^аг 1. Начиная с точки ст ^к методом локального поиска найти Т к -критическую точку ст ^к = (х ^к , y ^k , z ^k , а к ,/ к , Y k ) G S в задаче ( P ). Положить Z k := Ф(ст ^к ).

Шаг 2. Если ζ _k ≥ - ε, то стоп; найдено приближенное ε-равновесие по Нэшу в игре Г 3 : (х ^к , у ^к , z ^k ) G NE (Г 3 , е).

Шаг 3. По точкам (u r , v r , tv r ) G Dir построить точки (u r , v r , w ^r ) аппроксимации поверхности уровня функции h(Y, r = 1,..., N, так что h(u ^r , v r , w r ) = Y + 4 Y • (r — 1) + Z k , т. е. построить начальную популяцию точек P op _k с поверхности уровня. Для каждой точки популяции вычислить значение функции приспособлености: Z r := PLoc(u ^r , v r , w r ), r = 1,..., N . Положить p : Z p <  Z r V r = 1,-., N

Ш^аг 4. Если для некоторого номера f G { 1, ...N } выполнено неравенство Z r > - е, то стоп; найдено

(x * , y * , z*, а * , в * , Y * ) := ArgPLoc(u ^r , v r , w r ) — приближенное глобальное решение в задаче ( P ); (x * ,y * ,z * ) G NE(r 3 ,e).

Ш^аг 5. Положить r i := Rand{1,..., N } , r 2 := Rand{1,..., N } . Используя какую-либо процедуру кроссовера, по точкам (u r ¹ , v r ¹ , w r ¹ ) и (u r ² , v r ² , w r ² ) построить точки (e, v, w) и (u, v,w).

Ш^аг 6. Для точек (u, v, w) и (u, v,W) реализовать выбранную процедуру мутации с вероятностью P m .

Шаг 7. Вычислить а := а(е, tv), /3 := /(u, w), Y := Y(e, e); а := а(V,tv), / := /(u, w), Y := Y(u, e). Положить e := (e, v, w, a,в, Y), ст := (u, v, W, а, в, V). Вычислить также значения Z := Ф(3), Z := Ф(ст); ^ := g(e), Y := g(V) и построить две новые точки, лежащие на поверхностях уровня: h(u ^r 1 , v r ¹ , tv r ¹ ) = Y + Z и h(u r ² , v r ² , tv r ² ) = Y + Z.

Шаг 8. Вычислить PLoc(u ^r 1 , v r ¹ , tv r ¹ ) и PLoc(u r ² , v r ² , tv r ² ). Положить

(u ^r , v r , tv r ) := argmax { PLoc(u ^r 1 , v r ¹ , tv r ¹ ), PLoc(u r ² , v r ² , tv r ² ) } .

Ш^аг 9. Если PLoc(u ^r , v r , tv r ) > — е, то стоп; найдено приближенное е-равновесие по Нэшу в игре Г 3 .

(x * , y * , z * , а * ,/ * , Y * ) := ArgPLoc(u r , v r , tv r ) — приближенное глобальное решение задачи ( P ).

Ш^аг 10. Если PLoc(u r , v r , w r ) >  Z p , то обновить точку j популяции: (u ^p ,v ^p ,w ^p ) := (u r ,v r ,w r ).

Ш^аг 11. Если k < G max , то k : = k + 1 и перейти на шаг 3, иначе стоп. (u * ,v * , w * ) := argmax { PLoc(u ^r , v r , w r ) | (u r , v r , w r ) G Pop k , r = 1,...,N } , (x * , y * , z * , а * , в * , Y * ) := ^: = ArgPLoc(u * , v * , w * ) — полученное решение задачи. #

Допустимая стартовая точка σ ⁰ , как и для «базового» алгоритма, легко строится с помощью барицентров канонических симплексов и свойства (2) [6–8, 18]. Точности τ _k и δ _k используются в ГАГП внутри функции PLoc0, где мы решаем линеаризованную задачу и осуществляем локальный поиск. Поэтому упоминание о τ _k и δ _k на шагах алгоритма отсутствует. Вспомогательные выпуклая линеаризованная задача и задачи ЛП на шагах локального поиска могут быть решены одним из классических методов линейного и квадратичного программирования (см., например, [11, 12]). Построение точек, принадлежащих аппроксимации поверхности уровня, по заданным векторам из Dir и на шаге 7 проводится аналитически (подробнее см. [6, 7]). При этом заметим, что эта процедура может быть реализована для любой точки евклидова пространства (кроме 0), поэтому проблем с допустимостью точек, полученных в результате применения операторов ГА, здесь не возникает.

Отметим также необходимость специального вычисления значений скалярных переменных задачи на шаге 7, поскольку аппроксимация поверхности уровня функции, задающей базовую невыпуклость в такого типа задачах, строится только в пространстве трех векторных переменных. Кроме того, немаловажным элементом ГАГП в гексаматричных играх (равно как и «базового» АГП) являются дополнительные критерии останова (см. шаги 2, 4 и 9), которые определяют приближенное глобальное решение задачи ( P ) согласно свойствам редукции гексамат-ричной игры.

Наконец, из всего широкого спектра возможных вариантов генетических операторов для реализации в ГАГП были выбраны процедуры однородного кроссовера и равномерной мутации [19, 20], которые осуществляются следующим образом. Пусть r i ,r 2 G { 1, ...N } (r i = Г 2 ) — номера особей для осуществления однородного кроссовера и к : = Rand[0,1]. Тогда V j = 1,...,m + n + l, если к <  0.5 то (u,v,w) j := (u r ¹ , v r ¹ , w r ¹ ) j , (e, e, w) j := (u r ² , v r ² , w r ² ) j , иначе

(e, e, -w) j := (u r ¹ , v r ¹ , w r ¹ ) j , (u, v, w) j := (u r ² , v r ² , w r ² ) j . Далее, пусть P m — вероятность ос уществления мутации, и вследствие особенностей задачи K = 0, K = K > 0. Для каждого j = 1,...,m + n +1 вычисляются свои к 1 := Rand[0, 1] и к 2 := Rand[0, 1]. Если к 1 < P _m , то (u, v,w)) j := Rand[0,K]. Если к ₂

_m , то (e, e, te) j := Rand[0,K].

Предварительное численное тестирование разработанного алгоритма, проведенное в [18], показало работоспособность предложенного гибридного подхода к решению гексаматричных игр. Ниже подробно представим сравнительный вычислительный эксперимент по решению большого количества случайно сгенерированных игр различной сложности и размерности.

3 Вычислительный эксперимент

Программы, реализующие разработанный ГАГП, равно как и «базовый» АГП из [6–8], были реализованы в системе MATLAB 7.11.0.584 R2010b. При этом для возможности корректного сравнения счет проводился на том же компьютере, что и в [8], с процессором Intel Core i5-4690К CPU (3.5 GHz) и 16 Gb RAM. Вспомогательные задачи линейного и выпуклого квадратичного программирования решались с помощью подпрограмм «cplexlp» и «cplexqp» пакета IBM ILOG CPLEX 12.6.2 соответственно, с установками по умолчанию.

Наборы тестовых гексаматричных игр были случайно сгенерированы с помощью подпрограммы «sprand» системы MATLAB. Элементы матриц A 1 , A 2 , B 1 , B 2 , C 1 , и C 2 представляют собой целые псевдослучайные числа, равномерно распределенные на отрезке [ — (m + n + l)/10, (m + n + l)/10]. Заполненность матриц была равна 0.1. При этом параметры подпрограммы генерации были установлены так, что при каждом запуске программы генерируется одна и та же псевдослучайная последовательность. Это также дает возможность корректно сравнивать результаты работы двух алгоритмов, поскольку для определенной размерности строится одна и та же серия гексаматричных игр.

Как и во время второго этапа вычислительного эксперимента из [8], с помощью ГАГП решались игры размерности от (10 + 10 + 10) до (100 + 100 + 100) (m = n = l), количество игр в серии зависело от размерности и изменялось от 10000 до 10 (Sr).

Таким образом, все условия эксперимента из [8] были сохранены. Напомним полученные в этом эксперименте результаты решения тестовых задач. Они приведены ниже в табл. 1 со следующими обозначениями: SLoc — количество задач из серии, решенное только с помощью первичного локального поиска; Loc _av — среднее (на одну задачу серии) количество запусков локального поиска, потребовавшееся при глобальном поиске; LP _av и QP _av — среднее количество решенных задач ЛП и выпуклых квадратичных задач соответственно. Можно считать эти показатели некой «мерой» эффективности АГП наряду с T _av — средним временем решения одной задачи (в секундах). Наконец, uS — количество задач в серии, в которых не была достигнута заданная точность Е = 10 -3 приближенной ситуации равновесия по Нэшу.

Таблица 1. Тестирование «базового» АГП на сериях задач различной размерности

m	Sr	SLoc	LP av	Loc av	QP av	T av	uS
10	10000	1325	200.06	14.75	3.11	0.21	0
15	10000	97	806.57	45.84	8.30	0.94	0
20	1000	1	6057.86	291.23	49.20	6.98	4
25	1000	0	8243.24	575.84	96.65	10.08	7
30	1000	0	14038.57	983.67	164.64	17.81	8
40	1000	0	29920.71	1741.52	290.94	42.49	11
50	100	0	40650.39	2077.65	346.98	58.55	1
60	100	0	58387.44	2584.34	431.37	91.39	1
70	100	0	119430.68	5777.18	963.46	215.88	2
80	10	0	29301.5	985.0	164.8	57.6	0
90	10	0	219911.8	3055.7	509.9	363.5	0
100	10	0	117174.9	3328.4	555.3	265.0	0

Напомним также, что локальный поиск в «базовом» АГП представлял собой последовательную реализацию шести возможных процедур [6–8, 22] типа «mountain climbing», получающихся, в частности, с помощью изменения порядка решения задач ЛП. И, как можно видеть из таблицы, в этом случае удалось решить с заданной точностью более 99.8% сгенерированных задач (всего 34 из 24330 задач остались нерешенными).

При реализации ГАГП после предварительных экспериментов прежде всего было уменьшено количество вызовов процедур в локальном поиске с 6 до 2. Стартовая допустимая точка и значения общих параметров выбирались, как и в [8].

Далее, выбор специфических «генетических» параметров (размера популяции (N), вероятности мутации (P _m ) и количества поколений (G max )) проводился последовательно из наборов { m; (m+n+1); (m+n+ +1) * 3; (m + n +1) * 2 } , { 0.02; 0.01;0.03;0.04 } и {(m + n + 1);(m + n +1) * 3; (m+n +1) * 5; (m+n+1) * [Vm] } соответственно. В результате было организовано 4 запуска ГАГП, после окончания каждого из них заново проводилось построение начальной популяции. Сама же начальная популяция строилась с помощью векторов множеств Dir , которые наиболее эффективно зарекомендовали себя в качестве векторов множеств направлений для построения аппроксимаций поверхностей уровня в «базовом» АГП, а именно: первые m точек этого множества выбирались из набора:

Dirl = {er G ]Rm++n++, r = 1,..., m + n + 1}, где er — соответствующий вектор стандартного евклидового базиса. А остальные выбирались случайным образом из множеств

Dir2 = { (e i , e j , e¹), i = 1,..., m, j = 1,..., n, t = 1,..., l},

Dir3 = { (e i + x k , e j + y k , e ^t + z k ), i = 1,..., m, j = 1,..., n, t = 1,..., l}, где e ⁱ , e ^j , e ^t — также векторы евклидового базиса соответствующей размерности, a (x k , y k , z k ) — компоненты текущей критической точки в задаче (P ) (с шага 1 ГАГП). При этом было реализовано два варианта ГАГП: в первом случае выбор из множества Dir2 происходил на 1-м и 3-м запусках ГАГП, а из Dir3 — на 2-м и 4-м (прямой шрифт в таблице); во втором случае — наоборот (из Dir3 на 1-м и 3-м; из Dir2 на 2-м и 4-м запусках — курсивный шрифт в таблице ). В табл. 2, приведенной ниже, представлены результаты, полученные лучшим из этих двух вариантов. При этом в столбце P ar 1_,2_,3_,4 указано количество задач из серии, решенных с помощью соответствующего набора параметров N , P _m и G _max . Остальные обозначения и количество задач в сериях остались прежними.

Из табл. 2 прежде всего можно видеть, что количество нерешенных задач из 24330 сгенерированных сократилось с 34 до 11, т. е. более чем в три раза. Естественно, что при реализации ГАГП уменьшилось количество задач, решенных на небольших размерностях только одним локальным поиском, поскольку теперь внутри него действует только 2 процедуры, а не 6.

Тем не менее среднее время решения задач значительно уменьшилось. ГАГП проиграл «базовому» АГП только на размерностях 10, 80 и 100. В первом случае это объясняется тем, что, действительно, при повышении размерности в среднем эффективность ГАГП по времени увеличивается. А во втором и третьем случаях, равно как и для задач с размерностью 90, в сгенерированных сериях слишком мало задач, чтобы можно было судить о какой-то общей тенденции. На размерности 90 ГАГП выигрывает по времени более чем в 4.5 раза, а на размерностях 80 и 100 — проигрывает соответственно в 3.2 и 1.25 раза. Более надежные выводы можно сделать на задачах средних размерностей от 15 до 70. Здесь выигрыш ГАГП очевиден и колеблется от 1.1 до 3.4 раза.

Таблица 2. Тестирование ГАГП на тех же сериях задач
m	SLoc	LP av	Loc av	QP av	P ar 1 , 2 , 3 , 4	T av	uS
10	591	195.89	21.36	10.74	(9399;8;2;0)	0.31	0
15	67	497.82	40.48	20.78	(9796;126;8;2)	0.86	1
20	0	1197.91	85.68	45.15	(943;49;8;0)	2.08	0
25	0	2548.52	163.97	87.37	(904;83;9;2)	4.51	2
30	0	4454.42	276.03	146.47	(842;130;24;2)	8.62	2
40	0	11015.89	578.68	306.00	(739;213;34;8)	23.76	6
50	0	13405.28	744.73	400.79	(65;33;1;1)	30.23	0
60	0	28232.14	1340.10	711.88	(56;38;2;4)	68.14	0
70	0	29017.16	1367.57	725.96	(42;52;6;0)	78.22	0
80	0	62126.4	2469.3	1258.1	(1;7;2;0)	183.69	0
90	0	19781.7	944.2	489.1	(6;4;0;0)	80.04	0
100	0	85091.4	3607.6	1896.2	(0;8;2;0)	329.09	0

Можно заметить также, что при повышении размерности происходит «смещение» доли задач, для решения которых требуются дополнительные запуски ГАГП. Если для задач небольших размерностей более 90% решаются на первом запуске, то для задач размерности 100 уже ни в одной из них равновесие на первом запуске найти не удается. Наконец, первый вариант ГАГП оказался более эффективным по сравнению со вторым, поскольку показал лучшие по качеству результаты в 7 сериях из 12-ти.

Итак, на основании вышесказанного можно сделать окончательный вывод о преимуществе разработанного ГАГП над «базовым» АГП на достаточно широком спектре случайно сгенерированных задач различной размерности.

В завершение статьи (табл. 3) представим результаты решения «усложненных» задач, на которых «базовый» алгоритм показал неприемлемые результаты (до 50% нерешенных задач в серии). При этом была использована модификация разработанного алгоритма, заключающаяся в выборе не т, а до т + n +1 точек из набора Dirl при построении начальной популяции. Эта модификация показала себя еще более эффективно во время решения задач таблиц 1 и 2.

Здесь заполненность матриц была повышена до 0.5 для задач размерностей 10 и 15, с постепенным уменьшением до 0.15 для задач высоких размерностей. Отметим, что этим вариантом алгоритма удалось решить задачи вплоть до размерности 200. Обозначения в таблице остались прежние, при этом из нее был исключен столбец S Loc, поскольку вследствие сложности новых задач одним локальным поиском удалось решить только 16 из 10000 задач с 10 стратегиями у каждого из игроков.

Таблица 3. Тестирование ГАГП на усложненных задачах

m	Sr	LP av	Loc av	QP av	P ar 1 , 2 , 3 , 4	T av	uS
10	10000	1076.80	60.14	31.20	(8817;1066;75;10)	1.58	16
15	1000	4309.67	165.62	85.75	(732;238;21;2)	6.84	7
20	1000	10446.60	419.75	215.83	(571;337;60;8)	17.38	24
25	1000	22649.31	819.83	422.18	(410;387;160;18)	36.20	25
30	100	25337.93	1106.68	567.93	(34;41;21;0)	47.27	4
40	100	56583.75	2368.12	1217.07	(9;28;33;25)	114.16	9
50	100	82016.14	3687.08	1897.53	(14;41;28;6)	170.48	11
60	10	79521.8	3225.1	1665.3	(2;3;5;0)	185.59	0
70	10	134172.0	5280.4	2707.8	(1;4;3;1)	366.06	1
80	10	151104.9	6715.2	3601.3	(0;3;5;2)	517.18	0
90	10	220415.0	9677.2	5065.0	(1;3;3;1)	894.40	2
100	1	501558	23425	12242	(0;0;0;1)	2355.30	0
120	1	122514	4095	2485	(0;1;0;0)	618.80	0
150	1	50003	1782	944	(1;0;0;0)	431.32	0
175	1	164588	8041	4314	(0;1;0;0)	2085.30	0
200	1	654850	23544	12315	(0;0;1;0)	8576.27	0

По среднему времени решения задач, числу запусков локального поиска и количеству решенных вспомогательных задач из табл. 3 можно видеть, что «усложненные» задачи труднее для алгоритма примерно в 5–8 раз. Количество нерешенных с точностью 10 ^{- 3} задач остается достаточно низким (не решены с заданной точностью 99 (менее 1 %) из 13345 сгенерированных задач). При этом в 93 из этих 99 задач удалось приблизиться к нулю с точностью 10 ^{- 1} , так что здесь получено просто более грубое приближенное равновесие по Нэшу. Также сохраняется эффект «смещения» доли задач, для решения которых требуются дополнительные запуски ГАГП. И более эффективным остается первый вариант алгоритма (в 12 сериях из 16).

В целом можно сделать вывод, что гибридный подход к решению гексаматричных игр оказался достаточно эффективным, хотя и сохраняется необходимость его совершенствования с целью дальнейшего повышения размерности и заполненности матриц в сгенерированных задачах.

Заключение

В работе представлены результаты детализации гибридного алгоритма, разработанного в [21] и предназначенного для поиска ситуаций равновесия по Нэшу в гексаматричных играх. Подробно описан выбор его параметров, а также процесс организации и итоги обширного вычислительного эксперимента.

По результатам эксперимента можно сделать вывод, что ГАГП позволяет быстрее и качественнее, чем «базовый» алгоритм [8], решать гексаматричные игры, особенно это касается игр с повышенной размерностью и заполненностью матриц. Дальнейшее совершенствование алгоритма будет направлено, в частности, на модификацию блока локального поиска, чтобы можно было решать еще более сложные задачи данного класса.