Материал: Оптимизация и моделирование в автоматизированных системах

ным образом, поэтому он не может рассматриваться как оптимизированные значения.

Математический аппарат нечеткой логики успешно включается в состав практически всех алrоритмов Data Mining; так появились нечеткие нейронные сети, нечеткие деревья решений, нечеткие ассоциативные правила. Объединение технологии баз данных и нечетких запросов позволяет аналитикам получать нечеткие срезы и т.д. [3].

Одним из наиболее эффективных инструментариев при решении сложных задач анализа данных являются нечеткие гибридные методы. К числу таких методов относятся генетические, эволюционные, бионические, адаптивные и другие методы поиска.

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

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

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

Литература

1.Knowledge Discovery Through Data Mining: What Is Knowledge Discovery” – Tandem Computers Inc., 1996.

2.Гик Дж., ван. Прикладная общая теория систем. – М.: Мир, 1981.

3. Минаева, Ю.В. Методы статистического и интеллектуального анализа данных: учеб. пособие / Ю.В. Минаева. – Воронеж: ВГТУ, 2017. – 90 с.

4.Минаева, Ю.В. Структурно-параметрическая адаптация генетического алгоритма / Вестник СибГУТИ. 2017. № 1 (37). С. 83-89.

5.Minaeva ,Yu.V. Adaptive modification of the particle swarm method based on dynamic correction of the trajectory of movement of individuals in the population

/Бизнес-информатика. 2016. № 4 (38). С. 52-59.

ФГБОУ ВО «Воронежский государственный технический университет», Россия

5

УДК 519.816

А.Г. Коротченко, Е.А. Трошина

О ПРИНЦИПАХ РАНЖИРОВАНИЯ В ЗАДАЧАХ ПРИНЯТИЯ РЕШЕНИЙ

Введение Под ранжированием объектов (или элементов) конечного множества, на

котором задано линейное бинарное отношение предпочтения, понимается, расположение их в цепочку по убыванию ценности, важности [1,2]. Задачи ранжирования возникают, например, при сортировке результатов запросов пользователей в поисковых системах, формировании списка рассылки рекламы, а также при решении многокритериальных и многоэтапных задач оптимизации, см., на-

пример, [3,4].

Если исходное отношение транзитивно, то оно является линейным квазипорядком и принцип ранжирования состоит в факторизации этого квазипорядка по его симметричной части [1,2].

В случае, когда отношение является нетранзитивным, используется два принципа ранжирования: принцип «грубого» и принцип «тонкого» ранжирования. «Грубое» ранжирование – это выделение классов «равноценных» объектов путем факторизации исходного отношения по отношению его взаимной достижимости, а «тонкое» ранжирование – это ранжирование элементов внутри каждого класса [1,2,5].

Пусть M − матрица доминирований-безразличий, соответствующая рассматриваемому1 классу, где каждый элемент матрицы может принимать значе-

ния 0, 1, 2 . Принцип «тонкого» ранжирования состоит в том, что оно осущест-

вляется по компонентам предельного вектора, совпадающим с точностью до скалярного сомножителя с нормированным собственным вектором матрицы M соответствующим ее числу Перрона-Фробениуса [1,2].

В статье рассматривается упрощение принципа «тонкого» ранжирования элементов множества, на котором задано линейное бинарное нетранзитивное

осуществлять так же, как по компонентам предельного вектора π. Например,

6

называть ранжирование, проведенное по компонентам предельного вектора π-ранжированием, а ранжирование, проведенное по компонентам векторов X, Y, Z соответственно X-ранжированием, Y-ранжированием и Z- ранжированием.

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

A = {Установленоa, b, c} , что для линейных отношений, заданных на множестве существует три автоморфных класса, два из которых содержат по

нейных отношений, заданных на множестве A = {a, b, c}, принцип ранжирования для нетранзитивного случая, равносилен X-ранжированию.

6 автоморфных отношений и один – 2 отношения. Также доказано, что для ли-

A = {Установленоa, b, c, d} , что для линейных отношений заданных на множестве , у которых на этапе «грубого» ранжирования образовался класс, содержащий три элемента, существует шесть автоморфных классов, два из ко-

торых содержат по 8 автоморфных отношений и 4 класса - по 24 отношения. Также доказано, что для таких отношений принцип ранжирования равносилен

