ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 165
Скачиваний: 0
ВВЕДЕНИЕ
ю
характеризует предысторию поиска и определяет влия ние предыдущих шагов поиска на выбор JV-ro шага.
Вектор памяти WJV-I с точки зрения информации, по лученной на (N— 1)-м этапе поиска, корректируется в соответствии с алгоритмом самообучения
W f f = 4 f ( W f f _ b X w _ b |
Х*<1>, . . . , ХдЛ-л-)). |
(0.1.1.4) |
При \У^ = 0 имеет |
место независимый поиск. |
Приме |
ром такого независимого поиска является поиск по методу градиента.
Для исследования и оценки эффективности поисковых процедур, для сопоставления различных алгоритмов по иска и для определения сходимости процесса поиска не обходимо задать ситуацию, в которой эти алгоритмы действуют, т. е. иметь модели.
Приведем некоторые модели функции качества, на ко торых в дальнейшем будут исследованы и сопоставлены алгоритмы поиска.
1. Линейная модель объекта является наиболее прос той из всех возможных. Она характеризуется линейной зависимостью показателя качества объекта от его управ
ляемых |
параметров: |
|
|
п |
|
Q(xu |
...,хп) = Q & + 2 ai(Xi-Xio), |
(0.1.15) |
или, в векторной форме, |
|
|
Q ( A , X ) = Q 0 + [ ( X - X o ) , A ] , |
(0.1.16) |
|
где квадратными скобками выделено скалярное произве дение. Вектор градиента функции качества равен
grad Q(Xo) = ( а ь . . . , а„) = А , |
(0.1.17) |
т. е. он предполагается постоянным в зоне поиска. Это означает, что функция качества является линейной в пре делах, определяемых смещением АХ=Х—Х0 .
Эта модель хорошо отражает локальные свойства объ екта вдали от экстремума или при достаточно малых шагах поиска АХ. Поэтому она применима для локаль
ного анализа работы алгоритмов поиска. |
|
|
|||
2. |
Стохастическая |
модель |
объекта |
характеризуется |
|
тем, |
что в ней вектор |
ситуации объекта |
А = (аи ..., |
ап), |
|
ВВЕДЕНИЕ
11
т. е. градиент функции качества Q(X), меняется от од ного состояния к другому по некоторому вероятностному закону. В общем виде такая модель выражается форму лой
А ^ + 1 = Р ( А № Д Х * ) , |
(0.1.18) |
где F — случайный вектор, плотность распределения ко торого зависит от двух векторных аргументов — вектора ситуации А в предыдущей исходной точке и вектора смещения АХ.
В общем случае плотность распределения вектора си туации А на (iV+l) - M шаге зависит от вектора ситуаций на N предыдущих шагах AN,..., А] и от смещения AXN на N-u шаге, т. е.
р ( А л - + 1 / А * , . . . , А , , AXJV). |
(0.1.19) |
Такая модель объекта может быть использована для мо делирования весьма широкого класса объектов оптими зации. Объект в этом случае задается при помощи функ ции F(AN, AXjy) или плотности распределения (0.1.19).
Далее будем исследовать работу алгоритмов поиска на стохастической модели, ситуации которой принимают значения из конечного множества векторов
А = { А Ь А 2 , . . . , А„}. |
(0.1.20) |
Плотность распределения (0.1.19) в простейшем случае
можно задавать |
в виде однородной цепи Маркова |
||
|
|
6ц <*> |
|
p(AN+l/AN, |
AXW <4 ) ) = |
(0.1.21) |
|
|
|
6 , i ^ |
. . . 6™<*> |
где i — номер |
реализации вектора ДХя на ЛГ-м шаге |
||
|
поиска (t'= 1,..., т); |
|
|
v — число |
направлений, которые может принимать |
||
|
вектор |
градиента. |
|
§ 0.2. А Л Г О Р И Т М Ы С Л У Ч А Й Н О Г О П О И С К А
Алгоритмы случайного поиска характери зуются тем, что выбор пробных шагов Х ^ 1 ' , . . . , Х ^ ( т л \ а также рабочего смещения AXJV производится случайно
ВВЕДЕНИЕ
12
в соответствии с вероятностным распределением (0.1.11) и функцией решения (см. формулу (0.1.13)). Различают алгоритмы случайного поиска без самообучения и с са мообучением.
АЛГОРИТМ ПОИСКА БЕЗ САМООБУЧЕНИЯ
При работе алгоритмов поиска без само обучения не учитывается предыстория процесса поиска, т. е. W = 0 , и не используется выражение (0.1.14).
Среди алгоритмов поиска без самообучения можно условно выделить два класса алгоритмов: 1) алгоритмы
поиска с линейной тактикой и 2) алгоритмы |
поиска с не |
|||||
линейной тактикой. |
|
|
|
|
|
|
Алгоритм |
с линейной |
тактикой [4] |
характеризуется |
|||
тем, что при неудачном шаге |
(AQ'N^0) |
делаются |
проб |
|||
ные шаги |
в соответствии |
с |
распределением |
(0.1.11), а |
||
потом передается управление на выбор |
AXJV в соответст |
|||||
вии с функцией решения |
(0.1.13). При удачном |
шаге |
||||
(AQ'JV<0) |
пробные шаги |
не делаются, а блок пробных |
||||
шагов сразу передает управление на блок функции реше ния, который определяет последующий как равный
предыдущему, т. е. |
|
|
|
|||
AXN=AXN^. |
|
|
|
(0.2.1) |
||
Примером алгоритма поиска с линейной тактикой |
||||||
может |
быть, |
например, |
следующий алгоритм: |
|
||
|
Г AXN-i |
при |
AQN_1=Q(XN^)-Q(XN-2)<0; |
|||
N |
X aS |
|
при AQjv - i^O . |
(0.2.2) |
||
Алгоритм с |
нелинейной |
тактикой. При удачном |
шаге |
|||
делаются пробные шаги в соответствии с |
распределе |
|||||
нием (0.1.11), |
а потом передается управление на выбор |
|||||
А Х № в соответствии с решающим правилом |
(0.1.13). При |
|||||
неудачном шаге пробные шаги не делаются, |
а сразу уп |
|||||
равление передается на блок функции решения. |
|
|||||
Для |
некоторых |
нелинейных алгоритмов |
поиска |
этот |
||
шаг может быть равным предыдущему с противополож ным знаком, т. е.
AXjy— —AXJV_). |
(0.2.3) |
ВВЕДЕНИЕ |
|
13 |
• |
Ниже в основном будут |
рассмотрены алгоритмы по |
иска с одним пробным шагом, совпадающим со смеще
нием AXN. |
алгоритма поиска с |
нелинейной тактикой: |
||||
Пример |
||||||
{ |
" З д х |
" Р " |
^ " - < ° п |
; |
(0.2.4) |
|
1 |
— AXJY-I |
при |
Д ф л ч ^ О , |
|
|
|
где |
|
|
|
|
|
|
A Q ^ _ I = Q ( X J V - i ) - Q ( X J v _ 2 ) ; |
|
|
(0.2.5) |
|||
Х*_, = Х*_* + ДХ№ _,; |
|
|
(0.2.6) |
|||
S — реализация случайного вектора, |
равномерно |
рас |
||||
пределенного |
на |
единичной |
гиперсфере; |
3 = |
||
=(h> • • • . I n ) ;
а— длина смещения АХ№ :
c = | A X w | . |
(0.2.7) |
АЛГОРИТМ ПОИСКА С САМООБУЧЕНИЕМ
Валгоритмах поиска с самообучением
[6—9] вектор Ww изменяется по формуле (0.1.14) в зави симости от сделанного шага A X ^ - j и полученной инфор мации (опыта) AQJV-I- Ниже будут рассмотрены алго ритмы поиска с самообучением с одним пробным шагом, совпадающим с рабочим шагом AXjv-ь В этом случае алгоритм самообучения можно задать, например, при помощи следующей рекуррентной формулы:
W w = W w _ 1 - 6 s i g n A Q J f _ i ( X ) signAXw-,, |
(0.2.8) |
||
где б — параметр, характеризующий |
скорость |
обучения |
|
(6>0); |
A Q J V - I ( X ) определяется формулой (0.2.5); |
||
sign АХ^_!= (sign А х И * - 1 ' , . . . , sign A*n <w-i>) |
(0.2.9) |
||
( A x j ( J V - 1 ) |
— i-я координата вектора |
AXjy-i). |
|
Чтобы |
устранить нежелательное |
детерминирование |
|
поиска, на изменение вектора накладывается |
ограниче |
||
ние |
|
|
|
| W | « f | / t t |
|
(0.2.10) |
|
( 0 < d < l ) . |
|
|
|
