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

• Метлицкая, Дарья Вадимовна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Метлицкая, Дарья Вадимовна

ОГЛАВЛЕНИЕ

Введение

Глава 1. Применение генетических алгоритмов

1.1. Генетический алгоритм с бинарным кодированием

111 ПпТ1Г»ОШ1А ОТПОТПГ1Ш ГТГЧТТГ»Т/-а ГПЛ^ОТТТЛГЛГЛ 1 Q

1 J. *

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

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

1.2. Генетический алгоритм с вещественным кодированием

1.2.1. Описание стратегии поиска глобального экстремума

1.2.2. Применение генетического алгоритма с вещественным кодированием в задаче нахождения оптимального программного управления дискретными системами

1.2.3. Применение генетического алгоритма с вещественным кодированием в задаче нахождения оптимального программного управления непрерывными системами

1.3. Примеры применения генетических алгоритмов

1.3.1. Задачи оптимального управления дискретными системами

1.3.2. Задачи оптимального управления непрерывными системами

1.3.3. Задачи оптимального управления летательным аппаратом

1.3.4. Рекомендации по выбору параметров алгоритмов

1.4. Выводы

Глава 2. Применение методов, имитирующих иммунные системы организмов

2.1. Метод искусственных иммунных систем

2.1.1. Описание стратегии поиска глобального экстремума

2.1.2. Применение метода искусственных иммунных систем в задаче нахождения оптимального программного управления дискретными системами

2.1.3. Применение метода искусственных иммунных систем в задаче нахождения оптимального программного управления непрерывными системами

2.2. Расширенный метод искусственных иммунных систем

2.2.1. Описание стратегии поиска глобального экстремума

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

2.2.3. Применение расширенного метода искусственных иммунных систем в задаче

нахождения оптимального программного управления непрерывными системами

2.3. Примеры применения методов, имитирующих иммунные системы организмов

2.3.1. Задачи оптимального управления дискретными системами

2.3.2. Задачи оптимального управления непрерывными системами

2.3.3. Задачи оптимального управления летательным аппаратом

2.4. Выводы

Глава 3. Применение метода динамических сеток

5.1. Метод динамических сеток

5.1.1. Описание стратегии поиска глобального экстремума

5.1.2. Применение метода динамических сеток в задаче нахождения оптимального программного управления дискретными системами

5.1.3. Применение метода динамических сеток в задаче нахождения оптимального программного управления непрерывными системами

5.2. Примеры применения метода динамических сеток

5.2.1. Задачи оптимального управления дискретными системами

5.2.2. Задачи оптимального управления непрерывными системами

5.2.3. Рекомендации по выбору параметров метода

5.3. Выводы

Глава 4. Комплекс программ

4.1. Структура комплекса

4.2. Возможности комплекса

4.3. Примеры работы комплекса

4.3.1. Задача поиска глобального экстремума функций многих переменных

4.3.2. Задача поиска оптимального программного управления дискретными системами

4.3.3. Задача поиска оптимального программного управления непрерывными системами

4.4. Выводы

Заключение

Библиографический список

Приложение 1. Характеристики и техническая постановка задачи поиска

оптимального управления ракетой

3

Приложение 2. Набор тестовых функций

Приложение 3. Метод рассеивания

П3.1. Описание стратегии поиска глобального экстремума

П3.2. Применение метода рассеивания в задаче нахождения оптимального

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

программного управления непрерывными системами

П3.4. Рекомендации по выбору параметров метода

П3.5. Примеры применение метода рассеивания

Приложение 4. Эволюционные стратегии преобразования ковариационной

матрицы

П4.1. Эволюционная стратегия преобразования ковариационной матрицы

П4.1.1. Описание стратегии поиска глобального экстремума

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

дискретными системами

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

непрерывными системами

П4.2. Модифицированная эволюционная стратегия преобразования ковариационной

матрицы

П4.2.1. Описание стратегии поиска глобального экстремума

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

управления дискретными системами

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

управления непрерывными системами

П4.3. Примеры применения эволюционных стратегий преобразования ковариационной матрицы

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

ВВЕДЕНИЕ

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

Основополагающими результатами, полученными в теории оптимального управления, являются принцип максимума JI.C. Понтрягина [87], метод динамического программирования Р. Беллмана [5], достаточные условия оптимальности В. Ф. Кротова [24]. На их основе созданы различные методы решения задач оптимального управления.

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

Для решения задач оптимального управления динамическими детерминированными системами к настоящему времени получены необходимые и достаточные условия оптимальности. Однако при этом возникают трудности, связанные с необходимостью решать краевую задачу, с большой размерностью систем и их нелинейностью, с многоэкстремалыюстыо задачи, а также с наличием ограничений на управление и вектор состояния. Поэтому точное аналитическое решение задач оптимального управления возможно получить лишь для узкого круга задач. В связи с перечисленными трудностями построения аналитического решения большое значение получили приближенные и численные методы решения задач оптимального управления, которым посвящены работы Ю.Г. Евтушенко, H.H. Моисеева, А.Б. Куржан-ского, Р.П. Федоренко, И.А. Крылова, Ф.Л. Черноусько, А.Н. Тихонова, Ф.П. Васильева, В.Б. Колмановского, II. Н. Красовского, А. М. Летова, С.Н. Васильева, В.Ф. Кротова, В.И. Гурмана, М.М.Хрусталева и многих других.

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

К первому подходу относятся итерационные процедуры на основе принципа максимума Понтрягина (ПМ) и классического вариационного исчисления, которые основываются на сведении задачи оптимального упоавления к коаевой задаче с использованием необходимых условий оптимальности. Подобные методы разрабатывались и широко применялись для численного решения задач оптимального управления в работах В.К. Исаева, В.В. Сонина, В.Н. Лебедева [26], Г.Л. Гродзовского [13], H.H. Моисеева [54], Брайсона и Хо Ю-ши [6] и многих других. Итерационные процедуры ПМ также связаны с локальными и нелокальными аппроксимациями функционалов, вспомогательными задачами на максимум функции Понтрягина, разнообразными схемами игольчатого варьирования управлений, процедурами нелокального улучшения. Для дискретных систем аналогичные подходы развивались в работах А. И. Пропоя, Р. Габасова и Ф. М. Кирилловой [88, 9].

Вторую группу образуют методы, в основе которых лежат итерационные процессы в пространстве управляющих функций с использованием формул для приращения функционала качества. Для этого используются либо формулы классического вариационного исчисления (такие методы называют градиентными методами оптимального управления), либо соотношения, связанные с ПМ Понтрягина (методы последовательных приближений). Градиентные методы в пространстве управляющих функций, использующие формулы для первой вариации функционала качества, и методы штрафных функций, были предложены в работах Л. И. Шатровского [97], Т. М. Энеева [98], Брайсона, Денхэма [108], Хо Ю-ши [124] и др. Метод последовательных приближений, основанный на принципе максимума Понтрягина, был предложен в работах: Келли, Коппа, Мойера [128], И. А. Крылова, Ф. Л. Черноусь-ко [25]. Дальнейшей разработке метода и улучшению скорости сходимости посвящены работы И. А. Крылова, Ф. Л. Черноусько, Н. В. Баничука. Градиентные методы используют классические и неклассические вариации функционалов, вспомогательные задачи на минимум вариаций, квазиградиентные процедуры.

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

работы Н. Н. Моисеева [53], В. И. Коробова [23], JI. Д. Подвального [85], Р. П. Федоренко [95], Р. Jlyyca [131].

Еще одну группу методов образуют методы улучшения на основе условий оптимальности Кротова. К ним относятся приближенные и численные методы оптимального управления непрерывными и дискретными системами: итерационные методы первого и второго порядков поиска с использованием достаточных условий локальной оптимизации Гурмана В. И., а также методы на основе полиномиальной аппроксимации решения уравнения Беллмана и траекторного восстановления функции цены. Данному направлению посвящены работы Гурмана В. И., Хрусталева М.М., Батурина В.А., Срочко В.А., Дыхта В.А., Аручинцева A.B.

Методы пятой группы характеризуются общим подходом, связанным с применением алгоритмов нелинейного программирования. Он заключается в дискретной аппроксимации задачи оптимального управления и адаптации конечномерных методов оптимизации к получающимся дискретным задачам управления. Это направление развивалось в работах Н. Н. Моисеева, Ю. Г. Евтушенко, 10. М. Ермольева, Ф. П. Васильева и др.

Кроме вышеописанных групп методов существуют методы, основанные на анализе множеств достижимости [15], нелокальные методы улучшения [7], методы, основанные на многомерных аппроксимациях и параллельных вычислениях [17] и многие другие. Кроме того, существуют перспективные направления развития новых методов, связанные с комбинированием различных методов в процессе решения задач [94] и использованием растущих возможностей современной вычислительной техники.

Представленный обзор численных методов решения задач оптимального управления является далеко не полным. Наряду с изложенными выше методами существует целый ряд других вычислительных методов решения задач оптимального управления системами разных типов. Обзоры различных методов решения задач оптимального управления представлены в [14, 55, 56, 96]. В настоящее время описанная область математики активно развивается.

