A high-efficient multi-deme genetic algorithm with better load-balance. (2018)

• Record Type: Journal Article
• Authors: Jie, Wang; Jiangjun, Yuan
• Is Part Of: International journal of computing science and mathematics. Volume 9:Number 3(2018)
• Page Start: 240
• Page End: 246
• Publication Date: 2018
• Subjects: genetic algorithm -- multi-deme genetic algorithm -- MGA -- load imbalance -- fine-grained schedule; Mathematics -- Periodicals; Computer science -- Periodicals; Mathematics -- Data processing -- Periodicals; 510.285
• Languages: English
• ISSNs: 1752-5055

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.