Автореферат диссертации Глушко.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
На правах рукописи
Глушко Сергей Иванович
Иерархические
нечеткие
много
колониальные
муравь
ные
алгоритмы
и комплекс программ оптимизации
телекоммуникационн
нефтетранспорт
ных
пре
прияти
Специальность:
05.13.18
Математическое мод
елирование, численные методы и комплек
сы
программ (технические науки)
Автореферат
диссертации на соискание ученой степени
кандидата технических наук
Москва 2013
Работа выполнена в филиале ФГБОУ ВПО «Национальный исследовательский
универси
тет «МЭИ» в г.
Смоленске на кафедре менеджмента и информационных
технологий в экономике
Научный руководитель:
Член
корреспондент РАН, заслуженный деятель науки РФ,
доктор технических наук, профессор Мешалкин Валерий Павл
вич
Российский химико
технолог
ический университет им. Д.И.
Менделеева,
заведующий кафедрой
логистики и эконом
ческой информатики
Официальные оппоненты:
Бутусов Олег Борисович, д
октор физико
математических наук, профессор
Московский государственный машиностроительный университет
заведующий кафедрой
прикладной математики
Большаков Александр Афанасьевич, д
октор технических наук, профессор
Саратовский государственный технический университет им. Г
гарина Ю.А.
профессор кафедры
систем искусственного интеллекта
Ведущая организация:
Уфимский государственный нефтяной технический университет
Защита состоится «
сентября
201
г.
.00
часов на заседании
диссертационного совета Д 212.
204
при
РХТУ им. Менделеева
по адресу:
125047
, г. Москва,
Миусская пл.
, д.
Конференц
зал (ау
д. 443)
С диссертацией можно ознакомиться в
Научно
информационном центре РХТУ
им. Менделеева
Автореферат разослан ∫

