ГлавнаяОптимизацияМетаэвристические методы оптимизации

Гальченко В.Я., Якимов А.Н. Популяционные метаэвристические алгоритмы оптимизации роем частиц. Метаэвристические методы оптимизации


algorithm - Подходы к оптимизации (метаэвристический, основанный на графике, MILP)

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

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

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

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

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

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

qaru.site

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

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

авторы: Бенза Н. Н., профессор, д.ф.-м.н. Карпенко А. П.

УДК 519.6

Россия, МГТУ им. Н.Э. Баумана

[email protected]

[email protected]

 

Введение

В последние годы интенсивно развивается новый класс стохастических поисковых методов оптимизации, которые называют по-разному: поведенческие, интеллектуальные, метаэвристические методы, методы вдохновленные (инспирированные) природой, роевые, многоагентные, популяционные методы. Используем последний термин как, на наш взгляд, наиболее точно передающий суть этих методов. Обзор большого числа популяционных методов (populationmethods), предназначенных для решения задачи глобальной непрерывной оптимизации, представлен в работе [1].

В настоящее время наиболее развитыми являются следующие популяционные методы оптимизации, вдохновленные живой природой ‑ методы роя частиц, муравьиной колонии, пчелиного роя. Достаточно широко известны также такие методы данного класса, как иммунный, бактериальный, светлячковый, сорняковый, обезьяний, прыгающих лягушек, летучих мышей, косяка рыб, растущих деревьев, мух, биогеографии [1, 2]. К этому же классу относится рассматриваемый в работе метод кукушки (CuckooSearch, CS).

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

Метод кукушки предложен и разработан Янгом (Xin-SheYang) и Дебом (Suash Deb) в 2009 году [3]. На создание метода авторов вдохновило поведение кукушек в процессе вынужденного гнездового паразитизма, когда некоторые виды кукушек подкладывают яйца в гнезда птиц других видов.

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

Для повышения эффективности CS-метода предложено несколько модификаций канонического варианта этого метода [4, 5]. Кроме того, известны модификации CS-метода на основе его гибридизации с другими метаэвристическими методами. Например, в работе [6] предложена гибридизация CS-метода с методом роя частиц. Расширение CS-метода для решения задачи многокритериальной оптимизации рассмотрено в работе [7].

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

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

 

1 Постановка задачи и схема канонического метода кукушки

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

,                                       (1)

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

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

CS-метод основан на трех следующих правилах.

Схема канонического CS-метода имеет следующий вид.

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

2) Выполняем случайные перемещения кукушки в пространстве поиска с помощью полетов Леви (Lévy Flights) [3] и находим ее новое положение .

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

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

5) Если условие окончания итераций не выполнено, то переходим к шагу 2.

При создании нового решения  полеты Левиосуществляем по формуле

.                                            (2)

Здесь  – -мерный вектор независимых вещественных случайных чисел, распределенных по закону Леви

, ;                                         (3)

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

Заметим, что большинство популяционных алгоритмов глобальной оптимизации используют миграционный оператор вида (2), но равномерное

www.technomag.bmstu.ru

Гальченко В.Я., Якимов А.Н. Популяционные метаэвристические алгоритмы оптимизации роем частиц [PDF]

Гальченко В.Я., Якимов А.Н. Популяционные метаэвристические алгоритмы оптимизации роем частиц: Учебное пособие / В.Я. Гальченко, А.Н. Якимов – Черкассы: ФЛП Третяков А. Н., 2015. – 160 с., ил.

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

ОГЛАВЛЕНИЕВВЕДЕНИЕ 1. АЛГОРИТМЫ НЕПРЕРЫВНОЙ ОПТИМИЗАЦИИ РОЕМ ЧАСТИЦ 1.1. Бионические предпосылки 1.2. Описание канонического алгоритма непрерывной оптимизации. 1.3. Выбор топологии связей роя частиц 1.4. Верификация алгоритмов оптимизации роем частиц. 1.4.1. Тестовые функции для проверки эффективности оптимизационных алгоритмов. 1.4.2. Тестирование алгоритма PSO с типовыми топологиями связей. 2. МОДИФИКАЦИИ КЛАССИЧЕСКОГО АЛГОРИТМА PSO 2.1. Метод полностью информированного роя (FIPS) 2.2. Метод роя частиц, основанный на отношении «значение-расстояние» 2.3. Метод роя частиц с дополнением графа соседних частиц. 2.4. Адаптивный PSO (APSO). 2.4.1. Адаптация значения инерционного коэффициента. 2.4.2. Адаптация размера роя частиц 2.5. Коэволюционный PSO. 2.6. Сравнение эффективности вариантов алгоритма PSO для задач непрерывной оптимизации 3. АЛГОРИТМЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ РОЕМ ЧАСТИЦ3.1. Дискретный алгоритм PSO. 3.2. Комбинаторный вариант алгоритма PSO 4. ГИБРИДНЫЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ РОЕМ ЧАСТИЦ 4.1. Меметический гибридный алгоритм оптимизации роем частиц с локальным поиском методом Нелдера-Мида 4.2. Гибридный алгоритм оптимизации роем частиц с эволюционным формированием состава роя 4.3. Гибридный алгоритм оптимизации роем частиц и методом моделирования перемещения бактерий 4.4. Гибридный алгоритм оптимизации роем частиц и методом клеточных автоматов 4.5. Гиперэвристический алгоритм оптимизации роем частиц 5. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИИ РОЕМ ЧАСТИЦ 5.1. Алгоритм роевой многокритериальной оптимизации. 5.2. Алгоритм PSO для поиска Парето-оптимального решения 5.3. Верификация гибридного алгоритма PSO поиска оптимального решения из множества Парето. ЗАКЛЮЧЕНИЕ СПИСОК ЛИТЕРАТУРЫ

