Method For The Best Solutions Search in Multiobjective Decision Problems

Introduction

Decision theory which belongs to the area of artificial intelligence is quickly developing. Decision making is closely related to problem solving, though these are not identical processes. Problem solving implies the search of means to achieve the clearly visible goal which nevertheless cannot be achie­ ved directly [1]; the decision process in general implies the search of all possib­ le means of achieving the set objective, preference comparison among them and

choice of the best one.

The most important specific of decision-making problems is the presence of a decision-maker who has to act in the situation which is characterized by lack of information about the environ­ ment, about the possible outcomes of the decisions and about the values of some outcomes. It is not only that objective functions (optimal criteria) in these problems are not stated but also their

existence is not indisputable.

The need to solve complex practical problems and the interest to scientific

METHOD FOR THE BEST SOLUTIONS SEARCH IN MULTIOBJECTIVE DECISION PROBLEMS

V.M. Ozernoi and M.G. Gaft Institute of Control Sciences 81 Profsoyuznaya, Moscow

problems accompaning them led to quick development of decision theory. It is very important that decision theory postulates nonexistence of a decision that could be considered the best one in any absolute sence, but only for a given decision maker in connection with the set objective. Thus the two main problems of the decision theory are as follows:

1. to substitute man in repeating routine decision problems (programmable problems);
2. to help man in complex and uncertain situations to choose decisions consistent with his preference judgments using formalized models and methods which allow avoiding mistakes in long and complex chains of logical arguments (unprogrammable problems).

Decision theory must provide the basis for development of models and me­ thods whereby all the information on the problem, including the decision maker's preference judgements is used in order to decide which of the alternative courses of actions is the best. When de­ cision problems are formalized difficult questions such as analysis of complex and uncertain situations become concep­ tually equivalent to simple problems that can be solved by "common sense".

Presently it is universally acknowledged that in most important real life decision problems the solution quality cannot be estimated by one scalar -valued performance criterion. Here arises the problem of estimating and comparing alternatives taking into con­ sideration a great number of criteria (multicriteria or multiobjective decision JrOblems[2} nemain difficulties in deve­ loping formalized decision methods which could be applied to a wide range of prac­ tical problems are caused by the fact that multiobjective decision problems are ill-structured [3], and in order to formalize them successfully one must con­ sider a lot of factors such as sociologi­ cal, psychological, measurement-theoretic, etc. Disregard of these factors at the stage of formalizing the process of de­ cision-making shows up as distru at on the part of the decision-makers of the results of formalized methods which are thus downgraded.

When stating and solving multiobjec­ tive problems it is essential to

consider a great number of meanin­ gful circumstancies and ideas which cannot be easily given a strict mathema­ tical motivation. Another difficulty is in what criteria must be considered in a specific problem, whether all feasible solutions are considered, etc. These questions must be solved by all means and all of them are outside the mathema­ tical formulation of the problem. At the same time working out the methods of choosing most preferable alternatives is impossible without using mathematical methods which are applied to formalized models rather than to real problems. Thus in model approach to solving certain multiobjective problems meaningful consi­ derations which cannot be strictly for­ malized have to co-exist with formalized methods and to be used in combination with them. It is only in interaction that they can lead to useful results.

The development and use of a model it possible to get ordered sets of feamb­ le solutions, provided that the sets are consistent with the model used. At the same time it must be stressed that there is no "right" or "objective" model for any specific multiobjective problem. In connection with the fact that in each problem there is a great number of fac­ tors which may be taken into or left out of consideration, there always exists the possibility to present the same situation by different models. One can find whether these models are fit or not only using them in real situations.

The process of developing multicri­ teria models in decision problems may be broken into the following series of stages: 1) goal formulation and problem type identification; 2) working out a feasible solutions set; 3) working out a criteria set; 4) criteria scale develop­ ment; 5) mapping of feasible solutions set in the set of vector-valued estima­ tes; 6) identification of a decision­ maker's preference judgments; ?) the de­ cision rule construction. The specifics of the first six stages of constructing multicriteria models and means of their implementation are described in [4]. We shall discuss in more detail the ques­ tions connected with constructing a deci­ sion rule.

Construction of Decision Rules

A number of various decision rules have been proposed, and each of them has some shortcomings which considerable limit the sphere of its possible appli­ cation [5-9]. Multicriteria problem analysis drives one to the conclusion that the construction of a generally applicable decision rule appears to be absolutely impossible. The following fact may account for it. Depending on the decision-makers goals his preference

