Программные продукты и системы

Знание кристаллической структуры веществ является предпосылкой к знанию и предсказанию свойств материалов. Наиболее часто используемая техника для определения кристаллических структур – исследование монокристаллов (или отдельных больших кристаллитов). Структурный анализ методами порошкового дифракционного анализа необходим в тех случаях, когда затруднительно получить вещество в форме монокристалла, подходящего для анализа развитыми монокристальными дифракционными методами. Поскольку большинство веществ, и тем более многофазных материалов, находится в поликристаллической форме, потенциальная область применения методов порошковой дифракции очень обширна, а их развитие актуально.

Порошковые дифрактограммы объединяют все богатство информации об истинной кристаллической структуре, однако случайное и систематическое перекрытие пиков, обусловленное проекцией трехмерного обратного пространства на одномерную ось, приводит к сильному уменьшению данных для отдельного кристалла. Тем не менее, несмотря на потери угловой информации, в одномерный набор данных передается достаточная информация для реконструкции структуры в объеме при помощи различных математических методов моделирования и оптимизации.

Задача поиска структурной модели

Рассмотрим основные этапы структурного анализа. После установления формулы соединения и регистрации дифрактограммы происходят определение (индицирование) и уточнение параметров решетки, а затем пространственной группы симметрии. Далее выполняется полнопрофильная декомпозиция интенсивности перекрытых рефлексов дифрактограммы с использованием известных методов ЛеБэйля или Поули. Следующий этап – поиск модели неизвестной кристаллической структуры. Третьим этапом структурного анализа является уточнение найденной модели.

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

Эффективным средством решения многопараметрических оптимизационных задач в различных областях науки и техники зарекомендовали себя генетические алгоритмы (ГА). Известны работы, например, Харриса и ряда других авторов по применению классического ГА для определения кристаллических структур в прямом пространстве. Так, для решения задачи определения кристаллической структуры поликристаллического вещества по данным порошковой дифракции предложено использовать двухуровневый гибридный ГА, комбинированный с эффективными математическими методами оптимизации и подходящими дифракционными, кристаллохимическими и физическими критериями оценки структурных моделей [2]. Данный алгоритм при правильной настройке может обеспечивать эволюцию моделей с устойчивой сходимостью в глобальный оптимум, отвечающий истинной структуре, при существенном увеличении размерности структурных задач [3]. Однако определение правильной настройки является очень серьезной проблемой в прикладных задачах.

Для приведения терминологии кристаллографической задачи к терминологии ГА можно ввести следующие соответствия: степень свободы аналогична гену; последовательность степеней свободы, необходимая для идентификации положения, ориентации и внутреннего устройства структурной модели, аналогична хромосоме; целевая функция аналогична приспособленности, сопоставляемой каждому индивиду (хромосоме). Целевая функция основана на брэгговском R-факторе и использует интегральные интенсивности для упрощения расчета. Каждый индивид представляет некоторое решение задачи, то есть возможную кристаллическую структуру.

Задача 1-го уровня гибридного алгоритма – найти удовлетворительные (в смысле величины R-фактора) начальные приближения параметров модели. В процессе выполнения 2-го уровня происходит поиск пути спуска на гиперповерхности R-фактора из точек, полученных с 1-го уровня ГА. Эффективность сходимости к решению обеспечивает метод минимизации производной разнос- ти (МПР) расчетной и экспериментальной дифрактограмм. Однако для достижения глобаль- ного оптимума необходимо, чтобы начальные приближения, поступившие на 2-й уровень, были достаточно близки к решению. Таким образом, успех в достижении решения обеспечивает ГА, применяемый на 1-м уровне.

Коэволюционный асимптотический ГА

Одной из основных проблем при применении ГА является настройка его параметров, от которой существенно зависит эффективность работы. Стандартный ГА имеет как минимум три метода селекции (пропорциональная, турнирная и ранговая), три метода рекомбинации (одноточечная, двухточечная и равномерная) и несколько уровней мутации, требующих дополнительной настройки. Количество возможных комбинаций достигает многих десятков. Полный перебор комбинаций настроек требует чрезмерно много времени и вычислительных ресурсов и не может применяться на практике. Выбор настроек наугад – тоже плохое решение, так как эффективность ГА на одной и той же задаче может варьироваться от нуля до 100 % в зависимости от выбора параметров.

Существует несколько подходов к решению этой проблемы. Например, прямое кодирование параметров ГА нижнего уровня, решающего задачу оптимизации, в хромосому мета-ГА более высокого уровня, решающего задачу настройки параметров. Другой подход состоит в гибридизации ГА со специальным алгоритмом локального поиска в бинарном пространстве. В некоторых приложениях это приводит к низкой чувствительности эффективности ГА к выбору параметров, что позволяет избежать их настройки. Следующий подход – адаптация стратегии ГА за счет конкурирующих подпопуляций. Каждая подпопуляция имеет собственную стратегию (комбинацию параметров алгоритмов). Перераспределение ресурсов обеспечивает доминирование подпопуляции с наиболее подходящей для решаемой задачи стратегией поиска. Этот подход может рассматриваться как один из примеров коэволюционных ГА, отличающихся идеями организации взаимодействия стандартных ГА. В частности, ранее был предложен подход, использующий как конкуренцию, так и сотрудничество индивидуальных ГА, каждый из которых имеет свою комбинацию параметров [4]. Сотрудничество индивидуальных ГА достигается благодаря миграции лучших решений во все подпопуляции, что обеспечивает рост эффективности коэволюционного алгоритма за счет положительного эффекта взаимодействия подпопуляций. Проблемой применения коэволюционных алгоритмов является неопределенность выбора кандидатов для включения в коэволюцию. Число таких кандидатов не может превышать полутора–двух десятков алгоритмов, в то время как выбирать их надо из сотен.

