Abstract

Many problems which belong to the classes NP and NP-Complete are permutation-dependent. Their solution depends on finding some appropriate permutation of a set of objects. Since no known polynomial-time algorithms are available for such problems, a deterministic approach to solving them requires the enumeration of all possible permutations of the objects. This leads to unacceptable algorithmic performance. This paper demonstrates a technique derived from the field of Evolutionary Algorithms, which uses the transpositional nature of permutations, both for solving such permutation-dependent problems as well as for dealing with the more complicated subset problems that can occur.