Date of Award
1985
Degree Type
Dissertation
Degree Name
Doctor of Philosophy
Abstract
This thesis is concerned with the application of genetic algorithms to solve the p-median problem. The problem finds a specified number of locations that are the most accessible among a fixed set of locations. Genetic algorithms are an adaptive search method based on models of mathematical population genetics. Basically, the algorithms simulate the evolution of a population in an environment, where selective pressure during evolution forces the population to improve. Modification to fit a particular environment is in a sense optimization. The extended analogy has the environment as the objective function of the p-median, the population as a set of solutions, and the optimal solution as creation after evolution.;This study describes the extant methodologies for solving the problem, and concludes that because they are either limited by computation time, or to small problems, methods with reliability and/or speed are needed.;The quantitative developments in population genetics are described together with the theory of natural selection. Artificial adaptive systems have used natural systems to confirm their models. Natural selection, or reproduction in proportion to measured performance, has been equated to optimization. The mechanisms of genetic algorithms are described as a stochastic process, where knowledge about the entire population is obtained through patterned sampling.;The implementation of a genetic algorithm to solve the p-median first requires a representation that is suitable for the genetic operators that simulate the reproduction of genetic material by recombining and mutation the existing material. A representation for this problem was designed and its operability proved in two algorithms. The two algorithms used in testing are given and the parameters adjusted during experimentation are reviewed.;The genetic algorithms required significant fine tuning and the invention of a new mutation operator for the p-median. Three methods of calculation the probability of selection were tested. Scaling of the objective functions prior to selection was a substantially superior method.;Several factors are thought to be responsible for the less than robust performance of the algorithm: The selective pressures may have been incorrectly specified via the probabilities of selection, and the mapping of solutions in the representation was prone to epistasis that was exacerbated by genetic drift and resulted in suboptimal solution. (Abstract shortened with permission of author.)
Recommended Citation
Hosage, Catherine Marya, "Genetic Algorithms Applied To The ('p')-median Problem" (1985). Digitized Theses. 1473.
https://ir.lib.uwo.ca/digitizedtheses/1473