遗传算法解决旅行商问题python代码

遗传算法是一种基于生物进化思想的优化算法，可以应用于求解旅行商问题。下面是使用Python实现遗传算法求解旅行商问题的代码示例：

import numpy as np
import random

# 定义旅行商问题类
class TSP():
    def __init__(self, city_num, city_position):
        self.city_num = city_num # 城市数量
        self.city_position = city_position # 城市位置
        self.distance = self.calc_distance() # 城市间距离矩阵
    
    # 计算城市间距离矩阵
    def calc_distance(self):
        distance = np.zeros((self.city_num, self.city_num))
        for i in range(self.city_num):
            for j in range(i+1, self.city_num):
                distance[i][j] = np.sqrt((self.city_position[i]-self.city_position[j])**2 + (self.city_position[i]-self.city_position[j])**2)
                distance[j][i] = distance[i][j]
        return distance
    
    # 计算路径长度
    def calc_path_length(self, path):
        length = 0
        for i in range(self.city_num-1):
            length += self.distance[path[i]][path[i+1]]
        length += self.distance[path[self.city_num-1]][path]
        return length
    
    # 随机生成初始种群
    def generate_population(self, pop_size):
        population = []
        for i in range(pop_size):
            path = list(range(self.city_num))
            random.shuffle(path)
            population.append(path)
        return population
    
    # 选择
    def selection(self, population, fitness):
        idx1 = random.randint(0, len(population)-1)
        idx2 = random.randint(0, len(population)-1)
        if fitness[idx1] < fitness[idx2]:
            return population[idx1]
        else:
            return population[idx2]
    
    # 交叉
    def crossover(self, parent1, parent2):
        child = [-1]*self.city_num
        start_idx = random.randint(0, self.city_num-1)
        end_idx = random.randint(0, self.city_num-1)
        if start_idx > end_idx:
            start_idx, end_idx = end_idx, start_idx
        for i in range(start_idx, end_idx+1):
            child[i] = parent1[i]
        idx = end_idx+1
        for i in range(self.city_num):
            if idx == self.city_num:
                idx = 0
            if parent2[i] not in child:
                child[idx] = parent2[i]
                idx += 1
        return child
    
    # 变异
    def mutation(self, path):
        idx1 = random.randint(0, self.city_num-1)
        idx2 = random.randint(0, self.city_num-1)
        path[idx1], path[idx2] = path[idx2], path[idx1]
    
    # 遗传算法求解旅行商问题
    def GA_solve(self, pop_size, elite_rate=0.2, crossover_rate=0.8, mutation_rate=0.05, max_iter=100):
        population = self.generate_population(pop_size)
        fitness = [self.calc_path_length(path) for path in population]
        best_fitness = min(fitness)
        best_path = population[fitness.index(best_fitness)]
        elite_size = int(pop_size*elite_rate)
        for iter in range(max_iter):
            # 选择精英种群
            elite_population = []
            elite_fitness = []
            elite_index = np.argsort(fitness)[:elite_size]
            for idx in elite_index:
                elite_population.append(population[idx])
                elite_fitness.append(fitness[idx])
            # 生成新种群
            new_population = []
            new_population.extend(elite_population)
            while len(new_population) < pop_size:
                parent1 = self.selection(population, fitness)
                if random.random() < crossover_rate:
                    parent2 = self.selection(population, fitness)
                    child = self.crossover(parent1, parent2)
                else:
                    child = parent1[:]
                if random.random() < mutation_rate:
                    self.mutation(child)
                new_population.append(child)
            # 计算新种群适应度
            new_fitness = [self.calc_path_length(path) for path in new_population]
            # 更新最优解
            if min(new_fitness) < best_fitness:
                best_fitness = min(new_fitness)
                best_path = new_population[new_fitness.index(best_fitness)]
            # 替换种群
            fitness.extend(new_fitness)
            population.extend(new_population)
            idxs = np.argsort(fitness)[:pop_size]
            population = [population[idx] for idx in idxs]
            fitness = [fitness[idx] for idx in idxs]
        return best_path, best_fitness

# 测试代码
if __name__ == '__main__':
    city_num = 10 # 城市数量
    city_position = np.random.rand(city_num, 2) # 城市位置随机生成
    tsp = TSP(city_num, city_position)
    best_path, best_fitness = tsp.GA_solve(pop_size=100, max_iter=500)
    print("最优路径：", best_path)
    print("最优解：", best_fitness)