CN-122021490-A - High-dimensional constraint multi-objective Bayesian optimization method based on Voronoi tree search

Abstract

The invention belongs to the field of integrated circuit computer aided design/electronic design automation, and relates to a comprehensive and efficient Voronoi tree searching multi-target Bayesian optimization method for a high-dimensional analog integrated circuit. Firstly, quick non-dominant sorting is carried out on an observation point set, and two clusters are carried out on the observation points according to sorting labels to determine the segmentation boundary of the Voronoi tree, so that the high-potential leaf nodes containing the pareto solution set are recursively halved, and the multi-target Voronoi tree can be constructed. Traversing the Voronoi tree by a gradient gambling algorithm can achieve efficient exploration of a high-dimensional design space. In the local development stage, we propose to efficiently advance the pareto solution set along the radial direction of the pareto curved surface based on the acquisition function of the pareto front desired lifting/probability lifting. The method not only has higher sampling efficiency and lower calculation complexity, but also has the quality and diversity of the pareto front edge which are obviously superior to those of the currently mainstream multi-objective optimization algorithm.

Inventors

• ZENG XUAN
• Bi Chaori
• YAN CHANGHAO
• YANG FAN
• ZHAO AIDONG
• YANG XIHAN

Assignees

• 复旦大学

Dates

Publication Date

20260512

Application Date

20241110

Claims (3)

1. 1. A high-dimensional band-constrained multi-objective Bayesian optimization method based on Voronoi tree search, It is characterized in that the method comprises the steps of, Firstly, carrying out rapid non-dominant sorting on an observation point set, carrying out secondary clustering on the observation points according to sorting labels to determine the segmentation boundary of the Voronoi tree, and carrying out binary division on high-potential leaf nodes containing the pareto solution set in a recursion mode so as to construct a multi-target Voronoi tree; Traversing the Voronoi tree through a gradient gambling algorithm can realize efficient exploration of a high-dimensional design space, and provides a dispersion batch selection strategy of Voronoi units so as to ensure diversity of pareto solution sets; in a local development stage, we propose to efficiently advance the pareto solution set along the radial direction of the pareto curved surface based on the acquisition function of the pareto front expected lifting/probability lifting; Experimental results show that the high-dimensional multi-objective Bayesian optimization algorithm based on Voronoi tree search has higher sampling efficiency and lower calculation complexity, and meanwhile, the quality and diversity of the pareto front edge obtained by the method are obviously superior to those of the multi-objective optimization algorithm of the current main stream.
2. 2. The method of claim 1, comprising the steps of: The method comprises the steps of 1, carrying out design space decomposition through dynamic establishment of a Voronoi tree, carrying out high-dimensional design space decomposition according to a hierarchical Voronoi tree structure, and redesigning strategies such as path selection (path selection), branch expansion (branch expansion), reward back-propagation (reward) and the like aiming at the characteristics of a multi-objective optimization problem with constraint; If the number of observation points in a certain target leaf node reaches the maximum node size N leaf , clustering the observation points into 'good' and 'bad' Voronoi clusters by a K-means method, dividing the leaf node into two new child nodes, and simultaneously continuing to grow the Voronoi tree tau; Step 2, global space exploration is carried out through Voronoi tree search, the establishment of the Voronoi tree T converts the global exploration problem of the high-dimensional space into a tree search problem, and the Voronoi tree is searched from a root node The selected path can determine a promising leaf node v * to find a Voronoi cluster with high potential; Step 3, bulk selection of high-potential Voronoi units, clustering the Voronoi units on the pareto front in a performance space in order to realize efficient parallel sampling and ensure diversity of the pareto front at the same time, and then selecting the Voronoi unit Vor (x k,* ) with the largest super-volume contribution from each type k for local development; The method comprises the steps of step 4, carrying out local development through multi-objective Bayesian optimization with constraint, firstly estimating the shape of the pareto curved surface according to the position of the center point of the pareto curved surface for the local development, then generating a circuit simulation point of the next round in a selected Voronoi unit Vor (x k,* ) through an acquisition function for maximizing the expected lifting (EPFI) of the pareto front or the lifting (PPFI) of the pareto front probability, and adopting feasibility probability (PoF) to process black box constraint for the problem with constraint.
3. 3. The method of claim 2, wherein in said step 2, the preference value of the node is updated by a reward back propagation mechanism according to the reward value Rt in the following manner: Wherein, the If the newly generated observation point in the target node belongs to the pareto solution set in the t round of iteration, the reward value R t =1 of the t round exists, otherwise, R t =0; The method comprises the steps of obtaining an average rewarding value in the previous t rounds of iteration, enabling two newly generated child nodes to be accessed with the same probability in an initial state, enabling the probability of a system to access a high-potential node containing a pareto optimal solution to be gradually increased along with the progress of iteration through the reinforcement learning process, enabling the probability of accessing a dominant unfavorable node to be gradually reduced, enabling the probability of being accessed of the two child nodes to be equivalent when the left child node and the right child node contain partial pareto solution sets, and avoiding the abnormal deformation of the pareto curved surface shape caused by continuously accessing a single node in a certain period by using a UCT function.

