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

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

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

БЗ называется непротиворечивой на V, если на наборе признаков Х}еХ невозможно получить выводы: п=IV и ~(u=w).

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

Пусть Х1 — независимая многозначная переменная величина, Х,е[0... к,/], являющаяся одной из характеристик объекта. Приведем основные свойства многозначной логики.

к — 1 при X = У

О при X Ф }

) =

¡Л*,)

к, — 1 при X ,: = ]

О при X1 Ф )

2) Свойство коммутативности; °Х2— Х2 ° X].

3) Свойство ассоциативности: (X, °Х2) °Х3= X, ° (Х2 °Х3).

4) Свойство дистрибутивности: (Х1\уХ2) Х3= Х^3 \/Х2Х}.

\1м(х)при )=г

5)' Правила упрощёния; 1 ],(Х) * , §при

Теперь отметим ряд свойств, справедливых для многозначной логики:

(к-1)*Х=Х

0*Х=0

(к-1) VХ=(к-1) 0^Х=Х.

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ И АВТОМАТИЗАЦИИ КАБАРДИНО-БАЛКАРСКОГО НАУЧНОГО ЦЕНТРА РОССИЙСКОЙ АКАДЕМИИ НАУК

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

04201455782

(5ул/ъ

Димитриченко Дмитрий Петрович

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

05.13.17 - Теоретические основы информатики

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

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

доктор технических наук профессор А.В. Тимофеев

Нальчик - 2013

СОДЕРЖАНИЕ

Введение.......................................................................................3

Глава 1. Исследование информационных структур сложных открытых систем.........................................................................................17

1.1. Информационная структура сложных систем...........................17

1.2. Оптимизация информационных сетей при помощи генетических алгоритмов...................................................................................22

1.3. Организация поиска на основе нечетких отношений предпочтения.............................................................................................28

1.4. Выводы.................................................................................35

Глава 2. Построение баз знаний при помощи переменнозначных предикатов.............................................................................................37

2.1. Основные понятия и определения переменнозначных логических систем........................................................................................37

2.2. Сравнительный анализ извлечения знаний при помощи нечетких отношений и переменнозначных предикатов........................................46

2.3. Минимизация баз знаний, описываемых при помощи переменнозначных предикатов.......................................................................52

2.4. Извлечение дополнительных знаний при помощи структурных характеристик функции, построенной на основе переменнозначных предикатов..............................................................................................67

2.5. Выводы..........................................................................69

Глава 3. Верификация логического поиска структуры информационной сети с наперед заданными свойствами..............................................71

3.1. Выразительность описания знаний при помощи переменнозначных предикатов...................................................................................71

3.2. Свойства адаптивности и самообучения..................................75

3.3.Верификация алгоритма извлечения знаний на основе исходных данных........................................................................................77

3.4. Выводы..........................................................................88

Заключение Список литературы Приложение

ВВЕДЕНИЕ

В современном обществе важную роль играет как обмен информацией (информационные потоки), так и совокупность технических и организационных средств, позволяющих организовывать и поддерживать такие информационные потоки. Совокупность этих средств объединяется в распределенные информационные структуры, называемые информационными сетями. Основное назначение информационной сети, как системы, выполнение функции информационного обмена между входящими в нее подсистемами, каждая из которых также может являться информационной сетью. Очевидно, что различные совокупности связей (топологии) между объектами (сетевыми агентами) по разному могут решать поставленную перед информационной сетью задачу. Например, задача максимального упрощения присоединения к данной информационной сети новых объектов требует хорошей реконфигурируемости внутренних связей, а задача сохранения конфиденциальности информации для своего решения требует многоступенчатой проверки входящих в информационную сеть объектов, жесткой, иерархической структуры связей и процедур шифрования передаваемых данных. Одним из эффективных методов исследования сложных информационных систем является теория графов. В рамках этой теории сформулировано и решено много важных с прикладной точки зрения задач. Теория графов успешно применяется в задачах искусственного интеллекта: От нахождения топологии нейронных сетей и до получения заключений на основе рассуждений, при проектировании сложных технических систем: от построения оптимальных транспортных систем различного назначения и до оптимизации топологии связей между радиоэлементами при создании устройств микроэлектроники. Хорошо известно, что сложность и трудоемкость решения многих оптимизационных задач резко возрастает с увеличением числа вершин и соединяющих их связей (класс пр-трудных задач).

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

3

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

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

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

Цели и задачи исследования. Для достижения поставленной цели в диссертационном исследовании решаются следующие задачи:

1. Провести анализ существующих методов поиска объектов в слабо-формализованных областях знаний в условиях противоположного влияния актуальных характеристик на результат выбора этих объектов;

2. Разработать и исследовать методы выявления скрытых закономерностей в слабоформализованных областях знаний на основе логических алгоритмов при помощи переменнозначных логических предикатов;

3. Разработать и исследовать методов формализации критериев выбора структуры информационных сетей соответствии с предъявляемыми к ним требованиями;

4. Построить программную модель для экспериментального исследования и апробации теоретических выводов и результатов.

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

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

4

ритмов, а также результатами проведенных экспериментов.

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

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

2. Предложен подход интеллектуальной обработки полученных знаний при помощи переменнозначных предикатов;

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

Основные положения, выносимые на защиту:

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

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

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

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

Апробация работы. Основные результаты и положения диссертации были представлены и обсуждены на конференциях: Международная научная конференция «Моделирование устойчивого регионального развития» (Нальчик, 2005 г.); Международный конгресс студентов, аспирантов и молодых ученых «Перспектива 2007» (КБГУ, Нальчик, 2007 г.); Международный Рос-

5

сийско-Азербайджанский симпозиум «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик-Эльбрус, 2008 г.); III Международная научная конференция «Современные проблемы прикладной математики и математического моделирования» (Воронеж, 2009 г.); Международный Российско-Абхазский симпозиум «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик-Эльбрус, 2009 г.); Международный Российско-Болгарский симпозиум «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик-Хабез, 2010 г.), Второй Международный Российско-Казахский симпозиум «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик, 2011 г.), Второй Международный Российско-Узбекский симпозиум «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик-Эльбрус, 2012 г.).

