Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

6.4. Методы организации переходов. Требуемые свойства целевой функции

Идеи, лежащие в основе построения стратегий поиска X*, z* при n>2 (этап II), весьма разнообразны. Часто они формируются применительно к конкретным условиям задачи, однако существуют методы, претендующие на универсальность и применимые к решению классов задач.

Метод исключения

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

Пусть на какой-либо поверхности уровня выбрана опорная точка, через которую прошла касательная плоскость (гиперплоскость) , разделившая область эксперимента на две подобласти (рис. 6.5). Если f(X) строго унимодальна, то оказывается возможным отделить подобласть с более высокими (т. е. лучшими) значениями z от подобласти с меньшими z, не представляющей интереса. В результате образуется новая область неопределенности, и применительно к ней вся процедура исключения повторяется. Сделав несколько таких шагов, можно приблизиться к X* и завершить процесс поиска исследованиями по программе этапа III.

Рис. 6.5
Рис. 6.5

Формальным обоснованием метода исключения служит следующая теорема (15):

если максимум строго унимодальной функции z=f(X) достигается в точке Х* = (x*1, x*2 ,..., х*n), то для любой точки XA = (x1A, x,...., xnA) из области, эксперимента справедливо соотношение


Доказательство: предположим противное -


пусть X - точка, лежащая на отрезке, соединяющем ХА с X*; ее координаты заданы равенствами xj = ax*j+(1-a)xja(j=1,...,n; 0<a<1); поскольку положение X заранее не оговорено, его всегда можно выбрать так, что будет справедливо утверждение


или


Величина а положительна, а сумма, умножаемая на а, меньше нуля (по предположению), следовательно, f(X)<f(XA); но этого не должно быть, если f(X) строго унимодальна (возникшее противоречие доказывает теорему). □

Обращая внимание на тот факт, что


есть уравнение гиперплоскости, касательной к поверхности уровня в точке ХА, приходим к заключению: доказанная выше теорема утверждает необходимость появления X* всегда по одну сторону от касательной.

Достоинством рассматриваемого метода является простота; на основании только одного локального исследования окрестности очередной опорной точки (оно нужно для определения положения касательной) отбрасывается целая бесперспективная область. Недостатки метода-ограниченные возможности применения (только для строго унимодальных f(X)) и чувствительность к ошибкам эксперимента (они пока не принимаются во внимание). Ниже дан иллюстративный пример; несмотря на свою простоту он позволяет продемонстрировать

технику применения метода.

Пример: найти значения переменных х1, х2 х3, доставляющие максимум строго унимодальной функции z = е-(0,1x21+0,4x22+0,9x23) при условиях 0≤xj≤3 (j = 1,.., 3), ε = 0,05.

Рис. 6.6
Рис. 6.6

Решение: а) областью эксперимента Э является в данном случае куб (см. рис. 6.6,а). В качестве начальной опорной точки выбирается средняя точка Хс (центр куба) с координатами x1c=1,5, х=1,5, x=1,5. Значение z в этой точке есть zc=e-3,15. Проводится группа пробных экспериментов в точках X1c=(1,55; 1,5; 1,5),


с целью оценки

производных (df/dxj)Xc и составления уравнения касательной.

Результатами этих экспериментов являются соответственно


позволяющие получить


и


отсюда следует уравнение касательной


Для дальнейшего рассмотрения интерес представляют точки, удовлетворяющие условию Δz≥0, которое вместе с исходными условиями 0≤xj≤3 дает возможность указать новую область неопределенности (см. рис. 6.6,6), остающуюся после проведенного первого исключения.

б) использование средней точки в качестве центра области оказалось удачным (отброшена почти половина Э), поэтому, начиная второй шаг, будем опять ориентироваться на среднюю точку как на новый центр группы пробных экспериментов; обозначая его Хц, получаем x = 1,5; x = 1,5; x = 1,2; zц = е-2,42 (полезно заметить, что zц>zс, т. е. "движение" происходит в нужном направлении). Значения z в точках Х = (1,55; 1,5; 1,2), Х = (1,5; 1,55; 1,2) и Х = (1,5; 1,5; 1,25) равны соответственно


