Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

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

Магистральные трубопроводы играют важнейшую роль в нефтяной и нефтеперерабатывающей промышленности, являясь основным и наиболее дешевым средством транспортировки нефти и природного газа в цепи поставок добыча — транспортировка — переработка — конечные потребители. С помощью магистральных трубопроводов осуществляется перемещение почти 100% добываемого природного газа, свыше 95% нефти, не менее 50… Читать ещё >

Содержание

  • 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 п.л.

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: Количество рёбер графа О, инцидентных вершине х. трассировка: Процедура получения информации о маршрутизаторах (узлах) сети, через которые проходит трафик на пути к месту назначения. функция принадлежности нечёткого множества: Обобщение индикаторной (или характеристической) функции классического множества. В нечёткой логике она представляет степень принадлежности каждого члена пространства рассуждения к данному нечёткому множеству. целевая функция: Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации. эвристический алгоритм: Алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. эвристический муравьиный алгоритм выбора унифицированной структуры телекоммуникационной сети: Муравьиный алгоритм поиска максимально однородной унифицированной структуры телекоммуникационной сети, основанный на поиске минимального маркированного остовного дерева с ограниченными степенями на графе с использованием обособленных феромонных троп для каждой трассы, а также модифицированной процедуры определения возможности перехода муравьев между вершинами графа как функции от количества связанных компонент графа.

