Главная страница Алгоритмы [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
Заметим, что модифицированный метод дает для каждого Параметра одинаковые относительные погрешности, в то время как * Здесь используются обозначения, -принятые в алгоритме 17ва. {Прим. ред.) фиксированный размер шага приводит к одинаковым абсолютныьв погрешностям. В большинстве случаев относительная точность более предпочтительна чем абсолютная. Подтверждение и замечания к алгоритму 178а М. И. Агеев, Ю. И. Марков, Москва, май 1971 Модификации, предложенные в предыдущих двух «Замечаниях», были внесены в алгоритм 178а, и с ними были повторены расчеты для примера, указанного Л. Смитом в последнем из этих двух «Замечаний». Результаты расчетов приведены в табл. 27. ♦ Таблица 27
в табл. 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.0199 |