автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритм поиска композиционной модели Липшиц-ограниченного отображения одной переменной

Национальный исследовательский университет «МИЭТ»

На правах рукописи

Калинников Иван Сергеевич

АЛГОРИТМ ПОИСКА КОМПОЗИЦИОННОЙ МОДЕЛИ ЛИПШИЦ-ОГРАНИЧЕННОГО ОТОБРАЖЕНИЯ ОДНОЙ ПЕРЕМЕННОЙ

Специальность: 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

I5 ПАР 2015

Москва 2015

005561056

005561056

Работа выполнена на кафедре Высшей математики №1 Национального исследовательского университета «МИЭТ».

Научный руководитель:

доктор физико-математических наук, профессор Кожухов Игорь Борисович

Официальные оппоненты:

доктор физико-математических наук, профессор кафедры компьютерных методов физики Физического факультета МГУ имени М. В. Ломоносова Чуличков Алексей Иванович

доктор технических наук, профессор кафедры «Компьютерные системы и сети» факультета «Информатика и системы управления» МГТУ им. Н. Э. Баумана Иванова Галина Сергеевна

Ведущая организация:

Санкт-Петербургский государственный университет телекоммуникаций имени профессора М.А. Бонч-Бруевича (СПбГУТ)

Защита диссертации состоится 21 апреля 2015 года в 14 часов 30 мин. на заседании диссертационного совета Д212.134.02 при Национальном исследовательском университете «МИЭТ» по адресу: 124498, г. Москва, г. Зеленоград, проезд 4806, д.5.

С диссертацией можно ознакомиться в библиотеке НИУ «МИЭТ» Автореферат разослан «/¿7 » иле/Ьго 2015 г.

Ученый секретарь

диссертационного совета Д212.134.02, д.т.н., доцент

Гуреев А. В.

Общая характеристика работы Актуальность темы исследования

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

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

- получение вычислительно эффективных приближений с известной погрешностью для аналитических выражений;

- преобразование аналитических выражений к более удобной форме представления;

- синтез аналитических выражений, имеющих заданные свойства.

к. м. имеют следующие свойства, которые определяют их высокую

эффективность в названных приложениях:

- широкие возможности выбора системы базовых функций, композицией подмножества которых будет получаемое приближение;

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

- возможность построения как интерполяций, так и экстраполяций при корректном выборе системы базовых функций;

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

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

1 Далее в тексте «композиционные модели» сокращенно обозначаются «к. м.».

2 Зависимости, полученные в рамках имитационного моделирования или экспериментального исследования, далее в тексте называются «эмпирическими зависимостями» или сокращенно «э. з.».

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

Степень изученности проблемы

В зарубежной [1-3] и отечественной [4,5] литературе к. м., построенные для зависимостей нескольких аргументов, иногда называются символьными регрессиями. Данный термин ввел Дж. Р. Коза (J. R. Koza) в работе [1]. В ней рассматривается вопрос построения композиционных моделей с использованием генетических алгоритмов. Описанный в [1] подход к поиску композиционных моделей при применении к практическим задачам оказывается недостаточно эффективным. Повышение эффективности построения композиционных моделей генетическими алгоритмами за счет изменения представления данных разрабатывалось А. И. Дивеевым и Е. А. Софроновой [4,5], предложившими метод сетевого оператора. Другие методы повышения производительности рассматривались И. Зелинкой (I. Zelinka) [2], введшим метод аналитического программирования; М. О'Нилом и С. Райном (М. O'Neill, С. Ryan) [3], построившими методы на основе формальных грамматик. Недостатком построения к. м. с использованием генетических алгоритмов, по мнению автора, является отсутствие обоснования выбора операторов скрещивания с учетом утверждений теоремы Дж. Р. Прайса (G. R. Price) [6] и, соответственно, отсутствие доказательства снижения времени работы алгоритма по сравнению с алгоритмом случайного поиска. Иной подход к решению задачи построения к. м. для функций одного аргумента развит в работе С. А. Лабутина и М В. Пугина [7], которыми предложен переборный алгоритм решения данной проблемы при смешении этапов выбора структуры модели и предварительной параметрической оптимизации полученной к. м.

