### Python 遗传算法实现最短路径问题 以下是基于遗传算法求解最短路径问题的一个完整示例代码。此代码采用优先级编码的方式，避免了二进制编码可能产生的大量不可行解的问题。 #### 地图定义 为了简化问题，我们假设有一个简单的无向加权图表示的地图： ```python import random from deap import base, creator, tools # 定义地图 (邻接矩阵形式) map_graph = { 1: {2: 10, 3: 5}, 2: {4: 1, 3: 2, 1: 10}, 3: {2: 2, 4: 1, 5: 2, 1: 5}, 4: {5: 3, 2: 1, 3: 1}, 5: {3: 2, 4: 3} } start_node = 1 end_node = 5 ``` #### 编码与解码逻辑 在此处，我们将使用节点顺序作为染色体的基因表达方式。例如 `[1, 3, 4, 5]` 表示从起点 `1` 到终点 `5` 的一条路径。 #### 初始化种群 通过随机生成合法路径来初始化种群。 ```python def create_individual(): """ 创建单个个体 """ unvisited = list(map_graph.keys()) unvisited.remove(start_node) individual = [start_node] current_node = start_node while True: neighbors = list(set(map_graph[current_node].keys()) & set(unvisited)) if not neighbors or end_node in neighbors: break next_node = random.choice(neighbors) individual.append(next_node) unvisited.remove(next_node) current_node = next_node individual.append(end_node) # 确保路径以目标节点结束 return individual def init_population(pop_size): """ 初始化种群 """ population = [] for _ in range(pop_size): population.append(create_individual()) return population ``` #### 计算适应度 适应度函数计算路径总长度，越短越好。 ```python def calculate_path_length(individual): """ 计算路径长度 """ total_distance = 0 for i in range(len(individual) - 1): from_node = individual[i] to_node = individual[i + 1] if to_node in map_graph[from_node]: total_distance += map_graph[from_node][to_node] else: return float('inf') # 如果路径不存在，则返回无穷大距离 return total_distance creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) creator.create("Individual", list, fitness=creator.FitnessMin) toolbox = base.Toolbox() toolbox.register("individual", tools.initIterate, creator.Individual, create_individual) toolbox.register("population", tools.initRepeat, list, toolbox.individual) toolbox.register("evaluate", calculate_path_length) toolbox.register("mate", tools.cxOrdered) # 使用有序交叉 toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05) # 变异操作 toolbox.register("select", tools.selTournament, tournsize=3) ``` #### 主程序运行 执行遗传算法的主要循环过程。 ```python def main(): pop_size = 100 generations = 50 crossover_prob = 0.8 mutation_prob = 0.2 population = init_population(pop_size) population = [creator.Individual(indiv) for indiv in population] stats = tools.Statistics(lambda ind: ind.fitness.values) stats.register("min", min) stats.register("avg", lambda vals: sum(vals)/len(vals)) logbook = tools.Logbook() for gen in range(generations): offspring = algorithms.varAnd(population, toolbox, cxpb=crossover_prob, mutpb=mutation_prob) invalid_ind = [ind for ind in offspring if not ind.fitness.valid] fitnesses = toolbox.map(toolbox.evaluate, invalid_ind) for ind, fit in zip(invalid_ind, fitnesses): ind.fitness.values = (fit,) population[:] = toolbox.select(offspring, len(population)) record = stats.compile(population) logbook.record(gen=gen, **record) best_individual = tools.selBest(population, k=1)[0] print(f"最佳路径: {best_individual}, 路径长度: {best_individual.fitness.values[0]}") if __name__ == "__main__": main() ``` --- ### 关键点说明 1. **地图构建**：通过字典模拟了一个简单加权图结构[^1]。 2. **个体编码**：采用了节点序列的形式，确保每条路径都是可行解[^3]。 3. **适应度评估**：路径长度越短，适应度越高[^1]。 4. **遗传操作**：包括选择、交叉和变异三个主要部分[^3]。 ---