Ранжирование объектов по числу пи и L-правилам в ассоциативных матрицах

Формирование автоматизированных справочников по компонентам районных электрических сетей. Рассмотрение методики ранжирования однородных альтернатив по числу пи и L-правилам в ассоциативных матрицах. Алгоритм построения очередей оборудования на ремонт.

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 08.12.2018
Размер файла 152,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http: //www. allbest. ru/

Московский энергетический институт (ТУ)

Ранжирование объектов по числу пи и L-правилам в ассоциативных матрицах

Проф. Ю.В. Кандырин, асп. А.М. Кошелев

Аннотация

СТАТЬЯ ПРЕДЛАГАЕТСЯ ДЛЯ ПУБЛИКАЦИИ В ЭЛЕКТРОННОМ ЖУРНАЛЕ «СИСТЕМОТЕХНИКА»,

СВЕДЕНИЯ ОБ АВТОРАХ:

Кандырин Юрий Владимирович, академик Российской академии надежности, профессор Московского энергетического института, зам директора Центра инженерного проектирования МЭИ, заместитель заведующего кафедрой Радиоприемных устройств МЭИ, автор более 200 научных работ, в том числе 9 учебных пособий для Вузов и 2-х монографий. Проблемами надежности и многокритериального выбора в САПР РЭС занимается более 40 лет. По этой тематике под его руководством защищены 6 кандидатских диссертаций.

Тел. раб.: 362-79-41, Моб: 8-926-560-02-08.Тел. дом.: 360-19-56. E-mail: ywk@mail.ru

Кошелев Александр Михайлович, аспирант Радиотехнического факультета Московского энергетического института. Лауреат открытого конкурса студенческих работ, кавалер медали Министерства образования и науки РФ.

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

ранжирование алгоритм очередь автоматизированный

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

В представленной работе предложены р и L - правила ранжирования вариантов с помощью аппарата фактор-множеств в ассоциативных матрицах.

Рассмотрим р -правило структурирования альтернатив. На исходном множестве, представленном матрицей реляционного отношения для вариантов

= {i {kl}}; i={1,N}, l= {1,M}

(табл.1) выделяется множество показателей качества (ПК):

{kl}, l={1,M},

назначенных лицом, принимающим решения (ЛПР). Далее производится формирование окрестностей и фактор-множеств [1]. Под окрестностью Оi единичного радиуса элемента i по отношению R будем понимать множество элементов {i*}, доминирующих или эквивалентных i таких, что они могут быть описаны следующим линейным порядком {i*},i R.

Таблица 1 Исходное множество альтернатив в виде реляционного отношения

Варианты

Показатели качества вариантов {kl}

k1

k2

kM

1

k11

k12

k1M

2

k21

k22

k2M

N

kN1

kN2

kNM

Очевидно, что окрестностью минимальных элементов является пустое множество - . Отношение R определяет доминирование альтернатив при их бинарном сравнении. Это отношение может задаваться критериями Парето (р), Слейтера (S), лексикографическим L-критерием, а также метрическими свертками. Окрестность Оi по kl по р -критерию определяется соотношениями

Оi(/kl) {j : kl(j) kl(i), j, i } (для kl v),

Оi(/kl) {j : kl(j) kl(i), j, i } (для kl ^).

Фактор-множеством ФТ/R (множества по отношению R) называется множество окрестностей единичного радиуса, взятых для всех i

, i={1,N}, т.е. ФТ/kl = {Оi(/kl)}, i = {1,||}.

Знак «Т» отображает транзитивность ФТ/kl .

Поясним методику формирования фактор-множеств и окрестностей на примере. Пусть все показатели качества приведены к минимизации, а линейные порядки вариантов по kl : {L(/kl)} на , l = 3 заданы по условию задачи в виде

L(/k1): <5, 3, {4, 6}, {1, 2}>,

L(/k2): <4, {1, 2}, {3, 6}, 5>, (1)

L(/k3): <6, 5, 1, 4, 2, 3>.

Графически, проекции альтернатив на двойки показателей качества {k1, k2}, {k1, k3}, {k2, k3} представлены на рис. 1, 2 и 3, соответственно.

Рис. 1 Проекции альтернатив на двойку {k1, k2}

Рис. 2 Проекции альтернатив на двойку {k1, k3}

Рис. 3 Проекции альтернатив на двойку {k2, k3}

