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

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

import random

# TSP问题的数据，这里使用Berlin52的数据
cityList = [(565.0, 575.0), (25.0, 185.0), (345.0, 750.0), (945.0, 685.0), (845.0, 655.0), (880.0, 660.0), (25.0, 230.0), (525.0, 1000.0), (580.0, 1175.0), (650.0, 1130.0), (1605.0, 620.0), (1220.0, 580.0), (1465.0, 200.0), (1530.0, 5.0), (845.0, 680.0), (725.0, 370.0), (145.0, 665.0), (415.0, 635.0), (510.0, 875.0), (560.0, 365.0), (300.0, 465.0), (520.0, 585.0), (480.0, 415.0), (835.0, 625.0), (975.0, 580.0), (1215.0, 245.0), (1320.0, 315.0), (1250.0, 400.0), (660.0, 180.0), (410.0, 250.0), (420.0, 555.0), (575.0, 665.0), (1150.0, 1160.0), (700.0, 580.0), (685.0, 595.0), (685.0, 610.0), (770.0, 610.0), (795.0, 645.0), (720.0, 635.0), (760.0, 650.0), (475.0, 960.0), (95.0, 260.0), (875.0, 920.0), (700.0, 500.0), (555.0, 815.0), (830.0, 485.0), (1170.0, 65.0), (830.0, 610.0), (605.0, 625.0), (595.0, 360.0), (1340.0, 725.0), (1740.0, 245.0)]

# 计算两个城市之间的距离
def distance(city1, city2):
    return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5

# 计算路径的总长度
def pathLength(path):
    length = 0
    for i in range(len(path) - 1):
        length += distance(cityList[path[i]], cityList[path[i+1]])
    length += distance(cityList[path[-1]], cityList[0]) # 加上回到起点的距离
    return length

# 初始化种群
def initPopulation(popSize, cityNum):
    population = []
    for i in range(popSize):
        individual = list(range(cityNum))
        random.shuffle(individual)
        population.append(individual)
    return population

# 计算个体的适应度值
def fitness(individual):
    return 1.0 / pathLength(individual)

# 按照适应度值从大到小排序
def sortPopulation(population):
    return sorted(population, key=fitness, reverse=True)

# 选择操作
def selection(population, eliteSize):
    elite = population[:eliteSize]
    selectionPool = population[eliteSize:]
    fitnesses = [fitness(individual) for individual in selectionPool]
    prob = [f / sum(fitnesses) for f in fitnesses]
    indices = random.choices(range(len(selectionPool)), weights=prob, k=len(selectionPool) - eliteSize)
    selection = [selectionPool[i] for i in indices]
    return elite + selection

# 交叉操作
def crossover(parent1, parent2):
    child = [-1] * len(parent1)
    start = random.randint(0, len(parent1) - 1)
    end = random.randint(start, len(parent1) - 1)
    for i in range(start, end+1):
        child[i] = parent1[i]
    j = 0
    for i in range(len(parent2)):
        if parent2[i] not in child:
            while child[j] != -1:
                j += 1
            child[j] = parent2[i]
    return child

# 突变操作
def mutation(individual, mutationRate):
    for i in range(len(individual)):
        if random.random() < mutationRate:
            j = random.randint(0, len(individual) - 1)
            individual[i], individual[j] = individual[j], individual[i]
    return individual

# 进化操作
def evolve(population, eliteSize, mutationRate):
    selectedPopulation = selection(population, eliteSize)
    offspringPopulation = []
    for i in range(eliteSize, len(selectedPopulation)):
        parent1, parent2 = random.sample(selectedPopulation, 2)
        child = crossover(parent1, parent2)
        child = mutation(child, mutationRate)
        offspringPopulation.append(child)
    return selectedPopulation + offspringPopulation

# TSP问题的求解
def solveTSP(popSize, eliteSize, mutationRate, generations):
    cityNum = len(cityList)
    population = initPopulation(popSize, cityNum)
    bestIndividual = population[0]
    for i in range(generations):
        population = evolve(population, eliteSize, mutationRate)
        currentBest = sortPopulation(population)[0]
        if fitness(currentBest) > fitness(bestIndividual):
            bestIndividual = currentBest
    return bestIndividual

# 测试
bestIndividual = solveTSP(popSize=100, eliteSize=20, mutationRate=0.01, generations=500)
print("最短路径：", bestIndividual)
print("路径长度：", pathLength(bestIndividual))

其中，`cityList`是TSP问题的数据，每个元素表示一个城市的坐标；`distance`函数计算两个城市之间的距离；`pathLength`函数计算一条路径的总长度；`initPopulation`函数用于初始化种群；`fitness`函数计算一个个体的适应度值；`sortPopulation`函数按照适应度值从大到小排序；`selection`函数进行选择操作；`crossover`函数进行交叉操作；`mutation`函数进行突变操作；`evolve`函数进行进化操作；`solveTSP`函数是TSP问题的求解函数，其中`popSize`表示种群大小，`eliteSize`表示精英个体数量，`mutationRate`表示突变率，`generations`表示进化代数。最后，调用`solveTSP`函数进行求解，并输出最短路径和路径长度。