Иерархические нечеткие многоколониальные муравьиные алгоритмы и комплекс программ оптимизации телекоммуникационных сетей нефтетранспортных предприятий тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Глушко, Сергей Иванович

• Глушко, Сергей Иванович
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Глушко, Сергей Иванович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

1.1 Телекоммуникационная сеть как объект математического моделирования

1.2 Анализ существующих методов оптимизации структуры распределенных телекоммуникационных сетей

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

1.4 Обоснование цели и задач исследования

2 Разработка иерархических многоколониальных муравьиных алгоритмов двухкритериальной оптимизации структуры телекоммуникационных сетей

2.1 Иерархическая мультиколониальная муравьиная модель задачи оптимизации структуры телекоммуникационной сети

2.2 Обобщенный муравьиный алгоритм оптимизации структуры телекоммуникационной сети нефтетранспортного предприятия

2.3 Нечетко-продукционный муравьиный алгоритм оптимизации структуры телекоммуникационной сети

2.4 Эвристический муравьиный алгоритм выбора унифицированной структуры телекоммуникационной сети

2.5 Выводы

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

3.1 Методика имитации поведения муравьев с использованием инструментальной среды МайаЪ

3.2 Имитационное моделирование разработанных муравьиных алгоритмов для

оптимизации структуры телекоммуникационной сети

3.3 Результаты вычислительных экспериментов по оценке эффективности муравьиных алгоритмов

3.4 Выводы

4 Разработка и практическое применение комплекса программ оптимизации телекоммуникационных сетей «СеоКЕБ 1.0»

4.1 Архитектура комплекса программссСеоЛДО 1.0» оптимизации структуры телекоммуникационной сети

4.2 Режимы функционирования и методика применения комплекса программ оптимизации телекоммуникационных сетей

4.3 Результаты применения разработанных алгоритмов и комплекса программ «СеоКЕБ 1.0» для проектирования оптимальной телекоммуникационной сети предприятия ОАО «АК «Транснефть»

4.4 Выводы

ЗАКЛЮЧЕНИЕ

Список сокращений и условных обозначений

Словарь терминов

Список литературы

Приложение А. Логико-информационные модели процедуры управления проектированием и строительством телекоммуникационной сети нефтетранспортного предприятия

Приложение Б. Справка о реализации результатов диссертации на предприятии ОАО «Связьтранснефть»

Введение диссертации (часть автореферата) на тему «Иерархические нечеткие многоколониальные муравьиные алгоритмы и комплекс программ оптимизации телекоммуникационных сетей нефтетранспортных предприятий»

ВВЕДЕНИЕ

Актуальность темы. Магистральные трубопроводы играют важнейшую роль в нефтяной и нефтеперерабатывающей промышленности, являясь основным и наиболее дешевым средством транспортировки нефти и природного газа в цепи поставок добыча - транспортировка - переработка - конечные потребители. С помощью магистральных трубопроводов осуществляется перемещение почти 100% добываемого природного газа, свыше 95% нефти, не менее 50% продуктов нефтепереработки. В общем объеме транспортировки продукции по магистральным трубопроводам доля нефти составляет 40,3%, газа - 55,4%, нефтепродуктов -4,3%. Эффективность транспортировки углеводородов в значительной мере предопределяет промышленную и экологическую безопасность, динамику экономического роста страны, что обуславливает необходимость решения задач контроля и управления магистральными трубопроводами с использованием информационно-телекоммуникационных систем.

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

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

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

Методологические основы решения задач оптимизации сетевой инфраструктуры изложены в работах отечественных ученых: Балашова Е.П., Вишневского В.М., Казеннова Г.Г., Коробова П.Н., Лобанова Ф.И., Марченко A.M., МешалкинаВ.П., Щемелинина В.М., а также зарубежных ученых: Breuer М.А., Burstein M., Chiang С., Cong J., Lien J.C., Pelavin R., Shapiro J.F., Szymanski T.G., Takagi H. В данных работах отмечено, что в настоящее время наиболее перспективными методами оптимизации структуры ТЛКС являются эвристические методы. Преимущество этих методов состоит в возможности решения задач большой размерности с относительно небольшими вычислительными затратами. Теоретические основы разработки эвристических алгоритмов оптимальной трассировки инфраструктурной сети представлены в работах отечественных и зарубежных ученых: Антамошкина А.Н., Баркалова С.А., БронштейнаЕ.М.. БурковаВ.Н., Дайнеко В.Г., МешалкинаВ.П., МудроваВ.И., Образцова A.A., ШнитинаЮ.В., Юсуповой Н.И., DorigoM., Gambardella L.M., Maniezzo V., Neumann К., Paletta G., Schneider W.G., Tarn V. В то же время существующие эвристические методы не позволяют учитывать неопределенность исходной информации при решении задач оптимальной трассировки, а также возможность многокритериальной оптимизации трассы. Для учета неопределенности при решении этих задач целесообразно использовать нечеткие множества для неопределенных значений параметров математических моделей, а также методы нечетко-логического вывода с использованием экспертных оценок.

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

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

Основные разделы диссертационной работы соответствуют Плану фундаментальных исследований Российской академии наук на период до 2025 года (IV. Информатика и информационные технологии по направлениям: п. 33. «Управление крупномасштабными и сетевыми производственными, транспортными, логистическими, энергетическими и другими инфраструктурными системами», п. 35. «Когнитивные системы и технологии, нейроинформатика и биоинформатика, системный анализ, искусственный интеллект, системы распознавания образов, принятие решений при многих критериях», п. 36. «Системы автоматизации, САЬ8-технологии, математические модели и методы исследования сложных управляющих систем и процессов»), а также Перечню критических технологий РФ («Технологии информационных, управляющих, навигационных систем»).

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

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

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

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

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

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

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

4. Предложить нечеткий муравьиный алгоритм выбора оптимальной по стоимости структуры ТЛКС в условиях неопределенности информации.

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

6. Оценить вычислительную эффективность разработанных иерархических многоколониальных муравьиных алгоритмов при решении тестовых задач оптимизации структуры ТЛКС.

7. Разработать научно-обоснованные рекомендации по развитию телекоммуникационной инфраструктуры предприятия ОАО «Связьтранснефть».

Научная новизна. К наиболее существенным научным результатам, полученным лично соискателем, относятся:

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

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

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

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

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

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

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

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

6. Разработан комплекс программ «GeoRES 1.0» оптимизации структуры ТЛКС НТП, реализованный в программных средах Delphi и Matlab, который включает блоки нечетко-логических вычислений и обработки экспертной информации, что позволяет повысить эффективности процессов проектирования и строительства сетей в условиях неопределенности исходной информации.

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

1. Разработанные иерархические нечеткие многоколониальные муравьиные алгоритмы для двухкритериального выбора оптимального маршрута прокладки ТЛКС вносят определенный вклад в развитие теории эвристического поиска решений в условиях неопределенности.

2. Предложенный обобщенный муравьиный алгоритм двухкритериальной оптимальной трассировки ТЛКС может быть практически использован для оптимизации ТЛКС при модернизации и развитии нефтетранспортных предприятий.

3. Разработанный нечетко-продукционный муравьиный алгоритм может быть практически использован для определения оптимального по минимуму общих затрат на трассировку ТЛКС в условиях неопределенности исходных данных на НТП.

4. Предложенный комплекс программ «GeoRES 1.0» может быть использован для решения задач управления развитием телекоммуникационных сетей НТП.

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

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

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

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

3. Модифицированный с использованием процедур нечетко-логического вывода муравьиный алгоритм определения оптимальной структуры ТЛКС.

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

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

