基于python语言的matlab遗传算法旅行商问题

以下是基于Python语言的遗传算法解决旅行商问题的示例代码：

import numpy as np
import matplotlib.pyplot as plt

# 旅行商问题类
class TSP:
    def __init__(self, city_num, pop_size, pc, pm, max_gen):
        self.city_num = city_num  # 城市数量
        self.pop_size = pop_size  # 种群大小
        self.pc = pc  # 交叉概率
        self.pm = pm  # 变异概率
        self.max_gen = max_gen  # 最大迭代次数
        self.city_pos = np.random.rand(city_num, 2)  # 城市坐标
        self.dist_mat = self.get_dist_mat()  # 距离矩阵
        self.pop = np.zeros((pop_size, city_num), dtype=int)  # 种群
        self.fitness = np.zeros(pop_size)  # 适应度
        self.best_path = np.zeros(city_num, dtype=int)  # 最优路径
        self.best_dist = np.inf  # 最优距离

    # 计算距离矩阵
    def get_dist_mat(self):
        dist_mat = np.zeros((self.city_num, self.city_num))
        for i in range(self.city_num):
            for j in range(i + 1, self.city_num):
                dist_mat[i][j] = np.sqrt(np.sum(np.square(self.city_pos[i] - self.city_pos[j])))
                dist_mat[j][i] = dist_mat[i][j]
        return dist_mat

    # 初始化种群
    def init_pop(self):
        for i in range(self.pop_size):
            self.pop[i] = np.random.permutation(self.city_num)

    # 计算适应度
    def calc_fitness(self):
        for i in range(self.pop_size):
            dist = 0
            for j in range(self.city_num - 1):
                dist += self.dist_mat[self.pop[i][j]][self.pop[i][j + 1]]
            dist += self.dist_mat[self.pop[i][-1]][self.pop[i][0]]
            self.fitness[i] = 1 / dist

    # 选择操作
    def selection(self):
        idx = np.random.choice(self.pop_size, size=self.pop_size, replace=True, p=self.fitness / np.sum(self.fitness))
        self.pop = self.pop[idx]

    # 交叉操作
    def crossover(self):
        for i in range(0, self.pop_size, 2):
            if np.random.rand() < self.pc:
                j, k = np.random.choice(self.city_num, size=2, replace=False)
                if j > k:
                    j, k = k, j
                temp1 = np.zeros(self.city_num, dtype=int)
                temp2 = np.zeros(self.city_num, dtype=int)
                temp1[j:k] = self.pop[i + 1][j:k]
                temp2[j:k] = self.pop[i][j:k]
                idx1 = 0
                idx2 = 0
                for m in range(self.city_num):
                    if self.pop[i][m] not in temp1[j:k]:
                        temp1[idx1] = self.pop[i][m]
                        idx1 += 1
                    if self.pop[i + 1][m] not in temp2[j:k]:
                        temp2[idx2] = self.pop[i + 1][m]
                        idx2 += 1
                self.pop[i] = temp1
                self.pop[i + 1] = temp2

    # 变异操作
    def mutation(self):
        for i in range(self.pop_size):
            if np.random.rand() < self.pm:
                j, k = np.random.choice(self.city_num, size=2, replace=False)
                self.pop[i][j], self.pop[i][k] = self.pop[i][k], self.pop[i][j]

    # 获取最优解
    def get_best_path(self):
        for i in range(self.pop_size):
            dist = 0
            for j in range(self.city_num - 1):
                dist += self.dist_mat[self.pop[i][j]][self.pop[i][j + 1]]
            dist += self.dist_mat[self.pop[i][-1]][self.pop[i][0]]
            if dist < self.best_dist:
                self.best_path = self.pop[i]
                self.best_dist = dist

    # 迭代
    def evolve(self):
        self.init_pop()
        self.calc_fitness()
        self.get_best_path()
        for i in range(self.max_gen):
            self.selection()
            self.crossover()
            self.mutation()
            self.calc_fitness()
            self.get_best_path()

    # 绘制城市分布图和最优路径图
    def plot(self):
        plt.figure(figsize=(10, 5))
        plt.subplot(121)
        plt.scatter(self.city_pos[:, 0], self.city_pos[:, 1])
        plt.title('City Distribution')
        plt.subplot(122)
        plt.plot(self.city_pos[self.best_path][:, 0], self.city_pos[self.best_path][:, 1], '-o')
        plt.title('Best Path')
        plt.show()

# 示例
tsp = TSP(city_num=20, pop_size=100, pc=0.8, pm=0.1, max_gen=500)
tsp.evolve()
tsp.plot()