Authors V. M. Kureichik, T. G. Kaplunov
Month, Year 05, 2018 @en
Index UDC 004.021
Abstract The article describes the methods of increasing the search capabilities of the genetic algorithm. The purpose of this work is to find ways to accelerate the work of genetic algorithms. The relevance of the work lies in the fact that today the increase in the search capabilities of genetic algorithms is the main problem when using such algorithms. Often, with manipulations with an algorithm, the probability of getting into the local extremum of the function under investigation increases. The method described in the paper is to change the point of view of the natural selection process. The classical genetic algorithm implements the action of natural selection (EO) at the level of individuals. However, in microbiology, natural selection is presented as a selection of genes; this viewpoint is not widely used in the theory of genetic algorithms. This paper presents an algorithm that implements natural selection at the level of genes. The measure of the fitness of a gene in its work is taken as its stability in the process of changing generations, which can be traced based on the Shewhart maps. The algorithm uses a set of fuzzy rules, with the help of which the dynamically changing parameters of the algorithm are controlled, in particular, the probability of hitting the next generation. Based on the conclusion that genes are statistically manageable, a prediction block has been implemented in the algorithm. To increase the speed of the algorithm, you can enter the internal prediction of the genome. The prediction decision is made on the basis of a fuzzy rule: if the time series of the i-th representative of the population is controlled according to Schuhart over the last L generations, then add an individual to the population whose genome consists of the predicted values of the genes for K generations ahead. Thus, the algorithm manages dynamically changing parameters (mutation, population size), and also predicts the most adapted genes based on third-party GA. The results are confirmed by an experiment conducted on test functions for optimization algorithms. On the basis of the conducted experiments, it can be concluded that the algorithm is practically applicable in search and optimization problems.

Download PDF

Keywords Genetic algorithm; optimization; prediction; Shewhart control charts; fuzzy rules.
References 1. Gladkov L.A., Kureychik V.V, Kureychik V.M. i dr. Bioinspirirovannye metody v optimizatsii: monografiya [Bioinspired methods in optimization: monograph]. Moscow: Fizmatlit, 2009, 384 p.
2. Rutkovskaya D., Pilin'skiy M., Rutkovskiy L. Neyronnye seti, geneticheskie algoritmy i nechetkie sistemy [Neural networks, genetic algorithms and fuzzy systems]. 2nd ed. Moscow: Goryachaya liniya-Telekom, 2008, 452 p.
3. Uiler Donal'd, Chambers Devid. Statisticheskoe upravlenie protsessami: Optimizatsiya biznesa s ispol'zovaniem kontrol'nykh kart [Statistical process management: business Optimization using control charts]. Moscow: Al'pina Pablisher, 2009, 410 p.
4. Sinyuk V. G., Akopov V.N. Upravlyaemye statisticheskie geneticheskie algoritmy [Managed statistical genetic algorithms], Programmnye produkty i sistemy [Software products and systems], 2008, No. 4.
5. Kureychik V.M., Sinyutin V.G., Kaplunov T.G. Prognozirovanie sostoyaniy tekhnicheskikh sistem pri pomoshchi geneticheskikh algoritmov [Prediction of the state of technical systems using genetic algorithms], Vestnik ryazanskogo gosudarstvennogo radiotekhnicheskogo universiteta [Bulletin of the Ryazan State Radio Engineering University], 2018, No. 3, pp. 107-113.
6. Yarushkina N.G., Afanas'eva T.V., Perfil'eva I.G. Intellektual'nyy analiz vremennykh ryadov: ucheb. posobie [Intellectual analysis of time series: textbook]. Moscow: Izd. dom «FORUM»: INFRA-M, 2012, 315 p.
7. Holland J.H. Hidden Order: how adaptation builds complexity. Addison-Wesley, 1995, 204 p.
8. Baeck T., Fogel D., Michalewicz Z. Evolutionary computation. Basic algorithms and operators. Bristol&Philadelphia: IOP publishing LTD, 2000, 304 p.
9. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy: ucheb. posobie [Genetic Algorithms: Study Guide]. 2nd ed. Moscow: Fizmatlit, 2006, 320 p.
10. Uziel Sandler, Lev Tsitolovsky. Neural Cell Behavior and Fuzzy Logic. Springer, 2008, 478 p.
11. Terano T., Asai K., Sugeno M. Prikladnye nechetkie sistemy [Applied fuzzy systems]. Moscow: Mir, 1993, 368 p.
12. Rutkovskiy Leshek. Iskusstvennye neyronnye seti. Teoriya i praktika [Artificial neural networks. Theory and practice]. Moscow: Goryachaya liniya - Telekom, 2010, 452 p.
13. Novak V., Perfil'eva I., Mochkrozh I. Matematicheskie printsipy nechetkoy [Mochkrozh I. Mathematical principles of fuzzy logic]. Moscow: Fizmatlit, 2006, 352 p.
14. Lapidus V.A. Sistema Shukharta [Shukhart System]. Nizhniy Novgorod: OOO SMTs «Prioritet», 2004, 65 p. ISBN 5-98366-010-1.
15. Barabanova O.A. Sem' instrumentov kontrolya kachestva [Seven quality control tools]. Moscow: ITs «MATI» - RGTU im. Tsiolkovskogo, 2001, 88 p.
16. Spears W.M. Adapting crossover in a genetic algorithm. The University of Michigan Press, 1988.
17. Donald J. Wheeler. Advanced Topics in Statistical Process Control: The Power of Shewhart's Charts. SPC Press, 1995.
18. Romanov V.N. Nechetkie modeli prinyatiya resheniy [Fuzzy models of decision-making], Al'manakh sovremennoy nauki i obrazovaniya [Almanac of modern science and education], 2013, No. 5 (72), pp. 144-147.
19. Grant V. Evolyutsionnyy protsess: Kriticheskiy obzor evolyutsionnoy teorii [The evolutionary process: A critical review of evolutionary theory]: Transl. from English. Moscow: Mir, 1991, 488 p.
20. Shmal'gauzen I.I. Izbrannye trudy. Organizm kak tseloe v individual'nom i istoricheskom razvitii [Selected Works. The organism as a whole in individual and historical development]. Moscow: Nauka, 1982, pp. 348-372.
21. Goldberg D.E., Sastry K. A Practical Schema Theorem for Genetic Algorithm Design and Tuning, Illinois Genetic Algorithms Laboratory, 2001.
22. Herrera F., Lozano M., Verdegay J.L. Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis, 1996. Department of Computer Science and Artifcial Intelligence University of Granada, Spain.
23. Rosenbrock H.H. An automatic method for finding the greatest or least value of a function, The Computer Journal, 1960, No. 3, pp. 175-184.
24. Rastrigin L.A. Systems of extremal control. Moscow: Mir, 1974.

Comments are closed.