点击上方“进修编程”，选择“星标”公众号
超级无敌干货，第一时间送达！！！
在本文中，我将分享有关使用遗传算法来解决我们所有人都面临的问题交通信号灯配时。
优化结果是：交通流量增加了 10.52%，平均拥堵减少了 37.58%。
1. 简介
城市交通拥堵是现代城市面临的一个关键问题，导致污染增加、经济损失和生活质量下降 。传统的交通管理方法往往难以应对城市交通模式的动态特性 。
本案例研究的目标是：
开发真实的城市交通动态模拟
实施多目标遗传算法来优化交通信号灯配时
分析遗传算法 (GA) 方法对改善交通流量和减少拥堵的影响
2. 方法论
2.1 仿真环境
这是城市环境的模拟，具有以下属性：
城市大小：20x20 网格
路口数量：4
车辆数量：初始40辆，随机添加新车
模拟围绕三个主要类别构建：TrafficLight、Car和City。
从数学上讲，我们可以将城市表示为图 G = (V, E)，其中 V 是路口的集合，E 是连接路口的道路的集合。每个路口 v ∈ V 都有一个交通信号灯，其状态为 s_v ∈ {红，绿}，并有一个计时器 t_v。
汽车的运动可以通过功能m：c×t→v来描述，其中c是一组汽车，t是一组时间步骤，v是时间t的汽车c的集合。
M(c, t+1) = { 如果路径畅通，则 M(c, t) + d_c，否则 M(c, t) }
其中 d_c 是车辆 c 的方向向量。
以下是这些的概述：
@dataclassclass TrafficLight:state: str = 'red'timer: int = 0def update(self, timing: int) -> None:self.timer += 1if self.timer >= timing:self.state = 'green' if self.state == 'red' else 'red'self.timer = 0@dataclassclass Car:x: inty: intdirection: Tuple[int, int]def move(self, city: 'City') -> None:nx, ny = (self.x + self.direction[0]) % city.size, (self.y + self.direction[1]) % city.sizeif (nx, ny) in city.intersections:intersection_index = city.intersections.index((nx, ny))if city.traffic_lights[intersection_index].state == 'green':self.x, self.y = nx, nyelse:self.x, self.y = nx, nyif random.random() < 0.1:self.direction = random.choice([(0, 1), (0, -1), (1, 0), (-1, 0)])class City:def __init__(self, size: int, num_intersections: int):self.size = sizeself.num_intersections = num_intersectionsself.grid = np.zeros((size, size))self.intersections = self._place_intersections()self.traffic_lights = [TrafficLight() for _ in range(num_intersections)]self.cars = self._initialize_traffic()def update(self, traffic_light_timings: List[int]) -> None:for light, timing in zip(self.traffic_lights, traffic_light_timings):light.update(timing)for car in self.cars:car.move(self)if random.random() < 0.1:self.cars.append(self._create_random_car())
2.2 交通优化中的遗传算法
遗传算法 (GA) 是一类受自然选择过程启发的进化算法。
GA 的关键概念：
能够处理大型搜索空间：交通优化涉及灯光时间的多种可能组合，从而创建了 GA 可以有效探索的庞大搜索空间。
适应性：GA 可以适应不断变化的适应方法，这在动态交通环境中至关重要。
在这个实现中，GA 种群中的每个个体代表模拟城市中所有交叉路口的一整套交通信号灯时序。
2.2.1 适应度函数设计
适应度函数引导 GA 找到最优解。在我们的多目标方法中，我们定义了两个关键目标：
最大化交通流量：f₁(X) = 车辆总移动量 这是模拟期间所有成功车辆移动量的总和。
最小化拥堵：f₂（X）=-总拥堵拥堵以堵在路口的汽车数量来衡量，我们对该值取反，以将最小化问题转换为最大化问题。
从数学上来说，我们的适应度函数 F(X) 可以描述为：
F（X）=（f₁（X），f₂（X））
在哪里：
f₁（X）= Σ_{t=1}^T Σ_{c∈C} I（M（c，t）≠M（c，t-1））
f₂(X) = -Σ_{t=1}^T Σ_{v∈V} |{c ∈ C | M(c,t) = v}|
其中，T 是总模拟时间，C 是所有车辆的集合，V 是所有交叉路口的集合，I 是指示函数。
2.2.2 多目标优化
目标是最大限度地提高交通流量，同时最大限度地减少拥堵，但这些目标可能相互矛盾。这时多目标优化就变得至关重要。
这里将应用 NSGA-II（非支配排序遗传算法 II）进行多目标优化。NSGA-II 具有一些优点：
基于帕累托的方法：它沿着帕累托前沿维护一组多样化的解决方案，允许探索目标之间的不同权衡。
精英主义：保留迄今为止发现的最佳解决方案，确保好的解决方案不会丢失。
多样性保持：NSGA-II采用拥挤距离机制来保持种群的多样性。
通过使用 NSGA-II，我们可以找到一组代表交通流和拥堵之间不同权衡的帕累托最优解。
2.2.3 为什么采用遗传算法进行交通优化？
GA 特别适合解决流量优化问题，原因如下：
复杂的相互作用：交通系统涉及车辆、交通信号灯和道路网络之间的复杂相互作用。GA 可以捕捉这些相互作用，而无需显式建模。
非线性优化：交通信号灯时间和整体系统性能之间的关系是非线性的。GA 可以处理非线性搜索空间。
可扩展性：随着城市的发展，交通网络变得越来越复杂，并可能导致指数级的复杂性。
灵活性：GA 可以应用于各种目标或约束。
鲁棒性：与一些传统的优化方法相比，GA 不太可能陷入局部最优。
2.2.4 遗传算法的实现：
我使用DEAP（Python 中的分布式进化算法）库 实现了 GA 。
GA 实施的关键组件包括：
染色体表示：X = (x_1, x_2, …, x_n)，其中 x_i ∈ [20, 80] 表示交叉路口 i 的绿灯持续时间。
适应度函数：同时考虑交通流和拥堵的多目标适应度函数：
def evaluate(individual: List[int], city: City) -> Tuple[float, float]:city_copy = City(city.size, city.num_intersections)city_copy.intersections = city.intersections.copy()city_copy.cars = [Car(car.x, car.y, car.direction) for car in city.cars]total_movement = 0congestion = 0for _ in range(50):city_copy.update(individual)total_movement += sum(1 for car in city_copy.cars if (car.x, car.y) not in city_copy.intersections)congestion += sum(sum(1 for car in city_copy.cars if car.x == x and car.y == y)for x, y in city_copy.intersections)return total_movement, -congestion
3.选择：NSGA-II算法进行多目标优化。
在遗传算法中，选择是从种群中选择个体进行繁殖并将其遗传信息传递给下一代的过程。目标是选择适应度最高的个体，并以此随着时间的推移改善总体种群。
在本代码中，我们使用NSGA-II 算法（非支配排序遗传算法 II）进行选择。NSGA-II 特别适用于多目标优化问题，其中有多个相互冲突的目标需要同时优化（在本例中，两个目标具有相同的权重）。它是多目标优化最流行的算法之一，因为它使用一种称为拥挤距离的技术来保持种群的多样性并确保向帕累托最优前沿收敛。
该tools.selNSGA2函数通过以下方式实现该算法：
根据帕累托支配地位（非支配排序）对个体进行排序。
在探索（寻找多样化的解决方案）和利用（专注于最佳解决方案）之间保持平衡。
NSGA-II 的主要优势在于它允许算法演化出针对多个目标最优的解决方案。
4.交叉和变异：我实现了二点交叉和均匀整数变异。
交叉是一种将两个亲本的遗传物质（染色体）结合起来产生后代的算子。它模仿生物繁殖，对于将变异引入种群至关重要。
在此实现中，使用两点交叉tools.cxTwoPoint（ ）。在两点交叉中，在父代染色体中随机选择两个位置，并交换这些点之间的片段以创建两个新的后代。与单点交叉相比，此方法可确保交换更重要的遗传物质块，这有助于在保留部分父代结构的同时引入变异。
例如：
父代 1: [25, 30, 40, 50, 60, 70]
父代 2：[30, 35, 45, 55, 65, 75]
经过两点交叉（例如在位置 2 和 5 之间），后代可能如下所示：
后代1: [25, 30, 45, 55, 65, 70]
后代2：[30, 35, 40, 50, 60, 75]
此操作通过结合父母双方的特征来促进解决方案空间的探索。
变异：统一整数变异
变异是另一个将随机性引入种群的遗传算子。其目的是通过对系统进行小的改变来防止种群陷入局部最优。
这里利用了均匀整数突变（tools.mutUniformInt），其中个体中的每个基因（或染色体值）都有很小的概率（indpb=0.1）被指定范围内的随机整数（在本例中为 20 到 80 之间）替换。
例如，如果一个个体[25, 30, 40, 50, 60, 70]，并且将突变概率应用于每个基因，结果可能如下所示：
变异个体：[25, 35, 40, 50, 62, 70]
变异确保探索解决方案空间的新区域，并防止群体变得过于同质，并提高算法寻找全局最优的能力。
完整代码示例
以下是 GA 代码的演示
! pip install deapdef create_toolbox(num_intersections: int):creator.create("FitnessMulti", base.Fitness, weights=(1.0, 1.0))creator.create("Individual", list, fitness=creator.FitnessMulti)toolbox = base.Toolbox()toolbox.register("attr_timing", random.randint, 20, 80)toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_timing, n=num_intersections)toolbox.register("population", tools.initRepeat, list, toolbox.individual)return toolboxdef run_ga(city: City, num_generations: int = 50, population_size: int = 50) -> Tuple[List[int], tools.Logbook]:toolbox = create_toolbox(city.num_intersections)toolbox.register("evaluate", evaluate, city=city)toolbox.register("mate", tools.cxTwoPoint)toolbox.register("mutate", tools.mutUniformInt, low=20, up=80, indpb=0.1)toolbox.register("select", tools.selNSGA2)population = toolbox.population(n=population_size)stats = tools.Statistics(lambda ind: ind.fitness.values)stats.register("avg", np.mean, axis=0)stats.register("std", np.std, axis=0)stats.register("min", np.min, axis=0)stats.register("max", np.max, axis=0)logbook = tools.Logbook()logbook.header = ['gen', 'nevals'] + stats.fieldsfor gen in range(num_generations):offspring = algorithms.varAnd(population, toolbox, cxpb=0.7, mutpb=0.3)fits = toolbox.map(toolbox.evaluate, offspring)for fit, ind in zip(fits, offspring):ind.fitness.values = fitpopulation = toolbox.select(population + offspring, k=len(population))record = stats.compile(population)logbook.record(gen=gen, nevals=len(offspring), **record)return tools.selBest(population, k=1)[0], logbook
3.结果与分析
我运行了 60 代遗传算法，种群规模为 50。以下是主要发现：
Genetic Algorithm Optimization ║╠═══════════╦═══════════════════╦═══════════════════╦═════════════════════╦═══════════════════╣║ Generation ║ Avg Traffic Flow ║ Avg Congestion ║ Best Traffic Flow ║ Best Congestion ║╠═══════════╬═══════════════════╬═══════════════════╬═════════════════════╬═══════════════════╣║ 0 ║ 2161.66 ║ 3.14 ║ 2295.00 ║ 12.00 ║║ 1 ║ 2187.58 ║ 3.06 ║ 2348.00 ║ 12.00 ║║ 2 ║ 2200.66 ║ 2.78 ║ 2348.00 ║ 12.00 ║║ 3 ║ 2212.90 ║ 2.52 ║ 2348.00 ║ 12.00 ║║ 4 ║ 2221.12 ║ 2.24 ║ 2348.00 ║ 9.00 ║║ 5 ║ 2226.74 ║ 2.12 ║ 2348.00 ║ 9.00 ║║ 6 ║ 2231.98 ║ 1.96 ║ 2348.00 ║ 9.00 ║║ 7 ║ 2234.78 ║ 1.94 ║ 2348.00 ║ 9.00 ║║ 8 ║ 2240.70 ║ 2.26 ║ 2348.00 ║ 10.00 ║║ 9 ║ 2245.08 ║ 2.44 ║ 2348.00 ║ 10.00 ║║ 10 ║ 2250.18 ║ 2.40 ║ 2348.00 ║ 10.00 ║║ 11 ║ 2251.34 ║ 2.36 ║ 2348.00 ║ 10.00 ║║ 12 ║ 2254.88 ║ 2.36 ║ 2348.00 ║ 10.00 ║║ 13 ║ 2255.76 ║ 2.38 ║ 2348.00 ║ 10.00 ║║ 14 ║ 2256.36 ║ 2.32 ║ 2348.00 ║ 10.00 ║║ 15 ║ 2258.50 ║ 2.48 ║ 2348.00 ║ 10.00 ║║ 16 ║ 2258.50 ║ 2.48 ║ 2348.00 ║ 10.00 ║║ 17 ║ 2259.72 ║ 2.46 ║ 2348.00 ║ 10.00 ║║ 18 ║ 2261.04 ║ 2.56 ║ 2348.00 ║ 10.00 ║║ 19 ║ 2261.04 ║ 2.56 ║ 2348.00 ║ 10.00 ║║ 20 ║ 2261.96 ║ 2.64 ║ 2348.00 ║ 10.00 ║║ 21 ║ 2265.64 ║ 2.58 ║ 2348.00 ║ 10.00 ║║ 22 ║ 2266.32 ║ 2.46 ║ 2348.00 ║ 10.00 ║║ 23 ║ 2266.90 ║ 2.50 ║ 2348.00 ║ 10.00 ║║ 24 ║ 2267.62 ║ 2.48 ║ 2348.00 ║ 10.00 ║║ 25 ║ 2269.08 ║ 2.42 ║ 2348.00 ║ 10.00 ║║ 26 ║ 2269.90 ║ 2.58 ║ 2348.00 ║ 10.00 ║║ 27 ║ 2269.90 ║ 2.58 ║ 2348.00 ║ 10.00 ║║ 28 ║ 2270.22 ║ 2.30 ║ 2348.00 ║ 10.00 ║║ 29 ║ 2272.24 ║ 2.34 ║ 2348.00 ║ 10.00 ║║ 30 ║ 2272.24 ║ 2.34 ║ 2348.00 ║ 10.00 ║║ 31 ║ 2273.18 ║ 2.42 ║ 2348.00 ║ 10.00 ║║ 32 ║ 2273.18 ║ 2.42 ║ 2348.00 ║ 10.00 ║║ 33 ║ 2274.00 ║ 2.26 ║ 2348.00 ║ 10.00 ║║ 34 ║ 2277.46 ║ 2.26 ║ 2348.00 ║ 10.00 ║║ 35 ║ 2277.80 ║ 2.26 ║ 2348.00 ║ 10.00 ║║ 36 ║ 2278.16 ║ 2.22 ║ 2348.00 ║ 10.00 ║║ 37 ║ 2278.98 ║ 2.22 ║ 2348.00 ║ 10.00 ║║ 38 ║ 2279.46 ║ 2.18 ║ 2348.00 ║ 10.00 ║║ 39 ║ 2281.58 ║ 2.30 ║ 2360.00 ║ 10.00 ║║ 40 ║ 2281.56 ║ 2.26 ║ 2360.00 ║ 10.00 ║║ 41 ║ 2282.16 ║ 2.24 ║ 2360.00 ║ 10.00 ║║ 42 ║ 2284.66 ║ 2.12 ║ 2389.00 ║ 10.00 ║║ 43 ║ 2284.68 ║ 2.14 ║ 2389.00 ║ 10.00 ║║ 44 ║ 2285.44 ║ 2.16 ║ 2389.00 ║ 10.00 ║║ 45 ║ 2286.12 ║ 2.20 ║ 2389.00 ║ 10.00 ║║ 46 ║ 2286.12 ║ 2.20 ║ 2389.00 ║ 10.00 ║║ 47 ║ 2288.12 ║ 2.06 ║ 2389.00 ║ 10.00 ║║ 48 ║ 2290.00 ║ 2.04 ║ 2389.00 ║ 10.00 ║║ 49 ║ 2290.10 ║ 2.04 ║ 2389.00 ║ 10.00 ║║ 50 ║ 2292.64 ║ 1.98 ║ 2389.00 ║ 10.00 ║║ 51 ║ 2293.88 ║ 2.02 ║ 2389.00 ║ 10.00 ║║ 52 ║ 2293.88 ║ 2.02 ║ 2389.00 ║ 10.00 ║║ 53 ║ 2293.88 ║ 2.02 ║ 2389.00 ║ 10.00 ║║ 54 ║ 2294.78 ║ 1.98 ║ 2389.00 ║ 10.00 ║║ 55 ║ 2296.04 ║ 2.04 ║ 2389.00 ║ 10.00 ║║ 56 ║ 2297.46 ║ 1.84 ║ 2389.00 ║ 7.00 ║║ 57 ║ 2297.46 ║ 1.84 ║ 2389.00 ║ 7.00 ║║ 58 ║ 2297.90 ║ 1.92 ║ 2389.00 ║ 7.00 ║║ 59 ║ 2298.76 ║ 1.96 ║ 2389.00 ║ 7.00 ║╚═══════════╩═══════════════════╩═══════════════════╩═════════════════════╩═══════════════════╝
改善交通流量：
初始平均值：2161.66
最终平均成绩：2298.76
最佳成绩：2389.00
总体改善：6.34%（平均）、10.52%（最佳）
2.减少交通拥堵：
初始平均值：3.14
最终平均值：1.96
最佳成绩：7.00（越低越好）
总体减少：37.58%（平均）
3. 最佳交通信号灯时序：
GA 找到的最佳解决方案建议四个交叉路口的时序如下（以秒为单位）：
[ 80,73,64,69 ]4. 帕累托前沿分析
以下是实验解决方案的帕累托前沿的分析：
算法的收敛表现出明显的初始改进，随后逐渐优化。这是遗传算法的典型特征，表明该算法在对解决方案进行微调之前可以快速找到解决方案空间的良好区域 。
帕累托前沿分析表明，交通流量和拥堵之间存在权衡。这凸显了问题的多目标性质以及在城市交通管理中考虑这两个因素的重要性 。
讨论
结果证明了遗传算法在优化城市交通系统方面的潜力。交通流量和拥堵减少方面的显著改善凸显了这种方法的强大作用。
推荐一本关于python深度学习的书，有需要的可以点击链接购买。
python、matlab程序设计找我
— 完 —
