Метаэвристические алгоритмы поиска оптимального программного управления

А.В. ПАНТЕЛЕЕВ
Д.В. СКАВИНСКАЯ
Е.А. АЛЕШИНА
МЕТАЭВРИСТИЧЕСКИЕ  
АЛГОРИТМЫ   ПОИСКА  
ОПТИМАЛЬНОГО  
ПРОГРАММНОГО  УПРАВЛЕНИЯ 
МОНОГРАФИЯ
Москва
ИНФРА-М
2020

УДК 517.977(075.4)
ББК 22.14
 
П16
Р е ц е н з е н т ы: 
А.В. Борисов – д-р физ.-мат. наук, ведущий научный сотрудник (Институт 
 
проблем информатики Федерального  исследовательского  центра «Информатика и управление»  Российской академии наук);
Л.В. Вишнякова – д-р техн. наук,  проф., начальник подразделения (Государственный научно-исследовательский институт авиационных систем)
П16
Пантелеев А.В.
Метаэвристические алгоритмы поиска оптимального программного управления : монография / А.В. Пантелеев, Д.В. Скавинская, Е.А. Алешина. — Москва : ИНФРА-М, 2020. — 396 с. — 
(Научная мысль). — DOI 10.1273718293.
ISBN 978-5-16-011841-3 (print)
ISBN 978-5-16-104298-4 (online)
В книге описано применение современных методов поиска условного 
глобального экстремума: эволюционных методов; методов «роевого» интеллекта; методов, имитирующих физические процессы; мультистартовых 
методов в задачах нахождения оптимального программного управления 
нелинейными детерминированными динамическими системами. В каждом разделе приведены постановка задачи, стратегия поиска, детальный 
алгоритм решения, результаты решения модельных примеров и прикладных задач.
Для студентов и аспирантов  технических вузов и университетов, 
а также инженеров, интересующихся проблемами глобальной оптимизации и теории управления.
УДК 517.977(075.4)
ББК 22.14 
©  Пантелеев А.В., Скавинская Д.В., 
      Алешина Е.А., 2016
ISBN 978-5-16-011841-3 (print)
ISBN 978-5-16-104298-4 (online)

ВВЕДЕНИЕ
Отличительной особенностью большинства актуальных научно-технических задач проектирования современных образцов ракетно-космической и авиационной техники является поиск рациональных решений
в многомерном пространстве альтернатив. Показатели качества сравниваемых вариантов, как правило, описываются нелинейными зависимостями и оцениваются при помощи сложных моделирующих алгоритмов, 
что обусловливает высокую трудоемкость вычислений при решении задач оптимизации. Применение классических численных методов поиска
экстремума многоэкстремальных функций со сложным рельефом поверхностей уровня становится малоэффективным [44, 45, 64]. В настоящее время существует достаточно много оригинальных методов поиска
глобального экстремума [11, 67, 107, 161, 167]. Одной из основных проблем их практического использования является обеспечение сходимости к точному решению задачи оптимизации, заключающейся в поиске
наилучшего (наибольшего или наименьшего) значения целевой функции на множестве допустимых решений. 
В настоящее время большое внимание в научной литературе уделяется приближенным методам глобальной оптимизации, которые позволяют найти решение высокого качества за приемлемое (с практической
точки зрения) время. Среди них широкое распространение получили
метаэвристические методы оптимизации. Описание этих, а также других методов глобальной оптимизации, можно найти в [6, 9, 13–15, 24, 
27, 54, 80, 86, 95, 98, 102, 107, 112, 147, 156, 163]. В отличие от классических методов оптимизации, метаэвристические методы могут применяться в ситуациях, когда практически полностью отсутствует информация о характере и свойствах исследуемой функции. Эвристические методы, основанные на интуитивных подходах, позволяют найти достаточно хорошие решения задачи без доказательства корректности применяемых процедур и оптимальности получаемого результата. При этом
в качестве существенного фактора рассматриваются вычислительные
затраты. Метаэвристические методы объединяют в себе один или более
эвристических методов (процедур), опирающихся на стратегию поиска
более высокого уровня (отсюда – ɦɟɬɚ). Они способны покидать окрестности локальных экстремумов и выполнять достаточно полное исследование множества допустимых решений. 
Хотя классификация метаэвристических методов в настоящее время
носит условный характер, поскольку характерные группы методов базируются на сходных идеях, и имеется устойчивая тенденция к созданию
гибридных алгоритмов, авторами выделены четыре группы методов: 
эволюционные методы; методы, имитирующие физические процессы; 
мультистартовые методы, методы «роевого» интеллекта. 
К эволюционным методам относятся генетические алгоритмы; методы, имитирующие иммунные системы организмов; методы рассеивания; 
методы эволюционного преобразования ковариационной матрицы; ме3

