Назад в библиотеку

Метод поиска глобального экстремума функций от разнотипных переменных

Лбов Г.С.

Институт математики СО РАН, Россия

630090, г. Новосибирск-90, пр. академика Коптюга, 4

lbov@math.nsc.ru

Введение

Рассматривается функция y=p(x)=p(x₁,...,xj,...x_n), yєD_Y, xєD. Обозначим глобальный экстремум (для определенности - глобальный максимум) функции через y_max= f(x*). Пару <x', ф> будем называть испытанием. Под алгоритмом поиска приближенного значения глобального максимума функции понимается некоторая процедура последовательного планирования N испытаний с целью нахождения максимально возможного значения функции. Число N обычно невелико, поскольку обычно каждое вычисление функции p(x) в точке x' предполагает достаточно большие затраты либо на вычисление функции, либо на проведение эксперимента в том случае, когда математическая модель оптимизируемого объекта не задана. Впервые излагаемая ниже идея адаптивного планирования испытаний была предложена и использована при построении алгоритма приближенного поиска глобального экстремума на единичном гиперкубе (случай бинарных переменных). В дальнейшем с использованием этой идеи были предложены соответствующие алгоритмы для случая номинальных переменных (с неупорядоченным набором значений) [2] и для случая как количественных, так и качественных переменных [3]. Заметим, что до сих пор остаются открытыми вопросы о введении достаточно слабых ограничений на класс функций p(x) и об определении оптимальной стратегии планирования N испытаний. Необходимость введения слабых ограничений на класс функций p(x) связана с тем, что при решении прикладных задач априорные сведения о свойствах функции p(x), как правило, отсутствуют. Ниже будет изложен метод оптимизации для случая разнотипных переменных с использованием класса логических решающих функций. Кроме того, рассматриваются вопросы, связанные с введением слабых ограничений на класс функций p(x) в случае разнотипных переменных.

Постановка задачи

Пусть задана функция y= p(x)= f(x₁,...,x_J-,...,x_n), xgD, D= п Dj, Dj - множество значений переменной Xj. Для простоты изложения полагаем, что Dj дискретное множество, представляющее набор упорядоченных или неупорядоченных lj значений Xj, \D\= п lj =S.

Кроме того, полагаем, что значения функции на элементах множества D различны между собой. Зададим порядок на этих значениях (y^l>... >y'>... > y^s), полученных в точках x^l,...,x\...,x^s. Под классом эквивалентности понимаем множество функций ф(х), для которых в заранее фиксированных точках x^l,...,x\...,x^s соблюдается один и тот же порядок: y*>... >y^S. дальнейшем любые функции ф₁(х), ф₂(х) считаем различными только в том случае, если они принадлежат разным классам эквивалентности. Не теряя общности, любой функции ф(х) припишем одно и то же множество упорядоченных значений D_y= {y¹,...,y^S}. Обозначим множество таких функций через F, 9(x)eF. Очевидно, что |F|=S!. Введем понятие 8-окрестности максимального значения функции f(x).

При фиксированных функции f(х), алгоритме Q и величине 8_l считаем, что задача решена, если xe D_r В противном случае задача считается нерешенной. Заметим, что если не вводить каких-либо ограничений, то любая функция ф(х) с вероятностью 1/5! может быть предоставлена для решения. Будем говорить, что в этом случае задано равномерное распределение ро(ф) на множестве F. Можно доказать, что при распределении ро(ф) любой алгоритм Q по своей эффективности (по вероятности P(xeD_Sl ) совпадает с методом

Монте-Карло, т.е. со случайным выбором N точек в пространстве D с равномерным распределением р₀(ф)= 1/|D|. Из интуитивных соображений следует, что, по-видимому, в прикладных задачах не все функции равновероятны: существует неравномерное распределение р(ф) на множестве функций, т.е. р(ф) фр₀(ф). Вопрос о введении слабых ограничений на класс функций f(х) сводится к разумным соображениям введения неравномерного распределения р(ф). Если задано распределение р(ф), то можно сформулировать понятие оптимального алгоритма планирования N испытаний: под оптимальным алгоритмом понимается алгоритм Q₀, для которого Pq₀(x eD_E)= _maxPQ (х eD_el), где A - множество алго-

Qe A

ритмов планирования N испытаний.

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

Можно сформулировать и другое понятие оптимального алгоритма. Для любого алгоритма QgA потребуем, чтобы PQ(x^leD) >у, у = 1 -8,8» 0. Обозначим через Nq минимальное число испытаний, необходимое для достижения заданного неравенства. Тогда под оптимальным алгоритмом понимается алгоритм Q₀, для которого Nq= _mi_n Nq .

Укажем один из разумных способов введения неравномерного распределения р(ф).

Пусть проведено L испытаний (2 <L<N ): <x¹,y1>,...,<x^L,yL>, где у,=ф(х^г). Рассматривается разбиение п -мерного пространства D на M подмножеств: а= {E¹,...,E^f,...,E^M}.

Для каждого E^t определим множество ^t={i₁,...,i_Lt} номеров тех из L испытаний, для которых х^іе E^t. Пусть выполняются два ограничения: число L_t < 1 и нет совпадающих точек из множества (x'¹,...,x'^if}. Определим для множества E максимальное значение функции Утах = ^maxy' . Для разбиения а упорядочим множества E¹,...,E^M в соответствии с порядком

y'max >ymmax >- >yax. Получим упорядоченный набор множеств (E*¹,..., e\..., E^tM}. Обозначим через p' вероятность Р*єЕ'), где x* - точка, в которой достигается глобальный максимум функции 9(x).

Для введения ограничения на распределение p(9) используется следующая гипотеза: указанная вероятность p' зависит от числа проведенных испытаний L, мощности множества | E' |, занимаемого номера ' множества E' в указанном выше порядке. При фиксированном | E' | чем меньше номер ', тем выше вероятность p'; при фиксированном номере ' чем больше | E' |, тем больше p'. Функцию p' = х (|E' |, ', L) определим ниже. В дальнейшем

будем полагать, что L' > L*, где L* - некоторый параметр.

Введем распределение p(x)=P(x=x*), x є D, следующим образом: если x є E', то p(x)=p '/\E '\. Очевидно, что при p(9)=1/S! вероятность p^f не зависит ни от номера ', ни от числа проведенных испытаний L, а только от | E' |,т.е. p' =| E' |/| D |. Тогдаp(x)=p₀(x) = 1/\ D \ , x є D. Другими словами, при p(p) = 1/S! проведенные испытания не дают информации о местоположении глобального экстремума. Вычислим энтропию H₀ = - 2 po (x)logpo (x) = log S, определяющую максимальную меру неопределенности местоположения точки x*. Задавая неравномерное распределение p(x), тем самым вводим неравномерное распределение р(ф). Отметим, что чем больше отклонение p(x) от равномерного, тем меньше энтропия H. При фиксированном числе проведенных испытаний L, L<N, чем меньше величина p(L)= H(L)/H₀, где H(L)= - 2 p(x)logp(x), тем больше отклонение распределения p(9) от неравномерного (тем "сильнее" гипотеза). Ясно, что при увеличении числа испытаний L величина p(L) должна уменьшаться.

Исходя из указанных выше общих соображений, приведем пример реализации данной идеи.

Алгоритм ADAPT

Алгоритм ADAPT реализует последовательную процедуру планирования N испытаний и в общем случае предназначен для поиска приближенного значения глобального экстремума функции от разнотипных переменных.

Общее число испытаний N разбивается на R групп N=N₁ +... +N+... +N_R.

решающих функций. Функции f^v соответствует разбиение a_v=(E_v¹,..., E_v¹,..., E_v^Mv}. Если функция p(N^v) задана (способ задания функции p(N^v) будет определен ниже), можно определить вероятности ptv, t=1,...,M_v.

Для этого используется вспомогательная функция i_b(z)=(b+1)/(1+bz)², 0<z <1, 0<Ь< ж Выбор этой функции определяется следующими ее свойствами:

1) при Ь=0 получаем i_b(z)=1 ;

2) при Ь > 0 получаем монотонно убывающую функцию по z;

