人工免疫算法解决tsp问题代码

以下是使用人工免疫算法解决TSP问题的Python代码：

import random
import numpy as np

# 定义TSP问题的类
class TSP:
    def __init__(self, city_num, coords):
        self.city_num = city_num
        self.coords = coords
        self.dist_mat = self.get_dist_mat()

    # 计算两个城市之间的距离
    def get_distance(self, coord1, coord2):
        distance = np.sqrt(np.sum(np.square(coord1 - coord2)))
        return distance

    # 获取城市之间的距离矩阵
    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 = self.get_distance(self.coords[i], self.coords[j])
                dist_mat[i][j] = dist
                dist_mat[j][i] = dist
        return dist_mat

# 定义免疫算法的类
class AIS:
    def __init__(self, tsp, pop_size=50, num_mutations=2, num_clones=5, clone_factor=0.5):
        self.tsp = tsp
        self.pop_size = pop_size
        self.num_mutations = num_mutations
        self.num_clones = num_clones
        self.clone_factor = clone_factor
        self.antibodies = self.init_antibodies()

    # 初始化抗体
    def init_antibodies(self):
        antibodies = []
        for i in range(self.pop_size):
            antibody = list(range(self.tsp.city_num))
            random.shuffle(antibody)
            antibodies.append(antibody)
        return antibodies

    # 计算路径长度
    def calc_path_len(self, path):
        path_len = 0
        for i in range(self.tsp.city_num-1):
            path_len += self.tsp.dist_mat[path[i]][path[i+1]]
        path_len += self.tsp.dist_mat[path[-1]][path[0]]
        return path_len

    # 选择克隆
    def select_clones(self):
        # 排序
        self.antibodies = sorted(self.antibodies, key=lambda x: self.calc_path_len(x))
        # 选择克隆
        clones = []
        for i in range(self.num_clones):
            for j in range(int(self.clone_factor*(self.pop_size-i))):
                clones.append(self.antibodies[i])
        return clones

    # 变异
    def mutate(self, antibody):
        for i in range(self.num_mutations):
            idx1, idx2 = random.sample(range(self.tsp.city_num), 2)
            antibody[idx1], antibody[idx2] = antibody[idx2], antibody[idx1]
        return antibody

    # 免疫算法主函数
    def immune_algo(self, max_iter=100):
        best_path = None
        best_len = np.inf
        for i in range(max_iter):
            # 克隆
            clones = self.select_clones()
            # 变异
            for j in range(len(clones)):
                clones[j] = self.mutate(clones[j])
            # 选择
            clones = sorted(clones, key=lambda x: self.calc_path_len(x))
            self.antibodies = clones[:self.pop_size]
            # 更新最优解
            if self.calc_path_len(self.antibodies[0]) < best_len:
                best_path = self.antibodies[0]
                best_len = self.calc_path_len(self.antibodies[0])
        return best_path, best_len

# 测试
coords = np.array([[60, 200], [180, 200], [80, 180], [140, 180], [20, 160], [100, 160], [200, 160], [140, 140], [40, 120], [100, 120], [180, 100], [60, 80], [120, 80], [180, 60], [20, 40], [100, 40], [200, 40], [20, 20], [60, 20], [160, 20]])
tsp = TSP(city_num=len(coords), coords=coords)
ais = AIS(tsp=tsp, pop_size=50, num_mutations=2, num_clones=5, clone_factor=0.5)
best_path, best_len = ais.immune_algo(max_iter=100)
print("最优路径：", best_path)
print("最优路径长度：", best_len)

该代码采用了人工免疫算法求解TSP问题。主要思路是将路径表示为一个城市序列，抗体表示为一个路径序列。在算法的每一次迭代中，选择一部分抗体进行克隆操作，然后对克隆体进行变异。通过不断迭代，逐渐优化抗体的适应度，最终得到一个最优的路径。