DOI: https://doi.org/10.15588/1607-3274-2019-2-10

OPTIMIZATION METHOD BASED ON THE SYNTHESIS OF CLONAL SELECTION AND ANNEALING SIMULATION ALGORITHMS

O. O. Grygor, E. E. Fedorov, T. Y. Utkina, A. G. Lukashenko, K. S. Rudakov, D. A. Harder, V. M. Lukashenko

Abstract


Context. The problem of increasing the efficiency of optimization methods by synthesizing metaheuristics is considered. The object
of the research is the process of finding a solution to optimization problems.
Objective. The goal of the work is to increase the efficiency of searching for a quasi-optimal solution at the expense of a metaheuristic
method based on the synthesis of clonal selection and annealing simulation algorithms.
Method. The proposed optimization method improves the clonal selection algorithm by dynamically changing based on the annealing
simulation algorithm of the mutation step, the mutation probability, the number of potential solutions to be replaced. This
reduces the risk of hitting the local optimum through extensive exploration of the search space at the initial iterations and guarantees
convergence due to the focus of the search at the final iterations. The proposed optimization method makes it possible to find a conditional
minimum through a dynamic penalty function, the value of which increases with increasing iteration number. The proposed
optimization method admits non-binary potential solutions in the mutation operator by using the standard normal distribution instead
of the uniform distribution.
Results. The proposed optimization method was programmatically implemented using the CUDA parallel processing technology
and studied for the problem of finding the conditional minimum of a function, the optimal separation problem of a discrete set, the
traveling salesman problem, the backpack problem on their corresponding problem-oriented databases. The results obtained allowed
to investigate the dependence of the parameter values on the probability of mutation.
Conclusions. The conducted experiments have confirmed the performance of the proposed method and allow us to recommend it
for use in practice in solving optimization problems. Prospects for further research are to create intelligent parallel and distributed
computer systems for general and special purposes, which use the proposed method for problems of numerical and combinatorial
optimization, machine learning and pattern recognition, forecast.


Keywords


metaheuristics, clonal selection, annealing simulation, optimization, technology of information parallel processing.

Full Text:

PDF

References


Talbi El-G. Metaheuristics: from design to implementation Hoboken, New Jersey, Wiley & Sons, 2009, 618 p. DOI:10.1002/9780470496916

Engelbrecht A. P. Computational intelligence: an introduction. Chichester, West Sussex, Wiley & Sons, 2007, 630 p. DOI:10.1002/9780470512517

Yu X., Gen M. Introduction to evolutionary algorithms. London, Springer-Verlag, 2010, 433 p. DOI: 10.1007/978-1-84996-129-5

Nakib A., Talbi El-G. Metaheuristics for Medicine and Biology. Berlin, Springer-Verlag, 2017, 211 p. DOI: 10.1007/978-3-662-54428-0

Yang X.-S. Nature-inspired Algorithms and Applied Optimization. Charm, Springer, 2018, 330 p. DOI: 10.1007/978-3-642-29694-9

Subbotin S. Oliinyk A. , Levashenko V. , Zaitseva E. Diagnostic Rule Mining Based on Artificial Immune System for a Case of Uneven Distribution of Classes in Sample, Communications, 2016, Vol. 3, pp. 3–11.

Blum C., Raidl G. R. Hybrid Metaheuristics. Powerful Tools for Optimization. Charm, Springer, 2016, 157 p. DOI:10.1007/978-3-319-30883-8

Glover F., Kochenberger G. A. . Handbook of metaheuristics. Dordrecht, Kluwer Academic Publishers, 2003, 570 p. DOI:10.1007/B101874

Yang X.-S. Optimization Techniques and Applications with Examples. Hoboken, New Jersey : Wiley & Sons, 2018, 364 p.

DOI: 10.1002/9781119490616

Martí R., Pardalos P. M., Resende M. G. C. Handbook of Heuristics. Charm, Springer, 2018, 1289 p. DOI: 10.1007/978-3-319-07124-4

Gendreau M., Potvin J.-Y. Handbook of Metaheuristics. New York, Springer, 2010, 640 p. DOI: 10.1007/978-1-4419-1665-5