Задача построения композиционной модели с параметрами включает как минимум два этапа на каждом шаге:

-синтез структуры к. м. с учетом резервирования мест' под адаптируемые параметры;

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

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

Цели и задачи диссертационного исследования

Основными целями диссертационного исследования являются:

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

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

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

В соответствии с целями в ходе диссертационного исследования решались следующие задачи:

- Классификация задач построения к. м. на поиск точных, оптимальных и приближенных к. м. и их формализация.

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

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

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

- Анализ методологии теории поиска в метрических пространствах и ее применения к построению алгоритма нахождения приближенных к. м.

- Определение системы ограничений, при которых достигается повышение эффективности алгоритма поиска приближенных к. м. по сравнению со случайным поиском, при ограниченном объеме предвычислений.

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

- Разработка критерия завершения и способов реализации алгоритма поиска, позволяющих повысить его эффективность,

-Разработка модели топологий КРС с ДА и ее имитационное исследование на выбранном наборе параметров.

- Нахождение приближенной к. м. функции распределения расстояний между узлами в модели топологий КРС с ДА.

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

Научная новизна диссертационного исследования

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

Во-вторых, в диссертационном исследовании развита методология поиска в метрических пространствах [8,9]. Рассмотрены методы работы с метриками, оцениваемыми с погрешностями. Найдены варианты оптимизации процесса поиска в отсутствие линейных (от объема пространства поиска) предвычислений, при условии наличия связей значений метрик между элементами пространства. В диссертационном исследовании данные результаты применены к ускорению поиска приближенной к. м. в пространстве композиций по сравнению с алгоритмом случайного поиска. Связи значений метрик устанавливаются за счет свойства метрики Чебышева и Липшиц-

ограниченности отображений. Полученный в результате алгоритм обладает научной новизной.

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

Теоретическая и практическая значимость работы

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

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

Практической значимостью также обладает проведенный анализ различных моделей топологий КРС с ДА. Описанные модели топологий КРС с ДА, полученная аппроксимация распределения расстояний межу узлами сети применялись в рамках ОКР «Ангстрем-Р» в ОАО «НПО Ангстрем», что подтверждается справкой об использовании результатов.

Методология исследования

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

Результаты диссертационной работы получены автором лично и составляют вклад автора. Из материалов совместных публикаций [AI], [A3] в диссертационной работе использованы только принадлежащие автору.

Положения, выносимые на защиту

На защиту выносятся следующие положения:

- задача построения точной к. м. является ИР-полной, а задача построения оптимальной к. м. - ^-трудной; данные результаты верны в случае построения к. м. на основе Липшиц-ограниченных отображений одной переменной;

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

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

- на этапе эскизного и технического проектирования КРС с ДА для оценки эффективности их внедрения и принятия верных технических решений целесообразно применять модели, построенные на основе экспериментальных данных;

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

Основные результаты докладывались автором на 4 научно-технических конференциях:

- IX международной научной конференции «Инновации в науке и образовании» - г. Калининград-2011 г.

- X международной научной «Инновации в науке и образовании» -г. Калининград - 2012 г.

- XXXII Всероссийской научно-технической конференции «Проблемы эффективности и безопасности функционирования сложных технических и информационных систем» - г. Серпухов -2013 г.

- V Всеукраинской научно-практической конференции «Информатика и системные науки-2014» - г. Полтава - 2014 г.

Публикации тезисов и текстов докладов представлены в списке публикаций автора по теме диссертации [А1-А5].

По результатам диссертационного исследования автором написаны три статьи [А6-А8], опубликованные в журналах, входящих в перечень рекомендованных ВАК.

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

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

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

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

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

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

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

Текст диссертации состоит из введения, трех глав, заключения, библиографического списка и приложений. Работа изложена на 152 страницах, из них 138 страниц основного текста (10 таблиц, 8 рисунков). Библиография работы содержит 107 наименований.

Основное содержание работы

Введение

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

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

