2022, issue 2, p. 31-37

Received 01.09.2022; Revised 13.09.2022; Accepted 29.09.2022

Published 30.09.2022; First Online 05.10.2022

https://doi.org/10.34229/2707-451X.22.2.3

Previous  |  FULL TEXT (in Ukrainian)  |  Next

 

UDC 519.711: 519.711.3: 519.81

About Selecting the Number of Processors for Parallel Multipopulation Genetic Algorithm

Ihor Lukianov,   Fedir Lytvynenko

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it., This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. The paper considers some features of the parallel implementation of a multipopulation genetic algorithm, as well as approaches to its optimization. The results of experiments with the use of a different number of processors and different methods of generating initial populations are presented in order to optimize the algorithm according to several criteria (assessment of the use of computational and time resources). On the example of a specific test problem, estimates are given for choosing the optimal number of processors to obtain the desired result.

The purpose of this work is to conduct experiments with a given test problem with a different number of processors and alternative methods for generating the initial population to evaluate the effectiveness of the algorithm.

Results. For the test problem, to obtain a result of 90–94 % of the optimum, the most efficient in terms of computing resources is the use of 4 processors with an algorithm for uniform scanning of the space of factor values. To achieve a result exceeding 94 % and optimize by K1 (computational resources), 8 processors and an algorithm for uniform scanning of the space of factor values showed the best result. If we also take into account the criterion of time resources K2, then to achieve 90–98 % of the optimum, it is necessary to use 8 processors, for 99–100 % 12 or 16 processes, depending on С1 and С2 (cost of computational and time resources respectively).

Conclusions. Performed experiments show that the algorithm of uniform scanning of the space of factor values is more efficient than the random method of generating the initial population. Experiments also showed that in order to achieve the maximum efficiency of PMGA, the number of processors must be chosen depending on the desired result precision.

 

Keywords: parallel genetic algorithm, initial population generation, choice of the number of processors (populations), algorithm optimization.

 

Cite as: Lukianov I., Lytvynenko F. About Selecting the Number of Processors for Parallel Multipopulation Genetic Algorithm. Cybernetics and Computer Technologies. 2022. 2. P. 31–37. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.2.3

 

References

           1.     Lytvynenko F., Lukianov I., Krykovluk H. Features of the implementation of the parallel version of the multipopulation genetic algorithm. Kompyuterna matematyka. 2018. 2. P. 21–29. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/161882

           2.     Lukianov I., Lytvynenko F., Krykovluk H. On Improving the Efficiency of the Parallel Version of the Multipopulation Genetic Algorithm. Teoriya optumalnuh rishen. 2019. 18. P. 116–122. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/161683

           3.     Lytvynenko F., Lukianov I., Krykovluk H. Using the Diversity of the Initial Population in a Multipopulation Genetic Algorithm. Kompyuterna matematyka. 2019. 1. P. 116–123. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/161941

           4.     Horne G.E., Meyer T.E. Data Farming: Discovering Surprise. Proc. of the Winter Simulation Conference, 2005. P. 1082–1087.

           5.     Horne G.E., Schwierz K.-P. Data Farming around the world overview. Proc. of the Winter Simulation Conference. 2008. P. 1442–1447. https://doi.org/10.1109/WSC.2008.4736222

           6.     Pepelyaev V., Chernii Y. On the possibilities of using genetic algorithms in optimization and simulation experiments. Teoriya optumalnuh rishen. 2019. 18. P. 69–77. (in Russian) http://dspace.nbuv.gov.ua/handle/123456789/161681

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT (in Ukrainian)  |  Next

 

 

 

© Website and Design. 2019-2024,

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine,

National Academy of Sciences of Ukraine.