• 欢迎访问速搜资源吧,如果在网站上找不到你需要的资源,可以在留言板上留言,管理员会尽量满足你!

【速搜问答】确定性算法是什么

问答 admin 9个月前 (04-13) 157次浏览 已收录 0个评论

汉英对照:
Chinese-English Translation:

确定性算法是利用问题的解析性质,产生一确定的有限或无限点序列使其收敛于全局最优解。这类方法依据某一确定性策略搜索局部极小,并试图跳跃已获得的局部极小而达到某个全局最优点,能充分利用问题的解析性质,从而计算效率高。

Deterministic algorithm is to use the analytical properties of the problem to generate a certain sequence of finite or infinite points to make it converge to the global optimal solution. This kind of method searches the local minima according to a certain deterministic strategy, and tries to jump the local minima that have been obtained to achieve a global optimum. It can make full use of the analytical properties of the problem and thus has high computational efficiency.

确定性算法是利用问题的解析性质,产生一确定的有限或无限点序列使其收敛于全局最优解。这类方法依据某一确定性策略搜索局部极小,并试图跳跃已获得的局部极小而达到某个全局最优点,能充分利用问题的解析性质,从而计算效率高。

Deterministic algorithm is to use the analytical properties of the problem to generate a certain sequence of finite or infinite points to make it converge to the global optimal solution. This kind of method searches the local minima according to a certain deterministic strategy, and tries to jump the local minima that have been obtained to achieve a global optimum. It can make full use of the analytical properties of the problem and thus has high computational efficiency.

如填充函数法、打洞函数法、D.C.规划算法、区间法、单调规划、分支定界方法和积分水平集方法等,这些算法的构造都涉及到已知目标函数的某些局部性质或者全局性质。其中,函数的连续性、可微性认为是局部性质,而凸性、单调性、稠密性、等度连续性、李普希兹连续、水平集等通常称为全局性的解析性质。

Such as filling function method, hole function method, D.C. programming algorithm, interval method, monotone programming, branch and bound method and integral level set method, the construction of these algorithms all involve some local or global properties of the known objective function. Among them, the continuity and differentiability of functions are considered as local properties, while convexity, monotonicity, density, equicontinuity, Lipschitz continuity and level set are generally called global analytical properties.

填充函数法

Filled function method

填充函数是由西安交通大学的 R.Ge(葛仁溥)教授首先提出的,填充函数法充分地利用了函数在可行域上的局部性质。

Filled function is first proposed by Professor Ge Renpu of Xi’an Jiaotong University. Filled function method makes full use of the local properties of function in feasible region.

由填充函数的定义可以看出,如果当前极小点不是全局极小点的话,通过极小化填充函数则可以跳出原问题当前局部极小点,并到达一个原问题函数值比当前局部极小值还要小的点。因此,从该点出发极小化原问题目标函数,必将导致一个原问题目标函数值更小的局部极小点。

From the definition of filled function, we can see that if the current minimum is not the global minimum, by minimizing the filled function, we can jump out of the current local minimum of the original problem and reach a point where the function value of the original problem is smaller than the current local minimum. Therefore, minimizing the objective function of the original problem from this point will lead to a local minimum point with smaller value of the objective function of the original problem.

填充函数算法由两个阶段组成:极小化阶段和填充阶段。这两个阶段交替使用直到找不到更好的局部极小点。在第一阶段里,可以用经典的极小化算法寻找目标函数的一个局部极小值点

The filled function algorithm consists of two phases: minimization phase and filling phase. These two stages are used alternately until no better local minima can be found. In the first stage, the classical minimization algorithm can be used to find a local minimum of the objective function

填充函数的优点是较多地利用了函数的性质,所以收敛速度比较快,算法的设计和执行也相对容易;缺点是填充函数过多依赖一些未知参数,这就增加了算法设计之前的工作量,要经大量的实验,来确定参数的取值范围,以确保能找到满意的全局最优解,而且填充函数利用的是线搜索,所以对寻找低盆谷的点也有很大的难度。

The advantage of the filled function is that it makes more use of the properties of the function, so the convergence speed is faster, and the design and implementation of the algorithm is relatively easy; the disadvantage is that the filled function relies too much on some unknown parameters, which increases the workload before the algorithm design. A large number of experiments are needed to determine the range of parameters, so as to ensure that a satisfactory global optimal solution can be found, and the filled function is easy to implement The function uses line search, so it is very difficult to find the point of low basin valley.

打洞函数法

Hole function method

打洞函数法是由 Levy 和 Montalvo 在 1985 年首先提出的,它由一系列循环组成,每个循环包括两个阶段:局部极小化阶段和打洞阶段。

The hole function method was first proposed by Levy and Montalvo in 1985. It consists of a series of cycles. Each cycle includes two stages: local minimization stage and hole drilling stage.

首先是极小化阶段,由一个初始点出发,应用局部极小化算法,求得 f(x)的一局部极小点

The first stage is the minimization stage. Starting from an initial point, a local minimization algorithm is applied to obtain a local minimization point of F (x)

这里

here

采用适当极小化打洞函数的方法找到一个局部极小点 x’,并对其进行讨论:

A local minimum x ‘is found by properly minimizing the hole function

(1) 如果 x’=

(1) If x ‘=

(2) 如果 x’≠

(2) If x ‘≠

这里,

here,

