Шестаков В.С. Расчет на ЭВМ нефтегазового оборудования. Учебное пособие для МНГ-2015 (811778), страница 33

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

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

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

С учетом того, что выполняются вычисления по краям начального интервала, потребуется провести 21 вычисление функции, а с учетом того, что оптимальное решение в поисковой оптимизации выводится в виде интервала из двух участков, то после первичного проведения вычислений будет достигнута точность 1/10 от начального интервала. Привторичном вызове, если оставить те же 20 делений, снова потребуется21 вычисление и интервал уменьшится до 1/100 от первичного начального интервала. Таким образом, после 42 вычислений полученаточность, для достижения которой при обычном методе без вторичного вызова потребовалось бы 201 вычисление. Этот эффект уменьшения числа вычислений будет особенно ощутим при оптимизациисложных функций, каждое вычисление которых занимает длительноевремя (несколько минут).188На листе “ПП” Excel были введены следующие исходные данныеи после расчетов получены результаты.А123456789BCПроверка оптимизацииИсходные данныеМинимальное значение переменнойМаксимальное значение переменнойКоличество участков деления начальногоинтервалаОптимальное значениеНачало интервала с оптимальным значениемКонец интервала с оптимальным значениемМинимальное значение функцииD-1010204.8999995.0999999.09E-13Метод одномерной поисковой оптимизации дихотомииВ результате усовершенствования алгоритма метода прямого перебора мы несколько уменьшили недостаток метода оптимизациипрямого перебора, но все же число вычислений остается сравнительнобольшим.Рассмотрим методы, в которых исключен этот недостаток.

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

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

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

Если мы будемвычислять обе точки у левой границы интервала, то никакого эффектаот применения направления не получим – мы и так бы двигались всторону увеличения переменной. Если Вы выскажите суждение, чтовычислять точки нужно у средней точки рассматриваемого интервала,то это будет верным ответом. На рис. 5.6 показан этот вариант. Итак,мы определили первые две точки Х1 иХ2, при которых вычислим значенияуфункции, соответственно Y1 и Y2. Чтоделать дальше? Некоторые студентыy1высказываются, что нужно проводитьy2вычисления снова у средних точек между Xmin и x1, а также между Хmax и x2.хсрПроанализировав график функции порис.

5.4 и вычисления на рис. 5.6, перХminx 1 x2Хmахвый вариант исключим – зачем двигатьРис. 5.6. Иллюстрацияся в сторону заведомого «ухудшения»метода дихотомиифункции. Исключим направление, приводящее к «ухудшению» функции (т. е.,проще говоря, отбросим половину рассматриваемого интервала сожидаемым «худшим» значением функции). Некоторые из Вас сразуотметят, что исключать половину интервала можно только для унимодальных функций, а для неунимодальных это может привести к нахождению в результате не глобального, а локального оптимума.

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

рис. 5.6) xср=(Xmin+Xmax)/2 и вычисляются значения аргумента, отстоящие на половину точности поиска от средней точки:x1= xср- x/2 , x2= xср+x/2;3) в найденных точках определяются значения целевой функцииy1=f(x1), y2=f(x2);4) уменьшается рассматриваемый интервал изменения переменной путем перемещения ближайшего конца интервала в точку, в которой функция имеет "худшее" из полученных значений (на рис. 5.6 припоиске минимума необходимо будет исключить интервал [Хmin,x1]).

Впрограмме это может бытьобеспеченоравенствомXmin,Xmax, Δxа1Хmin=x1 или Хmax=x2.Процесс расчета, вклюxср=(Xmin+ Xmax)/2 2чающий эти этапы, будетпродолжаться до тех пор, пох1=хср - Δx/23ка интервал не уменьшитсядо x. Примечание: x лучше4х2=хср+Δx/2всего задавать в относительных единицах (в долях на5y1=f(x1)чального интервала поиска),тогда при сравнении достиНет 6Дажения заданной точностиy1>y2необходимо применить абсоXmin=х18Xmax=х27лютное значение.xа= ( Xmax - Xmin) x.ДаАлгоритм в виде блокXmax-Xmin>Δxa Нет 9схемы приведен на рис. 5.7.При этом методе, поx1 ,y110сравнению с методом прямого перебора, происходитРис.

