Date of Award
12-2010
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Industrial Engineering
Committee Chair/Advisor
Kurz, Mary E
Committee Member
Ferrell , William G
Committee Member
Mason , Scott J
Committee Member
Mayorga , Maria E
Committee Member
Taaffe , Kevin M
Abstract
The Quadratic Assignment Problem (QAP) is a widely researched, yet complex, combinatorial optimization problem that is applicable in modeling many real-world problems. Specifically, many optimization problems are formulated as QAPs. To resolve QAPs, the recent trends have been to use metaheuristics rather than exact or heuristic methods, and many researchers have found that the use of hybrid metaheuristics is actually more effective. A newly proposed hybrid metaheuristic is path relinking (PR), which is used to generate solutions by combining two or more reference solutions. In this dissertation, we investigated these diversification and intensification mechanisms using QAP. To satisfy the extensive demands of the computational resources, we utilized a High Throughput Computing (HTC) environment and test cases from the QAPLIB (QAP test case repository).
This dissertation consists of three integrated studies that are built upon each other. The first phase explores the effects of the parameter tuning, metaheuristic design, and representation schemes (random keys and permutation solution encoding procedures) of two path-based metaheuristics (Tabu Search and Simulated Annealing) and two population-based metaheuristics (Genetic Algorithms and Artificial Immune Algorithms) using QAP as a testbed.
In the second phase of the study, we examined eight tuned metaheuristics representing two representation schemes using problem characteristics. We use problem size, flow and distance dominance measures, sparsity (number of zero entries in the matrices), and the coefficient of correlation measures of the matrices to build search trajectories.
The third phase of the dissertation focuses on intensification and diversification mechanisms using path-relinking (PR) procedures (the two variants of position-based path relinking) to enhance the performance of path-based and population-based metaheuristics. The current research in this field has explored the unusual effectiveness of PR algorithms in variety of applications and has emphasized the significance of future research incorporating more sophisticated strategies and frameworks. In addition to addressing these issues, we also examined the effects of solution representations on PR augmentation.
For future research, we propose metaheuristic studies using fitness landscape analysis to investigate particular metaheuristics' fitness landscapes and evolution through parameter tuning, solution representation, and PR augmentation.
The main research contributions of this dissertation are to widen the knowledge domains of metaheuristic design, representation schemes, parameter tuning, PR mechanism viability, and search trajectory analysis of the fitness landscape using QAPs.
Recommended Citation
Rupasinghe, Thashika, "AN INVESTIGATION OF METAHEURISTICS USING PATH- RELINKING ON THE QUADRATIC ASSIGNMENT PROBLEM" (2010). All Dissertations. 625.
https://tigerprints.clemson.edu/all_dissertations/625