A characteristic feature of many practical decision-making tasks is their multicriteria, which leads to the complexity of information processing when finding a solution. Failure to consider many criteria can lead to inconsistency of the constructed model with the real problem and impossibility to find its solution. Therefore, improving the effectiveness of methods for solving such problems is an urgent research problem. This work is a continuation of research on the use of the clustering method based on fuzzy binary relations in solving different classes of applied problems. It is devoted to the urgent problem of increasing the efficiency of methods for solving multi-objective problems of linear programming by applying the approach of clustering the criterion space, identifying strongly dependent efficiency criteria, further reduction of the criterion space of the problem into a smaller centroid space. In this paper we analyzes the current state of research of multi-objective optimization problem. The clustering method based on fuzzy binary relations has been adapted to detect groups of vectors by angular similarity measure. At the same time, a new kind of membership function was proposed. The approach of criterion space reduction of the problem by the space of centroids is described. At the same time centroids no longer need normalization. Based on this approach, the weighted sum scalarization method in the selection of the decision maker who decides the weights of the efficiency criteria is modified. Some approaches for determining the weights of centroids representing the criteria in the respective clusters are proposed. The scheme of the complex approach to the decision of multi-objective linear optimization problem with use of the approach of criterion space reduction is presented. Multicriteria, multi-objective optimization problem, weighted sum scalarization method,
clustering, reduction of criterion space
Decision-making processes are the basis of any purposeful activity. Mathematical and information models have become widely used to describe and analyze complex technical, social, economic, medical and other systems. The real needs of the practice of designing, creating and operating complex systems require consideration and coordination of several (many) different goals. Consideration of only one criterion simplifies the real problem and leads to a wrong solution [1]. A characteristic feature of many practical problems in the study of socio-economic [2-4] systems is multicriteria, which leads to the complexity of information processing in finding a solution. An important place in solving practical problems is occupied by problem situations, which are modeled and described by linear models and depend on many factors, so solving a multicriteria decision-making problem is often accompanied by solving vector optimization problems [1-5].
2021 Copyright for this paper by its authors. organization of decision-making processes. For example, consider the problem of economic planning, which is the basis of production management in socio-economic systems. As a rule, production planning is carried out taking into account certain criteria, which must reach extreme values with limited resources (raw materials, labor, production, time). For example, the criteria of profit, profitability, demand, gross output, load of equipment and manpower, sales - are maximized, and outlay, cost of production, costs of purchasing raw materials, the use of overtime - are minimized.
There are many methods for solving multi-objective optimization problem (in short MOP). The main idea of many of them is the transition to a single-criteria task, taking into account additional information from the decision-maker (in short DM): determining the weights of performance criteria, highlighting the main criterion and certain thresholds for others, ranking criteria by priority. Obviously, such information is subjective, but directly affects the solution to the problem. Therefore, it is advisable to study and analyze the existing hidden relationships between the criteria of effectiveness and the definition of groups of similar goals, to reduce the criterion space of the problem, and only then to determine one or another method for solving it.
small number of criteria, the task of comparing two alternatives is quite simple and transparent, the values of the criteria can be directly compared and a preferred alternative can be worked out. With a large number of criteria, the task becomes immense for the decision maker. Sometimes, with a large number of criteria, they can usually be combined into groups that have a specific semantic meaning.
Let = ( , = ̅1̅̅,̅̅) – be a vector variables of model; is the number of variables (coordinates of the vector), the vector of variables belongs to the space of -dimensional vectors ∈ (space variables of model) and, as a rule, its integrality ≥ 0.
functionally related to the vector of variables ( ), = ̅1̅̅,̅̅̅,
≥ 2, where – number of criteria. which is called a vector criterion (vector objective function). ( ), = ̅1̅̅,̅̅̅ are called partial or local criteria. The set of all criteria can be conditionally considered as some criterion space of the problem.
The functional relationship of variables is established by certain relations, which are subject to restrictions: = ( 1( ), 2( ), … , ( )),
( ) ≤ , = ̅1̅̅,̅̅,
where – the number of constraints included in the mathematical model. Relation (
⊂ (space of alternatives).
of its value. The problem of choosing an acceptable vector of variables
≥ 0 from the area of
restrictions (
) by vector criterion is called a vector problem of mathematical programming or
a multi-objective optimization problem (MOP). function, ( ), = ̅1̅̅,̅̅ – convex functions.
compact set. It follows that there is a global solution of the multicriteria problem for each local criterion
from (
Multicriteria problem (
( ∗) ≥ ( ′), ∀ = ̅1̅̅,̅̅̅, for at least one criterion, a strict inequality holds.
set of non-improved points, i.e., you can not find another such point from , that some of the criteria
improve and others do not deteriorate. In the general case, effective solutions are not equivalent to each
other, so for two Pareto optimal solutions, one cannot say which one is better. The set of points, Pareto,
lies between the points of the optimum obtained in solving problems (
If in problem (
≥ 2, ∑ ≤ ,
= ̅1̅̅,̅̅,
≥ 0, = ̅1̅̅,̅̅.
where (
they are all heuristic in nature. When developing methods for solving multipurpose problems, it is necessary to solve specific problems, which, one way or another, are related to the normalization of criteria [7], the choice of the optimality principle, which determines the rule of choosing one point from the whole Pareto set.
be difficult to formally describe the principle of optimality (criteria of "correctness of the solution").
First, the objects considered by decision theory are so diverse that it is not possible to establish uniform
optimality principles for all classes of problems. Secondly, the goals of the participants in the
decisionmaking processes are different and often opposite. Thirdly, the criteria for the correctness of the solution
depend not only on the nature of the problem, its purpose, but also on how impartially they are chosen,
otherwise there will be preparation for the answer. And finally, the difficulties of choosing a solution
(
problems of vector optimization) is carried out in several directions. We distinguish from these areas the main [6-8]: methods based on the collapse of the criteria (Weighted Sum Scalarization (WSS)
method of successive concessions, a group of methods of target programming (ideal point method,
The existence of such a large number of methods is a consequence of the "mathematical incorrectness" of the problem. Each of them has its disadvantages and advantages. Let's highlight the main ones. Methods that truncate the set of valid solutions Х can lead to sub-optimal Pareto solution (the main criterion method, method of successive concessions). Targeted programming methods (WCS) require the prior solution of single-criteria optimization problems for each partial criterion. The method of additive convolution (WSS) of criteria is considered to be one of the most popular [6, 8]. Its advantages are simplicity and the well-known fact that the resulting solution will be Pareto optimal [8]. It is necessary to obtain additional information from the DM on the weights of the performance criteria that characterize the degree of their importance. A known significant disadvantage is that this method is quite sensitive to small changes in the weights of the objective functions. Also, some iterative humanmachine dialogic decision-making procedures are built on its basis [9]. An analysis of the existing relationships between the criteria will reduce the criteria space of tasks and provide important information for decision maker for a more sound selection of weights of performance criteria.
non-overlapping), called clusters, so that each cluster consists of similar objects, and the objects of different clusters differ significantly. One of the goals of clustering is to identify internal relationships between data by defining the cluster structure. Dividing observations into groups of similar objects simplifies further data processing. following relationships between them.
To group the efficiency criteria described by the objective functions ( ), = ̅1̅̅,̅̅̅ use the ̅1̅̅,̅̅̅ . value.
improvement of the score on one criterion on the set leads to its improvement by another criterion.
If you move the beginning of the vector ± coincides with the radius vector ̅̅̅̅̅, where point ( ) with the beginning of the coordinate system, it – origin, ( 1, 2, … , ), = ̅1̅̅,̅̅̅. Therefore, segmenting the vectors ̅̅̅̅̅ = ̅ into sets, thus segmenting the criteria that according to them ( ), = ( ).
chosen. It allows you to group objects into clusters of different geometric shapes by changing only the types of similarity measures of objects (feature-vector of efficiency criteria). To determine the number of clusters, certain values are set - clustering thresholds ∗ , which characterize the degree of objects similarity in the inside of the cluster. The closer this value is to one, the more clusters are formed as a result. Conversely, a null value of ∗ will generate a single cluster that includes all objects.
of vector features = { ̅ | = 1̅̅,̅̅̅̅} with a membership function ( ̅, ̅ ), where : 2 → [0,1]. – characterizes the degree of similarity between objects with numbers and expressed in numerical
criteria of problem (
Types of functions may be different. In particular, represented by formulas (
Function graphs 1 (dotted line) and 2 (solid line) is shown in Figure 1, where the abscissa axis
determines the angle between the feature-vectors, and the ordinate axis - the value of the similarity
measure.
(
Let Ω1={1, 2, …, m}. 180°, the closer the value of the similarity measures will be to zero.
Graphs of similarity measure 1 very slowly descends around the point = 0, therefore accurately
determine the clustering threshold ∗ will be quite difficult when using this feature. Therefore, it is
expedient to use a similarity measure (
Step 1. We choose the dominant centroid vector с̅∗ from the set { ̅ | Ω }, around which the l-th cluster will be built. This vector can be arbitrary or determined by a specific rule. In particular, given the heuristics, it is recommended to assign as dominant one of the vectors { ̅ | Ω }, which provides the maximum value of the function R in relation to all other vectors from { ̅ | which 2 ( ̅ , ̅∗) ≥ ∗ , is valid are included in the conventional cluster . Ω }. All { ̅ | Ω }, for
recalculated.
bisector of the largest angle between the vectors of gradients of efficiency criteria inside one cluster . Therefore, in this case, the centroid can be determined by the formula: ̅∗ = (̅̅̅∗ + ̅̅̅∗)/2, where { ∗, ∗} min ( , ∈ | ̅ || ̅ | ̅ ∙ ̅ ) and = { | ̅ }.
belonging to the cluster .
points corresponding to the ortho-vectors of the gradients within one cluster :
2 ( ̅ , ̅∗) ≥ ∗ }. Ω / = max 2 ( ̅ , ̅∗).
The procedure of alignment of the cluster is held until the ̅∗ coordinates change in recalculation.
Step 3. The procedure of refinement of the cluster is performed. For this, the vector ̅ , which is
“the most similar” to the vector ̅∗, is determined from the set Ω / , i.e., 2 ( ̅ , ̅∗) =
are cleared. Further, a
new
refined cluster is formed =
And the possibility of joining ̅ to is checked. For the set ∪ { ̅ }, the centroid vector ̅̅∗̅̅∗ is
calculated according to the formulas (
If the set { ̅ ∪ { ̅ }| 2 ( ̅ , ̅̅∗̅̅∗) ≥ ∗ } is equal to the set ∪ { ̅ }, the vector ̅ is included in the set , and the centroid vector ̅∗ is recalculated, i.e. ̅∗ = ̅̅∗̅̅∗. If { ̅ ∪ { ̅ }| 2 ( ̅ , ̅̅∗̅̅∗) ≥ ∗ } ≠ ∪ { ̅ }, the procedure of refinement of the cluster is completed.
Step 4. We form the cluster = and Ω +1=Ω / .
centroids ̅1∗, ̅2∗, … , ̅∗. of item 8 in [10].
The result of the method will be crisp clusters 1, 2, … , , ≤
with appropriate centroids
̅1∗, ̅2∗, … , ̅∗ is performed. Thus, the criterion space of problem (
vector criterion. Indeed, the need to make a decision taking into account all particular criteria leads to the quite obvious conclusion that each particular criterion makes its own "contribution" to the final assessment of one or another alternative. To obtain such an estimate in an explicit form, it is required to construct a functional that is intended to serve as the final (resulting, integral) criterion. Pareto drew attention to this and introduced the concept of weights.
The vector of weight coefficients of criteria is set relative importance of the relevant criterion for it. Approaches to determining weights are described in [11-13]. Weights are usually used in normalized form and satisfy the conditions 0, ∀ . If we find the sum of the criteria ( ), = 1̅̅̅,̅̅̅, multiplied by their weights, we obtain a linear scalarized function that is maximized on the allowable range of constraints . The one-criteria (scalar) ∑ =1 = 1, ≥ problem of mathematical programming is received: = ( , = ̅1̅̅,̅̅̅), which characterizes the ̅∗ = ∗ = ∑
( ) → ( ) ≤ , = ̅1̅̅,̅̅, ≥ 0, = ̅1̅̅,̅̅ ∑
= 1, ≥ 0.
In most cases, the construction of the convolution is preceded by the execution of the normalization
of particular criteria. The essence and meaning of this operation is to get rid of differences in dimension
that may occur for individual particular criteria, as well as to reduce the sets of their possible values to
(
satisfies condition (
optimal, additive convolution of criteria has a number of disadvantages. Therefore, the selection must be justified.
three criteria on a set of alternatives Х (Figure 2).
In Figures 2 and 3, the bold line highlights the set of Pareto AB non-improving alternatives and local solutions of the problem. As can be seen, the local optimum points for the first and second criteria coincide and are at point A, i.e., it is obvious that the improvement of the evaluation vector for one of them leads to the automatic improvement of the evaluation for the other. Therefore, it becomes obvious that this fact must be taken into account when determining the weights of the decision maker. Of course, in problems of higher dimension it is very difficult (or impossible) to make a geometric interpretation, so the clustering of the criterion space by the angular similarity measure at the value of the thresholds ∗ close to the unit just and will allow you to identify highly dependent criteria. Consider its application in this example (Figure 3).
Figure 3 shows that after clustering, the objective functions 1 and 2 will represent the centroid of the cluster ∗ = ( 1 + 2), which is the collinear sum of the first two vectors.
of the clusters. That is, in the context of the example, the output was a two-criterion problem with objective functions ∗ and 3. Further, the decision maker can assign weights according to different approaches, ranking not all partial criteria, but formed clusters of criteria.
given to those centroids that represent a more powerful cluster:
where – weighting factor of the i-th centroid, | |- the number of elements of the i-th cluster, m- the total number of efficiency criteria in the problem.
If the decision maker can compare clusters of criteria in pairs, then a square matrix of pairwise comparisons is created dimension × , elements which can take binary values: 1, if the criteria of the cluster prevail over the group of criteria of the cluster ; 0 – otherwise. = | |
, =
∑ =1
∑ ,
, = ∑
∙ ∗.
=1
measure
(
weights, which are not selected arbitrarily, but on the basis of information about the relationship between the criteria. Therefore, in this example, the use of the clustering approach has only slightly modified the method of simple linear convolution and this ensures that the solution f ound will be
multipurpose linear programming problem (Figure 4).
Thus, the use of the method based on fuzzy binary relations and similarity measure (
objective functions of the reduced criterion space. It should be emphasized that the obtained centroids are already normalized. Next, the decision maker assigns weights 1, 2, … , , which are used in a simple linear convolution of the criteria of reduced space:
linear programming are presented in detail in [14-16]. The solution of this problem ∗ will be Pareto optimal and non-improving. Next, you need to find the vector of evaluations ( 1( ∗), 2( ∗), … , ( ∗)) that are provided to the decision maker for analysis. If the obtained values of the efficiency criteria satisfy the decision-maker, then the process of finding a solution is considered complete. If not, the DM should increase the weights of the groups of criteria whose values need to be improved. The numerical ratios of the weights of all other criteria must be left unchanged. Thus, it is possible to develop a dialog human-machine procedure for finding solutions to multicriteria linear programming problems.
This work is a continuation of research [10, 17] on the use of the clustering method based on
fuzzy binary relations [10] in solving different classes of applied problems. It is devoted to the
urgent problem of increasing the efficiency of methods for solving multi-objective problems of
linear programming by applying the approach of clustering the criterion space, identifying strongly
dependent efficiency criteria, further reduction of the criterion space of the problem into a smaller
centroid space. This allows you to structure the criteria space and provide additional information
about the relationships between the criteria to the decision maker for a more accurate selection of
weights. The analysis of the current state of research of multipurpose optimization problems is
carried out. The clustering method based on fuzzy binary relations was adapted [10] to detect
groups of vectors similar in angular similarity measure (
for some applications. In particular, for the calculation of individualized diets for a nutritionist.
8. References