蚁群算法聚类设计PPT学习教案

1、会计学1 蚁群算法聚类设计蚁群算法聚类设计 目 录 算法的提出 算法的基本原理 模型建立 算法的实现 算法改进 结论 第1页/共24页 一一.蚁群算法的提出蚁群算法的提出 蚁群算法蚁群算法(ant colony optimization, (ant colony optimization, ACO)ACO)，又称蚂蚁算法，是一种用来寻找优，又称蚂蚁算法，是一种用来寻找优 化路径的机率型算法。它由化路径的机率型算法。它由Marco Marco DorigoDorigo 于于19921992年在他的博士论文中提出，其灵感年在他的博士论文中提出，其灵感 来源于蚂蚁在寻找食物过程中发现路径的来源于蚂蚁

2、在寻找食物过程中发现路径的 行为。遗传算法在模式识别、神经网络、行为。遗传算法在模式识别、神经网络、 机器学习、工业优化控制、自适应控制、机器学习、工业优化控制、自适应控制、 生物科学、社会科学等方面都得到应用生物科学、社会科学等方面都得到应用。 Macro Dorigo 第2页/共24页 二二.算法的基本原理算法的基本原理 NestFood Obstacle 图1 蚂蚁正常行进，突然环境改变，增加了障碍物 第3页/共24页 二二.算法的基本原理算法的基本原理 NestFood Obstacle 图2 蚂蚁以等同概率选择各条路径 较短路径信息素浓度高，选择该路径的蚂蚁增多 第4页/共24页 二

3、二.算法的基本原理算法的基本原理 图3 蚂蚁选路过程示例 E A B D HC E A B D HC d=0.5 d=0.5 d=1 d=1 30ants 30ants 15ants 15ants 15ants 15ants t=0 E A B D HC 30ants 30ants 20ants 20ants 10ants 10ants t=1 第5页/共24页 二二.算法的基本原理算法的基本原理 NestFood Obstacle 图4 蚂蚁最终绕过障碍物找到最优路径 第6页/共24页 三三.模型建立模型建立 o基于蚂蚁构造墓地和分类幼体的聚类分析模基于蚂蚁构造墓地和分类幼体的聚类分析模 型

4、型 o基于蚂蚁觅食行为和信息素的聚类分析模型基于蚂蚁觅食行为和信息素的聚类分析模型 第7页/共24页 三三.模型建立模型建立 1.1.基于蚂蚁构造墓地和分类幼体的聚类分析模型基于蚂蚁构造墓地和分类幼体的聚类分析模型 o蚁群构造墓地行为和分类幼体行为统称之为蚁群聚类行为。 o生物学家经过长期的观察发现，在蚂蚁群体中存在一种本能的聚集 行为。蚂蚁往往能在没有关于蚂蚁整体的任何指导性信息情况下，将 其死去的同伴的尸体安放在一个固定的场所。 第8页/共24页 三三.模型建立模型建立 p真实蚁群的聚类行为 Deneuboug JL等人也 用 pheidole pallidula 蚂蚁做了实验。发现蚁群

5、会根据蚂蚁幼体的大小将 其放置在不同的位置，分 别把其堆放在蚁穴周围和 中央的位置。 真实的蚁群聚类行为 的实验结果右图，四张照 片分别对应为实验初始状 态、3小时、6小时和36小 时的蚁群聚类情况。 第9页/共24页 三三.模型建立模型建立 o基本模型经过利用个体与个体和个体与环境之间的交互作用，实 现了自组织聚类，并成功的应用于机器人的控制中(一群类似于 蚂蚁的机器人在二维网格中随意移动并可以搬运基本物体，最终 把它们聚集在一起)。该模型成功的应用引起了各国学者的广泛 关注和研究的热潮。 oLumerE和FaietaB通过在Denurbourg的基本分类模型中引入数据对 象之间相似度的概念

6、，提出了LF聚类分析算法，并成功的将其 应用到数据分析中。 第10页/共24页 三三.模型建立模型建立 2.基于蚂蚁觅食行为和信息素的聚类分析模型 蚂蚁在觅食的过程中，能够分为搜索食物和搬运食物两个环节。 每个蚂蚁在运动过程中都将会在其所经过的路径上留下信息素，而且 能够感知到信息素的存在及其强度，比较倾向于向信息素强度高的方 向移动，同样信息素自身也会随着时间的流逝而挥发，显然某一路径 上经过的蚂蚁数目越多，那么其信息素就越强，以后的蚂蚁选择该路 径的可能性就比较高，整个蚁群的行为表现出了信息正反馈现象。 第11页/共24页 四四.算法的实现算法的实现 由于蚁群优化算法是迭代求取最优值，所以

