Материал: 2426
Глобальные критерии оценки эффективности алгоритмов
Информационные критерии |
|
Операционные критерии |
|
Точностные критерии |
||||
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
Пространственная сложность |
|
Временная сложность |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
Информационная длина алгоритма
Количество входных величин алгоритма Количество выходных величин алгоритма Количество используемых констант Количество строк программы Объем информации, занимаемой кодом программной реализации на носителе
Асимптотическая пространственная сложность
Время расчетов
МО времени расчетов
ДИ времени расчетов Количество шагов алгоритма
МО количества шагов алгоритма ДИ количества шагов алгоритма
Количество строк выполняемого кода МО количества строк кода ДИ количества строк кода
Асимптотическая временная сложность
Нечисловые (качественные) критерии |
Числовые (количественные) критерии |
||
Полнота |
|
Сходимость |
Скорость сходимости |
Корректность |
Устойчивость |
МО скорости сходимости |
|
ДИ скорости сходимости |
|||
Оптимальность |
|
Интервал сходимости |
|
|
МО интервала сходимости |
||
|
|
|
|
Абсолютная погрешность |
результирующей |
ДИ интервала сходимости |
|
|
|||
величины алгоритма |
|
|
Критерий устойчивости по Ляпунову |
МО абсолютной погрешности |
|||
ДИ абсолютной погрешности |
МО критерия по Ляпунову |
||
Относительная погрешность (к условному |
ДИ критерия по Ляпунову |
||
глобальному оптимуму) |
|
|
Критерий устойчивости по Найквисту |
МО относительной погрешности |
МО критерия по Найквисту |
||
ДИ относительной погрешности |
ДИ критерия по Найквисту |
||
Рис. 3.5. Дерево иерархических связей глобальных и частных критериев по пер- |
|||
вому, третьему и пятому классификационным признакам |
|||
На рис. 3.6 изображено дерево иерархических связей частных критериев по характеру проведения исследований и получения результатов и по признаку наличия/отсутствия элементов вероятностного характера при задании исходных данных. Блоки используемых частных критериев выделены затемнением.
Всего в настоящей монографии использовано 3 самостоятельных частных численных критерия оценки эффективности алгоритмов и методик на их основе: Tр – математическое ожидание значения вре-
мени расчетов, с; M e – информационная длина исследуемого алго-
80
ритма (требуемый объем памяти, занимаемой всеми массивами и переменными алгоритма при его реализации), байт; δLусл – математиче-
ское ожидание значения относительной погрешности к условному глобальному оптимуму, %.
Рис. 3.6. Дерево иерархических связей частных критериев по второму и четвертому классификационным признакам
81
Указанные три частных критерия использовались для сравнительного анализа предложенных методик путем сравнения численных значений критериев при программной реализации соответствующих алгоритмов, т.е. при применении метода эталонных тестов и проведении вычислительных экспериментов.
Математическое ожидание значения времени расчетов Tр определяется по зависимости
|
|
|
1 |
ne |
(Tр ) |
|
|
|
Tр = |
× å |
, |
(3.23) |
|||||
ne |
||||||||
|
|
|
i=1 |
i |
|
|
||
где Tр – время расчетов для отдельного эксперимента, с; ne – число независимых экспериментов.
Требуемый объем памяти, занимаемой всеми массивами и переменными алгоритма при его реализации M e , определяется как сумма
объемов памяти, необходимой для размещения всех массивов и переменных, объявленных в программной реализации алгоритма:
me |
pe |
|
Me =å(mm)j +å(mp)k , |
(3.24) |
|
j=1 |
k=1 |
|
где mm – объем памяти, занимаемый отдельным массивом данных, байт; me – количество массивов данных алгоритма; mp – объем памяти, занимаемый отдельной переменной, байт; pe – количество переменных алгоритма.
Математическое ожидание значения относительной погрешности к условному глобальному оптимуму δLусл определяется по зависимости
δL = 1 |
× å(δL |
) , |
(3.25) |
|||
|
|
|
|
ne |
|
|
|
усл |
|
усл |
i |
|
|
|
ne |
|
||||
|
|
|
i=1 |
|
|
|
где δLусл – относительная погрешность к условному глобальному оптимуму, определенная для отдельного эксперимента, %.
Три используемых частных критерия оценки эффективности алгоритмов и методик приведены в табл. 3.2. Использование данных критериев позволяет провести обоснованный количественный анализ и сравнение эффективности разработанных алгоритмов и методик на их основе.
82
Таблица 3.2. Принятые критерии оценки эффективности алгоритмов
и методик
|
Название критерия |
|
|
|
|
Аналитическое |
|
Параметры |
||||||||||||||||
|
|
|
|
|
|
выражение |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
1. |
Математическое |
ожи- |
|
|
|
|
|
1 |
|
|
ne |
|
Tр – время расчетов для от- |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
дельного эксперимента, с; |
||||||
дание |
значения |
времени |
Tр = |
|
×å(Tр )i |
|||||||||||||||||||
|
ne |
ne – |
число независимых |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
расчетов Tр |
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
i=1 |
экспериментов |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
2. Информационная длина |
|
|
|
|
|
|
|
|
|
|
|
|
mm – объем памяти, зани- |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
маемый отдельным масси- |
||||||||||||
исследуемого |
алгоритма |
|
|
|
|
|
|
|
|
|
|
|
|
вом данных, байт; me – ко- |
||||||||||
Me (требуемый объем па- |
|
|
|
|
|
me |
|
|
|
|
pe |
личество массивов данных |
||||||||||||
мяти, |
занимаемой |
всеми |
Me =å(mm)j +å(mp )k |
алгоритма; mp – объем па- |
||||||||||||||||||||
массивами и |
переменны- |
|
|
|
|
|
j=1 |
|
|
|
|
k=1 |
мяти, занимаемый отдель- |
|||||||||||
ми алгоритма при его реа- |
|
|
|
|
|
|
|
|
|
|
|
|
ной переменной, байт; pe – |
|||||||||||
лизации) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
количество переменных ал- |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
горитма |
||
3. |
Математическое |
ожи- |
|
|
|
|
|
|
|
|
1 |
|
|
ne |
δLусл |
– относительная по- |
||||||||
дание |
значения |
относи- |
|
|
|
|
|
|
|
|
|
|
||||||||||||
δLусл |
= |
|
|
× |
å(δLусл )i |
грешность к условному гло- |
||||||||||||||||||
тельной погрешности к |
|
|
|
|||||||||||||||||||||
ne |
||||||||||||||||||||||||
условному |
глобальному |
|
|
|
|
|
|
|
|
i=1 |
бальному оптимуму для от- |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
дельного эксперимента, % |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
оптимуму δLусл |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Задачу выбора оптимальной методики предлагается свести к задаче оптимизации с векторной целевой функцией из трех компонент
[211, 213, 253]:
|
|
|
|
|
(3.26) |
GTML =[Tр Me δLусл ]. |
|||||
Относительная значимость компонент в общем случае заранее не определена. Компоненты вектора (3.26) являются конкурирующими, поэтому отсутствует единственное решение поставленной задачи. В этом случае может быть определено подмножество неулучшаемых методик Λ, оптимальных по Парето [211, 213, 253].
Пусть имеется некоторое множество методик решения поставленной задачи в критериальном пространстве компонент вектора
(3.26)
Ω={Метi}, i [1; Nмет], |
(3.27) |
где Метi – отдельная методика; Nмет – общее число рассматриваемых методик.
Для каждой из методик множества Ω известны численные значения компонент векторной целевой функции (GTML )i вида (3.26).
83
Предлагается использовать алгоритм интеллектуальной поддержки САПР выбора методики оптимизации траектории, который заключается в следующей последовательности шагов:
1. Задание исходных данных: максимальных предельных значений частных критериев (Tр )max; (Me)max; (δLусл )max, значений шагов дискретизации частных критериев (Tр ); (Me); (δLусл ) и множества
векторов {(GTML )i}, i [1; Nмет].
2. Используются вложенные циклы по j, k, l, определяющие текущие максимальные значения частных критериев ((δLусл )maxтек)j; ((Tр )maxтек)k; ((Me)maxтек)l соответственно:
((δLусл )maxтек)j [ (δLусл ): (δLусл ):(δLусл )max]; |
|
((Tр )maxтек)k [ (Tр ): (Tр ):(Tр )max]; |
|
((Me)maxтек)l [ (Me): (Me):( Me)max]. |
(3.28) |
3. Для каждого сочетания значений ((δLусл )maxтек)j; ((Tр )maxтек)k;
((Me)maxтек)l из множества методик Ω={Метi}, i [1; Nмет] выбирается оптимальная методика Метiопт по минимальному значению Θmin
скалярной функции линейной свертки критериев Θi, определяемой в
виде суммы отношений [166, 253]: |
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(δ |
L |
|
) |
|
|
|
|
|
(Tр ) |
|
|
|
(M |
) |
|
|
|
||||
Θi = |
|
|
|
усл |
i |
|
|
+ |
((T |
|
) |
|
i |
) |
+ |
|
e |
i |
|
. |
(3.29) |
||
((δ |
|
|
) |
|
) |
|
|
((M |
) |
|
) |
||||||||||||
|
|
|
|
|
|
||||||||||||||||||
L |
|
j |
р |
|
|
|
|||||||||||||||||
|
|
усл |
|
maxтек |
|
|
|
maxтек |
k |
|
|
e maxтек |
l |
|
|||||||||
|
iопт=Индекс(min({Θi})); Θmin=Θiопт. |
|
|
(3.30) |
|||||||||||||||||||
Функцией Индекс обозначено выполнение известного алгоритма определения номера минимального элемента одномерного массива
[74].
Методики, для которых не выполняется условие попадания внутрь допустимого интервала, не рассматриваются (Θi=∞). Условие выглядит следующим образом:
((δLусл )i≤((δLусл )maxтек)j ((Tр )i≤((Tр )maxтек)k) |
|
((Me)i≤((Me)maxтек)l, |
(3.31) |
где – знак логического умножения (конъюнкции).
84