先遗传算法后蚁群算法路径规划代码

以下是遗传算法和蚁群算法的路径规划代码示例：

遗传算法：

import random

# 遗传算法参数设置
POP_SIZE = 100  # 种群数量
GENERATIONS = 1000  # 迭代次数
MUTATION_RATE = 0.05  # 变异率

# 生成初始种群
def generate_population(size, x_bound, y_bound):
    pop = []
    for i in range(size):
        x = random.uniform(*x_bound)
        y = random.uniform(*y_bound)
        pop.append((x, y))
    return pop

# 计算适应度
def fitness(individual, target):
    x, y = individual
    return -(x ** 2 + y ** 2 - target)  # 最大化目标函数值

# 选择函数
def select(population, k=10):
    return sorted(random.sample(population, k), key=lambda x: fitness(x, target), reverse=True)

# 交叉函数
def crossover(p1, p2):
    c1 = (p1[0], p2[1])
    c2 = (p2[0], p1[1])
    return c1, c2

# 变异函数
def mutate(individual, x_bound, y_bound):
    x, y = individual
    if random.random() < MUTATION_RATE:
        x = random.uniform(*x_bound)
    if random.random() < MUTATION_RATE:
        y = random.uniform(*y_bound)
    return x, y

# 遗传算法主函数
def genetic_algorithm(x_bound, y_bound, target):
    population = generate_population(POP_SIZE, x_bound, y_bound)
    for i in range(GENERATIONS):
        parents = select(population, k=2)
        offspring = crossover(*parents)
        offspring = [mutate(individual, x_bound, y_bound) for individual in offspring]
        population.extend(offspring)
        population = sorted(population, key=lambda x: fitness(x, target), reverse=True)
        population = population[:POP_SIZE]
        print(f"Generation {i+1}, Best Fitness: {fitness(population[0], target)}")
    return population[0]

蚁群算法：

import random

# 蚁群算法参数设置
ALPHA = 1  # 信息素重要程度因子
BETA = 5  # 启发函数重要程度因子
RHO = 0.1  # 信息素挥发因子
Q = 100  # 常系数
ANT_COUNT = 50  # 蚂蚁数量
GENERATIONS = 200  # 迭代次数

# 生成城市坐标
def generate_cities(num_cities, x_bound, y_bound):
    cities = []
    for i in range(num_cities):
        x = random.uniform(*x_bound)
        y = random.uniform(*y_bound)
        cities.append((x, y))
    return cities

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

# 计算启发函数
def heuristic(city1, city2):
    return 1 / distance(city1, city2)

# 初始化信息素矩阵
def init_pheromone_matrix(num_cities):
    return [[1 / (num_cities * num_cities) for j in range(num_cities)] for i in range(num_cities)]

# 蚂蚁类
class Ant:
    def __init__(self, start_city, pheromone_matrix, alpha, beta):
        self.start_city = start_city
        self.pheromone_matrix = pheromone_matrix
        self.alpha = alpha
        self.beta = beta
        self.tabu_list = [start_city]
        self.total_distance = 0
    
    # 选择下一个城市
    def select_next_city(self):
        current_city = self.tabu_list[-1]
        unvisited_cities = [i for i in range(len(self.pheromone_matrix)) if i not in self.tabu_list]
        if not unvisited_cities:
            return -1
        probabilities = []
        for city in unvisited_cities:
            pheromone = self.pheromone_matrix[current_city][city]
            h = heuristic(self.tabu_list[0], city)
            p = pheromone ** self.alpha * h ** self.beta
            probabilities.append(p)
        probabilities = [p / sum(probabilities) for p in probabilities]
        next_city = random.choices(unvisited_cities, weights=probabilities)[0]
        self.tabu_list.append(next_city)
        self.total_distance += distance(self.tabu_list[-2], self.tabu_list[-1])
        return next_city
    
    # 更新信息素
    def update_pheromone_matrix(self, q):
        for i in range(len(self.tabu_list)-1):
            city1, city2 = self.tabu_list[i], self.tabu_list[i+1]
            self.pheromone_matrix[city1][city2] += q / self.total_distance
    
    # 重置蚂蚁状态
    def reset(self):
        self.tabu_list = [self.start_city]
        self.total_distance = 0

# 蚁群算法主函数
def ant_colony_optimization(cities):
    num_cities = len(cities)
    pheromone_matrix = init_pheromone_matrix(num_cities)
    ants = [Ant(i, pheromone_matrix, ALPHA, BETA) for i in range(num_cities)]
    best_path = None
    best_distance = float('inf')
    for i in range(GENERATIONS):
        for ant in ants:
            while ant.select_next_city() != -1:
                pass
            if ant.total_distance < best_distance:
                best_path = ant.tabu_list
                best_distance = ant.total_distance
            ant.update_pheromone_matrix(Q)
            ant.reset()
        pheromone_matrix = [[(1 - RHO) * pheromone for pheromone in row] for row in pheromone_matrix]
        for i in range(num_cities-1):
            for j in range(i+1, num_cities):
                for ant in ants:
                    if (i == ant.tabu_list[-1] and j == ant.tabu_list[-2]) or (j == ant.tabu_list[-1] and i == ant.tabu_list[-2]):
                        pheromone_matrix[i][j] += Q / ant.total_distance
                        pheromone_matrix[j][i] = pheromone_matrix[i][j]
        print(f"Generation {i+1}, Best Distance: {best_distance}")
    return best_path, best_distance