2024年4月27日发(作者：)
计算机时代2021年第5期
·1·
DOI:10.16644/33-1094/tp.2021.05.001
DIRECT算法及其实现
葛仁磊，王亚男，王毅，张明浩
(海洋石油工程股份有限公司，山东青岛266500)
关键词：
为了有效地解决传统Lipschitz函数极值求解方法向高维推广时遇到的复杂度及计算量急剧增加的问题，
DIRECT算法使用超矩形的中心点替代顶点，降低了算法的复杂度及运算量。在进行初始化后，迭代进行“查找潜在超矩
形”和“细分超矩形”，直至运算结果满足要求。本文从实用角度出发，对该算法的原理及实现的细节进行了全面介绍，并
对算法进行了实现，验证了算法的可行性。
关键词：
DIRECT算法；全局优化；细分超矩形；潜在超矩形
中图分类号：TP312文献标识码：A文章编号：1006-8228(2021)05-01-05
DIRECTalgorithmanditsPythonimplementation
GeRenlei,WangYanan,WangYi,ZhangMinghao
（OffshoreOilEngineeringCo.,Ltd.,Qingdao,Shandong266500,China）
Abstract：Inordertoeffectivelysolvetheproblemthatthecomplexityandcalculationincreasesharplywhenthetraditional
Lipschitzfunctionextremumsolvingmethodisextendedtohighdimension,DIRECTalgorithmusesthecenterpointofhyper-
rectanglestoreplacethevertices,nitialization,iteratively
"findingpotentiallyoptimalhyper-rectangles"and"subdividingthehyper-rectangles"untilthecalculationresultsmeetthe
paper,fromthepracticalpointofview,theprincipleandimplementationdetailsofthealgorithmare
comprehensivelyintroduced,andthealgorithmisimplementedtoverifyitsfeasibility.
Keywords：DIRECTalgorithm;globaloptimization;subdividingthehyper-rectangle;potentiallyoptimalhyper-rectangle
0引言
DIRECT（DIvidingRECTangles，细分矩形法）算法
是属于Lipschitz函数在有限区间内极值问题的一种求
解方法，其本质是一种采样算法。DIRECT算法不需
要求解目标函数的参数，非常适合于黑箱函数的优化
仿真。本文抛开DIRECT算法的技术与理论细节，展示
其具体实现，使得读者能够对照本文快速实现应用，
并在文章最后给出实际案例以供参考。
1
K
为则称
f
(
x
)
为区间
[
a,b
]
上的Lipschitz函数，
Lipschitz常数，所有满足条件中的
K
中最小的为最佳
Lipschitz常数。一阶可导且有界的函数都是Lipschitz
连续的
[2]
。根据定义⑴可得，对任意
x∈
[
a,b
]
都有：
[1]
{
f
(
x
)
≥f
(
a
)
-K
(
x-a
)
f
(
x
)
≥f
(
b
)
+K
(
x-b
)
⑵
则直线
y=f
(
a
)
-K
(
x-a
)
与
y=f
(
b
)
+K
(
x-b
)
1Lipschitz函数
函数
f
(
x
)
为闭区间
[
a,b
]
上的函数，如果存在正常
数
K
使
f
(
x
)
满足：
(
x
,g
(
K,f
(
a
)
,f
(
b
)
)
)
为函数
f
(
x
)
的下界值。
⑴
f
(
x
)
的最小值。如图1所示。
都位于函数曲线下方。两条直线的交点
使用相同的方法可以求得在
[a,x
1
]
和
[x
1
,b]
两个
区间内下
f
(
x
)
的下界值。依此类推，区间的划分和最
|
f
(
x
)
-f
(
x'
)
|
≤K
|
x-x'
|
x,x'∈
[
a,b
]
小值的求解可以一直迭代下去，直到下界值无限逼近
收稿日期：2020-12-15
作者简介：葛仁磊（1987-），男，山东海阳人，学士，工程师，主要研究方向：精密工程测量及相关算法研究，工程测量检验及质量控制。
·2·
ComputerEraNo.52021
图1Lipschitz函数最小值估计
2DIRECT算法
传统的算法对于一维的Lipschitz函数最小值的求
解问题非常有效，但不便于向n维空间推广。对一个n
维的Lipschitz函数，进行一次最小值的迭代就需要对
其
2
n
个边界点的函数值进行计算，效率较低。
DIRECT算法改进了此问题。令
x
1
并带入(1)式可得
[6]
{
：
=
(
m+n
)
/2
f
(
x
)
≥f
(
x
1
)
+K
f
(
x
)
≥f
(
x
1
)
-K
(
(
x
x
-
-
x
x
1
1
)
)
,
,
x
x
≤
≥
x
x
1
1
⑶
式⑶的几何意义如图2步骤(a)所示。后续对每一
个半区间使用相同的方法进行迭代（图2步骤(b)），就
可以使下界值逐渐逼近
f
(
x
)
的最小值。
(a)
(b)
图2DIRECT算法最小值估计步骤
为了便于后文的讨论，此处引入以下与DIRECT
算法相关的概念。
超矩形：超矩形：n维空间内的闭区间。
潜在超矩形：潜在超矩形：可能存在函数最小值的超矩形。
细分超矩形：细分超矩形：将超矩形划分成更小的超矩形的过程。
在不考虑效率的前提下，我们对所有超矩形都进
行细分，再计算细分区间的下界值就可以无限逼近函
数的最小值。实际上只有满足一定条件的超矩形才是
潜在超矩形，在此前提下，我们只需要对潜在超矩形进
行细分就能更快的逼近最小值。所以“寻找潜在超矩
形”及“细分超矩形”是DIRECT算法的两个主要任务。
2.1寻找潜在超矩形
假设
ε
为一较小正常数，
f
min
为当前分割下的最优
解，
I
为所有超矩形索引的集合，
d
i
为超矩形中心到超
矩形顶点的欧氏距离。如果
j∈I
为潜在矩形，首先根
据
I
内元素与
{
j
的关系将
I
划分成三个集合：
I
1
=i∈
则
3
j
=
满足以下三个条件
i
∈
I
∈
I
:
I
:
d
:
d
i
j I 2 =i d i i > = d d j I j [3] ： 条件一： f ( c j ) 条件二： ≤f ( c i ) ,i∈I 3 ⑷ max f ( c j ) j ) i∈I -f d -f j -d ( c i i ) ≤min f ( c i∈I j -d ( c i d i ) ⑸ 条件三：当 f min ≠0 时： ε≤ f min -f ( c i ) d j f ( c i ) | f min i∈I min | + | f min | d -f i -d ( c j j ) ⑹ 当 f min =0 时： f ( c j ) ≤d f ( c i ) j min i∈I -f i ε 被称作琼斯因子（ - Jones d ( c j d j ) ⑺ Factor） [8] ，这个值为经 验值。实验证明 1×10 -2 不大， ε 的推荐值为 1×10 ≤ -4 ε 。以上引理的正确性本文 ≤1×10 -7 时对计算影响 不再论述，如读者对引理的证明感兴趣，可到引文[3] 第2.4.3节中查看详细的证明过程。 2.2细分超矩形 为了使超矩形在各个维度上的边长都能不断减 小，保证分割的效率，超矩形的细分只在一条或多条 最长边上进行 [4] 。图3、图4和图5展示了二维超矩形 和三维超矩形的一次分割方法。 计算机时代2021年第5期 ·3· 图3细分2维超矩形 图4细分3维超矩形 图5细分3维超矩形 2.3迭代终止条件 在引文[1,2,5,6]中，都使用了当迭代次数达到预设 值T时，结束该算法。这种方法在规模特定的问题中 得到了很好的应用 [5-6] 。在引文[3]中，对停止迭代条件 进行了更深入的探讨，同时也建议将目标函数的评估 次数及进行超矩形分割的深度当作终止迭代的条件， 这种做法在采样算法中经常用到。 在实际应用中，特别是工程应用中函数的全局区 间最小值 f global 往往是未知的。而且正如前文所述， DIRECT算法无法对函数的参数及Lipschitz常数进行 估计，所以在 f global 未知时也无法对 f global 进行估计。这 导致在实际应用中更常用、更有效的为“精度”或“百 分精度”很难作为DIRECT算法的终止条件。 在寻找Lipschitz函数的最小值过程中，除了获得 函数最小值外，有时函数在何处取得最小值对用户来 说也非常重要。用户自然的会以 f min 所在超矩形尺寸 达到某一特定要求作为终止迭代的条件 [8] 。在后面的 DIRECT算法实现中，我们将以 f min 所在的超矩形最长 被细分的次数定义为深度，并以深度小于等于给定值 作为终止条件之一。 表1总结了DIRECT算法常用终止条件。 表1终止条件方法列表 序号终止条件 1迭代次数大于等于给定值 2函数计算次数大于等于给定值 3 f min 所在的超矩形最长边小于等于给定值 3性能优化 第2节给定的算法逻辑清晰有效，但效率有待优 化。本节从超矩形细分维度次序、边长的指数式存储 和距离的存储与计算三个方面讨论如何提高DIRECT 算法的效率。 3.1超矩形的细分维度次序 2.2节中进行超矩形的细分讨论时对哪个维度优 先进行细分并没有讨论。但实际情况不同维度优先 会造成不同的效果，如图6所示。 图6超矩形细分不同维度次序 图6中(a)与(b)显示出相同的中心点进入了不同 尺寸的超矩形中。如在细分(a)中，左侧中心点最终进 入了边长为 13×13 的超矩形中。而在细分(b)中， 该中心点进入了边长为 13×1 超矩形中。这种差别 会影响后续潜在超矩形的查找及下一步分割的工作量。 那么(a)与(b)两种方式，哪个更有利于后续运算 呢？我们使用的策略是将最优的函数值放入到更大 的超矩形中，这是由于较大的超矩形总是能够更快的 被再次分割。经过实验也发现，这样的分割策略的确 能够提高算法速度 [6] 。 3.2边长的指数式存储 第2.2节细分超矩形的过程（图2、图3、图4）中，每次 超矩形的最长边都会变成原来边长的 13 。即一条边 如果经历 i 次分割，那么边的长度会变成原边长的 3 -i 。 为了便于边长的存储，在算法开始前将边长不规 则的初始超矩形映射到所有边长都为1的超正方形 ·4· ComputerEraNo.52021 内。此后就可以使用指数 i 来替代原有边长 3 -i 来进行 存储、排序等操作，可以节省空间并提高运算效率。 3.3距离的存储与计算 在寻找潜在超矩形时，公式⑸⑹⑺都用到了中心 到顶点的距离。DIRECT算法在提出时 [6] ，作者很自然 的使用了欧氏距离。欧氏距离是二范数距离，其计算 涉及平方和开方运算，计算量大，且产生的结果为实 数。为了保证计算精度，往往需要较大的存储空间。 这些原因促使研究者转而研究其他类型的距离是否 也能产生相同的效果，以及其他类型的距离能不能加 快运算速度，节省存储空间。 在引文[7]中，作者提出并证明了使用无穷范数距 离可以达到与欧氏距离相同的效果。超矩形中心到 超矩形顶点的无穷范数距离可以表示为： dist ∞ l 表示超矩形最长边被分割的次数， =3 -l 其中 /2 无穷范数距 离本质上就是最长边的一半。使用无穷范数距离有 如下好处。 少存储空间。 ⑴距离的表示与存储可以直接使用自然数 l ，减 ⑵ 够得到更少的潜在超矩形， ⑶ 距离的计算转化为边长排序， 在第2.1节的运算中， 减少计算量。 减少后续查找潜在超矩形 进行条件一运算时，能 的运算量。而且会进一步减少中心点处函数值的 运算次数。 为了比较二范数与无穷范数的效率，我们使用GP 函数 [8,13] 这个例子，分别使用欧氏距离和无穷范数距离 两种方法进行运算，得到统计数据如表2所示。 表2GP函数运算效率比较 欧氏距离无穷范数距离 f min 迭代次数评估次数迭代次数评估次数 200.54869680505 8.924791275321321 3.43 3.1961 3.451183 3.0518221 3.479681171 3.1 从表2数据可以看出，使用无穷范数作为距离度 量时，虽然有时迭代次数会超过使用二范数作为距离 度量，但在目标函数的计算次数上有很大优势。所以 本文给出的示例代码中以无穷范数作为距离度量。 4DIRECT算法实现 4.1算法流程图 DIRECT算法总体流程图7所示。 图7DIRECT算法流程图 图7中步骤a即为第2.2节“查找潜在超矩形”，其 细节请参照图8。步骤b和步骤c合在一起为2.1节 ，其细节请参照图9。 图8查找潜在超矩形 “细分超矩形” 计算机时代2021年第5期 ·5· 图9细分超矩形 4.2DIRECT算法算例 按照4.1节提供的流程图，笔者用Python编写了 。我们使用引文[4,9]中采用的Goldstein- Price(GP)测试函数： f ( x ) = ê é ë 1+ ( x 1 +x 2 +1 ) 2 ( 19-14x 1 +3x 2 1 -14x 2 +6x 1 x 2 +3x 2 2 ) ù ú û × é ê ë 30+ ( 2x 1 -3x 2 ) 2 ( 18-32x 1 +12x 2 1 +48x 2 -36x 1 x 2 +27x 2 2 ) ù ú û 同样，采用与引文[4]相同的范围 -2≤x i i∈1,2 ，图10、图11表示了在此区间范围内的图像： ≤2 ， 图10GP函数图像 图11GP函数计算结果 5结束语 DIRECT算法稳定性强，适用性广泛，适合在对性 能、精度要求不高的情况下使用。本文从实用角度， 全面而详细的介绍了DIRECT算法，提供了一种开箱 可用的算法，并给出了详细的算法流程图及其实现， 读者可以按照自身需求直接使用。 参考文献(References): [1]安华萍,李文静.DIRECT优化算法计算机仿真研究[J].惠州 学院学报,2019.3:16 [2]ealanalysis[M].Boston,Basel,Berlin: Birkhäuser,2003. [3]JonesDR,PerttunenCD,itzian optimizationwithouttheLipschitzconstant[J].Journal ofoptimizationTheoryandApplications,1993.79(1): 157-181 [4]cationsofthe directalgorithm[M],2001. [5]optimizationalgorithmuserguide[R]. forResearch inScientificComputation,2003. [6]宋科康,冯文涛.采用DIRECT算法的外辐射源雷达高效直 接定位方法[J].信号处理,2020. [7]王云宏.基于DIRECT算法的微震震源快速网格搜索定位方 法研究[J].地球物理学进展,2016.31(4):1700-1708 [8]武汉大学测绘学院测量平差学科组.误差理论与测量平差 基础-第2版[M].武汉大学出版社,2009. [9]CoxSE,HaftkaRT,BakerC, multidisciplinaryoptimizationofahighspeedcivil transport[C]//aceNumericalSimulation Symposium,1999.99:23-28 [10]DixonL,sGlobalOptimisation2North- Holland[J],1978. ▲ CE
发布评论