Для данного примера фактор-множества ФТ/k1, ФТ/k2, ФТ/k3 по соответствующим показателям качества представлены в табл. 2, 3 и 4, соответственно.

Таблица 2 Представление фактор-множества ФТ/k1 для L(/k1)

i

Oi(/k1)

1

2, 3, 4, 5, 6

2

1, 3, 4, 5, 6

3

5

4

3, 5, 6

5

6

3, 4, 5

Таблица 3 Представление факор-множества ФТ/k2 для L(/k2)

i

Oi(/k2)

1

2, 4

2

1, 4

3

1, 2, 4, 6

4

5

1, 2, 3, 4, 6

6

1, 2, 3, 4

Таблица 4 Представление фактор-множества ФТ/k3 для L(/k3)

i

Oi(/k3)

1

5, 6

2

1, 4, 5, 6

3

1, 2, 4, 5, 6

4

1, 5, 6

5

6

6

В [1], [2] показано, что результирующие фактор-множества по Парето с большей размерностью, для совокупности показателей качества {kM}, l ={1, M}, определяются последовательным пересечением фактор-множеств меньшей размерности:

ФТ/{k1,k2...kM} = ФТ/k1 ? ФТ/k2 ?··? ФТ/ kM (2)

В примере, заданном выражением (1) фактор-множества ФТ/k1, ФТ/k2, ФТ/k3 и ФТ/{k1, k2, k3} сведены в таблицу 5, иллюстрируя выражение (2). В таблице, серым цветом выделен столбец фактор-множества, содержащего нехудшие решения для р- критерия. Итак, нехудшими альтернативами Щ в -постановке (Щ/{k1, k2, k3}) являются 1, 3, 4, 5, 6.

Таблица 5 Представление фактор-множеств ФТ/k1, ФТ/k2, ФТ/k3 и ФТ/{k1, k2, k3}

i

ФТ/{k1})

ФТ/{k2})

ФТ/{k3})

ФТ/{k1, k2, k3})

1

2, 3, 4, 5, 6

2, 4

5, 6

2

1, 3, 4, 5, 6

1, 4

1, 4, 5, 6

1, 4

3

5

1, 2, 4, 6

1, 2, 4, 5, 6

4

3, 5, 6

1, 5, 6

5

1, 2, 3, 4, 6

6

6

3, 4, 5

1, 2, 3, 4

В свою очередь, результирующая окрестность определяется пересечением окрестностей Oi соответствующих альтернатив щi

Oi(Щ/{k1,k2...kM}) = Oi(Щ/k1) ? Oi(Щ/k2) ?·····? Oi(Щ/kM), (3)

ФТ/{k1,k2...kM} = O1(Щ/{k1,k2...kM}) O2(Щ/{k1,k2...kM}) … ON(Щ/ k1,k2...kM). (4)

Для бинарного представления процесса формирования фактор-множеств, а также в целях оптимизации хранения данных в электронных базах данных в [2] введено понятие ассоциативной матрицы фактор-множества, имеющей вид, показанный в табл. 6.

Таблица 6 Ассоциативная матрица фактор-множества линейного порядка L(/kj)

Окрестности\ Альтернативы

O1(1)

O2(2)

ON(N)

1

0

B12

B1N

2

B21

0

B2N

...

N

BN1

0

Здесь каждый столбец задаёт окрестность Oi(i) i -го варианта. Совокупность всех окрестностей по kl представляет собой транзитивное фактор-множество ФТ/kl . Вхождение варианта в соответствующую окрестность идентифицируется «1» в данной ячейке, отсутствие - «0». Так, если вариант входит в окрестность i -ой альтернативы, то элемент ассоциативной матрицы Bi,j = 1, и Bi,j = 0, если - не входит. В ассоциативной форме, окрестности представляют собой столбцы ассоциативной матрицы и, матрица результирующего фактор-множества для выбранных показателей качества формируется в виде последовательного поэлементного пересечения столбцов ассоциативных матриц фактор-множеств меньшей размерности

, l = {1, M}. (5)

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

по предыдущим ПК или критериям, следовательно, поэлементное произвольное (независимое от порядка) пересечение по выражению (5) - невозможно.

Cформулируем определение L-правила пересечения Oli .

Утверждение 1:

Пусть имеется два фактор-множества ФТ/k1, ФТ/k2. Назовем окрестностью OiН(Щ/<k1,k2>) неразличимых вариантов {щi-1, щi} по < k1,k2> выражение

