本文约7,100字，建议收藏阅读
作者 | 直观解
出品 | 汽车电子与软件
欢迎关注下方公众号阿宝1990，本公众号专注于自动驾驶和智能座舱，每天给你一篇汽车干货，我们始于车，但不止于车。
确定一款域控制器的最优物料清单BOM（bill of materials）是一件计算量很大的工作，要求物美的同时也要价廉。假设每一种物料有M种选择，那么域控制器全部N款物料总共有M的N次方种方案，也就是N个M相乘。要在这么多种方案中做出选择，架构人力已经不够用，本文使用元启发式优化算法为车辆域控制器选型最佳的物料清单，以求在激烈的市场竞争中为域控制器获得性价比优势。
车辆域控制器是现代汽车电子系统中的重要组成部分，它负责管理和协调各种车载电子系统和子系统的运作。因此，它包含了多种关键物料和组件。以下是一些主要的物料列表（注意，不是说每一种域控制器一定会包含以下所有）：
1. 微处理器（MCU）/微控制器：这是域控制器的核心，负责执行控制算法和逻辑处理任务。通常使用高性能的32位或64位处理器。
2. 专用集成电路（ASIC）：为特定功能设计的集成电路，如电源管理、信号处理等。
3. 可编程逻辑器件（PLD）/现场可编程门阵列（FPGA）：用于实现灵活的逻辑功能和快速原型开发。
4. 存储器：包括RAM（随机存取存储器）、ROM（只读存储器）、EEPROM（电可擦除可编程只读存储器）和闪存等，用于存储程序代码、配置数据和运行时数据。比如OTA升级时断点续传，就是先把旧包和升级包下载到域控制器本地存储器，一旦安装失败就可以回滚rollback。
5. 传感器接口：用于连接和处理来自各种传感器的数据，如温度传感器、压力传感器、加速度计等。
6. 通信接口：支持CAN（控制器局域网）、LIN（本地互连网络）、FlexRay、Ethernet等车载网络协议的硬件接口。有些高级的还有车载以太网的硬件接口。
7. 电源管理单元（PMIC）：确保域控制器内部各部分的电压稳定，并提供过压、欠压保护等功能。
8. 隔离器件：如光耦合器、磁耦合器等，用于在不同电压等级或电气隔离的电路之间传输信号。
9. 散热解决方案：包括散热片、风扇或热管等，用于管理域控制器工作时产生的热量。
10. 外壳和机械结构件：为域控制器提供物理保护和支持，可能包括金属壳体、固定支架等。
每一类器件可以有不同的型号选择，导致不同的价格和性能。在竞争激烈的车辆市场，最优性价比能够带来竞争优势。
假设有10类器件，每类有三种选择，那么总共有3的10次方种（=59,049）总体选择方案。这已经超出了设计人员手工计算可以处理的范围。
如果一种算法，能够面对巨量的解空间（一般是指数级别，比如2^N）,在可行的计算时间内，找出质量近似最优（不是绝对最优）的优质可行解。那么这种算法在工业上就具有应用价值。
元启发式算法就是能达到上述目的的一大类算法。
由于其优化性质，元启发式算法用于车辆算法中的方方面面，比如自动驾驶中：
元启发式算法在自动驾驶领域中用的最多是在路径规划和优化方面，也包括优化神经网络来改进目标识别。这些算法通过模拟自然现象或生物行为（这也是为什么叫启发式，表示受某种客观现象的启发）来解决复杂的优化问题，具有较强的全局搜索能力和跳出局部最优解的能力。
1. 路径规划与优化
a. 避免局部最小值：与基于梯度的算法相比，元启发式优化算法不太可能陷入局部最小值，因为它们的探索阶段可以帮助探索不同的空间。这使得它们非常适合用于动态和不确定环境下的路径规划。
b. 提高效率：A* 算法作为一种启发式搜索方法，能够提供搜索方向的指引信息，从而大大提高搜索效率，尤其是在大规模静态路网中求解最短路径时表现优异。
c. 适应复杂环境：元启发式算法如萤火虫算法（FA）等可以处理复杂的交通场景，并根据实时数据做出独立且明智的决策，使车辆能够在复杂环境中安全行驶。
2. 应对不确定性
a. 处理输入数据的不确定性：路径规划算法依赖于地图数据和传感器数据的准确性和完整性。然而，在实际应用中，这些数据可能存在不确定性和误差。元启发式算法可以通过其强大的鲁棒性来应对这些问题，确保路径规划结果的可靠性。
3. 结合深度学习
a. 增强感知能力：元启发式算法还可以与深度学习技术相结合，例如使用改进的鲸鱼优化算法（WOG-YOLO）进行目标检测，以提高自动驾驶车辆对周围环境的理解和反应速度。
b. 优化神经网络：元启发式算法可以用于优化神经网络的权重，进一步提升深度学习模型的性能，从而更好地支持自动驾驶系统的决策过程。
为什么满足于近似最优解而不强调绝对最优解呢？
因为人类目前的算法理论顶峰，不确定能够在超大的解空间中找到绝对最优解，至少不能在可以忍受的计算时间（多项式时间内）内找到绝对最优解。只好退而求其次，满足于寻找近似最优解。
你能用启发式方法（打比方的方式）告诉我什么叫启发式算法吗？
笔者想用筛子筛板栗来举例。板栗收获后，太小的板栗不适合做糖炒栗子。农家会用筛子来筛板栗，让较小的板栗漏出去，尽可能只留下大板栗留在筛子里面。虽然农家完全不理解这个随机的复杂物理过程，但知道它是有效果的，可以用来启发某个“筛板栗”算法的实现。
筛的次数越多，留在筛子里面的小板栗就越少。这表明增加迭代次数有助于逐步改进解的质量。
筛的次数超过一个上限后，继续增加筛的次数不能进一步减少留在筛子里的小板栗数量，或者很不划算，多筛几百次才能减少一两个小板栗。这说明不应该继续迭代，而是应该结束算法，取目前找到的所有解中最好的那一个作为结果。
如果用算法来模拟这个过程，就是受到这个物理现象的启发，虽然不能完全确认这个随机的复杂筛动过程的机理，但仍然能够达到优化效果，即筛掉尽可能多的小板栗。那么这个算法就是受到筛板栗启发的启发式算法。
有时候优化目标不止一个，我们就需要寻找帕累托最优解，这种解想改进一个目标值，就必须劣化另外一个目标值。
以下我们正式介绍多目标优化的原理和核心概念：
多目标优化（Multi-Objective Optimization, MOO）是指在多个目标函数之间寻找最优解的过程。这些目标通常是相互冲突的，例如在产品设计中，我们可能希望同时最小化成本和最大化性能，但这两者往往是相互矛盾的。因此，多目标优化的目标是找到一组帕累托最优解（Pareto Optimal Solutions），这些解表示在不降低任何一个目标的情况下，无法改进其他目标的情况。
多目标优化的核心概念：
帕累托最优性：一组解被称为帕累托最优解，如果不存在其他解能够在所有目标上都不比它差，并且至少在一个目标上更好。帕累托最优解集构成了帕累托前沿（Pareto Front），即所有可能的帕累托最优解的集合。
元启发式算法：元启发式算法是一类基于启发式搜索策略的优化算法，它们通常能够处理复杂和大规模的优化问题。常见的元启发式算法包括遗传算法（Genetic Algorithms, GA）、粒子群优化（Particle Swarm Optimization, PSO）、模拟退火（Simulated Annealing, SA）等。
多目标元启发式算法：为了处理多目标优化问题，需要对传统的元启发式算法进行扩展。这些扩展通常通过引入特定的机制来维护帕累托最优解集，例如：
非支配排序：在每一代进化过程中，根据解之间的支配关系（dominance relation）对种群中的个体进行排序。一个解支配另一个解，如果它在所有目标上都不差，并且至少在一个目标上更好。
拥挤距离：为了解决拥挤现象，即大量解聚集在帕累托前沿的某些区域，可以使用拥挤距离（crowding distance）来度量解的稀疏程度。拥挤距离较大的解被认为更具有多样性。
外部档案（External Archive）：保存帕累托最优解集，以确保在优化过程中不会丢失这些重要的解。外部档案可以是有限大小的，通常会使用特定的机制来控制档案的大小，如删除最不重要的解。
比如域控制器对各种内部物料的选型，又希望最小化成本，又希望最大化性能，所以有两个优化目标。而算出来的帕累托最优解，如果想增加性能就必须增加成本，或者减小成本就必须损害性能，而不能同时又减小成本又增加性能。帕累托最优解可以有多个。
笔者所在的某新势力重卡OEM，在自行设计某些域控制器，比如动力域控制器，车身域控制器等等。我们以一款车身域控制器为例，对每种物料设置三个备选项，并且对每种物料根据供应商友好度，以往使用经验，性能参数等等组织内部专家打分（满分10分），得到如下表格（芯片等物料的价格随着供求关系变化很快，所以价格仅供参考）：
我们希望在两个目标上达成最优化：最小化价格之和，最大化性能评分之和。直观说就是物美又价廉。
而且为了数学上的方便，我们可以统一用最小化：最小化价格之和，最小化性能评分之和的负值。
车身域控的以上bom中有11种物料，每种从三个候选项选一，那么总共有3*3*3*3*3*3*3*3*3*3*3=3^11 = 177,147种组合。这么大的搜索空间已经超过人力所及，值得用算法。
为方便读者，每种物料的作用也列表如下：
序号 | 部件名称 | 描述 |
1 | 主控芯片（MCU） | SPC56EC74L8 或 Renesas RH850 系列，用于处理复杂的控制逻辑和通信任务 |
2 | PCB板 | 多层印刷电路板，支持高速信号传输和复杂布线 |
3 | 电源管理IC (PMIC) | 提供稳定的电源供应，确保各个模块正常工作 |
4 | 存储器 | 包括闪存（Flash）和随机存取存储器（RAM），用于存储程序和数据 |
5 | CAN/LIN收发器 | 实现与车内其他控制器的通信 |
6 | 射频元器件（射频就是无线电） | 用于无线通信模块，如蓝牙、Wi-Fi等 |
7 | 无源元件 | 电阻、电容、电感等，用于滤波、稳压等功能 |
8 | 接插件 | 连接器和线束，确保与其他系统的物理连接 |
9 | 散热组件 | 散热片或散热风扇，保证芯片在高温环境下稳定运行 |
10 | 外壳 | 金属或塑料外壳，提供机械保护和电磁屏蔽 |
11 | 安全芯片 | 用于加密通信和安全认证，防止未经授权的访问 |
针对3^11 = 177,147种组合的解空间，本文使用NSGA-II（Non-dominated Sorting Genetic Algorithm II）来整数优化寻找近似最优解。
之所以是整数优化，是因为每种物料对备选器件的选择是要么选要么不选，选择是整数化的，不可能出现 某一种物料选0.3的A器件，再选0.5的B器件，再加上0.2的C器件。
下面我们比较正式地介绍NSGA-II优化算法，这是为了实现“可复制性”，需要的读者可以直接复制。
NSGA-II（Non-dominated Sorting Genetic Algorithm II）是一种多目标优化算法，用于在多个目标之间寻找最优解。与传统的单目标遗传算法不同，NSGA-II能够同时处理多个目标，并找到一组非支配解（Pareto最优解）。
1. 基本概念
多目标优化：在一个优化问题中，通常有多个相互冲突的目标。例如，在选择电子元件时，我们希望性能高但成本低，这两个目标通常是相互矛盾的。
非支配解（Pareto最优解）：一组解被称为非支配解，如果不存在其他解在所有目标上都不比它差，并且在至少一个目标上更优。
2. NSGA-II的主要步骤
（1）初始化种群
首先生成初始种群，每个个体表示一个候选解。在这个例子中，每个个体由11个整数变量组成，每个变量取值范围为0到2。
（2）非支配排序
对初始种群中的每个个体进行非支配排序，即将种群分成不同的等级（层）。第一级包含所有非支配解，第二级包含在第一级之后的非支配解，依此类推。
（3）计算拥挤距离
在每个等级内部，计算每个个体的拥挤距离。拥挤距离衡量了个体在其相邻个体中的稀疏程度。距离越大，表示该个体越稀疏，越不容易被其他个体包围。
（4）选择操作
根据非支配排序结果和拥挤距离，选择下一代种群。首先选择第一级的所有个体，直到种群大小达到设定值。如果第一级不足以填满种群，继续选择第二级的个体，依此类推，直到种群大小满足要求。
（5）变异和交叉操作
对新生成的种群进行变异和交叉操作，产生新的候选解。这有助于种群探索搜索空间并保持多样性。
（6）重复迭代
重复上述步骤（非支配排序、拥挤距离计算、选择操作、变异和交叉操作），直到达到预定的迭代次数或收敛条件。
实现代码如下：
首先需要安装pymoo库
这个库pymoo用于Multi-objective Optimization in Python
其自我描述为：Our framework offers state of the art single- and multi-objective optimization algorithms and many more features related to multi-objective optimization such as visualization and decision making. 我们的框架提供先进的单目标和多目标优化算法，以及可视化、决策支持等与多目标优化相关的诸多功能。
安装命令如下：
pip install pymoo
接下来是代码：
import numpy as np
from pymoo.algorithms.moo.nsga2 import NSGA2
from pymoo.core.problem import Problem
from pymoo.factory import get_sampling, get_crossover, get_mutation
from pymoo.optimize import minimize
# 定义问题
class ComponentSelection(Problem):
def __init__(self):
super().__init__(n_var=11, n_obj=2, n_constr=0,
xl=np.zeros(11), # 最小值为0
xu=np.ones(11) * 2) # 最大值为2，0，1，2表示在三个候选项选哪个
def _evaluate(self, x, out, *args, **kwargs):
F = np.zeros((x.shape[0], self.n_obj))
# 性能评分
perf_scores = np.array([
[8, 9, 7], # 主控芯片（MCU）
[8, 9, 10], # PCB板
[7, 8, 9], # 电源管理IC (PMIC)
[8, 9, 7], # 存储器
[8, 9, 7], # CAN/LIN收发器
[9, 8, 7], # 射频元器件
[7, 8, 9], # 无源元件
[8, 7, 9], # 接插件
[8, 9, 7], # 散热组件
[7, 8, 9], # 外壳
[9, 8, 7] # 安全芯片
])
# 价格
prices = np.array([
[200, 250, 180], # 主控芯片（MCU）
[50, 60, 70], # PCB板
[30, 35, 40], # 电源管理IC (PMIC)
[100, 110, 90], # 存储器
[25, 30, 20], # CAN/LIN收发器
[80, 90, 75], # 射频元器件
[0.5, 0.6, 0.45], # 无源元件
[15, 10, 20], # 接插件
[80, 100, 70], # 散热组件
[50, 30, 60], # 外壳
[150, 130, 140] # 安全芯片
])
# 计算总性能评分和总价格
for i in range(x.shape[0]):
perf_sum = -sum(perf_scores[j][int(x[i][j])] for j in range(11)) # 最小化性能评分之和的负值，也就是最大化性能评分之和。.
price_sum = sum(prices[j][int(x[i][j])] for j in range(11))
F[i, 0] = perf_sum
F[i, 1] = price_sum
out["F"] = F
# 使用NSGA-II算法进行优化
algorithm = NSGA2(
pop_size=40,
sampling=get_sampling("int_random"),
crossover=get_crossover("int_sbx", prob=0.9, eta=15),
mutation=get_mutation("int_pm", eta=20),
eliminate_duplicates=True
)
res = minimize(ComponentSelection(),
algorithm,
('n_gen', 50),
seed=1,
verbose=True)
print("Best solutions found: ")
for solution in res.opt:
print(f"Performance Score: {solution.F[0]}, Price: {solution.F[1]}")
return res.opt
这段代码定义了一个问题类`ComponentSelection`，它继承自`pymoo`的`Problem`类，并实现了必要的方法来计算性能评分和价格。我们使用NSGA-II算法来寻找帕累托前沿上的最优解。
运行这段代码后，我们得到一系列帕累托最优解，这些解代表了在性能和成本之间达到最佳平衡的不同选择方案。
可能的输出如下所示：
Best solutions found:
Performance Score: 85.0, Price: 476.55
Performance Score: 86.0, Price: 475.65
Performance Score: 87.0, Price: 474.75
在使用算法得到一组帕累托最优解（数量不超过10个）后，内部评审选择的一种近似最优解BOM如下：
1. 主控芯片（MCU）: Renesas RH850系列 - 这是系统中的主芯片，负责控制整个系统的运行，处理各种输入输出数据，控制各种功能模块的工作。
2. PCB板: 高密度互连PCB - PCB板是电子产品中的基板，用于支持和连接各种电子元件，高密度互连PCB能够提供更好的信号传输和互连性能。
3. 电源管理IC (PMIC): STMicroelectronics L99PMW1 - 电源管理IC负责管理系统的电源供应，提供稳定的电压和电流，确保各个电子元件正常工作。
4. 存储器: Samsung K4B4G1646Q - 存储器用于存储系统运行时的数据和程序，提供临时数据存储和读写功能。
5. CAN/LIN收发器: Infineon TCAN4550D - CAN/LIN收发器用于控制器区域网络（Controller Area Network）和局域互联网络（Local Interconnect Network）通信，实现不同设备之间的数据传输。
6. 射频元器件: Qualcomm QCA6174A - 射频元器件用于处理无线信号的发送和接收，支持设备之间的无线通信和数据传输。
7. 无源元件: Panasonic EEUE3V300J - 无源元件是电路中不具备放大作用的元件，如电阻、电容等，用于电路的补偿、滤波和稳定性调节。
8. 接插件: Amphenol HR10A-10-TFS - 接插件用于连接不同模块或设备之间的信号传输和电源连接，起到连接和分离的作用。
9. 散热组件: Noctua NF-A12x25 PWM - 散热组件用于散热和降温，确保系统长时间稳定运行，防止过热损坏设备。
10. 外壳: IP67 Waterproof Enclosure - 外壳用于保护电子设备免受外部环境的影响，防水外壳可以防止水和湿气侵入，保护内部元件不受损坏。
11. 安全芯片: Infineon OPTIGA TPM SLI 9600 - 安全芯片用于加密和保护系统中的数据和信息安全，防止未经授权的访问和攻击。
据粗略统计，我们将一款车身控制器的物料bom选择从约80人天工作量（含会议，辩论等等），降到了15人天工作量。15人天中有5-6人天是专家团队对各种物料备选项的性能打分和采购询价，有3人天是开发优化程序、调试、输入数据和运行出结果，还有6人天是传统的评审会评估，由于大大缩小了需要评估的物料的组合数量（<10个），所以评审会评估的工作量也大大减少。