DOI: https://doi.org/10.32626/2308-5916.2019-19.17-24

Найкраще рівномірне наближення сплайнами з використанням диференціальної еволюції

Лариса Петрівна Вакал, Євген Сергійович Вакал

Анотація


Розглянуто задачу найкращого рівномірного наближення функцій поліноміальними сплайнами з фіксованими вузлами. Для її розв’язання запропоновано підхід на основі еволюційних алгоритмів — потужного класу стохастичних пошукових методів оптимізації. Для знаходження сплайна найкращого рівномірного наближення адаптовано алгоритм диференціальної еволюції. Це один із кращих еволюційних алгоритмів, який стабільно знаходить глобальний оптимум цільової функції (критерію оптимізації) за мінімальний час. Еволюційний процес в алгоритмі починається з генерації популяції випадкових векторів, координати яких представляють собою можливі значення коефіцієнтів сплайна. Далі вектори постійно модифікуються за допомогою операцій мутації, схрещування та селекції з метою зменшення значення цільової функції (похибки наближення сплайном). Алгоритм завершується, якщо вичерпано задане максимальне число популяцій або відбувається стагнація еволюційного процесу. Алгоритм диференціальної еволюції простий у програмній реалізації й використанні (містить мало параметрів, що потребують підбору), легко розпаралелюється. Розроблені рекомендації щодо вибору оптимальних значень основних параметрів алгоритму: розміру популяції, коефіцієнта мутації, ймовірності схрещування. Для низки тестових функцій виконано порівняння похибок наближення, отриманих за стохастичним алгоритмом диференціальної еволюції та за іншими (детерміністичними) алгоритмами. Результати порівняння показали, що точність наближення функцій сплайнами з використанням алгоритму диференціальної еволюції не гірше, ніж при застосуванні значно складніших детерміністичних алгоритмів рівномірного наближення. Це свідчить про ефективність алгоритму диференціальної еволюції. Він може використовуватись як альтернатива відомим детерміністичним алгоритмам наближення сплайнами.


Повний текст:

PDF

Посилання


Стечкин С. Б., Субботин Ю. Н. Сплайны в вычислительной математике. М. : Наука, 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.