4. Потенциальное экономическое влияние Договоренности о взаимном признании МКМВ. Заключительный отчет. МБМВ, Севр, Франция, KPMG Consulting, 2002. [Электрон. версия] http://www.bipm.org/utils/common/pdf/KPMG_report.pdf (дата обращения 18.10.2014 г.)
5. Договоренность о взаимном признании национальных измерительных эталонов и сертификатов калибровки и измерений, выдаваемых национальными метрологическими институтами (Mutual Recognition Arrangement — MRA). Севр, Франция.1999.
6. Федеральный закон Российской Федерации от 26 июня 2008 года № 102-ФЗ «Об обеспечении единства измерений».
7. Приказ Минпромторга РФ от 17 июня 2009 года № 529 «Об утверждении Стратегии обеспечения единства измерений в России до 2015 года».
8. Распоряжение Правительства РФ от 27 декабря 2012 г. № 2539-р о государственной программе РФ «Развитие промышленности и повышение ее конкурентоспособности». Подпрограмма 12 «Развитие системы технического регулирования, стандартизации и обеспечения единства измерений».
9. Приказ Росстандарта от 19.09.2014 № 1360 «Об утверждении ведомственной целевой программы «Проведение фундаментальных исследований в области метрологии, разработки государственных (в том числе первичных) эталонов единиц величин».
10. Слаев В. А., Бапалаев В. А., Синяков А. И. Теория систем воспроизведения единиц и передачи их размеров / Под ред. В. А. Слаева. СПб.: Профессионал, 2004.
Дата принятия 18.12.2014 г.
519.853.62:006.015.7
Комбинированный алгоритм оптимизации и его применение к решению метрологических задач
Ю. С. СЫСОЕВ
Волгодонский инженерно-технический институт — филиал Национального исследовательского ядерного университета «МИФИ», Волгодонск, Россия, e-mail: sysoev2004@mail.ru
Представлен комбинированный алгоритм оптимизации, аналогичный алгоритму покоординатного спуска (не по одномерным пространствам, а по подпространствам различной размерности) и методу градиентного спуска. Выбор подпространств, по которым осуществляется спуск, определяется абсолютным значением координат градиента в очередной итерационной точке.
Ключевые слова: оптимизация, метод градиентного спуска, итерации, эффект оврагов.
The combined optimization algorithm combining an analogue of coordinated lowering algorithm (not by one-dimensional spaces, but by the different dimension under-spaces) and of a method of gradient lowering are presented. The choice of under-spaces on which the lowering is made is determined by absolute value of gradient coordinates in the regular iterative point.
Key words: optimization, gradient loweringmethod, iterations, ravine method.
Решение целого ряда метрологических задач связано с поиском оптимальных значений тех или иных параметров [1—4]. При этом приходится искать минимальные (или максимальные) значения гладких целевых функций у = /(х) многих переменных х = (х1, х2, ..., х"), заданных в евклидовом пространстве Н с системой координат, определенной орто-нормированным базисом. Поскольку целевые функции в указанных работах имели сильно выраженную овражную структуру, то стандартные методы градиентного спуска из-за их медленной сходимости не позволяли получить искомые оптимальные значения параметров с заданной точностью. Поэтому для нахождения результата с требуемой точностью приходилось для каждой целевой функции строить индивидуальный алгоритм оптимизации.
Суть построения алгоритмов сводили к разовому выбору нескольких вложенных друг в друга подпространств, строго фиксированных на всем периоде работы алгоритма [1—4]. По этим подпространствам последовательно проводили оптимизацию на каждом шаге итерационного процесса. Подпространства выбирали на основе предварительного анализа формул, задающих целевую функцию, или визуальной оценки скорости изменения целевой функции по различным параметрам. Однако для многих целевых функций этот процесс достаточно сложен, требует трудоемкого анализа и не всегда приводит к нужному результату. 3 адача существенно усложняется, когда требуется учитывать соотношения между скоростями изменения функции по разным переменным, зависящие от итерационной точки, в которой рассматрива-
ется функция. Таким образом, необходимо создать гибкий алгоритм оптимизации, предусматривающий операции по определению указанных подпространств на каждом шаге оптимизации. Такая процедура позволит не только отказаться от «угадывания» этих подпространств, но и разрешит изменять их в процессе оптимизации.
Алгоритм, предложенный в настоящей работе, удовлетворяет всем указанным требованиям. Он является комбинированным, сочетающим аналог алгоритма покоординатного спуска (организованный не только по одномерным, но и по многомерным пространствам различной размерности) и метода градиентного спуска. Выбор подпространств спуска определяется абсолютным значением координат градиента в очередной итерационной точке. При таком подходе в процессе реализации алгоритма на каждом его шаге будет меняться набор подпространств спуска, поскольку в рекомендуемом автором процессе оптимизации учитывается скорость изменения целевой функции по различным переменным в соответствующей итерационной точке. Следовательно, алгоритм получится более гибким, чем приведенные в [1—4], и позволит добиться высокой точности при решении оптимизационных задач.
Одной из основных проблем, которую приходится решать при построении любого итерационного метода оптимизации функций многих переменных, является выбор направления спуска. В этой работе алгоритм строится так, чтобы в течение одного шага оптимизации направление могло изменяться несколько раз. Подобная последовательность направлений спуска на каждом конкретном шаге определяет вложенные подпространства.
Поскольку задача нахождения максимума функции сводится к нахождению ее минимума (и наоборот), то в дальнейшем будем рассматривать только минимизацию функции.
Выбор направления спуска должен осуществляться таким образом, чтобы на нем можно было получить точку, значение функции в которой не больше значения в исходной точке. Такое направление назовем допустимым, а вектор, его определяющий, будем считать допустимым в ектором. Как и в любом итерационном процессе минимизации, построим последовательность точек х1, х2, х3, ..., при которой соответствующая последовательность ^(х1), ^(х2), ^х3), ... значений функции будет монотонно невозрастающей. Процесс перехода от предыдущей итерационной точки к последующей обозначим как итерационный шаг или шаг оптимизации.
Рассмотрим произвольный вектор а = (а1, а2, а3, ..., ап), и заменим в нем какие-нибудь координаты нулями. Для определенности будем считать, что это будут две первые координаты а1, а2. Получим новый вектор а1 = (0, 0, а3, ..., ап). Тогда определим косинус угла между векторами:
cos ф= X (aj
j=3
= Л (aj)2
(1)
получить вектор, имеющий ближайший к п/2 угол с вектором а, нужно заменить нулями две его наибольшие по модулю координаты. Аналогичное утверждение можно сформулировать не только для двух координат вектора а, но и для любого другого их количества.
Опишем основные принципы построения одного шага итераций от точки хк к хк+1, так как традиционные части алгоритма оптимизации представлены в [5, 6].
Описание шага оптимизации. Найдем градиент функции zk = Vf(xk) в точке хк и проведем один шаг градиентного спуска [5] с дроблением шага исходя из точки хк. Для этого воспользуемся равенством [5]:
xk = xk-ak Vf (xk )■
(2)
Из (1) следует, что чем большие по модулю координаты в векторе a будут заменены нулевыми значениями, тем меньше будет значение cos ф и тем ближе к п/2 угол между вектором a и вновь полученным вектором. Таким образом, чтобы
где ак — некоторое положительное число.
При необходимости уменьшив в два раза последовательно положительное число ак, при некотором значении а к
получим новую точку х1 = хк-аk'Vf {хк), для которой будет
выполняться неравенство f (х]< f {хк).
При овражной структуре целевой функции из-за малости шагов спуска в направлениях антиградиентов часто не удается получить результат требуемой точности. Поэтому следующий спуск на этом же шаге оптимизации осуществим в направлении допустимого вектора, имеющего угол с вектором Vf(xk), ближайший к п/2. Из изложенного следует, что этот вектор можно получить из Vf(xk) заменой наибольших по модулю координат, имеющих одинаковый порядок (выделенные координаты), нулевыми значениями. Рассмотрим подпространство Н1 пространства Н, полученное при замене у всех векторов Н нулевыми значениями тех координат, номера которых совпадают с номерами выделенных координат. Через Н0 обозначим подпространство Н, которое получается заменой нулевыми значениями тех координат векторов этого пространства, номера которых не совпадают с
номерами выделенных координат. Подпространство Н0 будет ортогональным дополнением к Н1 в пространстве Н. В дальнейшем все элементы подпространства пространства Н,
включая Н1, Н1, будем рассматривать как элементы Н, дополняя соответствующие координаты нулями. Это позволит совершать операции сложения и вычитания векторов из разных подпространств. Обозначим Р1, Р0 операторы проектирования, заданные на пространстве Н и действующие в подпространства Н1, Н0], соответственно. Применив введенные обозначения, запишем равенство, определяющее продолжение операции спуска в пределах рассматриваемого шага оптимизации:
x2 = xk-a^Vf (xk)] - P0(xk) + Plixk). (3)
Направления спуска, определяемые формулами (2), (3), являются допустимыми. Выберем в равенстве (3) началь-
ное значение ак в 25 раз больше, чем начальное значение а.^ (можно также использовать ак, равное начальному значению ак из (2), однако при этом время работы алгоритма может увеличиться). При необходимости уменьшив последовательно в два раза ак в (3) и сравнив значения функции во вновь полученных точках со значением f (хк), получим точку х2, для которой будет справедливо неравенство
f (х2) * f (хД
Будем считать подпространство Н1 исходным. Тогда применив P1[Vf(xk)] вместо У^хк), как и в предыдущем случае, найдем новое подпространство Н2 пространства Н1, а значит, и пространства Н. Определим подпространство н2 как ортого
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.