基于改进边际优化的离散变量优化设计算法

吴诗辉, 李正欣, 刘晓东, 周 宇, 贺 波

(空军工程大学装备管理与无人机工程学院, 陕西 西安 710051)

0 引 言

离散变量仿真优化区别于连续变量仿真优化,其主要特点是参数取值是离散化的,这在多参数设计问题中广泛存在[1-8]。事实上,在实际应用中,尤其是工程问题,由于变量的精度要求或变量性质特点,离散变量的优化比连续变量更具有实际意义。

传统优化方法主要适用于连续变量的优化,由于离散变量不连续、约束函数限制等特点,许多传统优化方法不再适用。通常的处理方法,一种是基于连续变量优化的方法。比如圆整法,即将所有离散变量视为连续变量,找出局部最优解,然后将其圆整到附近的离散解上,该方法可能找到局部满意解,但是大多数情况下,这些离散解不是离散变量优化问题的最优解[2-3]。两步搜索法在圆整法的基础上,以圆整法找到的解作为起点,按照某种方式搜索离散最优解,但是离散最优解不一定在连续最优解附近。第二种是遗传算法[2,4-6]。通过设计适用于离散搜索的遗传算子在离散空间进行搜索,从而找到最优解。但是遗传算法在复杂最优化问题尤其是高维度最优化问题中,可能出现效率低、难以找到最优解等问题,有时找到的满意解周边就是局部最优解,却不能发现(如例2中对文献[4]得到解的分析),这是遗传算法非连续、跳跃性搜索的原理决定的。第三种是各种启发式算法,如蚁群算法[7],粒子群算法[8-9],模拟退火算法[10],萤火虫算法[11],禁忌搜索算法[12]等,这些算法原本是用于对连续变量问题进行优化,通过对算法从编码、搜索算子、惩罚函数等方面进行适应性改进,能够解决离散变量的优化问题,但是这些算法往往需要对目标函数值进行大量的测试和计算。比如,对于一个双变量的问题,数量级达到10 000次[13],对于需要较长时间完成一次目标函数值测算的问题,如仿真优化问题[14-15],是不切实际的。

因此,如何针对高维度的复杂离散变量优化问题,以最少的迭代次数得到满意解或局部最优解,是本文的研究目标。由于现实中的离散变量优化设计问题,多是有限区域的,即离散变量存在上下界,本文主要研究有限区域、高维度的复杂离散变量优化问题。通过借鉴边际优化思想、模式搜索算法的搜索策略,设计了一种基于边际优化的离散变量优化算法,可以快速、收敛地找到局部最优,通过引入变异操作,能够尽可能找到更多局部最优或得到全局最优。该方法不需要目标函数的先验信息(如梯度等)，适合于多变量的优化、离散变量的仿真优化等问题。

1 基本原理

离散变量优化问题可描述为

(1)

式中,XD为离散空间。

定义 1对于离散变量优化问题,称点A(用XA表示)为可行点,即当点A在可行域内(XA∈XD),且gi(XA)≤0,hj(XA)=0均满足时;若以可行点A为起点,向其周围进行单位步长搜索,即每次仅对一个变量进行单步长增减,其余变量不变,称得到的所有点构成点A的周围单位步长空间Ω(A)。

比如,点A为(x1,x2),x1和x2的离散步长分别为d1和d2,则其周围单位步长空间定义为集合Ω(A)={(x1+d1,x2), (x1-d1,x2), (x1,x2+d2), (x1,x2-d2)}。如图1所示的E点,其周围单位步长空间为Ω(E)={B,D,F,H},由于图1中的d1=d2,则其周围单位步长点刚好位于以E点为圆心,以d1为半径的圆上。由于单位步长空间每次仅改变单个元素,通过增加或减少单位步长得到,因此单位步长空间包含点的个数为2n,n表示维数。

图1 边际搜索与单位步长Fig.1 Marginal search and unit step

对于边界上的点,仍假定其周围单位步长空间点为2n个,但其中超出边界的点为不可行点,规定不可行点的目标函数值均为∞,如图1中的边界点C,其超出边界的周围单位步长空间点K和J的目标函数值均设为∞。

定义 2对于离散变量优化问题,假设可行点A为起点,若存在点B满足B∈Ω(A),B≠A,且B点的目标函数值在Ω(A)中最小,称B点为单步边际优化点,称路线A→B为单步边际优化搜索路线。

