Module org.cicirello.chips_n_salsa
Package org.cicirello.search.operators.permutations
package org.cicirello.search.operators.permutations
This package includes classes that implement local search and evolutionary operators for
permutations, such as mutation operators, crossover operators, and initializers. The classes of
this package depend upon the
Permutation class,
and other classes, from JavaPermutationTools (JPT). More
information on JPT, see its website: https://jpt.cicirello.org/. Or you can go directly to JPT's API
documentation.
For a survey covering the breadth of evolutionary operators available for permutations, along with an analysis of crossover operators that identifies the permutation features (e.g., positions, edges, precedences, etc) that different crossover operators effectively optimize, see the following paper:
Vincent A. Cicirello. A Survey and Analysis of Evolutionary Operators for Permutations. In Proceedings of the 15th International Joint Conference on Computational Intelligence, pages 288-299. November 2023. doi:10.5220/0012204900003595. [PDF] [BIB] [DOI]
The following paper provides an analysis of many of the mutation operators that identifies the permutation features (e.g., positions, edges, precedences, etc) that different crossover operators effectively optimize:
Vincent A. Cicirello. On Fitness Landscape Analysis of Permutation Problems: From Distance Metrics to Mutation Operator Selection. Mobile Networks and Applications, 28(2): 507-517, April 2023. doi:10.1007/s11036-022-02060-z. [PDF] [BIB] [DOI] [PUB] [arXiv]
-
ClassesClassDescriptionThis class implements an adjacent swap mutation on permutations, where one mutation consists in randomly swapping a pair of adjacent elements.This class implements a block interchange mutation on permutations, where one mutation consists in swapping two randomly chosen non-overlapping "blocks" (i.e., subsequences).This class implements a block move mutation on permutations, where one mutation consists in removing a randomly chosen "block" (i.e., subsequence) and reinserting it at a different randomly chosen index.This class implements the Cycle(α) form of cycle mutation on permutations, where one mutation generates a random permutation cycle.Implementation of cycle crossover (CX).This class implements the Cycle(kmax) form of cycle mutation on permutations, where one mutation generates a random permutation cycle.Implementation of the Edge Recombination operator, a crossover operator for permutations.Implementation of the Enhanced Edge Recombination operator, a crossover operator for permutations.This class implements an insertion mutation on permutations, where one mutation consists in removing a randomly chosen element and reinserting it at a different randomly chosen location.Implementation of non-wrapping order crossover (NWOX).Implementation of order crossover (OX).Implementation of the crossover operator for permutations that is often referred to as Order Crossover 2 (OX2).Implementation of partially matched crossover (PMX).The PermutationInitializer provides metaheuristic implementations, such as of simulated annealing, etc, with a way to generate random initial solutions to a problem, as well as a way to make copies of current solution configurations.Implementation of position based crossover (PBX).Implementation of Precedence Preservative Crossover (PPX), the two-point version.This class implements a reversal mutation on permutations, where one mutation consists in reversing the order of a randomly selected subpermutation.This class implements a rotation mutation on permutations, where one mutation consists in a random circular rotation of the permutation.This class implements a scramble mutation on permutations, where one mutation consists in randomizing the order of a randomly selected subpermutation.This class implements a swap mutation on permutations, where one mutation selects two elements uniformly at random and swaps their locations.This class implements the classic 3-Opt neighborhood as a mutation operator for permutations.This class implements the classic two-change operator as a mutation operator for permutations.This class implements a scramble mutation on permutations, where one mutation consists in randomizing the order of a randomly selected subpermutation.This class implements a scramble mutation on permutations, where one mutation consists in randomizing the order of a non-contiguous subset of the permutation elements.Implementation of uniform order-based crossover (UOBX).Implementation of uniform partially matched crossover (UPMX).Implementation of Precedence Preservative Crossover (PPX), the uniform version.This class implements a scramble mutation on permutations, where one mutation consists in randomizing the order of a non-contiguous subset of the permutation elements.This class implements a window-limited version of the
BlockMoveMutationmutation operator on permutations.This class implements a window-limited version of theInsertionMutationmutation operator on permutations.This class implements a window-limited version of theReversalMutationmutation operator on permutations.This class implements a window-limited version of theScrambleMutationmutation operator on permutations.This class implements a window-limited version of theSwapMutationmutation operator on permutations.This class implements a window-limited version of theScrambleMutationmutation operator on permutations.