тоды динамических сеток; методы дифференциальной эволюции; гибридные меметические алгоритмы. 
Ко второй группе метаэвристических методов, методов, имитирующих физические процессы, относятся метод гравитационной кинематики, адаптивный метод имитации отжига, метод поиска гармонии. 
К третьей группе метаэвристических методов – к мультистартовым
методам – относятся метод случайного поиска с последовательной редукцией области исследования, жадный адаптивный метод случайного
поиска и метод направленного табу-поиска. 
К четвертой группе методов – методам «роевого» интеллекта – относятся метод частиц в стае, метод муравьиных колоний, метод имитации
поведения бактерий, методы роя пчел и искусственных пчелиных колоний. Отметим, что методы гравитационной кинематики и поиска гармонии могут быть также отнесены к методам «роевого» интеллекта, поскольку в процессе поиска происходит обмен информацией между решениями на текущей итерации. 
Авторами
было
сформировано
алгоритмическое
и программное
обеспечение перечисленных метаэвристических методов глобальной оптимизации. Его эффективность проверена при решении задач поиска
глобального экстремума для типовых функций, имеющих сложный
рельеф поверхностей уровня [27, 54, 79, 94, 101, 116, 148]. Поэтому они
были выбраны в качестве инструмента для приближенного решения задач поиска оптимального управления динамическими системами. 
Эволюционные методы поиска (Evolutionary Methods) имитируют
процессы природного развития популяции особей – эволюции. В основе
эволюционных методов лежат принципы, заимствованные из биологии
и генетики. Основная идея эволюционных методов состоит в создании
популяции особей (индивидов, клеток). В задаче оптимизации каждая
особь соответствует одному из возможных решений. Для поиска наилучшего решения используется значение целевой функции или связанной с ней функции приспособленности. Значение функции приспособленности показывает, насколько хорошо подходит особь в качестве решения задачи. Для обеспечения процесса эволюционного поиска к текущей популяции применяются основные генетические операции (селекция, скрещивание, мутация, клонирование), в результате которых генерируется новая популяция при помощи добавления новых особей с лучшими значениями функции приспособленности и удаления старых. 
Подобно другим метаэвристическим методам, эволюционные методы не гарантируют обнаружения глобального решения, но они успешно
работают, когда требуется найти достаточно хорошее решение за приемлемое время. 
Генетические алгоритмы (Genetic Algorithms) являются представителями эволюционных методов поиска. Основные принципы работы генетических алгоритмов (ГА) изложены в [3, 6, 80, 94, 115, 122, 149, 171]. 
В ГА создается популяция особей, каждая из которых представляется
в виде хромосомы. В задаче оптимизации множество допустимых решений кодируется так, чтобы каждая хромосома соответствовала одному
4

