Методы экспрессной обработки результатов относительной двухволновой рентгеновской рефлектометрии для контроля многослойных структур микро- и наноэлектроники тема диссертации и автореферата по ВАК РФ 05.11.13, кандидат наук Карташов, Дмитрий Александрович

• Карташов, Дмитрий Александрович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Карташов, Дмитрий Александрович

Оглавление

Актуальность проблемы

Методы исследований

Научная новизна работы

Практическая ценность работы заключается в следующем:

Апробация работы и публикации

Личный вклад автора

Достоверность результатов

Публикации

Основные положения, выносимые на защиту

Структура и объём работы

Глава 1. Аналитический обзор литературы

1.1. Использование параллельных вычислительных систем для расчёта параметров многослойных структур, измеренных с помощью рентгеновских методов

1.1.1. Технология NVIDIA CUDA

1.1.2. Расчет параметров многослойных структур

1.2. Расчет коэффициента отражения рентгеновского излучения

1.3. Выводы к главе 1

Глава 2. Методы исследования

2.1. Неразрушающие методы

2.2. Разрушающие методы

2.3. Выводы к главе 2

Глава 3. Решение прямой задачи в рентгеновской рефлектометрии

3.1. Привязка алгоритма пчёл к решаемой задаче

3.2 Исследование влияния диапазона поиска и количества итераций на функцию ошибки

3.2.1 Однослойная структура (Al-Si)

3.2.2 Трёхслойная структура (Al-Si-Al-Si)

3.3 Определение эффективности применения известных и собственных алгоритмов для расшифровки моделируемых рентгеновских рефлектограмм58

3.3.1 Описание эксперимента

3.4 Экспрессный метод обработки результатов относительной двухволновой

рентгеновской рефлектометрии

3.5.Технологический подход к анализу многослойных структур

3.8 Выводы к главе 3

Глава 4. Решение обратной задачи в рентгеновской рефлектометрии

4.1 Увеличение точности компьютерной обработки относительных рентгеновских рефлектограмм

4.2 Повышение эффективности обработки результатов относительной двухволновой рентгеновской рефлектометрии при использовании графических процессоров и технологии CUDA

4.2.1 Описание эксперимента

4.2.2 Основные результаты

4.3.Расшифровка экспериментальных рентгеновских рефлектограмм при помощи распространённых и собственных алгоритмов. Сравнение их эффективности

4.3.1 .Методика эксперимента

4.3.2,Обсуждение результатов

4.4.Измерение образцов независимыми методами

4.5 Выводы к главе 4

Основные результаты и выводы

Благодарности

Список литературы

Приложение 1 . Стохастические алгоритмы оптимизации

1.1. Использование параллельных вычислительных систем на основе технологии NVIDIA CUDA и алгоритмов поиска глобального минимума функционала невязкидля параллельных вычислительных систем

1.1.1 Введение

1.1.2 Оптимизация, основанная на коллективном интеллекте

1.1.3 Генетический алгоритм

1.1.4 Алгоритм роя частиц

1.1.5 Муравьиный алгоритм

1.1.6 Алгоритм пчёл

1.1.7. Алгоритмы поиска глобального минимума функционала невязки,

используемые для решения обратной задачи в рентгеновской рефлектометрии

Введение диссертации (часть автореферата) на тему «Методы экспрессной обработки результатов относительной двухволновой рентгеновской рефлектометрии для контроля многослойных структур микро- и наноэлектроники»

Введение

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

- экспрессность методов, включая увеличение скорости обработки информативных сигналов и представление результатов в приборах и средствах контроля;

- точность измерения, не уступающую точности других методик при сохранении экспрессности (оперативности) контроля для получения не только начальных и конечных, но и промежуточных результатов технологического цикла.

- экспрессность методики и при этом сохранение её точности при обработке результатов позволяет расширить диапазон и номенклатуру измеряемых параметров т.е. измерять не только толщины, но и шероховатости межслойных границ раздела (т.е. увеличить количество слоев в модели шероховатости до ранее недостижимых значений при той же экспрессности), а также измерять параметры не только нанослоёв, но и межслойных границ раздела.

Экспрессность и оперативность применения рентгеновских методов для контроля технологии микро- и наноэлектроники возникла с одной стороны за счёт применения нового алгоритмического и программно-технического обеспечения процессов обработки информативных сигналов, получаемых с помощью рентгеновских измерений, а с другой - явилось следствием разработки и оптимизации

методов расчёта и проектирования системы неразрушающего рентгеновского контроля с учетом особенностей объектов контроля, т.е. применения измерительной базы нового поколения (рентгеновского комбайна разработки А.Г. Турьянского, ФИАН им. П.Н. Лебедева) для контроля параметров наноразмерных приборных структур. Это позволило:

-использовать незащищённое рабочее пространство; -сократить энерго- и водопотребление;

-использовать возможности персонала с меньшим уровнем подготовки.

В этом комбайне реализована впервые для практического применения двухволновая рентгенооптическая схема, а также предусмотрена работа с рентгеновскими пучками малой мощности (до 300 Вт).

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

Данный существенно модернизированный рентгеновский комплекс позволяет впервые получить информативный сигнал в виде зависимости отношения коэффициентов отражения рентгеновского излучения на двух близких длинах волн (0,154 нм. и 0,139 нм.) от угла скольжения. Однако для получения параметров экспериментальных многослойных структур (толщины и плотности слоев, а также шероховатости межслойных границ раздела) из исходного информативного сигнала необходимо решение обратной задачи.

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

Это в свою очередь преследует следующие цели:

- анализ физических особенностей объекта контроля, т.е. наноразмерных твердотельных структур;

- разработка и оптимизация методов расчета информативных сигналов с учетом особенностей модели объектов контроля;

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

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

Методы исследований. Для изучения исследуемых образцов были использованы:

-методика относительной двухволновой рентгеновской рефлектометрии, реализованная в многофункциональном рентгеновском рефлектометре (МИЭТ, установка МИНИЛАБ-6, разработки А.Г. Турьянского, ФИАН им. П.Н. Лебедева, произведена ООО "Институт Рентгеновской Оптики", г. Москва, РФ, 2007г);

-методика прецизионной профилометрии, реализованная в профилометре AlphaStep-200 (ОАО "НИИМЭ и Микрон", установка AlphaStep-200, произведена KLA, США, 1988г);

- методика измерения линейных размеров, реализованная в растровом электронном микроскопе Quanta-200 3D (ОАО "НИИМЭ и Микрон", установка Quanta-200 3D, произведена FEI, Нидерланды, 2007г);

- методика измерения толщины металлических слоев ультразвуковым методом, реализованная в установке измерения толщины металлических слоёв (ОАО "НИИМЭ и Микрон", установка Metapulse-200, произведена Rudolph, США, 2008г).

Обработка результатов измерений проводились на персональном компьютере с поддержкой технологии CUD А на следующих программах: ХОР, Reflectometry Tool и программе, разработанной автором диссертации.

Научная новизна работы

В процессе исследования получены следующие новые научные результаты:

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

-к увеличению точности;

-к увеличению оперативности.

2. Алгоритм минимизации целевой функции, разработанный с применением предложенного автором диссертации способа определения уменьшенного диапазона поиска, позволил добиться на пятнадцать порядков меньшей функции ошибки для модельных МС, состоящих из 1 - 5 слоёв.

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

Практическая ценность работы заключается в следующем:

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

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

3) Использование обработки результатов рентгеновской рефлектометрии предлагаемым методом на тестовых пластинах (плёнки металлов и диэлектриков на кремнии) по сравнению с измерениями независимыми методами контроля (РЭМ, прецизионная профилометрия, ультразвуковой метод на приборе Ме1ари1Бе) показало их превосходство по совпадению измеряемых величин по сравнению с величинами, полученными другими независимыми методами.