Р = {- множество базисных функций, то:

- точная к. м. длины М над множеством й - это вектор 1 = (1Х,...,1М) индексов функций из Р, такой что для любого хеД выполняется равенство ё(х) = /,1(/,1 (.../^(х)...));

- оптимальная к. м. длины М по метрике // - это вектор индексов I = (ц,такой, что на нем достигается

......то есть

/ = аггтт^л.....))) ;

- приближенная к. м. длины М точности б по метрике // - это вектор индексов / = (%...,1и) такой, что ;,)<£.

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

10

множестве базовых функций. Понятие оптимальной к. м. обобщает понятие точных к. м., более того, если точная к. м. существует - она является оптимальной. Оптимальные к. м. существуют всегда, если М> О,/г?*0. Оптимальные к. м. могут применяться для аппроксимации э. з., а также синтеза функций по ограничениям.

Проводимый в первой главе диссертационного исследования анализ вычислительной сложности построения точных и оптимальных к. м. привел к доказательству теоремы:

Теорема. Задача построения точной к. м. является ИР-полной, а задача построения оптимальной к. м. №-трудной.

Доказательство теоремы проводится редукцией проблемы ЗХС поиска точного покрытия 3-множествами, входящей в список 21 проблемы Карпа [10]. Доказательство опубликовано в работе [Аб] и приводится в тексте диссертации.

Следствие. На текущий момент не известны полиномиальные от М и N алгоритмы для решения задач построения точных или оптимальных к. м.

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

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

- основанные на сведении к параметрической адаптации, схожие с описываемыми в [А2].

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

——+1) + ё, которое возрастает показательно относительно 1/ 1

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

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

В первой главе диссертации приводится обзор методов поиска приближенных к. м., в худшем случае имеющих вычислительную сложность переборного алгоритма 0(ЫМ). К подобным методам относятся метаэвристические [11] алгоритмы построения к. м.: генетические и эволюционные алгоритмы, алгоритмы на основе симуляции отжига, алгоритмы колониальной оптимизации и т.д. Данные алгоритмы являются более устойчивыми, однако на текущий момент теоретически недостаточно обосновано их преимущество по объему вычислений по сравнению с алгоритмом случайного поиска.

В главе показывается, что поисковую процедуру аналогичного типа последовательно можно построить на основе методологии теории поиска в метрических пространствах. Если ограничить выбор метрики ¡Л метрикой Чебышева для непрерывных функций или ее поточечным приближением, то данная процедура может стать более эффективной, нежели случайный поиск. При этом традиционная методология поиска в метрических пространствах требует доработки для исключения линейных от объема пространства поиска предвычислений, которые в данном случае имеют сложность 0(ЫМ ). Вторая глава

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

Традиционно для методов метрического поиска [8,9] оптимизация достигается с применением неравенства треугольника на основе имеющихся предвычислений, однако анализ данного подхода позволяет прийти к следующим утверждениям:

Утверждение 1. Если а - элемент пространства поиска А, а х -приближаемый элемент и задачей поиска является нахождение а =а^ттасА(р(а,х)), то либо должна быть проведена непосредственная оценка а,х), либо предвычислено значение Ка.Ь), где Ъ е А - другой элемент пространства поиска.

Утверждение 1 следует из того, что для оценки минимума значение /л(а,х) должно быть либо непосредственно оценено, либо оценено с использованием неравенства треугольника за счет оценки //(Ь,х).

Утверждение 2. Пусть все пары элементов (а,Ь) пространства поиска А, для которых предвычислено ц(а,Ь), будут ребрами графа С = (А,Е). Для работы алгоритма поиска а =а^ттаеА( ц(а,х)) в каждой компоненте связности v из |к| вершин графа С?, где уже было совершено не менее |К| -1 предвычислений, потребуется минимум одно вычисление метрики ,х).

Утверждение 2 следует из утверждения 1 и неравенства треугольника.

Утверждение 3. Суммарный объем вычислений - предвычислений и вычислений значений метрик не менее \а\ .

Утверждение 3 следует из утверждения 2, суммированием по всем компонентам связности.

Более подробно данные утверждения (1-3) рассматриваются в тексте диссертационного исследования и статье [А7].

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

