论文部分内容阅读
群体智能优化算法是一种近年来新兴的优化方法,是受到关注最多的优化领域之一,也是人工智能界的一个重要研究方向。其模拟各种社会性动物的群体行为,利用群体中个体之间的信息交互与合作来实现寻优目的。与其它类型的优化方法相比,其具有实现简单、效率较高等优点,目前已经被广泛地应用到了函数优化问题、组合优化问题、人工生命、自动控制、机器学习等各个领域当中。
本论文围绕群体智能算法中的蚁群优化算法与进化计算算法的原理与应用进行研究。主要就蚁群优化算法与遗传算法在曲线提取问题中的应用、进化规划算法在模糊聚类问题中的应用、蚁群算法在云计算平台下的并行化实现等问题进行了较为深入、系统的研究。取得的主要成果包括:
1.对所要解决的曲线提取问题给出了形式化描述,并从计算机视觉、模糊聚类、组合优化的不同角度对该问题进行了分析与讨论。在视觉模型的基础上,有效地设计了曲线的适应度评价函数,能够同时作为非闭合曲线与闭合曲线的评价标准。通过对曲线提取问题与旅行商问题的异同点分析,利用其相似点,继承了蚁群算法中状态转移规则、信息素更新规则;针对不同点,特别设计了搜索终止函数与路径翻转算子。通过对各种长度、角度、纹理、存在各种噪声的二值图像测试集进行仿真实验,结果表明所提出的方法能够有效地从充斥噪声的二值图像中提取出含有断点的目标曲线,在120副二维图像上的平均提取准确率达到98.8%。并通过对三维空间中“像素立方体”距离、密度的设计,将所能处理的数据对象从二维平面推广到三维空间中。与基于小生境遗传算法的曲线提取算法的统计t测试对比结果表明了所提出的基于蚁群优化的方法在提取精准度与算法所需运行时间方面均具有显著优越性,并从蚁群算法与遗传算法的算法机理与运行机制上讨论分析了不同噪声强度对于两类方法的影响以及基于蚁群优化的方法能够具有显著优越性的内在原因。此外,与计算机视觉中传统的Hough变换算法相比,该方法无需预先给定曲线的形状和方程,是一种非参数化的曲线提取算法,更加适用于实际问题的求解。
2.针对实际应用中一副图像中同时含有多条目标曲线,需要进行多曲线提取的情况,提出了基于最大最小蚂蚁算法的多曲线提取方法。蚁群优化方法关注的往往只是问题的最优解,而多曲线可以看做问题的多个局部最优解。根据两曲线公共像素占比对两曲线之间的相似度进行了定义,任何适应度值达到阈值要求且相互之间相似度小于阈值要求的曲线都能够在算法执行过程中被有效存储;同时针对多曲线提取任务,设计了特殊的信息素更新方式,允许所有的目标解贡献信息素增量。在此基础上,对该方法进行了总结,提出了更具一般性的基于蚁群优化的多目标解求解方法的思想与算法框架。
3.研究了基于摄动的模糊聚类方法(FCMBP),指出其指数复杂度的遍历过程是目前PC计算环境下难以处理十阶以上较高阶数模糊相似矩阵的原因。把寻求具有最小“失真”的最优模糊等价矩阵看作优化问题来求解,提出了一种基于进化规划的FCMBP模糊聚类改进算法(EP-FCMBP)。算法首先随机产生一组模糊等价矩阵,通过对每个等价矩阵进行变异操作产生新的模糊等价矩阵,进而通过q竞争选择法实现优胜劣汰和种群进化,并最终趋于得到一个“失真”最小的模糊等价矩阵。对于低阶模糊相似矩阵的情况,EP-FCMBP算法能够获得与FCMBP算法结果相同的具有最小“失真”的最优模糊等价矩阵,且算法搜索的时间代价远远小于FCMBP算法。对于高阶模糊相似矩阵的情况,在不同阶数的数十个相似矩阵上的实验结果经过统计t测试(置信度为95%),表明EP-FCMBP方法较传递闭包法在获得“失真”更小的模糊等价矩阵方面具有显著优越性。此外,EP-FCMBP算法具有良好的灵活性与实用性,对于实时性要求较高的聚类问题,算法能够在进化初期迅速获得比传递闭包法更为精确的聚类结果;而对精度要求高的聚类问题,算法也可以通过迭代过程的不断进行,满足更高精度要求。
4.首先对基于Hadoop云计算平台的并行数据挖掘平台PDMiner进行介绍,并给出了数据挖掘任务中若干数据预处理操作的并行化实现方式与并行化实现效果。然后,对基于MapReduce的并行最大最小蚂蚁算法的算法思想、并行化策略、以及实现方法进行了详细的分析与介绍。通过在经典旅行商问题上的实验分析,表明所提出的基于MapReduce的并行最大最小蚂蚁算法具有良好的加速比性能,能够有效提高算法的执行效率,从而更加适合于处理规模较大的优化问题。