www.twirpx.com

Метаэвристический • ru.knowledgr.com

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

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

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

Свойства и классификация

Это свойства, которые характеризуют большую часть метаэвристики:

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

Один подход должен характеризовать тип стратегии поиска. Один тип стратегии поиска - улучшение на простых алгоритмах локального поиска; метаэвристика этого типа включает моделируемый отжиг, запрещает поиск, повторенный локальный поиск, переменный поиск района и СХВАТЫВАНИЕ. У другого типа стратегии поиска есть компонент изучения к поиску; метаэвристика этого типа включает оптимизацию колонии муравьев, эволюционное вычисление и генетические алгоритмы.

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

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

Заявления

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

предположенный, что именно Фред Гловер выдумал метаэвристику слова

Вклады

Многие различная метаэвристика существующая и новые варианты, все время предлагаются. Некоторые самые значительные вклады в область:

См. также

Внешние ссылки

ru.knowledgr.com

Книга "Методы глобальной оптимизации: Метаэвристические стратегии и алгоритмы" (Пантелеев Андрей Владимирович) из жанра Научная, учебная литература для специалистов

Методы глобальной оптимизации: Метаэвристические стратегии и алгоритмы

Автор: Пантелеев Андрей Владимирович Жанр: Научная, учебная литература для специалистов Год: 2013 Количество страниц: 244 Формат:  PDF (12.20 МБ) Дата загрузки: 28 июля 20142016-02-26 Скачать
Поделись с друзьями!
 

Аннотация

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

Комментарии

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

literu.ru

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

Выдержка из работы

