Материал: 2426

где Lусл – условный глобальный оптимум решения задачи, определяемый как минимальное значение из множества значений целевой функции, полученных при использовании различных методик, но для одних и тех же численных значений исходных данных задачи,

здесь i – номер применяемой методики на основе: 1 – направленного волнового алгоритма; 2 – алгоритма роевого интеллекта; 3 – генетического подхода; 4 – алгоритма декомпозиции линейных и угловых координат; 5 – алгоритма вероятностной дорожной карты.

В работе [34] предложено разделение критериев оценки эффективности алгоритмов на три группы по целевому признаку, т.е. по назначению. Все критерии разделены на три группы: информационные, операционные и точностные [34].

Информационные характеристики определяют размер алгоритмов в пространстве, т.е. в запоминающей среде и каналах передачи информации средств реализации – в запоминающих устройствах ЭВМ и каналах устройств ввода-вывода данных машин. Операционные характеристики определяют реализуемость исследуемых алгоритмов во времени. Точностные характеристики определяют качество реализации алгоритмов на вычислительных средствах, а также выступают как исходные данные для определения требований к параметрам (шаги квантования сетки координат и т. п.) задания исходных данных для расчета [34].

Соответственно пространственная сложность может быть отнесена к информационным критериям, временная сложность – к операционным критериям, полнота и оптимальность – к точностным критериям.

Кроме того, для многих численных, итерационных либо рекуррентных алгоритмов важное значение имеют такие глобальные точ-

ностные критерии, как корректность, устойчивость и сходимость.

Эти критерии имеют качественный характер [57, 74, 190, 220]. Алгоритм считается устойчивым по исходному параметру x, если

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

75

теории автоматического управления и может быть применено к любому вычислительному алгоритму [2, 41, 54].

Алгоритм корректен, т.е. задача для вычислительного алгоритма считается поставленной корректно, если для любых значений исходных данных из некоторого ограниченного множества ее решение существует, единственно и устойчиво по исходным данным [65, 74, 190].

Под сходимостью алгоритма понимают сходимость используемого численного метода (совокупности методов), т.е. достижимость в процессе итерационных вычислений значения результата, близкого к истинному или действительному при неограниченном возрастании числа итераций (в пределе) [65, 74].

Могут использоваться самые разнообразные частные количественные критерии более низкого иерархического уровня по отношению к глобальным критериям устойчивости и сходимости, применяемые для анализа соответствующих численных методов, например,

скорость сходимости, критерий устойчивости по Ляпунову и т.д. [2, 41, 54].

По степени обобщения полнота, оптимальность, пространственная сложность, временная сложность, корректность, устойчи-

вость и сходимость являются глобальными критериями.

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

1.Частные критерии, соответствующие глобальному критерию

временной сложности: время расчетов Tp; общее количество шагов (элементарных операций/битовых операций), выполняемых алгоритмом; количество строк выполняемого кода и др.

2.Частные критерии, соответствующие глобальному критерию пространственной сложности: информационная длина исследуемого алгоритма M e ; количество входных величин используемого алгорит-

ма; количество выходных величин используемого алгоритма; количество используемых в алгоритме констант; количество строк программной реализации алгоритма; объем информации, занимаемой кодом программной реализации на носителе данных и др.

3. Частные критерии, соответствующие глобальному критерию оптимальности: максимальная абсолютная погрешность результирующей величины алгоритма; максимальная относительная погрешность результирующей величины алгоритма; относительная погрешность к условному глобальному оптимуму и др.

76

4.Частные критерии, соответствующие глобальному критерию сходимости: скорость сходимости, интервал сходимости и др.

5.Частные критерии, соответствующие глобальному критерию устойчивости: критерий устойчивости по Ляпунову; критерий устойчивости по Найквисту и др.

При проведении вычислительных экспериментов было установлено, что все предлагаемые в настоящей монографии алгоритмы обладают полнотой, сходимостью и вычислительной устойчивостью, а следовательно, корректностью, поэтому данные глобальные критерии

ичастные критерии на их основе не использовались для сравнительного анализа алгоритмов.

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

иих программных реализаций, т.е. для определенной тестовой схемы (эталона с определенным набором входных данных), либо для ограниченного количества заранее определенных тестовых схем. Однако при экспериментально-детерминированном подходе полученные оценки могут иметь неполный характер и их распространение на общий случай не всегда обосновано.

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

В качестве статистических критериев оценки эффективности могут использоваться математическое ожидание, дисперсия и другие статистические показатели большинства перечисленных выше детерминированных частных критериев оценки. Таким образом, все частные экспериментальные критерии оценки могут быть разделены по признаку наличия/отсутствия элементов вероятностного характера при задании исходных данных на детерминированные и стохастические.

В табл. 3.1 приведены все критерии оценки эффективности алгоритмов с указанием наличия/отсутствия у каждого упомянутых классификационных признаков. Выделено 5 признаков классификации

77