из возможных решений. Хромосома состоит из конечного числа генов, 
представляя генотип объекта. Поиск экстремума ведется на уровне генотипов. 
Генетические алгоритмы делятся на две группы: генетические алгоритмы с бинарным кодированием и генетические алгоритмы с вещественным кодированием. 
Первая группа использует двоичный алфавит для кодирования либо
точек, либо элементарных «площадок» на множестве допустимых решений (иногда применяется смешанное кодирование). Высокая эффективность отыскания глобального экстремума с помощью генетического алгоритма с бинарным кодированием обоснована теоремой о шаблоне
[122], в которой доказано, что двоичный алфавит позволяет обрабатывать максимальное количество информации по сравнению с другими
методами кодирования. Однако двоичное представление хромосом влечет за собой трудности при поиске экстремума в непрерывных пространствах, поскольку дискретизация множества допустимых решений
приводит к потере точности. Описание различных генетических алгоритмов и соответствующих программных продуктов можно найти в [3, 
27, 28, 36, 49, 54, 73, 86, 146]. 
Вторая группа возникла в результате отказа от идеи кодирования. 
В таком случае решение в хромосоме представляется в виде набора вещественных чисел. При этом реализация генетических операторов изменяется, а операции кодирования и декодирования отсутствуют. Генетические алгоритмы с вещественным кодированием были предложены
в [171] и интенсивно развиваются [14, 27, 28, 35, 49, 51, 52, 54, 86, 119, 
146]. 
К эволюционным методам относятся методы, имитирующие иммунные системы организмов, – методы искусственных иммунных систем
(Artificial Immune Systems), опирающиеся на идеи из иммунологии. Основные принципы работы методов искусственных иммунных систем
(ИИС) изложены в [9, 22, 48, 50, 80, 82–84, 128]. 
В методах ИИС создается популяция иммунных клеток, которая
в течение работы метода имитирует борьбу иммунной системы организма с чужеродными телами. В результате этой борьбы, подобно естественным природным процессам, искусственная иммунная система запоминает способы борьбы с чужеродными телами в клетках памяти и приобретает новые свойства. При этом система совершенствуется, повышая
эффективность своей работы. 
Особенностью работы методов ИИС является тщательное исследование множества допустимых решений. Методы находят не только глобальные экстремумы функций, но также и локальные. Модифицированный метод ИИС при исследовании множества допустимых решений сочетает в себе глобальный и локальный поиски, что позволяет ему эффективно справляться с поставленной задачей. 
Еще одним представителем эволюционных методов является метод
рассеивания (Scatter Search). Основные принципы работы метода рассеивания изложены в [27, 54, 99, 113, 114]. Свое название метод полу5

чил из-за способа создания базового множества особей, которое формируется таким образом, чтобы особи в нем были достаточно отличны
друг от друга, т.е. хорошо «рассеяны» по множеству допустимых решений. Данное множество используется для формирования начальной популяции и пополнения новых популяций в течение работы метода. Таким образом, обеспечивается тщательное исследование множества допустимых решений и эффективное использование вычислительных ресурсов метода. У метода рассеивания существует несколько модификаций, комбинирующих его с локальными методами поиска – линейным
поиском, табу-поиском, методом деформируемого многогранника (Нелдера-Мида) [45]. 
Метод эволюционного преобразования ковариационной матрицы
(Covariance Matrix Adaptation Evolution Strategy, CMA-ES) был предложен в [117]. Основные принципы работы данного метода изложены
в [54, 116, 123]. Свое название метод получил благодаря способу, которым формируются новые популяции. Формирование происходит при
помощи нормального распределения случайного вектора. При этом при
переходе от одной популяции к другой происходит преобразование ковариационной матрицы распределения. Также производится постоянное
изменение параметров метода в течение его работы. Изменение элементов ковариационной матрицы и параметров метода реализуется таким
образом, чтобы обеспечить наиболее эффективную его работу на каждой итерации. Изначально CMA-ES разрабатывался как локальный метод поиска, поэтому его можно использовать в качестве улучшающего
решение метода в комбинации с другими методами поиска. Однако
CMA-ES и его модификации справляются и с задачами поиска глобального экстремума. 
В методе динамических сеток (Variable Мesh Оptimization), предложенном в [160], популяция представляется в виде некоторой сетки, 
состоящей из набора решений, называемых узлами. В процессе поиска
сетка подвергается изменениям: расширению (добавлению новых узлов
в сетку) и сокращению (удалению узлов, расположенных слишком близко друг к другу). Метод имитирует эволюцию начальной популяции
и представляет собой итерационный процесс. Во время работы метода
на каждой итерации происходит расширение (локальное, глобальное
и дополнительное) и последующее сокращение сетки. Таким образом, 
формируется новая сетка. Критерием окончания поиска является достижение заранее заданного количества вычислений целевой функции. 
В качестве приближенного решения задачи из последней популяции выбирается узел, которому соответствует наилучшее значение целевой
функции. 
Метод дифференциальной эволюции (Differential Evolution) [85, 
105, 159] относится к классу методов, в которых переход от одной популяции к другой происходит посредством искусственной эволюции. 
Использование различий (differences) между индивидами (значениями аргумента целевой функции) с помощью линейного оператора, названного дифференциацией, привело к появлению нового класса методов, различные модификации которого нашли широкое применение
6

