RESEARCH OF COEVOLUTION GENETIC PROGRAMMING ALGORITHM AND ITS APPLICATION IN THE PROBLEM OF MODEL ANALYSIS OF PHASE BOUNDARIES OF MAGNETIC STATE OF A CRYSTAL

Full Text

Результаты исследования алгоритма генетического программирования (ГП) показывают, что нельзя од- нозначно говорить о превосходстве какого-то кон- кретного алгоритма ГП и даже после многократных решений задачи остается неопределенность в выборе параметров метода ГП [1]. Это подтверждает то, что для каждой задачи существует свой алгоритм с наи- лучшей стратегией поиска. А выбор конкретного ал- горитма и настройка его параметров сами по себе яв- ляются очень сложными проблемами. Для устранения подобных проблем необходимо разрабатывать процедуры, автоматизирующие под- стройку параметров ГП в ходе однократного решения задачи. Одной из таких процедур является использо- вание коэволюционных стратегий, т. е. конкуренции алгоритмов ГП за ресурс [2; 3]. Основная идея коэволюционного алгоритма со- стоит в одновременной эволюции нескольких субпо- пуляций, каждая из которых решает свою задачу сим- вольной регрессии и обладает своей стратегией поис- ка (моделирования). При этом субпопуляции борются за общий ресурс, который в течение работы алгорит- ма перераспределяется в пользу более эффективной из них. Коэволюционный алгоритм состоит из следующих шагов. Шаг 1. Выбор индивидуальных алгоритмов. Шаг 2. Инициализация параметров коэволюцион- ного алгоритма. Шаг 3. Работа индивидуальных алгоритмов ГП в течение заданного интервала адаптации. Шаг 4. Проверка критерия остановки: если данный критерий срабатывает, то выводится лучшее найден- ное решение и алгоритм прекращает работу; иначе – переход на шаг 6. Шаг 5. Оценка алгоритмов. Шаг 6. Перераспределение ресурса (на основе оценки, полученной на шаге 5). Шаг 7. Переход на шаг 3. Использование в коэволюционном алгоритме кон- курирующих стратегий алгоритмов предполагает, что для субпопуляций необходимо ввести функцию при- годности, с помощью которой будет определяться лучшая субпопуляция с предоставлением ей большего ресурса для решения задачи. Пусть Т – интервал адап- тации, b(k) = (kT, kT–1, …, k1) – вектор длиной Т. Если i-я популяция в момент k содержит наилучшего (по всем популяциям) индивида, то bi(k) = 1, в противном случае bi(k) = 0. Качество популяции можно оценить по формуле [4]: Т −1 T − k qi = ∑ ⋅ bi (k ) . (1) k =0 Размеры ресурсов изменяются за счет сокращения каждой проигравшей популяции на некоторое число индивидов, т. е. определенный заранее размер штра- фа, и увеличения победившей популяции на число, равное сумме потерь проигравших. Таким образом, общее число индивидов остается неизменным. Со- кращение проигравших популяций осуществляется только до тех пор, пока они не достигнут минималь- ного гарантированного размера – социального мини- мума. В связи с тем что ГП является стохастической процедурой, оценка его эффективности осуществля- ется усреднением по многократным запускам. В каче- стве критерия сравнения может быть использован показатель надежности – процент успешных запусков алгоритма от общего числа запусков алгоритма. При этом в состав коэволюционного алгоритма индивиду- альные алгоритмы включаюттся случайным образом. В результате проведенного авторами исследования было выявлено, что коэволюционный алгоритм пре- восходит все индивидуальные алгоритмы ГП (рис. 1). Происходящий в ходе поиска процесс перераспреде- ления ресурсов между алгоритмами, показанный на рис. 2, подтверждает правильность предположения о том, что нельзя отнимать весь ресурс у алгоритма (выгодность социального минимума), так как проиг- рывающие на начальных шагах алгоритмы могут в дальнейшем найти лучшее решение. На эффективность коэволюционного алгоритма могут оказывать влияние следующие параметры: ве- личина интервала адаптации, размер штрафа и размер социального минимума, количество индивидуальных алгоритмов. *Работа выполнена в рамках НИР Б1.25.11 по тематическому плану ЕЗН Сибирского государственного аэрокосмическо- го университета имени академика М. Ф. Решетнева и при поддержке ФЦП «Научные и научно-педагогические кадры Рос- сии» (НИР 2011-1.2.1-113-025, 2011-1.2.2-215-021). 9 Математика, механика, информатика Рис. 1. Пример поведения лучшего индивида: коэволюционный алгоритм ГП показан плошной жирной линией Рис. 2. Пример перераспределения ресурса в ходе работы коэволюционного алгоритма ГП В ходе исследования было установлено, что ис- пользование такого параметра, как размер штрафа, равного некоторому проценту от величины популя- ции индивидуального алгоритма, неэффективно, так как данная величина является фиксированной и не зависит от количества индивидуальных алгоритмов. Однако такой штраф будет эффективным в случае, когда размер популяции индивидуального алгоритма равен 100 индивидам. Уменьшение или увеличение этой величины отрицательно сказывается на эффек- тивности работы коэволюционного алгоритма. Для разрешения этой проблемы предложена сле- дующая процедура расчета размера штрафа в зависи- мости от количества индивидуальных алгоритмов ГП и общего числа индивидов (рис. 3): Разме р штрафа 25 20 15 10 5 0 2 3 4 5 6 7 8 Размер штрафа 20 15 10 7 5 4 3 Количество алгоритмов Рис. 3. Функция изменения штрафа в зависимости от количества индивидуальных алгоритмов Z = ⎛ SpCA ⋅ zh ⎞ ⋅ 2−( N 2) , (2) ⎜ 100 ⎟ ⎝ ⎠ где Z – количество индивидов, на которое будут штрафоваться проигравшие индивидуальные алго- ритмы; SpCA – общее число индивидов; zh – устанав- ливаемый пользователем размер штрафа в процентах; N – количество индивидуальных алгоритмов. Изменение процедуры вычисления размера штра- фа привело к тому, что величина социального мини- мума, как и размер штрафа, также должна зависеть от общего числа индивидов. Поэтому было принято ре- шение устанавливать величину социального миниму- ма как некоторый процент от общего числа индиви- дов, задаваемого пользователем. Результаты исследования зависимости эффективности коэволюционного алгоритма от размеров штрафа и социального минимума Таблица 1 Социальный минимум/штраф, %246810121416 215202051052010 4101510201025105 651025202520155 815515151520515 102025152045402015 1210520253025155 14151015102015150 16055101510510 10 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Для того чтобы установить характер зависимости эффективности коэволюционного алгоритма от зна- чений его параметров и выработать рекомендации по их настройке, были проведены: – исследование эффективности коэволюционного алгоритма в зависимости от величины штрафа и соци- ального минимума (табл. 1); – исследование зависимости эффективности ко- эволюционного алгоритма от величины интервала адаптации (табл. 2); – исследование зависимости эффективности ко- эволюционного алгоритма от количества индивиду- альных алгоритмов (табл. 3). Таблица 2 Результаты исследования зависимости эффективности коэволюционного алгоритма от величины интервала адаптации Интервал адаптацииN3, %N2, %N1, % 2157510 3106030 4355510 545505 6256510 710855 8157510 958015 10107515 Таблица 3 Результаты исследования зависимости эффективности коэволюционного алгоритма от количества индивидуальных алгоритмов Количество алгоритмовN3, %N2, %N1, % 215805 3355015 445505 5405010 6355015 7305020 8206020 Примечание. В табл. 2 и 3 применяются следующие обо- значения: − N1 – количество запусков, в которых было получено решение с ошибкой аппроксимации больше 5 %, в процен- тах от общего количества запусков; − N2 – количество запусков, в которых было получено решение с ошибкой аппроксимации больше 1 %, но меньше 5 %, в процентах от общего количества запусков; − N3 – количество запусков, в которых было получено решение с ошибкой аппроксимации меньше 1 %, в процен- тах от общего количества запусков. В табл. 1–3 в качестве примера приведены наибо- лее информативные результаты тестовой функции sin(x) на интервале [–3,14; 3,14] со случайным шагом, объем тестовой выборки равен 100 точкам. В качестве функционального множества использовались только арифметические операции (+, –, *, /), терминальное множество содержало переменную x и набор констант на интервале [–1; 1] со случайным шагом. В результате исследования эффективности работы коэволюционного алгоритма ГП в зависимости от параметров, входящих в его настройку, было установ- лено, что: – коэволюционный алгоритм ГП всегда лучше са- мого худшего из алгоритмов и даже лучше чем сред- ний алгоритм по показателям надежности; – коэволюционный алгоритм ГП позволяет авто- матически выбирать лучшую стратегию из имеющих- ся и включать ее в необходимый момент; – не нужно сильно штрафовать (размер штрафа 10…12 %) проигравшие алгоритмы, но в то же время не надо оставлять им больших социальных гарантий; – интервал адаптации необходимо выбирать рав- ным 4…5; – количество индивидуальных алгоритмов должно быть 3…6; – в случае полного отсутствия знаний о предпоч- тительности выбора индивидуальных алгоритмов да- же комбинация из практически неработающих алго- ритмов, худших по надежности в сравнении с другими алгоритмами, имеет большую надежность, чем надеж- ность каждого из этих алгоритмов по отдельности; – 75 % решений по показателю N2 имеют ошибку аппроксимации меньше 1,6 %, т. е. коэволюционный алгоритм ГП позволяет получать достаточно хорошие аппроксимации; – коэволюционный алгоритм генетического про- граммирования практически на порядок превосходит по скорости нахождения решения метод генетическо- го программирования. Результаты работы коэволюционного алгоритма ГП с применением предложенных выше настроек представлены в табл. 4. Точное решение в табл. 4 оз- начает, что алгоритм нашел точную структуру задан- ной тестовой функции. На основе полученных результатов можно сделать вывод о полезности и перспективности коэволюцион- ного алгоритма, который позволяет автоматически выбирать лучшую стратегию из имеющихся и вклю- чать ее в необходимый момент. Однако для подтвер- ждения этого вывода требуется проведение дополни- тельной проверки на реальных задачах. Одна из них приведена ниже. Задача построения фазовых границ магнитного состояния кристалла. При решении данной задачи ис- пользовались следующие параметры коэволюционного алгоритма генетического программирования: терми- нальное множество – {x,C}, где x∈R, C∈ [–10;10]; функ- циональное множество – {+, –, *, ÷, sin, cos, sqrt, power, ln, exp}; размер ресурса – 400; начальная глу- бина деревьев – 3; интервал адаптации – 5; размер штрафа – 10 %; размер социального минимума – 10; количество индивидуальных алгоритмов – 4. К сожалению, для антиферромагнетиков даже с достаточно слабым обменом (низкие температуры Нееля TN) обменные поля имеют порядок 1 000 кЭ, а постоянные лабораторные поля достигают величин напряженности на два порядка ниже обменных. По- этому экспериментальных данных по исследованию поведения двупреломления при изменении магнитной 11 Математика, механика, информатика структуры во внешнем магнитном поле для них прак- тически нет. Уникальными являются данные, полу- ченные в импульсных магнитных полях на кристаллах Rb2MnCl4 и NaMnCl3, представленные в [5; 6]. Будучи чувствительными к магнитной структуре, рефракто- метрические свойства могут быть использованы для изучения фазового состояния кристалла (рис. 4–6). Проецируя на плоскость H−T критическое поле HSF, при котором наблюдается скачок двупреломле- ния при различных температурах, можно получить линию фазовых переходов первого рода, связанных с опрокидыванием магнитных моментов подрешеток в Rb2MnCl4 (рис. 7). Фазовая граница между антиферромагнитной и парамагнитной фазами лежит в узком температурном интервале. Ожидаемое соотношение, описывающее уравнение границы между антиферромагнитной и парамагнитной фазами, имеет вид TN(H)/TN(0) ≈ (1 + γH2)ξ, (3) где ξ = 1 (получено в приближении молекулярного поля); Tтр = 49 ± 1,5 К, Hтр = 64 ± 2 кЭ. На этой гра- нице сходятся линии фазовой диаграммы, разделяю- щие антиферромагнитную, спин-флоп и парамагнит- ную фазы. Спин-волновое приближение дает оценку зави- симости, описывающей границу между антиферро- магнитной и спин-флоп-фазами, в виде HSF ≈ T g, где g = 3/2 – 5/2. Полученная генетическим алгорит- мом символьная зависимость (рис. 8) практически неотличима от T 3/2. Кривые зависимости двупреломления от магнит- ного поля и температуры, представленные на рис. 6, можно использовать для построения фазовых границ магнитного состояния NaMnCl3. Проецируя критиче- ские поля Hc, при которых меняет знак вторая произ- водная ∂2 ϕ ∂H 2 , получим линию Hc(T) для критиче- ских полей, при которых происходят фазовые перехо- ды из антиферромагнитного в парамагнитное состоя- ние при температуре Т (рис. 9). Результаты работы коэволюционного алгоритма ГП Таблица 4 № п/пТестовая функцияТочное решение, %Е < 0,000 1, %C(n)N 1f ( x, y) = x2 + y2100100710 2f ( x, y) = x2 + y2 − cos( x) − cos( y)7510013116 3m ⋅ m F (m1, m2 , R ) = 1 2 R210010087 4f ( x, y, z) = x2 + y2 + z 2100100933 5f ( x, y, z) = x3 + x ⋅ y + z 21001001176 66 f ( x) = ∑ xi i =11001001158 Примечание. В таблице использованы следующие обозначения: E – ошибка аппроксимации; C(n) – количество узлов в лучшем решении; N – номер поколения, на котором алгоритм нашел решение с заданной точностью. Величина d ΔndT ведет себя как производная термодинамических потенциалов, поэтому по ее аномалиям можно определить точку фазового перехода. Рис. 4. Зависимость линейного двупреломления Rb2MnCl4 при неаксиальном направлении распространения света от магнитного поля H || C4 при различных температурах [5] Рис. 5. Полевые зависимости кругового двупреломления света в Rb2MnCl4 от магнитного поля H || C4 с λ = 632,8 нм при различных температурах 12 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Рис. 6. Зависимости кругового двупреломления NaMnCl3 от магнитного поля H || C3 с λ = 632,8 нм при различных температурах Рис. 7. Фазовая диаграмма Rb2MnCl4: поле HSF получено с помощью линейного (+) и кругового (• и ○) двупреломления; линии графиков – схема ожидаемых фазовых границ Рис. 8. Результат работы генетического алгоритма (−): поле спин-флоп перехода HSF получено с помощью линейного (○) и кругового (•) двупреломления Рис. 9. Фазовая диаграмма NaMnCl3, построенная с помощью алгоритма генетического программиро- вания и основанная на экспериментальных данных по измерению двупреломления света: • – круговое двупреломления, H || C3; ○ – линейное дву- преломления, H ⊥ C3 Таким образом, применение коэволюционного ал- горитма генетического программирования позволило построить аналитические выражения для фазовых границ магнитного состояния кристаллов Rb2MnCl4 и NaMnCl3, на основании которых можно сделать выводы о применимости предложенных модельных оценок.

About the authors

S. S. Aplesnin

Email: aplesnin@sibsau.ru.

V. G. Zhukov

Email: vadimzhukov@mail.ru.

E. A. Popov

Email: epopov@bmail.ru.

Yu. Yu. Loginov

Email: loginov@sibsau.ru.

References

Supplementary files