Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems |
| |
Authors: | Jing Tang Meng Hiot Lim Yew Soon Ong |
| |
Affiliation: | (1) School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore, 639798, Singapore;(2) School of Computer Engineering, Nanyang Technological University, Singapore, 639798, Singapore |
| |
Abstract: | Parallel memetic algorithms (PMAs) are a class of modern parallel meta-heuristics that combine evolutionary algorithms, local
search, parallel and distributed computing technologies for global optimization. Recent studies on PMAs for large-scale complex
combinatorial optimization problems have shown that they converge to high quality solutions significantly faster than canonical
GAs and MAs. However, the use of local learning for every individual throughout the PMA search can be a very computationally
intensive and inefficient process. This paper presents a study on two diversity-adaptive strategies, i.e., (1) diversity-based
static adaptive strategy (PMA-SLS) and (2) diversity-based dynamic adaptive strategy (PMA-DLS) for controlling the local search
frequency in the PMA search. Empirical study on a class of NP-hard combinatorial optimization problem, particularly large-scale
quadratic assignment problems (QAPs) shows that the diversity-adaptive PMA converges to competitive solutions at significantly
lower computational cost when compared to the canonical MA and PMA. Furthermore, it is found that the diversity-based dynamic
adaptation strategy displays better robustness in terms of solution quality across the class of QAP problems considered. Static
adaptation strategy on the other hand requires extra effort in selecting suitable parameters to suit the problems in hand. |
| |
Keywords: | Island model parallel memetic algorithm Adaptive local search frequency Quadratic assignment problem |
本文献已被 SpringerLink 等数据库收录! |
|