Augmenting Metaheuristics with Rewriting Systems

Citation

Swan J, Edjvet M & Ozcan E (2014) Augmenting Metaheuristics with Rewriting Systems. Computing Science and Mathematics-Muscat. Technical Report, CSM-197. Stirling FK9 4LA, Scotland: University of Stirling, Department of Computing Science and Mathematics. http://www.cs.stir.ac.uk/~jsw/metaheuristic-atp-TR.pdf

Abstract
We describe the use of a rewriting system to determine equivalence classes over the search-space of optimisation problems. These equivalence classes may be used to derive redundant subsequences in the search-space for incorporation into metaheuristics such as backtracking, genetic algorithms and tabu-search. We use this approach as the basis for a new tabu-search variant - ‘Equational- TS' and apply it to the Quadratic Assignment Problem, yielding significant results in terms of the number of iterations to convergence.