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

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

005060712

Лазарев Евгений Александрович

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

Специальность 05.13.01. - "Системный анализ, управление и обработка информации (в науке и промышленности)" по техническим наукам

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

3 О МАЯ

Нижний Новгород - 2013 г.

005060712

Работа выполнена на кафедре «Вычислительные системы и технологии» федерального государственного бюджетного образовательного учреждения высшего профессионального образования Нижегородский государственный технический университет им. P.E. Алексеева.

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

доктор технических наук, доцент

Официальные оппоненты: Есипенко Валентин Иванович, доктор

физико-математических наук, профессор, Нижегородский государственный технический университет им. P.E. Алексеева, заведующий кафедрой «Теория цепей и телекоммуникации»

Белов Дмитрий Алексеевич, кандидат технических наук, ОАО «МТС», ведущий специалист отдела технического администрирования

Ведущая организация: ОАО «Научно-производственное

предприятие «Полет», г. Нижний Новгород

Защита диссертации состоится « G » июня 2013 года в Н часов в ауд. 1258 на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева.

Автореферат разослан «_£_» 2013 года.

Ученый секретарь диссертационного совета

A.C. Суркова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. С развитием сети Интернет, сетей связи и коммуникации люди стали обмениваться все большими объемами информации. Немаловажную роль играет высокая доступность телекоммуникационных услуг. Так, к концу 1995 года в мире насчитывалось всего 26 миллионов пользователей сети Интернет, тогда как к сентябрю 1999 их количество перевалило за 201 миллион, а в 2012 интернет-аудитория составляет более полутора миллиардов человек (около четверти населения земного шара).

По прогнозам компании Cisco объем передаваемых данных в сети Интернет к 2015 году по сравнению с 2011 возрастет в 4 раза, достигнув отметки в тысячу экзабайт в год. Такое значительное увеличение количества передаваемой информации будет оказывать существенную нагрузку на имеющиеся сети передачи данных (СПД). Таким образом, оптимизация существующих и создание новых СПД, способных удовлетворить все растущие требования конечных пользователей, являются крайне важными и актуальными задачами.

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

Проектированию и оптимизации СПД посвящены работы В.М. Гостева, Д. Дэвиса, Ю.П. Зайченко, JI. Клейнрока, С.Е. Ландсберга, A.A. Морозова, М.Х. Прилуцкого, И.А. Соколова, A.A. Стецко, Г.Ф. Янбыха, М. Gerla и М. Averiii. Фундаментальные исследования по компьютерным сетям представлены в работах Д. Бертсекаса, Р. Бесслера, В.И. Вишневского, A.B. Максименкова, В.Г. Олифер и H.A. Олифер, М. Шварца, A.B. Шмалько, M.G.C. Resende и P.M. Pardalos. Различным методам решения многокритериальных задач оптимизации посвящены работы М.А. Айзермана, Д.И. Батищева, Ю.А. Дубова, Д.И. Когана, В.Д. Ногина, В.В. Подиновского, Ю.С. Федосенко, Д.Е. Шапошникова, Р. Штойера и других.

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

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

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

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

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

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

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

Для достижения поставленной цели решались следующие задачи.

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

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

■ 3. Адаптация различных методов бикритериальной оптимизации для решения задачи пункта 2 и оценка их трудоемкости.

4. Программная реализация предложенных методов.

Научная новизна работы состоит в следующем.

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

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

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

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

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

1. Математическая модель сети передачи данных.

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

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

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

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

Внедрение. Результаты работы использованы в практической деятельности ООО «Теком» при разработке системы анализа и мониторинга качества услуг широкополосного доступа Ж\"/1п (^оБ, а также внедрены в учебный процесс НГТУ при организации лекционного курса «Моделирование» для студентов и аспирантов кафедр «Вычислительных систем и технологий» и «Компьютерные технологии в проектировании и производстве».

Апробация работы. Основные результаты диссертации докладывались на конференциях различного уровня.

1. Вторая международная конференция «Second International Conference on Network Analysis», Nizhny Novgorod, 2012.

2. Международные молодежные научно-технические конференции "Информационные системы и технологии", Нижний Новгород, 2010, 2011 (выступление отмечено дипломом), 2012 (выступление отмечено дипломом).

3. Международная молодежная научно-техническая конференция "Будущее технической науки БТН - 2011", Нижний Новгород, 2011.

4. Нижегородская сессия молодых ученых, Нижний Новгород, 2012 (выступление отмечено дипломом).

5. Десятая научная конференция с участием зарубежных ученых «Дифференциальные уравнения и их приложения в математическом моделировании», Саранск, 2012.

