Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2018.02.068

Upr. sist. maš., 2018, Issue 2 (274), pp. 68-79.

UDK 6:004.8

O.G. Moroz, junior research scientist, Departament for Technologies of Inductive Modelling, International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, Moroz.@ukr.net

ANALYSIS AND APPLICATION OF GENETIC ALGORITHMS FOR GLOBAL OPTIMIZATION PROBLEMS

Introduction. Most of the existed traditional methods of optimization and identification models of complex systems are not effective in solving the problems of finding a globally optimal solution for the undifferentiated, multimodal, nonlinear, and multi-objective tasks. This leads to the development of approximate methods, in particular the meta-heuristic global search methods such as the genetic algorithm. The effectiveness of their application is confirmed by the numerous successful practical implementations.

Purpose. The purpose of the research is to examine more comprehensively the theoretical and practical aspects of the genetic algorithms and their capabilities for solving optimization and system identification problems.

Methods. The goal of this article is achieved by presenting a comprehensive survey of the main publications in the area of genetic algorithms theory and their application to the complex optimization tasks.

Results. The theoretical and applied aspects of genetic algorithms are considered in detail. Some examples of modern global optimization and model identification problems successfully solved by genetic algorithms are presented.

Conclusion. The genetic algorithms are a powerful tool for solving various complex global optimizations and modeling tasks that are characterized by incompleteness of input information, multi-objectiveness, large dimensionality, nonlinearity, lack of analytical description of objective function etc. The effectiveness of GA depends on its type, the choice of genetic operators, encoding method of potential solutions, etc. The theoretical aspects are well developed for simple GAs. Genetic algorithms have a great perspective and require further improvements, developments and more general theoretical justification.

Download full text! (In Ukrainian).

Keywords: global optimization, genetic algorithm, system identification.

REFERENCES

1. Hollannd, J.H., 1975. Adaptation in natural and artificial systems, University of Michigan, 210 p.

 2. Goldberg, D.E., 1989. Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, Reading, 432 p.

 3. REEVES, C.R., ROWE, J.E., 2003. Genetic algorithms: principles and perspectives. A Guide to GA Theory, Kluwer Acad. Publ., 332 p.

 4. Glybovets, M.M., Gulaev, N.M., 2013. Evolutionary algorithms, K.: NaUKMA, 828 p.

 5. Kureichik, V.M., 2002. Genetic algorithms and their application, Taganrog: Taganrog University Publishing House, 244 p.

 6. Talbi, E.-G., 2009. Metaheuristics: from design to implementation, John Wiley & Sons, Inc., 593 p.

https://doi.org/10.1002/9780470496916

 7. Deb, K., 1999. “Multi-objective genetic algorithms: Problem difficulties and construction of test problems”. EvolutionaryComputation, 7 (1), pp. 205–230.

https://doi.org/10.1162/evco.1999.7.3.205

 8. Bremermann, H.J., 1962. “Optimization through evolution and recombination”. Yovits M.C., Jacobi G.T., Goldstein G.D., eds., Self-Organizing Systems. Spartan Books, pp. 93–106.

 9. Reed, J., Toombs, R., Barricelli, N.A., 1967. “Simulation of biological evolution and machine learning”. J. of Theoretical Biology, 17, 3, pp. 319–342.

https://doi.org/10.1016/0022-5193(67)90097-5

 10. Zhang, G.X., 2011. “Quantum-inspired evolutionary algorithms: a survey and empirical study”. J. Heuristics, 17 (3), pp. 303–351.

https://doi.org/10.1007/s10732-010-9136-0

 11. Deb, K., Pratap, A., Agarwal S. et al., 2002. “Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II”. IEEE Transactions on evolutionary computation, 6 (2), pp. 182–197.

https://doi.org/10.1109/4235.996017

 12. Zhong, W, Liu, J., Xue M. et al., 2004. “A multiagent genetic algorithm for global numerical optimization”. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 34 (2), pp. 1128–1141.

https://doi.org/10.1109/TSMCB.2003.821456

 13. Koumousis, V.K., Katsaras, C.P., 2006. “A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance”. IEEE Trans. Evol. Comput., 10(1), pp. 19–28.

https://doi.org/10.1109/TEVC.2005.860765

 14. ELDOS.T., 2013. “Mutative Genetic Algorithms”. J. of Computations & Modelling, 3 (2), pp. 111–124.

 15. Vose, M.D., Liepins, G.E., 1991. “Punctuated Equilibria In Genetic Search”. Complex Systems, 1991, 5 (1), pp. 31–44.

 16. DE JONG, K.A., 1975. An analysis of the behavior of a class of genetic adaptive systems, Doctoral Thesis, Department of Computer and Communication Sciences, University of Michigan, Ann Arbor.

 17. Goldberg, D.E., Segrest, P., 1987. “Finite Markov chain analysis of genetic algorithms”. Proc. of the 2nd Int. Conf. on Genetic Algorithms, Cambridge, pp. 1–8.

 18. Nix, A.E., Vose, M.D., 1992. “Modelling genetic algorithms with Markov chains”. Annals of Mathematics and Artificial Intelligence, 5 (1), pp. 79–88.

https://doi.org/10.1007/BF01530781

 19. Ljung, L., 1999. System Identification — Theory for the User, Prentice-Hall, Upper Saddle River, N J, 607 p.

 20. Garashchenko, F.G., Moroz, O.G., 2012. “Identification of the Hammerstein Nonlinear System Using the Genetic Algorithm”. Visn. KNU im.T. Shevchenko Series: Physics and Mathematics, 1, pp. 145-150. (In Ukrainian).

 21. HATANAKA, T., UOSAKI, K., KOGA, M., 2002. “Evolutionary Computation Approach to Wiener Model Identification”. Proc. of the 2002 Cong. on Evolutionary Computation, CEC’2002, Honolulu, Hawaii: IEEE, pp. 914–919.