3) чем больше значение параметра Ь, тем больше скорость убывания функции по z; 1

4) J i_b(z) dz =1 при любом b.

Данные свойства функции i_b(z) позволяют формализовать вышеуказанную гипотезу. Отметим, что в качестве функции i_b(z) можно выбрать любую функцию, удовлетворяющую этим свойствам. Зададим функцию i^u= J i_b(z)dz =(b+1)u/(1+bu), 0<u<1.

Определим вероятность p_t^v, соответствующую множеству Ef. По оси z откладываем относительные мощности Ef /|D|. Причем первоначально откладываются относительная мощность наилучшего множества E^f 1, которому соответствует Ут_ах, затем относительная мощность второго по порядку множества Ef², которому соответствует y^tr2_ax , и т.д. Таким образом, отрезок [0,1] на оси z разбивается на M_v отрезков.

Из изложенного ясно, что чем больше мощность множества Ef и меньше номер i, определяющий номер этого множества в порядке {E_v¹,..., E_v¹,..., E_v^Mv}, тем больше вероятность pf (в соответствии с указанной выше гипотезой). Зададим линейную зависимость параметра Ь от числа проведенных испытаний N, т.е. b^v= N b_max/N. Величина b_max определяется из следующих соображений. После проведения всех испытаний (N^R=N) в соответствии с гипотезой можно указать область E(у) такую, что вероятность нахождения точки x* равна p(y) « 1. При этом область E(y) достаточно мала, т.е. y=E(y)\/\ D | « 0, например, р(у)=0,95, у =0,05.

Исследование эффективности алгоритма оптимизации

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

f(x1 ,x2 ) = -x2 Z -2--⁽l - x2 ) Z -2-

i=1 ^(ki1 (^x1 ^{- a}i1) + ^ci1 i=1 ^(ki2 ^(x1 ^- ai2 ) + ^ci2 где 0<x;<10, х₂є{0,1}, а коэффициенты - случайные числа с равномерным распределением на интервалах 0 < a_i1, a_i2 < 10, 1 < k_i1,ka_i2 < 3, 0.1 < c_i1,ca_i2 < 0.3. Таким образом, функция f(xi,x₂) является случайной функцией от разнотипных переменных (X₁ - количественная, X2 - бинарная переменная).

Для каждой из 100 реализаций данной функции с помощью предложенного алгоритма найдено приближенное значение глобального минимума f*_mm путем адаптивного планирования 200 вычислений функций (испытаний).

Средняя погрешность 8 за 100 реализаций функций равна 0,78%. Работа проделана при поддержке гранта РФФИ №98-01-00673.

Литература

1. Лбов Г.С. Выбор эффективной системы зависимых признаков. -Вычислительные системы, 1965, вып.19, с. 21-34

2. Lbov G.S. Training for ехетит determination of function of variables measured in names scale. In: Second Intern. Conf. on artificial intelligence. London, 1972,p.418-423

3. Lbov G.S. Algorithm of searching the global extremum of function of variables measured in different scales. - In: Proc. 9-th Intern. Conf. on optimization techneques, IFIP. 1979, pt.2 New York a.o. 1980, p. 87-95

4. Лбов Г.С., Старцева Н.Г. Логические решающие функции и вопросы статистической устойчивости решений. Изд-во Института математики СО РАН, Новосибирск, 1999, 211 с.