POPULATION ALGORITHM FOR CONSTRUCTING A TREE OF SOLUTIONS BY METHOD OF CRYSTALLIZATION OF ALTERNATIVES FIELD

Abstract

In some cases, it becomes necessary to establish a correspondence between the declared
and actual value of a categorical variable on the basis of a set of object characteristics. In this
case, there is a need for a classifier with an optimal sequence of the considered attributes with agiven value of the objective function. The target variable can be: yes, no, variety number, class
number, etc. This paper solves the problem of constructing a classification model in the form of an
optimal sequence of the considered attributes and their values included in the route from the root
vertex to the terminal vertex with a given value of the target variable. If a classifier is required
that includes the possibility of alternative answers, then first, independently from each other, optimal
routes are built for each value of the target variable, and then these routes are combined
("glued") into a single binary decision tree. In the algorithm for constructing a classifier based on
the method of crystallization of a placer of alternatives, each solution Qk is interpreted as an oriented
route Mk on a binary decision tree. Let us call the ordinal number of an element in the directed
route Mk the position siS={si|i=1,2,…,nA}. An element of the route Mk is the pair (xi, ui-),
where xi corresponds to Ai. ui- in the route Mk is an edge outgoing from xi and corresponds to the
value Ai chosen together with Ai. The second index of the element ui- is determined after the choice
of Ai, placed in the position sj+1 adjacent to sj. The work of the decision tree construction algorithm
is based on the use of collective evolutionary memory, which is understood as information
reflecting the history of the search for a solution. The algorithm takes into account the tendency to
use alternatives from the best solutions found. The peculiarities are the presence of an indirect
exchange of information – stigmerges. The totality of data on alternatives and their assessments
constitutes a scattering of alternatives. The key points of the analysis of alternatives in the process
of evolutionary collective adaptation are considered. Experimental studies have shown that the
developed algorithm finds solutions that are not inferior in quality, and sometimes surpass their
counterparts by an average of 3–4 %. The time complexity of the algorithm, obtained experimentally,
lies within O(n2)-O(n3).