июля
Ученый секретарь
диссертационного совета
212.204.10
.э.н.,
профессор
З.В. Вдовенко
��1 &#x/MCI; 0 ;&#x/MCI; 0 ;ОБЩАЯ ХАРАК
ТЕРИСТИКА РАБОТЫ
Актуальность темы.
Магистральные т
рубопровод
играют важнейшую
роль
в нефт
яной и нефтеперерабатывающей
промышленности,
явл
ясь
основным
и наиболее дешевым средством транспортировки нефти и приро
ного газа
в цепи
поставок добыча
транспорт
ировка
переработка
конечны
потребител
. С
помощью
магистральных трубопроводов
осуществляется перемещение почти
100% добываемого природного газа, свыше 95% нефти, не менее 50% продуктов
нефтепереработки. В общем объеме транспортировки продукции по маги
страл
ным трубопроводам доля нефти составляет 40,3%, газа
55,4%, нефтепродуктов
4,3%.
ффективность транспортировки углеводородов в значительной мере
пре
определяет
промышленную и экологическую
безопасность
динамику
экономич
е−
ского
роста
страны
, что
уславливает
необходимость реш
ния задач
контроля и
управления
магистральными трубопров
дами с использованием
нформационн
телекоммуникационны
систем
Современные тенденции
модернизации
структуры управления
предприят
ями
нефтяной и нефтеперерабатывающей
промышленности
предполагают нео
ходимость разработки
и внедрени
корпоративных
информацион
ных
систем
нефтетранспортн
предприяти
(НТП)
включа
ющих
комплексы программ о
тимизации структуры телекоммуникационной сети НТП, которые состоят из
ного хранилищ
а данных, систем сбора, обработки и анализа информации
Реш
е−
ние
указанных научно
технических
задач для территориально распределенных
предприятий
нефт
ной и нефтеперерабатывающей промышленности
возможно
только при создании гибкой, масштабируемой
структуры т
елекомм
никационной
сети НТП
Проведенный
системный
нализ
современного состояния
телекомм
никационных
сет
передачи данных
(сетей верхнего уровня)
как основы
эле
тронного
обмена производственно
технологической, финансовой и администр
а−
тивно
хозяйственной
информацией
для
распределенных
НТП
выявил необход
мость реконструкции
их
существующей структуры
, которая
включает
меропри
я−
тия по замене
оборудования узлов сети, а также изменение
её
структуры
на рад
ально
узловую, что позволит
обеспечить
высок
надежност
Прое
тирование
оптимальной структуры
телекоммуникационной
сети
(ТЛКС)
по
минимуму о
щих затрат
и унифицированности используемых видов кабелей
позволит
в знач
тельной степени сократить затраты материальных, трудовых и финансовых р
е−
сурсов, необходимых для
строительства
каналов связи
, а также д
стичь высоких
показат
лей их функционирования
Методологические основы
решения задач
оптимизации сетевой инфрастру
туры
изложены в работах отечественных ученых
член
корр. РАН, проф. Мешалк
В.П.,
проф. Балаш
.П.,
проф. Вишневского
В.М.,
проф.
Казеннова
Г.Г.,
профессоров
Коробова
П.Н.,
Лобанова
Ф.И.,
Марченко
А.М.,
Щем
е−
линина
В.М.
, а
также зарубежных ученых:
Breuer
M.A., Burstein
M., Chiang
C.,
Cong
J., Lien
J.C., Pelavin
R.,
Shapiro
J.F.,
Szymanski
T.
, Taka
gi H.
данных
работах
отмечено, что
в настоящее время
наиболее перспективным
мет
ами
оптимизации
структуры
ТЛКС являю
тся
эвристические ме
тоды
Преимущество
этих методов
стоит в
возможност
решения задач большой размерности с относительно
небол
шими
числительными затратами.
Теоретические основы
разработки
эвристич
е−
��2 &#x/MCI; 0 ;&#x/MCI; 0 ;ских
алгоритмов
оптимальной трассировки
инфраструкту
ной сети
представлены в
работах оте
чественных и зарубежных уч
Антамошкина
А.Н., Баркалова
С.А.,
проф. Бронштейн
Е.М.. Буркова
В.Н.,
Дайнеко
В.Г., Мудрова
В.И.,
Шнитина
Ю.В.,
Штовбы
С.Д.,
Юсуповой
Н.И.,
Dorigo
Gambardella
.,
Maniezzo
Neumann
Paletta
.,
Schneider
.,
Tam
В то же время с
уществующие эвр
стические методы
не позволяют учит
вать неопределенность исходно
й информации
при
решении задач оптимальной трассировки
а также возможность многокритер
ально
оптимизации
трассы
. Для
учета
неопределенности
при решении этих задач
целесообразно использовать интервальные оценки
неопределенных
значений пар
а−
метров
математич
еских
модел
ей
, а также
методы нечетко
логического вывода
с−
польз
вани
ем
экспертных
оценок
Таким образом, задача разработки математических моделей и иерархич
е−
ских многокритериальных эвристических алгоритмов
оптимизации унифицир
ванной ТЛКС
, а также реал
изация их в виде
комплекса
программ, является акт
альной научно
задачей,
решение которой позволяет
создавать
ТЛКС
нефте
ранспортных предприятий
с высокими
технико
эксплуатационны
показател
ями
при
минимуме общих
затрат.
Основные разделы диссертационной
работы соответствуют
Плану фунд
а−
ментальных исследований Российской академии наук на период до 2025 года (
Информатика и информационные технологии по направлениям:
33. «Управл
е−
ние крупномасштабными и сетевыми производственными, транспортными, лог
стич
ескими, энергетическими и другими инфраструктурн
ми системами»,
35.
Когнитивные системы и технологии, нейроинформатика и биоинформатика, с
стемный анализ, искусственный интеллект, системы распознавания образов, пр
нятие решений при многих критериях
36. «Системы автоматиз
ции, CALS
технологии, математические модели и методы исследования сложных управля
щих систем и процессов»
а также
Перечню критических технологий
РФ
(«Те
нологии информационных, управляющих, навигационных с
стем»)
Цель диссертац
ионно
работы
азработать
математическ
модел
иерархические нечеткие
много
колониальные
муравьиные
алгоритмы, а также
комплекс
программ
оптимизации
телекоммуникационной сети
нефте
транспор
ного предприятия
, обеспечивающих за счет
минимизации
затрат и
выс
оких
нико
эксплуатационных характеристик
телекоммуникационной инфраструктуры
снижение объема
сетевого
трафика и уровня энергопотреблени
, что позволит п
высить продолжительность безотказной работы и уменьшит
затраты на
технич
е−
ское
обсл
живание сети.
рактически применить предложенн
математическую
модель
иерарх
ческие
много
колониальные
нечеткие
муравь
ные алгоритмы
многокритериально
оптимизации
структуры ТЛКС
для разработки научно
обоснованных рекоменд
а−
ций
по развитию телекоммуникационной инфрастру
ктуры
ОАО «АК «Тран
с−
нефть»
Для достижения поставленной
цели
необходимо решить
следующи
мосвязанны
задач
Провести анализ
особенностей задачи проектирования и
строительства
оптимальных телекоммуникационных
сетей
нефте
транспортного предприятия,
��3 &#x/MCI; 2 ;&#x/MCI; 2 ;пред
ложить
их математическ
формализаци
с учетом
выявленных огранич
е−
ний
в усл
виях
неопределенности.
Разработать
муравьиный
алгоритм многокритериально
оптимизации
структуры ТЛКС
на основе взвешенного агрегир
вания нечеткой информации о
локальных решениях п
о каждому критерию.
Предложить
муравьиный
алгоритм поиска унифицированного,
мин
мальн
количество
различных типов кабелей
структуры ТЛКС
на основе
определения
компонент связности
графа.
Предложить нечеткий
муравьиный
алгоритм выбора
экономически
оптима
льной структуры ТЛКС
в условиях неопределенности информ
ции.
Разработать архитектуру и режимы функционирования
комплекса
грамм
оптимизации структуры ТЛКС
на основе
использования
предложенных
е−
четких
моделей, методов и алг
ритмов.
Оценить
вычислительную
эффективност
разработанных иерархических
много
колониальных
муравьиных
алгоритмов при решении тестовых задач
опт
мизации структуры
ТЛКС
Разработать научно
обоснованные рекомендации
по развитию телеко
м−
муникационной инфраструктуры предприятия ОАО «АК «Тран
снефть».
Научная новизна.
К наиболее существенным научным результатам, пол
ченным лично соискателем, относятся:
Предложена математическая формализация основных задач развития т
е−
лекоммуникационной
сети
нефтетранспортного предприятия как задач оптимиз
а−
ции
ст
руктуры
ТЛКС
и новых современных цифровых каналов связи с целью д
стижения требуемых
технико
эксплуатационных показателей
и пропускной сп
собности, которая
позволяет учитывать
многокритериальност
выбора раци
нально
трассы
Разработана
иерархическая
мног
колониальная
муравьиная
модель опр
е−
деления
оптимальной
затрат
ам
и унифицированности (однородности)
структ
телекоммуникационной сети, отличающаяся одновременным использованием
двух колоний муравьев с обособленными феромонными тропами для поиска
тим
альных
трасс
прокладки кабелей с учетом
необходим
инвестиционных з
а−
трат и затрат на техническое обслуживание каналов связи, а также для определ
е−
ния возможности использования унифицированного сетевого оборудования с
дальнейшим решением
задачи
двухкритериа
льной оптимизации сети
с примен
е−
нием
обобщенных
муравьиных алгоритмов.
Применение данной модели позволяет решать задачи оптимизации структ
ры развивающейся
ТЛКС нефте
транспортн
предприяти
с учетом
неодноро
ности условий прокладки телекоммуникационных к
абелей, необходимости обе
с−
печения
связей
между большим количеством информационных узлов, а также ц
е−
лесообразности комплексного решения различных распределенных задач
упра
ления
бизнес
процесс
ами
транспортировки нефти и обучения персонала.
Предложен обобща
ющий муравьиный алгоритм
оптимальной
трассиро
ТЛКС
на ориентированном графе
, отлич
ющийся представлением
веса дуги в
графе в виде
феромона
муравья
как
лингвистическ
переменн
нечетк
числа
и применением идентифицируемой операции свертки нечетки
высказ
��4 &#x/MCI; 2 ;&#x/MCI; 2 ;ваний
типа для определения возможности выбора вершины
в маршруте
использованием комплексирования и
формации о количестве феромона, а также
модифицированной процедуры обновления феромонных троп первого и второго
па с учетом найденного тре
тьей колонией муравьев локального решения, что
позволяет увеличить
при поиске поимального маршрута
скорость сходимости
равьиного
алгоритма, а также снизить количество итераций.
Разработан нечетко
продукционный
муравьиный
алгоритм поиска опт
мального по с
тоимости
трассировки
ТЛКС
личающийся
использованием базы
знаний
экспертов
в виде нечетких продукционных правил и
процедуры
нече
логического вывода для оценки возможности перемещения муравьев между ве
шинами
графа
, что позволяет учитывать неопределенн
ость исходной информации
о стоимости строительных работ на различных участках
трассы
сократить кол
чество итераций алг
ритма.
Предложен эвристический
муравьиный
алгоритм выбора унифицирова
ного технологически однородного маршрута прокладки
ТЛКС
, основанн
ый на
поиске минимального маркирова
ного остовного дерева на графе
, отображающем
структуру
ТЛКС
с использованием обособленных феромонных троп для каждо
трассы
, а также модифицированной процедуры определения возможности пер
е−
хода муравьев между вершинами
афа
как функции от количества связанных
компонент графа
, что позволит
увеличить показатели надежности и бесперебо
ности проектируемой
ТЛКС
, а также снизить затраты на её строительство и эк
с−
плуатацию.
Разработан
комплекс
программ
GeoRAS
1.0
оптимизации ст
руктуры
ТЛКС нефте
транспортного предприятия,
реал
зованный в программных средах
Delphi
Matlab
котор
включает
блок
нечетко
логических вычислений и о
работки экспертной информации
, что позволяет
для
повысить
эффективности
процессов проектирования и стр
оительства сетей в условиях н
определенности
исходной инфо
мации.
Теоретическая и практическая значимость результ
тов
работы
Разработанные иерархические
нечеткие
многоколониальные
муравь
ные
алгоритмы для двухкритериального выбора
оптима
льного маршрута пр
кладки
ТЛКС
вносят
определенный
вклад в развитие теории
эвристического п
иска решений.
Предложенный
обобщенный
муравьиный алгоритм
двухкритериальной
оптимальной
трассировки
ТЛКС
может быть практически использован для
опт
мизации ТЛКС
при моде
зации и ра
звити
нефте
транспортных предприяти
Разработанный нечетко
продукционный
муравьиный
алгоритм может
быть практически использован для определения оптимального
по минимуму о
щих
затрат
на трассировку
ТЛКС
в условиях неопределенности исходн
ых данных
на НТП
редложенный
комплекс
программ
GeoRAS
1.0
может быть практич
е−
ски использован для решения задач управления развитием телекоммуникацио
сетей
Методология и методы исследования в диссертации
методы системного
анализа, методы комбинаторной и дискретн
ой оптимизации,
методы теории
а−
��5 &#x/MCI; 0 ;&#x/MCI; 0 ;фов и
нечетких множеств,
таэвристические методы. При разработке
комплекса
программ
применял
ось
ектно
ориентированн
программирование
Положения, выносимые на защиту.
Формализованная постановка задачи
оптимизации
телек
оммуникацио
ной
сети
предприятия как двухкритериальн
ая комбинаторная
задача
Иерархическая м
ного
колониальная
муравьиная
модель
определения
тимальной
по минимуму общих
затрат и унифицированности
структуры
телеко
м−
муникационной сети на основе трех колон
ий муравьев с обособленными фер
монными тропами.
Модифицированный
с использованием процедур нечетко
логического
вывода
муравьиный
алгоритм
определения
опт
мальной структуры ТЛКС
родукционный
муравьиный
алгоритм
оптимизации
трассы
инфр
структурной сети
использованием
базы знаний
экспертов
процедуры
нечетко
логического вывода.
Эвристический
муравьиный
алгоритм
выбора унифицированной
техн
логически однородн
трассы
телекоммуникационной сети, основанный на пои
с−
ке минимального маркированн
го остовного де
рева на графе.
Архитектура и режимы функционирования
комплекса
программ
GeoRAS
1.0
оптимизации ТЛКС НТП
Достоверность
научных результатов, выводов и рекомендаций, сформул
рованных в диссертации, обусловлена использованием достоверных
исходных
данных,
числ
ительны
ми эк
периментами,
а также практической реализацией
алгоритмов
многокритериальной оптимизации
ТЛКС
для решения
задачи
опт
мизации
кабельной сети на ОАО «АК «Транснефть»
Апробация работы.
Основные положения и результаты диссертационной
работы до
кладывались и обсуждались на конференци
VIII Международной
научно
практической конференции «Теория и практика современной науки»
(Москва, 2012),
Международной научно
практической конференции «Приор
тетные научные направления: от теории к практике» (Н
овосибирск, 2012),
III
Международной научно
практической конференции «Европейская наука и техн
логии» (Германия, Мюнхен, 2012),
Международной научно
технической ко
ференции «Энергетика, информатика, инновации
2012» (Смоленск, 2012),
Международной нау
чно
технической конференции
«Информационные технол
гии, энергетика и экономика» (Смоленск, 2013).
Объект исследования:
телекоммуникационн
сет
нефтетранспортных
предприятий.
Предмет исследования:
процедуры трассировки
телекоммуникационн
сет
ей
с использ
ованием математических моделей
Обоснованность
теоретических разработок диссертации определяется
ректным применением методов теории графов и
теории
искусственного интелле
та, теории нечетких множеств и теории принятия решений
согласованностью
вых
пол
ученных
результатов с известными теоретическими положениями.
Реализация результатов работы.
Предложенные методы, алгоритмы и и
струменты
многокритериальной оптимизации
структуры
телекоммуникационной
сети практически использованы для разработки научно
обосн
ованных рекоме
��6 &#x/MCI; 0 ;&#x/MCI; 0 ;даций по созданию системы централизованного сбора и обработки инфо
мации
единого корпоративного хранилища
на предприятии ОАО «АК «Траснефть».
Публикации.
Основные результаты диссертационной работы отражены в
публикациях, в том числе в
статьях в изданиях перечня ВАК.
Общий объ
публикаций составил 6,3 п.л., в том числе лично автору принадлежит
п.л.
СОДЕРЖАНИЕ РАБОТЫ
Во введении
обоснована актуальность решаемой в диссертации новой
научной задачи; определены объект и предмет и
следов
ания; сформулированы
цель и задачи исследования; пр
ведены основные теоретические и практические
результаты ди
сертационной работы.
В первой главе
Анализ современных математических моделей и мет
дов оптимизации структуры телекоммуник
ционн
ых
сет
ей
прове
ден анализ
методов
оптимизации структуры
сет
ей
математически формализована задача
тимизации
трассы
ТЛКС
дана краткая характеристика существующих эвристич
е−
ских алгоритмов и обоснован выбор
муравьиных
алгори
мов для решения задач
оптимизации ТЛКС
В сост
ав
ТЛКС
входят кабельные, радиорелейные, возду
ные, спутниковые
линии связи, сетевые узлы и станции, подви
ая
радиосвяз
В настоящее время
ТЛКС
предъявляются все более высокие требования
по эффективности и наде
ности их функционирования
ожно выделить
следующие задачи разв
тия
ТЛКС
территориально распределенного
Модификация
структуры
существующей
ТЛКС
для
достижения опт
мальных показателей надежности.
Реконструкция существующих линий связи и строительство новых с
временных цифровых каналов
необходимой пр
пускной способност
Развитие
ТЛКС
в направлениях освоения новых мест
рождений.
При
выборе
оптимальной трассы
ТЛКС
целесообразно учитывать такие
критерии, как
общая
стоимость,
а также
степень однородности сети
, что обесп
е−
чивает высокий
уровень стандартизации и существенно облегчает как
проектир
вание
ТЛКС
, так и их эксплуатацию.
Для
решения
этой задачи поиск
оптимал
ной трассы
целесообразно использовать модель ТЛКС в виде графа
, отобража
структуру ТЛКС
. В этом графе
требуется постр
оить маршрут
:(,,...),
eee
как совокупность
дуг
, соединяющих
множеств
вершин, от
ражающих
вычи
с−
лительны
е
узл
сети
мощностью
, при котором достигается минимум
щей
стоимост
прокладки
и функции неоднородности сети
), определяемо
количеством переходов от одного вида кабеля
друго
му
между
смежными
узл
а−
ми
сети
{(),Pr()},
где
min
χχχ
⠀⤀⠀⤀Ⰰ‱ⰀⰀⰀ
SsldlqQe
χχ
=∈

