Шестаков В.С. Оптимизация параметров горных машин. Учебное пособие (811777), страница 7
Текст из файла (страница 7)
Аргументы x1, x2 определятся по выражениям:x1 xmin 0.618 ( xmax xmin )x2 xmax 0.618 ( xmax xmin )y(2.6)0.618(хmax- хmin)0.618(хmax- хmin)0.618(х'max- х'min)хminY2Y1Y ’2Y ’1х2хmax 1-й шагх1х'1х'2х'minх'max 2-й шагРис. 2. 8. Схема к методу золотого сеченияВ этих точках и вычисляются значения функции (рис. 2. 8).После сравнения полученных значений функции, уменьшается рассматриваемый интервал путем исключения участка между точкой, в29которых функция имеет "худшее" из сравниваемых значение, иближайшим концом рассматриваемого интервала.
По рис. 2.8 напервом шаге это будет [xmin, x2].Если для оставшегося интервала снова провести вычислениеаргументов х1 и х2 по (2.6), то окажется, что одна из точек делениянового интервала совпадает с ранее вычисленной (можете проверить это положение построением в масштабе подобного рисунка).Значение функции в этой точке известно, поэтому не требуется еевычислять. Таким образом, при рассмотрении каждого уменьшенного интервала требуется вычислять значение функции толькоодин раз.Запишем алгоритм метода:1) задается интервал возможного изменения проектного параметра при оптимизации [xmin, xmax] и конечный интервал Δx, придостижении которого прекращаются расчеты;2) вычисляются значения переменной оптимизации для точекделения рассматриваемого интервала:x1 xmin 0,618 ( xmax xmin ) ;x 2 xmax 0,618 ( xmax xmin ) ;3) вычисляются значения целевой функции при найденныхзначениях переменной (в обеих точках при первом делении и только в той точке, в которой целевая функция еще не вычислялась приследующих делениях).
Значения целевой функции сравниваютсямежду собой;4) после сравнения значений функции между собой уменьшают рассматриваемый интервал путем исключения из рассмотренияучастка, расположенного между точкой, в которой функция имеет"худшее" из сравниваемых значений, и ближайшим концом рассматриваемого интервала. К примеру, при первом делении нарис. 2.8 при поиске минимума исключают из рассмотрения интервал [xmin, x2];5) оставшийся интервал снова принимают за интервал поиска.Этапы 2..5 повторяют до достижения заданной точности.Примечание: x, также как и в методе дихотомии, лучшевсего задавать в относительных единицах, а при сравнении достижения заданной точности применить абсолютное значение30xа= ( xmax - xmin) . x.Пример программы применения метода золотого сечения дляпоиска оптимального решения функции y=(x-5)2.
В программе предусмотрен вывод промежуточных значений для проверки алгоритмаметода.Option ExplicitDim I As IntegerSub Оптимизация_методом_золотого_сечения()Dim Xmin As Single, Xmax As Single, dx As Single, Xomin As SingleDim Xomax As Single, Y1 As Single, Y2 As Singlei = 14Call Ввод_зол_сечения(Xmin, Xmax, dx)Call Мет_зол_сечения(Xmin, Xmax, dx, Xomin, Xomax, Y1, Y2)Call Вывод_зол_сечения(Xomin, Xomax, Y1, Y2)End SubSub Ввод_зол_сечения(Xmin As Single, Xmax As Single, dxa As Single)Dim dx As SingleXmin = Worksheets("Зол_Сеч").Range("D3")Xmax = Worksheets("Зол_Сеч ").Range("D4")dx = Worksheets("Зол_Сеч").Range("D5")dxa= dx*( Xmax- Xmin)End SubSub Мет _зол_сечения(Xmin As Single, Xmax As Single, N As Long, _X1 As Single, X2 As Single, Y1 As Single, Y2 As Single)X1 = Xmin + 0.618 * (Xmax - Xmin)X2 = Xmax - 0.618 * (Xmax - Xmin)Y1 = Fx(X1)Y2 = Fx(X2)While (Xmax - Xmin) >= dxIf Y1 < Y2 ThenXmin = X2X2 = X1Y2 = Y1X1 = Xmin + 0.618 * (Xmax - Xmin)Y1 = Fx(X1)ElseXmax = X1:X1 = X2: Y1 = Y2X2 = Xmax - 0.618 * (Xmax - Xmin)Y2 = Fx(X2)End If31WendEnd SubFunction Fx(X As Single) As SingleFx = (X - 5) ^ 2Worksheets("Зол_Сеч ").Cells(i, 1) = XWorksheets("Зол_Сеч ").Cells(i, 2) = (X - 5) ^ 2i=i+1End FunctionSub Вывод_зол_сечения(Xomin As Single, Xomax As Single, Yo1 As Single, _Yo2 As Single)Worksheets("Зол_Сеч ").Range("D7") = XominПрограмма оптимиWorksheets("Зол_Сеч ").Range("D8") = Xomaxзации методом зоWorksheets("Зол_Сеч ").Range("D9") = Yo1лотого сеченияWorksheets("Зол_Сеч ").Range("D10") = Yo2Worksheets("Зол_Сеч ").Range("D11") = I-14End SubПример расположения информации на листе Excel123456789101112131415161718192021222324АВСПроверка оптимизации по методу золотого сеченияИсходные данные1.
Минимальное значение переменной-102. Максимальное значение переменной103. Точность поиска (в относительных единицах)0,001Оптимальное значение1. Начало интервала с оптимальным значением x15.0005932. Конец интервала с оптимальным значением x24.9970773. Значение функции при x13.51E-074. Значение функции при x28.54E-065. Число вычислений функции17Изменение переменной и целевой функции в процессе оптимизацииПеременнаяФункция2,3606,9696-2,36054,16965,2780,07767,0824,33274,1640,69955,9670,93494,8520,02184,5890,16855,0150,00025,1160,01344,9530,0022322.1.4.
Сравнение методов одномерной поисковой оптимизацииКритериями сравнения рассмотренных методов поиска оптимального решения являются их универсальность и эффективность.Универсальность методов означает, что их легко можно применять для решения самых разнообразных задач. С точки зренияуниверсальности лучшим из рассмотренных будет метод прямогоперебора, так как его можно применять и для неунимодальныхфункций, если они достаточно гладкие. Использование для неунимодальных функций методов дихотомии и золотого сечения можетпривести к нахождению не глобального, а локального оптимума.Под эффективностью алгоритма обычно понимают число вычислений целевой функции, необходимое для достижения требуемой точности.
В табл. 2.1 приведены коэффициенты дробления интервала неопределенности в зависимости от числа вычислений.Из табл. 2.1 следует, что лучшим методом по эффективностиявляется метод золотого сечения, худшим - прямого перебора.Таблица 2.1Сравнение методов одномерного поиска по значениямкоэффициента дробления интервала поискаЧисло вычислений функции4567891011121314151617181920Прямого перебораДихотомии0,40,3330,2860,250,2220,20,1820,1670,1540,1430,1330,1250,1180,1110,1050,10,0950,250,1250,06250,03120,01560,007810,003930,001950,00097633Золотого сечения0,2360,1460,090,0560,03450,02130,01320,008130,005020,003110,001920,001190,0007330,004530,000280,0001780,0001072.2.
Методы многомерной поисковой оптимизации2.2.1. Особенности многомерной поисковой оптимизацииПрежде всего выясним, отличается ли процесс поиска «наилучшего» решения для двух и более переменных от поиска при одной переменной. Можно ли применять методы одномерной поисковой оптимизации для двух переменных.Для графической иллюстрации метода рассмотрим оптимизацию для двух переменных.
Изображение для двух переменныхдолжно быть объемным (переменные откладываются по осям x и y,а функция - по z), что приводит при некоторых функциях к сложным рисункам. Для упрощения изображений функции можно применить тот же подход, что используется для представления возвышенностей и впадин на топографических картах, – линиями равногоуровня. Эти линии получены путем соединения точек одинаковыхзначений целевой функции.
Иллюстрация метода показана на рис.2. 9. При y1>y2>…yK будет изображена впадина, в противном случае– возвышенность. Для унимодальных функций будет одна впадина(возвышенность), а для неунимодальных – несколько. Следует помнить, что до проведения оптимизации нам эти линии неизвестны,иначе мы бы сразу нашли оптимальное решение указанием нижнейточки.Подумаем, каким образом можно построить алгоритм поискаоптимального решения. Обычно всегда следует предложение разбить каждую переменную в допустимом интервале на отрезки и вычислить функцию во всех полученных точках, после сравнения результатов выявляется «лучшая» точка.
Это будет метод полного перебора. Такой алгоритм будет прекрасно работать, но ему будетприсущ очевидный недостаток – большое число вычислений длядостижения высокой точности. Причем с увеличением числа переменных объем вычислений, необходимых для поиска оптимальногорешения с заданной точностью, увеличивается в степенной зависимости, показатель функции равен количеству переменных проектирования. Так, если в случае одномерного пространства для достижения точности поиска, равной 0,1 от начального интервала поиска,методом прямого перебора требуется 21 вычисление, то при двухпеременных для выполнения полного перебора всех решений с такой же точностью потребуется 2121=441 вычисление. При трех пе34x2y1y2y3y4yKyK-1x2maxx2minx1x1minx1maxРис.
2.9. Схема к пояснению методов многомерной поисковой оптимизацииременных это число составит 212121=9261, при четырех - 194481,при пяти - 4084101.Таким образом, с увеличением числа переменных, если неприменять специальных методов поиска оптимального решения,существенно увеличивается требуемое число вычислений, необходимых для получения решения.
При сложных целевых функцияхдля выполнения большого числа вычислений потребуются большиезатраты времени на поиск оптимума. Поэтому для поиска оптимального решения при двух и более переменных проектированияиспользуют специальные методы оптимизации.2.2.2. Классификация методов многомерной поисковойоптимизацииМетоды оптимизации принято делить на группы, в зависимости от использования производных целевой функции для поискаоптимального решения: нулевого порядка (покоординатного спуска, случайногопоиска, поиска по симплексу, деформируемого многогранника и35др.), в них производная не используется; первого порядка (градиентный, наискорейшего спуска,сопряженных градиентов и др.), в них используется первая производная; второго порядка (Ньютона и др.), в них используется вторая производная.2.2.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
