Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 98
Текст из файла (страница 98)
Для обучения алгоритма в процессе поиска часто берут семейство случайных векторов $ = $(ю), зависящих от параметров и =(ю', ..., ю"), и при переходе от й-й итерации к (й+1)-й итерации имеющиеся значения параметров и, заменяют новыми значениями ю,», с учетом результатов предыдущего поиска. Приведем два варианта метода случайного поиска с обуче нием для минимизации функции у(и) на всем пространстве.
О методе случАйнОГО поискА $ ПО а) Алгоритм покоординатного обучения. Пусть имеется семейство случайных векторов $ = 6(1о)=($', ..., $"), каждая координата з' которых принимает два значения: $'=1 с вероятностью р' и $'=-1 с вероятностью 1 — р', где вероятности р' зависят от параметра 1о' следующим образом: О, и~( — 1, л (1+ю~), ~ю~[(1, 1, ю ~ 1, 1 = 1, ..., и. (3) Пусть начальное приближение и, уже выбрано. Тогда для определения следующего приближения и, в формуле (2) при й=О берется какая-либо реализация случайного вектора $,=$(0), соответствующего значению параметров и= и,=(0, О, ..., 0).
Приближение и, определяется по формуле (2) при й = 1 с помощью случайного вектора $, = $(0). Пусть известны приближе- 1 » ния и„и„..., и„и значения параметров иъ 1 =(ю» 1, ..., ю«-1) при некотором й»1. Тогда полагаем 1оь = риъ„1 — бз1яп [(Х(и« „) — г (иь»)) (и'„, — и«»)1, 1 = 1, ...„ и, й = 2, 3, ..., (4) где величина р ~ 0 называется параметром забывания, 6 ~ 0— параметром интенсивности обучения, у+6) О. При определении следующего приближения и,+, в формуле (2) берем какую-либо реализацию случайного вектора з»= $(иъ»), и1» = (иРь ° ..~ юь).
Из (3), (4) видно, что если переход от точки п„, к и,, привел к уменьшению значения функции, то вероятность выбора направления и,, — и,, на следующем шаге увеличивается. И наоборот, если прн переходе от и»-» к и» 1 значение функции увеличилось, то вероятность выбора направления и„, — и,, на последующем шаге уменьшается.
Таким образом, формулы (4) осуществляют обучение алгоритма. Величина 6~0 в (4) регулирует скорость обучения: чем больше 6>0, тем быстрее обучается алгоритм; при 6 =0, как видно, обучения нет. Величина р>0 в формулах (4) регулирует влияние предыдущих значений параметров на обучение алгоритма; при р = 0 алгоритм «забывает» предыдущие значения 1о,-1 Для устранения возможного чрезмерного детерминирования алгоритма и сохранения способности алгоритма к достаточно быстрому обучению на параметры « ! 1 го» накладываются ограничения ~ 1о»[(сь и при нарушении этих ограничений ю»«заменяются ближайшим из чисел с1 и — с, (1=1, ..., и).
Величины р, 6, с1 являются параметрами алгоритма. 444 метОды минимизАции Функций многих пегеменных ~гл, » Вместо формул (4), посредством которых производится обу- чение алгорптма, часто пользуются другими формулами ш,', = ))ш» 1 — б(Х(и»,) — л (и»,)) (и„',— и» 1), 1 = 1, ..., и, й = 2, 3, ... (5) Описанный алгоритм покоординатного обучения имеет тот недостаток, что поиск и обучение происходят лишь по одному из 2" направлений $ = (е', ..., $"), где либо $' = 1, либо $' = — 1.
Отсутствие «промежуточных» направлений делает покоординатное обучение немобнльным в областях с медленно изменяющимися направлениями спуска. От этого недостатка свободен следующий алгоритм. б) Алеоритм непрерывного самообучения, Пусть имеется семейство случайных векторов Е = Е(ш) = + где ш=(ш, ... ц+м $ ..., ш") — параметры обучения, 11 =(11', ..., ц") — случайный вектор, координаты ц*' которого представляют собой независимые случайные величины, распределенные равномерно на отрезке [ — 1, 1].
Поиск начинается с рассмотрения случайных векторов $, = с(0), $, = $(0), реализации которых используются при определении приближений и„и, по формулам (2). Обучение алгоритма при й > 2 производится так же, как в алгоритме по- координатного обучения, с помощью формул (4) или (5). При больших значениях ~ш,~ влияние случайной величины ц уменьшается, и направление $,=$(ш,) становится более детерминированным и близким к направлению шп Во избежание излиш- 1 п1 ней детерминированности метода на параметры и» = (ш», ..., ш») накладываются ограничения ~ш,~ (с=сопзс, и при нарушении "'А этих ограничений ш„заменяется на — с. ! "ъ! ' Приведенные алгоритмы случайного поиска с обучением показывают, что процесс обучения в ходе поиска сопровождается уменыпением фактора случайности и увеличением степени детерминированности алгоритма поиска минимума, направляя поиск преимущественно по направлению убывания функции.
В то же время наличие случайного фактора в выборе направления дает возможность алгоритму «переучитываться», если свойства функции в районе поиска изменились или предыдущее обучение было неточным. Случайный поиск с обучением в некотором смысле занимает промежуточное положение между случайным поиском без обучения и детерминированными методами поиска минимума из предыдущих параграфов. Разумеется, и в методах предыдущих параграфов можно обнаружить в том или ином виде элементы самообучения алгоритма, однако наличие случайного фактора в алгоритме делает метод случайного поиска более гибким. ОБЩИЕ ЗАМЕЧАНИЯ 4гэ э ез! 3. Весьма усложняет решение задачи минимизации функций многих переменных наличие помех, когда на значения функции 7(и) в каждой точке и накладываются случайные ошибки.
В этих случаях можно использовать метод стохастической аппроксимации. Один из вариантов этого метода был описан в 113 применительно к задачам минимизации функций одной переменной. Для функций и переменных эта процедура приводит к построению последовательности (и„) по закону е (иь + е,еЕ) — и (и — е,еЕ) и„+, = и„' — аь 1 = 1, ..., п, 'А й = О, 1,...„ где ее =(О, ..., О, 1, О, ..., О), г(и) — наблюдаемые в экспорнменте значения функции е(и) в точке и, последовательности (а,), (с„) удовлетворяют условиям (1 13.2). Заметим, что задача минимизации функций при наличии случайных ошибок относится к задачам стохастического программирования.
Более подробно о стохастическом программировании, о теоретических и вычислительных аспектах методов случайного поиска, стохастической аппроксимации см., например, в [11, 49, 113, 123, 127, 147, 148, 151, 154, 157, 158, 173, 180, 214, 235, 259, 279, 308, 339]. й 18. Общие замечания Выше были рассмотрены лишь немногие из известных в настоящее время методов минимизации. В гл.
7 мы обсудим еще один метод решения задач минимизации специального вида— метод динамического программирования. Заметим, что по сей день интенсивно продолжается разработка все новых и новых методов решения экстремальных задач, о чем свидетельствует неуклонно растущее количоство публикаций в научной печати по атой тематике. 1. Возникают естественные вопросы: чем руководствоваться при выборе метода для решения той или иной конкретной экстремальной задачи, какой же метод является нанлучшим7 Иногда считают, что тот метод лучше, у которого выше скорость сходи- мости на некотором фиксированном классе задач. Однако при таком способе оценки методов не принимается во вниманпе такое ваясное качество, как трудоемкость каждой отдельно взятой итерации метода. Нередко бывает, что при решении конкретной задачи выгоднее применять метод, который сходится не очень быстро и для получения решения с нужной точностью требует довольно большого числа итераций, но тем не менее из-за того, что каждая итерация метода осуществляется просто, суммарный объем вычислений и, следовательно, общее машинное время для получения решения оказывается меньшим, чем при применении 4я методы минвмиэации Функций мнОГих пеРеменных [Гл, э другого быстросходящегося метода, каждая итерация которого весьма трудоемка.
Таким образом, при характеристике метода минимизации важным является не столько скорость его сходи« мости, сколько общий объем вычислений, общее машинное время, необходимое для получения решения с нужной точностью. При практическом использовании методов значительная часть времени, отведенного на расчеты, часто аатрачивается на вычисление значений минимизируемой функции или ее производных. Поэтому в тех случаях, когда вычисление значений функ. ции намного проще вычисления ее производных, естественно, выгоднее пользоваться теми методами, которые для своей реализации требуют лишь вычисления значений функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