定义 3对于离散变量优化问题,称点A为一个局部极小点,当且仅当A在其周围单位步长空间Ω(A)内目标函数值最小时。

以图1为例,考虑一个简单的二维离散变量优化问题。该问题的取值区间为[-1,1]2,x1和x2的离散步长均为1,该区间内共有9个离散点,将各点的目标函数值标在点上,如图1(a)所示。图中E点的目标函数值为3,其周围单位步长空间Ω(E)={B,D,F,H}上各点的目标函数值均大于3,则可认为E点为1个局部极小点。同样,C点为另一个局部极小。该问题如按照连续变量优化,则E点可能不是一个局部极小,因为假设在EC连线方向上目标函数值是不断降低的,则只有C点为局部极小,如图1(b)所示。这也说明了离散变量优化问题与连续变量优化问题的不同，即离散变量极小点只比较周围单位步长空间内的点,而连续变量极小点则要比较周围空间的所有点。

定理 1对于离散变量优化问题,如果边际优化搜索在可行点A的周围单位步长空间内均找不到更好的解,则点A可看作一个局部极小点。

根据定义3,即可得出定理1。

从图1可以看出,根据定义3,E点为1个局部极小,C点为另一个局部极小。当搜索起点为D,H,G时,将搜索得到E点,而当搜索起点为A,B,I,F时,将搜索得到C点。比如,以A为搜索起点,经过路线A→B→C,搜索得到局部极小点C;以I为搜索起点,经过路线I→F→C,搜索得到局部极小点C;以G为搜索起点,经过路线G→H→E,搜索得到局部极小点E。

推论 1(收敛性) 对于离散变量优化问题,给定足够的搜索步数,边际优化搜索一定能够找到局部极小点。

证明由于边际优化搜索总是朝着使得目标函数值f(x)下降最多的方向,以等步长均匀下降,则可能存在两种情形:一种对应于图2中的A5点,该点为局部极小值点,其以A1点为初始点,经过等步长搜索:A1→A2→A3→A4→A5得到。可以看到,当搜索到A5点时,比较周围邻近的可行点A4和A6,都大于A5点，因此停止搜索,得到一个局部极小点A5。另一种对应于图2中的B6点,其以B1点为初始点,经过等步长搜索:B1→B2→B3→B4→B5→B6得到,假设B6点位于边界上,则其也可看作一个局部极小。这是由离散变量优化的边界点必然也是离散值决定的,比如假设步长为1,B5点为x=4时,边界点B6点只可能为x=5,而不可能为x=4.4(因为不到1个步长)。由于边界点B6也可看作局部极小,且B6小于周围邻近的可行点B5,因此停止搜索,得到一个边界局部极小。所以,以上两种情况下,边际优化搜索均能搜索得到局部极小点。

证毕

图2 边际优化搜索算法寻找局部极小点示意图Fig.2 Schematic diagram of marginal optimization search algorithm for finding local minimum point

事实上,离散变量优化问题的离散特点以及非线性约束条件,决定了离散变量优化相比连续变量存在更多的局部最优点。因此,设计有效的算法跳出局部最优点非常重要。研究发现,很多文献的结论都陷入局部最优[4-5,16-17],详见本文例2和例3。其中,文献[16]采取传统边际优化法得到的解为一个局部最优解(4, 7, 5, 4),对应系统可靠度为0.996 7,本文方法得到的最优解为(5, 6, 5, 4),对应系统可靠度为0.997 47。说明传统的边际优化法、遗传算法等在解决离散变量优化问题上容易陷入局部最优。这也是本文算法的设计初衷。

推论 2(唯一性) 对于离散变量优化问题,一个初始点经过边际优化搜索只能得到一个局部极小点,且搜索路径唯一。

证明根据定义2,从初始点开始,单步边际优化搜索的路线是唯一的,找到的单步边际优化点也是唯一的,则执行多次单步边际优化搜索直到找到局部极小,整个搜索路线也是唯一的。因此也只能得到唯一的一个局部极小点。

证毕

离散变量优化的边际优化搜索算法,与连续变量优化的模式搜索算法[14]不同。模式搜索算法由于搜索步长会根据搜索效果发生变化,因此可能漏掉局部极值点。同时,连续变量优化可能产生边界噪声点[14],而非局部极小。但对于离散变量优化,边际优化搜索找到的边界极小点必然是局部极小点,这在推论1中已进行了说明。

