With `allow_duplicate_genes=False`, the random mutation never changes a permutation

[tachsin]

Version: PyGAD 3.7.0 (same code on master)

I found this while benchmarking PyGAD on permutation problems. With allow_duplicate_genes=False and a gene space of num_genes values, the setup that pygad.benchmarks.tsp.TSP and examples/benchmarks/example_tsp.py use for permutations, the default random mutation never changes a solution.

The new value of a mutated gene comes from select_unique_value() (pygad/helper/unique.py L269-L280): a value of the gene space that no gene uses yet. In a permutation, every value is used, so the gene keeps its value:

values_to_select_from = list(set(list(gene_values)) - set(solution))

if len(values_to_select_from) == 0:
    ...
    else:
        # If the gene is not None, then just keep its current value as long as there are no values that make it unique.
        selected_value = solution[gene_index]

Reproduction

import numpy
import pygad

num_genes = 8
# The permutation setup of pygad.benchmarks.tsp and examples/benchmarks/example_tsp.py
ga = pygad.GA(num_generations=1, num_parents_mating=2, sol_per_pop=4, num_genes=num_genes,
              fitness_func=lambda ga, solution, idx: 0.0,
              gene_space=list(range(num_genes)), gene_type=int, allow_duplicate_genes=False,
              random_seed=1, suppress_warnings=True)
offspring = numpy.array([numpy.random.permutation(num_genes) for _ in range(1000)])
mutated = ga.random_mutation(offspring.copy())
print("changed:", numpy.any(mutated != offspring, axis=1).sum(), "of 1000")

Expected: most permutations change, as mutation is the only source of new tours once the population converges.

Actual: changed: 0 of 1000. The same happens with mutation_probability, a nested gene space and adaptive mutation. The example's GA then only recombines its initial tours: on 12 cities on a circle (the example's settings, 200 generations, seeds 0 to 2), it ends with tours of length 11.7, 12.5 and 9.6; the optimum is 6.2.

Suggested fix: when the mutation can't find a free value (the value it picks equals the gene's value), swap the gene with another gene instead: one whose value is in this gene's space and whose space holds this gene's value. The swap keeps the genes unique, and a swap is the usual mutation for permutations. On the example above, all 1000 permutations change and stay permutations, and the 3 TSP runs reach 6.2. I'll open a pull request with this change and tests.