How to solve TSP problem using pyGAD package?

Question

Using PyGAD Package, how to generate the item of populations with element not duplicate between 1 and 12? It is always has duplicate value in random population. I have no ideal how to avoid that. Or, should I manipulate in callback function when generate new population?

import pandas as pd
import numpy as np
import pygad
xs = [8, 50, 18, 35, 90, 40, 84, 74, 34, 40, 60, 74]
ys = [3, 62, 0, 25, 89, 71, 7, 29, 45, 65, 69, 47]
cities = ['Z', 'P', 'A', 'K', 'O', 'Y', 'N', 'X', 'G', 'Q', 'S', 'J']
locations = list(zip(xs, ys, cities))

def fitness_func(solution, solution_idx):
    # Calculating the fitness value of each solution in the current population.
    # The fitness function calulates the sum of products between each input and its corresponding weight.
    # output = numpy.sum(solution*function_inputs)
    # fitness = 1.0 / numpy.abs(output - desired_output)
    
    total_length = 0
    itemidx=0
    
    for loc in solution:
        if itemidx>0 :
            cityidx1 = loc-1
            cityidx2 =solution[itemidx-1]-1   
            total_length +=((xs[cityidx1] - xs[cityidx2]) ** 2 + (ys[cityidx1] - ys[cityidx2]) ** 2) ** (1 / 2)  
            # print(xs[cityidx1],ys[cityidx1], xs[cityidx1], ys[cityidx2],total_length )
        elif  itemidx==solution.size :
            cityidx1 = loc-1
            cityidx2 =solution[itemidx-1]-1 
            total_length +=((xs[cityidx1] - xs[cityidx2]) ** 2 + (ys[cityidx1] - ys[cityidx2]) ** 2) ** (1 / 2)  
            if ((xs[cityidx1] - xs[cityidx2]) ** 2 + (ys[cityidx1] - ys[cityidx2]) ** 2) ** (1 / 2)  <0:
                print('ERROR',((xs[cityidx1] - xs[cityidx2]) ** 2 + (ys[cityidx1] - ys[cityidx2]) ** 2) ** (1 / 2)  )
            # print(xs[cityidx1],ys[cityidx1], xs[cityidx1], ys[cityidx2],total_length )
            
            cityidx2 =solution[0] 
            total_length +=((xs[itemidx] - xs[0]) ** 2 + (ys[itemidx] - ys[0]) ** 2) ** (1 / 2) 
            # print(total_length)
        itemidx += 1
    #print("fitness_func",total_length,solution,solution_idx)    
    return total_length*-1 #fitness

fitness_function = fitness_func
num_generations = 50 # Number of generations.
num_parents_mating = 7 # Number of solutions to be selected as parents in the mating pool.
sol_per_pop = 50 # Number of solutions in the population.
num_genes = 12  

init_range_low = 1
init_range_high = 12

parent_selection_type = "rank" # Type of parent selection.
keep_parents = 7 # Number of parents to keep in the next population. -1 means keep all parents and 0 means keep nothing.

crossover_type = "single_point" # Type of the crossover operator.

# Parameters of the mutation operation.
mutation_type = "swap" # Type of the mutation operator.
mutation_percent_genes = 10 

last_fitness = 0
population_list=[]
gene_space = [i for i in range(1, 13)]
for i in range(sol_per_pop):
    nxm_random_num=list(np.random.permutation(gene_space)) 
    population_list.append(nxm_random_num) # add to the population_list
ga_instance = pygad.GA(num_generations=num_generations,
                       num_parents_mating=num_parents_mating, 
                       fitness_func=fitness_function,
                       sol_per_pop=sol_per_pop, 
                       initial_population=population_list,
                       num_genes=num_genes,

                       gene_space = gene_space, #  
                    #    init_range_low=init_range_low,
                    #    init_range_high=init_range_high,

                       parent_selection_type=parent_selection_type,
                       keep_parents=keep_parents,
                       crossover_type=crossover_type,
                       mutation_type=mutation_type,
                       mutation_percent_genes=mutation_percent_genes
                       )
ga_instance.run()
solution, solution_fitness, solution_idx = ga_instance.best_solution()
print("best_solution: {solution}".format(solution =solution)) 

#best_solution: [ 3  4 12 10  6  9  2 10 12 10  6  9] 
#**Is any way to get new gerneration that elements not duplication**

Any help would be highly appreciated!

Answer 1

Update

PyGAD 2.13.0 is released which supports a new bool parameter called allow_duplicate_genes. If set to False, then no duplicate genes will exist in the solution. Read more here: https://pygad.readthedocs.io/en/latest/README_pygad_ReadTheDocs.html#prevent-duplicates-in-gene-values

.........................................

Thanks for using PyGAD :)

The feature of rejecting duplicate genes in a solution is not yet supported in PyGAD. So, you may expect duplicate values.

This is a very good feature to support in the next release of PyGAD (2.13.0). Thanks for asking this question.

Until the next release, you can build your own mutation function to reject duplicate values. Just follow these steps:

1. Disable the mutation by setting the mutation_type argument in the constructor of the pygad.GA class to None:

mutation_type=None

2. Build your own mutation operation that applies mutation without duplicates:

def mut(...):
   result = ....
   return result 

3. Implement the on_crossover() callback function. This function is called directly after the crossover operation is complete. There, you fetch the array build after crossover [which is passed as an argument automatically to the callback function], apply your own mutation, and save the result back to be used by PyGAD.

You can check the Life Cycle of PyGAD for more information about the callback functions.

def on_crossover(ga_instance, offspring_crossover):
    # 1) Apply your mutation on the solutions in the offspring_crossover array.
    # Assume the mutation offspring is saved in the offspring_mutation array.
    offspring_mutation  = mut(offspring_crossover)

    2) Save the result in the last_generation_offspring_mutation attribute of ga_instance:
    ga_instance.last_generation_offspring_mutation = offspring_mutation

    # The previous links makes the next population to use your mutation offspring.

4. Assign your crossover callback function to the on_crossover argument in the constructor of the pygad.GA class:

on_crossover=on_crossover

That is all.

Answer 2

To avoid duplicate genes. I think the TSP problem should use a custom mutation method and a custom crossover method(for example, the CX method).

FYI:

a genetic algorithm solving the traveling salesman problem may use an ordered list of cities to represent a solution path. Such a chromosome only represents a valid solution if the list contains all the cities that the salesman must visit. Using the above crossovers will often result in chromosomes that violate that constraint. Genetic algorithms optimizing the ordering of a given list thus require different crossover operators that will avoid generating invalid solutions. Many such crossovers have been published:

partially mapped crossover (PMX)
cycle crossover (CX)
order crossover operator (OX1)
order-based crossover operator (OX2)
position-based crossover operator (POS)
voting recombination crossover operator (VR)
alternating-position crossover operator (AP)
sequential constructive crossover operator (SCX)
simulated binary crossover operator (SBX)