Методология теории поиска в метрических пространствах, развитая в работах [8,9], не оперирует понятием погрешности определения значения метрики, которое неизбежно при работе с экспериментальными данными или оценивании метрики Чебышева по дискретной сетке. Поэтому при разработке алгоритма вместо метрики

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

метрики считается меньше (<) другой [ , //2+ ], если

</л'г)л(/л^ <£), где /.¡и и />2~„д/2+У - оценки различных

расстояний. При этом сравнимыми (э ) считаются оценки [^ ,/.1* ] ,

Л^./^У. если |/"> с£,у> гДе ^ характеризует

минимальную достижимую погрешность поисковой процедуры и предельную точность определения значения расстояния. В таком случае критерием полного завершения поиска будем считать достижение ситуации, когда выбрана наименьшая (относительно порядка <) оценка и нет сравнимых (=„ ) с ней оценок. Перспективным множеством

поиска (является множество оценок, сравнимых () с

наименьшей из найденных оценок [■

Для упрощения предположим, что базовые функции и целевая функция - сюръективные отображения /"ОД] -» /"0,1 ] . Целевую функцию, определенную на ограниченном отрезке, в силу ее Липшиц-ограниченности, всегда можно привести к рассматриваемому виду линейным преобразованием значений функции и аргумента. Для метрики Чебышева (задачи приближения зависимости на отрезке) /-ё) - таххе[й,\]\/(х) ~8(х)\ или ее поточечного варианта />Е) = тахх^[о,\]\/(х)~х)\ (задачи приближения зависимости в

фиксированном наборе узлов Б) верны следующие ограничения на значения верхних и нижних оценок метрики:

1. ц+(а,Ь) = ц+(Ъ,а)< 1, ¿Г(а,Ь) = М~(Ь,а)> 0, М*(а.а) = 0, ц(а,а) = 0;

2. ^(а,Ь)<^(а,с) + и+(с,Ь)-

3. ¡.Г(а,Ъ) > тах(/Г(а,с) + (с,Ъ),/Г(Ь,с) + //+(с,а));

4. 1?(а,Ъ) = тт(ц\(а,Ъ),ц\(а,Ъ)),

ц~(а,Ъ) = тах(ц-х(а,Ъ),ц1(а,Ъ)), где //,\//2+//Г - оценки, полученные различными способами;

5. ц±(а(= /.1±(а,Ь) , в случае если // - метрика Чебышева и

О, Ъ(1)) = а, Ъ) ± Н(3, 1(8))(Ьи +Ьь) - в случае если ^ -поточечный аналог метрики Чебышева, при этом

Н(Б,Т) - - ф - предельное расстояние между сетками

5 и Т, а Ьа,1ъ - константы Липшица отображений а,Ь.

6. /.1+(^а)^(Ь))<11^(а,Ь), где Ц - константа Липшица функции /.

7. /Г(^а)^(Ь))> А1/.Г(а,Ь), где А, - константа минимального изменения, существующая только для монотонных функций и определяемая из условия V*,,х2 е [0,1 хх)-1(х2)\ > А,|х, -х2\. Здесь а,Ъ, с обозначают целевую функцию - g или к. м. - Стр(1,Р), а /eF- одна из базовых функций. При этом ограничения 1-3 соответствуют определению метрики, ограничение 4 определяет правило совместного действия различных оценок метрики, а ограничения 5-7 связывают значения метрик между различными элементами пространства.

С использованием полученных ограничений 1-7 удается построить алгоритм поиска, работающий эффективнее случайного поиска без предвычислений, пропорциональных объему пространства. Алгоритм поиска работает в пространстве всевозможных векторов и = {('¡1,-,'м)\1,,-,1м }} индексов базовых функций из Р, где

требуется найти вектор индексов Г минимизирующий