judgments and the set of assumptions used in the model, different decision rules may be constructed that naturally lead to different ordered sets of feasib­ le solutions [ 4 J. The impossibility of constructing a generally applicable deci­ sion rule requires development of a method for constructing decision rules leading to the needed result in ever,y specific situation.

Difficulties of finding out prefe­ rence judgments of the decision-maker are responsible for the iterative nature of the decision rule construction proce­ dure involving stage-wise acquisition of information about decision-maker's prefe­ rence judgments [sJ. Information received at each stage must be used to construct an intermediate decision rule on the basis of which decisions are ordered. Procedure of constructing the decision rule leading to the problem solution must be organized in such a way that the received sequence of intermediate deci­ sion rules has the following character­ istics: the initial (weakest) one is based on the simplest and most evident assumptions; the following rules follow from the previous ones because we make extra assumptions that do not contradict the earlier ones and receive extra in­ formation. If an intermediate decision rule leads to the desired result it is accepted as the final and this is the end of the procedure.

Basic Principles

In spite of the fact that decision rules may be constructed in different ways depending on the problems at hand, one may formulate principal requirements that every iterative procedure of such a kind must meet:

1. Additional information on prefe­ rences, received by the researcher from the decision-maker at the i+1-th step of the procedure must allow establish­ ment of the preference at least between two vector-valued estimates that cannot be compared at the i-th step (meaningful­ ness criterion of additional information~
2. The preference between any two vector-valued estimates received at i-th step must not change during the subsequ­ ent steps (consistency criterion of adopted assumptions and addittional in­ formation).

When ·comparing vector-valued esti­ mates, the use of decision rule defines uniquely a binary relation (quasi-order in the general case) on the set Y of vector-valued estimates and, thus, on the set of feasible solutions.

Major Relationships

Let the expression ( R ". Y ) denote preference-indifference relation received when comparing vector-valued estimates from )( on the basis of the i-th decision rule. The relation ( R', Y > allows to define relations of strict preference ( f'-Y > equiva­ lence_ < r:· y > : incomparability ( JV~ y > in the following way [ 9]:

The requirements to iterative pro­ cedures formulated earlier for construct­ ing decision rules may be formally writt­ en down in the following way:

Strictness of inclusion (1) follows from the first requirement. Nonstrict­ ness of inclusion (2) follows from the possibility to find strict preference between vector-valued estimates incom­ parable at the i-th step as well as to establish their equivalence using the information received at the i+1-th step.

. Definition 1. Relations ( R': Y> , (R'': Y> , satisfying expressions (1) and (2) will be called inserted.

. Assertion 1. If relations ( ,(': Y.}, < /('"~ Y > are inserted, the fol.lowing expressions are valid: J '· S J' · 1 , ,.f' · -~N'~' P't 1V'.2P''' I'.v!Vt·, 1-,·,.t I ) - ·

At the same time at least one of the two last inclusions is strict.

Asnertion 1 is needed to prove whether the information received from the decision-maker in practical situati­ ons is noncontradictory.

Let the expression A£ Y denote the subset of vector-valued estimates corresponding to feasible solutions.

Definition 2. The subset

will be called the set of the most preferable estimates trom A with respect to preference-indifference rela­ tion ( /(~ Y > · ,

Assertion 2. If the relations < R~ Y>. <R'··: Y> are inserted the expression A;, :l A:, .. , is valid.

Therefore the insertion of relations < R'~ Y). , < J<i·,' Y > provides the possi­ bility of reducing at the i+1-th step the most preferable estimates subset received at the i-th step. It is suffio li cient for a strict inclusion AR, ., AK,., to establish, at the i+1-th step, pre­ ferences between incomparable estimates from A~i.

Information on Decision Maker's Prefere~ £!.!!

When organizing a decision rule generating procedure it is essential to define and substantiate a sequence in which different kinds of information on the decision-maker's preferences are received. Thus it becomes necessary to make a classification of such informa­ tion. Reference [a] classifies the in­ formation in terms of its relation with one or several criteria. This approach makes it possible to distinguish three types of information:

1. Information on the effect of estimates chan~es over one criterion scale on the decisions value (utility) in general.
2. Information on the effect of

estimates changes over one criterion scale in comparison with estimates chan­ ges over another criterion scale on the decisions value in general.

1. Information on the effect of estimates changes over the scales of criteria belonging to one group in compa­ rison with the estimates changes over the scales of criteria belonging to another eroup on decisions value in gene­ ral; at the same time at least one of the compared groups must contain more than one scale.

Information of each type is calssi­ fied with due regard to the degree of its effect on elimination of vector­ valued estimates incomparability. The set of all possible collbinations of the re­ sultant ordered information classes may be presented as a flowchart which deter­ mines the sequence of obtaining diffe­ rent types information on decision­ maker's preference judgments. The classi­ fication suggested in [s]allows finding a decision rule for each type of infor­ mation presented by the flowchart.

Application

The suegested procedure of constr­ ucting the decision rule was applied to developing the method of isolating the needed amount of the most preferable versions of a mineshaft layout [1o]. When designing coal mines the number of feasible layout versions may be as high as tens of thousands. At the same time the mineshaft layout is such a complex plant that the number of its versions cannot be estimated by one scalar-valued performance criterion. On the basis of the detailed design examination which consumes much time no more than 20-30 versions may be studied. Thus the selec­ tion of the best desi~n version through a detailed design examination is to a great extent determined by the versions under study.

The developed method for most pre­ ferable solutions search makes it possib­ le at the early stages of designing:

• to work out all feasible layout versions for a wide range of mineral­ geological factors on the basis of mor­ phological analysis,
• to estimate all versions with respect to 25 nonanalytical technological and economic criteria1
• to compare all feasible versions and isolate from them the desired number of most preferable ones.

When developing the method the deci­ sion rule was constructed in three sta­ ges. At the first stage only information on different estimate preferences over each criterion scale was used; at the second stage extra information was received in terms of some criteria on the preference of estimates change over the scale of one of them from the best estimate to some other in comparison witq similar estimates change over the scale of another criterion; at the third stage information on utility changes relations corresponding to estimates changes both over one criterion scale and over some different criteria scales

was received.

The method of search for the most preferable decisions .was repeatedly applied to designing mines for certain coal deposits. In one problem the ini­ tial set contained 7704 feasible ver­ sions of the layout; from these 21 ver­ sions were chosen as most preferable. This subset contained layouts that had been disregarded earlier as well as those that had been usually included in the number of the best ones.

At the same time some versions which were traditionally used in design­ ing were not included in the number of most preferable ones. The subsequent research and design examination fully

confirmed the wisdom of that selection.

Analysis of the results of the me­ thodology application to certain problems solution shows that it allows considerab­ le saving of time and cost of design work and improvement of the quality of the decisions made. The methodology allows substitution of man in choosing the most preferable system versions at early stages of design.