1,
если ()(),
Pr()(), ,
где ()=
0,
если ()()
ii
ii
ii
qeqe
feefe
qeqe
=∈
⠱⤀
где
участок сети,
входящий в маршрут
длина ребра
;
sldl
стоимость прокладки кабеля типа
, как непрерывная функция
на
,2,
ein
fe
функция, определяющая количество переходов от одного вида
кабеля на другой на маршруте
тип
кабеля
, используемого на
ребр
Поставленная в диссертац
задача является
сложной,
поэтому
для её
решения целесообразно использовать эвристические методы,
позволяющие опр
е−
делить приближенные
опт
мальн
ому
решения
. К эффективным и популярным
эврист
ическим методам относятся так называемые метаэвристики
обо
щенные
стратегии поиска оптимума в пространстве решений: метод имитации отжига
simulated annealing
), метод поиска с запретами (
tabu search
),
оптим
зационный
метод муравьиной колонии (
ant colony
optimization
), генетические и эволюцио
ные алгоритмы. Преимущество данных методов
состоит
в том, что они по
воляют
исследовать большее пространство для
поиска
решения близкого к о
тимальному.
Во второй главе
Разработка иерархических многоколониальных м
ра
вьиных алгоритмов двухкритериальной оптимизации структуры тел
е−
коммуникацион
ных
сет
ей
описаны
разработанные
иерархическая
много
кол
ниальная муравьиная модель
обобщенный
муравьиный алгоритм двухкритер
ально
оптимизации структуры
ТЛКС,
нечетко
продукционный
муравьиный
горитм поиска
минимального
по стоимости маршрута
вристический
муравь
ный
алгоритм выбора ун
фицированно
трассы
ТЛКС
Для решения задачи поиска оптимально
й трассы
ТЛКС
буде
использоват
ся алгоритм
двухкритериальной
инимиз
ации
: первый критерий
минимизация
количества переходов от одного вида используемого канала
ТЛКС
на другой;
второй критерий
общая
стоимость
проектирования и строительства
ТЛКС
тором предложена модификация
му
равьиных алгоритмов для решения
двухк
териальной задачи
, которая
состоит
в использ
вании
трех
колоний
муравьев
по
одной для каждого
из
двух
критери
ев
третьей
обобщающей колонии
для
прин
я−
тия
итог
вого
решения по
выбор
оптимальной трассы
Обобщенная
блок
схема
иерархического
много
колониаль
муравьиного алгоритма
оптимизации
минимуму
затрат и унифицированности (однородности)
структуры ТЛКС нефте
ранспортных предпри
тий
представлена на рисунке 1.
Оптимизация осуществляется одновременно по двум критериям на основе
перемещения трех колони
й муравьев. Цель первой колоний
сократить колич
е−
ство переходов от одного вида кабеля на другой (т.е. максимизировать унифиц
рованность и технологическую однородность ТЛКС).

