Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,441

МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА И ИНТЕРПРЕТАЦИЯ ВАРИАНТА ЗАДАЧИ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ НА ТЕМПОРАЛЬНОМ ГРАФЕ

Мохов В.А. 1 Туровский Ф.А. 1 Туровская Е.В. 1
1 Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова
В работе показана тенденция роста размерности оптимизационных задач, решаемых на современном этапе развития технологий. Выполнен анализ ряда задач. Задачи для анализа выбраны на основании опубликованных результатов исследований из различных предметных областей. Последние объективно указывают на актуальную востребованность: а) в создании оптимальных траекторий космических перелётов с использованием гравитационного маневра; б) эффективной организации перевозок товаров с ограниченным сроком годности; в) быстрой маршрутизации в распределённых программно-конфигурируемых сетях; г) качественном планировании траекторий индивидуального обучения с учётом эффекта забывания и некоторых других. Рассмотрена общая постановка для перечисленных задач. На конкретных примерах представлены варианты формализации описания. Разработана математическая модель единообразного представления постановки рассмотренных задач. Проанализированы ограничения. Выполнена интерпретация полученной математической постановки задачи в терминах теории графов для ряда случаев. Показано обоснование для последующего решения группы рассмотренных задач на основе алгоритмов агентных метаэвристик.
дискретная оптимизация
теория графов
динамические задачи дискретной оптимизации
агентные метаэвристики
1. Дутова И.Г., Мохов В.А., Кузнецова А.В., Есаулов В.А. Метаоптимизация роя частиц на основе метода дробного исчисления // Современные проблемы науки и образования. – 2015. – № 2–1; URL: http://www.science-education.ru/ru/article/view id=20817 (дата обращения: 16.01.2016).
2. Иванченко А.Н., Ван Нгон Нгуен Имитационное моделирование процесса освоения модульной образовательной программы // Известия высших учебных заведений. Северо-Кавказский регион // Технические науки. – 2015. – № 3. – С. 28–33.
3. Кубил В.Н., Мохов В.А. К вопросу о применении роевого интеллекта в решении задач транспортной логистики // Проблемы модернизации инженерного образования в России: сб. науч. статей по проблемам высшей школы / Юж.-Рос. гос. политехн. ун-т (НПИ)/ – Новочеркасск: ЮРГПУ(НПИ), 2014. – С. 140–144.
4. Кубил В.Н., Мохов В.А. Применение муравьиного алгоритма в задачах многокритериальной оптимизации с изменяющимися условиями // Информационно-телекоммуникационные системы и технологии: материалы Всерос., науч.-практ. конф. (Кемерово, 16–17 окт. 2015 г.). – Кемерово, 2015. – С. 80–81.
5. Мохов В.А. Разработка алгоритмов прямого синтеза аппроксимирующих искусственных нейронных сетей: диссертация на соискание ученой степени кандидата технических наук: 05.13.11: защищена 20.10.2005: утв. 10.02.2006. – Ростов-на-Дону, 2005. – 179 с.
6. Мохов В.А., Сильнягин Н.Н. Интегрированный алгоритм когнитивной оценки и выбора оптимального варианта онтологической модели // Инженерный вестник Дона. – 2011. – Т. 18, № 4. – С. 351–356.
7. Мохов В.А., Туровский Ф.А. К вопросу о единообразии постановки некоторых задач дискретной оптимизации // Современный научный вестник. – 2015. – Т. 9, № 1. – С. 41–45.
8. Мохов В.А.; Туровская Е.В., Туровский Ф.А. Анализ бинарного алгоритма летучих мышей при решении задач дискретной оптимизации // Новая наука: от идеи к результату: Междунар. науч. период. издание по итогам Междунар. науч.-практ. конф., 29 декабря 2015 г.: в 3 ч. / Агентство международных исследований – Стерлитамак: РИЦ АМИ, 2015. – Ч. 3. – С. 101–103.
9. Соловьева О.И., Соловьева Е.А. Создание социально-ориентированной системы управления качеством транспортных услуг // Транспортное дело России. – 2010. – № 12. – С. 200–203.
10. Тарасов В.Н., Ушаков Ю.А., Коннов А.Л. Канальная коммутация в программно-конфигурируемых сетях // Новые информационные технологии и системы: тр. XМеждунар. науч.-техн. конф. (Пенза, 27–29 ноября 2012 г.). – Пенза: Изд-во ПГУ, 2012. – С. 104–109.
11. Туровская Е.В., Мохов В.А., Кузнецова А.В. Моделирование процесса оптимального размещения товаров на складе самообслуживания на основе эволюционных алгоритмов поиска // Инженерный вестник дона. – 2014. – Т. 28. – № 1. – С. 56.
12. Logsdon T. Orbital mechanics: theory and applications. – John Wiley & Sons, 1998. – 268 с.
13. Lones M. Sean Luke: essentials of metaheuristics // Genetic Programming and Evolvable Machines. – 2011. – Т. 12. – № 3. – С. 333–334.
14. Minisci E.A., Avanzini G. Orbit transfer manoeuvres as a test benchmark for comparison metrics of evolutionary algorithms // Evolutionary Computation, 2009. CEC’09. IEEE Congress on. – IEEE, 2009. – С. 350–357.
15. Vasile M., Zuiani F. Multi-agent collaborative search: an agent-based memetic multi-objective optimization algorithm applied to space trajectory design // Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering. – 2011. – Т. 225. – № 11. – С. 1211–1227.

