Шестаков В.С. Оптимизация параметров горных машин. Учебное пособие (811777), страница 9
Текст из файла (страница 9)
После Мвычислений будет достигнута заданная вероятность Ро для каждойиз независимых переменных, т.е. для всего пространства проектирования. Результаты вычислений для нескольких значений Ро и fприведены в табл. 2. 2, где указано, сколько ячеек надо выбратьслучайным образом, чтобы обеспечить заданную вероятность Po призаданной доле f изменения переменных.
Из таблицы видно, что прислучайном выборе 44 ячеек при f = 0,1 вероятность достижения оп42тимального значения составит 99 %. Это очень неплохо, так как длядостижения 100 % вероятности целевую функцию, как отмечалосьвыше, в случае 5 переменных пришлось бы вычислять 4084101 раз.Таблица 2.2Требуемое число вычислений для достижения заданной вероятностиДоля измененияПеременных f0,10,01Вероятность Po0.90.9522292302990.8161610.9944459Иллюстрация метода показана на рис. 2.12.Алгоритм, реализующий данный метод, включает следующиеэтапы:x2max1) задаются интервалы изменениявсехпеременных:[x1min, x1max] .. [xnmin, xnmax], требуемая вероятность достиженияx2 iоптимального решения Ро, количество интервалов k, на которое делится каждая переменнаяпроектирования;x2min2) определяется доля и шагизменения каждой переменнойx1 ix1minx1maxf = 1/k,Рис.
2. 12. Иллюстрация методаслучайного поискаdx1=(x1max-x1min)/k, ... ,dxn=(xnmax-xnmin)/k;3) определяется требуемое число вычислений функции M длядостижения заданной вероятностиM = ln(1-Po) / ln(1-f);4) подпрограммой генератором случайных чисел задаютсяпоочередно случайные числа Si в интервале 0..1;5) вычисляются значения переменных проектированияxi=ximin + Si (ximax - ximin),436) этапы 4, 5 повторяются для всех переменных проектирования;7) после вычисления всех переменных вычисляется целеваяфункцияY = f(x1, x2, ..., xn);8) этапы 4...7 повторяют M раз;9) полученные результаты сравнивают между собой и определяют область переменных проектирования, при которой целеваяфункция имеет "наилучшее" значение.Этот алгоритм в виде блок-схемы приведен на рис.
2.13.N, f, Po,[ximin, ximax]N - число переменных,f – доля изменения переменных,Ро - вероятность,[ximin, ximax]-интервал изменения i-йпеременнойln(1-Po)ln(1-f)Требуемое число вычисленийдля достижения заданной вероятностиНачалоM=Для запоминания «наилучшего решения»yo=1010j=1, MВывод Fo,xoii=1, NЗадание случайногочисла Sxi=ximin+( ximax -ximin)·SiРасчет функцииy=f(xi)Нетy<yoКонецДаyо= yi=1, Nxоi= xiЗапоминаниенаилучшегозначения функции и переменныхРис. 2. 13.
Блок схема алгоритма метода случайного поискаДостоинством метода является то, что после проведения оп44тимизации будет определен глобальный оптимум при любой целевой функции.К недостаткам метода можно отнести значительный рост требуемого числа вычислений для достижения высокой точности и вероятности.Для исключения этого недостатка можно рекомендовать использование метода случайного поиска совместно с другим, болееточным, например с методом покоординатного спуска. Вначалепроводится оптимизация с использованием метода случайного поиска, а затем найденные оптимальные значения переменных оптимизации используются в качестве начальных значений для методапокоординатного спуска.
В методе покоординатного спуска осуществляется поиск более точного решения. В программе для ЭВМ этоможет быть организовано последовательным вызовом соответствующих подпрограмм.ПримерпрограммыдлявычисленияфункцииY=10+(x1-5)2+(x2-3)2 будет иметь вид:Option ExplicitDim X(10), Xmin(10), Xmax(10), dx(10), Xo(10)Dim Yo, A0, A1, A2, P, Fi, Iv, NNSub Оптимизация_сл()ВводIv = 16'Первая строка в табл. промежуточных расчетовОпт_случайного_поиска 2, Fi, Р, Xmin, Xmax, Xo, Yo, NNWorksheets("Сл_поиск").Range("C13") = Xo(1)Worksheets("Сл_поиск").Range("F13") = Xo(2)Worksheets("Сл_поиск").Range("G13") = YoWorksheets("Сл_поиск").Range("G14") = NNEnd SubSub Ввод()With Worksheets("Сл_поиск")A0 = .Range("G4"): A1 = .Range("G5"): A2 = .Range("G6")Fi = .Range("G7"): P = .Range("G8")Xmin(1) = .Range("F10"): Xmin(2) = .Range("G10")Xmax(1) = .Range("F11"): Xmax(2) = .Range("G11")End WithEnd SubFunction Fy(X)45Dim 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 Опт_случайного_поиска(N, Fi, P, Xmin, Xmax, Xo, Yo, NN)' Подпрограмма оптимизации методом случайного поиска' Входные данные:' N - количество переменных проектирования;' P - заданная вероятность получения оптимального решения;' Fi - заданная доля изменения переменных;' Xmin - массив с минимально допустимыми значениями переменных;' Xmax - массив с максимально допустимыми значениями переменных;' Выходные данные:' Хо - массив с оптимальными значениями переменных;' Yо - наилучшее значение функции после оптимизации;' NN - число вычислений целевой функции' Целевая функция должная быть оформлена подпрограммой функцией'Function FY(x), где x - массив со значениями переменных.Dim Ks, K, i, YNN = Int(Log(1 - P) / Log(1 - Fi)) 'Требуемое число вычисл.
функцииYo = 10 ^ 10For K = 1 To NN' Цикл организации NN раз вычислений функцииFor i = 1 To N' Цикл вычисления всех переменных перед' каждым расчетом функцииKs = Rnd()' Функция выдачи случайного числа от 0 до 1X(i) = Xmin(i) + (Xmax(i) - Xmin(i)) * KsNext iY = Fy(X)' Вызов подпрограммы расчета функцииIf Y < Yo Then' Запоминание "лучшего" решенияYo = YFor i = 1 To NXo(i) = X(i)Программа оптимизаNext iции методом случайEnd Ifного поискаNext KEnd Sub46472.2.5.
Метод поиска по симплексуМетод покоординатного спуска начинает плохо работать длятак называемых «овражных» целевых функций, а также функций,вытянутых под углом к направлениям изменения переменных. Дляисключения этого недостатка существует много предложений.Большинство из них основаны на слежении за изменением функции, предлагается двигаться не вдоль переменных, а в направлении,приводящем в большей степени к «улучшению» функции. Одним изтаких оригинальных предложений является рассматриваемый метод.Данный метод некоторыми авторами называется также методоммногогранника и симплекс-методом. Однако следует отметить, чтоданный метод не имеет ничего общего с симплекс-методом линейного программирования. Основой метода является использованиесимплекса для принятия решения по направлению движения. Симплексом называется N-мерная замкнутая геометрическая фигура,ребра которой представляют собой прямые линии, пересекающиесяв (N+1) вершинах.
В двумерном пространстве - это треугольник, втрехмерном - тетраэдр.Схемы поиска с использованием симплексов основаны на слежении за изменением значений целевой функции в их вершинах.Главным в этих схемах является процесс отражения - нахождениевершин нового симплекса, расположенного симметрично относительно плоскости, прохоНовая верх2дящей через одну из стороншинаисходного симплекса. ВыНовыйбор направления поискасимплексвершины нового симплексаопределяетсяположениемСимплекстойвершиныисходногоВершина с «наихудшим»симплекса,вкоторойцелезначением функциивая функция имеет наихудх1шее значение (рис.
2.14).Новая точка называетсяРис. 2.14. Схема к алгоритму поиска"дополнением" наихудшейпо симплексуточки. Если в только чтополученной точке нового симплекса значение целевой функции48оказывается “худшим”, то алгоритм предусматривает возврат в исходную точку - вершину прежнего симплекса. Затем осуществляется отражение вершины симплекса, в которой целевая функция имеет следующее по величине значение за наихудшей вершиной.
Такойалгоритм обеспечивает систематическое смещение центра симплекса в направлении экстремума целевой функции. Этот метод реализован в некоторых известных системах автоматического управлениядля вывода объектов на оптимальный режим функционирования.Алгоритм метода включает следующие этапы:1) устанавливают границы изменения всех переменных:[ximin, ximax];2) принимаются значения начальных шагов изменения переменных Δxi, например, может быть принято 0,1· (ximах - ximin);3) внутри границ изменения переменных задаются начальнойточкой поиск xiн;4) определяются координаты вершин начального симплекса:xij = xiн + Сij · Δxi,где i - номер переменной, i=1,2,...,N;j - номер вершины, j=1, 2, ..., N+1;Cij -коэффициент для расчета переменных проектирования(табл.
2.3);5) вычисляется значение функции в каждой вершине симплексаYj= f(x1j, x2j, ..., xij);6) определяется "наихудшая" вершина, в которой функцияимеет "наихудшее" значение;7) вычисляются координаты новых вершин симплекса, расположенного напротив "наихудшей" вершины:x i .нов 2 N x ij x i .нх ,N j 1где xi.нх - значение i-той переменной в "наихудшей" вершине,Σxij - сумма прежних значений i-й переменной во всех вершинах симплекса, за исключением "наихудшей".8) вычисленные значения переменных сравнивается с допустимыми значениями этих переменных.
Если новая вершина выходит за допустимую область, то этот симплекс отбрасывается, и вычисляется новая вершина при отражении не "наихудшей" вершины,а следующей за ней;499) вычисляется значение функции в новой вершине симплекса;10) пункты 6...9 повторяют до тех пор, пока симплекс не начнет вращаться вокруг одной точки;11) выявленная область, в которой находятся оптимальныезначения переменных, может быть сужена путем уменьшения сторон симплекса (уменьшается Δxi) и повторением расчетов при построении начального симплекса на "лучшей" вершине последнегосимплекса.Своевременность окончания поиска можно определить по выражениюN ( xi X ) 2i 1N ,где xi _ - значение переменных в последнем симплексе,X- среднее значение переменных по последнему симплексуε - заданная погрешность.Таблица 2.3Таблица коэффициентов для расчета переменных оптимизациивершинаx1+1-10,46123вершина12345Для N=2коэффициент СijДля N=3вершинаx2+10,46-1Для N=3коэффициент Сijx1x2x1x2-1+1+1+1+1-1+1+1+1+1-1+1+1+1-1-10,818 0,818 0,818 0,818коэффициент Сijx1x2x3-1-1+1+1+1-1-1+1-1+1-1+11234вершина123456Для N=4коэффициент Сijx1x2-1+1+1-1+1+1+1+1+1+1-0,38 -0,38x3+1+1-1+1+1-0,38x4+1+1+1-1+1-0,38x5+1+1+1+1-1-0,38Примечание по алгоритму.
Если симплекс начинает колебаться,т. е. осуществляется возврат в старую точку предыдущего симплек50са, то отражать надо не "наихудшую" вершину, а следующую за нейпо значению целевой функции. Если по каким-либо причинам нельзя отразить ни одну из вершин последнего симплекса, то надо отражать другую вершину предыдущего симплекса.Рассмотренный алгоритм показывает, что для реализации требуется большое число защит, а это приведет к достаточно сложнойпрограмме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
