结合模式搜索法的混合MIMIC算法

张 丹,夏桂梅

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



结合模式搜索法的混合MIMIC算法

张 丹,夏桂梅

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

分布估计算法是一种全局寻优能力较强而局部求精能力较弱的优化算法，为增强分布估计算法的局部寻优能力，将局部求精能力强，收敛速度快的模式搜索法引入到分布估计算法中，提出一种结合模式搜索法的混合MIMIC算法(PS-MIMIC).通过测试函数测试算法性能，并与标准MIMIC算法结果进行比较，结果表明该算法在解决优化问题时具有良好的性能，可以较快的寻找到最优值。

分布估计算法；模式搜索法；MIMIC算法

分布估计算法(EDA)源于遗传算法，是一种基于统计学习理论的群体进化算法[1]，最早在1996年提出并得到了迅猛的发展，目前已经成为人工智能领域的研究热点[2]。它的基本思想是从初始群体中选择一部分优秀个体，通过对当前优秀个体集合建立概率模型来指导新群体的生成，如此反复进行，直到搜索到问题的满意解。概率分布的模型有很多种，目前，根据变量之间的相关性，分布估计算法可以分为变量无关分布估计算法，双变量相关分布估计算法和多变量相关分布估计算法[3]。

由于分布估计算法的过程是一个不断更新概率模型，从而使概率模型越来越能反映优秀个体的分布的过程，所以在进化过程中，容易对解空间分布过于依靠，导致算法在后期的进化过程中速度变慢，种群的多样性减少，这说明分布估计算法具有比较强的全局搜索能力，但是局部求精能力弱。为了有效提高分布估计算法的求精能力，可以在分布估计算法中加入其他优化算法，例如文献[4]在分布估计算法的基础上加进了微粒群算法，文献[5]是基于罚函数的分布估计算法。本文是在种群的进化过程中加入了局部求精能力强，收敛速度快的模式搜索法(Pattern Search)，提出一种结合模式搜索法的分布估计算法(PS-MIMIC).

1 PS-MIMIC

1.1 模式搜索法

模式搜索法又叫Hooke-Jeeves方法[6]，是Hooke和Jeevs在1996年提出的。模式搜索法是对当前迭代点按照固定模式和步长进行探索移动，来寻求函数的下降方向的直接搜索方法，它不必要求目标函数必须连续或者可导，是求解求导麻烦或者不可导优化问题的一种有效方法[7]。如文献[8]，文献[9]，和文献[10]都是模式搜索法的应用。

模式搜索法的基本思想是：算法从某个初始点开始，交替进行轴向移动和模式移动。轴向移动是依次沿n个坐标轴的方向进行，目的是确定新的基点和有利于函数值下降的方向。模式移动是沿着相邻两个基点的连线方向进行，目的则是沿着有利方向加速运动[4]。

模式搜索算法的步骤如下：

步2 令y=xk；

步3 从y出发，依次作平行于单位矢量ej(j=1,…,n)的轴向探测移动：

步4 令xk+1=y，若f(xk+1)

1.2 MIMIC算法

MIMIC(Mutual Information Maximization for Input Clustering)算法，即输入聚类最大互信息算法，是在1997年由美国MIT人工智能实验室的De Bonet等人提出的一种双变量分布估计算法[11]。在此算法中，用链式结构描述变量之间的关系，如下图所示:

设随机变量集合x=(x1,x2,…,xn)的联合概率分布是p(x)=p(x1,x2,…,xn)，即有

p(x)=p(x1|x2,…,xn)p(x2|x3,…xn)…

p(xn-1|xn)p(xn)

算法中解空间的概率模型描述为：

其中，h(X) = -∑xP(X=x)logp (X=x)，

h(X|Y)=-∑yh(X|Y=y)p(Y=y)，

h(X|Y=y)=

1.3 PS-MIMIC

模式搜索法是一种局部搜索算法，具有较强的局部求精能力，而MIMIC算法的全局搜索能力强，局部搜索能力较弱，所以在MIMIC算法进化过程中可以加入模式搜索算法来提高算法的寻优能力和效率。在MIMIC算法中，由于新个体的产生规则单一，导致新群体个性差异较小，为了增加种群的个性差异，同时又不背离群体的分布模型，在生成新的群体时，从当前群体中随机选择出部分个体进行模式搜索，将得到的新个体作为新群体中的一部分。具体步骤如下：