OiН(Щ/<k1,k2>)) = [(Oi(Щ/ k1) ? Oi+1(Щ/ k1)) (Oi(Щ/ k1) ? Oi(Щ/ k2))]. (6)

Окрестность сравнимых вариантов OiС(Щ/<k1,k2>) определяется как

OiС(Щ/<k1,k2>) = Oi (Щ/k1),

где i - не является индексом несравнимого варианта. (7)

Тогда определим полное транзитивное фактор-множество ФТ/<k1,k2> как результат пересечения ФТ/k1, ФТ/k2 в виде совокупности окрестностей несравнимых и сравнимых вариантов

ФТ/<k1, k2> = OiН(Щ/<k1,k2>) OiС(Щ/<k1,k2>) (8)

Проиллюстрируем L-правило небольшим примером. Пусть линейные порядки по каждому из показателей качества заданы (1) и требуется решить задачу выбора в L-критериальной постановке L(/<k1, k2>). Фактор-множества порядков L(/k1), L(/k2) приведены в табл. 2 и табл.3, соответственно. Выделяем неразличимые по k1 группы альтернатив - это {щ1, щ2} и {щ4, щ6} (табл. 7). Пересекая, по правилу (6), окрестности неразличимых вариантов по k1, получаем:

Рис. 4 Выделение неразличимых по k1 групп альтернатив

O4Н(/<k1, k2>) = (O4(/k1) ? O6(/k1)) (O4(/k1) ? O4(/k2)) = ({3, 5, 6} ? {3, 4, 5}) ({3, 5, 6} ? {}) = {3, 5} {} = {3, 5},

O6Н(/<k1, k2>) = (O6(/k1) ? O4(/k1)) (O6(/k1) ? O6(/k2)) = ({3, 4, 5} ? {3, 5, 6}) ({3, 4, 5} ? {1, 2, 3, 4}) = {3, 5} {3, 4} = {щ3, щ4, щ5}.

Следовательно, неразличимость по k1 в отношении {щ4, щ6} устранена. Повторяя все вышеизложенное для альтернатив {щ1, щ2} получаем

O1Н(/<k1, k2>) = (O1(/k1) ? O2(/k1)) (O1(/k1) ? O1(/k2)) = ({2, 3, 4, 5, 6} ? {1, 3, 4, 5, 6}) ({2, 3, 4, 5, 6} ? {2, 4}) = {3, 4, 5, 6} {2, 4} = {2, 3, 4, 5, 6},

O2Н(/<k1, k2>) = (O2(/k1) ? O1(/k1)) (O2(/k1) ? O2(/k2)) = ({1, 3, 4, 5, 6} ? {2, 3, 4, 5, 6}) ({2, 3, 4, 5, 6} ? {1, 4}) = {3, 4, 5, 6} {1, 4} = {1, 3, 4, 5, 6}.

Неразличимость не раскрыта. Остальной порядок неопределенностей не содержит, следовательно, остальные окрестности фактор-множества ФТ/<k1, k2>, строго равны окрестностям фактор-множества ФТ/k1 (см. выражение (7), (8)). Таким образом, согласно (8), фактор-множество

В таблицу 8 сведены все окрестности фактор-множества ФТ/<k1, k2> для вариантов {i}, i = {1, 6}. Квазилинейный порядок, соответствующий этому фактор-множеству, следующий:

ФТ/<k1, k2> = {O1(/<k1, k2>), O2(/<k1, k2>), O3(/<k1, k2>), O4(/<k1, k2>), O5(/<k1, k2>), O6(/<k1, k2>)}.

L(/{k1, k2}) = <5, 3, 4, 6, {1, 2}> (9)

Таблица 7 Представление фактор-множества ФТ/< k1,k2>

i

Oi(/<k1, k2>)

1

2, 3, 4, 5, 6

2

1, 3, 4, 5, 6

3

5

4

3, 5

5

6

3, 4, 5

Теперь решим эту же задачу классическим способом, описанным в [1]. Линейный порядок L(/k1) задан выражением (1). Раскрываем неопределенности с помощью показателя качества k2. Альтернативы 1, 2 по данному показателю неразличимы, поэтому неопределенность раскрыть не удаётся. Значение k2(4) ? k2(6), следовательно {4, 6} раскрывается в <4, 6>. Тогда квазилинейный порядок для двух ПК в приоритете < k1, k2> можно представить в виде