αре элемента. Классы, удовлетворяющие указанным условиям, будем называть

-классами. Установлено, что для α-классов существует 28 автоморфных классов, содержащих по 24, 12, 8 или 6 автоморфных отношений. Также доказано, что существует восемь вариантов α-классов, каждый из которых характеризуется своим условием, накладываемым на векторы X, Y, Z: 1. Если все компоненты вектора X различны, тогда π-ранжирование совпадает с Z-ранжированием. 2. Если вектор X содержит две одинаковые компоненты, а X-ранжирование совпадает с Y-ранжированием, а Y-ранжирование совпадает c Z-ранжированием, тогда π-ранжирование совпадает с X-ранжированием. 3. Если вектор X содержит две одинаковые компоненты и вектор Y содержит две одинаковые компоненты, а X-ранжирование не совпадает с Y-ранжированием, а Y-ранжирование не совпадает c Z-ранжированием и X-ранжирование не совпадает c Z- ранжированием, тогда π-ранжирование совпадает с Z-ранжированием. 4. Если вектор X содержит две одинаковые компоненты, а все компоненты вектора Y различны, и X-ранжирование не совпадает с Y-ранжированием, а Y- ранжирование не совпадает c Z-ранжированием и X-ранжирование не совпадает c Z-ранжированием, тогда π-ранжирование совпадает с Y-ранжированием.

7

5. Если вектор X содержит две одинаковые компоненты и X-ранжирование не совпадает с Y-ранжированием, а Y-ранжирование совпадает c Z- ранжированием, тогда π-ранжирование совпадает с Y-ранжированием. 6. Если вектор X содержит две одинаковые компоненты и вектор Z содержит две одинаковые компоненты, а X-ранжирование совпадает с Y-ранжированием, а Y- ранжирование не совпадает c Z-ранжирование, тогда π-ранжирование совпадает с X-ранжированием. 7. Если вектор X содержит две одинаковые компоненты, а все компоненты вектора Z различны, а X-ранжирование совпадает с Y- ранжированием, а Y-ранжирование не совпадает c Z-ранжированием, тогда π- ранжирование совпадает с Z-ранжированием. 8. Если все компоненты вектора

класса эквивалентности, где в качестве эквивалентности используется отношение взаимной достижимости. Обозначим матрицу доминирований-безразличий,

8

Для класса 1 π-ранжирование трехэлементного множества совпадает с X-

решение задачи «тон-

кого» ранжирования производится с использованием условия 2, то есть π- ранжирование совпадает с X-ранжированием.

Заключение В статье приведена классификация автоморфных классов линейных не-

транзитивных отношений, заданных на трех и четырех элементных множествах, и установлены простые правила построения предельного вектора, с помощью которого решается задача «тонкого» ранжирования

Литература

1.Розен, В.В. Цель-оптимальность-решение (математические модели принятия оптимальных решений) / В.В. Розен. – М.: Радио и связь, 1982. – 168 с.

2.Коротченко, А.Г. Принципы оптимальности в задачах принятия решений: Учебно-методическое пособие / А.Г. Коротченко, Н.Н. Чернышова, В.М. Сморякова. – Нижний Новгород, Фонд образовательных электронных ресурсов (компьютерных изданий) Нижегородского государственного университета, рег.

№944.15.08, 2015. – 44 с.

3.Коротченко, А.Г. О задачах математического программирования, имеющих многоэтапный характер / А.Г. Коротченко // Вестник Нижегородского университета. Сер. Математическое моделирование и оптимальное управления, 2011. №1. С.183-187.

4.Korotchenko, A.G. On a method of construction of numerical integration formulas / A.G. Korotchenko, V.M. Smoryakova - AIP Conference Proceedings, V.

1776, №9780735414389, 2016, P.090012-1 -- 090012-4.

5.Коротченко, А.Г. Динамический способ формирования классов при решении задачи "грубого" ранжирования / А.Г. Коротченко, Н.Н. Чернышова // Научно-образовательный и прикладной журнал "Инженерный вестник Дона"

– 2015. - № 1 (часть 2) - URL: http://www.ivdon.ru/ magazine/archive/nly 2015/2843 ISSN 20738633.

ФГБОУ ВО «Нижегородский государственный университет им. Н.И. Лобачевского», Россия

9