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

Рис 2. Линейные порядки альтернатив показателям качества

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

Рис 3. Фактор-множества представленные набором совокупностей окрестностей

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

Oi((/{k1,k₂...k_l}) = O_i(/k₁₎ O_i(/k₂) … O_i(/k_l). (1)

Известно, что s-слой по Парето _s на множестве определяется как

_s = ( \ )

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

Для построения алгоритма автоматизированного многокритериального упорядочивания оптимальных по Парето вариантов в слое введем ассоциативную модель описывающую фактор-множества /k_l (рис.4).

упорядочивание альтернатива ассоциативный

Рис 4. Ассоциативная матрица фактор-множества /k_l, представленная совокупностью окрестностей всех альтернатив.

Элемент B_ij ассоциативной матрицы определяется следующим образом

(2)

В случае, когда альтернативы несравнимы, элемент B_i,j принимает значение "1" (см. определение окрестности альтернативы).

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

Рис 5. Результирующая ассоциативная матрица (РАМ)

Элемент РАМ определяется следующим образом:

, (3)

где - элемент ассоциативной матрицы для показателей качества {k_l}. Альтернатива _i включается в множество -решений, если для столбца, т. е. для окрестности альтернативы _i: О_i(_i/{k_l}) выполняется условие

, (4)

означающее отсутствие альтернатив, доминирующих вариант _i.

Так как "0" окрестности (4) однозначно определяют -оптимальные варианты, то после их удаления, для дальнейшего структурирования можно переходить к поиску второго слоя. Следующий, второй слой, будет содержать все ₂ - нехудшие варианты для \₁. Далее осуществляется переход к следующему -слою, содержащему нехудшие варианты из оставшегося множества, не включающего альтернативы предыдущих слоев. Если после исключения альтернатив всех предыдущих слоёв мощность \ , то задача -структурирования вариантов на МВА завершена.

Рассмотрим методы получения -расслоений в ассоциативных структурах фактор-множеств.

Метод исключения столбцов и строк из РАМ

Цель метода - найти все _s-слои на МВА . Для этого последовательно из результирующей матрицы удаляются столбцы и строки, соответствующие вариантам, имеющим на данном шаге пустые окрестности О_i(_i/{k_l}) = . То есть, если _i - входит в множество нехудших решений _s, то столбец О_i(_i /{k_l}) и строка _i исключается из ассоциативной матрицы (рис. 6).

Рис 6. Исключение альтернативы _i из РАМ

Если в матрице на s-шаге окажется q нулевых столбцов, то удаляются все эти столбцы и соответствующие им строки (рис. 7).

Рис 7. Матрица, полученная в результате исключений нехудших вариантов

Как видно из рис. 7, результирующая матрица уже не содержит альтернатив предыдущих _s-1 -слоёв и их окрестностей. Дальнейший анализ, сводится к использованию выражения (4) и дальнейшему исключению альтернатив, входящих в последующее (s+1) множество нехудших решений.

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

Рассмотрим далее еще один предлагаемый вариант введения -расслоения.

Метод последовательного перемещения слоев в РАМ

Будем изменять результирующую ассоциативную матрицу так, чтобы искусственно ухудшать нехудшие альтернативы каждого текущего _s -слоя. Идея последовательного анализа принадлежности вариантов к текущему паретовскому слою, с последующим его «ухудшением» демонстрируется рис. 8 (для min).

Рис. 8. Последовательное ухудшение _s - слоёв для установления приоритетов

Пусть, например (рис. 6), альтернатива _i входит в первый ₁-слой, т.к. О_i(_i/{k_l}) = и, следовательно, должна быть перенесена в самый «худший слой». Перенос альтернативы производится по следующему правилу: в столбец, соответствующий О_i(_i /{k_l}) в ячейки заносится «1» (это означает, что

Рис 9. Искусственное перемещение -слоев

альтернатива _i будет хуже всех вариантов, кроме самой себя), в остальные столбцы, в ячейки, соответвующие _i заносится «0» (альтернативы становятся лучше исключаемой (рис. 9)).

При перемещении нескольких альтернатив {_j}, j = {1, q N} изменяются только те значения элементов, которые не имеют индексов перемещаемых альтернатив. При этом значения G_ip, G_pi для _i {_j} принимают вид

G_pi = 1, p ? i, p ? j, p = {1, [N - (q - 1)]}, j = {1, q N}, i = {1, N}

G_ip = 0, p i, p ? j, p = {1, (N - q}, j = {1, q N}, i = {1, N} (5)

где i - индекс исключаемых альтернатив: _i {_j}.

Выражение (5) иллюстрируется ниже приведенным примером. Ограничение p ? j необходимо для сохранения информации о доминируемости между альтернативами. Если его снять, то перемещаемый слой расслоится на j слоев.

Указанное преобразование должно быть проведено для всех исключаемых альтернатив. Полученная ассоциативная матрица вновь исследуется на наличие нехудших решений по правилу (4), после переноса _s-1 решения по правилу (5), осуществляется переход к следующему паретовскому слою и т. д. Главным достоинством данного метода является сохранение размерности (N) результирующей матрицы, что существенно облегчает алгоритм реализации на ЭВМ.

Критерии остановки перемещения -слоёв

В работе предлагается несколько способов контроля последнего шага в методе последовательного перемещения слоев:

· Накапливание альтернатив. Ведется подсчет ухудшаемых альтернатив. Как только была включена последняя альтернатива из , поиск останавливается. Перенос _s -слоя, состоящего из Л альтернатив приводит к

_s = _(s-1) + Л;

где _s - накопленное количество альтернатив.

При этом условие прекращения построения расслоений _s = N

Сравнение ассоциативных матриц слоев. Каждый последующий _s -слой, идентифицируется с первым ₁ посредством сравнения матриц. При их совпадении, поиск прекращается. Условие прекращения построения слоев можно выявить тождеством АМ^s АМ^1, где АМ^s - ассоциативная матрица текущего _s -слоя (т.е. слоя, где осуществляется, в настоящий момент, поиск нехудших альтернатив), АМ¹ - ассоциативная матрица первого ₁ -слоя.

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

Рассмотрим пример, иллюстрирующий применение метода последовательного перемещения слоев для установления приоритетов вариантов на МВА .

Пример. Пусть исходное множество W задано шестью альтернативами, для каждой из которых определены три числовые характеристики - показатели качества k_1, k₂, k_3. Описание исходного множества представим реляционной моделью (рис. 10). Пусть требуется получить очередь альтернатив при следующих ингредиентах Р₁ = k₁ , Р₂ = k₂ двух показателей качества.

Рис. 10. Реляционная модель исходных данных

Решение задачи начнем с построения линейных порядков по k₁ и k₂. (Построение линейного порядка по столбцу k₃ не требуется, т. к. эта характеристика не используется по условию задачи.) L(/k₁) = < ₅, ₆, ₃, ₁, ₂, ₄ >, L(/k₂) = < ₆, ₅, ₁, ₃, ₂, ₄ >. Построим ассоциативные матрицы фактор-множеств по каждому линейному порядку. Элементы этих матриц определяются выражением (2). На рис.11 представлена АМ₁ для фактор-множества /k₁, а на рис.12 представлена АМ₂ для фактор-множества /k₂.

Рис 11. Ассоциативная матрица АМ₁ для фактор-множества /k₁

Столбцы этой матрицы представляют собой окрестности соответствующих вариантов. Соответственно, пустые окрестности (О₅(₅ /{k_l}) = ) идентифицируют недоминируемые варианты (в данной матрице - ₅).

Рис 12. Ассоциативная матрица АМ₂ для фактор-множества /k₂

Результирующую ассоциативную матрицу (РАМ) получаем путем пересечения окрестностей фактор-множеств /k₁ /k₂ для всех альтернатив (1).

Рис. 13. Результирующая ассоциативная матрица фактор-множества /{k₁, k₂}

Анализ результирующей матрицы для /{k₁, k₂} позволяет выделить множество нехудших решений, как совокупность недоминируемых альтернатив, имеющих пустые окрестности О₅ (₅) и О₆ (₆): {₅, ₆}.

Для дальнейшего поиска решения воспользуемся методом последовательного перемещения слоев. Искусственно ухудшим альтернативы ₁-слоя {₅, ₆}. Для этого по правилу (5) элементы в столбцах, соответствующих ₅ и ₆ должны принять значение «1», а все элементы в строках, соответствующих ₅ и ₆ значение «0». Серым тоном выделены строки и столбцы, подвергающиеся преобразованию. Так, как элементы ₅ и ₆ ухудшаются одновременно (находятся в одном слое), то G₅₆, G₆₅, в соответствии (5) не изменяют свое значение. Соответствующее преобразование ассоциативной матрицы показано на рис. 14.

Рис 14. Преобразование матрицы / {k₁, k₂}, искусственным ухудшением ₁ -слоя

Итак, матрица /{k₁, k₂} после искусственного ухудшения первого ₁ -слоя примет вид, представленный на рис. 15, а число ухудшенных альтернатив равно 2.

Рис 15. Результирующая матрица после перемещения ₁ -слоя

Очевидно, что теперь множество неулучшаемых альтернатив, соответствующее строкам с нулевыми элементами, задает ₂-слой: _р2 - {₁, ₃}. Вновь, преобразовывая матрицу по ранее рассмотренному правилу (5), переносим ₁ и ₃ в подмножество худших вариантов.

Рис 16. Преобразование матрицы, представленной на рис. 15 с целью искусственного ухудшения альтернатив ₁, ₃

В результате матрица /{k₁, k₂} после «перемещения» ₁ и ₂ слоев в число худших, приобретает вид, представленный на рис.17, а общее число ухудшенных альтернатив становится равным 4.

Рис 17. Результирующая матрица после перемещения ₂ -слоя в подмножество худших вариантов

Проводим дальнейшее преобразование матрицы, перемещая нехудшие варианты ₃ -слоя, состоящего из одного варианта {₂} в число худших.

Рис 18. Преобразование результирующей матрицы (рис. 17) для выявления 4-го паретовского слоя

В четвертом ₄-слое идентифицируется одна альтернатива - ₄, а общее число альтернатив, входящих в четыре _1-4 -слоя составит 5.

Рис 19. Результирующая матрица после перемещения ₃ -слоя в число худших

Для демонстрации метода сравнения ассоциативных матриц преобразовываем матрицу, изображенную на рис.19 посредством искусственного ухудшения варианта ₄ по ранее принятым правилам (5).

Рис 20. Преобразование результирующей матрицы к 5-му паретовскому слою.

Метод накапливания альтернатив указывает на возможность остановки поиска, так как общее число ухудшенных альтернатив достигло 6 = .

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

Рис 21. Результирующая матрица после перемещения ₄ -слоя.

Сравнивая матрицы, изображенные на рис. 21 и рис. 12 убеждаемся, что они абсолютно идентичны, поэтому поиск может быть прекращён. Однако число накопленных альтернатив стало равно 6 еще до перемещения 4-го паретовского слоя, т.е. поиск можно было прекратить раньше. Это и определяет метод накапливания альтернатив, как приоритетный по отношению к методу сравнения ассоциативных матриц слоев, из-за меньшего числа итераций. Итак, -расслоение по двум показателям качества {k_1, k₂} приводит к следующему линейному порядку <{₅, ₆}, {₁, ₃}, ₂, ₄>, на основании которого может быть задана очередь на ремонт в среде однородных альтернатив.

Выводы

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

Литература

1. Горбатов В.А. Теория частично упорядоченных систем. -М.: Сов. радио, 1976г. -336 стр.

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

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

4. Кандырин Ю.В. Автоматизированный многокритериальный выбор альтернатив в инженерном проектировании. Учебное пособие. -М.: Издательство МЭИ, 1992г - 73с.

5. Кандырин Ю.В. Анализ свойств неметрических критериев выбора компонентов электронных устройств Журнал «Надежность» № 3 (10). -М.: Издательский Дом «Технологии» 2004г. - С. 48-54.

6. Кандырин Ю.В. Сравнительный анализ технических объектов с целью формирования оптимальных очередей ремонтов. Журнал «Надежность» № 2 (13). -М.: Издательский Дом «Технологии» 2005г. - С. 34 - 44.

7. Кошелев А.М., Кандырин Ю.В. Алгоритм построения фактор-множеств для решения задач многокритериального выбора. Материалы Х Международной научно-технической конференции студентов и аспирантов, -М.: Издательство МЭИ, 2-3 марта 2004г. С. 69.

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