Opposition-based Memetic Search for the Maximum Diversity Problem

Fichier pdf chargé le 04/06/2017 à 09:52:06
Accès libre
(version auteur)
TitreOpposition-based Memetic Search for the Maximum Diversity Problem
Type de publicationArticle de revue
AuteurZhou, Yangming , Hao, Jin-Kao , Duval, Béatrice
1, 2
EditeurInstitute of Electrical and Electronics Engineers
TypeArticle scientifique dans une revue à comité de lecture
DateOctobre 2017
Titre de la revueIEEE Transactions on Evolutionary Computation
Mots-clésLearning-based optimization, Maximum diversity, Memetic search, opposition-based learning, tabu search
Résumé en anglais

As a usual model for a variety of practical applications, the maximum diversity problem (MDP) is computational challenging. In this paper, we present an opposition-based memetic algorithm (OBMA) for solving MDP, which integrates the concept of opposition-based learning (OBL) into the wellknown memetic search framework. OBMA explores both candidate solutions and their opposite solutions during its initialization and evolution processes. Combined with a powerful local optimization procedure and a rank-based quality-and-distance pool updating strategy, OBMA establishes a suitable balance between exploration and exploitation of its search process. Computational results on 80 popular MDP benchmark instances show that the proposed algorithm matches the best-known solutions for most of instances, and finds improved best solutions (new lower bounds) for 22 instances. We provide experimental evidences to highlight the beneficial effect of opposition-based learning for solving MDP.

URL de la noticehttp://okina.univ-angers.fr/publications/ua15973
Lien vers le document


Titre abrégéIEEE Trans. Evol. Computat.