книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей
..pdfШа г 11. Если L Ф К, то положить К = L и перейти к шагу 12; иначе перейти к шагу 16.
Ша г 12. Провести серию из L бросков.
Ша г 13. Если обнаружены значимые отклонения от гипотети ческого закона распределения, перейти к шагу 14; иначе перейти к шагу 15.
Ш а г |
14. |
Положить М — L и перейти к шагу 10. |
Ш а г |
15. |
Положить N = L и перейти к шагу 10. |
Ш а г |
16. Положить N = L и остановиться. Искомая длина N |
серци броско^ найдена.
Алгоритм 3.2, приведенный для объяснения сути метода дихото мии в данной задаче, является неэкономичным с точки зрения ма шинной реализации. При его работе чрезвычайно часто вычисля ются значения функционала f на различных перестановках. Объем этих вычислений можно резко сократить, воспользовавшись сле дующим рассуждением. Пусть имеем выборку из К значений слу чайной величины, а нужна выборка из L значений. Если L > К, то достаточно получить еще М — L — К реализаций случайной величины и рассматривать их вместе с К уже имеющимися реализа циями. Если L < К, то можно выбрать L из К реализаций случай ной величины для дальнейшего анализа. При этом вследствие того что реализации получены случайным образом, нет необходимости выбирать эти L из К реализаций случайным образом. Достаточно, например, рассмотреть первые L реализаций.
Опишем |
основанный на этом рассуждении алгоритм, который |
|
фактически используется нами для определения длины N серии |
||
бросков. |
|
|
Алгоритм 3.3. |
10, М = 1. |
|
Ш а г 1. |
Положить К = Ю10, N = |
|
Ш а г 2. |
N раз случайным образом |
генерировать перестановки |
р из п символов и вычислить соответствующие значения функцио-. нала f (р). Записать эти значения в массив ft (i = 1 ,2 .......N).
Ш а г 3. Если в полученной выборке из N чисел обнаружены от клонения от гипотетического закона распределения, то перейти к. шагу 4; иначе перейти к шагу 7.
Ш а г 4. Если 2N < Q, то перейти к шагу 5; иначе перейти к ша гу 13.
Ш а г 5. Провести серию из N бросков и рассмотреть результа ты ранее проведенных N бросков вместе с последними. .Положить. М = 2N. Если в серии обнаружены значимые отклонения от гипо тетического закона, то перейти к шагу 6; иначеперейти к шагу 7.
Ша г 6. Положить N = М и перейти к шагу4.
Ша г 7. Положить L = entier [(// + М)/2].
Ша г 8. Если L Ф К, то положить К = L иперейти к шагу 9;. иначе перейти к шагу 12.
Ш а г 9. Выбрать первые L элементов массива |
Если среди вы |
бранных элементов будет найдено отклонение от |
гипотетического, |
закона, перейти к шагу 10; иначе перейти к шагу 11.
ill.
Ш а г |
10. Положить М — L и перейти к шагу 7, |
Ш а г |
11., Положить N — L и перейти к шагу 7. |
Ш а г |
12. Положить N = L и остановиться. Искомая длина |
серии бросков найдена. |
|
Ш а г |
13. Остановиться. Длйна серии не найдена. Использовать |
метод сужающихся окрестностей нецелесообразно.
Далее подробнее остановимся на том, как устанавливается нали чие или отсутствие значимых отклонений от гипотетического закона.
Используем критерий Ха для случая, когда по выборке оцени ваются некоторые параметры. В самом деле, если априори известно, что закон распределения является нормальным (или логнормаль ным), а параметры т и а (или р и s) нужно оценить, то в предель ном распределении необходимо уменьшить на два число степеней свободы.
Прежде всего рассмотрим гипотезу о нормальном характере за кона распределения.
Пусть задано N выборочных значений случайной величины (результатов испытаний). Обычным способом оцениваем математи ческое ожидание и дисперсию для этих значений. Полагаем
1 N m = ~N ,5,
где | г (i — 1, 2, ..., N) — выборочные |
значения |
случайной |
вели |
чины. |
|
1, 2, ..., N), а Р — |
|
Обозначим а наименьшие из значений & (t = |
|||
наибольшее. Разобьем сегмент (а, р] |
на г интервалов: Si, |
S2, ... |
..., Sf. Вероятность попадания на каждый из интервалов S/ вычислим по формулам
р‘~ т Ь j/ exp[ - ( w ) !]‘K' ,= |' 2..... г
где*/ и xj+t — границы интервалах,. Кроме того, вычислим величины
%/ (/ = 1, 2.......г) — число попаданий выборочных значений |
на |
|||
интервалы |
S/. |
|
|
|
Как меру расхождения между распределением выборки и гипо |
||||
тетическим |
распределением |
выбираем величину |
|
|
|
|
|
(Ij —Npi)* |
|
|
X2 = |
2 |
NPi |
|
|
|
м |
|
|
которую легко выразить через наблюденные частоты X, и ожидаемые частоты Np, для всех г групп.
Гипотеза Н в данном случае состоит в том, что закон распреде ления является нормальным. Вследствие теоремы Пирсона можно
112
ввести критерий для проверки этой гипотезы. Если бы все парамет ры нормального закона были известны, то проверка свелась бы к следующему.
Пусть Хр — р-проаентное значение X2 при г — 1 степенях сво боды. Тогда вероятность
Р = Р {X2 > %1)
при больших N будет приблизительно равна р%. Фиксируем такое малое значение р, чтобы можно было считать практически несом ненным, что при одном испытании событие с вероятностью р% не лроизойдет. Предположим далее, что N столь велико, что для прак тических целей вероятность Р можно отождествить с ее предельным значением р%. Если гипотеза Н верна, то в единственной выборке
практически невозможно встретить значение X2, превышающее Хр- Единственное изменение, которое нужно внести в случае нали чия известных параметров, состоит в следующем: число степеней свободы предельного распределения необходимо уменьшить на ко личество единиц, равное числу параметров, оцениваемых повыбор
ке, В данном случае необходимо рассматривать х»> при г — 3 степе нях свободы.
Если в наличной выборке обнаруживается значение X > Хр, то говорят, что выборка имеет значимое отклонение от гипотезы Н, и потому гипотеза должна быть забракована.
Заметим, что достаточно точные для обычных целей результаты проверки гипотез получаются при Npt > 10. Поэтому, если неко торые из Np, < 10, то обычно бывает целесообразно перед приме нением критерия объединить маленькие группы с тем, чтобы каждая из них содержала по крайней мере 10 ожидаемых результатов.
Вприложениях чаще других используются 5- и 1- и 0,1%-ные уровни значимости. Отклонения, превосходящие 5%-ный предел, но не 1%-ный, называют почти значимыми, отклонения между 1%-ным и 0,1%-ным пределами — значимыми, а отклонения, превы шающие 0,1%-ный предел, — высоко значимыми.
Внашей работе всюду используется 1%-ный уровень значи мости.
Объединение интервалов в случае, когда не выполняется условие NPi > 10, осуществляем следующим образом. Если Np1/ < 10, то объединяем интервалы S< и S ^i. Такая процедура верна для всех, интервалов, кроме правого. Его объединяем с предыдущим.
Алгоритм для выбора длины серии реализован в виде программы LENGTH, текст которой приведен ниже.
С |
SUBROUTINE LENGTH |
|
********************************************************************* |
||
с |
||
с |
|
СПРОГРАММА ПРЕДНАЗНАЧЕНА ДЛЯ ВЫЧИСЛЕНИЯ
СДЛИНЫ СЕРИИ БРОСКОВ
8 |
9—961 |
113 |
n n o n n n
ВЫЗЫВАЕМЫЕ ФУНКЦИИ И ПОДПРОГРАММЫ: KI
******************************************г**************************
COMMON /INNE/ N /IENK/ IZ,NSK */IPRI/ IR /IPIN/FR(20),PR(2)
*/IRIN/ IPA /NKSE/ NQ /RANE/ NU
NSK = 0 |
|
|
IR = |
20 |
- |
NSF = |
60 |
|
READ |
105,NSL |
|
NU = |
N |
16 |
K L = |
1 .E + |
|
NS = |
NSF |
|
M = 1 |
NS |
|
NQ = |
|
|
CALL |
KI |
|
IF (IZ.EQ.O)
— |
GOTO 2 |
1 M = 2*NS |
|
IF |
(M.GT.NSL) |
—GOTO 2
NQ = M CALL KI
IF (IZ.EQ.O)
—GOTO 2
NS = M GOTO 1
2 К = (NS + M)/2
IF(K.LT.40)
—GOTO 9
IF (K - KL) 6,4,6
4NS = К IPA = 0
PRINT 104,NS
6 |
RETURN |
|
K L = К |
|
|
|
NQ =* К |
|
|
CALL KI |
|
|
IF (IZ.EQ.O) |
GOTO 3 |
9 |
— |
|
IF(NS — M) |
8,8,7 |
|
3 |
IF (NS — M) 7,7,8 |
7M = К GOTO 2
8N S = К GOTO 2
5IPA = 1 PRINT 103 RETURN
101FORMAT (13/14)
102FORMAT (20F4.2)
103FORMAT (20X, 'ДЛИНА СЕРИИ HE НАЙДЕНА'/ *8X,'ИСПОЛЬЗОВАТЬ МЕТОД HE ЦЕЛЕСООБРАЗНО')
104FORMAT (10X, 'ИСКОМАЯ ДЛИНА СЕРИИ БРОСКОВ РАВНА1,15)
105FORMAT (5Х,'НАЧАЛЬНОЙ ЧИСЛО БРОСКОВ',15/
*5Х, 'ПРЕДЕЛЬНОЕ ЧИСЛО БРОСКОВ',17) END
114
Замечание к программе LENGTH.
Программа |
LENGTH |
использует |
подпрограмму KI, которая |
в свою очередь использует подпрограммы PERMUT, AIM и PROBAB.. |
|||
Подпрограмма |
PERMUT |
приведена |
на с. аа. Подпрограмма AIM. |
определяет значения функционала на перестановке и составляется пользователем. Приведем тексты программ KI и PROBAB.
О О О О О П О О П П П
SUBROUTINE К1
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * « * * * * * * * * * * * * * * * * .<ф *«*****,|!**ф ,!;****,|;ф с
ПРОГРАММА ПРЕДНАЗНАЧЕНА ДЛЯ ОПРЕДЕЛЕНИЯ НАЛИЧИЯ ЗНАЧИМЫХ ОТКЛОНЕНИЙ
ВЫЗЫВАЕМЫЕ ФУНКЦИИ И ПОДПРОГРАММЫ! PERMUT,AIM,PROBAB
************ г********************************************************
COMMON /NEME/ Z /NKSE/ NS /INNE/ N */lENK/ IZ,NSK /IPIN / FR(20),PR(20) */MENE/ IBP(300),IP(300)
*/IPRI/ IRP /LESE/ IS /KISE/ BZ
*/IKFI/ CR(1000) |
|
||
DIMENSION |
JR (20),TAB(17) |
||
DATA TAB |
/06.64,09.21,11.34,13.28,15,09,16.81,18.48,20.01» |
||
*21.67,23.21,24.73,26.22,27.69,29.14,30.58,32.00,33.41) |
|||
SUM = 0. |
|
|
|
IR = IRP |
|
17 |
|
AMAX = |
—1 .E + |
||
AMIN = |
+ 1 .E + |
17 |
DO 2 K = 1,NS
IF (NS.LE.NSK)
—GOTO 1
IF (K.LE.NSK)
—GOTO 1
CALL PERMUT CALL AIM
IS = IS + 1
CR(K) = Z
1Z = CR(K)
IF (Z.GT.AMAX)
— AMAX = Z
IF (Z — AMIN) 16,2,2
16AMIN = Z
IF (AMIN.GE.BZ)
|
DO 17 I K * |
GO TO 2 |
17 |
1,N |
|
IB P (IK )= IP(IK) |
||
2 |
BZ = AMIN |
|
CONTINUE |
|
|
|
IF (NS.GT.NSK) |
|
|
— |
NSK = NS |
|
DO 3 K = |
1,IR |
3JR (K) * 0
DX = AMAX — AMIN T = DX/IR
IRK = I R + 1
8 * |
115 |
ПОПП
DO 4 К = l.IRK
4FR(K) = AMIN + T*(K — 1). FR(1) = FR(1) — l.E — 10 FR(IRK) = FR(IRK) + l.E — 10 DO 6 I = l.NS
ZK = CR(I)
|
DO 5 K = l.IR |
|
|
IF (ZK.GE.FR(K>rAND.ZK.LT.FR(K + 1)) |
|
2 |
— |
GO TO 6 |
CONTINUE |
||
6 |
JR (K )= JR(K) + 1 |
|
|
CALL PROBAB |
|
7 |
К = |
0 |
K = |
K + 1 |
8RE = NS*PR(K) IF (RE.GE.10)
—GOTO 11
IF (K.LT.IR) |
|
|
|||
— |
К - |
|
GOTO 9 |
||
K1 = |
|
1 |
|
JR(K) |
|
JR(Kl) = |
|
JR(K1) + |
|||
PR(K1) - |
|
PR(K1) + |
PR(K) |
||
IR = |
IR — 1 |
|
|
||
IF (IR.LE.3) |
|
|
|||
— |
|
|
GOTO 13 |
||
RE = |
NS*PR(K1) |
|
|
||
K = |
K1 |
|
|
|
|
GOTO 11 |
|
1 |
|
|
|
9 K l = |
K + |
JR(K1) |
|||
JR(K) - |
JR(K) + |
||||
PR(K) - |
PR(K) + |
PR(K1) |
|||
IR = |
IR - |
I |
|
|
IF (IR.LE.3)
—GOTO 13
IF (K.EQ.IR)
—GOTO 8
|
DO 10 I = K U R |
|||
|
II = |
1 + 1 |
|
|
10 |
JR(I) - |
JR(I1) |
||
PR (I) - |
PR (II) |
|||
11 |
GO TO 8 |
RE |
||
В = |
JR(K) - |
|||
|
D = |
B*B |
|
|
|
E - |
D/RE |
E |
|
|
SUM = |
SUM + |
||
|
IF (K.LT.IR) |
|
—GOTO 7
12 IRK = IR - |
3 |
|
IF |
(SUM-LE.TAB(IRK)) |
|
— |
|
GOTO 14 |
13IZ = 1 RETURN
14 I Z = 0 RETURN END
SUBROUTINE PROBAB
****************He**************************************************)**
ПРОГРАММА ПРЕДНАЗНАЧЕНА ДЛЯ ВЫЧИСЛЕНИЯ
119
o n o n n n n o
ВЕРОЯТНОСТИ ПОПАДАНИЯ НА ИНТЕРВАЛЫ
ВЫЗЫВАЕМЫЕ ФУНКЦИИ И ПОДПРОГРАММЫ
FREQ
«я*******************************************************************
COMMON /NKSE/ NS /IPR I/ IR •/IPIN / FR(20), PR(20)/ IKFI/ CR(1000) */SEBO/ ETA /SELE/ KH
E = 0.
D ■*=0.
IF (KH.EQ.l)
—GO TO 3
|
DO 1 |
K = |
1,NS |
|
|
E K = CR(K) |
|||
1 |
D = |
D + |
EK*EK |
|
E = |
E + |
EK |
||
3 |
GO TO 5 |
1,NS |
||
DO 4 K - |
||||
|
EK = |
ALOG (CR(K) — ETA) |
||
4 |
D = |
D + |
EK*EK |
|
E = |
E + |
EK |
||
5 |
E = |
E/NS |
||
|
D = |
SQRT ((D — E*E*NS)/(NS — 1)) |
||
6 |
IF (D - |
|
l.E — 10)6,8,8 |
|
DO 7 1 = |
1,IR |
|||
7 |
PR (I) = |
0. |
||
|
GOTO |
9 |
|
8DO 2 I = 1,IR IF(KH.EQ.l)
—GOTO 10
|
EN = |
(FR(I + 1) — E)/D |
|
EK = |
(FR (I) — E)/D |
10 |
GOTO 2 |
|
EN = |
(ALOG(FR(I + 1) — ETA) — E)/D |
|
2 |
EK = |
(ALOG(FR(I) — ETA) — E)/D |
PR (I) = FREQ (EN) — FREQ (EK) |
9RETURN END§
§ 6. Выбор радиусов шаров
Использование метода сужающихся окрестностей предполага ет постепенное уменьшение радиуса шаров в пространстве переста новок. В предлагаемом исследовании используются три различных правила уменьшения радиуса.
1. Радиус шара делится пополам. Причем отметим, что шары в пространстве перестановок могут иметь только целочисленные ради усы. Поэтому полагаем
vt = entier(v,_i/2), |
i = |
1, % ... |
(3.63) |
2. Радиус шара уменьшается на единицу. Полагаем |
|
||
v, = V/—j — 1, i = |
1, |
2, . . . |
(6.64) |
117
3.Для изменения радиуса шара используется набор чисел Фи
боначчи. Ряд чисел Фибоначчи строится по следующему правилу* Каждый член ряда равен сумме двух предыдущих:
Ф* = Ф*_14“ Ф(—2*
При этом полагаем Фг = О, Ф2 = 1. Выпишем первые члены ряда Фибоначчи:
О, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.
Как наибольший радиус шара v, выбираем наибольший член ряда Фибоначчи, не превосходящий v0. Пусть это будет число Ф*. Все последующие радиусы строятся по следующему правилу:
V* = |
Фб_/_|_1. |
(3.65) |
Исходная величина v0 для |
подсчета |
радиуса окрестностей вы |
бирается с учетом числа п символов в перестановке и способа мет ризации пространства перестановок.
Именно, для транспозиционной, цепной и алфавитной метрик полагаем v0 = п — 1, для инверсной метрики выбираем v0 =
— .n (nz~ (См. главу 2, § 8). В случае лексикографической метрики
следовало бы положить v0 = я!. Однако 'это приводит к неоправдан но большим затратам машинного времени. Поэтому для лексикогра
фической метрики также положим v0 = --п- ~
В заключение отметим, что предлагаемые правила умень шения радиусов не являются в общем случае самыми лучшими в смысле скорости сходимости метода сужающихся окрестностей. Это объясняется тем, что управление величиной радиусов осуществля ется независимо от некоторых объективных стохастических харак теристик, например таких, как математическое ожидание и диспер сия. Поэтому, как нам кажется, скорость сходимости метода можно существенно увеличить, если изменения радиусов окрестностей поставить в зависимость от большего числа стохастических пара метров и при этом отказаться от монотонного сужения окрестностей. Разумеется, такой подход требует дополнительных исследований.
Имеющиеся алгоритмы уменьшения радиусов реализованы в виде программы RADIUS на языке ФОРТРАН. Ниже приведен ее текст.
С |
SUBROUTINE RADIUS |
|
********************************************************************* |
||
С |
||
С |
|
€ПРОГРАММА ФОРМИРУЕТ НАЧАЛЬНЫЙ РАДИУС
СЦ1АРА И ДАЛЬНЕЙШИЕ ЕГО ИЗМЕНЕНИЯ
С
С FIBNCH
•с с *********************************************************************
с
COMMON /RANE/ NR /11/ 1RAD,KR */NESE/ KN /INNE/ N /FINE/ NF,KF(1000)
118
IF (IRAD.EQ.l)
— |
GO TO 6 |
IF (KH.EQ.2.0R.KN.EQ.4) |
|
— |
GOTO I |
NR = |
N — 1 |
GO TO 5 |
|
1 NR = |
(N — l)*N/2 |
5IF (KR.EQ.— 1)
—CALL FIBNCH
RETURN
6IF (KR) 9,8,7
7NR = NR — 1 RETURN
8NR — NR/2
RETURN ,
9NF = NF — 1 NR = KF(NF) RETURN END
Программа RADIUS использует подпрограмму FIBNCH. При едем ее текст.
nnonnn-nn
SUBROUTINE FIBNCH
V
*********************************************************************
ПРОГРАММА ФОРМИРУЕТ РЯД ЧИСЕЛ ФИБОНАЧЧИ МЕНЬШИХ, ЧЕМ NF
*********************************************************************
COMMON /FINE/ NF.KF(IOOO) /RANE/ NR
KF(1) = 0
KF(2) = |
1 |
|
NF = |
2 |
|
1 NF = |
NF + 1 |
|
KF(NF) = |
KF(NF — 1) + KF(NF — 2) |
IF (KF(NF).LT.NR) GO TO 1
RETURN
END
Г Л А В А 4
ПРИКЛАДНЫЕ ЗАДАЧИ
§ 1. Уравновешивание диска с размещенными на его периферии массами
В турбостроении, авиамоторостроении и других отраслях про мышленности, связанных с вращающимися дискретно распределен ными массами, часто возникает задача уравновешивания масс вра щающихся частей. Неуравновешенность масс приводит к возникно вению значительных центробежных сил, оказывающих вредное воздействие на подшипники агрегата. Кроме того, под действием динамических нагрузок могут появляться трещины в сварных соединениях, широко применяемых в практике турбостроения.
Такого рода задачи рассмотрим на примере ротора паровой турбины.,Он представляет собой вал с насаженными на него облопаченными дисками или барабан с насаженными ступенями облопачивания. Естественно ожидать, что наилучшее статическое уравновешивание каждой ступени даст удовлетворительное (как статическое, так и динамическое) уравновешивание ротора в целом. В связи с этим поставим задачу об уравновешивании изолирован ной рабочей ступени турбомашины. Ступень обычно представляет собой диск, который можно считать полностью уравновешенным. На этот диск с равным угловым шагом посажены рабочие лопатки.
Вследствие технологических особенностей процесса изготовле ния лопаток такие их параметры, как масса и статический момент, имеют некоторый разброс вблизи соответствующих средних значе ний. Поэтому при произвольном размещении лопаток на диске может возникнуть значительный суммарный небаланс ступени. Его можно измерить на испытательном стенде и устранить путем установки балансировочных грузов. Такой способ требует значительных вре менных затрат. Если речь идет о гидротурбинах, то балансировка проводится с помощью сверления диска, что приводит к уменьшению его прочности.
В связи со сказанным значительный интерес представляв! попыт ка добиться достаточной уравновешенности диска путем соответст вующего выбора местоположения каждой лопатки на диске. При этом предполагается, что статические моменты отдельных лопаток известны.
120