https://doi.org/10.1109/CEC.2002.1007047

 22. Sebastian, A., Kumar, P., Schoen, M.P., 2011. “Spatial filter masks optimization using genetic algorithm and modeling dynamic behavior of sEMG and finger force signals”. Int. J. of Circuits, Systems, and Signal Processing, 5 (6), pp. 597–608.

 23. Kristinsson, K., DUMONTG., 1992. “System identification and control using genetic algorithms”. IEEE Transactions on Systems, Man and Cybernetics, 22 (5), pp. 1033–1046.

https://doi.org/10.1109/21.179842

 24. Duong, V., Stubberud, A.R., 2002. “System identification by genetic algorithm”. Proc. IEEE Aerospace Conf., Big Sky, Montana, 5 (3), pp. 2331–2337.

https://doi.org/10.1109/AERO.2002.1035405

 25. Moroz, O.G., Stepashko, V.S., 2015. “An overview of hybrid structures of GMDH-like neural networks and genetic algorithms”. Inductive modeling of complex systems: Coll. sciences works, 7, K .: IRTC ITS NASU, pp. 173-191.

 26. Chapot, J.L.C., Da Silvab, F.C., Schirrub, R., 1999. “A New Approach to the Use of Genetic Algorithms to Solve the Pressurized Water Reactor’s Fuel Management Optimization Problem”. Annals of Nuclear Energy, 26 (7), pp. 641–655.

https://doi.org/10.1016/S0306-4549(98)00078-4

 27. Pereira, C.M.N.A., Schirru, R., Martinez, A.S., 1999. “Basic Investigations Related to Genetic Algorithms in Core Designs”. Annals of Nuclear Energy, 26 (3), pp. 173–193.

https://doi.org/10.1016/S0306-4549(98)00036-X

 28. Dechaine, M.D., Feltus, M.A.,1995. “Nuclear Fuel Management Optimization Using Genetic Algorithms”. Nuclear Technology, 111 (1), pp. 109–114.

https://doi.org/10.13182/NT95-A35149

 29. Karahroudi, M.R., Shirazi, S.A.M., Sepanloo, K., 2013. “Optimization of Designing the Core Fuel Loading Pattern in AVVER-1000 Nuclear Power Reactor Using the Genetic Algorithm”. Annals of Nuclear Energy, 57 (7), pp. 142–150.

https://doi.org/10.1016/j.anucene.2013.01.051

 30. Leung, H., White, L., 1989. “Insights into regression testing”. Proc. of the Conf. on Software Maintenance, pp. 60–69.

 31. Elbaum, S., Malishevsky, A.G., Rothermel, G., 2002. “Test case prioritization: A family empirical studies”. IEEE Transactions on Software Engineering, 28 (2), pp. 159–182.

https://doi.org/10.1109/32.988497

 32. Moroz, G.B., Plis, A.V., 2014. “Regressive Testing: Methods and Future Directions of Research”. Problems of Programming, 2-3, pp. 133-142.

 33. Walcott, K.R., Soffa, M.L., Kapfhammer, G.M. et al., 2006. “Time aware test suite Prioritization”. Proc. of Int. Symp. on software Testing and Analysis (ISSTA 06), New York, USA, P. 1–12.

 34. Conrad, A.P., Roos, R.S., 2010. “Empirically Studying the role of selection operators during search based test suite prioritization”. Proc. of the ACM SIGEVO Genetic and Evolutionary Comp. Conf., Portland, Oregon, pp. 1373–1380.

 35. Freitas, A.A., 2008. “A review of evolutionary algorithms for data mining”. Soft Computing for Knowledge Discovery and Data Mining, Springer, pp. 79–111.

https://doi.org/10.1007/978-0-387-69935-6_4

 36. SHEIKH, R.H., RAGHUWANSHI, M.M., JAISWAL, A.N., 2008.” Genetic algorithm based clustering: A Survey”. First International Conference on Emerging Trends in Engineering and Technology (ICETET ’08), IEEE, pp. 314–319. https://doi.org/10.1109/ICETET.2008.48

 37. KROVI, R., 1992. “Genetic algorithms for clustering: a preliminary investigation”. Proc. of the Twenty-Fifth Hawaii Int. Conf., IV, pp. 540–544.

https://doi.org/10.1109/HICSS.1992.183445

 38. FELTL, H., RAIDL, G.R., 2004. “An Improved Hybrid Genetic Algorithm for the Generalized Assignment Problem”. The 19th Annual ACM Symp. on Applied Computing (SAC ’04), March 14–17, Nicosia, Cyprus, pp. 990–995.

https://doi.org/10.1145/967900.968102

 39. CHAKRAVARTHY, V.K., RAMANA, V.V, UMASHANKAR, C. Genetic Algorithmic Approach to Generalized Assignment Problems in Conjunction with Supply Chain Optimization: A Survey. [online] Available at: <pdfs.semanticscholar.org/0774/ 5e749118a21c4d4d8818 bab29c01116c2ec2.pdf> [Accessed 08 Jan. 2017].

 40. JUELL, P., PERERA, A., NYGARD, K.E. Application of a Genetic Algorithm to Improve an Existing Solution for the Generalized Assignment Problem. [online] Available at: <www.cs.ndsu.nodak.edu/~nygard/research/GaIctpFinal2.pdf> [Accessed 05 Jan. 2017].

 41. Alba, E., Chicano, F., 2017. “Software project management with GAs”. Information Sciences: an Int. J., 177 (11), pp. 2380–2401.

 

Received 28.03.2018