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

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

Глушко Сергей Иванович

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

Специальность:

05.13.18- Математическое моделирование, численные методы и комплексы программ (технические науки)

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

г 9 АВГ 2013

005532332

Москва 2013

005532332

Работа выполнена в филиале ФГБОУ ВПО «Национальный исследовательский университет «МЭИ» в г. Смоленске на кафедре менеджмента и информационных технологий в экономике

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

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

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

Бутусов Олег Борисович, доктор физико-математических наук, профессор, Московский государственный машиностроительный университет, заведующий кафедрой прикладной математики

Большаков Александр Афанасьевич, доктор технических наук, профессор, Саратовский государственный технический университет им. Гагарина Ю.А., профессор кафедры систем искусственного интеллекта

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

Уфимский государственный нефтяной технический университет

Защита состоится «27» сентября 2013 г. в 13.00 часов на заседании диссертационного совета Д 212.204.10 при РХТУ им. Менделеева по адресу: 125047, г. Москва, Миусская пл., д. 9, Конференц-зал (ауд. 443).

С диссертацией можно ознакомиться в Научно-информационном центре РХТУ им. Менделеева.

Автореферат разослан «23» августа 2013 г.

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

Д 212.204.10, д.э.н., профессор

З.В. Вдовенко

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оглавление диссертации

ВВЕДЕНИЕ

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 Результаты применения разработанных алгоритмов и комплекса программ «GeoR.ES 1.0» для проектирования оптимальной телекоммуникационной сети предприятия ОАО «Связьтранснефть»

4.4 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СЛОВАРЬ ТЕРМИНОВ

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

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

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

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

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

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

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

показателей надежности.

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

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

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

mmiSizXVrix)} х', где х

S(x) = i'hzxi)dl, q = XQ,e^x,

<•=i о

n IX если ) * а(е, ,),

ыг [0, если q(et) = q(e,_t)

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

ei

js^(l)d! - стоимость прокладки кабеля типа q, как непрерывная функция на дуге

о

е,; /(е/)- функция, определяющая количество переходов от одного вида кабеля

на другой на маршруте х", Ч(е,) -тип кабеля, используемого на ребре е,-.

Сформулированная автором задача является Л'Р-сложной, поэтому для её решения целесообразно использовать эвристические методы. К эффективным современным эвристическим методам относятся так называемые метаэвристики, отображающие обобщенные стратегии поиска оптимума в пространстве решений: метод имитации отжига ("simulated annealing")', метод поиска с запретами ("tabu search"); оптимизационный метод муравьиной колонии {"ant colony optimization "); генетические и эволюционные алгоритмы. Преимущество данных методов состоит в том, что они позволяют исследовать большее пространство для поиска решения, близкого к оптимальному.

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

трассы ТЛКС.

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

Оптимизация осуществляется одновременно по двум критериям на основе перемещения трех колоний муравьев. Цель первой колоний — сократить количество переходов от одного вида кабеля на другой (т.е. максимизировать унифицированность и технологическую однородность ТЛКС).

Формирование нечетких множеств и функций принадлежности

Определение функций принадлежности нечетких множеств для первой колонии Определение функций принадлежности нечетких множеств для второй колонии Определение функций принадлежности нечетких множеств для третьей колонии

Оптимизация маршрута по степени однородности

Формирование первой колонии муравьев к], определяющих степень

однородности прокладываемых _трасс_

Итерационный поиск наиболее однородного маршрута х'ш

Обновление количества феромона на всех участках маршрута

С °

о &

Оптимизация маршрута по общей стоимости прокладки

Формирование второй колонии муравьев 1с2, определяющей стоимость прокладываемых трасс

Итерационный поиск наиболее дешевого маршрута -¿п

Обновление количества феромона на всех участках маршрута^

Формирование третьей колонии Выбор оптимального

муравьев к3 маршрута %*

Обновление количества феромона и ^

_ ^^У^кр^херишшая^зттюадая^^шр^ тр^^^ме^(мму1шкационной_сети I

Рисунок 1 - Обобщенная блок-схема иерархического многоколониального муравьиного алгоритма оптимизации по минимуму затрат и унифицированности структуры ТЛКС

НТП

Вторая колония ищет минимальный по общей стоимости проектирования и строительства маршрут. Обе колонии используют независимые друг от друга феромон-пые тропы: цх и ¡л1. На основе объединения полученных двумя колониями на каждой итерации процедуры поиска локальных решений в графе ТЛКС количеств феромона, а также весов ребер 771 и /72 первого и второго типов, третья колония искусственных муравьев осуществляет поиск оптимального решения поставленной задачи. Для увеличения скорости сходимости предложенного многоколониального муравьиного алгоритма, а также для учета неопределенности исходной информации количество феромона первого и второго типов, а также вес дуг графа второго типа представлено в виде нечетких высказываний.

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

этапы:

1. Первоначальная трасса ТЛКС определяется значениями феромона и веса первого и второго типа , ц^ и т/1, т]г соответственно) для каждой дуги гра-

