Authors D. Ju. Zaporozhets, D. V. Zaruba
Month, Year 04, 2018 @en
Index UDC 681.3.06
Abstract The architecture of parallel search is proposed herein. The following three levels of parallelization are distinguished: microlevel, that is the parallelization of tasks at the level of execution of operators generating new alternative solutions; macrolevel, that is the parallelization of the search at the generation level; meta-level, that is the parallelization of the search process at the level of an isolated set of alternative solutions. As an example, herein we propose the implementation of a parallel genetic algorithm with parallelization at the microlevel. A generalized architecture is proposed and the main steps of a new parallel genetic algorithm with parallelization at the micro level are described. The basic idea of this approach is the initialization of N threads, in each of which the crossing-over operator is executed and, with a certain probability, mutation and inversion operators. For all new solutions, the fitness is calculated in the flow in which the decision was received. The algorithm waits for all threads to end. Then, all new generated solutions are combined into one population and the selection operator is executed. The process continues iteratively after reaching the specified number of iterations. To confirm the effectiveness of the proposed approach, a software implementation of the parallel genetic algorithm was developed. As an applied problem one of the classical optimization problems was chosen - the Hamiltonian cycle in the graph. The purpose of conducting experimental studies is the speed of the implemented genetic algorithm, as well as its comparison with the classical "sequential" genetic algorithm. The research was conducted on two different platforms with processors: Intel I7 – 4 cores, 2.7 GHz and AMD 6000 – 2 2.5 GHz cores. Experimental studies have been performed that showed a significant increase in the speed of the algorithm with a number of vertices in the graph of more than 250. The speed of the algorithm increased by 100–200 % compared with the classical implementation, depending on the processor used. Thus, it has been experimentally proved that with the use of the same hardware, the proposed parallel approach makes it possible to shorten the running time of the optimization algorithm by several times compared to its classical sequential implementation.

Download PDF

Keywords Genetic algorithms; parallel search; population algorithms; traveling salesman problem; hamiltonian cycle.
References 1. Kureychik V.M., Pisarenko V.I., Kravchenko Yu.A. Tekhnologiya mnogoaspektnogo analiticheskogo issledovaniya kak metod mashinnogo obucheniya [Technology multidimensional analytical studies as a method of machine learning], Otkrytoe obrazovanie [Open education], 2008, No. 2, pp. 11-17.
2. Kurejchik V.V., Kurejchik V.M. On genetic-based control, Avtomatika i telemekhanika [Automation and remote control], 2001, No. 10, pp. 174-187.
3. Kureychik V.M., Kureychik V.V., Rodzin S.I., Gladkov L.A. Osnovy teorii evolyutsionnykh vychisleniy [Fundamentals of the theory of evolutionary computation]. Rostov-on-Don: YuFU, 2010, 222 p.
4. Kureychik V.V., Kureychik V.M., Zinchenko L.A. i dr. Bionicheskie informatsionnye sistemy i ikh prakticheskie primeneniya [Bionic information systems and their practical applications]. Moscow: Fizmatlit, 2011, 288 p.
5. Rodzin S.I., Kureychik V.V. Sostoyanie, problemy i perspektivy razvitiya bioevristik [State, problems and prospects of development of bio-heuristics], Programmnye sistemy i vychislitel'nye metody [Software systems and computational methods], 2016, No. 2, pp. 158-172.
6. Rodzin S.I., Kureychik V.V. Teoreticheskie voprosy i sovremennye problemy razvitiya kognitivnykh bioinspirirovannykh algoritmov optimizatsii [Theoretical questions and contemporary problems of the development of cognitive bio-inspired algorithms for optimization], Kibernetika i programmirovanie [Cybernetics and programming], 2017, No. 3, pp. 51-79.
7. Zaporozhets D., Zaruba D. Bacterial foraging optimization for VLSI fragments placement, Advances in Intelligent Systems and Computing, 2018, 679, pp. 341-348.
8. Kureichik V.M., Lebedev B.K., Lebedev O.B. Channel routing based on ant colony adaptive behavior model, Journal of Computer and Systems Sciences International, 2015, Vol. 54 (2), pp. 278-293.
9. Kureichik V.V., Kravchenko Y.A. Bioinspired algorithm applied to solve the travelling salesman problem, World Applied Sciences Journal, 2013, Vol. 22, No. 12, pp. 1789-1797.
10. Kureychik V.V., Zaruba D.V., Zaporozhets D.Yu. Algoritm parametricheskoy optimizatsii na osnove modeli povedeniya roya svetlyachkov [The algorithm of parametric optimization based on the behavior patterns of a swarm of fireflies], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 6 (167), pp. 6-15.
11. Kureychik V.V., Zaruba D.V., Zaporozhets D.Yu. Ierarkhicheskiy podkhod pri razmeshchenii komponentov SBIS [A hierarchical approach to the placement of VLSI components], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156),
pp. 75-84.
12. Kuliev E.V., Kureychik V.V., Kursitys I.O. Prinyatie resheniy v zadache razmeshcheniya komponentov SBIS na osnove modeli povedeniya stai volkov [Decision-making in the problem of placing VLSI components based on the behavior model of a pack of wolves], Mezhdunarodnaya konferentsiya po myagkim vychisleniyam i izmereniyam [International conference on soft computing and measurements], 2018, Vol. 1, pp. 712-715.
13. Kuliev E.V., Kravchenko Yu.A., Loginov O.A., Zaporozhets D.Yu. Metod intellektual'nogo prinyatiya effektivnykh resheniy na osnove bioinspirirovannogo podkhoda [Method of intellectual decision-making based on bioinspired approach], Izvestiya Kabardino-Balkarskogo nauchnogo tsentra RAN [Izvestiya of Kabardino-Balkar scientific center of RAS], 2017,
No. 6-2 (80), pp. 162-169.
14. Knysh D.S., Kureichik V.M. Genetic algorithm for routing switching units, Russian Microelectronics, 2011, Vol. 40 (7), pp. 486-490.
15. Kureychik V.M., Kureychik V.V., Rodzin S.I. Modeli parallelizma evolyutsionnykh vychisleniy. [Models of parallelism of evolutionary calculations], Vestnik Rostovskogo gosudarstvennogo universiteta putey soobshcheniya [Bulletin of Rostov state University of railway engineering], 2011, No. 3 (43), pp. 93-97.
16. Knysh D.S., Kureichik V.M. Parallel genetic algorithms: A survey and problem state of the art, Journal of Computer and Systems Sciences International, 2010, Vol. 49 (4), pp. 579-589.
17. Kacprzyk J., Kureichik V.M., Malioukov S.P., Kureichik V.V., Malioukov A.S. Experimental investigation of algorithms developed, Studies in Computational Intelligence, 2009, Vol. 212, pp. 211-223+227-236.
18. Gladkov L.A., Kureichik V.V., Kravchenko Y.A. Evolutionary algorithm for extremal subsets comprehension in graphs, World Applied Sciences Journal, 2013, Vol. 27, No. 9, pp. 1212-1217.
19. Polkovnikova N.A., Kureichik V.M. Hybrid Expert System Development Using Computer-Aided Software Engineering Tools, Communications in Computer and Information Science, 466 CCIS, 2014, pp. 433-445.
20. Gudilov V., Kureichik V. Evolutional synthesis with incomplete information, Life Science Journal, 11 (10 SPEC. ISSUE), art. no. 68, 2014, pp. 359-363.

Comments are closed.