ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 207
Скачиваний: 1
ПОИСК БЕЗ САМООБУЧЕНИЯ
123•
§1. 11. А В Т О М А Т Н А Я О П Т И М И З А Ц И Я ПРИ Н А Л И Ч И И ОГРАНИЧЕНИЙ
Выше рассматривались процессы оптимиза ции без ограничения на область поиска. Однако в реаль ных случаях на область поиска накладываются различ ного рода ограничения. Чаще всего в виде неравенств:
5 : /гг -(Х)^>0
Учет ограничений может быть сделан двояко. Во-пер вых, методом штрафных функций, т. е. путем образова ния новой функции качества вида
^ v ; |
I Q(X)+</(X) |
при ХфБ, |
где а(Х) — штраф за нарушение ограничений, который строится следующим образом:
<7(Х)=0 |
при |
X e S ; |
4 ( Х ) > 0 |
при |
ХфБ; |
например,
<7(X) = - 8 m i n { 0 , « , ( X ) , . . . , n f e ( X ) } ,
где 5 — достаточно большой коэффициент штрафа.
Минимизируя функцию Q(X) в открытой области, т. е. решая задачу
Q(X) - v m i n ,
получаем X*, который при достаточно большом б совпа дает с решением исходной задачи (0.1.5), т. е.
Х* = Х*.
Такой подход, как это очевидно, не требует коррекции алгоритма, но допускает заход в область XsjfeS.
ГЛАВА I
124
Другой подход к решению оптимизационных задач с ограничениями связан с организацией реакции на заход в недопустимую область. Например, нарушение ограни чений отождествляется с неудачным шагом:
(XgfeS) = ( A Q ^ 0 ) .
В этом случае использование нелинейного алгоритма
(0.2.4), записанного в виде |
|
|||||
= |
| а Е |
|
при |
( A Q J v _ 1 < 0 ) A ( X w _ 1 s S ) ; |
||
N |
I - A X W |
_ , |
при |
( A Q w _ i > 0 ) V ( X f f _ l 4 E S ) I |
||
гарантирует решение |
поставленной задачи |
(здесь знак |
||||
!Д — логическое «И»; V — логическое «ИЛИ»). |
||||||
Линейный алгоритм |
(0.2.2) запишется в виде |
|||||
|
AXJV_ ! |
при (AQ W - i<0 )A (Xw - i«=S) ; |
|
|||
АХЛ ,= |
аЗ |
при ( A Q ^ - i ^ 0 ) A ( X A - i e S ) ; |
(1.11.1) |
|||
|
— AXjv-i |
при |
X J Y - J ^ S . |
|
||
Здесь обратный шаг введен как реакция на нарушение ограничений.
Рассмотрим работу последнего алгоритма для случая, когда множество возможных направлений {АХ} образу ется координатными направлениями (1.5.1), т. е. имеет место стохастический вариант алгоритма Гаусса—Зей- деля (см. § 1.5):
ati |
при |
t ^ n ; |
Д Х < * > = { |
при |
n<is^2n, |
-aei-n |
где ег — t-й орт. Здесь случайный вектор Н имеет дис кретное распределение
Р ( 0 = 2 ^ ( t = l , . . . , 2 n ) .
Ограничимся для простоты случаем п = 2, который рас
смотрел И. Л. Антонов [17]. |
|
Схема рассмотренного им алгоритма |
такова. В началь- |
1 |
л |
ныи момент с равной вероятностью |
выбирается один |
ПОИСК БЕЗ САМООБУЧЕНИЯ
125
из регулируемых параметров Xi или х2 и с вероятностью 1 2 по этому параметру делается шаг в ту или другую сто
рону. Если этот шаг удачен, т. е. если приращение пока зателя качества имеет желаемый знак, то система про должает движение по той же координате и в том же направлении до тех пор, пока указанное приращение не сменит знак. После этого снова производится случайный выбор направления движения. Если первый шаг был не удачен, то процедура выбора направления движения повторяется сразу после этого шага.
Будем считать, что переход системы из точки в точку
происходит мгновенно, но в каждой точке |
плоскости, |
куда система попадает после n-го шага, она |
задержива |
ется на единицу времени (например, на 1 сек). |
|
Определим поведение системы в окрестности точек, яв ляющихся запрещенными, следующим образом. Сис
тема, попав |
в процессе поиска в точку, |
принадлежащую |
||
запрещенной |
области, |
остается |
там |
в течение 1 сек, |
после чего с |
вероятностью 1 возвращается в точку, ис |
|||
ходную для |
последнего |
шага. |
Если |
при «отражении» |
знак приращения показателя качества будет таким, ка кой нужен, система будет продолжать двигаться в том же направлении до момента, пока не сменится знак при ращения, после чего указанным образом производится выбор нового направления движения. Если при «отра жении» приращение показателя качества имеет нежела тельный знак, то выбор нового направления движения производится сразу.
В § 1.5 было показано, что такой процесс поиска по средством его автоматного представления сводится к не которой цепи Маркова, т. е. представляет собой случай ное блуждание по плоской решетке с шагом, равным единице. Легко заметить, что вероятности переходов сис темы из точки в точку будут зависеть только от того, в какой точке система находится в данный момент, т. е. процесс переходов также будет марковским. Точнее го воря, этот процесс будет описываться однородной мар ковской цепью со счетным множеством состояний.
Назовем переход системы из точки в точку между двумя последовательными остановками для выбора на правления движения тактом и рассмотрим процесс по-
ГЛАВА I
126
иска, принимая в качестве аргумента этого процесса число тактов.
Будем |
считать, |
что показатель |
качества |
системы |
|
можно представить в виде |
|
|
|
||
Q ( * i , * a ) = fi (*i)+fa ( *2 ), |
|
|
|
||
где fi(xi) |
и /2(^2) |
— произвольные |
функции, |
имеющие |
|
единственный строгий минимум. |
|
|
|
||
Будем |
считать, |
что минимум |
показателя |
качества |
|
Q(xu х2) |
находится в точке (0, 0). |
точки (1,1), (1, — 1), |
|||
Назовем окрестностью минимума |
|||||
( — 1 , 1), ( — 1, —1) и найдем среднее число |
тактов, не |
||||
обходимое системе, чтобы из некоторой точки |
плоскости |
||||
попасть впервые в одну из точек |
окрестности |
минимума. |
|||
Поскольку нас интересует среднее число тактов, необ ходимое системе для первого попадания в окрестность минимума, мы можем считать точки, принадлежащие этой окрестности, поглощающими, т. е. такими, что веро ятность перехода из этих точек в самих себя равна 1, и, следовательно, можем для определения искомого сред него числа тактов воспользоваться следующей форму лой [47]:
со |
|
N= ^ / V ^ X ^ S ) , |
(1.11.2) |
где X; — исходное состояние системы;
S— множество всех возможных состояний сис темы, кроме состояний, принадлежащих окрестности минимума;
Pq(X{, S) — вероятность того, что, выходя из состоя
ния Хг-, система после |
q тактов |
окажется |
в одном из состояний |
множества S, не за |
|
ходя при этом ни разу в точки, |
принадле |
|
жащие окрестности минимума; |
|
|
Pq(Xit S)=2Jp<i(9)
Для определения этих вероятностей разобьем мно жество на однородные подмножества.
ПОИСК БЕЗ САМООБУЧЕНИЯ
Разбиением на однородные подмножества назовем та кое разбиение множества 5, когда для любых двух со стояний Xj и Xj-eSft и для любого подмножества Si имеет место равенство
и подмножества 5, попарно не пересекаются. По край ней мере одно такое разбиение всегда существует: каж дое возможное состояние является однородным подмно жеством.
Обозначим J^j pij |
для Xi^Sk |
через p(Sk, Si). Ис- |
|||
|
|
xi6=s, |
|
|
|
пользуя то, что подмножества Si,...,Sm |
не пересекаются, |
||||
можем |
записать |
|
|
|
|
|
|
т |
|
|
|
Pq(\itS)= |
^P(XuSh). |
|
|
(1.11.4) |
|
|
|
ft=i |
|
|
|
Вводя |
производящую |
функцию |
A(s) |
последователь |
|
ности |
ад |
|
|
|
|
|
|
со |
|
|
|
A(s)= |
]£aqs4, |
|
|
(1.11.5) |
|
|
|
9=1 |
|
|
|
умножая выражения (1.11.4) на si и суммируя их для всех q от 1 до оо, получим
со
P(s,S)= |
^P(s,Sk), |
(1.11.6) |
|
fe=i |
|
где P(s, S) и P(s, Sk) — соответственно производящие функции последовательностей Pq(Xi, S) и Pq(Xi, Sk).
Предположим, что Ро(Х,-, S) = l , т. е. что Xj=S . Тогда формулу (1.11.2) можно записать так:
т
A / = 1 + P ( l , 5 ) = l + ]?P(l,Sh). |
(1.11.7) |
й = 1 |
|
ГЛАВА I
128 |
|
|
Задача, таким образом, |
свелась к отысканию |
чисел |
Р(\, Sh)• Для сокращения |
записи в дальнейшем |
будем |
писать вместо Р(\, Sk) просто P(Sk).
Теперь найдем вероятность P(Sfe). Согласно определе нию переходной вероятности за q шагов
Используя уравнение Колмогорова—Чепмена, получим
Pq(Xi,Sl)= |
]?pih«i-» |
]?Ры = |
|
|
xje=s, |
xfte=s |
|
|
т |
2 phi> |
(1Л1-9) |
= 2 2 Pikiq~i) |
|||
|
s =i x^s, |
xA<=ss |
|
или, применяя введенные |
обозначения, |
|
|
|
ГЦ |
|
|
Pq(\uSi)= |
2p(St'Sl)p^(^i,Ss). |
(1.11.10) |
|
8=1
Переходя к уравнениям в производящих функциях и по лагая в них s = 1, получим
т т
P(Si)= |
2P(Ss,Sl)P(Ss)+ |
2' |
PiSs.S^PoiSs) |
|
|
|
8=1 |
"\l=l, |
. . . , m ) , (1.11.11) |
|
|
|
||
где |
Po(Ss) |
есть вероятность того, что в начальный мо |
||
мент |
X ; ^ 5 S . |
|
|
|
Решая полученную линейную неоднородную систему
уравнений, найдем P(Si) (1=1,...,т). |
Подставляя по |
||
лученные значения в |
(1.11.7), |
определим среднее число |
|
тактов, необходимое |
системе |
для первого попадания |
|
вокрестность экстремума.
Сточки зрения сравнения детерминированных и слу чайных методов поиска интересно рассмотреть ограни
ченные запрещенные области, закрывающие прямой путь в окрестность экстремума из какой-либо части плос кости.