整个搜索过程,可以想象成1个n维的球体在离散空间滚动,每次滚动1个单位步长,且总是朝着最低的方向(即目标函数值最小)持续滚动,直到达到1个局部极小点,球体停止滚动。

2 基于边际优化的离散变量优化算法设计

2.1 传统边际优化

边际效应分析理论是当代经济学理论中的基础方法之一。该理论认为市场上一个商品的价值不是由最初的效用决定的,也不是由平均效用决定,而是由人们使用的最后一个单位商品的效用——边际效用决定的,把这种通过比较边际效用进行优化的方法,称为边际优化法。除了在经济学领域的应用,边际优化法还被广泛应用于备件库存的最优决策[18-19]、可靠性分配问题[16]、层次分析法(analytic hierarchy process, AHP)优化决策[20]等。

传统边际优化法的基本思想是:假设变量的维数为n,初始值为所有变量的下界值组成。假设初始值为x0=(0,0,…,0),从x0开始,每次只对1个变量增加1,得到n个新解,即{(1,0,…,0), (0,1,…,0), …, (0,0,…,1)}。比较这些新解的收益增量Δf与资源耗费的增量Δc的比值,比值最大说明增加该变量带来的边际效费比最大。因此,选择对该变量增加1。按照此方法不断迭代,直到资源耗费达到规定值。该方法能够实现一定资源约束条件下的收益值最大化。

2.2 改进边际搜索算法

借鉴传统边际优化的思想,针对离散变量优化问题,做以下改进。

一是初始点不是选择所有变量的下界值,而是随机生成一个可行解。这和离散变量优化问题的特点是相关的:对于一个离散变量优化问题,所有变量的下界值组成的解不一定为可行解(即约束条件可能不满足,见例1);同时,可能存在很多的局部极小,而不是像备件库存的最优决策[18-19]等问题中只有1个最优解(因为备件数量越多,目标函数值——满足率必然越大,不会减小)。根据定理1,1个初始点只能搜索得到1个局部最优,故需要多个随机的初始可行解才能得到全部局部最优,从而找到最优解。因此,设置变异操作生成初始解,以跳出局部极小(详见第2.3节)。

二是边际增量不是每次增加1,而是增加或减少1个单位步长(取决于离散变量的步长间隔)。这是由初始点选择的随机性决定的,因为局部最优点可能位于初始点的增量方向,也可能位于减量方向。

三是设置禁忌搜索策略。传统边际优化因为是从0开始,逐步增加1,不可能出现新搜索点与已搜索点相同的情况。而改进算法需要设置多个初始点进行搜索,为防止与已搜索点重复,对所有搜索过的点进行记录,并在发现与已搜点重复时,立即变异,以减少重复搜索。当发现1个搜索点重复时,根据推论2,即以该搜索点为起点的剩余搜索路线具有唯一性,若不执行变异,则剩余搜索过程将全部是重复搜索。

2.3 变异操作

为防止算法陷入局部极小,同时避免重复搜索,设计变异操作。文献[21]设计了整数变量优化问题的单点变异方法,由于离散变量优化问题一般涉及较多的变量,本文考虑多点变异,变异点的个数应介于[1,n/2]之间,n为问题的维数。

同时,为保证变异操作起到变异效果,对于单点变异的情况,改变的元素值应该不属于周围单位步长空间内。比如,考虑一个4维离散变量优化问题,4个变量可行域均为[1, 5],离散步长分别为(0.1, 0.5, 1, 0.01),对局部极小点x1=(3,1,2,5)进行单点变异。随机选择对第3个元素进行变异,则第3个元素将只可能变异为{4, 5}中的一个,因为{1, 3}均在点x1的周围单位步长空间内。对该问题执行单点变异和多点变异操作,如图3所示。

图3 变异操作Fig.3 Mutation operation

例如,对于一个确定性函数,假设y1和y2都是整数:

(2)

式中,y1∈[-3 000, 3 000],y2∈[-2 000, 2 000]。

该问题是一个二维的无约束离散变量优化问题,搜索过程如图4所示。

图4 改进边际优化的寻优过程(不同视角的等高线图)Fig.4 Optimization process of the improved marginal (contour plots from different perspectives)

