CN-122021491-A - Gao Weibei phyllos optimization algorithm based on Voronoi diagram migration

Abstract

The invention belongs to the field of integrated circuit computer aided design/electronic design automation, and particularly relates to a Gao Weibei leaf optimization algorithm based on Voronoi diagram migration. The method maps the continuous design space into an undirected connection graph, and realizes global exploration of the design space through the wandering operation of an upper confidence boundary (upper confidence bound, UCB) function on the graph. For the actual circuit optimization problem or other inherent low-dimensional problems, a local feature extraction method based on slice inverse regression is introduced, next simulation query points are generated in an effective subspace, and the sampling efficiency of an algorithm is further improved. The VGT algorithm is a high-dimensional optimization algorithm which is popularized to 1000D in the ultra-high-dimensional scale at present.

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 Gao Weibei leaf optimization algorithm based on Voronoi graph migration is characterized in that a VGT algorithm maps a continuous design space into an undirected connection graph, and global exploration of the design space is realized through the migration operation of an upper confidence boundary (upper confidence bound, UCB) function on the graph; For the actual circuit optimization problem or other internal low-dimensional problems, a local feature extraction method based on slice inverse regression is introduced, and next simulation query points are generated in an effective subspace, so that the sampling efficiency of an algorithm is further improved; the VGT algorithm is a high-dimensional optimization algorithm which is popularized to 1000D in the ultra-high-dimensional scale at present.
2. 2. The method of claim 1, wherein the VGT algorithm first decomposes the design space x into a plurality of convex Voronoi cells using a Voronoi diagram, then maps it into an undirected diagram according to the adjacency between nodes in the Voronoi diagram, and continuously finds a path leading to global optima along the valley bottom where the objective function value is better by iteratively performing operations such as path selection (path selection), local bayesian optimization (localBO sampling), and expansion and propagation (graph expansion) of the diagram in the diagram.
3. 3. The method of claim 2, wherein, in the local bayesian optimization operation, voronoi cells corresponding to the selected high potential neighbor nodes are generated Performing local Bayesian optimization to generate a new observation point; To reduce the high computational complexity of the gaussian process model, a partial gaussian process (Voronoi neighbored Gaussian process, VNGP) model based on Voronoi neighbors is proposed, i.e. employing only a subset of neighbors of the target node Modeling is carried out; Since the correlation defined by the kernel function of the Gaussian process model decays exponentially with increasing distance between observation points, the observation points farther from the target Voronoi unit have very little contribution to the local modeling in the Voronoi unit, the VNGP model fully utilizes the adjacency provided by the Vorono undirected graph, can greatly reduce the calculation cost while maintaining the local modeling accuracy, and then, the model is applied to the Voronoi unit Internal optimization obtaining function to generate new observation points To realize efficient sampling, the method adopts observation points Sampling the objective function for a centered Gaussian distribution, as shown by the black dashed oval in FIG. 3 (c), using a bin falling on the target The inner sample points adjust the superparameter of the sampling distribution, and the sample points falling outside the target Voronoi unit are discarded.

Description

Gao Weibei phyllos optimization algorithm based on Voronoi diagram migration 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 Gao Weibei phyllos optimization algorithm based on Voronoi diagram migration in analog integrated circuit design automation. Background The performance of Gao Weibei phyllss optimization algorithms decays exponentially with increasing design space dimensions, affected by dimensional disasters in high-dimensional design space. On one hand, sparse observation data in a high-dimensional design space severely limits the accuracy of a gaussian process model, and it is difficult to effectively capture the topography of an objective function through limited observation points, thereby leading to blind exploration of the high-dimensional design space. On the other hand, the training complexity of the gaussian process model increases in cubic scale with increasing number of observation points, however, the solution of the high-dimensional problem is usually accompanied by a large number of observation points, which further aggravates the computational cost of bayesian optimization in solving the high-dimensional problem. The convergence performance of bayesian optimization algorithms depends heavily on the accuracy of gaussian process models, and it is not practical to build reliable proxy models with limited observation data in high-dimensional space. The main stream Gao Weibei phyllus optimization algorithm aims at improving the credibility of a Gaussian process model in the solving thought of the high-dimensional problem, so that the sampling efficiency of Bayesian optimization is improved. The method based on dimension decoupling tries to fit a high-dimensional objective function by using a set of low-dimensional additive Gaussian process models, and converts the high-dimensional problem into a form of adding a set of low-dimensional functions. The subspace embedding-based method projects a high-dimensional input space into a low-dimensional hidden space through linear or nonlinear mapping for modeling and optimization. Both of the above methods fit a low-dimensional manifold (low-dimensional manifold) of the objective function in a low-dimensional subspace using a gaussian process model. While the trust domain approach gradually increases the trust of the proxy model in the trust domain through the limitation of local trust, it is still computationally expensive and impractical to build a reliable local model for the high-dimensional optimization problem of hundreds or even thousands of dimensions. The multi-start point driven local search algorithm is a common idea for solving the high-dimensional optimization problem at present. The local search algorithm continuously adjusts the search direction (search direction) and step size (STEP LENGTH) of the next step from a certain initial point, so as to continuously find better solutions. Line search and trust domains are two types of commonly used local search algorithms. However, the final convergence performance of such methods is heavily dependent on the choice of initial point. Based on the state of the art, the inventors of the present application propose a Gao Weibei leaf optimization algorithm based on Voronoi diagram walk (Voronoi GRAPH TRAVERSAL, VGT). We have focused on generalizing bayesian optimization to hundreds to thousands of dimensions of the ultra-high dimensional space. Since it is not realistic to accurately describe high-dimensional function landscapes purely by means of proxy models in a high-dimensional space, we convert the solution ideas of the problem, do not pursue improving the accuracy of the gaussian process model any more, but fully utilize boundary information and adjacency relations provided by Voronoi diagrams to guide optimization. The Zhang Ji provides a sample efficient Voronoi diagram walk (Voronoi GRAPH TRAVERSAL, VGT) algorithm for solving hundreds to thousands of dimensions of high-dimensional black-box optimization problems. VGT first uses Voronoi diagram to design spaceDecomposing into a plurality of convex Voronoi units, mapping the Voronoi units into an undirected graph according to the adjacency relation among nodes in the Voronoi graph, and continuously finding a path which leads to global optimization along the valley bottom with better objective function value by iteratively executing path selection (path selection), local Bayesian optimization (local BO sampling), graph expansion and propagation (propagation) and the like in the graph. Reference is made to: [1]Li K C.Sliced Inverse Regression for Dimension Reduction[J].Journal of the American Statistical Association,1991,86(414):316–327. [2]Contal E,Buffoni D,Robicquet A,et al.Parallel Gaussian process optimization with upper confidence bound and pure exploration[C].Pro