6. Архитектура и режимы функционирования комплекса программ «GeoRES 1.0» оптимизации структуры ТЛКС НТП.

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

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на конференциях: VIII Международной научно-практической конференции «Теория и практика современной науки» (Москва, 2012), II Международной научно-практической конференции «Приоритетные научные направления: от теории к практике» (Новосибирск, 2012), III Международной научно-практической конференции «Европейская наука и технологии» (Германия, Мюнхен, 2012), II Международной научно-технической конференции «Энергетика, информатика, инновации-2012» (Смоленск, 2012), IX Международной научно-технической конференции «Информационные техноло-

гии, энергетика и экономика» (Смоленск, 2013).

Объект исследования: телекоммуникационные сети нефтетранспортных предприятий.

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

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

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

Публикации. Основные результаты диссертационной работы отражены в 13 публикациях, в том числе в 7 статьях в изданиях перечня ВАК. Общий объем публикаций составил 12,1 п.л., в том числе лично автору принадлежит 5,5 п.л.

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

1.1 Телекоммуникационная сеть как объект математического моделирования

В соответствии с определением, данным в Федеральном Законе «О связи» (от 07.07.2003 N 126-ФЗ) сеть связи - это технологическая система, включающая в себя средства и линии связи [110].

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

К ТЛКС на сегодняшний день относят[76]: - - телефонные сети общего пользования;

- радиосети;

- телевизионные сети;

- компьютерные вычислительные сети.

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

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

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

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

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

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

Выделенные сети передачи данных характеризуются внутренним номером и не имеют соединений с сетями общего пользования. Технологические сети используются для обработки технологических (или производственных) данных отдельного предприятия, однако могут соединяться с сетями общего пользования. Необходимо заметить, что некоторые исследователи считают, что термины «ведомственная» и «корпоративная» сеть являются синонимами, однако это не совсем корректно. К ведомственным сетям относятся сети российских министерств и ведомств, например, сети министерства транспорта, энергетических компаний, предприятий нефтегазового комплекса и т.д. На сегодняшний день в связи с процессами приватизации большая часть ведомственных сетей реорганизована в акционерные общества, например, ЗАО «Транстелеком», ООО «Газпром связь», ОАО «Связьтранснефть», функционирование которых направлено не только на решение задач обеспечения телекоммуникационной связью министерств, ведомств или предприятий, но и на удовлетворение потребностей в телекоммуникационных услугах на коммерческой основе. В качестве примера можно рассмот-

реть ОАО «РАО ЕЭС». Сеть предприятия не относится к выделенным, поскольку она соединена с сетями общего пользования. Она также не относится и к технологическим, так как включает сегмент, используемый для предоставления услуг доступа к энергетической бирже.

Классификация сетей передачи данных, помимо описанной выше, может осуществляться по различным критериям. Наиболее часто используемыми из них являются [76,13]:

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

- Территориальный масштаб: национальные, региональные и местные сети.

- Иерархические уровни: многоуровневые и одноуровневые структуры сетей.

- Виды электросвязи: сети с одним или несколькими видами электросвязи.

- Технологическая реализация: однородные и комплексные сети.

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

Ниже представлена совокупность показателей для проведения интегральной оценки состояния телекоммуникационной сети [37]:

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

2. Связность и разветвлённость сети передачи данных. Связность сети - это свойство, которое заключается в способности организации связи между любыми узлами. В случае, когда между двумя произвольными узлами установить соединение невозможно, сеть является несвязной. Сеть передачи данных называется односвязной, если соединение возможно между всеми узлами; двусвязной, когда между узлами соединение может быть организовано по двум автономным путям и т.д. На практике сети передачи данных обладают неоднородной связностью, т.е. существуют двусвязные и трехсвязные фрагменты. Разветвлённость сети — это показатель, отражающий количество линий (рёбер) сходящихся к узлам сет».

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

3. Пропускная способность каналов связи - скорость, с которой по данному каналу передается информация. Показатель измеряется в единицах бит в секунду (бит/сек) [13].

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

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

5. Расширяемость сети связи. Под расширяемостью подразумевается возможность быстрого добавления новых элементов сети передачи данных (абонентов, приложений, вычислительной техники, служб), увеличения длин отдельных линий сети и замены аппаратно-технологического обеспечения на более производительное. Важно отметить, что легкость и быстрота расширения сети иногда может быть достигнута только на некоторых ограниченных участках. Так, например, локальная сеть Ethernet, для построения которой используется один сегмент коаксиального кабеля, характеризуется высоким показателем расширяемости и обеспечивает возможность для подключения новых станций, однако их количество ограничено (не более 30-40). Несмотря на то, что сеть физически дает возможность подключить к сегменту до 100 станций, это сильно снизит производительность сети [76].

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

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

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

С математической точки зрения задача проектирования структуры сети связи представляется как поиск минимального значения функции стоимости 8(Ы,Т,Ь) при существовании ограничений на вероятностно-временные и структурные характеристики сети С ¡(И, Т,Ь) и требований принадлежности множества вариантов архитектуры сети М(Ы,Т,Ь) к технически реализуемым решениям [37]:

С^,Т,Ь)<С^ (1.1)

М{И,Т,Ь) е М0,

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

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

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

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

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

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

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

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

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

Наиболее известный метод оптимизации функции одной переменной заключается в нахождении ее производной. Если в точке а производная равна нулю, то в этой точке /(х) имеет минимум или максимум. Максимум достигается при условии, что /"(а) < 0. В противном случае исследуемая функция имеет минимум.

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

Долгое время использование теории графов для оптимизации структуры сети признавалось бесперспективным из-за необходимости анализа большого количества существующих вариантов объединения линий связи. Так, в ТЛКС из 10 узлов насчитывается 245 способов соединения, в том числе тривиальные случаи [37]. С учетом предположения, что анализ каждого существующего варианта занимает не менее 1с (реально эта величина несколько больше, поскольку анализ предполагает проверку показателей надежности, формирование и и распределение потоков), то общее исследование всех вариантов будет закончено через 9-Ю8 лет. Даже для небольших сетей с количеством узлов 6 и 7 необходимо 8,8 и 580,8 часов соответственно.

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

Необходимость разработки алгоритмов комбинаторной оптимизации вызвана следующими причинами [109,89]:

1. Распределенные сети большого масштаба проектируются поэтапно, при этом на первых этапах размерность ТЛКС относительно мала, что дает возможность получить точное решение задачи оптимизации топологической структуры с использованием комбинаторных алгоритмов. Вместе с тем, существующие приближенные алгоритмы обеспечивают точное решение даже для ТЛКС с небольшим количеством узлов. Лучшие эвристические алгоритмы (по оценкам специалистов) имеют погрешность до 10%.

2. Точное решение дает возможность определить качество известных и разрабатываемых эвристических алгоритмов.

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

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

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

1. Модернизация существующей структуры ТЛКС для обеспечения оптимальных параметров надежности.

2. Реконструкция существующих ТЛКС и строительство новых цифровых линий с требуемой пропускной способностью.

3. Развитие ТЛКС в направлениях освоения новых месторождений полезных ископаемых.

При поиске оптимальной структуры ТЛКС необходимо принимать во внимание следующие критерии: совокупная стоимость, степень однородности сети, что обеспечивает высокий уровень стандартизации и существенно облегчает как проектирование ТЛКС, так и их эксплуатацию. Для решения этой задачи поиска оптимальной трассы целесообразно использовать модель ТЛКС в виде графа, отображающего структуру ТЛКС. В этом графе требуется построить маршрут X \{ех,е2,...еп), как совокупность дуг, соединяющих множество вершин, отображающих вычислительные узлы сети V мощностью п, при котором достигается минимум общей стоимости прокладки S(%) и функции неоднородности сети Рг(х), определяемой количеством переходов от одного вида кабеля к другому между смежными узлами сети:

min{5(j),Pr(^)}->/, где X

п'е, _

S(Z) = Z \sqe(!)dl, q= 1 (1.2)

¿=1 о '

