论文部分内容阅读
分布估计算法是一种通过对优势候选解构建概率模型和采样,探索可能的解空间的随机优化技术。在分布估计算法中没有传统遗传算法的交叉和变异操作,取而代之的是对选择出来的优势群体的概率分布模型进行估计并根据估计的模型进行采样。多变量相关的分布估计算法是目前研究的难点,为反映变量的相关性,往往采用贝叶斯网络、高斯网络或马尔科夫网络等结构,或者假设变量服从联合正态分布,但这种假设往往不能准确地反映实际优化问题中变量的相关性。Copula理论表明,可以将一个联合分布分解成n个边缘分布和一个copula函数,从而可以对它们的边缘分布和相关结构分别加以研究。而分层copula函数可以将高阶copula函数分解为多个低阶的copula函数,论文研究的基于分层copula函数的分布估计算法正是利用了这一特点,构造了更为灵活的概率模型,从而克服了多变量正态分布模型的缺陷。分层copula函数主要研究高维问题复杂的相关关系,涉及到copula函数如何构造和选择以简化问题处理的复杂度。论文针对高维优化问题,研究了基于copula分布估计算法中copula函数的选择问题、基于不同分层copula形式的分布估计算法(包括嵌套copula、pair-copula分解模型中的C藤、D藤等),以及基于copula熵的高阶藤结构分布估计算法的模型降阶问题。最后将算法应用于无线传感器网络覆盖问题的求解。主要完成的工作如下:1.基于两种不同copula函数选择方式的分布估计算法。在基于copula函数的分布估计算法中,如何选择合适的copula函数,是一个亟待解决的难题。在研究混合copula函数的基础上,给出了一种新的copula函数选择方法,称为切换copula函数。将切换copula函数与分布估计算法相结合,给出了基于切换copula函数的分布估计算法。在此算法中,选择的不是固定的copula函数,而是按照轮盘赌的原则依一定的概率在备选copula中进行切换,文中给出了一种对copula函数被选中概率进行自适应调整的策略。仿真结果表明,基于混合copula函数的分布估计算法计算量会大大增加,基于切换copula函数的分布估计算法在耗用时间上与采用固定的copula函数的分布估计算法几乎相同,但优化效果要优于后者。2.基于嵌套copula函数的分布估计算法。嵌套的阿基米德copula函数将二元阿基米德copula函数扩展到高维问题,用来研究多维变量的相关性,相对简单和实用。在可交换阿基米德copula采样方法和d维嵌套阿基米德copula的采样方法的基础上,详细讨论了三维嵌套阿基米德copula的采样方法。最后,给出了基于嵌套copula函数分布估计算法的一般框架,并以三维嵌套Gumbel copula函数为例,给出了具体的算法步骤。仿真结果显示所有测试函数的收敛率都大于80%,收敛代数也非常合理,表明此方法不仅可行而且有效。3.基于藤结构的分布估计算法。Pair copula分解法将高维随机向量转化为一系列二元的copula模块和单变量边缘密度函数的乘积,在描述高维相关结构时更加灵活。藤结构是一种特殊的Pair copula分解方法。在讨论C藤和D藤的结构图、层次图及密度函数表达式的基础上,给出了C藤和D藤的参数估计算法及采样算法,进而给出了基于藤结构的分布估计算法框架。仿真结果表明该算法能够有效地解决多维数值优化问题,其全局探测能力较强。4.基于copula熵的多维藤分布估计算法。为减轻高阶藤结构带来的繁重的计算负担,将信息论和copula熵引入,利用coupla熵与互信息及Kullback-Leibler距离的关系,对高阶藤结构模型进行降阶简化。在最大限度减少由于模型降阶造成的信息损失的前提下,讨论了C藤和D藤采用截断简化时的准则。在此基础上,利用基于copula熵的多维藤分布估计算法框架进行了仿真实验,结果表明该算法具有很好的应用潜力。5.基于copula函数的分布估计算法在无线传感器网络覆盖问题中的应用。copula函数很适合于描述无线传感器网络中节点之间的不确定的相关性。在建立了无线传感器网络覆盖问题优化模型的基础上,令分布估计算法中每个个体为[0,1]区间的连续变量,该变量用来表示对应的传感器节点被选中的概率,这样,就将基于copula函数的分布估计算法成功地应用于离散的无线传感器网络覆盖问题的求解。针对不同节点部署、不同感知模型情形下的大量仿真实验验证了算法的有效性。