Алгоритм наилучшей равномерной аппроксимации сплайнами со свободными узлами
Предложен алгоритм наилучшего равномерного приближения сплайном с оптимальными узлами. Для поиска оптимальных узлов использована дифференциальная эволюция один из лучших эволюционных алгоритмов, стабильно находящий глобальный оптимум функции за минимальное время. Коэффициенты сплайна определены как...
Gespeichert in:
| 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 |