Использование результатов работы. Результаты диссертационной работы используются при автоматизированной обработке информативных сигналов, полученных методом относительной двухволновой рентгеновской рефлектометрии в лаборатории радиационных методов технологии и анализа в МИЭТе, а также в ООО "Институт Физической Оптики", г. Москва. Разработанные методы апробированы на образцах, предоставленных ОАО "НИИМЭ и Микрон", показали удовлетворительные результаты и применимость для контроля технологических процессов.

Апробация работы и публикации

Полученные результаты были многократно представлены и обсуждались в докладах на российских и международных конференциях: "Микроэлектроника и Информатика - 2009", МИЭТ, Зеленоград (2009); Международная конференция "Микро- и наноэлектроника - 2009" (ICMNE-2009), Звенигород (2009); "Микроэлектроника и Информатика - 2010", МИЭТ, Зеленоград (2010); "ВНКСФ -16", Волгоград (2010); "Кремний - 2010", Нижний Новгород (2010); "Нанотехнологии - 2010". Дивноморское (2010); "Хаос и структуры в нелинейных системах. Теория и эксперимент", Караганда (2010); "Физические и физико-химические основы ионной имплантации - 2010", Нижний Новгород (2010); X-th International Conference on Nanostructures Materials NANO-2010, Italy, Roma, 2010, Abstract book, p. 77;X Всероссийская научно-техническая конференция молодых специалистов "Твердотельная электроника, сложные функциональные блоки РЭА", Дубна (2011); "Кремний - 2011", Москва (2011); III Научно-техническая конференция молодых учёных и специалистов, Москва, Зеленоград (2011); II Международная научно-техническая конференция "Технологии микро- и наноэлектроники в микро- и наносистемной технике", Москва, Зеленоград (2011); "Рентгеновское, синхротронное излучения, нейтроны и электроны для исследования наносистем и наноматериалов. Нано-Био-Инфо-Когнитивные технологии - 2011", Москва (2011); - 219-th ECS Meeting, Canada, Monreal (2011); XIV-я международная конференция DSPA-2012 "Цифровая обработка сигналов и её применение", Москва, (2012); VII Международная научно-практическая конференция "Актуальные проблемы современных наук", Новости информационных технологий, Плзень, Польша, (2012);Х1 Всероссийская научно-техническая конференция молодых специалистов "Твердотельная электроника, сложные функциональные блоки РЭА", Дубна (2012);Ш Международная научно-техническая конференция "Технологии микро- и наноэлектроники в микро- и наносистемной технике", Москва, Зеленоград (2012); "Микроэлектроника и Информатика - 2013", МИЭТ, Зеленоград (2013).

Свидетельства о государственной регистрации программ для ЭВМ

В ходе работы были получены следующие свидетельства о государственной регистрации:

1. Герасименко Н. Н., Карташов Д. А.

Программный комплекс автоматизированной оценки параметров наноструктур по результатам рентгенооптических измерений, регистрационный № 2010610386 (заявка № 2009616133, зарегистрировано в реестре программ для ЭВМ 11 января 2010 года).

2. Герасименко Н. Н., Карташов Д. А., Медетов Н. А., Орлов Р. С.

Программа расчёта рентгеновских рефлектограмм на видеокартах NVidia с технологией CUD А, регистрационный № 2010615187 (заявка № 2010613431, зарегистрировано в реестре программ для ЭВМ 11 августа 2010 года).

Личный вклад автора

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

- разработан новый алгоритм решения обратной задачи и реализовано решение прямой задачи по технологии CUDA, в результате чего получено 2 свидетельства о государственной регистрации программы для ЭВМ;

- представлены и реализованы в виде компьютерных программ экспрессные методы анализа информативных сигналов, полученных методом относительной двухволновой рентгеновской рефлектометрии;

- проведены эксперименты по апробированию методики и численных расчётов на экспериментальных и модельных образцах;

- разработаны и протестированы программы для решения прямой задачи по технологии CUDA и обратной задачи на языке С#;

- проведена обработка и интерпретация результатов экспериментов и расчётов;

- проведён выбор и подготовка образцов для исследований в соответствии с предлагаемой программой и методикой контроля.

Достоверность результатов

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

Публикации

По теме диссертации опубликована 32 печатная работа, в том числе 20 докладов на конференциях, 10 статей в рецензируемых журналах, из которых 3 входят в перечень, утверждённый ВАК, получено 2 свидетельства о государственной регистрации программ для ЭВМ.

Основные положения, выносимые на защиту

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

2. Разработанная для анализа полученных с помощью рентгеновской рефлектометрии информативных сигналов оригинальная система алгоритмов, объединяющая возможности стохастических алгоритмов (алгоритм пчёл, алгоритм роя частиц и т.д.), позволяет:

-увеличить скорость достижения результата решения обратной задачи на порядок; -увеличить точность результата решения обратной задачи до двух раз.

3. Технология параллельных вычислений С1ГОА способствует ускорению решения

обратной задачи на один-два порядка по сравнению с общепринятыми методами

11

благодаря применению параллельных методов обработки результатов измерений. Это позволяет увеличить количество слоев в МС на один-два порядка при сохранении такого же времени расчёта одной МС как на центральном процессоре.

Структура и объём работы

Диссертация изложена на 143 страницах, проиллюстрирована 16 таблицами и 33 рисунками, содержит введение, 4 главы, основные результаты и выводы, список цитируемой литературы, состоящий из 100 наименований, и приложение.

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

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

Система компьютерных подходов для обработки результатов дополнена применением технологии CUD А, которая позволила существенно повысить скорость обработки результатов путём использования видеокарт.

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

Глава 1. Аналитический обзор литературы

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

Некоторые многослойные периодические структуры металл/кремний оказались очень перспективными отражающими элементами в оптике дальнего ультрафиолетового диапазона (1 <2<50нм). В последние годы были достигнуты существенные успехи в изготовлении высокоотражающих многослойных рентгеновских зеркал Mo/Si в связи с их перспективностью для рентгеновской литографии на длине волны 13,4 нм. Значительные усилия исследователей были направлены на понимание реальной структуры этих многослойных периодических покрытий (МПП) как в исходном состоянии, так и после отжига. МПП Se/Si с периодом 20-35 нм являются перспективными зеркалами для диапазона длин волн 35<А<50нм. Они нашли применение для управления излучением рентгеновского лазера с длиной волны Л = 46,9 нм, в рентгеновской микроскопии. Оптические свойства многослойных рентгеновских зеркал существенным образом зависят от наличия прослоек промежуточных фаз на границах раздела слоев исходных материалов. Это обстоятельство послужило дополнительным стимулом к изучению процессов диффузии и фазообразования в многослойных структурах металл/кремний.

Слоистые структуры металл/кремний, используемые в качестве изделий микроэлектроники и в качестве оптических элементов для мягкого рентгеновского диапазона, имеют наноразмерную толщину слоев, поэтому исследование ранних

стадий диффузии и фазообразования в этих системах является необходимым звеном в понимании их свойств. Кроме того, многослойные периодические покрытия оказались очень удобными модельными объектами для изучения процессов диффузии и силицидообразования. С точки зрения дифракции такие покрытия являются искусственными одномерными кристаллами. Малоугловая рентгеновская дифракция (РД) от границ слоев весьма чувствительна к малейшим изменениям структуры межфазных границ раздела. Это даёт возможность с высокой точностью определять толщину промежуточной фазы и чистых компонентов. Взаимодополняющим структурным методом исследования межфазных границ раздела является высокоразрешающая электронная микроскопия (ЭМ) поперечных срезов. Эта методика даёт общее представление о структуре отдельных слоёв.

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

