ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2017 г.)
2-летний импакт-фактор РИНЦ: 0,500
2-летний импакт-фактор РИНЦ без самоцитирования: 0,405
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,817
5-летний импакт-фактор РИНЦ: 0,319
5-летний импакт-фактор РИНЦ без самоцитирования: 0,264
Суммарное число цитирований журнала в РИНЦ: 6012
Пятилетний индекс Херфиндаля по цитирующим журналам: 404
Индекс Херфиндаля по организациям авторов: 338
Десятилетний индекс Хирша: 17
Место в общем рейтинге SCIENCE INDEX за 2017 год: 527
Место в рейтинге SCIENCE INDEX за 2017 год по тематике "Автоматика. Вычислительная техника": 16

Больше данных по публикационной активности нашего журнале за 2008-2017 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2018

Коэволюционный асимптотический генетический алгоритм для определения кристаллических структур

Coevolutionary asymptotic genetic algorithm for crystal structure characterization
Статья опубликована в выпуске журнала № 3 за 2011 год.[ 11.09.2011 ]
Аннотация:При восстановлении кристаллической структуры вещества по данным порошковой дифракции возникает задача определения модели неизвестной атомной структуры сложных химических соединений. В работе предложен и исследован эволюционный алгоритм безусловной оптимизации, позволяющий определять параметры структурной модели вещества, необходимые для следующего этапа уточнения кристаллической структуры.
Abstract:When restoring material’s crystal structure on the basis of powder diffraction a problem of determining a model of the atomic structure of complex chemical compounds appears. In this research the evolutionary algorithm for unconstrained optimization was developed and analyzed. It allows to define parameters of the structural model of material which are necessary for the next stage of the crystal structure refinement.
Авторы: Семенкин Е.С. (styugin@rambler.ru) - Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, г. Красноярск, Россия, Швец А.В. (alexandershvets@mail.ru) - Сибирский федеральный университет, г. Красноярск, , , Якимов И.С. (I-S-Yakimov@yandex.ru) - Сибирский федеральный университет, г. Красноярск, , , кандидат технических наук
Ключевые слова: дифракционный анализ, структурная модель вещества, безусловная оптимизация, коэволюционный асимптотический генетический алгоритм
Keywords: diffraction analysis, structural model of material, unconstrained optimization, coevolutionary asymptotic genetic algorithm
Количество просмотров: 5580
Версия для печати
Выпуск в формате PDF (5.05Мб)
Скачать обложку в формате PDF (1.39Мб)

Размер шрифта:       Шрифт:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функция

Надежность лучшего индивидуального ГА

Скорость ГА

Надеж-ность КАГА

Скорость КАГА

AdditivePotential

1

2160

1

1062

DeJong2

1

3040

1

2226

GaussianQuartic

1

2990

1

1861

Griewank

0,98

1428

0,6

3813

Ackley

1

2745

1

2014

Ackley2

1

2775

1

1850

Griewank2

1

2130

1

2146

Himmelblau

0,72

6764

0,4

2237

HyperEllipsoid

1

2595

1

2180

HyperEllipsoid2

1

3875

1

2073

Rastrigin

1

3490

1

3881

Katkovnik

1

3310

1

2278

Multiextremal3

1

3415

1

1747

Multiextremal4

1

4330

1

1838

MultiplicativePotential

1

1845

1

1335

Rastrigin2

1

2415

1

1964

Rastrigin3

1

3425

0,98

4259

RastriginWithTurning

1

2970

1

1948

Rosenbrock

0,36

6666

0,44

6502

SphereModel

1

2880

1

1861

Среднее значение

0,953

3262

0,921

2454

Использовалась точность кодирования 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.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=2836
Версия для печати
Выпуск в формате PDF (5.05Мб)
Скачать обложку в формате PDF (1.39Мб)
Статья опубликована в выпуске журнала № 3 за 2011 год.

Назад, к списку статей

Хотите оценить статью или опубликовать комментарий к ней - зарегистрируйтесь