A Domain Aware Genetic Algorithm for the p-Median Problem.

摘要

The p-median problem is an NP-complete combinatorial optimization problem often used in the fields of facility location and clustering. Given a graph with n nodes and an integer p n, the p-median problem seeks a set of p medians such that the sum of the distances of the n nodes from their nearest median is minimized. This dissertation develops a genetic algorithm that generates solutions to the p-median problem that improves on previously published genetic algorithms by implementing operators that exploit domain specific information. More specifically, this GA explores the following: (1) The advantages of using "good" solutions generated using extant heuristics in the initial generation of chromosomes. (2) The effectiveness of a crossover operation that exchanges centers in the same neighborhood rather than exchanging arbitrarily chosen subsets of centers. (3) The efficacy of using a biased mutation operator that favors replacing existing medians from less fit chromosomes with non-median nodes from the same neighborhood as the median being replaced.;Using published problem sets with known solutions, this dissertation examines solutions identified by the new genetic algorithm in order to determine the accuracy, efficiency and performance characteristics of the new algorithm. In addition, it tests the contribution of each of the algorithm's operators by systematically controlling for all the other factors.;The results of the analysis showed that integrating operators that exploited domain specific information did have an overall positive impact on the genetic algorithm. In addition, the results showed that using a structured initial population had little impact on the algorithm's ability to find an optimal solution but it did create a better initial solution and allowed the algorithm to produce a relatively good solution early in the search. Also, the analysis showed that a directed approach to crossover operations was effective and produced superior solutions. Finally, the analysis showed that a directed approach toward mutation did not have a large impact on the overall functionality of the algorithm and may be inferior to an arbitrary approach to mutation.