Анализ параллельного алгоритма синтеза эмпирических моделей на принципах генетических алгоритмов

Розроблено метод синтезу емпіричних моделей з використанням генетичних алгоритмів, який порівняно з індуктивним методом самоорганізації моделей значно скорочує затрати машинного часу на їх реалізацію. Для підвищення ефективності обчислювального процесу розроблено паралельний алгоритм та здійснено йо...

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208069
record_format	dspace
spelling	irk-123456789-2080692025-10-20T00:06:38Z Анализ параллельного алгоритма синтеза эмпирических моделей на принципах генетических алгоритмов Аналіз паралельного алгоритму синтезу емпіричних моделей на принципах генетичних алгоритмів Analyses of parallel algorithm of empirical models synthesis on the principles of genetic algorithms Горбийчук, М.И. Медведчук, В.М. Лазорив, А.Н. Методы обработки информации Розроблено метод синтезу емпіричних моделей з використанням генетичних алгоритмів, який порівняно з індуктивним методом самоорганізації моделей значно скорочує затрати машинного часу на їх реалізацію. Для підвищення ефективності обчислювального процесу розроблено паралельний алгоритм та здійснено його аналіз, що дало змогу оцінити зменшення затрат машинного часу порівняно з послідовним алгоритмом. The developed method of synthesis of empirical models using the genetic algorithms reduces the computing time for the implementing of empirical models, comparing to the inductive method of self-organizing models. To improve the effectiveness of computing process the parallel algorithm was developed and analyzed, which allows reducing the computing time comparing to the sequential or / FIFO / algorithm. 2016 Article Анализ параллельного алгоритма синтеза эмпирических моделей на принципах генетических алгоритмов / М.И. Горбийчук, В.М. Медведчук, А.Н. Лазорив // Проблемы управления и информатики. — 2016. — № 1. — С. 112-131. — Бібліогр.: 17 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208069 519.684.4 10.1615/JAutomatInfScien.v48.i2.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/208069
citation_txt	Анализ параллельного алгоритма синтеза эмпирических моделей на принципах генетических алгоритмов / М.И. Горбийчук, В.М. Медведчук, А.Н. Лазорив // Проблемы управления и информатики. — 2016. — № 1. — С. 112-131. — Бібліогр.: 17 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT gorbijčukmi analizparallelʹnogoalgoritmasintezaémpiričeskihmodelejnaprincipahgenetičeskihalgoritmov AT medvedčukvm analizparallelʹnogoalgoritmasintezaémpiričeskihmodelejnaprincipahgenetičeskihalgoritmov AT lazorivan analizparallelʹnogoalgoritmasintezaémpiričeskihmodelejnaprincipahgenetičeskihalgoritmov AT gorbijčukmi analízparalelʹnogoalgoritmusintezuempíričnihmodelejnaprincipahgenetičnihalgoritmív AT medvedčukvm analízparalelʹnogoalgoritmusintezuempíričnihmodelejnaprincipahgenetičnihalgoritmív AT lazorivan analízparalelʹnogoalgoritmusintezuempíričnihmodelejnaprincipahgenetičnihalgoritmív AT gorbijčukmi analysesofparallelalgorithmofempiricalmodelssynthesisontheprinciplesofgeneticalgorithms AT medvedčukvm analysesofparallelalgorithmofempiricalmodelssynthesisontheprinciplesofgeneticalgorithms AT lazorivan analysesofparallelalgorithmofempiricalmodelssynthesisontheprinciplesofgeneticalgorithms
first_indexed	2025-10-20T01:15:25Z
last_indexed	2025-10-21T01:09:30Z
_version_	1846551742510006272
fulltext	© М.И. ГОРБИЙЧУК, В.М. МЕДВЕДЧУК, А.Н. ЛАЗОРИВ, 2016 112 ISSN 0572-2691 УДК 519.684.4 М.И. Горбийчук, В.М. Медведчук, А.Н. Лазорив АНАЛИЗ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА СИНТЕЗА ЭМПИРИЧЕСКИХ МОДЕЛЕЙ НА ПРИНЦИПАХ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Введение Построение эмпирических моделей занимает важное место как в научной, так и в практической деятельности. Такие модели используются в различных областях деятельности человека — прогноз, распознавание образов, оптимизация и т. п. Суть задачи построения эмпирических моделей в том, что имеются некоторые входы и выходы, между которыми существует определенная функциональная зави- симость, но она исследователю неизвестна. В лучшем случае можно указать неко- торый класс функций, которому принадлежит такая функциональная зависимость. Возможны два принципиально разных случая. Первый, когда входы наблюдаются без искажений, а на выходы накладывается аддитивная помеха. В этом случае для построения эмпирической модели применим метод наименьших квадратов (МНК) [1]. Классический МНК основан на максимизации функции правдоподобия при условии, что закон распределения помехи, накладываемой на выход, носит нормальный характер. Во втором случае вход и выход наблюдаются на фоне помех. Учет помех, которые накладываются на переменные вход–выход, при построении эмпирических моделей возможен, если использовать байесовский подход [2, 3]. Важное место в современной теории построения эмпирических моделей занимает метод опорных векторов [4]. Его нелинейная версия носит название ядерный метод опорных векторов. Рассматривать его следует как один из методов математической статистики [4]: его линейная версия близка к методу гребневой регрессии [5], а нелинейная версия — к методу непараметрического ядерного оценивания [6]. Метод непараметрического ядерного оценивания успешно конкурирует с нейросетевым подходом [4], когда функциональная зависимость между парой вход–выход — реакция обобщенной регрессионной нейросети [7], вход которой пред- ставлен как множество векторов, компоненты которых — экспериментальные данные. Во всех методах построения эмпирических моделей открытым остается вопрос о выборе структуры модели. В классическом МНК предполагается, что структура модели известна и задача сводится к отысканию функциональной зави- симости вход–выход. Если модель линейна относительно своих параметров, задача МНК имеет аналитическое решение. В общем случае синтез эмпирических моделей осуществляется , исходя из условия, что известен класс функций, и ставится задача выбрать такую функцию из заданного класса, которая в определенном смысле лучше всего описывает экспериментальные данные. Для решения поставленной задачи акад. А.Г. Ивахненко предложил метод, основанный на теореме Геделя [8]. Полученные методы известны как метод груп- пового учета аргументов (МГУА) и комбинаторный метод [9, 10]. МГУА в качестве аргументов содержит некоторые промежуточные величины, порожденные многорядной его природой, а комбинаторный метод для своей реализации требует значительных вычислительных затрат [11]. 60 1956 2016 Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 113 Цель настоящей работы — дальнейшее усовершенствование индуктивного метода самоорганизации эмпирических моделей на основе генетического подхода, а также исследование полученного алгоритма на параллелизм, что позволит создать эффективные алгоритмы построения эмпирических моделей. Метод синтеза моделей оптимальной сложности на принципах генетических алгоритмов В основе эмпирического моделирования многих явлений и процессов лежит широко известный МНК, содержание которого заключается в следующем. Пусть рассматривается некоторый объект или система, функционирование которых характеризуется вектором входных величин T 21 ),,( nxxxx  и выходной величи- ной .y В результате наблюдений за входными и выходными величинами получают множество значений )()2()1( ...,,, Nxxx и ,)1(Y ,)2(Y , ,)(NY где N — коли- чество наблюдений. Совокупность векторов )()2()1( ...,,, Nxxx образует так называ- емую матрицу наблюдений: .]...,,,[ T)()2()1( NxxxX  В МНК допускают, что структура модели известна и чаще всего выбирается линейной относительно ее параметров:    r k kk xfay 0 )( , (1) где ,ka ,,0 rk  — параметры модели. Задача заключается в том, чтобы на основе наблюдений за входными и вы- ходной величинами, определить параметры, ,ka ,,0 rk  модели (1) таким обра- зом, чтобы как можно точнее приблизить выход системы к выходу модели. Кри- терием такого приближения выбирают сумму квадратов отклонений расчет- ных )(iy от экспериментальных значений, )(iY , .,1 Ni  По известным )(iY и вычисленным значениями )(iy согласно (1) можно получить критерий приближения (аппроксимации) ,)()( 2)()( 1 ii N i yYaJ   который в векторной форме приобретет следующий вид: )()()( T aFYaFYaJ  , (2) где Y — вектор наблюдений с компонентами ,)(iY ;,1 Ni  F — матрица, строки которой — значения функций ),( )( j i xf ,,0 ri  ,,1 Nj  в точках наблюдений за величинами .)( jx Значения параметров модели (1) вычисляют из условия, что критерий приближения (2) приобретет минимальное значение относительно вектора пара- метров .a Минимизация (2) приводит к следующему результату: ,TYFaMF  (3) где FFMF T — матрица Фишера. 114 ISSN 0572-2691 Если размерность вектора a небольшая и матрица M хорошо обусловлена, из уравнения (3) можно непосредственно определить .T1 YFMa F  В подавляющем большинстве случаев структура модели (1) неизвестна, что приводит к необходимости выбора как структуры самой модели, так и ее параметров. Критерий приближения (2) является внутренним критерием [10] , и его приложение приводит к ошибочному выводу: чем сложнее модель, тем она точнее. Поскольку на выход системы накладывается помеха (допускают, что она аддитивна), то чрезмерная точность модели может значительно иска- зить объективно существующую функциональную зависимость между выхо- дом системы и ее входами. Поэтому для выбора структуры модели (1) акад. А.Г. Ивахненко предложил индуктивный метод самоорганизации моделей [10], идейную сторону которого определяет теорема Геделя [8]. Относительно задачи синтеза модели геделевский подход означает применение внешнего критерия для однозначного выбора струк- туры модели из заданного класса моделей. Критерий называют внешним, если его вычисление основывается на данных, которые не использовались при решении задачи (2). Это значит, что все данные, полученные в результате эксперимента, разбиваются на две части: учебную AN и проверочную .BN Преимущественно для выбора структуры модели (1) используют критерии регулярности 2)( 1 2)()( 12 )( ))()(( )( BY ByBY B i N i ii N i B B       (4) и смещения 2)( 1 2)()( 12 )( ))()(( ),( i N i ii N i Y ByAy BA       , (5) где )(),( )()( ByAy ii — значения выхода модели, которые вычислены соответ- ственно на множествах экспериментальных значений AN и .BN Если выбранный критерий регулярности (4), то выбирают такое распределение данных эксперимента [12]: NNA 7,0 и ,3,0 NNB  а при выборе критерия (5) — NNA 5,0 и .5,0 NNB  Реализация индуктивного метода самоорганизации моделей осуществляется поэтапно: первый этап генерирования моделей-претендентов (в определенном порядке повышения их сложности); второй — выбор наилучшей модели по минимуму критерия селекции (4) или (5). Различают три способа генерирования моделей-претендентов. Первый из них комбинаторный [12]: выбор моделей-претендентов осуществляется при- равниванием к нулю некоторых коэффициентов в выражении (1), которое да- ет возможность получить совокупность моделей. Выбор наилучшей из них осуществляется на основе одного из критериев селекции (4) или (5). Второй способ — МГУА [9], в котором генерирование моделей-претендентов осу- ществляется с помощью многорядной процедуры. Третий метод [10] подобен Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 115 второму. Разница лишь в том, что на каждом ряду селекции частичные модели образуются приравниванием к нулю определенного числа их коэффициентов. Недостаток комбинаторного метода селекции моделей — необходимость большого перебора частичных моделей. Если начальной моделью выбран полный полином степени ,m то общее число моделей-претендентов ,12 M где M — общее число членов начального полинома. Даже современные ЭВМ не способны ре- ализовать комбинаторный алгоритм селекции моделей при значительном ко- личестве входных величин и при высокой степени начального полинома. МГУА синтезирует модели, в которых фигурируют промежуточные переменные, что зна- чительно усложняет процесс перехода к входным переменным системы. Сказанное относится и к третьему методу, поскольку он является модификацией МГУА. МГУА имеет тот недостаток, что в соответствии с принятой процедурой син- теза эмпирических моделей выходные переменные достаточно сложно выразить в явном виде через входные переменные объекта. Из всех трех методов наиболее привлекателен комбинаторный метод, поскольку он дает возможность получить оптимальную модель, где в качестве аргументов выступают входные переменные системы. Для снятия проблемы большой размерности комбинаторного метода применим генетический подход. Как эмпирическую модель выберем полином степени ,m jis j n j i M i xay      1 1 0 , (6) где ia — коэффициенты полинома; jis — степени аргументов, которые должны удовлетворять ограничению . 1 ms ji n j   Число членов M полинома (6) определяют согласно формуле [11] !! )!( nm nm M   . (7) Образуем упорядоченную последовательность, где на і-м месте будет нахо- диться единица или нуль в зависимости от того, будет ли параметр ,ia ,1,0  Mi модели (6) отличаться от нуля или иметь значение нуль. В теории гене- тических алгоритмов такая упорядоченная последовательность носит название хромосомы, а атомарный элемент (единица или нуль) хромосомы — это ген; набор хромосом образует популяцию. Важным понятием теории генетических алгоритмов является функция приспособленности, которая определяет степень приспособ- ленности отдельных особей в популяции. Она дает возможность из всей популяции выбрать особей, наиболее приспособленных, т.е. тех, которым отвечает наименьшее значение функции приспособленности. В задаче синтеза моделей оптимальной слож- ности как функцию приспособленности выберем критерий селекции (4) или (5). Как и классический генетический алгоритм [13], алгоритм синтеза моделей оптимальной сложности состоит из следующих шагов. Шаг 1. Формирование начальной популяции (инициализация). На пер- вом шаге работы алгоритма случайным образом формулируется популяция из I особей, каждая из которых является хромосомой длиной .M Число генов в хро- мосоме определяется по формуле (7). 116 ISSN 0572-2691 Шаг 2. Оценка приспособленности хромосомы в популяции. Для каждой хромосомы вычисляется значение критерия селекции (4) или (5) следующим образом. Если выбранный критерий селекции (4), то формируются матрицы AF и BF размерами MNA  и .MNB  Из матрицы AF изымается і-й столбец, если на і-й позиции хромосомы находится нуль; если единица, то соответствующий столбец остается без изменений. В итоге получим матрицу , ~ AF из которой изъято c столбцов (по количеству нулей в хромосоме). Размер такой матрицы ).( cMNA  Аналогично получим матрицу BF ~ размером ).( cMNB  На множестве точек AN вычисляются ненулевые коэффициенты ,Aja ,,1 cMj  модели (8) путем решения нормального уравнения Гаусса, которое видоизменяется следующим образом: AAAAF YFaM T , ~~  , (8) где T 1,10 ),,,(  cMAAAA aaaa  — вектор ненулевых параметров модели, который ассоциируется с дежурной хромосомой; AAAF FFM ~~~ T ,  . ,( )1(YYA  ),, )()2( AN YY  — вектор экспериментальных значений на множестве .AN По найденным коэффициентам Aa полиномиальной модели на множестве точек BN вычисляют значение AB aFBy ~ )(  . (9) Зная )(By , по формуле (4) вычисляют значение функции приспособленности ),(2 Bj ,,1 Ij  для каждой хромосомы из начальной популяции. В том случае, когда критерий смещения (5) используют как функцию при- способленности, составляют уравнение (8), которое решают методом Гаусса от- носительно параметров Aa . После этого вычисляют AA aFАy ~ )(  по формуле (9). Полученные значения )(Аy и )(By дают возможность найти значение ),(2 BAj , ,,1 Ij  для каждой хромосомы из популяции. Шаг 3. Проверка условия остановки алгоритма. Определяют )(min)( 22 BB j j m  , (10) ),(min),( 22 BABA j j m  . (11) Если минимальное значение (10) или (11) критерия селекции (4) или (5) не превышает некоторого заданного значения ,Ε то происходит остановка вычислений. Она также может состояться и в случае, когда в результате выпол- нения алгоритма функция приспособленности уменьшается несущественно или когда выполнено заданное число итераций. После выполнения одного из трех условий из текущей популяции выбирается та хромосома ,ch для которой выполняется условие (10) или (11). Эта хромосома задает структуру модели оптимальной сложности и формирует матрицу F таким образом, что из начальной матрицы изымаются столбцы, ассоциируемые с ну- Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 117 левыми значениями соответствующих генов. Пересчет параметров модели (6) осуществляется на всем множестве точек N с помощью МНК. Шаг 4. Селекция хромосом. По рассчитанным на втором шаге алгоритма значениям функции приспособленности осуществляется отбор хромосом, участвующих в создании потомков для новой популяции. Такой отбор прово- дится по принципу естественного отбора, когда наибольшие шансы в создании новой популяции имеют хромосомы с наилучшими значениями функции при- способленности (4) или (5). Самый распространенный метод селекции — метод рулетки и турнирный метод [13]. Метод рулетки можно применять тогда, когда функция приспособленности положительна, что делает его пригодным лишь для задач максимизации. Турнирный метод можно использовать как в задачах максимизации, так и в задачах минимизации. При турнирной селекции все хромосомы разбиваются на подгруппы со сле- дующим выбором из каждой подгруппы хромосомы с наилучшей приспособлен- ностью. Подгруппы могут иметь произвольный размер, но чаще популяцию делят на подгруппы по 2–3 особи в каждой. Шаг 5. Формирование новой популяции потомков. Над отобранными особями на четвертом шаге алгоритма осуществляют видоизменения с помощью двух основных операторов: скрещивание и мутации. Следует заметить, что опе- ратор мутации применяется реже по сравнению с оператором скрещивания. Веро- ятность скрещивания достаточно высока ( 10  cP ), тогда как вероятность му- тации составляет .1,00  mP Вероятность мутации mP можно задать путем вы- бора случайного числа из интервала ]1,0;0[ для каждого гена. Мутация может осуществляться как над пулом родственников, так и над пулом потомков. Шаг 6. После выполнения оператора скрещивания возвращаемся к шагу 2. Алгоритм распараллеливания процесса формирования эмпирической модели Реализация генетического алгоритма синтеза эмпирических моделей опти- мальной сложности показала, что значительная часть машинного времени тратится на решение системы линейных алгебраических уравнений (8). На практике построение эмпирической модели порождает систему уравнений большой размерности [14]. Нормальное уравнение Гаусса (8) запишем в такой форме: , ~~ baA A  (12) где ; ~~ , aFMA  . ~~ A T A YFb  Уравнение (14) будем решать методом гауссового исключения, где система (12) приводится к верхней диагональной форме по следующим формулам [15]: , ~ ~ ~ )1( )1( )(      i ii i ii i a a a ;,1 cMi  (13) ,1,1,,1,~~~~ )1()()1()(      cMjcMikaaaa i kj i i i k i k (14) 118 ISSN 0572-2691 где )()( ~,~ i k i i aa  — i - и k -й строки расширенной матрицы, получаемой присоедине- нием к матрице A ~ векторного столбца ; ~ b   ii aa ~~ )0( , cMi  ,1 ;   kk aa ~~ )0( , .,1 cMik  В вычислительном процессе цикл по индексу k является внутренним по отноше- нию к внешнему циклу по индексу .i Результат применения итерационных процедур (13) и (14) — верхняя диагональная матрица U с единицами на главной диагонали. Остальные элементы матрицы: , )(i ijij au  ,,1 cMi  .1,1  cMij Таким образом, уравнение (12) превратится в эквивалентную систему линейных алгебраических уравнений: , ~ AA baU  (15) где U ~ — квадратная матрица размером ,cM  которая получена из матрицы U путем исключения последнего столбца: ,1,,  cMiiA ub cMi  ,1 . Уравнение (12) решается методом обратной прогонки, начиная с последнего уравнения. Очевидно, что .,, cMAcMA ba   (16) Другие значения iAa , вычисляются по такой итерационной процедуре:     cM ij jAijiAiA auba 1 ,,, , .1,1  cMi (17) Вычисление параметров модели (4) по рекуррентным соотношениям (16) и (17) дает ощутимую экономию машинного времени по сравнению с классическим методом Гаусса. Сказанное справедливо и для LU — метода, в соответствии с которым матрица A ~ подается в виде произведения двух матриц: L и .RU Первая из них — нижняя диагональная с единицами на главной диагонали, а вторая — верхняя диагональная матрица. С помощью прямой и обратной прогонок решаются треугольные системы AbL  и ARaU . Другой способ уменьшения затрат машинного времени — распараллеливание алгоритма приведения матрицы A ~ к верхней треугольной матрице .U На эту операцию тратится бльшая часть времени из расходуемого на решение системы уравнений (12). Суть такого алгоритма в следующем. На стадии инициализации (начальной стадии) вся матрица A ~ размещается в рабочем пространстве первого процессора- мастера (далее — мастера). Первый шаг — мастер отправляет, по возможности, ровные слои матрицы A ~ другим процессором-рабочим (далее — рабочим) так, что каждый из процессоров, включая и первый, получает подматрицы ,1,0, ~ )1(  qiAi где q — общее количество процессоров. После отправления мастер нормирует первую строку своей подматрицы )1( 0 ~ A по формуле (13) и тут же отсылает значение )1( 1 ~ a другим рабочим. Рабочие, получив строку )1( 1 ~ a , каждая из них согласно формуле (14), где ,,1 cMk  перечисляют элементы своих подматриц, включая и элемент 1, ~ cMqia . Одновременно мастер вычисляет новые значения Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 119 элементов по формуле (14), начиная со второй строки. В результате такого пере- счета рабочие получают подматрицы , ~ )1( iA ,1,1  qi в которых нулевыми будут первые столбцы. В матрице )0( 1 ~ A первый столбец будет иметь нулевые элементы, кроме первого ,~ )1( 11a равного единице. Второй шаг — мастер нормирует вторую строку своей подматрицы и значение ,~ )2( 2a которое вычислено по формуле (13), посылает всем рабочим. Одновременно с мастером они модифицируют свои подматрицы в соответствии с процедурой (14). Причем мастер изменяет индекс k от 3 до cM  , а рабочие соответственно — от 2 до .cM  В итоге длина второй строки с ненулевыми элементами сокра- тилась на единицу (первый элемент равняется нулю, а второй — единице). Подматрицы, которые размещены в пространствах рабочих, будут иметь по два нулевых столбца. Процесс модификации элементов подматриц осуществляется циклически по приведенной схеме до тех пор, пока мастер не приведет свою подматрицу к верхнему диагональному виду. В итоге после окончания первого цикла в рабочем пространстве мастера будет храниться верхняя прямоугольная подматрица с едини- цами на главной диагонали, а в рабочих пространствах рабочих получим подматрицы, число нулевых столбцов которых определяется числом строк матрицы мастера. В начале второго цикла рабочие посылают свои подматрицы мастеру, где происходит их объединение. Затем мастер объединенную подматрицу разделяет на q частей и рассылает их всем рабочим, в том числе и себе. Мастер нормирует первую строку своей подматрицы. При этом ведущим элементом будет первый ненулевой элемент первой строки подматрицы мастера. Модифицированную первую строку в соответствии с формулой (13) мастер рассылает всем рабочим, которые модифицируют свои строки по формуле (14). В дальнейшем вычисления происходят так, как это было в первом цикле. Алгоритм продолжает работать до тех пор, пока размер дежурного слоя, подлежащего отправлению, не будет превышать количества процессоров. Тогда мастер приводит оставшуюся подматрицу к верхней прямоугольной матрице с единицами на главной диагонали. Завершающий этап — объединение всех матриц, сохраненных в рабочем пространстве мастера. Вычислим количество операций на каждом шаге вычислений, которые выполняются мастером и каждым рабочим при их параллельной работе. Выполнение мастером операции нормирования первой строки подматрицы )1( 0 ~ A в соответствии с формулой (13) требует cMz  операций деления (диагональным элементам подматрицы )1( 0 ~ A присваивается значение единицы). На перечисление элементов остальных )1( 0s строк подматрицы )1( 0 ~ A по формуле (14) будут тратить zs )1( )1( 0  операций умножения и zs )1( )1( 0  операций вычитания. Общее количество операций, которое выполнено мастером на первом шаге, zsN )12( )1( 0 )1( 10  . Каждый рабочий, получив )1(~ iA подматрицу с )1( is строками, выполняет )1( iN операций на пересчет элементов по формуле (14). Всего будет zsi )1( операций умножения и zsi )1( операций вычитания. Общее количество операций, которое выполняет i -й рабочий, zsN ii )1()1( 1 2 , .1,1  qi 120 ISSN 0572-2691 На втором шаге вычислений мастер нормирует вторую строку матрицы, , ~ )1( 0A затратив 1z операций деления. Другие строки матрицы )1( 0 ~ A перечисляются по формуле (14). При этом будет выполнено )1()2( )1( 0  zs операций умножения и такое же количество операций вычитания. Следовательно, на втором шаге вы- числений мастер выполнит )1()32( )1( 0 )2( 10  zsN арифметических операций. Поскольку в рабочем пространстве каждого і -го рабочего имеем матрицы, в которых на один столбец ненулевых элементов стало меньше, то общее количество операций деления, умножения и вычитания, выполняемых і-м рабочим, )1(2 )1()2( 1  zsN ii , .1,1  qi На третьем шаге вычислений мастер нормирует третью строку, выполнив 2z операций деления. Начиная с четвертой строки, мастер пересчитывает все элементы подматрицы )1( 0 ~ A по формуле (14), тратя такое количество операций деления, умножения и вычитания: .)2()52( )1( 0 )3( 10  zsN Другие 1q рабочие пересчитывают элементы своих подматриц )1(~ iA по фор- муле (14), выполнив при этом ),2(2 )1()3( 1  zsN ii ,1,1  qi операций умножения и вычитания. Обобщая полученные результаты, можно утверждать, что на k -м шаге вы- числений мастер и і-й рабочий выполняют соответственно такое количество опе- раций деления и вычитания: ),1()1)(2( )1( 0 )( 10  kzksN k (18) ),1(2 )1()( 1  kzsN i k i 1,1  qi . (19) Первый цикл параллельных вычислений заканчивается тогда, когда выпол- нится условие )1( 0sk  , т.е. в формулах (18), (19) )1( 0,1 sk  . Таким образом, после первого цикла вычислений получаем верхнюю прямо- угольную матрицу, в которой на главной диагонали будут помещены единицы. Размер такой матрицы .)1( )1( 0 zs После объединения мастером 1q матриц в его памяти будет храниться матрица размером )1()( )1( 0 )1( 0  szsz , в которой изъяты все нулевые элементы. Полученную матрицу мастер делит на q слоев, мощность каждого из них составляет , )2( is ,1,1  qi строк. В рабочем пространстве мастера будет находиться матрица )2( 0 ~ A с )2( 0s строками. Количество операций деления, умножения и вычитания, которые выполняет мастер, и количество операций умножения и вычитания, которые выполняет i -й ра- бочий, вычислим по формулам (18), (19), учитывая, что количество столбцов подматриц, которые размещены в рабочих пространствах мастера и рабочих, составляет 1 )1( 0  sz . Это значит, что в формулах (18), (19) необходимо z за- Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 121 менить на )1( 0sz  , а )1( 0s и )1( is — соответственно на )2( 0s и . )2( is В результате такой замены получим: ,)1()1)(2( )1( 0 )2( 0 )( 20  kszksN k .1,1,)1(2 )1( 0 )2()( 2  qikszsN i k i Второй цикл вычислений закончится выполнением условия . )2( 0sk  После окончания второго цикла вычислений в памяти мастера будет храниться прямоугольная матрица размером ,)1()( )2( 0 )1( 0  zss на главной диагонали, которой будут помещены единицы. В начале третьего цикла вычислений мастер объединяет 1q подматрицу в одну матрицу размером ,)1()( )2( 0 )1( 0 )2( 0 )1( 0  sszssz которая не содержит нулевых элементов, и делит ее на q подматриц. Первая подматрица, которая будет иметь )3( 0s строк, остается в рабочем пространстве мастера, а другие отправ- ляются 1q рабочим. Как и во втором цикле, количество операций деления и вычитания, кото- рые выполняют в третьем цикле соответственно мастер и рабочие, вычислим по формулам (18), (19), заменив z на . )2( 0 )1( 0 ssz  При этом необходимо учесть, что мощность подматрицы )3( 0 ~ A составляет )3( 0s строк, а мощность подматриц )3(~ iA имеет , )3( is ,1,1  qi строк. Следовательно, ,)1()1)(2( )2( 0 )1( 0 )3( 0 )( 30  ksszksN k (20) .1,1,)1(2 )2( 0 )1( 0 )3()( 3  qiksszsN i k i (21) Третий цикл заканчивается при условии, что . )3( 0sk  Пусть выполнено r циклов вычислений. В результате в памяти мастера будет размещена прямоугольная матрица размером )1( )( 0 1 1             zs j r j , на главной диагонали которой размещены единицы. В рабочем пространстве мастера будет находиться матрица размером                         1 )( 0 1 1 )( 0 1 1 j r j j r j szsz с ненулевыми эле- ментами, которую мастер делит на q слоев. В результате получим q подматриц, каждая из которых имеет мощность , )(r is .1,0  qi Опираясь на результаты формул (20), (21), можем утверждать, что по завер- шении r -го цикла вычислений мастер и каждый i -й рабочий выполнят такое ко- личество операций деления и вычитания:              1)1)(2( )( 0 1 1 )( 0 )( 0 kszksN j r j rk r , (22) 122 ISSN 0572-2691              12 )( 0 1 1 )()( kszsN j r j r i k ri , 1,1  zNr , 1,1  qi . (23) Окончанием r -го цикла является выполнение условия . )( 0 r sk  Алгоритм приведения матрицы A ~ к верхнему треугольному виду с единицами на главной диагонали заканчивает свою работу тогда, когда выполнится условие , 1 1 )( 0 qsz zN j j     (24) где zN — общее количество циклов вычислений. Теперь вычислим количество операций деления, умножения и вычитания, которые выполняются в течение r -го цикла. Мастер выполняет такое количество указанных операций: , )( 0 1 , )( 0 k r s k rM NN r    ,1,1  zNr (25) а на долю каждого i -го рабочего приходится следующее количество операций умножения и вычитания: , )( 1 )( , )( 0 k ri s k i rw NN r    1,1  zNr , 1,1  qi , (26) где )( 0 k rN и )(k riN — соответственно определяются по формулам (22) и (23). Поскольку в общем случае размер матрицы A ~ не кратен количеству парал- лельных процессов, то неодинаковое количество строк приводит к неравномерной вычислительной нагрузке процессоров и окончание вычислений будет определяться временем выполнения наиболее загруженного процессора. Если учесть операции на пересылки )(~ i ija элемента в каждом k -м шаге вычислений, то общее количество операций деления и вычитания, которые вы- полняются в r -м цикле, будет таким: )( 0 )( ,, 11 },{max ri rwrM qi r sNNN   , 1,1  zNr . (27) Все rN операций в r -м цикле вычислений выполняются параллельно. Допустим, что на выполнение всех операций деления и вычитания в r -м цикле вычислений тратится r единиц времени, а на операции пересылки — rt, единиц времени. Тогда общие затраты времени на реализацию параллельного алгоритма приведения матрицы A ~ к верхнему диагональному виду следует вычислять по следующей формуле: f N r r rt i rwrM qi r TsNNT z            1 1 )( 0, )( ,, 11 },{max , (28) где fT — затраты времени на приведение подматрицы на последнем шаге вычисле- ний к верхней диагональной форме. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 123 На последнем этапе вычислений, когда выполнено условие (24), мастер подматрицу zA ~ размером                         1 1 1 )( 0 )( 0 1 1 r j jj r j szsz приводит к верхнему диагональному виду в соответствии с формулами (13) и (14). Вычислим количество операций деления и вычитания, которые выполняются на последнем цикле вычислений. Введем такие обозначения: )( 0 1 1 j r j szz      . Матрицу zA ~ можно рассматривать как квадратную матрицу размером ,z к которой присоединен столбец свободных членов системы линейных алгебраических урав- нений. Приведение такой матрицы к верхнему диагональному виду с единицами на главной диагонали потребует [17] 6 34 23    zzz N f (29) операций деления, умножения и вычитания. С учетом значения fN формулу (28) запишем ,},{max )( 0, )( ,, 11 1 1 ff r rt i rwrM qi r N r NsNNT z                где f — затраты времени на выполнение операций на завершающем этапе вычислений. Найдем верхнюю оценку для величины ,T считая, что если начальная матри- ца , ~ A подлежащая преобразованию к верхнему треугольному виду по форму- лам (13) и (14), разбивается на q одинаковых слоев, то , )(r is ,1,0  qi .,1 zNr  Поскольку операция пересылки элемента )(~ i ija выполняется значительно быст- рее, чем арифметические операции умножения, деления и вычитания, то в по- следнем выражении можно пренебречь величиной . )( 0 r s Также допустимо, что }.,{max , 11 rtr Nr z   Тогда .},{max 1 1 )( ,, 11               f N r i rwrM qi NNNT z (30) Из формулы (30) следует, что оценка значения T сводится к определению общего числа операций, которые необходимо выполнить для приведения мат- рицы A ~ к верхнему треугольному виду. На первом цикле вычислений мощность каждого из )1( is слоев q z si  )1( , ,1,0  qi а матрица AA ~~ 1  имеет nn 1 строк. 124 ISSN 0572-2691 По окончании первого цикла вычислений количество строк матрицы A ~ уменьшилось на величину . )1( 0s Новая матрица 2 ~ A будет иметь следующее коли- чество строк: . )1( 02 szz  Учитывая значения , )1( 0s находим )1(2  q q z z . В начале второго этапа вычислений мастер делит матрицу 2 ~ A на q ровных слоев, что в итоге дает ,)1( 2 )2(  q q z si .1,0  qi Выполнение второго этапа вычислений приводит к сокращению матрицы 2 ~ A на )2( 0s строк. В итоге получаем матрицу , ~ 3A имеющую следующее количество строк: . )2( 0 )1( 03 sszz  Если принять к сведению значения )1( 0s и , )2( 0s то получим .)1( 2 23  q q z z После раздела матрицы 3 ~ A на q ровных слоев получим ,)1( 2 3 )3(  q q z si .1,0  qi В результате выполнения третьего этапа вычислений получим матрицу 4 ~ A с таким количеством слоев: . )3( 0 )2( 0 )1( 04 ssszz  С учетом значений , )1( 0s )2( 0s и )3( 0s будем иметь .)1( 3 34  q q z z Если теперь матрицу 4 ~ A разделить на q одинаковых слоев, то ,)1( 3 4 )4(  q q z si .1,0  qi Следовательно, по завершении r -го цикла вычислений получим матрицу rA ~ с количеством строк .)1( r rr q q z z  Для продолжения работы алгоритма на 1r цикле мастер разделяет матрицу rA ~ на q ровных слоев, так что ,)1( 1)(  r r r i q q z s ,1,0  qi .1,1  zNr (31) Предположим, что на последнем цикле вычислений условие (24) будет иметь сле- дующий вид: . )( 0 1 1 qsz j N j z     В соответствии с формулой (27) ,)1( 1)( 0  j j j q q z s поэтому . 11 1 11 1 z q q q q jN j z            Выражение 11 1 1           jN j q qz является суммой геометрической прогрессии, вычисление которой, с учетом последней формулы, приводит к следующему Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 125 результату: z q q q zN        1 1 . Последнее уравнение дает возможность найти количество циклов вычислений, необходимых для приведения матрицы A ~ к верхнему треугольному виду . 1 ln 1 ln 1           q q z q N z В общем случае величина zN не принадлежит множеству натуральных чисел, поэтому его следует округлить до целого числа. Вычисление общего количества операций .},{max )( 0 )( ,, 11 1 1 f ri rwrM qi N r p NsNNN z                (32) происходит согласно следующему алгоритму. По формулам (25) и (26) находим значение rMN , и )( , i rwN . Поскольку в каждом цикле вычислений дежурная мат- рица iA ~ разбивается на q ровных слоев, то )( , i rwN зависит только от индекса ,r т.е. .)( ,, i rwrw NN  С учетом формулы (31) соотношения (22) и (23), которые входят в форму- лы (25) и (26), приобретут следующий вид: ),1)((1)(2 )( 0                 kqzLkqL q z N k r ,)1)(()(2)(  kqzLqL q z N k r ,1,1  zNr где . 1 1)( 1        r q qL Зная rMN , и rwN , , по формуле (32) вычислим ,N )( 0 r s определим согласно соотношению (31), а fN — по формуле (29). Обратный ход, в котором в обратном порядке определяются неизвестные, осуществляется по формулам 1,,  zzzA ua , ,, 1 1,, jAji z ij ziiA auua     1,1 zi . (33) Проанализируем алгоритм (33) решения системы линейных алгебраических уравнений с треугольной матрицей U методом обратной подстановки. Физиче- ское содержание задачи синтеза оптимальной структуры эмпирической модели таково, что матрица U является невырожденной. Формула (33) не определяет алгоритм однозначно, так как не определен порядок нахождения суммы. Рассмотрим последовательную операцию суммиро- вания, которая выполняется в правой части соотношения (33). Соответствующую рекуррентную процедуру запишем: ,1,, )0( ,  zzzAzA uaa , )1( 1,1, )1( , )( ,      j jzAjziz j izA j izA auaa ,1, )0( ,   zizizA ua , )( ,, i izAizA aa   ,1,1  zi .,1 ij  (34) 126 ISSN 0572-2691 Процедуре нахождения решения уравнения (15) по формулам (33) свойственен внутренний параллелизм. Поэтому для экономии машинного времени синтезируем соответствующий параллельный алгоритм. На первом шаге вычислений предпоследний z столбец матрицы ,U который имеет 1z отличающихся от нуля элементов (не учитывая элемента 1zzu ), разделим между q процессорами так, что мастер будет иметь )1( 0s элементов, а рабочие — по , )1( ks ,1,1  qk элементов. По формуле (16) вычислим значение , )1( , izAa  где )1( 0,1 si  для мастера; ,,1 )1()1( 1 kk ssi   ,1,1  qk для рабочих. Рабо- чие пересылают свои значения )1( , izAa  мастеру, при этом формируется множество значений 1, zAa и , )1( , izAa  ,1,2  zi хранящихся в рабочей области мастера. На втором шаге 2z элементы 1z столбца разделяем между q процессорами. В результате такого разделения мастер получит )2( 0s элементов, а рабочие — по , )2( ks ,1,1  qk элементов. Затем мастер, включая и себя, рассылает соответствующее количество элементов 1, zAa и )1( , izAa  , ,1,2  zi каждому процессору, включая и самого себя. Затем по формуле (34) вычисляют значение )2( 1, izAa , где )1( 0,1 si  для мастера; ,,1 )2()2( 1 kk ssi   ,1,1  qk для рабочих. При этом )2( 2,2,   zAzA aa . Завершается второй шаг формированием в рабочей области мастера множества значений 2, zAa и , )2( , izAa  1,3  zi . Дальнейшие шаги вычислений происходят по приведенной схеме и на r -м шаге мастер разделяет rz  элементы 1 rz столбца между q процессорами таким образом: мастер будет иметь )( 0 r s элементов, а рабочие — по , )(r ks ,1,1  qk элементов. По формуле (34) вычисляются значения )( 1, r rizAa  , где )1( 0,1 si  для мастера; ,,1 )()( 1 r k r k ssi   ,1,1  qk для рабочих. Как результат вычислений в рабочей области мастера будет содержаться множество значений rzAa , и )( , r izAa  , 1,1  zri . Процесс решения алгебраического уравнения (15) методом обратного хода с использованием параллельного алгоритма завершается последним шагом вычислений при выполнении условия .qrz  Тогда мастер вычисляет все значения ,, izAa  где ,1,  zri по формуле (34). Вычислим количество опера- ций умножения и вычитания, которые осуществляются в результате реализации параллельного алгоритма вычислений по формуле (16). На r -м шаге вычислений мастер осуществит ,2 )( 0 )( 0 rr sN  (35) а каждый рабочий )()( 2 r i r i sN  (36) операций умножения и вычитания. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 127 В общем случае размер каждого столбца матрицы U может оказаться не кратным количеству процессоров, что приводит к разной вычислительной нагрузке процессоров и окончание вычислений на каждом шаге будет опреде- ляться временем работы наиболее загруженного процессора, поэтому на 1r -м шаге вычислений .),(max )()( 0 11 )( r i r qi r NNN   Поскольку параллельные вычисления ведутся по столбцам матрицы ,U то zr ,1 и общее число операций при реализации параллельного алгоритма будет следующим: f r i r qi sz r NNNN f      ),(max )()( 0 111 )( 0 , где fN — число операций умножения и вычитания на последней стадии вы- числений. При переходе от одного шага вычислений к другому число элементов текущего столбца уменьшается на единицу. Поэтому на определенном шаге вычислений будет иметь место условие qs f  )( 0 , которое и определит завершение процесса вычислений. Учитывая условие завершения процесса вычислений, а также формулы (35), (36), приходим к выводу, что .),(max2 )()( 0 111 f r i r qi qz r NssN      (37) Вычислим величину .fN Последний шаг вычислений начинается с условия . )( 0 qs f  Дальнейшие действия производит мастер, вычисляя параметры моде- ли согласно описанной процедуре. Поэтому общее количество операций умножения и вычитания на последнем шаге вычислений определяется по фор- муле .)1()(2 1    qqiqN q i f С учетом значения fN формула (38) будет сле- дующей: .)1(),(max2 )()( 0 111      qqssN r i r qi qz r (38) При равномерной загрузке процессоров , )()( 0 q rz ss r i r   .i В таком случае значение N согласно формуле (38) приобретет такой вид: )1()( 2 1     qqrz q N qz r . Вычислив значение )( 1 rz qz r    , приходим к выводу, что .)1()1(    qqqz q qz N (39) 128 ISSN 0572-2691 Реализация последовательного алгоритма вычисления коэффициентов матема- тической модели (6), после того как полученная матрица ,U требует )1( ~  zzN операций умножения и вычитания [17]. Формулу (9) запишем в несколько ином виде: ,)( ,, 1 iAiB z i afBy    (40) где iBf , — i -й столбец матрицы . ~ BF Анализ формулы (40) показывает, что каждое слагаемое суммы может вы- числяться независимо, а это свидетельствует о внутреннем параллелизме ал- горитма вычисления )(By по формуле (9). Разделим столбцы матрицы BF ~ между q процессорами так, что в памяти каждого процессора будет храниться по ,is ,1,0  qi столбцов. Теперь каж- дый из q параллельно работающих процессоров будет вычислять сумму ,)( ,, 1 jAjB s j i afBy i    .1,0  qi Очевидно, что каждый из процессоров выполнит iBsN операций умножения и )1( iB sN операций суммирования. Поэтому общее количество операций умножения и суммирования, которые выполняет каждый процессор на первом шаге вычислений, определится выражением ,)12(  iBi sNN .1,0  qi По окончании первого шага вычислений каждый рабочий передает значение ,)(Byi ,1,1  qi мастеру, который и вычисляет ,)()( 1 0 ByBy i q i     тратя на эту процедуру BqN операций суммирования. Поскольку машинное время работы системы параллельных процессоров определяется временем работы процессора, который имеет наибольшее количество столбцов матрицы , ~ BF то общее количество операций умножения и суммирования при реализации параллельного алгоритма вычисления )(By , будет определяться формулой .max 10 Bi qi qNNN   Для случая, когда столбцы матрицы BF ~ равномерно распределены между всеми процессорами, , q z si  ,1,0  qi и .)12(  q q z NN B Таким образом, для реализации последовательного алгоритма вычисления )(By по формуле (9) необходимо выполнить )12( ~  zNN B операций умножения и суммирования. Суммарное количество арифметических операций ,PN выполняемых при реализации параллельного алгоритма, будет определяться количеством опера- ций на приведение матрицы A ~ к верхнему треугольному виду, количеством опе- раций на решение уравнения (15) и количеством операций на вычисления зна- чений )(By . Соответствующим образом суммарное количество арифметических операций SN определяется и для последовательного алгоритма [17]. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 129 Результаты численных экспериментов На рис. 1 показан график суммарного количества операций, необходимых при решении уравнения (12), для параллельного (а) и последовательного (б) алго- ритмов в зависимости от размера матрицы , ~ A а рис. 2 — это зависимость PS NN / от размера матрицы . ~ A Анализ полученных результатов показывает, что при использовании парал- лельного алгоритма решения уравнения (12) эффективность параллельного алго- ритма растет с увеличением размера матрицы . ~ A 100 0 0,5 300 700 500 900 К о л и ч ес тв о а р и ф м ет и ч ес к и х о п ер ац и й ( п ар ал л ел ьн ы й а л го р и тм ) 1 1,5 2,5 2 3,5 3 4 6 10 Размер матрицы A ~ 100 0 300 700 500 900 К о л и ч ес тв о а р и ф м ет и ч ес к и х о п ер ац и й ( п о сл ед о в ат ел ьн ы й а л го р и тм ) 1 7 6 2 5 3 4 8 10 Размер матрицы A ~ а б Рис. 1 100 0 300 700 500 900 N s / N p 40 80 120 160 Размер матрицы A ~ 180 Рис. 2 Заключение Синтез эмпирических моделей оптимальной сложности на принципах гене- тических алгоритмов требует многократного решения системы линейных алгеб- раических уравнений и нахождения значения )(By по формуле (9), на что тратится большая часть машинного времени. Применение параллельного алгоритма для решения поставленных задач дает значительный выигрыш во времени по сравнению с последовательным алгоритмом. Следует отметить, что приведенные расчеты не учитывают потери времени на обмен данными, синхронизацию и конфликты памяти. Учет таких потерь несколько увеличит затраты времени на реализацию параллельного алгоритма, но они будут значительно меньше затрат времени на реализацию последовательного алгоритма решения уравнения (12) и на отыскание значения )(By по формуле (9). 130 ISSN 0572-2691 М.І. Горбійчук, В.М. Медведчук, А.М. Лазорів АНАЛІЗ ПАРАЛЕЛЬНОГО АЛГОРИТМУ СИНТЕЗУ ЕМПІРИЧНИХ МОДЕЛЕЙ НА ПРИНЦИПАХ ГЕНЕТИЧНИХ АЛГОРИТМІВ Розроблено метод синтезу емпіричних моделей з використанням генетич- них алгоритмів, який порівняно з індуктивним методом самоорганізації моделей значно скорочує затрати машинного часу на їх реалізацію. Для підвищення ефективності обчислювального процесу розроблено паралель- ний алгоритм та здійснено його аналіз, що дало змогу оцінити зменшення затрат машинного часу порівняно з послідовним алгоритмом. M.I. Gorbiychuk, V.М. Мedvedchuk, А.N. Lazoriv ANALYSIS OF PARALLEL ALGORITHM OF EMPIRICAL MODELS SYNTHESIS ON THE PRINCIPLES OF GENETIC ALGORITHMS The developed method of synthesis of empirical models using the genetic algo- rithms reduces the computing time for the implementing of empirical models, comparing to the inductive method of self-organizing models. To improve the effectiveness of computing process the parallel algorithm was developed and analyzed, which allows reducing the computing time comparing to the sequen- tial or / FIFO / algorithm. 1. Ермаков С.М., Жиглявский А.А. Математическая теория оптимального эксперимента. — М.: Наука, 1987. — 320 с. 2. Химмельблау Д. Анализ процессов статистическими методами. — М.: Мир, 1973. — 957 с. 3. Грешилов А.А. Математические методы принятия решений. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. — 584 с. 4. Норкин В.И., Кайзер М.А. Об асимптотической эффективности ядерного метода опорных векторов (SVM ) // Кибернетика и системный анализ. — 2009. — № 4. — С. 81–97. 5. Draper N. R., Smith H. Applied regression analysis. — Chichester: Wiley, 1998. — 736 p. 6. A distribution free theory of nonparametric regression / L. Gyorfi, M., Kohler, A. Krzyzak, H. Walk. — New York; Berlin; Heidelberg: Springer, 2002. — 647 p. 7. Хайкин С. Нейронные сети: полный курс. — М.: Вильямс, 2006. — 1104 с. 8. Нагель Э., Ньюмен Д. Теорема Геделя. — М.: Знание, 1970. — 62 с. 9. Ивахненко А.Г., Лапа В.Г. Предвидение случайных процессов. — Киев: Наук. думка, 1969. — 420 с. 10. Ивахненко А.Г. Индуктивный метод самоорганизации моделей сложных систем. — Киев: Наук. думка, 1981. — 286 с. 11. Горбийчук М.И., Когутяк М.И., Заячук Я.И. Индуктивный метод построения математиче- ских моделей газоперекачивающих агрегатов природного газа // Нефтяная и газовая про- мышленность. — 2008. — № 5. — С. 32–35. 12. Справочник по типовым программам моделирования / А.Г. Ивахненко, Ю.В. Коппа, В.С. Степашко и др. — Киев: Техніка, 1980. — 180 с. 13. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы — М.: Горячая линия — Телеком, 2004. — 452 с. 14. Метод синтеза математических моделей на принципах генетических алгоритмов / М.И. Гор- бийчук, М.И. Когутяк, О.Б. Василенко, И.В. Щупак // Разведка и разработка нефтяных и газовых месторождений. — 2009. — № 4 (33). — С. 72–79. 15. Оленев Н.Н., Печенкин Р.В., Чернецов А.М. Параллельное программирование в MatLab и его приложение. — М.: ВЦ РАН, 2007. — 120 с. 16. Вержбицкий В.М. Основы численных методов: учебник для вузов. — М.: Высш. школа, 2002. — 840 с. Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 131 17. Волков Е.А. Численные методы: учебное пособие для вузов. — 2-е изд., исп. — М.: Наука, 1987. — 248 с. Получено 20.04.2015 После доработки 23.07.2015

Анализ параллельного алгоритма синтеза эмпирических моделей на принципах генетических алгоритмов

Репозитарії

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