В последние десятилетия серьёзный импульс развития получило научное направление, связанное с разработкой, исследованием и применением стохастических поисковых алгоритмов оптимизации [5, 3], которые также называют популяционными алгоритмами (или агентными метаэвристиками) [1].

Данные метаэвристики нашли широкое применение в решении оптимизационных задач, общая постановка которых предполагает нахождение допустимого множества решений [7]:

mohov01.wmf (1)

где D – является гиперкубом; x* – искомое оптимальное решение; f* – значение целевой функции; f – вектор-функция, представленная следующим образом:

mohov02.wmf

f:D > Rm; f(x) = [f1(x), f2(x), …, fm(x)]T.

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

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

Материалы и методы исследования

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

1. Создание траекторий космических перелётов с использованием гравитационного маневра [12, 13].

2. Организация перевозок товаров с ограниченным сроком годности [9].

3. Маршрутизация в распределённых программно-конфигурируемых сетях для динамической миграции виртуальных ресурсов [10].

4. Планирование траекторий индивидуального обучения с учётом эффекта забывания [2].

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

Результаты исследования и их обсуждение

Выполним указанную выше постановку на примере задачи № 1 и далее распространим её описание на остальные. Идеи первой из рассматриваемых задач нашли отражение в фильме «PlanetAnt: Life Inside the Colony – BBC» (Andrew Stephenson, 2012), и впоследствии, с использованием ряда допущений, были заимствованы из работ Максимилиано Василе (Massimiliano Vasile) [17] и Эдмондо Миниски (Edmondo Minisci) [14].

Рассмотрим процесс прокладки маршрута между двумя удалёнными планетами p0 и pn в космическом пространстве. Примем во внимание, что для получения дополнительного разгона (и сокращения издержек по расходу топлива) за счёт известного «эффекта пращи» [2, 8] полёт космического аппарата проходит мимо n – 1 промежуточных (движущихся) планет с целью выполнения около них соответствующих гравитационных маневров. Полёт будет проходить на протяжении T (T ≤ n) временных интервалов (каждый из которых соответствует перелёту между двумя планетами pj и pj+1). Абстрагируясь от деталей, будем считать, что переменными являются усреднённые значения собственной скорости космического аппарата mohov03.wmf на интервале t и скорости, полученной дополнительно mohov04.wmf в начале этого периода. Также предположим, что для каждого временного интервала t = 1, 2, …, T известно неотрицательное значение снижения скорости xt (рис. 1).

pic_62.tif

Рис. 1. Характеристики временного интервала t

