Warm tip: This article is reproduced from serverfault.com, please click

python-如何使用pyGAD包解决TSP问题?

(python - How to solve TSP problem using pyGAD package?)

发布于 2021-02-21 02:32:41

使用PyGAD包,如何生成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**


任何帮助将不胜感激!

Questioner
lokcyi
Viewed
11
Ahmed Gad 2021-03-13 10:23:20

更新

PyGAD 2.13.0 发布,它支持一个名为allow_duplicate_genes. 如果设置为False,则解决方案中将不存在重复的基因。在此处阅读更多信息:https : //pygad.readthedocs.io/en/latest/README_pygad_ReadTheDocs.html#prevent-duplicates-in-gene-values

……………………………………………………………………………………………………………………………………………………………………………………

感谢你使用PyGAD :)

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

这是 PyGAD 的下一个版本(2.13.0)支持的一个很好的特性。感谢你提出这个问题。

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

  1. 通过mutation_typepygad.GA的构造函数中设置参数来禁用突变None
mutation_type=None
  1. 构建你自己的变异操作,应用没有重复的变异:
def mut(...):
   result = ....
   return result 
  1. 实现on_crossover()回调函数。交叉操作完成后直接调用该函数。在那里,你在交叉后获取数组构建 [它作为参数自动传递给回调函数],应用你自己的更改,并将结果保存回以供 PyGAD 使用。

你可以查看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.
  1. 将你的交叉回调函数分配给on_crossoverpygad.GA 类的构造函数中的参数:
on_crossover=on_crossover

就这些。