### 基于蚁群算法的二维避障 Python 实现 #### 蚁群算法简介 蚁群算法是一种仿生智能算法，通过模拟蚂蚁在路径选择中的信息素更新机制，实现群体协作式的路径寻优。该算法广泛应用于多种优化问题，如旅行商问题、路径规划等[^1]。 #### 启发式函数设计 对于二维避障问题，启发式函数的设计至关重要。启发式函数应综合考虑距离、障碍物位置等因素，以引导蚂蚁向目标点移动并有效避开障碍物。一个有效的启发式函数能够显著提升算法性能和求解速度[^5]。 #### 环境设置与初始化 为了构建基于蚁群算法的二维避障模型，首先需定义环境参数及初始条件： ```python import numpy as np import matplotlib.pyplot as plt class Environment: def __init__(self, width=100, height=100): self.width = width self.height = height self.obstacles = [] def add_obstacle(self, x, y, radius): self.obstacles.append((x, y, radius)) env = Environment() env.add_obstacle(30, 70, 10) # 添加圆形障碍物 ``` #### 参数配置 设定蚁群算法所需的主要参数，包括蚂蚁数量、迭代次数以及信息素蒸发系数等： ```python class ACOParams: def __init__(self, num_ants=50, iterations=100, alpha=1.0, beta=2.0, rho=0.5): self.num_ants = num_ants self.iterations = iterations self.alpha = alpha # 信息素重要程度因子 self.beta = beta # 启发式信息重要程度因子 self.rho = rho # 信息素挥发率 params = ACOParams() ``` #### 主体逻辑实现 核心部分在于如何让每只蚂蚁按照一定规则探索最优路径，并不断调整信息素浓度直至找到最佳解决方案： ```python def distance(point_a, point_b): return ((point_a[0]-point_b[0])**2 + (point_a[1]-point_b[1])**2)**0.5 def heuristic_distance(current_pos, target_pos, env): min_dist_to_obs = float('inf') for obs in env.obstacles: dist_to_obs = max(distance(current_pos[:2], obs)-obs[-1], 0) if dist_to_obs < min_dist_to_obs: min_dist_to_obs = dist_to_obs h_value = distance(current_pos[:2], target_pos) / (min_dist_to_obs + 1e-6) return h_value def aco_path_planning(start_point, end_point, environment, params): pheromone_matrix = np.ones((environment.width, environment.height)) * 0.1 best_path_length = float('inf') best_path = None for iteration in range(params.iterations): all_paths = [] for ant_id in range(params.num_ants): current_position = start_point.copy() path = [current_position] while not np.allclose(current_position, end_point, atol=1e-3): possible_moves = [(dx, dy) for dx in [-1, 0, 1] for dy in [-1, 0, 1]] move_probabilities = [ ( pheromone_matrix[current_position[0]+dx][current_position[1]+dy]**params.alpha * (heuristic_distance([current_position[0]+dx, current_position[1]+dy], end_point, environment)**(-params.beta)), (dx, dy) ) for dx, dy in possible_moves if 0 <= current_position[0]+dx < environment.width and 0 <= current_position[1]+dy < environment.height and not any([ distance([current_position[0]+dx, current_position[1]+dy], o[:-1])<=o[-1] for o in environment.obstacles]) ] total_probability = sum(prob[0] for prob in move_probabilities) normalized_move_probs = [(p/total_probability, m) for p,m in move_probabilities] selected_dx_dy = weighted_choice(normalized_move_probs)[1] new_position = [sum(x) for x in zip(current_position, selected_dx_dy)] path.append(new_position) current_position = new_position all_paths.append(path) path_length = sum( distance(path[i], path[i+1]) for i in range(len(path)-1)) if path_length < best_path_length: best_path_length = path_length best_path = path update_pheromones(all_paths, pheromone_matrix, params.rho) return best_path def weighted_choice(choices): import random total = sum(w for c, w in choices) r = random.uniform(0, total) upto = 0 for c, w in choices: if upto + w >= r: return c upto += w assert False, "Shouldn't get here" def update_pheromones(paths, matrix, evaporation_rate): matrix *= (1-evaporation_rate) for path in paths: for pos_from, pos_to in zip(path[:-1], path[1:]): matrix[pos_from[0]][pos_from[1]] += 1/distance(pos_from, pos_to) start_point = [10, 90] end_point = [80, 20] best_solution = aco_path_planning(start_point=start_point, end_point=end_point, environment=env, params=params) print(f'Best found solution length={len(best_solution)}') plt.figure(figsize=(8,8)) for obstacle in env.obstacles: circle = plt.Circle(obstacle[:-1], obstacle[-1], color='red', fill=True) plt.gca().add_patch(circle) path_x_coords = [node[0] for node in best_solution] path_y_coords = [node[1] for node in best_solution] plt.