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.)

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.