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

Запропоновано неперервний генетичний алгоритм для розв’язання задачі найкращої рівномірної нелінійної апроксимації функцій. За результатами обчислювальних експериментів виконано порівняння цього алгоритму зі спеціалізованими алгоритмами наближення. Наведено приклад застосування генетичного алгоритму...

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208168
record_format	dspace
spelling	irk-123456789-2081682025-10-21T00:08:37Z Решение задачи равномерной нелинейной аппроксимации с использованием непрерывного генетического алгоритма Розв’язання задачі рівномірної нелінійної апроксимації з використанням неперервного енетичного алгоритму Solving uniform nonlinear approximation problem using continuous genetic algorithm Вакал, Л.П. Оптимальное управление и методы оптимизации Запропоновано неперервний генетичний алгоритм для розв’язання задачі найкращої рівномірної нелінійної апроксимації функцій. За результатами обчислювальних експериментів виконано порівняння цього алгоритму зі спеціалізованими алгоритмами наближення. Наведено приклад застосування генетичного алгоритму для побудови нелінійної емпіричної функції двох змінних для наближення експериментальних даних щодо продуктивності фільтра. A continuous genetic algorithm for solving a problem of the best uniform nonlinear approximation is proposed. A comparison of this algorithm with specialized algorithms of approximation is made according to results of computational experiments. It is presented an example of constructing a nonlinear empiric function of two variables for approximation of experimental data on filter capacity with using the genetic algorithm. 2016 Article Решение задачи равномерной нелинейной аппроксимации с использованием непрерывного генетического алгоритма / Л.П. Вакал // Проблемы управления и информатики. — 2016. — № 3. — С. 17-27. — Бібліогр.: 25 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208168 519.6:004.021 10.1615/JAutomatInfScien.v48.i6.50 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/208168
citation_txt	Решение задачи равномерной нелинейной аппроксимации с использованием непрерывного генетического алгоритма / Л.П. Вакал // Проблемы управления и информатики. — 2016. — № 3. — С. 17-27. — Бібліогр.: 25 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT vakallp rešeniezadačiravnomernojnelinejnojapproksimaciisispolʹzovaniemnepreryvnogogenetičeskogoalgoritma AT vakallp rozvâzannâzadačírívnomírnoínelíníjnoíaproksimacíízvikoristannâmneperervnogoenetičnogoalgoritmu AT vakallp solvinguniformnonlinearapproximationproblemusingcontinuousgeneticalgorithm
first_indexed	2025-10-21T01:19:40Z
last_indexed	2025-10-22T01:08:52Z
_version_	1846642299363131392
fulltext	© Л.П. ВАКАЛ, 2016 Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 3 17 УДК 519.6:004.021 Л.П. Вакал РЕШЕНИЕ ЗАДАЧИ РАВНОМЕРНОЙ НЕЛИНЕЙНОЙ АППРОКСИМАЦИИ С ИСПОЛЬЗОВАНИЕМ НЕПРЕРЫВНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА Введение Задача наилучшего приближения (аппроксимации) функций состоит в сле- дующем: для заданной функции )(xf из некоторого класса 1K необходимо найти в более узком классе 2K функцию )(x так, чтобы уклонение (в некотором смысле) )(x от )(xf в заданной области было наименьшим. В теории равно- мерного (чебышевского) приближения уклонение определяется как максимум мо- дуля разности функций )(x и )(xf . Наилучшие равномерные приближения ис- пользуются в различных областях науки и техники, например, для вычисления на ЭВМ элементарных и специальных функций, построения функциональных пре- образователей, синтеза электрических цепей, представления контуров проекций деталей и кривых, задающих траекторию режущих инструментов в станках с про- граммным управлением и др. Большое практическое значение имеет применение равномерных приближений в задачах обработки экспериментальных данных для определения параметров эмпирических формул. Еще Лаплас сформулировал важ- ное в методологическом плане положение, что только приближения по критерию наилучшей равномерной аппроксимации позволяют строго ставить и решать во- прос о том, укладываются ли полученные экспериментальные данные в эмпири- ческую формулу того или другого типа [1]. В настоящее время на основе результатов теоретических исследований со- зданы достаточно эффективные методы и алгоритмы наилучшего равномерного приближения функций как одной, так и нескольких переменных с помощью линейных аппроксимантов (многочленов, тригонометрических и обобщенных по- линомов и т.п.) [1–3]. Что же касается приближения нелинейными аппроксиман- тами, то соответствующий алгоритмический арсенал значительно скромнее и поз- воляет аппроксимировать преимущественно функции одной переменной. В нелиней- ном случае система уравнений для вычисления параметров аппроксиманта также является нелинейной, и требуется специальное исследование существования ее решения для каждого класса аппроксимантов. Эффективные алгоритмы разрабо- таны, например, для приближения дробно-рациональными выражениями j j q j i i p i pq xbxaxR    00 /)( , (1) при этом основной подход заключается в распространении на дробно-рациональный случай алгоритмов Е.Я. Ремеза для аппроксимации многочленами [2, 4–9]. Исполь- зуются также различные приемы последовательной дифференциальной линеари- зации по параметрам [10], методы с применением аппарата линейного програм- мирования, например метод проб [11], метод дифференциальной коррекции и его модификации [12–16]. Кроме того, предложены конструктивные методы прибли- 18 ISSN 0572-2691 жения суммой многочлена и экспоненты, выражениями, являющимися функция- ми от многочлена, экспоненциально-степенными функциями и некоторыми дру- гими [9, 17, 18]. Каждый из алгоритмов нелинейной аппроксимации имеет свои преимуще- ства и недостатки, но в то же время общими для них являются: узкая специализа- ция (приближение аппроксимантами только определенного класса), сложность (требуют привлечения численных методов) и громоздкость. Поэтому актуальна задача создания универсальных и одновременно эффективных и достаточно про- стых алгоритмов нелинейной аппроксимации, в том числе и для приближения функций нескольких переменных. С этой точки зрения перспективным видится под- ход, основанный на применении для определения оптимальных параметров нели- нейных аппроксимантов генетических алгоритмов. Постановка задачи Задача наилучшей равномерной взвешенной (с весом 0)( xw ) аппроксимации заключается в нахождении для заданной на множестве точек D функции )(xf из некоторого класса 1K набора параметров ),,( 1 kaaA  функции );()( Axx  из класса ,2K удовлетворяющего требованиям минимакса )(min)();()(max   xwAxxf Dx . (2) При 1)( xw величина  называется погрешностью наилучшего абсолютного приближения, при )(1)( xfxw  — погрешностью наилучшего относительного приближения. Рассматриваем случай, когда функция )(xf задана на множестве точек сетки ],[},,{ 211  mxxD  , ,km  а параметры ia входят в аппрок- симант );( Ax нелинейно. Для нахождения наилучшего нелинейного аппроксиманта будем применять предложенный в [19] подход, который позволяет перейти от задачи наилучшей аппроксимации (2) к задаче оптимизации и дает возможность использовать для ее решения генетические алгоритмы. Генетические алгоритмы (ГА) — это совре- менные эффективные методы решения сложных многопараметрических задач оп- тимизации. Их идея состоит в компьютерной организации эволюционного про- цесса создания, модификации и отбора лучших решений (в терминах ГА — осо- бей) в целях появления новых, еще лучших вариантов решения задачи. Каждая особь в алгоритме кодируется в виде хромосомы, в генах которой хранится ин- формация о параметрах решения. Оценкой качества закодированного в хромосоме решения служит значение функции приспособленности. Генетические алгоритмы просты в реализации. Схема стандартного ГА со- стоит из таких основных шагов: 1) создание начального поколения популяции особей; 2) оценивание особей по значению функции приспособленности; 3) моделирование эволюционного процесса: отбор родителей, скрещива- ние для получения потомков, мутация потомков, формирование нового поко- ления популяции; 4) проверка условия окончания алгоритма, и в случае его невыполнения по- вторение эволюционного процесса с шага 2. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 3 19 Если условие завершения алгоритма выполнено, то проводится выбор наилучшей особи, т.е. особи с наименьшим значением функции приспособленно- сти. Конструирование алгоритма решения задачи При конструировании ГА для решения задачи наилучшей равномерной ап- проксимации (2) прежде всего необходимо определить количество и тип пере- менных, которые будут закодированы в генах хромосомы, способ кодирования (двоичное иди вещественное), а также задать функцию приспособленности. Обозна- чим jS хромосому, кодирующую j-ю особь, Nj ,1 , где N — количество особей в популяции. В ГА для решения задачи (2) каждая хромосома ),,( 1 j k j j ssS  будет включать k генов, где ген j is соответствует некоторому значению параметра ia аппроксиманта );( Ax . В качестве способа представления генетической информа- ции выберем вещественное кодирование, когда гены хромосомы представляются напрямую в виде вещественных чисел [20]. Алгоритмы такого типа называются непрерывными ГА или ГА с вещественным кодированием. В большинстве случаев эти алгоритмы выполняют поиск оптимума быстрее, чем ГА с двоичным коди- рованием (в частности из-за ненужности операций кодирования и декодирова- ния) [20]. Значения функции приспособленности или фитнесс-функции Fit, служащие оценкой качества закодированного в хромосоме jS решения задачи (2), будем вычислять по формуле )(),,;()(max)(Fit 1 1 i j k j ii mi j xwssxxfS    . (3) На следующем этапе конструирования алгоритма необходимо определить наилучшие для решения задачи (2) генетические операторы (скрещивания и мута- ции), оператор выбора родительских особей для скрещивания и стратегию фор- мирования нового поколения. Следует заметить, что операторы ГА, как правило, определяются методом проб и ошибок на основе анализа получаемых результатов. Начнем с выбора оператора скрещивания (рекомбинации), который является ключевым оператором генетических алгоритмов, определяющим их эффектив- ность. В непрерывных ГА для создания потомков у родительской пары ),,( 11 11 kssS  и ),,( 22 12 kssS  могут использоваться различные операторы рекомбинации или кроссоверы [21, 22]. 1. Смешанный кросcовер (blend, BLX crossover): создается один потомок ),,( 1 kccC  , у которого значение гена ,ic ki ,1 , — случайное число из ин- тервала ],[ maxmin  pp , где ),min( 21 min ii ssp  , ),max( 21 max ii ssp  , minmax pp  . 2. Плоский кроссовер (flat crossover): генерируется один потомок ),,( 1 kccC  , где ic , ki ,1 , — случайное число из интервала ],[ 21 ii ss . 3. Промежуточная рекомбинация (intermediate recombination): генерируются по- томки ),,( 11 11 kccC  и ),,( 22 12 kccC  по правилу )( 1211 iiii sssc  ,  12 ii sc )( 12 ii ss  , ki ,1 , где множители  и  — случайные числа из интервала ]1,[ dd  , 0d , при этом для каждого гена потомка выбирается свой множи- тель. Наиболее оптимальное воспроизведение получается при 25,0d . 20 ISSN 0572-2691 4. Арифметический кроссовер (arithmetical crossover): создаются потомки ),,( 11 11 kccC  и ),,( 22 12 kccC  , гены которых определяются по формулам 211 )1( iii ssc  , 122 )1( iii ssc  , ki ,1 , ]1,0[ — const. 5. Одноточечное скрещивание (single-point crossover): создаются потомки ),,,,,( 22 1 11 11 kssssC   и ),,,,,( 11 1 22 12 kssssC   , где  — случайное чис- ло из интервала ]1,1[ k , т.е. «голова» и «хвост» хромосомы потомка берутся от разных родителей. 6. Линейный кроссовер (linear crossover): создаются потомки ),,( 11 11 kccC  , ),,( 22 12 kccC  и ),,( 33 13 kccC  по правилу 2 21 1 ii i ss c   , 2 3 21 2 ii i ss c   , 2 3 12 3 ii i ss c   , ki ,1 . Для определения наилучшего оператора скрещивания для решения задачи (2) проводился вычислительный эксперимент, в котором кроссоверы 1–6 сравнива- лись по скорости сходимости и точности (остальные операторы ГА были одина- ковыми). Для устранения эффекта случайных флуктуаций, неизбежных ввиду стохастического характера ГА, для каждого кроссовера производилось 1000 за- пусков алгоритма и фиксировались средние показатели. Скорость сходимости оценивалась по числу поколений, необходимых для выполнения одного из усло- вий окончания алгоритма: 1) значение фитнесс-функции лучшей особи в поколе- нии меньше заданной величины ; 2) достигнуто максимальное количество maxt поколений популяции. Результаты вычислительного эксперимента показали, что наилучший опера- тор скрещивания для применения в задаче (2) — линейный кроссовер. Преимуще- ства этого кроссовера демонстрирует табл. 1, где приведены результаты аппрок- симации функции xexf )( на множестве точек отрезка ]1,0[ дробно-рациональной функцией )(11 xR при 10 b , 0043,0 и 500max t . Первое число в клетках табл. 1 соответствует среднему значению фитнесс-функции, второе — среднему количе- ству поколений t . Следует добавить, что особенность линейного кроссовера, а также следующих за ним по рейтингу BLX кроссовера и оператора промежу- точной рекомбинации заключается в том, что значение гена потомка может ле- жать в области, выходящей за пределы значений родительских генов. Таблица 1 Тип кроссовера Численность популяции 100N 200N 300N 400N Линейный 0,0063416 198 0,0042988 29 0,0042984 25 0,0042984 24 BLX- с 5,0 0,0087658 493 0,0055449 472 0,0050339 461 0,0047706 443 Промежуточный с 25,0d 0,02449 495 0,0071776 481 0,0052493 460 0,0049403 441 Одноточечный 0,049850 500 0,02691 500 0,02093 500 0,01853 500 Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 3 21 Плоский 0,23597 500 0,19968 500 0,13184 500 0,10465 500 Арифметический с 3,0 0,47708 500 0,39612 500 0,26707 500 0,24683 500 Если скрещивание в классическом генетическом алгоритме проводится прак- тически всегда, то мутация, которая предназначена для диверсификации поиска путем случайной модификации решения, — не так часто. Для выяснения целесо- образности применения мутации в алгоритме решения задачи (2) проводился вы- числительный эксперимент, в котором сравнивались результаты аппроксимации с помощью ГА для трех случаев: 1) с применением оператора мутации, когда изменяется значение одного слу- чайного гена одной случайной выбранной особи [23]; 2) с использованием оператора мутации, когда изменяется значение гена с веро- ятностью 1,0MP , при этом величина изменения выбирается случайно в диапазоне ]5,0;5,0[ и может иметь как равномерное, так и любое другое распределение; 3) без мутации. В табл. 2 приведены усредненные по 1000 запускам ГА результаты аппрок- симации функции xexf )( на множестве точек отрезка ]1,0[ с помощью дроб- но-рациональной функции )(21 xR с 10 b , 000185,0 и .500max t Результаты показывают, что для популяций численностью 300 особей и более необходимости в мутации нет. Для популяций меньших размеров целесообразно использовать мутацию с помощью оператора 2. При этом значение вероятности MP следует выбирать небольшим, чтобы избежать сильных изменений хромосомы и роста числа поколений. Например, для 3,0MP среднее число поколений t до оконча- ния алгоритма равно 474 при 100N и 123 при ,200N в то время как для 1,0MP число поколений меньше — 455 и 89 соответственно. Таблица 2 Размер популяции N Без мутации Оператор мутации 1 Оператор мутации 2 Погрешность t Погрешность t Погрешность t 100 0,00225618 485 0,00237290 487 0,00134087 455 200 0,00028751 116 0,00027993 103 0,00018608 89 300 0,00019064 39 0,00020032 39 0,00018401 44 400 0,00018390 32 0,00018381 31 0,00018399 43 500 0,00018387 29 0,00018380 30 0,00018394 37 600 0,00018372 29 0,00018377 29 0,00018391 36 В ГА для выбора особей для рекомбинации чаще всего применяются руле- точная селекция, турнирный отбор и отбор усечением. При рулеточной селекции пары родителей выбираются случайным образом так, чтобы вероятность выбора конкретной особи для скрещивания равнялась заданной вероятности CP [21]. При турнирной селекции все особи популяции разбиваются на подгруппы с последу- ющим выбором в каждой из них особи с наилучшей приспособленностью. Чаще всего используются подгруппы по две (парный турнир) или три особи в каждой. http://edu.sernam.ru/book_kiber1.php?id=227 22 ISSN 0572-2691 При отборе усечением для скрещивания выбираются NT  лучших особей, где T — «порог отсечения» ( 10 T ). По результатам вычислительного эксперимента, в котором сравнивались рулеточная селекция с разным значением вероятности CP , турнирный отбор с численностью турнира две и три особи и отбор усечением с разным значением порога, установлено, что наиболее эффективна для примене- ния в задачах аппроксимации турнирная селекция. При этом численность под- группы (две или три особи) существенного влияния на результат не оказывает. При выборе наилучшей стратегии формирования новой популяции сравнива- лись четыре оператора. В трех операторах используется стратегия элитизма, когда в новую популяцию включаются: 1) N лучших (элитных) особей из расширенной популяции родителей и потомков; 2) 50 % элитных особей (остальные 50 % создаются случайно, как при фор- мировании начальной популяции); 3) 30 % элитных особей. В четвертом операторе, реализующем стратегию «дети замещают родите- лей», новое поколение формируется только из особей-потомков. Вычислительный эксперимент показал, что наилучших результатов алгоритм достигает при исполь- зовании оператора отбора 1. По итогам исследований сконструирован алгоритм для решения задачи наилучшей нелинейной аппроксимации (2), который имеет такие особенности реализации стандартной схемы ГА. В начальное поколение популяции вклю- чаются особи jS , Nj ,1 , гены j is ( ki ,1 ) которых — случайные числа из заданного числового интервала, по умолчанию это интервал ]1,1[ . Каждая особь оценивается по значению ее функции приспособленности Fit, которое вычисляется по формуле (3). Родительские особи определяются в соответ- ствии с процедурой парного турнирного отбора [21]. Для скрещивания при- меняется линейный кроссовер. Если численность популяции 300N , то вы- полняется мутация с помощью оператора 2, в противном случае мутация не проводится. В новое поколение из расширенной популяции родителей и по- томков включаются только N особей с наименьшим значением функции Fit. Алгоритм завершает работу, если выполняется одно из двух условий: 1) значение фитнесс-функции наилучшей особи в поколении меньше заданной величины ; 2) достигнуто максимальное число поколений — .maxt Анализ результатов вычислительных экспериментов Для проверки эффективности применения разработанного ГА для реше- ния задачи (2) выполнена серия вычислительных экспериментов по прибли- жению функций нелинейными аппроксимантами разных классов. Полученные погрешности приближения и оптимальные значения параметров аппрокси- мантов сравнивались с соответствующими величинами, найденными специа- лизированными алгоритмами наилучшей равномерной аппроксимации. При- ведем несколько примеров аппроксимации. Пример 1. Требуется найти наилучшее равномерное приближение функции x xx xf 8 1)18()8(arctg )( 2   (4) Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 3 23 на множестве точек 101 1})1(02,01{  ii ixD дробно-рациональным выраже- нием )(22 xR с коэффициентом 10 b . Для определения оптимальных значений пяти параметров аппроксиманта )(22 xR использовался разработанный ГА с таки- ми настройками: число генов ,5k размер популяции 300N , количество по- колений 500max t , 0 , интервал для создания начальной популяции ]1,1[ , число точек 101m , количество запусков алгоритма 20. В результате получен аппроксимант 2 2 22 2474857929,280120059403,41 5959753041,416534210288,104146723058,1 )( xx xx xR    , который приближает функцию (4) с погрешностью 0,023764. Для сравнения наилучший аппроксимант, найденный с помощью алгоритма чебышевского при- ближения [8], имеет вид 2 2 22 262765890,28010260079,41 616891987,41652968029,104144907943,1 )( xx xx xR    , а погрешность аппроксимации равна 0,023811. Это означает, что результаты при- ближения, полученные разработанным ГА и специализированным алгоритмом дробно-рациональной аппроксимации, практически совпадают. Пример 2. Требуется найти наилучшие равномерные приближения функции xexf )( на множестве точек отрезка ]1,0[ дробно-рациональными выражения- ми )(xRpq ( 10 b , 6 qp ). В табл. 3 приведены результаты, полученные с по- мощью традиционного алгоритма чебышевской аппроксимации [3], ГА с BLX кроссовером [19] и ГА, предложенного в настоящей работе. В качестве погрешно- сти приближения  в генетических алгоритмах бралось наименьшее за 100 запус- ков значение функции приспособленности. Из табл. 3 видно, что погрешности, найденные с помощью разработанного ГА, практически совпадают с погрешно- стями наилучшей чебышевской аппроксимации для всех значений 7,2k , в то время как ГА, описанный в [19], дает значительное расхождение с правильными результатами уже при 5k . Таблица 3 Аппрок- симант k Абсолютная погрешность приближения,  Чебышевский алго- ритм ГА, предложенный в [19] Разработанный ГА )(01 xR 2 0,977310– 1 0,977310– 1 0,977310– 1 )(11 xR 3 0,429510– 2 0,429510– 2 0,429510– 2 )(21 xR 4 0,180110– 3 0,207210– 3 0,180110– 3 )(22 xR 5 0,447010– 5 0,103210– 3 0,447010– 5 )(23 xR 6 0,111210– 6 0,137810– 2 0,111210– 6 )(33 xR 7 0,199710– 8 0,543610– 3 0,199210– 8 В ходе вычислительных экспериментов исследовалась зависимость между размером популяции и скоростью сходимости ГА. На рисунке приведены графики зависимостей среднего числа поколений t от численности популяции N при 24 ISSN 0572-2691 аппроксимации xexf )( функциями )(11 xR ( 3k , 0043,0 ), )(21 xR ( 4k , 000185,0 ) и )(22 xR ( 5k , 5105,0  ). Графики показывают, что увеличе- ние размера популяции приводит к более скорому (в смысле числа поколений) нахождению решения. Однако после некоторого значения N рост скорости схо- димости становится незначительным, поскольку использование больших популя- ций ведет к замедлению алгоритма из-за существенного роста объема вычисле- ний. Оптимальный размер популяции зависит от числа генов k в хромосоме, например, для 3k оптимальная численность составляет 150–200 особей, для 4k — 200–300 особей. k=3 k=4 k=5 500 400 300 200 100 0 t N 100 200 300 400 500 600 700 800 900 По итогам выполненных вычислительных экспериментов установлено, что результаты аппроксимации (параметры аппроксимантов и погрешности приближений), полученные с помощью разработанного ГА и специализиро- ванных алгоритмов равномерного приближения, практически совпадают, если количество оптимизируемых параметров k не превосходит десяти. При оп- тимизации большего числа параметров точность ГА ухудшается из -за сильно- го увеличения размера области поиска [19, 24], хотя и в этих случаях можно получить приемлемые результаты. Следует заметить, что ограничение 10k не является существенным в задачах приближения экспериментальных дан- ных, поскольку на практике применяются преимущественно эмпирические формулы с небольшим числом параметров. Задача построения эмпирической формулы, аппроксимирующей с той или иной точностью экспериментальные данные, достаточно часто возникает при исследовании различных физических процессов. Поскольку такие про- цессы преимущественно имеют нелинейный характер, то для более адекват- ного их представления используются нелинейные эмпирические формулы. Рассмотрим применения разработанного ГА для нахождения оптимальных параметров нелинейных эмпирических зависимостей на следующем примере. Пример 3. Исследуется зависимость между производительностью фильтра z (в кг жидкости на м2) и величиной вакуума y (в мм рт. ст.) при различных значе- ниях размера x (в см) частиц промываемого на фильтре осадка. Требуется подо- брать эмпирическую формулу, описывающую результаты измерений, приведен- ные в табл. 4 [25]. Таблица 4 Размер частиц, x Величина вакуума, y 0,250 0,313 0,344 0,375 0,438 0,500 Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 3 25 50 3144 4847 5883 6998 9535 12537 75 3811 4847 7205 8579 11680 15073 100 4402 6853 8320 9986 13486 17616 125 4976 7662 9302 11075 15073 19694 В рассматриваемом примере производительность фильтра z является функ- цией двух переменных ),( yxfz  , при этом истинный вид функции f неизве- стен. Анализ данных по каждой переменной показал, что для приближения целе- сообразно использовать функцию cb yxayx  ),( , где cba ,, — искомые па- раметры, т.е. необходимо решить задачу многомерной нелинейной аппроксимации. Для определения оптимальных значений параметров cba ,, при- менялся ГА с такими настройками: число генов ,3k размер популяции ,200N количество поколений 500max t , 0 , интервал для генерирования начальной популяции ]1,1[ , число точек двумерной сетки 24m , количество запусков алгоритма 20, формула для вычисления функции приспособленности i iii mi z yxz 1 ),(maxFit 1   , где iz — значения продуктивности в точках ),( ii yx . В результате найден наилучший аппроксимант 4996,09936,1258,7012 yx  , приближающий экспери- ментальные данные с относительной погрешностью 0,825 %. Поскольку показате- ли степени x и y близки к 2 и 0,5 соответственно, то для приближения удобнее использовать функцию yxa  2~ . С помощью ГА найдено оптимальное зна- чение 508,7057~ a . Таким образом, производительность фильтра можно описать формулой yxz  2508,7057 , при этом относительная погрешность приближе- ния экспериментальных данных не превысит 0,893 %. Заключение Рассмотрено применение генетических алгоритмов для решения важного класса задач теории аппроксимации функций — наилучшего равномерного нелинейного приближения. Преимуществами ГА по сравнению с традицион- ными специализированными алгоритмами равномерной аппроксимации явля- ются универсальность (возможность приближения аппроксимантами разных типов), отсутствие необходимости применения численных методов, простота реализации и возможность использования в других подобных задачах. Уста- новлено, что наилучших результатов при решении задачи равномерной нели- нейной аппроксимации ГА достигает при использовании линейного кроссове- ра, парного турнирного отбора родителей, а также при включении в новую по- пуляцию только лучших особей из числа родителей и потомков. Исследована зависимость между размером популяции и скоростью сходимости алгоритма. Приведены примеры приближения функций нелинейными аппроксимантами с помощью ГА. Показано, что результаты аппроксимации, полученные генети- ческим алгоритмом, практически совпадают с результатами специализирован- ных алгоритмов равномерного приближения, если количество оптимизируе- мых параметров аппроксимантов не превосходит десяти. Рассмотрено приме- 26 ISSN 0572-2691 нение ГА для построения нелинейной эмпирической функции двух перемен- ных для приближения экспериментальных данных о производительности фильтра. Л.П. Вакал РОЗВ’ЯЗАННЯ ЗАДАЧІ РІВНОМІРНОЇ НЕЛІНІЙНОЇ АПРОКСИМАЦІЇ З ВИКОРИСТАННЯМ НЕПЕРЕРВНОГО ГЕНЕТИЧНОГО АЛГОРИТМУ Запропоновано неперервний генетичний алгоритм для розв’язання задачі найкращої рівномірної нелінійної апроксимації функцій. За результатами обчислювальних експериментів виконано порівняння цього алгоритму зі спеціалізованими алгоритмами наближення. Наведено приклад застосу- вання генетичного алгоритму для побудови нелінійної емпіричної функції двох змінних для наближення експериментальних даних щодо продуктив- ності фільтра. L.P. Vakal SOLVING UNIFORM NONLINEAR APPROXIMATION PROBLEM USING CONTINUOUS GENETIC ALGORITHM A continuous genetic algorithm for solving a problem of the best uniform non- linear approximation is proposed. A comparison of this algorithm with special- ized algorithms of approximation is made according to results of computational experiments. It is presented an example of constructing a nonlinear empiric func- tion of two variables for approximation of experimental data on filter capacity with using the genetic algorithm. 1. Ремез Е.Я. Основы численных методов чебышевского приближения. — Киев: Наук. думка, 1969. — 623 с. 2. Каленчук-Порханова А.А. Аппроксимация функций одной и многих переменных // Числен- ные методы для многопроцессорного вычислительного комплекса ЕС. — М.: Изд-во ВВИА им. Н.Е. Жуковского, 1987. — С. 366–395. 3. Каленчук-Порханова А.А., Вакал Л.П. Пакет программ аппроксимации функций // Комп’ютерні засоби, мережі та системи. — 2008. — № 7. — С. 32–38. 4. Fraser W., Hart J.F. On the computation of rational approximations to continuous functions // Comm. ACM. — 1962. — 5, N 7. — P. 401–403. 5. Гаврилюк В.Т. Обобщение первого полиномиального алгоритма Е.Я. Ремеза для зада- чи построения дробно-рациональных чебышевских приближений // Украинский ма- тематический журнал. — 1964. — 16, № 5. — С. 575–585. 6. Ralston A. Rational Chebyshev approximation by Remez algorithm // Numer. Math. — 1965. — 7, N 4. — P. 322–330. 7. Cody W.J., Stoer J. Rational Chebyshev approximation using interpolation // Ibid. — 1966. — 9. — P. 177–188. 8. Werner H., Stoer J., Bommas W. Rational Chebyshev approximation // Ibid. — 1967. — 10. — P. 289–306. 9. Попов Б.А., Теслер Г.С. Приближение функций для технических приложений. — Киев : Наук. думка, 1980. — 352 с. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 3 27 10. Ремез Е.Я., Гаврилюк В.Т. Вычислительная разработка нескольких подходов к при- ближенному построению решений чебышевских задач с нелинейно входящими пара- метрами // Украинский математический журнал. — 1960. — 12, № 3. — С. 324–337. 11. Loeb H.L. Algorithm for Chebyshev approximations using the ratio of linear forms // J. Soc. In- dust. Appl. Math. — 1960. — 8, N 3. — P. 458–465. 12. Cheney E.W., Loeb H.L. Two new algorithms for rational approximation // Numer. Math. — 1961. — 3, N 1. — P. 72–75. 13. Dua S.N., Loeb H.L. Further remarks on the differential correction algorithm // SIAM J. Numeri- cal Analysis. — 1973. — N 10. — P. 123–126. 14. Петрак Л.В. Приближение функций одной переменной рациональными дробями // Программы оптимизации (приближение функций). — 1975. — Вып. 6. — С. 110–129. 15. Gugat M. An algorithm for Chebyshev approximation by rationals with constrained denominators // Constr. Approx. — 1996. — N 12. — P. 197–221. 16. Kaufman E.H., Taylor G.D. Uniform rational approximation on functions of several variables // Int. J. Numer. Math. Eng. — 1976. — 9, N 2. — P. 297–323. 17. Dunham C.B. Chebyshev approximation by exponential–polynomial product // J. Approx. Theo- ry. — 1975. — 14, N 1. — P. 77–78. 18. Попов Б.А., Малачивский П.С. Наилучшие чебышевские приближения суммой многочлена и нелинейных функций. — Львов: Физ.-мех. институт им. Г.В. Карпенко АН УССР, 1984. — 70 с. 19. Вакал Л.П. Генетичні алгоритми для чебишовської апроксимації // Комп’ютерні засоби, мережі та системи. — 2013. — № 12. — С. 20–26. 20. Herrera F., Lozano M., Verdegay J.L. Tackling real-coded genetic algorithms: operators and tools for the behaviour analysis // Artificial Intelligence Review. — 1998. — 12, N 4. — P. 265–319. 21. Панченко Т.В. Генетические алгоритмы. — Астрахань: Издательский дом «Астраханский университет», 2007. — 87 с. 22. Непрерывные генетические алгоритмы — математический аппарат. — http://basegroup.ru/ community/articles/real-coded-ga. 23. Vakal L.P. Using genetic algorithm for solving boundary value problems // Journal of Automation and Information Sciences. — 2015. — 47, N 8. — P. 52–62. 24. Паклин Н.Б., Сенилов М.А., Тененев В.А. Интеллектуальные модели на основе гибридного генетического алгоритма с градиентным обучением лидера // Искусственный интеллект. — 2004. — № 4. — С. 159–168. 25. Батунер Л.П., Позин М.Е. Математические методы в химической технике. — Л.: Химия, 1968. — 823 с. Получено 18.11.2015 Статья представлена к публикации акад. НАН Украины А.В. Палагиным. ftp://decsai.ugr.es/pub/arai/tech_rep/ga-fl/AIRE96.ps.Z ftp://decsai.ugr.es/pub/arai/tech_rep/ga-fl/AIRE96.ps.Z ftp://decsai.ugr.es/pub/arai/tech_rep/ga-fl/AIRE96.ps.Z ftp://decsai.ugr.es/pub/arai/tech_rep/ga-fl/AIRE96.ps.Z http://basegroup.ru/

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

Репозитарії

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