遗传算法货郎担算法代码

以下是一个简单的遗传算法实现货郎担问题的代码：

import random

# 城市坐标
CITIES = {"A": (0, 0), "B": (1, 5), "C": (5, 2), "D": (8, 3), "E": (6, 8)}

# 遗传算法参数
POPULATION_SIZE = 50
ELITISM_RATE = 0.1
MUTATION_RATE = 0.1
GENERATIONS = 100

# 计算两个城市之间的距离
def distance(city1, city2):
    x1, y1 = CITIES[city1]
    x2, y2 = CITIES[city2]
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

# 生成一个随机的个体（城市排列）
def generate_individual():
    cities = list(CITIES.keys())
    random.shuffle(cities)
    return cities

# 计算一个个体的适应度（路线总长度）
def fitness(individual):
    return sum(distance(individual[i], individual[i+1]) for i in range(len(individual)-1)) + distance(individual[-1], individual[0])

# 选择下一代个体
def select(population):
    elites_size = int(ELITISM_RATE * len(population))
    elites = sorted(population, key=lambda x: fitness(x))[:elites_size]
    parents = population[elites_size:]
    total_fitness = sum(fitness(p) for p in parents)
    probabilities = [fitness(p) / total_fitness for p in parents]
    selected = []
    for i in range(len(parents)):
        selected.append(random.choices(parents, probabilities)[0])
    return elites + selected

# 交叉两个个体，生成新的个体
def crossover(individual1, individual2):
    start = random.randint(0, len(individual1) - 1)
    end = random.randint(start, len(individual1) - 1)
    child = individual1[start:end]
    for city in individual2:
        if city not in child:
            child.append(city)
    return child

# 变异一个个体
def mutate(individual):
    if random.random() < MUTATION_RATE:
        i = random.randint(0, len(individual) - 1)
        j = random.randint(0, len(individual) - 1)
        individual[i], individual[j] = individual[j], individual[i]

# 遗传算法主函数
def genetic_algorithm():
    population = [generate_individual() for _ in range(POPULATION_SIZE)]
    for _ in range(GENERATIONS):
        population = select(population)
        new_population = []
        while len(new_population) < POPULATION_SIZE:
            parent1, parent2 = random.sample(population, 2)
            child = crossover(parent1, parent2)
            mutate(child)
            new_population.append(child)
        population = new_population
    best_individual = sorted(population, key=lambda x: fitness(x))[0]
    return best_individual, fitness(best_individual)

# 测试遗传算法
best_individual, best_fitness = genetic_algorithm()
print(f"最短路线: {' -> '.join(best_individual)}")
print(f"总长度: {best_fitness}")

该代码使用遗传算法求解五个城市之间的最短路线，其中`CITIES`定义了五个城市的坐标，`POPULATION_SIZE`定义了每一代的个体数量，`ELITISM_RATE`定义了保留精英的比例，`MUTATION_RATE`定义了变异率，`GENERATIONS`定义了遗传算法的迭代次数。在`select`函数中，使用了轮盘赌选择算法来选择下一代个体；在`crossover`函数中，使用了部分映射交叉算法；在`mutate`函数中，使用了交换两个城市的位置的变异操作。