Russia, St. Petersburg, State Technical University

COMPUTING METHODS FOR THE FUZZY CONTROL TASKS DECISION AND GENETIC ALGORITHMS

Annotation

There are discussed the methods of fuzzy tasks solution, forming of base of knowledges, with application of fuzzy technologies, generation of structures for intelligent systems. There are considered the perespectives of genetic algorithms application

Россия, С.-Петербург, Санкт-Петербургский государственный технический университет

Аннотация

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

In development of control methods of intellectual systems it is usually necessary to solve tasks of fuzzy control (TFC). Only in a case, when it is possible to specify a dial - objective function, which value defines a solution, the theory and methods of mathematical programming [27] are known and well advanced, permitting to carry out the qualitative and numerical analysis of precise tasks of solution optimization, originating at it, The account of indefiniteness originating at problem solving of design of control mechanism of intellectual systems allows to apply the indicated methods of mathematical programming with the larger or smaller chances on success in considered cases TFC.

Let's consider the most popular computational methods of decision making.

In the elementary situation of decision making a person that makes decisions (PMD) - the developer, pursues the only purpose and this purpose can be given in a form of scalar function, i.e. choice quality criterion. Thus, the values of quality criterion can be obtained for any admissible array of arguments. It is supposed that the range of definition of control (choice) parameters is known, i.e. components of a chosen vector or, anyway, for any given point can be established, whether it is an admissible choice, i.e. whether it belongs to a definition range of solution quality criterion. In such situation the task of decision making can be formalized and circumscribed by model of mathematical programming.

In a MP task it is required to calculate n-dimansional vector X, optimizing (achieving maximum or minimum depending on substantial task contents) solution quality criterion f0 (x) at observance of f_j(x) >_u_j , j I 1, r , x I G, where fj - known scalar functionals, uj - given numbers, G - beforehand given set of n-dimensional space.

Thus, the MP task looks like:

f₀(x) ® / f_j(x) >_u_j , j I 1, r , x I G I Eⁿ

Depending on function properties f = < f₀, f₁, …, f_n > and set G specifies a class of optimization tasks. If all fi functions - linear, and G - multiface set, than these are linear programming tasks (LMP). If among fi functions some are nonlinear, than these are nonlinear programming tasks (NMP). Among nonlinear extremum tasks there are convex tasks (CNMP), in which concave functions f₀(x) are subject for maximization at concave functionals of limitations f_j(x) and convex area G. The tasks, in which G has final or countable number of points, are selected in special section of mathematical programming - integer or discrete programming (DMP).

During solving TFC of logico-probability type it is possible to come to MP tasks while searching optimum solution for logical equation system, when there is a possibility of constructing scalar quality criterion from attributes of logical variables.

The traditional scheme of MP, requiring definition of objective function, i.e. quality criterion and functionals of limitations, can not be used in the mechanism of decision making. As solutions in many cases are taken by people, concept of sequential preference of one of compared variants to another is frequently more natural path of selecting rational alternative for them, than statement of purpose and approximation to it. In this case, it is expedient to set an admissible set of alternatives not by equations but by some conditions of preference of chosen variants. Such situations are met, in particular, at design, when the choice should depend on reaching series of purposes, and its admissibility is determined by different people knowing different resources, limiting a choice.

For solving such tasks it is possible to generalize the scheme of mathematical programming, switching from quantitative dials to ordinal, i.e. switching from models requiring definition of functionals, defining purpose and limitation of a task, to models which are taking into account preferences of people, participating in a decision making. It expands application range of extremum problem theory and can appear useful in lots of choice situations. During solving TFC of logico-probability type it is possible to come to MPOD tasks while searching optimum solution for logical equation, when the part of attributes of logical variables are linguistic or fuzzy, but there is a principal possibility of ordering preferences, based on analysis of attributes and judgement of people taking decision.

Let's consider the elementary transition from conditions of an extremum task in quantitative dials to conditions of a task in ordinal dials.

Let G - some fixed compact set in Eⁿ , R_j, j = 0, 1, 2, …, r - reflexive, transitive and complete binary ratios in a full-sphere containing preferences G, R0 - preference of a person accepting a solution. Thus Rj, j = 1, 2, …, r - can be interpreted as preference of people limiting, everyone in his own way, set of admissible plans. Some of ratios Rj can be defined by usual functional equations limiting ranges of change of different components of a solution.

Let's designate through uj, j = 1, 2, …, r - given a priory points G and consider, that the plan x I G is admissible on limitation j, if x R_j u_j, i.e. if pair (x, u_j) I R_j. Accordingly we shall name a point x I G as an admissible solution, if x R_j u_j, j = 1, 2, …, r.

The task MPOD represents a task of choosing "the best" (in a sense of binary ratio R0) among admissible solutions. In it it is required to find one of solutions x* - such, that:

