Adaptive Load Balancing in the Modified Mind Evolutionary Computation Algorithm

Maxim K. Sakharov; Anatoly P. Karpenko

doi:10.14529/jsfi180401

Authors

Maxim K. Sakharov Bauman MSTU
Anatoly P. Karpenko Bauman MSTU

DOI:

https://doi.org/10.14529/jsfi180401

Abstract

The paper presents an adaptive load balancing method for the modified parallel Mind Evolutionary Computation (MEC) algorithm. The proposed method takes into account an objective function's topology utilizing the information obtained during the landscape analysis stage as well as the information on available computational resources. The modified MEC algorithm and proposed static load balancing method are designed for loosely coupled parallel computing systems and imply a minimal number of interactions between computational nodes when solving global optimization problems. A description of the proposed method is presented in this work along with the results of computational experiments, which were carried out with a use of multi-dimensional benchmark functions of various classes. Obtained results demonstrate that an effective use of available computational resources in the proposed method helps finding a better solution comparing to the traditional parallel MEC algorithm balancing. Further development of the proposed method requires more advanced termination criteria in order to avoid excessive iterations.

References

Bischl, B., Mersmann, O., Trautmann, H., Preub, M.: Algorithm selection based on exploratory landscape analysis and cost-sensitive learning. In: Proceedings of the fourteenth Adaptive Load Balancing in the Modied Mind Evolutionary Computation Algorithm international conference on Genetic and evolutionary computation conference, New York, NY, USA. pp. 313–320 (2012), DOI: 10.1145/2330163.2330209

Chengyi, S., Yan, S., Wanzhen, W.: A Survey of MEC: 1998-2001. In: IEEE International Conference on Systems, Man and Cybernetics IEEE SMC2002, Hammamet, Tunisia. October 6-9. Institute of Electrical and Electronics Engineers Inc., vol. 6, pp. 445–453 (2002), DOI: 10.1109/ICSMC.2002.1175629

Floudas, A.A., Pardalos, P.M., Adjiman, C., Esposito, W.R., Gumus, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization. Kluwer, Dordrecht (1999)

Foster, I.: Designing and building parallel programs: concept and tools for parallel software engineering. Boston, Addison–Wesley (1995)

Gubenko, G.: Dynamic load Balancing for Distributed Memory Multiprocessors. Journal of parallel and distributed computing, 7, 279–301 (1989)

Jie, J., Han, C., Zeng, J.: An Extended Mind Evolutionary Computation Model for Optimizations. Applied Mathematics and Computation, 185, 1038–1049. (2007), DOI: 10.1016/j.amc.2006.07.037

Jie, J., Zeng, J.: Improved Mind Evolutionary Computation for Optimizations. In: Proceedings of 5th World Congress on Intelligent Control and Automation, 15–19 June 2004, Hang Zhou, China, pp. 2200–2204 (2004), DOI: 10.1109/WCICA.2004.1341978

Karpenko, A.P.: Modern algorithms of search engine optimization. Nature–inspired optimization algorithms. Moscow, Bauman MSTU Publ. (2014) (in Russian)

Karpenko, A.P., Sakharov, M.K.: Multi–memetic global optimization based on MEC. Information Technologies, 7, 23–30 (2014)

Kerschke, P., et al.: Cell mapping techniques for exploratory landscape analysis. EVOLVE A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation V, Springer, 115–131 (2014), DOI: 10.1007/978-3-319-07494-8 9

Liang, J.J., Qu, B.Y., Suganthan, P.N.: Problem Definitions and Evaluation Criteria for the CEC 2014. Special Session and Competition on Single Objective Real–Parameter Numerical Optimization. Technical Report, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China and Technical Report, Nanyang Technological University, Singapore (2013)

Mersmann, O., et al.: Exploratory landscape analysis. In: Proceedings of the 13th annual conference on Genetic and evolutionary computation, July 12–16, Dublin, Ireland. ACM, pp. 829–836 (2011), DOI: 10.1145/2001576.2001690

Munoz, M.A., Kirley, M., Halgamuge, S.K.: Exploratory landscape analysis of continuous space optimization problems using information content. IEEE Transactions on Evolutionary Computation, 19(1), 74–87 (2015), DOI: 10.1109/TEVC.2014.2302006

Sakharov, M., Karpenko, A.: A New Way of Decomposing Search Domain in a Global Optimization Problem. In: Proceedings of the Second International Scientific Conference Intelligent Information Technologies for Industry (IITI17). Springer, pp. 398–407 (2018), DOI: 10.1007/978-3-319-68321-8 41

Sakharov, M., Karpenko, A.: New Parallel Multi–Memetic MEC–Based Algorithm for Loosely Coupled Systems. In: Proceedings of the VII International Conference on Optimization Methods and Application Optimization and applications OPTIMA–2016, September 25 – October 2, Petrova, Montenegro. pp. 124–126 (2016)

Sakharov, M., Karpenko, A.: Performance Investigation of Mind Evolutionary Computation Algorithm and Some of Its Modifications. In: Proceedings of the First International Scientific Conference Intelligent Information Technologies for Industry (IITI16), Springer, pp. 475–486 (2016), DOI: 10.1007/978-3-319-33609-1 43

Sakharov, M.K., Karpenko, A.P., Velisevich, Ya.I.: Multi–Memetic Mind Evolutionary Computation Algorithm for Loosely Coupled Systems of Desktop Computers. Science and Education of the Bauman MSTU, 10, 438–452 (2015), DOI: 10.7463/1015.0814435

Sobol, I.M., Distribution of points in a cube and approximate evaluation of integrals. USSR Comput. Maths. Phys., 7, 86–112 (1967)

Vassilev, V., Fogarty, T., Miller, J.: Smoothness, ruggedness and neutrality of fitness landscapes: from theory to application. Advances in evolutionary computing. New York, NY, USA, Springer, 3–44 (2003)

Voevodin V.V., Voevodin Vl. V.: Parallel Computations. SPb.: BHV–Peterburg, (2004) (In Russian)