П fl, если q{ei) ^ q{e

Pr(z) = X /ОД € X, ГДe/(e,.H л ,ч/ч-1=2 [0, если q{ei) = q(ei_x)

где e, - участок сети, входящий в маршрут х> ~ длина ребра е,; •ч

- стоимость прокладки кабеля типа q, как непрерывная функция на

о

дуге е,; ^ f(ei)~ функция, определяющая количество переходов от одного

вида кабеля на другой на маршруте х> ч(е,) ~ тип кабеля, используемого на ребре е,.

1.2 Анализ существующих методов оптимизации структуры распределенных

телекоммуникационных сетей

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

- задача размещения базовых станций;

- оптимальный синтез топологической структуры телекоммуникационной

сети;

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

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

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

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

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

Будем предполагать, что ТЖС представляется в виде графаЄо(К,£0), где N = \у\ - число вершин, а м = \Е0\ - число ребер Є0.

Выделим остовное дерево С(У,Е) графа Є0, М=\Е\. Введем обозначе-

ния: О(Є) - диаметр графа Є (расстояние между вершинами графа, максимально удаленными друг от друга), О(О-е) - диаметр графа (С-е), построенного удалением из исходного графа Є случайно выбранного ребра, О(Є-у) - диаметр графа (/-V, построенного путем удалением из исходного графа произвольно выбранной вершины. Для каждого ребра графа Є определяются веса, показывающие затраты на аренду линий связи. Стоимость графа Є - это сумма весов всех ребер Є (обозначается (С(Є)). Пусть X— множество всех остовных деревьев графа Єо.

Тогда с математической точки зрения задачу синтеза топологии ТЛКС можно представить следующим образом:

Найти подграф С :

С{С') = тт{С{С)}, (1.3)

Сх€Л

при соблюдении условий:

0{0)<с1„ (1.4)

— е) < с12 для любой е є Е, (1-5)

ИІЄ - х) < с/2 для любой д: є V. (1-6)

Условие (1.4) в соответствии с определением диаметра графа равносильно ограничению на протяженность кратчайшего пути между любой парой вершин. Условия (1.5) и (1.6) накладывают ограничения на длины кратчайших путей между различными парами вершин при удалении в графе С ребра или вершины.

Задача (1.3)-(1.6) является 1чПР-сложной задачей комбинаторной оптимизации, которые исследуются с 18 века (обзор существующих математических методов представлен в [17,20]).

Общая классификация методов решения задачи комбинаторной оптимизации представлена на рисунке 1.1.

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

Рисунок 1.1- Классификация методов решения М>-полных задач комбинаторной

оптимизации

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

следовательного сокращения пространства решений. Впервые данный метод был предложен в 1960 г. Лэнгом и Дойгом, его последующее развитие споряжено с появлением в 1963 г. публикаций Литтла, Кэрел, Суини и Мурти, направленных на анализ возможностей решения задачи коммивояжера. На каждом этапе метода ветвей и границ выявляется факт, включают ли выделенные подмножества оптимальное решение. Если решается задача минимизации, то проверка проводится путем сопоставления нижней граничной оценки величины целевой функции на этом подмножестве с верхней границей функции. В виде верхней оценки применяется величина функции на допустимом решении. Допустимое решение, определяющее минимальную верхнюю оценку, носит название рекорд. Если нижняя оценка функции на подмножестве не меньше верхней оценки, то анализируемое подмножество не включает решения лучше рекорда, и оно отбрасывается. Если полученное значение функции на решении меньше рекордного, то осуществляется замена рекорда. Целесообразно говорить, что подмножество решений проанализировано, если определено, что оно не включает решение, лучшее рекорда [20].

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

С формальной точки зрения данный алгоритм можно представить следующим образом. Пусть поставлена задача минимизации /(х) —» min, где J(x) -

jceD

функция, а D - множество возможных решений. Предположим, что d сD. Функция b(d), которая ставит в соответствие произвольному множеству d разделение его на подмножества d^, ..., d^ N> 1, называется ветвлением. Вещественная функция H(d) - нижняя граница для d в случае, если:

1) #(</)< min Дх);

xed

2) на множестве из одного элемента {х} верно равенство H({x})=f(x).

Алгоритм, который реализует метод ветвей и границ, включает последовательность типовых шагов. На каждом этапе известно значение рекорда х° подмножества /, ... , ^ непроанализированных решений. Перед началом работы

алгоритма Ь — 1, £ = Д х° - любой элемент множества Б или пустое множество

(при пустом множестве значение функционала равно бесконечности).

На каждом этапе алгоритм проверяет базу элементов разбиения. Предложим, что проверяется множество //.Оно отсекается в одном из двух последовательно проверяемых случаев [33]:

а) если Я(д>/(х°);

б) если //(/ )</(Xй) и найден такой элемент};,^,, что /(у ) = шш/(х) =

■' } ЛГе^

В случае б) происходит смена рекорда х° = у .

Пусть £ /2,... , (М < Ь) - неотсеченные множества (будем считать, что отсечены множества с номерами М+1, ...,Ь).

В случае М= 0 алгоритм заканчивает работу, и в качестве решения задачи принимается рекорд х°. При М>1 среди множеств выбирается множество

для нового ветвления. Пусть таковым является множество * . Тогда осуществляется ветвление ЬУ ) = (с1, ..., с1 ), в результате которого получаем список множеств с1, ..., /2, ... , ^ Эти множества нумеруются числами от 1 до Ь, и начинается

новый шаг алгоритма.

Увеличение размерности задачи комбинаторной оптимизации приводит к нерациональности использования методов поиска точных решений из-за существенных временных затрат. Однако на практике, как правило, на предпроектной стадии создания ТЛКС, требуется оценить нижнее значение стоимости проектируемой сети, для чего в [37] предложен следующий алгоритм.

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

