局部搜索算法求解组合优化问题

发布时间：2022-01-25 00:13

　　连通顶点覆盖问题和k-plex问题是两个重要的难解组合优化问题。这两个问题在网络安全、大规模集成电路、无线网络设计以及社交网络等领域有着重要的应用。性能良好的求解算法不仅能够提高这两个问题的求解效率和精度,而且能够提高现实工业中的作业效率,降低时间和劳动力成本,节约资源,提升产品的利润空间。本文设计了三个局部搜索算法分别用于求解连通顶点覆盖问题和k-plex问题。其中GRASP-CVC算法和EWGRASP-CVC算法用于求解连通顶点覆盖问题。在这两个算法中我们采用贪心策略简单快速地构造出问题的初始可行解,同时为了避免局部搜索算法的循环搜索问题,格局检测策略以及带遗忘机制的边加权策略被应用到算法中。对于k-plex问题,我们设计了一个多阶段局部搜索（PLS）算法进行求解。PLS算法主要由三个子阶段组成,每个子阶段按不同的策略对问题的解空间进行搜索。PLS算法通过在这三个子阶段之间的切换,使得算法不仅能够处理不同特点的实例,而且保证算法能够搜索到尽可能大的解空间,提升了算法跳出局部最优的能力。为了验证我们所设计的算法的有效性和高效性,我们将现有算法和本文所提算法进行了实验对比。在大量经典实... 

【文章来源】：东北师范大学吉林省 211工程院校 教育部直属院校

【文章页数】：59 页

【学位级别】：硕士

【部分图文】：

最小顶点覆盖和连通顶点覆盖示例

第四章 PLS 算法求解 k-plex 问题多阶段局部搜索[57]（Phased Local Search,记为 PLS）最初是由 Pullan 在动态局部搜索[43]（Dynamic Local Search，记为 DLS）的基础上加以改进用于求解最大团问题的随机算法。PLS 算法由三个子算法组成，这三个子算法主要区别在于选择顶点的方法以及为克服局部最优采用的扰动策略不同，算法在迭代执行的过程中不断地在这三个子算法之间切换。其作者的实验也充分证明了 PLS 算法在求解最大团问题以及最大加权团问题上的有效性，而且与 DLS 算法不同，PLS算法没有依赖于具体实例的参数，这使得 PLS 实现起来更加便捷，也更具通用性。考虑到 PLS 的上述优点以及 k-plex 问题与最大团问题的关联性，采用 PLS算法框架求解 k-plex 问题便是一个很自然的想法。4.1 k-plex 相关定义及图化简原理在对 PLS 相关子过程进行介绍之前，本节首先对这些子过程运行时涉及到的重要概念进行说明。


本文编号：3607552