как и в предыдущем случае, условия Δz≥0, 0≤xj≤3 позволяют прийти к новой области неопределенности, показанной на рис. 6.6в.

Второе исключение оказалось не таким эффективным, как первое; причина этого - смещение точки Хц к периферии области Э (здесь проявился один из скрытых недостатков выбора средней точки в качестве центра), поэтому на третьем шаге придется внести необходимые коррективы.

в) Пусть центром оставшейся области неопределенности (рис. 6.6,в), имеющей объем V, будет ее центр тяжести Хцт, координаты которого заданы известными формулами




дающими


Точки проведения пробных экспериментов есть Х1цт (1,43; 1,09; 0,73), Х2цт = (1,38; 1,14; 0,73) и Х3цт = (1,38; 1,09; 0,78). Соответствующие результаты:


и


Условий Δz≥ и 0≤xj≤3 указывают область неопределенности, представленную на рис. 6,6,г. Легко видеть, что выбор Хцт в качестве центра оправдал себя; прежде чем сделать следующий шаг, имеет смысл проанализировать то, что уже достигнуто; при переходах из Х0 в Хц и далее в Хцт значения z возрастали, и наиболее существенное увеличение z произошло на переходе Хц→Хцт. Рассмотрим произвольную точку X на продолжении отрезка, соединяющего Хц с Хцт, предполагая, что это будет продолжение строго возрастающей прямолинейной траектории, идущей в X*. Учитывая неравенства xjцт<x(j = 1, 3), исследуем те X*, координаты которых (Xj) связаны с координатами Хц и Хцт соотношениями xjцт = ax+(1-a)xj (j = 1, 3; 0<a<1), поскольку именно таким X будут отвечать величины z, превышающие zцт. Очевидно, прямая, продолжающая отрезок [Хцт, Хц] и содержащая точку X, должна где-то пересечь границу области, показанной на рис. 6.6.г, причем это будет либо граница x1 = 0, либо x2 = 0, либо x3 = 0.

Полагая в равенстве, связывающем координаты Хц, Хцт, X, поочередно равными нулю x1, х2, х3, получаем из него три значения а, меньшее из которых, т. е.


определяет искомую точку пересечения. В нашем случае ã = 0,606, следовательно, точка пересечения есть Хп = (1,17; 0,45; 0). Проведя в точке Хп эксперимент (т. е. вычислив


убеждаемся в том, что действительно существует прямолинейная строго возрастающая траектория, проходящая через Хц, Хцт и Хп, однако вопрос о местонахождении X* останется открытым.

г) Поскольку наибольшей из всех полученных z является zΠ, можно принять точку Хп за новый центр группы пробных экспериментов и провести все необходимые операции, т. е. найти


уравнение касательной плоскости Δz = 16 (x1 - х) + 32 (х2 - x) + 32 (х3 - х) вместе с исходными ограничениями и требованием Δz≥0 укажет новую область неопределенности (см. рис. 6.6,д); ее объем составляет менее 40% объема предыдущей области (рис. 6.6,г), что является следствием анализа обстановки, проведенного перед четвертым шагом (теперь выяснилось, что Хп не есть X*). Обратим внимание на следующее обстоятельство: в процессе переходов от одной опорной точки к другой значения каждой их координаты не увеличивались (xjc ≥ x > xjцт > x, j = 1,3). В этой ситуации имеет смысл проверить точку (0,0,0), которая к тому же является крайней в области эксперимента; вычисляем z (0,0,0) = 1; все предшествующие z были меньше, поэтому можно предположить Х* = (0,6,0), z* = 1 и перейти к заключительному этапу решения задачи.

д) Прежде всего необходимо построить простейшую аппроксимирующую формулу (модель поверхности отклика в окрестности X*); для этого находим значения z в точках


Затем даются оценки производных


выступающие в роли коэффициентов формулы


Составляется система уравнений


решения которой


удовлетворяют неравенствам |Δxj|<ε. Таким образом, формула для ΔzKB может быть признана допустимой, тем более что ΔzKB как функция Δxj (j = 1,3) является отрицательно определенной (в условиях рассматриваемой задачи); вопрос о замене точки Х* = (0,0,0) точкой Х** = (0,025; 0,025; 0,025) в данном случае непринципиален.

