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).