Возьмём например правило Бене-Вольсера. Это правило заключается в том, что диффузионный массоперенос при отжиге бинарной диффузионной пары обеспечивает приближение термодинамической системы к равновесию. Поэтому между диаграммой состояния и диффузионной зоной существует однозначная связь. Если диффузионная зона протяжённая, а время диффузионного отжига продолжительное, то она должна состоять из слоёв-фаз, химический состав и порядок следования которых в диффузионной зоне должен соответствовать диаграмме фазового равновесия[1-3].

Рассмотрим кинетический подход Геселя и Ту. В тонкоплёночных диффузионных парах (случай тонких плёнок) металл/кремний обнаруживаются не все промежуточные фазы-силициды, имеющиеся на диаграмме фазового равновесия [5, 6]. Как правило, экспериментально наблюдают одну из фаз. Например, в диффузионной паре Ni/Si наблюдается силицид Ni2Si при температурах выше 200 ° С. Другие равновесные силициды NijSi, Ni3Si2, Ni5Si2, NiSi и NiSi2 в диффузионной зоне не образуются при условии, что исходные компоненты полностью не израсходовались. Для более толстых диффузионных пар, скажем, более 10 мкм (случай массива) в

14

диффузионном пространстве имеются все промежуточные равновесные фазы, предсказываемые диаграммой фазового равновесия. Для объяснения явления преобладания роста одной из фаз на начальных стадиях роста Гесель и Ту в своей работе [10] исследуют влияние реакционных барьеров на межфазных границах раздела на кинетику роста фаз в диффузионной зоне. Схема, иллюстрирующая основную идею работы [10], представлена на рис. 1.1.

