Все выпуски

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

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

В настоящей работе проводится систематическое исследование применения сверточных нейронных сетей (CNN) в качестве эффективного инструмента для анализа критических и низкотемпературных фазовых состояний в моделях двумерных спиновых систем. Рассматривается задача расчета зависимости средней энергии $\langle E\rangle_T^{}$ от пространственного распределения обменных интегралов $J_k^{}$ для модели Эдвардса – Андерсона на квадратной решетке с фрустрированными взаимодействиями. Реализуется единый сверточный классификатор фазовых состояний ферромагнитной модели Изинга на квадратной, треугольной, гексагональной решетках и кагоме-решетке, обученный на конфигурациях, сгенерированных кластерным алгоритмом Свендсена – Ванга. Температурные профили усредненной апостериорной вероятности высокотемпературной фазы, вычисленные этим классификатором, образуют четкие S-образные кривые с пересечением вблизи теоретических критических температур и позволяют установить значение $T_c^{}$ для решетки кагоме без дополнительного дообучения. Показано, что сверточные модели позволяют существенно снизить среднеквадратичную ошибку (RMSE) по сравнению с полносвязными архитектурами и эффективно улавливают сложные связи между термодинамическими характеристиками и структурой магнитных коррелированных систем.

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

В настоящей работе предложена математическая модель двухэшелонной маршрутизации транспортных средств (2E-VRP), адаптированная к условиям вывозки лесоматериалов в макрорегионе Урала и Сибири. Модель учитывает переменные транспортные затраты (пробег лесовозов), фиксированные затраты на задействование каждой единицы техники ($c_{fix}$ = 30 000 руб./рейс) и ограничения грузоподъемности. Задача приведена к форме QUBO — квадратичной безусловной бинарной оптимизации; емкостные ограничения интегрированы посредством штрафного коэффициента $\lambda_{cap} = 500$. Такое представление обеспечивает совместимость модели с современными специализированными решателями (квантовыми отжигателями и цифровыми аннилерами).

Апробация модели выполнена на реальной географии Уральского и Сибирского федеральных округов: 207 узлов логистической сети, 65 предприятий-потребителей, 8 магистральных транспортных узлов. Предложенный трехстадийный алгоритм «Допустимость прежде всего» формирует допустимый маршрутный план за 1,7 с и обеспечивает снижение суммарных транспортных затрат на 69% относительно базового генетического алгоритма. Последующая оптимизация методом имитации отжига дополнительно улучшает значение целевой функции QUBO на 55%.

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

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

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

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

В статье рассматривается разработка алгоритма шумоподавления на основе анизотропной нелинейной фильтрации данных. Анализ отечественной и зарубежной литературы показал, что наиболее эффективные алгоритмы шумоподавления данных рентгеновской компьютерной томографии применяют комплекс нелинейных методик анализа и обработки данных, таких как билатеральная, адаптивная, трехмерная фильтрации. Однако комбинация таких методик редко применяется на практике ввиду большого времени обработки данных. В связи с этим было принято решение разработать эффективный и быстродейственный алгоритм шумоподавления на основе упрощенных билатеральных фильтров с трехмерным накоплением данных. Алгоритм был разработан на языке C++11 в программной среде Microsoft Visual Studio 2015. Основным отличием разработанного алгоритма шумоподавления является применение в нем улучшенной математической модели шума на основе распределения Пуассона и Гаусса от логарифмической величины, разработанной ранее. Это позволило точнее определить уровень шума и тем самым порог обработки данных. В результате работы алгоритма шумоподавления были получены обработанные данные компьютерной томографии с пониженным уровнем шума. При визуальной оценке работы алгоритма были отмечены повышенная информативность обработанных данных по сравнению с оригиналом, четкость отображения гомогенных областей и значительное сокращение шума в областях обработки. При оценке численных результатов обработки было выявлено снижение уровня среднеквадратичного отклонения более чем в 6 раз в областях, подвергшихся шумоподавлению, а высокие показатели коэффициента детерминации показали, что данные не подверглись искажению и изменились только из-за удаления шумов. Применение разработанного универсального динамического порога, принцип работы которого основан на пороговых критериях, позволил снизить уровень шума во всем массиве данных более чем в 6 раз. Динамический порог хорошо вписывается как в разработанный алгоритм шумоподавления на основе анизотропной нелинейной фильтрации, так и другой алгоритм шумоподавления. Алгоритм успешно функционирует в составе рабочей станции MultiVox, получил высокую оценку своей работы от специалистов-рентгенологов, а также готовится к внедрению в единую радиологическую сеть города Москвы в качестве модуля.

В данной работе рассматривается задача восстановления матрицы корреспонденций для наблюдений реальных корреспонденций в г. Москве. Следуя общепринятому подходу [Гасников и др., 2013], транспортная сеть рассматривается как ориентированный граф, дуги которого соответствуют участкам дороги, а вершины графа — районы, из которых выезжают / в которые въезжают участники движения. Число жителей города считается постоянным. Задача восстановления матрицы корреспонденций состоит в расчете всех корреспонденций израйона $i$ в район $j$.

Для восстановления матрицы предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийная модель. В работе, в соответствии с работой [Вильсон, 1978], приводится описание эволюционного обоснования энтропийной модели, описывается основная идея перехода к решению задачи энтропийно-линейного программирования (ЭЛП) при расчете матрицы корреспонденций. Для решения полученной задачи ЭЛП предлагается перейти к двойственной задаче и решать задачу относительно двойственных переменных. В работе описывается несколько численных методов оптимизации для решения данной задачи: алгоритм Синхорна и ускоренный алгоритм Синхорна. Далее приводятся численные эксперименты для следующих вариантов функций затрат: линейная функция затрат и сумма степенной и логарифмической функции затрат. В данных функциях затраты представляют из себя некоторую комбинацию среднего времени в пути и расстояния между районами, которая зависит от параметров. Для каждого набора параметров функции затрат рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Мы предполагаем, что шум в восстановленной матрице корреспонденций является гауссовским, в результате в качестве метрики качества выступает среднеквадратичное отклонение. Данная задача представляет из себя задачу невыпуклой оптимизации. В статье приводится обзор безградиенных методов оптимизации для решения невыпуклых задач. Так как число параметров функции затрат небольшое, для определения оптимальных параметров функции затрат было выбрано использовать метод перебора по сетке значений. Таким образом, для каждого набора параметров рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Далее по минимальному значению невязки для каждой функции затрат определяется, для какой функции затрат и при каких значениях параметров восстановленная матрица наилучшим образом описывает реальные корреспонденции.