WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 59 | 60 || 62 | 63 |   ...   | 82 |

j For the decision of a problem (3)-(5) procedure of reduction of set of allowable decisions Z on a condition Xs=(Xs Xs …Xs ) of acyclicity of the relation which corresponds to the decision of a problem of a finding of 1 2 N strict resulting ranging of objects of set A is used. The analysis of variants in view of a condition of acyclicity of the decision is carried out with use of the procedure described in [Гнатиенко, 2005].

Let's designate set of all possible values which can get elements of a basic variant, through В0. Sets of a kind Вare formed of set Xs by association of three various columns of a matrix Xs: X0 X0 X0, 1j < j < j N, j1 j2 j3 1 2 X0,X0,X0 Xs. Capacity of this set is equal В0=6.

j1 j2 jBasic set В0 = B0 B0 B0, B0=(-1,1)Т, i=1,…,3, we shall name set of elements of a matrix of which values of 1 2 3 i basic vectors get out.

Columns of basic set B0=(-1,1)Т, i=1,2,3, we shall name subsets of basic set.

i The reduced basic set Вs, ВsВ0, s=1,2,..., we shall name a matrix which is formed of a matrix В0 by removal from it separate elements.

It is known [Макаров, 1982], that for matrixes of pair comparisons with elements of a kind (2) requirement of absence of cycles is equivalent to the requirement of absence of cycles of length three (Т=3).

As the top triangular matrix of a matrix Pi, iI, contains the full information on all matrix indexes of objects need to be considered only on increase, that is 1 i1 < i2 < i3 n. Indexes of elements of a vector of relations between objects also satisfy to conditions 1 j1 < j2 < j3 N.

Let's designate through function of two arguments which values are calculated under the formula j =(i1,i2 )= (i1 -1)n + i2 -(i1 +1)i1 / 2, 1 i1 < i2 < n.

Algorithm In a problem of definition of the linear order nearest to the set cyclic relation, it is possible to present algorithm of the consecutive analysis and elimination of inadmissible elements in the following kind.

Step 1. Let's put initial values of the decision of a problem equal x( j) = c( j), j J.

262 Mathematical Foundations of AI Step 2. The organization of three enclosed cycles: i:=1 до n-2; i :=i+1 до n-1; i :=i +1 до n. Variables of cycles i, 1 2 i, i are indexes of objects. In a body of these cycles the following steps are executed.

1 Step 3. Definition of indexes of elements j, j, j the current basic set B0 on indexes of objects і, і, і : j=(і,і ), 1 2 j 1 2 j =(і,і ), j =(і,і ).

1 2 2 1 Step 4. Definition of three of objects, relations between which form cycles. Quantity of all three n objects equally:

k3=n*(n-1)*(n-2)/6.

Quantity of cycles on set n objects it is equal d=(n3-4n)/24 for even and d=(n3-n)/24 for odd values n.

Step 5. Generation of a vector of indexes of participation of relations between objects in cycles: vc( j), j J.

That is, value vc( j), j J, is equal to quantity of ocurrences of the relation with an index j, j J, in cyclic three.

Step 6. Definition of values of vectors of indexes vic( j), j J, participations of the inverted relations x( j)= c( j)- 2, j J.

The choice of an index of the relation between objects is carried out in view of three criteria:

К – inversion of the relation does not generate new three;

К – the total quantity of cycles for the inverted relation is minimal;

К – the difference of quantity of cycles for the set relation and inverted is minimal.

Step 7. Definition of relations, which replacement on inverted, as much as possible reduces quantity of cycles.

Step 8. Choice of an index of the relation for decision-making on its final inverting.

Step 9. The termination of cycles on i, i, i.

1 Step 10. Recurrence of points 1-9 of the resulted algorithm until in the decision x( j), j J, problems (3)-(5) exist cycles.

Conclusion The resulted algorithm allows finding consistently for final quantity of steps the ranking of the objects nearest to the cyclic relation set by the expert between objects.

Computing experiments have confirmed efficiency of the resulted algorithm. Received with the help of algorithm of the decision are one of the rankings, the nearest to the cyclic relation set by the expert on set of objects.

Bibliography [Литвак, 1983] Литвак Б.Г. Меры близости и результирующие ранжирования // Кибернетика. 1983. №1. С.57-63.

[Миркин, 1976] Миркин Б.Г. Анализ качественных признаков: Математические модели и методы. М.: Статистика.

1976. 166 с.

[Левин, 1987] Левин М.Ш. Современные подходы к оценке эффективности плановых и проектных решений в машиностроении. Обзорная информация. Сер.С-9. Автоматизированные системы проектирования и управления.

М.: ВНИИТЭМР. 1987. Вып.3.-56с.

