|
DOI: 10.14489/vkit.2022.08.pp.011-025
Карпов Д. А., Смирнов С. С., Струченков В. И.
КОМПЬЮТЕРНОЕ ПРОЕКТИРОВАНИЕ ТРАСС ЛИНЕЙНЫХ СООРУЖЕНИЙ С ПРИМЕНЕНИЕМ АЛГОРИТМОВ СПЛАЙН-АППРОКСИМАЦИИ МНОГОЗНАЧНЫХ ФУНКЦИЙ. Часть 2
(с. 11-25)
Аннотация. Первый этап решения задачи аппроксимации сплайном, состоящим из дуг окружностей, сопрягаемых прямыми, многозначной функции, заданной последовательностью точек на плоскости, рассмотрен в [1]. На этом этапе с применением динамического программирования определены число элементов сплайна и приближенные значения его параметров. В настоящей статье рассматривается второй этап: оптимизация параметров сплайна с применением алгоритмов нелинейного программирования. Результат первого этапа используется как начальное приближение для итерационного процесса. Целевая функция: сумма квадратов отклонений заданных точек от искомого сплайна. Переменными, определяющими положение сплайна и отклонения от него заданных точек, являются длины отрезков прямых, дуг окружностей и их радиусы. На эти переменные накладываются ограничения в виде неравенств. Могут быть также ограничения на отклонения отдельных точек от сплайна. Дан анализ особенностей задачи: основная состоит в том, что целевая функция не выражается аналитически через переменные длины и радиусы. Тем не менее приведены формулы для вычисления ее частных производных по этим переменным. Реализован алгоритм нелинейного программирования, в котором ограничения на длины элементов и радиусы учитываются при вычислении направления спуска, а ограничения (равенства и неравенства) на отклонения заданных точек от сплайна учитываются с помощью модифицированной функции Лагранжа. Из-за «овражного» характера этой модифицированной функции сначала используется алгоритм сопряженных градиентов (для спуска в «овраг»), а затем известный DFP-алгоритм, использующий направления спуска на пройденных итерациях для построения матрицы, приближенной к обратной матрице вторых производных (матрице Гессе). Предложены математическая модель и алгоритмы оптимизации параметров сплайна, аппроксимирующего многозначные функции, которыми представляются трассы линейных сооружений. Применительно к проектированию таких сооружений, как траншеи для прокладки трубопроводов различного назначения и каналы оросительной сети, получаемый сплайн является окончательным решением. Применительно к проектированию железных и автомобильных дорог приведенные в статье формулы вычисления частных производных предстоит обобщить на случай сплайна, в котором окружности сопрягаются с прямыми с помощью клотоид.
Ключевые слова: трасса; сплайн; нелинейное программирование; целевая функция; ограничения; сопряженные градиенты; матрица Гессе.
Karpov D. A., Smirnov S. S., Struchenkov V. I.
COMPUTER DESIGN OF ROUTES OF LINEAR STRUCTURES USING ALGORITHMS SPLINE-APPROXIMATIONS OF MULTIPLE-VALUED FUNCTIONS. Part 2
(pp. 11-25)
Abstract. The article is the end of the previously published article, which considered the first stage of solving the problem of approximation by a spline, consisting of arcs of circles conjugated by straight lines, a multivalued function given by a sequence of points on the plane. At this stage, using dynamic programming, the number of spline elements and the approximate values of its parameters are determined. This article considers the second stage: optimization of spline parameters using nonlinear programming algorithms. The result of the first stage is used as the initial approximation for the iterative process. Target function: the sum of the squared deviations of the given points from the desired spline. The variables that determine the position of the spline and the deviations of the given points from it are the lengths of line segments, circular arcs and their radii. These variables are subject to constraints in the form of inequalities. There may also be restrictions on deviations of individual points from the spline. An analysis of the features of the problem is given, the main of which is that the objective function is not expressed analytically in terms of variable lengths and radii. Nevertheless, formulas are given for calculating its partial derivatives with respect to these variables. A non-linear programming algorithm has been implemented, in which restrictions on element lengths and radii are taken into account when calculating the direction of descent, and restrictions (equalities and inequalities) for deviations of given points from the spline are taken into account using the modified Lagrange function (MFL). Due to the “ravine” nature of the MFL, the conjugate gradient algorithm is first used (for descending into the “ravine”), and then the wellknown DFP algorithm that uses the descent directions built on the iterations passed to construct a matrix approximate to the inverse matrix of second derivatives. The purpose of the article is to present a mathematical model and algorithms for optimizing the parameters of a spline approximating multivalued functions that represent the routes of linear structures. With regard to the design of structures such as trenches for laying pipelines for various purposes, irrigation network channels, the resulting spline is the final solution. With regard to the design of the railway. and a.d. the formulas for calculating partial derivatives given in the article have to be generalized to the case of a spline, in which circles are conjugated with straight lines using a clothoid.
Keywords: Route; Spline; Non-linear programming; Objective function; Constraints; Conjugate gradients; Hessian matrix.
Д. А. Карпов, С. С. Смирнов, В. И. Струченков (Институт искусственного интеллекта МИРЭА – Российского технологического университета, Москва, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
D. A. Karpov, S. S. Smirnov, V. I. Struchenkov (Institute of Artificial Intelligence of the MIREA – Russian Technological University, Moscow, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Карпов Д. А., Смирнов С. С., Струченков В. И. Компьютерное проектирование трасс линейных сооружений с применением алгоритмов сплайн-аппроксимации многозначных функций. Ч. 1 // Вестник компьютерных и информационных технологий. 2022. Т. 19, № 7. C. 3 – 12. DOI: 10.14489/ vkit.2022.07.pp.003-012
2. Hao Pu, Wei Li, Paul Schonfeld. A Method for Automatically Recreating the Horizontal Alignment Geometry of Existing Railways // Computer-Aided Civil and Infrastructure. Engineering. 2019. V. 34(1). P. 71 – 94. URL: http://doi.org/10/111/mice.12392
3. Jha M. K., McCall C., Schonfeld P. Using GIS, Genetic Algorithms, and Visualization in Highway Development // Computer-Aided Civil and Infrastructure Engineering. 2001. V. 16(6). P. 399 – 414. URL: https:// doi.org/ 10.1111/0885-9507.00242
4. Jha M. K., Schonfeld P. A Highway Alignment Optimization Model Using Geographic Information Systems // Transportation Research. Part A Policy and Practice. 2004. V. 38(6). P. 455 – 481. URL: https:// doi.org/10.1016/j.tra.2004.04.001
5. Jong J. C., Jha M. K., Schonfeld P. Preliminary Highway Design with Genetic Algorithms and Geographic Information Systems // Computer-Aided Civil and Infrastructure Engineering. 2000. V. 15(4). P. 261 – 271. URL: https://doi.org/10.1111/0885-9507.00190
6. Kang M. W., Schonfeld P., Yang N. Prescreening and Repairing in a Genetic Algorithm for Highway Alignment Optimization // Computer-Aided Civil and Infrastructure Engineering. 2009. V. 24(2). P. 109 – 119. URL: https://doi.org/10.1111/j.1467-8667.2008.00574.x
7. Pushak Y., Hare W., Lucet Y. Multiple-Path Selection for New Highway Alignments Using Discrete Algorithms // European Journal of Operational Research. 2016. V. 248(2). P. 415 – 427. URL: https://doi.org/ 10.1016/ j.ejor.2015.07.039
8. Sarma K. C., Adeli H. Bilevel Parallel Genetic Algorithms for Optimization of Large Steel Structures // Computer Aided Civil and Infrastructure Engineering. 2001. V. 16(5). P. 295 – 304. URL: https://doi.org/ 10.1111/ 0885-9507.00234
9. Shafahi Y., Bagherian M. A Customized Particle Swarm Method to Solve Highway Alignment Optimization Problem // Computer-Aided Civil and Infrastructure Engineering. 2013. V. 28. P. 52 – 67. URL: https://doi.org/10.1111/j.1467-8667.2012.00769.х
10. Bosurgi G., D’Andrea A. A Polynomial Parametric Curve (PPC-curve) for the Design of Horizontal Geometry of Highways // Computer-Aided Civil and Infrastructure Engineering. 2012. V. 27(4). P. 303 – 312. URL: https://doi.org/10.1111/j.1467-8667.2011.00750.x
11. Cerf R. The Quasispecies Regime for the Simple Genetic Algorithm with Roulette Wheel Selection // Cornell University Computer Science > Neural and Evolutionary Computing. 2017. V. 49(3). P. 903 – 926. URL: https:// arxiv.org/ abs/1506.09081
12. Бородакий Ю. В., Загребаев А. М., Крицына Н. А., Кулябичев Ю. П. Нелинейное программирование в современных задачах оптимизации. М.: НИЯУ МИФИ, 2011. 244 с.
13. Bazaraa M., Sherali Y., Shetty C. Nonlinear Programming. Theory and Algorithms 3d Ed. Hoboken, NJ: Wiley, 2006. 872 p.
14. Betts J. T. Practical. Methods for Optimal Control Using Nonlinear Programming Ser. Advances in Design and Control. Philadelphia: SIAM, 2001. 190 p.
15. Lee J., Leyffer S. Mixed Integer Nonlinear Programming Publisher: Springer, 2011. 707 p.
16. Sun W., Yuan Y.-X. Optimization Theory and Methods. Nonlinear Programming. US: Springer, 2006. 688 p. URL: https://doi.org/10.1007/b106451
17. Струченков В. И. Методы оптимизации трасс в САПР линейных сооружений. М.: СОЛОН ПРЕСС, 2014. 271 с.
18. Пантелеев А. В., Летова Т. А. Методы оптимизации: учеб. пособие. М.: Логос, 2011. 424 c.
19. Кочегурова Е. А. Теория и методы оптимизации: учеб. пособие. Томск: Томский политехнический университет, 2013. 134 c.
20. Васильева О. А. Методы оптимизации: учеб. пособие. М.: Московский государственный строительный университет, 2014. 96 c.
21. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация / пер. с англ. М.: Мир, 1985. 509 c.
22. Audet C., Hare W. Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. Springer. Springer-Vergal, New York, 2017. 302 р.
23. Кохендерфер М., Уилер Т. Алгоритмы оптимизации. M.: Вильямс, 2020. 528 с.
24. Черноруцкий И. Г. Методы оптимизации. Компьютерные технологии. СПБ.: БХВ-Петербург, 2011. 329 с.
25. Ларичев О. И., Горвиц Г. Г. Методы поиска локальных экстремумов овражных функций. М.: Наука, 1990. 96 с.
26. Гилл Ф., Мюррей У. Численные методы условной оптимизации / пер. с англ. М.: Мир, 1977. 296 с.
1. Karpov D. A., Smirnov S. S., Struchenkov V. I. (2022). Computer design of routes of linear structures using algorithms spline-approximations of multiple-valued functions. Part 11. Vestnik komp'yuternyh i informatsionnyh tekhnologiy, Vol. 19, (7), pp. 3 – 12. [in Russian language] DOI: 10.14489/ vkit.2022.07.pp.003-012
2. Hao Pu, Wei Li, Paul Schonfeld. (2019). A Method for Automatically Recreating the Horizontal Alignment Geometry of Existing Railways. Computer-Aided Civil and Infrastructure. Engineering, Vol. 34, (1), pp. 71 – 94. Available at: http://doi.org/10/111/mice.12392
3. Jha M. K., McCall C., Schonfeld P. (2001). Using GIS, Genetic Algorithms, and Visualization in Highway Development. Computer-Aided Civil and Infrastructure Engineering, Vol. 16, (6), pp. 399 – 414. Available at: https:// doi.org/ 10.1111/0885-9507.00242
4. Jha M. K., Schonfeld P. (2004). A Highway Alignment Optimization Model Using Geographic Information Systems. Transportation Research. Part A Policy and Practice, Vol. 38, (6), pp. 455 – 481. Available at: https:// doi.org/10.1016/j.tra.2004.04.001
5. Jong J. C., Jha M. K., Schonfeld P. (2000). Preliminary Highway Design with Genetic Algorithms and Geographic Information Systems. Computer-Aided Civil and Infrastructure Engineering, Vol. 15, (4), pp. 261 – 271. Available at: https://doi.org/10.1111/0885-9507.00190
6. Kang M. W., Schonfeld P., Yang N. (2009). Prescreening and Repairing in a Genetic Algorithm for Highway Alignment Optimization. Computer-Aided Civil and Infrastructure Engineering, Vol. 24, (2), pp. 109 – 119. Available at: https://doi.org/10.1111/j.1467-8667.2008.00574.x
7. Pushak Y., Hare W., Lucet Y. (2016). Multiple-Path Selection for New Highway Alignments Using Discrete Algorithms. European Journal of Operational Research, Vol. 248, (2), pp. 415 – 427. Available at: https://doi.org/10.1016/ j.ejor.2015.07.039
8. Sarma K. C., Adeli H. (2001). Bilevel Parallel Genetic Algorithms for Optimization of Large Steel Structures. Computer Aided Civil and Infrastructure Engineering, Vol. 16, (5), pp. 295 – 304. Available at: https://doi.org/ 10.1111/ 0885-9507.00234
9. Shafahi Y., Bagherian M. (2013). A Customized Particle Swarm Method to Solve Highway Alignment Optimization Problem. Computer-Aided Civil and Infrastructure Engineering, Vol. 28, pp. 52 – 67. Available at: https://doi.org/10.1111/j.1467-8667.2012.00769.х
10. Bosurgi G., D’Andrea A. (2012). A Polynomial Parametric Curve (PPC-curve) for the Design of Horizontal Geometry of Highways. Computer-Aided Civil and Infrastructure Engineering, Vol. 27, (4), pp. 303 – 312. Available at: https://doi.org/10.1111/j.1467-8667.2011.00750.x
11. Cerf R. (2017). The Quasispecies Regime for the Simple Genetic Algorithm with Roulette Wheel Selection. Cornell University Computer Science > Neural and Evolutionary Computing, Vol. 49, (3), pp. 903 – 926. Available at: https://arxiv.org/ abs/1506.09081
12. Borodakiy Yu. V., Zagrebaev A. M., Kritsyna N. A., Kulyabichev Yu. P. (2011). Nonlinear programming in modern optimization problems. Moscow: NIYaU MIFI. [in Russian language]
13. Bazaraa M., Sherali Y., Shetty C. (2006). Nonlinear Programming. Theory and Algorithms. 3rd Ed. Hoboken, NJ: Wiley.
14. Betts J. T. (2001). Practical. Methods for Optimal Control Using Nonlinear Programming Ser. Advances in Design and Control. Philadelphia: SIAM.
15. Lee J., Leyffer S. (2011). Mixed Integer Nonlinear Programming Publisher. Springer.
16. Sun W., Yuan Y.-X. (2006). Optimization Theory and Methods. Nonlinear Programming. US: Springer. Available at: https://doi.org/10.1007/b106451
17. Struchenkov V. I. (2014). Methods for optimizing routes in CAD for linear structures. Moscow: SOLON PRESS. [in Russian language]
18. Panteleev A. V., Letova T. A. (2011). Optimization methods: textbook. Moscow: Logos. [in Russian language]
19. Kochegurova E. A. (2013). Theory and methods of optimization: textbook. Tomsk: Tomskiy politekhnicheskiy universitet. [in Russian language]
20. Vasil'eva O. A. (2014). Optimization methods: textbook. Moscow: Moskovskiy gosudarstvenniy stroitel'niy universitet. [in Russian language]
21. Gill F., Myurrey U., Rayt M. (1985). Practical optimization. Moscow: Mir. [in Russian language]
22. Audet C., Hare W. (2017). Derivative-Free and Blackbox Optimization. Springer Series in Operations Research and Financial Engineering. New York: Springer-Vergal.
23. Kohenderfer M., Uiler T. (2020). Optimization algorithms. Moscow: Vil'yams. [in Russian language]
24. Chernorutskiy I. G. (2011). Optimization methods. Computer technologies. Saint-Petersburg: BHV-Peterburg. [in Russian language]
25. Larichev O. I., Gorvits G. G. (1990). Methods for searching for local extrema of gully functions. Moscow: Nauka. [in Russian language]
26. Gill F., Myurrey U. (1977). Numerical methods of conditional optimization. Moscow: Mir. [in Russian language]
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 500 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2022.08.pp.011-025
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 500 rubles. (including VAT 20%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2022.08.pp.011-025
and fill out the form
.
|
Архив номеров
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»