若初始点为(1 000, 200),设定的搜索次数为2 000次,则本文算法能够在第894次搜索时,找到局部极小点:y*=(611,-305),函数极小值为f(y*)=-0.641 4。此时执行一次变异操作,得到第二次搜索的初始点为:y1=(-479,-305),算法经过1 091次搜索后,再次找到同一局部极小点y*。从图4中可以清晰地看到,改进边际优化算法执行的两条搜索路径均没有走任何多余的弯路,而是直接找到了局部极小点,实现了问题的最快搜索,而且当找到一个局部极值后,算法执行了一次单点变异,完成了两次不同的搜索。

2.4 算法步骤

步骤 1初始化。在可行域内随机生成符合条件的初始点x0=[x10,x20,…,xn0],设置最大搜索次数为N,令j=1,禁忌搜索点集合Ψ=∅。

步骤 2判断是否达到最大搜索次数。如果j≥N,达到最大搜索次数,输出找到的极小值xmin和Fmin;否则,进入步骤3。

步骤 3计算边际值。令离散步长矩阵v为

(3)

式中,vri表示v的第i行向量;di表示变量xi的离散步长。

以初始点x0为中心,分别计算其周边单位步长各点的目标函数值,即:

(4)

式中,

式中,x0+vri不可行有两种原因,一是搜索点超出了边界,二是搜索点不满足约束条件。

边际值为

Δ=[f(x0)-f(x0+vr1),f(x0)-f(x0+vr2),…,
f(x0)-f(x0+vr(2n))]

(5)

步骤 4选择新的搜索点。如果边际值Δ中均为负数,根据定理1,证明该搜索点为一个局部极小点,输出该极小值点xmin=x0,Fmin=f(x0),同时执行变异操作,转到步骤5,开始新一轮的搜索。否则,边际值Δ中至少存在1个正数,选择Δ中最大的正数,不妨假设Δk=maxΔ,判断如果x0+vrk∉Ψ,则选择点x0+vrk作为下一次搜索的初始点,同时将该点加入禁忌搜索的已搜索点集合Ψ,令x0=x0+vrk,j=j+1,转到步骤2;否则,如果x0+vrk∈Ψ,证明该新搜索点在之前的搜索中出现过,根据禁忌搜索原理,执行变异操作,转到步骤5。

步骤 5变异操作。按照第2.3节,根据问题的维数(即变量的个数),可选择需要进行变异的变量数量,比如单点变异或多点变异。根据定义1,将变异得到的点xm0进行可行性判断,若可行,且xm0∉Ψ,则将其作为新的初始点,令x0=xm0,转到步骤3;否则,重新执行变异操作步骤5,直到得到可行的新初始点。

3 实例分析

例1考虑以下二维离散变量优化问题:

(6)

式中,x1是0.25的整数倍,x2是0.1的整数倍,且x1∈[-50, 50],x2∈[3, 20]。

假设随机生成的可行初始点A1为x0=[3, 6],则g1(X)=-14,g2(X)=0,因此为可行解。搜索过程如表1所示,其中*表示边际值最大的变量。搜索路径如图5所示。从图5可以看出,该问题如果以A1点作为初始点,只需要14次迭代,按照图5中的路径A1-C-B就可以找到最优解B点:Xmin=(4, 5),f(Xmin)=-57。完成一次搜索后,算法将执行变异,经过单点变异得到A2点作为第2次搜索的初始点xA2=[4, 6.4],则算法将按照图5中路径A2-D,找到D点,xD=[4, 5.7],此时再进行1次边际搜索,将会与第1次搜索路径上的C点重复(xC=[4, 5.6]),若继续搜索则余下的搜索将按照路径C-B执行,显然发生了重复搜索(重复次数达7次)。因此,根据第2.4节中步骤4的禁忌搜索策略,搜索到D点时将不再继续搜索,而是执行变异,开始另一次寻优。

表1 改进边际搜索算法的逐步搜索过程

图5 改进边际优化的寻优路径Fig.5 Optimization path for improved marginal optimization

对于该问题,如果按照传统边际优化,从变量的下界开始搜索,即x0=[-50, 3],该初始点为不可行点,式(3)中两个约束不等式均不满足。初始点不可行,则无法计算边际值,算法将无法继续执行。

例 2考虑以下减速器体积优化设计问题[2,4-5,22],该问题为一个6维的离散变量优化问题:

(7)

式中,x1表示齿轮的宽度,x1∈[10, 20],取整数;x2表示小齿轮的齿数,x2∈[17, 30],取整数;x3表示齿轮的模数,x3∈[0.2, 1],要求精确到小数点后1位;x4表示减速器箱体的宽度,x4∈[20, 25],要求精确到小数点后2位;x5和x6表示轴的直径,x5∈[10, 15],x6∈[13, 20],均取整数。