步1 初始化群体。随机产生N个个体作为初始群体。

步2 评价适应值。计算种群中每个个体的适应值，若满足算法终止条件，则算法结束，否则转下一步。算法的终止条件为达到规定的进化代数(500代)，或者连续若干代(25代)最优值没有变化，或者误差在某个范围内(10-50)。对于约束问题，利用罚函数法转化为无约束问题。

步3 选择优势群体。采用截断法和轮盘赌法选择S(N/2)个个体作为优势群体，并保留p个最优个体。

步4 模式搜索法搜索。从当前群体中选择T个个体作为初始点进行模式搜索，将得到的新个体作为新一代群体的一部分。

步5 根据贪婪算法寻找最优排列构建概率模型。

(3)计算出概率分布

pl(xi1|xi2)pl(xi2|xi3)…pl(xin-1|xin)pl(xin)

步6 采样得到新个体。按逆序的方法依据概率模型采样N-T-p次，与步3保留的p个最优个体及模式搜索法得到的T个个体组成新一代群体，转步2.

2 数值实验

2.1 测试函数

为了测试算法性能，并与基本的MIMIC算法进行比较，对下面四个测试函数[12]进行测试。

-10≤xi≤10

-5.12≤xi≤5.12

-10≤xi≤10

-600≤xi≤600

2.2 参数设置

在实验中，算法的参数设置如下，群体规模N=200，截断选择S=N/2，保留最优个体数p=20，进行模式搜索法的初始点个数T=50，最大迭代次数500，精度10-6，加速系数γ=1.4，收缩系数θ=0.2，分别进行30次实验。

2.3 实验结果及分析

为了测试PS-MIMIC的性能，本文采用如下三种性能指标对实验结果进行分析。

(1)在固定进化代数内，算法得到的最优值及平均最优值，本文采取固定进化代数为500.

表1 500代内算法优化所得结果

Tab.1 The results of the algorithm within 500 generations

函数f(x*)PS-MIMIC最优值PS-MIMIC平均值MIMIC最优值MIMIC平均值10001.0891.913200004.011300000400000.223

由表1可知，PS-MIMIC算法对测试函数进行30次试验后都可以找到最优值，且与函数已知最优值一样，说明PS-MIMIC算法在固定的进化代数内可以得到很好的优化结果。同时，也可由表中看出，与标准的MIMIC算法相比较，PS-MIMIC算法在求精能力上有了进一步的提高，说明该算法具有一定的优势。

(2)到达确定阈值时的平均进化代数。

表2 到达确定阈值的平均进化代数

Tab.2 The average evolution algebra to determined threshold

函数PS-MIMICMIMIC1125—2621143342500479143

表2给出PS-MIMIC算法和标准MIMIC算法到达确定阈值的平均进化代数，四个函数的阈值均为0.通过表2可以看出，对于四个测试函数，PS-MIMIC算法的平均进化代数都要明显优于MIMIC算法，说明与标准MIMIC算法相比，PS-MIMIC算法具有较快的收敛能力，其中函数1，MIMIC算法在最大进化代数内没有达到确定阈值，所以没有进化代数。

(3)达标率

表3 到达预设阈值时的达标率

Tab.3 The target rate while reaching the preset threshold

函数PS-MIMICMIMIC1100%02100%13.33%3100%100%4100%33.33%

表3给出了MIMIC算法和PS-MIMIC算法到达预设阈值时达标率的比较结果，由表3可以看出，对于四个测试函数，PS-MIMIC算法的达标率都达到了100%，而在MIMIC算法下，函数1 的达标率为0，函数2的达标率为13.33%，函数3的达标率为100%，函数4的达标率为33.33%，所以PS-MIMIC算法的达标率明显优于标准MIMIC算法，说明PS-MIMIC算法的有效性和可靠性。

下图1-4分别给出了函数1-函数4的MIMIC 算法和改进后的算法在相同进化代数下的函数值的仿真实验图，从图中可以看出与标准的MIMIC算法相比，PS-MIMIC算法可以快速的找到最优值附近且收敛速度上要明显优于标准的MIMIC算法。

综上所述，结合模式搜索发的混合MIMIC算法是一个有效的，可行的优化算法，具有较强的寻优能力和较快的收敛速度，相比标准的MIMIC算法具有一定的优势。