при решении разнообразных прикладных задач [40, 42, 54]. Сначала на
множестве допустимых решений генерируется конечный набор векторов, называемый начальной популяцией. Как правило, для этого используется равномерное распределение. Для формирования новой
популяции проводится заданное число испытаний. При этом последовательно выбирается каждый элемент текущей популяции (он называется вектором-мишенью) и принимается решение, остается ли он
в новой популяции или нет путем сравнения с вектором-образцом, 
полученным в результате скрещивания и мутации. Если вектор-образец лучше по соответствующей величине целевой функции, чем вектор-мишень, то он его заменяет в популяции. Циклический процесс
замены текущей популяции новой заканчивается, когда количество
сформированных популяций оказывается равным заданному максимальному числу популяций. 
Меметический алгоритм (Memetic Algorithm), как правило, реализует идеи взаимодействия эволюционного или другого подхода, основанного на понятии популяции, и индивидуального обучения особей либо другой локальной процедуры улучшения решения для задач поиска
глобального оптимума. Теория «универсального дарвинизма» была разработана в [93]. Эта теория полагает, что понятие эволюции применимо
не только к биологическим системам, но и к любой сложной системе, 
которой присущи принципы наследования, изменения и селекции, т.е. 
все принципы развития. Таким образом, наука меметика представляет
собой аналог генетики в развитии культуры. Термин «мем» был определен как «единица передачи культурной информации, распространяемая
от одной особи к другой посредством имитации, научения и др.» [10]. 
Термин «меметический алгоритм» (МА) был впервые предложен
П. Москато (P. Moscato) в [150], где он рассматривал МА как гибрид генетического алгоритма и процедуры индивидуального обучения для
уточнения решения задачи. На этапе индивидуального обучения решение (особь или её генотип) заменяется новым (обученным) решением
в случае, если новое решение имеет большую приспособленность, независимо от остальной части популяции. Таким образом, происходит так
называемое культурное развитие особи, которое затем передаётся её потомкам в течение последующих поколений [151]. 
Одной из главных трудностей, возникающих при проектировании
алгоритма, сочетающего популяционный и локальный поиск, является
соблюдение баланса между ними. Можно говорить об этом как о более
общей проблеме соблюдения баланса между экстенсивным и интенсивным исследованиями пространства поиска. Кроме того, следует учитывать тот факт, что при большом числе особей даже простая процедура
локального поиска может занять непозволительно много времени. Разные исследователи по-разному оценивали важность локального поиска
и объём времени, который ему нужно уделять. В целом не существует
универсальных рекомендаций на этот счет. В данный момент МА также
называют гибридными эволюционными алгоритмами, эволюционными
алгоритмами Болдуина (Baldwinian Evolutionary Algorithms), эволюционными алгоритмами Ламарка (Lamarckian Evolutionary Algorithms), 
7

