ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 204
Скачиваний: 1
ПОИСК БЕЗ САМООБУЧЕНИЯ
115
в том, чтобы найти условное математическое ожидание смещения к цели
т
г=1
где т — число неблагоприятных направлений шага АХ.
В варианте |
случайного поиска |
на |
гиперсфере M[AQ] |
|||||
не зависит от выбора направления gradQ. Но при дис |
||||||||
кретном варианте ситуация резко меняется. Например, |
||||||||
при выборе координат градиента для случая п ^ 2 |
в виде |
|||||||
аг .= 1; a j |
= 0 |
|
|
|
|
(1.10.6) |
||
|
|
( t ^ / = l , 2 , . . . , n ) |
|
|
|
|
|
|
имеем |
2 n |
M значений AQi = \/~)fn, 2п~х |
значений |
AQi = |
||||
= — 1/Уя |
и M[AQ] = l/(2yn) —т*. При выборе |
координат |
||||||
градиента |
в виде |
|
|
|
|
|
||
a ^ a j = - ~ - ah = 0 |
|
|
|
{ 1 Ж 7 ) |
||||
|
|
|
( £ = 1 , 2 , . . . , п ; |
кф1ф\) |
|
|
||
имеем 2"~2 чисел Д@*=2/У2п, 2п~2 |
чисел |
AQi=-2/i2n, |
||||||
2" - 1 чисел AQi = 0 и M[AQ]= |
М{2рл) |
= т * . |
|
|
||||
Докажем ,что при п ^ 2 |
|
|
|
|
|
|||
m*^M[AQ]s^m*. |
|
|
|
(1.10.8) |
||||
Оценка сверху получается следующим образом. Пред |
||||||||
ставим |
M[AQ] |
как среднее |
арифметическое |
2п |
чисел: |
|||
м ^ |
= 4 |
г |
2 ^ = т 2 ~ п |
2 ^ - |
|
(1ло-9) |
||
|
|
A Q i ^ O |
г=1 |
|
|
|
|
|
Последнее равенство справедливо ввиду того, что для каждого AQi>0 в силу симметричности вершины Х£
8*
116 ГЛАВА I
гиперкуба и линейности объекта имеется равное по мо дулю, но обратное по знаку приращение A Q ' i . Используя известное неравенство, имеем
M [ A Q ] = l 2 - « ^ T |
| A Q i |
| S = ^ 2 - « |
/ J^AQ; 2 , (1.10.10) |
|||||
|
|
i = l |
|
|
|
/ |
г=1 |
|
причем |
равенство |
достигается |
только тогда, |
когда все |
||||
| A Q i | , |
кроме одного, равны |
нулю. Легко проверить, что |
||||||
такая |
ситуация |
возможна |
лишь при выборе |
градиента |
||||
Q ( X ) |
в виде (1.10.6). Для нахождения оценки |
снизу не |
||||||
обходимо рассмотрение |
A f [ A Q ] |
как |
среднего |
арифмети |
||||
ческого т положительных чисел AQc |
|
|
||||||
|
|
|
|
|
|
т |
|
|
M [ A Q ] = 4п |
S A |
& = |
т2-п— |
y^Qu |
(1.10.11) |
|||
|
AQt>0 |
|
|
|
г=1 |
|
|
|
для которого известно другое неравенство: |
|
|||||||
|
|
|
in |
|
|
|
|
|
M [ A Q ] > m 2 - |
|
П AQt- |
|
|
(1.10.12) |
|||
|
|
|
|
|
|
|||
Здесь |
равенство |
достигается |
при |
условии, |
что все |
|||
A Q i равны друг другу. |
Несложно |
показать, что равен |
||||||
ство возможно |
лишь при выборе градиента Q ( X ) в виде |
|||||||
(1.10.7). Таким |
образом, |
неравенства (1.10.8) |
доказаны. |
|||||
В работе [3] потери на поиск ka |
определены следующим |
|||||||
образом: |
|
|
|
|
|
|
|
|
|
max |
|
|
|
|
|
/ . |
, л i о \ |
|
|
|
|
|
|
|
|
( 1 Л 0 Л З ) |
*П = М А О Г
где / — число определений функции качества на один рабочий шаг.
При случайном поиске с пересчетом, который был рассмотрен выше, 1=1, а при градиентном методе по иска l = n+l. С учетом (1.10.2) и (1.10.3) для случайного поиска имеем
A Q m a x = J g r a d Q ( X ) J | А Х г | = 1 И к а = щ щ .
ПОИСК БЕЗ САМООБУЧЕНИЯ
117
Теперь сравним потери на поиск при различных мето дах оптимизации. Как показано в работе [3], потери на
поиск |
равны: |
kn=n+l; |
а) |
для метода градиента |
б) для варианта случайного поиска с пересчетом при
шаге, |
равномерно |
распределенном |
по гиперсфере, |
ka= |
; г |
, |
(1.10.14) |
где Г (га) — гамма-функция.
Для варианта случайного поиска на гиперкубе исполь зуем оценки (1.10.8).
На рис. 1.10.1 видно, что максимальные потери слу чайного поиска на гиперкубе меньше потерь при исполь зовании градиентного метода для п > 6 .
Рис. 1.10.1. Потери на поиск:
/ — метод градиента; 2 — непрерывный случайный поиск; зона потерь случайного поиска на гиперкубе заштрихована.
ГЛАВА I
118
Рассмотрим некоторые вероятностные характеристики •случайного поиска на гиперкубе. Отметим тот факт, что Af[AQ] при равномерном распределении направлений градиента совпадает с математическим ожиданием при ращения функции качества случайного поиска на гипер сфере. Это вытекает из того, что случайная величина фг из (1.10.2) будет иметь точно такое же распределение, как и при случайном поиске на гиперсфере. Однако если направление градиента зафиксировано, то распределе ние угла ф; при случайном поиске на гиперкубе дис кретно и зависит от выбора направлений градиента, что непосредственно видно из выражения для cos ф,:
п
c o s Ф<= |
^ , V M I A V |
| |
i = 2j |
a ^ |
(1 . Ю . 15) |
|
| g r a d Q ( X ) | | A X 1 |
3=1 |
|
|
|
|
|
|
|
|
|
|
( i = l , 2 , . . . , 2 » ; |
/ = 1 , 2 , . . . , / г ) . |
|||
Вид закона распределения угла ф зависит от направ ления градиента Q(X). Так, при выборе координат гра диента в виде (1.10.6) имеем:
СОЗф1=-)=-; Р(ф,) = - 1 ;
\п 2
|
|
l |
|
1 |
(1.10.16) |
• с о з ф 2 = |
\п |
Я(ф2 ) = |
— - . |
|
|
|
|
|
2 |
|
|
При |
выборе |
координат градиента |
в виде (1.10.7) |
||
имеем 2п~2 |
чисел созф! = 2/У2п, 2 n _ 1 |
чисел созф 2 = 0 и |
|||
2п-2 Ч И С е л cos ф 3 = — 2/у2/г, т. е. |
|
||||
cosq>i=—1=; |
/ > ( Ф 0 = |
4 " : |
|
||
|
|
\2п |
|
4 |
|
с о з ф 2 |
= 0; |
Р ( ф 2 ) = - 1 - ; |
|
(1.10.17) |
|
, С 0 5 ф з = |
— ; Р ( ф 3 ) = — . |
|
|||
|
|
]/2д |
|
4 |
|
ПОИСК БЕЗ САМООБУЧЕНИЯ
119 |
|
Если выбрать координаты градиента в виде |
|
ai = a 2 = " - = a n = - т г , |
(1.10.18) |
то будет иметь место следующий закон распределения угла <jp:
|
|
(п-т)~т |
|
2т |
Спт |
п |
|
1П |
0 Ч |
coscpm = |
п- |
= 1 |
п |
; ^ ф т )2п= — |
, |
|
(1.Ю.19) |
||
В |
последнем случае число разных по величине |
углов |
|||||||
ф т |
между векторами |
шагов и вектором градиента |
равно |
||||||
п + 1 |
, т. е. увеличивается |
с ростом Ли Попутно |
можно от |
||||||
метить, что при оптимизации n-мерной функции каче ства ситуация, при которой выполняется условие (1.10.6) г
может иметь место 2п раз, ситуация, когда |
выполняется |
|||
|
|
|
п - 1 |
|
условие |
(1.10.7), |
будет |
иметь место 4 |
r — 2n(n— 1) |
раз и ситуация, когда выполняется условие |
(1.10.18), мо |
|||
жет встретиться |
2п раз, |
т. е. при больших п условие |
||
(1.10.18) |
является |
наиболее возможным. |
|
|
Случайный поиск на гиперкубе, при котором на каж дом шаге производится случайный равновероятный выбор одного из множества дискретных направлений по иска, можно считать своего рода аппроксимацией слу чайного поиска на гиперсфере. Качество аппроксимации-
можно оценивать, |
например, по величине среднеквадра- |
||||
тического |
отклонения |
функции распределения |
Р*(ф) слу |
||
чайной величины угла |
ф при случайном поиске на гипер |
||||
кубе от |
функции |
распределения -Р(ф) при |
случайном |
||
поиске на гиперсфере, т. е. |
|
||||
б = У |
2Р |
(Фт) [F* (фт) - F (фт) р . |
(1.10.20) |
||
|
т |
|
|
|
|
Здесь
т
^ * ( ф т ) = / 5 ( 0 ^ ф < ф т ) = ^ Я ( ф А )
к=1
ГЛАВА I
122
матрицей полного факторного эксперимента типа 2™ и обладает свойством ортогональности [45]:
2 |
О при j=f=k; |
|
(1.10.26) |
||
|
||
г=1 |
•—- при \ — k. |
|
|
||
•Следовательно, |
|
|
|
(1.10.27) |
я в силу условия (1.10.3)
D[AQ}= ~ |
- M 2 [ A Q ] . |
(1.10.28) |
Отсюда |
при / г ^ 2 из неравенств |
(1.10.8) следуют |
оценки (1.10.22). |
|
|
Из рис. 1.10.3 видно, что в принятых |
терминах потери |
|
на поиск неравенства (1.10.22) можно интерпретировать так: минимальным потерям соответствует минимальная дисперсия, а максимальным потерям — максимальная дисперсия.
Рис. 1.10.3. График зависимости от п среднеквадратических отклонений ве личины относительного смещения к цели. Кривая / — метод непрерывного
.случайного поиска.