Сайт Информационных Технологий

ВЫБОР И УПОРЯДОЧЕНИЕ ОБЪЕКТОВ С ИЕРАРХИЧЕСКОЙ СИСТЕМОЙ ПОКАЗАТЕЛЕЙ

С.В.Микони, Р.В.Козченко, П.Г.Созоновский

Петербургский государственный университет путей сообщения

Abstract - The former designed system for the best object choosing from database is developed to create new properties. The main additional function of the system is ordering of objects, i.e. rank associating to each object. The procedure of generalized attribute calculation is proposed for objects with complex attribute system. The goal function is adopted to attribute calculation at the hierarchical database. The linguistic variable incodding procedure is considered for its participating at the best object choosing.

1. Постановка задачи

В [1] была представлена система выбора наилучших вариантов (СВ), обладающая следующими свойствами:

1) универсальность СВ относительно методов выбора в дискретном множестве;

2) возможность доступа из СВ к базам данных различного типа;

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

По результатам исследований были разработаны образцы СВ, спроектирован-ные в среде MS DOS (1997г) и Windows-95 (1998г).

Расширение области применения СВ и улучшение пользовательских характеристик потребовало решения следующих задач:

1) обеспечить наряду с выбором наилучших объектов их упорядочение относительно заданных показателей;

2) оценивать объекты, характеризуемые иерархической системой показателей;

3) адаптировать функцию суперкритерия к решению 2-х предыдущих задач;

4) реализовать экспертные методы выбора предпочтений для расчёта весов критериев;

5) охватить критериальными методами выбора нечисловые атрибуты;

6) модифицировать архитектуру системы под новые функции.

 

2. Упорядочение объектов

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

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

Наиболее простым путём решения задачи упорядочения в СВ является пометка найденных наилучших объектов, исключение их из общего списка и итеративный поиск наилучших объектов до получения пустого списка. Этот способ применим как для методов условной оптимизации, так и для метода суперкритерия. Поскольку задача упорядочения в этом случае более сложна, чем задача поиска наилучших объектов, необходимо предусмотреть 2 режима: ВЫБОР и ПОРЯДОК.

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

3. Оценивание объектов со сложной системой показателей

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

Количество баз данных для представления сложных систем показателей определяется исходя из эргономических соображений, основанных на числе признаков 7± 2 в одной базе данных. Декомпозиция системы показателей решается путём их кластеризации (группировки) относительно выбранных критериев общности.

С целью итеративного вычисления обобщённого показателя, характеризующего объект, базы данных связываются в иерархическую структуру. Эта процедура выполняется при настройке СВ на предметную область. Из списка баз данных выбирается та, которая принимается за наиболее общую (корневую). От показателей (атрибутов) общей базы данных выполняются ссылки на имена баз данных, детализирующих показатели предыдущей базы. Этот процесс продолжается до охвата всех баз данных из списка.

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

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

4. Функция суперкритерия

Для свёртки показателей обычно используется аддитивная функция вида:

f1= (1)

В ней y i - значение i-го критерия;

si - нормирующий коэффициент, равный максимальному значению шкалы для i-го критерия и переводящий его в безразмерную величину;

a i - вес i-го критерия, пропорциональ-ный его значимости.

Суммирование может выполняться как по всем n, так и по k<n выбранным критериям. Во 2-м случае n-k атрибутов играют роль ограничений, а формула (1) - роль целевой функции. Возможны 3 варианта оптимизации:

1) все k критериев максимизируются:

f® max;

2) все k критериев минимизируются:

f ® min;

3) p критериев максимизируются, а q критериев минимизируются: p+q=k;

Вариант 3 сводится к варианту 1 с помощью следующей составной функции:

f2= (2) В более сложных случаях вес i-го критерия может представляться не переменной a i, а функцией. Представление функций в качестве весов требует обеспечения ввода в СВ формул и значений входящих в них переменных, если они не содержатся в базе данных СВ. Если же они содержатся в базе данных, то следует адресовать их в качестве аргументов введённой формулы.

Метод суперкритерия отличается от метода приоритетов использованием интервальной шкалы для упорядочения критериев по важности. Эта шкала более информативна, чем порядковая (ранговая), так как позволяет учитывать нелинейную зависимость между коэффициентами значимости (весами) критериев. Например, оценкам значимости 3-х объектов в процентной шкале: 100, 50 и 45 процентов соответствуют места 1, 2 и 3 в ранговой шкале. При этом в ранговой шкале утрачиваются неравные интервалы величиной 50 и 5 соответственно, характеризующие неравномерность соотношения коэффициентов 100, 50 и 45. Учёт такого различия важен в тех случаях, когда необходимо учитывать не только место объекта среди других, ему подобных, но и интервал значений показателя качества для объектов, занимающих соседние места.

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

1) прямое задание нормированных весов 0? a i? 1, i=1,…,k, S a i =1.

2) задание ненормированных весов a i'>1, i=1,…,k.

3) задание мер предпочтения в процентной шкале [0-100].

4) задание матрицы попарных сравнений критериев (МПС).

При использовании способов 2-4 требуется выполнять преобразование введённых предпочтений к нормированным весам. Для способов 2 и 3 нормирование выполняется по формуле:

a i=a i'/ (3)

Расчёт весов критериев при задании предпочтений матрицей попарных сравнений выполняется на основе вычисления собственного вектора W положительной квадратной матрицы A [2].

5. Подготовка лингвистических атрибутов к выбору вариантов

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

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

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

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

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

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

1. Прямое кодирование лингвистического атрибута. Оно естественно для переменных, чьи значения являются качественными оценками. Например, значения “низкая”, “средняя”, “высокая” (эргономичность) ранжируются числами 0,1,2 (или наоборот).

2. Косвенное кодирование лингвистического атрибута. Для переменных с номинальными значениями прямое кодирование следует рассматривать как искусственный приём. Оно может выполняться косвенно за счёт введения экспертом некоторого признака относительно которого возможно упорядочение значений. Например, значения Санкт-Петербург, Москва, Орёл можно упорядочить по географической широте (с севера на юг) с помощью цифр 1,2,3.

3. Кодирование переменных со смешанными значениями.

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

Для раскрытия содержания значений переменной специалист (эксперт) должен предпринять следующие действия:

1) выбрать совокупность признаков, которую можно извлечь из значения сложной переменной;

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

3) разложить каждое значение сложной переменной в вектор значений выбранных признаков.

Для выполнения изложенных действий в системе кодирования предусмотрено окно с наименованием сложной переменной. В это окно заносятся имена извлекаемых из неё признаков. Далее, поочерёдно выводится окно каждого признака, в которое заносится его шкала.

Литература

1. Микони С.В., Козченко Р.В., Созоновский П.Г. Выбор наилучших вариантов из баз данных. Сборник докладов конф. по мягким вычислениям и измерениям. SCM'99, -СПб.: СПГЭТУ, 1999.

2. Саати Т., Кернс К. Аналитическое планирование. Организация систем. -М.: Радио и связь, 1991.


Site of Information Technologies
Designed by  inftech@webservis.ru.