Публикации. Материалы диссертации опубликованы в 14 печатных работах, из них четыре статьи в рецензируемых научных журналах списка ВАК [1-4].

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад диссертанта в опубликованные работы. Математическая модель сети передачи данных, алгоритмы, основанные на эволюционно-генетическом подходе и методе ветвей и границ, разработаны совместно с соавторами. Решающая процедура, основанная на методе имитации отжига, все дополнительные эвристики и способы оценки субоптимальной совокупности решений предложены соискателем. Программный комплекс решения задачи проектирования и оптимизации сети передачи данных и все алгоритмы, представленные в работе, реализованы лично диссертантом. Подготовка публикаций проводилась совместно с соавторами, причем соискателем были лично написаны [Ошибка! Источник ссылки не найден.3, 5, 6, 7, 14]. Все представленные результаты вычислительных экспериментов получены лично диссертантом.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, пяти приложений и библиографического списка из 125 наименований; содержит 120 страниц текста, 34 рисунка и 12 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

на защиту положения. Приводится аннотированное изложение по главам содержания диссертации.

В первой главе (Методы решения многокритериальных задач оптимизации сети передачи данных) даются общие сведения о задачах транспортного типа (§1.1), проводится обзор подходов (§1.2) и некоторых алгоритмов (§1.3, §1.4 и §1.5) решения многокритериальных задач, моделей и методов оптимизации сетей передачи данных (§1.6).

Во второй главе (Математическая модель, задача и алгоритмы оптимизации сети передачи данных [1, 4, 6, 8, 9, 11, 12, 14]) рассматривается структура телекоммуникационной сети, проводится построение математической модели сети передачи данных, формулируется бикритериальная задача оптимизации СПД, дается анализ ее вычислительной сложности. На основе метода ветвей и границ разрабатывается алгоритм нахождения множества Парето-оптимальных решений рассматриваемой задачи. Приводится оценка вычислительной сложности предложенного алгоритма.

В §2.1 рассматривается телекоммуникационная сеть, структура которой изображена на рисунке 1.

Телекоммуникационная сеть состоит из следующих компонентов.

1. Терминальное оборудование конечных пользователей.

2. Сети доступа.

3. Магистральная сеть.

4. Информационные центры, или центры управления сервисами.

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

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

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

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

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

Интернет - это «сеть сетей», но каждая входящая в Интернет сеть управляется независимым оператором - поставщиком услуг Интернета (Internet Service Provider, ISP). Некоторые центральные органы существуют, но они отвечают только за единую техническую политику, за согласованный набор стандартов, за централизованное назначение жизненно важных параметров сети.

сеть (LAN/PBX)

Рисунок 1 - Структура телекоммуникационной сети

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

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

ILEC (Incumbent Local Exchange Carriers) - уполномоченные региональными операторами связи, предоставляющие услуги Интернета в небольшом регионе.

NAP (Network Access Point) - центр обмен, в котором соединяются сети большого числа операторов.

Магистральный поставщик услуг 2__

Магистральный поставщик ~ услуг 1

Магистральный поставщик услуг 3

Корпоративны*

■ ■; /ЛИОНУ ^

Региональный поставщик услугЗ

Региональный поставщик услуг 1

Региональный поставщик услуг 2

Корпоративный^ --J

^ . клиент;^У/Локальнь1й

-/ ПОСТаВщИК

) V услуг 4

Локальный поставщик ч услуг

Локальный поставщик услуг 3

ILEC2

ILEC1

Корпоративный »клиент

Корпоративный

клиент

Индивидуальные клиенты

Индивидуальные клиенты

Рисунок 2 - Структура сети Интернет

В данном диссертационном исследовании рассматривается задача оптимизации сети передачи данных (Transmission Network), которая является составной частью магистральной сети и чаще всего принадлежит одному поставщику услуг Интернета.

В параграфе предлагается модель сети передачи данных, основанная на классических потоковых моделях. Известен ориентированный ациклический граф G = (V,E), описывающий существующую сеть (пример представлен на рисунке 3). V - множество вершин, которым соответствуют узловые элементы сети (коммутаторы). Ребро (u,v)eE между вершинами и и v задает канал связи и имеет положительную пропускную способность c(u,v), показывающую, какое максимальное количество информации может быть передано по нему в единицу времени.