m
n
Определение нечетких множеств и функций принадлежности
Определение функций
принадлежности нечетких
множеств для первой колонии
Определение функций
принадлежности нечетких
множеств для третьей колонии
Определение функций
принадлежности нечетких
множеств для второй колонии
Рисунок 1
Обобщенная блок
схема иерархического
мн
ого
колониального мур
а−
вьиного алгоритма
оптимизации
по минимуму затрат и унифицированности
структуры ТЛКС
НТП
торая колония ищет минимальный по
общей
стоимости проектирования и
строительства маршрут. Обе колонии используют независимые друг от друга ф
е−
ромо
нные тропы:
. На основ
объединения полученных двумя колониями
на каждой итерации
процед
ры поиска
локальных решений
в графе ТЛКС
за счет
взвешенного учета колич
ства феромона, а также весов ребер
первого и
второго типов
третья колония искусственных муравьев осуществляет поиск
тимального
решения поставленной задачи. Для увеличения скорости сходимости
много
колониального муравьиного
алгоритма, а т
акже для учета неопределенн
сти исходной информации количество феромона первого и второго типов, а также
вес
дуг графа
второго типа представлено в виде нечетких
высказываний
Для описания
процедуры
построения решения с использованием третьей
колонии мурав
ьев автором разработан обобщающий муравьиный алгоритм пои
с−
ка
оптимальной трассы
кладки
ТЛКС
, который включает следующие
этапы:
��9 &#x/MCI; 0 ;&#x/MCI; 0 ;1. Первоначальная
трасса
ТЛКС
определяется значениями феромона и веса
первого и второго типа (
,
соответственно) для каждой
дуги
а−
()
ijV
∀∈
Параллельный поиск
муравьями
трасс
на основе информации о кол
честве феромонов
и весах
. Муравей на каждо
шаге прокладки
трассы
в графе
выбирает следующую присоединяемую вершину
по правилу ра
с−
чета
вел
чины нечеткой
возможности
перехода
1(1)2
1(1)2
1(1)2
1(1)2
[()()][()()]
([()()][()()])
ωωα
ωωβ
ωωα
ωωβ
µµηη
µµηη
−−
−−
⊗⊗⊗
⊗⊗⊗
⠲⤀
где
количество первого феромона на
дуге
;
ij
количество второго ф
е−
ромона на
дуге
;
привлекательность п
рехода в вершину
из вершины
по кр
итерию однородности с
ти;
привлекательность перехода в вершину
из
вершины
по критерию стоимости
трассы
(нечеткая величина, обратная стоим
сти строительства сети на участке
ij
);
[0,1]
весовой коэффицие
нт, отража
щий относительную значимость критерия стоимости маршрута;
множество
вершин
в графе
, которые муравей
еще не посетил, но они доступны для перех
да на т
кущей итерации.
Поскольку количество феромона
первого и второго
типов
вес ребра
рого типа задается нечеткими числами

