Найкраще рівномірне наближення сплайнами з використанням диференціальної еволюції
DOI:
https://doi.org/10.32626/2308-5916.2019-19.17-24Анотація
Розглянуто задачу найкращого рівномірного наближення функцій поліноміальними сплайнами з фіксованими вузлами. Для її розв’язання запропоновано підхід на основі еволюційних алгоритмів — потужного класу стохастичних пошукових методів оптимізації. Для знаходження сплайна найкращого рівномірного наближення адаптовано алгоритм диференціальної еволюції. Це один із кращих еволюційних алгоритмів, який стабільно знаходить глобальний оптимум цільової функції (критерію оптимізації) за мінімальний час. Еволюційний процес в алгоритмі починається з генерації популяції випадкових векторів, координати яких представляють собою можливі значення коефіцієнтів сплайна. Далі вектори постійно модифікуються за допомогою операцій мутації, схрещування та селекції з метою зменшення значення цільової функції (похибки наближення сплайном). Алгоритм завершується, якщо вичерпано задане максимальне число популяцій або відбувається стагнація еволюційного процесу. Алгоритм диференціальної еволюції простий у програмній реалізації й використанні (містить мало параметрів, що потребують підбору), легко розпаралелюється. Розроблені рекомендації щодо вибору оптимальних значень основних параметрів алгоритму: розміру популяції, коефіцієнта мутації, ймовірності схрещування. Для низки тестових функцій виконано порівняння похибок наближення, отриманих за стохастичним алгоритмом диференціальної еволюції та за іншими (детерміністичними) алгоритмами. Результати порівняння показали, що точність наближення функцій сплайнами з використанням алгоритму диференціальної еволюції не гірше, ніж при застосуванні значно складніших детерміністичних алгоритмів рівномірного наближення. Це свідчить про ефективність алгоритму диференціальної еволюції. Він може використовуватись як альтернатива відомим детерміністичним алгоритмам наближення сплайнами.
Посилання
Стечкин С. Б., Субботин Ю. Н. Сплайны в вычислительной математике. М. : Наука, 1976. 248 с.
Попов Б. А. Равномерное приближение сплайнами. Киев : Наук. думка, 1989. 272 с.
Малачівський П. С., Скопецький В. В. Неперервне й гладке мінімаксне сплайн-наближення. Київ : Наук. думка, 2013. 270 с.
Barrodale J., Young A. A note on numerical procedures for approximation by spline functions. Comput. J. 1966. Vol. 9. P. 318–320.
Esch R. E., Eastman W. L. Computational methods for the best spline function approximation. J. Approx. Theory. 1969. Vol. 2. P. 85–96.
Вакал Л. П. Побудова найкращих чебишовських наближень сплайнами. Штучний інтелект. 2017. № 2 (76). С. 94–100.
Schumaker L. L. Some algorithms for the computation of interpolating and ap-proximating spline functions. Theory and applications of spline functions. New York : Academic Press, 1969. P. 87–102.
Nürnberger G., Sommer M. A Remez type algorithm for spline functions. Nu-mer. Math. 1983. Vol. 41, № 1. P. 117–146.
Каленчук-Порханова А. А., Вакал Л. П. Пакет программ аппроксимации функций. Комп’ютерні засоби, мережі та системи. 2008. № 7. С. 32–38.
Каленчук-Порханова А. А., Вакал Л. П. Аппарат аппроксимации в составе программного обеспечения суперкомпьютера с кластерной архитектурой. Искусственный интеллект. 2009. № 1. С. 158–165.
Storn R., Price K. Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization. 1997. Vol. 11. P. 341–359.
Vakal L. P. Seeking optimal knots for segment approximation. Journal of Automation and Information Sciences. 2016. Vol. 48, № 11. P. 68–75.
Вакал Л. П. Апроксимація функцій багатьох змінних із застосуванням алгоритму диференціальної еволюції. Математичні машини і системи. 2017. № 1. С. 90–96.
Vakal L. P., Kalenchuk-Porkhanova A. A., Vakal E. S. Increasing the efficiency of Chebyshev segment fractional rational approximation. Cybernetics and Sys-tems Analysis. 2017. Vol. 53, № 5. P. 759–765.
Вакал Л. П., Вакал Є. С. Розв’язання перевизначеної системи трансценден-тних рівнянь з використанням диференціальної еволюції. Математичне та комп’ютерне моделювання. Серія: Технічні науки : зб. наук. пр. Кам’янець-Подільський : Кам’янець-Подільськ. нац. ун-т, 2017. Вип. 15. С. 24–30.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