В графе выделяются две особые вершины: источник информации i и сток (. Из i ведут каналы от магистрального оператора, соединяющие сеть регионального ISP с сетями доступа. В сток ведут ребра от коммутаторов, к которым подключены сети доступа.

Множество ребер Е' (Ег\Е' = 0) описывает все каналы передачи данных, которые могут быть достроены. Для каждого (и,у)е£" известна пропускная способность с'(и, у) и стоимость строительства /?'(м,у). Пронумеруем все ребра из множеств Е' произвольным образом различными целыми числами от 1 до |£"|. Обозначим через е, ребро с номером г из Е'.

Магистральный поставщик услуг

Сети доступа

Рисунок 3 - Пример графа С, описывающего сеть передачи данных

Процесс транспортировки данных в сети моделируется с помощью функции потока fG :У хУ —»М. (х - декартово произведение, К. - множество вещественных чисел). Величина /с(м,у) показывает, какое количество информации передается в единицу времени по каналу связи, соответствующего ребру между вершинами и и V . Функция fc удовлетворяет трем условиям.

1. Ограниченность пропускной способности: \/и, у е V : /с(м,у)< с(м,у).

2. Антисимметричность: Vм,у е V : /с(м,у) = -/0(у,м).

3. Сохранение потока: \/и е V \{.?,/}: ^/с(м,у) = 0.

геУ

Через |/с| обозначим величину потока в графе С, показывающую какое количество информации может быть передано из источника в сток за единицу времени. Тогда |/с| вычисляется следующим образом:

|/с| = 1/сМ.

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

Планом проектирования сети передачи данных назовем множество ребер Е* с£". Оно соответствует каналам связи, которые будут достроены. При принятии решения о реализации плана проектирования исходная сеть трансформируется в сеть, описываемую графом G* = iy,EvjE'\

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

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

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

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

В §2.3 вводятся критерии оптимизации сети передачи данных. Через «2| обозначим стоимость реализации плана проектирования Е :

ßi(£*)= Zp'M-

(и,\>)еЕ

Через Qi{ß*) обозначим величину максимальной пропускной способности сети, описываемой графом G*, взятую со знаком минус1:

Задача оптимизации формулируется следующим образом.

Задача. По заданным ациклическим ориентированным графам G = (V,E) и множеству ребер Е'(ЕглЕ' = 0), матрицам пропускных способностей c(u,v) и c'(u,v) и матрице стоимости ребер p'{u,v) найти множество Парето-оптимальных решений задачи min (ß, (е* )), min (q2 (е* )).

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

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

Зная максимальную пропускную способность модифицированной сети, можно оценить, какое наибольшее количество конечных пользователей может ее использовать. Эта информация очень важна по следующей причине: региональный поставщик услуг сети Интернет покупает у магистрального оператора «виртуальный» канал определенной пропускной способности. В случае, если количество информации, передаваемой по нему, превышает данную величину, то региональный 1БР платит магистральному поставщику пени в зависимости от размера превышения. Значение функции штрафа растет достаточно быстро, поэтому выход за лимит пропускной способности «виртуального» канала является крайне нежелательным событием. Таким образом, поставщик услуг Интернета, зная максимальную пропускную способность сети, может оценить, какое количество пользователей он может обслужить без необходимости выплачивать пени.

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

Решение:

Исходная сеть передачи данных имеет пропускную способность равную 3 и нулевую стоимость. Из нее можно получить три различных сети с пропускными способностями 8, 98 и 103 и стоимостями 30, 50 и 80 соответственно. Графы, описывающие их, изображены на рисунке 5, рисунке 6 и рисунке 7. При этом для каждого ребра (и, у) указана его пропускная способность с(и,у) и величина потока /(и, у).

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

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

Рисунок 5 - Пример сети, с пропускной способностью 8, стоимости 30

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

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

В §2.4 описывается алгоритм полного перебора BF (Brute Force) решения рассматриваемой задачи и приводятся результаты экспериментов.

Показывается, что вычислительная сложность данного алгоритма составляет

