一种基于随机排序法的混合MIMIC算法

张金风，夏桂梅

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



一种基于随机排序法的混合MIMIC算法

张金风，夏桂梅

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

通过随机排序法思想定义 panduan函数来处理约束条件，提出一种基于随机排序法的混合MIMIC算法，改进后的MIMIC算法能够搜索到非线性约束优化问题的最优解.数值试验表明：该算法具有很强的全局搜索能力，能收敛到满足约束条件的全局最优解，是解决非线性约束优化问题的一种有效算法.

MIMIC算法；随机排序法；非线性约束优化问题

在工程和科学等领域中，优化问题的求解往往受到现实因数的制约，这些制约是由一系列的约束条件来描述的，可以表示为线性，非线性，等式和不等式等，因此求解约束问题比求解无约束问题更加困难.

非线性约束优化问题可表述为：

其中，D是可行域.

求解约束问题的传统算法，对目标函数和约束条件有连续性和可微性要求，只能分析一些具有较好性质的函数，随机性算法对函数要求低，仅需函数适应值.MIMIC算法[1]是一种新型的随机优化算法，对函数无任何连续可微要求.

MIMIC是基于优势群体的概率模型进化算法，与遗传算法（GA）迭代不同，它并不是通过交叉和变异算子的手段迭代，而是根据当前解空间的优势群体建立概率分布模型，并利用所建立的概率模型抽样来产生下一代新群体，如此迭代进化，直到满足所设置的终止条件.MIMIC算法是基于解空间的宏观层面的进化算法，具备更强的全局搜索能力，该算法已被成功地应用于求解旅行商问题[2]和多约束集装箱装载问题[3]以及其它工程领域[4]，如何将MIMIC算法应用于约束优化问题，特别是非线性约束优化问题，是一个重要的研究方向.

对于问题（1）和（2），本文给出一种新型的算法，借签随机排序法思想，定义 panduan函数来处理约束条件，并利用MIMIC算法求解.试验结果表明，所给算法是可行有效的.

1 MIMIC算法的改进

1.1 MIMIC算法

分布估计算法（EDAs）是一种新型的基于解空间分布的概率模型进化算法[5]，其根据当前优势群体的概率分布，抽样产生新的群体，既按照一定的选择方式先从当前群体中选出一部分较好的个体作为优势群体，并建立其概率分布模型，然后利用分布概率模型抽样产生新的群体，如此迭代进化，直到满足所设置的终止条件.

MIMIC算法是双变量相关的分布估计算法的一种，是由美国MIT人工智能实验室的Bonet De[6]等人于1997年提出的一种启发式优化算法.在MIMIC模型中，各变量是一种链式关系，解空间的概率模型为：

其中，π=(i1, i2,…,in)为变量x1, x2,…xn的一种排列，pl(xij|xi j+1)为第ij+1个变量取值为xij+1的条件下第 ij个变量取值为xij的条件概率.MIMIC算法中，建立优势群体的概率模型时，期望寻找最优排列，使pπl与试验中得到的每代优势群体的概率分布pπl(x)最相近.

l

衡量两个概率分布之间的距离，可以用K-L距离，定义如下：

寻找最优的排列π*使K-L距离Hlπ(x)最小化.为了不把所有的n!个可能排列都穷举，本文利用贪心算法[6]来搜索变量的近似最优排列.

MIMIC算法中，每一次迭代，都要根据选择的优势群体建立概率模型pπl(x)，然后由pπl(x)

抽样产生新的群体，其基本思想是按照π*的逆序，对第in, in-1,…,i1个变量依次采样，构造一个完整的解向量.步骤如下：

1）j=n，根据第ij个变量的概率分布pl(xij)，随机采样产生第 ij个变量；

2）根据第ij-1个变量的条件概率分布pl(xij-1|xij)，随机采样产生第ij-1个变量；

3）j=j-1，如果j=1，则一个完整的解向量构造完成，否则转2）.

1.2 随机排序方法