(1еЕ(уеК(С))>2, (1.7)

где с1е§(у е У(С)) - количество рёбер графа О, инцидентных вершине х.

Кроме того вводится новое условие, состоящие в том, что сеть содержит М ребер:

V — 2М.

(1.8)

уеК(О)

Таким образом, необходимо решить следующую задачу. Найти С(С) = шт{С(С)), если У deg V = 2М и е > 2.

(1.9)

У€К(0

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

Шаг 1. Ранжирование строк матрицы С . Строки матрицы располагаются в

порядке увеличения стоимостей. Тогда, для каждого значения / в /-й строке

С

хранятся затраты на соединение /-ого узла с остальными узлами по возрастанию (4=00).

Шаг 2. Для всех строк С отобрать первых два элемента:

N 2

с;=12Х-

,=1 7=1

с„

(1.10)

разместить по возрастанию их

Шаг 3. Оставшиеся N -2Ы элементов

стоимостей, т.е. из всех остальных ее элементов создать вектор С = {Сг} :С <С; при /</.

2М-2N _

Шаг 4. Взять первые 2-2Ы элементов вектора С, то есть С*2 - ^Г Сг.

г=1

Шаг 5. Рассчитать минимальную оценочную стоимость сети с М ребрами: С*(С* + С%2) / 2 (оценка делится на 2, т.к. полученное решение содержит 2Мребер, а не М, как должно быть).

Шаг 6. Завершение функционирования алгоритма.

Целесообразно отметить, что трудоемкость описанного алгоритма определяется выполнением шагов 1 (или 3) и рассчитывается как 0( N2 log N). Количество ребер М неизвестно. Поэтому для расчета нижней оценки стоимости сети необходимо определить границу числа ребер, при которой выполняются условия (1.3)—(1.6).

Таким образом, для просмотра и анализа множества возможных решений разработан алгоритм, который включает следующие этапы. На первом этапе оценивается нижняя граница коилчества ребер Mmin. Для определенного числа узлов N и ребер M=Mmin определяются все возможные двусвязанные графы, удовлетворяющие условиям (1.3)-(1.6). Из таких графов находится G' с минимальной суммой весов. Если в процессе анализа определено, что на графе получено значение, равное нижней оценочной стоимости для М ребер, тогда поиск оптимального решения останавливается. Если все возможные графы с М ребрами просмотрены, то количество ребер М увеличивается на 1; рассчитывается нижняя оценка стоимости, и если она не лучше текущего оптимального решения с меньшим количеством ребер, то работа алгоритма останавливается. В ином случае анализируются все графы с М+1 ребрами и т.д.

Машинные эксперименты синтеза топологии ТЛКС с количеством узлом, не превышающим 10, выявили важную особенности представленного комбинаторного алгоритма: на поиск оптимального решения затрачивается не более 5% от совокупного количества итераций. Остальные итерации направлены на доказательство оптимальности полученного решения. С учетом данной особенности на основе комбинаторного подхода существуют эвристические алгоритмы для синтеза структуры ТЛКС средней и большой размерности [88].

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

ного поиска являются наиболее наглядными. Основы реализации данных методов относятся к концу 50-х, началу 60-х годов двадцатого столетия и сопряжены в основном с решением задачи коммивояжера. В дальнейшем данные идеи применялись и для решения задач размещения, построения сетей, расписаний и др. Алгоритм локального спуска запускается с некоторого исходного решения /0, выбранного произвольным образом или с использованием какого-нибудь вспомогательного алгоритма [94]. На каждом этапе локального спуска осуществляется переход от текущего решения к соседнему с меньшим значением целевой функции до тех пор, пока не будет достигнут локальный оптимум.

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

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

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

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

Алгоритм имитации отжига. Название этого алгоритма сопряжено с использованием методов имитационного моделирования, основанных на методе Монте-Карло. Обследование кристаллической решетки и анализ поведения атомов при медленном охлаждении тела явилось причиной зарождения вероятностных алгоритмов, которые стали высоко эффективными в комбинаторной оптимизации. В настоящее время данный алгоритм является очень популярным как для решения практических задач, так и теоретических. Благодаря простоте, гибкости и эффективности алгоритма обеспечивается возможность исследования его свойства и сходимости [25]. Алгоритм имитации отжига является элементом класса пороговых алгоритмов локального поиска. На каждом этапе данного алгоритма для текущего решения ik в некоторой его окрестности Nfiif) осуществляется выбор решения j и, если разность между новым и текущим решением в расчете по целевой функции не больше порога tk, то новое решение j замещает текущее. В противоположном случае осуществляется выбор соседнего решения.

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

Основным механизмом, позволяющим алгоритму выбираться из локального оптимума, является список запретов Tabu(ik). Он строится по предыстории поиска, то есть по нескольким предшествующим решениям 4, ik-i+i, и запрещает часть окрестности текущего решения N(ik). На каждом шаге очередная точка ik+1 является оптимальным решением подзадачи: /(/i+1) = min{/(j)\j е N(ik)}. Список

запретов учитывает специфику задачи и, как правило, запрещает использование тех «фрагментов» решения (ребер графа, координат вектора, цвета вершин), которые менялись на последних / шагах алгоритма.

Генетические алгоритмы - популяционный подход к решению поисковой задачи [85]. Они образуют классы алгоритмов, основанные на математическом

моделировании биологических механизмов и природных процессов с помощью принципов популяционной генетики, которые позволяют находить оптимальные или близкие к ним (субоптимальные) решения. Генетические алгоритмы основаны на компьютерном моделировании эволюции особей. Каждый особь характеризуется своей хромосомой Бк, хромосома есть «геном» особи. Хромосома определяет приспособленность особи /(ЗУ; к =1,...,п; п - численность популяции. Хромосома есть цепочка символов 5^,...И- длина цепочки. Символы

интерпретируются как «гены» особи, расположенные в хромосоме .

Обобщенно генетический алгоритм можно представить как следующую последовательность этапов [93]:

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

2. Производится оценка особей в поколении по определённым критериям.

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

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

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

- определение глобального или субоптимального решения;

- превышение заранее определенного количества поколений;

- превышение временного интервала, заданного для эволюции.

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

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

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

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

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

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

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

Главное отличие алгоритма поиска дерева Штейнера от алгоритма Прима заключается в том, что добавление вершин к текущему решению осуществляется

во вспомогательных точках.

На основе анализа свойств вершин Штейнера и требований к проектированию телекоммуникационной сети в диссертации [54] был предложен модифицированный алгоритм покоординатного спуска, который предусматривает использование только тех вспомогательных вершин, которые повышают эффективность получаемого дерева Штейнера. Это позволяет получить неполное дерево Штейнера, тогда как в традиционном алгоритме всегда определяется полное дерево Штейнера, не всегда улучшающее ЯЗТ.

В работе [24] предложена методика проектирования рациональной топологической структуры беспроводных сенсорных сетей (БСС), в основе которой лежит использование игровой модели. Игроками в контексте поставленной задачи являются конечные устройства, которые конкурируют за доступ к каналу в процессе передачи их сообщений к общему шлюзу за счет ограниченного ресурса -ретрансляционной сети.

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

В [86] предложен редукционный топологическо-эвристический алгоритм (РТЭ-алгоритм) оптимальной трассировки 3-хмерных разветвленных сетей технологических трубопроводов, который отличается применением процедур построения топологической структуры пространства как деревьев Штейнера с использо-

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

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

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

Решению задачи поиска оптимальной топологии сети также посвящены работы [51, 67, 103, 73] и многие другие.

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

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

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

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

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

В 40-50-е гг. XX в., французский зоолог Пьер-Поль Грассе заметил, что некоторые виды термитов реагируют на так называемые «значимые стимулы». Он отметил, что эффекты от этих реакций могут выступать в качестве новых значимых стимулов как для насекомых, которые вырабатывают эти реакции, так и для

остальных насекомых в колонии. Грассе использовал специальный термин «стигмерджи», (англ -'Б^те^у'), то есть «работающий знак». Основные характеристики «стигмерджи», которые отличают его от других форм коммуникации включают [113]:

1. «Стигмерджи» является косвенным способом коммуникации посредством изменения состояния окружающей среды.

2. «Стигмерджи» информация является локальной: она доступна только для насекомых, которые находятся на соответствующей ей траектории (или в её ближайшем окружении).

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

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

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

Наиболее широкое применение муравьиные алгоритмы получили для решения задачи коммивояжера [73]. В контексте данной задачи задается набор городов и расстояние между ними (каждый с каждым). Цель состоит в отыскании кратчайшего маршрута, при этом каждый город должен быть посещен только один раз. С формальной точки зрения, цель состоит в нахождении гамильтонова пути минимальной длины полностью связного графа [114]. С использованием МА проблема решается моделированием ряда искусственных муравьев, перемещающихся на графе, при этом каждая вершина представляет собой город, каждая дуга - связь между двумя городами. Каждая дуга характеризуется определенным количеством феромона, которое может быть проанализировано и изменено всеми муравьями колонии.

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

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

- отсутствие централизованного контроля;

- косвенный обмен информацией с помощью феромона;

- испарение феромона с течением времени, обеспечивающее адаптивность поведения.

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

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

2. Поиск решений. Расчет вероятности перемещения муравья из вершины / в ] осуществляется по формуле:

Ту ат (.-¿-У

р9«)=-' 0-11)

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Глушко, Сергей Иванович

4.4 Выводы

Предложенные алгоритмы оптимизации трассы кабельной ТЛКС были практически реализованы в виде комплекса программ «СеоКЕЗ 1.0», используемом для управления телекоммуникационной инфраструктурой. Данный комплекс позволяет увеличить скорость процессов планирования структуры ТЛКС, рассчитывать точную стоимость их строительства с использованием геоинформационных систем и электронных картографических данных.

Разработанные алгоритмы практически использованы для создания научно-обоснованных рекомендаций по проектированию и строительству телекоммуникационной инфраструктуры ОАО «АК «Транснефть». Особое внимание компания «Транснефть» уделяет реализации Программы по проектированию и строительству транспортной сети высокоскоростных каналов связи для создания единой информационной системы (ЕИС) ОАО «АК «Транснефть», позволяющей объединить информационные системы всех организаций «Транснефть» в единое информационное пространство. Важным этапом построения высокоскоростной Единой Информационной Системы ОАО «АК «Транснефть» является строительство в 2015-2018 гг. волоконно-оптической линии связи на участке Ухта - Ярославль, общей протяженностью 1195 км. В рамках данного проекта планируется объединить 25 узлов связи.

С использованием комплекса программ «ОеоЯЕБ 1.0» спроектирована оптимальная структура ТЛКС. Полученная структура сети (см. рисунок 3) является однородной, поскольку для её построения использовался один вид кабеля - волоконно-оптический. Общая стоимость реализации проекта по трассе составила 1,195 млрд. руб. Использование разработанных иерархических многоколониальных алгоритмов муравьиных колоний выбора оптимальной трассы телекоммуникационной сети позволило сократить затраты материальных, трудовых, финансовых, временных ресурсов на реализацию проекта, что подтверждается сопоставлением с данными исходной сметной документации. Первоначальный план предусматривал объем инвестиций в размере 1,221 млрд. руб.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

6. Разработаны архитектура и режимы функционирования комплекса программ «веоЮ^ 1.0» оптимизации структуры ТЛКС нефтетранспортного предприятия.

7. Предложены научно-обоснованные рекомендации по оптимизации ТЛКС предприятия ОАО «Связьтранснефть».

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

Список сокращений и условных обозначений

БД - база данных

АК - акционерная компания

БЗ - база знаний

ГА - генетический алгоритм

ЕИС - единая информационная система

ЛПР - лицо, принимающее решение

ММОД - минимальное маркированное остовное дерево

МОД - минимальное остовное дерево

МО ДОС - минимальное остовного дерева с ограниченными степенями

НТП - нефтетранспортное предприятие

1111 - продукционное правило

СУБД - система управления базами данных

ТЛКС - телекоммуникационная сеть

ЭВМ - электронно-вычислительная машина

МР-задача - задача с нелинейной полиномиальной оценкой числа итераций

Словарь терминов база знаний: Систематизированная структурированная совокупность смысловых знаний, включающая смысловую и фактическую информацию, а также правила вывода, допускающие автоматические умозаключения о вновь вводимых фактах и, как следствие, осмысленную обработку знаний. взвешенный граф: Граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра). вычислительная сложность алгоритма: Функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. граф: Совокупность непустого множества вершин и связей между ними. дерево: Связный ациклический граф. диаметр графа: Максимальное из расстояний между парами его вершин. Расстояние между вершинами определяется как наименьшее число рёбер, которые необходимо пройти, чтобы добраться из одной вершины в другую. Иначе говоря, это расстояние между двумя вершинами графа, максимально удаленными друг от друга. длина дерева: Суммарный вес входящих в дерево рёбер, каждому из которых приписан вес в виде длины или стоимости. задача коммивояжёра: Задача комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. имитационное моделирование: Метод исследования, при котором изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему, с которой проводятся эксперименты с целью получения информации об этой системе. информационно-телекоммуникационная сеть: Технологическая система, предназначенная для передачи по линиям связи информации, доступ к которой осуществляется с использованием средств вычислительной техники. инцидентность: Понятие, используемое только в отношении ребра и вершины: если — вершины, а е=(\1,\2) — соединяющее их ребро, тогда вершина V/ и ребро е инцидентны, вершина \2 и ребро г тоже инцидентны. компонента связности графа: Некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества. математическая модель: Приближённое описание какого-либо класса явлений внешнего мира, выраженное с помощью математической символики. минимальное дерево Штейнера: Кратчайшая сеть, соединяющая заданный набор точек в метрическом пространстве. Главное отличие от минимального остовного дерева заключается в том, что для нахождения дерева Штейнера разрешается добавлять дополнительные точки ветвления с целью большего сокращения суммы длин рёбер. минимальное остовное дерево (минимальное покрывающее дерево): В связанном, взвешенном, неориентированном графе остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него ребер. минимальное остовное дерево с ограниченными степенями: Минимальное остовное дерево в заданном связанном, неориентированном графе О такое, что ни одна из его вершин не может иметь степень больше, чем некоторое заданное число оI. муравьиный алгоритм: Эвристический алгоритм оптимизации, основанный на имитации поведения муравьиной колонии; один из эффективных полиномиальных эвристических алгоритмов для нахождения приближенных решений задачи коммивояжера, а также аналогичных задач поиска маршрутов на графах. нечеткая логика: Раздел математики, являющийся обобщением классической логики и теории множеств, базирующее на понятии нечёткого множества, впервые введённого Лотфи Заде в 1965 году, как объекта с функцией принадлежности элемента к множеству, принимающей любые значения в интервале [0,1], а не только 0 или 1. нечеткие числа (Ь-И)-типа: Разновидность нечетких чисел специального вида, функции принадлежности которых задаются с помощью невозрастающих на множестве неотрицательных действительных чисел функций действительного переменного. нечетко-продукционный муравьиный алгоритм оптимизации структуры телекоммуникационной сети: Муравьиный алгоритм оптимизации структуры телекоммуникационной сети по критерию стоимости проектирования сети, в основе которого лежит использование базы знаний экспертов в виде нечетких продукционных правил и процедуры нечетко-логического вывода для расчета возможности перемещения муравьев между вершинами графа. обобщающий муравьиный алгоритм оптимальной трассировки телекоммуникационной сети: Двухкритериальный алгоритм оптимизации структуры телекоммуникационной сети по параметрам стоимости и унифицированности сети, основанный на использовании муравьиной колонии, перемещение которой определяется количеством феромона (лингвистической переменной с нечеткими множествами (Х-/?)-типа), определяемого с помощью операций свертки количества феромонов муравьев колоний, осуществляющих поиск решений по отдельным критериям. оптимизационная задача: Экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. остовное дерево: Ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины. подграф исходного графа: Граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. продукционная база знания: Модель знаний, основанная на правилах, позволяет представить знание в виде предложений типа «Если (условие), то (действие)». сетевая топология: Способ описания конфигурации сети, схема расположения и соединения сетевых устройств. степень вершины дс графа <7: Количество рёбер графа О, инцидентных вершине х. трассировка: Процедура получения информации о маршрутизаторах (узлах) сети, через которые проходит трафик на пути к месту назначения. функция принадлежности нечёткого множества: Обобщение индикаторной (или характеристической) функции классического множества. В нечёткой логике она представляет степень принадлежности каждого члена пространства рассуждения к данному нечёткому множеству. целевая функция: Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации. эвристический алгоритм: Алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. эвристический муравьиный алгоритм выбора унифицированной структуры телекоммуникационной сети: Муравьиный алгоритм поиска максимально однородной унифицированной структуры телекоммуникационной сети, основанный на поиске минимального маркированного остовного дерева с ограниченными степенями на графе с использованием обособленных феромонных троп для каждой трассы, а также модифицированной процедуры определения возможности перехода муравьев между вершинами графа как функции от количества связанных компонент графа.