x* R₀ x , at: x R_j u_j , x* R_j u_j , j = 1, 2,…, r , (x, x*)I G

If Ro and accordingly Rj can be expressed as logical equations: C0Q = 0, Cj Q = 0, where vector Q has components < q₁, q₂, …, q_n, q₁q₂, …, q₁q_n, q₂q₃, …, q_n-1q_n, q₁q₂q₃,…, q_n-2q_n-1q_n, …, q₁q₂ …q_n-1q_n >, identification lines C0 and Cj contain elements 0 and 1 in the given order (For С₀ = \ 1 0 0 1 0 …. 1 \ а С_j = \ 0 1 1 0 … 0 \), dimension of a vector Q and lines C0, Cj are equal, qi - logical variables describing x and x *, and for " qi, probability P (qi) = 1, than process of definition required x* can be easily automated.

If $ qi for which probability P (qi) < 1, the task MPOD will have a form:

x* ® max , при х* R_j u_j , x R_j u_j , j = 1, 2,…, r , (x*, x) I G

Ro

The solution of last task is connected with finding such x*, for which probability Р(С₀Q) = max. Thus it is possible to use MP methods. However exact calculation of P(C0Q) even at small number of logical variables qi represents rather labor-consuming tasks, which is expedient to solve approximately [5]. Besides sometimes instead of estimating probability of solutions in equations of a type: C0Q = 0 minimax estimations of reliability V(C0Q) is used, which are evaluated, using rules:

V(q_ivq_j) = max{V(q_i), V(q_j)} и V(q_i U q_j) = min{V(q_i), V(q_j)}