5.7. Блок-схема алгоритма методауменьшение числа вычислеоптимизации дихотомии191ний для определения оптимального решения. Так, если в методе прямого перебора требуется сделать для определения оптимума 1000 вычислений, то в методе половинного решения для достижения той жеточности - только 20. К недостатку метода относится то, что в результате оптимизации для функции с несколькими экстремумами можетбыть найден не глобальный оптимум, а локальный.Подпрограмма оптимизации методом дихотомии будет иметь вид:Sub Мет_дихотомии(Xmin, Xmax, dx, X1, Y1)Dim Xcr, X2, Y2While (Xmax - Xmin) > 1.2 * dxXcr = (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. Без этого коэффициента происходит «зацикливание» процесса решения.5.3.2.

Методы многомерной поисковой оптимизацииОсобенности многомерной поисковой оптимизацииПрежде всего выясним, отличается ли процесс поиска «наилучшего» решения при двух и более переменных от поиска при одной переменной. Можно ли применять методы одномерной поисковой оптимизации для двух переменных.Для графической иллюстрации метода рассмотрим оптимизациюдля двух переменных. Изображение для двух переменных должнобыть объемным (переменные откладываются по осям x и y, а функцияпо z), что приводит при некоторых функциях к сложным рисункам.Для упрощения изображений функции можно применить тот же подход, что используется для представления возвышенностей и впадин натопографических картах – линиями равного уровня.

Эти линии получены путем соединения точек одинаковых значений целевой функции. Иллюстрация метода показана на рис. 5.8. При Y1>Y2>…YK –будет изображена впадина, в противном случае – возвышенность. Дляунимодальных функций будет одна впадина (возвышенность), а для192Х2Y1Y2Y3Y4YKYK-1Х2maxХ2minХ1Х1minХ1maxРис. 5.8. Схема к пояснению методовмногомерной поисковой оптимизациинеунимодальных – несколько. Следует помнить, что до проведенияоптимизации нам эти линии неизвестны, иначе мы бы сразу нашлиоптимальное решение указанием нижней точки.Подумаем, каким образом можно построить алгоритм поискаоптимального решения.

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

Причем сувеличением числа переменных объем вычислений, необходимых дляпоиска оптимального решения с заданной точностью, увеличивается встепенной зависимости, показатель функции равен количеству переменных проектирования. Так, если в случае одномерного пространства для достижения точности поиска, равной 0.1 от начального интервала поиска, методом прямого перебора требуется 21 вычисление, топри двух переменных для выполнения полного перебора всех решений с такой же точностью потребуется 2121=441 вычисление.

Притрех переменных это число составит 212121=9261, при четырех 194481, при пяти - 4084101.193Таким образом, с увеличением числа переменных, если не применять специальных методов поиска оптимального решения, существенно увеличивается требуемое число вычислений, необходимых дляполучения решения. При сложных целевых функциях для выполнениябольшого числа вычислений потребуются большие затраты временина поиск оптимума. Поэтому для поиска оптимального решения придвух и более переменных проектирования используют специальныеметоды оптимизации.Классификация методов многомерной поисковой оптимизацииМетоды оптимизации принято делить на группы, в зависимостиот использования производных целевой функции для поиска оптимального решения: нулевого порядка (покоординатного спуска, случайного поиска, поиска по симплексу, деформируемого многогранника и др.), вних производная не используется; первого порядка (градиентный, наискорейшего спуска, сопряженных градиентов и др.), в них используется первая производная; второго порядка (Ньютона и др.), в них используется втораяпроизводная.Метод покоординатного спуска (метод Гаусса-Зейделя)Суть метода в поочередном одномерном поиске "лучшего решения" по направлениям координатных осей.Алгоритм метода состоит из следующих этапов (рис.

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

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