В диссертационной работе для решения задач оптимального управления нелинейными дискретными и непрерывными детерминированными динамическими системами применяются эволюционные методы глобальной оптимизации. Данные методы относятся к ме-таэвристическим методам глобальной оптимизации, которые позволяют найти решение «высокого качества» за приемлемое (с практической точки зрения) время. Описание данных методов можно найти в работах Дж. Холланда, А. Райта, С. Дасгупта, Ф. Хереро, Н. Хансена, Л. де Кастро, А. Дуарта, Ф. Гловера, Д. Гольдберга, А. Париса, Р. Марти и многих других.

В своей классической постановке эволюционные методы применимы к решению задачи оптимизации многопараметрической целевой функции

f(x) = f{xx,x2,...,xn), (В.1)

определенной на множестве допустимых решений D = {x\xj е [а,,£,], / = 1,2,...,«}с: R", и позволяют найти ее условный глобальный максимум (минимум) на заданном множестве, т.е. такую точку х* е D, что

/(**) = шах f(x) ( f(x*) = min f(x) ). (B.2)

*e£> xsD

Задача поиска минимума функции /(х) сводится к задаче поиска максимума путем замены знака перед функцией на противоположный: /(**) = min f(x) = -max[-/(jc)].

xeD xeD

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

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

В диссертационной работе рассмотрены получившие наибольшее распространение методы первой группы: генетические алгоритмы; методы, имитирующие иммунные системы организмов; методы рассеивания; эволюционная стратегия преобразования ковариационной матрицы; методы динамических сеток. К эволюционным методам также относятся: методы дифференциальной эволюции (Differential Evolution) [64, 111]; метод, имитирующий распространение сорняков (Weed Colonization); метод, имитирующий поведение кукушек (Cuckoo Search).

Ко второй группе методов - методам «роевого» интеллекта — относятся: метод частиц в стае [60], метод муравьиных колоний, метод имитации поведения бактерий [1], методы пчелиных колоний; метод, имитирующий поведение стаи рыб в поисках корма (Fish School Search); метод, имитирующий поведение летучих мышей (Bat-Inspired Algorithm); метод,

имитирующий поведение светлячков (Glowwarm Swarm Optimization); алгоритм, имитирующий поведение лягушек (Shuffled Frog-Leaping Algorithm).

К третьей группе метаэвристических методов - методов, имитирующих физические процессы, относятся: метод гравитационной кинематики (Central Force Optimization), метод имитации отжига (Simulated Annealing) [65], адаптивный метод имитации отжига (Adaptive Simulated Annealins). метод поиска гармонии (Tlarmonv Search): метод, используюший закон электромагнетизма (Electromagnetism-like Mechanism), аналогичный методу гравитационной кинематики.

К четвертой группе метаэвристических методов - мультистартовых методов, — относятся: жадный адаптивный метод случайного поиска (Greedy Randomized Adaptive Search Procedure) [83] и метод направленного табу-поиска (Tabu Search) [82].

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

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

Гсиетнческнс алгоритмы (Genetic Algorithms) являются типичными представителями эволюционных методов поиска. Основные принципы работы генетических алгоритмов (ГА) изложены в [3, 10, 11, 22, 105, 107, 117, 119, 126, 134, 136, 144]. В ГА создается популяция особей, каждая из которых представляется в виде хромосомы. В задаче оптимизации множество допустимых решений кодируется так, чтобы каждая хромосома соответствовала одному из возможных решений. Хромосома состоит из конечного числа генов, представляя генотип объекта. Поиск экстремума ведется на уровне генотипов.

Генетические алгоритмы делятся на две группы: генетические алгоритмы с бинарным кодированием и генетические алгоритмы с вещественным кодированием.

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

шанное кодирование). Высокая эффективность отыскания глобального экстремума с помощью генетического алгоритма с бинарным кодированием обоснована теоремой о шаблоне [109], в которой доказано, что двоичный алфавит позволяет обрабатывать максимальное количество информации по сравнению с другими методами кодирования. Однако двоичное представление хромосом влечет за собой трудности при поиске экстремума в непрерывных поосттнствах. поскольку дискретизация множества допустимых оешений приводит к потепе точности. Описание различных генетических алгоритмов и соответствующих программных продуктов можно найти в [4, 58, 59, 61, 62, 92,105,134].

Вторая группа возникла в результате отказа от идеи кодирования. В таком случае решение в хромосоме представляется в виде набора вещественных чисел. При этом реализация генетических операторов изменяется, а операции кодирования и декодирования отсутствуют. Генетические алгоритмы с вещественным кодированием были предложены в [144] и интенсивно развиваются [58, 59, 122, 134].

К эволюционным методам относятся методы, имитирующие иммунные системы организмов - методы искусственных иммунных систем (Artificial Immune Systems), опирающиеся на идеи из иммунологии. Основные принципы работы методов искусственных иммунных систем (ИИС) изложены в [18,103, 104, 106, 127].

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

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

Еще одним представителем эволюционных методов является метод рассеивания (Scatter Search). Основные принципы работы метода рассеивания изложены в [109, 113, 114, 132]. Свое название метод получил из-за способа создания базового множества особей, которое формируется таким образом, чтобы особи в нем существенно отличались друг от друга, т.е. были хорошо «рассеяны» по множеству допустимых решений. Данное множество используется для формирования начальной популяции и пополнения новых популяций в течение работы метода. Таким образом, обеспечивается тщательное исследование множества допустимых решений и эффективное использование вычислительных ресурсов метода.

У метода рассеивания существует несколько модификаций, комбинирующих его с локальными методами поиска: линейным поиском, табу-поиском, методом деформируемого многогранника (Нелдера-Мида) [8, 67].

Эволюционная стратегия преобразования ковариационной матрицы (Covariance Matrix Adaptation Evolution Strategy, CMA-ES) была предложена в [119]. Основные принципы работы данного метода изложены в Г118. 125. 1381. Свое название метод получил благодаря способу, которым формируются новые популяции. Формирование происходит при помощи нормального распределения случайного вектора. При этом при переходе от одной популяции к другой происходит преобразование ковариационной матрицы распределения. Также производится постоянное изменение параметров стратегии в течение ее работы. Изменение элементов ковариационной матрицы и параметров стратегии реализуется таким образом, чтобы обеспечить наиболее эффективную ее работу на каждой итерации. Изначально CMA-ES разрабатывалась как локальный метод поиска, поэтому ее можно использовать в качестве улучшающего решение метода в комбинации с другими методами поиска. Однако CMA-ES и ее модификации справляются и с задачами поиска глобального экстремума.

В методе динамических сеток (Variable Mesh Optimization), предложенном в [139], популяция представляется в виде некоторой сетки, состоящей из набора решений, называемых узлами. В процессе поиска сетка подвергается изменениям: расширению - добавлению новых узлов в сетку, и сокращению - удалению узлов, расположенных слишком близко друг к другу. Метод имитирует эволюцию начальной популяции и представляет собой итерационный процесс. Во время работы метода на каждой итерации происходит расширение (локальное, глобальное и дополнительное) и последующее сокращение сетки. Таким образом, формируется новая сетка. Критерием окончания поиска является достижение заранее заданного количества вычислений целевой функции. В качестве приближенного решения задачи из последней популяции выбирается узел, которому соответствует наилучшее значение целевой функции.

Формирование алгоритмического обеспечения перечисленных методов является актуальным не только для решения непосредственно задачи поиска глобального экстремума многоэкстремальных функций нескольких переменных, но и для решения разнообразных прикладных задач, в частности, проблемы параметрической оптимизации непрерывных и дискретных нелинейных систем управления. Применением некоторых методов, в частности генетических и эволюционных алгоритмов, к задачам оптимального управления занимались 3. Михайлевич, И. JI. Лопес Круз, II. В. Дакев [133, 130]. Полученные в их работах результаты показывают хорошую применимость метаэвристических методов к задачам оптимального управления и актуальность исследований в данной области.

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

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

х(/ + 1) = Д/,х(/),и(/)), (В.З)

где / — дискретное время, / е Т = [0,1,..., N -1]; х — вектор состояния системы, хеЛ"; и —

