2005 | OriginalPaper | Chapter
An Evolutionary Approach for the Maximum Diversity Problem
Authors : Kengo Katayama, Hiroyuki Narihisa
Published in: Recent Advances in Memetic Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The objective of the maximum diversity problem (MDP) is to select a set of
m
-elements from larger set of
n
-elements such that the selected elements maximize a given diversity measure. The paper presents an evolutionary algorithm incorporating local search — memetic algorithm (MA) — for the MDP which consists of a greedy method, simple evolutionary operators, a repair method, and a
k
-flip local search based on
variable depth search
. In the MA, the
k
-flip local search starts with a feasible solution and obtains a local optimum in the feasible search space. Since infeasible solutions may be created by the simple crossover and mutation operators even if they start with feasible ones found by the local search, the repair method is applied to such infeasible solutions after the crossover and the mutation in order to guarantee feasibility of solutions to the problem. To show the effectiveness of the MA with the
k
-flip local search, we compare with a MA with 2-flip local search for large-scale problem instances (of up to
n
=2500) which are larger than those investigated by other researchers. The results show that the
k
-flip local search based MA is effective particularly for larger instances. We report the best solution found by the MA as this is the first time such large instances are tackled.