ij
, то в формуле (2) алгебраич
е−
ские операции заменены на операции над нечеткими
высказываниями
(умнож
е−
ние, возведение
в ст
пень, деление). С
целью снижения объема вычислений для
представления
элементов
нечетких
множеств
используется форма ан
литической
аппроксимации с помощью так называемых (
функций,
когда
алгебраические
операции над
нечеткими
числами определяются на
основе значений соответств
ющих параметров их (
представлений. Умножение двух нечетких
высказыв
а−
ний
типа
> и
> является нечетким
сказыванием
,,
LRLRLR
ABCa
⋅==<>
определяемым по фо
мул
ам
1212211221
aaaaaaa
αααβββ
=⋅=⋅+⋅=⋅+⋅
⠳⤀
На каждой итерации
обобщающего муравьиного
алгоритма
искусстве
мураве
стро
т решени
задачи, двигаясь по графу
структуры ТЛКС,
нач
ная от исходной вершины
согласно правилу (2).
По окончании каждой
итерации
после того, как все ис
кусственные м
равьи завершат построени
маршрута
происх
дит переопределение
количества
феромона
первого и второго уровня

(1)(1)()()
ttt
µρµµ
+=−⊕∆
⠀㄀⤀⠀㄀⤀⠩⠩
ttt
µρµµ
+=−⊕∆
⼀⠀⤬ 
если (,)(),
0,
в противном случае
ll
QPtijTt
⠴⤀
где
коэффициент и
спарения феромона,
суммарное
изменение уровня
феромона на
дуге графа
общий маршрут, построенный муравьем
на
итерации
относ
тельная оценка качества найденного м
аршрута
константа
, показывающее общее количество феромона у муравья
Величина
позволяет сопоставлять полученные на различных итерациях
трассы
между с
бой, определяя, таким об
разом, наиболее рациональный
()(),
ijTt
PtSn
=⊗
⠵⤀
где
ijTt
общая
стоимость
(нечеткое
высказывание
кладки
трассы
количество переходов от одной техн
логии
передачи данных
на другую при
построении
трассы
Обоб
щающий муравьиный алгоритм поиска оптимальной
трассы
ТЛКС
прерывает свою работу после выполнения зада
ного заранее числа итераций (как
правило, не менее 100), что позволяет получить
оптимальный
маршрут прокладки
ТЛКС
Задача
первой колонии муравьев
состоит
поиск
е унифицированной
ма
симально однородной
ТЛКС
с учетом использ
вания кабелей различного вида
может быть представлена в виде
поиска минимального
маркир
ванного остовного
дерева на графе.
Для
решения поставленной задачи каждой метке
дуги
множества
поставлена в соответствие од
из возможных
способов
передачи данных:
оптоволоконный кабель, спутниковая связь, линии фиксированной телефонной
связи, радиоканалы п
движной мобильной связи и т.д.
вристичес
кий
муравьиный
алгори
выбора унифицированно
хнолог
чески однородно
трассы
ТЛКС
основан на
пользовани
для каждой метки
обособленно
значени
ромона
Тогда на каждой итерации муравей
строит решение, состоящее из
множеств
меток
при это
нечеткое высказыв
а−
добавления
метк
определяется
по формуле
(',),
если (')('),
0,
в остальных случаях
pLlcLlcL
⠶⤀

'{(')(')}
(',)
(',)
(',')
llLcLlcL
pLl
∈∈∪<
где
(')
cL
количество
компонент связности
графа
множество
дуг
меткой из множества
аланс между информацией о количестве феромона
(',)
весом
дуги
(',')
контролируется параметрами α и β. Пусть
(')
ELE
подмножество
дуг
отмеченных меткой
, и пусть
(')
cL
обозначает количество связанных комп
нентов подграфа
'(,('))
GVEL
Вес
дуги
равен
(',)(')(').
LlcLcLl
=−∪
⠷⤀
Обновление количества феромон
для каждой метки
(1)(1)()1
для
ll
tlL
µρµ
+=−+∀∈
⠸⤀
Для получени
я решения с допустимой величиной относительной погрешн
сти
(не более 5% при решении тестовых задач)
, количество итераций алгоритма
должно быть не менее 100,
при этом параметры
определяются экспериме
тально.
Нечетко
продукционный а
лгоритм работы втор
ой колонии муравьев
направлен на поиск минимального по
общей
стоимости маршрута
ТЛКС
Анализ
решаемой задачи позволил сделать в
вод, что для повышения эффективности и
обоснованности решений целесоо
бразно
учитывать
неопределенность исходной
формации
Обща
стоимост
трассы
передачи данных
между вершинами
графа
которая задает вес
дуги
графа,
может быть оценена
с помощью
теории нечетких и
интервальны
величин
. Обработка таких данных может быть осуществлена с и
с−
пользованием
методов
нечетко
логического
вывода
, который дает во
можность на
основе нечетких экспертных оценок перейти к формальным правилам и описан
ям. Таким образом, на основ
изложенного
, для
поиска рационально
трассы
ТЛКС
с и
пользованием муравьиных
алгоритмов
разработан
нечетко
продукционный
эвристический
алгоритм,
этапы которого подробно описаны в
диссертации.
В третьей главе
Методика имитационного моделирования и вычисл
тельные эксперименты по оценке эффекти
ности алгоритмов оптимизации
структуры телекоммуникационн
сет
ей
представлены ре
зультаты имитац
онного моделирования
разработанных
муравьиных алгоритмов
оптимизации
трассы
ТЛКС
проанализированы результаты вычислительных экспериментов
по
оценке эффективности разработанных алг
ритмов
Оценка эффективности иерархических многоколониальн
ых муравьиных
горитмов
оптимизации структуры
телекоммун
кационной сети осуществлялась
с
помощью
вычислительных экспериментов с тестовыми задач
ми и
сопоставления
полученных данных с резул
ьтатами работы других эвристических и экспер
ных
алгоритмов
Для о
ценки эффективности н
ечетко
продукционн
ого
муравьин
ого
алгори
оптимизации ТЛКС
по
минимуму
общей стоимости проведены вычислител
��12 &#x/MCI; 0 ;&#x/MCI; 0 ;ные эксперименты
для задач с небольшим количеством связываемых
в графе
лов. Это позвол
ло сравнить результаты, полученные
помощью трех различных
алгоритмов:
полного перебора
стандартного
муравьиного алг
ритма
и нечетко
продукционного муравьиного алгоритма.
Результаты вычислительных экспер
ментов представлены в табл
це 1.
Вычисления производились на персональном компьютере
с двухядерным
процессором с тактовой частотой 2,67 ГГц.
В качестве сопоставляемых параме
ров были выбраны
среднее
время работы (
в мс
средняя
стоимость маршрута (
условных ед
ницах
Таблица 1
Результаты
анализа эффективности
разработанных иерархи
ческих
многоколониальных муравьиных
алгоритмов
Количество
узлов
Алгоритм
полного пер
бора
Муравьиный алг
ритм
Нечетко
продукционный
муравьиный алг
ритм
, мс
, у.е.
, мс
, у.е.
, мс
, у.е.
Как видно из
таблицы
для задач малой размерности классический мур
а−
вьиный алгоритм и раз
работанный автором нечетко
продукционный муравьиный
алгоритм обеспечивают получение точных решений
, совпадающих с
трассами
получе
ными полн
перебор
за меньшее время.
При решении задач средней
размерности (количество узлов
в графе
более 10) сравнить к
ачество решений, п
лученных муравьиными алгоритмами и полн
перебор
затруднительно
за
экспоненциальной зависимости времени работы последнего от количества вхо
ных данных.
В целом, разработанный нечетко
продукционный муравьиный алг
ритм позволяет нах
одить маршрут на графе за меньшее время
. При этом качество
трассы
, полученное муравьиными алгоритмами,
практически одинаково с незн
а−
чительным преимуществом
предложенного автором нечетко
продукционного м
равьиного алгоритма
В то же время
данное
пре
мущест
во увеличивается с р
стом
колич
ства узлов
граф
Оценка эффективности
обобщающего муравьиного алгоритма
двухкритер
альной
оптимизации ТЛКС осуществлялась
на основе сравнения решения
тест
вых задач малой размерности
по
разработанн
ому
автором алгоритм
алгоритму
полного п
ребора. На рисунке 2а представлена исходная тестовая задача поиска
оптимального
по
минимуму
стоимости и унифицированности
маршрута
а р
сунк
2б представлен
решени
, получе
с использованием
алгоритма
полного
перебора и обобща
щего
муравьиного алгоритма.
В показанном примере маршруты, полученные с использованием метода
полного перебора и обобщенного муравьиного алгоритма, совпадают, что по
тверждает работоспособность алгоритма и обосновывает возможность его прим
е−
нения для задач сред
ней и большой размерности.

Рисунок 2
Пример решения задачи поиска оптимального по
минимуму
стоим
сти и унифицированности маршрута
В четвертой главе
Разработка и практическое прим
нение компле
кса
программ оптимизации телекоммуникационных сетей
GeoRES
1.0
пре
ставлена архитектура
комплекса
программ
GeoRES
1.0
двухкритериально
опт
мизации трассы
ТЛКС
обоснован выбор инструментальных программных
средств для разработки
комплекса
программ
описа
ны режимы функциониров
а−
ния и методика применения
GeoRES
1.0
пре
ставлены научно
обоснованные
рекомендации по применению
комплекса
программ
для выбора рациональной
структуры
ектируемой
ТЛКС
предприяти
ОАО «АК «Транснефть».
редложенны
алгоритм
опти
мизации трассы
кабельной
ТЛКС
был
практически реализованы в
виде комплекса
программ «
GeoRES
1.0
», использу
е−
мом для
управления телекомм
никационной инфраструктурой.
Данный комплекс
позволяет
увеличить скорость процессов
планировани
структуры ТЛКС
рассч
ывать точную стоимость
их строительства с использованием геоинформацио
ных
систем
и электронных картографических данных
с учетом направлений, пр
ходимости и удаленности объектов друг от друга.
Архитектура
комплекса
грамм
оптимизации структуры ТЛКС
постр
оена по модульному принципу
(см.
рисунок 3)
с использованием среды программирования
Delphi
и пакета программ
Matlab
В качестве системы управления базами данных выбрана
Microsoft
SQL
Server
Разработанные алгоритмы практически использованы для создания на
учно
обоснованных рекомендаций по проектированию и строительству телекоммун
кационной инфраструктуры ОАО «АК «Транснефть». Особое внимание компания
«Транснефть» уделяет реализации Программы по проектированию и строител
ству транспортной сети высокоскоростн
ых каналов связи для создания единой
информационной системы (ЕИС) ОАО «АК «Транснефть», позволяющей объед
нить информационные системы всех организаций «Транснефть» в единое инфо
мацио
ное пространство. Важным этапом построения высокоскоростной Единой
Инфор
мационной Системы ОАО «АК «Транснефть» является строительство в
2015
2018 гг. волоконно
оптической л
нии связи на участке Ухта
Ярославль,
общей протяженностью 1195 км. В рамках данного проекта планируется объед
нить 25 узлов связи.

Рисунок
Блок
схема архитектуры
комплекса
программ
GeoRES
1.0»
оптим
зации
телекоммуникационной сети
С использованием
комплекса
програм
GeoRES
1.0»
спроектирована о
тимальная структура ТЛКС (см.
рисун
Рису
нок
Граф оптимальной ТЛКС
на участке Ухта
славль
��15 &#x/MCI; 0 ;&#x/MCI; 0 ;Полученная структура сети
(см. рисунок 4
является одн
родной, поскольку
для её построения использовался один вид кабеля
волоконно
оптический.
щая
стоимость реализации проекта
по
трассе
составил
а
1,195 млрд
. руб.
Использование разработанных иерархических многоколониальных алг
ритмов муравьиных колоний выбора
оптимальной трассы
телекоммуникационной
сети позволило сократить затраты материальных,
трудовых
, финансовых, време
ных ресурсов на реализаци
ю проекта, что подтверждается
сопоставлением с да
ными исходной сметной документации. Первоначальный план предусматривал
объем инвестиций в размере 1
млрд
. руб.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
Математически формализована
задач
развития тел
коммуникационно
инфраструктуры нефтегазотранспортного предприятия как
полная
задач
многокритериально
й оптим
зации структуры ТЛКС
, что позволило обосновать
необходимость использования эвристических алгоритмов и сформулировать тр
е−
бования к их модификации.
Предложена
иерархическая многоколониальная муравьиная модель
определения оптимальной по
минимуму затрат
и унифицированности (одноро
ности) структуры телекоммуник
ционной сети
, отличающаяся использованием
трех колоний интеллектуальных муравьев с обособленными феромонн
ыми тр
пами
, что
позволяет
решать задачи оптимизации структуры
ТЛКС
крупн
ых
нефтетранспортных предприятий.
Предложен
обобщающий муравьиный алгоритм оптимальной
расс
ровки ТЛКС
, отличающийся
возможностью учета неопределенности исходной
информации
Разрабо
тан
нечетко
продукционный муравьиный алг
ритм
оптимизации
по стоимости
трассы
ТЛКС
, который отличается использованием базы знаний
экспертов
в виде
нечетких пр
дукционных правил
Предложен
эвристический муравьиный алгоритм выбора унифицир
ванно
технологиче
ски однородно
трассы
ТЛКС
, основанный на поиске мин
мального маркированного остовного дерева
графе
, что позволяет
повысить
нико
эксплуатационные характеристики проектируемой сети
Разработаны архитектура и режимы функционирования
комплекса пр
грамм «
GeoRAS
1.0
оптимизации структуры ТЛКС нефтетранспортного пре
приятия
Предложены научно
обоснованные рекомендации по
оптимизации
ТЛКС
предприяти
ОАО «АК «Транснефть».
По мнению автора, настоящая диссертация является зако
ченной научно
квалификационной р
аботой, которая представляет собой совокупность научно
обоснованных инженерно
технических решений
по созданию ТЛКС нефтетран
с−
портных предприятий с высокими технико
эксплуатационными показат
лями при
минимуме общих затрат
��16 &#x/MCI; 0 ;&#x/MCI; 0 ;Основные работы, опубликованные п
о теме диссертации
В изданиях перечня ВАК
Глушко С.И., Иванова И.В. Нечеткие муравьиные алгоритмы планир
вания оптимального маршрута прокладки трубопроводного транспорта // Эле
тронный научный журнал
Нефтегазовое дело
. 2012. №6. С. 120
125.
Глушко С.И.,
Какатунова Т.В. Нечеткая модификация алгоритма мур
а−
вьиных колоний // Научное обозрение. 2013. №1. С.377
381.
Дли М.И., Гимаров В.В., Глушко С.И. Применение алгоритмов муравь
ных колоний при управлении сложными пр
ектами // Транспортное дело России.
2012. №
4. С. 51
54.
Дли М.И., Гимаров В.В., Глушко С.И. Конфигурирование информац
онных и транспортных сетей в условиях неопределенности // Прикладная инфо
матика. 2012. №
). С.
М.И. Дли, В.В. Гимаров, С.И. Глушко.
Алгоритмы по
держки принятия
решений
по управлению инфраструктурными проектами на основе моделей мур
а−
вьиных колоний //
Весник СГТУ. 2012. №1 (64). Выпуск 2. С. 423
427.
Глушко С.И., Бояринов Ю.Г.
Полумарковские модели систем с нечетк
ми п
араметрами
// Программные продукты и с
стемы. 2012. №2
(98)
. С.
146
149
Глушко
С.И.
ногоколониальная муравьиная модель
тимизации т
е−
коммуникационной сети
//
Научное обозрение. №7. С.
В других изданиях
Глушко С.И.,
Мешалкин
В.П.
Интеллектуальный метод выбора опт
мального маршрута формирования инфраструктуры предприятия //
Экономика.
Менеджмент. Логистика. Корпор
тивные информационные системы.
Межвуз.
сб. науч. тр. (Вып. 3)
Смоленск: Смоленский ЦНТИ, 2010.
С. 47
49.
Глушко С
.И., Образцов А.А., Кузавко А.С. Применение алгоритма мур
а−
вьиных колоний для решения задач оптимизации на графе // Приоритетные нау
ные направления: от теории к практике: Сб. тр. II Межд. научно
практ. конф.
Новосибирск, 2012. С.67
71.
Dli M.I., Glushko
S.I., Ivanova I.V. Ant algorithms as a tool of infrastructure
project management // European Science and Technology:
materials of the III
research
and practice
conference.
Publishing office Vela Verlag Waldkraiburg. Munich
Germ
a-
2012.
127
129
Гимаро
в В.В., Глушко С.И., Образцов А.А. Алгоритм учета неопред
е−
ленности численных характеристик инфраструктурного
проекта //
Информацио
ные технологии, энергетика и экономика:
Сб.тр.
нар. Науч.
техн. конф. Т.
2. Смоленск:
Универсум
, 2012. С.14
Глушко С
.И.
Многоколониальные алгоритмы муравьиных колоний для
решения двухкритериальной задачи выбора маршрута
Информационные техн
логии, энергетика и экономика:
Сб.тр.
Междунар. Науч.
техн. конф.
Т. 2. См
ленск:
Универсум
, 2013. С.25
Мешалкин В.П., Глу
шко С.И. Иерархические нечеткие многоколониал
ные муравьиные алгоритмы и комплекс программ оптимизации телекоммуникац
онных сетей нефтетранспортных предприятий. Смоленск: Универсум, 2013. 142 с.

Приложенные файлы

  • pdf 5952612
    Размер файла: 650 kB Загрузок: 0

Добавить комментарий