基于嵌入协作的多方法协作优化方法

摘要

提出一种基于嵌入协作的多方法协作优化方法。算法采用嵌入方式组织各个优化方法之间的协作，利用优化方法之间的协作效应提高优化性能。进行遗传算法、模式搜索法和Powell法嵌入协作组成的多方法协作优化方法设计。计算实例表明，基于嵌入协作的多方法协作优化方法取得了优于单个优化方法的全局最优特性。

正文

《1 引言》

1 引言

多方法协作优化方法 (MCOA, multimethod collaborative optimization algorithm) 是笔者提出的一种优化方法, 是采用一定的协作策略将多个具有可协作性的优化方法组织起来进行协作优化而得到的优化方法, 将其成功地应用于非壅塞式固冲发动机导弹一体化优化设计中^[1]。MCOA利用参与协作的优化方法的协作效应来提高MCOA的优化特性, 可以获得优于参与协作的优化方法的全局最优特性, 在求解复杂函数优化问题以及飞行器总体优化设计等工程优化问题方面具有优势。

MCOA的优化结构与具体的协作策略有关。常规的协作策略有并联、串联以及串并联协作策略, 此时优化结构比较简单, 各个优化方法之间的位置可以相互替换, 对MCOA的性能影响不大。MCOA中的协作, 除了建立在迭代优化基础上的协作, 还可以在优化方法的各个优化过程中进行协作, 将优化方法嵌入到其他优化方法的优化过程中, 构成基于嵌入协作的MCOA, 也就是采用嵌入协作策略的MCOA, 称为多方法嵌入协作优化方法 (MECOA, multimethod embedding collaborative optimization algorithm) 。

首先介绍MECOA的基本结构和计算步骤, 然后进行MECOA的优化性能分析。采用2个典型的全局优化测试函数进行MECOA的实例研究。

《2 MECOA基本结构》

2 MECOA基本结构

在MECOA中, 采用其他优化方法作为其优化的一部分的优化方法称为主要方法, 相应的嵌入到主要方法中的优化方法称为辅助方法。

MECOA的基本结构由参与协作的优化方法以及嵌入协作的具体位置有关。一般将辅助方法的嵌入协作部分建立在主要方法的迭代优化的某一中间过程中, 在中间过程中进行辅助方法提供的协作优化信息的整理和利用。

以优化方法A为主要方法、优化方法B为辅助方法, 采用嵌入协作策略的MECOA计算步骤为:

Step 1 对优化方法A和B赋初值。

Step 2 进行优化方法A迭代优化操作, 在此过程中, 将优化方法B作为优化方法A的优化算子进行相应步数 (m步) 的迭代优化操作, 将优化方法B得到的优化信息进行协作处理, 改善优化方法A的优化特性。

Step 3 分析优化方法A得到的优化信息, 进行协作优化信息处理, 判断是否满足协作优化终止准则, 满足则转Step 4, 否则将当前得到的优化信息作为优化方法A的下一步迭代起始信息, 转Step 2。

Step 4 终止MECOA, 将当前得到的最优值作为MECOA的最优值输出。

图1是MECOA的流程图。从MECOA的计算步骤和流程图可知, MECOA的协作是通过辅助方法在主要方法的优化过程中的协作来完成的。不同主要方法的优化过程是不一样的, 优化过程中进行嵌入协作的位置也可以不一样。MECOA的具体的协作优化结构由参与协作的主要方法和辅助方法决定。

《图1》

图1 基于嵌入协作的多方法协作优化方法流程图

Fig.1 Flow chart of MECOA

以典型的遗传算法 (GA, genetic algorithm) ^[2] 为主要方法进行嵌入协作为例, 辅助方法进行嵌入协作的位置可以出现在GA优化过程的不同位置:

1) 辅助方法在GA每一次计算适应值 (函数值的函数) 时进行嵌入协作, 作为改进GA以求取更优的优化点的协作优化。

2) 辅助方法在GA的遗传算子部分进行嵌入协作, 作为GA的1个与复制、杂交、变异平等的遗传算子协作。

3) 辅助方法在GA生成中间群体时进行嵌入协作优化, 对中间群体得到的个体进行协作优化。

4) 辅助方法在GA的遗传算子操作完成后, 对生成的新群体中每1个个体或部分个体进行嵌入协作优化。

图2是GA的流程图, 其中虚线部分是可以进行嵌入协作部分。

《图2》

图2 遗传算法流程图

Fig.2 Flow chart of GA

《3 优化性能分析》

3 优化性能分析

具体的MECOA由参与协作的优化方法和具体的嵌入协作结构决定。由于采用协作优化, MECOA相对于参与协作的优化方法, 其优化特性有一定改变。

《3.1MECOA收敛性分析》

3.1MECOA收敛性分析

MECOA中, 主要方法占主导地位, 其他辅助方法只起到辅助、协作作用。由图1可知, MECOA的结构与主要方法密切相关。MECOA含有主要方法的协作优化信息处理, 一般是对辅助方法协作优化信息的处理, 主要方法对辅助方法的协作优化信息处理得到的协作信息进行利用, 因而MECOA的优化特性完全由含有辅助方法的主要方法决定, 由此可以得到:

性质1 如果MECOA的主要方法是收敛的, 则MECOA也是收敛的。

《3.2MECOA全局性分析》

3.2MECOA全局性分析

MECOA提高全局最优特性的主要途径如下:

1) 提高主要方法本身具有的全局最优特性;

2) 辅助方法的协作优化跳出和跳过主要方法的局部最优;

3) 通过主要方法提供的优化值, 跳过和跳出辅助方法的局部最优。

可见, MECOA的全局最优特性通过主要方法和辅助方法的协作一起提高, 选择全局最优特性较好的优化方法参与协作, 可以提高MECOA的全局最优特性。

《3.3MECOA计算时间分析》

3.3MECOA计算时间分析

MECOA中, 将单独优化方法作为某一个主要优化方法的一个辅助算子, 其优化特性由具体的辅助方法和主要方法的优化特性决定。辅助方法增加了在一次协作过程中的目标函数计算次数, 可能增加MECOA法的计算目标函数次数, 从而增加了计算时间, 提高了主要方法的优化质量。

MECOA的计算时间:

$Τ = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l_{i j}} (S_{i j k} Τ_{f i j k} + Τ_{p i j k}) + \sum_{j = 1}^{n} Τ_{c j} (1)$ $Τ = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l_{i j}} (S_{i j k} Τ_{f i j k} + Τ_{p i j k}) + \sum_{j = 1}^{n} Τ_{c j} (1)$

由式 (1) 可知, 参与协作的优化方法b_i (i=1, 2, …, m) 总数m、协作次数n、协作处理时间T_cj、优化方法b_i的迭代步数l_ij、优化方法b_i每一次迭代计算目标函数f (x) 次数S_ijk、优化方法b_i每一次迭代优化操作时间T_pijk、目标函数f (x) 计算时间T_fijk决定了MECOA的计算时间T (m, n, l_ij, S_ijk, T_fijk, T_pijk, T_cj) 。

由式 (1) 可知, 在其他参数不变的情况下, 减少协作次数n, 可以减少MECOA的计算时间。不同的协作优化终止准则决定了不同的协作次数, 增加协作次数, 增加了协作机会, 一般可以改善 MECOA的最优解特性。因而, 合理确定协作优化终止准则, 可以提高MECOA的优化特性。

《4 实例分析》

4 实例分析

由于MECOA的结构与具体的优化方法密切相关, 在此只选择遗传算法 (GA) 、Powell法 (PM) 、模式搜索法 (PSM) ^[3] 进行实例分析研究, 由不同优化方法协作构成的MECOA的优化特性可能与这3个优化方法有一些差异。这3个优化方法都是基于最优值比较的观点进行迭代优化的, 相互之间可以通过最优值和最优点进行协作。GA在全局性方面具有优势, PSM和PM的局部搜索能力很强, 相互之间具有互补优势, 可以通过相互之间的协作达到求取全局最优解。

《4.1测试函数与具体的MECOA》

4.1测试函数与具体的MECOA

采用以下2个全局优化测试函数 (求最小值) 进行MECOA的测试。

I. Rosenborock 函数

$\begin{array}{l} F (x) = 100 (x_{1} - x_{2}^{2})^{2} + (x_{2} - 1)^{2} (2) \\ - 5 \leq x_{1}, x_{2} \leq 5 ； \end{array}$ $\begin{array}{l} F (x) = 100 (x_{1} - x_{2}^{2})^{2} + (x_{2} - 1)^{2} (2) \\ - 5 \leq x_{1}, x_{2} \leq 5 ； \end{array}$

此函数有无限多个局部最优点, 全局最优点只有1个, 为 (1, 1) , 全局最优值为0。

II. 二维Shubert函数 (Ⅰ)

$\begin{array}{l} \begin{array}{l} F (x) = {\sum_{i = 0}^{5} i \cos [(i + 1) x_{1} + i]} \cdot \\ {\sum_{i = 0}^{5} i \cos [(i + 1) x_{2} + i]} + \end{array} \\ 0.5 [(x_{1} + 1.425 13)^{2} + (x_{2} + 0.800 32)^{2}] ‚ \\ - 10 \leq x_{1}, x_{2} \leq 10 (3) \end{array}$ $\begin{array}{l} \begin{array}{l} F (x) = {\sum_{i = 0}^{5} i \cos [(i + 1) x_{1} + i]} \cdot \\ {\sum_{i = 0}^{5} i \cos [(i + 1) x_{2} + i]} + \end{array} \\ 0.5 [(x_{1} + 1.425 13)^{2} + (x_{2} + 0.800 32)^{2}] ‚ \\ - 10 \leq x_{1}, x_{2} \leq 10 (3) \end{array}$

此函数有760个局部最优解, 只有 (-1.425 13, -0.800 32) 是全局最优点, 全局最优值为-186.730 9。

以GA, PSM, PM 三种单独优化方法的不同组合方式来进行嵌入协作, 构成MECOA。具体的各个MECOA的构造如下:

MECOA 1 GA为主要方法, PM为辅助方法;PM作为GA的1个遗传算子进行协作优化。

MECOA 2 GA为主要方法, PM为辅助方法;PM对GA的遗传算子中间群体的每一个个体进行协作优化。

MECOA 3 GA为主要方法, PM为辅助方法;PM对GA的遗传算子产生的最优个体进行协作优化。

MECOA 4 GA为主要方法, PM, PSM为辅助方法;PM, PSM分别作为GA的一个遗传算子进行协作优化。

MECOA 5 PSM为主要方法, PM为辅助方法;PM作为PSM的一个搜索方向进行协作优化。

GA的群体数目为100, 中间值数目为120, 采用最优值继承的策略, 淘汰中间值中最差的20个个体, 终止准则是在迭代过程中连续40次出现相同的最优值或者计算次数达到最大计算代数 (取1 000) , 变异概率为0.05, 杂交概率为0.80。PSM和PM的终止准则是满足允许误差 (取0.000 000 1) 。其中PM中用到的一维搜索方法采用改进的0.618法^[3]。在MECOA中用到的单独优化方法的参数与采用该优化方法独立优化时一致。在每一次协作优化过程中, 给定GA, PSM, PM的迭代次数为1。协作优化信息处理采用最优值信息处理, 协作优化终止准则是满足GA的终止准则。

《4.2优化及优化结果分析》

4.2优化及优化结果分析

每个优化问题采用不同的随机产生的初值计算100次, 以统计平均比较各个优化方法得到的优化结果。2个全局优化测试问题的优化结果的数据见表1至表4。

表1 优化方法平均最优值

Table 1 Average optima of each method

《表1》

测试函数	Ⅰ	Ⅱ
GA	0.000 5	-143.201 8
PSM	15 262.105 4	-76.131 9
PM	3 357.800 7	-141.745 8
MECOA 1	0.000 1	-186.695 8
MECOA 2	0	-186.526 0
MECOA 3	0	-171.361 2
MECOA 4	0	-186.526 0
MECOA 5	1 699.501 1	-167.940 7

从表1可知, MECOA的平均最优值优于相应参与协作的优化方法的平均最优值。MECOA1的平均最优值优于MECOA5的平均最优值。对于测试函数Ⅰ, MECOA1至MECOA4都取得了等于或接近于全局最优值的平均最优值;对于测试函数Ⅱ, MECOA1, MECOA2, MECOA4的平均最优值接近于全局最优值, MECOA3和MECOA5的平均最优值稍差。

表2 优化方法达到全局最优解次数

Table 2 Times of global best optima each method has reached

《表2》

测试函数	Ⅰ	Ⅱ
GA	57	0
PSM	0	1
PM	84	9
MECOA 1	92	91
MECOA 2	96	88
MECOA 3	100	23
MECOA 4	95	88
MECOA 5	97	17

从表2可知, MECOA的全局最优解次数明显优于相应参与协作的优化方法的全局最优解次数。对于测试函数Ⅰ, 各个MECOA的全局最优解次数接近或等于100。对于测试函数Ⅱ, MECOA1, MECOA2, MECOA4的全局最优解次数较多, 接近100, 而MECOA3和MECOA5的全局最优解次数较少。

表3 优化方法最优值与平均最优值标准差

Table 3 Standard error of optima and average optima of each method

《表3》

测试函数	Ⅰ	Ⅱ
GA	0.001 4	34.084 5
PSM	18 281.978 7	60.561 7
PM	11 187.587 5	46.576 0
MECOA 1	0.000 3	0.111 7
MECOA 2	0.000 1	1.612 2
MECOA 3	0	18.752 3
MECOA 4	0.000 1	1.612 2
MECOA5	10 815.686 1	17.741 0

从表3可知, MECOA的最优值与平均最优值标准差相对于相应参与协作的优化方法有明显的改善。MECOA1的标准差优于MECOA5的标准差。对于测试函数Ⅰ, 除MECOA5以外, 其他MECOA都取得了很好的标准差。对于测试函数Ⅱ, MECOA1的标准差较好, MECOA3和MECOA 5的标准差相对较差。

表4 优化方法计算目标函数值次数

Table 4 Average number of function evaluations of each method

《表4》

测试函数	Ⅰ	Ⅱ
GA	7 545	8 034
PSM	1 803	213
PM	1 971	980
MECOA 1	37 203	23 677
MECOA 2	35 211	24 048
MECOA 3	17 350	14 312
MECOA 4	34 248	24 609
MECOA 5	222 137	2 627

从表4可知, MECOA的计算目标函数值次数和参与协作的优化方法的计算目标函数值次数相比增加较多。其中MECOA1, MECOA2, MECOA4, MECOA5的次数相对于参与协作的优化方法的计算目标函数次数成倍增加。

综合表1至表4的数据可知, MECOA相对于相应参与协作的优化方法具有更好的平均最优值和更好的全局最优解特性, 算法的稳定性也得到提高, 但是成倍地增加了计算目标函数值次数。对于给定的优化问题和优化方法, 合理选择参与协作的优化方法和设置进行嵌入协作的位置, 参与协作的优化方法的数目在2到3之间时便可以满足求取全局优化解的要求。即使采用相同的主要方法与辅助方法、不同的嵌入协作位置构成的MECOA, 其优化特性也可能不一样。

《5 结语》

5 结语

基于嵌入协作的多方法协作优化方法 (MECOA) 采用嵌入协作方式将不同的优化方法协作起来, 相对于参与协作的优化方法, MECOA改善了平均最优值特性, 改进了全局最优特性, 提高了优化方法的稳定性, 但相应增加了计算目标函数次数。嵌入协作的位置不同, MECOA的优化特性也不一样;提高参与协作的优化方法的优化特性可以相应提高MECOA的优化特性。一般情况下, 采用2个优化方法进行嵌入协作就可以取得较好的优化效果, 如上述采用PM作为GA的一个遗传算子进行协作优化的MECOA1。

进一步的研究工作可以在减少MECOA的计算目标函数次数和提高优化效率方面展开, 如参与协作优化的优化方法的选择以及总数对MECOA的优化性能的具体影响, 如何合理设置优化方法迭代步数的以达到最快求解到全局最优解, 不同嵌入协作方式的机理研究, 等等。

展示更多