Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

MATHEMATICAL FORMULATION AND INTERPRETATION FOR VARIANT OF THE PROBLEM OF DISCRETE OPTIMIZATION ON TEMPORAL GRAPH

Mokhov V.A. 1 Turovskiy F.A. 1 Turovskaya E.V. 1
1 Platov South-Russian State Polytechnic University (NPI)
The tendency of growth of dimension of the optimizing tasks solved at the present stage of development of technologies is shown in article. The analysis of a number of tasks is made. Tasks for the analysis are chosen on basis of the published results of researches from various subject domains. The last objectively point to an actual demand in a) creation of optimum trajectories of space flights with use of gravitational maneuver; b) the effective organization of transportations of goods with a limited expiration date; c) fast routing in the configured networks distributed program; d) high-quality planning of trajectories of individual learning with effect of forgetting and some other. The general formulation for the listed tasks is considered. On concrete examples of formalization of the description are presented. The mathematical model of uniform representation of formulation of the considered tasks is developed. Restrictions are analysed. Interpretation of the received mathematical problem definition in terms of the theory of counts for a number of cases is executed. Justification for the subsequent decision of group of the considered tasks on basis of algorithms of agent-based metaheuristicsis shown.
discrete optimization
graph theory
dynamic problems of discrete optimization
agent-based metaheuristics
1. Dutova I.G., Mohov V.A., Kuznecova A.V., Esaulov V.A. Metaoptimizacija roja chastic na osnove metoda drobnogo ischislenija // Sovremennye problemy nauki i obrazovanija. 2015. no. 2–1; URL: http://www.science-education.ru/ru/article/view id=20817 (data obrashhenija: 16.01.2016).
2. Ivanchenko A.N., Van Ngon Nguen Imitacionnoe modelirovanie processa osvoenija modulnoj obrazovatelnoj programmy // Izvestija vysshih uchebnyh zavedenij. Severo-Kavkazskij region // Tehnicheskie nauki. 2015. no. 3. рр. 28–33.
3. Kubil V.N., Mohov V.A. K voprosu o primenenii roevogo intellekta v reshenii zadach transportnoj logistiki // Problemy modernizacii inzhenernogo obrazovanija v Rossii: sb. nauch. statej po problemam vysshej shkoly / Juzh.-Ros. gos. politehn. un-t (NPI)/ Novocherkassk: JuRGPU(NPI), 2014. рр. 140–144.
4. Kubil V.N., Mohov V.A. Primenenie muravinogo algoritma v zadachah mnogokriterialnoj optimizacii s izmenjajushhimisja uslovijami // Informacionno-telekommunikacionnye sistemy i tehnologii: materialy Vseros., nauch.-prakt. konf. (Kemerovo, 16–17 okt. 2015 g.). Kemerovo, 2015. рр. 80–81.
5. Mohov V.A. Razrabotka algoritmov prjamogo sinteza approksimirujushhih iskusstvennyh nejronnyh setej: dissertacija na soiskanie uchenoj stepeni kandidata tehnicheskih nauk: 05.13.11: zashhishhena 20.10.2005: utv. 10.02.2006. Rostov-na-Donu, 2005. 179 р.
6. Mohov V.A., Silnjagin N.N. Integrirovannyj algoritm kognitivnoj ocenki i vybora optimalnogo varianta ontologicheskoj modeli // Inzhenernyj vestnik Dona. 2011. T. 18, no. 4. рр. 351–356.
7. Mohov V.A., Turovskij F.A. K voprosu o edinoobrazii postanovki nekotoryh zadach diskretnoj optimizacii // Sovremennyj nauchnyj vestnik. 2015. T. 9, no. 1. рр. 41–45.
8. Mohov V.A.; Turovskaja E.V., Turovskij F.A. Analiz binarnogo algoritma letuchih myshej pri reshenii zadach diskretnoj optimizacii // Novaja nauka: ot idei k rezultatu: Mezhdunar. nauch. period. izdanie po itogam Mezhdunar. nauch.-prakt. konf., 29 dekabrja 2015 g.: v 3 ch. / Agentstvo mezhdunarodnyh issledovanij Sterlitamak: RIC AMI, 2015. Ch. 3. рр. 101–103.
9. Soloveva O.I., Soloveva E.A. Sozdanie socialno-orientirovannoj sistemy upravlenija kachestvom transportnyh uslug // Transportnoe delo Rossii. 2010. no. 12. рр. 200–203.
10. Tarasov V.N., Ushakov Ju.A., Konnov A.L. Kanalnaja kommutacija v programmno-konfiguriruemyh setjah // Novye informacionnye tehnologii i sistemy: tr. XMezhdunar. nauch.-tehn. konf. (Penza, 27–29 nojabrja 2012 g.). Penza: Izd-vo PGU, 2012. рр. 104–109.
11. Turovskaja E.V., Mohov V.A., Kuznecova A.V. Modelirovanie processa optimalnogo razmeshhenija tovarov na sklade samoobsluzhivanija na osnove jevoljucionnyh algoritmov poiska // Inzhenernyj vestnik dona. 2014. T. 28. no. 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. T. 12. no. 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. CEC09. 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. T. 225. no. 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].