Список литературы диссертационного исследования кандидат технических наук Глушко, Сергей Иванович, 2013 год

Список литературы

1. Colorni, A. Distributed Optimization by Ant Colonies / A. Colorni, M. Dori-go and V. Maniezzo // Proceedings of the First European Conference on Artificial Life, F.J. Varela and P. Bourgine (Eds.), MIT Press, Cambridge, MA, 1992. pp. 134-142.

2. Das, S. An Ant Colony Approach for the Steiner Tree Problem / S. Das, S.V. Gosavi, W.H. Hsu, S.A. Vaze // In Proc. of Genetic and Evolutionary Computing Conference, New York City, 2002.

3. Dli M.I., Glushko S.I., Ivanova I.V. Ant algorithms as a tool of infrastructure project management // European Science and Technology: materials of the III research and practice conference. Publishing office Vela Verlag Waldkraiburg. Munich. Germany. 2012. 127-129 p.

4. Dorigo, M. Ant Colony Systems: A Cooperative Learning Approach to the Traveling Salesman Problem / M. Dorigo, L.M. Gambardella // IEEE Transactions on Evolutionary Computation, 1(1), 1997. — pp.53-66.

5. Dorigo, M. The Ant System: Optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, Vol.26, No.l, 1996, pp.29-41.