(3) 如果 f(x’)≤f(

(3) If f (x ‘) ≤ f(

打洞函数存在下述缺陷:

The hole function has the following defects

(1) 极的强度

(1) The strength of the pole

(2) 打洞函数可能找到另一局部极小点 x’,成立 f(x’)≥f(

(2) The hole function may find another local minimum x ‘, f (x’) ≥ F(

(3) 极的增加会引起打洞函数成为平坦,这时候极小点很难求。

(3) The increase of the minimum will cause the hole function to be flat, and the minimum is difficult to find.

D.C.规划算法

D. C. planning algorithm

通过引入变量 t,下面的 D.C.规划问题:

By introducing the variable t, the following D.C. programming problem is solved

可以转化为等价的凹极小化问题(记为问题(4)):

It can be transformed into an equivalent concave minimization problem (denoted as problem (4)):

显然,目标函数

Obviously, the objective function

因此,对于任一 D.C.规划问题都可以通过凹极小化算法求解。对于凹极小化问题,人们已经提出了一些算法,这些算法多以分枝定界技巧、割平面方法、最优性条件和整数规划等方法为基础,且它们的有效性依赖于所要解决问题的结构特点。

Therefore, any D.C. programming problem can be solved by concave minimization algorithm. For concave minimization problems, some algorithms have been proposed, which are based on branch and bound techniques, cut plane methods, optimality conditions and integer programming, and their effectiveness depends on the structural characteristics of the problem to be solved.

区间方法

Interval method

区间方法考虑的是问题(2),其基本思想是以区间分析为基础,按照区间算术运算规则用区间变量代替点变量进行区间计算,并将分支定界法和 Moore-Skelboe 算法等方法相结合。对这类算法,Moore 首次提出区间全局优化这一概念。在这一研究领域里,所有的算法都包含精确区间计算,以及算法的执行效率依赖于目标函数、梯度和约束区间扩张的构造方法。这类方法一般分为五个基本步骤:定界、分支、终止、删除和分裂。其中包括区间分裂规则、删除规则及区间选择规则,不同的区间算法在于这几种规则的不同处理手段上。

The basic idea of interval method is based on interval analysis, using interval variable instead of point variable to calculate interval according to interval arithmetic operation rules, and combining branch and bound method with Moore skelboe algorithm. For this kind of algorithm, Moore first proposed the concept of interval global optimization. In this research area, all algorithms include accurate interval calculation, and the efficiency of the algorithm depends on the construction methods of objective function, gradient and constrained interval expansion. This kind of method is generally divided into five basic steps: delimitation, branching, termination, deletion and splitting. It includes interval splitting rules, deletion rules and interval selection rules. Different interval algorithms are based on different processing methods of these rules.

区间方法和其他方法(即以点搜索方式产生近似点序列)相比,它的突出优点是对于低维空间中全局优化问题,能在给定精度内求出问题的全部全局极小点。特别地,对于二维空间中的单变量目标函数,建立了计算效率很高的求一元函数全局极小的区间斜率算法。缺点是当用于高维全局优化问题时,算法的计算量很大,对于区间分裂规则、删除规则及区间选择规则以及它们的检验条件的确定,难度都很大。

Compared with other methods (i.e. generating approximate point sequence by point search), interval method has the outstanding advantage that for global optimization problems in low dimensional space, it can find all global minima within a given precision. In particular, for the univariate objective function in two-dimensional space, a highly efficient interval slope algorithm for global minimization of univariate function is established. The disadvantage is that when applied to high-dimensional global optimization problems, the algorithm has a large amount of computation, and it is very difficult to determine the interval splitting rules, deletion rules, interval selection rules and their test conditions.

分支定界方法

branch-and-bound procedure

在分支定界算法中,可行域得到松弛,并且把原区域逐次分割成越来越多的小区域,这个过程称为分支;在这些小区域内,确定目标函数的下界和上界,这个过程称为定界。在算法的某个阶段,对于在其内下界大于当前最小的上界的小区域,将其删除,这个过程称为剪支,因为这些小区域中显然不包含最优解。随着分支越来越细,最小上界的不断下降,最大下界的不断上升,当最大下界和最小上界之差趋于零,同时细分的小区域收缩为一个点时,我们可以得到目标函数的全局极小值和全局极小点。

In the branch and bound algorithm, the feasible region is relaxed, and the original region is divided into more and more small regions step by step, which is called branch; in these small regions, the lower and upper bounds of the objective function are determined, which is called bound. At a certain stage of the algorithm, small regions whose inner and lower bounds are larger than the current minimum upper bounds are deleted. This process is called pruning, because these small regions obviously do not contain the optimal solution. When the difference between the maximum lower bound and the minimum upper bound tends to zero, and the subdivision region shrinks to a point, we can get the global minimum and the global minimum of the objective function.

各种分支定界算法在求解连续变量的全局最优化问题时,有如下共同的特点:

All kinds of branch and bound algorithms have the following common characteristics in solving global optimization problems with continuous variables

(1) 对目标函数和可行域有较高的要求,以便于分支和定界。算法的效率与分支和定界方法的效率紧密相关。

(1) There are higher requirements for the objective function and feasible region to facilitate the branching and demarcation. The efficiency of the algorithm is closely related to the efficiency of branch and bound methods.

(2) 在算法实施时,需要储存越来越多的细分的小区域和目标函数在其上的下界,这使得在编程时,对数据结构的选择、计算机内存的使用提出了更高的要求。

(2) In the implementation of the algorithm, it is necessary to store more and more subdivided small areas and the upper and lower bounds of the objective function, which makes higher requirements for the selection of data structure and the use of computer memory in programming.


速搜资源网 , 版权所有丨如未注明 , 均为原创丨转载请注明原文链接:【速搜问答】确定性算法是什么
喜欢 (0)
[361009623@qq.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址