Рисунок 1.1. Схематический концентрационный профиль атомов А в диффузионном пространстве АаВ/ А ¡¡В/ АуВ («>/?>;') без учёта и с учётом барьера химической реакции [24]. Фаза А^В является промежуточным соединением. СД,— равновесная концентрация.

Шварц и Джонсон в своей работе [12] впервые показали, что взаимная диффузия в тонкоплёночных кристаллических металлических многослойных структурах может приводить к образованию аморфных промежуточных фаз на межфазных границах раздела между исходными компонентами. Это явление получило название реакции твердофазной аморфизации (РТФА). Впоследствии РТФА наблюдалась на многих металлических системах, состоящих, главным образом, из слоев переходных металлов. При этом один слой состоит из так называемого "ближнего" переходного металла с малым числом электронов на недостроенной с1-

оболочке (например, Ti, Zr, Hf, ...), а другой слой — из "дальнего" переходного металла, соответственно с большим числом электронов на недостроенной d-оболочке (например, Fe, Со, Ni, ...). Явление РТФА было впервые открыто Кохом и др. [13] и наблюдается также при механическом сплавлении металлических порошков в шаровой мельнице. В этой технологии взаимная диффузия является основным механизмом сплавления порошков.

Многочисленные экспериментальные данные показывают, что часто в начальный момент времени на межфазной границе раздела металл/кремний также образуются аморфные силициды: Mo/Si [4, 20-22], Ti/Si [23-26], V/Si [25], Ni/Si [27], Co/Si [28], Rh/Si [29], Gd/Si [30], Tb/Si [31] и др. Движущей силой образования силицидов, в том числе и аморфных, является отрицательная теплота смешения металла и кремния, которая рассчитана для многих пар металл/кремний в работе [32] исходя из модели Миедемы [33].Рассмотрим модели, объясняющие образование метастабильных фаз на межфазных границах раздела в начальный момент времени. Объяснение явления образования метастабильных фаз на межфазных границах раздела в начальный момент времени, основанное на принципах неравновесной термодинамики, даётся в работе Бене [34]. В самые начальные моменты фазообразования промежуточная фаза зарождается и растёт в сильно неравновесных условиях, при наличии большого градиента химического потенциала, поэтому основной принцип равновесной термодинамики (принцип минимума свободной энергии) вряд ли применим в этих условиях. Действительно, как правило, первым образуется не силицид с наибольшей отрицательной энергией образования (энергией на атом силицида или энергией на атом металла).

Напротив, часто образуется и растёт метастабильная фаза, аморфная или высокотемпературная. Автор работы [34] предполагает, что зарождение силицидной фазы и её рост на начальных стадиях являются кинетически контролируемыми процессами. Эволюция структуры должна идти в направлении уменьшения свободной энергии Гиббса, но при этом свободная энергия не обязательно минимальна на пути термодинамической системы. Автор сравнивает межфазную границу раздела с кристаллизацией сильно переохлаждённого пара (рост снежинок). При малом переохлаждении кристалл должен иметь сферическую форму, так как она

16

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

Автор работы [34] считает, что принцип максимального снижения свободной энергии системы может быть положен в основу отбора и роста промежуточной фазы на начальных стадиях роста. В случае выполнения параболического закона диффузии увеличение толщины (х) растущей промежуточной фазы

(1.1)

Л 2х

где Б — эффективный коэффициент диффузии.

Скорость уменьшения свободной энергии можно записать как

= (1.2)

Л 2х

где АС— различие свободных энергий растущей фазы и исходного состояния разделённых компонентов.

Гесель и Ту в работе [35] использовали идею Бене [34] при модификации своей кинетической теории отбора фаз в диффузионной зоне [10] для случая метастабильной аморфной фазы. Авторы рассматривают случай, когда аморфная фаза уже образовалась и растёт в диффузионной зоне. Авторы [35] исследуют вопрос о существовании критической толщины аморфной фазы и о том, что будет происходить в аморфной фазе после достижения этой критической толщины: будет ли она сосуществовать с кристаллической фазой или станет кинетически неустойчивой и исчезнет. Подход авторов состоит в исследовании взаимного расположения зависимостей свободной энергии Гиббса аморфной (Оа) и кристаллической (Ос) фазы от концентрации. Если зависимость Оа лежит ниже общей касательной к зависимости свободной энергии образующейся второй кристаллической фазы Ос и одного из чистых компонентов, то аморфная фаза может сосуществовать с новой кристаллической фазой и продолжать расти. В противоположном случае, когда кривая ва расположена выше общей касательной к кривой Ос и одного из чистых

Список литературы диссертационного исследования кандидат наук Карташов, Дмитрий Александрович, 2013 год

Список литературы

1. Зубарев E.H. Реакционная диффузия в наноразмерных слоистых системах металл/кремний. УФН.: том. 181, №5,(2011)

2. Гегузин Я Е Диффузионная зона (М.: Наука, 1979)

3. Tu K--N, Mayer J W, Feldman L С Electronic Thin Film Science: for Electrical Engineers and Materials Scientists (New York: Macmillan, 1992)

4. Брик В Б Диффузия и фазовые превращения в металлах и сплавах (Киев: Наукова думка, 1985)

5. Holloway К, Do К В, Sinclair R J. Appl. Phys.65 474 (1989)

6. Murarka S P Silicides for VLSK Applications (New York: Academic Press, 1983) [Мьюрарка. Силициды для СБИС(М.: Мир, 1986)]

7. Poate J М, Tu К N, Mager J W (Eds) Thin Films-Interdiffusion and Reactions (New York: Wiley, 1978) [ПоутДж, TyK N, МейерДж (Ред.)Тонкие пленки. Взаимная диффузия и реакции (М.: Мир, 1982)]

8. Walser R М, Bene R W Appl. Phys. Lett.28 624 (1976)

9. Shewmon P G Diffusion in Solids (New York: McGraw-Hill, 1963) [Шьюмон П Диффузия в твердых телах (М.: Металлургия, 1966)]

10.Mader S Thin Solid Films 35 195 (1976)

11. Gosele U, Tu К N J. Appl. Phys.53 3252 (1982)

12. Tu К N Annu. Rev. Mater. Sei. 15 147 (1985)

13. Schwarz R В, Johnson W L Phys. Rev. Lett.51 415 (1983)

14. Koch С С et al. Appl. Phys. Lett.43 1017 (1983)

15. Cotts E J, Meng W J, Johnson W L Phys. Rev. Lett.57 2295 (1986)

16. Cotts E J, Wong G C, Johnson W L Phys. Rev. В 37 9049 (1988)

17. Dorner W, Mehrer H Phys. Rev. В 44 101 (1991)

18. Donovan E P et al.J. Appl. Phys. 57 1795 (1985)

19. Donovan E P et al.Appl. Phys. Lett. 42 698 (1983)

20. Petford-Long А К et al.J. Appl. Phys.61 1422 (1987)

21. Bugaev E A et al.Surface Investigation^ 141 (1999)

22. Slaughter J M et al.Pros. SPIE1343 73 (1991)

23. Holloway K, Sinclair R J. Appl. Phys.61 1359 (1987)

24. Holloway K, Sinclair R J. Less Common Met. 140 139 (1988)

25. Nathan M J. Appl. Phys. 63 5534 (1988)

26. Gong S F et al J. Appl. Phys.68 4535 (1990)

27. Ma E et al. Appl. Phys. Lett.53 2033 (1988)

28. Wang W H, Wang W K J. Appl. Phys.76 1578 (1994)

29. Tu K N, Herd S R, Gosele U Phys. Rev. B 43 1198 (1991)

30. Chen J C, Shen G H, Chen L J J. Appl. Phys.84 6083 (1998)

31. Kjornrattanawanich B et al. Appl. Opt. 45 1765 (2006)

32. Gong S F, Hentzell H T G J. Appl. Phys.68 4542 (1990)

33. Miedema A R J. Less Common Met. 46 67 (1976)

34. Bene RW J. Appl. Phys. 61 1826 (1987)

35. Gosele U, Tu K N J. Appl. Phys.66 2619 (1989)

36. Stearns D G, Rosen R S, Vernon S P Proc. SPIE1547 2 (1992)

37. Slaughter J M et al.J. Appl. Phys.76 2144 (1994)

38. Andreev S S et al.Thin Solid Films415 123 (2002)

39. Becker H ct al. Proc. SPIE4688 503 (2002)

40. Bajt S, Stearns D G, Kearney PA J. Appl. Phys.90 1017 (2001)

41. Stearns M B, Chang C-H, Stearns D G J. Appl. Phys.71 187 (1992)

42. Voorma H-J et al.J. Appl. Phys.83 4700 (1998)

43. Niibe M et al. Proc. SPIE1343 2 (1991)

44. Voorma H-J et al.J. Appl. Phys.82 1876 (1997)

45. Yakshin A E et al.Physica B 283 143 (2000)

46. Cilia M, Verhoeven J J. Appl. Phys.82 4137 (1997)

47. Cheng Y et al. J. Appl. Phys.72 5165 (1992)

48. Stearns D G et al.J. Appl. Phys.67 2415 (1990)

49. Windt D L, Hull R, Waskiewicz W K J. Appl. Phys.71 2675 (1992)

50. Windt D L, Hull R, Waskiewicz W K J. Appl. Phys.71 2675 (1992)

51. Boercker D B, Morgan W L Proc. SPIE1547 47 (1992)

52. Slaughter J M et al.Phys. Rev. B 44 3854 (1991)

53. Bedrossian P J Surf. Sci. 320 247 (1994)

54. Bedrossian P J Surf. Sci. 322 73 (1995)

55. Vernon S P, Stearns D G, Rosen R S Appl. Opt. 32 6969 (1993)

92

56. Hasan M M, Highmore R J, Somekh R E Vacuum 43 55 (1992)

57. Birch J et al. Vacuum 68 275 (2002)

58. Zhou X W, Wadley H N G J. Appl. Phys.84 2301 (1998)

59. Eriksson F et al. Thin Solid Films 500 84 (2006)

60. Louis E et al. Proc. SPIE3997 406 (2000)

61. Folta J A et al.Proc. SPIE3676 702 (1999)

62. Bajt S et al. Proc. SPIE4506 65 (2000)

63. Shimizu M et al. Jpn. J. Appl. Phys.32 4074 (1993)

64. Feigl T et al. Proc. SPIE3997 420 (2000)

65. Yulin S A et al.Proc. SPIE4343 607 (2001)

66. Yulin S A et al.Proc. SPIE5645 289 (2005)

67. Yulin Setal. Proc. SPIE5751 1155(2005)

68. Yulin S et al. Microelectron. Eng. 83 692 (2006)

69. Gautier J et al. Appl. Opt. 44 384 (2005)

70. Shih W C, Stobbs W M Ultramicroscopy 32 219 (1990)

71. Burkhalter P G et al. J. Vac. Sci. Technol. B 9 845 (1991)

72. Kortright J B, Joksch St, Ziegler E J. Appl. Phys.69 168 (1991)

73. Windt D L J. Vac. Sci. Technol. A 18 980 (2000)

74. Salditt T, Metzger T H, Peisl J Phys. Rev. Lett.73 2228 (1994)

75. Salditt T et al. Phys. Rev. B 54 5860 (1996)

76. Windt D L et al.J. Appl. Phys.88 460 (2000)

77. Bower R W, Mayer J W Appl. Phys. Lett.20 359 (1972)

78. Guivarc'h A et al. J. Appl. Phys.49 233 (1978)

79. Bravman J C, Sinclair R J. Electron. Microsc. Tech.l 53 (1984)

80. Cheng J Y, Cheng H G, Chen L J J. Appl. Phys.61 2218 (1987)

81. Rosen R S et al.Appl. Opt.32 6975 (1993)

82. Cage P R, Bartlett R W Trans. Metall. Soc. AIME 233 832 (1965)

83. SloofW G et al. Scripta Metall.20 1683 (1986)

84. Nakajima H, Fujimori H, Masahiro K J. Appl. Phys. 63 1046 (1988)

85. Wang W-H et al.Phys. Rev. B 59 10811 (1999)

86. Cook H E, Hilliard J E J. Appl. Phys. 40 2191 (1969)

87. Loopstra O B et al.Phys. Rev. B 44 13519 (1991)

93

88. Cohen M H, Turnbull D J. Chem. Phys. 31 1164 (1959)

89. Cohen M H, Grest G S Phys. Rev. В 20 1077 (1979)

90. Spaepen F Mater. Sei. Eng. 97 403 (1988)

91. Sietsma J, Thijsse В J Phys. Rev. В 52 3248 (1995)

92. Данилин Б С, Сырчин В К Магнетронные распылительные системы (М.: Радио и связь, 1982)

93. Patelli А et al. Surf. Coat. Technol. 201 143 (2006)

94. Somekh RE J. Vac. Sei. Technol. A 2 1285 (1984)

95. Williams D B, Carter В С Transmission Electron Microscopy. A Textbook for Materials Science (New York: Springer-Science Business Media, 2009)

96. Barbee T W Opt. Eng. 25 899 (1986)

97. Spiller E Soft X-Ray Optics (Washington: SPIE Optical Engineering Press, 1994)

98. Stearns D G J. Appl. Phys. 65 491 (1989)

99. Виноградов А В и др. Зеркальная рентгеновская оптика (Под ред. А В Виноградова) (JL: Машиностроение, 1989)

100. Апрелов С.А. Многоволновая рентгеновская рефлектометрия для анализа многокомпонентных пространственно упорядоченных структур :дисс.канд. физмат. наук 01.04.10: защищена 22.05.2007: / Апрелов Сергей Аркадьевич.-М., 2007. -119с

Приложение 1. Стохастические алгоритмы оптимизации

1.1. Использование параллельных вычислительных систем на основе технологии NVIDIA CUDA и алгоритмов поиска глобального минимума функционала невязки для параллельных вычислительных систем

1.1.1 Введение

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

1.1.2 Оптимизация, основанная на коллективном интеллекте

Алгоритмы оптимизации, основанные на поведении популяций (Swarm Optimization Algorithms, SOAs) напоминают природные методы поиска оптимального решения. Ключевое различие между алгоритмами SOA и прямыми поисковыми алгоритмами такое как же, как между методом Монте-Карло и методом hill-climbing. Алгоритмы класса SOAs используют популяцию решений для каждой итерации вместо единичного решения. Популяция решений обрабатывается на каждой итерации, а результатом каждой итерации является новая популяция решений. Если задача оптимизации имеет единственное решение, члены популяции алгоритмов SOA могут в будущем сближаться к нему. Однако, если задача оптимизации имеет множество решений, в алгоритмах SOA могут быть захвачены несколько решений. К алгоритмам SOAs относятся:

-генетический алгоритм (GA), -муравьиный алгоритм (АСО), -алгоритм частичной роевой оптимизации (PSO), -алгоритм пчёл.

Общим для всех методов поиска, основанных на поведении популяции является стратегия, которая создаёт вариации найденных решений.

95

Рассматривая алгоритмы, сформулируем задачу, обозначив конкретный элемент алгоритма (пчела, муравей, особь) как особь, общую для всех алгоритмов.

Для данной задачи особь это минимальная, но самодостаточная единица, полностью описывающая объект т.е. многослойную структуру (плотности и толщины всех слоев в многослойной структуре (МС), шероховатость верхней и нижней границы раздела для каждого слоя в МС). Инициализация начальной популяции это инициализация всех переменных, относящихся к МС.

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

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

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

Алгоритм частичной роевой оптимизации — это оптимизационная процедура,

основанная на поведении групп, например стаи птиц или скопления рыб.

Индивидуальные решения в популяции представляются в виде точек, которые

эволюционируют или меняют своё положение со временем. Каждая частица изменяет

96

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

Известны и другие алгоритмы класса БОА, похожие на алгоритм пчёл. Однако, эти алгоритмы не так близко соответствуют поведению пчёл. В частном случае они не применимы к технике, которую используют пчёлы, когда собирают пищу.

Группа алгоритмов, использующих в своей основе идею эволюции Дарвина, называется эволюционными алгоритмами. В ней выделяют следующие направления.

• Генетические алгоритмы (ГА).

• Эволюционные стратегии.

• Генетическое программирование.

• Эволюционное программирование.

Генетические алгоритмы применяются для решения таких задач, как:

• поиск глобального экстремума многопараметрической функции,

• аппроксимация функций,

• задачи о кратчайшем пути,

• задачи размещения,

• настройка искусственной нейронной сети,

• игровые стратегии,

• обучение машин.

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

1.1.3 Генетический алгоритм

Природный механизм

Живые существа характеризуются их внешними параметрами (фенотипом). Некоторые из параметров оказываются полезными для выживания и размножения, другие скорее вредят. Все внешние данные особи кодируются ее цепью ДНК (генотипом). Отдельные участки этой цепи (гены) определяют различные параметры особи.

Согласно теории эволюции Чарльза Дарвина , особи популяции конкурируют между собой за ресурсы (пищу) и за привлечение брачного партнера. Те особи, которые наиболее приспособлены к окружающим условиям, проживут дольше и создадут более многочисленное потомство, чем их собратья. Скрещиваясь, они будут передавать потомкам часть своего генотипа. Некоторые дети совместят в себе части цепи ДНК, отвечающие за наиболее удачные качества родителей, и, таким образом, окажутся еще более приспособленными.

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

Изредка происходит мутация: некоторый случайный нуклеотид цепи ДНК особи может измениться на другой. Если полученная цепь будет использоваться для создания потомства, то возможно появление у детей совершенно новых качеств.

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

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

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

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

Классический генетический алгоритм

Основоположником современной теории генетических алгоритмов (ГА) считается Холланд (J.Holland), чья работа «Adaptation in Natural and Artificial Systems», стала классикой в этой области. В ней Холланд впервые ввел термин «генетический алгоритм». Сейчас описанный там алгоритм называют «классический ГА» (иногда «канонический ГА», canonical GA), а понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.

Ученики Холланда Кеннет Де Йонг (Kenneth De Jong) и Дэвид Голдберг (David Е. Goldberg) внесли огромный вклад в развитие ГА. На книгу Голдберга «Genetic algorithms in search optimization and machine learning», ссылаются авторы практически каждой работы по этой теме.

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

потомства. Таким образом, приспособленность нового поколения в среднем выше предыдущего.

Функция приспособленности и кодирование решений

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

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

В генетических алгоритмах никак не используются такие свойства функции, как непрерывность, дифференцируемость и т. д. Она подразумевается как устройство (blackbox), которое на вход получает параметры, а на выход выводит результат.

Теперь обратимся к кодировке набора параметров. Закодируем каждый параметр строкой битов. Если он принимает непрерывное множество значений, то выберем длину строки в соответствии с требуемой точностью. Таким образом, параметр сможет принимать только дискретные значения (этих значений будет степень 2), в некотором заданном диапазоне.

Например, пусть переменная хк принадлежит отрезку [xmin, хтах]. Закодируем ее бинарной строкой из I битов. Тогда строка sk обозначает следующее значение переменной хк\

~~ -^min ^(-^rnax -^min)/2 (п. 1.1.)

если в формуле обозначает значение бинарного числа, кодируемого этой строкой.

100

Если же некоторый параметр принимает конечное количество значений, к примеру, целые от 0 до 1000, то закодируем его бинарной строкой достаточной длины, в данном случае 10. Лишние 23 строки могут повторять уже закодированные значения параметра, либо они могут быть доопределены в функции приспособленности как «худшие», т. е. если параметр кодируется одной из этих строк, то функция принимает заведомо наименьшее значение.

Итак, мы определили для каждого параметра строку, кодирующую его. Особью будет называться строка, являющаяся конкатенацией строк всего упорядоченного набора параметров:

101100 11001011 01101100 1100 1 11101 (п. 1.2)

I Xi I Х2 I I 11 х„ I

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

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

1.1.3.4Схема работы алгоритма

На рисунке ri.1.1 изображена схема работы любого генетического алгоритма:

Рисунок п.1.1. Блок-схема работы генетического алгоритма.

В классическом ГА начальная популяция формируется случайным образом. Фиксируется размер популяции (количество особей в ней будем обозначать символом АО, который не изменяется в течение работы всего алгоритма. Каждая особь генерируется как случайная ¿-битная строка, где Ь — длина кодировки особи, она тоже фиксирована и для всех особей одинакова.

102

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

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

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

Шаг алгоритма состоит из трех стадий: генерация промежуточной популяции (intermediate generation) путем отбора (selection) текущего поколения (current generation), скрещивание (recombination) особей промежуточной популяции путем кроссовера (crossover), что приводит к формированию нового поколения (next generation), и мутация нового поколения. На рисунке п. 1.2 изображены первые две стадии:

Выбор Скрещивание

(копирование) (кроссовер)

Текущее Промежуточное Следующее

поколение I поколение I поколение 1+1

Рисунок п. 1.2. Первые две стадии работы ГА.

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

В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т. е. работает пропорциональный отбор (proportional selection). Можно его реализовать следующим образом: пусть особи располагаются на колесе рулетки, так что размер сектора каждой особи пропорционален ее приспособленности. Изначально промежуточная популяция пуста. Лраз запуская рулетку, выберем требуемое количество особей для записи в промежуточную популяцию. Ни одна выбранная особь не удаляется с рулетки. Такой отбор называется stochastic sampling.

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

В классическом генетическом алгоритме применяется одноточечный оператор кроссовера (1-point crossover): для родительских хромосом (т. е. строк) случайным образом выбирается точка раздела, и они обмениваются отсеченными частями. Полученные две строки являются потомками:

11010 01100101101=^ 10110 01100101101

10110 10011101001 =>11010 10011101001

К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью рт инвертируется. Эта вероятность обычно очень мала, менее 1%.

1011001100101101 => 1011001101101101

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

104

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

Схождением называется такое состояние популяции, когда все строки популяции почти одинаковы и находятся в области некоторого экстремума. В такой ситуации кроссовер практически никак не изменяет популяции. А вышедшие из этой области за счет мутации особи склонны вымирать, так как чаще имеют меньшую приспособленность, особенно если данный экстремум является глобальным максимумом. Таким образом, схождение популяции обычно означает, что найдено лучшее или близкое к нему решение (рисунок п. 1.3).

Рисунок п. 1.3. Схождение популяции ГА.

Ответом на поставленную задачу может служить набор параметров, кодируемый наилучшей особью последнего поколения.

Кодирование

Если сравнивать кодирование бинарным алфавитом и небинарным, то первый вариант обеспечивает лучший поиск с помощью гиперплоскостей, т. к. предоставляет максимальное их количество. Действительно, если требуется закодировать 21 значений, то для бинарного алфавита количество гиперплоскостей будет 3^, тогда как при использовании, к примеру, четырехзначного алфавита длина слов будет в 2 раза меньше, и гиперплоскостей будет 5й2, т. е. меньше.

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

х

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

С другой стороны, небинарные алфавиты зачастую обеспечивают более наглядное представление решений задачи.

Для большинства функций генетические алгоритмы будут работать лучше, если закодировать параметры в строку кодом Грея, а не прямым бинарным кодом. Это связано с т. н. Hamming cliffs, когда, к примеру, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Это можно показать на примере: пусть требуется минимизировать функцию

■л

/(х) - х . Если в популяции изначально преобладали отрицательные хорошие решения,

то с большой вероятностью она сойдется к —1 == 11___1. При этом достигнуть

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

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

Некоторые модели генетических алгоритмов

Гибридные алгоритмы

Идея гибридных алгоритмов (hybrid algorithms) заключается в сочетании генетического алгоритма с некоторым другим методом поиска, подходящим в данной задаче (зачастую это бывает hill-climbing). На каждом поколении каждый полученный потомок оптимизируется этим методом, после чего производятся обычные для ГА действия. При использовании hill-climbing получается, что каждая

особь достигает локального максимума, вблизи которого она находится, после чего подвергается отбору, скрещиванию и мутации.

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

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

Таким образом, применительно к нашей задаче, ГА может рассматриваться следующим образом: в данном контексте под "особью" понимается объект, полностью описывающий многослойную структуру (количество слоев, плотности и толщины слоев, шероховатость верхней и нижней границы каждого слоя). Под "популяцией" понимается набор ранее описанных объектов. Инициализация начальной популяции - это инициализация всех переменных, относящихся к МС, например, при помощи генератора случайных чисел. Под функцией полезности понимается значение функции ошибки с отрицательным знаком плюс 1, вычисляемое для каждого объекта. Операторы "скрещивания" и "мутации" работают с данными в объектах на уровне битов. Выбор "особей" в новую "популяцию" проводят преимущественно по большему значению функции полезности, что соответствует минимальной функции ошибки.

Параллельные ГА

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

107

Сделаем из классического ГА параллельный. Для этого будем использовать турнирный отбор. Заведем N/2 процессов (здесь и далее процесс подразумевается как некоторая машина, процессор, который может работать независимо). Каждый из них будет выбирать случайно из популяции 4 особи, проводить 2 турнира, и победителей скрещивать. Полученные дети будут записываться в новое поколение. Таким образом, за один цикл работы одного процесса будет сменяться целое поколение.

Другие модели

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

К примеру, пусть вероятность мутации для каждой особи будет отдельной. Можно добавить к строке особи подстроку, кодирующую эту вероятность. При вычислении приспособленности эта подстрока будет игнорироваться, но она будет подвергаться кроссоверу и мутации так же, как и остальная часть строки. Вероятность каждого бита данной особи быть инвертированным при мутации будет равна значению, кодируемому добавленной подстрокой. Инициализируются вероятности мутации случайным образом.

Thomas Back (1992) [19] в своей работе заметил, что для унимодальных функций вариант с глобальной вероятностью мутации работает лучше, однако для многоэкстремальных функций использование адаптивной мутации дает лучшие результаты.

Факторы, создающие сложность для ГА

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

Многоэкстремальность: это проблема для любого метода поиска, т. к. создается множество ложных аттракторов. Пример — функция Растригина (п.1.3.):

f(x) = 10« + X(x,i, -10cos(2^,)) <=i

(n.1.3)

Минимум достигается при всех х,- = 0. Количество аргументов функции можно варьировать, тем самым повышая или понижая сложность задачи поиска минимума.

Обманчивость (deception) — это характеристика функции, построенной так, что шаблоны малого порядка уводят популяцию к локальному экстремуму. Пример: пусть строка состоит из 10-ти четырехбитных подстрок. Пусть w, равно количеству единиц в /-той подстроке. Зададим функцию g(u) следующей таблицей (таблица п.1.1.):

Таблица н.1.1.Значения функции g(u).

и 0 1 2 3 4

3 2 1 0 4

• и пусть функция приспособленности равна сумме g(ul) по всем / = 1..10

(п. 1.4):

/ = £*(«,) (п. 1.4)

<=1

Локальный максимум достигается при всех битах, равных 0, глобальный — при всех 1. В большинстве случаев при добавлении единицы в подстроку приспособленность особи будет падать (за исключением случая, когда все остальные биты подстроки уже равны 1). При замене 1 на 0 она будет расти. Поэтому с большой вероятностью популяция сойдется к решению, при котором большинство подстрок будут состоять из всех нулей, и лишь некоторые из всех единиц. Однако это не будет глобальным максимумом. Из этого решения попасть в глобальный максимум, т. е. заменить все нули единицами, для ГА будет сложно.

Изолированность («поиск иголки в стоге сена») — также проблема для любого метода оптимизации, поскольку функция не предоставляет никакой информации, подсказывающей, в какой области искать максимум. Лишь случайное попадание особи в глобальный экстремум может решить задачу.

Дополнительный шум (noise) разбрасывает значения приспособленности шаблонов, поэтому часто даже хорошие гиперплоскости малого порядка не проходят отбор, что замедляет поиск решения.

Размер популяции

Для того, чтобы получить хорошие результаты, необходимо правильно выбрать размер популяции (рисунок п.1.4.). На графике изображена зависимость количества вычислений функции приспособленности для нахождения максимума унимодальной функции от размера популяции. Видно, что существует оптимальный размер популяции. Действительно, если популяция мала, то при заданном ограничении количества вычислений функции приспособленности (а значит, фиксированном времени вычислений) она успеет создать большее количество поколений, но вероятнее всего преждевременно сойдется. Слишком большая популяция должна найти решение, но она может не успеть достичь этого момента, т. к. ей отведено малое количество поколений.

10000

1 ■ Ч Г I I

1—t ■ а щ I

I | » ■ ■

Число вычислений целевой функции

1000

100

J ' ' Д 1 L -L

Г I I 11

» 1 I lg ^ д

2

10

100

500 1000

Размер популяции

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

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

Примеры применения ГА

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

1.1.4 Алгоритм роя частиц

Введение

Стая птиц представляет собой прекрасный пример коллективного поведения животных. Летая большими группами, они почти никогда не сталкиваются в воздухе. Стая двигается плавно и скоординировано, словно ей кто-то управляет. А любой, кто вешал в своем дворе кормушку, знает, что спустя несколько часов ее найдут все птицы в округе.

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

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

очевидные недостатки, как необходимость борьбы за найденную пищу с другими особями.

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

Модель Boids

Наблюдение за птицами вдохновило Крейга Рейнольдса (Craig Reynolds) на создание в 1986 году компьютерной модели, которую он назвал Boids. Для имитации поведения стаи птиц, Рейнольде запрограммировал поведение каждой из них в отдельности, а также их взаимодействие. При этом он использовал три простых принципа. Во-первых, каждая птица в его модели стремилась избежать столкновений с другими птицами. Во-вторых, каждая птица двигалась в том же направлении, что и находящиеся неподалеку птицы. В-третьих, птицы стремились двигаться на одинаковом расстоянии друг от друга.

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

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

Классический алгоритм роя частиц

В 1995 году Джеймс Кеннеди (James Kennedy) и Рассел Эберхарт (Rüssel Eberhart) предложили метод для оптимизации непрерывных нелинейных функций, названный ими алгоритмом роя частиц. Вдохновением для них послужила имитационная модель Рейнольдса, а также работа Хеппнера (Неррпег) и Гренадера (Grenader) на схожую тему. Кеннеди и Эберхарт отметили, что обе модели основаны на управлении дистанциями между птицами — а, следовательно, синхронность стаи является в них функцией от усилий, которые птицы прилагают для сохранения оптимальной дистанции.

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

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

На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц изменяются в соответствие со сведениями о найденных оптимумах (п. 1.5):

V, = V, + ах ■ rndQ• (pbesti-х,) + а2 ■ rnd§• (gbest¡ -х,) (п. 1.5)

где V — вектор скорости частицы (v, — его i-ая компонента), а,, а2 —

постоянные ускорения, рЬез1- лучшая найденная частицей точка, - лучшая

точка из пройденных всеми частицами системы, х- текущее положение частицы, а функция п7й?() возвращает случайное число от 0 до 1 включительно.

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

Модификации классического алгоритма

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

1.1.5 Муравьиный алгоритм Введение

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

Эти факты, однако, никак не согласуются с успешностью муравьев как вида. Они существуют на планете более 100 миллионов лет, строят огромные жилища, обеспечивают их всем необходимым и даже ведут настоящие войны. В сравнении с полной беспомощностью отдельных особей, достижения муравьев кажутся немыслимыми.

Добиться таких успехов муравьи способны благодаря своей социальности. Они живут только в коллективах - колониях. Все муравьи колонии формируют так называемый интеллект роя. Особи, составляющие колонию, не должны быть умными: они должны лишь взаимодействовать по определенным — крайне простым - правилам, и тогда колония целиком будет эффективна.

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

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

В 1992 году в своей диссертации Марко Дориго (Marco Dorigo) предложил заимствовать описанный природный механизм для решения задач оптимизации. Имитируя поведение колонии муравьев в природе, муравьиные алгоритмы используют многоагентные системы, агенты которых функционируют по крайне простым правилам. Они крайне эффективны при решении сложных комбинаторных задач — таких, например, как задача коммивояжера, первая из решенных с использованием данного типа алгоритмов.

Классический муравьиный алгоритм для решения задачи коммивояжера

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

Каждый муравей хранит в памяти список пройденных им узлов. Этот список называют списком запретов (tabu list) или просто памятью муравья. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качестве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма - то есть перед тем, как муравей вновь проходит путь — он опустошается.

Кроме списка запретов, при выборе узла для перехода муравей руководствуется «привлекательностью» ребер, которые он может пройти. Она зависит, во-первых, от расстояния между узлами (то есть от веса ребра), а во-вторых, от следов феромонов, оставленных на ребре прошедшими по нему ранее муравьями. Естественно, что в отличие от весов ребер, которые являются константными, следы феромонов обновляются на каждой итерации алгоритма: как и в природе, со временем следы испаряются, а проходящие муравьи, напротив, усиливают их.

После того, как муравей успешно проходит маршрут, он оставляет на всех пройденных ребрах след, обратно пропорциональный длине пройденного пути (п. 1.6):

\=j (п. 1.6)

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

1.1.6 Алгоритм пчёл Введение

Алгоритм пчел (в англоязычных статьях так же встречаются названия Artificial Bee Colony Algorithm и Bees Algorithm) является довольно молодым алгоритмом для нахождения глобальных экстремумов (максимумов или минимумов) сложных многомерных функций (будем называть эту функцию целевой функцией). Первые работы датируются 2005 годом. В довольно хорошо описана суть этого алгоритма, приведено сравнение алгоритма пчел с генетическим алгоритмом и алгоритмом, моделирующим поведение муравьев.

Природный механизм

Колонии медовых пчёл могут простираться на большие расстояния (более 10 км) в нескольких направлениях и одновременно используют большое число источников пищи. Колония процветает при распространении пчёл-сборщиков мёда на хорошие участки. В принципе, пути к цветам с большим числом нектара или пыльцой, которая может быть собрана с меньшим усилием, должны быть посещены большим числом пчёл, в то время как участки с меньшим содержанием нектара и пыльцы должны посещать меньше пчёл.

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

Когда пчёлы-разведчики возвращаются в улей, они идут на танцпол для исполнения виляющего танца.

Этот таинственный танец является неотъемлемой сущностью общения для колоний, и содержит три компоненты информации об участке с цветами:

- направление, в котором они были найдены,

- расстояние от улья,

-коэффициент качества (fitness).

Эта информация помогает колониям посылать своих пчёл на участки с цветами

более точно без использования проводников или карт. Танец позволяет колониям

117

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

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

Основные принципы

Идея алгоритма взята у пчел, а именно из их поведения при поиске мест, где можно раздобыть как можно больше нектара. Сначала из улья вылетают в случайном направлении какое-то количество пчел-разведчиков, которые пытаются отыскать участки, где есть нектар. Через какое-то время пчелы возвращаются в улей и особым образом сообщают остальным где и сколько они нашли нектара.

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

достаточно умножить на -1). Наши "неправильные" пчелы могут собирать и отрицательное количество нектара.

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

На первом шаге алгоритма в точке, описываемой случайными координатами, отправляется некоторое количество пчел-разведчиков (пусть будет S пчел, от слова scout). В зависимости от значения целевой функции, которое определяется координатами пчелы, выделяются два вида перспективных участков на поверхности функции, вблизи которых возможно располагается глобальный максимум. А именно:

• Выбирается п лучших участков, где значения целевой функции больше всех

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

Здесь нужно обратить внимание на одну особенность, которая может быть важна при реализации алгоритма. Несколько пчел могут попасть на один и тот же участок (близко друг к другу, размер участка, или возможная близость пчел, задается отдельным параметром). Поэтому можно выделить два варианта поведения:

• Считать, что эти две пчелы нашли два разных пересекающихся участка, и оба этих участка отметить как лучшие или выбранные.

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

В реализации, которая будет описана ниже, используется второй вариант поведения, так как он показал себя менее подверженным застреванию в локальных экстремумах[30].

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

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

После того как пчелы были отправлены на лучшие и выбранные участки, можно отправить тех же пчел-разведчиков на другие случайные точки. После всех этих операций снова находятся п лучших и т выбранных участков, на этот раз среди всех пчел из роя, а не только среди разведчиков, и запоминается самое лучшее место на функции, значение больше которого пока не было найдено, это и будет промежуточным решением. Затем алгоритм повторяется до тех пор, пока не сработает какой-нибудь из критериев останова. Критериев останова может быть несколько. Например, если мы знаем значение целевой функции в глобальном экстремуме, то можем повторять алгоритм до тех пор, пока функция не достигнет некоторого значения, близкого к желаемому. Если значение функции в экстремуме неизвестно, то можем повторять шаги алгоритма до тех пор, пока на протяжении какого-то достаточно большого количества итераций найденное решение не будет улучшаться. Алгоритм требует следующие значения устанавливаемых параметров: -число пчёл-разведчиков (п),

-число мест, выявленных после посещения п посещённых мест (т), -число лучших мест, найденных из т выбранных мест (е), -число пчёл, направляемые на лучшие е мест (пер),

-число пчёл (m-e), направляемых на другие места (nsp), -начальные пути (ngh), которые включают пути и их окрестности -критерий остановки.

Для алгоритма пчёл необходимо выполнить следующие операции:

1) Инициализировать популяцию со случайными решениями.

