论文部分内容阅读
演化计算是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法,能够在不要求函数连续、可微、单峰的情况下,找到问题的近似全局最优解。基于这些优点,演化计算被广泛地应用于NP和NPC难题求解、神经网络优化、多目标优化问题求解及其它众多领域。然而,随着问题规模和复杂程度的不断提高,串行演化算法的搜索过程将成倍地增长,由此,并行演化计算成为一个重要的研究方向。Cantú-Paz将并行演化计算划分为四种类型,分别是主从模型、粗粒度模型、细粒度模型和分层模型。这些模型通常在MPI、PVM和OpenMP等并行编程环境下实现。为了避免传统并行演化算法中常见的“征服问题”和“无效问题”,克服过早收敛,提高算法运行效率,本文提出了异步分层并行演化算法(Asynchronous Hierarchical Parallel Evolutionary Algorithm,AHPEA)。在算法中,对扩展的模糊交叉算子进行改进,加入了适应值信息,提出基于标准化适应值的模糊交叉算子(Fuzzy Recombination Operator Based on Standardized Fitness,SF-FRO),提高算法的收敛速度。并在此基础上提出异构模型,为各子种群的交叉操作应用不同的全局/局部搜索度,指定相异的种群拓扑,以获取适当的选择压力。最后将各子种群充分连接,构建异步迁移模型。本文提出的AHPEA算法有效地解决了“征服问题”和“无效问题”,避免了算法的过早收敛,提高了算法效率。在仿真研究中,基于一组被广泛使用的测试问题集,从交叉算子SF-FRO、异构模型和异步迁移三个方面对AHPEA算法进行性能测试。实验结果表明:(1)SF-FRO由于引入了适应值信息,为算法指明了潜在的搜索方向及范围,能够有效地提高算法的收敛速度;(2)AHPEA算法在求解大型多峰值问题时采用异构模型比采用同构模型具有更优越的性能;(3)在AHPEA算法的各子种群间进行异步迁移,无论从理论分析还是仿真研究的角度来看,都极大地提高了算法的性能。作为AHPEA算法的实际应用,本文在最后部分研究了FKCN聚类分析的理论基础,并将FKCN聚类问题抽象为一个优化模型,应用AHPEA算法对其进行优化。实验结果显示,基于AHPEA算法的动态聚类方法不仅能够准确地探测出最佳聚类个数,而且误判率明显降低,具有更准确、更稳定的聚类效果。