Algorithm for Solving the Problem of Comparing Complex Objects
Abstract Generated abstract
The paper addresses the comparison and ranking of complex technical or organizational objects when no single efficiency criterion is adequate and evaluation must rely on multiple weighted local indicators. It proposes a simple algorithm that normalizes each criterion by measuring its relative deviation from an ideal value, aggregates these losses through an additive weighted sum, and ranks objects in ascending order of the resulting generalized estimate. The discussion considers alternative ways to define the ideal vector, especially for organizational management systems, and notes both the method’s main limitation, compensation among criteria, and its advantages: simplicity, empirical adequacy relative to more complex methods, and independence of each object’s estimate from the others.
Full Text
AN ALGORITHM FOR SOLVING THE PROBLEM OF COMPARING COMPLEX OBJECTS
V. Z. YAMPOLSKII
(Presented by the scientific-technical seminar of the Department of Automated Control Systems and the Control Laboratory)
The problem of comparing complex objects arises in the analysis of large (technical, organizational) systems. The complexity and diversity of the properties of objects, as a rule, do not make it possible to formulate a single criterion of efficiency in order to carry out their comparison on a quantitative basis. Usually the way out is sought in constructing a set of local criteria \(P_i,\ i=\overline{1,n}\), each of which is used to evaluate the \(j\)-th property of the object \(j,\ j=\overline{1,m}\).
The set of local criteria—the vector \(\mathbf{P}=(P_1,P_2,\ldots,P_n)\)—is also called a system of indicators. Usually each of the indicators of the system characterizes properties of the objects that differ in importance. The degree of importance of the indicators—the components of the vector \(\mathbf{P}\)—is established according to the corresponding values of the components of the vector \(V=(V_1,V_2,\ldots,V_n)\), called the vector of indicator weights. Their determination is carried out by mathematical processing of the results of group expert evaluation using one of the known methods.
In what follows we assume that the objects are amenable to quantitative measurement, that is, it is possible to determine the value \(p_{ij}\)—the assessment of object \(j\) with respect to the indicator (criterion) \(P_i\). For any \(i=\overline{1,n}\) and \(j=\overline{1,m}\), the assessments \(p_{ij}\) are real, numerical, nonnegative quantities taking arbitrary values in a prescribed range.
On the basis of the available information about the indicators of the objects—the matrix \(\|p_{ij}\|\) of dimension \(n\times m\)—it is required to analyze the results of their activity. For this it is necessary to find the solution of the following problems:
Problem 1—evaluation—to determine the generalized assessment of an object
\[
U_j=f(p_{1j},p_{2j},\ldots,p_{nj}),\quad j=\overline{1,m};
\]
Problem 2—ranking—to carry out a complete ordering of the objects, that is, to rank them in the order of decreasing (or increasing) preference.
Let us note that if Problem 1 has been solved, and moreover sufficiently correctly, then Problem 2 may be regarded as trivial. However, there exist approaches [1] by means of which a solution of Problem 2 can be obtained directly.
without explicitly defining estimates \(U(P_j)\), which makes it possible to regard problem 2 as being of independent interest.
The results of solving problems 1 and 2, in combination with the data contained in the matrix \(\|p_{ij}\|\), sufficiently exhaust the problem of information support for making well-founded decisions when comparing complex objects.
The formulated problems of comparing objects belong to the class of problems of making complex decisions under conditions of certainty with a vector effectiveness criterion [2—4], also known as problems of aggregation of estimates [5], scalarization [2], or convolution of local criteria [6].
The inconsistency of object estimates in such problems, differences in units of measurement, ranges of variation, and degrees of importance of local criteria create significant difficulties in passing from the natural vector formalization of the problem to an equivalent scalar form. A method for solving the problem of comparing complex objects may be considered determined if the following are specified:
a) the principle of preference among objects;
b) a method for bringing local criteria to a single range of variation;
c) a method for determining the components of the vector \(V\)—the importance of the local criteria.
The features of the objects under consideration, the sets of criteria for their evaluation, and also considerations of a conceptual nature in choosing the principle of preference and the method of normalizing the criteria give rise to considerable diversity in approaches and methods for solving problems of comparing complex objects.
Let us proceed to the exposition of one possible algorithm for solving the problem.
As a measure of object preference, an additive weighted sum of estimates by local criteria of the form is used here
\[ U(P_j)=\sum_{i=1}^{n} V_i p_{ij}. \tag{1} \]
Bringing the local criteria \(P_i,\ i=\overline{1,n}\) to a single range of variation is carried out using the mathematical form
\[ w_{ij}=\frac{P_i^*-p_{ij}}{P_i^*},\quad i=\overline{1,n},\quad j=\overline{1,m}, \tag{2} \]
where \(P^*\) is the “ideal” value of the estimate according to the \(i\)-th local criterion.
The quantity \(P_i^*-p_{ij}\) characterizes the deviation of the actual estimate of object \(j\) according to the \(i\)-th criterion from the “ideal” value, while the quantity \(w_{ij}\) characterizes the relative magnitude of this deviation. The quantity \(w_{ij}\) may therefore be interpreted as the loss of optimality of object \(j\) according to criterion \(i\), and the smaller it is, the more preferable the object is.
As applied to the evaluation of objects tending toward the maximization of all \(P_i,\ i=\overline{1,n}\), the mathematical form (2) is a special case, studied in detail in [7], of the form
\[ \frac{|P_i^*-p_{ij}|}{|P_i^*+p_{ij}|}, \tag{3} \]
and has the following evident properties:
a) for any \(p_{ij}\in \|p_{ij}\|\), the quantity \(w_{ij}\) lies in the range \([0,1]\), with
\[ w_{ij}= \begin{cases} 0 & \text{when } p_{ij}=P_i^*,\\ 1 & \text{when } p_{ij}=0; \end{cases} \]
b) for any \(P_i,\ i=\overline{1,n}\), \(w_{ij}\) is a dimensionless quantity. In accordance with the introduced metrics, it is proposed to compute generalized estimates of complex objects by the totality of local criteria using the expression
\[ U_j=\sum_{i=1}^{n_t}\sum_{t=1}^{l} V_t V_i^t \frac{P_i^t-p_{ij}^t}{P_i^t},\qquad j=\overline{1,m}, \tag{4} \]
where \(l\) is the number of groups of local criteria,
\(n_t\) is the number of local criteria in the \(t\)-th group,
\[ t=\overline{1,l},\qquad \sum_{t=1}^{l} n_t=n, \]
\(V_t\) is the weighting coefficient of the criteria of the \(t\)-th group,
\[ \sum_{t=1}^{l} V_t=1 \]
\(V_i^t\) is the weighting coefficient of the \(i\)-th local criterion of the \(t\)-th group, and
\[ \sum_{i=1}^{n_t} V_i^t=1. \]
The objects are then ranked by completely ordering them in increasing order of \(U_j\), so that rank 1 is assigned to the object having the minimal value of the estimate \(U_j\), and so on, up to assigning rank \(m\) to the object having the maximal value of \(U_j\).
Let us dwell on the question of determining \(P_i^*,\ i=\overline{1,m}\), which are components of the ideal vector of values of local criteria \(\mathbf P^*\). In problems of vector optimization, to which the problem under consideration also belongs, the ideal vector \(\mathbf P^*\) is identified with one of the following vectors:
a)
\[ \mathbf P^*\equiv \mathbf P^s=(P_1^s,P_2^s,\ldots,P_n^s), \]
where \(P_i^s,\ i=\overline{1,n}\), are specified values of the components of the vector \(\mathbf P^s\) (on the basis of considerations of a professional-logical nature).
The subjective character of the arguments inherent in this variant of forming the vector \(\mathbf P^*\), to a greater extent than in the others, seriously limits the area of its application.
b)
\[ \mathbf P^*\equiv \mathbf P_{\mathrm{opt}}=(\operatorname{opt} P_1,\operatorname{opt} P_2,\ldots,\operatorname{opt} P_n), \]
where \(\operatorname{opt} P_i,\ i=\overline{1,n}\), are optimal values of the local criteria (components of the vector \(\mathbf P_{\mathrm{opt}}\)).
c)
\[ \mathbf P^*\equiv \mathbf P^s=(\sup P_1,\sup P_2,\ldots,\sup P_n), \]
where \(\sup P_i,\ i=\overline{1,n}\), are upper bounds of the values of the local criteria (components of the vector \(\mathbf P^s\)).
As applied to systems of organizational management, the objects in which are the corresponding subdivisions, it is prefer-
...tion should be given to the vector \(P^s\). As local criteria, relative indicators are usually used here, which also removes the frequently encountered difficulty when \(\sup P \to \infty\). In those cases when \(\sup P_i\) is difficult to determine even on the basis of considerations of a professional-logical nature, one may take \(\max P_{ij}\), \(j=1,m\), as \(\sup P_i\).
Among the shortcomings of the algorithm presented—as, indeed, of any other algorithm that uses an additive weighted sum of estimates as its preference principle—is the possibility of compensating low values of estimates according to some local criteria by high values of estimates according to others. Indeed, in a summary estimate of the form (4), the components are indistinguishable, and the same value \(U_j=\mathrm{const}\) may correspond to different sets of estimates \(p_{ij}\), \(i=1,n\). Among them there may also be such sets as are unacceptable from the point of view of the persons responsible for decision making, in particular sets with zero values of estimates according to the most important local criteria.
An obvious merit of the algorithm for comparing complex objects presented here is its simplicity. At the same time, as numerous experiments have shown, the accuracy of the results obtained with its help is not inferior to the accuracy of algorithms of substantially greater complexity. In addition, an important advantage of the algorithm presented is the independence of the estimates \(U_j\), \(j=1,m\), obtained with its help from the estimates of all the remaining objects. This creates the possibility of comparing summary estimates relating to different periods of time, which is very important in analyzing trends in the changes of the estimates of the objects being compared.
REFERENCES
-
V. Z. Yampolsky, I. P. Makarov, V. A. Suchkov. A method for making a complex decision on the basis of pairwise comparison of alternatives. Reports of the VI Symposium on Cybernetics, Part III. Tbilisi, 1972.
-
V. I. Borisov. Choosing a decision in the case of several efficiency criteria, or the problem of vector optimality. Problems of general and social forecasting. Issue 2, information bulletin No. 14/29, USSR Academy of Sciences. 1969.
-
V. M. Ozernoy. Decision making (survey). Avtomatika i telemekhanika, No. 11, 1971.
-
V. L. Volkovich. Methods of decision making according to a set of optimality criteria (survey). Proceedings of the seminar “Complex Control Systems.” Issue 1, “Naukova dumka,” 1968.
-
O. I. Larichev. Human-machine decision-making procedures (survey). Avtomatika i telemekhanika, No. 12, 1971.
-
Yu. B. Germeier. Introduction to the Theory of Operations Research. Moscow, “Nauka,” 1971.
-
I. V. Kuzmin, E. A. Dedikov, B. K. Kukharev. A method for constructing a global criterion in problems of mathematical programming. Mekhanizatsiya i avtomatizatsiya upravleniya, No. 6, Kiev, 1971.