2) До тех пор пока не достигнут критерий останова выполнять:

a. Рассчитать fitness для популяции.

b. Выбрать места для поиска окрестностей

c. Направить пчёл на выбранные места (больше пчёл на лучшие места) и вычислить fitness.

d. Выбрать fitness пчёл для каждого участка.

e. Направить оставшихся пчёл на произвольный поиск и вычислить их fitness

г)

Рисунок п. 1.5. Иллюстрация работы алгоритма пчёл по итерациям (а - первая итерация, г - последняя).

Блок-схема алгоритма пчёл показана на рис.п.1.6.

Рисунок п.1.6. Блок-схема алгоритма пчёл.

Результаты работы алгоритмов оптимизации на тестовых функциях приведены в таблицах п. 1.2 и п. 1.3.

Таблица п.1.2. Тестовые функции для алгоритмов оптимизации.

№ функци и Название функции Интервал Функция Глобаль ный экстрему м

1 De Jong [-2.048, 2.048] maxF = (3905.93)-100(x,2 -x2f -(1-х,) 2X(1, 1) F=3905.9 3

2 Goldstein &Price [-2, 2] mi nF = гзо + (2л |_+12x2 1 + (x, + x2 +1)2 ■Q9-14xl+3x?-l4x2 + 6x,x2 + 3x2) \-Ъх2)г-(\2>-Ъ2хх -48x2 -36x,x2 +21X1) x X(0,-1) F=3

