Open Access Open Access  Restricted Access Subscription or Fee Access

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

Lev Kazakovtsev, Ivan Rozhnov, Guzel Shkaberina

Abstract



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.

Keywords


clustering, p-median problem, CUDA, genetic algorithm, mutation operator

Full Text:

PDF


Disclaimer/Regarding indexing issue:

We have provided the online access of all issues and papers to the indexing agencies (as given on journal web site). It’s depend on indexing agencies when, how and what manner they can index or not. Hence, we like to inform that on the basis of earlier indexing, we can’t predict the today or future indexing policy of third party (i.e. indexing agencies) as they have right to discontinue any journal at any time without prior information to the journal. So, please neither sends any question nor expects any answer from us on the behalf of third party i.e. indexing agencies.Hence, we will not issue any certificate or letter for indexing issue. Our role is just to provide the online access to them. So we do properly this and one can visit indexing agencies website to get the authentic information. Also: DOI is paid service which provided by a third party. We never mentioned that we go for this for our any journal. However, journal have no objection if author go directly for this paid DOI service.