随机排序法（SR）是由Runarsson和Yao[7]提出的一种新型处理约束条件的方法，主要思想是根据约束违反程度和目标函数值的大小对解按一定概率进行排序，当两个解满足约束条件时，目标适应值越小越被放在前面，其它情况下以概率pf按照目标适应值大小对解进行排列，以概率1-pf按照约束违反程度的大小对解进行排列，来实现约束优化问题求解过程中约束条件的满足和目标函数值改进之间的权衡，具体流程图如图1.

图1 随机排序操作流程图

本文借签SR思想，定义panduan函数，根据解的约束违反程度对解进行排序，约束违反程度越小越排在前面，当两个解约束违反程度相等时，以概率pf按照目标适应值大小对解进行排列，以概率1-pf按照约束违反程度的大小对解进行排列.

定义违反约束程度：

其中，hi(x)为每个约束条件的违反程度，h(x)为总约束违反程度.

定义panduan函数如下：

其中，上式中1代表为真，0代表假，对于两个个体，当panduan为1时，表示x2比x1好，否则，表示x2没有x1好.

1.3 基于随机排序法的混合MIMIC算法

针对非线性约束优化问题，借签SR思想，定义panduan函数，对群体按panduan函数从好到坏排序.

具体步骤如下：

1）设置参数，随机产生N个个体作为初始群体pop0，k→0；

2）计算群体中每个个体的适应值和约束违反程度，利用panduan函数和随机排序概率pf对群体中所有个体进行从好到坏排序，并仍记为popk，x1为最好个体，xN为最不好个体；

3）当panduan(x1, xN)为1时，算法结束，否则算法继续进行迭代；

4）用截断和轮盘赌选择M(M＜N)个体作为优势群体，并保留最优个体p个；

5）根据贪婪算法寻找最优排列而建立优势群体的概率模型；

6）按逆序从概率模型中采样m次，当panduan函数为1时，xk+1代替xk，形成新的个体，与p个最优个体形成新一代群体popk+1，转步骤2）（m=N-p）.

2 数值试验

2.1 测试函数

为了验证改进算法的可行性和有效性，选取测试函数[8-9]如下：

2.2 试验方法

试验中算法参数设置为：群体规模为2 000，进化代数为300，精度为10-3，各进行15次仿真试验.对数值测试结果和进化代数进行统计，并分析结果.

2.3 试验结果

2.3.1 随机排序概率pf对试验结果的影响

随机排序法主要思想是根据约束违反程度和目标函数值的大小对解按一定概率pf进行排序，由此来实现约束条件的满足和目标函数值改进之间的权衡.在仿真实验中，令参数概率值pf取值从0.2开始，按0.05递增至0.95为止，分别对四个测试函数进行仿真实验，共60组参数.结果发现，参数概率值pf对测试函数的进化代数均有影响，但具体到每个函数，变化均不相同，比如随机概率值0.65以后，函数1的进化代数随着随机概率值的增大而变大，函数2却刚好相反.结果如图2.

2.3.2 优势群体个数对独立运行时间的影响

在仿真实验中，取参数概率值pf为定值0.8，令优势群体个数的取值从500开始，按100递增至2 000为止，分别对四个测试函数进行仿真实验，共60组参数.结果发现优势群体个数对测试函数的进化所需时间均有影响，整体趋势是随着优势群体个数增大而增大，说明MIMIC算法在总群体规模一定和满足精度要求的情况下，优势群体个数对进化速度有一定影响，选取合理的优势群体个数，可以提高进化速度.结果如图3.

2.3.3 测试函数的试验结果

表1给出了每个标准测试函数独立运行15次实验的最优解的最好值、平均值，且给出了文献[8]和[9]的每个测试函数的已知最优解f(x*)以及本文算法的最优解与已知最优解的偏差.

图3 进化所需时间和优势群体个数的关系图

表1 测试函数试验结果

从表1可知，本文算法在15次试验中能找到测试函数已知的最优解，说明该算法的寻优成功率较高，且本文的最优解与已知最优解的偏差都接近于0，说明该算法是有效的.

