遗传算法 禁忌搜索算法 混合 python

遗传算法和禁忌搜索算法是两种常见的启发式算法，用于解决优化问题，如TSP问题。下面是一个使用Python混合遗传算法和禁忌搜索算法求解TSP问题的示例：

import random

# 初始化种群
def init_population(num_cities, population_size):
    population = []
    for _ in range(population_size):
        individual = list(range(num_cities))
        random.shuffle(individual)
        population.append(individual)
    return population

# 计算路径长度
def calculate_distance(city1, city2):
    # 计算城市之间的距离，这里假设城市之间的距离已知
    pass

def calculate_fitness(individual):
    total_distance = 0
    for i in range(len(individual)):
        city1 = individual[i]
        city2 = individual[(i + 1) % len(individual)]
        total_distance += calculate_distance(city1, city2)
    return 1 / total_distance

# 选择操作
def selection(population, num_parents):
    parents = []
    for _ in range(num_parents):
        parent = random.choice(population)
        parents.append(parent)
    return parents

# 交叉操作
def crossover(parents):
    child = []
    # 选择一个随机的交叉点
    crossover_point = random.randint(0, len(parents[0]))
    child.extend(parents[0][:crossover_point])
    for gene in parents[1]:
        if gene not in child:
            child.append(gene)
    return child

# 变异操作
def mutation(individual):
    # 选择两个随机的变异点
    mutation_points = random.sample(range(len(individual)), 2)
    individual[mutation_points[0]], individual[mutation_points[1]] = individual[mutation_points[1]], individual[mutation_points[0]]
    return individual

# 禁忌搜索操作
def tabu_search(individual, tabu_list):
    best_individual = individual
    best_fitness = calculate_fitness(individual)
    for i in range(len(individual)):
        for j in range(i + 1, len(individual)):
            new_individual = individual.copy()
            new_individual[i], new_individual[j] = new_individual[j], new_individual[i]
            new_fitness = calculate_fitness(new_individual)
            if new_fitness > best_fitness and new_individual not in tabu_list:
                best_individual = new_individual
                best_fitness = new_fitness
    return best_individual

# 主函数
def tsp_ga_ts(num_cities, population_size, num_generations):
    population = init_population(num_cities, population_size)
    for _ in range(num_generations):
        parents = selection(population, 2)
        child = crossover(parents)
        child = mutation(child)
        population.append(child)
        population = sorted(population, key=lambda x: calculate_fitness(x), reverse=True)[:population_size]
        tabu_list = []
        for i in range(len(population)):
            population[i] = tabu_search(population[i], tabu_list)
            tabu_list.append(population[i])
            if len(tabu_list) > population_size:
                tabu_list.pop(0)
    best_individual = max(population, key=lambda x: calculate_fitness(x))
    return best_individual

# 示例使用
num_cities = 10
population_size = 100
num_generations = 1000
best_individual = tsp_ga_ts(num_cities, population_size, num_generations)
print("Best individual:", best_individual)

这个示例中，我们首先定义了一些基本的遗传算法和禁忌搜索算法的操作，如初始化种群、计算路径长度、计算适应度、选择、交叉、变异和禁忌搜索。然后，我们使用这些操作来实现一个求解TSP问题的混合算法。最后，我们使用示例数据进行演示，并输出最优解。