Выносимые на защиту научные результаты были предметом обсуждения на заседаниях научно-исследовательского семинара по современному анализу, информатике и физике Федерального государственного бюджетного учреждения науки Научно-исследовательского института прикладной математики и автоматизации Кабардино-Балкарского научного центра Российской академии наук.

Исследования «Построение алгоритма и программы метода множественной оптимизации ТКС», проводимые в рамках работы над диссертацией, (2006-2009) были поддержаны программой «Организация и финансирование работ молодых ученых Российской академии наук по приоритетным направлениям фундаментальных исследований».

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

Структура и объем работы. Диссертация состоит из введения, трех глав, приложения, заключения, списка цитированной литературы. Объем работы составляет 119 страниц, включая библиографию, содержащую 127 на-

6

именований.

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

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

1. Теория графов позволяет строить модели, отражающие количественные и качественные характеристики информационных сетей;

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

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

Одним из способов учета нескольких критериев, оказывающих влияние на на результаты поиска, является метод анализа нечетких отношений предпочтения, который обладает рядом следующих достоинств:

7

1. Простота интерпретации результатов: полученного нечеткого множества недоминируемых альтернатив х;

2. Легкость включения новых, ранее не известных, критериев;

3. Гибкий способ учета важности критериев путем задания соответствующих коэффициентов относительной важности;

4. Небольшие вычислительные затраты;

5. Простота программной реализации алгоритма многокритериального выбора при нечеткой исходной информации.

Однако, приведенный метод не лишен следующих недостатков:

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

2. Невозможность произвольного изменения коэффициентов важности в силу требования линейной свертки.

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

8

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

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

Многозначным предикатом с переменной значностью называется конечное отображение вида а:8—> 1та, где 1та -ае{0,1,..кг1}> Ь е [2..И].

Пусть задано разбиение В на два непересекающихся подмножества £={а,.. <7п} и П ={п1„жт}. Множества П называют соответственно целевым и базовым. На основе значения целевых необходимо уметь определять значение базовых. При этом, множество сведений, содержащихся в БД должно быть непротиворечивым относительно задачи определения базовых значений.

БЗ называется непротиворечивой на V, если на наборе признаков X) еХ невозможно получить выводы: п=м> и ~(п=м).

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

Пусть Хг - независимая многозначная переменная величина, Х1в[0... к-1], являющейся одной из характеристик объекта. Введем еще несколько функций и свойств многозначной логики.

к — 1 при X - ]

О при X Ф у

I ) =

о

при при

х, = ]

х, * ]

2) Свойство коммутативности:^ °Х2= Х2 °Х1.

3) Свойство ассоциативности: (Х! °Х2) °Х3= X, ° (Х2 °Х3).

4) Свойство дистрибутивности: (X/ уХ2) Х3= Х1Х3 ^Х2Х3.

1л(х)при ) = Г

5 ) Правила упрощения:

О при

Отметим ряд свойств, справедливых для многозначной логики:

(к-1)*Х=Х

0*Х=Х

(к-1) \/Х=(к-1) OvX=X.

Введем понятие обобщенной инверсии: Обобщенной инверсией является следующее выражение

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

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