Increasing Population Variability in Parallel Genetic Algorithms with a Greedy Crossover for Large-Scale p-Median Problems

The continuous p-median problem is a classical unconstrained global optimization model of unsupervised machine learning and location theory where the aim is to find p points (medians) so that the sum of distances from known demand points to the closest of the p sought points reaches its minimum. The problem is NP-hard, and the researchers focus on the development of heuristic algorithms. A greedy agglomerative procedure starts its search from a solution with an excessive number of medians K > p and combines the elimination of the medians with local search procedures. Genetic algorithms with the crossover operator based on greedy agglomerative procedures are capable of obtaining rather precise results. However, they are computationally expensive, which limits their scope for mediumscale problems. In the case of running such algorithms on massive parallel processing systems with large-scale problems, the population degeneration plays more important role. We propose hybrid genetic algorithms with both crossover and mutation operators involving the greedy agglomerative procedures and partially isolated subpopulations (islands) for the p-median problem. Computational experiments show the comparative efficiency of new algorithmic combinations and demonstrate that with an increase in the input data volume, the instruments for maintaining the population diversity improve the obtained results.