УДК 519. 85 + 517. 977. 58 ББК 22. 18 + 22. 19РАЗРАБОТКА ИНТЕРВАЛЬНЫХ МЕТАЭВРИСТИЧЕСКИХ МЕТОДОВ МИНИМИЗАЦИИ ДЛЯ ПОИСКА ОПТИМАЛЬНОГО ПРОГРАММНОГО УПРАВЛЕНИЯ1Пантелеев А. В. 2, Пановский В. Н. 3(Московский авиационный институт, Москва)Разработаны алгоритмическое и программное обеспечение метаэвристических интервальных методов глобальной условной оптимизации (усредненных концов путей, стохастической сетки, разбросанного поиска) и методика их применения для решения задачи поиска оптимального программного управления нелинейными детерминированными системами. Приведено решение прикладной задачи трехмерного сближения с маневрирующим объектом, проведен сравнительный анализ эффективности.Ключевые слова: интервальные методы, метаэвристические методы, глобальная условная оптимизация, оптимальное управление.1. ВведениеВ современной математике достаточно большое внимание уделяется решению задач глобальной оптимизации, которые возникают, например, в ходе выбора наилучших параметров конструкций самолетов, вертолетов, космических аппаратов1 Исследование выполнено при финансовой поддержке РФФИ в рамках научных проектов № 16−31−115 мола, № 16−07−419 А.2 Андрей Владимирович Пантелеев, доктор физико-математических наук, профессор (avpanteleev@inbox. ru).3 Валентин Николаевич Пановский, аспирант (panovskiy. v@yandex. ru).(веса, дальности полета, аэродинамических характеристик). Существующие численные методы используют разнообразные подходы, но их использование связано с большими вычислительными затратами, излишними требованиями к постановке задачи, трудностями в достижении сходимости метода [9, 12].В статье предлагаются новые методы поиска глобального условного экстремума функций многих переменных, использующие аппарат интервального анализа [8, 10, 11, 13]. Существующие интервальные методы оптимизации можно разделить на методы безусловной оптимизации (алгоритмы Мура-Скелбоу, Ичиды-Фуджи, Дюсселя, интервальный алгоритм «имитации отжига», метод случайного интервального дробления и др. [15−17]) и условной оптимизации (методы Хансена, Мура и др.[11, 14]).Предлагаемые интервальные методы глобальной условной оптимизации относятся к классу метаэвристических методов. Метаэвристическим алгоритмом называют алгоритм, не имеющий строгого обоснования, но, тем не менее, позволяющий найти приемлемое решение задачи в большинстве практически значимых случаев. Он не гарантирует нахождения лучшего решения, не гарантирует нахождения решения, даже если оно существует («проскакивание решения»). Однако существенным достоинством таких алгоритмов является их низкая вычислительная сложность, что позволяет их применять для решения задач повышенной трудности, не накладывая существенных ограничений на элементы постановок задач (дифференцируе-мость, выпуклость, ограниченность и т. д.). При этом необходимые и достаточные условия экстремума [4] в алгоритмах не используются. Метаэвристические методы объединяют в себе один или несколько эвристических методов (процедур), опирающихся на стратегию более высокого уровня.Существующие численные методы поиска оптимального управления включают в себя достаточно большое количество методов, которые используют принцип максимума Понтрягина и уравнение Беллмана, а также прямые методы, например, градиентные методы (методы первого порядка), методы второго порядка, основывающиеся на тейлоровской аппроксимациифункции Кротова-Беллмана, разнооборазные методы улучшения и др. [1, 7]Несмотря на большое количество проведенных исследований, проблема численного решения нелинейных задач оптимального управления остается актуальной и требующей разработки новых подходов, к которым относится применение интервального анализа совместно с метаэвристическими стратегиями [2−6]. Предлагаемые в статье методы дают возможность нахождения глобального экстремума критерия оптимальности для достаточного широкого класса задач.2. Используемые понятия и обозначенияОсновной идеей интервального анализа является окружение вещественных чисел интервалами, а вещественных векторов -интервальными векторами, или параллелотопами [10]. Для обозначения интервала используются строчные латинские буквы, заключенные в квадратные скобки ([о], [Ь], [с],…) или привычное представление ([ог- о"], [Ьг- Ь"], [с- с"], …), где указывается нижняя и верхняя границы. Для задания параллелотопа применяется то же обозначение с полужирным начертаниембукв ([х] = [Х1] x … x [ХП]).Для произвольного интервала [х] определены: нижняя граница/й ([х]) = [х] = зир^ е № и {-оо, оо} | УС е [х]: & lt- С}, верхняя границаиЪ ([х]) = [х] = М {?, е М11 {-оо, оо} | УС, е [х]: С, & lt-, ширина непустого интервала & lt-«([ х]) = [ х]-[х],средняя точка ограниченного и непустого интервала [х ]+[х ]т1ё ([ х]):2Те же параметры определены и для параллелотопов. Нижняя, верхняя границы и средняя точка становятся векторами,ширина же рассчитывается как максимум из ширин всех образующих параллелотоп компонентов.Интервальной оболочкой множества X с К& quot- называется параллелотоп с наименьшей шириной, который содержит X. Если множество берется в квадратные скобки, это значит, что рассматривается интервальная оболочка этого множества.Пусть о — некоторая бинарная операция, тогда [х] о [у] = [{^о2 | ^е[х], ^2е[у]}]. Пусть /- некоторый унарный оператор, тогда/([х]) = [{Д?) | ?е[х]}]. Описанная бинарная операция позволяет определить арифметические операции над интервалами [10].Множество интервалов обозначается как Ж, интервальных векторов — Ж& quot-. Пусть имеется некоторая функция/^ действующая из К& quot- в К. Функция [/](•) называется интервальной функцией включения для /, действующей из Ж& quot- в Ж, если {Д?)|?, е [х]} с [/]([х]), /[х]еШ& quot-. Функция включения позволяет получить априорную оценку множества значений функции, даже если оно не является выпуклым или связным (если вместо переменных используются интервалы и соответствующие арифметические операции, то полученная оценка называется оценкой прямого образа функции).3. Постановка интервальной задачи е-минимизацииКлассическая постановка задачи условной оптимизации имеет вид: пусть имеются параллелотоп [в], задающий множество допустимых решений, и целевая функция /: К& quot- -& gt- Ж. Требуется найти точку х* такую что[8]: / (/)& lt- / (х).Приведем интервальный аналог поставленной задачи: пусть имеются параллелотоп [в], задающий множество допустимых решений, целевая функция /: К& quot- -& gt-Ж, малое число? & gt- 0. Требуется найти параллелотоп [р]*, такой что(2) [р]* ^ ["], ш ([Р]*) & lt- е,*[х] е [¦], ш ([х]) & gt- е,[/]([х]) & lt- [/]([р]*).4. Стратегии интервальных метаэвристических методов глобальной условной оптимизации4.1. МЕТОД УСРЕДНЕННЫХ КОНЦОВ ПУТЕЙВ основе метода лежат следующие процедуры:• построение случайной сетки на области поиска (представляет собой разбиение целевого параллелотопа [8] на множество{[п] непересекающихся параллелотопов, таких чтоNМ = и Ю-?=1• выбор случайного параллелотопа из сетки-• поиск пути (последовательности параллелотопов, в которой каждый следующий параллелотоп имеет общую гиперплоскость с предыдущим) до «оптимального» решения по сетке-• полученный в ходе выполнения описанных процедур «перспективный» параллелотоп запоминается.Процедуры повторяются несколько раз. Из полученных параллелотопов берутся их средние точки, на основе которых строится новый целевой параллелотоп (он рассматривается как усредненный из «перспективных» параллелотопов, являющихся концами последовательностей, полученных в результате поиска, начинающегося с некоторого параллелотопа, принадлежащего построенной сетке), к которому снова применяется метод. Так повторяется до тех пор, пока ширина целевого параллелотопа не будет удовлетворять условию точности.4.2. МЕТОД СТОХАСТИЧЕСКОЙ СЕТКИСтратегия данного метода заключается в построении на целевом параллелотопе сетки (множества непересекающихся параллелотопов, объединение которых дает искомый целевой параллелотоп) случайным образом. Далее для некоторых элементов сетки ищется оценка прямого образа функции, выбирается наиболее «перспективный» параллелотоп (с наименьшимзначением нижней грани оценки прямого образа). Такая процедура повторяется несколько раз. Средние точки выбранных параллелотопов определяют новый параллелотоп, к которому снова применяется алгоритм. Так повторяется до тех пор, пока ширина целевого параллелотопа не будет удовлетворять условию точности.4.3. МЕТОД ИНТЕРВАЛЬНОГО РАЗБРОСАННОГО ПОИСКАВ основе точечного метода разбросанного поиска (scatter search) лежит обработка множества элементарных исходов, состоящих из найденных на предыдущем этапе «перспективных» решений. Фактически обработка заключается в комбинации, улучшении и обновлении множества элементарных исходов. В основе интервального метода лежат пять методов: метод генерации разнообразных решений, методы конструирования и обновления множества элементарных исходов, метод генерации подмножеств, метод комбинации решений, метод улучшения решений.Процедура повторяется до тех пор, пока ширина целевого параллелотопа не будет удовлетворять условию точности.5. Алгоритмы интервальных метаэвристических методов глобальной условной оптимизации5.1. МЕТОД УСРЕДНЕННЫХ КОНЦОВ ПУТЕЙШаг 1. Задать [s] - область поиска- е — параметр точности (отвечает за ширину итогового параллелотопа) — w — «скорость» уменьшения параллелотопа- pamount — количество точек для построения случайной сетки- pattempts — количество повторений- rmax — максимальное количество возвращений (используется во время поиска пути до «оптимального» решения). Положить целевой параллелотоп [t] = [s].Шаг 2. Если «([t]) & lt- е, то закончить работу алгоритма, вернув параллелотоп [t]. В противном случае положить множество концов путей (последний элемент в последовательности параллелотопов, представляющей путь) E = 0 и перейти к шагу 3.Шаг 3. Случайным образом, используя равномерный закон распределения, выбрать в целевом параллелотопе рошоим точек.Шаг 4. Разбить целевой параллелотоп относительно выбранных на шаге 3 точек на множество параллелотопов (так как любой параллелотоп является п-мерным параллелепипедом (п — размерность задачи), то разбиение можно делать следующим образом: в каждой точке строятся п гиперплоскостей, каждая из которых параллельна одной паре сторон данного параллелепипеда- совокупность этих гиперплоскостей порождает сетку на параллелотопе).Шаг 5. Из полученной сетки выбрать случайный параллелотоп [р].Шаг 6. Процедура поиска пути от параллелотопа [р] к «оптимальному» параллелотопу (путь — последовательность параллелотопов ] I™!, таких, что все параллелотопы ^]г+1,1 = 1, …, ш — 1, граничат, т. е. имеют общую гиперплоскость):Шаг 6.1. Из параллелотопов сетки сформировать множество параллелотопов М = ([п] }-=1, граничащих с параллелотопом [р]. Поместить в список параллелотопов, образующих путь, начальный элемент (Р = {[р]}) и задать количество возвращенийШаг 6.2. Если г & lt- Гшох, то перейти к шагу 6.3. В противном случае перейти к шагу 6.6.Шаг 6.3. Выбрать случайный параллелотоп [п] еЖ, удалить его из N. Еслито перейти к шагу 6.4. В противном случае перейти к шагу 6.5.Шаг 6.4. Если [п] еР, то положить г = г + 1 и перейти к шагу 6.2. В противном случае добавить [п] в Р. Положить [р] = [п] и вернуться к шагу 6.1.Шаг 6.5. Если NФ 0, то перейти к шагу 6. 3, в противном случае перейти к шагу 6.6.Шаг 6.6. Параллелотоп [р] добавить в множество концов путей Е. Переход к шагу 7.г = 0.Шаг 7. Если в множестве E содержится pattempts элементов, то перейти к шагу 8. В противном случае перейти к шагу 3. Шаг 8. Найти вектор1 Pattempts..— ^ midi [e] J, где [e], е E.m = --г attempts i=1Заменить параллелотоп [t] на параллелотопУУ J УУ Jm---wid, m н---wid1 2 1 2x… xwwm"---wid, m» н---widn 2 2n[t]=где wid = «([t]). Перейти к шагу 2.5.2. МЕТОД СТОХАСТИЧЕСКОЙ СЕТКИШаг 1. Задать [8] - область поиска- е — параметр точности (отвечает за ширину итогового параллелотопа) — w — «скорость» уменьшения параллелотопа- pamount — количество гиперплоскостей для построения случайной сетки- pattempts — количество повторений- panalyze — количество анализируемых параллелотопов. Положить целевой параллелотоп [1] = [8].Шаг 2. Если «([1]) & lt- е, то закончить работу алгоритма, вернув параллелотоп [1]. В противном случае положить множество выбранных параллелотопов E = 0 и перейти к шагу 3.Шаг 3. Случайным образом, используя равномерный закон распределения, выбрать в целевом параллелотопе pamount точек.Шаг 4. Разбить целевой параллелотоп относительно выбранных на шаге 3 точек на множество параллелотопов В = {[Ь]-}'-=1. Так как любой параллелотоп является «-мернымпараллелепипедом («- размерность задачи), то разбиение можно реализовать следующим образом: в каждой точке строится гиперплоскость, параллельная одной (случайно выбранной) паре сторон данного параллелепипеда- совокупность этих гиперплоскостей порождает разбиение исходного параллелотопа. В полученном множестве следует удалять случайно выбранные параллелотопы до тех пор, пока количество элементов не станет равным panalyze. В результате получится стохастическая сетка.Шаг 5. Из полученной сетки выбрать параллелотоп[p]= Arg min [f ]([b]-)и добавить его в множество E.Шаг 6. Если в множестве E содержится pattempts элементов, то перейти к шагу 7. В противном случае перейти к шагу 3. Шаг 7. Найти вектор1 Pattemptsm =- ^ mid ([e]), где [e], е Е.Pattempts i=1Заменить параллелотоп [t] на параллелотопw wm---wid, m л---wid1 2 1 2:… xw wm"---wid, m л---widn 2 2n[t],где wid = «([t]). Перейти к шагу 2.5.3. МЕТОД ИНТЕРВАЛЬНОГО РАЗБРОСАННОГО ПОИСКАШаг 1. Задать [s] - область поиска- е — параметр точности (отвечает за ширину итогового параллелотопа) — rgm, rmc, rcs, rim е (0−1) — доли для генерации- psize, rssize, subsize — размеры множеств Р, RS, SUB соответственно- maxm — количество точек для улучшения- о — величину влияния ширины.Шаг 2. Метод генерации разнообразных решений. Сформировать множество P из psize параллелотопов [mi — «i- mi + «i] x … x [mi — «i- mi + «i] П [s], где величина Wk = 0,5 • rgm • w ([s]), mk — случайная точка на отрезке, соответствующем k-й компоненте параллелотопа [s]. Отсортировать множество P по возрастанию величины [ f ]([р]г-), где [р]геР.Шаг 3. Метод конструирования множества элементарных исходов. Сформировать множество RS из [rrsc • psize] (здесь [•] означает целую часть от числа) первых элементов множества Р. Выбранные элементы удалить из P. Создать множествоfsize I'-rsc г size JI пе^-ще ] / IО= X Ч^м)где йш ([о], [6]) — метрика Хаусдорфа [10], [г8]уeRS. Упорядочить множество О расстояний между параллелотопом [р], (оставшимся после удаления) и параллелотопами [г8] eRS по убыва-нию. В множество RS добавить (rssize — [rrsc ¦ psize]) параллелотопов из P, которым соответствуют первые (наибольшие) значения из D (добавляются наиболее удаленные параллелотопы от имеющихся в RS для поддержания разнообразия).Шаг 4. Отсортировать множество RS элементарных исходов по возрастанию величины [ f ]([rs]), где [rs]ieRS.Шаг 5. Если «([rs]1) & gt- е, то перейти к шагу 6. В противном случае закончить работу алгоритма, вернув параллелотоп [rs]1.Шаг 6. Метод генерации подмножеств. Создать множество SUB, состоящее из всех подмножеств размера subsize множества RS.Шаг 7. Создать множество комбинированных решенийCS = 0.Шаг 8. Метод комбинации решений. Для каждого подмножестваsubi = {[s]j е RS, j = 1,…, subslze }е SUBвыполнить: составить векторmw = I min aJ=1,…, subsize([si]j),…, j=A. a ([s-]j)),Su& amp-sizeсоздать параллелотоп |u |'- = [J |s, сгенерировать n случайныхj=iточек |pn e [u ] j. Построить n параллелотопов{[p — - p + ] X… X [pk — 0) n- pkn + a& gt-» ] П [u Jна сгенерированных точках, где cok = 0,5 • rcsmwlk, и добавить их в множество CS.Шаг 9. Создать множество улучшенных решений IS = 0. Шаг 10. Метод улучшения решений. Для каждого из параллелотопов [cs]- e CS сгенерировать случайным образом множество {pk = (p,…, pkn) T e[cs]}mXm точек. Выбрать точку p* = Arg min f (pn). Добавить в множество IS параллелотопk=l,…, max-«,+ ®1]х… х[/&gt-*-ю"-р1 +®"]П[с8]., где величинаШ] = 0,5 • Гт • «([с5-]г).Шаг 11. Метод обновления множества элементарных исходов. Для каждого параллелотопа ^в] eIS, если есть такое число для которого выполнено соотношение[ У ]([Ц)N У ](["] у) у),то вставить перед ]-м параллелотопом в множестве RS параллелотоп рз]г и последний элемент множества RS удалить. Шаг 12. Вернуться к шагу 5.6. Поиск оптимального программного управления непрерывными системами6.1. ПОСТАНОВКА ЗАДАЧИПоведение модели объекта управления описывается дифференциальным уравнением(3) ?(г) = /(г, х (г), ы (г)),где / - непрерывное время, / е 7 = | 1»: ! | - заданный промежуток времени функционирования системы- хеК& quot- - вектор состояния системы- и е [и] с К9 — вектор управления- [II] - множество допустимых значений управления, представляющее собой параллелотоп- Дг, х, и) = (/1((, х, и), … ,/п (г, х, ы))Т — непрерывная вектор-функция.Начальное состояние задано и равно(4) х (^) = х0.Конечное состояние х (^) должно удовлетворять условиям(5) Гг (х (^)) = 0, / = 1… 1,где 0 & lt- I & lt- п, функции Г (х) — непрерывно дифференцируемы- система векторов {ЭГг (х)/Эх1, …, ЭГг (х)/Эх"}, 7 = 1,… ,/, линейно независима VI е 1& quot-.При управлении используется информация только о времени г (применяется программное управление).Множество допустимых процессов ^(?0, Х0) определяется как множество пар й = (х (-), и (-)), включающих кусочно-дифференцируемую траекторию х () и кусочно-непрерывное управление и (^), где и (*)е[и]У* е Т, удовлетворяющих уравнению состояния (3), условиям (4) и (5).На множестве допустимых процессов определен функционал качества управления ч(6) I © = } /0 (*, X (*), и (*))С + ^ (X)) ,*0где /'-(г, х, и), Дх) — заданные непрерывные функции.Требуется найти пару й* = (х*(-), и* (•)) Х0), на которойдостигается минимальное значение функционала (6) на множестве допустимых процессов.6.2. СТРАТЕГИЯ ПОИСКА РЕШЕНИЯОсновным элементом предлагаемой стратегии является последовательное сведение поставленной задачи к соответствующей задаче нелинейного программирования, а затем — к задаче интервальной е-минимизации и решение последней с помощью разработанных интервальных методов.Для более простого вычисления интегрального члена в критерии (6) к системе (3) добавляется уравнение хй+1(0 = /°(г, х (г), м (г)) с начальным условием х"+1(^0) = 0, тогда значение функционала качества (6) определяется выражением 1 = Х"+! (*1) + ^(X ()).Для сведения к задаче со свободным правым концом траектории к терминальному члену функционала добавляются либо классические штрафные функции, характеризующие степень выполнения условий (5), либо их интервальный аналог вида(7) ([гг (х (*!))-Гг (х (*))],[Чг-]),г=1где^ ([а],[й]) = [шт (^ ([а],[й]),^ ([а],[й])), тах (^ ([а],[й]),([а],[*]))]— метрика Хаусдорфа-^ ([а],[Ь]) = ^{г | [а] ^ [Ь] + [-г-г], г & gt- 0}— мера близости интервалов- Я, — величины штрафов-& gt- 0 — величины допустимой погрешности выполнения конечного условия, которые задаются пользователем.Искомое субоптимальное программное управление предлагается искать в двух различных классах функций: кусочно -постоянных и кусочно-линейных.Поскольку ищется наилучшее управление в каждом из классов, не совпадающих с классом кусочно-непрерывных функций, то найденное управление является субоптимальным, рассматриваемым в качестве кандидата в решение задачи.Так как при решении задачи применяется интервальный подход, то каждому из описанных управлений сопоставляется интервальный аналог, задаваемый интервальным вектором:• кусочно-постоянное интервальное управление (рис. 1, а) — для управления такого типа необходимо задать значения функции и (0 в N моментах времени т = ^ + (?1 — ?о) •1 / N 1 = 0, …, N — 1, т. е. управлению можно однозначно сопоставить интервальный вектор [и] = [м1(г0)]х… х|д (г0^ х … хх [м1(^_1)]х… х[м9(г^_1)]- соответствующее интервальное управ'--V-'-ление будет находиться по формуле[и ](*)е[и (*,-)] = [» (*,¦)-и Ы], г,. &lt- * & lt-^+1, / = 0,…, N -1-• кусочно-линейное интервальное управление (рис. 1, б) — для управления такого типа необходимо задать дополнительное значение управления и (0 на последнем временном интервале, поэтому интервальный вектор, который ставится в соответствие управлению, имеет вид[и] = [,(го)]х., Ь (го)] х… х [»!(^)]х… х[и9(^)]- СООТВеТСТВу-^М] [МЫ]ющее интервальное управление будет находиться по формуле-[и (тт)] +{и (тм)], т, & lt- г & lt-тм, 1=0,…, N-1.б)Рис. 1. Замена кусочно-непрерывного управления интервальным кусочно-постоянным («а») и кусочно-линейным («б»)Интервальной траекторией называется решение уравнения (3) с начальным условием (4), соответствующее заданному интервальному управлению.Если система (3), описывающая поведение модели объекта управления, нежесткая, для ее численного интегрирования применяются явные методы (методы Эйлера, Эйлера-Коши, методы Рунге-Кутты различных порядков и др.). Если же система (3) жесткая, применяются неявные методы численного интегрирования (неявный метод Эйлера, метод трапеций, Адам-са-Моултона, Гира и др.). Вычисление правых частей системы (3) производится по правилам интервальной арифметики [10].Заметим, что описанные процедуры могут быть использованы при других способах параметризации управления, напри-мер, кусочно-полиномиальном или применении разложений по системам ортонормированных базисных функций7. Программное обеспечение. Решение прикладного примераНа основе изложенных алгоритмов сформирован комплекс программ поиска оптимального программного управления. Среда разработки — Microsoft Visual Studio, язык программирования — C#.В качестве примера рассмотрим решение задачи преследования в трехмерном пространстве, рассмотренной в [18].Поведение модели объекта управления описывается системой дифференциальных уравнений:х (() = Ух ((), Ух (() = их ((), х{(() = Ух (((), Ух ((() = их{((),(8) y (t)=Vy (t), vy (t)=uy 0t), y'- (t)=v- (t), v- (t)=" — (t),z (t) = Vz (t), Vz (t) = uz (t), e& lt- (t) = Vz (t), Vj (t) = и/ (t),где r = (x, y, z) T и r = (x*, y*, Z) T — радиус-векторы, описывающие положение перехватчика и цели соответственно- V = (Vx, Vy, VZ) T и V* = (Vj, Vy, VZ) T — векторы скоростей перехватчика и целисоответственно- u = (ux, Uy, uz) T и u* = (uj, uy, uz) T — векторыускорения перехватчика (управление) и цели соответственно.Пусть цель движется с постоянным ускорением: U = (-1, -2, 0,1)T м/с2, начальное положение цели: Г = (500, -600, 500) T м, скорость цели: V = (100, 100, 10) T м/с, начальное положение перехватчика: r = (0, 0, 0) T м, начальная скорость перехватчика: V = (150, 40, 5) T м/с.Время, за которое должен быть осуществлен перехват (координаты цели и перехватчика совпадают): t = 50 с.Тогда можно задать функционал качества управления:I = (X (*1) — х* (*1))2 + (y (*1) — y* (*1))2 + (z (*1) — z* (*1))2. Для сглаживания искомого интервального управления в функционал добавим слагаемоечМ = 0,001 • (и2 (t) + и2у (t) + и] (t))dt.оВ результате решается задача минимизации функционала I + AI.В качестве метода дискретизации были выбраны явная и неявная схемы Эйлера, область поиска[s] = [-2−2]x х[-2−2]ш(для кусочно-постоянного управления) и[s] = [-2−2]x… x[-2−2]4-V-'-3-(ЛГ+1)(для кусочно-линейного управления), N = 2.Параметры метода усредненных концов путей: s = 0,001-w 0,5- Pamount 75- Pattempts 5- rmax 5.Параметры метода стохастической сетки: s = 0,001- w = 0,9-Pamount = 100 — PattemPts = 100 — panalyze 1000.Параметры метода интервального разбросанного поиска: s = 0,001- rgm = 0,8- rrsc = 0,25- rCs = 0,9- ггт = 0,9- pslZe = 100- rssize = 10- subsize = 2- maxim = 1000- о = 2500.На рис. 3 и 4 приведены графики траекторий цели и перехватчика, полученные с помощью интервальных кусочно-постоянных и кусочно-линейных управлений. Их сравнение с рис. 2 показывает близость результатов с найденными при использовании алгоритма пропорциональной навигации [18].Рис. 2. График движения цели и перехватчика (при использовании алгоритма пропорциональной навигации [18])О 5 13 15 20 25 30 35 40 45 50 -1000 ОРис. 3. Графики движения цели и перехватчика, законов изменения управления, найденные методами усредненных концов путей, стохастической сетки и интервального разбросанного поиска (кусочно-постоянное управление)В таблице 1 и 3 приведены интервалы значений критерия оптимальности, найденные в результате применения соответствующего метода интервальной минимизации в каждом из двух рассматриваемых классов управлений.Таблица 1. Значение функционала качества управления (кусочно-постоянное управление)_Название метода Значение функционала качестваЯвная схема Эйлера Неявная схема ЭйлераМетод усредненных концов путей [0,0377- 0,0378] [0,0371- 0,0372]Метод стохастической сетки [0,0359- 0,0360] [0,0354- 0,0355]Метод интервального разбросанного поиска [0,0445- 0,0446] [0,0437- 0,0438]Таблица 2. Максимальные значения отклонения цели и перехватчика (кусочно-постоянное управление)Название метода Значение Ах- Ау- ДгЯвная схема Эйлера Неявная схема ЭйлераМетод усредненных концов путей 0,1040- 0,0501- 0,0401 0,1035- 0,4 993- 0,0409Метод стохастической сетки 0,0632- 0,0735- 0,0053 0,0631- 0,0733- 0,0051Метод интервального разбросанного поиска 0,0910- 0,0912- 0,0317 0,0908- 0,091- 0,0315В таблицах 2, 4 величины отклонений вычисляются какАх = max|x (/1) — X (/1)|, Ay = max |У (h)-У (tx)|, Az = max|z (^) -Z (4)|.Полученные данные о максимальных значениях отклонения являются приемлемыми с практической точки зрения и свидетельствуют об успешности применения разработанных алгоритмов. Наиболее точным оказался метод стохастической сетки, кусочно-линейное управление (таблица 3, 4) предпочтительнее по величине функционала, чем кусочно-постоянное (таблица 1, 2).а)б)в)Рис. 4. Графики движения цели и перехватчика, законов изменения управления, найденные методами усредненных концов путей, стохастической сетки и интервального разбросанного поиска (кусочно-линейное управление)Таблица 3. Значение функционала качества управления (кусочно-линейное управление)Название метода Значение функционала качестваЯвная схема Эйлера Неявная схема ЭйлераМетод усредненных концов путей [0,0347- 0,0348] [0,0343- 0,0344]Метод стохастической сетки [0,0341- 0,0341] [0,0340- 0,0341]Название метода Значение функционала качестваЯвная схема Эйлера Неявная схема ЭйлераМетод интервального разбросанного поиска [0,0345- 0,0346] [0,0339- 0,0340]Таблица 4. Максимальные значения отклонения цели и перехватчика (кусочно-линейное управление)_Название метода Значение Дх- Ду- ДzЯвная схема Эйлера Неявная схема ЭйлераМетод усредненных концов путей 0,0607- 0,0698- 0,0060 0,0609- 0,0697- 0,55Метод стохастической сетки 0,0636- 0,0431- 0,0353 0,0632- 0,043- 0,0035Метод интервального разбросанного поиска 0,0432- 0,0935- 0,0053 0,0431- 0,0932- 0,00518. ЗаключениеРазработаны алгоритмическое и программное обеспечение трех метаэвристических интервальных методов оптимизации: усредненных концов путей, стохастической сетки и разбросанного поиска. Поставлена задача интервальной е-оптимизации, к которой была сведена задача поиска оптимального программного управления нелинейными непрерывными детерминированными системами. Решена прикладная задача преследования в трехмерном пространстве. Анализ полученных результатов свидетельствует об эффективности предложенных методов.Литература1. ГУРМАН В.И., РАСИНА И.В., БЛИНОВ, А О. Эволюция и перспективы приближенных методов оптимального управления // Программные системы: теория и приложения. -2001. — № 2(6). — С. 11−29.2. ПАНОВСКИЙ В. Н. Прикладное применение интервального метода взрывов // Электронный журнал «Труды МАИ». -2014. — № 73. — [Электронный ресурс] - URL: http: //www. mai. ru/science/trudy/published. php? ID=48 451 (дата обращения: 19. 03. 2016.)3. ПАНОВСКИЙ В. Н. Применение аппарата интервального анализа для поиска глобального экстремума функций // Электронный журнал «Труды МАИ». — 2012. — № 51. -[Электронный ресурс] - URL: http: //www. mai. ru/ science/trudy/published. php? ID=28 948 (дата обращения: 19. 03. 2016.)4. ПАНТЕЛЕЕВ А. В. Вариационное исчисление в примерах и задачах.- М.: Высшая школа, 2006. — 272 с.5. ПАНТЕЛЕЕВ А.В., МЕТЛИЦКАЯ Д.В., АЛЕШИНА Е.А.Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы. — М.: Вузовская книга, 2013. -244 с.6. ПАНТЕЛЕЕВ А. В. Применение эволюционных методов глобальной оптимизации в задачах оптимального управления детерминированными системами. — М.: Изд-во МАИ, 2013. — 160 с.7. ФЕДОРЕНКО Р. П. Приближенное решение задач оптимального управления. — М.: Наука, 1978. — 488 с.8. ШАРЫЙ С. П. Конечномерный интервальный анализ. -Новосибирск: XYZ, 2010. — 606 с.9. FLOUDAS C.A., PARDALOS P.M. Encyclopedia of Optimization. — London: Springer, 2009. — 4626 p.10. JAULIN L., KIEFFER M., DIDRIT O., et al. Applied interval analysis. — London: Springer-Verlag, 2001. — 391 p.11. HANSEN E. Global optimization using interval analysis. — New York: Marcel Dekker, 2004. — 492 p.12. MICHALEWICZ Z., FOGEL D. How to solve it: Modern Heuristics. — London: Springer, 2004. — 554 p.13. MOORE R.E. Interval analysis. — Englewood Cliffs: Prentice Hall, 1966. — 145 p.14. MOORE R.E. Methods and applications of interval analysis. -Philadelphia: SIAM, 1979. — 152 p.15. RATSCHEK H., ROKNE J. New computer methods for global optimization. — Chichester: Horwood, 1988. — 236 p.16. SHARY S.P. A surprising approach in interval global optimization // Reliable Computing. — 2001. — P. 497−505.17. SHARY S.P. Randomized algorithms in interval global optimization // Numerical Analysis and Applications. — 2008. -Vol. 1. — P. 376−389.18. TEWARI A. Advanced control of aircraft, spacecraft and rockets. — New York: A John Wiley & amp- Sons, 2011. — 390 p.DEVELOPMENT OF METAHEURISTIC INTERVAL MINIMIZATION METHODS FOR THE OPTIMAL PROGRAM CONTROL SYNTHESISAndrei Panteleev, Moscow Aviation Institute, Moscow, Doctor of Science, professor (avpanteleev@inbox. ru).Valentin Panovskiy, Moscow Aviation Institute, Moscow, postgraduate student (panovskiy. v@yandex. ru).Abstract: We propose metaheuristic interval methods of global constrained optimization and their software implementation. Three methods are considered: average path ending, stochastic grid and interval scatter search. The methods are applied to the problem of optimal program control of nonlinear deterministic discrete and continuous systems. The solution of the applied problem of 3-dimensional interception and a brief comparative analysis of the effectiveness are given.Keywords: interval methods, metaheuristic, global constrained optimization, optimal control.Статья представлена к публикации членом редакционной коллегии П. С. Щербаковым.Поступила в редакцию 29. 10. 2015.Опубликована 31. 03. 2016.

Показать Свернуть

vpu7.lg.ua

Prostoy-Site | Все права защищены © 2018 | Карта сайта