基于蚁群系统的聚类算法研究

针对传统聚类算法在对复杂密集型数据集聚类时不能取得较好聚类结果的问题,利用进化聚类算法对复杂密集型数据集进行聚类,提出一种基于蚁群系统的聚类算法(clustering algorithm based on ant colony system,CAACS),利用蚂蚁在行进路径中释放信息素且追求浓信息素的原理来实现蚂蚁的随机搜索,并引入近邻函数值的概念来确定样本数据之间的相似性,通过蚂蚁在行走过程中不断建立样本数据之间的最相似连接来形成各个子连通图,各个子连通图中的样本数据构成一个类。实验采用随机产生的不规则数据集以及一系列合成的数据集将CAACS算法与DBSCAN算法(density-based spatial clustering of application with noise)及面向非规则非致密空间分布数据的蚁群聚类方法进行比较。实验结果表明CAACS算法对复杂密集型数据集能达到较好的聚类结果。     

基于GPU的共享信息素矩阵多蚁群算法

在研究并行蚁群信息素交流方法的基础上,提出了一种适于GPU统一计算架构模型的多蚁群算法。采用多个同构和异构蚁群共享同一信息素矩阵的交流策略,解决信息素多样性和算法性能之间的矛盾。在路径探索阶段,多只获得迭代最优解且差异较大的蚂蚁共同释放信息素,以利群体多样性;在路径开发阶段,获得唯一全局最优解的蚂蚁释放信息素,以利迅速收敛。多蚁群映射到GPU的线程块而群内蚂蚁对应块内多线程。以MMAS和ACS混合为例给出了该策略下信息素初始化和动态界限的新方法,证明了算法是值收敛和解收敛的。在标准TSP问题实例上的实验评测表明,该算法不仅提升了性能,在充分收敛条件下获得了更高质量的解。     

两阶段判别嵌入模糊聚类

针对两阶段判别嵌入式聚类算法无法有效地反映数据的真实结构问题,提出一种两阶段判别嵌入模糊聚类算法。首先利用模糊C-均值算法对数据进行初始聚类,得到数据的初始隶属度矩阵,然后通过奇异值分解和求解最大散度差对数据降维处理,最后在低维子空间中对降维后的数据再次进行模糊C-均值聚类。通过对初始数据和降维后的数据进行模糊聚类提高算法的准确度。对比实验结果表明,该算法可获取最优聚类精度,并能更有效地反映数据的真实结构。     

一种改进蚁群算法在配电网络规划中的应用

在基本蚁群算法的基础上,将蚂蚁经过路径上各路段的次数与信息素更新机制相关联,改进了信息素更新方式,旨在提高蚁群算法的寻优能力和收敛到最优解的速度。将改进算法应用于只考虑过负荷约束和网络辐射型约束、以网络年综合费用和过负荷惩罚费用之和最小为目标函数的配电网规划问题中。通过一个10 kV配电网络规划问题的算例验证表明,改进算法在寻优能力和收敛速度方面均有所提高。     

两阶段判别嵌入式聚类

针对判别嵌入式聚类算法对高维数据聚类速度慢的问题,给出一种两阶段判别嵌入式聚类算法。对正则化类间散度矩阵做奇异值分解,得到数据的变换矩阵,对数据进行初次降维,并用判别嵌入式聚类算法中的经典降维方法对低维数据再次降维。通过两次降维来减少判别嵌入式聚类算法的时间复杂度,提高聚类效率。     

基于改进蚁群算法的多批次协同三维航迹规划

针对基本蚁群算法容易陷入局部寻优、收敛速度慢的缺陷以及解决多批次协同航迹规划问题的需要,提出了基于改进蚁群算法的多批次三维航迹规划算法。该算法采用基于加权排序的信息素更新规则,扩大各优劣蚂蚁的差异,提高了算法收敛速度,并采用了一种信息素挥发系数的随机自适应调节方法,在确保收敛速度的同时使算法具有全局寻优,解决了基本蚁群算法容易过早陷入局部最优缺点;在此基础上,引入蚂蚁子群间多约束条件下的协同进化策略,解决了多批次协同三维航迹规划。仿真结果表明:改进的蚁群算法在运算效率和收敛性上明显优于基本蚁群算法,多批次协同航迹规划能有效提高无人机的作战效能。     

带运力限制车辆路径问题的简易蚁群算法实现

以求解旅行商问题的蚁群算法为基础,根据带运力限制车辆路径问题的实际应用条件,提出一种较为简易的求解带运力限制车辆路径问题的蚁群算法,并对其中的信息素更新策略进行了分析,对蚁群中的精英蚂蚁(搜索出最优解的蚂蚁个体)所经过路径的信息素进行加强,提高了算法的全局收敛性能和收敛速度,允许蚂蚁在搜索的最初阶段有较大的自由以扩大最优解的寻找空间,提出改进蚁群算法.实验结果表明,该方法能在较短的时间内达到已知最优解的1.5%误差范围.     

