如何使用 pyGAD 包解决 TSP 问题？

Question

使用PyGAD Package，如何生成元素在1到12之间不重复的种群项？ 它在随机种群中总是具有重复值。 我不知道如何避免这种情况。 或者，我应该在生成新人口时在回调函数中操作吗？

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**

非常感谢任何帮助！

Answer 1

更新

PyGAD 2.13.0 发布，支持名为 allow_duplicate_genes 的新 bool 参数。如果设置为False，则解决方案中将不存在重复基因。在这里阅读更多：https://pygad.readthedocs.io/en/latest/README_pygad_ReadTheDocs.html#prevent-duplicates-in-gene-values

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

感谢使用 PyGAD :)

PyGAD 尚不支持拒绝解决方案中重复基因的功能。因此，您可能会期望重复值。

这是下一个 PyGAD 版本 (2.13.0) 中支持的非常好的功能。感谢您提出这个问题。

在下一个版本之前，您可以构建自己的变异函数来拒绝重复值。只需按照以下步骤操作：

1. 通过将 pygad.GA class 的构造函数中的 mutation_type 参数设置为 None:
来禁用突变

mutation_type=None

2. 建立你自己的变异操作，应用变异而不重复：

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

3. 实现on_crossover()回调函数。交叉操作完成后直接调用该函数。在那里，您获取交叉后构建的数组 [作为参数自动传递给回调函数]，应用您自己的变异，并将结果保存回 PyGAD 使用。

您可以查看 Life Cycle of PyGAD 了解有关回调函数的更多信息。

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. 将交叉回调函数分配给 pygad.GA class:
的构造函数中的 on_crossover 参数

on_crossover=on_crossover

就是这样。

Answer 2

避免重复基因。我认为TSP问题应该使用自定义变异方法和自定义交叉方法（例如CX方法）。

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)