Метод наискорейшего спуска

Приступая к изучению этого метода, необходимо иметь в виду, что я представляет собой скалярную функцию векторного аргумента Х = (х1, х2, ....,хn).

Ее модели, используемые на разных этапах поиска X*, z* и основанные на оценках частных производных первого и высших порядков, позволяют предполагать существование вектора градиента ∇f = (df/dx1, df/dx2, ....,df/dxn) в точках Х∈Э.

Чтобы выяснить, какую роль играет градиент в выборе способа переходов от одной опорной точки к другой, обратимся к формуле производной по направлению:


здесь r-единичный вектор с составляющими rj(j= 1,...,n), в направлении которого берется производная функции z = f (X) в точке ХА. Правая часть этого равенства есть скалярное произведение векторов ∇f, r, определяемое и как |∇fА||r| cos Θ или |∇fA|cosΘ, где ∇fA - градиент f(X) в ХА, Θ - угол между ∇fA и r.

Ясно, что наибольшая величина производной достигается при Θ=0, т. е. тогда, когда направление r совпадает с градиентным. Таким образом, шаг в направлении ∇f означает возможность получить максимальное (по модулю) приращение z.

Эта идея лежит в основе любого градиентного метода, в том числе и метода наискорейшего спуска (возникновение названия связано с задачей отыскания min z, см. 4.3). Учитывая, что вектор ∇f всегда перпендикулярен поверхности уровня в точке, где он рассматривается, можно представить процесс переходов в следующем виде: из очередной опорной точки, в которой с помощью пробных экспериментов найдены составляющие ∇f, делается шаг в градиентном направлении; величина шага определяет новую опорную точку, применительно к которой вся процедура повторяется. В результате образуется ломаная траектория "движения" к X* (рис. 6.7), воспроизводящая более или менее приближенно непрерывную "чисто градиентную" траекторию.

Рис. 6.7
Рис. 6.7

Рис. 6.8
Рис. 6.8

Методу наискорейшего спуска посвящено много работ, поэтому здесь достаточно ограничиться изучением вопроса о выборе длины шага при переходах от одной опорной точки (например, ХА) к другой. Рассмотрим уравнение луча, исходящего из ХА в направлении ∇fA : Х = ХА+a∇fА, a>0 или xj-xJA+a(df/dxj)XA (j = 1,...,n). Если подставить последнее равенство в выражение


определяющее линейную часть приращения z, то полученная формула


покажет, что с ростом а (т. е. при "движении" вдоль ∇fA) всегда появляются положительные Δz (пусть на достаточно малом шаге, в пределах допустимости линейной оценки Δz). Очевидно, перемещение вдоль луча имеет смысл до тех пор, пока значения z улучшаются. Отсюда следует рекомендация: продолжив луч от исходной точки ХА до пересечения с границей области эксперимента, необходимо организовать на образовавшемся отрезке поиск точки экстремума функции z = f(X) любым из доступных методов (см. гл. 5). Найденная при этом оптимальная величина а=а̂ укажет точку Хь которая может быть принята в качестве новой опорной точки и т. д. (рис. 6.7). Таким образом, процесс решения задачи сводится к повторениям однотипных простейших операций поиска.

Метод наискорейшего спуска применим в случаях, когда f(X) унимодальна (а не только строго унимодальна), а также при ошибках эксперимента.

Метод Гаусса - Зайделя

В основе метода Гаусса - Зайделя лежит идея так называемого покоординатного поиска. Пусть из n переменных x1, х2, ..., хn выбрана какая-то одна xs(1≤s≤n), значения же остальных фиксированы (тем самым определена прямая, параллельная одной из координатных осей, а именно оси xs). Производится поиск вдоль этой прямой (конечно, на том ее отрезке, который лежит в пределах области Э), в результате чего становится возможным указать точку экстремума X̂s, функции z, еще не претендующую на роль X*. После этого номера

меняется на р (1≤p≤n, p≠s), X̂s назначается опорной точкой, и применительно к хр вся процедура повторяется. Так продолжается до тех пор, пока не будет найдена точка, подозрительная на экстремум (рис. 6.8). Полезно заметить, что одна и та же переменная xs (или xp) может быть исследована более одного раза.

