Performance Analysis And Optimization Of Genetic Algorithms On Multi-core Systems

Genetic Algorithm (GA) is a random algorithm which is widely applied to solvecomplex engineering problems. It is a computational model which originated from thenatural process of evolution and selection. Due to the strong independencies amongIndividuals in a Population of GA during the key operations (selection, crossover andmutation), GAcanbeeasilyparallelized. Therefore, theresearchofParallelGA(PGA)can be dated back to the invention of GA itself. As the popularization of multi-coreprocessor, the costs to do research in GA have been largely reduced. Most researchersmainly focus on the improvement on the algorithm of GA itself or special applicationscenarios. However, because of ignoring or misunderstanding the architectural detailsof multi-processor, there are now still no general rules or guidelines to exploit perfor-mance improvement of GA from an architecture perspective.In this paper, we ?rstly try to reveal the performance of 3 schemes of PGA -Master-Salve scheme, Island scheme and Mixed scheme - by fully understand the ar-chitecture of Chip Multi-Processor (CMP). We raise a new perspective to evaluate GAaccording to how fast it could reach a ?xed solution. For the Master-Salve scheme,we introduce a Thread Align concept to avoid extra performance overhead. For theIsland scheme, we compare the synchronized and asynchronized model in theory. Forthe Mixed scheme, we introduce a concept of Parallelism Degree (PD) to indicate thetradeo? between speed and accuracy of GA. The corresponding experiments demon-strate that our rules are e?ective, and there does exist a PD whose value could lead theMixed scheme reach the ?xed value with the highest speed.According to the good performance of Mixed Scheme, we extend out target sys-tem to symmetric multi-processor (SMP). Based on the architectural features of SMP, we proposed an optimized thread organization strategy for Mixed scheme to improveits performance by reducing the overhead of maintaining cache coherence among pro-cessors. The strategy could guide users to manually bind threads to correspondingprocessors while adopting Mixed scheme. The corresponding experiments demon-strate that this thread organization optimization strategy could bene?t Mixed schemean extra 10% speedup.Lastly, to add randomness to GA for bene?ts in solution accuracy, we design anextendrandomnumbermodelforGA.Thismodelaimstobringenormousrandomnessto GA while sacri?ces in space complexity. The corresponding experiments demon-strate that this model could generally gain improvement in solution accuracy for nearlyall schemes of GA.