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