ИССЛЕДОВАНИЕ НЕЙРОСЕТЕВОГО МЕТОДА РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (2023)
В статье исследован метод определения вектора движения по гиперплоскостям, ограничивающим допустимый многогранник многомерной задачи линейного программирования на основе визуальных образов, подаваемых на вход нейронной сети прямого распространения. Алгоритм визуализации строит в окрестности точки, расположенной на ограничивающей гиперплоскости, рецептивное поле. Для каждой точки рецептивного поля вычисляется скалярное смещение до поверхности гиперплоскости. На основании вычисленного смещения каждой точке рецептивного поля присваивается скалярная величина. Полученный визуальный образ подается на вход нейронной сети прямого распространения, которая вычисляет на ограничивающей гиперплоскости направление максимального увеличения целевой функции. В статье предложена усовершенствованная форма крестообразного рецептивного поля. Описано построение обучающего множества на основе случайно сгенерированных ограничивающих гиперплоскостей и целевых функций в многомерных пространствах. Разработана масштабируемая архитектура нейронной сети с изменяемым числом скрытых слоев. Произведен подбор гиперпараметров нейронной сети. В вычислительных экспериментах подтверждена высокая (более 98%) точность работы крестообразного рецептивного поля. Исследована зависимость точности результатов нейронной сети от числа скрытых слоев и продолжительности обучения.
Идентификаторы и классификаторы
- eLIBRARY ID
- 55079130
Одной из фундаментальных задач современной прикладной математики является задача линейного программирования (ЛП) с большим числом параметров [1]. Оптимизационные модели, основанные на многопараметрической (многомерной) задаче ЛП встречаются в системах поддержки принятия решений в экономике [2, 3], в системах управления беспилотными летательными аппаратами [4], в управлении технологическими процессами [5–7], при построении логистических цепочек [8–10], в оперативном управлении и планировании [11, 12].
До сих пор одним из наиболее распространенных способов решения задач ЛП был класс алгоритмов, разработанных на основе симплекс-метода [13]. Было установлено, что симплекс-метод эффективен для решения большого класса задач ЛП. В частности, симплекс-метод эффективно использует преимущества любой гиперразреженности в задачах ЛП [14]. Однако симплекс-метод обладает некоторыми фундаментальными особенностями, которые ограничивают его использование для решения больших задач ЛП. Вопервых, в определенных случаях симплекс-метод должен выполнять итерации по всем вершинам симплекса, что соответствует экспоненциальной временной сложности [15–17].
Список литературы
- Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных // Параллельные вычислительные технологии - XI международная конференция (ПаВТ’2017): Короткие статьи и описания плакатов, Казань, 3-7 апреля, 2017. Челябинск: Издательский центр ЮУрГУ, 2017. C. 471-484. URL: http://omega.sp.susu.ru/pavt2017/short/014.pdf. EDN: ZAPYPF
- Brogaard J., Hendershott T., Riordan R. High-Frequency Trading and Price Discovery // Review of Financial Studies. 2014. Vol. 27, no. 8. P. 2267-2306. DOI: 10.1093/rfs/hhu032
- Deng S., Huang X., Wang J., et al. A Decision Support System for Trading in Apple Futures Market Using Predictions Fusion // IEEE Access. 2021. Vol. 9. P. 1271-1285. DOI: 10.1109/ACCESS.2020.3047138
- Seregin G. Lecture Notes on Regularity Theory for the Navier-Stokes Equations. WORLD SCIENTIFIC, 2014. DOI: 10.1142/9314. EDN: YVDGVT
- Demin D. Synthesis of optimal control of technological processes based on a multialternative parametric description of the final state // Eastern-European Journal of Enterprise Technologies. 2017. Vol. 3, no. 4 (87). P. 51-63. DOI: 10.15587/1729-4061.2017.105294 EDN: YTUYGB
- Kazarinov L.S., Shnayder D.A., Kolesnikova O.V. Heat load control in steam boilers // 2017 International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM). IEEE, 2017. P. 1-4. DOI: 10.1109/ICIEAM.2017.8076177 EDN: XXYNBZ
- Zagoskina E., Barbasova T., Shnaider D. Intelligent Control System of Blast-furnace Melting Efficiency // 2019 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON). IEEE, 2019. P. 0710-0713. DOI: 10.1109/SIBIRCON48586.2019.8958221 EDN: OPASEG
- Fleming J., Yan X., Allison C., et al. Real-time predictive eco-driving assistance considering road geometry and long-range radar measurements // IET Intelligent Transport Systems. 2021. Vol. 15, no. 4. P. 573-583. DOI: 10.1049/itr2.12047
- Scholl M., Minnerup K., Reiter C., et al. optimization of a Thermal Management System for Battery Electric Vehicles // 2019 Fourteenth International Conference on Ecological Vehicles and Renewable Energies (EVER). IEEE, 2019. P. 1-10. DOI: 10.1109/EVER.2019.8813657
-
Meisel S. Dynamic Vehicle Routing // Anticipatory Optimization for Dynamic Decision Making. Vol. 51. New York, NY: Springer, 2011. P. 77-96. Operations Research/Computer Science Interfaces Series. DOI: 10.1007/978-1-4614-0505-4_6 -
Cheng A.M.K. Real-Time Scheduling and Schedulability Analysis // Real-Time Systems. Wiley, 2002. P. 41-85. DOI: 10.1002/0471224626.ch3 -
Kopetz H. Real-Time Scheduling // Real-Time Systems. Boston, MA: Springer, 2011. P. 239-258. Ral-Time Systems Series. DOI: 10.1007/978-1-4419-8237-7_10 -
Dantzig G.B. Linear programming and extensions. Princeton university press, 1998. 656 p. -
Hall J.A.J., McKinnon K.I.M. Hyper-Sparsity in the Revised Simplex Method and How to Exploit it // Computational Optimization and Applications. 2005. Vol. 32, no. 3. P. 259-283. DOI: 10.1007/s10589-005-4802-0 EDN: RPHXYV -
Klee V., Minty G.J. How good is the simplex algorithm? // Inequalities - III. Proceedings of the Third Symposium on Inequalities Held at the University of California, Los Angeles, Sept. 1-9, 1969 / ed. by O. Shisha. Academic Press, 1972. P. 159-175. -
Jeroslow R. The simplex algorithm with the pivot rule of maximizing criterion improvement // Discrete Mathematics. 1973. Vol. 4, no. 4. P. 367-377. DOI: 10.1016/0012-365X(73)90171-4 -
Zadeh N. A bad network problem for the simplex method and other minimum cost flow algorithms // Mathematical Programming. 1973. Vol. 5, no. 1. P. 255-266. DOI: 10.1007/BF01580132 EDN: THKEQW -
Bartels R.H., Stoer J., Zenger C. A Realization of the Simplex Method Based on Triangular Decompositions // Handbook for Automatic Computation. Berlin, Heidelberg: Springer Berlin Heidelberg, 1971. P. 152-190. DOI: 10.1007/978-3-642-86940-2_11 -
Tolla P. A Survey of Some Linear Programming Methods // Concepts of Combinatorial Optimization / ed. by V.T. Paschos. 2nd ed. Hoboken, NJ, USA: Wiley, 2014. P. 157-188. DOI: 10.1002/9781119005216.ch7 -
Hall J.A.J. Towards a practical parallelisation of the simplex method // Computational Management Science. 2010. Vol. 7, no. 2. P. 139-170. DOI: 10.1007/s10287-008-0080-5 EDN: UONZJG -
Mamalis B., Pantziou G. Advances in the Parallelization of the Simplex Method // Algorithms, Probability, Networks, and Games. Vol. 9295 / ed. by C. Zaroliagis, G. Pantziou, S. Kontogiannis. Springer, 2015. P. 281-307. Lecture Notes in Computer Science. DOI: 10.1007/978-3-319-24024-4_17 -
Lubin M., Hall J.A.J., Petra C.G., Anitescu M. Parallel distributed-memory simplex for large-scale stochastic LP problems // Computational Optimization and Applications. 2013. Vol. 55, no. 3. P. 571-596. DOI: 10.1007/s10589-013-9542-y EDN: BUQBDG -
Khachiyan L. Polynomial algorithms in linear programming // USSR Computational Mathematics and Mathematical Physics. 1980. Vol. 20, no. 1. P. 53-72. DOI: 10.1016/0041-5553(80)90061-0 -
Shor N.Z. Cut-off method with space extension in convex programming problems // Cybernetics. 1977. Vol. 13, no. 1. P. 94-96. DOI: 10.1007/BF01071394 EDN: GWUFQI -
Юдин Д.Б., Немировский А.С. Информационная сложность и эффективные методы решения выпуклых экстремальных задач // Экономика и математические методы. 1976. № 2. C. 357-369. EDN: ITHFKV -
Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. Vol. 4, no. 4. P. 373-395. DOI: 10.1007/BF02579150 EDN: PDNYHL -
Gondzio J. Interior point methods 25 years later // European Journal of Operational Research. 2012. Vol. 218, no. 3. P. 587-601. DOI: 10.1016/j.ejor.2011.09.017 -
Fathi-Hafshejani S., Mansouri H., Peyghami M.R., Chen S. Primal-dual interior-point method for linear optimization based on a kernel function with trigonometric growth term // Optimization. 2018. Vol. 67, no. 10. P. 1605-1630. DOI: 10.1080/02331934.2018.1482297 -
Asadi S., Mansouri H. A Mehrotra type predictor-corrector interior-point algorithm for linear programming // Numerical Algebra, Control & Optimization. 2019. Vol. 9, no. 2. P. 147-156. DOI: 10.3934/naco.2019011 -
Yuan Y. Implementation tricks of interior-point methods for large-scale linear programs // International Conference on Graphic and Image Processing (ICGIP 2011). Vol. 8285. International Society for Optics, Photonics, 2011. P. 828502. DOI: 10.1117/12.913019 -
Kheirfam B., Haghighi M. A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function // Optimization. 2016. Vol. 65, no. 4. P. 841-857. DOI: 10.1080/02331934.2015.1080255 -
Xu Y., Zhang L., Zhang J. A full-modified-Newton step infeasible interior-point algorithm for linear optimization // Journal of Industrial and Management Optimization. 2015. Vol. 12, no. 1. P. 103-116. DOI: 10.3934/jimo.2016.12.103 -
Roos C., Terlaky T., Vial J.-P. Interior Point Methods for Linear Optimization. SpringerVerlag, 2005. 500 p. DOI: 10.1007/b100325 EDN: SSXGWR -
Ольховский Н.А., Соколинский Л.Б. О новом методе линейного программирования // Вычислительные методы и программирование. 2023. Т. 24, № 4. C. 408-429. DOI: 10.26089/NumMet.v24r428 EDN: LWBDDB -
Соколинский Л.Б., Соколинская И.М. Об одном итерационном методе решения задач линейного программирования на кластерных вычислительных системах // Вычислительные методы и программирование. 2020. Т. 21, № 3. C. 329-340. 10. 26089 / NUMMET.V21R328. DOI: 10.26089/NUMMET.V21R328 EDN: VMVCEB -
Ольховский Н.А., Соколинский Л.Б. Визуальное представление многомерных задач линейного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2022. Т. 11, № 1. C. 31-56. DOI: 10.14529/cmse220103 EDN: VFXZOJ -
Соколинский Л.Б., Соколинская И.М. О новой версии апекс-метода для решения задач линейного программирования // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2023. Т. 12, № 2. C. 5-46. DOI: 10.14529/cmse230201 EDN: QKTRMC -
Biewald L. Experiment Tracking with Weights and Biases // Software available from wandb.com. 2020. January. -
Goodfellow I., Bengio Y., Courville A. Deep Learning (Adaptive Computation and Machine Learning). Vol. 8. 2016. -
Биленко Р.В., Долганина Н.Ю., Иванова Е.В., Рекачинский А.И. Высокопроизводительные вычислительные ресурсы Южно-Уральского государственного университета // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2022. Т. 11, № 1. C. 15-30. DOI: 10.14529/cmse220102 EDN: OLCPUG
Выпуск
Другие статьи выпуска
Анализ временных рядов и прогнозирование являются одной из широко исследуемых областей. Идентификация с помощью различных статистических методов, нейронных сетей или математических моделей уже давно используется в различных областях исследований от промышленности, до медицины, социальной сферы, аграрной среды. В статье рассматривается параллельный вариант алгоритма идентификации параметров квазилинейного рекуррентного уравнения для решения задачи регрессионного анализа с взаимозависимыми наблюдаемыми переменными, основанный на обобщенном методе наименьших модулей (GLDM). В отличие от нейронных сетей, широко используемых в настоящее время в различных системах прогнозирования, данный подход позволяет в явном виде получать качественные квазилинейные разностные уравнения, адекватно описывающие рассматриваемый процесс. Это позволяет повысить качество анализа изучаемых процессов. Существенным преимуществом модели, использующей обобщенный метод наименьших модулей, по сравнению с многочисленными нейросетевыми подходами является возможность интерпретации коэффициентов модели с точки зрения задачи исследования и использование полученного уравнения в качестве модели динамического процесса. Проведенные вычислительные эксперименты с использованием временных рядов показывают, что максимальное ускорение алгоритма происходит при использовании количества потоков, равного половине возможных потоков для данного устройства.
В параллельных планировщиках задач, работающих по стратегии work-stealing, каждый процессор имеет свой дек задач. Один конец дека используется для добавления и извлечения задач только владельцем, а другой - для перехвата задач другими процессорами. В статье предлагается обзор методов управления work-stealing деками, которые используются при реализации work-stealing планировщиков параллельных задач, а также представлено описание поставленных и решенных нашим коллективом задач оптимального управления деками для стратегии work-stealing. Принцип алгоритмов оптимального управления деками в двухуровневой памяти заключается в том, что при переполнении выделенного участка быстрой памяти происходит перераспределение элементов (задач) дека между уровнями памяти. В быстрой памяти остаются элементы из концов дека, так как с ними будет происходить работа в ближайшее время, а элементы средней части дека хранятся в медленной памяти. В таком случае необходимо определить оптимальное количество элементов, которое нужно оставить в быстрой памяти, в зависимости от критерия оптимальности и параметров системы.
Оценка производительности добычи полезных ресурсов, в том числе определение геометрических размеров объектов горной породы в открытом карьере, является одной из наиболее важных задач в горнодобывающей промышленности. Задача фрагментации горных пород решается с помощью методов компьютерного зрения, таких как экземплярная сегментация или семантическая сегментация. В настоящее время для решения таких задач для цифровых изображений используются нейронные сети глубокого обучения. Нейронные сети требуют больших вычислительных мощностей для обработки цифровых изображений высокого разрешения и больших наборов данных. Для решения этой проблемы в литературе предлагается использование облегченных архитектур нейронных сетей, а также методов оптимизации производительности, таких как параллельные вычисления с помощью центральных, графических и специализированных процессоров. В обзоре рассматриваются последние достижения в области нейронных сетей глубокого обучения для решения задач компьютерного зрения применительно к фрагментации горных пород и вопросы повышения производительности реализаций нейронных сетей на различных параллельных архитектурах.
Издательство
- Издательство
- ЮУрГУ
- Регион
- Россия, Челябинск
- Почтовый адрес
- 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
- Юр. адрес
- 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
- ФИО
- Александр Рудольфович Вагнер (Ректор)
- E-mail адрес
- admin@susu.ru
- Контактный телефон
- +7 (351) 2635882
- Сайт
- https://www.susu.ru