Поиск оптимальных узлов для сегментной аппроксимации

Запропоновано алгоритм диференціальної еволюції для пошуку оптимальних вузлів чебишовської (рівномірної) кусково-поліноміальної апроксимації. Наведено результати апроксимації за допомогою алгоритму. Виконано порівняння запропонованого алгоритму з детерміністичними алгоритмами сегментного наближення...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автор:	Вакал, Л.П.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Назва видання:	Проблемы управления и информатики
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/208268
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Поиск оптимальных узлов для сегментной аппроксимации / Л.П. Вакал // Проблемы управления и информатики. — 2016. — № 6. — С. 45-51. — Бібліогр.: 12 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208268
record_format	dspace
spelling	irk-123456789-2082682025-10-25T00:11:41Z Поиск оптимальных узлов для сегментной аппроксимации Пошук оптимальних вузлів для сегментної апроксимації Optimal knots searching for segment approximation Вакал, Л.П. Оптимальное управление и методы оптимизации Запропоновано алгоритм диференціальної еволюції для пошуку оптимальних вузлів чебишовської (рівномірної) кусково-поліноміальної апроксимації. Наведено результати апроксимації за допомогою алгоритму. Виконано порівняння запропонованого алгоритму з детерміністичними алгоритмами сегментного наближення многочленами та з неперервним генетичним алгоритмом. It is proposed a differential evolution algorithm of optimal knots searching for Chebyshev (uniform) piecewise-polynomial approximation. It is presented approximation results with using the algorithm. A comparision of this algorithm with deterministic algorithms of segment polynomial approximation and with continuous genetic algorithm is made. 2016 Article Поиск оптимальных узлов для сегментной аппроксимации / Л.П. Вакал // Проблемы управления и информатики. — 2016. — № 6. — С. 45-51. — Бібліогр.: 12 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208268 519.6+004.02 10.1615/JAutomatInfScien.v48.i11.60 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Вакал, Л.П. Поиск оптимальных узлов для сегментной аппроксимации Проблемы управления и информатики
description	Запропоновано алгоритм диференціальної еволюції для пошуку оптимальних вузлів чебишовської (рівномірної) кусково-поліноміальної апроксимації. Наведено результати апроксимації за допомогою алгоритму. Виконано порівняння запропонованого алгоритму з детерміністичними алгоритмами сегментного наближення многочленами та з неперервним генетичним алгоритмом.
format	Article
author	Вакал, Л.П.
author_facet	Вакал, Л.П.
author_sort	Вакал, Л.П.
title	Поиск оптимальных узлов для сегментной аппроксимации
title_short	Поиск оптимальных узлов для сегментной аппроксимации
title_full	Поиск оптимальных узлов для сегментной аппроксимации
title_fullStr	Поиск оптимальных узлов для сегментной аппроксимации
title_full_unstemmed	Поиск оптимальных узлов для сегментной аппроксимации
title_sort	поиск оптимальных узлов для сегментной аппроксимации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/208268
citation_txt	Поиск оптимальных узлов для сегментной аппроксимации / Л.П. Вакал // Проблемы управления и информатики. — 2016. — № 6. — С. 45-51. — Бібліогр.: 12 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT vakallp poiskoptimalʹnyhuzlovdlâsegmentnojapproksimacii AT vakallp pošukoptimalʹnihvuzlívdlâsegmentnoíaproksimacíí AT vakallp optimalknotssearchingforsegmentapproximation
first_indexed	2025-10-25T01:01:52Z
last_indexed	2025-10-26T02:03:52Z
_version_	1847008147734003712
fulltext	© Л.П. ВАКАЛ, 2016 Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 6 45 УДК 519.6+004.02 Л.П. Вакал ПОИСК ОПТИМАЛЬНЫХ УЗЛОВ ДЛЯ СЕГМЕНТНОЙ АППРОКСИМАЦИИ Введение При сегментной аппроксимации промежуток приближения разбивается на ряд подынтервалов (сегментов) и на каждом из них функция аппроксимируется некоторым аналитическим выражением (многочленом, дробно-рациональной функцией и др.). Непрерывность аппроксимирующей функции в узлах разбиения промежутка аппроксимации на сегменты в общем случае не требуется. Существует немало прикладных задач, например задачи геометрического моделирования плоских и пространственных объектов с кусочно-гладкими границами, сжатия численной информации, построения функциональных преобразователей и др. [13], в которых аппроксимирующая функция может быть разрывной — лишь бы погреш- ность приближения на всем промежутке была достаточно малой. Принципиально различается два случая сегментной аппроксимации: с фиксиро- ванными узлами разбиения на подынтервалы и со свободными узлами. Погрешность сегментного приближения намного меньше, если используются свободные узлы. В случае фиксированных узлов задача сегментной аппроксимации линейна, а в слу- чае свободных узлов — нелинейная задача многомерной оптимизации. В данной статье предлагается алгоритм чебышевского кусочно-многочленного приближения функций со свободными узлами, в котором для поиска оптимальных уз- лов используется метод дифференциальной эволюции (ДЭ). Он относится к группе эво- люционных алгоритмов, моделирующих базовые процессы биологической эволюции (отбор, мутацию и воспроизводство). Алгоритм ДЭ прост в реализации и исполь- зовании (содержит мало варьируемых параметров), легко распараллеливается. Постановка задачи Пусть )(xf — непрерывная на отрезке ],[  функция, r — натуральное число, n nxaxaaxP  10)( — многочлен степени не выше n , T — сово- купность разбиений }{ 10  rttt  отрезка ],[  на r сегментов ],[ 1 jj tt  ),1( rj  , где rttt ,,, 10  — узлы разбиения. Обозначим ),( 1 jj ttL  наилучшее чебышевское (равномерное) приближение функции )(xf многочле- нами степени n на сегменте ],[ 1 jj tt  )()(max)()(maxmin)( ][][ 1 11 xPxfxPxft,tL j t,txt,txP jj jjjj     . (1) Функция вида ]))([()()( 1 1 xttxxPxS jjj r j     ,       ,0,1 0,0 )( x x x (2) где каждый из многочленов )(xPj — многочлен наилучшего равномерного прибли- жения для функции )(xf на соответствующем сегменте ],[ 1 jj tt  , называется чебы- шевским кусочно-многочленным приближением для функции )(xf на отрезке ],[  . В общем случае функция )(xS является разрывной в узлах 11 ,, rtt  . 46 ISSN 0572-2691 Рассматривается случай чебышевской кусочно-многочленной аппрокси- мации со свободными узлами. Заданными считаются степень многочленов n и число сегментов r , но сами сегменты, образующие покрытие отрезка ],[  , не фиксируются. Положим ),(max)( 1 1 jj rj ttLL    . Разбиение  отрезка ],[  называется оптимальным, а его узлы * 1 * 0 ,,, rttt  — оптимальными узлами, если )(inf)( *   LL . (3) Для любой непрерывной на отрезке ],[  функции оптимальное разбиение существует, хотя может быть и неединственным [4, 5]. Задача сегментной аппрок- симации заключается в нахождении оптимального разбиения  и значения по- грешности аппроксимации )( L для этого разбиения. Эта погрешность будет минимальной для заданного числа сегментов r . Разбиение  называется разбиением с равными уклонениями, если ),(),( 11   jjjj ttLttL , 1,1  rj . (4) Известно [5], что для любой непрерывной на отрезке ],[  функции )(xf разбиение с равными уклонениями существует и является оптимальным (но оп- тимальное разбиение может и не быть разбиением с равными уклонениями). Ста- вится задача — найти для заданной функции )(xf разбиение с равными уклоне- ниями. Следует заметить, что если функция )(xf удовлетворяет требованиям ],[)( 1  nCxf , 0)()1(  xf n для ],[ x , то при выполнении условий (4) чебышевское кусочное приближение )(xS многочленами нечетной степени n будет непрерывным [5]. Разработан ряд алгоритмов чебышевской сегментной аппроксимации мно- гочленами со свободными узлами [58], в основе которых лежит требование выполнения условий оптимальности (4). Например, в [6] соотношения (4) рас- сматриваются как система трансцендентных уравнений относительно неиз- вестных 11 ,, rtt  ( ,0 t rt ), и задача сводится к решению системы ме- тодом Ньютона, сходимость которого напрямую зависит от начального выбора узлов. В данной статье для поиска разбиения с равными уклонениями и построе- ния соответствующего чебышевского кусочно-многочленного приближения с минимальной погрешностью для функции )(xf на отрезке ],[  предлага- ется подход, в котором неизвестные свободные узлы 11 ,, rtt  (узлы 0t и rt известны) находятся как решение задачи минимизации       11 11 11 ,0 ,1,1,),(),( min,),,( r jjjj r tt rjttLttL tt   с помощью метода дифференциальной эволюции. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 6 47 Алгоритм вычисления оптимальных узлов для сегментной аппроксимации Метод дифференциальной эволюции предназначен для нахождения глобаль- ного оптимума недифференцированных, нелинейных, мультимодальных функций многих переменных и принадлежит к прямым методам оптимизации, т.е. в ходе его работы требуется вычисление только значения целевой функций (критерия оптимизации), но не ее производных. Предложенный Р. Сторном и К. Прайсом [9] алгоритм ДЭ относится к классу стохастических алгоритмов (т.е. работает с использованием случайных чисел) и состоит из таких шагов. На первом шаге генерируется некоторое множество векторов (поколение популяции), представляющих собой возможные решения задачи оптимизации. Далее на каждой итерации алгоритма (эпохе эволюционного процесса) создается новое поколение. Для каждого вектора старого поколения, называемого базовым вектором (target vector), генерируется мутантный вектор (mutant vector) с использованием трех других случайных векторов и операций сложения и вычитания их координат. Затем над мутантным вектором выполняется операция скрещивания (crossover), в ходе которой некоторые его координаты замещаются координатами базового вектора. Полученный после скрещивания вектор называется пробным (trial vector). Если он оказывается лучше базового вектора (значение целевой функции улучшилось), то в новом поколении базовый вектор заменяется на пробный, в противном случае базовый вектор сохраняется в новом поколении. Такое правило отбора гарантирует неизменность размера популяции в процессе работы алгоритма. На каждой эпохе эволюционного про- цесса в целях контроля скорости поиска оптимального решения определяется лучший вектор поколения. Условиями окончания эволюционного процесса могут быть, например, достижение удовлетворительного значения критерия оптимизации, исчерпание заданного максимального числа поколений и др. В целом алгоритм ДЭ представляет собой одну из возможных «непрерыв- ных» модификаций генетического алгоритма. В то же время он имеет существен- ную особенность, во многом определяющую его свойства. В качестве источника шума при мутации в алгоритме ДЭ используется не внешний генератор случай- ных чисел, а «внутренний», реализованный как разность между случайно выбран- ными векторами текущей популяции. Благодаря этому алгоритм ДЭ обладает спо- собностью динамически моделировать особенности рельефа оптимизируемой функции, подстраивая под них распределение «встроенного» источника шума. Именно этим объясняется способность алгоритма быстро проходить сложные овраги, обеспечивая эффективность даже в случае сложного рельефа. Для вычисления оптимальных узлов и нахождения чебышевского кусочно- многочленного приближения с минимальной погрешностью предлагается следу- ющий алгоритм дифференциальной эволюции. 1. Генерируется начальное поколение векторов ),,( ,11 irii vvV   , Npi ,1 , где Np ― размер популяции (один из параметров настройки алгоритма). Коорди- наты каждого вектора — упорядоченные по возрастанию случайные числа из ин- тервала ),(  ),()1,0(rand jiv Npi ,1 , 1,1  rj , где )1,0(rand ― случайное число из интервала )1,0( . Заметим, что координата с индексом j соответствует узлу jt . 2. Для базового вектора iV ( Npi ,1 ) из старого поколения выбирается три случайных вектора dcb VVV ,, ( idcb  ) и генерируется мутантный вектор bV ~ по правилу )( ~ dcbb VVFmVV  , 48 ISSN 0572-2691 где Fm — некоторая положительная вещественная константа из интервала ]2,0[ , которая называется силой мутации и является параметром алгоритма. Сила мутации Fm определяет амплитуду возмущений, вносимых в вектор bV внешним шумом. 3. Задается вероятность скрещивания Cr (еще один параметр алгоритма ДЭ), с которой потомок iU наследует искаженный мутацией генетический признак от «родительского» вектора bV . Соответствующий признак от базового вектора iV (второго «родителя») наследуется с вероятностью )1( Cr . Далее вычисляются координаты пробного вектора iU по формуле        .1)rand(0,если, ,1)rand(0,если,~ rand rand jjCrv jjCrv u ij jb ij 4. Для включения в новое поколение выбирается тот из векторов iU и iV , значение целевой функции которого меньше. Такой оператор выбора гарантирует, что лучшее значение целевой функции не может быть пропущено, что приводит к быстрой сходимости алгоритма. Целевая функция F для каждого вектора вычисляется по формуле jj rj iVF    1 1 max)( , Npi ,1 , где ),( ,1 ijijj L   — погрешность наилучшей чебышевской многочленной аппроксимации (1) для функции )(xf на сегменте ],[ ,1 ijij vv  , rj ,1 (  i0 ,  ir ). Заметим, что выбор такой целевой функции обусловлен стремлением найти разбиение с равными уклонениями (погрешностями аппроксимации на сегмен- тах), так как в этом случае будет выполнено достаточное условие оптимальности (4). Для вычисления j ),1( rj  применяется алгоритм [10], реализующий вто- рой метод Ремеза [11]. Поскольку алгоритм предназначен для приближения функций, заданных на сетке, то каждый сегмент предварительно покрывается равномерной сеткой из m точек. 5. Алгоритм ДЭ завершает эволюционный процесс, если выполняется одно из условий: — значение целевой функции лучшего вектора в поколении меньше заданного  ; — исчерпано максимальное число поколений популяции maxp ; — происходит стагнация итерационного процесса, т.е. относительный раз- брос значений целевой функции в популяции меньше заданной величины  )(min)(min)(max ,1,1,1 i Npi i Npi i Npi VFVFVF   . В противном случае осуществляется переход к шагу 2. По умолчанию зада- ется 1210 , 200max p , 410 . 6. Для лучшего вектора узлов из последнего поколения, участвовавшего в эволюционном процессе, на каждом из сегментов вычисляются коэффициенты многочлена наилучшего приближения (1). Результатом работы алгоритма являет- ся кусочно-многочленный аппроксимант, который имеет наименьшую погреш- ность приближения функции )(xf среди всех аппроксимантов вида (2) с таким же числом сегментов r на отрезке ],[  . Следует заметить, что ввиду стохастического характера алгоритма ДЭ для получения приемлемого решения задачи следует выполнить алгоритм несколько раз. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 6 49 Анализ результатов вычислительных экспериментов Для проверки эффективности предложенного алгоритма ДЭ для поиска оп- тимальных узлов чебышевского кусочного приближения выполнена серия вычис- лительных экспериментов по аппроксимации функций многочленами разных сте- пеней и с различным числом узлов разбиения отрезка аппроксимации на сегмен- ты. Анализ полученных результатов свидетельствует о том, что с помощью алгоритма ДЭ удается найти более точные значения оптимальных узлов и постро- ить чебышевское кусочно-многочленное приближение с меньшей погрешностью, чем с помощью сложных детерминистических алгоритмов. В качестве иллюстрации рассмотрим аппроксимацию функции 12)1()(  xxf на отрезке ]5,5[ многочленами степеней 5,4,3n с числом сегментов 6,2r . Для вычисления оптимальных узлов и чебышевских кусочно- многочленных приближений применялся алгоритм ДЭ с такими настройками: размер популяции 50Np , сила мутации 4,0Fm , вероятность скрещивания 9,0Cr , количество точек сетки 501m , число запусков алгоритма равно десяти (зна- чения  , maxp ,  — по умолчанию). В табл. 1, где приведены полученные по ал- горитму ДЭ результаты, первое число в клетках таблицы означает погрешность сегментной аппроксимации j rj  1 max , второе — значение целевой функции, остальные числа — внутренние узлы (внешние узлы совпадают с концами отрез- ка аппроксимации). В табл. 1 приведены также результаты детерминистического алгоритма [7], для которого дополнительно вычислены максимальные значения разностей погрешностей аппроксимации на сегментах для сравнения со значени- ями целевой функции алгоритма ДЭ. Таблица 1 r Детерминистический алгоритм Алгоритм ДЭ 3n 4n 5n 3n 4n 5n 2 0,04476 0 0 0,0375 0 0 0,0215 0 0 0,047709 0 0 0,037547 0 0 0,037547 0 0 3 0,0142 1,510– 4 – 0,6745 0,6616 0,00265 3,510– 5 – 0,5643 0,7845 0,00137 1,210– 5 – 0,6738 0,6737 0,0141892 2,610– 12 – 0,667998 0,667998 0,0026042 6,610– 12 – 0,777154 0,777154 0,0013649 6,010– 12 – 0,674394 0,674394 4 0,00586 9,010– 5 – 1,2839 0 1,2839 0,000905 1,410– 7 – 1,4899 0 1,4899 0,000313 7,710– 6 – 1,1361 0 1,1361 0,0058119 1,510– 13 – 1,280404 0 1,280404 0,00090483 4,310– 13 – 1,489922 0 1,489922 0,00031280 8,310– 13 – 1,142365 0 1,142365 5 0,00286 1,610– 4 – 1,6614 – 0,4102 0,4018 1,6341 0,000466 7,110– 6 – 1,7745 – 0,5374 0,5399 1,7775 0,000103 1,610– 6 – 1,7225 – 0,4019 0,4102 1,7287 0,0027244 7,810– 12 – 1,656935 – 0,407128 0,407128 1,656935 0,00046049 8,710– 11 – 1,779121 – 0,539921 0,539921 1,779121 0,00010275 8,810– 12 – 1,725198 – 0,405822 0,405822 1,725198 6 0,000451 5,810– 6 – 2,4581 – 0,7826 0 0,7826 2,4581 0,000239 1,510– 6 – 2,0411 – 0,7452 0 0,7452 2,0411 4,4210– 5 2,710– 7 – 2,0329 – 0,7841 0 0,7841 2,0329 0,00044794 6,010– 13 – 2,455901 – 0,780985 0 0,780985 2,455901 0,00023846 7,910– 13 – 2,038807 – 0,744142 0 0,744142 2,038807 4,429610– 5 4,210– 13 – 2,032335 – 0,784319 0 0,784319 2,032335 Выполнено сравнение предложенного ДЭ и непрерывного генетического ал- горитма (ГА) по времени выполнения (в секундах) и числу итераций (поколений популяции). Как показывают данные табл. 2, где приведены усредненные резуль- 50 ISSN 0572-2691 таты сегментной аппроксимации для случая 3r , число итераций ГА меньше, чем алгоритма ДЭ, однако в ГА для нахождения оптимальных узлов требуется больше времени, чем в алгоритме ДЭ. В среднем время выполнения одной итера- ции в алгоритме ДЭ в два раза меньше, чем в ГА. Таблица 2 Np Генетический алгоритм Алгоритм ДЭ Число итераций Время выполнения, с Время одной итерации, с Число итераций Время выполнения, с Время одной итерации, с 20 37,1 0,9 0,024 66,3 0,8 0,012 30 51,3 1,7 0,033 56,7 1,0 0,018 40 49,9 2,2 0,044 52,8 1,1 0,021 50 37,2 2,1 0,056 49,3 1,4 0,028 60 36,6 2,3 0,063 52,3 1,7 0,033 70 33,9 2,5 0,074 53,4 2,1 0,039 Наименьшее время для нахождения решения затрачивается в алгоритме ДЭ при использовании популяций небольшого размера 30,20Np (см. табл. 2). В то же время в экспериментах установлено, что для малочисленных популяций за- вершение алгоритма происходит преимущественно вследствие выполнения условия стагнации итерационного процесса, например, для 30Np — в среднем в 41 % случаев при 3r и в 60 % случаев при 4r , а для 20Np — в 77 % и 98 % случаев соответственно. Это связано с тем, что малый размер популяции не соответствует сложности решаемой задачи, поскольку не обеспечивается достаточное разнообразие векторов для поиска оптимального решения. Поэтому в случае окончания алгоритма ДЭ по условию стагнации рекомендуется увеличить размер популяции, например вдвое, и произвести рестарт алгоритма. В экспериментах исследовалось также влияние на скорость сходимости алго- ритма ДЭ таких его параметров, как сила мутации Fm и вероятность скрещи- вания Cr . Сила мутации характеризует максимально возможное расстояние, на которое может расшириться область поиска оптимума по одной переменной за одно поколение популяции. Установлено, что с увеличением силы мутации Fm растет и число поколений, необходимых для завершения алгоритма. В то же время при малых значениях Fm высок процент выходов из алгоритма по условию стагнации итерационного процесса. Рекомендуемые значения для силы мутации лежат в диапазоне 6,04,0  Fm . Что касается вероятности скрещивания Cr , то с увеличением значения этого параметра число поколений, необходимое для нахождения оптимума целевой функции, уменьшается. И наоборот, при уменьшении значения Cr каждое новое поколение все меньше отличается от старого, поэтому для получения оптимального решения следует увеличить максимальное количе- ство поколений maxp . По результатам вычислительных экспериментов рекомен- дуется выбирать значения этого параметра в интервале 18,0 Cr . Заключение В настоящей работе представлен алгоритм дифференциальной эволюции, адаптированный для решения задачи поиска оптимальных узлов и соответствую- щего чебышевского кусочно-многочленного приближения. Алгоритм ДЭ — один из лучших стохастических алгоритмов, который стабильно находит оптимум функции за минимальное время благодаря способности динамически моделиро- вать особенности рельефа оптимизируемой функции. Он прост в реализации и ис- пользовании (содержит мало параметров, требующих подбора). Результаты вычислительных экспериментов показали, что алгоритм ДЭ поз- воляет точнее найти значения оптимальных узлов и получить меньшую погрешность чебышевской сегментной аппроксимации, чем сложные детерминистические алго- ритмы. Кроме того, время выполнения одной итерации алгоритма ДЭ в среднем в два раза меньше, чем непрерывного генетического алгоритма. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 6 51 Проанализировано влияние варьируемых параметров (размера популяции, силы мутации, вероятности скрещивания) на скорость сходимости алгоритма и сформулированы рекомендации по выбору их наилучших значений. Поскольку расположение оптимальных узлов для кусочно-многочленной ап- проксимации отображает особенности поведения приближаемой функции, то найденные с помощью алгоритма ДЭ узлы могут использоваться при аппрокси- мации функций многочленными сплайнами с фиксированными узлами (с необхо- димыми условиями гладкости в узлах). В этом случае оптимальные узлы следует считать фиксированными и по ним вычислять соответствующее сплайн- приближение. Л.П.Вакал ПОШУК ОПТИМАЛЬНИХ ВУЗЛІВ ДЛЯ СЕГМЕНТНОЇ АПРОКСИМАЦІЇ Запропоновано алгоритм диференціальної еволюції для пошуку оптимальних вузлів чебишовської (рівномірної) кусково-поліноміальної апроксимації. Наве- дено результати апроксимації за допомогою алгоритму. Виконано порівняння запропонованого алгоритму з детерміністичними алгоритмами сегментного на- ближення многочленами та з неперервним генетичним алгоритмом. L.P.Vakal OPTIMAL KNOTS SEARCHING FOR SEGMENT APPROXIMATION It is proposed a differential evolution algorithm of optimal knots searching for Che- byshev (uniform) piecewise-polynomial approximation. It is presented approximation results with using the algorithm. A comparision of this algorithm with deterministic algorithms of segment polynomial approximation and with continuous genetic algo- rithm is made. 1. Попов Б.А. Равномерное приближение сплайнами. — Киев : Наук. думка, 1989. — 272 с. 2. Исаев В.К., Плотников С.А. Обратная задача Чебышева и сплайны Чебышева // Труды Ма- тематического института РАН. — 1995. — 211. — С. 164–185. 3. Каленчук-Порханова А.А., Вакал Л.П. Наилучшая чебышевская аппроксимация для сжатия численной информации // Компьютерная математика. — 2009. — № 1. — С. 99–107. 4. Lawson C.L. Characteristic properties of the segmented rational minmax approximation problem // Numer. Math. — 1964. — 6, N 4. — P. 293–301. 5. Вершик А.М., Малоземов В.Н., Певный А.Б. Наилучшая кусочно-полиномиальная аппрок- симация // Сибирский математический журнал. — 1975. — 16, № 5. — С. 925–938. 6. Вопросы теории и элементы программного обеспечения минимаксных задач. — Л. : Изд-во Ленинградского университета, 1977. — 192 с. 7. Nürnberger G., Sommer M., Strauss H. An algorithm for segment approximation // Numer. Math. — 1986. — 48, N 4. — P. 463–477. 8. Meinardus G., Nürnberger G., Sommer M., Strauss H. Algorithm for piecewise polynomials and splines with free knots // Math. of Computation — 1989. — 53, N 187. — P. 235–247. 9. Storn R., Price K. Differential evolution — a simple and efficient heuristic for global optimiza- tion over continuous spaces // Journal of Global Optimization. — 1997. — 11. — P. 341–359. 10. Каленчук-Порханова А.А., Вакал Л.П. Аппарат аппроксимации в составе программного обеспечения суперкомпьютера с кластерной архитектурой // Искусственный интеллект. — 2009. — № 1. — С. 158–165. 11. Ремез Е.Я. Основы численных методов чебышевского приближения. — Киев : Наук. думка, 1969. — 623 с. 12. Vakal L.P. Solving uniform nonlinear approximation problem using continuous genetic algorithm // Journal of Automation and Information Sciences. ― 2016. ― 48, N 6. ― P. 49–59. Получено 06.07.2016 Статья представлена к публикации акад. НАН Украины А.В. Палагиным.

Поиск оптимальных узлов для сегментной аппроксимации

Репозитарії

Схожі ресурси