ц(¿,Стр(I' ,Р)) с учетом того, что точность определения метрики не более сее. Работу алгоритма можно представить как

последовательность получения различных оценок метрик, часть из которых завершается изменением текущего лучшего решения [Кш-Кт] или(и) изменением множества ^„//й./С,,^ Поскольку изменение лучшего решения влияет на размер множества иа,(М,то оценка его размера

)= Т,(^(Стр(1,Р),к)-^(Стр(1,Р)^)) является

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

1¥(исе (({))-1У(исе (1г)) ¿2 будем понимать значение Е(ЦЛг) =-1-1- -

отношение уменьшения размера множества перспективных вариантов к количеству вычислений С(1и12), проведенных между и /2.

Считая основной вычислительной сложностью получение оценок значений метрик путем вычисления значений функций на сетках, можно предложить способ повышения эффективности алгоритма случайного поиска приближенной композиционной модели. Предвычислив оценки р±(Стр( ),Стр()), где У, е{(11,...,1к)\{11,...,1к е Д..,// },К <М }} короткие (длиной К <М ) наборы индексов базовых функций, можно на каждом шаге алгоритма после непосредственной оценки ц±(Стр( 1,Рполучить набор оценок {/л±(Стр(I, пользуясь неравенством треугольника (3) и имея оценки {/л±(Стр( 1,Г),Стр(I,Р))} . В свою очередь оценки {/л±(Стр(1,Е),Стр(1 ,¥))} получаются за счет оценок р?(Стр(1!1,Р ),Стр(3 )) с применением ограничений 5-7. Подробнее данный алгоритм рассматривается в тексте диссертационной работы как «алгоритм 5» и в статье [А7]. Эффективность алгоритма по значению Е(0,(), где / - время от начала поиска в мс., показана рисунке 1, где пунктиром обозначена эффективность алгоритма случайного поиска, а сплошной линией - эффективность оптимизированного алгоритма, при этом время и вычислительная сложность предвычислений включены в расчет.

поиска

Достигнутое повышение производительности не может сделать вычислительную сложность алгоритма полиномиальной, так как он находит оптимальное (в рамках погрешности) решение. В соответствии с методологией метрического поиска для построения приближенного алгоритма необходимо применить эвристику раннего завершения. Для этого в алгоритм вводится предположение о возможных распределениях значений Р{ Стр( I, Р),§) = х} - рассматриваются взвешенные суммы показательного, степенного и равномерного распределения с дельта-функцией в 1. Параметры всех видов распределений оцениваются одновременно по выборке последних просматриваемых

алгоритмом значений р+(Стр(1,Р)^). Наиболее подходящее распределение выбирается по критерию х1 > в зависимости от последних просмотренных алгоритмом значений /1+(Стр(1,Р. На

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

Совокупность оптимизации работы алгоритма поиска, применения эвристики раннего завершения и приемов реализации алгоритма (описанных в конце главы 2) позволяет на персональной ЭВМ успешно

17

проводить поиск композиционной модели в пространствах мощности

|С/|~Ю10-10М.

Третья глава

В третьей главе приводится пример использования разработанного алгоритма построения приближенных к. м. к аппроксимации распределения расстояний между узлами в одноранговой КРС с ДА. Целью построения подобных аппроксимаций традиционно является интеграция э. з. в аналитический расчет интересующих характеристик КРС с ДА.

КРС с ДА ([А8], МезЬ[12]) являются компьютерными сетями, узлы которых обладают равными потенциальными возможностями при доступе к сети и в равной степени могут быть использованы для передачи трафика всех абонентов сети, при этом характеризуются динамичной сменой состава радиоканалов связи, перечня абонентов и узлов сети. КРС с ДА решают задачу организации высокоскоростной сети в ограниченной области пространства, лишенной базовой инфраструктуры. Повышение пропускной способности в такой сети достигается путем расширения полосы ведения связи, оптимизации энергетики организуемых каналов связи за счет применения ретрансляций сигналов соседними с передающей станцией узлами, которые наиболее близки к станции-получателю.

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

Предельная скорость обменов между узлами, количество служебного трафика и другие параметры КРС с ДА зависят от модели топологии сети. Имеющиеся методы аналитической оценки параметров КРС с ДА, например [13,14], не привязаны к практическим моделям топологий и не могут применяться при определении параметров разрабатываемой КРС с ДА на этапах эскизного или технического

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

Данные наблюдения приводят к выводу о возможности гибридного подхода к моделированию КРС с ДА, когда на основе требований заказчика строится имитатор топологии, из которого после моделирования получается ряд э. з. Примером такой зависимости, необходимой при анализе КРС с ДА, является распределение расстояний между узлами сети [15].

В главе рассматривается модель топологии КРС с ДА на основе алгоритма группового движения К. Рейнольдса (С. Reynolds) [16]. Из нее получается эмпирическое распределение расстояний, представленное на рисунке 2. Из нескольких вариантов аппроксимаций (МНК, сплайн-интерполяция и к. м.), наиболее корректно описывает эмпирическую зависимость приближенная к. м. (рисунок 3). Аналитическое выражение данной к. м. достаточно удобно для применения в расчете характеристик КРС с ДА с соответствующей моделью топологии.

0,3

15 20 25 30 35 40 45 50 Расстояние, км

Рис. 2 — Эмпирическая функция распределения расстояний

.(.1).{.Интерполяция кубичеокими-сплайнами (2) т Композиционное представление (3.11) - МНК аппроксимация полиномами 9 степени (3.2) - МНК аппроксимация полиномами 7 степени (3.31) - МНК аппроксимация полиномами 5 степени

5 10 15 20 25 30 Расстояние, км

Рис. 3 — Различные аппроксимации распределения расстояний Заключение

В ходе диссертационного исследования были получены следующие результаты:

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

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

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

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

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

- Проведено имитационное исследование одной из моделей топологий КРС с ДА на выбранном наборе параметров.

- Найдена э. з. распределения расстояний между узлами в модели топологии, для нее построены аппроксимации различными способами (МНК, кубические сплайны, приближенная к. м.).

-Показано, что наиболее корректной аппроксимацией является приближенная к. м., которая может далее использоваться в оценке параметров КРС с ДА при заданной модели топологии.

Таким образом, основные задачи диссертационной работы выполнены и реализованы цели исследования:

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

- построен и реализован оптимизированный алгоритм случайного поиска приближенной композиционной модели;

- проанализированы возможности применения разработанного алгоритма для аппроксимации э. з. на примере из области моделирования топологий КРС с ДА.

Список источников

1. Koza, J. R. Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems / J. R. Koza, Stanford university.- 1990,- 131 p.Th. rep. CS-TR-90-1314.

2. Zelinka, I. Analytic programming - symbolic regression by means of arbitrary evolutionary algorithms / I. Zelinka, Z. Oplatkova, L. Nolle // International Journal of Simulation, Systems, Science and Technology: Special Issue on Intelligent Systems - 2005 - №6(9).- p. 44-56.

3. O'Neill, M. Grammatical evolution: Evolutionary automatic programming in an arbitrary language / M. O'Neill, C. Ryan.- Kluwer Academic Publishers, 2003- 144 p.

4. Дивеев, А.И. Метод сетевого оператора и его применение в задачах управления: монография / А. И. Дивеев, Е. А. Софронова-М.:РУДН, 2012.- 182 с.

5. Софронова, Е. А. Метод сетевого оператора для решения задачи многокритериального структурно-параметрического синтеза системы управления: автореф. дис. на соиск. учен. степ. к. т. н. (05.13.01) / Е. А. Софронова,-М.:2008,- 18 с.

6. Altenberg, L. The schemata theorem and Price's theorem / L. Altenberg // Foundations of genetic algorithms 3 / Ed. D. Whiteley, M. Vose - San Francisco: Morgan Kaufmann, 1995 -p. 23-49.

7. Лабутин, С. А. Анализ сигналов и зависимостей : Учеб. пособие / С.А. Лабутин, М.В. Пугин; Нижегород. гос. тех. ун-т.- Н. Новогород, 2001,- 158 с.

8. Searching in metric spaces / E. Chavez, G. Navarro, R. Baeza-Yates, J. L. Marroquin// ACM Comput. Surv.-2001.-№ 3(33).-p. 273-321.

9. Similarity search: The metric space approach / P. Zezula, G. Amato, V. Dohnal, M. Batko .- Springer, 2006 .- 220p.

10. Karp, R. M. Reducibility among combinatorial problems / R. M. Karp // Complexity of Computer Computations / Ed. R. E. Miller, J. W.Thatcher- Plenum Press, 1972- Mode of access: cs.stanford.edu/people/trevisan/csl72-07/karp.pdf.

11. Sean, L. Essentials of Metaheuristics / L. Sean - 2013 - Mode of access: cs.gmu.edu/~sean/book/metaheuristics/ (ver.2.1).

12. Challenges and Issues in designing architectures and protocols for wireless mesh network / V. C. Gungor, E. Natalizio, P. Pace, S. Avallone .Mode of access: www.academia.edu/894954/Challenges_and_Issues_in_ Designing_Architectures_andJProtocols_for_Wireless_Mesh_Networks.

13. Marcus, J. N. Throughput for packet radio networks with dynamic power levels / J. N. Markus: dis. on master of science degree - MIT, 1984.111 p.-Mode of access: dspace.mit.edu/handle/1721.1/15406.

14. Gupta, P. The Capacity of wireless networks / P. Gupta, P. R. Kumar // IEEE trans, on inform. Theory.- 2000,- № 2(46).- p. 388404.

15. A primer in spatial modeling and analysis in wireless networks / J. G. Andrews, R. Ganti, M. Haenggi, N. Jindal, S. Weber // IEEE comm. magazine.-2010.-№ll(48).-p. 156-163.

16. Reynolds, C. W. Flocks, herds and Schools: A distributed behavioral model / C.W.Reynolds // SIGGRAPH Computer graphics.-1987.-№4(2 l).-p.25-34.

Публикации автора по теме диссертации

Тезисы и доклады

А1. Калинников, И. С. Разработка алгоритмов построения декомпозиционных моделей непрерывных отображений / И. С. Калинников, С. С. Нестерова // Труды IX международной научной конференции «Инновации в науке и образовании» в 2 ч - Калининград: КГТУ, 2011.-4.2,- с.76-78.

А2. Калинников, И. С. Алгоритм построения декомпозиции непрерывной функции одного аргумента по заданному множеству

функций / И. С. Калинников // Труды X международной научной конференции «Инновации в науке, образовании и бизнесе» в 2 ч-Калининград: КГТУ, 2012,-ч.2.- с.160-163.

АЗ. Калинников, И. С. Алгоритм маршрутизации для беспроводных сетей с динамической архитектурой / И. С. Калинников, А. В. Сахариленко // Труды X международной научной конференции «Инновации в науке, образовании и бизнесе» в 2 ч,- Калининград: КГТУ, 2012-Ч.2.-С.173- 175.

А4. Калинников, И. С. Декомпозиция отображений как способ автоматизированного построения моделей сложных систем / И. С. Калинников // Труды XXXII Всероссийской научно-технической конференции «Проблемы эффективности и безопасности функционирования сложных технических и информационных систем»,-Серпухов: фил. Военной ак. им. Петра Великого, 2013 - том 5 - с. 213217.

А5. Калинников, И. С. Сложность поиска оптимальной композиционной модели Липшиц-ограниченной функции / И. С. Калинников // Сборник трудов V Всеукраинской научно-практической конференции «Информатика и системные науки-2014».-Полтава: ПУЭТ, 2014.- с. 133-135.

Публикации в журналах, рекомендованных ВАК

А6. Калинников, И. С. Вычислительная сложность построения Липшиц-ограниченных отображений композиционных моделей / И.С.Калинников // «Прикладная дискретная математика» .- 2014-№3 (25).— с.ЮЗ — 110.

А7. Калинников, И. С. Алгоритм поиска приближенной композиционной модели Липшиц-ограниченной сюръективной функции / И.С.Калинников // «Прикладная информатика»,- 2014,— №4(52).- с.49-57.

А8. Калинников, И. С. Декомпозиционное представление в моделировании компьютерных радиосетей с динамической архитектурой / И. С. Калинников // «В мире научных открытий»,-2013—№7(43).—с.297-320.

Подписано в печать: Формат 60x84 1/16. Уч.-изд. л. 1.2. Тираж 80 экз. Заказ №16. Отпечатано в типографии ИПК МИЭТ. 124498, г. Москва, г. Зеленоград, проезд 4806, д. 5, МИЭТ