Сравнительный анализ методов оптимизации многоуровневых планов многофакторного эксперимента

ВЫВОДЫ

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

СПИСОК ЛИТЕРАТУРЫ

1. Leland, W. E. On the self-similarnature of ethernet traffic /

[W. E. Leland, M. S. Taqqu, W. Willinger, D. V Wilson] // IEEE/ ACM Transactions of Networking. - 1994. - № 2(1). - P. 1-15.

2. Sheluhin, O. I. Similar processes in telecommunications /

O. I. Sheluhin, S. M. Smolskiy, A. V. Osin. - John Wiley & Sons Ltd, England, 2007. - 337 р.

3. Столлингс, В. Современные компьютерные сети 2-е изд. / В. Столлингс - С. Пб. : Питер, 2003. - 784 с.

4. Шелухин, О. И. Мультифракталы. Инфокоммуникацион-ные приложения приложения / О. И. Шелухин . - М. : Горячая Линия -Телеком, 2011. - 578 с.

5. Veitch, D. Multifractality in TCP/IP traffic: the case against / D. Veitch, N. Hohn, P. Abry // Computer Networks-2005. -№ 48(3). - P. 293-313.

6. RiediR. H. Multifractal processes / Riedi R. H., Doukhan P., Oppenheim G., Taqqu M. S. (Eds.) // Long Range Dependence: Theory and Applications: Birkhuser. - 2002. -Р. 625-715.

7. Kantelhardt, J. W. Fractal and Multifractal Time Series. -2008 [Электронный ресурс]. - Режим доступа: http:// arxiv.org/abs/0804.0747. - Загл. с экрана.

8. Федер, Е. Фракталы / Е. Федер. - М. : Мир, 1991. - 254 с.

9. Calvet, L. Large Deviationsand the Distribution of Price Changes / L. Calvet, A. Fisher, B.B. Mandelbrot // Cowles Foundation Discussion Paper. - 1997. -N. 1165. -P. 1-30.

10. Малла, С. Вэйвлеты в обработке сигналов / С. Малла. -М. : Мир, 2005. - 671 c.

11. Muzy, J. F. Multifractal formalism for fractal signals: the structure-function approach versus the wavelet-transform modulus-maxima method / Muzy J. F., Bacry E., Arneodo A. // Phys. Rev. E. - 1993. -V. 47. - P. 875-884.

12. Павлов, А. Н. Мультифрактальный анализ сигналов / А. Н. Павлов, В. С. Анищенко // Известия Саратовского университета. Серия «Физика». - 2007. - Т. 7, Вып. 1. - С. 3-25.

Стаття надійшла до редакції 16.01.2012 Після доробки 14.02.2012.

Кіріченко Л. О., Демерчян К. А., Кайалі Е., Хабачова А. Ю. МОДЕЛЮВАННЯ ТЕЛЕКОМУНІКАЦІЙНОГО ТРАФІКУ З ВИКОРИСТАННЯМ СТОХАСТИЧНИХ МУЛЬТИ-ФРАКТАЛЬНИХ КАСКАДНИХ ПРОЦЕСІВ

В роботі розглядається моделювання реалізацій телекомунікаційного трафіку, що володіє мультифрактальними властивостями, на основі математичної моделі мультиплікативно-го стохастичного каскаду, вагові коефіцієнти якого мають бета-розподіл ймовірностей.

Ключові слова: стохастичний каскадний процес, модель телекомунікаційного трафіку, самоподібний процес, мультиф-рактальний процес.

Kirichenko L. O., Demerchan K. A., Kayali E., Habachyova A. Yu. MODELING TELECOMMUNICATIONS TRAFFIC USING STOCHASTIC MULTIFRACTAL CASCADE PROCESS

In the work the simulation of telecommunications traffic has been examined, which has multifractal properties, based on a mathematical model of the stochastic multiplicative cascade, the weights of which are beta probability distribution.

Key words: a stochastic cascade process, the model of telecommunications traffic, self-similar process, multifractal process.

УДК519.24:62-50 Кошевой Н. Д.1, Сухобрус Е. А.2

1Д-р. техн. наук, профессор, заведующий кафедрой Национального аэрокосмического

университета им. Н. Е. Жуковского «ХАИ» 2 Аспирант Национального аэрокосмического университета им. Н. Е. Жуковского «ХАИ»

СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ОПТИМИЗАЦИИ МНОГОУРОВНЕВЫХ ПЛАНОВ МНОГОФАКТОРНОГО ЭКСПЕРИМЕНТА

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

Ключевые слова: программное обеспечение, симплекс-метод, быстродействие.

ПОСТАНОВКА ЗАДАЧИ увеличении количества рассматриваемых вариантов ус-

Изменение порядка проведения опытов существен- ложняется гоиск пдата с наименьшей стоим°стью. Трудно влияет на стоимость реализации эксперимента. При шсть шиота вызвана быстрым р^том мриашш ш-