Достоинства излучаемого метода: простота и отсутствие локальных исследований окрестностей опорных точек. Недостаток: ограниченные возможности применения (метод применим тогда, когда зависимость между переменными x1, х2, ..., хn практически отсутствует). В связи с этим имеет смысл упомянуть об одном осложнении, часто возникающем на практике. Предположим,

что первый шаг привел к отысканию Xs; может оказаться, что попытка сделать следующий шаг будет неудачной какая бы переменная ни выбиралась в качестве свободной на втором шаге, значения z улучшить не удается, хотя достоверно известно, что X̂s не есть X*. Множество точек, из которых невозможно продолжить процедуру Гаусса - Зайделя, называется гребнем. Гребень не только частная специфическая особенность той или иной функции f(X); он может возникнуть, например, при повороте координатных осей, его появлению способствует ограниченная разрешающая способность экспериментов, выражающаяся в существовании конечного ε>0, и т. д.

Идея покоординатного поиска, как будет показано ниже, используется частично и в других методах.

Метод конфигураций

Пусть X10 = (x10, x20, ..., хn0)-точка, из которой начинается поиск, a Δxj>s - выбранные заранее величины изменений соответствующих xj (j = 1, ...,). Предлагается последовательность действий, предусматривающая поочередные изменения координат Х10 с целью получения лучших (по смыслу задачи) значений z. Она заключается в следующем (на примере отыскания max z):

а) Выбирается переменная х1 и оценивается (при известном Δх1) значение целевой функции z = z11 в точке Х+11 = (х10+Δx1, x20, ..., хn0). Оно сравнивается со значением z = z10, найденным предварительно в x10; если оказывается z+11 > z10, то совершается переход из Х10 в Х+11, после чего Х+11 обозначается просто как X11; если же z+11>z10, проводится б).

б) Определяется z = z-11 в точке Х-11 = (х10-Δх1, x20,... ...,xn0). Если в результате сравнения z-11 с zl0 оказалось z-11>z10, то совершается переход из Х10 в Х-, обозначаемую как Х11. Если же z-11≤z10, то приходится признать неудачной попытку увеличения z за счет варьирования x1 и перейти к рассмотрению х2. Здесь роль исходной точки будут выполнять либо Х11, либо Х10 в зависимости от результатов операций а), б). В целях унификации обозначений удобно всегда использовать для этой точки обозначение Х11, даже если ею является Х10, т. е.


в) Оценивается значение z = z+12 в точке Х+12, которая определяется либо координатами (x10+Δx1, х20+Δx2, х30, ...,хn0), либо (х10-Δx1, х20+Δх2, х30,..., хn0), либо (x10, x20 + Δх2, х30,..., хn0). Оно сравнивается со значением z в Х11; если z+12>z11, то совершается переход из X11 в X+12 после чего точка Х+21 обозначается как Х12; если же z+12≤z11, проводится операция г).

г) Рассматривается точка Х-12, заданная аналогично Х+11, но со второй координатой х2-Δх2. Величина z-12 сравнивается с z11; если z-12>z11, то совершается переход из точки Х11 в Х-12, обозначаемую как Х12; если же то Х11 сохраняется в качестве исходной для последующих операций, связанных с х3. Таким образом, в результате этих действий будет указана точка


д) Описанная процедура повторяется для х3, х4, ... ..., хn и позволяет получить точки X13, X14, ..., X1n; с получением X1n становится возможным указать первую конфигурацию (совокупность точек Х10 и X1n) и завершить тем самым первый цикл поиска X*, z*.

Чтобы начать второй цикл, необходимо указать новую исходную точку Х20. Ею могла бы быть Х1n, однако для ускорения процесса часто используется следующий прием: точки Х10 и X1n соединяются отрезком, и на его продолжении выбирается Х20, причем расстояние между X1n и Х20 зависит от конкретных условий задачи. После того как Х20 определена, все операции, перечисленные в пп. а)-д), повторяются сначала; в результате отыскивается точка Хоп, образующая вместе с Х20 вторую конфигурацию, затем строится точка Х30, являющаяся исходной для третьего цикла поиска, и т. д.

