Оптимизация параметров сплайна при аппроксимации многозначных функций

Цели. Методы сплайн-аппроксимации последовательности точек на плоскости получают все более широкое применение в различных областях. Сплайн рассматривается как однозначная функция с известным числом повторяющихся элементов. Наиболее широкое применение получили полиномиальные сплайны. Применительно к проектированию трасс линейных сооружений приходится рассматривать задачу с неизвестным числом элементов. Алгоритм решения задачи применительно к проектированию продольного профиля реализован и опубликован ранее. В этой задаче элементами сплайна являются дуги окружностей, сопрягаемые отрезками прямых, и сплайн представляет собой однозначную функцию. Однако при проектировании плана трассы в общем случае сплайн является многозначной функцией. Поэтому разработанный ранее алгоритм не пригоден для решения этой задачи, даже в случае использования тех же элементов сплайна. Цель настоящей статьи – обобщение полученных результатов на случай аппроксимации многозначных функций с учетом особенностей проектирования трасс линейных сооружений. На первом этапе работы было определено число элементов аппроксимирующего сплайна с помощью динамического программирования. В статье рассматривается следующий этап решения задачи.

Методы. Для оптимизации параметров сплайна используется новая математическая модель в виде модифицированной функции Лагранжа и специальный алгоритм нелинейного программирования. При этом удается вычислять аналитически производные целевой функции по параметрам сплайна при отсутствии ее аналитического выражения через эти параметры.

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

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

1. Карпов Д.А., Струченков В.И. Двухэтапная сплайнаппроксимация в компьютерном проектировании трасс линейных сооружений. Russ. Technol. J. 2021;9(5): 45–56. https://doi.org/10.32362/2500-316X-2021-9-5-45-56

2. Карпов Д.А., Струченков В.И. Сплайн-аппроксимация многозначных функций в проектировании трасс линейных сооружений. Russ. Technol. J. 2022;10(4):65–74. https://doi.org/10.32362/2500-316X-2022-10-4-65-74

3. Li W., Pu H., Schonfeld P., et al. Amethod for automatically recreating the horizontal alignment geometry of existing railways. Comput.-Aided Civ. Inf. 2019;34(1):71–94. https://doi.org/10.1111/mice.12392

4. Jha M.K., McCall C., Schonfeld P. Using GIS, genetic algorithms, and visualization in highway development. Comput.-Aided Civ. Inf. 2001;16(6):399–414. https://doi.org/10.1111/0885-9507.00242

5. Jha M.K., Schonfeld P. A highway alignment optimization model using geographic information systems. Transportation Research Part A: Policy and Practice. 2004;38(6):455–481. https://doi.org/10.1016/j.tra.2004.04.001

6. Jong J.C., Jha M.K., Schonfeld P. Preliminary highway design with genetic algorithms and geographic information systems. Comput.-Aided Civ. Inf. 2000;15(4):261–271. https://doi.org/10.1111/0885-9507.00190

7. Kang M.W., Schonfeld P., Yang N. Prescreening and repairing in a genetic algorithm for highway alignment optimization. Comput.-Aided Civ. Inf. 2009;24(2): 109–119. https://doi.org/10.1111/j.1467-8667.2008.00574.x

8. Pushak Y., Hare W., Lucet Y. Multiple-path selection for new highway alignments using discrete algorithms. Eur. J. Oper. Res. 2016;248(2):415–27. https://doi.org/10.1016/j.ejor.2015.07.039

9. Sarma K.C., Adeli H. Bilevel parallel genetic algorithms for optimization of large steel structures. Comput.-Aided Civ. Inf. 2001;16(5):295–304. https://doi.org/10.1111/08859507.00234

10. Shafahi Y., Bagherian M. A customized particle swarm method to solve highway alignment optimization problem. Comput.-Aided Civ. Inf. 2013;28(1):52–67. https://doi.org/10.1111/j.1467-8667.2012.00769.x

11. Bosurgi G., D’Andrea A. A polynomial parametric curve (PPC-curve) for the design of horizontal geometry of highways. Comput.-Aided Civ. Inf. 2012;27(4):303–312. https://doi.org/10.1111/j.1467-8667.2011.00750.x

12. Cerf R. The quasispecies regime for the simple genetic algorithm with roulette wheel selection. Adv. Appl. Probability. 2017;49(3):903–926. https://doi.org/10.1017/apr.2017.26

13. Бородакий Ю.В., Загребаев А.М., Крицына Н.А., Кулябичев Ю.П., Шумилов Ю.Ю. Нелинейное программирование в современных задачах оптимизации. М.: НИЯУ МИФИ; 2011. 244 с. ISBN 987-5-7262-1451-1

14. Bazaraa M., Sherali Y., Shetty C. Nonlinear programming. Theory and algorithms. 3rd ed. Hoboken, NJ: Wiley; 2006. 872 p. ISBN 978-0-471-48600-8

15. Betts J.T. Practical methods for optimal control using nonlinear programming. Ser. Advances in Design and Control. Philadelphia: SIAM; 2001. 190 p.

16. Lee J., Leyffer S. Mixed integer nonlinear programming. NY: Springer; 2011. 707 p. https://doi.org/10.1007/978-1-4614-1927-3

17. Sun W., Yuan Y.-X. Optimization theory and methods. Nonlinear programming. NY: Springer; 2006. 688 p. https://doi.org/10.1007/b106451

18. Струченков В.И. Методы оптимизации трасс в САПР линейных сооружений. М.: СОЛОН-Пресс; 2015. 271 с. ISBN 978-5-91359-139-5

19. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: пер. с англ. М.: Мир; 1985. 509 c.

20. Audet C., Hare W. Derivative-free and backbox optimization. Springer Series in Operations Research and Financial Engineering. Springer; 2017. 302 р. https://doi.org/10.1007/978-3-319-68913-5

21. Кохендерфер М.Д., Уилер Т.А. Алгоритмы оптимизации. M.: Вильямс; 2020. 528 с.

22. Черноруцкий И.Г. Методы оптимизации. Компьютерные технологии. СПб.: БХВ-Петербург; 2011. 329 с.

23. Ларичев О.И., Горвиц Г.Г. Методы поиска локальных экстремумов овражных функций. М.: Наука; 1990. 96 с.

24. Гилл Ф., Мюррей У. Численные методы условной оптимизации: пер. с англ. М.: Мир; 1977. 296 с.