3 Branin [-5, 10] min F = a(x2 - bxf + cx, - d)2 + e(l -/)cos(x,) + e , , 5Af7 V $ n j t a = 1,6 = — — ,c = —xl,d = 6, 4 {22J 22 e = \0,f = —x — 8 22 X(-22/7, 12.275) X(22/7, 2.275) X(-66/7, 2.475) F=0.3977 272

4 Martin& Gaddy [0, 10] min F = (x, — x2)2 +((x, +x2 -10)/3)2 X(5, 5) F=0

5 Rosenbro ck (a) [-1.2, 1.2] (b) [-10, 10] min F = 100(x,2 - x2)2 + (1 - x, f X(l, 1) F=0

6 Rosenbro ck [-1.2, 1.2] min F = ¿{l00(x2 -x(+1)2 +(1 -x,)2} /=1 X(l, 1, 1, 1) F=0

7 Hyper sphere [-5.12,5.12] minF = ^{x2} 1=1 X(0, 0, 0, 0,0, 0) F=0

8 Griewang [-512,512]

к

max F =

10 x2

0.i+ Y-i—ГТ l 4000 11=1

сое

X(0, o, o, o, o, o, o, 0, o, 0) F=10

Таблица п.1.3. Результаты работы алгоритмов оптимизации на тестовых функциях.

№ функции Генетический алгоритм Муравьиный алгоритм Алгоритм пчёл

% успеха Число вычислений ЦФ % успеха Число вычислений ЦФ % успеха Число вычислений ЦФ

1 100 10160 100 6000 100 868

2 100 5662 100 5330 100 999

3 100 7325 100 1936 100 1657

4 100 2844 100 1688 100 526

5а 100 10212 100 6842 100 631

5Ь **** **** 100 7505 100 2306

6 **** **** 100 8471 100 28529

7 100 15468 100 22050 100 7113

8 100 200000 100 50000 100 1847

Из полученных результатов следует, что для всех задач, кроме 6-й, алгоритм пчёл превосходит по эффективности и генетический алгоритм и муравьиный, т.к. требует меньшее число вычислений целевой функции.

1.1.7. Алгоритмы поиска глобального минимума функционала невязки, используемые для решения обратной задачи в рентгеновской рефлектометрии

В основе генетического алгоритма лежит метод случайного поиска. Основным недостатком случайного поиска является то, что неизвестно, сколько понадобится времени для решения задачи. Для того, чтобы избежать таких расходов времени при поиске оптимума, используются методы, открытые в биологии при изучении эволюции и происхождения видов. Как известно, в процессе эволюции выживают наиболее приспособленные особи. Это приводит к тому, что приспособленность популяции возрастает, позволяя ей лучше выживать в изменяющихся условиях. Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов. В разные годы множество групп ученых занималось пристальным исследованием свойств генетических алгоритмов. Так, в работах Де Йонга (De Jong), Голдберга (Golberg), Дэвиса (Davis), Эшельмана (Eshelman), Фореста (Forest) и других авторов проводятся исследования генетических алгоритмов и особенностей их применения к задачам оптимизации.

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

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

программных продуктов, позволяющих анализировать данные рентгеновской рефлектометрии.

Так авторами был предложен алгоритм поиска глобального минимума функционала невязки данных рентгеновской рефлектометрии. Алгоритм получил название «дифференциальная эволюция» (ДЭ). Авторами проведена серия экспериментов по расчету параметров многослойных структур с помощью ДЭ, и проведен сравнительный анализ скорости расчета максимально приспособленной особи при различных выбранных функционалах невязки. В большинстве случаев наиболее адекватной показала себя функция:

Н**}=X (/V, {хк}) - .пт2 (п. 1.7)

где Хк- к-я особь (элемент популяции), в — угол скольжения, /'А и /ехр — теоретическая и экспериментальные зависимости, соответственно, а /09) = \пг(в) -натуральный логарифм коэффициента отражения.

Дифференциальная эволюция - это вариант эволюционного алгоритма, позволяющий проводить поиск глобального максимума/минимума непрерывной функции. ДЭ оперирует числами с плавающей точкой. Во время процесса оптимизации популяции ДЭ создает новые особи (решения), объединяя свойства родительской особи и нескольких других случайно выбранных особей из той же популяции. Новая особь может занять место родительской только в случае лучшей приспособленности (меньшего значения функционала невязки в случае поиска глобального минимума). ДЭ имеет три рабочих параметра, подбирая значения которых, можно добиться наибольшего быстродействия алгоритма. Первый параметр - это фактор прироста вектора отличий, второй — фактор перекрестной мутации, и третьим параметром является размер популяции. Наличие всего лишь трех управляющих параметров, остающихся неизменными во время всего процесса оптимизации, делает алгоритм ДЭ достаточно простым для понимания и управления.

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

126

познакомиться на личной Интернет-странице Ени Лампинена (Jouni Lampinen), на которой он собрал большую коллекцию публикаций по теме ДЭ.

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

В сравнении с другими алгоритмами оптимизации, ДЭ превосходит их. Показано, что алгоритм ДЭ превосходит метод частичной роевой оптимизации и некоторые реализации эволюционных алгоритмов в большинстве проведенных численных тестах. Численные тесты, используемые в их работе, являются довольно распространенными и используются для сравнения алгоритмов оптимизации, Али (АН) и Терн (Torn) в своей работе предложили новую версию алгоритма ДЭ, а также предложили несколько модификаций классического алгоритма ДЭ, позволяющих увеличить эффективность и надежность. Ими же были предложены несколько правил для автоматического расчета некоторых управляющих параметров ДЭ.

В развитие использования генетических алгоритмов для решения обратной задачи рентгеновской рефлектометрии был предложен, так называемый, расширенный генетический алгоритм. Проводился сравнительный анализ четырех алгоритмов поиска глобального минимума. Среди них уже упомянутый расширенный генетический алгоритм, классический генетический алгоритм, алгоритм отжига и симплекс-метод. Применительно к решению задач рентгеновской рефлектометрии, расширенный генетический алгоритм показал наилучшие результаты и в среднем позволял рассчитать точные параметры структуры в 3-4 раза быстрее, чем другие методы. Также стоит сказать, что расширенный генетический алгоритм является запатентованной разработкой немецкой компании «Bruker AXS» и входит в набор

опций коммерческого продукта LEPTOS, выпускаемого этой компанией.

127

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

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

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