CCE Theses and Dissertations

Date of Award

2011

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Computer Information Systems (DCIS)

Department

Graduate School of Computer and Information Sciences

Advisor

Sumitra Mukherjee

Committee Member

Michael Laszlo

Committee Member

Greg Simco

Keywords

Genetic Algorithm, p-Median

Abstract

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.

Download
Share Feedback

  Link to NovaCat

Share

COinS