The majority of nonlinear MPOD tasks has no solution procedure of acceptable complexity. However for convex tasks of MPOD, i.e. for tasks, in which the set G is convex, and preferences Rj, j = 0,1,2,…, r - are concave, the dialogue solution method is developed. Such procedure using sequentially entered alternatives and obtained local information about preferences Rj on the appropriate pairs variants as input allows to receive ( approximated solution of a task. At expansion of concept “ optimization on a binary ratio ” and expansion of concept “ the solution (optimum on R0 ”, which is accepted in [28], it is possible to generalize the method of solving convex task of MPOD in case of arbitrary (irreflexive, deficient and not transitive) binary ratios. It is expected, that the significant advance in solving MPOD tasks will be achieved at the expense of neural nets implementation.

The generalized mathematical programming is a methodology, which spreads principles and methods of traditional mathematical programming to a case of vector criteria and vector limitations. Unlike traditional theory of optimization GMP scheme does not evaluate admissibility and quality of each alternative, but find solution by comparing pairs of alternatives. Optimization and limitations in GMP are treated in terms of preference ratios.

In many cases, GMP represents the natural approach to a numerical solution of multicriteria tasks, acceptance of group solutions and analysis of conflict situations. The approach used in GMP for selecting solutions takes into account preferences of people making them. Thus it is supposed, that each participant of decision making process induces on a set of alternatives some binary ratios and saves them during this process.

Formally, GMP model looks like:

1. If " q_i , P(q_i) = 1 , то f₀ (x*)R₀ f₀(x) at f_j(x*)R_ju_j , f_j(x)R_ju_j , j = 1,r , (x*,x) I G I Eⁿ

2. If $ q_i , P(q_i) < 1 , то f₀(x*) ® max at f_j(x*)R_ju_j , f_j(x)R_ju_j , j = 1,r ,

R₀

(x*,x) I G I Eⁿ ,

where: fj (x), j = 0, 1, 2, …, r - vector function in E^m_j,

uj - fixed vector in E^m_j,

Rj, j = 0, 1, 2, …, r - binary ratios on G I Eⁿ

The GMP model corresponds to a choice of objects based on comparison of their performances, then, as MPOD corresponds to a choice of objects selected at immediate comparison of pairs of objects. Therefore, structure of GMP model is much more complex.

It is possible to get GMP model in TFC of logic-linguistic type, if when searching optimum solution of a logical equations system it is required to analyze complex linguistic expressions that are attributes (w*, w) or derived from attributes (w*, w) of logical variables q and q *, describing solutions (x*, x). Thus, if the indicated linguistic expressions can be reduced to logical expressions in a form: fi = CiY, where: Ci - identification line of 0 and 1, Y - vector, which components are conjunctions of logical variables describing solutions (x*, x), then the decision making process can be automated by means of artificial intelligence. Besides that GMP model can be reached during solving TFC of evolution-genetic type, if constant PMD preference are being saved intact during evolution.

However, to get GMP task of acceptable complexity it is necessary, that performances of a vector-function fj(x), range of solution definition G and used binary ratios Rj satisfied some special requirements. So, constructive methods of GMP tasks analysis are constructed for cases, when components of vector-function fj(x) - linear or concave functions, G - convex set, and binary ratios Rj - continuous, concave, monotone and regular preferences. Such GMP models are called generalized convex programming (GCP) models. Solving GMP tasks is now connected with use of genetic algorithms, neural nets and environments such as A-life.

In the previous case the choice function (CF), defined by PMD preferences was constant. The multistage scheme of generalized mathematical programming can implement arbitrary CF on a final set of variants. MSGMP scheme assumes some expansion of a “GMP task” concept. It assumes that the admissible set of solutions can be received from sets of solutions selected by separate limitations of a task (x Rj uj), both with their intersection (elimination of bad organisms in A-life system), and their join (crossover in A-life system). It is possible to get MSGMP scheme in a TFD task of evolution-genetic type at varying PMD preferences.

The MSGMP scheme represents a set of GMP tasks, each of which answers the fixed presentation X. Thus, a solution of an initial GMP task can be accepted as input (presentation) for other GMP task etc. In such a way, we come to the sequential multistage scheme GMP. However, sequential scheme does not implement all CF. In particular, within the framework of sequential scheme some extremum tasks, for example minimax task, can not be formulated. The deficiency of the sequential scheme can be eliminated if it is allowed to use on step t outcomes from the previous steps.

To construct MSGMP scheme with large number of steps changing CF with the given precision, excessively many observations behind CF implementation are needed. Besides, the computational complexity of MSGMP task grows fast with the increase of number of steps. Therefore, there is a problem of approximating CF functions by more simple mechanisms, such as, for example, the scheme of unconditional optimization on a binary ratio (elimination of the worst of two organisms after crossover), one, two, and etc. step GMP schemes (elimination of the worst after first, second etc. steps of evolution). However, using modern systems such as A-life it is possible to achieve some progress in solving MSGMP tasks.

Thus, there is some number of computational methods of decision making existing in present time. Their use in TFC along with modern artificial intelligence software opens new possibilities of essential increase in quality and velocity of fuzzy control.

The considered computational methods do not exhaust all possible methods TFC solving. However, they are most advanced in theory and implementation with the help of intellectual program systems. Therefore, explained methods can be considered as a constructive basis for choosing rational solutions in TFC. It is necessary to expect, that some generalization of selection mechanisms will considerably expand application area of a decision making theory in a field of engineering knowledge, to be exact in methods of syntheses of knowledge. Apparently, it is expedient to specify definition of knowledge base, having specified common and flexible structures of fixation and accumulation of knowledge based on formalization of a generalized choice function.

Genetic algorithms are quickly developing mathematical area. The quadratic form optimization is poligon to study iteration method properties. The nonunimodal functions optimization occupies significant place too. Using the genetic algorithms in control system theory and zero and poles placement by genetic procedures will be described in must detail. Using genetic algorithms in linear operator theory, dynamic system optimal signals and norms calculation will be described too.

Moreover we shall describe using genetic algorithms in:

• biological evolution theory,
• dinosaur evolution modelling,
• modern automobile,
• technical evolution modelling,
• mathematical experiments,
• animation graphics,

In a conclusion, we shall consider the generalized structure of intellectual system possessing implementation abilities of circumscribed fuzzy control mechanism.

Thus, it is possible to come to conclusion, that in the present time exist sufficient computational, algorithmic, program and hardware means of implementing all considered fuzzy control mechanism of intellectual systems.

1. Gorodetsky A. E., Dubarenko V. V. About one method of the decision dynamic logical-and-probabilistic problems. / Proceedings of the First International Conference of Dynamic Objects Logic-Linguistic Control, SPb, 1997.

2. Gorodetsky a. E., Dubarenko V. V. Method of approached calculation of probability of complex logic function used in logic probabilistic description of reliability of technical systems./ Proceeding of the First International Conference. Mathematical methods in Reliability. MMR'97. Part 1, Bucharest, Romania, 1997.

3. Gorodetsky A.E., Fuzzy Decision Making in Design on the Basis of the Habituality Situation Application // Fuzzy System Design, L. Reznik, V. Dimitrov, J. Kacprzyk, Physica Verlag 1998, ISBN 3-7908-1118-1

4. Gorodetsky A. E., Dubarenko V. V. Combinatorial method of complex logic functions probability calculation.// Computing mathematics and mathematical physics Journal, N 7, 1999. (Russia)

5. Gorodetsky A. E., Erofeev A. A. Construction principles of the intellectual systems for the dynamic objects control. // Automatic and Telemechanic, N 9, 1997.(Russia)

6. Gorodetsky A. E., Dubarenko V. V., Erofeev A. A. Algebra approach to the logic control problems decision. // Automatic and Teltmechanic, N 12, 1999.(Russia).