Author | Intuitive Solution
Produced by | Automotive Electronics and Software
#01Introduction and Background
Determining the optimal bill of materialsBOM (bill of materials) for a domain controller is a computationally intensive task that requires both quality and cost-effectiveness. Assuming there areM choices for each material, the total number of combinations for allN materials in the domain controller isM raised to the power ofN, which isN multiplied byM. To make a selection from so many options, human resources are insufficient. This article uses metaheuristic optimization algorithms to select the best BOM for vehicle domain controllers, aiming to gain a cost-performance advantage in the fierce market competition.
Vehicle domain controllers are a crucial component of modern automotive electronic systems, responsible for managing and coordinating the operation of various in-vehicle electronic systems and subsystems. Therefore, they include a variety of key materials and components. Below is a list of some main materials (note that not every domain controller will necessarily include all of the following):
1. Microprocessor (MCU)/Microcontroller: This is the core of the domain controller, responsible for executing control algorithms and logic processing tasks. Typically, high-performance32-bit or64-bit processors are used.
2. Application-Specific Integrated Circuit (ASIC): Integrated circuits designed for specific functions, such as power management and signal processing.
3. Programmable Logic Device (PLD)/Field-Programmable Gate Array (FPGA): Used to implement flexible logic functions and rapid prototyping.
4. Memory: Includes RAM (Random Access Memory), ROM (Read-Only Memory), EEPROM (Electrically Erasable Programmable Read-Only Memory), and flash memory, used to store program code, configuration data, and runtime data. For example, during OTA upgrades, the old package and upgrade package are first downloaded to the local memory of the domain controller, allowing for rollback in case of installation failure.
5. Sensor Interfaces: Used to connect and process data from various sensors, such as temperature sensors, pressure sensors, accelerometers, etc.
6. Communication Interfaces: Support hardware interfaces for in-vehicle network protocols such as CAN (Controller Area Network), LIN (Local Interconnect Network), FlexRay, Ethernet, etc. Some advanced ones also have hardware interfaces for in-vehicle Ethernet.
7. Power Management Integrated Circuit (PMIC): Ensures stable voltage for various parts of the domain controller and provides over-voltage and under-voltage protection functions.
8. Isolation Devices: Such as optocouplers and magnetic couplers, used to transmit signals between circuits at different voltage levels or electrically isolated circuits.
9. Cooling Solutions: Including heat sinks, fans, or heat pipes, used to manage the heat generated during the operation of the domain controller.
10. Enclosures and Mechanical Components: Provide physical protection and support for the domain controller, which may include metal housings, mounting brackets, etc.
Each type of device can have different model options, leading to varying prices and performance. In the highly competitive automotive market, optimal cost-performance can provide a competitive advantage.
Assuming there are10 types of devices, each with three options, there are a total of3 raised to the power of10 (=59,049) overall selection schemes. This already exceeds the range that designers can manually calculate.
#02Metaheuristic Algorithms and Multi-Objective Optimization
If an algorithm can face a massive solution space (generally exponential, such as2^N), and find high-quality feasible solutions that are approximately optimal (not absolutely optimal) within a feasible computation time, then this algorithm has industrial application value.
Metaheuristic algorithms are a large class of algorithms that can achieve the above objectives.
Due to their optimization properties, metaheuristic algorithms are used in various aspects of vehicle algorithms, such as in autonomous driving:
Metaheuristic algorithms are most commonly used in autonomous driving for path planning and optimization, including optimizing neural networks to improve object recognition. These algorithms solve complex optimization problems by simulating natural phenomena or biological behaviors (which is why they are called heuristic, indicating inspiration from some objective phenomenon), possessing strong global search capabilities and the ability to escape local optima.
1. Path Planning and Optimization
a. Avoiding Local Minima: Compared to gradient-based algorithms, metaheuristic optimization algorithms are less likely to get trapped in local minima because their exploration phase helps explore different spaces. This makes them very suitable for path planning in dynamic and uncertain environments.
b. Improving Efficiency: The A* algorithm, as a heuristic search method, can provide guidance information for search direction, significantly improving search efficiency, especially when solving the shortest path in large-scale static road networks.
c. Adapting to Complex Environments: Metaheuristic algorithms such as the Firefly Algorithm (FA) can handle complex traffic scenarios and make independent and wise decisions based on real-time data, allowing vehicles to navigate safely in complex environments.
2. Dealing with Uncertainty
a. Handling Input Data Uncertainty: Path planning algorithms rely on the accuracy and completeness of map data and sensor data. However, in practical applications, this data may have uncertainties and errors. Metaheuristic algorithms can address these issues through their robustness, ensuring the reliability of path planning results.
3. Combining with Deep Learning
a. Enhancing Perception Capabilities: Metaheuristic algorithms can also be combined with deep learning technologies, such as using an improved Whale Optimization Algorithm (WOG-YOLO) for object detection, to enhance the understanding and response speed of autonomous vehicles to their surroundings.
b. Optimizing Neural Networks: Metaheuristic algorithms can be used to optimize the weights of neural networks, further enhancing the performance of deep learning models, thereby better supporting the decision-making process of autonomous driving systems.
Why settle for approximate optimal solutions instead of emphasizing absolute optimal solutions?
Because the current peak of human algorithm theory cannot guarantee finding absolute optimal solutions in an extremely large solution space, at least not within a tolerable computation time (polynomial time). We have to settle for finding approximate optimal solutions.
Can you explain what heuristic algorithms are using a heuristic method (metaphor)?
The author wants to use the example of using a sieve to sift chestnuts. After harvesting, small chestnuts are not suitable for making candied chestnuts. Farmers use a sieve to sift chestnuts, allowing smaller ones to fall through, leaving only the larger chestnuts in the sieve. Although farmers do not fully understand this random complex physical process, they know it is effective and can inspire the implementation of a “sifting chestnuts” algorithm.
The more times the sieve is used, the fewer small chestnuts remain in the sieve. This indicates that increasing the number of iterations helps gradually improve the quality of the solution.
Once the number of sifting exceeds a limit, continuing to increase the number of sifting cannot further reduce the number of small chestnuts left in the sieve, or it becomes very uneconomical, requiring hundreds more sifts to reduce just a couple of small chestnuts.This indicates that we should not continue iterating but should end the algorithm and take the best solution found among all solutions as the result..
If we simulate this process with an algorithm, it is inspired by this physical phenomenon. Although we cannot fully confirm the mechanism of this random complex sifting process, we can still achieve optimization effects, that is, sifting out as many small chestnuts as possible. Thus, this algorithm is a heuristic algorithm inspired by sifting chestnuts.
Sometimes, there are multiple optimization objectives, and we need to find Pareto optimal solutions, where improving one objective value must degrade another objective value.
Next, we formally introduce the principles and core concepts of multi-objective optimization:
Multi-Objective Optimization (MOO) refers to the process of finding optimal solutions among multiple objective functions. These objectives are often conflicting; for example, in product design, we may want to minimize costs while maximizing performance, but these two are often contradictory. Therefore, the goal of multi-objective optimization is to find a set of Pareto optimal solutions, which represent situations where no other objective can be improved without degrading another.
The core concepts of multi-objective optimization:
-
Pareto Optimality: A set of solutions is called Pareto optimal if there are no other solutions that are not worse in all objectives and better in at least one objective. The set of Pareto optimal solutions constitutes the Pareto front, which is the collection of all possible Pareto optimal solutions.
-
Metaheuristic Algorithms: Metaheuristic algorithms are a class of optimization algorithms based on heuristic search strategies, typically capable of handling complex and large-scale optimization problems. Common metaheuristic algorithms include Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA), etc.
-
Multi-Objective Metaheuristic Algorithms: To address multi-objective optimization problems, traditional metaheuristic algorithms need to be extended. These extensions typically introduce specific mechanisms to maintain the set of Pareto optimal solutions, such as:
-
Non-Dominated Sorting: In each generation of evolution, individuals in the population are sorted based on the dominance relationship between solutions. A solution dominates another if it is not worse in all objectives and better in at least one objective.
-
Crowding Distance: To address the crowding phenomenon, where many solutions cluster in certain areas of the Pareto front, crowding distance can be used to measure the sparsity of solutions. Solutions with larger crowding distances are considered more diverse.
-
External Archive: To preserve the set of Pareto optimal solutions, ensuring that these important solutions are not lost during the optimization process. The external archive can be of limited size, typically using specific mechanisms to control the size of the archive, such as removing the least important solutions.
For example, when selecting various internal materials for a domain controller, we hope to minimize costs while maximizing performance, resulting in two optimization objectives. The calculated Pareto optimal solutions indicate that if we want to increase performance, we must increase costs, or if we want to reduce costs, we must degrade performance, and we cannot simultaneously reduce costs and increase performance. There can be multiple Pareto optimal solutions.
#03Case Study and Code Implementation
The author is part of a new force heavy truck OEM, designing certain domain controllers, such as power domain controllers, body domain controllers, etc. Taking a body domain controller as an example, we set three alternatives for each material and score each material based on supplier friendliness, past usage experience, performance parameters, etc., organized by internal experts (with a full score of10), resulting in the following table (the prices of chips and other materials change rapidly with supply and demand, so the prices are for reference only):
We aim to optimize on two objectives: minimizing the total price and maximizing the total performance score. Intuitively, this means achieving high quality at a low price.
For mathematical convenience, we can unify the minimization: minimizing the total price and minimizing the negative value of the total performance score.
The above BOM for the body domain controller has11 types of materials, each selected from three candidates, resulting in a total of3*3*3*3*3*3*3*3*3*3*3=3^11 = 177,147 combinations. This large search space exceeds human capability, making it worthwhile to use algorithms.
For the convenience of readers, the functions of each material are also listed below:
|
Index |
Component Name |
Description |
|
1 |
Main Control Chip (MCU) |
SPC56EC74L8 or Renesas RH850 series, used for processing complex control logic and communication tasks |
|
2 |
PCB Board |
Multi-layer printed circuit board, supporting high-speed signal transmission and complex wiring |
|
3 |
Power Management IC (PMIC) |
Provides stable power supply, ensuring normal operation of various modules |
|
4 |
Memory |
Includes flash memory and RAM, used for storing programs and data |
|
5 |
CAN/LIN Transceiver |
Enables communication with other controllers in the vehicle |
|
6 |
RF Components (RF refers to radio frequency) |
Used for wireless communication modules, such as Bluetooth and Wi-Fi |
|
7 |
Passive Components |
Resistors, capacitors, inductors, etc., used for filtering, voltage stabilization, etc. |
|
8 |
Connectors |
Connectors and wiring harnesses, ensuring physical connections with other systems |
|
9 |
Cooling Components |
Heat sinks or cooling fans, ensuring stable operation of chips in high-temperature environments |
|
10 |
Enclosure |
Metal or plastic enclosure, providing mechanical protection and electromagnetic shielding |
|
11 |
Security Chip |
Used for encrypting communication and ensuring data security, preventing unauthorized access |
For the solution space of3^11 = 177,147 combinations, this article uses NSGA-II (Non-dominated Sorting Genetic Algorithm II) for integer optimization to find approximate optimal solutions.
The reason for integer optimization is that the selection of alternative devices for each material is binary; it is either selected or not selected. It is not possible to select 0.3 of device A, then select0.5 of device B, and then add0.2 of device C.
Next, we formally introduce the NSGA-II optimization algorithm, which is necessary for achieving “replicability”; interested readers can directly copy it.
NSGA-II (Non-dominated Sorting Genetic Algorithm II) is a multi-objective optimization algorithm used to find optimal solutions among multiple objectives. Unlike traditional single-objective genetic algorithms, NSGA-II can handle multiple objectives simultaneously and find a set of non-dominated solutions (Pareto optimal solutions).
1. Basic Concepts
-
Multi-Objective Optimization: In an optimization problem, there are usually multiple conflicting objectives. For example, when selecting electronic components, we want high performance but low cost, which are often contradictory objectives.
-
Non-Dominated Solutions (Pareto Optimal Solutions): A set of solutions is called non-dominated if there are no other solutions that are not worse in all objectives and better in at least one objective.
2. Main Steps of NSGA-II
(1) Initialize Population
First, generate the initial population, where each individual represents a candidate solution. In this example, each individual consists of11 integer variables, each ranging from0 to2.
(2) Non-Dominated Sorting
Perform non-dominated sorting on each individual in the initial population, dividing the population into different levels (layers). The first level contains all non-dominated solutions, the second level contains non-dominated solutions after the first level, and so on.
(3) Calculate Crowding Distance
Within each level, calculate the crowding distance for each individual. Crowding distance measures the sparsity of individuals among their neighboring individuals. The larger the distance, the sparser the individual, making it less likely to be surrounded by other individuals.
(4) Selection Operation
Based on the non-dominated sorting results and crowding distance, select the next generation population. First, select all individuals from the first level until the population size reaches the set value. If the first level is insufficient to fill the population, continue selecting individuals from the second level, and so on, until the population size meets the requirements.
(5) Mutation and Crossover Operations
Perform mutation and crossover operations on the newly generated population to produce new candidate solutions. This helps the population explore the search space and maintain diversity.
(6) Repeat Iteration
Repeat the above steps (non-dominated sorting, crowding distance calculation, selection operation, mutation and crossover operations) until the predetermined number of iterations or convergence conditions are met.
The implementation code is as follows:
First, install thepymoo library
This librarypymoo is used for Multi-objective Optimization in Python
It self-describes as: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.我们的框架提供先进的单目标和多目标优化算法，以及可视化、决策支持等与多目标优化相关的诸多功能。
The installation command is as follows:
pip install pymoo
Next is the code:
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
# Define Problem
class ComponentSelection(Problem):
def __init__(self):
super().__init__(n_var=11, n_obj=2, n_constr=0,
xl=np.zeros(11), # Minimum value is0
xu=np.ones(11) * 2) # Maximum value is2,0,1,2 indicates which of the three candidates to select
def _evaluate(self, x, out, *args, **kwargs):
F = np.zeros((x.shape[0], self.n_obj))
# Performance Scores
perf_scores = np.array([
[8, 9, 7], # Main Control Chip (MCU)
[8, 9, 10], # PCB Board
[7, 8, 9], # Power Management IC (PMIC)
[8, 9, 7], # Memory
[8, 9, 7], # CAN/LIN Transceiver
[9, 8, 7], # RF Components
[7, 8, 9], # Passive Components
[8, 7, 9], # Connectors
[8, 9, 7], # Cooling Components
[7, 8, 9], # Enclosure
[9, 8, 7] # Security Chip
])
# Prices
prices = np.array([
[200, 250, 180], # Main Control Chip (MCU)
[50, 60, 70], # PCB Board
[30, 35, 40], # Power Management IC (PMIC)
[100, 110, 90], # Memory
[25, 30, 20], # CAN/LIN Transceiver
[80, 90, 75], # RF Components
[0.5, 0.6, 0.45], # Passive Components
[15, 10, 20], # Connectors
[80, 100, 70], # Cooling Components
[50, 30, 60], # Enclosure
[150, 130, 140] # Security Chip
])
# Calculate Total Performance Scores and Total Prices
for i in range(x.shape[0]):
perf_sum = -sum(perf_scores[j][int(x[i][j])] for j in range(11)) # Minimizing the negative value of the total performance score, which is equivalent to maximizing the total performance score..
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
# UsingNSGA-II algorithm for optimization
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
This code defines a problem class`ComponentSelection`, which inherits from`pymoo`‘s`Problem` class and implements the necessary methods to calculate performance scores and prices. We useNSGA-II algorithm to find optimal solutions on the Pareto front.
After running this code, we obtain a series of Pareto optimal solutions, representing different options that achieve the best balance between performance and cost.
Possible output is as follows:
Best solutions found:
Performance Score: 85.0, Price: 476.55
Performance Score: 86.0, Price: 475.65
Performance Score: 87.0, Price: 474.75
#04Conclusion
After using the algorithm to obtain a set of Pareto optimal solutions (no more than10), an internally reviewed approximate optimal solution BOM is as follows:
1. Main Control Chip (MCU): Renesas RH850 series – This is the main chip in the system, responsible for controlling the operation of the entire system, processing various input and output data, and controlling the operation of various functional modules.
2. PCB Board: High-Density Interconnect PCB – The PCB board is the substrate in electronic products, used to support and connect various electronic components. High-density interconnect PCBs can provide better signal transmission and interconnection performance.
3. Power Management IC (PMIC): STMicroelectronics L99PMW1 – Power Management IC is responsible for managing the power supply of the system, providing stable voltage and current, ensuring the normal operation of various electronic components.
4. Memory: Samsung K4B4G1646Q – Memory is used to store runtime data and programs, providing temporary data storage and read/write functions.
5. CAN/LIN Transceiver: Infineon TCAN4550D – CAN/LIN transceiver is used for communication in the Controller Area Network (CAN) and Local Interconnect Network (LIN), enabling data transmission between different devices.
6. RF Components: Qualcomm QCA6174A – RF components are used for processing the transmission and reception of wireless signals, supporting wireless communication and data transmission between devices.
7. Passive Components: Panasonic EEUE3V300J – Passive components are elements in the circuit that do not amplify, such as resistors and capacitors, used for compensation, filtering, and stability adjustment in circuits.
8. Connectors: Amphenol HR10A-10-TFS – Connectors are used for signal transmission and power connection between different modules or devices, serving the purpose of connecting and separating.
9. Cooling Components: Noctua NF-A12x25 PWM – Cooling components are used for heat dissipation and cooling, ensuring the system operates stably for long periods and preventing overheating damage to devices.
10. Enclosure: IP67 Waterproof Enclosure – Enclosures are used to protect electronic devices from external environmental influences. Waterproof enclosures can prevent water and moisture from entering, protecting internal components from damage.
11. Security Chip: Infineon OPTIGA TPM SLI 9600 – Security chips are used for encrypting and protecting data and information security in the system, preventing unauthorized access and attacks.
According to rough statistics, we reduced the workload of selecting materials for a body controller from about80 person-days (including meetings, debates, etc.) to15 person-days. Of the 15 person-days, 5-6 are for expert teams scoring various material options and procurement inquiries, 3 person-days are for developing optimization programs, debugging, inputting data, and running results, and 6 person-days are for traditional review meetings. Due to the significant reduction in the number of material combinations that need to be evaluated (<10), the workload for review meetings has also been greatly reduced.
