METHOD OF BINARY ANALYTIC PROGRAMMING TO LOOK FOR OPTIMAL MATHEMATICAL EXPRESSION

Full Text

ВведениеМетоды символьной регрессии могут осуществлять поиск структуры матема- тического выражения. Многие важные задачи требуют нахождения оптимально- го математического выражения, в том числе задачи обработки экспериментальных данных для прогнозирования и поиска общих факторов, идентификации мате- матической модели и синтеза управления.Все методы символьной регрессии кодируют математические выражения и осуществляют поиск на пространстве кодов с помощью эволюционного алгорит- ма. Наиболее подходящим для поиска решения в методах символьной регрессии является генетический алгоритм. Он не использует арифметические операции для модификации возможных решений. Основными операциями генетического алгоритма являются операции скрещивания и мутация. Операция скрещивания генетического алгоритма зависит от вида кода. Генетическое программирование [1] делает операцию скрещивания в определенных точках корректных кодов для того, чтобы новый код после скрещивания был правильным и соответствовал некоторому возможному решению. Методы грамматической эволюции [2] и ана- литического программирования [3] осуществляют скрещивание в любых точках, как генетический алгоритм для численных задач. После применения операциискрещивания в данных методах иногда получается неправильный код. Исправ- ление кода требует дополнительных затрат времени. Методы сетевого оператора [4], декартово генетического программирования [5] и метод матриц синтаксиче- ского разбора [6] всегда применяют корректную операцию скрещивания, но эти методы символьной регрессии используют избыточные элементы в коде.В работе представлен новый метод символьной регрессии, метод бинарного аналитического программирования. Метод кодирует математические выражения только в виде суперпозиции функций с одним или двумя аргументами. Для кор- ректного выполнения операции скрещивания метод также включает в себя из- быточные элементы кода, тождественную функцию с одним аргументом и еди- ничными элементами для функций с двумя аргументами. Эти элементы, как и нули в позиционной записи чисел, также позволяют построить правильный код математического выражения, в котором чередуются коды функций с различным числом аргументов.Бинарное аналитическое программированиеДля того, чтобы составить код бинарного аналитического программирования, мы используем следующие базовые наборы:множество аргументов математического выраженияF0 = (q1, …, qP, x1, …, xN); (1)множество функций с одним аргументомF1 = (f1,1(z) = z, f1,2(z), …, f1,R(z)); (2)множество функций с двумя аргументамиF2 = (f2,1(z1, z2), …, f2,S(z1, z2)); (3)множество единичных элементов для функций с двумя аргументамиE2 = (e1, …, eM). (4)Набор функций с одним аргументом должен включать в себя тождественные функции.f1,1(z) = z. (5)Каждая функция с двумя аргументами множества (3), ∨f2,i(z1, z2) ∈ F2, имеет единичный элемент из множества (4), ∃ej ∈ E2,f2,i(ej, z2) = z2, f2,i(z1, ej) = z1, i ∈ {1, …, S}, j ∈ {1, …, M}. (6) Чтобы сгенерировать код бинарного аналитического программирования, мыобъединяем в одно упорядоченное множество аргументов математического вы-ражения (1), множество единичных элементов (4) и множество функций с двумя аргументами (3)F = (f1 = q1, …, fP = qP, fP+1 = x1, …, fP+N = xN, fP+N+1 = e1, …, fP+N+M = eM,fP+N+M+1 = f2,1(z1, z2), …, fP+N+M+S = f2,S(z1, z2)). (7)Запишем математическое выражение в виде суперпозиции вложенных функ- ций и аргументов математического выраженияy = fα (fα (…fα )…) = fα fα… fα , (8)1 2 Kiгде fα ∈ F0  F1  F2, i = 1, …, K.1 ° 2 ° ° KДля получения кода бинарного генетического программирования суперпози- ция функций (8) должна удовлетворять следующим условиям:аргументами функций с двумя аргументами являются только функции с одним аргументом;аргументами функций с одним аргументом являются аргументы математи- ческих выражений или функции с двумя аргументами или их единичные аргу- менты;первой функцией является функция с двумя аргументами.Если суперпозиция не удовлетворяет условиям кодирования, мы исправляем это, добавив тождественную функцию и / или функцию с двумя параметрами, с единицей в качестве одного из аргументов.Пусть условие a) не выполнено. Аргументом функции с двумя аргументами является тоже функция с двумя аргументам. Добавим функцию тождества (5) в математическое выражениеf2,k(f2,l(z1, z2), z3) = f2,k(f1,1(f2,l(z1, z2)), z3). (9)Аргументом функции с двумя аргументами является аргумент математическо- го выражения. Мы снова добавим функцию тождества в математическое выра- жение.где z1 ∈ F0.f2,k(z1, z2) = f2,k(f1,1(z1), z2), (10)Пусть условие b) не выполнено. Аргументом функции с одним аргументом является тоже функция с одним аргументом. Добавим функцию с двумя аргумен- тами и с единицей в качестве одного из аргументов в математическом выражении.где er ∈ E2, f2,m(z, er) = z.f1,k(f1,l(z) = f1,k(f2,m(f1,l(z), f1,1(er))), (11)Пусть условие c) не выполнено. Функцией суперпозиции (8) является функция с одним аргументом. Добавим функцию с двумя параметрами, взяв в качестве одного из аргументов единичный элемент, в начало математического выраженияf1,k(z) = f2,m(f1,k(z), f1,1(er)). (12)После коррекции суперпозиции (8) мы получаем суперпозицию с нечетным количеством элементов и чередующихся элементов из множеств (7) и (2)αгде f2i+1α∈ F, f2i1 °fα2 °y = fα∈ F1, i = 0, …, (L - 1)/2.α°… f , (13)LДля получения кода математического выражения мы заменим элементы су- перпозиции (13) на их серийные номера в соответствующих наборах F и F1A = (a1, …, aL), (14)2i+1где a2i+1 = v, если fα= fv ∈ F, i = 0, …, (L - 1)/2, (15)2ia2i = m, если fα= f1,m ∈ F1, i = 0, …, (L - 1)/2. (16)Бинарное дерево графа имеет количество листьев на единицу больше числа узлов. Узлы и листья бинарного дерева графа математического выражения (14) соответствуют элементам множества (7). Если серийный номер элемента явля- ется не более чем объединенным числом параметров, переменных и единичныхэлементов в F, a2i+1  P + N + M, i ∈ {0, …, (L - 1)/2}, то элемент множества на-ходится на листе бинарного дерева графа. В противном случае a2i+1 > P + N + M, i ∈ {0, …, (L - 1)/2}, а элемент расположен в листе двоичного дерева графа.Пусть количество узлов σn и листьев σl в коде (14) математического выражения рассчитываются по формулам(L-1)/2σn = ∑i =0ni ,(17)(L-1)/2σl = ∑i =0li ,(18)где⎩⎧1, если a2i +1 > P + N + M ni = ⎨0 - иначе ,(19)⎧1, если⎩l =a2i +1 ≤ P + N + M .(20)i ⎨0 - иначеДля корректного кода математического выражения справедливо уравнениеσl - σn = 1. (21)Рассмотрим операцию скрещивания для кодов бинарного аналитического про- граммирования. Для того чтобы реализовать функцию операции скрещивания,мы совершаем обмен подмножеств кодов. Каждое подмножество соответствует коду математического выражения. Точки для операция скрещивания определя- ются в нечетных позициях кодов.Определение подмножеств кодов для операция скрещивания является важной задачей.Подмножество кода (14) математического выражения всегда начинается с не- четного порядкового элемента r и имеет нечетное число элементов kгде r + k  L.A(r, k) = (ar, ar+1, …, ar+k), (22)Количество узлов и листьев в подмножестве кода математического выражения рассчитывается по формулам(k -1)/2σn (r, k) = ∑i =(r -1)/2ni ,(23)(k -1)/2σl (r, k) = ∑i =(r -1)/2li ,(24)где ni и li определяются выражениями (19), (20).Подмножество A(r, k) кода соответствует математическому выражению, когда условие (21) справедливо для минимального количества элементов в немmin{σl (r, k) - σn (r, k) = 1}.k(25)Для операции скрещивания мы выбираем два кода для математических вы- раженийαAα = (aα,1, …, aα,L ), (26)βAβ = (aβ,1, …, aβ,L ). (27)Нечетные позиции для точек операции скрещивания определяются случайным образом rα ∈ {1, …, Lα}, rβ ∈ {1, …, Lβ}.Определим подмножества кодов для математических выражений с помощьюуравнения (25)Aα(rα, kα) = (aα,r , …, aα,r +k ), (28)α α αAβ(rβ, kβ) = (aβ,r , …, aβ,r +k ), (29)β β βгде переменные kα и kβ удовлетворяют следующие выраженияmin{σα,l (rα , kα ) - σn (rα , kα ) = 1},kα(30)min{σβ,l (rβ , kβ ) - σn (rβ , kβ ) = 1}.kβ(31)Поменяем подмножества кодов математических выражений и получим коды для новых математических выраженийA = (a ,1, …, a ,r1, a ,r , …, a ,r k , a ,r k1, …, a ,r L ),(32)α α α α - β ββ β + βα α + α + α α + αA = (a ,1, …, a ,r1, a ,r , …, a ,r k, a ,r k1, …, a ,r L ).(33)β β β β - α αα α + αβ β + β + β β + βРассмотрим пример. Пусть это множество двух математических выражений⎧cos(q2 x2 + q3 ), еслиy = sin(q x ) +q1 x1 ≤ q2 x2 ,1 1 1⎨⎩exp(-q2 x2 ) - иначе⎧exp(-q2 x2 ), если cos(q2 x2 + q3 ) ≤ sin(q1 x1 + q3 )y =2 ⎨exp(-q x ) - иначе .⎩ 1 1Составим коды бинарного генетического программирования для математиче- ских выражений y1 и y2.Будем использовать следующие базовые множестваF0 = (x1, x2, q1, q2, q3),F1 = (f1,1(z) = z, f1,2(z) = sin(z), f1,3(z) = cos(z), f1,4(z) = exp(z),f1,5(z) = -z, f1,6(z) = ϑ(z), f1,7(z) = 1 - ϑ(z)),F2 = (f2,1(z1, z2) = z1 + z2, f2,2(z1, z2) = z1z2),гдеE2 = (0,1),⎧1, еслиϑ(z) = ⎨z > 0.⎩0 - иначеОбъединим множества F0, E2 и F2F = (f1 = x1, f2 = x2, f3 = q1, f4 = q2, f5 = q3, f6 = 0, f7 = 1, f8 = z1 + z2, f9 = z1z2).Наши математические выражения y1, y2 включают в себя функцию с тремя аргументами⎧z2, если z1 ≤ 0z⎩ 3f (z , z , z ) =3,1 1 2 3⎨ - иначе .Мы можем представить эти функции с помощью некоторых функций с одним и двумя аргументамиf3,1(z1, z2, z3) = (1 - ϑ(z1))z2 + ϑ(z1)z3 == f2,2(1 - ϑ(z1), z2) + f2,2(ϑ(z1), z3) = f2,2(f1,7(z1), z2) + f2,2(f1,6(z1), z3) == f2,1(f2,2(f1,7(z1), z2), f2,2(f1,6(z1), z3)).Представим математические выражения y1, y2 элементами множеств F0, F1, F2 y1 = f2,1(f1,2(f2,2(q1, x1)), f2,1(f2,2(f1,7(f2,1(f2,2(q1, x1),f1,5(f2,2(q2, x2)))), f1,3(f2,1(f2,2(q2, x2), q3))),f2,2(f1,6(f2,1(f2,2(q1, x1), f1,5(f2,2(q2, x2)))), f1,4(f1,5(f2,2(q2, x2)))))).y2 = f2,1(f2,2(f1,7(f2,1(f1,3(f2,1(f2,2(q2, x2)), q3)), f1,5(f1,2(f2,1(f2,2(q1, x1),f1,4(f1,5(f2,2(q2, x2)))), f2,2(f1,6(f2,1(f1,3(f2,1(f2,2(q2, x2)), q3)),f1,5(f1,2(f2,1(f2,2(q1, x1), q3))))), f1,4(f1,5(f2,2(q1, x1))))).Полученные записи математических выражений не удовлетворяют свойствамa, b, c. Исправим оба выражения в соответствии с формулами (9)-(12)y1 = f2,1 ° f1,2 ° f2,2 ° f1,1 ° q1 ° f1,1 ° x1 ° f1,1 ° f2,1 ° f1,1 ° f2,2 ° f1,7 °f2,1 ° f1,1 ° f2,2 ° f1,1 ° q1 ° f1,1 ° x1 ° f1,5 ° f2,2 ° f1,1 ° q2 ° f1,1 °x2 ° f1,3 ° f2,1 ° f1,1 ° f2,2 ° f1,1 ° q2 ° f1,1 ° x2 ° f1,1 ° q3 ° f1,1 ° f2,2 ° f1,6 ° f2,1 ° f1,1 ° f2,2 ° f1,1 ° q1 ° f1,1 ° x1 ° f1,5 ° f2,2 ° f1,1 ° q2 ° f1,1 ° x2 ° f1,4 ° f2,1 ° f1,1 ° 0 ° f1,5 ° f2,2 ° f1,1 ° q2 ° f1,1 ° x2,y2 = f2,1 ° f1,1 ° f2,2 ° f1,7 ° f2,1 ° f1,3 ° f2,1 ° f1,1 ° f2,2 ° f1,1 ° q2 ° f1,1 ° x2 ° f1,1 ° q3 ° f1,5 ° f2,1 ° f1,1 ° 0 ° f1,2 ° f2,1 ° f1,1 ° f2,2 ° f1,1 ° q1 ° f1,1 ° x1 ° f1,4 ° f2,1 ° f1,1 ° 0 ° f1,5 ° f2,2 ° f1,1 ° q2 ° f1,1 ° x2 ° f1,1 ° f2,2 ° f1,6 ° f2,1 ° f1,3 ° f2,1 ° f1,1 ° f2,2 ° f1,1 ° q2 ° f1,1 ° x2 ° f1,1 ° q3 ° f1,5 ° f2,2 ° f1,1 ° 0 ° f1,2 ° f2,1 ° f1,1 ° f2,2 ° f1,1 ° q1 ° f1,1 ° x1 ° f1,1 °q3 ° f1,4 ° f2,2 ° f1,1 ° 0 ° f1,5 ° f2,2 ° f1,1 ° q1 ° f1,1 ° x1.Заменим элементы упорядоченных множеств F0, F1, F2 на номера этих элемен- тов в множествах F1 и FA1 = (8,2,9,1,3,1,1,1,8,1,9,7,8,1,9,1,3,1,1,5,9,1,4,1,2,3,8,1,9,1,4,1,2,1,5,1,9,6,8,1,9,1,3,1,1,5,9,1,4,1,2,4,8,1,6,5,9,1,4,1,2),A2 = (8,1,9,7,8,3,8,1,9,1,4,1,2,1,5,5,8,1,6,2,8,1,9,1,3,1,1,4,8,1,6,5,9,1,4,1,2,1,9,6,8,3,8,1,9,1,4,1,2,1,5,5,9,1,6,2,8,1,9,1,3,1,1,1,5,4,9,1,6,5,9,1,3,1,1).Мы получили коды бинарного аналитического программирования для мате- матических выражений.Рассмотрим пример операции скрещивания кодов A1, A2.Определим случайным образом нечетные точки для скрещивания. Пустьr1 = 15, r2 = 21.Определим подмножества математической формы формулами (28)-(31),k1 = 4, k2 = 16,σ1,l(15,4) = 0 + 1 + 1 = 2,σ1,n(15,4) = 1 + 0 + 0 = 1,σ1,l(15,4) - σ1,n(15,4) = 2 - 1 = 1,σ2,l(21,16) = 0 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 = 5,σ2,n(21,16) = 1 + 1 + 0 + 0 + 1 + 0 + 1 + 0 + 0 = 4,σ2,l(21,16) - σ2,n(21,16) = 5 - 4 = 1.Мы получили следующие подмножества кодов1A = (8,2,9,1,3,1,1,1,8,1,9,7,8,1,9,1,3,1,1,5,9,1,4,1,2,3,8,1,9,1,4,1,2,1,5,1, - - A1(15,4)9,6,8,1,9,1,3,1,1,5,9,1,4,1,2,4,8,1,6,5,9,1,4,1,2),2A = (8,1,9,7,8,3,8,1,9,1,4,1,2,1,5,5,8,1,6,2,8,1,9,1,3,1,1,4,8,1,6,5,9,1,4,1,2,1,9, ----- ----- A2 (21,16)6,8,3,8,1,9,1,4,1,2,1,5,5,9,1,6,2,8,1,9,1,3,1,1,1,5,4,9,1,6,5,9,1,3,1,1).Новые коды соответствуют новым математическим выражениямỹ1 = sin(q1x1) + (1 - ϑ(q1x1 +exp(-q2x2) - q2x2)) ·· cos(q2x2 + q3) + ϑ(q1x1 - q2x2)exp(-q2x2),ỹ2 = (1 - ϑ(cos(q2x2 + q3) - sin(q1x1))) ·· ϑ(cos(q2x2 + q3) - sin(q1x1 + q3))exp(-q1x1).ВыводыПредставлен новый метод символьный регрессии, бинарного генетического программирования. Новый метод использует бинарное вычислительное дерево. Метод увеличивает число возможных точек скрещивания и не требует коррекции кода после скрещивания.© Дивеев А.И., Ломакова Е.М., 2017

About the authors

Askhat I Diveev

Federal Research Center “Computer Science and Control” of RAS; Engineering Academy Peoples’ Friendship University of Russia

Email: aidiveev@mail.ru
Doctor of technical sciences, professor, chief of sector of Cybernetic problems, professor of department Mechanics and mechatronics Vavilov str., 44, Moscow, Russia, 119333; Miklukho-Maklaya str., 6, Moscow, Russia, 117198

Evgenia M Lomakova

Engineering Academy Peoples’ Friendship University of Russia

Email: lomakovajm@gmail.com
graduate student, department Mechanics and mechatronics Miklukho-Maklaya str., 6, Moscow, Russia, 117198

References

Supplementary files