表2给出了本文算法与文献[10]的GA算法对测试函数的结果比较，其中本文算法为15次实验结果，GA算法为10次实验结果，结果如表2所示.

表2 本文算法和GA算法的性能比较

由表2可知，从平均结果来看，本文算法的平均值与已知最优解相等或是相近，对于测试函数3，本文算法结果与已知最优解相差0.000 2，而GA算法平均值与已知最优解相差0.016 7，说明本文算法优于GA算法.试验结果验证了本文算法的有效性和合理性.

3 结束语

文章借签随机排序法（SR）思想，定义了panduan函数，对群体按panduan函数从好到坏排序，约束违反程度越小越被放在前面，当约束违反程度相等时，以概率pf按照目标适应值大小对解进行排列，以概率1-pf按照约束违反程度大小对解进行排列，实现了约束违反程度的满足和目标适应值的改进，提出了改进的MIMIC算法.

试验仿真结果证明改进的MIMIC算法能够收敛到满足约束条件的全局最优解，说明该算法有一定优势，从而为解决非线性约束优化问题提供了一种新的且有效的途径.

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

[2] 黄宝珠, 肖箐. 改进的MIMIC算法求解旅行商问题[J]. 计算机工程与设计, 2010, 31(16): 3650-3654.

[3] 左先亮, 郭莉莉, 高尚. 改进分布估计算法解决多约束集装箱装载问题[J]. 科学技术与工程, 2014, 14(11): 117-118.

[4] 武燕, 王宇平, 邓小雄, 等. 求解动态优化问题的自组织进化算法[J]. 控制与决策, 2009, 24(5): 655-657.

[5] 王圣尧, 王凌, 方晨, 等. 分布估计算法研究进展[J]. 控制与决策, 2012, 27(7): 961-963.

[6] De Bonet J S, Isbell C L, Viola P. MIMIC: Finding optima by estimating probability densities [EB/OL]. [2014-08-08] http://wenku.baidu.com/link?url=rMtf5-Y8b5RwZQwzEbO3zuPHbX8aEUoQN4EXmDShJ7T9lKW_vi288WhFrsd NJC8BQFzsw3BCjhbVLME5UhdB68yeCgiE-pfVhysoP0Cx0s_.

[7] Runarsson T P, Yao X. Stochastic ranking for constrained evolutionary optimization [J]. Transactions on Evolutionary Computation, 2000, 4(3): 284-294.

[8] Runarsson T P, Yao X. Search biases in constrained evolutionary optimization [J]. Transactions on systems, man, and cybernetics part c: applications and reviews, 2005, 35(2): 238-242.

[9] 屈向红, 夏桂梅, 王希云. 求解约束优化问题的改进微粒群算法[J]. 太原科技大学学报, 2012, 33(5): 407-408.

[10] Koziel S, Michalewicz Z. Evolutionary algorithm, homomorphous mappings, and constrained parameter optimization [J]. Evolutionary computation, 1999, 7(1): 19-44.

A Hybrid MIMIC Algorithm Based on Stochastic Ranking

ZHANG Jinfeng, XIA Guimei (School of Applied Science, Taiyuan University of Science and Technology, Taiyuan, China 030024)

A hybrid MIMIC algorithm based on stochastic ranking is proposed in this paper by means of the random ranking method to define panduan function in order to solve the constraint condition. The improved MIMIC algorithm is able to detect the optimal solution of nonlinear constraint optimization problem. The numerical experimentation indicates that the proposed algorithm has stronger global search ability and is able to converg the globally optimalsolution to meet the need of constraint condition. Therefore, such an algorithm is an effective arithmetic to solve nonlinear constraint optimization problem.

MIMIC Algorithm; Stochastic Ranking; Nonlinear Constraint Optimization Problem

O221

A

1674-3563(2016)01-0001-06

10.3875/j.issn.1674-3563.2016.01.001 本文的PDF文件可以从xuebao.wzu.edu.cn获得

(编辑：王一芳)

2014-10-11

张金风(1986- )，女，山西大同人，硕士研究生，研究方向：最优化理论及其应用