Priority Encoding Scheme for Solving Permutation and Constraint Problems with Genetic Algorithms and Simulated Annealing

Encoding for solutions of combinatorial optimization problems involving permutations or constraints that maintain the generality of operators in evolutionary computation is often difficult. In this paper, we present the Priority Encoding Scheme (PES), a general-purpose encoding scheme that encodes information used to construct solutions rather than directly encoding solutions themselves. We show that not only is PES simple to implement, but that it can be used effectively with Genetic Algorithms (GA) and Simulated Annealing (SA) to find good solutions to the multiple-constraint knapsack problem (MKP) and shows promise for finding good solutions to the traveling salesman problem (TSP).