7、事先无需训练数据，故取 59组数据确定类别。流程图如下： 第12页/共24页 四四.算法的实现算法的实现 重要程序代码介绍： 1.程序初始化 lX = load(data.txt); lN,n=size(X); % N =测试样本数;n =测试样本的属性数; lK = 4; % K = 组数; lR = 100; % R = 蚂蚁数; lt_max = 1000; % t_max =最大迭代次数; lbest_solution_function_value = inf; % 最佳路径度量值（初值为无穷大， 该值越小聚类效果越好） 2.信息素矩阵初始化 信息素矩阵维数为N*K（样本数*聚类数）初

8、始值为0.01。 lc = 10-2; ltau = ones(N,K) * c; %信息素矩阵，初始值为0.01的N*K矩阵 （样本数*聚类数） 第13页/共24页 四四.算法的实现算法的实现 3.蚂蚁路径的选择及标识 定义标识字符矩阵solution_string，维数为R*N+1，初始值都为0，以 信息矩阵中信息素的值确定路径（即确定分到哪一组），具体方法如下： 如果该样本各信息素的值都小于信息素阈值q，则取信息素最大的为作为 路径。若最大值有多个，则从相同的最大值中随机取一个，作为路径。 若信息数大于阈值q，则求出各路径信息素占该样本总信息素的比例，以 概率确定路径。 4.聚类中心选择

9、 聚类中心为该类所有样本的各属性值的平均值。 5.偏离误差计算 偏离误差的计算，即各样本到其对应的聚类中心的欧式距离之 和MIN。 MIN越小，聚类效果越好。计算各只蚂蚁的MIN值，找到最 小的MIN值，该值对应的路径为本次迭代的最佳路径。 第14页/共24页 四四.算法的实现算法的实现 6.信息素更新 对信息素矩阵进行更新，更新方法为： 新值为原信息素值乘以(1 - rho)，rho为信息素蒸发率，在加上 最小偏差值的倒数。程序如下： lfor i = 1 : N ltau(i,best_solution(1,i) = (1 - rho) * tau(i,best_solution(1,i)

10、 + 1/ tau_F; 信息数更新之后，再根据新的信息数矩阵，判断路径。进行迭 代运算。直到达到最大迭代次数，或偏离误差达到要求值。 第15页/共24页 四四.算法的实现算法的实现 程序运行完以后，聚类结果如图所示。从图中可以看出基本蚁 群聚类法的分类效果不太好。 第16页/共24页 四四.算法的实现算法的实现 程序运行结果： t = 1001 time = 23.4018 cluster_center = 1.0e+03 * 1.3710 2.6187 1.8872 1.3950 2.4997 2.1124 1.1438 2.6196 2.0613 1.6024 2.1673 2.0350

11、 best_solution_function_value = 6.3409e+04 index1 = 3 4 6 14 19 27 34 37 41 44 48 49 57 index2 = 1 2 7 9 15 23 24 40 43 45 50 58 index3 = 5 8 12 13 17 18 28 29 32 38 39 46 54 55 56 index4 = 1 至 15 列 10 11 16 20 21 22 25 26 30 31 33 35 36 42 47 16 至 19 列 52 53 59 第17页/共24页 五五.算法改进算法改进 o 基于遗传变异 的算法改进

12、第18页/共24页 五五.算法改进算法改进 改进代码： lpls = 0.1; %局部寻优阈值pls（相当于变异率） lsolution_temp = zeros(L,N+1); l k = 1; l while(k = L) l solution_temp(k,:) = solution_ascend(k,:); l rp = rand(1,N); %产生一个1*N(51)维的随机数组， l for i = 1:N l if rp(i) = pls %某值小于pls则随机改变其对应的路径标识 current_cluster_number = setdiff(1:K,solution_temp

13、(k,i); rrr=randint(1,1,1,K-1); lchange_cluster = current_cluster_number(rrr); lsolution_temp(k,i) = change_cluster; lend lend 第19页/共24页 五五.算法改进算法改进 程序运行完后，仿真结果如图所示。从图中可以看出MMAS聚类 效果比基本蚁群聚类效果要好，但分类效果还不是太好，说明该三元 色不适合使用该算法分类。 第20页/共24页 五五.算法改进算法改进 程序运行结果： t = 1001 time = 84.9270 cluster_center = 1.0e+03

14、 * 1.9095 2.3453 1.6705 0.4709 3.1052 2.2664 1.7053 2.0221 2.1305 1.6203 2.1557 2.0522 best_solution_function_value = 4.1595e+04 index1 = 1 至 15 列 1 3 8 14 15 19 22 24 26 33 36 39 41 43 45 16 列 47 第21页/共24页 五五.算法改进算法改进 index2 = 1 至 15 列 2 5 6 9 10 12 13 23 27 28 29 34 38 44 46 16 至 18 列 48 49 55 index3 = 11 16 17 18 20 37 40 42 50