Title: A high-efficient multi-deme genetic algorithm with better load-balance

Authors: Wang Jie; Yuan Jiangjun

Addresses: School of Shangmao, Zhejiang Technical Institute of Economics, Hangzhou, 310018, China ' School of Shangmao, Zhejiang Technical Institute of Economics, Hangzhou, 310018, China

Abstract: Genetic algorithm is a very powerful search algorithm that fits for many complex situations. However, it is very time consuming, which limits its usage. Previous work which makes use of multi-core systems to parallelise it performs well and gains much attention. This paper introduces that the load-imbalance problem in parallel genetic algorithm will incur large overhead and will limit the performance. We propose two efficient mechanisms (postponed waiting and work stealing) to achieve fine-grained schedule to solve the problem. Compared with traditional multi-deme parallel genetic algorithm, our high-efficient multi-deme genetic algorithm (HMGA) can achieve an average speedup of 1.36.

Keywords: genetic algorithm; multi-deme genetic algorithm; MGA; load imbalance; fine-grained schedule.

DOI: 10.1504/IJCSM.2018.093162

International Journal of Computing Science and Mathematics, 2018 Vol.9 No.3, pp.240 - 246

Received: 08 Dec 2017
Accepted: 21 Mar 2018
Published online: 11 Jul 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article