В различных областях научно-исследовательской и производственной деятельности человека встречается задача обработки экспериментальных данных с целью извлечения из них закономерностей, описывающих различные процессы и явления. Если изучающиеся закономерности представляются в виде математических моделей, они носят название моделей идентификации, а задача их восстановления – задачи идентификации.

Построение математических моделей разбивается на две подзадачи – структурную идентификацию (определение конкретной формы, структуры модели) и параметрическую идентификацию (определение параметров модели при уже известной её структуре). Остановимся на задаче параметрической идентификации.

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

В качестве решения данных проблем предлагается представить задачу параметрической идентификации в виде задачи многоэкстремальной оптимизации. Минимизируемой функцией в данном случае будет сумма квадратов отклонений расчетных значений от экспериментальных данных.

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

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

Следует отметить, что регулярные поисковые методы решения многомерных оптимизационных задач как правило сводят многомерную задачу к системе одномерных подзадач. Редукция размерности при решении таких задач может основываться на некоторых фундаментальных свойствах многомерных функций и многомерных пространств.

Один из подходов использует отображение многомерной области поиска на одномерный интервал с помощью кривых Пеано. Итальянским математиком Пеано было доказано существование кривых, заданных непрерывными координатными функциями однозначно отображающих отрезок [0,1] на N-мерный гиперкуб D [2].

Такие кривые, называемые также развертками Пеано, позволяют свести многомерную задачу условной минимизации в области D к одномерной задаче условной минимизации на отрезке [0,1]

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

При параллельной реализации индексного метода решающие правила алгоритма в целом совпадают с правилами последовательного алгоритма, кроме способа проведения испытания:

• После выбора точки очередной итерации поиска процессор информирует о произведенном выборе все остальные процессоры;

• Каждый процессор после проведения испытания в точке итерации передает полученный индекс и значение функции всем процессорам вычислительной системы;

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

Список литературы

1. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. (Информационно-статистические алгоритмы). М.: Наука, 1978.

2. Баркалов К.А. Ускорение сходимости в задачах условной глобальной оптимизации. Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2005.

3. Strongin R.G., Sergeyev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. Kluwer Academic Publishers, Dordrecht, 2000.