Enhanced forma analysis of permutation problems

ABSTRACT

Forma analysis provides an approach to formally derive domain specific operators based on domain-independent operator templates by manipulating a set of equivalence relations (i.e., the basis), which is used to describe the search space. In the case of permutation problems, where the basis is highly constrained, the declarative nature of forma analysis encounters some difficulties which give rise to some additional issues, such as the interpretation of declarative constraints and the complexity of the application of operator. This paper aims to address these issues by introducing Enhanced Forma Analysis that explores a broader view of forma analysis by using ideas from constraint satisfaction.

REFERENCES

• 1: T. Bäck. Evolutionary Computation 2:Advanced Algorithms and Operators. Institute of Physics (IOP) Publishing, Bristol, UK, 2000.
• 2: T. Bäck, D. Fogel, and Z. Michalewicz. Evolutionary Computation 1:Basic Algorithms and Operators. Institute of Physics (IOP)Publishing, Bristol, UK, 2000.
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: M. DeLeon. A study of su. cient conditions for hamiltonian cycles. Technical report, Department of Mathematics and Computer Science, Seton Hall University, NJ, USA, 2000.
• 5: T. Gong and A. L. Tuson. Formal descriptions of real parameter optimisation. In Proceedings of IEEE Congress on Evolutionary Computation 2006, Vancouver , pages 2119--2126. IEEE Press, 2006.
• 6: I. M. Oliver , D. J. Smith , J. R. C. Holland, A study of permutation crossover operators on the traveling salesman problem, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.224-230, October 1987, Cambridge, Massachusetts, United States
• 7: N. Radcliffe. The algebra of genetic algorithms. Annals of Maths and Artificial Intelligence , 10:339--384, 1994.
• 8: T. Starkweather, S. McDaniel, K. Mathias, C. Whitley, and D. Whitley. A comparison of genetic sequencing operators. In R. Belew and L. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms , pages 69--76. Morgan Kaufmann, 1991.
• 9: P. D. Surry. A Prescriptive Formalism for Constructing Domain-specific Evolutionary Algorithm. PhD thesis, University of Edinburgh, Edinburgh, Scotland, UK, 1998.
• 10: E. P. K. Tsang. Foundations of Constraint Satisfaction. Academic Press, London, UK, 1993.
• 11: A. L. Tuson. No optimization without representation: a knowledge based systems view of evolutionary/neighbourhood search optimization. PhD thesis, University of Edinburgh, Edinburgh, 1999.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Theory

Keywords:
constraint satisfaction, forma analysis, permutation problems