随机方向搜索法优化策略

1.随机方向搜索法的基本原理

随机方向搜索法是解决小型约束最优化问题的一种简单的直接求解方法，它的基本思路是在可行域内选择一个初始点X^（0），再随机选择一个能使目标函数值下降的方向作为可行搜索方向S，沿S方向进行搜索，求得满足一定条件的新点X，作为下一次迭代的起点，重复上述过程直至满足精度要求。

下面以二维问题为例说明随机方向搜索法的基本原理。如图3-22所示，在约束可行域内任意选择一个初始点X^（0），以给定的初始步长α=α^（0），沿着随机方向S^（1）（以某种形式随机产生），取得探索点X=X^（0）+αS^（1），检验该点是否满足下降性和可行性要求。若不能满足，则重新产生另一个搜索方向进行搜索。若同时满足，则表示X点探索成功。并以它作为新的起始点，在S^（1）方向上继续探索成功点。直到所探索的点不能同时满足下降性和可行性要求时停止，并将前一个成功点作为S^（1）方向搜索的最终成功点，记为X^（1）。此后将X^（1）作为新的起始点，然后再产生另一随机方向S^（2），以原定步长α重复上述过程，得最终成功点X^（2）。经若干循环，X^（k）必最后逼近约束最优点X^∗。

当在某个转折点处（如图3-22中X^（2）点），沿N_max（预先给定的某个转折点处产生随机方向的最大数目）个随机方向以步长α探索失败时，可将步长α缩半，即以α=0.5α进行探索，直到α已缩减到预定精度ε以下，且沿N_max个随机方向都探索失败时，则以最后一个成功点（如图3-22中的X^（3）点）为所求的最优约束点。一般选取N_max=50～100，对目标函数性态不好的应取较大的值，以提高解题成功率。

图3-22 随机方向搜索法的基本原理

2.初始点的选择

随机方向搜索法的初始点X（0）必须是一个可行点，即必须满足全部约束条件

g_u（X）≥0 （u=1，2，…，m）

当约束条件比较简单时，可在约束可行域内人为地确定一个初始点。当约束条件比较复杂时，则采取随机选择方法，即利用计算机产生的伪随机数来选择可行初始点X^（0），此时需要输入设计变量的估计上下限，即

a_i≤x_i≤b_i （i=1，2，…，n）

这样，初始点的各分量为

X_i^（0）=a_i+r_i（b_i-a_i） （i=1，2，…，n）

式中，r_i为[0，1]区间内服从均匀分布的伪随机数。这样产生的初始点还必须经过可行性条件的检验，看是否满足约束条件，因为能满足设计变量的边界条件，不一定就能满足所有约束条件。若不满足，则应重新随机选取初始点。

3.可行搜索方向的产生(www.xing528.com)

过一点要构成k个n维随机方向单位向量可按如下的公式计算

式中，y_i^（j），y₂^（j），…，y_n^（j）为形成第j个随机单位向量在[-1，1]区间内的n个随机数。y^j_i可以利用计算机直接产生。或者可以通过已经确定的r_i来求取。其公式如下

y_i=2r_i-1

由于y_i在区间[-1，1]内产生，因此构成的随机单位向量端点一定位于n维超球面上。

4.约束随机方向搜索法的步骤

1）选择一个可行的初始点X^（0）。

2）按式（3-18）产生j个n维随机单位向量e^（j）（j=1，2，…，k）。

3）取试验步长α₀，按照X^（j）=X^（0）+α₀e^（j）计算出j个随机点X^（j），其中j=1，2，…，k。

4）在所产生随机点中找出满足f（X_L）＜f（X^（0））的随机点X，产生可行搜索方向S=X_L-X^（0）。

5）从初始点X^（0）出发，沿可行搜索方向S以步长α进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点X。

6）若收敛条件

得到满足，迭代终止，约束最优解为X^∗=X，f（X^∗）=f^（X）。若收敛条件不满足，令X^（0）=X转到步骤2）。