Введение к работе
Актуальность темы. В практике жизнедеятельности человека почти всегда возникают задачи выбора оптимальной альтернативы и последующее принятие решений. В самых простых случаях, когда рассматриваемые альтернативы оцениваются одним показателем, осуществить выбор возможно интуитивно, без использования математического аппарата. Если же рассматриваемые альтернативы оцениваются несколькими показателями качества, то задача значительно усложняется – возникает ситуация многокритериальности. Для нахождения многокритериального оптимума в настоящее можно воспользоваться математическим арсеналом теории многокритериальной оптимизации. Более сложные задачи многокритериального выбора возникают в условиях недетерминированности исходных данных. Под недетерминированностью исходных данных в контексте настоящей диссертационной работы следует понимать описание весов ребе графа тремя видами неопределенности: интервал значений, нечеткое множество, временной ряд. При осуществлении выбора и принятии решения в таких многокритериальных задачах возникает ряд сложностей: сравнение величин с неточными и размытыми границами числовых значений параметров, обобщение понятия оптимальной альтернативы, разработка методов отыскания оптимальной альтернативы. Актуальность диссертационного исследования обусловлена необходимостью разработки вычислительных методов нахождения оптимальной по нескольким критериям альтернативы в задачах на графах с весами ребер в временных рядов, нечетких или интервальных чисел.
Положения работы поддержаны грантами Российского фонда фундаментальных исследований: «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности», «Структурирование, выявление несоответствий и прогнозирование эволюционных дискретных процессов и систем при наличии долговременных корреляций».
По теме диссертационной работы выполнены следующие проекты Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы»: «Разработка вычислительных методов структурирования, выявления несоответствий и прогнозирования эволюционных дискретных процессов с долговременными корреляциями в системах обработки информации» (2010-2012), «Разработка технологий проектирования эволюционирующих информационных систем на основе моделирования регламентов в специальных средах» (2010-2012).
Объектом исследования являются слабо формализуемые системы с неточными и размытыми границами числовых значений параметров, математическое описание которых представляет собой задачи многокритериального выбора на графах в условиях недетерминированности исходных данных.
Предметом исследования являются вычислительные методы нахождения многокритериального оптимума в задачах на графах с недетерминированными весами ребер.
Степень разработанности темы исследования. Задачам математического моделирования систем в условиях детерминированности исходных данных посвящены публикации ученых: Самарский А.А., Партыка Т.Л., Попов Э.В., Мышкис А.Д., Плотинский Ю.М., Сергиенко И.В. и др.
Развитию методов многокритериальной оптимизации и принятия решений посвящены научные труды отечественных и зарубежных авторов: Саати Т., Прокушева А.П., Прокушев Я.Е., Подиновский В.В., Ногин В.Д., Пападимитриу Х., Стайглиц К., Моисеев Н.Н., Михалевич B.C., Трубин В.А., Шор Н.З., Майника Э., Львович Я.Е., Чернышева Г.Д., Каширина И.Л., Лесин В.В., Лисовец Ю.П., Ларичев О.И., Иванов Б.Н., Дубов Ю.А., Травкин С.И., Якимец В.Н.
В развитие теории моделирования нечетких и интервальных данных внесли существенный вклад научные исследователи: Заде Л., Зайченко Ю.П., Нариньяни А.С., Орловский С.А., Мелькумова Е.М., Левин В.И., Куржанский А.Б., Курдюмов И.В., Мосолова М.В., Назайкинский В.Е., Кофман А., Корченко А.Г., Ким-Гю-Пхир, Калмыков С.А., Шокин Ю.И., Юлдашев З.Х., Дробязко О.Н., Нефедов С.Ф., Дилигенский Н.В., Дымова Л.Г., Севастьянов П.В., Берштейн Л.С., Мелихов А.Н., Боженюк А.В. и др.
Анализу и прогнозированию временных рядов посвящено огромное количество публикаций, среди которых можно выделить публикации авторов: Мандельброт Б.Б., Отнес Р., Петерс Э., Осборн М., Песаран М., Пригожин А.И., Пуарье Д., Мартино Дж., Хакен Г., Сигел Э., Хейс Д., А. Хоскинг, Базаров В.А., Громан В.Г., Канторович Л.В., Кондратьев Н.Д., Новожилов В.В., Перепелица В.А., Фельдман Г.А., Шаталин С.С. и др.
Прагматическая проблема. Необходимость решения класса задач многокритериального выбора на графах, состоящее в структурировании неопределенностей весов ребер и получение более точных количественных оценок рассматриваемых альтернатив при снижении вычислительной сложности.
Научная проблема. Теоретическое обоснование применения методов многокритериальной оптимизации и принятия решений, нечеткой и интервальной арифметики и разработки вычислительных методов нахождения достоверного многокритериального оптимума в задачах выбора на графах с недетерминированными весами ребер.
Целью настоящей диссертационной работы является повышение точности и снижение вычислительной сложности получения предпочтительной альтернативы в многокритериальных задачах выбора на графах с недетерминированными весами ребер.
Научная задача состоит, во-первых, в разработке вычислительных методов структурирования и моделирования недетерминированных исходных данных, во-вторых, в развитии теории многокритериального выбора на графах для случая неоднозначно определенных исходных данных.
Поставленная цель требует решения следующих частных научных задач:
– разработка метода нахождения многокритериального оптимума в задачах многокритериального выбора на графах в условиях недетерминированности весов ребер;
– разработка математических моделей для структурирования неопределенностей исходных данных в виде нечетких множеств, позволяющих при реализации арифметических операций, с одной стороны, оперировать как носителем нечеткого множества, так и степенью принадлежности, с другой стороны, при многократном использовании не приводящих к увеличению количества компонентов нечетких множеств;
– разработка методов сравнения интервалов с вложенными границами и нечетких множеств с пересекающимися границами носителя без использования стандартной процедуры приведения к -уровневому виду;
– теоретическое обоснование выбора классификации временных рядов по признаку «Персистентность значений»;
– разработка прогнозных моделей для персистентных временных рядов, особенностью которых является долговременная коррелированность значений, нестационарность и неподчинение нормальному закону распределения;
– развитие методов выбора предпочтительной альтернативы для задач многокритериального выбора на графах с детерминированными весами ребер.
Научная новизна диссертационного исследования состоит в разработке методологического и инструментального обеспечения для моделирования недетерминированности исходных данных и нахождения многокритериального оптимума в задачах на графах с весами ребер в виде интервалов, нечетких множеств или временных рядов.
В области математического моделирования:
-
математическая модель сведения размерностей нечетких множеств к единой величине, позволяющая реализовывать более экономные арифметические операции по принципу «векторное получение носителя и теоретико-множественные операции над степенью принадлежности» (с. 80-98);
-
математический метод сравнения нечетких множеств с использованием дефазификации по центрам тяжести носителя и функции принадлежности, являющийся менее трудоемким и позволяющий расширить область сравнимости нечетких множеств с пересекающимися и вложенными носителями (с. 98-102);
-
математический метод сравнения вложенных интервалов, использующий взвешенную свертку границ интервала, и, являющийся развитием метода сравнения в центральном смысле (с. 102-107);
-
математический метод вычисления глубины долговременных корреляций в персистентных временных рядах, базирующийся на свойстве фрактальности, для определения длины конфигурации с памятью и осуществления настройки клеточно-автоматной прогнозной модели (с. 110-111);
-
методы преобразования числовых временных рядов в лингвистические временные ряды: огибающих ломаных, трендовых коридоров, локального размаха (с. 123-129);
-
математическая модель прогнозирования персистентных временных рядов на базе линейных клеточных автоматов для надежного прогнозирования временных рядов с признаками фрактальности: наличие долговременных зависимостей значений, неподчинение нормальному закону, частая смена тренда, нестационарность (с. 122-135);
-
математические методы получения оценок «суммарный эффект» и «оценка по наихудшему» для допустимых решений задачи многокритериального выбора на графах со структурированными исходными данными (с. 155-181);
-
адаптированный метод Парето для реализации многокритериального сравнения допустимых решений с количественными оценками в виде нечетких множеств и интервалов с пересекающимися и вложенными границами (с. 181-183).
-
асимптотически точный и статистически эффективный алгоритмы для подкласса задач покрытия граф звездами одного типа с весами ребер в виде интервалов равной ширины (с. 230-238).
В области численных методов:
-
численный метод сведения размерностей нечетких множеств к единой величине для реализации арифметических операций по принципу «векторное получение носителя и теоретико-множественные операции над степенью принадлежности» (с. 197-198);
-
численный метод реализации дефазификации по центрам тяжести носителя и функции принадлежности для сравнения нечетких множеств с пересекающимися и вложенными носителями (с. 198);
-
численный метод сравнения вложенных интервалов на базе взвешенной свертки границ интервала (с. 199);
-
численный метод вычисления глубины долговременных корреляций в персистентных временных рядах (с. 199-200);
-
численные методы преобразования числовых временных рядов в лингвистические временные ряды: огибающих ломаных, трендовых коридоров, локального размаха (с. 201-204);
-
численный метод прогнозирования персистентных временных рядов базе клеточно-автоматной прогнозной модели (с. 204-206);
-
численный метод адаптированного метода Парето для многокритериального сравнения альтернатив на графах со структурированными весами ребер (с. 207-209).
В области комплексов программ разработан комплекс проблемно-ориентированных программ «Многокритериальная оптимизация на графах в условиях стохастической неопределенности исходных данных», позволяющий производить расчет количественных оценок допустимых альтернатив на основе предложенных методов и моделей в условиях недетерминированности весов ребер графа и осуществления дальнейшего многокритериального сравнения (с. 240-267).
Теоретическая и практическая значимость работы. Разработанный метод решения задач многокритериального выбора на графах в условиях недетерминированности исходных данных на этапе структурирования подготавливает веса ребер к возможности их адекватного суммирования или сравнения в зависимости от вида частных критериев предпочтительности, что значительно сокращает количество промежуточных расчетов. Комплекс проблемно-ориентированных программ «Многокритериальная оптимизация на графах в условиях стохастической неопределенности исходных данных» является универсальным инструментальным средством для нахождения количественных оценок рассматриваемых альтернатив в задачах многокритериального сравнения и выбора предпочтительных альтернатив. Предложенные в диссертации модели, методы и алгоритмы представляют собой эффективный математический инструментарий для информационных систем аналитических служб предприятий и организаций различного рода деятельности.
Методология и методы исследований. Для решения частных научных задач, поставленных в диссертационной работе, использованы методы теории систем и системного анализа, теории графов и дискретной математики, теории приближенных алгоритмов с оценками, теории многокритериальной оптимизации и принятия решений, теории математической статистики, теории интервального анализа и нечеткой логики, теории недетерминированного хаоса.
Положения, выносимые на защиту:
-
Метод решения задач многокритериального выбора на графах в условиях недетерминированности исходных данных, базирующийся на известной схеме решения задач многокритериального выбора в условиях детерминированности, с добавлением этапа структурирования неопределенности и уточненного этапа расчета количественных оценок допустимых решений.
-
Классификация исходных данных в виде нечетких множеств по признаку «Близость к более вероятной величине», позволяющая выполнять операции сжатия функции принадлежности и дискретизации.
-
Математическая модель сведения нечетких множеств к единой размерности, позволяющая сжимать функцию принадлежности без потери информативности и осуществлять более экономные арифметические операции над нечеткими множествами.
-
Метод дефазификации центров тяжести носителя и функции принадлежности, позволяющий сравнивать нечеткие множества с пересекающимися и вложенными носителями.
-
Метод взвешенной свертки границ вложенных интервалов, являющийся развитием метода сравнения «в центральном смысле» для случая не равнозначности границ интервала.
-
Математическая модель для прогнозирования персистентных временных рядов на безе линейных клеточных автоматов, в основу которой заложен частотный анализ имеющихся конфигураций с памятью, где длина конфигурации с памятью однозначно определяется глубиной долговременной коррелированности.
-
Метод вычисления глубины долговременных корреляций персистентных временных рядов, являющийся развитием алгоритма нормированного размаха Херста и использующий понятия «окончание памяти о начальной точке», «глубина долговременной памяти».
-
Адаптированный метод Парето для нахождения множества несравнимых альтернатив в условиях интервальности или нечеткости количественных характеристик допустимых решений.
-
Приближенные алгоритмы для интервальной задачи нахождения оптимального покрытия 2-дольного графа звездами одного типа с весами ребер – интервалы равной ширины.
-
Комплекс проблемно-ориентированных программ для решения задач многокритериального выбора на графах в условиях недетерминированности исходных данных.
Степень достоверности научных положений и выводов, полученных в диссертационной работе, основных теоретических и практических результатов обеспечена корректным применением математического аппарата теории графов, теории сложности алгоритмов, теории интервального анализа и нечеткой логики, элементов теории детерминированного хаоса.
Апробация результатов. Результаты диссертационного исследования и его основные положения обсуждались на конференциях и симпозиумах Всероссийского и Международного уровня: Российская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002); Международная школа-семинар по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, 2002, 2004); VIII Международная конференция «Нелинейный мир. Образование. Экология. Экономика. Информатика» (Астрахань, 2003); III и IV Международные конференции «Новые технологии в управлении, бизнесе и праве» (Невинномысск, 2003, 2004); Международный Российско-Узбекского и Российско-Казахский симпозиумы «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик – п. Эльбрус, 2003, 2004); I и II Всероссийская научно-практической конференции «Экономическое прогнозирование: модели и методы – 2004» (Воронеж, 2004, 2007); Одиннадцатая Международная конференция «Математика. Компьютер. Образование» (Дубна, 2004); Одесский семинар по дискретной математике Южного научного центра НАН и МОН Украины (Одесса, 2004); Международная научно- техническая конференция «Интеллектуальные системы (IEEE AIS’04)» и «Интеллектуальные САПР» (CAD-2004) (Дивноморское, 2004); VI INTERNATIONAL CONGRESS OF MATHEMATICAL MODELING(Nizhniy Novgorod, 2004); 1-ый Международный форум «Актуальные проблемы современной науки. Естественные науки» (Самара, 2005); VII Международный симпозиум «Математическое моделирование и компьютерные технологии» (Кисловодск, 2005); IV Международная научно-практическая конференция «Проблемы регионального управления, экономики, права и инновационных процессов в образовании» (Таганрог, 2005); Международная междисциплинарная научная конференция «Вторые Курдюмовские чтения Идеи синергетики в естественных науках» (Тверь, 2006); IX Международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, МГУ, 2006); Proceedings 17th International Conference on the Application of Computer Science and Mathematics Architecture and Civil Engineering K. Gurlebeek and C. Konke(eds) (Weimar, 2006); III Международная конференция «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 2006); IX Международный семинар «Дискретная математика и ее приложения» (Москва, МГУ, 2007); XI Международная научно-практическая конференция «Системный анализ в проектировании и управлении» (Таганрог, 2007); Международная научно-практической конференции «Современные тенденции развития теории и практики управления в России и за рубежом» (Ставрополь, 2009); Международная научно-практическая конференция «Современные достижения в науке и образовании: математика и информатика» (Архангельск, 2010); 55-я, 56-я, 57-я научно-методические конференции «Современное состояние и приоритеты развития фундаментальных и прикладных исследований в области физики, математики и компьютерных наук» (Ставрополь, СГУ, 2010, 2011, 2012); IV Международная научно-практическая конференция «Моделирование производственных систем и совершенствование информационных технологий» (Ставрополь, 2012); II Международная научно-практическая конференция «Актуальные проблемы современной науки» (Ставрополь, 2013); на научных семинарах Ставропольского государственного университета и Северо-Кавказского федерального университета (Ставрополь, 2012, 2013).
По теме диссертации опубликовано: 118 печатных работах, из них: 23 – в научных журналах, рекомендованных ВАК, 88 – тезисов докладов и сборниках статей, 5 – в свидетельствах о государственной регистрации программы для ЭВМ, 3 – в монографиях.
Структура и объем диссертации. Диссертация изложена на 303 страницах основного текста, включает 65 рисунка, 35 таблиц, состоит из введения, шести глав, заключения, списка использованных источников из 298 наименований и 3 приложений.
Автор выражает благодарность доктору физико-математических наук, профессору Перепелице Виталию Афанасьевичу за многолетнюю совместную работу, а также доктору технических наук, профессору Копытову Владимиру Вячеславовичу и кандидату технических наук, доценту Петренко Вячеславу Ивановичу за консультирование, всестороннюю помощь и поддержку.