© Кошевой Н. Д., Сухобрус Е. А., 2012

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

АНАЛИЗ ПОСЛЕДНИХ ИССЛЕДОВАНИЙ И ПУБЛИКАЦИЙ

Известна программа поиска оптимальных многоуровневых комбинаторных планов многофакторного эксперимента [1]. В основе работы программы лежит генерация комбинаторных планов многофакторного эксперимента, оценка их характеристик, отбор оптимального по стоимости варианта. Программа реализована на языке «Turbo Pascal». Предусмотрено два режима поиска оптимального решения: случайный поиск и последовательная генерация возможных вариантов перестановок. Количество рассматриваемых вариантов может быть задано, а процесс поиска может быть прерван.

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

1. Осуществляется ввод имени файла исходных данных, содержащего информацию о количестве анализируемых факторов, матрицу исходного плана эксперимента и стоимости изменений значений факторов. Производится чтение исходных данных.

2. Выбирается режим поиска: случайный поиск или анализ перестановок.

3. Производится выбор количества анализируемых вариантов путем введения заданного количества N или введения «0». В последнем случае процесс поиска может быть прерван при нажатии клавиши «ESC».

4. Рассчитывается стоимость исходной матрицы планирования эксперимента.

5. Осуществляется генерация перестановок строк исходной матрицы. В режиме случайного поиска генерация производится с использованием функции Randomize. В режиме анализа перестановок используется алгоритм генерации перестановок с минимальным числом транспозиций соседних элементов.

6. Производится расчет стоимости полученной матрицы и последующее сравнение её со стоимостью исходной матрицы. Если полученное значение стоимости меньше, чем стоимость исходной матрицы, то оно признается оптимальным. В противном случае полученное значение стоимости признается максимальным.

7. Производится сравнение количества проанализированных вариантов с заданным количеством N. Если заданное количество анализируемых вариантов достигнуто или произошло прерывание процесса поиска при нажатии клавиши «ESC», то осуществляется создание файла результата и переход к окончанию процесса поиска. В противном случае происходит переход к этапу 5 и повторяется аналогичная процедура.

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

перестановок и, следовательно, снижение быстродействия процесса поиска при увеличении количества уровней факторов.

ЦЕЛЬ СТАТЬИ

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

ОСНОВНАЯ ЧАСТЬ

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

1. В качестве первой строки плана выбирается та, переход на которую максимален по стоимости.

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

3. Выполняется проверка: приводит ли перемещение уровня фактора, определенного на шаге 2, к появлению повторяющейся строки. Если полученная строка не встречалась ранее, то она записывается в выходную матрицу планирования. Если полученная строка уже встречалась, то перемещается следующий по возрастанию стоимости перемещения уровень фактора или, в случае наличия равноценных по стоимости перемещения уровней факторов, следующий по порядковому номеру.

4. Производится циклический повтор шагов 2 и 3 до тех пор, пока не будет получено требуемое количество строк матрицы планирования. В случае, если все строки, в которые возможно осуществить переход, уже повторялись, а требуемое количество строк матрицы планирования не достигнуто, осуществляется возврат к строке, содержащей равноценные по стоимости перемещения уровни факторов, и перемещается следующий по порядковому номеру уровень фактора.

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

Рис. 1. Схема алгоритма работы известного программного обеспечения

г

5. ] іоніх СЛСіЦі'ЩиїВН ілрикн

Рис. 2. Схема алгоритма поиска оптимального плана эксперимента на основе симплекс-метода

Был проведен сравнительный анализ разработанного программного обеспечения с известной программой поиска оптимальных многоуровневых комбинаторных планов многофакторного эксперимента. Объектом сравнения являлся процесс оптимизации многоуровневых планов многофакторного эксперимента для количества факторов к=3 с количеством уровней факторов от 2 до 8. Сравнительный анализ производился по следующим функциональным параметрам оптимизации: полученное оптимальное или близкое к оптимальному значение стоимости реализации плана эксперимента, количество рассмотренных вариантов перестановок, время счета программы, выигрыш по стоимости реализации плана эксперимента, определяемый как отношение стоимостей реализации исходного и полученного планов эксперимента. Результат проведенного сравнительного анализа представлен в табл. 1.

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

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

Динамика изменения количества рассматриваемых вариантов перестановок при увеличении количества уровней факторов для анализируемых программ представлена на рис. 3.

Таблица 1. Сравнительный анализ разработанной и известной программ

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

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

2 18 9 40320 1 2,0000 9 8 < 0,01 2,0000

3 126 106 1000000 69 1,1887 39 27 < 0,01 3,2307

4 235 220 500000 1825 1,0682 69 64 < 0,01 3,4058

5 529 517 500000 5572 1,0232 14S 125 0,25 3,5743

