3.4. Случайный поиск с локальной оптимизацией

Надо помнить, что описанные выше градиентные процедуры в условиях многоэкстремальности целевой функции q(͞x) приводят лишь к локальному минимуму, в районе которого была выбрана начальная точка ͞( D) – область протяжения локального минимума.

С целью улучшения результатов поиска можно предложить провести градиентный спуск с новой начальной точки ͞ D ( ͞ ≠͞ ), выбрав в качестве окончательного решения наименьший из двух локальных минимумов и т.д. Предположив теперь, что начальные точки для локальных спусков выбираются в области D в соответствии с некоторым случайным механизмом (например, по равномерному закону распределения), получим так называемый случайный поиск с локальной оптимизацией.

Рассмотрим более подробно процедуру такого поиска. Задается начальная случайная точка ͞ = (x₁⁰x₂⁰ …., x_i⁰, x_m⁰) D. Далее одним из методов локальной оптимизации (например, градиентным спуском) производится поиск локального минимума q₀=q(͞ ). Значения ͞ и q₀ запоминаются. Выбирается новая случайная точка = (x₁¹x₂¹ …., x_i¹, x_m¹) D. Снова производится поиск локального минимума q₁=q(͞ ). Если очередной результат лучше предыдущего в смысле целевой функции (q₁< q₀), то запоминается соответствующие значения ͞ x₁* и q₁. В противном случае (q₀≤ q₁) остаются прежние значения ͞ * и q₀ попытка считается безуспешной. Поиск прекращается после того, как совершится µ безуспешных попыток улучшить результат.

Если количество локальных экстремумов заранее известно, то по заданному значению вероятности нахождения глобального экстремума можно с достаточной точностью оценить целое число µ. Пусть есть β минимумов, из них β-1 принадлежит областям D(ρ=1,2,….,β-1), а один – глобальный – области D. Производится моделирование равномерно распределенной в области D случайной точки µ раз. Обозначим через Р вероятность попадания точки в область притяжения , а через αР (0<α<1) – вероятность попадания точки в область притяжения . Тогда, очевидно, (β-1) Р + αР = 1, а вероятность пропуска глобального экстремума:

(39)

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

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

Функциональная зависимость между критерием останова и относительной погрешностью , имеющей место при нахождении приближенного значения оптимума критерия q, устанавливается экспериментально. Для этого выбирается последовательность значений, , ,…., . С помощью алгоритма случайного поиска с локальной оптимизацией находятся соответствующие приближенные значения , …, оптимума. Табл. 3.1 экспериментальных данных отражает функциональную зависимость между µ и q: q=q(r).

Таблица 3.1

			…		…
			…		…

При минимизации критерия q эта функция является убывающей и при возрастании µ функция q(µ) стремится к q_min. Кроме того, как показывают эксперименты, q = q(µ) можно аппроксимировать вогнутой функцией.

С помощью экстраполяции по экспериментальным данным оценивается q_min. Затем вычисляются относительные погрешности и формируется таблица 3.1 экспериментальных данных.

Эти данные можно представить в виде графика (рис. 3.14), который и используется как номограмма для оценки значения критерия останова по заданной относительной погрешности δ_q.

Рис. 3.14. График зависимости критерия останова µ от относительной погрешности δ_q

Например, при δ_q=0,02 значение µ >7, а при δ_q = 0,3 µ >5 (см. рис. 3.14).

Таблица 3.2

			…		…
			…		…

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

Обычно значение критерия останова выбирается из практических соображений, исходя из наличия конкретной ПК, времени, точности поиска.

Случайные точки получаются на ПК моделированием равномерно распределённой случайной величины в гиперпараллелепипеде, задаваемом условиями задачи НП x_kmin≤ x_i≤ x_imax, i=͞1͞,͞m с последующей проверкой ограничений h_k≤0, k=͞1͞,P. Такие точки ͞х D называются псевдослучайными.

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

(40)

с областью

Функция (40) в указанной области D имеет десять оврагов, изображенных на рис. 3.15 штриховыми линиями и осями координат, на дне которых имеется пять минимумов (точки пересечения штриховой линии и осей координат). Глобальный минимум находится в точке:

2

1

5

3

11

4

8

7

6

10

-1,0

-0,7

0,3

1,0

-0,3

-1,0

0,7

1,0

Рис. 3.15. Результаты поиска в области D

По формуле (39) при р=0,2 и α=1 можно оценить целое число µ из неравенства: откуда µ ≥39.

На рис. 3.15 изображены результаты поиска в области D в виде траекторий. Как видно из рисунка, поиск сошелся к глобальному экстремуму с четвертой итерации. В связи с этим после 11-й итерации поиск прекращен. Результаты поиска следующие: x₁ =0,000953; x₂ =0,006810; q_min=-1,992301.

Далее уменьшена была область D введением дополнительных ограничений вида x₁+1,1 x₂- 0,1 ≤ 0 и - x₁+0,5 x₂-0,5 ≤ 0.

В этом случае в области D находится только десять локальных минимумов. Тогда при Р = 0,2 и α= 0,51 целое число µ оценивается из соотношения: откуда µ ≥15.

Наилучший результат следующий:

x₁=0,347632; x₂ =0,0000019;

q_min = -1,078818 (10-я итерация).

Ясно, что результат довольно хороший.

Иногда в качестве псевдослучайных точек используются точки ЛПτ последовательностей из единичного m-мерного куба, так как считается, что они более равномерно, чем псевдослучайные, в нем распределены. Такой поиск обычно называют ЛПτ поиском. Недостатком изложенного метода оптимизации является его вероятностный характер, что приводит в большинстве случаев к невозможности оценки вероятности нахождения глобального решения.