Doerner K. F., Gendreau M., Greistorfer P., Gutjahr W., Hartl R. F. , Reimann M. Metaheuristics. Progress in Complex Systems Optimization. New York, Springer, 2007, 408 p. DOI:10.1007/978-0-387-71921-4

Bozorg Haddad O., Solgi M., Loaiciga H. Meta-heuristic and Evolutionary Algorithms for Engineering Optimization. Hoboken, New Jersey, Wiley & Sons, 2017, 293 p. DOI:10.1002/9781119387053

Chopard B., Tomassini M. An Introduction to Metaheuristics for Optimization. New York, Springer, 2018, 230 p. DOI:10.1007/978-3-319-93073-2

Radosavljević J. Metaheuristic Optimization in Power Engineering. New York, Institution of Engineering and Technology, 2018, 536 p. DOI:10.1049/PBPO131E

de Castro L. N., von. Zuben F. J. The clonal selection algorithm with engineering applications, The Genetic and Evolutionary Computation Conference (GECCO’00) : Workshop on Artificial Immune Systems and Their Applications : proceedings. Las Vegas, 2000, pp. 36–39.

de Castro L. N., von. Zuben F. J. Learning and optimization using clonal selection principle, IEEE Transactions on Evolutionary Computation, 2002, Vol. 6, pp. 239–251. DOI:10.1109/TEVC.2002.1011539

Babayigit B., Guney K., Akdagli A. A clonal selection algorithm for array pattern nulling by controlling the positions of selected elements, Progress in Electromagnetics Research, 2008, Vol. 6, pp. 257–266. DOI: 10.2528/PIERB08031218

White J. A., Garrett S. M. In: Timmis J., Bentley P. J., Hart E. (eds). Improved pattern recognition with artificial clonal selection, Artificial Immune Systems: ICARIS-2003. Berlin, Springer, 2003, pp. 181–193. (Lecture Notes in Computer Science, Vol. 2787). DOI: 10.1007/978-3-540-45192-1_18

Alba E., Nakib A., Siarry P. Metaheuristics for Dynamic Optimization, Berlin, Springer-Verlag, 2013, 398 p. DOI:10.1007/978-3-642-30665-5

Du K.-L., Swamy M. N. S. Search and Optimization by Metaheuristics. Techniques and Algorithms Inspired by Nature. Charm, Springer, 2016, 434 p. DOI: 10.1007/978-3-319-41192-7

Brownlee J. Clever algorithms: nature-inspired programming recipes. Melbourne, Brownlee, 2011, 436 p.


GOST Style Citations


