Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Кибернетика и системный анализ
Datum:2019
Hauptverfasser: Вакал, Л.П., Вакал, Е.С.
Format: Artikel
Sprache:Russisch
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schlagworte:
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/180875
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами / Л.П. Вакал, Е.С. Вакал // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 121-128. — Бібліогр.: 22 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859674105570131968
author Вакал, Л.П.
Вакал, Е.С.
author_facet Вакал, Л.П.
Вакал, Е.С.
citation_txt Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами / Л.П. Вакал, Е.С. Вакал // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 121-128. — Бібліогр.: 22 назв. — рос.
collection DSpace DC
container_title Кибернетика и системный анализ
description Предложен алгоритм наилучшего равномерного приближения сплайном с оптимальными узлами. Для поиска оптимальных узлов использована дифференциальная эволюция один из лучших эволюционных алгоритмов, стабильно находящий глобальный оптимум функции за минимальное время. Коэффициенты сплайна определены как решение задачи сплайн-аппроксимации с фиксированными узлами. Приведены результаты вычислительного эксперимента. Запропоновано алгоритм найкращого рівномірного наближення сплайном з оптимальними вузлами. Для пошуку оптимальних вузлів застосовано диференціальну еволюцію один з найкращих еволюційних алгоритмів, що стабільно знаходить оптимум функції за мінімальний час. Коефіцієнти сплайна визначено як розв’язання задачі сплайн-апроксимації з фіксованими вузлами. Наведено результати обчислювального експерименту. An algorithm for best uniform spline approximation with free knots is presented in this paper. A differential evolution is used for finding the optimal knots. It is one of the best evolutionary algorithms which finds function’s global optimum in minimum time. Spline coefficients are computed as a solution of a spline-approximation problem with fixed knots. Results of the numerical experiment are given
first_indexed 2025-11-30T14:55:20Z
format Article
fulltext Ë.Ï. ÂÀÊÀË, Å.Ñ. ÂÀÊÀË ÓÄÊ 519.6+004.02 ÀËÃÎÐÈÒÌ ÍÀÈËÓרÅÉ ÐÀÂÍÎÌÅÐÍÎÉ ÀÏÏÐÎÊÑÈÌÀÖÈÈ ÑÏËÀÉÍÀÌÈ ÑÎ ÑÂÎÁÎÄÍÛÌÈ ÓÇËÀÌÈ Àííîòàöèÿ. Ïðåäëîæåí àëãîðèòì íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ ñïëàéíîì ñ îïòèìàëüíûìè óçëàìè. Äëÿ ïîèñêà îïòèìàëüíûõ óçëîâ èñïîëü- çîâàíà äèôôåðåíöèàëüíàÿ ýâîëþöèÿ — îäèí èç ëó÷øèõ ýâîëþöèîííûõ àë- ãîðèòìîâ, ñòàáèëüíî íàõîäÿùèé ãëîáàëüíûé îïòèìóì ôóíêöèè çà ìèíè- ìàëüíîå âðåìÿ. Êîýôôèöèåíòû ñïëàéíà îïðåäåëåíû êàê ðåøåíèå çàäà÷è ñïëàéí-àïïðîêñèìàöèè ñ ôèêñèðîâàííûìè óçëàìè. Ïðèâåäåíû ðåçóëüòàòû âû÷èñëèòåëüíîãî ýêñïåðèìåíòà. Êëþ÷åâûå ñëîâà: íàèëó÷øàÿ ðàâíîìåðíàÿ àïïðîêñèìàöèÿ, ñïëàéí, îïòè- ìàëüíûå óçëû, äèôôåðåíöèàëüíàÿ ýâîëþöèÿ. ÂÂÅÄÅÍÈÅ Â ïîñëåäíèå äåñÿòèëåòèÿ èíòåíñèâíî èññëåäóåòñÿ è èñïîëüçóåòñÿ â ïðèêëàä- íûõ çàäà÷àõ àïïàðàò ñïëàéíîâ. Îíè ïðèìåíÿþòñÿ ïðè ðàñ÷åòå íà ïðî÷íîñòü ñòðîèòåëüíûõ êîíñòðóêöèé, äëÿ àíàëèòè÷åñêîãî îïèñàíèÿ ïîâåðõíîñòåé äåòà- ëåé ìàøèí, òðàåêòîðèè äâèæåíèÿ ðåçöà ñòàíêà ñ ïðîãðàììíûì óïðàâëåíèåì è äð. [1–3]. Îñîáåííî ïîïóëÿðíû èíòåðïîëÿöèîííûå ñïëàéíû ñòåïåíè íå âûøå òðåõ, ïîñêîëüêó ñîîòâåòñòâóþùåé ãëàäêîñòè âî ìíîãèõ çàäà÷àõ äîñòàòî÷íî è ïàðàìåòðû òàêîãî ñïëàéíà ëåãêî âû÷èñëÿþòñÿ. Îäíàêî íàõîæäåíèå ïàðàìåòðîâ èíòåðïîëÿöèîííûõ ñïëàéíîâ áîëåå âûñîêèõ ñòåïåíåé, íàïðèìåð â ñëó÷àå íå- ðàâíîìåðíîé ñåòêè, çàòðóäíèòåëüíî [1]. Íà ïðàêòèêå èñïîëüçóþòñÿ òàêæå ñïëàéíû íàèëó÷øåãî ïðèáëèæåíèÿ. Ïðè îäèíàêîâîì ÷èñëå ïàðàìåòðîâ òàêîé ñïëàéí ïðèáëèæàåò ôóíêöèþ íå õóæå, ÷åì èíòåðïîëÿöèîííûé, è ïðè ýòîì äëÿ åãî ïîñòðîåíèÿ íå òðåáóåòñÿ çàäàâàòü â óçëàõ êðàåâûõ óñëîâèé [1]. Ñ ó÷åòîì ýòîãî âî ìíîãèõ ïðèêëàäíûõ çàäà÷àõ ïðèìåíåíèå ñïëàéíîâ íàèëó÷øåãî ïðèáëèæåíèÿ îêàçûâàåòñÿ áîëåå ïðåäïî÷òèòåëüíûì [4, 5]. Ïðèíöèïèàëüíî ðàçëè÷àåòñÿ äâà ñëó÷àÿ íàèëó÷øåé àïïðîêñèìàöèè ñïëàéíà- ìè: ñ ôèêñèðîâàííûìè è ñî ñâîáîäíûìè óçëàìè, êîãäà çàäàííûìè ñ÷èòàþòñÿ èõ ÷èñëî è ñòåïåíü ñïëàéíà, íî ñàìè óçëû íå ôèêñèðóþòñÿ.  ïîñëåäíåì ñëó÷àå óçëû ðàññìàòðèâàþòñÿ êàê ñâîáîäíûå ïàðàìåòðû, ÷òî ïîçâîëÿåò íå òîëüêî çíà÷èòåëüíî óìåíüøèòü ïîãðåøíîñòü àïïðîêñèìàöèè ñïëàéíîì, íî è äîñòè÷ü ìèíèìàëüíîé ïî- ãðåøíîñòè ïðè èñïîëüçîâàíèè îïòèìàëüíûõ óçëîâ. Îòìåòèì, ÷òî íàõîæäåíèå òà- êèõ óçëîâ ÿâëÿåòñÿ ñëîæíîé íåëèíåéíîé çàäà÷åé ìíîãîìåðíîé îïòèìèçàöèè.  íàñòîÿùåé ñòàòüå ðàññìàòðèâàþòñÿ ñïëàéíû íàèëó÷øåãî ïðèáëèæåíèÿ â ðàâíîìåðíîé (÷åáûøåâñêîé, ìèíèìàêñíîé) íîðìå è äëÿ ïîèñêà îïòèìàëüíûõ óçëîâ ïðåäëàãàåòñÿ ýâðèñòè÷åñêèé ïîäõîä ñ ïðèìåíåíèåì àëãîðèòìà äèôôåðåí- öèàëüíîé ýâîëþöèè, ïðåäíàçíà÷åííîãî äëÿ ïîèñêà ãëîáàëüíîãî îïòèìóìà íåëè- ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 121 � Ë.Ï. Âàêàë, Å.Ñ. Âàêàë, 2019 íåéíûõ, íåäèôôåðåíöèðóåìûõ, ìóëüòèìîäàëüíûõ ôóíêöèé ìíîãèõ ïåðåìåííûõ è ÿâëÿþùåãîñÿ ïðÿìûì ìåòîäîì îïòèìèçàöèè. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È È ÎÁÇÎÐ ÌÅÒÎÄΠÅÅ ÐÅØÅÍÈß Ïóñòü f x( ) — íåïðåðûâíàÿ íà îòðåçêå [ , ]� � ôóíêöèÿ, T t tr� ( , , )1 � — âåêòîð óçëîâ, òàêèõ ÷òî � �� � � � � ��t t t tr r0 1 1� . Ôóíêöèÿ s x( ) íàçûâàåòñÿ ñïëàé- íîì ñòåïåíè n äåôåêòà k (0 � �k n) ñ óçëàìè T , åñëè íà êàæäîì ïðîìåæóòêå [ , ]t tj j�1 ( j r� �1 1, ,� ) îíà ñîâïàäàåò ñ íåêîòîðûì ìíîãî÷ëåíîì ñòåïåíè n è s C n k� � [ , ]� � [1]. Áóäåì ðàññìàòðèâàòü ìíîæåñòâî S n r, ïîëèíîìèàëüíûõ ñïëàéíîâ ñòåïåíè n äåôåêòà k �1 ñ r óçëàìè. Ïðîèçâîëüíûé ñïëàéí s S n r� , ìîæíî ïðåäñòàâèòü â âèäå s x a x a x ti i i n n i i n i r ( ) ( ) ( )� � � � � � � � � 0 1 , (1) ïðè÷åì òàêîå ïðåäñòàâëåíèå åäèíñòâåííî (ñì., íàïðèìåð, [6]).  ôîðìóëå (1) êîýôôèöèåíòû a a an r0 1, , ,� � — äåéñòâèòåëüíûå ÷èñëà è ( ) ( ) , , , . x t x t x t x t i n i n i i � � � � � � � � 0 Çàäà÷à íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ ôóíêöèè f ñïëàéíîì ñ r ôèêñèðîâàííûìè óçëàìè ñîñòîèò â íàõîæäåíèè ñïëàéíà s S n r * ,� , äëÿ êîòîðîãî max | ( ) ( )| min max [ , ] * , , , [ , ]x a a a x f x s x n r� � � � �� � � �{ }0 1 � | ( ) ( )|f x s x� . (2) Ìåòîäû ðåøåíèÿ çàäà÷è (2) äîñòàòî÷íî õîðîøî ðàçðàáîòàíû. Îíè ÿâëÿþòñÿ ðåàëèçàöèåé äâóõ îñíîâíûõ ïîäõîäîâ. Ïåðâûé ïîäõîä [7–9] ñîñòîèò â çàìåíå ïðîìåæóòêà ïðèáëèæåíèÿ [ , ]� � íåêîòîðîé ñåòêîé è ñâåäåíèè äèñêðåòíîé çàäà÷è (2) ê çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Âòîðîé ïîäõîä [10, 11] çàêëþ÷àåòñÿ â îáîáùåíèè íà ñëó÷àé ñïëàéíîâ ìåòîäà ïîñëåäîâàòåëüíûõ ÷åáûøåâñêèõ èíòåð- ïîëÿöèé Ðåìåçà [12]. Òåîðåòè÷åñêîé îñíîâîé äàííîãî ïîäõîäà ÿâëÿåòñÿ óòâåð- æäåíèå [13], ÷òî äëÿ êàæäîé ôóíêöèè f C� [ , ]� � ñóùåñòâóåò íàèëó÷øàÿ àïïðîê- ñèìàöèÿ s Sf n r� , òàêàÿ, ÷òî ðàçíîñòü f s f� èìååò ïî êðàéíåé ìåðå (n r� �2) òî÷åê, â êîòîðûõ îíà äîñòèãàåò ñâîåãî ìàêñèìàëüíîãî ïî ìîäóëþ çíà÷åíèÿ ñ ïî- ñëåäîâàòåëüíîé ïåðåìåíîé çíàêà. Îáîçíà÷èì �( )T ïîãðåøíîñòü íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ ôóíêöèè f ñïëàéíîì ñ ôèêñèðîâàííûìè óçëàìè T � � � ( ) min max | ( ) ( , )| , , , [ , ] T f x s x T a a a xn r � � � �{ }0 1 � . Çàäà÷à íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ ôóíêöèè f ñïëàéíîì ñ r ñâîáîäíûìè óçëàìè ñîñòîèò â íàõîæäåíèè ñïëàéíà s S n r * ,� , óäîâëåòâîðÿþùåãî óñëîâèþ max | ( ) ( )| min ( ) [ , ] * x T f x s x � � � � � � { } T . (3)  îòëè÷èå îò ñëó÷àÿ ôèêñèðîâàííûõ óçëîâ íàèëó÷øèå ñïëàéí-ïðèáëèæåíèÿ ñî ñâîáîäíûìè óçëàìè íåâîçìîæíî îõàðàêòåðèçîâàòü òîëüêî àëüòåðíàíñíûìè ñâîéñòâàìè ðàçíîñòè ôóíêöèè è ñïëàéíà. Êàêèìè äîëæíû áûòü äîïîëíèòåëüíûå óñëîâèÿ, ÷òîáû ïîëíîñòüþ îõàðàêòåðèçîâàòü íàèëó÷øåå ñïëàéí-ïðèáëèæåíèå, â íàñòîÿùåå âðåìÿ íåèçâåñòíî [14]. Èññëåäîâàíèÿ â ýòîì íàïðàâëåíèè ïðîäîëæàþòñÿ (ñì., íàïðèìåð, [15]). 122 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 Äëÿ ïðàêòè÷åñêîãî ïîñòðîåíèÿ ñïëàéíà íàèëó÷øåãî ïðèáëèæåíèÿ ñî ñâî- áîäíûìè óçëàìè íåîáõîäèìî íàéòè îïòèìàëüíûé âåêòîð óçëîâ T t tr * * *( , , )� 1 � , íà êîòîðîì äîñòèãàåòñÿ ìèíèìóì â çàäà÷å (3). Ïîãðåøíîñòü àïïðîêñèìàöèè ñïëàéíîì ñ óçëàìè T * îáîçíà÷èì � �� ( )*T . Ýòî íàèìåíüøàÿ ïîãðåøíîñòü ïðè- áëèæåíèÿ ôóíêöèè f â ðàâíîìåðíîé íîðìå ñðåäè âñåõ ñïëàéíîâ s S n r� , . Ïðè íåáîëüøèõ r äëÿ ïîèñêà T t tr * * *( , , )� 1 � ìîæíî ïðèìåíÿòü îáùèå ìå- òîäû ìèíèìèçàöèè ôóíêöèé ìíîãèõ ïåðåìåííûõ. Íî ñ ðîñòîì ÷èñëà óçëîâ óâå- ëè÷èâàåòñÿ ðàçìåðíîñòü ïðîñòðàíñòâà ïîèñêà è âîçíèêàþò ñåðüåçíûå òðóäíîñòè ÷èñëåííîãî äèôôåðåíöèðîâàíèÿ. Êðîìå òîãî, ïîãðåøíîñòü �( )T îáû÷íî íå ÷óâñòâè- òåëüíà ê ìàëûì èçìåíåíèÿì â T âáëèçè T * [8]. Âñå ýòî îãðàíè÷èâàåò ïðèìåíåíèå îáùèõ ìåòîäîâ. Áîëåå ýôôåêòèâíûìè ÿâëÿþòñÿ äâà ñïåöèàëüíûõ ìåòîäà: ñåêóùåé ïëîñêîñòè (secant plane method) è óïðîùåííûé ìåòîä Íüþòîíà (simplified Newton’s method), ó÷èòûâàþùèå õàðàêòåðèñòè÷åñêèå ñâîéñòâà íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëè- æåíèÿ [8]. Îäíàêî ñõîäèìîñòü ìåòîäîâ òèïà Íüþòîíà îáåñïå÷èâàåòñÿ ëèøü â ñëó÷àå, åñëè îíè ñòàðòóþò ñ ïî÷òè îïòèìàëüíûõ óçëîâ [16]. Ïîñêîëüêó â îáùåì ñëó÷àå òàêèå óçëû íåèçâåñòíû, òî ñõîäèìîñòü ìåòîäîâ íå ãàðàíòèðóåòñÿ. Íî äàæå åñëè îíè ñõîäÿòñÿ, òî â îáùåì ñëó÷àå ñòðîÿòñÿ ëîêàëüíûå íàèëó÷øèå ïðèáëèæåíèÿ.  [16] ïðåäëîæåí àëãîðèòì, ñõîäÿùèéñÿ ñ ïðîèçâîëüíûõ óçëîâ, íàïðèìåð ðàâíîîòñòîÿùèõ, è ïîçâîëÿþùèé ïîëó÷àòü äîñòàòî÷íî õîðîøóþ ãëîáàëüíóþ àï- ïðîêñèìàöèþ. Îí ñîñòîèò èç äâóõ ýòàïîâ: âíà÷àëå âû÷èñëÿþòñÿ îïòèìàëüíûå óçëû �T êóñî÷íî-ìíîãî÷ëåííîãî ïðèáëèæåíèÿ (òàê íàçûâàåìàÿ ñåãìåíòíàÿ àï- ïðîêñèìàöèÿ, â êîòîðîé íåïðåðûâíîñòü àïïðîêñèìàíòà íå òðåáóåòñÿ) ñ èñïîëüçî- âàíèåì ìåòîäà regula falsi, çàòåì óçëû �T ôèêñèðóþòñÿ è ñòðîèòñÿ ñïëàéí íåîáõî- äèìîé ãëàäêîñòè ñ ïîìîùüþ àíàëîãà àëãîðèòìà Ðåìåçà. Òàê êàê � � �( � ) ( � )T T� � , ãäå �( � )T — ïîãðåøíîñòü êóñî÷íî-ìíîãî÷ëåííîãî ïðèáëèæåíèÿ ñ îïòèìàëüíûìè óçëàìè, òî ïîãðåøíîñòü | ( � )|� �� T ìåíüøå, ÷åì çíà÷åíèå | ( � ) ( � )|� �T T� , êîòîðîå ìîæíî âû÷èñëèòü ñ ïîìîùüþ àëãîðèòìà [16]. Òàêèì îáðàçîì, â ñóùåñòâóþùèõ àëãîðèòìàõ äëÿ íàõîæäåíèÿ îïòèìàëüíûõ èëè áëèçêèõ ê íèì óçëîâ, êàê ïðàâèëî, íåîáõîäèìî ðåøàòü òðàíñöåíäåíòíûå óðàâíåíèÿ, ñèñòåìû òàêèõ óðàâíåíèé èëè ñèñòåìû äèôôåðåíöèàëüíûõ óðàâíå- íèé, ÷òî ñîçäàåò îïðåäåëåííûå âû÷èñëèòåëüíûå ñëîæíîñòè. Ïîýòîìó àêòóàëüíà ðàçðàáîòêà íîâûõ ýôôåêòèâíûõ è áîëåå ïðîñòûõ â ðåàëèçàöèè àëãîðèòìîâ ðåøåíèÿ çàäà÷è (3). Äëÿ ïîèñêà îïòèìàëüíûõ óçëîâ ñïëàéíà (àíàëîãè÷íî ñëó÷àþ ñåãìåíòíîé àï- ïðîêñèìàöèè [17, 18]) ïðåäëàãàåòñÿ àäàïòèðîâàòü àëãîðèòì äèôôåðåíöèàëüíîé ýâîëþöèè (ÄÝ) [19]. Îí îòíîñèòñÿ ê ãðóïïå ýâîëþöèîííûõ àëãîðèòìîâ (ÝÀ) — ñîâðåìåííîãî ýôôåêòèâíîãî èíñòðóìåíòà ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷.  ÝÀ ñîçäàþòñÿ ïîïóëÿöèè èç ðåøåíèé, êîòîðûå â ðåçóëüòàòå ïðèìåíåíèÿ îïå- ðàòîðîâ ñêðåùèâàíèÿ, ìóòàöèè è ñåëåêöèè ïîñòîÿííî ìîäèôèöèðóþòñÿ. Ñ ðîñ- òîì ÷èñëà ïîêîëåíèé ðåøåíèÿ ñõîäÿòñÿ â íåêîòîðóþ òî÷êó ïðîñòðàíñòâà ðåøå- íèé, ÿâëÿþùóþñÿ ãëîáàëüíûì îïòèìóìîì. Àëãîðèòì ÄÝ — îäèí èç ëó÷øèõ ÝÀ, ñ åãî ïîìîùüþ ñòàáèëüíî îïðåäåëÿåòñÿ îïòèìóì ôóíêöèè çà ìèíèìàëüíîå âðå- ìÿ [19]. Êðîìå òîãî, îí ïðîñò â ðåàëèçàöèè è èñïîëüçîâàíèè (ñîäåðæèò ìàëî ïà- ðàìåòðîâ, òðåáóþùèõ íàñòðîéêè), ëåãêî ðàñïàðàëëåëèâàåòñÿ. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 123 ÀËÃÎÐÈÒÌ ÍÀÈËÓרÅÃÎ ÐÀÂÍÎÌÅÐÍÎÃÎ ÏÐÈÁËÈÆÅÍÈß ÑÏËÀÉÍÎÌ Ñ ÎÏÒÈÌÀËÜÍÛÌÈ ÓÇËÀÌÈ Ýâîëþöèîííûé ïðîöåññ â àëãîðèòìå ÄÝ íà÷èíàåòñÿ ñ ãåíåðàöèè ïîïóëÿöèè ñëó÷àéíûõ âåêòîðîâ, êîîðäèíàòàìè êîòîðûõ ÿâëÿþòñÿ âîçìîæíûå çíà÷åíèÿ óçëîâ ñïëàéíà. Äàëåå äëÿ êàæäîãî âåêòîðà, íàçûâàåìîãî áàçîâûì, ñ èñïîëüçî- âàíèåì òðåõ äðóãèõ ñëó÷àéíûõ âåêòîðîâ èç òîãî æå ïîêîëåíèÿ ñîçäàåòñÿ ìó- òàíòíûé âåêòîð. Íàä ïîñëåäíèì âûïîëíÿåòñÿ îïåðàöèÿ ñêðåùèâàíèÿ. Âåêòîð, ïîëó÷åííûé ïîñëå ñêðåùèâàíèÿ, íàçûâàåòñÿ ïðîáíûì.  íîâîå ïîêîëåíèå âêëþ÷àåòñÿ òîò âåêòîð — áàçîâûé èëè ïðîáíûé, çíà÷åíèå öåëåâîé ôóíêöèè (êðèòåðèÿ îïòèìèçàöèè) êîòîðîãî ìåíüøå. Ýâîëþöèîííûé ïðîöåññ çàêàí÷èâà- åòñÿ, åñëè âûïîëíÿåòñÿ îäíî èç òåðìèíàëüíûõ óñëîâèé (èñ÷åðïàíî ìàêñèìàëü- íîå ÷èñëî ïîêîëåíèé ïîïóëÿöèé è äð. [19]). Îïûò ïðèìåíåíèÿ ÝÀ äëÿ ðåøåíèÿ çàäà÷ àïïðîêñèìàöèè ôóíêöèé ïîêàçàë, ÷òî ïðè áîëüøîì ÷èñëå îïòèìèçèðóåìûõ ïàðàìåòðîâ èõ ðåçóëüòàòèâíîñòü óõóä- øàåòñÿ âñëåäñòâèå ñèëüíîãî óâåëè÷åíèÿ ðàçìåðà îáëàñòè ïîèñêà [20–22], õîòÿ è â ýòèõ ñëó÷àÿõ ìîæíî ïîëó÷èòü ïðèåìëåìûå ðåçóëüòàòû.  ïðåäëàãàåìîì àëãî- ðèòìå íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ ñïëàéíîì ñî ñâîáîäíûìè óçëàìè ÄÝ ïðèìåíÿåòñÿ òîëüêî äëÿ ïîèñêà îïòèìàëüíûõ óçëîâ T t tr * * *( , , )� 1 � , à êîýô- ôèöèåíòû ñïëàéíà a a an r0 1, , ,� � íàõîäÿòñÿ êàê ðåøåíèå çàäà÷è àïïðîêñèìàöèè ñïëàéíîì ñ ôèêñèðîâàííûìè óçëàìè (2). Ýòî ïîçâîëÿåò ïðåîäîëåòü âû÷èñëèòåëü- íûå òðóäíîñòè, âûçâàííûå áîëüøîé ðàçìåðíîñòüþ, â ñëó÷àå îäíîâðåìåííîãî ïîèñêà è óçëîâ, è êîýôôèöèåíòîâ ñïëàéíà. Äàëåå ïðèâåäåíà âû÷èñëèòåëüíàÿ ñõåìà àëãîðèòìà íàèëó÷øåãî ðàâíîìåðíî- ãî ïðèáëèæåíèÿ ôóíêöèè ïîëèíîìèàëüíûì ñïëàéíîì ñî ñâîáîäíûìè óçëàìè, â êîòîðîì äëÿ ïîèñêà îïòèìàëüíûõ óçëîâ ïðèìåíÿåòñÿ ÄÝ. 1. Óñòàíàâëèâàåòñÿ íîìåð ïîêîëåíèÿ G � 0 è ñîçäàåòñÿ ïîïóëÿöèÿ PG � � { }T TG NP G1, ,, ,� , ñîñòîÿùàÿ èç âåêòîðîâ T t ti G i G i r G, , , , ,( , , )� 1 � , i NP�1, ,� , ãäå NP — ðàçìåð ïîïóëÿöèè. Êîîðäèíàòû âåêòîðîâ âû÷èñëÿþòñÿ ïî ôîðìóëå ti j G, , , ) ( )� � �rand (0 1 � � , j r�1, ,� , (4) ãäå rand ( , )0 1 — ñëó÷àéíîå ÷èñëî èç èíòåðâàëà ( , )0 1 . 2. Äëÿ êàæäîãî âåêòîðà T t ti G i G i r G, , , , ,( , , )� 1 � âû÷èñëÿåòñÿ çíà÷åíèå öåëå- âîé ôóíêöèè F Ti G( ), , ðàâíîå ïîãðåøíîñòè íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæå- íèÿ çàäàííîé ôóíêöèè f ñïëàéíîì s ñ óçëàìè t ti G i r G, , , ,, ,1 � : F T Ti G i G( ) ( ), ,� � . Äëÿ íàõîæäåíèÿ âåëè÷èíû �( ),Ti G ïðèìåíÿåòñÿ àëãîðèòì ÷åáûøåâñêîé àï- ïðîêñèìàöèè ïîëèíîìèàëüíûìè ñïëàéíàìè ñòåïåíè n äåôåêòà k �1 ñ ôèêñèðî- âàííûìè óçëàìè [9], â êîòîðîì èñïîëüçóåòñÿ ñâåäåíèå ê çàäà÷å ëèíåéíîãî ïðî- ãðàììèðîâàíèÿ ñ ãëàâíîé äâîéñòâåííîé ìàêñèìóì-çàäà÷åé çàìåíîé ïðîìåæóòêà àïïðîêñèìàöèè [ , ]� � íåêîòîðîé (ðàâíîìåðíîé èëè íåðàâíîìåðíîé) ñåòêîé D x x xm m� �{ }1 2, , , [ , ]� � � , ãäå m n r � �1. 3. Äëÿ êàæäîãî áàçîâîãî âåêòîðà Ti G, , i NP�1, ,� , îïðåäåëÿåòñÿ ìóòàíòíûé âåêòîð V v vi G i G i r G, , , , ,( , , )� 1 � ïî ôîðìóëå V T FM T Ti G b G c G d G, , , ,( )� � � � , (5) ãäå b ñ, è d — ñëó÷àéíûå öåëûå ÷èñëà èç ïðîìåæóòêà [ , ]1 NP , b c d i� � � , FM — çàäàííàÿ ïîëîæèòåëüíàÿ âåùåñòâåííàÿ êîíñòàíòà èç èíòåðâàëà ( , ]0 2 , êîòî- ðàÿ íàçûâàåòñÿ ñèëîé ìóòàöèè è îïðåäåëÿåò àìïëèòóäó âîçìóùåíèé, âíîñèìûõ â âåêòîð Tb G, âíåøíèì øóìîì. Åñëè êàêàÿ-ëèáî èç êîîðäèíàò âåêòîðà Vi G, âû- 124 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 õîäèò çà ãðàíèöû ïðîìåæóòêà [ , ]� � , òî ñ ïîìîùüþ ãåíåðàòîðà ñëó÷àéíûõ ÷è- ñåë âûáèðàþòñÿ íîâûå çíà÷åíèÿ èíäåêñîâ b ñ, , d è ïî ôîðìóëå (5) âûïîëíÿåò- ñÿ ïåðåñ÷åò âåêòîðà Vi G, . 4. Âûïîëíÿåòñÿ îïåðàöèÿ ñêðåùèâàíèÿ. Âû÷èñëÿþòñÿ êîîðäèíàòû ïðîáíîãî âåêòîðà U u ui G i G i r G, , , , ,( , , )� 1 � , i NP�1, ,� , ïî ôîðìóëå u v CR j j t i j G i j G i j G , , , , , , , , , � � � �åñëè rand (0 1) â ïð rand îòèâíîì ñëó àå� , � � � j r�1, ,� , (6) ãäå jrand — ñëó÷àéíîå öåëîå ÷èñëî èç äèàïàçîíà [ , ]1 r , CR — çàäàííàÿ âåðîÿò- íîñòü ñêðåùèâàíèÿ, ñ êîòîðîé ïðîáíûé âåêòîð U i G, óíàñëåäóåò èñêàæåííûé ìóòàöèåé ãåíåòè÷åñêèé ïðèçíàê îò âåêòîðà Tb G, . 5. Âû÷èñëÿåòñÿ çíà÷åíèå öåëåâîé ôóíêöèè ïðîáíîãî âåêòîðà F U i G( ), . 6. Äëÿ âêëþ÷åíèÿ â íîâîå ïîêîëåíèå ñ íîìåðîì G �1 âûáèðàåòñÿ òîò èç âåê- òîðîâ U i G, è Ti G, , çíà÷åíèå öåëåâîé ôóíêöèè F êîòîðîãî ìåíüøå T U F U F T T i G i G i G i G i G , , , , , , � � � 1 åñëè ( ) ( ), â ïðîòèâíîì ñëó àå� . � � � 7. Åñëè âûïîëíÿåòñÿ îäíî èç òåðìèíàëüíûõ óñëîâèé: èñ÷åðïàíî ìàêñèìàëü- íîå ÷èñëî ïîêîëåíèé ïîïóëÿöèè Gmax , îòíîñèòåëüíûé ðàçáðîñ çíà÷åíèé öåëåâîé ôóíêöèè â ïîïóëÿöèè ìåíüøå çàäàííîé âåëè÷èíû � (óñëîâèå ñòàãíàöèè ýâîëþöèîííîãî ïðîöåññà) max ( ) min ( ) min , , , , , , , ,i NP i G i NP i G i N F T F T � � � � � � 1 1 1� � � � P i GF T( ), , òî äëÿ ëó÷øåãî âåêòîðà óçëîâ èç ïîñëåäíåãî ïîêîëåíèÿ âû÷èñëÿþòñÿ êîýôôè- öèåíòû ñïëàéíà íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ è çàâåðøàåòñÿ ðàáîòà àëãîðèòìà. Ïî óìîë÷àíèþ ïîëàãàåòñÿ Gmax � 200, � � �10 4 . Åñëè íè îäíî èç ïåðå÷èñëåííûõ óñëîâèé íå âûïîëíÿåòñÿ, òî îñóùåñòâëÿåòñÿ ïåðåõîä ê ï. 3. Çàìå÷àíèå 1. Äëÿ êîððåêòíîé ðàáîòû àëãîðèòìà â ïï. 1, 3 è 4 ïîñëå âû÷èñ- ëåíèé ñîîòâåòñòâåííî ïî ôîðìóëàì (4)–(6) íåîáõîäèìî âûïîëíÿòü ïðîöåäóðó óïîðÿäî÷èâàíèÿ êîîðäèíàò âåêòîðîâ ïî âîçðàñòàíèþ. Çàìå÷àíèå 2. Àëãîðèòì ìîæíî èñïîëüçîâàòü íå òîëüêî äëÿ ñïëàéíîâ ñòåïåíè n äåôåêòà k �1, íî è äëÿ àïïðîêñèìàöèè ñïëàéíàìè ïðîèçâîëüíîãî äåôåêòà 0 � �k n. Äëÿ ýòîãî â àëãîðèòìå [9], êîòîðûé ïðèìåíÿåòñÿ äëÿ âû÷èñëåíèÿ çíà÷åíèé öåëåâîé ôóíêöèè, íåîáõîäèìî âíåñòè ñîîòâåòñòâóþùèå èçìåíåíèÿ â ïðîöåäóðó ôîðìèðîâà- íèÿ íà÷àëüíîé ñèìïëåêñ-òàáëèöû çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Ðàçìåð ïîïóëÿöèè NP, ñèëà ìóòàöèè FM è âåðîÿòíîñòü ñêðåùèâàíèÿ CR ÿâ- ëÿþòñÿ ïàðàìåòðàìè íàñòðîéêè àëãîðèòìà ÄÝ, è âûáîð èõ çíà÷åíèé â áîëüøîé ñòåïåíè çàâèñèò îò ðåøàåìîé çàäà÷è [19]. Ïî ðåçóëüòàòàì âûïîëíåííîãî èññëå- äîâàíèÿ äëÿ ïîèñêà îïòèìàëüíûõ óçëîâ ñïëàéíà ðåêîìåíäóþòñÿ ñëåäóþùèå íà- ñòðîéêè: 5 10r NP r� � , 0 4 0 5. .� �FM , 0 9 1. � �CR . Îòìåòèì, ÷òî ââèäó ñòîõàñ- òè÷åñêîãî õàðàêòåðà àëãîðèòìà ÄÝ äëÿ ïîëó÷åíèÿ ïðèåìëåìîãî ïî òî÷íîñòè ðå- øåíèÿ àëãîðèòì íóæíî âûïîëíèòü íåñêîëüêî ðàç.  ÷àñòíîñòè, ïðè ïðîâåäåíèè âû÷èñëèòåëüíîãî ýêñïåðèìåíòà âûïîëíÿëîñü 10 çàïóñêîâ àëãîðèòìà. ÐÅÇÓËÜÒÀÒÛ ÂÛ×ÈÑËÈÒÅËÜÍÎÃÎ ÝÊÑÏÅÐÈÌÅÍÒÀ Äëÿ ïðîâåðêè ýôôåêòèâíîñòè ïðåäëîæåííîãî àëãîðèòìà âûïîëíåí âû÷èñëè- òåëüíûé ýêñïåðèìåíò ïî ïîëó÷åíèþ íàèëó÷øèõ ðàâíîìåðíûõ ïðèáëèæåíèé ðÿäà ôóíêöèé ñïëàéíàìè ðàçëè÷íîé ñòåïåíè n è ñ ðàçíûì êîëè÷åñòâîì óçëîâ r.  òàáë. 1 è 2 ïðèâåäåíû ðåçóëüòàòû àïïðîêñèìàöèè íà îòðåçêå [ , ]0 1 äëÿ ôóíê- ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 125 öèé f x x1 11( ) ( )� � � è f x x2 ( ) � ñîîòâåòñòâåííî. Îòìåòèì, ÷òî ðåçóëüòàòû äëÿ ôóíêöèè f x x2 ( ) � ïðàêòè÷åñêè ñîâïàäàþò ñ èçâåñòíûìè [8] ðåçóëüòàòà- ìè, ïîëó÷åííûìè ïî ìåòîäó ñåêóùåé ïëîñêîñòè è óïðîùåííîìó ìåòîäó Íüþ- òîíà. Ñðåäíåå ÷èñëî ïîêîëåíèé, íåîáõîäèìûõ äëÿ íàõîæäåíèÿ îïòèìàëüíûõ óçëîâ ñ ïîìîùüþ àëãîðèòìà ÄÝ, â ñëó÷àå ôóíêöèè f x x1 11( ) ( )� � � ðàâíî 20, 35, 60 è 87 ïðè r �1 2 3 4, , , ñîîòâåòñòâåííî, à â ñëó÷àå ôóíêöèè f x x2 ( ) � — 17, 38 è 58 ïðè r �1, 2 è 3 ñîîòâåòñòâåííî.  òàáë. 3 ïðèâåäåíû ðåçóëüòàòû àïïðîêñèìàöèè ôóíêöèé êóáè÷åñêèìè ñïëàéíàìè ñ òðåìÿ óçëàìè. Äëÿ ñðàâíåíèÿ òî÷íîñòè ïðèáëèæåíèé ñïëàéíàìè ñ ðàçëè÷íûìè óçëàìè äëÿ ðÿäà ôóíêöèé èñïîëüçóþòñÿ ñëåäóþùèå îáîçíà÷å- íèÿ: � — ïîãðåøíîñòü íàèëó÷øåé ðàâíîìåðíîé àïïðîêñèìàöèè êóáè÷åñêèì 126 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 Êîëè÷åñòâî óçëîâ, r Ñïëàéí ñòåïåíè n n � 2 n � 3 n � 4 0 � � 0 06764. � � 0 04598. � � 0 03471. 1 � � 0 01916. t1 0 0590* .� � � 0 01223. t1 0 0395* .� � � 0 00894. t1 0 0295* .� 2 � � 0 00823. t1 0 0109* .� , t2 * .� 0 1523 � � 0 00494. t1 0 0064* .� , t2 * .� 0 1075 � � 0 00349. t1 0 0045* .� , t2 * .� 0 0823 3 � � 0 00435. t1 0 0031* .� , t2 * .� 0 0414, t3 * .� 0 2381 � � 0 00243. t1 0 0016* .� , t2 * .� 0 0261, t3 * .� 0 1747 � � 0 00165. t1 0 0010* .� , t2 * .� 0 0185, t3 * .� 0 1357 Ò à á ë è ö à 2 . Àïïðîêñèìàöèÿ ôóíêöèè f x x2 ( ) � íà îòðåçêå [ , ]0 1 Êîëè÷åñòâî óçëîâ, r Ñïëàéí ñòåïåíè n n � 3 n � 4 n � 5 0 � � � �1 263 10 3. � � � �2 166 10 4. � � � �3 717 10 5. 1 � � � �1 494 10 4. t1 0 3895* .� � � � �2 063 10 5. t1 0 3935* .� � � � �2 972 10 6. t1 0 3965* .� 2 � � � �3 750 10 5. t1 0 2560* .� , t2 * .� 0 5397 � � � �4 202 10 6. t1 0 2704* .� , t2 * .� 0 5352 � � � �5 088 10 7. t1 0 27996* . ,� t2 * .� 0 5291 3 � � � �1 345 10 5. t1 0 1938* .� , t2 * .� 0 3921, t3 * .� 0 6332 � � � �1 259 10 6. t1 0 2059* .� , t2 * .� 0 3960, t3 * .� 0 6234 � � � �1 303 10 7. , t1 0 2165* .� 0, t2 * .� 0 3988, t3 * .� 0 6139 4 � � � �5 952 10 6. t1 0 1549* .� , t2 * .� 0 3070, t3 * .� 0 4850, t4 * .� 0 6944 � � � �4 770 10 7. t1 0 1662* . ,� t2 * .� 0 3141, t3 * . ,� 0 4851 t4 * .� 0 6835 � � � �4 296 10 8. t1 0 1764* . ,� t2 * .� 0 3199 , t3 * . ,� 0 4840 t4 * .� 0 6729 Ò à á ë è ö à 1 . Àïïðîêñèìàöèÿ ôóíêöèè f x x1 11( ) ( )� � � íà îòðåçêå [ , ]0 1 Ôóíêöèÿ � �( � )T �( ~ )T f x x1 11( ) ( )� � � , x �[ , ]0 1 1 345 10 5. � � 2 039 10 5. � � 3 328 10 5. � � f x x2 ( ) � , x �[ , ]0 1 2 43 10 3. � � 3 52 10 3. � � 2 724 10 2. � � f x ex 3 ( ) � , x �[ , ]0 1 5 716 10 6. � � 8 487 10 6. � � 9 524 10 6. � � f x x4 2 11( ) ( )� � � , x � �[ , ]5 5 1 509 10 2. � � 5 112 10 2. � � 1 1421 10 1. � � Ò à á ë è ö à 3 . Àïïðîêñèìàöèÿ ôóíêöèé êóáè÷åñêèìè ñïëàéíàìè ñ òðåìÿ óçëàìè ñïëàéíîì ñ îïòèìàëüíûìè óçëàìè T * , íàéäåííûìè ñ ïîìîùüþ àëãîðèòìà ÄÝ; �( � )T — ïîãðåøíîñòü ðàâíîìåðíîãî ïðèáëèæåíèÿ ñïëàéíîì, ãäå â êà÷åñòâå óçëîâ âûáðàíû, êàê ïðåäëîæåíî â [16], îïòèìàëüíûå óçëû �T ñåãìåíòíîé àïïðîêñèìàöèè (äëÿ ðàñ÷åòîâ ïîñëåäîâàòåëüíî ïðèìåíÿëèñü àëãîðèòìû èç [17] è [9]); �( ~ )T — ïî- ãðåøíîñòü ðàâíîìåðíîãî ïðèáëèæåíèÿ ñïëàéíîì ñ ðàâíîîòñòîÿùèìè óçëàìè ~ T (äëÿ ðàñ÷åòîâ ïðèìåíÿëñÿ àëãîðèòì èç [9]). ÇÀÊËÞ×ÅÍÈÅ Â ñòàòüå ïðåäëîæåí àëãîðèòì íàèëó÷øåãî ðàâíîìåðíîãî ïðèáëèæåíèÿ ïîëèíî- ìèàëüíûì ñïëàéíîì ñ îïòèìàëüíûìè óçëàìè. Ýòîò ñïëàéí èìååò íàèìåíüøóþ ïîãðåøíîñòü àïïðîêñèìàöèè ôóíêöèè ñðåäè âñåõ ñïëàéíîâ òîé æå ñòåïåíè è ñ òàêèì æå êîëè÷åñòâîì óçëîâ. Äëÿ ïîèñêà îïòèìàëüíûõ óçëîâ èñïîëüçóåòñÿ ÄÝ — îäèí èç ëó÷øèõ ñòîõàñòè÷åñêèõ àëãîðèòìîâ, ñòàáèëüíî íàõîäÿùèé ãëî- áàëüíûé îïòèìóì ôóíêöèè çà ìèíèìàëüíîå âðåìÿ. Ê ïðåèìóùåñòâàì ÄÝ ìîæ- íî îòíåñòè âûñîêóþ òî÷íîñòü îïðåäåëåíèÿ îïòèìàëüíûõ óçëîâ, ïðîñòîòó ïðî- ãðàììíîé ðåàëèçàöèè è èñïîëüçîâàíèÿ (ñîäåðæèò ìàëî ïàðàìåòðîâ íàñòðîéêè, òðåáóþùèõ ïîäáîðà), ÷òî ïîäòâåðæäåíî ðåçóëüòàòàìè âû÷èñëèòåëüíîãî ýêñïå- ðèìåíòà. Ïðåäëîæåííûé ïîäõîä ñ èñïîëüçîâàíèåì ÄÝ äëÿ ïîèñêà îïòèìàëü- íûõ óçëîâ ìîæíî ïðèìåíÿòü è â ñëó÷àå ñïëàéíîâ íàèëó÷øåãî êâàäðàòè÷íîãî ïðèáëèæåíèÿ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ñòå÷êèí Ñ.Á., Ñóááîòèí Þ.Í. Ñïëàéíû â âû÷èñëèòåëüíîé ìàòåìàòèêå. Ìîñêâà: Íàóêà, 1976. 248 ñ. 2. Áåðäûøåâ Â.È., Ïåòðàê Ë.Â. Àïïðîêñèìàöèÿ ôóíêöèé, ñæàòèå ÷èñëåííîé èíôîðìàöèè, ïðè- ëîæåíèÿ. Åêàòåðèíáóðã: ÓðÎ ÐÀÍ, 1999. 297 ñ. 3. Vakal E.S., Kivva S.L., Mistetskii G.E., Stelya O.B. Solution method for nonlinear parabolic equations. Journal of Mathematical Sciences. 1991. Vol. 54, N 2. P. 781–786. 4. Ïîïîâ Á.À. Ðàâíîìåðíîå ïðèáëèæåíèå ñïëàéíàìè. Êèåâ: Íàóê. äóìêà, 1989. 272 ñ. 5. Ìàëà÷³âñüêèé Ï.Ñ., Ñêîïåöüêèé Â.Â. Íåïåðåðâíå é ãëàäêå ì³í³ìàêñíå ñïëàéí-íàáëèæåííÿ. Êè¿â: Íàóê. äóìêà, 2013. 270 ñ. 6. Êîðíåé÷óê Í.Ï. Òî÷íûå êîíñòàíòû â òåîðèè ïðèáëèæåíèÿ. Ìîñêâà: Íàóêà, 1987. 424 ñ. 7. Barrodale J., Young A. A note on numerical procedures for approximation by spline functions. Comput. J. 1966. Vol. 9. P. 318–320. 8. Esch R.E., Eastman W.L. Computational methods for best spline function approximation. Journal of Approximation Theory. 1969. Vol. 2, N 1. P. 85–96. 9. Âàêàë Ë.Ï. Ïîáóäîâà íàéêðàùèõ ÷åáèøîâñüêèõ íàáëèæåíü ñïëàéíàìè. Øòó÷íèé ³íòåëåêò. 2017. ¹ 2. Ñ. 94–100. 10. Schumaker L.L. Some algorithms for the computation of interpolating and approximating spline functions. Theory and applications of spline functions. New York: Academic Press, 1969. P. 87–102. 11. Nu��rnberger G., Sommer M. A Remez type algorithm for spline functions. Numer. Math. 1983. Vol. 41, N 1. P. 117–146. 12. Ðåìåç Å.ß. Îñíîâû ÷èñëåííûõ ìåòîäîâ ÷åáûøåâñêîãî ïðèáëèæåíèÿ. Êèåâ: Íàóê. äóìêà, 1969. 623 ñ. 13. Schumaker L.L. Uniform approximation by chebyshev spline functions. II. Free knots. SIAM Journal of Numerical Analysis. 1968. Vol. 5, N 4. P. 647–656. 14. N��urnberger G. Bivariate segment approximation and free knot splines; research problems 96-4. Constructive Approximation. 1996. Vol. 12, N 4. P. 555–558. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3 127 15. Crouzeix J.P., Sukhorukova N., Ugon J. Characterization theorem for best polynomial spline approximation with free knots, variable degree and fixed tails. Journal of Optimization Theory and Applications. 2017. Vol. 172, N 3. P. 950–964. 16. Meinardus G., Nu��rnberger G., Sommer M., Strauss H. Algorithm for piecewise polynomials and splines with free knots. Math. of Computation. 1989. Vol. 53, N 187. P. 235–247. 17. Vakal L.P. Seeking optimal knots for segment approximation. Journal of Automation and Information Sciences. 2016. Vol. 48, N 11. P. 68–75. 18. Vakal L.P., Kalenchuk-Porkhanova A.A., Vakal E.S. Increasing the efficiency of Chebyshev segment fractional rational approximation. Cybernetics and Systems Analysis. 2017. Vol. 53, N 5. P. 759–765. 19. 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. 20. Âàêàë Ë.Ï. Ãåíåòè÷í³ àëãîðèòìè äëÿ ÷åáèøîâñüêî¿ àïðîêñèìàö³¿. Êîìï’þòåðí³ çàñîáè, ìå- ðåæ³ òà ñèñòåìè. 2013. ¹ 12. Ñ. 20–26. 21. Vakal L.P. Solving uniform nonlinear approximation problem using continuous genetic algorithm. Journal of Automation and Information Sciences. 2016. Vol. 48, N 6. P. 49–59. 22. Âàêàë Ë.Ï. Àïðîêñèìàö³ÿ ôóíêö³é áàãàòüîõ çì³ííèõ ³ç çàñòîñóâàííÿì àëãîðèòìó äèôå- ðåíö³àëüíî¿ åâîëþö³¿. Ìàòåìàòè÷í³ ìàøèíè ³ ñèñòåìè. 2017. ¹ 1. Ñ. 90–96. Íàä³éøëà äî ðåäàêö³¿ 26.06.2018. Ë.Ï. Âàêàë, ª.Ñ. Âàêàë ÀËÃÎÐÈÒÌ ÍÀÉÊÐÀÙί вÂÍÎ̲ÐÍί ÀÏÐÎÊÑÈÌÀÖ²¯ ÑÏËÀÉÍÀÌÈ Ç Â²ËÜÍÈÌÈ ÂÓÇËÀÌÈ Àíîòàö³ÿ. Çàïðîïîíîâàíî àëãîðèòì íàéêðàùîãî ð³âíîì³ðíîãî íàáëèæåííÿ ñïëàéíîì ç îïòèìàëüíèìè âóçëàìè. Äëÿ ïîøóêó îïòèìàëüíèõ âóçë³â çàñòî- ñîâàíî äèôåðåíö³àëüíó åâîëþö³þ — îäèí ç íàéêðàùèõ åâîëþö³éíèõ àëãî- ðèòì³â, ùî ñòàá³ëüíî çíàõîäèòü îïòèìóì ôóíêö³¿ çà ì³í³ìàëüíèé ÷àñ. Êîåô³ö³ºíòè ñïëàéíà âèçíà÷åíî ÿê ðîçâ’ÿçàííÿ çàäà÷³ ñïëàéí-àïðîêñèìàö³¿ ç ô³êñîâàíèìè âóçëàìè. Íàâåäåíî ðåçóëüòàòè îá÷èñëþâàëüíîãî åêñïåðèìåíòó. Êëþ÷îâ³ ñëîâà: íàéêðàùà ð³âíîì³ðíà àïðîêñèìàö³ÿ, ñïëàéí, îïòèìàëüí³ âóçëè, äèôåðåíö³àëüíà åâîëþö³ÿ. L.P. Vakal, E.S. Vakal ALGORITHM FOR BEST UNIFORM SPLINE APPROXIMATION WITH FREE KNOTS Abstract. An algorithm for best uniform spline approximation with free knots is presented in this paper. A differential evolution is used for finding the optimal knots. It is one of the best evolutionary algorithms which finds function’s global optimum in minimum time. Spline coefficients are computed as a solution of a spline-approximation problem with fixed knots. Results of the numerical experiment are given. Keywords: best uniform approximation, spline, optimal knots, differential evolution. Âàêàë Ëàðèñà Ïåòðîâíà, êàíäèäàò òåõí. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, Êèåâ, e-mail: lara.vakal@gmail.com. Âàêàë Åâãåíèé Ñåðãååâè÷, êàíäèäàò ôèç.-ìàò. íàóê, äîöåíò Êèåâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Òàðàñà Øåâ÷åíêî, e-mail: jvakal@gmail.com. 128 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 3
id nasplib_isofts_kiev_ua-123456789-180875
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1019-5262
language Russian
last_indexed 2025-11-30T14:55:20Z
publishDate 2019
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
record_format dspace
spelling Вакал, Л.П.
Вакал, Е.С.
2021-10-23T16:50:08Z
2021-10-23T16:50:08Z
2019
Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами / Л.П. Вакал, Е.С. Вакал // Кибернетика и системный анализ. — 2019. — Т. 56, № 3. — С. 121-128. — Бібліогр.: 22 назв. — рос.
1019-5262
https://nasplib.isofts.kiev.ua/handle/123456789/180875
519.6+004.02
Предложен алгоритм наилучшего равномерного приближения сплайном с оптимальными узлами. Для поиска оптимальных узлов использована дифференциальная эволюция один из лучших эволюционных алгоритмов, стабильно находящий глобальный оптимум функции за минимальное время. Коэффициенты сплайна определены как решение задачи сплайн-аппроксимации с фиксированными узлами. Приведены результаты вычислительного эксперимента.
Запропоновано алгоритм найкращого рівномірного наближення сплайном з оптимальними вузлами. Для пошуку оптимальних вузлів застосовано диференціальну еволюцію один з найкращих еволюційних алгоритмів, що стабільно знаходить оптимум функції за мінімальний час. Коефіцієнти сплайна визначено як розв’язання задачі сплайн-апроксимації з фіксованими вузлами. Наведено результати обчислювального експерименту.
An algorithm for best uniform spline approximation with free knots is presented in this paper. A differential evolution is used for finding the optimal knots. It is one of the best evolutionary algorithms which finds function’s global optimum in minimum time. Spline coefficients are computed as a solution of a spline-approximation problem with fixed knots. Results of the numerical experiment are given
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Програмно-технічні комплекси
Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
Алгоритм найкращої рівномірної апроксимації сплайнами з вільними вузлами
Algorithm for best uniform spline approximation with free knots
Article
published earlier
spellingShingle Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
Вакал, Л.П.
Вакал, Е.С.
Програмно-технічні комплекси
title Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
title_alt Алгоритм найкращої рівномірної апроксимації сплайнами з вільними вузлами
Algorithm for best uniform spline approximation with free knots
title_full Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
title_fullStr Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
title_full_unstemmed Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
title_short Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
title_sort алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
topic Програмно-технічні комплекси
topic_facet Програмно-технічні комплекси
url https://nasplib.isofts.kiev.ua/handle/123456789/180875
work_keys_str_mv AT vakallp algoritmnailučšeiravnomernoiapproksimaciisplainamisosvobodnymiuzlami
AT vakales algoritmnailučšeiravnomernoiapproksimaciisplainamisosvobodnymiuzlami
AT vakallp algoritmnaikraŝoírívnomírnoíaproksimacíísplainamizvílʹnimivuzlami
AT vakales algoritmnaikraŝoírívnomírnoíaproksimacíísplainamizvílʹnimivuzlami
AT vakallp algorithmforbestuniformsplineapproximationwithfreeknots
AT vakales algorithmforbestuniformsplineapproximationwithfreeknots