一种结合信赖域算法的混合mimic算法

《一种结合信赖域算法的混合mimic算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第38卷第2期温州大学学报（自然科学版）2017年5月Vol38,No2JournalofWenzhouUniversity(NaturalScienceEdition)May,2017一种结合信赖域算法的混合MIMIC算法夏桂梅，张文林(太原科技大学应用科学学院，山西太原030024)摘要：针对分布估计算法在求解问题的过程中局部搜索能力较弱的缺点，引入了信赖域算法，提出了结合信赖域算法的分布估计算法．由于信赖域算法是一种很好的局部快速寻优方法，因此在分布估计算法的基础上，再对每一个粒子分别实施信赖域算法，能够加强算法的局部搜索

2、能力．新算法不仅保持了种群的多样性，而且具备更全面的学习能力，提高了算法的寻优能力，避免早熟收敛的发生．数值试验结果表明：该算法能收敛到满足约束条件的最优解，并且具有很强的搜索能力，为解决非线性约束优化问题提供了一种新的有效途径．关键词：分布估计算法；信赖域算法；MIMIC算法中图分类号：O221文献标志码：A文章编号：1674-3563(2017)02-0001-07DOI：10.3875/j.issn.1674-3563.2017.02.001本文的PDF文件可以从xuebao.wzu.edu.cn获得分布估计算法（Esti

3、mationofDistributionAlgorithm，简称EDA）是1996年提出的一种基于[1]概率模型的优化算法，EDA在进化过程中通过统计方法建立解空间的概率分布模型，然后对模型进行采样得到新一代群体，如此反复进行，直至实现种群的进化．它不涉及在传统算法中出现的交叉变异等操作步骤，减少了参数设置，简化了计算过程，因而可解决一些传统算法难以解决的优化问题．根据变量之间的相关性，将分布估计算法分成下列三类：变量之间相互独立的分布[2]估计算法、双变量相关的分布估计算法，以及多个变量相关的分布估计算法．然而，EDA在后期进

4、化过程中速度很慢，且每一次的进化改变也很小，究其原因在于EDA在构建概率模型过程中，对空间内解分布过于依靠，多次迭代后，种群多样性减少，这些情况说明EDA的局部搜索[3]能力较弱．鉴于EDA的此缺陷，在种群的进化过程中加入局部搜索能力很高的信赖域算法，提出一种结合信赖域算法的分布估计算法．新算法是在原分布估计算法基础上加入信赖域算法，在每次迭代过程中，粒子在进行完分布估计算法步骤后再对每一个粒子实施信赖域算法，寻找更优个体，这样，新算法不仅利用了分布估计算法全局搜索能力强的优点，且利用了信赖域算法局部搜索能力强的优点，同时保持了

5、种群多样性，因而具备更全面的学习能力，提高了算法的寻优能力．1结合信赖域算法的混合MIMIC算法1.1罚函数法[4]罚函数法的思想是将约束优化问题通过构造一个增广目标函数转化为无约束优化问题，从收稿日期：2015-11-10基金项目：山西省自然基金(2014011006-2)；太原科技大学研究生教改项目(20133001)作者简介：夏桂梅(1968-)，女，山西大同人，副教授，研究方向：最优化理论与应用2温州大学学报（自然科学版）(2017)第38卷第2期而利用有关的无约束问题来研究约束极值问题．经常采用的方法是在原来的目标函数

6、上加上一个由约束函数组成的一个“惩罚项”来迫使迭代点逼近可行域．罚函数的定义为：nFx()fx()Hxhkx()(),DR．（1）其中，fx()为约束优化问题中的目标函数，hk()是随着迭代次数在变化的动态罚值，k是种群的迭代次数，Hx()是多段映射惩罚因子，其定义如下：m(())qxiHx()(())()qxqxii．（2）i1其中qx()max{0,px()},i1,2,,m，px()为原约束优化问题中的约束条件函数，包括等iii式函数与不等式函数，qx()是约束冲突函数，(())qx是一个多级赋值

7、函数，(())qx是罚函iii数的力度，h(.)，(.)，(.)是依赖于具体的问题．1.2MIMIC算法MIMIC算法（MutualInformationMaximizationforInputClustering）是最早提出的一种双变量[5]相关的分布估计算法，它将变量之间的关系简单化，只考虑相邻的两个变量之间的关系，避免了遗传算法中的交叉和变异等操作，减少了参数的设置，更容易求解．[6]DeBonet等人在1997年提出的MIMIC算法是用链式结构来表示变量之间的关系，其模型图如图1所示．对于需要优化的变量(,xx,

8、,x)，存在一个最优的排列π(,,ii,)i，使得根据优势群12n12nπ体估计出来的概率分布模型px()px(

9、x)px(

10、x)px(

11、x)与优势群体的实际概lli1i2li2i3lin1inπ率分布ppxx(

12、xpx)(

13、xx)px(

14、xp