6. G. R. Raidl and B. A. Julstrom, "A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem," in Proceedings of the ACM Symposium on Applied Computing, 2000, pp. 440-445.

7. G. R. Raidl, "An efficient evolutionary algorithm for the degree-constrained minimum spanning tree problem," IEEE Transactions on Evolutionary Computation, Vol. 1,2000, pp. 104-111.

8. G. Zhou and M. Gen, "Approach to the degree-constrained minimum spanning tree problem using genetic algorithm," Engineering Design and Automation, Vol. 3, 1997, pp. 228-231.

9. G. Zhou, M. Gen, and T. Wu, "A new approach to the degree-constrained

minimum spanning tree problem using genetic algorithm," in Proceedings of the International Conference on System, Man, and Cybernetics, Vol. 4, 1996, pp. 2683- 2688.

10. Hanan, M. On Steiner's problem with rectilinear distance / M. Hanan // SIAM Journal of applied mathematics, №14(2). 1966. — pp.255-265.

11. J. Knowles and D. Corne, "A new evolutionary approach to the degree-constrained minimum spanning tree problem," IEEE Transactions on Evolutionary Computation, Vol. 4, 2000, pp. 125-134.

12. M. Krishnamoorthy, A. T. Ernst, and Y. M. Sharaiha, "Comparison of algorithms for the degree constrained minimum spanning tree," Journal of Heuristics, Vol. 7, 2001, pp. 587-611.

13.Maitzman, R. Design for Networks - The Ultimate Design for X. / K.M. Rembis, M. Donisi, M. Farley, R.C. Sanchez, A.Y. Ho // Bell Labs Technical Journal. - Vol. 9, Number 4, 2005.

14. N. Deo and S. L. Hakimi, "The shortest generalized Hamiltonian tree," in Proceeding of the 6th Annual Allerton Conference, 1968, pp. 879-888.

15.R.-S. Chang and S.-J. Leu. The minimum labeling spanning trees. Information Processing Letters, 63(5):277-282, 1997.

16. S. M. Soak, D. Corne, and B. H. Ahn, "A new encoding for the degree constrained minimum spanning tree problem," Lecture Notes Artificial Intelligence, Vol. 3213, 2004, pp. 952-958.

17. Schrijver A. On the history of combinatorial optimization (till 1960) / A. Schrijver, In K. Aardal, G.L. Nemhauser, R. Weismantel. // Elsevie: Amsterdam, 2005.-p. 1-68.

18. Szykman, S. Constrained Three Dimensional Component Layout Using Simulated Annealing / S. Szykman, J.Cagan // ASME Journal of Mechanical Design. Vol.119, No. 1, 1997. —P.28-35.

19. T. N. Bui and C. M. Zrncic, "An ant-based algorithm for finding degree-constrained minimum spanning tree," in Proceedings of the 8th Annual Conference on

Genetic and Evolutionary Computation, 2006, pp. 11-18.

20. Weise T. Global optimization algorithms: Theory and application, 2008.

21. Y. T. Bau, С. К. Ho, and H. T. Ewe, "An ant colony optimization approach to the degree-constrained minimum spanning tree problem," Lecture Notes Artificial Intelligence, Vol. 3801, 2005, pp. 657-662.

