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.
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: 29 Jun 2018 *