改进边际搜索在运行100次的情况下,目标函数值的变化如图6所示。从图6可以看出,对于离散变量优化问题,改进边际优化算法可以持续降低目标函数值,当达到某个局部极小点(对应目标函数值为30 622),此时无法继续减小,算法执行变异操作,跳出局部极小,开始新一轮的寻优。本例中,发生了一次变异,从图6也可看出,变异后目标函数值发生跳跃式增大。经过多次试验,算法不仅找到了全局最优方案,也找到了几个相对满意的局部最优方案,如表2所示。

图6 改进边际优化的目标函数值变化趋势图Fig.6 Change trend chart of objective function value for improved marginal optimization

表2 所提方法找到的局部极小与文献的对比

文献[4]找到局部极小为:xm1=[13, 24, 0.6, 23.75, 10, 13],f(xm1)=30 675。对其进行检验，在其周围单位步长空间内,容易找到点xa=[13, 24, 0.6, 23.74, 10, 13],f(xa)=30 673,由于f(xa)

文献[5]找到局部极小为xm2=[14, 23, 0.6, 29.33, 12, 13],f(xm2)=33 540。对其进行检验,发现其周围单位步长空间内无更小的点,因此,该点为一个局部极小点。但显然该点的目标函数值过大,不能视为满意解。文献[22]的局部极小为xm3=[13, 19, 0.9, 23.6, 10, 13],f(xm3)=40 459,经验证,该点实际为不可行点,因为约束条件g2(X)不满足,如表2所示。文献[2]找到了全局最小点xm4,与本文方法得到的最优解一致。但是,本文还找到了几个次优的局部极小解,可作为备选优化方案。由于局部极小的搜索路径上的点都可作为初始点,故初始点不唯一,实验中5组解的初始点分别为xa1的初始点为[13, 24, 0.6, 24.61, 14, 13],经过116次搜索得到;xa2的初始点为[14, 23, 0.7, 24.86, 10, 13],经过38次搜索得到;xa3的初始点为[12, 27, 0.6, 23.63, 14, 13],经过119次搜索得到;xa4的初始点为[12, 30, 0.6, 24.53, 12, 16],经过312次搜索得到;xa5的初始点为[13, 22, 0.7, 24.93, 10, 14],经过246次搜索得到。

如果按照连续变量优化问题求解,利用Matlab自带的fmincon函数可以很快找到最优解,即最优目标函数值为29 476,最优解为(10.577, 23.858, 0.661 1, 21.077, 10, 13)。该连续解若经过四舍五入法圆整处理,得到邻近的离散解为(11, 24, 0.7, 21.08, 10, 13),代入约束式g1(X)～g10(X),得到该点为可行点,同时对应的目标函数值为32 622,可见明显大于本文找到的最优解,故用圆整法往往只能得到非最优解或不可行解。通过与文献的对比可见,本文算法具有以下优点。

(1) 能够保证算法的收敛性。通过对比文献[4]发现,遗传算法往往能够找到满意解,但是不一定是局部极小,即使找到的解在局部极小附近,也难以发现局部极小。这是由于遗传算法的搜索原理决定的,而根据定理1,本文算法一定能够得到局部极小。

(2) 目标函数测算次数尽可能少。相比各种启发式算法,改进边际搜索算法所需的目标函数测算次数相对较少,且根据推论2,每个初始点的边际搜索路径唯一,因此在算法中引入了禁忌搜索策略。一旦出现已搜索路径上的点,即执行变异操作,避免了大量的重复路径搜索过程。

(3) 本文算法原理简单,容易实现,且专门针对离散变量优化问题设计,适用性强。对于非整数的离散变量优化问题无需转化为整数优化,可直接用离散步长进行搜索实现。

例 3考虑以下齿轮减速器的可靠性优化设计问题[2,17],为一个4维离散变量优化问题:

(8)

式中,x1表示法向模数,x1∈[2, 20],取整数;x2表示小齿轮数,x2∈[17, 50],取整数;x3表示螺旋角,x3∈[0.6, 1.2],要求精确到小数点后2位;x4表示齿宽系数,x4∈[6, 20],取整数;r表示传动比,本文取5。

