ISSN 2305-9052 · EISSN 2410-7034

Языки: ru · en

Статья: ИССЛЕДОВАНИЕ НЕЙРОСЕТЕВОГО МЕТОДА РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (2023)

Читать

Читать онлайн

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

Ключевые фразы: ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, МЕТОД ПОВЕРХНОСТНОГО ДВИЖЕНИЯ, искусственная нейронная сеть, глубокое обучение

Автор (ы): Ольховский Николай Александрович

Журнал: ВЕСТНИК ЮЖНО-УРАЛЬСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. СЕРИЯ: ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА И ИНФОРМАТИКА

Идентификаторы и классификаторы

УДК: 004.032.26. Нейронные сети
eLIBRARY ID: 55079130

Для цитирования:

ОЛЬХОВСКИЙ Н. А. ИССЛЕДОВАНИЕ НЕЙРОСЕТЕВОГО МЕТОДА РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ // ВЕСТНИК ЮЖНО-УРАЛЬСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. СЕРИЯ: ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА И ИНФОРМАТИКА. 2023. Т. 12 № 4

Текстовый фрагмент статьи

Одной из фундаментальных задач современной прикладной математики является задача линейного программирования (ЛП) с большим числом параметров [1]. Оптимизационные модели, основанные на многопараметрической (многомерной) задаче ЛП встречаются в системах поддержки принятия решений в экономике [2, 3], в системах управления беспилотными летательными аппаратами [4], в управлении технологическими процессами [5–7], при построении логистических цепочек [8–10], в оперативном управлении и планировании [11, 12].

До сих пор одним из наиболее распространенных способов решения задач ЛП был класс алгоритмов, разработанных на основе симплекс-метода [13]. Было установлено, что симплекс-метод эффективен для решения большого класса задач ЛП. В частности, симплекс-метод эффективно использует преимущества любой гиперразреженности в задачах ЛП [14]. Однако симплекс-метод обладает некоторыми фундаментальными особенностями, которые ограничивают его использование для решения больших задач ЛП. Вопервых, в определенных случаях симплекс-метод должен выполнять итерации по всем вершинам симплекса, что соответствует экспоненциальной временной сложности [15–17].

Моя история просмотров (2)

01. Статья: О некоторых тензорах 6-мерных уплощающихся эрмитовых подмногообразий алгебры Кэли

02. Статья: Транскраниальная магнитная стимуляция в оценке функциональной состоятельности кортикоспинального тракта у детей

Список литературы

Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных // Параллельные вычислительные технологии - 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

Выпуск

Т. 12 № 4 (2023)

Кол-во страниц: 109 страниц

Другие статьи выпуска

ВОЗМОЖНОСТИ ПАРАЛЛЕЛИЗМА ПРИ ИДЕНТИФИКАЦИИ КВАЗИЛИНЕЙНОГО РЕКУРРЕНТНОГО УРАВНЕНИЯ (2023)

Авторы: Аботалеб Мостафа Салахелдин Абделсалам, Макаровских Татьяна Анатольевна, Панюков Анатолий Васильевич

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

Сохранить в закладках

МЕТОДЫ УПРАВЛЕНИЯ WORK-STEALING ДЕКАМИ В ДИНАМИЧЕСКИХ ПЛАНИРОВЩИКАХ МНОГОПРОЦЕССОРНЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ (2023)

Авторы: Аксенова Елена Алексеевна, Соколов Андрей Владимирович

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

Сохранить в закладках

ОБЗОР ПРИМЕНЕНИЯ ГЛУБОКИХ НЕЙРОННЫХ СЕТЕЙ И ПАРАЛЛЕЛЬНЫХ АРХИТЕКТУР В ЗАДАЧАХ ФРАГМЕНТАЦИИ ГОРНЫХ ПОРОД (2023)

Авторы: Ронкин Михаил Владимирович, Акимова Елена Николаевна, Мисилов Владимир Евгеньевич, Решетников Кирилл Игоревич

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

Сохранить в закладках

Издательство

Издательство: ЮУрГУ
Регион: Россия, Челябинск
Почтовый адрес: 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
Юр. адрес: 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
ФИО: Александр Рудольфович Вагнер (Ректор)
E-mail адрес: admin@susu.ru
Контактный телефон: +7 (351) 2635882
Сайт: https://www.susu.ru

Все права на тексты и товарные знаки принадлежат их законным владельцам. Подробнее...

Сайт https://scinetwork.ru (далее – сайт) работает по принципу агрегатора – собирает и структурирует информацию из публичных источников в сети Интернет, то есть передает полнотекстовую информацию о товарных знаках в том виде, в котором она содержится в открытом доступе.

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

Все права на товарные знаки принадлежат их законным владельцам!

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

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

Спасибо, понятно.