python人工免疫算法tsp

Python人工免疫算法（Artificial Immune Algorithm，简称AIA）是一种基于免疫系统原理的优化算法，用于解决各种优化问题，其中包括旅行商问题（Traveling Salesman Problem，简称TSP）。

TSP是一个经典的组合优化问题，目标是找到一条最短路径，使得旅行商能够访问所有城市并回到起始城市。Python人工免疫算法可以用于求解TSP问题的近似最优解。

在Python中实现TSP问题的人工免疫算法，可以按照以下步骤进行：

1. 初始化免疫群体：随机生成一组初始解，每个解表示一条路径。
2. 计算适应度：根据路径长度计算每个解的适应度，适应度越小表示路径越短。
3. 免疫选择：根据适应度选择一部分优秀的解作为免疫群体。
4. 免疫克隆：对选中的优秀解进行克隆操作，生成一定数量的克隆解。
5. 免疫变异：对克隆解进行变异操作，引入一定的随机性。
6. 更新适应度：计算克隆解的适应度。
7. 免疫选择：根据适应度选择一部分优秀的克隆解作为下一代免疫群体。
8. 终止条件判断：如果满足终止条件（例如达到最大迭代次数或找到满意的解），则结束算法；否则，返回步骤4继续迭代。

通过不断迭代，Python人工免疫算法可以逐步优化路径，寻找到近似最优解。

相关问题

人工免疫算法求解TSP，写一段python代码

好的，以下是一个简单的人工免疫算法求解TSP的Python代码实现：

import random
import math

# 定义TSP问题的距离矩阵
distance_matrix = [
    [0, 2, 9, 10],
    [1, 0, 6, 4],
    [15, 7, 0, 8],
    [6, 3, 12, 0]
]

# 定义参数
N = 10  # 种群规模
G = 100  # 迭代次数
beta = 2  # 信度水平
p = 0.1  # 免疫率
d = 0.9  # 丧失率

# 初始化种群
population = []
for i in range(N):
    chromosome = list(range(len(distance_matrix)))
    random.shuffle(chromosome)
    population.append(chromosome)

# 计算每个个体的适应度值
def evaluate(chromosome):
    distance = 0
    for i in range(len(chromosome)-1):
        distance += distance_matrix[chromosome[i]][chromosome[i+1]]
    distance += distance_matrix[chromosome[-1]][chromosome[0]]
    return 1 / distance

# 进行GA操作，包括选择、交叉、变异
def genetic_algorithm(population):
    # 选择
    population = sorted(population, key=lambda x: evaluate(x), reverse=True)
    elite = population[0]
    parents = population[:int(N/2)]

    # 交叉
    children = []
    for i in range(int(N/2)):
        parent1 = random.choice(parents)
        parent2 = random.choice(parents)
        child1, child2 = order_crossover(parent1, parent2)
        children += [child1, child2]

    # 变异
    for i in range(N):
        if random.random() < p:
            children[i] = inversion_mutation(children[i])

    # 合并父代、子代，选择前N个
    population = parents + children
    population = sorted(population, key=lambda x: evaluate(x), reverse=True)
    return population[:N]

# 顺序交叉
def order_crossover(parent1, parent2):
    child1, child2 = [-1]*len(parent1), [-1]*len(parent2)
    left, right = sorted([random.randrange(len(parent1)) for _ in range(2)])
    for i in range(left, right+1):
        child1[i] = parent1[i]
        child2[i] = parent2[i]
    idx1, idx2 = right+1, right+1
    while -1 in child1:
        if parent2[idx1%len(parent2)] not in child1:
            child1[idx1%len(parent2)] = parent2[idx1%len(parent2)]
        idx1 += 1
    while -1 in child2:
        if parent1[idx2%len(parent1)] not in child2:
            child2[idx2%len(parent1)] = parent1[idx2%len(parent1)]
        idx2 += 1
    return child1, child2

# 反转变异
def inversion_mutation(chromosome):
    left, right = sorted([random.randrange(len(chromosome)) for _ in range(2)])
    return chromosome[:left] + chromosome[left:right+1][::-1] + chromosome[right+1:]

# 初始化抗体群
antibodies = []
for i in range(N):
    chromosome = list(range(len(distance_matrix)))
    random.shuffle(chromosome)
    antibodies.append(chromosome)

# 进行人工免疫算法操作
for g in range(G):
    # 计算每个抗体的亲和度
    affinities = [evaluate(antibody) for antibody in antibodies]

    # 选择免疫记忆库中的抗体
    selected_antibodies = []
    for i in range(N):
        if random.random() < d:
            selected_antibodies.append(population[i])
        else:
            selected_antibodies.append(antibodies[i])

    # 交叉变异
    for i in range(N):
        parent1 = random.choice(selected_antibodies)
        parent2 = random.choice(selected_antibodies)
        child = order_crossover(parent1, parent2)[0]
        if random.random() < p:
            child = inversion_mutation(child)
        antibodies[i] = child

    # 更新免疫记忆库
    population = genetic_algorithm(population + antibodies)

# 输出最优解
print("最优解：", population[0])
print("最优解的距离：", 1/evaluate(population[0]))

这段代码实现了一个简单的人工免疫算法，其中包括了遗传算法操作和抗体操作，用于求解TSP问题。在代码中，我们首先定义了TSP问题的距离矩阵，然后初始化了种群和抗体群。在每次迭代中，我们计算了每个抗体的适应度值，并选择了免疫记忆库中的抗体进行交叉变异操作。最后，我们用遗传算法对免疫记忆库进行更新，并输出最优解。

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