6 682 671 500000 6470 1,0164 242 216 0,12 2,8182

7 2074 2053 500000 6538 1,0102 411 343 0,87 5,0462

8 2124 2109 500000 6673 1,0071 594 512 1,33 3,5758

І

К

12G0DG0 1 G 0  О G G SGGG0G 600000

Ї1

g' 400000

200000

0

іооетсю

Л і Ч

1 / \ \

і / 'яюссо soodod ЗООООО зоскоо L-OCOOC

{

40320^. 21 (А 125 216 343 igt to

2 3 4 3 6 7 8

Количество уровней факторов

— «- -Известная программа поиска оптимальных многоуровневых

комбинаторных планов многофакторного эксперимента

- -Разработанное программное обеспечение

Рис. 3. Зависимость количества рассматриваемых вариантов от количества уровней факторов

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

Зависимость быстродействия сравниваемых программ от количества уровней факторов представлена на рис. 4.

Видно, что для этих программ показатели быстродействия при реализации планов эксперимента, факторы ко-

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

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

8000

7000

6000

5000

4000

6470

Є535

35Ї2,

Г

1Г

&

СП

3000

2000

1000

__________________І—

1 О

0^25

0,12

1,33

2 3 А 5 6 7

Количество уровней факторов

+- - Изв естная программа поиска оптимальных многоуровневых комбин ат орных пл ан ов мн от о факт орн ого эк спе римент а »- -Разработанное программное обеспечение

Рис. 4. Зависимость времени счета от количества уровней факторов

Рис. 5. Зависимость выигрыша по стоимости реализации плана эксперимента от количества уровней факторов

ВЫВОДЫ

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Кошовий, М. Д. Комп’ютерна програма «Програма пошуку оптимальних багаторівневих комбінаторних планів ба-гатофакторного експерименту» / М. Д. Кошовий, О. М. Костенко, В. А. Дергачов. - Зареєстр. в Держ. де-парт. інтелектуальної власності Міністерства освіти і науки України; Реєстр. 28.01.2010, Свід. про реєстр. автор. права на твір № 31824

Стаття надійшла до редакції 09.02.2012.

Кошовий М. Д., Сухобрус О. А.

ПОРІВНЯЛЬНИЙ АНАЛІЗ МЕТОДІВ ОПТИМІЗАЦІЇ БАГАТОРІВНЕВИХ ПЛАНІВ БАГАТОФАКТОРНОГО ЕКСПЕРИМЕНТУ

Запропоновано метод пошуку оптимального або близького до оптимального за вартістю реалізації багаторівневого плану багатофакторного експерименту. Для автоматизації процесу пошуку з використанням запропонованого методу розроблено програмне забезпечення. Проведено порівняльний аналіз розробленого програмного забезпечення з програмою пошуку оптимальних багаторівневих комбінаторних планів багатофак-торного експерименту, яка реалізує метод генерації перестановок з мінімальним числом транспозицій сусідніх елементів.

Ключові слова: програмне забезпечення, симплекс-метод, швидкодія.

Koshevoy N. D., Sukhobrus E. A.

THE COMPARATIVE ANALYSIS OF OPTIMIZATION METHODS OF MULTILEVEL MULTIFACTOR EXPERIMENT PLANS

А method for finding the optimal or close to the optimum implementation value of a multi-level multifactorial experiment plan are proposed. To automate the search process using the proposed method, the software was developed. A comparative analysis of the developed software with multi-level program for finding the optimal combinatorial plans of multifactor experiment, which implements the generating permutations method with a minimal number of adjacent elements transpositions are implemented.

Key words: software, simplex method, speed.

УДК378.14:004.421

Кулик А. С.1, Пищухина О. А.2, Клочок А. Ю.3

1Д-р техн. наук, профессор, Национального аэрокосмического университета им. Н. Е. Жуковского «Харьковский

авиационный институт»

2Канд. техн. наук, доцент Национального аэрокосмического университета им. Н. Е. Жуковского «Харьковский

авиационный институт»

3Ассистент Национального аэрокосмического университета им. Н. Е. Жуковского «Харьковский авиационный

институт»

МОДЕЛИ И АЛГОРИТМЫ ПОИСКА ОШИБОК ПРИ РЕШЕНИИ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ КОМПЬЮТЕРНЫХ СРЕДСТВ ОБУЧЕНИЯ

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

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

ВВЕДЕНИЕ

На кафедре систем управления летательными аппаратами Национального аэрокосмического университета им. Н. Е. Жуковского «ХАИ» с 2004 г. непрерывно формируется и обновляется комплекс компьютерных обучающих программ, каждая из которых представляет собой независимые модули, объединяемые в единую структуру [1, 2]. Выбор задач, предназначенных для реа-

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

© Кулик А. С., Пищухина О. А., Клочок А. Ю., 2012