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



Скачать 227.28 Kb.
страница1/3
Дата04.07.2013
Размер227.28 Kb.
ТипАвтореферат
  1   2   3


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


Ястребинская Дина Николаевна

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

Специальность: 05.13.17- Теоретические основы информатики

АВТОРЕФЕРАТ

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

кандидата технических наук


Таганрог - 2010

Работа выполнена в Технологическом институте Федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет»


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

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

Боженюк Александр Витальевич


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


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

Ромм Яков Евсеевич
доктор технических наук, доцент

Чернов Андрей Владимирович


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

Государственное образовательное учреждение высшего профессионального образования «Ростовский государственный университет путей сообщения» (РГУПС), г. Ростов-на-Дону


Защита диссертации состоится «__» _________2011г. в 1420 на заседании диссертационного совета Д 212.208.21 при Южном федеральном университете по адресу:

347928, ГСП-17А, Ростовская область, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148
Автореферат разослан «___» ___________2011 г.

Ученый секретарь

диссертационного совета

д.т.н., профессор Чернов Н.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. В настоящее время бурное развитие информационных технологий обусловило использование теории нечетких множеств и нечеткой логики в качестве инструмента для решения самого широкого круга задач принятия решений в условиях недостаточной определенности и субъективности информации об условиях окружающей среды. К таким задачам относятся проблемы нахождения и увеличения живучести транспортных сетей, нахождение максимальных потоков с заданной степенью живучести, а также задачи размещения центров обслуживания с наиболее возможной степенью живучести. Для транспортных систем различного назначения живучесть имеет важное значение для соответствующего управления и принятия решений при сбоях в работе или плохом функционировании.
Рассмотрение этих задач в нечетких условиях, когда некоторые параметры сети заданы неточно, или приблизительно, позволяет находить такие решения, получение которых традиционными (четкими) методами было бы затруднительно или вообще не возможно. Детальное изложение особенностей, характерных свойств, отличающих одни объекты и связи между объектами транспортной сети от других, а также использование относящихся к ним числовых данных, дают возможность представления исходной информации в нечетком виде. Следовательно, задачи формализации, моделирования и анализа транспортных сетей в нечетких условиях являются актуальными.

При решении данных задач используются элементы теории графов, нечетких множеств, представленные работами Л. Заде, Р. Беллмана, А.Н. Мелихова, Л.С. Берштейна, А.Н. Борисова, Н. Кристофидеса, А. Кофмана, Т. Саати, Х.-Ю. Циммерманна и других авторов. Работы перечисленных ученых относятся к ряду фундаментальных работ по теории графов, нечеткой логике и теории нечетких множеств, положенных в основу исследований, проводимых в данной работе.

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

Поставленная цель определяет следующие основные задачи диссертационного исследования:

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

2. Разработка и исследование методов решения задач живучести транспортной сети. В частности:

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

б) разработка метода увеличения степени живучести транспортной сети представленной нечетким графом второго рода;

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

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

4. Разработка и исследование метода нахождения центров обслуживания на нечетких интервальных графах.

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

Методы исследования основаны на применении теории нечетких множеств, теории графов и нечеткой логики.

Научная новизна диссертационной работы:

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

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

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

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

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

Практическая значимость. Прикладными результатами являются разработанные в диссертационной работе:

1. Алгоритм и программа нахождения степени живучести нечетких графов второго рода.

2. Алгоритм и программа увеличения степени живучести нечетких графов второго рода.

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

4. Алгоритм и программа нахождения центров обслуживания на нечетких графах второго рода.

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

6. Определение максимального потока в транспортной сети с заданной степенью живучести.

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

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

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

- при выполнении гос.бюджетной НИР НТЦ «Интех» ЮФУ № гос.регистрации 01200504744;

- при выполнении гранта РФФИ № 10-01-00029а.