Description

High-dimensional constraint multi-objective Bayesian optimization method based on Voronoi tree search Technical Field The invention belongs to the technical field of integrated circuit Computer aided design/electronic design automation (Computer AIDED DESIGN/Electronic DesignAutomatic CAD/EDA), and particularly relates to a high-dimensional band constraint multi-objective Bayesian optimization method based on Voronoi tree search for high-dimensional analog circuit synthesis in analog integrated circuit design automation. Background It is documented that optimizing a plurality of competing black box objective functions is a common mathematical problem in analog circuit design or other engineering applications. For example, in the design of operational circuits, engineers typically strive to optimize a number of key performance metrics, such as unity Gain bandwidth UGF and power consumption I q, while meeting the constraints of Gain 100dB, phase margin PM 60 and slew rate SR 5V/μs. Whereas evaluation of circuit performance typically requires expensive circuit simulations. In this case, the importance of the sample-efficient multi-objective optimization (MOO) algorithm is particularly prominent. Multi-objective bayesian optimization (multi-objective Bayesian optimization, MOBO) has proven to have high sampling efficiency for solving the expensive black box optimization problem of low dimensions. However, for the high-dimensional constrained multi-objective optimization problem, the multi-objective bayesian optimization approach faces three key challenges: (1) High-dimensional design space most existing multi-objective bayesian optimization methods can only handle small-scale problems with less than 20 design variables. As the dimensions of the design variables increase, the size of the design space grows in geometric progression. In a high-dimensional huge design space, the distribution of observation points is sparse, and the average distance between the observation points is increased. The modeling accuracy of the Gaussian process model is seriously influenced by sparse observation points, so that most of regions of the model in space have larger posterior uncertainty, and the Bayesian optimization blindly explores the whole space due to weakening of model guiding significance, so that the model is difficult to focus on the high-potential subregions. (2) The high computational complexity of multi-objective Bayesian optimization mainly comes from training of a Gaussian process model and optimization of a multi-objective acquisition function. The training complexity of the Gaussian process model and the number N of observation points are increased in a square level, namelyAnd for the multi-objective optimization problem with constraints, we typically need to train a separate gaussian process model for each optimization objective and constraint, which further increases the training cost of the model. Furthermore, the optimization of the multi-objective acquisition function is yet another time bottleneck for multi-objective bayesian optimization. The mainstream multi-objective acquisition functions can be largely divided into two categories, an entropy search (entropy search based) based acquisition function and a super-volume lifting (hypervolume improvement based) based acquisition function. The entropy search based acquisition function (e.g., multi-objective maximum entropy search MESMO [1 ]) does not have an explicit analytical formula, and its numerical approximation involves time-consuming Monte Carlo integration (Monte Carlo integration), which is computationally expensive. And for highly uncertain gaussian process models in a high dimensional design space, the numerical integration method has difficulty capturing small differences in the trend of the acquisition function. The acquisition function based on the hypervolume lifting, such as the hypervolume expected lifting function (expected hypervolume improvement, EHVI) [2], requires expensive hypervolume calculation, while the calculation complexity of the hypervolume increases exponentially with the number of optimization targets M, such as the complexity of the hypervolume calculation method using the square decomposition (box decomposition) in the commonly used BoTorch package isWhere n is the number of observation points in the pareto solution set. This limits its usefulness in multi-objective optimization problems with large objective numbers (M≥3). Furthermore, the supersvolume expected lifting function EHVI also does not have an explicit computational expression, and its expected value still needs to be approximated by means of monte carlo integration, which further exacerbates the excessive consumption of computational resources by this approach. (3) The number of optimization targets and the strict black box constraint are that the number of observation points in the pareto solution set is exponentially increased due to the increase of the numbe