Self-adjusting Genetic Algorithm with Greedy Agglomerative Crossover for Continuous p-Median Problems

The continuous p-median problem is a classical global optimization model used both for finding optimal locations of facilities on a plane, and as a clustering model. The problem is to find p points (medians) such that the sum of the distances from known demand points to the nearest median is minimal. Such a clustering model is less sensitive to “outliers” (separately located demand points that are not included in any cluster), compared with k-means models. Many heuristic approaches were proposed for this NP-hard problem. The genetic algorithms with the greedy agglomerative crossover operator are some of the most accurate heuristic methods. However, a parameter of this operator (parameter r) determines the efficiency of the whole genetic algorithm. The optimal value of this parameter is hardly predictable based on numerical parameters of the problem such as the numbers of demand points and medians. We investigate its influence on the result of the algorithm, and also propose the use of an exploratory search procedure for adjusting it. The advantages of the self-adjusting algorithm are shown for problems with a data volume of up to 2,075,259 objects.