Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems

Jing Tang

doi:10.1007/s00500-006-0139-6

Return

Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems

2006-10-18

114

PRE

DOI：10.1007/s00500-006-0139-6

Original

Original request for help

Save

Abstract

En 中文

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