各种情形下优化问题搜索历程的一般说明

以下是程序运行遇到各种不同复杂情形时的自动应对方法说明，供理解搜索方法参考，与程序实际使用操作无涉。

多维函数的一轮轮搜索，搜索方式相同，取得当轮优点后的变量区间调整逐个进行，举一维问题的例已可说明一般情形。

设有如图4-3情形。图中函数为一维，搜最小。基本目标函数为横贯全区间的值为Y1- Y5- Y *- Y8-Y9的实线函数，特点是区间左半函数值缓慢降低，最优点Y * 靠近右边界点，过了该点，函数值急剧升高。为说清各种情形，设置了不同条件进行优化搜索。

图4-3　说明本法搜索原理的图

图左有一个用虚线标出的细尖峰G； 右半有一个用虚线标出的凹坑H及一个阴影部分的约束域；图中λ为当轮区间L（1）分3点搜索时的步长。为方便说明，将变量区间坐标总长L（1）分为8个等距小段画出，即x1﹑x2﹑… x9。小正数ε＞0为每遍搜索终止判据。设每轮变量均分3点搜索，区间含两个步长。以下逐项对以上诸情形分别做优化搜索说明。

3.1　仅有唯一最优解、无约束优化问题的搜索

设函数Y（1）=f（X），无约束，求最小，有唯一解。目标函数仅为图4-3贯穿全区间的实线函数。首轮R =1，取x1、x5、x9三点搜，得函数值Y1、Y5、Y9，其中Y5最优（见图），当轮Y（R）* =Y5 ，X（R）*=x5，优点居区间中部。随后进行变量区间调整，将区间向内收缩一半，下轮区间为x3—x7区段，L（R+1）=0.5L（R），舍弃率50%，此时含最优点区间x7 —x9段丢失。再进行R=R+1的新一轮（第二轮）搜索。新的R轮搜点为x3﹑x5﹑x7，搜得函数值Y3﹑Y5﹑Y7，且Y3＞Y5＞Y7，Y7为当轮最优。新的当轮变量优点为当前区间右边界点，为最优点分布的另一特征情形。因已假定问题仅有唯一解，故实际最优点只可能为当轮右边界点或其临近点，不会在相反方向。此时的区间调整规定，将当轮区间向优点方向（右）游移一个步长λ，不收缩，L（R+1）=L（R），下轮搜索区间为x5—x9段，使首轮搜索后被舍弃的x7—x9段恢复，此使当轮优点在下轮区间内位置居中。也可能遇到相邻两点函数值相等且最优情形，此时规定，按搜索顺序取后搜点为优点。故本搜索法，只会遇到当轮优点居中或居边的两种特征分布，各情形分别按各自规定调整区间。以下搜索面对的情形与首轮搜索类似。按图4-3，第三轮搜得优点仍居中，再搜几轮，可搜得全局最优解Y（1）*=f（X *）。搜索后的变量区间调整使下轮区间保留了当轮搜得优点，故后轮即使未搜到改进解，即“搜空”，已搜得优点仍在，且成后轮优点。

下面看包含图4- 3右侧虚线函数的搜索情形。

设函数Y（2）=f (X)为按图4-3左侧实线并接按右侧虚线规律变化，与左侧虚线和右侧实线及阴影区无关。此时问题仍无约束，搜最小，有唯一解，而函数已非凸非凹，H为全局优点。

仍分三点搜。经两轮搜索，因分点位置关系，最优值H未搜到，第3轮区间将移至x5—x9段，再搜后，优点居中；第4轮区间将移至x6—x8，搜后仍优点居中；经区间调整，第5轮搜索中变量左端点函数值将为H或相当接近H（可按图模拟搜索）。可见，本法对仅有唯一最优解非凸非凹函数的无约束优化搜索也适用。

3.2　无约束多解优化问题的搜索

设函数Y（3）=f (X)，为图4-3左侧实线加虚线，过G，再加右侧横贯后部全区间的实线部分，与右侧虚线和阴影区无关。

图中G为细尖峰，函数值在小区间内发生突降并迅速回复。用本法变量分三点经一轮搜时未能搜到。但如一定要搜到，定性地说，必要条件是，将变量区间细细分段取点，使每变量小段所占区间长度小于突降峰所占区间长度，搜索中尖峰区必落有搜点，将其搜到；又为进行函数值比较取优，保证搜索成功的充分条件应是，尖峰区段长度内至少应落2-3个搜点，满足比较取优的要求。这是保证只经一轮搜到最优解区域的绝对方法。

前文提到，多解优化问题搜索中的函数最优域概念，只要搜得变量最优域，即可保证搜索成功。但实际问题的搜索，通常不能保证此点，因①变量最优域大小搜前不知，不可能搜前正确确定变量搜索小分段长度；②变量分点过多将搜索耗时甚长，如本例若必须一轮搜到尖峰G，从图看，约须将区间均分16段取17点搜，对低维问题还可以，对高维问题则搜索时间可能过长。说本法适于求解多解问题，一方面是从原理上说，另一方面，局优解必须是缓慢变化并有较大范围，而且数量不能多，如只有2-3个等，此时变量分6-10点搜有可能不会失误。本法不保证搜到细尖峰。好在实际工程优化问题有多解的情形很少，有细尖峰的更少。本法规定了对任何优化问题的求解均须采用不同分点方案——包括分点很少方案——的多遍搜索，希望变量有点随机落入其最优域。但变量取点实际有随机性，一遍遍搜索中，碰上最优域内点的可能性也较大。例如图4-4 的搜索。