[Гнатиенко, 1993] Гнатиенко Г.Н., Микулич А.Ю. Методы метризации качественных ранжировок объектов. Киев.ун-т.Киев.1993. Библиогр.: 6 назв. Рус. Деп.в УкрНИИНТИ 10.03.93. №432-Ук93.-10с.

[Гнатиенко, 2005] Гнатієнко Г.М. Процедура послідовного аналізу та відсіювання варіантів з урахуванням ациклічності розв’язку//Наукові праці Кіровоградського державного університету. Технічні науки.-Вип.16.-Кіровоград. 2005.С.294-299.

[Макаров, 1982] Макаров И.М., Виноградская Т.М., Рубчинский А.А. и др. Теория выбора и принятия решений:

Учебное пособие. М.:Наука, 1982.-328с.

Author’s Information Grigoriy M. Gnatienko – T. Shevchenko Kiev National University, Faculty of Cybernetics, Dr.Ph., Kiev, Ukraine;

e-mail: G.Gnatienko@veres.com.ua XII-th International Conference "Knowledge - Dialogue - Solution" СПОСОБЫ ПРЕДСТАВЛЕНИЯ МАТРИЦ ОТНОШЕНИЙ МЕЖДУ ПАРАМИ ОБЪЕКТОВ И ПРЕВРАЩЕНИЯ МЕЖДУ НИМИ Григорий Н.Гнатиенко Аннотация: Описаны способы представления отношений между парами объектов при целостном выборе. Рассматриваются методы выявления и виды отношений между объектами. Приводится таблица соответствий между различными формами представления отношений.

Ключевые слова: парные сравнения, ранжирование, тождественные преобразования, балльная оценка, эксперт.

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

Известны многочисленные результаты систематических исследований задачи сравнения друх объектов и выделения «лучшего» из них. Эти результаты свидетельствуют о том, что такая операция является сложной для эксперта, если объект характеризуется большим количеством параметров. Уже при наличии трех характеристик объектов эксперты используют упрощающие задачу эвристики, которые могут приводить к противоречиям. Эти ограничения свойственны человеку в силу специфических характеристик его оперативной памяти [Ларичев, 1980]. При этом, согласно [Larichev, 1980], в задачах целостного выбора возможности эксперта очень велики, поскольку он использует гештальт (целостный образ) объекта как одну структурную единицу информации. Гештальт, как правило, богаче соответствующего набора параметровю В связи с этим решения, принятые на основании целостного представления, часто не совпадают с решениями тех же задач формальными методами.

Постановка задачи Пусть рассматривается множество n объектов ai A, i I = {1,...,n}, (1) параметры которых не выделяются. С учетом природы практической задачи целостный выбор осуществляется в связи с тем, что параметры объектов невозможно измерить, они неизвестны по некоторым причинам или являются несущественными для принятия решения. Эксперту предлагается определить отношения (предпочтения, сходства-различия, близости или другие) между объектами, используя личный опыт или некоторые иные косвенные свидетельства.

Одним из основных способов представления отношений между объектами множества (1) являются матрицы парных сравнений (МПС):

P = (pij ), i, j I = {1,..., n}.

(2) Элементами pij,i, j I, матриц вида (2) являются действительные числа, отражающие в некоторой шкале результаты сравнения экспертом объектов с индексами i,i I, и j, j I.

Симметрические элементы матриц pij и p выбираются равными, если соответствующие им объекты ji равноценны с точки зрения эксперта. Если же объект с индексом i,i I, по мнению эксперта, является «лучшим», чем объект с индексом j, j I, то отношение между симметричными элементами матрицы устанавливается pij > p, pij, p P, i, j I. Кроме этих очевидных условий на элементы ji ji 264 Mathematical Foundations of AI матрицы вида (2), как правило, накладываются дополнительные (калибровочные) ограничения, которые однозначно связывают попарно симметрические элементы pij и p.

ji В зависимости от условий задачи, значения элементов pij,i, j I, матриц вида (2) могут иметь различный смысл. Матрица P может характеризовать относительный «вес» объектов, если определяется вектор предпочтений на множестве объектов (1), может указывать на относительную важность параметров объектов при принятии решений или свидетельствовать об относительной компетентности экспертов в паре (i, j), i, j I.

Метод парных сравнение и виды МПС Одним из наиболее распространенных и наиболее надежных ([Миркин, 1974]) методов выявления отношений на заданном множестве объектов (1) является метод парных (иногда употребляется термин – попарных [Паниотто, 1986], [Юшманов, 1990]) сравнений ([Дэвид, 1978], [Литвак, 1982]). При использовании этого метода результаты экспертизы заносятся в МПС вида (2) или представляются в виде ориентированного графа парных сравнений, вершинами которого являются объекты, а дуги характеризуют отношения между ними.

Отношения на заданном множестве объектов выявляются также путем использования методов множественного сравнения ([Паниотто, 1982]), ранжирования ([Миркин, 1974]), приписывания баллов ([Кини, 1981]) и других методов. При этом МПС являются наиболее общим способом представления отношений на множестве объектов ([Миркин, 1980]).

