禁忌遗传算法python实现

禁忌遗传算法是一种结合了禁忌搜索和遗传算法的优化算法。它通过遗传算法的交叉和变异操作来生成新的解，并通过禁忌搜索的方式来避免陷入局部最优解。下面是禁忌遗传算法的Python实现步骤：

1. 初始化种群：随机生成一定数量的初始解作为种群。

2. 评估适应度：对于每个个体，计算其适应度值。

3. 选择操作：根据适应度值选择一定数量的个体作为父代。

4. 交叉操作：对于选出的父代，进行交叉操作生成新的个体。

5. 变异操作：对于新生成的个体，进行变异操作。

6. 禁忌搜索：对于新生成的个体，进行禁忌搜索操作，避免陷入局部最优解。

7. 更新种群：将新生成的个体加入种群中。

8. 重复步骤2-7，直到达到预设的停止条件。

下面是一个简单的禁忌遗传算法的Python实现示例：

import random

# 初始化种群
def init_population(pop_size, chrom_size):
    population = []
    for i in range(pop_size):
        chromosome = [random.randint(0, 1) for j in range(chrom_size)]
        population.append(chromosome)
    return population

# 计算适应度
def fitness(chromosome):
    return sum(chromosome)

# 选择操作
def selection(population, fitness):
    parents = []
    for i in range(len(population)):
        parent1 = random.choice(population)
        parent2 = random.choice(population)
        if fitness(parent1) > fitness(parent2):
            parents.append(parent1)
        else:
            parents.append(parent2)
    return parents

# 交叉操作
def crossover(parents, pc):
    offspring = []
    for i in range(0, len(parents), 2):
        parent1 = parents[i]
        parent2 = parents[i+1]
        if random.random() < pc:
            point = random.randint(1, len(parent1)-1)
            offspring1 = parent1[:point] + parent2[point:]
            offspring2 = parent2[:point] + parent1[point:]
            offspring.append(offspring1)
            offspring.append(offspring2)
        else:
            offspring.append(parent1)
            offspring.append(parent2)
    return offspring

# 变异操作
def mutation(offspring, pm):
    for i in range(len(offspring)):
        for j in range(len(offspring[i])):
            if random.random() < pm:
                offspring[i][j] = 1 - offspring[i][j]
    return offspring

# 禁忌搜索
def tabu_search(solution, tabu_list, max_tabu_size):
    best_solution = solution
    best_fitness = fitness(solution)
    for i in range(len(solution)):
        for j in range(i+1, len(solution)):
            if (i, j) not in tabu_list:
                new_solution = solution.copy()
                new_solution[i], new_solution[j] = new_solution[j], new_solution[i]
                new_fitness = fitness(new_solution)
                if new_fitness > best_fitness:
                    best_solution = new_solution
                    best_fitness = new_fitness
                    tabu_list.append((i, j))
                    if len(tabu_list) > max_tabu_size:
                        tabu_list.pop(0)
    return best_solution

# 禁忌遗传算法
def tabu_genetic_algorithm(pop_size, chrom_size, max_iter, pc, pm, max_tabu_size):
    population = init_population(pop_size, chrom_size)
    for i in range(max_iter):
        fitness_values = [fitness(chromosome) for chromosome in population]
        parents = selection(population, fitness_values)
        offspring = crossover(parents, pc)
        offspring = mutation(offspring, pm)
        for j in range(len(offspring)):
            offspring[j] = tabu_search(offspring[j], [], max_tabu_size)
        population = parents + offspring
    best_chromosome = max(population, key=fitness)
    best_fitness = fitness(best_chromosome)
    return best_chromosome, best_fitness

# 测试
chrom_size = 10
pop_size = 50
max_iter = 100
pc = 0.8
pm = 0.1
max_tabu_size = 10
best_chromosome, best_fitness = tabu_genetic_algorithm(pop_size, chrom_size, max_iter, pc, pm, max_tabu_size)
print("Best solution:", best_chromosome)
print("Best fitness:", best_fitness)