В соответствии с техническими требованиями, в каждом периоде собственная скорость космического аппарата должна быть не менее mohov05.wmf и не более mohov06.wmf единиц измерения, а интервал возможного изменения дополнительной скорости располагается соответственно между mohov07.wmf и mohov08.wmf. Логично предположить, что эти параметры неотрицательны (скорость должна быть достаточно велика, чтобы не возымел эффект падения космического аппарата на одну из планет). Ради простоты будем считать, что в начале межпланетного перелёта собственная скорость задана положительной константой из интервала mohov09.wmf, а первый импульс дополнительной скорости можно получить, только начиная с маневра около планеты p1 (т.е. в начале 2-го периода). Также предположим, что известны некоторые вогнутые функции mohov10.wmf и mohov11.wmf, первая из которых определяет длительность времени межпланетного перелёта в периоде t (или длину траектории от pj до pj+1), а вторая – средний объём расхода топлива в единицу времени (или на единицу расстояния) в зависимости от mohov12.wmf. Важно отметить, что указанные функции имеют соответствующие ограничения mohov13.wmf и mohov14.wmf снизу и mohov15.wmf и mohov16.wmf сверху на области допустимых значений.

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

Предположим, что цель описанного процесса состоит в получении такого межпланетного маршрута G(p), который удовлетворял бы всем ограничениям и минимизировал суммарные затраты при реализации данного перелёта. На рис. 2 показан пример маршрута G(p) = {p0, p3, p4, p7} в двумерном пространстве с тремя интервалами (T = 3) для исходной задачи с семью планетами (n = 7), где пунктиром показаны возможные варианты маршрутов между планетами p0 и p7, сплошной линией – проложенный маршрут между планетами.

pic_63.tif

Рис. 2. Пример маршрута G(p) = {p0, p3, p4, p7}

Подобную ситуацию описывает постановка задачи:

mohov17.wmf

mohov18.wmf

mohov19.wmf

mohov20.wmf

t = 1, 2, …, T; mohov21.wmf mohov22.wmf (2)

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

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

Предполагается, что процесс работы компании организован следующим образом. Водительский экипаж каждого автомобиля направляется в командировку, состоящую из T временных интервалов, в которой каждый из интервалов t = 1, 2, …, T соответствует одному перегону между городами pj и pj+1 из известного множества городов P = {p0, …, pn}. В городе pj необходимо заправиться и приобрести товар для доставки в город pj+1, где, в свою очередь, необходимо продать этот товар, дозаправить автомобиль, приобрести очередную партию товара для доставки в следующий город и т.д.

Как уже было отмечено, для каждого экипажа необходимо сформировать маршрут на основе принципа «свободного работника», т.е. с минимальными издержками (а следовательно – с максимальной финансовой выгодой). В этой задаче переменными являются сумма денег mohov23.wmf, которая имеется у экипажа для приобретения бензина и закупки товара на интервале t, и объём прибыли mohov24.wmf, полученной от перевозки товара на этом же интервале. Будем считать, что товар приобретается из некоторого заранее определённого перечня товаров (обладающих достаточно высокой рентабельностью для выполнения перевозок). Поэтому каждый товар при перевозке позволяет получить некоторый объём прибыли из диапазона от mohov25.wmf до mohov26.wmf валютных единиц. Также, из соображений безопасности, имеются ограничения на объём возимых денежных средств, сумма которых варьируется в интервале от mohov27.wmf до mohov28.wmf. Помимо этого, для каждого временного интервала t известно неотрицательное значение текущих издержек xt в денежном эквиваленте (средства, выделяемые на питание, проживание экипажа и др.).

Очевидно, что в начале командировки сумма затрат на заправку автомобиля и закупку первой партии товара будет определена некоторой положительной константой из интервала mohov29.wmf, а первая прибыль будет получена лишь в городе p1 (т.е. в начале 2-го периода). Функции mohov30.wmf и mohov31.wmf определяют соответственно время, затрачиваемое на доставку товара (например, в зависимости от состояния дорожного покрытия) из города pj в город pj+1 в периоде t, и размер финансовых потерь при перевозке партии товара (из-за его порчи или ухудшения свойств). Как и в задаче № 1, указанные функции имеют соответствующие ограничения mohov32.wmf и mohov33.wmf снизу и mohov34.wmf и mohov35.wmf сверху на области допустимых значений.

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

Заключение

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


Библиографическая ссылка

Мохов В.А., Туровский Ф.А., Туровская Е.В. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА И ИНТЕРПРЕТАЦИЯ ВАРИАНТА ЗАДАЧИ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ НА ТЕМПОРАЛЬНОМ ГРАФЕ // Фундаментальные исследования. – 2016. – № 9-2. – С. 279-283;
URL: http://www.fundamental-research.ru/ru/article/view?id=40735 (дата обращения: 28.09.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074