2. Параллельный поиск М муравьями трасс на основе информации о количестве феромонов и ¡л1) и весах (г/1 и ц1). Муравей на каждом шаге прокладки трассы в графе выбирает следующую присоединяемую вершину по правилу расчета величины нечеткой возможности перехода:

® {^гт ® [(ф0""' ® (т?*ГГ Ри'у7 ' (2)

® (/4)Т ®[(^)<1"в) ® (.ч»)'У)

I

где ® - операция умножения нечетких чисел; ¡л^ - количество первого феромона на дуге (iJ)^, /¿у - количество второго феромона на дуге - привлекательность пе-

рехода в вершину] из вершины г" по критерию однородности сети; г^ — привлекательность перехода в вершину у из вершины г по критерию стоимости трассы (нечеткая величина, обратная стоимости строительства сети на участке у)\ гае[0,1] — весовой коэффициент, отражающий относительную значимость критерия стоимости маршрута;

Ру - множество вершин в графе, которые муравей т еще не посетил, но они доступны

для перехода на текущей итерации.

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

определяются на основе значений соответствующих параметров их (£-Л)-представлений. Умножение двух нечетких высказываний (Х-/У-типа Л/./г=<а;,ес;,/?;> и Вщ=<а2,а2,р2> является нечетким высказыванием Л1Я ■ Ви{ = С1Н =<а,а,Р >, определяемым по формулам:

а = а,-а2; а = а{ а2 + а2 -«■,; ¡3 = ах- рг+а2- (3)

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

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

^ (/ +1) = (1 - р)ц]. (О е д^. (0

V (/)=Iе''^(0, если (,'У) е ^

" [0, в противном случае где р- коэффициент испарения феромона, Д/^Дг)- суммарное изменение уровня феромона на дуге графа (ц); Г'(0_ общий маршрут, построенный муравьем / на итерации - относительная оценка качества найденного маршрута; <3 -константа, показывающее общее количество феромона у муравья. Величина Р1 (I) позволяет сопоставлять полученные на различных итерациях трассы между собой, определяя, таким образом, наиболее рациональный:

^'(0 = ( X V®!!4, (5)

//еГ'(0

где ^ - общая стоимость (нечеткое высказывание) прокладки трассы Т1 (/);>/-

коэффициент значимости показателя «стоимость»; п - количество переходов от одного

способа передачи данных на другой при построении трассы Т (0, £ - коэффициент значимости показателя «количество переходов».

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

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

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

однородной трассы ТЛКС основан на использовании для каждой метки / е L обособленного значения феромона Тогда на каждой итерации муравей m строит решение, состоящее из множества меток L ', при этом нечеткое высказывание добавления метки / определяется по формуле:

„ _(p(L'J), если c(L \j /) < c(L '),

PL. ' I — i

[О, в остальных случаях

p{LJ)=-X-Mr'-nWV

/•s{/SZ.[C(£W)«7(Z.')}

где c(L') - количество компонент связности графа G=(V,E'): Е' — множество дуг с меткой из множества L '.

Баланс между информацией о количестве феромона /л(Ь\1) и весом дуги r](L'J') контролируется параметрами а и р. Пусть E(L')czE - подмножество дуг, отмеченных меткой /sL, и пусть c(L') обозначает количество связанных компонентов подграфа G'= (V,E(L')). Вес дуги равен:

77(L',/) = c(L')-c(£VW). (7)

Обновление количества феромонов для каждой метки равно:

+1) = (1 - р)ц\(0 +1 для V/ е L'. (8)

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

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

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

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

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

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

Вычисления производились на персональном компьютере с двухядерным процессором с тактовой частотой 2,67 ГГц. В качестве сопоставляемых параметров были выбраны среднее время работы (?) в мс, средняя стоимость маршрута (5) в условных единицах.

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

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

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

В четвертой главе «Разработка и практическое применение комплекса программ оптимизации телекоммуникационных сетей «йеоИЕЗ 1.0» представлена архитектура комплекса программ ОеоЛН>1.0 двухкритериальной оптимизации структуры ТЛКС; обоснован выбор инструментальных программных средств для разработки комплекса программ; описаны режимы функционирования и методика применения «СеоЛЕ5 1.0»; представлены научно-обоснованные рекомендации по применению комплекса программ для выбора рациональной структуры проектируемой ТЛКС предприятия ОАО «Связьтранснефть».

Рисунок 2 - Пример решения задачи поиска оптимального по минимуму стоимости и унифицированности маршрута

Предложенные алгоритмы оптимизации структуры кабельной ТЛКС практически реализованы в виде комплекса программ «GeoRES 1.0», используемом для управления телекоммуникационной инфраструктурой. Данный комплекс позволяет увеличить скорость процессов планирования структуры ТЛКС, рассчитывать точную стоимость их строительства с использованием геоинформационных систем и электронных картографических данных с учетом направлений, проходимости и удаленности объектов друг от друга. Архитектура комплекса программ оптимизации структуры ТЛКС построена по модульному принципу (см. рисунок 3) с использованием среды программирования Delphi и пакета программ Matlab (пакет Fuzzy Logic Toolbox). В качестве системы управления базами данных выбрана Microsoft SQL Server.

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

Полученная структура сети (см. рисунок 4) является однородной, поскольку для её построения использовался один вид кабеля - волоконно-оптический. Общая стоимость реализации проекта по трассе составила 1,195 млрд. руб.

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

Продукционная БЗ

Модуль управления БЗ

Добавление знаний

Редактирование знаний

Удаление знаний

Модуль ввода фактографических данных о ТЛКС

Модуль управления нечеткими данными

Ввод экспертной информации

Обработка и согласование экспертной информации

Построение структуры нечетко-логической системы

Определение функций принадлежности нечетких множеств системы

Нечетко-логический вывод

Интеллектуальный блок

Модуль поиска оптимального маршрута ТЛКС

Определение структуры моделей Задание параметров моделей Проведение экспериментов

Корректировка моделей Интерпретация результатов Формирование отчетов

БД

картографии

БД

атрибутов

БД

алгоритмов

Хранилище данных

СУБД Microsoft SQL Server

Имитационный блок

1ЛЫ

ЛПР

Информационная система «ОеоИАЗ 1.0»

Рисунок 3 - Блок-схема архитектуры комплекса программ «веоИЕЗ 1.0» оптимизации телекоммуникационной сети

С использованием комплекса программ «ОгоЛЕЯ 1.0» спроектирована оптимальная структура ТЛКС (см. рисунок 4).

Рисунок 4 - Граф оптимальной ТЛКС на участке Ухта - Ярославль

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

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

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

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

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

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

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

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

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

Список работ, опубликованных автором по теме диссертации:

В изданиях перечня ВАК

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

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

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

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

5. Дли М.И., Гимаров В.В., Глушко С.И.. Алгоритмы поддержки принятия решений по управлению инфраструктурными проектами на основе моделей муравьиных

колоний // Весник СГТУ. 2012. №1 (64). Выпуск 2. С. 423-427.

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

7. Глушко С.И. Многоколониальная муравьиная модель оптимизации телекоммуникационной сети // Научное обозрение. №7. С. 83-86.

В других изданиях

8. Глушко С.И., Мешалкин В.П. Интеллектуальный метод выбора оптимального маршрута формирования инфраструктуры предприятия // Экономика. Менеджмент. Логистика. Корпоративные информационные системы. - Межвуз. сб. науч. тр. (Вып. 3) - Смоленск: Смоленский ЦНТИ, 2010. - С. 47-49.

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

10. Dli M.I., Glushko S.I., Ivanova I.V. Ant algorithme as a tool of infrastructure Project management // European Science and Technology: materials of the III research and practice conférence. Publishing office Vela Verlag Waldkraiburg. Munich. Germany. 2012. 127-129 p.

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

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

13. Мешалкин В.П., Глушко С.И. Иерархические нечеткие многоколониальные муравьиные алгоритмы и комплекс программ оптимизации телекоммуникационных сетей нефтетранспортных предприятий. Смоленск: Универсум, 2013. 142 с.

В работах, написанных в соавторстве, Глушко С.И. принадлежат следующие результаты: в работах [1, 2, 3, 8, 9] разработан обобщающий муравьиный алгоритм оптимальной трассировки ТЛКС, отличающийся возможностью учета неопределенности исходной информации; в работах [4, 5, 10] описан эвристический муравьиный алгоритм выбора унифицированной технологически однородной трассы ТЛКС, основанный на поиске минимального маркированного остовного дерева в графе; в [6] проанализированы возможности описания параметров системы с использованием нечетко-логических выражений; в [13] предложена архитектура и режимы функционирования комплекса программ «GeoRAS 1.0».

Дата сдачи в печать 19.08.2013 г. Формат 60x84/16. Усл. печ. л. 1,0. Тираж 150. Заказ № 5608/1.

Отпечатано в ООО «Принт-Экспресс», г. Смоленск, пр-т Гагарина, 21. Тел.: (4812) 32-80-70

ФИЛИАЛ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МЭИ» В Г. СМОЛЕНСКЕ

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

04201361428

Глушко Сергей Иванович

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

Специальность

05.13.18 - Математическое моделирование, численные методы и комплексы программ (технические науки).

Диссертация

на соискание ученой степени кандидата технических наук

Научный руководитель: Мешалкин Валерий Павлович, член-корреспондент РАН, заслуженный деятель науки РФ, доктор технических наук, профессор

Смоленск - 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ......................................................................................................................4

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

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

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

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

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

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

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

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

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

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

2.5 Выводы.....................................................................................................................74

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

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

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

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

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

3.4 Выводы.....................................................................................................................95

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

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

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

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

4.4 Выводы...................................................................................................................120

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

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

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

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

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

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

ВВЕДЕНИЕ

Актуальность темы. Магистральные трубопроводы играют важнейшую роль в нефтяной и нефтеперерабатывающей промышленности, являясь основным и наиболее дешевым средством транспортировки нефти и природного газа в цепи поставок добыча - транспортировка - переработка - конечные потребители. С помощью магистральных трубопроводов осуществляется перемещение почти 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. Формализованная постановка задачи оптимизации телекоммуникационной сети предприятия �