图1 两种算法在函数1所获收敛曲线比较

Fig.1 Comparison of the convergence curves of two kinds of algorithms on f1

图2 两种算法在函数2所获收敛曲线比较

Fig.2 Comparison of the convergence curves of two kinds of algorithms on f2

图3 两种算法在函数3所获收敛曲线比较

Fig.3 Comparison of the convergence curves of two kinds of algorithms on f3

图4 两种算法在函数4所获收敛曲线比较

Fig.4 Comparison of the convergence curves of two kinds of algorithms on f4

4 结束语

从仿真实验结果可以看出，与标准的MIMIC算法相比，结合模式搜索法的混合MIMIC算法可以更精确的求得最优值，且到达确定阈值时的进化代数和达标率都要优于标准的MIMIC算法，所以结合模式搜索法的混合MIMIC算法既结合了MIMIC算法的全局搜索能力强的优点，又结合了模式搜索法局部求精能力强，收敛速度快的优点，使得该算法在解决优化问题时具有较强的寻优能力和较快的收敛速度，它不要求优化函数必须连续或者可导，它是求解不可导或者求导麻烦的函数的一种有效方法。

由于该算法结合了两种算法，涉及参数较多，所以对于参数设置的问题有待做进一步的研究，在保证更快的收敛速度前提下寻找更精确的解。

[1] LARRANAGA P, LOZANOJ A. Estimation of distribution algorithms: A new tool for evolutionary computation [M]. Boston: Kluweer Press, 2002.

[2] 王丽芳,曾建潮,洪毅. 利用Copula函数估计概率模型并采样的分布估计算法[J]. 控制与决策,2011,26(9):1333-1337.

[3] 周树德,孙增圻.分布估计算法综述[J].自动化学报,2007,33(2):115-118.

[4] 龚纯,王正林.精通Matlab最优化计算[M].北京：电子工业出版社,2012.

[5] 张文林,夏桂梅.一种结合微粒群算法的混合MIMIC算法[J].太原科技大学学报,2015,36(5):406-410

[6] 张金凤,夏桂梅,王泰.一种基于罚函数的混合分布估计算法[J].西南民族大学学报：自然科学版，2015,41(1):120-123

[7] 吴兴远.模式搜索法在最优化问题中的应用[J].软件导刊,2009,8(8)：122-123.

[8] 唐超宏，莫海鸿，刘少跃.模式搜索法在边坡稳定性分析中的应用[J]. 华南理工大学学报,2000,28(2)：42-46.

[9] 淳静,吴宇列,戴一帆等. 模式搜索法在光纤有源自动对准中的应用[J]. 光学精密工程,2006,14(2)：236-241.

[10] 莫海鸿,唐超宏,刘少跃. 应用模式搜索法寻找最危险滑动圆弧[J]. 岩土工程学报，1999，21(6)：696-699.

[11] DE BONET J S, ISBELL C L, VIOLA P. MIMIC: Finding optima by estimating probability densities [J]. Advances in Neural Information Processing Systems, 1997, 9:424-430.

[12] 王丽芳.copula分布估计算法[M].机械工业出版社,2012.

A Hybrid MIMIC Algorithm Combined with Pattern Search Algorithm

ZHANG Dan, XIA Gui-Mei

(School of Applied Science, Taiyuan University of Science and Technology, Taiyuan 030024)

Estimation of distribution algorithm is an algorithm with higher global optimization ability but lower partial refinement ability. To enhance the partial refinement capacity of this algorithm, this paper introduced pattern search algorithm which belongs strong local refinement ability and fast convergence rate to the estimation of distribution algorithm, and then proposed a hybrid MIMIC algorithm combined with pattern search algorithm. Through testing the performance of the algorithm with test function and comparing the results with the standard MIMIC algorithm, we conclude that the algorithm has good performance in dealing with optimization problem and the optimal value can be found rapidly.

estimation of distribution algorithms, pattern search, MIMIC algorithm

1673-2057(2016)06-0490-05

2016-01-28

太原科技大学校研究生教改项目(20133001)

张丹(1990-)，女，硕士研究生，研究方向：最优化理论与应用；通信作者：夏桂梅副教授，Email:xiaguimeiznn@163.com

0221

A

10.3969/j.issn.1673-2057.2016.06.014