Апробация работы. Основные результаты работы представлены на региональной научно-практической конференции «Информационные технологии в профессиональной деятельности и научной работе» (Йошкар-Ола, 2006 г.), на 18-й международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании (МК-58-96)» (Пенза, 2006 г.), на международной научно-технической конференции «Интеллектуальные системы» (AIS’06) и «Интеллектуальные САПР»(CAD-2006) (с.Дивноморское, 2006 г.), на VIII всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2006 г.), на IV всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2006 г.), на IV Международной научно-технической конференции «Искусственный интеллект в XXI веке. Решения в условиях неопределенности» (Пенза,2006), на международной научно-технической конференции «Интеллектуальные системы» (AIS’07) и «Интеллектуальные САПР» (CAD-2007) (с.Дивноморское, 2007 г.), на VIII Всероссийском симпозиуме по прикладной и промышленной математике (Сочи-Адлер, 2007 г.), на IX Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2008 г.), на IX Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (Таганрог, 2008 г.), на 15th Zittau East-West Fuzzy Colloquium (Циттау, Германия, 2008 г.), на научно-практической конференции студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (Коломна, 2009 г.), на международной научно-технической конференции «Интеллектуальные системы» (AIS’09) и «Интеллектуальные САПР» (CAD-2009) (с.Дивноморское, 2009 г.), на 17th East-West Zittau Fuzzy Colloquium (Циттау, Германия, 2010 г.)

Публикации. Результаты диссертации отражены в 22 печатных работах, в том числе в 8 работах, опубликованных в изданиях, рекомендованных ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, выводов по главам, заключения, списка литературы и приложений. Работа выполнена на 161 странице машинописного текста, содержит 46 рисунков и 6 таблиц. Список использованной литературы включает 113 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертационной работы, сформулированы цели и задачи исследования, охарактеризованы научная новизна работы, ее практическая ценность, реализация и апробация результатов работы, дано краткое содержание структуры диссертации.

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

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

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



Рис.1. Нечеткий граф второго рода

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



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

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

, .

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

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

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

В данной главе также рассмотрены методы увеличения степени живучести нечеткого графа первого и второго рода относительно такого важного фактора, как стоимость. В данном случае стоимость увеличения живучести ветви и вершины на некоторую величину (например, на =0,1) есть некоторое неотрицательное число. Тогда задачи увеличения степени живучести нечеткого графа первого и второго рода относительно фактора стоимости могут быть сформулированы следующим образом: увеличить степень живучести нечеткого графа до величины с минимальными суммарными затратами. Формальный алгоритм решения задачи является обобщением метода увеличения степени живучести нечеткого графа второго рода.
  1   2   3

Похожие:

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

Разработка и исследование методов и алгоритмов определения живучести транспортных сетей в геоинформационных системах на основе нечетких графов iconСложность алгоритмов. Уметь оценивать сложность всех алгоритмов и программ
Графы. Основные способы хранения графов, их преимущества и недостатки, количество необходимой памяти. Сложности алгоритмов над разными...
Разработка и исследование методов и алгоритмов определения живучести транспортных сетей в геоинформационных системах на основе нечетких графов iconИсследование и разработка некоторых графических алгоритмов
Шайдуров А. Г. Исследование и разработка некоторых графических алгоритмов. Квалификационная работа на степень магистра наук по направлению...
Разработка и исследование методов и алгоритмов определения живучести транспортных сетей в геоинформационных системах на основе нечетких графов iconИсследование и разработка алгоритмов обобщения на основе теории приближенных множеств
Специальность 05. 13. 11 – Математическое и программное обеспечение вычислительных машин, комплексов
Разработка и исследование методов и алгоритмов определения живучести транспортных сетей в геоинформационных системах на основе нечетких графов iconЛабораторная работа №1 Тема лабораторной работы: Исследование способов формирования нечетких множеств и операций над ними
Изучение методов построения нечетких множеств с использованием различных типов функций принадлежности. Ознакомится с наиболее распространенными...
Разработка и исследование методов и алгоритмов определения живучести транспортных сетей в геоинформационных системах на основе нечетких графов iconИсследование и разработка методов защиты прав собственности на изображения на основе использования цифровых водяных знаков в условиях коалиционных атак 05. 12. 13 Системы, сети и устройства телекоммуникаций
Исследование и разработка методов защиты прав собственности на изображения на основе использования цифровых водяных знаков в условиях...
Разработка и исследование методов и алгоритмов определения живучести транспортных сетей в геоинформационных системах на основе нечетких графов iconАлгулиев Р. М., Оруджов Г. Г., Сабзиев Э. Н., Панахов Н. А., Расулова Н. В., Алиева А. А
Целью работы является разработка алгоритмов для определения и устранения ошибок и неточностей векторной карты рельефа местности с...
Разработка и исследование методов и алгоритмов определения живучести транспортных сетей в геоинформационных системах на основе нечетких графов iconАлгебра связных графов и проектирование топологии компьютерных сетей
Описывается один из возможных вариантов алгебры регулярных графов и ее приложения к проектированию и исследованию свойств топологии...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org