Particle Swarm Optimization and Differential Evolution for Derangement Problems

Combinatorial optimization involves solving problems that can be represented by combinatorial objects. Due to the complexity of these problems, exact solutions are difficult to obtain. Consequently, nature-inspired metaheuristics have been widely used to provide approximate solutions. While nature-inspired approaches have been extensively applied to general permutation and combination problems, there is limited exploration in solving constrained permutation problems, such as derangements. This paper investigates the use of Particle Swarm Optimization (PSO) and Differential Evolution (DE) to solve derangement problems. We introduce a novel, efficient algorithm that transforms arbitrary permutations into derangements and analyze its impact on the effectiveness of PSO and DE in solving these problems. The results contribute to the application of nature-inspired metaheuristics in constrained combinatorial optimization. Finally, we note the potential of constrained permutation problems to test nature-inspired metaheuristics.