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 siS={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).
References
Techniques. 3rd Edition. Morgan Kaufmann, 2011, 178 p.
2. Zhuravlev Yu.I., Ryazanov V.V., Sen'ko O.V. «Raspoznavanie». Matematicheskie metody.
Programmnaya sistema. Prakticheskie primeneniya [Recognition". Mathematical methods.
Software system. Practical applications]. Moscow: Fazis, 2006, 122 p.
3. Berikov V.S., Lbov G.S. Sovremennye tendentsii v klasternom analize [Modern trends in cluster
analysis], Vserossiyskiy konkursnyy otbor obzorno-analiticheskikh statey po prioritetnomu
napravleniyu «Informatsionno-telekommunikatsionnye sistemy» [All-Russian competitive selection
of review and analytical articles in the priority direction "Information and telecommunication
systems], 2008, 126 p.
4. Barsegyan A.A., Kupriyanov M.S., Stepanenko V.V., Kholod I.I. Metody i modeli analiza
dannykh: OLAP i Data Mining [Methods and models for data analysis: OLAP and Data Mining].
Saint Petersburg: BKhV-Peterburg, 2004, 93 p.
5. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 448 p.
6. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation.
Helsinki University of Technology, TKK Dissertations, Espoo 2009, 161 p.
7. Lebedev B.K., Lebedev O.B., Lebedev V.B. Gibridizatsiya roevogo intellekta i geneticheskoy
evolyutsii na primere razmeshcheniya [Hybridization of swarm intelligence and genetic evolution
on the example of placement], Programmnye produkty, sistemy i algoritmy [Software
products, systems and algorithms], 2017, No.4.
8. Lebedev B.K., Lebedev O.B. Gibridnyy bioinspirirovannyy algoritm resheniya zadachi
simvol'noy regressii [Hybrid bioinspired algorithm for solving the problem of symbolic regression],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015,
No. 6 (167), pp. 28-41.
9. Kureychik V.M., Lebedev B.K., Lebedev O.B. Poiskovaya adaptatsiya: teoriya i praktika
[Search engine adaptation: theory and practice]. Moscow: Fizmatlit, 2006, 288 p.
10. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi al'ternativ [Optimization
by the method of сrystallization of alternatives field], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
11. Lebedev B.K., Lebedev O.B., Lebedeva E.M. Raspredelenie resursov na osnove gibridnykh
modeley roevogo intellekta [Resource allocation based on hybrid models of swarm intelligence],
Nauchno-tekhnicheskiy vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific
and technical bulletin of information technologies, mechanics and optics], 2017, Vol.
17, No. 6, pp. 1063-1073.
12. Kureychik V.V., Kureychik Vl.Vl. Arkhitektura gibridnogo poiska pri proektirovanii [Architecture
of hybrid search in design], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2012, No. 7 (132), pp. 22-27.
13. Lebedev B.K., Lebedev O.B., Lebedeva E.O. Reshenie zadachi simvol'noy regressii metodami
geneticheskogo poiska [The solution of the problem of symbolic regression by methods of genetic
search], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2015, No. 2 (163), pp. 212-225.
14. Kennedy J., Eberhart R.C. Particle swarm optimization, In Proceedings of IEEE International
Conference on Neural Networks, 1995, pp. 1942-1948.
15. Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006, 133 р.
16. Lebedev B.K., Lebedev V.B. Evolyutsionnaya protsedura obucheniya pri raspoznavanii obrazov
[Evolutionary training procedure for pattern recognition], Izvestiya TRTU [Izvestiya TSURE],
2004, No. 8 (43), pp. 83-88.
17. Lebedev B.K., Lebedev O.B., Lebedeva E.O. Razbienie na klassy metodom al'ternativnoy
kollektivnoy adaptatsii [Division into classes by the method of alternative collective adaptation],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016,
No. 7 (180), pp. 89-101.
18. Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and
Placement Algorithms, Proc. of the International Symposium on Physical Design. Monterey,
CA, 2003, pp. 88-94.
19. Zakharov D.O, Karpenko A.P. Issledovanie effektivnosti populyatsionnogo algoritma ligi
chempionov dlya zadachi global'noy optimizatsii [Research of the efficiency of the population algorithm
of the Champions League for the global optimization problem], Matematika i matematicheskoe
modelirovanie [Mathematics and Mathematical Modeling], 2020, No. 2, pp. 25-45.
20. Karpenko A.P. Metody povysheniya effektivnosti populyatsionnykh algoritmov global'noy
optimizatsii [Methods for increasing the efficiency of population algorithms for global optimization],
Mater. V mezhregional'noy nauchno-prakticheskoy konferentsii [Proceedings of the V
interregional scientific and practical conference]. Sevastopol': Izd-vo: Sevastopol'skiy
gosudarstvennyy universitet, 2019, pp. 87-88.
21. Kuchuganov V.N., Kuchuganov A.V., Kaksimov D.R. Algoritm klasterizatsii mnozhestva
detaley po chertezham [Algorithm for clustering a set of parts according to drawings],
Programmirovanie [Programming]. Moscow: Izd-vo: Rossiyskaya akademiya nauk, 2020,
pp. 29-38.
