Modification of the method of sequential simplex planning and its application to the solution of optimization problems

Abstract

A modification of the algorithm Nealder-Mida is proposed when the point, which determines the direction of reflection the “worst” node, is chosen based on the values of minimazed functions in the rest of the vertices of a simplex. There was investigated the efficiency of the proposed modifications on the test functions.

Full Text

Предлагаемая модификация Метод симплексного планирования Нелдера-Мида является неградиентным методом нелинейной оптимизации для поиска минимума целевой функции . Симплексом в n-мерном евклидовом пространстве называется многогранник с количеством вершин n+1, не лежащих в одной гиперплоскости. Для случая n=2 – это треугольник, для случая n=3 – тетраэдр. Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума с помощью процедур отражения, растяжения, сжатия и редукции симплекса [2-4]. Каждая итерация начинается с упорядочения вершин таким образом, чтобы было выполнено условие: . (1) С точки зрения минимизации считается наилучшей, а наихудшей вершиной симплекса. Затем вычисляется центр тяжести первых n точек симплекса, где . На линии , проходящий через точки и , рассматриваются точка отражения , точки внутренного и внешнего сжатия и , точка растижения . Исходя из соответствующих проверок, вершина симплекса заменяется одной из точек , для которой целевая функция уменьшает свое значение (рисунок 1). Рисунок 1 Если данный шаг проходит неудачно (точки с «лучшим» значением функции на линии отображения не найдено), симплекс редукцируется: Цикл поиска минимума целевой функции повторяется до тех пор, пока не выполняется критерий остановки, например . Если требуемая точность достигнута, выводится значение как минимальное значение целевой функции. В этой статье рассматривается модифицированный метод симплексного планирования, который для поиска минимума ряда тестовых функций требует меньше процессорного времени, чем исходной метод. В методе Нелдера-Мида центр тяжести равномерно удален от первых n вершин симплекса. Предлагаемая модификация основана на идее весовых коэффициентов. В этом случае по формуле (2) рассчитывается средневзвешенный центр грани, противостоящей «наихудшей» вершине. , (2) где (3) Предлагается выбрать весовые коэффициенты так, чтобы центр был бы ближе к той вершине симплекса, по направлению к которой целевая функция быстрее убывает. По формуле (4) сначала вычисляют весовые коэффициенты (4) Здесь – расстояние между вершинами и , а числа – координаты Весовой коэффициент есть относительное изменение целевой функции , на вершинах симплекса и . Чем больше это относительное изменение , тем больше вероятность того, что значения целевой функции по направлению к вершине убывают быстрее. Целесообразно новую вершину искать по направлению к тем вершинам симплекса, для которых весовые коэффициенты больше,. Отметим, что весовые коэффициенты не удовлетворяют условию , поэтому по формуле (5) рассчитывают из коэффициентов новые нормированные весовые коэффициенты . (5) Для всяких i, j, если , то и соотношение весовых коэффициентов не изменяется. Полученные коэффициенты полностью удовлетворяют условию (3). После вычисления весовых коэффициентов, определяется средневзвешенный центр грани симплекса: Весовой центр ближе к той вершине симплекса, для которой весовой коэффициент больше. Затем вершина заменяется точкой линии , уменьшающей значение целевой функции. Данная модификация меняет направление поиска новой вершины симплекса, что повышает эффективность алгоритма. В качестве примера рассмотрим тестовую функцию “Trid”: . Данная функция принимает свое минимальное значение на точке . На рисунке 2 представлен симплекс с вершинами , где . Поскольку , то вершина считается наилучшей вершиной симплекса, а – наихудшей вершиной. Коэффициенты будут рассчитываться следующим образом: Рисунок 2 С помощью формулы (5) определяем коэффициенты , для которых : Тогда весовой центр симплекса будет определяться следующим образом: . Из рисунка 2 видно, что полученный весовой центр симплекса находится ближе к наилучшей вершине и к точке минимума целевой функции , чем центр тяжести , определяющийся методом Нелдера-Мида. Тем самым, с большой вероятностью можно сказать, что на точках линии целевая функция примет меньшие значения, чем на точках линии , (линия проходит через точки и , а линия через точки и ). Для достижения глобального минимума целевой функции нужно повторять процедуру поиска несколько раз. Описание алгоритма Шаг 1.1. В области определения целевой функции строят начальный регулярный симплекс . Для этого сначала случайным образом генерируют вершину , а остальные вершины симплекса определяют следующим образом: , где единичные координатные векторы, h – ребро симплекса. Вычисляют значения целевой функции . Выбирают число, Шаг 1.2. Вершины симплекса сортируют так, что Основной цикл Пока , повторяется последовательность 2-6 шагов, в противном случае работа алгоритма завершается и выводится вершина симплекса и значение . Шаг 2. Определяют весовые коэффициенты , , – расстояние и вершин, – координаты вершин Шаг 3. Нормированием коэффициентов вычисляют новые весовые коэффициенты . Коэффициенты удовлетворяют условию . Шаг 4. Определяют средневзвешенный центр первых n вершин симплекса. Шаг 5. На линии , определяют точку отражения . при . Находят значение целевой функции на этой точке. Дальше, как в методе Нелдера-Мида, в зависимости от значения , наихудшая вершина симплекса шагами 5.1-5.4 заменяется новой точкой, находящейся на линии . Шаг 5.1. Если , то наихудшая вершина симплекса заменяется точкой отражения , делается переход на шаг 2. Шаг 5.2. Если , проводят операцию растяжения. , при Если , то наихудшую вершину симплекса заменяют точкой и переходят на шаг 2. В противном случае вершину заменяют точкой и переходят на шаг 2. Шаг 5.3. Если , делают операцию внешнего сжатия , при Если точка лучше, чем точка отражения, то есть , вершина заменяется точкой , переходят на шаг 2. В противном случае переходят на шаг 6. Шаг 5.4. Если , делается операция внутреннего сжатия , при Если точка лучше, чем вершина симплекса , то есть , вершина заменяется точкой , переходят на шаг 2. В противном случае переходят на шаг 6. Шаг 6. Проводим операцию редукции симплекса. Тестирование предложенной модификации Приведенные ниже тестовые функции оптимизации были тестированы методом Нелдера-Мида и предложенной модификацией весовых коэффициентов (ВК), каждый по 100 раз. Каждый раз первая вершина начального симплекса была выбрана из области поиска тестовой функции произвольным образом. В таблице 1 приведено сравнение методов Нелдера-Мида и предложенной модификации по среднему процессорному времени (CPU-сек.) и среднему числу расчета значений тестовой функции (вызовов функции) для одного теста. Тестирование проводилось на компьютере с 2,66 ГГц процессорной мощностью и 3 Gb оперативной памятью. На рисунке 3 приведены данные о средних затратах процессорного времени для поиска минимума тестовых функций для обоих методов. После названия тестовой функции приведено число переменных данной функции. Для каждой тестовой функции отмечено, насколько сокращаются средние затраты процессорного времени при использовании модифицированного метода для поиска минимума целевой функции по сравнению с методом Нелдера-Мида. Из рисунка 3 и таблицы 1 видно, что эффективность модифицированного метода возрастает при увеличении числа переменных тестовых функций. Например, для поиска минимального значения тестовой функции “Trid” средние затраты процессорного времени для n=2 сокращаются на 2.08%-ов, для n=4 – на 8.77%-ов, а для n=6 на 18.34%-ов. Таблица 1 Сравнение методов Нелдера-Мида и предложенной модификации (n – число переменных) N Название тестовой функции n Нелдер-Мид Модификация ВК CPU-сек. Число выз. функции CPU-сек. Число выз. функции 1 Trid Function 2 0.048 101.58 0.047 102.25 2 Trid Function 4 0.171 285.69 0.156 253.26 3 Trid Function 6 0.529 567.08 0.432 471.5 4 Zakharov Function 2 0.048 109.69 0.046 108.75 5 Zakharov Function 4 0.181 291.62 0.163 263.14 6 Zakharov Function 6 0.583 619 0.479 515.71 7 Helical valley Function 3 0.131 255.49 0.141 281.52 8 Gaussian Function 3 0.123 183.54 0.113 177.2 9 Box 3 dim. Function 3 0.127 267.05 0.099 266.1 10 Colville Function 4 0.372 603.63 0.368 601.57 11 Branin Function 2 0.047 108.67 0.043 107.39 12 Sphere Function 3 0.081 165.87 0.076 159.01 13 Sphere Function 5 0.241 338.97 0.209 291.45 14 Sphere Function 10 2.347 1144.98 1.132 682.38 15 Sum Squares Function 3 0.087 177.16 0.079 168.29 16 Sum Squares Function 5 0.259 360.28 0.224 313.69 17 Sum Squares Function 10 2.939 1276.25 1.386 781.67 18 Rotated hyper-ellipsoid 3 0.106 198.44 0.105 193.21 19 Rotated hyper-ellipsoid 5 0.305 420.46 0.276 380.31 Список тестовых функций 1. Trid Function: , Область поиска: Минимум функции ( – точки минимума приведенных тестовых функций): при , ; при , ; при 2. Zakharov Function: , Область поиска: . Минимум функции: 3. Helical valley Function: , Область поиска: Минимум функции: Рисунок 3. Сравнение средних затрат процессорного времени (сек.) для поиска минимума тестовых функций 4. Gaussian Function: y=(0.0009, 0.0044, 0.0175, 0.054, 0.1295, 0.242, 0.3521, 0.3989, 0.3521, 0.242, 0.1295, 0.054, 0.0175, 0.0044, 0.0009); Область поиска: Минимум функции: 5 Box 3 dimensional Function: Область поиска: . Минимум функции: 6. Colville Function: 100(x12-x2)2+(x1-1)2+(x3-1)2+90(x32-x4)2+10.1((x2-1)2+(x4-1)2)+19.8(x2-1)(x4-1) Область поиска: Минимум функции: 7. Branin Function: , Область поиска: Минимум функции: 8. Sphere Function: , Область поиска: Минимум функции: 9. Sum Squares Function: , Область поиска: Минимум функции: 10. Rotated hyper-ellipsoid function: , Область поиска: Минимум функции: Применение метода симплексного планирования в задачах оптимизации Предложенная модификация последовательного симплексного планирования может быть применена для решения задачи равномерного распределения ресурсов по времени. Пусть организация осуществляет комплексную программу, состоящую из n проектов. Известны функции , i=1,…,n, характеризующие потребность ресурсов в момент времени t для реализации проекта i. Задана продолжительность каждого проекта , самый ранний момент начала и самый поздний момент окончания . Если реализация i-го проекта начнется с задержкой , распределение ресурсов будет соответствовать функции , где . Суммарная потребность в ресурсах в момент времени t равна . Требуется выбрать такие моменты начала выполнения проектов , чтобы распределение суммарных ресурсов по времени было наиболее равномерным. Под равномерным распределением ресурсов понимается такое распределение, когда значения суммарной функции как можно меньше отличаются от средней потребности M, где (b-a) – продолжительность комплексной программы. В [1] в качестве оценки близости потребности ресурсов к среднему значению выбран квадратичный критерий. Тогда задача равномерного распределения ресурсов сходится к задаче