蚁群算法中基于知识引导的信息素控制策略

针对蚁群算法在求解旅行商问题性能方面的不足,提出了一种基于知识引导的信息素控制策略.该策略利用问题先验知识初始化信息素,旨在提高算法运行初期信息素对蚂蚁搜索的启发能力;采用群知识引导信息素更新,加强信息素对蚂蚁搜索的引导能力,增强蚂蚁搜索的目的性.实验结果表明,基于这种信息素控制策略的蚁群算法的总体性能明显优于当前最先进的蚁群算法.     

一种基于文本分类的特征选择方法

文本分类中通常采用向量空间模型(VSM)来表示文本特征,如何选择最能够表达文本主题的特征词,从而减少特征空间维数,降低时空复杂度,是一个十分重要的问题。针对此问题本文提出了采用截集模糊C-均值(S2FCM)聚类进行类间特征降维,该方法以最大隶属度原则为指导,在保持模糊聚类的同时,提高收敛速度,并且能够提高特征选择的正确性。同时在算法中使用改进的隶属度、聚类中心计算方法并使用非随机方法确定初始聚类中心。最后实验表明采用该方法选择的文本特征项进行文本分类能够收到比较好的分类结果。     

基于双向蚁群算法的路径规划研究

针对蚁群算法存在的搜索精度不足以及收敛速度缓慢等问题，本文提出了一种加入角度参数的双向蚁群算法用于解决机器人路径搜索问题。与传统蚁群算法不同，该算法首先对蚁群的起始位置进行改进，使其根据蚂蚁编号从地图中的一系列起点集合中选择适当节点出发，增加解的多样性同时并获得全局最优解。同时改进了信息素更新规则，对当前迭代次数寻找到的最优路径进行信息素奖励，使其对下次迭代蚂蚁的寻路过程起到引导作用。最后，为提高算法的收敛速度，提出了角度参数并将其加入到蚂蚁的转移概率中，使得蚂蚁在根据转移概率选择下一行走节点时能够优先选择与目标节点角度差较小的节点，从而提高获取最优解的概率，并在算法后期加快收敛速度。大量仿真实验结果表明本文所提出算法的路径搜索能力和迭代收敛效果显著提高。     

蚁群算法解决连续优化问题的新途径

为了克服蚁群算法难以直接处理连续优化问题的缺陷,在保持蚁群算法基本框架的基础上,将传统蚁群算法中蚂蚁由解分量的信息素和启发式的乘积值按比例来决定取值概率的方式,改为根据连续的概率分布函数来取值.并将函数在各个维上的极值点方向作为蚂蚁搜索的启发式信息.在标准测试函数上的试验结果显示,该算法不但具有较快的收敛速度,而且能够有效地提高解的精确性,增强了算法的稳定性.     

改进多步长蚁群算法移动机器人路径规划研究

为改善传统蚁群算法在路径规划中存在的规划路径实用性差、收敛速度慢、易陷入局部最优等问题,提出一种改进多步长蚁群算法.改进算法以移动机器人视野域内所有可直达节点作为下一步可选节点集,采用多步长移动方式以任意方向任意步长寻找下一节点,提高算法寻优效率和路径规划多样性;节点之间初始信息素依各节点与当前节点和目标节点连线的距离采取不均匀分布,降低蚁群在算法初期搜索的盲目性;通过路径长度增大优质路径与劣质路径的信息素更新差距,改进启发函数,提高算法收敛速度.仿真结果表明,改进算法规划路径具有长度短、路径平滑度高、步数少的优点,更符合移动机器人实际使用需求,收敛速度明显加快,路径规划效果提升显著.     

模糊c-harmonic均值算法在不平衡数据上改进

针对模糊c-harmonic均值算法(FCHM)在不平衡数据集上的聚类效果不理想的问题,提出了一种基于聚类体量约束的模糊c-harmonic均值算法。首先,利用隶属度矩阵定义各个类的体量,用于约束FCHM算法的代价函数,从而构建一个新的代价函数;然后,将该代价函数最小化,得到新的隶属度矩阵和聚类中心的计算公式;最后,在UCI数据集、模拟不平衡数据集及真实机床振动检测不平衡数据集上分别进行实验。实验结果表明,与同类算法相比,本文算法在保持传统算法全局最优性能的同时,在不平衡数据集上也能得到理想的聚类效果。     

自适应避障蚁群算法的移动机器人路径规划

