一种求解最大团问题的交叉熵算法与其并行化研究

论文摘要

最大团问题是一个经典的组合优化问题，在理论研究和实际应用方面都有重要的价值，本文对最大团问题的最新研究进展做了分析综述。交叉熵算法是Rubinstein发起的一种新的问题求解方法，交叉熵算法的特色是给出了用来产生好的更新学习策略的数学框架，主要思想是利用Kullback-Leibler交叉墒，重要度采样以及波尔兹曼分布，把组合优化最优解问题转化为求解辅助的简单随机优化问题。为了研究一种新的问题求解策略，本文设计实现了求解最大团求解的交叉熵算法。利用适应度地形分析方法，对算法实际运行情况进行了分析，并根据实验结果提出了伪随机机制与局部扰动的改进策略。交叉熵算法是基于大量的数据模拟，为了加快算法运行，本文还设计实现了基于OpenMP和MPI两种并行算法。基于OpenMP并行算法是面向共享内存平台的。基于MPI的并行算法是面向分布式结构的，在设计中提出了一种基于领导行为的并行策略。本文最后对DIMACS的80个实例都做了实验，另外选取的27个实例与当前最好的几个算法做了比较，实验结果表明本文算法对于问题实例具有很好的适用能力，具有应用和研究价值。而并行算法的加速比和效率实验结果表明本文的两种并行算法也具有很好的加速性能。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 引言
• 1.1 论文背景
• 1.2 本文的主要工作
• 1.3 本文研究的意义
• 1.4 本文的组织结构
• 第二章 最大团问题概述
• 2.1 最大团问题一般描述
• 2.2 最大团问题形式化描述
• 2.3 最大团问题在国外的相关研究
• 2.3.1 RLS算法
• 2.3.2 KLS-MCP算法
• 2.3.3 DLS算法
• 2.3.4 DAGS算法
• 2.3.5 QUALEX-MS算法
• 2.3.6 ACO算法
• 2.3.7 GLS算法
• 2.3.8 EDA/G算法
• 2.4 最大团问题在国内的相关研究
• 2.4.1 求解图的最大团的一种算法
• 2.4.2 一种借助邻接矩阵求任意图最大团的方法
• 2.4.3 DNA计算中的基因算法:求解最大团的一种方法
• 2.4.4 采用MEC求解最大团问题
• 2.4.5 基于遗传算法的近似最大连通分量的抽取算法
• 2.4.6 基于离散粒子群算法的近似最大连通分量抽取
• 2.5 本章小结
• 第三章 交叉熵方法概述
• 3.1 交叉熵算法原理
• 3.2 交叉熵算法在组合优化问题中的应用
• 3.3 交叉熵算法的应用研究
• 3.3.1 用于组合优化和连续优化问题的交叉熵算法
• 3.3.2 用于组合优化问题的交叉熵算法
• 3.3.3 交叉熵算法
• 3.3.4 一种用于估计通信网缓冲溢出问题的快速交叉熵算法
• 3.4 本章小结
• 第四章 求解最大团问题的交叉熵方法
• 4.1 最大图问题求解分析
• 4.1.1 产生集团的方法
• 4.1.2 参数更新方法
• 4.2 求解最大团问题的交叉熵算法
• 4.3 算法的运行分析及改进
• 4.3.1 算法验证
• 4.3.2 算法求解的适应度地形分析
• 4.3.3 改进策略
• 4.4 本章小结
• 第五章 求解最大团问题的并行交叉熵算法
• 5.1 并行元启发概述
• 5.1.1 并行计算的目标
• 5.1.2 平行计算平台
• 5.2 交叉熵算法的并行研究
• 5.3 基于OpenMP的并行算法
• 5.3.1 算法的实现
• 5.4 基于领导策略的并行算法
• 5.4.1 任务分配
• 5.4.2 决策行为
• 5.4.3 算法实现
• 5.5 本章小结
• 第六章 实验结果及分析
• 6.1 改进措施的影响
• 6.2 局部扰动对算法的影响
• 6.3 串行算法的求解结果
• 6.4 并行算法的试验结果与评价
• 6.4.1 基于OpenMP的并行算法实验结果
• 6.4.2 基于MPI的并行计算结果
• 6.5 并行算法之间的对比
• 6.6 本章小结
• 第七章 总结
• 7.1 已完成工作总结
• 7.2 今后的研究展望
• 参考文献
• 发表文章目录
• 致谢
• 代码说明及代码片段