L(/<k1, k2>) = <5, 3, 4, 6, {1, 2}> (10)

Сравнивая (9) и (10) убеждаемся, что частичные порядки идентичны, следовательно, пересечение фактор-множеств по L-правилу дает верный результат, а значит, Утверждение 1 можно считать верным.

Автоматизацию описанных процедур наиболее эффективно проводить в ассоциативной модели данных. В бинарном представлении, пересечение фактор-множеств ФТ/k1 и ФТ/k2 реализуется через поэлементное пересечение ассоциативных матриц А1 и А2 соответственно. Так как, неразличимые варианты {щi-1, щi} характеризуются значениями «1», стоящими симметрично, относительно главной диагонали матрицы (табл.6), то элементы матрицы А12 фактор-множества

ФТ/<k1, k2> можно определить как

(11)

где aij1 - элемент ассоциативной матрицы A1 фактор-множества ФТ/k1, aij2 - элемент ассоциативной матрицы A2 фактор-множества ФТ/k2, aij - элемент ассоциативной матрицы A12 фактор-множества ФТ/{k1, k2}.

Из выражения (11) видно, что процесс формирования пересечения по L-правилу, в бинарном виде проще, т.к. требует значительно меньше операторов.

Проиллюстрируем полученное правило примером. Пусть линейные порядки заданы выражениями (1) и требуется решить задачу выбора в соответствии с L(/<k1,k2>) -правилом. Ассоциативные матрицы фактор-множеств порядков L(/k1), L(/k2) показаны в таблицах 9 и 10 соответственно. В табл. 9 цветом выделены элементы, соответствующие неразличимым вариантам по k1.

Таблица 8 Ассоциативная матрица фактор-множества ФТ/ k1

Окрестности\ Альтернативы

O1(i)

O2(i)

O3(i)

O4(i)

O5(i)

O6(i)

1

0

1

0

0

0

0

2

1

0

0

0

0

0

3

1

1

0

1

0

1

4

1

1

0

0

0

1

5

1

1

1

1

0

1

6

1

1

0

1

0

0

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

Таблица 9 Ассоциативная матрица фактор-множества ФТ/ k2

Окрестности Альтернативы

O1(i)

O2(i)

O3(i)

O4(i)

O5(i)

O6(i)

1

0

1

1

0

1

1

2

1

0

1

0

1

1

3

0

0

0

0

1

1

4

1

1

1

0

1

1

5

0

0

0

0

0

0

6

0

0

1

0

1

0

a21рез = a211 ? a212 =1 ? 1 = 1,

a12рез = a121 ? a122 =1 ? 1 = 1,

a64рез = a641 ? a642 =1 ? 0 = 0,

a46рез = a461 ? a462 =1 ? 1 = 1.

Таблица 10 Ассоциативная матрица фактор-множества ФТ/< k1, k2>

Окрестности\ Альтернативы

O1(i)

O2(i)

O3(i)

O4(i)

O5(i)

O6(i)

1

0

1

0

0

0

0

2

1

0

0

0

0

0

3

1

1

0

1

0

1

4

1

1

0

0

0

1

5

1

1

1

1

0

1

6

1

1

0

0

0

0

Квазилинейный порядок, соответствующий данной матрице результирующего фактор-множества, выглядит, как и полученный ранее в реляционных структурах (10):

L(/{k1, k2}) = <5, 3, 4, 6, {1, 2}> (11)

Выводы

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

Литература

1. Кандырин Ю.В. Методы и модели многокритериального выбора вариантов в САПР. Учебное пособие для вузов. М.: Издательство МЭИ, 2004г. -172с.

2. Кандырин Ю.В., Кошелев А.М. Алгоритмы установления приоритетов объектов по техническим показателям в целях назначения оптимальной очередности их ремонтов. М: Издательство Машиностроение, журнал «Вестник информационных и компьютерных технологий», №7, 2006.

3. С.18-25.

4. Кандырин Ю.В. Принципы построения информационных систем для автоматизированного многокритериального выбора. -М.: Журнал “Радиотехника”, 1999г. № 5. -С. 32-37

Размещено на Allbest.ru

...

