Шестаков В.С. Оптимизация параметров горных машин. Учебное пособие (811777), страница 8
Текст из файла (страница 8)
Метод покоординатного спуска (метод Гаусса-Зейделя)Суть метода в поочередном одномерном поиске "лучшегорешения" по направлениям координатных осей.Алгоритм метода состоит из следующих этапов (рис. 2.10):1) устанавливаются границы изменения всех переменных:[xmin i, xmax i];2) принимаются значения начальных шагов изменения переменных dxi в относительных единицах (можно задать 0,05 от задаваемого интервала изменения переменной);3) задаются начальной точкой поиска xнi;4) вычисляется значение функции в начальной точке:y = f(xн1, xн2,..., xнi);5) изменяется первая переменная на шаг x1 = x1 + dx1, а значения остальных остаются неизменными, и вновь вычисляется значение функции y=f(x1, x2, ..., xi);6) сравнивается последнее значение функции с предыдущим,если происходит "улучшение" функции, то продолжают изменятьпеременную x1 в том же направлении.
Если сразу же происходит"ухудшение" функции, то изменяют x1 в другом направлении:x1 = x1 - dx1;7) изменение переменной осуществляется до тех пор, покафункция не начнет "ухудшаться", после чего выполняется возврат в"лучшую" найденную точку по переменной x1;8) из найденной точки x1 организуется аналогичным образомизменение переменной x2, а после нахождения лучшего значения повторой переменной - изменение поочередно всех остальных;9) после изменения всех остальных переменных уменьшаютсязначения шагов изменения переменных (обычно в два раза) и повторяются пункты 7...9 до достижения заданной точности.
Дляпрактического применения при реализации в программе можно задавать определенное число циклов по уменьшению шага. Так, при36задании 6 циклов будет достигнута точность 0,16 % от заданногодиапазона изменения переменной, что вполне достаточно дляинженерных расчетов.x2x2maxx2нx2minx1minХ1x1нx1maxРис. 2.10. Иллюстрация метода многомерной поисковой оптимизации покоординатного спускаДостоинствами метода можно считать существенное уменьшение требуемого числа вычислений по сравнению с полным перебором.К недостаткам метода следует отнести то, что в результатеоптимизации может быть найден не глобальный, а локальный оптимум.Рассмотренный алгоритм достаточно сложен для реализацииего в виде программы для ЭВМ, поэтому его не программируюткаждый раз заново, а после первого программирования оформляютв виде подпрограммы и используют для других задач, вызывая подпрограмму в нужном месте.
Для тестирования программы можнорекомендовать использовать функцию, оптимальное решение которой заранее известно, например, минимальное значение функцииy=10+(x1-5)2+(x2-3)2 будет равно 10 при значении x1=5 и x2=3.Пример программы для этой функции с выводом на лист«Покоорд» промежуточных и конечных значений будет иметь следующий вид:37Option ExplicitDim Xmin(10) As Single, Xmax(10) As Single, dx(10) As Single,Xo(10) As Single, Xн(10) As SingleDim Yo As Single, A0, A1, A2, Iv, NNSub Оптимизация_пок()Call Ввод_покIv = 17Call opt_pok_spuska(2, Xн, Xmin, Xmax, Xo, Yo, NN)Worksheets("Покоорд").Range("G12") = Xo(1)Worksheets("Покоорд").Range("G13") = Xo(2)Worksheets("Покоорд").Range("G14") = YoWorksheets("Покоорд").Range("G15") = NNEnd SubSub Ввод_пок()With Worksheets("Покоорд")A0 = .Range("G4"): A1 = .Range("G5"): A2 = .Range("G6")Xmin(1) = .Range("F8"): Xmin(2) = .Range("G8")Xmax(1) = .Range("F9"): Xmax(2) = .Range("G9")Xн(1) = .Range("F10"): Xн(2) = .Range("G10")End WithEnd SubFunction Fy(X() As Single)Dim YY = A0 + (X(1) - A1) ^ 2 + (X(2) - A2) ^ 2Worksheets("Покоорд").Cells(Iv, 1) = X(1)Worksheets("Покоорд").Cells(Iv, 2) = X(2)Worksheets("Покоорд").Cells(Iv, 3) = YIv = Iv + 1Fy = YEnd FunctionSub opt_pok_spuska(N As Integer, Xн() As Single, Xmin() As Single, Xmax() AsSingle, X() As Single, Yo As Single, NN)' Подпрограмма оптимизации методом покоординатного спуска' Входные данные' N - количество переменных оптимизации' Хн - массив с начальными значениями переменных' Хmin- массив с минимально допустимыми значениями переменных' Хmax- массив с максимально допустимыми значениями переменных' Выходные данные' Х - массив с оптимальными значениями переменных' YO - наилучшее значение функции после оптимизации38' Целевая функция должная быть оформлена подпрограммой-функцией' Function FY(x), где Х - массив со значениями переменных.Dim i, j, k1 As Integer, dx(10) As SingleDim Y As Single, B As BooleanYo = 1E+31For i = 1 To Ndx(i) = (Xmax(i) - Xmin(i)) / 20 'Начальный шаг изменения переменнойNext iNN = 1'Переменная для выдачи числа вычислений функцииFor i = 1 To NX(i) = Xн(i)'Занесение в массив Х начальных значенийNext iY = Fy(X)'Вызов подпрограммы расчета функцииj=1'Переменная для цикла оптимизации уменьшения шагаDo While (j <= 7) 'Начало цикла оптимизацииFor i = 1 To N'Цикл поочередного изменения всех переменныхB = Truek1 = 0'Переменная для возврата в "лучшую" точкуWhile B'Цикл изменения при увеличении переменнойk1 = k1 + 1If Y < Yo Then Yo = YX(i) = X(i) + dx(i) 'Изменение переменныхIf X(i) > Xmax(i) ThenX(i) = Xmax(i)B = False'Выход из цикла при достижении границыEnd IfNN = NN + 1Y = Fy(X)'Вызов подпрограммы расчета функцииIf Y > Yo ThenB = FalseX(i) = X(i) - dx(i) 'Возврат в лучшую точкуEnd IfWend '----while b doB = TrueWhile B And (k1 <= 1) 'Цикл при уменьшении переменнойIf Y < Yo Then Yo = YX(i) = X(i) - dx(i)'Изменение переменныхIf X(i) < Xmin(i) ThenПрограмма оптимиX(i) = Xmin(i)зации методом покоB = Falseординатного спускаEnd If39NN = NN + 1Y = Fy(X)'Вызов подпрограммы расчета функцииIf Y > Yo ThenX(i) = X(i) + dx(i)B = False'Для выхода из цикла по ВEnd IfWend' Завершение цикла while b dodx(i) = dx(i) / 2Next i'Конец цикла изменения переменныхj=j+1Loop' while j<=7 по заданному числу циклов оптимизацииEnd Sub2.2.4.
Метод случайного поискаРассмотрим метод, который лишен недостатка предыдущего,- обеспечивает поиск глобального оптимума. Из-за простоты алгоритма он используется очень часто для проведения оптимизации.Метод основан на достижении заданной вероятности получения оптимального решения.
Требуемое число вычислений для достижениязадаваемой вероятности не зависит от числа переменных проектирования.Суть метода заключается в следующем. Интервал изменениякаждой переменной делится на равное число ячеек (наиболее просто организовать алгоритм вычислений, если поделить интервал начисло ячеек, кратное 10). Затем, пользуясь случайными числами,осуществляют вычисление целевой функции требуемое число раз.После сравнения полученных значений целевой функции определяется "лучшая" область, где находятся оптимальные значения переменных. Случайные числа могут быть взяты из таблиц случайныхчисел или получены специальной программой - генератором случайных чисел.Рассмотрим вначале определение требуемого числа вычислений функции для одной переменной (рис.
2.11). Если разбить интервал ее изменения на k=10 ячеек (доля изменения переменной приэтом будет равна f=1/k=0.1) и вычислить один раз функцию, то, какизвестно, вероятность того, что мы получили оптимальное решение,Po = 0,1, т. е. равна доле изменения переменной, Po =f .4041yА что будет, если выполнимдва вычисления? По логикевероятность должна возрасти, но нам известно из курса"Теория вероятности", что сувеличением числа попытоквероятности перемножаются, поэтому возникает абсурдная ситуация, что с увеxличением числа расчетовxminxmaxснижается вероятность. НоРис.
2. 11. Схема к определениювсе приходит в норму, еслитребуемого числа вычислений длярассматривать вероятностьодной переменнойне поиска оптимального решения, а противоположную ей вероятность пропуска оптимальногорешения, которая определится по известному выражениюPп = 1 - Po , или через долю, Pп = 1 – f .После М вычислений вероятность пропуска лучшего значенияPп =(1 - f ) М,а вероятность получения оптимального решенияPo = 1 -Pп = 1 - (1 - f ) М .Для определения М по задаваемым значениям Po и f необходимо прологарифмировать выражениеМ = ln(1-Po) / ln( 1-f ).Требуемое число вычислений функции, согласно полученному выражению, в данном методе не зависит от числа переменных(именно число вычислений функции, а не просто всех вычислений,включающее и вычисление значений самих переменных).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