o(2l£'l-|vf).

Рисунок 7 - Пример сети, с пропускной способностью 103, стоимости 80 В §2.5 описывается алгоритм В&В, основанный на методе ветвей и границ (Branch and Bound), решения рассматриваемой задачи и приводятся результаты вычислительных экспериментов. Доказывается, что его

вычислительная сложность составляет С>(2'£'-|V|3]. Алгоритмы BF и В&В имеют одинаковую вычислительную сложность, но среднее время работы метода ветвей и границ значительно меньше, чем у полного перебора, что доказывается вычислительными экспериментами, результаты которых приведены в параграфе.

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

В третьей главе (Синтез субоптимального множества решений задачи оптимизации сети передачи данных [2, 3, 5, 7, 10]) вводятся понятия представительной выборки и субоптимальной совокупности, предлагаются два способа оценки отклонения субоптимального множества от Парето-совокупности. Для решения рассматриваемой в диссертационной работе задачи применяются эвристические процедуры поиска субоптимального множества решений на основе метода имитации отжига и эволюционно-генетического подхода. Приводятся результаты вычислительных экспериментов, оценки вычислительной сложности и рассматриваются примеры работы предложенных алгоритмов.

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

Так как задача относится к классу ЫР-трудных, то можно сделать вывод о невозможности ее решения полиномиальными алгоритмами, принимая во внимание общепринятую гипотезу Р Ф ЫР. При рассмотрении реальных сетей передачи данных |£"| может достигать величин порядка сотни, поэтому алгоритмы, имеющие не полиномиальную сложность, не способны дать ответ за приемлемое время.

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

Решения, найденные эвристическим алгоритмом, доминируемые каким-то другим решением, не представляют интереса и, поэтому, могут быть исключены из рассмотрения. В связи с этим в §3.2 дается определение субоптимального множества решений.

Множество решений А {\/а е А: а е О) назовем субоптимальным, если оно достаточно близко к фронту Парето, и каждый элемент из А не доминирует и не равен ни одному другому элементу из А .

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

В §3.3 предлагаются два способа оценки отклонения А(К,К') субоптимального множества решений К' от совокупности Парето К :

Д 2{K,K') = avg

(вм&ММ'

16

max(Qnp,Qb)

\K\

min p(x;x')

(в| (*).Й2 _

р(х";х0)

ч /

где = |{х: х е АГ,х <£. , = |{х: х е Л",х £ А"|, х, х' и х" - соответствуют планам проведения дополнительных каналов,

р(х;х')= max(\Ql(x)-Ql(x')i,\Q2(x)~Q2(x'J) - расстояние между решениями х и х', которым соответствуют оценки (<2, (х), Q2 (х)) и (Q,(x'),Q2(x')); (Q](x"),Q2(x"J) - ближайшая к (Q2(x'\б2(х')) оценка, avg - операция вычисления среднего значения.

В §3.4 описывается алгоритм SPEA_M (Strength Pareto Evolutionary Algorithm Modified), основанный на эволюционно-генетическом подходе. Схема работы метода представлена на рисунке 8.

Рисунок 8 - Схема работы генетического алгоритма

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

1. Из популяции происходит отбор в множество недоминируемых особей (при этом из Ш удаляются элементы, доминируемые вновь добавленными).

2. Если мощность множества недоминируемых особей превышает М , то используется метод кластеризации, описанный для алгоритма БРЕА, чтобы уменьшить размер М> до требуемой величины. Так получается множество недоминируемых особей следующего поколения.

3. К популяции добавляются «мутанты» (особи, созданные случайным образом), чтобы привнести новый генетический материал.

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

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

1. Способ кодирования решения.

2. Выбор метода скрещивания особей.

3. Алгоритм вычисления приспособленности особи.

4. Методика поддержания многообразия решения.

5. Общая схема работы алгоритма (использование концепции элитизима).

6. Критерий останова.

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

В параграфе анализируется вычислительная сложность основных этапов работы генетического алгоритма. Доказывается оценка времени расчета нового поколения, которая составляет О^ТУ • + N ■ м), где N - размер популяции.

Требования по памяти данного алгоритма имеют экспоненциальную зависимость от размерности задачи, так как необходимо хранить все недоминируемые решения, найденные в ходе работы. Однако, принимая во внимание ограничение на максимальный размер М Парето-совокупности, требование по памяти составляет о(м \g\E\ + |У|2).

В параграфе представлен пример решения задачи алгоритмом 8РЕА_М, а также результаты вычислительных экспериментов.

В §3.5 предлагается алгоритм SA (Simulated Annealing), основанный на методе имитации отжига. Общее количество итераций алгоритма для каждого решения из множества S равно t ■ togc(Tnin/T!mx). На вычисление вектора решений S на каждом шаге работы алгоритма требуется время порядка о(|Е'| • |v|3 +|£'|))- Общее число шагов работы алгоритма составляет

Г.log

V шах J

Требования по памяти данного алгоритма составляют о((м +1£"|2 ]■|£"|].

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

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

В §3.7 представлен сводный график (рисунок 9) времени работы всех рассмотренных в работе алгоритмов и графики (рисунок 10 и рисунок 11) среднего значения отклонения субоптимальной совокупности оценок найденных генетическим алгоритмом и методом имитации отжига, вычисленного двумя способами. Время, с

0,01

15 20 25 30 35 40 45 |Е'|

-»-BF -И-В&В —SPEA_M+B&B -*-SPEA_M ^SA

Рисунок 9 - Среднее время работы алгоритмов

Ах, %

0,14 0,12 0,1 0,08 0,06 0,04 0,02

15 20 25 30

■ SPEA М ISA

35

40

45 |Е'|

Рисунок 10 - Среднее значение отклонения Д,

Л2,%

9

15

20

35

40

45 | Е' |

25 30

■ SPEA_M ■ SA

Рисунок 11 - Среднее значение отклонения Д2 Все вычислительные эксперименты проводились на компьютере с двуядерным процессором Intel® Core™ 15 М520 с частотой 2.4 гигагерца и 4 ГБ оперативной памяти DDR3.

В четвертой главе (Программный комплекс решения задачи проектирования и оптимизации сети передачи данных и рекомендации по

применению алгоритмов [13]) в §4.1 описывается назначение и возможности программного комплекса. В §4.2 рассматривается архитектура разработанного программного обеспечения, представлена высокоуровневая схема (рисунок 12) взаимодействия между его компонентами. В §4.3 описывается графический пользовательский интерфейс (рисунок 13). В параграфе представлено описание основного окна работы программы, элементов меню, а также окна параметров алгоритма. В §4.4 дается типовой сценарий работы с программным комплексом. В §4.5 представлены рекомендации по использованию рассматриваемых алгоритмов.

В заключении изложены основные научные и практические результаты диссертационной работы.

Приложение содержит документы о внедрении и использовании результатов диссертационной работы, свидетельство о государственной регистрации программы для ЭВМ, доказательства теорем о ЫР-трудности и максимальной мощности множества Парето-оптимальных решений рассматриваемой задачи, описание архитектуры интерактивного программного комплекса (ИПК), иМЬ-диаграммы основных классов ИПК, пример конфигурационного файла р1^Ш5.хт1, описывающего решающие алгоритмы и параметры их запуска.

Алгоритм I Алгоритм 2

Алгоритм п

Менеджер алгоритмов

Анализатор результатов

Графический пользовательский интерфейс

Рисунок 12 - Схема взаимодействия между компонентами ИПК

Оптимизация сети передачи данных

Файл Граф Решения Справка

Построена

Алгоритм:

| Метод ветвей и границ •*• |

Настройки алгоритма

Рисунок 13 - Основное окно программного комплекса

Добавить вершину

Ш

Удалить вершину

Сделать источником

Сделать стоком

Начать оптимизацию

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях из сниска ВАК

1. Лазарев, Е.А. Бикритериальная модель сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников, П.В. Мисевич // Системы управления и информационные технологии, №3.2(45), 2011. - С. 255-258.

2. Лазарев, Е.А. Генетические алгоритмы оптимизации сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников, П.В. Мисевич // Системы управления и информационные технологии, №4(46), 2011. - С. 59-63.

3. Лазарев, Е.А. Алгоритм имитации отжига решения задачи оптимизации сети передачи данных [Текст] / Е.А. Лазарев // Системы управления и информационные технологии, №3(49), 2012. - С. 50-53.

4. Лазарев, Е.А. Метод ветвей и границ для оптимизации структуры сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников, П.В. Мисевич // Известия Волгоградского государственного технического университета: актуальные проблемы управления вычислительной техники и информатики в технических системах, № 10(97), выпуск 14, 2012. - С. 189-193.

Свидетельства о государственной регистрации программы для ЭВМ

Свидетельство о государственной регистрации программы для ЭВМ №2012616035. Программный комплекс решения задачи проектирования и оптимизации сети передачи данных / Е.А. Лазарев. - заявл. 10.05.2012; - зарег. 02.07.2012. - Федеральная служба по интеллектуальной собственности, патентам, товарным знакам РФ, Реестр программ для ЭВМ.

Публикации в других изданиях

5. Лазарев, Е.А. Методы оценки эффективности алгоритмов решения многокритериальных задач [Текст] / Е.А. Лазарев // Журнал Средневолжского математического общества. - 2012. - Т. 14. - № 2. - С. 81-86.

6. Лазарев, Е.А. О применении эвристик для метода ветвей и границ решения задачи оптимизации сети передачи данных [Текст] / Е.А. Лазарев // Труды Нижегородского государственного технического университета им. P.E. Алексеева. - Н.Новгород: НГТУ, 2012. -№ 3. - С. 91-96.

7. Лазарев, Е.А. Применение метода ветвей и границ для решения бикритериальной задачи оптимизации сети передачи данных [Текст] / Е.А. Лазарев // Нижегородская сессия молодых ученых. Технические науки.

Материалы докладов (17; 2012). - Нижний Новгород: Зверева И.А., 2012. -С. 96-99.

8. Лазарев, Е.А. Оптимизация на графах с помощью методов глобальной оптимизации [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2010. Материалы XVI международной научно-технической конференции. - Н.Новгород: НГТУ, 2010. - С. 294.

9. Лазарев, Е.А. Бикритериальная модель и алгоритмы синтеза оптимальной сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2011. Материалы XVII международной научно-технической конференции. — Н.Новгород: НГТУ, 2011. -С. 351.

10. Лазарев, Е.А. Об оценке точности решения бикритериальной задачи синтеза оптимальной сети передачи данных эвристическими алгоритмами [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Будущее технической науки. Материалы X международной молодежной научно-технической конференции.

- Н.Новгород: НГТУ, 2011. - С. 64.

11. Лазарев, Е.А. Бикритериальная модель сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2012. Материалы XVIII международной научно-технической конференции. - Н.Новгород: НГТУ, 2012. - С. 313-314.

12. Лазарев, Е.А. Применение метода ветвей и границ для оптимизации структуры сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2012. Материалы XVIII международной научно-технической конференции. - Н.Новгород: НГТУ, 2012.-С. 310-312.

13. Лазарев, Е.А. Средства автоматизации проектирования оптимальной структуры сети передачи данных [Текст] / Е.А. Лазарев, Д.Е. Шапошников // Информационные системы и технологии ИСТ-2012. Материалы XVIII международной научно-технической конференции. — Н.Новгород: НГТУ, 2012. -С. 315.

14. Лазарев, Е.А. Методы ускорения адаптированного алгоритма ветвей и границ решения потоковых задач оптимизации теории графов на примере задачи оптимизации сети передачи данных [Текст] / Е.А. Лазарев // Управление в технических, эргатических, организационных и сетевых системах УТЭОСС-2012. Материалы V Российской мультиконференции по проблемам управления.

- СПб.: ГНЦ РФ ОАО «Концерн «ЦНИИ «Электроприбор», 2012. - С. 12321235.

Подписано в печать 29.04.2013 г. Формат 60x84 1/16. Бумага офсетная. Печать цифровая. Усл. печ. л. 1. Заказ № 420. Тираж 100 экз.

Отпечатано с готового оригинал-макета в РИУ ИНГУ им. Н.И. Лобачевского. 603000, г. Нижний Новгород, ул. Б. Покровская, 37

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

университет им. Р.Е. Алексеева

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

042ОЇ15^852

Лазарев Евгений Александрович

БИКРИТЕРИАЛЬНАЯ МОДЕЛЬ И АЛГОРИТМЫ ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ

ДАННЫХ

05.13.01 - «Системный анализ, управление и обработка информации (в науке и

промышленности)» (технические науки)

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н. Мисевич Павел Валерьевич

Нижний Новгород - 2013 г.

ВВЕДЕНИЕ ............................................................................................................5

ГЛАВА 1.МЕТОДЫ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ

ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ.............................12

§ 1.1 Задачи транспортного типа...................................................................................................12

§ 1.2 Подходы к решению многокритериальных задач............................................................14

§ 1.3 Применение метода ветвей и границ для решения задач оптимизации......................16

§ 1.4 Применение генетических алгоритмов для решения задач оптимизации..................17

§ 1.5 Применение алгоритма имитации отжига для решения задач оптимизации.............19

§ 1.6 Модели и методы оптимизации сетей передачи данных.................................................20

Выводы по главе.................................................................................................................................23

ГЛАВА 2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ, ЗАДАЧА И АЛГОРИТМЫ

ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ.............................24

§ 2.1 Структура сети Интернет......................................................................................................24

§ 2.2 Математическая модель сети передачи данных...............................................................27

§ 2.3 Задача оптимизации сети передачи данных......................................................................29

2.3.1 Постановка задачи...........................................................................................................29

2.3.2 Пример решения задачи..................................................................................................31

§ 2.4 Нахождение множества Парето-оптимальных решений задачи оптимизации сети передачи данных методом полного перебора................................................................................33

2.4.1 Описание метода..............................................................................................................33

2.4.2 Результаты вычислительных экспериментов................................................................33

§ 2.5 Нахождение множества Парето задачи оптимизации сети передачи данных методом ветвей и границ...................................................................................................................................34

2.5.1 Описание метода..............................................................................................................34

2.5.2 Пример решения задачи методом ветвей и границ......................................................37

2.5.3 Результаты вычислительных экспериментов................................................................45

Выводы по главе.................................................................................................................................45

ГЛАВА 3.СИНТЕЗ СУБОПТИМАЛЬНОГО МНОЖЕСТВА РЕШЕНИЙ

ЗАДАЧИ ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ............47

§ 3.1 Представительная выборка..................................................................................................47

§ 3.2 Отыскание субоптимального множества решений..........................................................49

§ 3.3 Методика оценки отклонения субоптимального множества решений от совокупности Парето..........................................................................................................................50

3.3.1 Метод подсчета решений................................................................................................51

3.3.2 Метод усреднения отклонения от точного решения....................................................52

§ 3.4 Нахождение субоптимального множества решений задачи оптимизации сети передачи данных с помощью генетического алгоритма.............................................................53

3.4.1 Описание метода..............................................................................................................53

3.4.2 Дополнительные эвристики............................................................................................58

3.4.3 Пример решения задачи с помощью генетического алгоритма..................................60

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

3.4.5 Результаты вычислительных экспериментов................................................................64

§ 3.5 Нахождение субоптимального множества решений задачи оптимизации сети передачи данных с помощью алгоритм имитации отжига.........................................................66

3.5.1 Описание метода..............................................................................................................66

3.5.2 Дополнительные эвристики............................................................................................69

3.5.3 Результаты вычислительных экспериментов................................................................70

§ 3.6 Использование комбинированных методов.......................................................................72

§ 3.7 Сводные графики результатов вычислительных экспериментов................................73

Выводы по главе.................................................................................................................................76

ГЛАВА 4.ПРОГРАММНЫЙ КОМПЛЕКС РЕШЕНИЯ ЗАДАЧИ

ПРОЕКТИРОВАНИЯ И ОПТИМИЗАЦИИ СЕТИ ПЕРЕДАЧИ ДАННЫХ И РЕКОМЕНДАЦИИ ПО ПРИМЕНЕНИЮ АЛГОРИТМОВ.........................................................................................77

§ 4.1 Назначение и возможности программного комплекса....................................................77

§ 4.2 Описание архитектуры программного комплекса...........................................................78

§ 4.3 Описание графического пользовательского интерфейса................................................79

4.3.1 Основное окно работы программы................................................................................79

4.3.2 Главное меню программы...............................................................................................82

4.3.3 Окно параметров алгоритма...........................................................................................83

§ 4.4 Типовой сценарий работы с программным комплексом................................................83

§ 4.5 Рекомендации по применению алгоритмов.......................................................................84

4.5.1 Использование метода полного перебора.....................................................................84

4.5.2 Использование метода ветвей и границ и комбинированного метода.......................84

4.5.3 Использование генетического алгоритма......................................................................85

4.5.4 Использование алгоритма имитации отжига................................................................86

Выводы по главе.................................................................................................................................86

ЗАКЛЮЧЕНИЕ ..........................................................................................................87

ЛИТЕРАТУРА ..........................................................................................................88

СПИСОК СОКРАЩЕНИЙ.....................................................................................103

ПРИЛОЖЕНИЯ........................................................................................................104

Приложение А. Справка о внедрении результатов диссертационной работы в ООО

«Теком» ........................................................................................................................................105

Приложение Б. Акт о внедрении результатов диссертационной работы в учебный процесс

Нижегородского государственного технического университета им. Р.Е. Алексеева..........106

Приложение В. Свидетельство о государственной регистрации программы для ЭВМ.....108

Приложение Г. Теоремы о NP-трудности и максимальной мощности множества Парето-

оптимальных решений задачи оптимизации сети передачи данных.....................................109

Приложение Д. Архитектура интерактивного программного комплекса............................114

ВВЕДЕНИЕ

Актуальность работы. С развитием сети Интернет, сетей связи и коммуникации люди стали обмениваться все большими объемами информации. Немаловажную роль играет высокая доступность телекоммуникационных услуг. Так, к концу 1995 года в мире насчитывалось всего 26 миллионов пользователей сети Интернет, тогда как к сентябрю 1999 их количество перевалило за 201 миллион, а в 2012 интернет-аудитория составляет более полутора миллиардов человек (около четверти населения земного шара) [124].

По прогнозам компании Cisco объем передаваемых данных в сети Интернет к 2015 году по сравнению с 2011 возрастет в 4 раза, достигнув отметки в тысячу экзабайт в год [123, 124]. Такое значительное увеличение количества передаваемой информации будет оказывать существенную нагрузку на имеющиеся сети передачи данных (СПД). Таким образом, оптимизация существующих и создание новых СПД, способных удовлетворить все растущие требования конечных пользователей, являются крайне важными и актуальными задачами.

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

Проектированию и оптимизации СПД посвящены работы В.М. Гостева, Д. Дэвиса, Ю.П. Зайченко, JI. Клейнрока, С.Е. Ландсберга, A.A. Морозова, М.Х. Прилуцкого, И.А. Соколова, A.A. Стецко, Г.Ф. Янбыха, М. Gerla и М. Averiii. Фундаментальные исследования по компьютерным сетям представлены в работах Д. Бертсекаса, Р. Бесслера, В.И. Вишневского, A.B. Максименкова, В.Г. Олифер и H.A. Олифер, М. Шварца, A.B. Шмалько,

M.G.C. Resende и P.M. Pardalos. Различным методам решения многокритериальных задач оптимизации посвящены работы М.А. Айзермана, Д.И. Батищева, Ю.А. Дубова, Д.И. Когана, В.Д. Ногина, В.В. Подиновского, Ю.С. Федосенко, Д.Е. Шапошникова, Р. Штойера и других.

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

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

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

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

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

проектирования СПД применяются парадигмы объектно-ориентированного программирования.

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

Для достижения поставленной цели решались следующие задачи.

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

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

3. Адаптация различных методов бикритериальной оптимизации для решения задачи пункта 2 и оценка их трудоемкости.

4. Программная реализация предложенных методов.

Научная новизна работы состоит в следующем.

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

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

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

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

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

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

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

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

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

Внедрение. Результаты работы использованы в практической деятельности ООО «Теком» при разработке системы анализа и мониторинга качества услуг широкополосного доступа IRWIn QoS (приложение А), а также внедрены в учебный процесс НГТУ при организации лекционного курса «Моделирование» для студентов и аспирантов кафедр «Вычислительных систем и технологий» и «Компьютерные технологии в проектировании и производстве» (приложение Б).

Апробация работы. Основные результаты диссертации докладывались на конференциях различного уровня.

1. Вторая международная конференция «Second International Conference on Network Analysis», Nizhny Novgorod, 2012.

2. Международные молодежные научно-технические конференции "Информационные системы и технологии", Нижний Новгород, 2010, 2011 (выступление отмечено дипломом), 2012 (выступление отмечено дипломом).

3. Международная молодежная научно-техническая конференция "Будущее технической науки БТН - 2011", Нижний Новгород, 2011.

4. Нижегородская сессия молодых ученых, Нижний Новгород, 2012 (выступление отмечено дипломом).

5. Десятая научная конференция с участием зарубежных ученых «Дифференциальные уравнения и их приложения в математическом моделировании», Саранск, 2012.

Публикации. Материалы диссертации опубликованы в 14 печатных работах, из них четыре статьи в рецензируемых научных журналах списка ВАК [34, 35,41,42].

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад диссертанта в опубликованные работы. Математическая модель сети передачи данных, алгоритмы, основанные на эволюционно-генетическом подходе и методе ветвей и границ, разработаны совместно с соавторами. Решающая процедура, основанная на методе имитации отжига, все дополнительные эвристики и способы оценки субоптимальной совокупности решений предложены соискателем. Программный комплекс решения задачи проектирования и оптимизации сети передачи данных (свидетельство о государственной регистрации программы для ЭВМ в приложении В) и все алгоритмы, представленные в работе, реализованы лично диссертантом. Подготовка публикаций проводилась совместно с соавторами, причем соискателем были лично написаны [39, 40, 41, 43, 44]. Все представленные результаты вычислительных экспериментов получены диссертантом.

В первой главе (Методы решения многокритериальных задач оптимизации сети передачи данных) даются общие сведения о задачах транспортного типа (§1.1), проводится обзор подходов (§1.2) и некоторых алгоритмов (§1.3, §1.4 и §1.5) решения многокритериальных задач, моделей и методов оптимизации сетей передачи данных (§1.6).

Во второй главе (Математическая модель, задача и алгоритмы оптимизации сети передачи данных [31, 32, 34, 36, 37, 39, 42, 44]) рассматривается структура телекоммуникационной сети (§2.1), предлагается математическая модель сети передачи данных (§2.2), формулируется задача оптимизации СПД (§2.3). Для поиска совокупности Парето-оптимальных решений рассматриваемой задачи адаптируется метод ветвей и границ (§2.5). Анализируется его вычислительная сложность. Прив