культурными алгоритмами или генетическими алгоритмами локального
поиска. 
Метод имитации отжига (Simulated Annealing) и его модификации основаны на анализе процесса замерзания жидкостей или рекристаллизации металлов в процессе отжига. Кроме классического алгоритма, предложенного в работе [135], существуют также его модификации, позволяющие ускорить сходимость [75, 124–127]. Применяемая стратегия поиска, основанная на использовании распределений
Больцмана и Гиббса, позволяет проскочить локальные минимумы оптимизируемой функции и попасть в область притяжения глобального
минимума. Попадание в эту область происходит с определенной вероятностью, поэтому метод имитации отжига не гарантирует нахождения глобального минимума функции. Однако при правильной политике выбора траектории изменения «температуры» (параметра метода) 
происходит не только улучшение начального приближения, но и существенное приближение к глобальному экстремуму. Как правило, необходимая эвристическая политика реализуется за счет выбора удачного
начального приближения, высокого значения начальной «температуры» и постепенного ее снижения. Все алгоритмы имитации отжига
с некоторой вероятностью допускают переход в состояние с более высоким значением целевой функции в процессе поиска решения для того, чтобы точка могла покинуть окрестность локального минимума. 
Однако для обеспечения этого свойства в обычном методе отжига требуется снижать «температуру» очень медленно, что значительно увеличивает время счета. В адаптивном методе имитации отжига
(Adaptive Simulated Annealing) отмеченный недостаток устраняется за
счет ввода нового закона уменьшения температуры и возможности ее
изменения по каждой координате отдельно с учетом специфики влияния каждого параметра в конкретной задаче оптимизации. Также одним из отличий адаптивного метода имитации отжига от обычного метода и большинства других его модификаций является возможность
использования в задачах условной оптимизации, что существенно расширяет область применения методов имитации отжига.
Исторически первым и довольно долгое время единственным широко используемым методом поиска глобального экстремума являлся
метод, названный впоследствии мультистарт. Этот метод состоит
в многократном отыскании локальных минимумов и различных начальных точек. Для повышения эффективности мультистарта используются исключение повторных спусков в те же локальные минимумы, 
обеспечение выхода траектории спуска из «неглубоких ям» и генерирование перспективных начальных точек. Также находят применение
идеи кластеризации поисковых точек для определения уже найденных
локальных минимумов. Для обеспечения выхода из «неглубоких ям» 
спускающейся точке приписывают инерцию, т.е. модифицируют целевую функцию для достижения туннельного эффекта с целью перехода из текущего в более глубокий минимум.
Основная сложность при практической реализации метода мультистарта состоит в следующем. Для того чтобы с высокой надежно8

