面向大规模实值优化问题的CMA-ES算法及其分制策略研究

摘要

实值优化问题在工程和学术领域有广泛的应用背景，许多问题最后都可以被定义成实值优化问题来求解。随着系统越来越复杂，需要优化的参数越来越多，优化问题解空间的维度越来越高，导致大规模优化问题的出现。演化算法作为一种优化问题通用求解器，具有启发式算法的一系列优良特性，包括对优化问题的鲁棒性、全局搜索能力强等，而且易实现、易并行，特别适合求解实值优化问题。演化算法，已经在实值优化问题上表现出了良好的性能，并且，在近似优化上，已经有了理论保证。但是，由于维度灾难，演化算法在大规模优化问题上的表现会快速下降。协作性协同演化框架是一种基于分制策略的演化框架，它将待求解问题分解成多个子问题，并在每个子问题上应用演化算法来求解，最后合并多个子问题的解，从而形成原问题的解。基于协作性协同演化框架，多种演化算法已经成功的从低维优化问题拓展到了大规模优化问题。协作性协同演化框架基于分制策略，所以问题的划分方式对问题求解的效果产生非常大的影响。在实值优化问题中，往往存在变量之间的相关性，不恰当的划分方式将相关变量划分到不同的子问题中，导致了子问题求解的耦合性，从而不能很好的解决原优化问题。本论文有以下研究目的:
　　1.研究基于协同演化框架的演化算法在实值优化问题上的分制策略;
　　2.研究基于协同演化框架的演化算法，用于求解大规模实值优化问题;
　　3.将分制策略形式化定义为优化问题，并开展应用研究。
　　根据以上研究目的，本论文以Covariance Matrix Adaptation Evolution Strategy(CMA-ES)实值优化算法和协作性协同演化框架为研究基础，进行了问题分制策略的研究，并将问题分制策略应用于CMA-ES算法上，用于求解大规模实值优化问题，最后解释了问题分解定义的理论基础，并将问题划分拓展到一般聚类问题，在聚类问题上进行应用研究。本论文的主要工作和创新之处主要有以下几点:
　　1.首先基于高斯分布，研究了CMA-ES实值优化算法的问题分解策略，从控制高斯分布作为局部搜索算子的搜索力度的角度，提出了两种新的问题分解方法;
　　2.将提出的问题分制策略应用到CMA-ES算法上，基于协作性协同演化框架，提出了一种更加高效的CC-CMA-ES算法，并在大规模实值优化问题上进行实验研究，验证了提出的问题分制策略和优化算法在大规模实值优化问题上的有效性;
　　3.从KL散度的角度，将基于高斯分布的问题分解定义成了一个离散优化问题，解释了两种问题分解方法的理论基础，并将基于高斯分布的问题分解所形成的离散优化问题，拓展到一般的聚类问题上，提出了一种新的聚类算法。
　　本论文通过对协同演化框架和CMA-ES算法的研究，提出了两种新型的问题分解策略，并将问题分解策略应用于CMA-ES算法，提出一种基于协作性协同演化框架的CMA-ES算法，可以在高达1000维的大规模实值优化问题上表现出良好的特性;然后，从KL散度的角度，理论解释了两种问题分解策略的出发点，并且将问题分解拓展成为一般形式的聚类问题，将聚类定义为一个离散优化问题，在Iris数据集上进行了应用研究。这些工作对于将演化算法应用到大规模实值优化问题有着重要的理论和应用价值，并且和聚类问题建立了联系，对于相关领域的研究有重要意义。

目录

声明

摘要

表格索引

插图索引

算法索引

第一章 绪论

1．1 大规模实值优化问题定义

1．2 基于协作型协同演化的优化算法综述

1．3 问题分制策略综述

1．4 本论文主要研究内容与创新之处

1．5 本论文的组织安排

1．6 本章小结

第二章 基础知识综述

2．1 CMA-ES算法

2．1．1 算法简介

2．1．2 采样操作

2．1．3 更新操作

2．2 协作性协同演化框架

2．3 本章小结

第三章 基于协同演化的大规模实值优化算法研究

3．1 协同演化分制策略

3．1．1 研究思路

3．1．2 分制策略MiVD与MaVD

3．1．3 MiVD与MaVD的理论分析

3．1．4 结论与展望

3．2 基于协同演化的大规模CMA-ES算法

3．2．1 研究思路

3．2．2 分制策略自适应

3．2．3 采样操作

3．2．4 适应度计算

3．2．5 参数更新

3．2．6 CC-CMA-ES算法

3．2．7 实验及分析

3．2．8 结论与展望

3．3 本章小结

第四章 分制策略MiVD及MaVD的研究

4．1 基于KL散度的分制策略分析

4．1．1 理论分析

4．1．2 可行性与复杂度分析

4．1．3 结论与展望

4．2 基于KL散度的分制策略在聚类问题上的应用

4．2．1 Iris数据集

4．2．2 参数选择与工程实现

4．2．3 总结与展望

4．3 本章小结

第五章 总结与展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果