Главная страница  Алгоритмы 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [ 45 ] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57]

яе соответствует описанию использования параметра max, данному в пояснительном тексте, но он це противоречит принципу исключения лишних вычислений.

Для получения определенного минимума, уменьшения количества вычислений функции, когда размер шага больше delta, я удаления лишней метки нужно внести следующие изменения.

1. Строки *

п2: if evalmax then

begin corr:=false; go to exit end; нужно (вычеркнуть.

2. Следующий за этими строками заголовок цикла for i:= il step 1 until к do

нужно заменить на заголовок п2: for i:= 1 step 1 until к do

3. После оператора spsi: = ss;

нужно вставить следующие строки:

if evalmax then пЗ: begin corr:= false; go to exit end;

4. Строку **

nSriTd delta tlien

нужно заменить на строку if ddelta then

5. Строку • 1 begin d:=rho X d; ,

нужно заменить на строку begin

if eval>max then go to n3;

d: = rho X d; . .

Замечание к алгоритму 178

Л. Смит (Smith L. В. «САСМ», 1969, № И)

Алгоритм 178 в том виде, как он был модифицирован М. Беллом и М. Пайком (Bell М., Р i к е М. С. «САОМ», 1966, i№ 9), был успешно использован автором данного «Замечания» для решения нескольких разных задач с применением различных языков (таких, например, как расширенный АЛГОЛ для машины В 5500, сокращенный АЛГОЛ для машины IBM 7090 и ФОРТРАН для машины IBM 360). Было найдено полезным внесение одной модификации, включающей выбор шага так, чтобы он стал эффективным для перченных, значительно различающихся по величине.

М. Беллом и М. Пайком было указано, что как только найден минимум, то каждая переменная увеличивается (или уменьшается) на величину d. Если функция такова, что <в районе минимума значения переменных .различаются по величине на несколько порядков, то универсальный шаг приведет к тому, что в процессе поиска некоторые параметры будут, по существу, игнорированы. Например, если функция двух переменных имеет минимум вблизи точки (100.0, 0.1), то для минимизации по первому параметру размер шага

* В данном переводе используются обозначения, принятые в алгоритме 178а. [Прим. ред.)

** Эта модификация была уже внесена в алгоритм 178а. [При-ред.)



jO.O будет полезным, но для минимизации по второму параметру- бесполезным до тех пор, ттока этот шаг не будет уменьшен до величины 0.01. С другой стороны, размер шага 0.01 для второй переменной будет полезным, а для минимизации ло первой переменной он будет требовать слишком много итераций

Модификация процедуры directsearch, решающей задачу -масштабирования, предусматривает использование для каждой переменной соответствующего размера шага. Такая модификация легко осуществляется, поскольку для запоминания размеров шага, спаб-зкенных знаками, уже используется массив. Изменегше выполняется путем удаления оператора с меткой start и замены его следующим -TjTiepaTopoM *. start: for i:= 1 step 1 until к do

begin slli]: = d X abs(psil[i]);

if sl[i]=0.0 then 5щ: = й end;

Это изменение полагает размер шага по каждой переменной равным начальному значению, умноженному на d, или, если начальное значение равно О, равным d. Следовательно, d - это доля первоначального значения каждой переменной, используемая как начальный азмер шага. Соответствующие уменьшения размера шага дела-;я по-прежнему без дополнительных модификаций процедуры. Для иллюстрации полезности вышеуказанной. модификации рас-, [отрим -функцию

f {Xi,X2,Xs) = (a:i-0.01) 2+ (а:2-1.0) + (а:з-ЮО.О) г минимумом в точке (0.01,1.0,100.0). В табл. 26 представлены ре-ультаты использования процедуры directsearch для этой функции, полученные с модификацией размера шага и без нее. Результаты •были вычислены на машине ЮМ 360/75 с использованием арифметики одинарной точности при /-/10=0.1, delta=0.O0l, d=OU для модиф.ицированного выбора шага (когда для рачального размера шага -задавался масштаб 20% от начального значения переменной), а для опубликованного алгоритма d задавалось равным среднему значению нач-альных приближений к переменным. В табл. 26 буква т - это количество вычислений функции f

Таблица 26

Процедура

Конечные значения переменных

дг, 1

Без модифик-ции С модификацией

66.6667 U.2

Для I

153 112

шчальных зн

0.841,0-7 0.597,0-7

ачешй (0.0,

0.00999995 0.00999998

0.0. 200.0)

0.999995 0.999990

100.000 100.000

Вез модификации G модификацией

168.35 0.2

Для на

гальньш ана>

0.934,0-7 0.559,0-6

[ений (0.05,

0.0100263 0.00999988

5.0, 500.0)

0.998958 0.999998

99.9999 99.9992

Заметим, что модифицированный метод дает для каждого Параметра одинаковые относительные погрешности, в то время как

* Здесь используются обозначения, -принятые в алгоритме 17ва. {Прим. ред.)



фиксированный размер шага приводит к одинаковым абсолютныьв погрешностям. В большинстве случаев относительная точность более предпочтительна чем абсолютная.

Подтверждение и замечания к алгоритму 178а М. И. Агеев, Ю. И. Марков, Москва, май 1971

Модификации, предложенные в предыдущих двух «Замечаниях», были внесены в алгоритм 178а, и с ними были повторены расчеты для примера, указанного Л. Смитом в последнем из этих двух «Замечаний». Результаты расчетов приведены в табл. 27. ♦

Таблица 27

Начальные зиаюния

Результаты трансляции

Xl 1 1 Хг

.f" 1 Lin

0.99999999 1.0000000

100.00000 100.00000

0 0.05

200 500

-0.28,0-15 -0.13,„-14

0.99999999,„-2 0.010000000

в табл. 27 буква m - это количество вычислений функции /.

Как видно из табл. 27, результаты трансляции алгоритма 178а на машине М-220 (TA-IM) точнее результатов, полученных Л. Сми-тем на машине IiBM 360/75 (табл. 24).

Кроме того, для проверки окончания работы процедуры, когда количество вычислений функции достигает значения параметра max, были проведены расчеты для (льхг.лз) =(0,0,200) и тй.)С= 114,100,50 при значениях остальных параметров, которые использовались в предыдущих расчетах. Количество вычислений функции было Г14, 108 и 49 соответственно. Аналогичные расчеты для {хиХ2,Хз)== = (0.05,5,500) и тах:=49,45,40 дали количества вычислений функции 49,49 и 43 соответственно. Количество вычислений функции на выходе из .процедуры иногда превышает max потому, что при каждом обращении к процедуре ее параметр eval возрастает сразу на несколько единиц.

Замечание к алгоритму 201

Дж. Чандлер, В. Гаррисон (Chandler J. P., Harrison W. С. «САСМ», 1970, № 6)

В работе Т. Хиббарда [201, с. 206] этот метод запрограммирован так, что скорость выполнения алгоритма существенно увеличена.-В процедуре sliellsort каждый шаг каждого просмотра состоит из последовательных обменов местами пар элементов. Модификация заключается в замене каждой последовательности п таких парных обменов на одно «запоминание», п-1 перемещение и однов вставление.

В табл. 28 даиа информация о времени выполнения процедур sheltsort и shellsort2 (модифицированный -вариант процедуры shel-Isort), записанных на языках АЛГОЛ, ФОРТРАН и COMPASS ,1ля




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [ 45 ] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57]

0.0248