如表3所示,文献[2]利用改进遗传算法、文献[17]利用圆整法,找到局部极小分别为xm1=xm2=[2, 17, 0.96, 6],f(xm1)=106.231。应用定理1对其进行检验,该点为一个局部极小点。而本文算法则找到了更好的最优解[2, 17, 0.97, 19],目标函数值为103.165。与例2类似,算法还找到了几个全局最优解(见表3)。实验中4组解的初始点(不唯一)分别为:xa1的初始点为[2, 28, 0.97, 18],经过13次搜索得到;xa2的初始点为[3, 41, 1.12, 19],经过26次搜索得到;xa3的初始点为[2, 48, 0.95, 20],经过33次搜索得到;xa4的初始点为[19, 29, 1.02, 20],经过31次搜索得到。

表3 例3实验结果对比

由于目标函数中不包含x3,因此改变x3能够带来的边际增量始终为0,算法将始终不会对其进行改变。故当最优解中x3取其他值时,必然还可找到更多解,其余解不再一一列举。

例 4考虑以下离散变量优化问题[23-24],其维度n可根据需要设定:

minf(X)=(x1-1)2+(xn-1)2+

s.t. -5≤xk≤5,k=1,2,…,n

(9)

式中,xk取整数。

该问题是一个无约束的非线性整数规划问题,常用于测试优化算法在高维度情况下的运行效果。其有11n个可行点和许多局部极小值[24],但只有一个全局极小值解:xmin=[1, 1, …, 1],对应目标函数值为f(xmin)=0。

本文采取随机初始值的方法,分别在n为25, 50, 100的情况下进行了10次试验,均找到了全局最优解,结果如表4所示。其中,FN表示算法找到最优解时目标函数的计算次数,分别给出了最少、最多和平均次数;T表示算法找到最优解时的CPU用时(为与文献比较,仅给出了最长的一次用时)。

表4 例4实验结果对比

通过对比发现,本文算法找到最优解时所需的FN和T的最大值均明显少于文献[24]。对于n=50的情形,文献[24]以更少的FN得出了最优解,甚至比n=25的情况下还少。这是因为n=50时,所选择的初始点刚好能够很快收敛到全局最优,而如果随机选择初始点时,文献[24]可能需要更多的迭代次数才能收敛到全局最优。另外,文献[24]是在指定初始点的情况下得到的结果,本文则是在随机初始点情况下的结果。通过反复实验发现,对于高维度问题,除非初始点刚好能够一次收敛到全局最优,本文算法对于初始点的选择以及变异点数(采取单点变异或多点变异)的影响不大。

这里给出一次实验的运行结果:当n=100时,采取3点变异,在2 000次迭代的情况下,目标函数值的变化如图7(a)所示,整个过程共发生143次变异,实际进行了1 857步搜索。如图7(b)所示,第1次搜索在第423次迭代时,找到局部极值点,x1=[0, 0, …, 0],对应f(x1)=2;在第797次迭代时,找到第2个局部极值点,x2=[1, 1, …, 1],对应f(x2)=0,为本问题的全局最优解;在第1 212次迭代时,找到第3个局部极值点,x3=[-1, 1, 1, …, 1],对应f(x3)=4。除以上2次有效变异,其余的141次变异均因禁忌搜索策略而中止搜索。

图7 目标函数值变化趋势图Fig.7 Change trend chart of objective function value

4 结 论

本文针对离散变量优化问题的特点,设计了基于改进边际优化的搜索算法,为保证搜索效率,设置了变异操作和禁忌搜索策略,以实现通过最少的迭代次数得到更多的局部最优解,从而找到问题的最优解或满意解。算法借鉴了传统边际优化和模式搜索算法的原理,相比传统边际优化,本文算法选择初始点更为灵活,不需要从所有变量的下界开始搜索,且搜索方向不仅是边际增量方向,也包括边际减量方向,从而保证最快速度落入局部极小点。相比模式搜索算法,由于选取的步长为离散变量的单位步长,可避免出现模式搜索因搜索步长过大而漏掉搜索区域内的局部极小点,以及搜索到假的局部极小点的问题。

对于离散变量优化问题,本文证明了改进边际搜索具有收敛性和路径唯一性的特点,对于保证解的质量、提高求解效率具有重要意义。因此,本文算法特别适用于目标函数为黑箱模型、仿真模型以及高维离散变量优化问题。下一步,考虑研究边际优化算法与其他算法的混合使用,主要从初始点的选择策略、变异调整策略、禁忌搜索策略等角度开展深入研究,以进一步提高复杂高维离散变量优化问题的求解效率。