МПС вида (2) могут быть полными (когда все элементы матрицы P полностью определены) или неполными, то есть такими, в которых не все элементы pij P, i, j I, известны. В последнем случае может возникать задача восстановления неизвестных элементов МПС ([Загоруйко, 1999]), а также определения «веса» объектов по неполной МПС [Чеботарев, 1989].

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

Однако в этой работе будем рассматривать только точечные значения элементов МПС.

Способы представления отношений между объектами Согласно [Миркин, 1980], при сравнении объектов множества (1) существует четыре основных способа представления результатов такого сравнения в виде элементов МПС вида (2). Оценка экспертом отношения между объектами может выражать:

П1) просто факт предпочтения эксперта одного объекта другому или равноценности между объектами (простая структура) ([Кемени, 1972], [Кендэлл, 1975], [Литвак, 1982]);

П2) долю суммарной интенсивности предпочтения сравниваемых объектов, которая приходится на каждый из них ([Литвак, 1982]), так что pij + p = T, i, j I, где T 0 - некоторое действительное ji число, одинаковое для всех pij P, i, j I; чаще всего T = 1 и тогда говорят, что применяется вероятностная калибровка; при T = 0 имеет место кососимметрическая калибровка, а при T > 0 - турнирная калибровка;

П3) балльную оценку отношения ([Кини, 1981]) pij R, p R, i, j I, где R - множество ji действительных чисел; иногда устанавливаются односторонние или двухсторонние границы допустимого приписывания баллов;

П4) во сколько раз один объект превосходит другой, то есть pij = 1/ p, i, j I, - говорят, что имеет ji место степенная калибровка ([Миркин, 1980], [Белкин, 1990]).

Важной характеристикой метризованных отношений является их сверхтранзитивность или кардинальная согласованность в силе предпочтения, которая состоит в выполнении условий: pij > 0 и pij p = pik, jk i, j,k I.

XII-th International Conference "Knowledge - Dialogue - Solution" Если отношения между парами объектов задаются в формах П1) или П2), то матрица вида (2) является кососимметрической (антисимметрической): pij = - p, i, j I, или легко сводится к такой. Если же ji отношения заданы в форме П3) или П4), то матрица (2) является обратносимметрической:

pij = 1/ p, i, j I, или сводится к ней.

ji Систематизированные и разработанные автором формулы превращения между различными способами представления попарных отношений между объектами приводятся в таблице 1. В таблице 1 через pij,i, j I, обозначены исходные значения элементов матрицы вида (2). Через rij,i, j I, – результирующие значения этих элементов при решении задачи превращения их в требуемую форму представления.

Простая структура Простая структура Простая Балльная Степенная ПС {0,1/2,1) ПС {-1,0,1) структура структура калибровка ПС {0,1,2) (Б) (С) Простая структура _ rij=2(pij-1/2) rij=2pij ПС {0,1/2,1) Простая структура rij=(pij+1)/2 _ rij=2pij+МЕТОДЫ МЕТРИЗАЦИИ ПС {-1,0,1) Простая структура rij=pij/2 rij=pij-1 _ ПС {0,1,2) Балльная оценка (взвешенная rij=[sign(pij-pji)+1]/2 rij=sign(pij-pji) rij=sign(pij-pji)+1 _ rij = pij / pij структура) pij0, i,jI, (Б) Степенная калибровка rij=[sign(pij-pji)+1]/2 rij=sign(logTpij), T>1 rij=sign(pij-pji)+1 rij=T1pij/(T2+pij), _ pijpji=1, pij>0, i,jI, (С) T1>0, ТТурнирная калибровка rij=[sign(pij-pji)+1]/2 rij=sign(pij-pji) rij=sign(pij-pji)+1 rij=pij rij = pij / pij pij+pji=Т, i,jI, (Т) Вероятностная rij=[sign(pij-pji)+1]/2 rij=sign(pij-pji) rij=sign(pij-pji)+1 rij=Тpij, rij = pij / pij калибровка (В) Т>pij+pji=1, 0pij1, i,jI, Турнирная Вероятностная Кососимметрическая калибровка калибровка калибровка (Т) (В) (К) Простая структура ПС {0,1/2,1) МЕТОДЫ МЕТРИЗАЦИИ Простая структура ПС {-1,0,1) Простая структура ПС {0,1,2) rij = pij + (max Sij - Sij ) / 2; rij = pij + (max Sij - Sij ) / 2;

rij = pij - Sij;

i, j i, j Балльная оценка (взвешенная структура) rij = pij + ( pij max Sij ) / Sij ;

rij = pij + ( pij max Sij ) / Sij;

Sij = pij + p ;

Pages:     | 1 |   ...   | 59 | 60 || 62 | 63 |   ...   | 82 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.