стью отыскать точку глобального минимума, необходимо взять количество начальных точек для локальных алгоритмов существенно большее, чем число локальных минимумов функции (которое к тому же
обычно неизвестно). Но при этом большая часть вычислительных затрат будет связана с нахождением точек локальных минимумов, найденных ранее. Для преодоления указанной сложности мультистарт
обычно модифицируют одним из двух следующих способов.
Первый способ состоит в том, что найденные точки локальных минимумов окружаются некоторыми окрестностями, и попадание других точек в эти окрестности считается равносильным попаданию
в точки локальных минимумов.
Второй способ, иногда называемый методом конкурирующих точек, заключается в том, что поиск локальных минимумов производится одновременно (параллельно), причем точки, расстояние между
которыми мало (не превышает некоторого фиксированного, достаточно малого числа), объединяются, т.е. заменяются одной из них – той, 
значение целевой функции в которой лучше. Проблема объединения
точек является задачей кластерного анализа.
В данной книге описаны три мультистартовых метода: метод случайного поиска с последовательной редукцией области поиска [142], 
жадный адаптивный метод случайного поиска [120] и метод направленного табу-поиска [99, 112, 118]. 
Метод случайного поиска с последовательной редукцией области
исследования (метод Luus-Jaakola) использует идею переменной области поиска новых решений, которая в процессе работы метода подвергается редукции (сокращению) и восстановлению (расширению). При
применении данного метода строится последовательность итераций из
заданной начальной точки так, что в некоторой окрестности текущей
точки с использованием равномерного распределения генерируется определенное количество случайных точек с учетом размеров множества
допустимых решений. Среди полученных точек выбирается наилучшая, 
и из нее процесс продолжается. При этом размер множества поиска сокращается от итерации к итерации вплоть до достижения их заданного
числа. Как только заданное число итераций выполнено, завершается
проход. При переходе к следующему проходу размер множества поиска
восстанавливается, а далее снова выполняется заданное число итераций. 
На каждой итерации размеры исследуемой области сокращаются, что
позволяет обеспечить сходимость последовательности полученных таким образом приближенных решений к искомой точке глобального экстремума. 
Жадный
адаптивный
метод
случайного
поиска
(Greedy 
Randomized Adaptive Search Procedure) использует идею мультистарта, 
т.е. многократного поиска решения, где каждая итерация включает
в себя две фазы: фазу конструирования и фазу локального поиска. 
Наилучшее из найденных решений принимается за приближенное решение поставленной задачи. В результате первой фазы (фазы конструирования) порождаются решения хорошего качества, из которых начинается вторая фаза – локального поиска. Затем полученные точки
9

берутся в качестве начальных для первой фазы, и процедура продолжается.
Метод направленного табу-поиска (TabuSearch) включает в себя
три фазы: исследовательскую, перераспределительную и интенсивно-уточняющую. На исследовательской фазе происходит генерация
новых точек вблизи текущего решения. Используемая концепция памяти при этом позволяет избежать циклических попаданий в ранее посещенные области. Один из инструментов памяти – лист посещенных
областей – является элементом перераспределительной фазы, служащей для организации поиска в непосещенных областях исследуемого
пространства. Предполагается, что одна из лучших точек, найденных
на исследовательско-перераспределительной фазе, близка к глобальному экстремуму. Поэтому на фазе интенсивного уточнения найденные хорошие точки улучшаются с целью получения результата с заданной точностью.
Метод частиц в стае (Particle Swarm Optimization Strategy), предложенный в работах [100, 134], имитирует некоторые свойства живой
природы и позволяет отыскать приемлемое с точки зрения практики
решение, может быть, несколько отличающееся от оптимального. 
Основная идея метода частиц в стае состоит в моделировании поведения стаи животных при поиске пищи. Каждый член стаи рассматривается как частица в многомерном пространстве, которая имеет положение и скорость (она появляется в процессе движения). Каждая частица
изменяет свое положение, запоминая наилучшее, которому соответствовало наилучшее значение целевой функции. Члены стаи сообщают
информацию о хороших позициях друг другу и используют ее для корректировки своего положения и скорости на каждой итерации. Также
учитываются найденные ранее позиции. Процедура поиска заканчивается при достижении максимального числа итераций. В качестве
приближенного решения выбирается наилучшее среди всех членов
стаи.
При реализации метода частиц в стае используются следующие основные принципы, взятые из природы: для достижения цели используется множество особей (частиц); каждая особь получает информацию о передвижении соседей; движение по направлению к цели происходит путем подражания действиям соседа; учитывается информация о цели (величина целевой функции), получаемая через органы
чувств (например, запах пищи); используется собственный прошлый
опыт. При этом моделируются тенденции живого организма повторять
успешное в прошлом поведение, особенно в случае локальной неудачи; 
подражать успеху остальных; двигаться за лидером, выбираемым среди
соседей.
Метод муравьиных колоний (Ant Сolony Optimization) также относится к методам «роевого» интеллекта [102, 163], которые в связи
со своей эффективностью приобретают все большую популярность. 
Метод был разработан М. Дориго (M. Dorigo) для дискретных множеств допустимых решений и применялся для решения комбинаторных задач [96]. В [97] была предложена модификация метода муравьи10