22. Yu Hu, Tong Jing, Xianlong Hong, Zhe Feng, Xiaodong Hu, Guiying Yan. An Efficient Rectilinear Steiner Minimum Tree Algorithm Based on Ant Colony Optimization. In Proc. of International Conference on Communications, Circuits and Systems 2004 (IEEE ICCCAS'04), Chengdu, China. — pp. 1276-1280.

23. Yu Hu. ACO-Steiner: Ant Colony Optimization Based Rectilinear Steiner Minimal Tree Algorithm / Yu Hu, Tong Jing, Xian-Long Hong, Zhe Feng, Xiao-Dong Hu, and Gui-Ying Yan // Journal of Computer Science & Technology. - 2006, 21(1), pp. 147-152.

24. Акимов, E.B. Проектирование рациональной топологии беспроводных сенсорных сетей: автореф. дисс. на соискание ученой степени канд. техн. наук / Акимов Евгений Вячеславович. - М., 2010. - 22 с.

25. Алгоритм имитации отжига [Электронный ресурс]. - Режим доступа: http://www.math.nsc.ru/AP/benchmarks/UFLP/uflp_sa.html

26. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях. — Тюмень: Изд-во «ТГУ», 2000

27. Ануфриев, И.Е. MATLAB 7.0 / И.Е. Ануфриев, А.Б. Смирнов, Е.Н. Смирнова. - СПб.: БХВ-Петербург, 2005. - 1104 с.

28. Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. — 288 с.

29. Атанов, С.К. Системы управления на нечеткой логике / С.К. Атанов // Вестник КГУ. - Казахстан, Костанай: КГУ им. А. Байтурсынова. - 2008. - №2. -С. 15-21.

30. Береснев В.JI. Алгоритм неявного перебора для задачи типа размещения и стандартизации. Управляемые системы. Вып. 12 (1974). Новосибирск, Институт математики Сиб.отд. АН СССР, С. 24-34.

31. Борисов, А.Н. Принятие решений на основе нечетких моделей / А.Н. Борисов, O.A. Крумберг, И.П. Федоров. - Рига: Зинанте, 1990. - 184 с.

32. Борисов, В.В. Нечеткие модели и сети / В.В. Борисов, В.В. Круглов, A.C. Федулов - М.: Горячая линия - Телеком, 2007. - 283 с.

33. Борознов, В.О. Исследование задачи коммивояжера / В.О. Борознов // Вестник АГТУ. - Серия: управление, вычислительная техника и информатика. -2009. -№2.-С.174-151.

34. Бугров Д.А. Постановка задачи структурной оптимизации магистральной корпоративной телекоммуникационной сети // Информация и Космос. — 2005. -№ 2. -С. 42-47.

35. Валеева, А.Ф. Применение конструктивных эвристик в задачах раскроя-упаковки / А.Ф. Валеева // Приложение к журналу «Информационные технологии» №11, 2006 г

36. Васильев, А.Н. Matlab. Самоучитель. Практический подход /

A.Н. Васильев. - М.: 2012. - 448 с.

37. Вишневский, В.М.. Теоретические основы проектирования компьютерных сетей/ В.М. Вишневский // Москва: Техносфера, 2003. - 254 с.

38. Галямов В.А. О задаче оптимизации построения первичной сети свя-зи.//Труды ИВМ и МГ. Сер. Информатика. Новосибирск, 2005. -№5. — С. 68-79.

39. Гладков, Л.А. Генетические алгоритмы. / Л.А Гладков, В.М. Курейчик,

B.В. Курейчик. - Ростов-на-Дону: ООО «Ростиздат», 2004.

40. Гливка, А.Г. Разработка моделей и программных средств для оптимизации оперативного планирования производства в машиностроении [Электронные данные] / А.Г. Гливка // Донецкий национальный технический университет. -2009. - Режим доступа: http://www.masters.donntu.edu.ua/2009/kita/glivka/

diss/index.htm#g

41.Глушко С.И. Многоколониальные алгоритмы муравьиных колоний для решения двухкритериальной задачи выбора маршрута // Информационные технологии, энергетика и экономика: Сб.тр. X Междунар. Науч.-техн. конф. Т. 2. Смоленск: Универсум, 2013. С.25-28.

42. Глушко С.И., Бояринов Ю.Г. Полумарковские модели систем с нечеткими параметрами // Программные продукты и системы. 2012. №2 (98). С. 146-149.

43. Глушко С.И., Гимаров В.В., Образцов A.A. Алгоритм учета неопределенности численных характеристик инфраструктурного проекта // Сб.тр. Междунар. Науч.-техн. конф. Т. 2. Смоленск: Универсум, 2012. С.14-17

44. Глушко С.И., Заенчковский А.Э., Жилкин И.А. Интеллектуальный метод выбора оптимального маршрута формирования инфраструктуры предприятия // Сборник материалов VIII Международной научной конференции «Теория и практика современной науки». Москва, 2012. С.221-225.

45. Глушко С.И., Иванова И.В. Нечеткие муравьиные алгоритмы планирования оптимального маршрута прокладки трубопроводного транспорта // Электронный научный журнал «Нефтегазовое дело». 2012. №6. С. 120-125.

46. Глушко С.И., Какатунова Т.В. Нечеткая модификация алгоритма муравьиных колоний // Научное обозрение. 2013. №1. С.377-381.

47. Глушко С.И., Образцов A.A., Кузавко A.C. Применение алгоритма муравьиных колоний для решения задач оптимизации на графе // Приоритетные научные направления: от теории к практике: Сб. тр. II Межд. научно-практ. конф. -Новосибирск, 2012. С.67-71.

48. Гончаров E.H., Кочетов Ю.А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер.2, т.6 (1999). — №1. — С. 12-32.

49. Гончаров E.H. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий // Дискретный анализ и исследование операций,

Серия 2, 1998, том 5, N1. С. 19-39.

50. Грешилов, A.A. Прикладные задачи математического программирования: учебное пособие / A.A. Грешилов. — М.: Логос. — 2006. — 288 с.

51. Демин А.Ю. Комбинированный метод решения линейных задач целочисленного программирования и его применение для оптимизации топологии локальных вычислительных сетей: автореф. дисс. на соискание ученой степени канд. техн. наук 05.13.18 / Демин Александр Юрьевич - М. 2002. - 20 с.

52. Дли М.И., Гимаров В.В., Глушко С.И. Конфигурирование информационных и транспортных сетей в условиях неопределенности // Прикладная информатика. 2012. № 6(42). С. 81-86.

53. Дли М.И., Гимаров В.В., Глушко С.И. Применение алгоритмов муравьиных колоний при управлении сложными проектами // Транспортное дело России. 2012. №4. С. 51-54.

54. Забержинский, Б.Э. Системный анализ и теоретико-графовые модели оптимизации региональных газораспределительных сетей: автореф. на соискание ученой степени канд. техн. наук: 05.13.18 / Забержинский Борислав Эдуардович. -Самара. 2007. - 20 с.

55. Заде Л. Понятие лингвистической переменной и ее применение к принятию приближенных решений. М.: Мир, 1976.

56. Заозерская Л.А., Китриноу Е., Колоколов Задача оптимального размещения центров телекоммуникаций в регионе // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск, Байкал, 2005. Т.1.-С. 469-476.

57. Иглин, С.П. Математические расчеты на базе MATLAB / С.П. Иглин. -СПб.: БХВ-Петербург, 2005. - 640 с.

58. Имитационное моделирование [Электронный ресурс]. - Режим доступа: http://www.simulation.ru/consulting/what_is_simulation/

59. Использование имитационного моделирования [Электронный ресурс] //

AnyLogic: Многоподходное имитационное моделирование. - СПб. - Режим доступа: http://www.anylogic.ru/use-of-simulation

60. Ищенко, С. Н. Разработка и исследование генетических алгоритмов решения задач компоновки элементов и трассировки СБИС: дис. канд. техн. наук: 05.13.12, Ростов-на-Дону, 2006

61.Кажаров, A.A. Об одном «муравьином» алгоритме. / A.A. Кажаров , В.М. Курейчик // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2008: Труды конференции. В 3-х т. Т. 3. - М.: ЛЕНАНД, 2008. - С. 315-325.

62. Кафаров, В.В. Проектирование и расчет оптимальных систем технологических трубопроводов / В.П. Мешалкин, В.В. Кафаров. — М.: Химия, 1991. — 279 с.

63. Кофман А. Введение в прикладную комбинаторику. М.: Наука, Гл. ред. физ.-мат. лит. 1975. 447 с.

64. Кочетов, Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации / Ю.А. Кочетов // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям. М: МГУ, 2001. — С. 87-117.

65. Кочетов, Ю.А. Вероятностный поиск с запретами для задач упаковки в контейнеры / Ю.А. Кочетов, А.Р. Усманова // Труды Байкальской международной конференции, Иркутск, 2001, т. 6. — С. 22-26.

66. Кочетов, Ю.А. Методы локального поиска для дискретных задач размещения: дисс. на соискание ученой степени д-ра. физ.-мат. наук // Кочетов Юрий Андреевич. - Новосибирск, 2009. - 267 с.

67. Краснов, С.В.. Автоматизированное проектирование вычислительных сетей промышленных предприятий в условиях нечетко заданного трафика: авто-реф. дисс. на соискание ученой степени канд. техн. наук / Краснов Сергей Васильевич - Ульяновск, 2001. - 19 с.

68. Кривоносов Д.М.. Системный анализ и синтез топологической структуры проводных сетей передачи данных: автореф. дисс. на соискание ученой степени канд. техн. наук 05.13.01 / Кривоносов Дмитрий Михайлович. - Волгоград. 2004. - 19 с.

69. Круглов В.В. Нечеткая игровая модель с единичным экспериментом //Нейрокомпьютеры: разработка и применение. 2003. № 8-9. С. 24-28.

70. Круглов В.В. Нечеткие игровые модели и их применение в задачах принятия решений, классификации и прогнозирования // Вестник МЭИ. 2004. № 1. С. 82-85.

71. Курейчик, В.В. Генетические алгоритмы / JI.A Гладков, В.В. Курейчик, В.М. Курейчик; под ред. В.М.Курейчика. - 2-е изд., испр. и доп. - М.: Физматлит, 2006. - 320 с.

72. Курейчик, В.М. Комбинаторные аппаратные модели и алгоритмы в САПР / В.М. Курейчик, В.М. Глушань, Л.И. Щербаков. — М.: Радио и связь, 1990

73. Курочкин, И.И. Разработка и анализ методов последовательной прокладки путей в сетях передачи данных: дисс. на соискание ученой степени канд. техн. наук / Курочкин Илья Ильич. - М., 2010. - 25с.

74. Лебедев, Б.К. Разработка теории и принципов поисковой адаптации для решения оптимизационных задач топологического синтеза: автореф. дисс. на соискание ученой степени канд. техн. наук. // Лебедев Борис Константинович. - Таганрог., 2001.-40 с.

75. Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане // Автоматика и телемеханика. 2004. №3. С. 80-89.

76. Лекция 8. Конвергенция компьютерных и телекоммуникационных сетей [Электронный ресурс]. — Режим доступа: http://wiki.auditoiy.ru/JIeK4M_8._ Конвергенция_компьютерных_и_телекоммуникационных_сетей

77. Леоненков, A.B. Нечеткое моделирование в среде MATLAB и fuzzyTECH. / A.B. Леоненков. - СПб.: БХВ-Петербург, 2003,- 736 с.

78. Лореш М.А. Алгоритмы муравьиной колонии для простейшей задачи размещения: Препринт. Омск, ОмГУ, 2006. - 19 с.

79. Лычкина, H.H. Имитационное моделирование экономических процессов /H.H. Лычкина. - М.: Академия АйТи, 2005. - 164 с. Режим доступа: http://simulation.su/uploads/files/default/2005-uch-posob-lychkina-l.pdf

80. М.И. Дли, В.В. Гимаров, С.И. Глушко. Алгоритмы поддержки принятия решений по управлению инфраструктурными проектами на основе моделей муравьиных колоний // Весник СГТУ. 2012. №1 (64). Выпуск 2. С. 423-427.

81. Мешалкин, В.П. Экспертные системы в химической технологии / В.П. Мешалкин. — М.: Химия, 1995. — 368 с.

82. Минаков, И.А. Сравнительный анализ некоторых методов случайного поиска и оптимизации / И.А.Минаков. // Известия Самарского научного центра Российской академии наук, № 2, 1999. — С. 286-293.

83. Модели принятия решений на основе лингвистической переменной /А. Н. Борисов, А. В. Алексеев, О. А. Крумберг и др. Рига: Зинатне, 1982.

84. Мухачева Э.А., Валеева А.Ф., Мухачева A.C. Методы локального поиска в дискретных задачах оптимального распределения ресурса: Учеб. пособие. Уфа: УГАТУ. 2001. 103 с.

85. Норенков, И.П. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации / И.П. Норенков, О.Т. Косачевский // Информационные технологии, №2, 1999.

86. Образцов A.A. Топологические декомпозиционно-эвристические алгоритмы и комплекс программ оптимальной ресурсоэнергоэффективной компоновки химических производств: автореф. дисс. на соискание ученой степени канд. техн. наук 05.13.18 // Образцов Андрей Александрович. - М., 2009. - 19 с.

87. Олейник Т.А. Основы дискретной математики: теория и практика. / Т.А. Олейник - М.-.МИЭТ, 2010. - 252 с.

88. Олейникова, С.А. Моделирование и структурно-топологическая оптими-

зация распределенной вычислительной системы с несколькими центрами обработки данных: диссер. на соискание ученой степени канд. техн. наук: 05.13.18 / Олейникова Светлана Александровна. - Воронеж. 2002. - 166 с.

89. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы. /

B.Г. Олифер, H.A. Олифер. — СПб.: Питер, 2013. — 944 с.

90. Олифер, В.Г. Подходы к интеграции неоднородных сетей [Электронный ресурс] / В.Г. Олифер, H.A. Олифер // Транспортная подсистема неоднородных сетей - Режим доступа: http://citforum.ru/nets/tpns/glava_l .shtml

91. Организации системы «Транснефть» [Электронный ресурс] // Открытое акционерное общество «Акционерная компания по транспорту нефти «Транснефть» -Режим доступа: http://www.transneft.ru/company/101//

92. Ощепков, А.Ю. Системы автоматического управления. Теория, применение, моделирование в MATLAB / А.Ю. Ощепков. - СПб.: Лань, 2011. - 456с.

93. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация, Алгоритмы и сложность. М.: Мир. 1985. 512 с.

94. Погребной, A.B. Математические и программные средства построения архитектуры и топологии сети вычислительной системы для управления территориально распределенными объектами: автореф. на соискание ученой степени канд. техн. наук: 05.13.11 / Погребной Александр Владимирович. - Томск, 2008. -21с.

95. Применение программы MATLAB при изучении курса электротехники [Электронный ресурс] // Механика и термодинамика - курс лекций. - М. -Режим доступа: http://matkb.ru/arf24/

96. Пятаев, О.В. Применение генетического алгоритма для оптимизации структуры кампусной сети // Радиоэлектронные и телекоммуникационные системы и устройства: Межвузовский тематический сборник научных трудов. 2000 г. -

C. 55-61.

97. Ричард М. Карп. Сводимость комбинаторных проблем // Кибернетиче-

ский сборник, 12, М.: Мир, 1975. С.16-38.

98. Ротштейн, А.П. Интеллектуальные технологии идентификации: нечеткая логика, генетические алгоритмы, нейронные сети / А.П. Ротштейн. — Винница: УНИВЕРСУМ-Винница, 1999. — 320 с.

99. Рыженко, Н.В. Задача построения дерева Штейнера для этапа глобальной трассировки / Н.В. Рыженко // Сб. научно-технических трудов "Высокопроизводительные вычислительные системы и микропроцессоры". - М.: ИМВС РАН, №4, 2003. - С.96-105.

100. Рыжиков, Ю.И. Имитационное моделирование. Теория и технология. / Ю.И. Рыжиков. - М.: Альтекс-А, 2004. -384 с.

101. Саати, Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы / Т. Саати; пер. с англ. В.Н.Веселова. — М.: Мир, 1973. — 302 с.

102. Самарский A.A., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. М.: ФИЗМАТЛИТ, 2002 - 320 с.

103. Свиридов, A.C. Модели и методы синтеза локальных вычислительных сетей в условиях нечеткой информации: автореф. дисс. на соискание ученой степени канд. техн. наук / Свиридов Андрей Станиславович. - Воронеж., 2000. - 19 с.

104. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, дум., 1988. - 472 с.

105. Сергиенко, И.В. Классификация прикладных методов комбинаторной оптимизации / И.В. Сергиенко, Л.Ф. Гуляницкий, С.И. Сиренко // Кибернетика и системный анализ. - 2009. - Т. 45. - №5. - С.71-84.

106. Сидорина, E.H. Имитационное моделирование [Электронный ресурс] / E.H. Сидорина // Сборник материалов Молодежной электронной научной школы-конференции «Актуальные проблемы защиты информации и информационной безопасности», Ставрополь - 2012. - Режим доступа: http://stavkombez.ru/ conf/2012/05/26/имитационное-моделирование

107. Сизиков, B.C. Обратные прикладные задачи и MATLAB /

B.C. Сизиков. - СПб.: Лань, 2011. - 264с.

108. Стоян, Ю.Г. Математические модели и оптимизационные методы геометрического проектирования /Ю.Г. Стоян, С.В.Яковлев. — Киев: Наук, думка, 1986, —268 с.

109. Таненбаум, Э. Компьютерные сети / Э. Таненбаум, Д. Уэзеролл. -СПб.: Питер, 2013.-960 с.

110. Федеральный закон «О СВЯЗИ» №126-ФЗ: [федер. закон: принят Гос. Думой 07.07.2003: по состоянию на 3 янв. 2001 г.] [Электронныйресурс]. — Режим доступа: http://www.consultant.ru/popular/communication/

111. Ходашинский И.А., Горбунов И.В., Дудин П.А. Алгоритмы муравьиной и пчелиной колонии для обучения нечетких систем // Доклады Томского государственного университета систем управления и радиоэлектроники. -2009. Т. 20, №2.-С. 157-161.

112. Царев, Ф.Н. Методы построения конечных автоматов на основе эволюционных алгоритмов: дисс. на соискание ученой степени канд. техн. наук // Царев Федор Николаевич. - СПб, 2012. - 196 с.

113. Чесалов, А.Ю. Анализ и выбор рациональной структуры региональных распределенных сетей передачи, обработки и хранения данных: автореф. дисс. на соискание ученой степени канд. техн. наук. / Чесалов Александр Юрьевич. - Тверь, 2003. - 21с.

114. Штовба С.Д.. Размещение базовых станций беспроводных широкополосных сетей с помощью муравьиного алгоритма оптимизации / С.Д. Штовба,

C.Ю. Ермолаев, В.Г. Карташевский // Оптико-електрон. інформ.-енерг. технології. -2011.-№ 1. - С.156-162.

115. Штовба, С.Д. Муравьиные алгоритмы / С.Д. Штовба. - Exponenta Pro. Математика в приложениях, 2003, №4, с.70-75.

116. Щербаков, B.C.. Алгоритм роевого интеллекта для планирования тра-

ектории перемещения груза в пространстве с препятствиями с учетом угловой ориентации /B.C. Щербаков // Вестник московского автомобильно-дорожного государственного технического университета (МАДИ). - 2011. - №1. - С. 86-90.

117. Яхъяева, Г.Э. Нечеткие множества и нейронные сети / Г.Э. Яхъяева. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006. - 316 с.