0 引言
解决最优化问题已经有很多比较成熟的算法， 如遗传算
法、神经网络、模拟退火法等，各有其优劣。模式搜索法作为一 种解决最优化问题的直接搜索方法，因为在计算时不需要目标 函数的导数， 所以在解决不可导或者求导异常麻烦时比较有 效。随着模式搜索法的发展，人们在Hooke-Jeeves 模式搜索法 的基础上设计了变步长搜索策略，使得模式搜索方向更接近于 最优下降方向，并且同时采用了插值技术和非单调技术，不仅 改善了方法的局部寻优能力，而且改善了方法的收敛性。现在 已有很多软件将这一算法集成到程序中， 如Matlab 已经将它 添加到工具箱中，使用时只要调用相应的函数就可以用模式搜 索法解决问题，大大提高了工作效率，降低了编程工作量。 1 模式搜索法的基本原理
模式搜索就是寻找一系列的点X0，X1，X2，…，这些点都越 来越靠近最优值点，当搜索进行到终止条件时则将最后一个点 作为本次搜索的解。利用模式搜索法解决一个有N 个自变量 的最优化问题。①要确定一个初始解X0，这个值的选取对计算 结果影响很大；②确定基向量用于指定搜索方向，如对于两个
自变量的问题可设为V（0，1；1，0；-1，0；0，-1）即按十字方向搜 索；③确定搜索步长它将决定算法的收敛速度，以及全局搜索 能力。
具体步骤为：①计算出初始点的目标函数值f（Xi），然后计
算其相邻的其它各点的值f（Xi+V（j）*L），j∈（1，2. . .2N）；②如 果有一点的函数值比更优则表示搜索成功，那么Xi+1=Xi+V（j） *L，且下次搜索时以Xi+1
为中心，以L=L*δ 为步长（δ>1，扩大搜
索范围），若没有找到这样的点则表示搜索失败，仍以Xi 为中
心，以L=L*λ 为步长（λ<1，缩小搜索范围）；③重复②的操作直 到终止条件为止，终止条件可以是迭代次数已到设定值或者误 差小于规定值等。 2 模式搜索法的改进
随着模式搜索法被逐渐认可与应用，人们对模式搜索法做 了许多改进。如在搜索方向上，用模式搜索法解决一个有N 个 自变量的问题时，共有Z＊N 个基向量，这样如果对每个方向 都搜索就会大大的增加计算量，对此人们提出了正基向量的概 念， 具体可参照， 编写的《Positive bases in
numerical optimization》一文，正__________基向量的应用与有运动矢量场 自适应快速搜索法（MVFAST），增强预测区域搜索（EPZS）、非 对称十字多层六边形搜索法（UMHexagonS）的提出在满足全局 搜索能力的情况下，大大降低了计算量。另外在步长控制方面， 出现了变步长模式搜索方法，推动了模式搜索法的发展。 3 Matlab模式搜索法工具箱应用及实例
Matlab 的工具箱里的patternsearch 就是基于模式搜索算
法的优化工具箱， 有两种方法可以调用patternsearch 工具箱， 一种是GUI 即图形界面形式的，用户可以直接在窗口中操作， 另一种就是在程序中调用patternsearch 函数来进行模式搜索， 本文主要介绍后面一种。Patternsearch 函数的完整格式为［X， FVAL］ =PATTERNSEARCH （FUN，X0，A，b，Aeq，beq，LB，UB， NONLCON，options）FVAL，X 分别为取得的最优值及所在的 点，FUN 为m 文件句柄该， 该m 文件就是要进行最优化的函
数，options 为对搜索方式的设置。A，b，Aeq，beq，LB，UB 为对x 取值的限制条件，具体的为： A*x≤B； Aeq*x=Beq； Lb≤x≤Ub ≤ ≤≤≤ ≤ ≤≤≤ ≤ ； 软件导刊
Software Guide 第8卷%第8期 2009年8 月
Aug. 2009
若没有限制则可以设为空即［］，下面用patternsearch 工具箱计 算带噪声的具有多个极小值的函数的最小值x21 函数具体表达式为： f（x1，x2）= x21 +x21
-25+m*rand；x21 +x22 ≤25 x21
+（x2-9）2-16+m*rand；x21 +（x2-9）2≤16 m*rand；其它情 ≤ ≤≤≤ ≤ ≤≤≤ ≤ 况
Rand 为（0 1）之间的随机数，m 为振幅，两者乘机代表噪 声大小（本算例取自matlab 软件包的help 文件，原算例没有带 噪声）。当m 取为1 时利用matlab 画出该函数的图形如图1，由
图可知当引入噪声后，图形变的很复杂，若利用一般的算法由 于无法求导则该问题变得很复杂，由于patternsearch 的工作原 理使得其在解决这类问题时有很大优势。解决步骤：
（1）编写m 函数，m 函数就是要计算的函数，具体如下： function y = myfun（z，noise）
y=zeros（1，size（z，1））；noise=1； for i=1：size（z，1） x=z（i，：）；
if x（1）^2+x（2）^2<=25
y（i）=x（1）^2+x（2）^2-25+noise*randn； elseif x（1）^2+（x（2）-9）^2<=16
y（i）=x（1）^2+（x（2）-9）^2-16+noise*randn； else y（i）=0+noise*randn； end end end
z 为矢量是目标函数的自变量，大小为自变量的个数，y 是 对应与自变量的目标函数的取值。 图1 m＝1 时，函数（1）的图形
（2）确定初始点，这对运算速度也结果有很大影响，这里取 为X0=［-8，8］；再就要确定搜索边界条件，一般要视具体问题 来确定，若选的过大则搜索速度变慢，过小则会影响全局搜索 能力。这里取为-10≤x1≤10；-10≤x2≤15 （3）编写主程序
X0 = ［-8 8］； % Starting point. LB = ［-10 -10］； %Lower bound UB = ［10 15］； %Upper bound
range = ［LB（1） UB（1）； LB（2） UB（2）］；
Objfcn = @myfun； % Handle to the objective function.
clf；showSmoothFcn （Objfcn，range）； hold on； % Plot the smooth objective function title（'objective function'） fig = gcf；
PSoptions = psoptimset （'Display'，'iter'，'OutputFcn'， @psOut）； ［x，z］ = patternsearch （Objfcn，X0， ［］， ［］， ［］， ［］，LB，UB，
PSoptions） figure（fig）； hold on；
plot3 （x （1），x（2），z，'dr'，'MarkerSize'，12，'MarkerFaceColor'，'
r'）； hold off 搜索过程：
Iter f-count f（x） MeshSize Method
建模优化问题的解决