传统蚁群算法在解决机器人路径规划的问题上存在收敛慢,容易收敛于次优路径的不足.针对以上不足,研究在状态转移概率、信息素更新方面进行改进.在状态转移概率上引入了一个避障函数因子,减小蚂蚁进入地图陷阱的概率,从而有效减少陷入死锁的蚂蚁数量,加快收敛速度.在信息素方面,加入了随迭代次数变化的信息素挥发因子,增加算法进行全局搜索的可能性,避免算法陷入局部最优.设计三种栅格障碍图对两种算法进行仿真,结果对比均表明,经过改进得到的AOA蚁群算法的初次收敛次数更少,迭代速度大大增强,并且最终规划得到的最小路径长度均比原算法小,与其他的改进算法相比,在找到最优路径的同时,其初次迭代的收敛次数也大大降低.     

基于多蚁型的蚁群聚类算法

本文提出了一种多蚁型的蚁群模型和在此模型上的一个具有移动空间的蚁群聚类算法。每个类簇都带有一个移动空间,使同类的蚂蚁紧密地聚在一起。移动空间为每个类簇选出一个代表蚂蚁用来长距离的类簇移动。代表蚂蚁通过连接将类簇中不相似的大量数据移动到与其相似的代表蚂蚁处,减少了蚂蚁的搜索时间,提高聚类性能。针对UCI数据集进行实验,结果表明新算法提高了聚类效果。     

地球物理资料非线性反演方法讲座（九）蚁群算法

蚁群算法是一种仿生类非线性优化算法,具有并行性、正反馈性和全局极小搜索能力强等特点。蚁群算法的机理是：生物界中的蚂蚁在搜寻食物源时,能在其走过的路径上释放一种蚂蚁特有的分泌物——信息素,使得一定范围内的其他蚂蚁能够觉察并影响其行为。当某些路径上走过的蚂蚁越来越多时,留下的这种信息素轨迹也越多,以至信息素强度增大,使后来蚂蚁选择该路径的概率也越高,从而更增加了该路径的信息素强度。为了将起源于离散网络路径优化的原始蚁群算法思想用于连续函数优化的地球物理反演问题,必须对有关实施细节进行改造和修正,本文基于网格划分策略的连续域蚁群算法实现了连续域大地电磁蚁群算法。通过选择蚂蚁数、信息素挥发系数等参数,利用三层K型模型和四层HA型模型进行数值试验,结果表明,蚁群算法可以稳定收敛,反演结果接近理论模型。     

蚁群算法

蚁群算法是一种仿生类非线性优化算法,具有并行性、正反馈性和全局极小搜索能力强等特点.蚁群算法的机理是:生物界中的蚂蚁在搜寻食物源时,能在其走过的路径上释放一种蚂蚁特有的分泌物信息素,使得一定范围内的其他蚂蚁能够觉察并影响其行为.当某些路径上走过的蚂蚁越来越多时,留下的这种信息素轨迹也越多,以至信息素强度增大,使后来蚂蚁选择该路径的概率也越高,从而更增加了该路径的信息素强度.为了将起源于离散网络路径优化的原始蚁群算法思想用于连续函数优化的地球物理反演问题,必须对有关实施细节进行改造和修正,本文基于网格划分策略的连续域蚁群算法实现了连续域大地电磁蚁群算法.通过选择蚂蚁数、信息素挥发系数等参数,利用三层K型模型和四层HA型模型进行数值试验,结果表明,蚁群算法可以稳定收敛,反演结果接近理论模型.     

使用蚁群优化和凝聚层次的混合聚类

为了获得全局最优的高质量层次聚类结果,针对智能蚁群优化算法改进凝聚层次聚类算法,以获得高质量的层次聚类结果,提出一种新的基于蚁群优化和凝聚层次聚类的混合聚类方法.该方法使用改进的凝聚层次聚类算法和新的目标函数生成聚类的系统树图,利用内部指标评估解决方案,用智能蚁群优化算法支持的信息素反馈和信息素挥发机制控制蚁群在解决方案空间中的搜索.由于使用了元启发式优化,加快了搜索过程,避免了局部最优.在加州大学欧文分校多个数据集上的实验结果表明,新方法具备一定的可行性.     

基于蚁群算法的粗糙集属性约简方法

利用蚁群算法的搜索技术,提出了一种基于蚁群算法的粗糙集属性约简方法。该算法将核引入初始信息素分布中,以加快算法的收敛。同时为提高全局搜索能力,根据蚂蚁在搜索过程中所得解的分布状况动态地调解蚂蚁的路径策略和信息量更新策略。实验证明该算法是有效的,具有较好的收敛速度和稳定性。     

基于FA-IACS算法的车辆路径问题优化

针对传统蚁群系统算法在解决有容量约束的普适性车辆路径优化中易陷入局部最优和收敛速度慢等问题,提出了一种改进的蚁群系统算法.采用改进的距离启发函数因子调整蚂蚁状态转移概率,利用改进编码方式的萤火虫算法作为搜索机制,改善蚁群系统的全局搜索能力,应用信息素震荡程序探索新路径的信息素,避免陷入局部最优.结果表明,该算法提高了全局搜索能力,能够节约寻找最优路径的时间,加快收敛速度,具有更好的鲁棒性.