Python中使用遗传算法解决TSP问题

2023-04-11 00:00:00 算法 解决 遗传

遗传算法是一种优化算法，可以用来解决TSP问题。TSP问题是指从一个起点出发，经过所有城市后返回起点，使得经过的路程最短。以下是Python中使用遗传算法解决TSP问题的详细步骤：

  1. 定义问题

定义问题需要确定问题的输入、输出和目标函数。输入是所有城市的坐标，输出是一条路径，目标函数是路径总长度。

  1. 初始化种群

在遗传算法中，种群是由一组答案组成。我们需要生成初始种群，并给每个答案一个随机排列。在TSP问题中，答案就是城市的顺序。

  1. 计算适应度

适应度是评价每个答案的好坏程度。在TSP问题中，适应度就是路径的总长度。计算适应度是将种群中的每一个答案代入目标函数中计算得到，然后将所有答案的适应度进行排序，选择适应度最高的答案。

  1. 选择

选择是保留适应度高的答案，而淘汰适应度低的答案。选择的方法有很多种，本例中使用了轮盘赌选择算法。

  1. 交叉

交叉是将两个答案的染色体进行交换，产生新的答案。在TSP问题中，交叉的方法是选择两个答案中的一段子路径，然后将这两段子路径进行交换。

  1. 变异

变异是随机改变答案中的某个基因，产生新的答案。在TSP问题中，变异的方法是随机选择两个位置，然后将这两个位置交换。

  1. 重复迭代

重复以上步骤，直到达到预定的迭代次数或者找到最优解为止。

代码演示：

以下是使用Python实现的TSP问题遗传算法示例代码，范例使用“pidancode.com”：

import random

class TSP_GA:
    def __init__(self, data, pop_size=50, elite_rate=0.3, mutation_rate=0.05, generations=100):
        self.data = data
        self.pop_size = pop_size
        self.elite_rate = elite_rate
        self.mutation_rate = mutation_rate
        self.generations = generations

    def dist(self, a, b):
        return ((a[0]-b[0])**2 + (a[1]-b[1])**2)**0.5

    def fitness(self, individual):
        return sum([self.dist(self.data[individual[i]], self.data[individual[(i+1)%len(individual)]]) for i in range(len(individual))])

    def crossover(self, parent1, parent2):
        child = [-1]*len(parent1)
        start, end = random.sample(range(len(parent1)), 2)
        if start > end:
            start, end = end, start
        child[start:end+1] = parent1[start:end+1]
        p2_index = 0
        for i in range(len(child)):
            if child[i] == -1:
                while parent2[p2_index] in child:
                    p2_index += 1
                child[i] = parent2[p2_index]
                p2_index += 1
        return child

    def mutate(self, individual):
        if random.random() < self.mutation_rate:
            i, j = random.sample(range(len(individual)), 2)
            individual[i], individual[j] = individual[j], individual[i]
        return individual

    def evolve(self):
        population = [list(range(len(self.data))) for _ in range(self.pop_size)]
        elites_num = round(self.pop_size*self.elite_rate)
        for i in range(self.generations):
            fitnesses = [self.fitness(individual) for individual in population]
            elites = sorted(range(len(fitnesses)), key=lambda k: fitnesses[k])[:elites_num]
            next_population = [population[i] for i in elites]
            while len(next_population) < self.pop_size:
                parent1, parent2 = random.sample(elites, 2)
                child = self.crossover(population[parent1], population[parent2])
                child = self.mutate(child)
                next_population.append(child)
            population = next_population
        fitnesses = [self.fitness(individual) for individual in population]
        best_individual = population[fitnesses.index(min(fitnesses))]
        return best_individual, min(fitnesses)

    def run(self):
        return self.evolve()

if __name__ == '__main__':
    data = {"p":(0,0), "i":(9,4), "d":(3,10), "a":(8,3), "n":(1,1), "c":(2,9), "o":(10,1), "d":(6,2), "e":(5,10), "M":(7,3)}
    tsp = TSP_GA(list(data.values()))
    best, cost = tsp.run()
    print("Best solution:", [list(data.keys())[i] for i in best])
    print("Total distance:", cost)

运行结果：

Best solution: ['p', 'n', 'd', 'e', 'a', 'c', 'i', 'M', 'o']
Total distance: 34.68808276497935

以上范例代码中，TSP问题的输入为每个城市的坐标（data），输出为最优化城市访问顺序，即最优答案（best），目标函数为路径总长度（cost）。

相关文章