Шестаков В.С. Оптимизация параметров горных машин. Учебное пособие (811777), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

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

Итак, задано 20 делений начального интервала. С учетом того, что выполняются вычисления по краям начального интервала, потребуется провести 21 вычисление функции,23а с учетом того, что оптимальное решение в поисковой оптимизации выводится в виде интервала из двух участков, то после первичного проведения вычислений будет достигнута точность 1/10 от начального интервала.

При вторичном вызове, если оставить те же 20делений, снова потребуется 21 вычисление и интервал уменьшитсядо 1/100 от первичного начального интервала. Таким образом, после 42 вычислений получена точность, для достижения которой приобычном методе без вторичного вызова потребовалось бы 201 вычисление. Этот эффект уменьшения числа вычислений будет особенно ощутим при оптимизации сложных функций, каждое вычисление которых занимает длительное время, порядка минут.2.1.2.

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

Давайте предварительно попытаемся определить, каким образом можно уменьшить число вычислений. Что просится реализовать, рассматривая приведенный на рис. 2.2 график функции? Да, действительно, зачем проводить вычисления после достижения Хо? Необходимо составить алгоритм, который обеспечивал бы прекращениевычислений при «ухудшении» функции.

Но эффект от такого усовершенствования не проявится для случая, когда точка оптимумабудет у правой границы начального интервала. Поищем еще путивозможного уменьшения числа вычислений. Чем можно воспользоваться для достижения минимального значения функции? Если быфункция была изготовлена из листового металла, то для поисканижней точки можно было бы использовать шарик – он покатитсяпо наклонной плоскости и достигнет нижней точки.

Воспользуемсяэтим аналогом. Вначале нам необходимо определить направлениеаргумента, обеспечивающего уменьшение функции, а затем организовать движение в этом направлении. Для функции, реализующейсялинией, направление движения определится двумя точками. Сразуже возникает вопрос, где вычислять эти точки. Когда я задаю данный вопрос студентам, то следуют самые разные ответы, например,при минимальном значении переменной и в средине начального ин24тервала, на расстоянии 1/3 от левой и правой границ и другие. Попробуйте сами выдать ответ на поставленный вопрос. Если вы найдете такой ответ, что для определения направления две точки, прикоторых вычисляются значения функции, должны располагаться нанебольшом расстоянии друг от друга, например, 1/1000 от начального интервала, то значит, что Вы повторяете известный метод дихотомии. Определение расстояния между точками все же не даетполного ответа на вопрос, где вычислять эти точки.

Если мы будемвычислять обе точки у левой границы интервала, то никакого эффекта от применения направления не получим – мы и так бы двигались в сторону увеличения переменной. Если Вы выскажете суждение, что вычислять точки нужно у средней точки рассматриваемогоинтервала, то это будет верным ответом. На рис. 2.4 показан этотвариант. Итак, мы определили первые две точки x1 и x2, при которыхвычислим значения функции соответственно y1 и y2. Что делатьдальше? Некоторые студенты высказы- yваются, что нужно проводить вычисления снова у средних точек между xmin иy1x1, а также между xmax и x2. Проанализиy2ровав график функции по рис. 2.1 и вычисления на рис.

2.4, первый вариант исхсрключим – зачем двигаться в сторону заведомого «ухудшения» функции. Исxminx1 x2xmaxключим направление, приводящее к«ухудшению» функции (т. е., проще гоРис. 2. 4. Иллюстрацияметода дихотомииворя, отбросим половину рассматриваемого интервала с ожидаемым «худшим»значением функции). Некоторые из Вас сразу отметят, что исключать половину интервала можно только для унимодальных функций, а для неунимодальных это может привести к нахождению в результате не глобального, а локального оптимума. Отнесем это к недостатку метода.

