Введение к работе
Актуальность темы
С началом популяризации саморазвивающихся систем, в частности социальных сетей, появился значительный интерес не только к динамике распространения информации в сложившейся статичной сети, но и к изменяющейся во времени структуре связей. Графы с изменяющимися связями упоминались и ранее, начиная с 1950-х годов в связи с развитием многоагентных систем, например, в задачах управления группой мобильных роботов. В настоящее время миниатюризация и тиражирование беспилотных (беспроводных) технологий дало новый толчок для исследования свойств динамических графов и оптимизационных задач на них.
С другой стороны, в последние два десятилетия с развитием информационных технологий наблюдается значительный рост накопления данных различной природы. Посредством глобальной сети Интернет осуществляется накопление больших объемов этих данных в единых базах. Сервис «YouTube» предоставил возможность каждому человеку опубликовать свое видео для просмотра многомиллиардной аудитории. Известная социальная сеть «Facebook» фактически реализовала модель «маленького мира» сократив расстояния между людьми из разных стран. Сотовые операторы обеспечивают покрытие больших территорий беспроводной связью. Каждый из этих сервисов собирает и аккумулирует данные либо в собственных закрытых, либо в общедоступных базах данных.
Терминология «большие данные» («big data») впервые была введена в специальном выпуске журнала Nature от 3 сентября 2008 года, в котором представлена информация о значительном росте объемов данных, различных подходах к их обработке и о новых возможностях получения качественных результатов при обработке количественных данных. С 2011 года крупнейшие информационно-технологические компании, такие как IBM, Oracle, Microsoft, Hewlett-Packard и др. используют в стратегических документах понятия больших данных, а наука о больших данных сформировалась в отдельное направление и получила название анализа больших данных. В деловой среде наряду с термином «большие данные» используются фразеологические словосочетания «большая нефть», «большая руда», «большие города» и т.п.
В науке о больших данных разрабатываются подходы, методы, инструменты обработки больших объемов как структурированных, так и неструктурированных данных. Тем не менее, для структурированных, классифицированных или сгруппированных по категориям данных существует значительный набор инструментов обработки. Методы структуризации применяются для первичной обработки и подготовки данных, если это возможно сделать. В том числе используются методы распознавания образов, категоризация и обогащение данных, визуальные методы классификации.
В качестве инструмента моделирования сложных многоэлементных систем используются графы большой размерности – с большим количеством вершин, связей между ними, весами разной природы. Для таких графов применяется
общий термин «большой граф», вне зависимости от плотности соединения вершин и степени структуризации в терминологии больших данных.
Одним из видов больших графов являются фрактальные (предфракталь-ные) графы – графы большой размерности со свойствами самоподобия. Термин фрактальный граф применен известными физиками Дж. Мелроузом, В.С. Лебедевым, А. Марголиной, Б.М. Смирновым при моделировании физических процессов. Распознавание фрактального графа подразумевает построение динамической траектории, каждому шагу которой соответствует своя структура связей. Современные исследования в этом направлении: фрактальность биологических древодвидных структур – Kalda J.; фрактальность и самоподобие масштабно-инвариантных сетей – Kim J.S., Goh K.-I. и др.; мультифрактальный анализ взвешенных сетей – Wei D., Chen X. и др.; самоподобие сложных сетей – Song Ch., Havlin Sh., Makse H.A.; распознавание мультифрактальности и анализ сложных сетей – Wang D.; распознавание фрактальности сложных сетей – Molontay R.; фрактальность больших графов – Akiba T., Nakamura K., Takaguchi T. Количество зарубежных публикаций по анализу фрактальных и самоподобных свойств масштабных графов и сетей значительно возросло с появлением исследований больших данных (2011-2013 гг.) и требует отдельного анализа.
Известные применения фрактальных графов – это разработка радиолокационной фрактальной антенны, описание физической структуры всемирной сети Интернет, моделирование систем капиллярного типа в медицине, анализ фрактально-графовых структур данных, фрактальные алгоритмы на графах и др.
По сути, предфрактальные графы сформировались в отдельный класс графов со своей теорией и самостоятельными методами исследования. В науке и практике имеется потребность обработки графов большой размерности. Решение задач классическими методами теории графов требует значительного увеличения вычислительных возможностей компьютерной техники, при этом обработка больших графов все равно занимает время, превышающее требования к скорости принятия решений. При этом предфрактальные графы являются подклассом динамических графов, показывая изменения с течением времени, для чего используется методика построения и терминология класса динамических графов. Траектория описывает все изменения в структуре связей предфрактального графа на каждый момент времени с начала порождения до заданного ранга. Моделирование задач посредством предфрактальных графов и использование специализированных методов решения позволяет сократить время обработки за счет свойства самоподобия, наследственности и других свойств этого класса графов.
На классе предфрактальных графов исследованы частные задачи с несколькими критериями: 3-критериальная задача покрытия простыми цепями; 5-критериальная задача Эйлера; 5-критериальная задача вершинной раскраски; 4-критериальная задача покрытия лесом; 4-критериальная задача размещения кратного центра; 6-критериальная потоковая задача и распознавание частных случаев порождения орграфов и предложены алгоритмы поиска решений с гарантированными оценками критериев. Предложены алгоритмы распознавания предфрактальных графов с чередованием затравок и с регулярной затравкой в
случае сохранения смежности и непересечения старых ребер, алгоритмы структурного разрушение сложных систем.
Настоящая диссертация посвящена построению классов многокритериальных задач на предфрактальных графах и разработке покрывающих их классов алгоритмов, выделению полиномиально-разрешимых подзадач из класса NP-трудных задач на предфрактальных графах при определенных условиях. Для этого проводится исследование многокритериальных задач на многовзвешенных предфрактальных графах, сформулированы общие и частные постановки задач, разработаны полиномиальные последовательные алгоритмы и быстрые параллельные алгоритмы поиска решений, классифицированы задачи на многовзве-шенных предфрактальных графах с недетерминированными весами, построены математические модели на предфрактальных графах.
Несмотря на самостоятельность класса предфрактальных и фрактальных графов вся терминология, описания и методы соответствуют методологии и канонам теории графов. Все разработки в диссертации опираются на труды ученых, ставших уже классиками, среди них – Басакер Р., Берж К., Гэри М., Джонсон Д., Дистель Р., Зыков А.А., Кристофидес Н., Оре О., Саати Т., Свами М., Татт У., Тхуласираман К., Уилсон Р., Харари Ф., а также на труды представителей современных научных школ по дискретной математике и математической кибернетике – Алексеев В.Б., Васильев С.Н, Касим-Заде О.М., Каркищенко А.Н., Малюгин С.А., Сапоженко А.А., Соколов В.А. и теории графов – Афраймо-вич Л.Г., Бондаренко В.А., Дольников В.Л., Евдокимов А.А., Иорданский М.А., Райгородский А.М., Прилуцкий М.Х. и др.
Арифметика нечетких чисел, используемая в диссертации, опирается на работы известных авторов, по интервальному исчислению – это Алефельд Г., Добронец Б.С., Марченко Л.В., Калмыков Л.А., Назаренко Т.И., Херцбергер Ю., Шарый С.П., Шокин Ю.И.; арифметика нечетких множеств – Заде Л., Коф-ман А.; обработка временных рядов – Кендалл М.Дж., Стьюарт А.
Все постановки многокритериальных задач на предфрактальных графах в исследовании получены автором впервые, соответствуют принятым в теории оптимизации подходу к описанию и опираются на достигнутые результаты в этом направлении. В качестве основы использовались работы ученых – Алеске-ров Ф.Т., Барыкин В.Д., Берман В.П., Гафт М.Г., Емеличев В.А., Кини Р.Л., Ногин В.Д., Озерной В.М., Перепелица В.А., Подиновский В.В., Сергиенко И.В. и др. В частности, Емеличев В.А. и Перепелица В.А. показали, что известные массовые задачи в многокритериальной постановке с двумя весовыми и одним топологическим критериями являются труднорешаемыми.
Параллельные вычисления и алгоритмы становятся обыденными с каждым новым витком развития компьютерной техники. Параллельные алгоритмы используются в многоядерных мобильных и персональных компьютерах. Для разработки параллельных алгоритмов использовалась структурная параллелизация на предфрактальных графах. Классификация, описание и методы построения параллельных алгоритмов основаны на работах известных ученых – Антонова А.С., Воеводина В.В., Воеводина Вл.В., Марчука Г.И., Эндрюса Г.Р. и др.
Цели и задачи
Во многих процессах и объектах, с которыми сталкивается человек в своей жизнедеятельности, наблюдается фрактальность. В живой природе это кораллы, морские звезды и ежи, морские раковины, цветы и растения, кроны деревьев и листья растений, кровеносная система, бронхи людей и животных и др. В неживой природе – границы географических объектов, береговые линии, снежинки, молнии, кристаллы и др. В природе эти фракталы являются непрерывными величинами. Описание и моделирование этих объектов и процессов осуществляется по уже ставшими классическими канонами фрактальной теории. В тоже время искусственные процессы, либо объекты, создаваемые человеком, описываются дискретными величинами. Визуализация может осуществляться посредством графов, а решение задач оптимизации известными методами теории графов. Как оказалось, понятие фрактальности применимо и в сфере человеческой жизнедеятельности, это и транспортные карты мегаполисов, система авиамаршрутов, фрактальные антенны и т.п. В результате на стыке двух теорий – теории фракталов и теории графов, появился новых класс графов – фрактальные графы, обладающие одновременно фрактальными (самоподобием) и дискретными свойствами. Исследование свойств и характеристик фрактальных и предфрактальных графов получило достаточное распространение. При постановке задач на предф-рактальных графах большой размерности – с большим количеством вершин и ребер, современная вычислительная техника не способна получать решения за приемлемое время с помощью известных классических алгоритмов. Сложности вычислениям также добавляют неопределенность весовых значений и много-взвешенность разной природы. В этом случае необходимо искать методы и подходы, использующие фрактальные свойства (самоподобие, наследственность) и позволяющие получать быстрые точные, либо приближенные с необходимой точностью решения.
Основной целью диссертационного исследования является создание подхода к построению классов многокритериальных задач на предфрактальных графах и разработке покрывающих их классов алгоритмов.
Для чего решаются следующие задачи:
– построить общую постановку многокритериальной задачи на многовзве-шенном предфрактальном графе, в том числе с недетерминированными весами – интервальными числами, нечеткими множествами и временными рядами; определить множества решений в терминологии классической теории графов – множество альтернатив, паретовское множество, лексикографическое множество альтернатив;
– классифицировать многокритериальные задачи на предфрактальных графах по типу и структурной принадлежности;
– разработать классы быстрых последовательных алгоритмов поиска точных и приближенных решений классов многокритериальных оптимизационных задач на предфрактальных графах; определить вычислительные сложности алгоритмов и гарантированные оценки критериев;
– исследовать некоторые NP-полные задачи на предфрактальных графах; выделить специальные условия, при которых их подзадачи разрешимы на классе предфрактальных графов;
– разработать параллельные алгоритмы поиска решений многокритериальных задач класса предфрактальных графов; определить вычислительные сложности параллельной реализации алгоритмов и сравнить их временные характеристики с характеристиками соответствующих последовательных алгоритмов;
– построить математические модели ряда прикладных задач на основе формализма предфрактальных графов;
– разработать вычислительный комплекс моделирования многокритериальных задач на многовзвешенных предфрактальных графах с недетерминированными весами; провести апробацию с расчетами на примерах.
Научная новизна, методология и методы исследования
В диссертации впервые предложены постановки многокритериальных задач на классе предфрактальных графов одновременно со многими и недетерминированными весами. Впервые построена и предложена интервальная арифметика на многовзвешенных предфрактальных графах, применимая к общему классу динамических графов. Впервые предложены параллельные алгоритмы решений многокритериальных задач, учитывающие свойства самоподобия графов, функционирующие со значительным ускорением по сравнению с известными последовательными и классическими алгоритмами на графах. Построены модели, на примере которых показаны широкие возможности использования пред-фрактальных графов в качестве инструмента описания объектов и процессов в жизнедеятельности человека, прогнозирования их будущих состояний, оптимизации локальных и глобальных характеристик, конструирования крупномасштабных систем с заданными свойствами.
Теоретической основой диссертационной работы являются основные положения теории графов и многокритериальной оптимизации. Методологическая платформа диссертационного исследования основана на классе предфракталь-ных графов. Введена сопутствующая терминология, описание и классификация задач, а также предложен набор методов, алгоритмов и подходов для их решения.
При решении конкретных задач диссертационного исследования использовались методы теории алгоритмов, параллельной арифметики, интервального исчисления, дискретной математики, исследования операций.
Достижения ведущих научных школ, материалы научных конференций, классические научные труды также положены в основу теоретической платформы исследования.
В качестве среды для реализации последовательных алгоритмов использовалась программная оболочка Python Anaconda 2 с дополнительным графическим модулем, развернутая в операционной системе Windows 10.
Теоретическая и практическая значимость
Диссертационная работа носит теоретический характер. Все результаты работы являются новыми и получены автором самостоятельно. Основные положения работы представляют собой вклад – в теорию предфрактальных графов, взвешенных многими недетерминированными весами; в развитие методов многокритериальной оптимизации графов большой размерности с фрактальными свойствами; в развитие алгоритмической базы решения модельных многокритериальных задач; в расширение применения параллельных алгоритмов на графах.
Предложенные результаты также могут быть использованы для решения практических теоретико-графовых модельных задач большой размерности в условиях недетерминированности и множественности данных, в том числе для прогнозирования эпидемиологической ситуации популяции животных и людей, распространения инфекционных заболеваний на посевах сельско-хозяйственных культур, создания инструментов управления изменяемой иерархией группы агентов, выявления устойчивости и угроз масштабных авиа и транспортных сетей, оптимального размещения информационно-коммуникационной сети беспроводных ретрансляционных антенн, вычисления и создания оптимальной конфигурации фрактальных радиоантенн.
Представляется, что самостоятельное практико-ориентированное значение имеют методы интервального исчисления на графах, подходы к структурной па-раллелизации последовательных алгоритмов решения многокритериальных задач на графах большой размерности со свойствами самоподобия, подходы к формализации целевых программ на основе фрактальных деревьев, обеспечивающие их простое погружение в информационно-сетевую среду, методы решения задачи конкурсного отбора проектов.
Полученные в диссертации результаты, а именно подход к построению классов полиномиальных задач на предфрактальных графах и построению алгоритмов, может быть применен в качестве шаблона для выделения классов полиномиальных задач и алгоритмов их решения.
Отдельные положения диссертационного исследования получены в рамках выполнения научно-исследовательских работ Института экономики РАН по теме «Экспертно-аналитическое обеспечение информационно-аналитической системы мониторинга и анализа выполнения ФЦП и ФАИП» в 2006 г., Финансового университета при Правительстве РФ по темам «Развитие методологии и инструментальной поддержки программно-целевого управления» в 2010 г., «Исследование целесообразности и экономической эффективности открытого распространения части продуктов разработчиками программного обеспечения» в 2013 г., «Разработка аналитического инструментария оценки эффективности российского импорта товаров и услуг и разработка системы индикаторов эффективности импортозамещения» и «Разработка учетно-контрольной системы реализации инвестиционных проектов с государственным участием» в 2016 г., «Исследование механизмов формирования и функционирования бюджетных фондов
инфраструктуры на основе модели концессионного контракта жизненного цикла с учетом косвенных эффектов в ЖКХ» в 2017 г.
Результаты диссертационного исследования включены в отчеты Школы молодых ученых Лаборатории №20 ИПУ РАН в 2015-2017 гг.
Научные исследования диссертационной работы поддержаны грантами РФФИ «Применение структурно-динамического подхода для моделирования децентрализованных мобильных сетей связи» в 2012 г., «Моделирование поведения групп роботов-агентов при решении задачи мониторинга в условиях непрерывно изменяющейся внешней среды» в 2016 г., «Разработка методики оценки результативности и эффективности реализации государственных целевых программ» в 2017 г.
Материалы диссертационного исследования использованы в преподавании учебных дисциплин «Дискретная математика», «Методы оптимальных решений», «Теория графов и классические задачи прикладной математики» департамента анализа данных, принятия решений и финансовых технологий Финансового университета при Правительстве РФ.
По результатам диссертационного исследования зарегистрированы программы ЭВМ – «Нахождение центральных вершин фрактального графа», «Нахождение p-центров фрактального графа», «Поиск решений многокритериальных задач на многовзвешенных предфрактальных графах».
Положения, выносимые на защиту
Все положения являются новыми. Основные из них следующие:
Подход к построению классов полиномиальных задач на предфрактальных
графах, в том числе выделение полиномиальных подзадач известных
NP-полных теоретико-графовых задач.
Общая постановка многокритериальной задачи на многовзвешенном пред-фрактальном графе. Правила взвешивания предфрактального графа многими весами с коэффициентом подобия. Описание множеств допустимых решений многокритериальных задач на предфрактальных графах. Классификация многокритериальных задач на многовзвешенных предфракталь-ных графах по типу и структурной принадлежности.
Подход к разработке классов быстрых полиномиальных алгоритмов, по
крывающих классы задач на предфрактальных графах.
Характеристики алгоритмов решения классов многокритериальных задач на многовзвешенных предфрактальных графах, в том числе вычислительные сложности. Классификация алгоритмов решения по структурной принадлежности. Быстрые последовательные полиномиальные алгоритмы поиска кратных центров и медиан, остовных лесов, совершенных паросоче-таний, покрытий простыми непересекающимися цепями, звездами и др. Расчеты вычислительной сложности алгоритмов и оценок решений по каждому из критериев многокритериальных задач.
Новые параллельные алгоритмы решения многокритериальных задач на многовзвешенных предфрактальных графах. Расчеты вычислительной сложности параллельной реализации алгоритмов, ускорения параллельных алгоритмов по сравнению с последовательными аналогами, оценки критериев многокритериальных задач.
Общая постановка многокритериальной задачи на многовзвешенном предф-рактальном графе с недетерминированными весами. Правила взвешивания интервальными числами, нечеткими множествами и временными рядами. Классификация задач по типу и структурной принадлежности.
Интервальная арифметика для предфрактально-графовых задач. Общая постановка многокритериальной задачи на интервально-взвешенном предф-рактальном графе со многими весами. Описание множеств допустимых решений многокритериальных задач на предфрактальных графах с недетерминированными весами.
Характеристики алгоритмов решения многокритериальных задач на мно-говзвешенных предфрактальных графах с недетерминированными весами. Классификация алгоритмов решения по структурной принадлежности. Быстрые последовательные алгоритмы решения задач с недетерминированными весами. Расчеты вычислительной сложности алгоритмов и оценки решений по каждому из критериев многокритериальных задач.
Прикладные теоретико-графовые модели на предфрактальных графах.
а) Формализованное представление целевой программы в виде предфрак-
тального дерева. Инструментарий конкурсного отбора проектов и меха
низм оценки результативности целевых программ. Модель конкурсного
отбора проектов – задача поиска совершенного паросочетания на предф-
рактальном графе, порожденном двудольными затравками.
б) Интервальная модель крупномасштабной кластеризации материи во
Вселенной. Описание иерархии кластеризации материи во Вселенной.
Процедура распознавания предфрактального графа произвольно выбран
ной области Метагалактики.
в) Пространственная теоретико-графовая модель распространения эпиде
мии. Описание сети взаимодействия агентов популяции, состояния агентов
и пороговые значения эпидемий. Описание структуры распространения за
болевания и меры разрушения эпидемического процесса. Процедура рас
познавания карты развития пандемии гриппа H1N1 в 2009 году в виде
предфрактального графа, порожденного затравками-звездами.
г) Топологическая модель крупномасштабной сети Интернет. Процедура
распознавания инфраструктурной карты сети Интернет в виде предфрак-
тального графа, порожденного деревьями. Описание процесса распростра
нения вирусов в сети и возможные состояния узлов связи.
Вычислительный комплекс моделирования многокритериальных задач на
многовзвешенных предфрактальных графах с недетерминированными ве
сами. Численный эксперимент поиска решения индивидуальной задачи –
выделение остовного дерева минимального веса предфрактального графа, порожденного множеством затравок, взвешенного недетерминированными весами – интервальными числами, нечеткими множествами и временными рядами.
Степень достоверности, публикации и апробация результатов
Достоверность и обоснованность результатов исследования обеспечиваются строгостью и корректным использованием математических доказательств. Результаты, включенные в диссертацию, опубликованы в 121 научной публикации, в их числе 4 монографии, 36 статей в журналах из перечня ВАК. Из совместных публикаций в диссертацию включены результаты, полученные лично соискателем. Конфликт интересов с соавторами отсутствует.
Результаты, включенные в диссертацию, докладывались на научных семинарах в 2010-2018 гг. в ведущих университетах и научных институтах: школе-семинаре «Управление и обработка информации в технических системах» Южного федерального университета; научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» и семинаре «Будущее прикладной математики» Института прикладной математики им. М.В. Келдыша РАН; семинарах лаборатории №20 Института проблем управления им. В.А. Трапезникова РАН; семинарах департамента анализа данных, принятия решений и финансовых технологий Финансового университета при Правительстве РФ; семинаре кафедры алгебры и математической логики Казанского (Приволжского) федерального университета; семинаре кафедры информатики и автоматизации научных исследований Нижегородского государственного университета им. Н.И. Лобачевского; межкафедральном семинаре по вопросам структурно-динамического моделирования Московского физико-технического института (государственного университета); семинаре отдела прикладных проблем оптимизации Вычислительного центра им. А.А. Дородницына РАН (ФИЦ «Информатика и управление» РАН).
Результаты диссертации докладывались на многочисленных международных и общероссийских конференциях и симпозиумах: Международной конференции «Проблемы управления безопасностью сложных систем» (Москва, 2002, 2005, 2006, 2011, 2012, 2015, 2016); Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2007, 2008, 2011, 2014-2016); Всероссийской научно-методической конференции «Современная математика и концепция инновационного математического образования» (Москва, 2015, 2016); Всероссийской научно-технической конференции «РТИ Системы ВКО-2016» (Москва, 2016); Международной междисциплинарной научной конференции «Идеи синергетики в естественных науках» (Тверь, 2006, 2007, 2015); Всероссийской научно-технической конференции молодых конструкторов и инженеров «Минцевские чтения» (Москва, 2015); Международной конференции «Параллельная компьютерная алгебра и её приложения в новых инфокоммуникационных системах» (Ставрополь, 2014); Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 2001, 2006, 2013); Международной
конференции «Параллельные вычисления и задачи управления» (Москва, 2010); Международной научной конференции «Перспектива» (Нальчик, 2008-2010); Международной конференции «Математика. Компьютер. Образование» (Пущино, 2005, Дубна, 2006); Международной научной конференции «Проблемы регионального и муниципального управления» (Москва, 2006); Международной конференции по проблемам управления (Москва, 2006); Международной конференции «Проблемы функционирования информационных сетей» (Новосибирск, 2006); Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 2006); Международной конференции «Когнитивный анализ и управление развитием ситуаций» (Москва, 2006); Международной научно-практической конференции «Реинжиниринг бизнес-процессов на основе современных информационных технологий. Системы управления знаниями» (Москва, 2005); Всероссийской научной конференции «Этноэкономика Юга России: концепции, параметры, механизмы» (Домбай, 2005); Международной конференции «Системный анализ и информационные технологии» (Переславль-Залесский, 2005); Международном междисциплинарном симпозиуме «Фракталы и прикладная синергетика» (Москва, 2005); Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии (Кисловодск, 1998, 2000, 2002).
Структура и объем работы
Диссертация содержит введение, шесть глав, заключение, приложение и список литературы. Объем диссертации с приложением составляет 252 страницы, список литературы состоит из 278 наименований.