Показать весь текст

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

  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. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. G. Zhou, M. Gen, and T. Wu, «A new approach to the degree-constrainedminimum spanning tree problem using genetic algorithm,» in Proceedings of the International Conference on System, Man, and Cybernetics, Vol. 4, 1996, pp. 2683- 2688.
  9. Hanan, M. On Steiner’s problem with rectilinear distance / M. Hanan // SIAM Journal of applied mathematics, № 14(2). 1966. — pp.255−265.
  10. 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.
  11. 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.
  12. 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.
  13. N. Deo and S. L. Hakimi, «The shortest generalized Hamiltonian tree,» in Proceeding of the 6th Annual Allerton Conference, 1968, pp. 879−888.
  14. R.-S. Chang and S.-J. Leu. The minimum labeling spanning trees. Information Processing Letters, 63(5):277−282, 1997.
  15. 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.
  16. 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.
  17. 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.
  18. 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
  19. 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. 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.
  23. , E.B. Проектирование рациональной топологии беспроводных сенсорных сетей: автореф. дисс. на соискание ученой степени канд. техн. наук / Акимов Евгений Вячеславович. М., 2010. — 22 с.
  24. Алгоритм имитации отжига Электронный ресурс. Режим доступа: http://www.math.nsc.ru/AP/benchmarks/UFLP/uflpsa.html
  25. А.Е., Семухин М. В. Модели и алгоритмы принятия решений в нечетких условиях. — Тюмень: Изд-во «ТГУ», 2000
  26. Ануфриев, И.Е. MATLAB 7.0 / И. Е. Ануфриев, А. Б. Смирнов, Е. Н. Смирнова. СПб.: БХВ-Петербург, 2005. — 1104 с.
  27. , М.О. Дискретная математика: графы, матроиды, алгоритмы / М. О. Асанов, В. А. Баранский, В. В. Расин. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. — 288 с.
  28. , С.К. Системы управления на нечеткой логике / С. К. Атанов // Вестник КГУ. Казахстан, Костанай: КГУ им. А. Байтурсынова. — 2008. — № 2. -С. 15−21.
  29. В.JI. Алгоритм неявного перебора для задачи типа размещения и стандартизации. Управляемые системы. Вып. 12 (1974). Новосибирск, Институт математики Сиб.отд. АН СССР, С. 24−34.
  30. , А.Н. Принятие решений на основе нечетких моделей / А. Н. Борисов, O.A. Крумберг, И. П. Федоров. Рига: Зинанте, 1990. — 184 с.
  31. , В.В. Нечеткие модели и сети / В. В. Борисов, В. В. Круглов, A.C. Федулов М.: Горячая линия — Телеком, 2007. — 283 с.
  32. , В.О. Исследование задачи коммивояжера / В. О. Борознов // Вестник АГТУ. Серия: управление, вычислительная техника и информатика. -2009. -№ 2.-С.174−151.
  33. Д.А. Постановка задачи структурной оптимизации магистральной корпоративной телекоммуникационной сети // Информация и Космос. — 2005. -№ 2. -С. 42−47.
  34. , А.Ф. Применение конструктивных эвристик в задачах раскроя-упаковки / А. Ф. Валеева // Приложение к журналу «Информационные технологии» № 11, 2006 г
  35. Васильев, А.Н. Matlab. Самоучитель. Практический подход /
  36. A.Н. Васильев. М.: 2012. — 448 с.
  37. , В.М. Теоретические основы проектирования компьютерных сетей/ В. М. Вишневский // Москва: Техносфера, 2003. 254 с.
  38. В.А. О задаче оптимизации построения первичной сети свя-зи.//Труды ИВМ и МГ. Сер. Информатика. Новосибирск, 2005. -№ 5. — С. 68−79.
  39. , Л.А. Генетические алгоритмы. / Л. А Гладков, В. М. Курейчик,
  40. B.В. Курейчик. Ростов-на-Дону: ООО «Ростиздат», 2004.
  41. С.И. Многоколониальные алгоритмы муравьиных колоний для решения двухкритериальной задачи выбора маршрута // Информационные технологии, энергетика и экономика: Сб.тр. X Междунар. Науч.-техн. конф. Т. 2. Смоленск: Универсум, 2013. С.25−28.
  42. С.И., Бояринов Ю. Г. Полумарковские модели систем с нечеткими параметрами // Программные продукты и системы. 2012. № 2 (98). С. 146−149.
  43. С.И., Гимаров В. В., Образцов A.A. Алгоритм учета неопределенности численных характеристик инфраструктурного проекта // Сб.тр. Междунар. Науч.-техн. конф. Т. 2. Смоленск: Универсум, 2012. С.14−17
  44. С.И., Иванова И. В. Нечеткие муравьиные алгоритмы планирования оптимального маршрута прокладки трубопроводного транспорта // Электронный научный журнал «Нефтегазовое дело». 2012. № 6. С. 120−125.
  45. С.И., Какатунова Т. В. Нечеткая модификация алгоритма муравьиных колоний // Научное обозрение. 2013. № 1. С.377−381.
  46. С.И., Образцов A.A., Кузавко A.C. Применение алгоритма муравьиных колоний для решения задач оптимизации на графе // Приоритетные научные направления: от теории к практике: Сб. тр. II Межд. научно-практ. конф. -Новосибирск, 2012. С.67−71.
  47. E.H., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер.2, т.6 (1999). — № 1. — С. 12−32.
  48. E.H. Метод ветвей и границ для простейшей двухуровневой задачи размещения предприятий // Дискретный анализ и исследование операций,
  49. Серия 2, 1998, том 5, N1. С. 19−39.
  50. , A.A. Прикладные задачи математического программирования: учебное пособие / A.A. Грешилов. — М.: Логос. — 2006. — 288 с.
  51. Дли М.И., Гимаров В. В., Глушко С. И. Конфигурирование информационных и транспортных сетей в условиях неопределенности // Прикладная информатика. 2012. № 6(42). С. 81−86.
  52. Дли М.И., Гимаров В. В., Глушко С. И. Применение алгоритмов муравьиных колоний при управлении сложными проектами // Транспортное дело России. 2012. № 4. С. 51−54.
  53. , Б.Э. Системный анализ и теоретико-графовые модели оптимизации региональных газораспределительных сетей: автореф. на соискание ученой степени канд. техн. наук: 05.13.18 / Забержинский Борислав Эдуардович. -Самара. 2007. 20 с.
  54. Л. Понятие лингвистической переменной и ее применение к принятию приближенных решений. М.: Мир, 1976.
  55. Л.А., Китриноу Е., Колоколов Задача оптимального размещения центров телекоммуникаций в регионе // Труды XI Байкальской международной школы-семинара «Методы оптимизации и их приложения», Иркутск, Байкал, 2005. Т.1.-С. 469−476.
  56. , С.П. Математические расчеты на базе MATLAB / С. П. Иглин. -СПб.: БХВ-Петербург, 2005. 640 с.
  57. Имитационное моделирование Электронный ресурс. Режим доступа: http://www.simulation.ru/consulting/whatissimulation/
  58. Использование имитационного моделирования Электронный ресурс. //
  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, т. 6. — С. 22−26.
  65. , Ю.А. Методы локального поиска для дискретных задач размещения: дисс. на соискание ученой степени д-ра. физ.-мат. наук // Кочетов Юрий Андреевич. Новосибирск, 2009. — 267 с.
  66. , С.В. Автоматизированное проектирование вычислительных сетей промышленных предприятий в условиях нечетко заданного трафика: авто-реф. дисс. на соискание ученой степени канд. техн. наук / Краснов Сергей Васильевич Ульяновск, 2001. — 19 с.
  67. Д.М. Системный анализ и синтез топологической структуры проводных сетей передачи данных: автореф. дисс. на соискание ученой степени канд. техн. наук 05.13.01 / Кривоносов Дмитрий Михайлович. Волгоград. 2004. — 19 с.
  68. В.В. Нечеткая игровая модель с единичным экспериментом //Нейрокомпьютеры: разработка и применение. 2003. № 8−9. С. 24−28.
  69. В.В. Нечеткие игровые модели и их применение в задачах принятия решений, классификации и прогнозирования // Вестник МЭИ. 2004. № 1. С. 82−85.
  70. , В.В. Генетические алгоритмы / JI. A Гладков, В. В. Курейчик, В.М. Курейчик- под ред. В. М. Курейчика. 2-е изд., испр. и доп. — М.: Физматлит, 2006. — 320 с.
  71. , В.М. Комбинаторные аппаратные модели и алгоритмы в САПР / В. М. Курейчик, В. М. Глушань, Л. И. Щербаков. — М.: Радио и связь, 1990
  72. , И.И. Разработка и анализ методов последовательной прокладки путей в сетях передачи данных: дисс. на соискание ученой степени канд. техн. наук / Курочкин Илья Ильич. М., 2010. — 25с.
  73. , Б.К. Разработка теории и принципов поисковой адаптации для решения оптимизационных задач топологического синтеза: автореф. дисс. на соискание ученой степени канд. техн. наук. // Лебедев Борис Константинович. Таганрог., 2001.-40 с.
  74. Т.В., Лореш М. А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане // Автоматика и телемеханика. 2004. № 3. С. 80−89.
  75. Лекция 8. Конвергенция компьютерных и телекоммуникационных сетей Электронный ресурс. — Режим доступа: http://wiki.auditoiy.ru/JIeK4M8. Конвергенциякомпьютерныхителекоммуникационныхсетей
  76. , A.B. Нечеткое моделирование в среде MATLAB и fuzzyTECH. / A.B. Леоненков. СПб.: БХВ-Петербург, 2003, — 736 с.
  77. М.А. Алгоритмы муравьиной колонии для простейшей задачи размещения: Препринт. Омск, ОмГУ, 2006. 19 с.
  78. , H.H. Имитационное моделирование экономических процессов /H.H. Лычкина. М.: Академия АйТи, 2005. — 164 с. Режим доступа: http://simulation.su/uploads/files/default/2005-uch-posob-lychkina-l.pdf
  79. М.И. Дли, В. В. Гимаров, С. И. Глушко. Алгоритмы поддержки принятия решений по управлению инфраструктурными проектами на основе моделей муравьиных колоний // Весник СГТУ. 2012. № 1 (64). Выпуск 2. С. 423−427.
  80. , В.П. Экспертные системы в химической технологии / В. П. Мешалкин. — М.: Химия, 1995. — 368 с.
  81. , И.А. Сравнительный анализ некоторых методов случайного поиска и оптимизации / И. А. Минаков. // Известия Самарского научного центра Российской академии наук, № 2, 1999. — С. 286−293.
  82. Модели принятия решений на основе лингвистической переменной /А. Н. Борисов, А. В. Алексеев, О. А. Крумберг и др. Рига: Зинатне, 1982.
  83. Э.А., Валеева А. Ф., Мухачева A.C. Методы локального поиска в дискретных задачах оптимального распределения ресурса: Учеб. пособие. Уфа: УГАТУ. 2001. 103 с.
  84. , И.П. Генетические алгоритмы комбинирования эвристик в задачах дискретной оптимизации / И. П. Норенков, О. Т. Косачевский // Информационные технологии, № 2, 1999.
  85. Т.А. Основы дискретной математики: теория и практика. / Т. А. Олейник М.-.МИЭТ, 2010. — 252 с.
  86. , В.Г. Компьютерные сети. Принципы, технологии, протоколы. /
  87. B.Г. Олифер, H.A. Олифер. — СПб.: Питер, 2013. — 944 с.
  88. , В.Г. Подходы к интеграции неоднородных сетей Электронный ресурс. / В. Г. Олифер, H.A. Олифер // Транспортная подсистема неоднородных сетей Режим доступа: http://citforum.ru/nets/tpns/glaval .shtml
  89. Организации системы «Транснефть» Электронный ресурс. // Открытое акционерное общество «Акционерная компания по транспорту нефти «Транснефть» -Режим доступа: http://www.transneft.ru/company/101//
  90. , А.Ю. Системы автоматического управления. Теория, применение, моделирование в MATLAB / А. Ю. Ощепков. СПб.: Лань, 2011. — 456с.
  91. X., Стайглиц К. Комбинаторная оптимизация, Алгоритмы и сложность. М.: Мир. 1985. 512 с.
  92. Применение программы MATLAB при изучении курса электротехники Электронный ресурс. // Механика и термодинамика курс лекций. — М. -Режим доступа: http://matkb.ru/arf24/
  93. , О.В. Применение генетического алгоритма для оптимизации структуры кампусной сети // Радиоэлектронные и телекоммуникационные системы и устройства: Межвузовский тематический сборник научных трудов. 2000 г. 1. C. 55−61.
  94. М. Карп. Сводимость комбинаторных проблем // Кибернетический сборник, 12, М.: Мир, 1975. С.16−38.
  95. , А.П. Интеллектуальные технологии идентификации: нечеткая логика, генетические алгоритмы, нейронные сети / А. П. Ротштейн. — Винница: УНИВЕРСУМ-Винница, 1999. — 320 с.
  96. , Н.В. Задача построения дерева Штейнера для этапа глобальной трассировки / Н. В. Рыженко // Сб. научно-технических трудов «Высокопроизводительные вычислительные системы и микропроцессоры». М.: ИМВС РАН, № 4, 2003. — С.96−105.
  97. , Ю.И. Имитационное моделирование. Теория и технология. / Ю. И. Рыжиков. М.: Альтекс-А, 2004. -384 с.
  98. , Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы / Т. Саати- пер. с англ. В. Н. Веселова. — М.: Мир, 1973. — 302 с.
  99. A.A., Михайлов А. П. Математическое моделирование: Идеи. Методы. Примеры. М.: ФИЗМАТЛИТ, 2002 320 с.
  100. , A.C. Модели и методы синтеза локальных вычислительных сетей в условиях нечеткой информации: автореф. дисс. на соискание ученой степени канд. техн. наук / Свиридов Андрей Станиславович. Воронеж., 2000. — 19 с.
  101. И.В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, дум., 1988. 472 с.
  102. , И.В. Классификация прикладных методов комбинаторной оптимизации / И. В. Сергиенко, Л. Ф. Гуляницкий, С. И. Сиренко // Кибернетика и системный анализ. 2009. — Т. 45. — № 5. — С.71−84.
  103. , B.C. Обратные прикладные задачи и MATLAB /
  104. B.C. Сизиков. СПб.: Лань, 2011. — 264с.
  105. , Ю.Г. Математические модели и оптимизационные методы геометрического проектирования /Ю.Г. Стоян, С. В. Яковлев. — Киев: Наук, думка, 1986, —268 с.
  106. , Э. Компьютерные сети / Э. Таненбаум, Д. Уэзеролл. -СПб.: Питер, 2013.-960 с.
  107. Федеральный закон «О СВЯЗИ» № 126-ФЗ: федер. закон: принят Гос. Думой 07.07.2003: по состоянию на 3 янв. 2001 г. [Электронныйресурс]. — Режим доступа: http://www.consultant.ru/popular/communication/
  108. И.А., Горбунов И. В., Дудин П. А. Алгоритмы муравьиной и пчелиной колонии для обучения нечетких систем // Доклады Томского государственного университета систем управления и радиоэлектроники. -2009. Т. 20, № 2.-С. 157−161.
  109. , Ф.Н. Методы построения конечных автоматов на основе эволюционных алгоритмов: дисс. на соискание ученой степени канд. техн. наук // Царев Федор Николаевич. СПб, 2012. — 196 с.
  110. , А.Ю. Анализ и выбор рациональной структуры региональных распределенных сетей передачи, обработки и хранения данных: автореф. дисс. на соискание ученой степени канд. техн. наук. / Чесалов Александр Юрьевич. Тверь, 2003. — 21с.
  111. С.Д. Размещение базовых станций беспроводных широкополосных сетей с помощью муравьиного алгоритма оптимизации / С. Д. Штовба,
  112. C.Ю. Ермолаев, В. Г. Карташевский // Оптико-електрон. інформ.-енерг. технології. -2011.-№ 1. С.156−162.
  113. , С.Д. Муравьиные алгоритмы / С. Д. Штовба. Exponenta Pro. Математика в приложениях, 2003, № 4, с.70−75.
  114. , Г. Э. Нечеткие множества и нейронные сети / Г. Э. Яхъяева. М.: Интернет-Университет Информационных Технологий- БИНОМ. Лаборатория знаний, 2006. 316 с.
Заполнить форму текущей работой

На отлично!