Ясно, что переход от Xk0 к Xk+1,0 (k - номер цикла) возможен тогда, когда Хk0≠Xkn. Если оказалось Хk0 = Xkn и, следовательно, Хk+1,0 = Хk0, то допустимы два предположения: либо точка Хk0 находится на гребне, либо она представляет собой X*. В этих условиях рекомендуется уменьшить Δxj, j = 1,...,n (конечно, в рамках требований Δxj≥ε), что позволит несколько "сузить" гребень (в случаях, когда остановка произошла из-за него) и продвинуться дальше в решении задачи. Если подобная операция не приводит к успеху, то поиск можно считать законченным, после чего остается провести исследования окрестности точки X* (см. § 6.3).

Достоинством рассмотренного метода является простота локальных исследований поверхности отклика. Недостатки заключаются в некоторой громоздкости схемы переходов и неполноте информации, получаемой в процессе решения задачи (исследуются только направления, параллельные координатным осям). Ниже дан пример применения метода конфигураций.

Пример: найти значения переменных x1 и х2, доставляющие минимум функции z = 5x21-6x1x2+5x22+8x1+24x2+32 при ε = 0,05, Δxj = 0,15 (j = 1,2).

Решение: а) областью эксперимента в данном случае является вся плоскость х1, х2 в качестве исходной точки может быть выбрана Х10 = (0,0); для нее z10 = 32. Первый шаг предполагает оценку z в точке Х+11 = (0,15; 0); проведя соответствующие вычисления, получим z+11 = 33,3 > z10, что должно быть признано неудовлетворительным (здесь задача на отыскание min z).

б) Обращаемся к Х-11 = (-0,15; 0); для нее z-11 = 30,9 <210, поэтому Х>11 = Х-11 и z11 = z-11 = 30,9.

в) Учитывая полученный результат, легко найти X+12 = (0,15; 0,15) и z+12 = 34,5 > z11 (точка Х+12 должна быть отброшена).

г) Величина z, вычисленная в точке Х-12 = (-0,15;-0,15), оказывается допустимой: z-12 = 27,6 < z11, т. е. Х12 = Х-12 и z12=27,6.

Очевидно, точка X12 выступает здесь в роли Х1n (n = 2) и, следовательно, операция г) завершает первый цикл поиска X*, z*.

Рассмотрим отрезок, соединяющий Х10 с Х12, на продолжении которого находится Х20. Координаты точек Х10, Х12, Х20 связаны зависимостями (1+а)-xj(12) = xj(20)+axj(10), где а - показатель отношения, в котором точка X12 делит отрезок [Х10, Х20]. Выбирая, например, а = 2, имеем Х20 = (-0,45; -0,45) и z20 = 20,8.

д) Второй цикл решения начинается с проверки точки Х+21 = (- 0,3; - 0,45), в которой z+21 = 21,1 > z20; затем проверяется Х-21 = (- 0,6; -0,45), где z-21 = 22,8 > z20, поэтому Х21 = Х20 (совершить переход из Х20 не удалось).

е) Обращаемся к Х+22 = (- 0,45; - 0,3) и получаем z+22 = 23,5>z20. Наконец, в точке Х+22 = (-0,45; -0,6) появляется удовлетворительное значение z-22 = 20,4<z20; таким образом, Х22 = X-22 и второй цикл завершен. Построение точки Х30 проводится при том же а = 2, что дает Х30 = (-0,45; -0,9) и z30 = 14,2. Третья и последующие конфигурации определяются так же, как первые две; в результате возникает траектория "движения" к X*, показанная на рис. 6.9 (последний, восьмой цикл реализован при ΔXJ = 0,1); точка (1; -2,95) принимается за X*; исследование ее окрестности подтверждает правильность найденного решения.

Рис. 6.9
Рис. 6.9

Рассмотренные в гл. 5, 6 методы могут найти применение тогда, когда эксперименты позволяют получать точные значения z. Подобное предположение не всегда допустимо. Очень часто приходится считаться с наличием тех или иных возмущений (прежде всего - ошибок эксперимента), нарушающих запланированный ход решения задачи. Анализу вопросов, связанных с учетом этого фактора, посвящена следующая глава.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"