Еще один полезный подход к решению проблемы выбора эффективных настроек ГА – сокращение количества настраиваемых параметров, например, использование так называемого вероятностного ГА, в котором операция скрещивания была заменена на генерирование потомков в соответствии с распределением вероятностей их компонент. Распределение вероятностей изменялось таким образом, чтобы возрастала вероятность правильного значения гена на конкретном месте в хромосоме. Очевидно, что выбор типа рекомбинации в таком алгоритме не требуется, что сокращает количество возможных комбинаций параметров в три раза.

Еще меньше настраиваемых параметров содержит асимптотический вероятностный ГА [5], в котором применяется адаптивная мутация, не требующая предварительной настройки. Дополнительным преимуществом асимптотического алгоритма является способ выполнения генетических операторов, который сводится к изменению распределения вероятностей компонент, что значительно сокращает время на проработку алгоритма. Фактически асимптотический вероятностный ГА имеет всего несколько комбинаций настроек параметров.

В данной работе применен разработанный авторами коэволюционный подход к организации работы асимптотического вероятностного ГА (КАГА), благодаря которому проблема выбора типов применяемых генетических операторов отсутствует.

Данный алгоритм сначала был протестирован на стандартном наборе тестовых функций безусловной оптимизации (например, на функциях Растригина, Розенброка, Катковника, ДеЙонга и др.). Результаты тестирования сравнили с результатами работы индивидуальных стандартных ГА при равных вычислительных ресурсах (произведение количества индивидов в популяции на число поколений). Усреднение проводилось по 100 запускам каждого алгоритма.

Исследования показали, что на большинстве задач предложенный подход по надежности не уступает наилучшему индивидуальному стандартному ГА (см. табл.) и превосходит его по скорости выполнения. Здесь под надежностью понимается отношение числа запусков, в которых с заданной точностью найден известный оптимум, к общему числу запусков. Скорость – среднее количество вычислений оптимизируемой функции.

Таким образом, КАГА показывает высокую надежность и эффективность на большинстве тестовых задач и не уступает стандартному ГА. Главное его преимущество заключается в автоматической настройке практически всех параметров, что значительно уменьшает влияние человеческого фактора на работу алгоритма и повышает эффективность поиска решения.

Результаты решения задач поиска структуры с помощью КАГА

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

В первом случае было необходимо по реальной дифрактограмме определить структуру соединения Pd(NH3)2(NO2)2. Единственный на ячейку атом Pd, как и при решении в [2], зафиксирован в центре инверсии, в общих позициях размещались 4 атома N и O (12 искомых координат), атомы водорода исключены из поиска. Независимая часть ячейки для каждого атома определяет следующую область поиска: xÎ[0; 0,5], y, zÎ[0; 1].

Результаты тестирования. Сравнение КАГА с индивидуальными алгоритмами

Использовалась точность кодирования 5 бит на переменную. Выраженная преимущественная ориентация не моделировалась для усложнения задачи поиска, что привело к величине целевой функции (R-фактора) в точке минимума, рав- ной 19,08.

Был осуществлен ряд пусков алгоритма, в которых варьировались размеры популяций и количество поколений. Во всех полученное решение было достаточно близким к известному [2], так что на втором уровне оно сводилось алгоритмом уточнения структуры к точному. Типичный пример сходимости процесса коэволюционного поиска продемонстрирован на рисунке 1. Каждая из линий соответствует какому-либо алгоритму, входящему в коэволюцию. Отдельная точка показывает значение пригодности лучшего индивида популяции в конкретный момент.

Вторая задача поиска кристаллических структур химических соединений заключается в отыскании структуры соединения K4SnO4. Количество переменных равно 27 – по 3 координаты на девять атомов. Точность кодирования – 5 бит на переменную. Поиск проводился по всей независимой части ячейки: x, yÎ[0; 1], zÎ[0; 0,5].

На рисунке 2 приведен пример хода процесса коэволюционного поиска. В связи с увеличением размерности задачи количество выделенных алгоритму ресурсов также было увеличено.

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

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

Литература

1. David W.I.F., Shankland K. Structure determination from powder diffraction data // Acta Cryst. 2008. A64, pp. 52–64.

2. Yakimov Y.I., Semenkin E.S., Yakimov I.S. Two-level genetic algorithm for a fullprofile fitting of X-ray powder patterns //

Z. Kristallogr. Suppl. 2009. Vol. 30, pp. 21–26.

3. Якимов Я.И., Семёнкин Е.С. Автоматизированная система рентгеноструктурного анализа поликристаллов // Программные продукты и системы. 2009. № 4 (88). С. 82–84.

4. Sergienko R., Semenkin E. Competitive Cooperation for Strategy Adaptation in Coevolutionary Genetic Algorithm for Constrained Optimization // IEEE World Congress on Computational Intelligence (WCCI'2010). Barcelona, Spain, 2010, pp. 1626–1631.

5. Галушин П.В., Семёнкин Е.С. Асимптотический вероятностный генетический алгоритм // Вестн. СибГАУ им. акад. М.Ф. Решетнева. 2009. Вып. 4 (25). С. 37–42.