Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature Req: Cycle mutation for permutations #231

Closed
cicirello opened this issue Mar 23, 2021 · 1 comment · Fixed by #246
Closed

Feature Req: Cycle mutation for permutations #231

cicirello opened this issue Mar 23, 2021 · 1 comment · Fixed by #246
Labels
enhancement New feature or request

Comments

@cicirello
Copy link
Owner

Describe the solution you'd like
A mutation operator for permutations that creates a random permutation cycle within the permutation. The idea is similar to cycle crossover, but instead of operating on a pair of permutations, the proposed mutation operator will operate on a single permutation to replace a set of elements chosen randomly with a cycle of those elements. Ideally, it will be configurable with a parameter specifying the probability of including an element in the cycle, similar to the parameter for a uniform crossover operator for bitstrings.

Describe alternatives you've considered
The library has a SwapMutation. Swap creates a special type of cycle of length 2. The library also has an InsertionMutation, which randomly removes an element, and reinserts it into a different randomly chosen position. Insertion mutation is a more specific type of cycle, where all of the elements of the cycle are in sequence. The requested cycle mutation is more general than both of these, specifically, select a set of elements (not necessarily in sequence) at random, and then form a permutation cycle of those.

@cicirello cicirello added the enhancement New feature or request label Mar 23, 2021
@cicirello
Copy link
Owner Author

After thinking better about it, instead of "a parameter specifying the probability of including an element in the cycle", have a parameter to specify max cycle size, such that the mutation creates a random cycle from a number of elements that is random in [2, max]. In this way, each call to mutate will be guaranteed to change the permutation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant