基于Minmax算法的混沌MIMIC算法

赵晋彬，夏桂梅

(太原科技大学 应用科学学院，太原 030024)

分布估计算法(EDAs)的基本思想是利用变量间的概率分布来表示变量之间的相关关系，并经过迭代进化，逼近问题的最优值，降低了对问题先验知识的要求，是一个很好的连锁学习算法[1]。

对优化算法进行改进以提高算法优化效率的能力是进化计算领域的热门研究课题。将算法进行融合，构建混合算法是算法改进的常用途径。混合算法可以融合多种优化算法的优势，提高算法的性能，更好地平衡算法的收敛性和群体多样性。DE/EDA[2]将差分进化算法与分布估计算法相结合，解决了连续域中的全局优化问题，研究表明DE/EDA要优于DE和EDA算法。PSO-MIMIC算法将微粒群算法(PSO)和分布估计算法相结合，保持群体多样性的同时，具备更好的收敛能力，并结合罚函数法应用于约束优化问题，效果显著[3]。

首先将分布估计算法与混沌算法[4]进行结合，提出混沌MIMIC算法(CS-MIMIC)，实验证明该算法可以收敛到无约束函数的最优解[5]。

在生产和实际优化设计中，大多优化问题为非线性约束优化问题，其数学模型可以表述为[6]：

minf(x)，x∈D

(1)

其中D是可行域。由于混沌MIMIC算法可以大概率搜索到测试函数的阈值，对于以上问题，本文给出另一种思路，就是通过Minmax算法将原问题转换为无约束问题，并利用混沌MIMIC算法进行迭代搜索，提出基于Minmax算法的混沌MIMIC算法(MxCS-MIMIC)。

1 MxCS-MIMIC

1.1 MIMIC算法

图1 MIMIC的概率图模型Fig.1 Probabilistic graphical model of MIMIC

1.2 混沌算法(CS)

在混沌算法中，通常选择Logistic映射所产生决策变量，其形式如下[9]：

(2)

其中：μ为操控参数，当μ=4时，处于完全混沌的状态，且xn在(0，1)范围内是遍历的。

混沌算法步骤如下：

1.3 Minmax算法

约束优化问题因为本身具有约束条件，使得求解此类问题，具有一定的难度，应用某种方法将其转换为无约束问题，是一种常见的解决方式。Minmax算法是一种可以解决这类问题的方法[13]。Minmax一般定义：

约束问题函数:

minF(x)

s.t.gi(x)≤0，i=1，…，m

(3)

转化后的无约束问题函数：

(4)

其中，αi(αi>0)为参数，类似于罚函数中的罚参数μ.能够证明式(3)问题对充分大的αi等价于式(4)问题。

1.4 MSCS-MIMIC算法

算法实现过程如下：

步1：随机生成若干个体组成初始种群N；

步2：利用Minmax算法将约束优化问题转化为无约束优化问题；

步3：评估初始群N，如果连续搜索至相同值或找到最终的最优解，算法结束，否则进入下一步骤；

步4：使用截断选择、轮赌选择，将S个变量选出作为主导变量群体，其中S=N/2；

步5：按照贪婪算法构建优势模型[14]：

(1)根据in=argminjhl(Xj)找出排列π=(i1，i2，…，in)中的in

(2)对任意k=n-1，…，1，根据ik=argminjhl(Xj|Xk+1)，其中k≠ik+1，…，in，计算出排列π=(i1，i2，…in)

步6：用混沌算法对优势群体进行搜索，对搜索后的优化值进行评价，并更新已知的最优值；

步7：合并种群，将根据模型产生的优势值与保留的优势群体组成新的种群，转到步2.

2 算法性能测试及分析

2.1 参数设置

为检测算法的性能，对下面六个约束函数进行检验[15]。

在实验中，MIMIC算法的参数设置如下：群体数量N=300，截断选择为N/2，最大迭代次数范围[10，50]，这里选择30次。混沌算法参数设置如下：迭代次数为30次，对优势群体的20%进行迭代实验。

函数1：

minf(x)=(x1-2)2+(x2-1)2

函数2：

minf(x)=(x1-10)2+5(x2-12)2+

4x6x7-10x6-8x7

函数3：

函数4：

函数5：

函数6：

37.293 239x1-407 92.141

0≤85.334 407+0.005 685 8x2x5+

0.000 26x1x4-0.002 205 3x3x5≤92

s.t.90≤80.512 49+0.007 131 7x2x5+

20≤9.300 961+0.004 702 6x3x5+

0.001 254 7x1x3+0.001 908 5x3x4≤25

78≤x1≤102，33≤x2≤45，

27≤xi≤45，i=3，4，5

2.2 实验结果及分析

本文将从两种情况分析算法的性能，并与结合了Minmax法的MIMIC算法进行比较。

由于6个函数在维数、运算复杂度和约束条件上有所不同，因此针对不同的函数，算法进化代数上也做出了相应的调整。在经过大量的实验运算之后，本文找出MxCS-MIMIC算法在测试6个函数能达到最优值(或算法陷入局部最优)时，算法所设置的固定进化代数如下：Nf1=100，Nf2=150，Nf3=50，Nf4=200，Nf5=50，Nf6=500.

(1)算法能否收敛到函数的最优值

表1所示是算法在经过30次迭代后的数据结果。可以看出，对于6个测试函数，MxCS-MIMIC算法找到了函数1、3、5的最优值，MIMIC算法找到了函数3、5的最优值，以及函数1的近似值；对于函数2、4，MxCS-MIMIC算法搜索到了最优值附近，且误差较小，MIMIC算法也搜索到了最优值附近，并且函数2的误差比MxCS-MIMIC小，函数4的误差比MxCS-MIMIC大；对于函数6，算法在经过500代更新后，两种算法都未找到最优值，但是MxCS-MIMIC算法比较接近最优值，MIMIC算法在500代内并没有得出较好的结果。

表1 两种算法优化所得结果Tab.1 The optimization results of the two algorithms

(2)算法的平均进化代数

表2是算法在经过30次迭代后的平均进化代数，可以看出，相较于结合了Minmax法的MIMIC算法，MxCS-MIMIC算法在寻优能力较强的情况下，运用了较少的进化代数达到了最优值，这与算法结合了混沌算法，提高了算法的收敛效率是分不开的。

表2 到达确定最优值的平均进化代数Tab.2 Average evolution algebra to determine optimal value

3 结论

基于Minmax算法的混沌MIMIC算法(MxCS-MIMIC)不仅继承了混沌算法寻优能力高，运行速度快的特点，此外它还具有MIMIC算法的细化能力和稳定性，是一种有效的优化算法。从两组实验得出的数据可以看出，MxCS-MIMIC算法能够以较高的精度收敛到最优值附近，或者直接收敛到全局最优值，并且最优值可以在较小的进化代数内找到，这对改进类似优化算法提出一种新的尝试。