1. Talbi El-G. Metaheuristics: from design to implementation / El-G. Talbi. – Hoboken, New Jersey : Wiley & Sons, 2009. – 618 p. DOI:10.1002/9780470496916
2. Engelbrecht A. P. Computational intelligence: an introduction / A. P. Engelbrecht. – Chichester, West Sussex : Wiley & Sons, 2007. – 630 p. DOI:10.1002/9780470512517
3. Yu X. Introduction to evolutionary algorithms / X. Yu, M. Gen. – London : Springer-Verlag, 2010. – 433 p. DOI:10.1007/978-1-84996-129-5
4. Nakib A. Metaheuristics for Medicine and Biology / A. Nakib, El-G. Talbi. – Berlin : Springer-Verlag, 2017. – 211 p. DOI:10.1007/978-3-662-54428-0
5. Yang X.-S. Nature-inspired Algorithms and Applied Optimization / X.-S. Yang. – Charm : Springer, 2018. – 330 p. DOI:10.1007/978-3-642-29694-9
6. Subbotin S. Diagnostic Rule Mining Based on Artificial Immune System for a Case of Uneven Distribution of Classes in Sample / S. Subbotin, A.Oliinyk, V. Levashenko, E. Zaitseva // Communications. – 2016. – Vol. 3. – P. 3–11.
7. Blum C. Hybrid Metaheuristics. Powerful Tools for Optimization / C. Blum, G. R. Raidl. – Charm : Springer, 2016. – 157 p.
DOI: 10.1007/978-3-319-30883-8
8. Glover F. Handbook of metaheuristics / F. Glover, G. A. Kochenberger. – Dordrecht : Kluwer Academic Publishers, 2003. – 570 p. DOI:10.1007/B101874
9. Yang X.-S. Optimization Techniques and Applications with Examples / X.-S. Yang. – Hoboken, New Jersey : Wiley & Sons, 2018. – 364 p. DOI:10.1002/9781119490616
10. Martí R. Handbook of Heuristics / R. Martí, P. M. Pardalos, M. G. C. Resende. – Charm : Springer, 2018. – 1289 p. DOI:10.1007/978-3-319-07124-4
11. Gendreau M. Handbook of Metaheuristics / M. Gendreau, J.-Y. Potvin. – New York : Springer, 2010. – 640 p. DOI:10.1007/978-1-4419-1665-5
12. Metaheuristics. Progress in Complex Systems Optimization / [K. F. Doerner, M. Gendreau, P. Greistorfer et al.], W. Gutjahr, R. F. Hartl, M. Reimann. – New York : Springer, 2007. – 408 p. DOI: 10.1007/978-0-387-71921-4
13. Bozorg Haddad O. Meta-heuristic and Evolutionary Algorithms for Engineering Optimization / O. Bozorg Haddad, M. Solgi,
H. Loaiciga. – Hoboken, New Jersey : Wiley & Sons, 2017. – 293 p. DOI: 10.1002/9781119387053
14. Chopard B. An Introduction to Metaheuristics for Optimization / B. Chopard, M. Tomassini. – New York : Springer, 2018. – 230 p. DOI:10.1007/978-3-319-93073-2
15. Radosavljević J. Metaheuristic Optimization in Power Engineering / J. Radosavljević. – New York : Institution of Engineering and Technology, 2018. – 536 p. DOI:10.1049/PBPO131E
16. de Castro L. N. The clonal selection algorithm with engineering applications / L. N. de Castro, F. J. von. Zuben // The Genetic and Evolutionary Computation Conference (GECCO’00) : Workshop on Artificial Immune Systems and Their Applications: proceedings. – Las Vegas, 2000. – P. 36–39.
17. de Castro L. N. Learning and optimization using clonal selection principle / L. N. de Castro, F. J. von. Zuben // IEEE Transactions on Evolutionary Computation. – 2002. – Vol. 6. – P. 239–251. DOI: 10.1109/TEVC.2002.1011539
18. Babayigit B. A clonal selection algorithm for array pattern nulling by controlling the positions of selected elements / B. Babayigit, K. Guney, A. Akdagli // Progress in Electromagnetics Research. – 2008. – Vol. 6. – P. 257–266. DOI:10.2528/PIERB08031218
19. White J. A. Improved pattern recognition with artificial clonal selection / J. A. White, S. M. Garrett // In: Timmis J., Bentley P. J., Hart E. (eds). Artificial Immune Systems: ICARIS- 2003. – Berlin : Springer, 2003. – P. 181–193. – (Lecture Notes in Computer Science, Vol. 2787). DOI:10.1007/978-3-540-45192-1_18
20. Alba E. Metaheuristics for Dynamic Optimization / E. Alba, A. Nakib, P. Siarry. – Berlin : Springer-Verlag, 2013. – 398 p.
DOI: 10.1007/978-3-642-30665-5
21. Du K.-L. Search and Optimization by Metaheuristics. Techniques and Algorithms Inspired by Nature / K.-L. Du, M. N. S. Swamy. – Charm : Springer, 2016. – 434 p. DOI:10.1007/978-3-319-41192-7
22. Brownlee J. Clever algorithms: nature-inspired programming recipes / J. Brownlee. – Melbourne : Brownlee, 2011. – 436 p.






Copyright (c) 2019 O. O. Grygor, E. E. Fedorov, T. Y. Utkina, A. G. Lukashenko, K. S. Rudakov K. S., D. A. Harder, V. M. Lukashenko

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.