Метод случайного поиска оптимизация

Метод случайного поиска

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

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

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

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

(случайный вектор Е) преимущественно в направлении удачного предыдущего шага или в направлении, обратном предыдущему неудачному шагу, в случае нелинейной целевой функции, например, путем перестройки вероятностей

целевой функции, близкой к линейной, вероятность шага в удачном направлении увеличивается, и наоборот.

На базе широкого использования различных методов случайного поиска

развилось новое направление в исследовании самых разнообразных процессов — имитационное моделирование, особенно в связи с появлением ЭВМ третьего

поколения. Вообще под имитацией понимается численный метод исследования

системы, процесса, операции с помощью математических моделей, описывающих функционирование исследуемых систем, на ЭВМ для анализа и синтеза

интересующих исследователя функциональных характеристик. Имитационное

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

случаев оно требует больших затрат на программирование, отладку моделей и

проведение доследования, а также усложняется процесс интерпретации полученных результатов.

Использование методов случайного поиска определяется в основном следующими ситуациями:

  • * неприемлемостью или отсутствием соответствующих аналитических и численных методов исследования модели;
  • * возможностью создания модели функционирования системы (процесса),

получением необходимого количества информации о моделируемой системе (процессе);

* наличием современной вычислительной техники и соответствующего программного обеспечения.

5.6.1 Общие соображения

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

ятность унимодальности целевой функции . Кроме того, множество элементов,

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

цией , показатель которой равен размерности пространства. Так, если в случае одномерного пространства для достижения f = 0.1 методом общего поиска требуется вычислить 19 значений целевой функции, то в случае двумерного пространства это число составляет 361, трехмерного — 6859, четырехмерного — 130321, а пятимерного — 2476099! Поскольку при выборе оптимальном проектировании нередко приходится иметь дело с пятью и более переменными, серьезность трудностей, обусловленных многомерностью, становится бесспорной.

5.6.2 Метод покоординатного спуска (подъема)

Наиболее простым прямым методом поиска оптимума считается метод Га-

усса-Зейделя, называемый также методом покоординатного спуска ( подъема ).

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

Пусть значения всех проектных параметров фиксируются, кроме последнего. На рис. 5.11 показана двумерная целевая функция, заданная линиями уровня, где начальная координата

зафиксирована, а вдоль коор-

ищется минимум или макси-

мум (точка M 1 ) одним из методов одно-

мерной оптимизации. Затем, сохраняя новое значение постоянным, ищут оптимум по (точка M 2 ) и т.д. В общем случае, по завершении этой процедуры для всех переменных можно вернуться к

первой и посмотреть, нельзя ли еще более усовершенствовать решение. Выход из этого итерационного процесса осуще-

ствляется по достижению заданной точности.

Особенно эффективен метод, если линии уровня близки по форме к окружностям или эллипсам, оси которых параллельны осям координат ( рис. 5.12 ). Физически это означает, что проектные параметры практически независимы друг от друга. Если же эти оси наклонены к осям координат (как на рис. 5.11 ), то приходится много раз изменять направление поиска, и эффективность алгоритма снижается, так как для нахождения оптимума приходится вычислять гораздо больше значений целевой функции.

Метод покоординатного подъема совершенно неприменим, если линии уровня имеют точки излома ( рис . 5.13 ). Поскольку линии уровня такого типа очень часто встречаются в инженерной

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

Несмотря на перечисленные недостатки, метод покоординатного подъема часто используют на первой стадии решения задачи, применяя затем более сложные методы. К достоинствам метода покоординатного подъема следует

Рисунок 5.12 — Линии уровня целевой функции близки по форме к окружностям или эллипсам, оси которых параллельны осям координат

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

5.6.3 Метод случайного поиска

Рисунок 5.13 — Целевая функция имеет линию излома

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

вычислить, чтобы, пользуясь методом общего поиска, получить f = 0.1, и было показано, что это число растет как степенная функция, показатель степени которой

равен размерности пространства. Оригинальный подход, позволяющий обойти эту

трудность, основан на случайном поиске (метод Монте-Карло).

Сущность метода Монте-Карло заключается в том, что на каждом k-цикле с

помощью специальной программы формируется последовательность псевдослучайных координат проектных параметров с равномерным

законом распределения и вычисляется соответствующее значение целевой функ-

ции . Перебирая точки ( рис. 5.14 ), компьютер отбрасывает те из них, кото-

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

Результат, полученный с помощью метода Монте-Карло характеризуется вероятностью P того, что при данном числе случайных проб K, расположение точки оптимума будет определено с точностью f , где f — объем N -мерного куба, выраженный в долях от общего объема поиска.