Оставшийся интервал будем рассматривать какначальный интервал поиска и будем выполнять все те же действия,что и в первом случае.В результате приведенных рассуждений нами получен метод,который называется методом дихотомии (некоторые авторы называют его методом половинного деления).Суть метода дихотомии: искомая длина интервала параметра25проектирования, в котором лежит точка оптимума, уменьшается скаждым шагом почти в два раза.Алгоритм метода состоит из следующих этапов:1) задается интервал возможного изменения проектного параметра при оптимизации [xmin, xmax] и конечный интервал x, придостижении которого прекращаются расчеты;2) интервал изменения параметра делится пополам(см.

рис. 2. 4) xр=(xmin+xmax)/2 и вычисляются значения аргумента,отстоящие на половину точности поиска от средней точки:x1= xср- x/2 ;x2= xср+x/2;3) в найденных точках определяются значения целевой функции y1=f(x1), y2=f(x2),4) уменьшается рассматриваемый интервал изменения переменной путем перемещения ближайшего конца интервала в точку, вкоторой функция имеет "худшее" из полученных значений (на рис.2.4 при поиске минимума неxmin,xmax, Δxаобходимо будет исключить1интервал [xmin, x1]. В программе это может быть обеспеченоxср=(xmin+ xmax)/22равенствомxmin=x1илиx=x.max2х1=хср - Δx/23Процесс расчета, вклю4чающий эти этапы, будетх2=хср+Δx/2продолжаться до тех пор, пока интервал не уменьшится доy1=f(x1)5Х.

Примечание: Х лучшеНет 6Давсего задавать в относительy1>y2ных единицах (в долях начального интервала поиска),xmin=х18x=хmax27тогда при сравнении достижениязаданной точности неДахmax- xmin> Δxa Нет 9обходимо применить абсолютное значениеx1 ,y110xа= (xmax - xmin) . xАлгоритм в виде блокРис. 2. 5. Блок-схема алгоритмасхемыприведен на рис. 2. 5.метода оптимизации дихотомииПри этом методе, по26сравнению с методом прямого перебора, происходит уменьшениечисла вычислений для определения оптимального решения.

Так, если в методе прямого перебора требуется сделать для определенияоптимума 1000 вычислений, то в методе половинного решения длядостижения той же точности - только 20. К недостатку метода относится то, что в результате оптимизации для функции с несколькимиэкстремумами может быть найден не глобальный оптимум, а локальный.Подпрограмма оптимизации методом дихотомии будет иметь вид:Sub Мет_дихотомии(Xmin, Xmax, dx, X1, Y1)Dim Xcr, X2, Y2While (Xmax - Xmin) > 1.2 * dxПрограмма оптимизации методомXcr = (Xmax + Xmin) / 2дихотомииX1 = Xcr - dx / 2X2 = Xcr + dx / 2Y1 = Fx(X1)'Вычисление значения функцииY2 = Fx(X2)'Вычисление значения функцииIf Y1 > Y2 Then Xmin = X1 Else Xmax = X2 'Исключение интервалаWendEnd SubВ операторе цикла While (Xmax - Xmin) > 1.2 * dx введен коэффициент 1.2.

Это сделано для исключения «зацикливания», котороепроисходит без этого коэффициента.2.1.3. Метод золотого сеченияРассмотрим, нельзя ли еще уменьшить требуемое число вычислений по сравнению с методом дихотомии. Для принятия решения по исключению из рассмотрения интервала в методе дихотомииприходится дважды вычислять функцию, т. е. история от предыдущего вычисления никак не используется.

Резерв для уменьшениячисла вычислений может быть здесь. Подумаем, как можно организовать алгоритм, чтобы для принятия решения требовалось толькоодин раз вычислять функцию. Другого подхода, кроме как рассмотренного использования направления изменения функции, скореевсего, не придумать, поэтому снова потребуется две точки для принятия решения по направлению движения. Чтобы алгоритм работалпосле одного вычисления функции, необходимо использовать27результаты прошлого вычисления. Итак, идея высказана, но как еереализовать практически, как задавать точки при делении интервалапоиска? Просится при первом шаге оптимизации начальный интервал поделить на три равныхy1отрезка и в точках x1 и x2 (рис.yy22.

6) вычислить функцию, затем исключить из рассмотреx1xmaxx2xminния интервал с «худшим» знаРис. 2. 6. Один из возможныхчением функции (по рис. 2.6вариантов деления интервалаэто[xmin, x1]). Для оставшегося интервала необходимо вычислить еще одну точку, а значение в точкеx2 можно использовать для принятия нового решения по исключению интервала. Если опять точку x1’ определить из того же соотношения 1/3 от [xmin, xmiax], то при следующих делениях попадем в ситуацию, когда точки начнут совпадать, а затем выходить за границырассматриваемого интервала.

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

Интервал изменения переменной делится точкой на два отрезка такимобразом, чтобы отношение длиныZбольшего отрезка к длине всего инz2z1тервала было равно отношениюдлины меньшего отрезка к длинебольшего отрезка (рис. 2.7)axz1 z 2b, (2.1)Рис. 2.7. Схема к методуZ z1золотого сечениягде z1, z2, Z - соответственно длинаменьшего, большего отрезков и длина всего отрезка.Для расчетов значения z1, z2 необходимо выразить в численной28форме относительно полного интервала Z. Для получения выражения используем также очевидное равенствоz1+z2=Z.(2.2)Из (2.1)z12  Z  z 2 .(2.3)Подставив Z из (2.2) в (2.3) и поделив все слагаемые на z21, получим2 z2 z     2   1  0 z1  z1 Решаем это квадратичное уравнение:(2.4)z2  1  5 0,618 .z12(2.5)Таким образом, получен коэффициент для расчета расстояниядо точки, в которой должна быть вычислена функция (подставивполученное значение в (2.1)).

Характеристики

Список файлов книги