Подобные документы

  • Характеристика основных средств обеспечения гибкости моделей в системе КОМПАС-3D. Разработка параметрического эскиза операции, настройка опций в программе. Особенности метода создания ассоциативных чертежей по твердотельным параметрическим моделям.

    лабораторная работа [376,7 K], добавлен 25.06.2013

  • Создание структуры интеллектуального анализа данных. Дерево решений. Характеристики кластера, определение групп объектов или событий. Линейная и логистическая регрессии. Правила ассоциативных решений. Алгоритм Байеса. Анализ с помощью нейронной сети.

    контрольная работа [2,0 M], добавлен 13.06.2014

  • Изучение основных средств обеспечения гибкости моделей в системе КОМПАС-3D. Изучение метода создания ассоциативных чертежей по твердотельным параметрическим моделям. Характеристика видов параметризации. Понятие вида чертежа. Управление состоянием видов.

    презентация [1,6 M], добавлен 25.06.2013

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

    дипломная работа [3,0 M], добавлен 06.07.2012

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

    лабораторная работа [2,8 M], добавлен 14.07.2012

  • APRIORI - масштабируемый алгоритм поиска ассоциативных правил. Создание официального информационного портала для студенческого совета УлГУ "Династия". Принципы построение и создания хранилища данных. Перенос информационного портала на сервер ulsu.ru.

    курсовая работа [1,5 M], добавлен 21.12.2015

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

    дипломная работа [332,2 K], добавлен 30.11.2012

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

    курсовая работа [273,9 K], добавлен 28.07.2009

  • Средства обеспечения гибкости моделей. Анимация и планирование детали. Настройка глобальных привязок. Параметризация в эскизах. Характеристика особенностей проецирования объектов. Создание ассоциативного чертежа. Использование переменных и выражений.

    методичка [2,6 M], добавлен 25.06.2013

  • Вероятностный подход к поиску. Основы теории вероятностей. Содержание правила Байеса. Проблема ранжирования документов, принцип вероятности. Бинарная модель независимости. Вывод функции ранжирования для терминов запросов. Okapi BM25: небинарная модель.

    презентация [406,9 K], добавлен 06.01.2014

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

    контрольная работа [208,4 K], добавлен 14.06.2013

  • Исследование основных отличий ассоциативных массивов от массивов скаляров. Разработка библиотеки классов. Выбор языка программирования. Сравнение языка C++ с Delphi, Java и JavaScript. Изучение методики тестирования и структуры тестового приложения.

    практическая работа [390,2 K], добавлен 06.01.2013

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

    курсовая работа [2,6 M], добавлен 28.02.2012

  • Описание и расчет параметров систем с очередями для различных вариантов (один или несколько серверов - одна очередь, несколько серверов - несколько очередей). Проведение оценки производительности компьютерной сети на основе данных о ее загрузке.

    курсовая работа [9,2 M], добавлен 19.11.2013

  • Анализ книги профессора Мюнхенского университета Юргена Плате, посвященной основным понятиям алгоритмизации и принципам написания алгоритмов, основам и правилам составления программ на языке программирования Си. Процесс работы с файлами и указателями.

    анализ книги [170,8 K], добавлен 15.05.2009

  • Обзор некоторых сведений о матрицах. Описание этапов работы с функциями. Проектирование программы для выполнения вычислений над матрицами в среде программирования MSVisualStudio 2008, при помощи языка программирования C++. Проверка результатов в Mathcad.

    курсовая работа [182,0 K], добавлен 06.04.2013

  • Понятие локальных вычислительных сетей, их виды и принципы построения. Топология (кольцо, звезда и шина) и древовидная структура ЛВС. Алгоритм решения экономической задачи по осуществляемой страховой деятельности на территории России по видам полисов.

    курсовая работа [604,2 K], добавлен 23.04.2013

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

    дипломная работа [158,1 K], добавлен 17.07.2010

  • Определение методики создания и поддержки веб-сайта о дорожном движении. Описания выбора подходящей среды разработки, создания карты и тематических разделов сайта. Характеристика учета возраста, индивидуальных и личностных особенностей пользователей.

    курсовая работа [11,3 M], добавлен 29.03.2012

  • Использование компьютерных сетей для передачи данных. Основные преимущества использования корпоративных сетей, защищенных от доступа извне физически или при помощи аппаратно программных средств сетевой защиты. Сетевой экран и алгоритмы шифрования.

    дипломная работа [573,3 K], добавлен 25.09.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.