В этом случае f есть вероятность попадания для каждой пробы в заданную область, имеющую объем f . Если делается K случайных проб, то вероятность того, что одна из этих проб попадет в заданную область, может быть определена по формуле

Рисунок 5.14 — Метод случайного поиска

– вероятность попадания в

заданную область f для одной пробы;

– вероятность того же для K проб.

Для нахождения числа случайных проб K , необходимых для того, чтобы с заданной вероятностью P расположение точки оптимума определялось с точностью f , можно воспользоваться формулой

В табл. 5.1 указано, сколько надо сделать случайных проб K для соответствующих величин P и f . Из таблицы видно, что при 44 случайных пробах вероятность достижения f = 0.1 составит 99%. Вспомним, что для 100%-ного обеспечения целевую функцию в случае пяти переменных пришлось бы вычислить 2 476 099 раз!

Таблица 5.1 – Необходимое число случайных проб K для обеспечения вероятности P получения заданного точности f

Значения K для различных P

Метод случайного поиска имеет два преимущества. Во-первых, он пригоден

для любой целевой функции независимо от того, является она унимодальной или нет. Во-вторых, вероятность успеха при попытках не зависит от размерности рас-

сматриваемого пространства. Хотя этот метод не позволяет непосредственно

найти оптимальное решение, он создает подходящие предпосылки для примене-

ния в дальнейшем других методов поиска. Поэтому его часто применяют в соче-

тании с одним или несколькими методами других типов.

5.6.4 Градиентные методы

Во многих алгоритмах многомерной оптимизации используется информация

о градиентах. Как известно, градиент ортогонален к гиперповерхности отклика

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

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

Чтобы лучше понять идею градиентных методов, подробнее остановимся на свойствах градиентов. Рассмотрим систему независимых единичных векторов , направленных вдоль осей координат х 1 , х 2 , х 3 , . x N , являющихся в то же время проектными параметрами. Вектор градиента произвольной целевой

функции F ( х 1 , х 2 , х 3 , . x N ) имеет вид

где частные производные вычисляются в рассматриваемой точке. Этот вектор направлен вверх, в направлении подъема; обратный ему вектор указывает направление спуска. Единичный вектор градиента часто представляют в виде

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

Здесь ∆ — небольшое смещение в направлении x i . Эту формулу часто называют «приближением секущей».

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

Пошаговые градиентные методы при отсутствии ограничений сводятся к следующему.

Этап 1. Пусть нам известны начальные значения проектных параметров

.

Этап 2. Определяется направление наискорейшего изменения целевой

функции F ( х 1 , х 2 , х 3 , . x N ), т.е. ее градиента

Выше в этой главе говорилось о громоздкости вычислений в случае многомерного пространства на примере числа значений целевой функции, которые необходимо вычислить, чтобы, пользуясь методом сеток, получить f==0,1, и было показано, что это число растет как степенная функция, показатель степени которой равен размерности пространства. Оригинальный подход, позволяющий обойти эту трудность, предложен Бруксом и основан на случайном поиске. Пусть пространство проектирования представляет собой куб или гиперкуб со стороной, равной единице, и разделено на кубические ячейки путем деления на 10 равных частей каждой стороны куба, соответствующей одному из проектных параметров. При N=2 число ячеек равно 100, при N=3 оно равно 100, в общем случае при N измерений число ячеек равно 10. Вероятность того, что выбранная наугад ячейка войдет в число 10% наиболее перспективных ячеек, равна 0,1, так как при N=1 нас будет интересовать одна ячейка из 10, при N=2 — одна из десяти лучших при общем количестве ячеек 100 и т.д. Вероятность того, что мы пропустим одну из 10% наиболее перспективных ячеек, составит 0,9. Если случайным образом выбрать две ячейки, то вероятность пропуска будет 0,9, т. е 0,81. Вообще вероятность нахождения по крайней мере одной ячейки из наиболее перспективных, доля которых равна f, после N попыток составит Р=1- (1-f) .

В таблице 1 указано, сколько ячеек надо выбрать случайным образом, чтобы обеспечить заданную вероятность при заданной доле наиболее перспективных ячеек. Из нее видно, что при случайной выборке 44 ячеек вероятность достижения f=0,1 составит 99%.

Это очень неплохо, если вспомнить, что для 100% -ного обеспечения целевую функцию в случае пяти переменных пришлось бы вычислить 2 476 099 раз.

Оцените статью
avataria-cheat.ru
Добавить комментарий