вектор управления, и &(/(() с: £/(/) — множество допустимых значений управления, для

каждого значения / представляющее собой прямое произведение отрезков [о,(/),й;(/)],

т

/ = 1, 2,...,д; число шагов дискретного времени N задано; /(1,х,и) = (/1((,х,и),...,/п^,х,и)) - непрерывная вектор-функция. Правый конец траектории х(Ы) свободен. Начальное условие:

х(0) = х0. (В.4)

Предполагается, что при управлении используется информация только о дискретном времени /, т.е. применяется программное управление.

Множество допустимых процессов 2)(0,х0) - это множество пар с/= (х(-),и(-)),

включающих траекторию х(-) = {х0,х(\),...,х(М)} и допустимое управление и(-) = {и(0),и(1),...,и(Ы-1)}, где «(/)е £/(/), удовлетворяющих уравнению состояния (В.З) и начальному условию (В.4).

На множестве В(0,хо) определен функционал качества управления

т=X ('> *(')> »(о)+, (в.5)

/=о

где /° (/,х(0,м(0)> -заданные непрерывные функции.

Требуется найти такую пару с1* = (х *(■),» * (•)) <= -0(0, х0), что

/(</*)= шах /(¿). (В.6)

¿е/)(0,х0)

Искомые элементы пары ¿/*: траектория х*(-) = {л:0,д:*(1),...,л:*(Л^)} и управление м*(-) = {и*(0),м*(1),..., и*(Ы-\)} называются соответственно оптимальной траекторией и оптимальным управлением. Если любому допустимому управлению ы(-) соответствует единственная пара й, то задача (В.6) может быть переписана в эквивалентной форме как задача поиска максимума функционала на множестве допустимых управлений.

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

x = f(t,x(t)MO), СВ.7)

где х - вектор состояния системы, хе. R"; и — вектор управления, и = yiix,...,u f ^uyt) £ л*; и— множество допустимых значении управления, для каждого значения t представляющее собой прямое произведение отрезков [а,(/),£,(/)], i = 1,2,...,q; t — непрерывное время, /еГ = [/0,^], начальный /0 и конечный tN моменты времени заданы;

f{t,x,u) = ^fx{t,x,n),...,fn{t,x,ujf — непрерывно дифференцируемая вектор-функция. Правый конец траектории x(tN) свободен. Начальное условие:

*('<>) = *о- (В-8)

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

Множество допустимых процессов D(t0,x0) - это множество пар d = (x(t),u(j)), включающих траекторию x(t) и кусочно-непрерывное допустимое управление u(t), где u(t) е U, удовлетворяющих дифференциальному уравнению (В.7) и начальному условию (В.8).

На множестве D(/0, х0) определен функционал качества управления

<N

1(d) = J f°(t,x(OMO)dt + F{x(tN)) , (В.9)

'о

где f°(t,x(t),u(t)) и F(x) - заданные непрерывные функции.

Требуется найти такую пару d* = (x*(i),u*(i)) е Z)(/0,x0), что

I(d*)= шах 1(d). (В. 10)

deD(t0,x0)

Искомые элементы пары d*: траектория x*(t) и управление u*(t) называются соответственно оптимальной траекторией и оптимальным управлением. Если любому допустимому управлению u(t) соответствует единственная пара d, то задача (В. 10) может быть переписана в эквивалентной форме как задача поиска максимума функционала на множестве допустимых управлений. Предполагается, что максимум в (В. 10) достигается. Задача поиска минимума функци-

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

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

П1.Ш ^moDiTATmp>M f л.

x = f(t,x(t),xQ~ т),и(0), (В-11)

где х - вектор состояния системы, х е R"; и - вектор управления, и = (nv...,uq)T е U(t) с R4; U(t) - множество допустимых значений управления, для каждого

значения t представляющее собой прямое произведение отрезков [ai(t),(/)], / = 1,2,...,q ; t

- непрерывное время, / e Г = начальный t0 и конечный tN моменты времени заданы;

х>0 — величина запаздывания; f(t,x,y,u) = (f1(t,x,y,u),...,fn(t,x,y,uyj)T — непрерывно дифференцируемая по всем переменным вектор-функция. Правый конец траектории x(tN)

свободен.

Начальное условие:

*(0 = git), V/ 6 [-т,/0); x(t0) = xQ. (В. 12)

где g(t) - заданная кусочно-непрерывная вектор-функция.

Предполагается, что система управления является разомкнутой по состоянию и применяется программное управление.

Множество допустимых процессов D(t0,x0) - это множество пар d = (x(t),u{t)), включающих траекторию x(t) и кусочно-непрерывное допустимое управление u(t), где u(t)eU, удовлетворяющих дифференциальному уравнению (В. 11) и начальному условию (В. 12).

На множестве D(t0,x0) определен функционал качества управления

т = \ f\t,x(t\u{t))dt + F{x(tN)), (В.13)

'о

где f°(t,x,u) и ^(х) - заданные непрерывные функции.

Требуется найти такую пару d* = {x*(t),u* (0) е D(tQ ,х0), что

I(d*)= шах 1(d) . (В. 14)

tleD(i0,xa)

Целями диссертационной работы является формирование алгоритмического и про-

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

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

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

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

Список литературы диссертационного исследования кандидат наук Метлицкая, Дарья Вадимовна, 2013 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

I. Алёшина Е.А. Применение метода имитации поведения бактерий к задаче поиска оптимального управления дискретными детерминированными системами // Информационные и телекоммуникационные технологии. 2012. №14. С. 52-56.

О А 7Т Л Т ГГ*ЧЛ г» ТТ Л*ТТГЛ Т'Л'ТЛТТТТГ Т» Г ЛЛ ЛТ1Л птгт* л* г тг»и»?»»»ттттг*»л/» л^» г» К • <чг»

радио. 1977.

3. Батищев Д.И. Генетические алгоритмы решения экстремальных задач / Под ред. Я.Е. Львовича: Учебное пособие. Воронеж, ВГТУ, 1995.

4. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов // Высокие технологии в технике, медицине и образовании: межвуз. сб. науч. тр. Ч. 3. Воронеж, ВГТУ, 1997. С. 4-17.

5. Беллман Р. Динамическое программирование. - М.: Изд-во ин. лит. 1960.

6. Брайсон Д., Хо Ю-Ши. Прикладная теория оптимального управления. — М.: «Мир», 1972, 544 с.

7. Булдаев А. С. Проекционные процедуры нелокального улучшения линейно управляемых процессов // Известия вузов. Математика. 2004. № 1. С. 18-24.

8. Васильев Ф.П. Численные методы решения экстремальных задач. - М.: Наука, 1980.

9. Габасов Р., Кириллова Ф. М. Построение последовательных приближений для некоторых задач оптимального управлении // Автоматика и телемеханика. 1966. № 2. С. 5-17.

10. Гладков В.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. - М.: ФИЗМАТЛИТ, 2006.

II. Гладков В.А., Курейчик В.В. Биоинспирированные методы в оптимизации. - М.: ФИЗМАТЛИТ, 2009.

12. Голубев КС., Светлов В.Г. Проектирование зенитных управляемых ракет. - М.: Изд-во МАИ, 1999.

13. Гродзовский Г. Л., Иванов 10. Н., Токарев В. В. Механика космического полета с малой тягой. - М.: «Наука. 1966. 679 с.

14. Гурман В. И., Расина И. В., Блинов А. О. Эволюция и перспективы приближенных методов оптимального управления // Программные системы: теория и приложения. №2(6). 2011. С. 11-29.

15. Гурман В. И, Батурин В. А. Алгоритм улучшения управления, основанный на оценках областей достижимости, Деп. в ВИНИТИ, 1985, № 65-85.

16. Гурман В. И. Принцип расширения в задачах управления. —М.: Наука. 1985.

17. Гурман В. И, Трушкова Е. А., Блинов А. О. Приближенная оптимизация управления в параллельных вычислениях // Вестник БГУ. 2010. № 9.

18.ДасгуптаД. Искусственные иммунные системы и их применение. - М.: ФИЗМАТ-ЛИТ, 2006.

19. Жиглявский A.A., Жилинскас А.Г. Методы поиска глобального экстремума. — М.: Наука, 1991.

20. Иванов 10. Н. Ступенчатая аппроксимация оптимальных управлений // Прикл. мат. и мех. 1964. 28. № 3. С. 528—633.

21. Информационно-новостная система «Ракетная техника» // [Эл. ресурс]: http://rbase.nevv-factoria.ru/missile/vvobb/aiml20/aiml20.shtml

22. Исаев С. Популярно о генетических алгоритмах. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов // [Эл. ресурс]: www.algolist.manual.ru

23. Коробов В. И. О сходимости одного варианта метода динамического программирования для задачи оптимального управления // Вычисл. мат. и мат. физ. 1968. 8. № 2. С. 429—435.

24. Кротов В. Ф., Гурман В. И. Методы и задачи оптимального управления. -М.: Наука, 1973.

25. Крылов И. А., Черноусько Ф. Л. О методе последовательных приближений для решения задач оптимального управления // Вычисл. мат. и мат. физ. 1962. 2. № 6. С. 1132-1139.

26. Лебедев В. Н. Расчет движения космического аппарата с малой тягой. — М.: Изд-во ВЦ АН СССР. 1967.108 с.

27. Летов A.M. Динамика полета и управление - М.: Наука, 1969.

28. Метлицкая Д.В. Алгоритмическое обеспечение модифицированного метода искусственных иммунных систем // Теоретические вопросы вычислительной техники и программного обеспечения: Межвуз. сб. науч. тр., МИРЭА, 2011. С. 81-86.

29. Метлицкая Д.В. Генетические алгоритмы поиска оптимального управления непрерывными детерминированными системами // Электронный журнал «Труды МАИ», №45, 2011, http://www.mai.ru/science/trudy/published. php?ID=25544

30. Метлицкая Д.В. Применение метода искусственных иммунных систем для оптимизации стоимостных показателей предприятия // Научн. альм. Вып. 16: Материалы VIII научно-практической конф. молодых ученых и студентов «Инновационный менеджмент в аэрокосмической промышленности». - М.: Изд-во «Доброе слово», 2012. С. 174—182.

31. Метлицкая Д. В. Разработка комплекса программных средств «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // XLVIII Межд. научная студенческая конф. «Студент и научно-технический прогресс», Новосибирск, 2010: Тез. докл. - Новосибирск: Новосиб. гос. ун-т, 2010. — С. 168-169.

32. Метлицкая Д. В. Лабораторный практикум «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // VII Всероссийская конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике

программирования», Москва, 2010: Тез. докл. - М.: Вузовская книга, 2010. - С. 129-130.

33. МетлицкаяД. В. Разработка комплекса программных средств «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // ХЬУ1 Всероссийская конференция по проблемам математики, информатики, физики и химии, Москва, 2010: Тез. докл. Секции математики и информатики. - М.: РУДН, 2010. - С. 26-28.

34. Метлицкая Д. В. Разработка лабораторного практикума «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // Научно-практическая конференция студентов и молодых ученых МАИ «Инновации в авиации и космонавтике — 2010», Москва, 2010: Тез. докл. - СПб.: Мастерская печати, 2010. - С. 288-289.

35. МетлицкаяД. В. Разработка лабораторного практикума «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // II Межд. научно-практической конф. "Научно-техническое творчество молодежи - путь к обществу, основанному на знаниях", Москва, 2010: Сборн. научн. докл. - М: МГСУ, 2010. - С. 433-435.

36. МетлицкаяД. В. Генетические алгоритмы с бинарным и вещественным кодированием в задачах синтеза оптимального управления непрерывными динамическими системами // 9-я Межд. конф. «Авиация и космонавтика - 2010», Москва, 2010: Тез. докл. - СПб.: Мастерская печати, 2010. - С. 388.

37. МетлицкаяД. В. Применение генетических алгоритмов с бинарным и вещественным кодированием к задаче поиска оптимального управления непрерывными детерминированными системами // Конкурс научн.-техн. работ и проектов «Молодежь и будущее авиации и космонавтики - 2010», Москва, Аннот. раб. -СПб: Мастерская печати, 2010. - С. 128-129.

38. Метлицкая Д.В. Генетические алгоритмы с бинарным и вещественным кодированием в задачах поиска оптимального управления динамическими системами // Материалы ХЫХ Международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика / Новосиб. гос. ун-т. Новосибирск, 2011. - С. 173.

39. Метлицкая Д.В. Применение генетических алгоритмов с бинарным и вещественным кодированием к задаче поиска оптимального управления летательным аппаратом» // Научно-практическая конф. студентов и молодых учёных МАИ «Инновации в авиации и космонавтике - 2011», 2011, Москва. Сб. тез. докл. - М.: МЭЙЛЕР, 2011. - С. 107-108.

40. Метлицкая Д.В. Комплекс программных средств «Генетические алгоритмы с бинарным и вещественным кодированием в задачах поиска оптимального управления динамическими системами» // Материалы XVII Международной конференции по вычислительной механике и современным прикладным программным системам (ВМСППС'2011), 2011, Алушта. - М.: Изд-во МАИ-ПРИНТ, 2011. - С. 711-713.

41. Метлицкая Д.В. Применение модифицированного метода искусственных иммунных систем к задачам поиска оптимального управления дискретными динамическими системами // 10-я Международная конференция «Авиация и космонавтика — 2011», Москва,

2011: Тез. докл. - СПб.: Мастерская печати, 2011. - С. 238.

42. Метлицкая Д.В. Методы, основанные на искусственных иммунных системах, в задачах поиска глобального условного экстремума функций многих переменных // L Международная научная студенческая конференция «Студент и научно-технический прогресс», Новосибирск, 2012: Тез. докл. - Новосибирск: Новосиб. гос. ун-т., 2012. - С. 178.

43. Метлицкая Д.В. Генетические алгоритмы в задаче поиска оптимального управления средней скоростью полета летательного аппарата // Инновации в авиации и космонавтике - 2012. Московская научно-практическая конференция молодых ученых, Москва, 2012: Тез. докл. - М.: ООО «Принт-салон», 2012. - С. 247-248.

44. Метлицкая Д.В. Поиск оптимального управления дискретными системами с помощью модифицированного метода искусственных иммунных систем // Международная научно-методическая конференция "Информатизация инженерного образования (Инфорино-2012)", Москва, 2012: Тез. докл. - М.: Издательский дом МЭИ, 2012. - С. 214-215.

45. Метлицкая Д.В. Применение метода искусственных иммунных систем в задаче поиска оптимального управления детерминированными системами // 11-я Межд. конф. «Авиация и космон. -2012», Москва, 2012: Тез. докл.- СПб.: Мает, печати, 2012. - С. 388.

46. Метлицкая Д.В. Применение метода рассеивания в задачах поиска оптимального программного управления детерминированными системами // Московская молодежная научно-практическая конференция «Инновации в авиации и космонавтике - 2013», Москва, 2013: Тез. докл. - М.: ООО «Принт-салон», 2013. - С. 288-289.

47. Мепутцкая Д.В. Применение метода динамических сеток в задачах поиска оптимального программного управления детерминированными системами // Материалы XVIII Межд. конф. по вычислительной механике и современным прикладным программным системам (ВМСППС'2013), 2013, Алушта. - М.: Изд-во МАИ-ПРИНТ, 2013. - С. 777.

48. Метлицкая Д.В. Применение генетических алгоритмов глобальной оптимизации с бинарным и вещественным кодированием в задаче оптимального управления дальностью полета летательного аппарата типа «воздух-воздух» / Метлицкая Д.В. // Св-во о гос. регистрации программы для ЭВМ № 2013617278. Федеральная служба по интеллект. собственности.-07.08.2013.

49. Метлицкая Д.В. Применение генетических алгоритмов глобальной оптимизации с бинарным и вещественным кодированием в задаче оптимального управления средней скоростью полета летательного аппарата типа «воздух-воздух» / Метлицкая Д.В. // Св-во о гос. регистрации программы для ЭВМ № 2013617279. Федеральная служба по интеллект. собственности.-07.08.2013.

50. Метлицкая Д.В. Применение методов глобальной оптимизации, имитирующих иммунные системы живых организмов, в задаче оптимального управления дальностью полета летательного аппарата типа «воздух-воздух» / Метлицкая Д.В. // Св-во о гос.

регистрации программы для ЭВМ № 2013617280. Федеральная служба по интеллект, собственности.-07.08.2013.

51. Мептгщкая Д.В., Пантелеев A.B. Разработка комплекса программных средств «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // Модернизация и инновации в авиации и космонавтике: Сб. науч. тр. - М.: Изд-во МАИ-ПРИНТ, 2011. С. 305-310.

52. Михалевич В. С. Последовательные алгоритмы оптимизации и их применение. Последовательные правила для опытов с детерминированными исходами. 1965. № 1. С. 45-66.

53. Моисеев Н. Н. Методы динамического программирования в теории оптимальных управлений. Системы, допускающие использование шкалы управлений // Вычисл. мат. и мат. физ. 1964. 4. № 3. С. 485— 494.

54. Моисеев Н. Н. Численные методы теории оптимальных управлений, использующие вариации в пространстве состояний // Кибернетика. 1966. № 3. С. 1—29.

55. Моржин О. В. Нелокальное улучшение управлений нелинейными дискретными системами // Программные системы: теория и приложения. 2010. №1. С. 21—44.

56. Никифорова JI. Н., Ухин М. Ю.. Приближенный синтез дискретного оптимального управления // Программные системы: теория и приложения. 2004. С. 377-385.

57. Остославский КВ., Страэюева КВ. Динамика полета. Траектории летательных аппаратов. -М.: Машиностроение, 1969.

58. Паклин Н. BaseGroup Labs. Непрерывные генетические алгоритмы — математический аппарат // [Эл. ресурс]: http://www.basegroup.ru/genetic/ real_coded_ga.htm

59. Пантелеев A.B. Метаэвристические алгоритмы поиска глобального экстремума.— М.: Изд-во МАИ-ПРИНТ, 2009.

60. Пантелеев A.B., Алёшина Е.А. Применение метода частиц в стае к задаче поиска оптимального управления дискретными детерминированными системами // Эл. ж. «Труды МАИ», 2010, №37. [Эл. ресурс]: http://\vww. mai.ru/ science/trudy/ published.php?ID=13421.

61. Пантелеев A.B., Апостол Н.П. Формирование генетического алгоритма поиска условного экстремума с вещественным кодированием // Теоретические вопросы вычислительной техники и программного обеспечения: Межв. сб. н. тр., МИРЭА, 2008. С. 115-121.

62. Пантелеев A.B., Апостол Н.П. Алгоритмическое и программное обеспечение модифицированного генетического алгоритма условной оптимизации с бинарным кодированием // Вестник Московского авиационного института. 2008. Т. 15. №2. С. 113-123.

63. Пантелеев A.B., Бортаковский A.C. Теория управления в примерах и задачах. — М.: Высш. шк., 2003.

64. Пантелеев A.B., Дмитраков КФ. Применение метода дифференциальной эволюции в задаче поиска оптимального управления непрерывными детерминированными системами // Известия института инженерной физики. 2012. № 3 (25). С. 32-36.

65. Пантелеев A.B., Дмитраков И.Ф. Применение адаптивного метода имитации отжига в задаче оптимального управления непрерывными детерминированными системами // Информационные и телекоммуникационные технологии. 2012. № 14. С. 57-64.

66. Пантелеев A.B., Кыреев В.И. Численные методы в примерах и задачах. - М.: Высш. шк., 2008.

67. Пантелеев A.B., Летова Т.А. Методы оптимизации в примерах и задачах. - М.: Высш. шк., 2008.

68. Пантелеев A.B., Мептицкая Д.В., Применение генетических алгоритмов с бинарным и вещественным кодированием к задаче поиска условного экстремума функций // Теоретические вопросы вычислительной техники и программного обеспечения: Межвуз. сб. науч. тр., МИРЭА, 2010. С. 156-165.

69. Пантелеев A.B., Метлицкая Д.В., Комплекс программных средств «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием»// Электронный журнал «Труды МАИ», 2010, №37. [Эл. ресурс]: http://www.mai.ru/science/trudy/ published.php?ID=13421.

70. Пантелеев А.В, Мегтицкая Д.В. Модифицированный метод искусственных иммунных систем в задачах поиска оптимального управления дискретными системами // Информационные и телекоммуникационные технологии. 2012. № 14. С. 43-51.

71. Пантелеев A.B., Метлицкая Д.В. Применение метода искусственных иммунных систем в задачах поиска условного экстремума функций // Научный вестник МГТУ ГА. 2012. №184(10). С. 54-61.

72. Пантелеев A.B., Мепшицкая Д.В. Применение генетических алгоритмов с бинарным кодированием к задаче оптимального управления дискретными системами // Научный вестник МГТУ ГА. 2010. № 157(7). С. 34-^1.

73. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов с бинарным кодированием к задаче поиска оптимального управления непрерывными детерминированными системами // Авиакосмическое приборостроение. 2011. №2. С. 23-30.

74. Пантелеев A.B., Метлицкая Д. В. Формирование генетических алгоритмов с вещественным кодированием в задаче синтеза оптимального управления дискретными системами // Авиакосмическое приборостроение. 2011. №3. С. 26-31.

75. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов с вещественным кодированием к задаче оптимального управления дискретными системами // Вестник компьютерных и информационных технологий. 2011. №9. С. 17-23.

76. Пантелеев A.B., Метлицкая Д.В. Применение генетических алго-ритмов с бинарным и вещественным кодированием для приближенного синтеза субоптимального управления детерминированными системами // Автомат, и телемех. 2011. № 11. С. 117-129.

77. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов к задаче оптимального управления дальностью полета летательного аппарата типа воздух-воздух // Вестник Московского авиационного института. 2011. №4. Т.18. С. 102-113.

78. Пантелеев A.B., Мепишцкая Д.В. Формирование генетических алгоритмов поиска оптимального управления средней скоростью полета летательного аппарата типа воздух-воздух // Вестник Московского авиационного института. 2012. №3. Т.19. С. 149-159.

79. Пантелеев A.B., Мепишцкая Д.В. Приближенный синтез оптимального управления дискретными системами с помощью генетических алгоритмов с вещественным кодированием // Научный вестник МГТУ ГА. 2011. № 169. С.13-19.

80. Пантелеев А.В, Метлицкая Д.В. Комплекс программных средств «Генетические алгоритмы с бинарным и вещественным кодированием в задачах синтеза оптимального управления дискретными и непрерывными динамическими системами»// Проблемы авиастр., космон. и ракетостр.: Сб. науч. тр. - М.: Изд-во Ваш полиграфич. партнер. 2012. С. 296-302.

81. Пантелеев А. В., Метлицкая Д. В. Применение метода динамических сеток в задачах поиска оптимального управления дискретными детерминированными системами // Научный вестник МГТУ ГА, №195. 2013. С. 21-28.

82. Пантелеев A.B., Рязанцева О.В. Применение метода табу-поиска к решению задач оптимального управления дискретными системами // Научный вестник МГТУ ГА. 2011. № 165. С.103-111.

83. Пантелеев A.B., Рязанцева О.В. Применение жадного адаптивного метода случайного поиска к задаче оптимального управления дискретными системами // Информационные и телекоммуникационные технологии. 2012. №16. С. 46-52.

84. Петров Б.Н., Портнов-Соколов Ю.П., Андриенко А.Я., Иванов В.П. Бортовые терминальные системы управления.-М.: Машиностроение, 1983.

85. Подвальный Л. Д. Об одном численном методе решения задачи оптимального управления // Вычисл. мат. и мат. физ. 1969. 9. № 2. С. 300-314.

86. Поляк Б.Т. Введение в оптимизацию. - М.: Наука, 1983.

87. Понтрягин Л. С., Болтянский В. Г., Гамкарелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. - М.: «Наука». 1969.

88. Пропой А. И. Методы возможных направлений в задачах оптимальногодискретно-го управления // Автоматика и телемеханика. 1967. № 2 . С. 69—79.

89. Разоренов Г.Н., Бахрамов Э.А., Титов Ю.Ф. Системы управления летательными аппаратами (баллистическими ракетами и их головными частями).— М.: Машиностр., 2003.

90. Растригин Л.А. Случайный поиск. - М.: Знание, 1979.

91. Рязанцева О.В. Метод направленного табу-поиска условного глобального экстремума функций многих переменных// Теоретические вопросы вычислительной техники и программного обеспечения: Межвуз. сб. науч. тр., МИРЭА, 2011. Т. 1. - С. 93-99.

92. Стариков A. BaseGroup Labs. Генетические алгоритмы — математический аппарат// [Эл. ресурс]: http://\vww. basegroup.ru/genetic/ ath.htm.

93. Сухарев А.Г. Глобальный экстремум и методы его отыскания. - М.: Изд-во МГУ, 1981.

94. Тятюшкгш А. И. Численные методы и программные средства оптимизации управляемых систем. Новосибирск. Наука. 1992.

95. Федорепко Р. П. К обоснованию метода вариаций в фазовом пространстве для численного решения задач оптимального управления // Вычисл. мат. и мат. физ. 1969. 9. № 6. С. 1396—1402.

96. Черноусъко Ф. Л., Колмановский В. Б. Вычислительные и приближенные методы оптимального управления // Итоги науки и техн. Сер. мат. анал. 14. ВИНИТИ. М. 1977. С. 101-166.

97. Шатровский Л. И. Об одном численном методе решения задач оптимального управления // Вычисл. мат. и мат. физ. 1962. 2. № 3. С. 488—491.

98. Энеев Т. М. О применении градиентного метода в задачах оптимального управления // Космические исследования. 1966. 4. № 5. С. 651—669.

99. Bomze I.M. et al. Developments in Global Optimization. - London, Kluwer, 1997.

100. BrownleeJ., Clever Algorithms: Nature-Inspired Programming Recepes. - LuLu, 2011.

101. BtysonA. E., Denham W. F. A steepest-ashent method for solving optimum programming problems. Trans. ASME. 1962. 29. № 2. P. 247—257.

102. de Castro L. N., Von Zuben F. J. Learning and Optimization Using the Clonal Selection Principle // IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Immune Systems. -2002. V. 6. №3. P. 239-251.

103. de Castro L., Timmis J. An Artificial Immune Network for Multimodal Function Optimization // Proceedings of IEEE Congress on Evolutionary Computation. 2002.V.1. P.669-674.

104. de Castro L. N„ Von Zuben F. J., Knidel II. Artificial Immune Systems //Proceedings of 6th International Conference, ICARIS 2007. - Springer, 2007.

105. Chambers L. Practical handbook of genetic algorithms, applications. - Chapman and Hall/CRC, 2001.

106. Dasgupta S. et al. Adaptive Computational Chemotaxis in Bacterial Foraging Optimization: An Analysis // IEEE Transact, on Evolutionary Comput. - 2009. V.13. № 4. P. 919-941.

107. DeJong K., Fogel L., Schwefel H-P. Handbook of evolutionary computation. - IOP Publ. Ltd and Oxford University Press, 1997.

108. Dixon L.C.W., Szego G.P. Towards Global Optimization 2.-North-Holland, 1978.

109. Duarte A., Marti R., Glover F., Gortazar F., Hybrid scatter tabu search for unconstrained global optimization// Annals of operations research. 2011, V. 183. № 1. P. 95-123.

110. Elbeltagi E., Hegazy Т., Grierson D. Comparison among five evolutionary-based optimization algorithms// J. Adv. Eng. Informatics. - 2005. V.19. P. 43-53.

111 .Feoktistov V. Differential Evolution In Search of Solutions. - Springer, 2006.

112. Floudas C.A., Pardalos P.M. (Eds.) Encyclopedia of optimization. - Springer, 2009.

113. Glover F. Heuristics for Integer Programming Using Surrogate Constraints // Decision Sciences.-1977. V. 8. P. 156-166.

114. Glover F. IV., Kochenberger G.A. (eds) Handbook of Metaheuristics. - 2003.

115. Glover F, Marti R., Lagitna M. Fundamentals of Scatter Search and Path Relinking // Control and cybernetics. -2000. V. 39. P. 653-684.

116. Glover F„ Marti R., Lagima M. Principles of Scatter Search // European Journal of Operational Research.-2006. V. 169. №2. P. 359-372.

117. Goldberg D. Genetic Algorithms in Search, Optimization and Machine learning. -Addison-Wesley, 1989.

118. Hansen N., Kern St. Evaluating the CMA Evolution Strategy on Multimodal Test Functions, Parallel Problem Solving from Nature // PPSN 2004. V. 3242. P. 282-291.

119. Hansen N., Ostermeier A. Completely Derandomized Self-Adaptation in Evolution Strategies // Evolutionary Computation. - 2001. V. 9. № 2. P. 59-195.

120. Hedar Abdel-Rahman, Fukushima Masao. Tabu Search directed by direct search methods for nonlinear global optimization// Department of Applied Mathematics and Phisics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan, 2003.

121. Herrera F., Lozano M., Molina D. Test Suite for the Special Issue of Soft Computing on Scalability of Evolutionary Algorithms and other Metaheuristics for Large Scale Continuous Optimization Problems, Technical report, University of Granada, 2010.

122. Herrera F., Lozano M., Verdegay J.L. Tackling real-coded genetic algorithms: operators and tools for the behavior analysis// Artificial Intelligence Review. - 1998. V.12. № 4. P. 265-319.

123. Holland J.N. Adaptation in Natural and Artificial Systems. - Ann Arbor, Michigan: Univ. of Michigan Press, 1975.

124. Ho Yu-Chi. A computational technique for optimal control problems with state variable constraint // Math. Aanlys. and Applic. 1962. 5. № 2. P. 216— 224.

125. Igel C., Hansen N., Roth St. Covariance Matrix Adaptation for Multi-objective Optimization//Evolutionary Computation.-2007. V. 15. №1. P. 1-28.

126. Ingber L. Genetic algorithms and very fast simulated reannealing: a comparison // Mathematical and Computer Modelling. - 1992. V.16 (11). P. 87-100.

127. Ishida Y. et al. Immunity-Based Systems-Intelligent Systems by Artificial Immune Systems - Corona Pub., Co. Japan, 1998.

128. Kelley H. J., Kopp P. E., Moyer H. G., Successive approximation techniques for trajectory optimization. Proc. of the Symp. on Vehicle System Optimization, N. Y., 1961

129. Lee K.S., Geem Z.W. A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice // Computer Methods in Applied Mechanics and Engineering. - 2005. V.194. P. 3902-3933.

130. Lopez Cruz J.L., Van Willigenburg L.G., Van Slraten G. Evolutionary Algorithms for optimal control of chemical processes// Proceedings of the IASTED International Conference on Control Applications. - 2000. P. 155-161.

131. Lints R. Iterative Dynamic Programming. — Monographs and Surveys in Pure and Applied Mathematics, London, UK: Chapman & Hall/CRC, 2000.

132. Martí R., Laguna M. Scatter Search: Basic Design and Advanced Strategies, Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial. 2003. №19. P. 123-130.

133. Michalewicz Z. Genetic algorithms, Numerical optimization and constraints // Proc. of the 6th Int. conf. on genetic algorithms. - 1995. P. 151-158.

134. Michalewicz Z., Fogel D. How to solve it: modern heuristics. - Springer, 2004.

135. Mishra S.K. Some New Test Functions For Global Optimization And Performance Of Repulsive Particle Swarm Method, Munich Personal RePEc Archive (MPRA), 2007.

136. Mitchell M. An introduction to Genetic Algorithm. - MIT Press, 1996 /CRC press,

1996.

137. Neumaier А. Личная страница, набор тестовых функций // [Эл. ресурс]: http://www.mat.univie.ac.at/~neum/glopt/ test_results.html.

138. Posik P. Stochastic Local Search Techniques with Unimodal Continuous Distribu-tions//A Survey, Evo Workshops '09 Proceedings of the Evo Workshops 2009 on Applications of Evolutionary Computing. P. 685 - 694.

139. Puris A. et al. Variable mesh optimization for continuous optimization problems // Soft сотр. DOI 10.1007/s00500-011-0753-9, Springer, 2011.

140. Rinnoy Kan A.H.G., Timmer G.T. Stochastic Global Optimization Methods // Mathematical programming.-1987. V. 39. P. 27-78.

141. Suganthan P. et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Technical report, Nanyang Technological University, 2005. - [Эл. ресурс]: http://www.ntu.edu.sg/home/ EPNSugan/.

142. Torn A. Global Optimization as a Combination of Global and Local Search. - Turku, Abo Akademi University, 1974.

143. Wolpert David II, Macready Williams G. No free lunch theorems for optimization // IEEE Trans, on evolutionary computation - 1997. V.l(l). P. 67-82.

144. Wright A. Genetic algorithms for real parameter optimization// Foundations of Genetic Algorithms. - 1991. V.l. P. 205-218.

Приложение 1. ХАРАКТЕРИСТИКИ И ТЕХНИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ ПОИСКА ОПТИМАЛЬНОГО

УПРАВЛЕНИЯ РАКЕТОЙ

Рассматривается задача управления ракетой класса "воздух-воздух" средней дальности А1М-120 [21]. Характеристики ракеты представлены в табл. 111.1. Аэродинамические характеристики представлены в табл. П1.2.

Таблица П1.

Характеристика ракеты Значение

Стартовый вес ракеты 161,5 кг

Конечный вес ракеты 110,4 кг

Площадь миделя (лт) 0,024885 м2

Время управляемого полета 150 с

Диаметр миделя 178 мм

Длина ракеты 3,65 м

Максимальная допустимая перегрузка на активном участке полета 8

Максимальная допустимая перегрузка на пассивном участке полета 25

Максимальный угол атаки (атах) 30°

Эквивалентное нагружение 1

Таблица П1.2

Характеристика Зависимость аэродинамической характеристики от скорости ракеты

Мах 0,5 0,8 1,05 1,2 1,5 2,0 3,0 4,0 6,0 12,0

с*о 0,45 0,45 0,764 0,68 0,6 0,49 0,4 0,32 0,32 0,245

Сх0р 0,6 0,6 0,98 0,96 0,83 0,63 0,49 0,37 0,37 0,307

СУ 0,18 0,18 0,18 0,13 0,11 0,09 0,07 0,08 0,06 0,06

сы 0,3 0,32 0,3 0,3 0,3 0,318 0,32 0,32 0,32 0,28

Система наведения ракеты - радиолокационная головка наведения (пассивная-активная) и инерциальная система управления. На ракете используется двухрежимный ракетный двигатель твердого топлива.

В табл. 2.15 представлены следующие аэродинамические характеристики:

• сх0 - коэффициент лобового сопротивления вблизи поверхности Земли на активном участке полета при нулевом угле атаки;

• сх0 - коэффициент лобового сопротивления вблизи поверхности Земли на

пассивном участке полета при нулевом угле атаки;

• су[ - коэффициент подъемной силы вблизи поверхности Земли при нулевом угле

атаки;

• сп1 - коэффициент, показывающий влияние высоты на аэродинамические характеристики ракеты.

Упрощенная диаграмма тяги двигателя вблизи поверхности Земли представлена в табл. П1.3.

__Таблица П1.3

Режим работы Время работы Тяга двигателя Массовый расход

двигателя режима, с топлива, кг/с

1 1,9 3350,0 13,4

2 3,4 1820,0 7,5526

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

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

Движение ракеты рассматривается в вертикальной плоскости в одном канале наведения и описывается системой дифференциальных уравнений [12, 57]:

в =—(и- соз(0 ч---—));

V ь + я"

■ ./г-соза-Р б х ..

V = £(-— - яп(е+-——));

пщ п + к3

х = к-собо;

где х, у, V, 9 — фазовые переменные ракеты; х, у - горизонтальная и вертикальная координаты ракеты; V - модуль скорости ракеты; 0 - угол наклона траектории (угол межлу наппавлением скопости пакеты и гопизонтальной осью"): и — управляемая величина (поперечная перегрузка ракеты); а - угол атаки при заданной перегрузке (угол между вектором скорости и продольной осью ракеты); g - ускорение свободного падения с учетом высоты над поверхностью Земли, которое вычисляется по формуле

£ = 9,8

—7 О

, где Я3 - радиус Земли; И = .у+ 0,785-10 х - высота над поверхностью

Земли; т - масса ракеты, зависящая от времени и режима работы двигателя (см. табл. 2.16); Я - тяга двигателя ракеты, определяемая режимом работы двигателя и высотой полета ракеты. Вектор поперечной перегрузки ракеты направлен перпендикулярно направлению вектора скорости ракеты. Допустимые значения управления определяются характеристиками ракеты и показаны в табл. 2.14. При пассивном полете двигатель отключен (Я=0), а при активном полете двигатель работает и тяга равна Р —Р(И)

д = ад+0,05 0 уч), где До - тяга двигателя вблизи поверхности Земли (см. табл.

П1.3); Ро - атмосферное давление вблизи поверхности Земли; Р(К) - атмосферное давление на высоте /г (используется стандартная атмосфера Земли); Елоб - сила лобового сопротивления: Рло6=сх-ц-8т, где 8т — площадь миделя (см. табл Ш.1.); # - скоростной

V2

напор, вычисляемый по формуле = р(/г)—; сх - коэффициент лобового сопротивления

при заданном угле атаки, р(К) - плотность воздуха на высоте И.

Коэффициент лобового сопротивления при заданном угле атаки и угол атаки ракеты на активном участке полета рассчитываются следующим образом:

_ а* пт _ _ _

а - ' Суп ~а'сп!> Сх - Сх0 + СЫ' Сгш1 ~ Суп^а '

а*„т с

на пассивном участке полета с = —-—, а = , сх = сх0 + с1пЫ, с1Пе1 = с; если угол атаки превышает максимально допустимый, то

а = ашах' Суп - а ' Сп1 > Сх = Сх0 + Стс1' Стс1 = С_)п18а .

где ап — управление, поперечная перегрузка с учетом эквивалентного нагружения, суп -

коэффициент подъемной силы с учетом эквивалентного нагружения, а - угол атаки с учетом эквивалентного нагружения, т - текущая масса ракеты, схо, сп1 -

аэродинамические характеристики ракеты (см. табл. П1.2), сш - коэффициент индуктивного сопротивления.

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

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

а) максимальную дальность полета;

б) максимальную конечную скорость полета.

Запуск ракеты считается успешным, если конечная высота ракеты отличается от заданной высоты не более чем на 200 метров.

Приложение 2. НАБОР ТЕСТОВЫХ ФУНКЦИЙ

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

Наиболее часто используемые для тестирования многомерные функции приведены в [121, 135, 137].

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

• унимодальная функция: параболическая функция (Sphere function);

• унимодальная функция со сложной структурой линий уровня в виде щели: функция

Розенброка (Rosenbrock's saddle);

• функции с одним глобальным и локальными экстремумами: синусоидальная

функция Швефеля (Schwefel's Sine Root function), функция Растригина (Rastrigin's

function), функция Экли (Ackley's function);

• функция с одним глобальным и бесконечным числом локальных экстремумов:

функция Шаффера (Schaffer's function);

• функции с несколькими глобальными экстремумами: мульти-функция (Multi

function), корневая функция (Roots function).

Таблица П2.1

Название функции Формула Множество допустимых решений Глобальный экстремум Дх';у) Точки глобал! ного экстремума (* \УУ

Параболическая функция (рис.П2.1) Дх,у) = -х2-у2 х,у 6 [-2; 2] 0 ((;0)г

Функция Розенброка (рис. П2.2) Дх,у) = -а[у-х2)~-(\-х)2 х,уе[-2; 2] 0 0;1)7

Синусоидальная функция Швефеля (рис. П2.3) Дх, у) = х зтСТГ*]) + у зтОу/Ш) д:, >» е [—500; 500] 837,9657 (420,968' ;420,9687)г

Мульти-функция (рис. П2.4) / (х, у) = х 8т(4;гх) + у эт^я-^) х,у е [-2; 2] 4,2539 (-1,6288;-1,6288 ,т (1,6288;1,6288)г (-1,6288; 1,6288)7 (1,6288;-1,6288)г

Корневая функция (рис. П2.5) /* (г) =-\-,zeC,z = x + iy х,уь[-2\2] 1 (-1;0)г (0,5;-0,8 56)г (-0,5;0,866)г (1; 0)т (0,5; 0,866 )т (-0,5;-0,866)г

Функция Шаффера (рис. П2.6) зт'^х'+у^-О.З 2 (1 + 0.001(х2+У)) е[-10;10] 1 ((;0)'

Функция Растригина (рис. П2.7) Дх, у) = -20 + (10 соэ(2л- х)-х2) + +(10соз(2/г у)-у2) х,у<= [-5; 5] 0 ((;0 у

Функция Экли (рис. П2.8) ( 1х2+ 2 Дх,у)= е + 20ехр Л у \ У \ +ехр — (со8(2я-х) + соз(2л-,у)) 42 , + х,_уе[-10;10] 20 ((;0)г

Рис. П2.1. Изображения поверхности и линий уровня параболической функции

-500

-1 500

-2 500

У -1

Рис. П2.2. Изображения поверхности и линий уровня функции Розенброка при а = 100

-500 -500

-500 -400 -300 -200 -100 0 100 200 300 400 500

Рис. П2.3. Изображения поверхности и линий уровня синусоидальной функции Швефеля

Рис. П2.4. Изображения поверхности и линий уровня мульти-функции

1,5

-1,5

/¡©V •71С • 1» / ^7)

/Оху

\ 1

Ко! /

.......

-2 -1.5 -1 -0.5 0 0.5 1

Рис. П2.5. Изображения поверхности и линий уровня корневой функции

0.25

Рис. П2.6. Изображения поверхности и линий уровня функции Шаффера

-5 -4 -3 -2 -1 0 1 2 3 4 5

x

Рис. П2.7. Изображения поверхности и линий уровня функции Растригина

Приложение 3. МЕТОД РАССЕИВАНИЯ

П3.1. ОПИСАНИЕ СТРАТЕГИИ ПОИСКА ГЛОБАЛЬНОГО

ЭКСТРЕМУМА

Метод рассеивания относится к эволюционным методам оптимизации, поэтому при

/">Т-¥ТЖûûТТТТТТ * 1ЛТГ» ПП Г ТТЛ* Г П«ТТТТЛЛМ»Т1Г»ОТТ Л<Т ТГЛТГ чт»П ТПП»*Т1Т1ЛПЛГтт ТГГЛ ТТ Г» П1ЛТ ГГТ^ »-чт>гч ТТТ/-*ТТТГ/-» ТТТТГ тлг

п ^гл 1 1 а 'н v

методах (популяция, особи и др.).

Классический метод рассеивания применим к решению задачи оптимизации целевой функции (В.1-В.2).

В методе рассеивания рассматриваемая целевая функция /(х) называется функцией приспособленности, а вектор параметров х = {хх,х2,...,хп)Т целевой функции — особыо. Каждый вектор является возможным решением поставленной оптимизационной задачи. Чем меньше значение целевой функции /(х), тем более особь х приспособлена, т.е. подходит в качестве решения.

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

Процедура поиска глобального экстремума начинается с генерации базового множества особей А. Для этого сначала на отрезке [а,,6,] изменения каждой координаты

выделяются 5 подынтервалов одинаковой длины. В базовое множество последовательно добавляется по одной особи:

1) для каждого отрезка [«,,6,] генерируется номер _/', подынтервала с вероятностью,

обратно пропорциональной числу раз, которое этот подынтервал уже выбирался;

2) генерируются значения координат х, случайным образом внутри выбранных подынтервалов;

3) если минимальное расстояние между сформированной особью и особями базового множества больше заданной величины а, то особь добавляется в базовое множество; иначе - не добавляется, рассеивание продолжается с п. 1.

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

При решении задачи (В.2) используются конечные наборы У = {х-> = (х{ ,х{,...,х^)т= \,2,...,Ир} с В возможных решений, называемые популяциями,

где х' — особь с номером у , Ыр — размер популяции.

Идеи рассеивания применяются также и при формировании начальной популяции. Популяция состоит из Ыр = ¿7, + Ъ2 особей, которые выбираются из базового множества

особей А. При этом Ьх особей выбираются по качеству (наилучшие особи по величине

функции приспособленности), а Ъ2 особей выбираются по расстоянию (суммарное

расстояние от них до уже имеющихся в начальной популяции особей должно быть минимально).

Метод рассеивания имитирует эволюцию начальной популяции ^о = =(х{,х{,...,х1)т е£>}

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

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

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

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

157

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

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

Общая схема работы метода рассеивания представлена на рис. П3.1.

Рис. П3.1. Общая схема работы модифицированного метода рассеивания

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

Мутация применяется к множеству потомков во время его формирования. Среди потомков выделяются Np = bx+b2 наилучших решений, для каждого из которых

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

На рис. П3.1 на шаге 4 добавлен оператор мутации, который работает при использовании модифицированного метода рассеивания.

П3.2. ПРИМЕНЕНИЕ МЕТОДА РАССЕИВАНИЯ В ЗАДАЧЕ НАХОЖДЕНИЯ ОПТИМАЛЬНОГО ПРОГРАММНОГО УПРАВЛЕНИЯ ДИСКРЕТНЫМИ СИСТЕМАМИ

При использовании метода рассеивания для решения задачи (В.З) - (В.6) нахождения оптимального программного управления дискретными системами будем оптимизировать управление и(-).

Целевой функцией, а также функцией приспособленности будет являться функционал I(d) = 1(х(-),и(•))• Особь с номером к в популяции будет представлять собой вектор

ик = (ик(0),ик (\),...,ик(iV-l))r, который соответствует дискретному управлению

Для того чтобы найти значение функционала I(dk), соответствующее паре dk = (хк (-),ик (•)), нужно найти траекторию xk(-) = {x(Q),xk(\),...,xk(N)}, соответствующую управлению ик, из уравнения дискретной системы (В.З) с учетом начального условия (В.4).

МЕТОДИКА РЕШЕНИЯ ЗАДАЧИ

Шаг 1. Создание базового множества А.

1.1. Задать параметры метода: максимальное количество особей в базовом множестве Asize; количество подынтервалов s; параметр рассеивания сг; максимальное количество

вычислений целевой функции Ы/. Задать к = О (счетчик количества особей в базовом множестве) и р = 0 (счетчик числа вычислений функции приспособленности).

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

" = ^2,1'*"'^ЛМ') = [щ >^2 ) »

где п = к = \,2,...,Аз1ге (заметим, что здесь й* = й*(/-1)).

1.2. На каждом отрезке [а, (/),&,(/)], / = 1,./ е Г = [0,1,—,N-1], где д -

размерность вектора управления, — число шагов, выделить д подынтервалов. Для каждой координаты / = времени / б Т = [0,1,ТУ — 1] и для каждого номера подынтервала

/ = задать количество попаданий = 0 .

1.3. Для каждого подынтервала с номером у (j = \,...,s) на каждом отрезке [£/,(/),&,(/)], / = 1,...,^, вычислить вероятность его выбора:

5

ри _ к=\,кф]_

7 _ 5

к=: 1

1.4. Для каждой координаты / = 1,...,^ и времени ^ е Г = [0,1,...,ЛГ-1] с вероятностью Р'1* выбрать подынтервал с номером т1,, где т1, е {1,...,^}, и, используя равномерный закон распределения на выбранных подынтервалах, генерировать значения координат особи й,+]

и саму особь й = Й2,...,Й*) е£/.

Г"

1.5. Если й&А и (¡(й,А)>а, d(i^, А) = гтп d(x,й), d(x,й) = /УЧх,-й,)2 , то добавить

^ V <=1

особь у к множеству А: А = Аи{й}, положить к = к +1; иначе перейти к шагу 1.4.

1.6. Для каждой координаты / = 1,...,<? и времени /еГ = [0,1,...,А^-1] изменить количество попаданий /гед(1^,т11) = /гед(1,(,тп) + \.

1.7. Если £ = , процесс генерации базового множества завершить, перейти к шагу 1.8; иначе — перейти к шагу 1.3.

1.8. Для всех особей множества А вычислить значение функции приспособленности 1к = 1(хк(•),ик(•)) , к = \,2,...,А.ыге. Для этого необходимо найти траекторию хк(•),

соответствующую особи йк е А. Расположить особи по возрастанию соответствующих им значений функции приспособленности: А = {z7(1),...,z7(/ii'2f!)}, где = 1тт.

Положить p = Asize.

Результатом шага 1 является сформированное упорядоченное базовое множество А с особями, достаточно отличающимися друг от друга. Шаг 2. Создание начальной популяции.

2.1. Задать параметры метода: количество «качественных» особей в популяции Ьх; количество добавляемых по расстоянию особей Ъ2; t = 0 - счетчик популяций.

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

2.3. Данный шаг выполнить Ь2 раз. Для каждой особи uJ множества А вычислить расстояние до особей начальной популяции: d(uJ,Y0) = ^ d(uJ,и). Добавить в начальную

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

2.4. Расположить особи начальной популяции по возрастанию соответствующего им

значения функции приспособленности: У0 = где Np = bx+b2,

I(xw(-),u(l)(-y) = Imitl.

Результатом шага 2 является упорядоченная начальная популяция У0. Шаг 3. Генерация родительских пар из элементов популяции (селекция). Сформировать множество Set из пар особей, входящих в текущую популяцию (число пар

равно ^ ^^——, где Np = b{+b2)\ при очередном формировании в множество Set должна

входить хотя бы одна новая пара.

Результатом шага 3 является множество из родительских пар Set. Шаг 4. Генерация множества потомков (скрещивание). Создать пустое множество потомков ChildSet. Для каждой пары (х;_у) из множества Set выполнить шаги 4.1-4.4:

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

1 4 1

zi(Xi) = x + 'ki(y-x), i = 1,2,3, =-, ^2 = 2' ^з =--•

4.2. Вычислить значения функции приспособленности 1(хх (•), z{ (•)), /(x2(-),z2(-)), /(x3(-),z3(0), предварительно определив соответствующие траектории. Выбрать потомка z*, которому соответствует минимальное значение функции приспособленности. Положить р = р + 3.

4.3. Добавить потомка z* в множество потомков ChildSet. Удалить пару из множества Set.

4.4. При использовании модификаций применить один из методов улучшения множества потомков ChildSet, приведенных в описании стратегии модифицированного метода рассеивания (подробно см. далее). Пусть при использовании метода улучшения производилось Bp вычислений функции приспособленности. Тогда следует положить р = р + Вр.

Результатом шага 4 является множество потомков ChildSet. Шаг 5. Формирование новой популяции.

5.1. Сформировать популяцию Yt+x=Yt. Положить NewSolution = false, t = t +1. Для каждого потомка z из множества потомков ChildSet выполнить:

5.2. Для каждой особи ик, k = \,..,Np, из новой популяции Y, вычислить расстояние d(uk,z) . Выбрать решение и2, которому соответствует наименьшее

расстояние d(uz ,z) = min d(u, z).

ueY,

5.3. Если выполнено одно из условий:

а) /(x--(-)5"z0)<V(-),",0);

б) 1(х:(•),и:(•))</(xNp(•),uNp(•)), где Np = bx+b2, и d(u\z)><s,

то заменить особь uNp в популяции Yt на потомка z: Yt =Yt\{uNp}u{z}, положить

NewSolution = true; иначе — перейти к следующему потомку. Результатом шага 5 является новая популяция. Шаг 6. Проверка условий окончания локального поиска. Если NewSolution = true, локальный поиск продолжить, перейти к шагу 3. Если NewSolution = false, локальный поиск закончить, перейти к шагу 7. Шаг 7. Сокращение популяции. Расположить особи текущей популяции по возрастанию соответствующего им значения функции приспособленности:

Yt = {и(1),...,и(лм}, где Np = bi+b2, J(xw(-),uw(-)) = Imin. Удалить b2 последних особей (с

наихудшим значением функции приспособленности).

Результатом шага 7 является сокращенная популяция.

Шаг 8. Проверка условий окончания глобального поиска. Если р < Nf, то глобальный поиск продолжить, перейти к шагу 9; иначе - глобальный поиск завершить, перейти к шагу 10.

Шаг 9. Пополнение популяции из базового мноэюества.

9.1. Данный шаг выполнить Ь2 раз. Для каждой особи множества А вычислить расстояние до особей текущей популяции: d(üJ,Yt) = ^ d(üj,и). Добавить в популяцию

не/,

особь с минимальным расстоянием до популяции и удалить ее из базового множества А .

9.2. Расположить особи популяции по возрастанию соответствующего им значения

функции приспособленности: Y, ={M(1),...,z/yVp)}, где Np = b{+b2, f(x(1)(-),uw(-)) = Imin. Перейти к шагу 3.

Шаг 10. Выбор решения из последней популяции. Из текущей популяции выбрать клетку и* с наименьшим значением функции приспособленности:

и* = ü* = arg min I(xJ (•), uJ (•)) • В качестве решения (приближенного) задачи (1.1) - (1.4)

J=\,-,Np

выбрать пару d* = (х*(-),и*(-)). Значение функционала (целевой функции) при этом будет равно I(d*) = I(x *(•),« *(•))•

МОДИФИКАЦИИ МЕТОДА РАССЕИВАНИЯ

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

1. Выделить среди множества потомков ChildSet Np особей с наилучшей приспособленностью. Если в множестве меньше, чем Np потомков, выделить все множество.

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

2.1. Упорядочить переменные z(, i = \,..,n, мутируемого потомка z случайным образом. Положить New = false - индикатор наличия улучшений, j = 0 - номер переменной в упорядоченном списке.

2.2. Пусть на j -и месте в списке стоит /-я переменная. «Просканировать» множество, то есть вычислить значение функции приспособленности для особей из множества ls(z, h,i) = {у е Rh | у = z + khet, к е Z, а < у < Ь), где et - единичный орт, состоящий из всех нулей и одной единицы на i -м месте,

<* = (<*! (0),...,а9(0),а, (Г),...,aqQ),...,ax (N-l),...,aq(N-l)f =(а, ,a2,...,anf,

2.3. Если в результате сканирования находится особь у такая, что /(*(•), >>(•)) <КХ(')>2('У)> то потомка z заменить особью у, положить New = true.

2.4. Если j <п, то положить j = j +1 и перейти к шагу 2.2. Если j = n, то, если New = true , положить j = 0, а если New = false, перейти к шагу 2.2, иначе - процесс локального линейного поиска завершить.

Табу-поиск. В качестве улучшающего метода в методе рассеивания можно использовать табу-поиск [109]. Ниже приведен алгоритм, основанный на локальном линейном поиске с применением идей табу-поиска. Дополнительно задаваемые параметры метода - количество улучшаемых направлений ts, максимальный размер табу-листа tenure, шаг поиска h. В начале работы метода рассеивания необходимо задать значения дополнительных параметров, а также создать пустой табу-лист. Далее, после каждой глобальной итерации табу-поиска в табу-лист необходимо добавлять новую информацию.

1. Выделить среди множества потомков ChildSet Np особей с наилучшей приспособленностью. Если в множестве меньше, чем Np потомков, выделить все множество.

2. Для каждого из выделенных потомков выполнить процедуру улучшения (шаги 2.12.5) (глобальная итерация табу-поиска).

2.1. Для каждого номера / переменной, которая не находится в табу-листе, найти величину привлекательности поиска:

A(z, /) = тах[/(х(-)> *(•))■- I(xI+h(-),z'+h (•)), / (*(■),z(-))^- I(x'~" (•),*'"* О)],

где состояние х'+1'(-) и управление z'+/'(-) соответствуют особи z'+h =(ul,...,ul +h,...,un)T, а

состояние х'-/'0 иуправление z'~h(-) соответствуют особи z'~b = (iil,...,uj-h,...,un)T.

2.2. Упорядочить переменные по убыванию величины соответствующей привлекательности A(z,i): первой переменной соответствует наибольшее значение A(z,i). Положить / = 0 - номер переменной в упорядоченном списке.

2.3. Пусть на первом месте в списке стоит /-я переменная. «Просканировать» множество ls(z,h,i) как в локальном линейном поиске. Выбрать лучшую особь z1 в данном множестве и заменить ею потомка z (даже если 1(х '(•), z '(•)) > 1(х(')> г(0) )• Занести / -ю переменную в табу-лист на tenure глобальных итераций (после tenure глобальных итераций / -ю переменную из табу-листа удалить). Положить j = j +1.

2.4. Пусть на j-u месте в списке стоит к-я переменная. «Просканировать» множество ls(z\h,k) как в локальном линейном поиске. Выбрать лучшую особь z" в данном множестве. Если I(x"(-),z"(-)) < 1(х'(■)>z'(•))> то заменить z' на особь z". Занести к-ю переменную в табу-лист на tenure глобальных итераций.

2.5. Если j < ts, то положить j = j +1 и перейти к шагу 2.4. Если j = ts, то процесс завершить.

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