1、主主 讲：周润景讲：周润景 教授教授单单 位：电子信息工程学院位：电子信息工程学院 蚁群算法聚类设计蚁群算法聚类设计目目 录录 算法的提出算法的提出算法的基本原理算法的基本原理模型建立模型建立算法的算法的实现实现算法改进算法改进结论结论 一一.蚁群算法的提出蚁群算法的提出蚁群算法蚁群算法(ant colony optimization, (ant colony optimization, ACO)ACO)，又称蚂蚁算法，是一种用来寻找优化，又称蚂蚁算法，是一种用来寻找优化路径的机率型算法。它由路径的机率型算法。它由Marco Marco DorigoDorigo于于19921992年在他的博士
2、论文中提出，其灵感来源年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。于蚂蚁在寻找食物过程中发现路径的行为。遗传算法在模式识别、神经网络、机器学习、遗传算法在模式识别、神经网络、机器学习、工业优化控制、自适应控制、生物科学、社工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用会科学等方面都得到应用。Macro Dorigo二二.算法的基本原理算法的基本原理 NestFoodObstacle图图1 蚂蚁正常行进，突然环境改变，增加了障碍物蚂蚁正常行进，突然环境改变，增加了障碍物二二.算法的基本原理算法的基本原理 NestFoodObstacle图图2 蚂蚁以等同
3、概率选择各条路径蚂蚁以等同概率选择各条路径较短路径信息素浓度高，选择该路径的蚂蚁增多较短路径信息素浓度高，选择该路径的蚂蚁增多二二.算法的基本原理算法的基本原理 图图3 蚂蚁选路过程示例蚂蚁选路过程示例EABDHCEABDHCd=0.5d=0.5d=1d=130ants30ants15ants15ants15ants15antst=0EABDHC30ants30ants20ants20ants10ants10antst=1二二.算法的基本原理算法的基本原理 NestFoodObstacle图图4 蚂蚁最终绕过障碍物找到最优路径蚂蚁最终绕过障碍物找到最优路径三三.模型建立模型建立 o 基于蚂蚁构
4、造墓地和分类幼体的聚类分析模型基于蚂蚁构造墓地和分类幼体的聚类分析模型o 基于蚂蚁觅食行为和信息素的聚类分析模型基于蚂蚁觅食行为和信息素的聚类分析模型 三三.模型建立模型建立 1.1.基于蚂蚁构造墓地和分类幼体的聚类分析模型基于蚂蚁构造墓地和分类幼体的聚类分析模型o蚁群构造墓地行为和分类幼体行为统称之为蚁群聚类行为。蚁群构造墓地行为和分类幼体行为统称之为蚁群聚类行为。o生物学家经过长期的观察发现，在蚂蚁群体中存在一种本能的聚集生物学家经过长期的观察发现，在蚂蚁群体中存在一种本能的聚集行为。蚂蚁往往能在没有关于蚂蚁整体的任何指导性信息情况下，将行为。蚂蚁往往能在没有关于蚂蚁整体的任何指导性信息情
5、况下，将其死去的同伴的尸体安放在一个固定的场所其死去的同伴的尸体安放在一个固定的场所。三三.模型建立模型建立 p真实真实蚁群的聚类行为蚁群的聚类行为 Deneuboug JL等人也等人也用用 pheidolepheidole pallidulapallidula蚂蚁做了实验。发现蚁群蚂蚁做了实验。发现蚁群会根据蚂蚁幼体的大小将会根据蚂蚁幼体的大小将其放置在不同的位置，分其放置在不同的位置，分别把其堆放在蚁穴周围和别把其堆放在蚁穴周围和中央的位置。中央的位置。 真实真实的蚁群聚类行为的蚁群聚类行为的实验结果右图，四张照的实验结果右图，四张照片分别对应为实验初始状片分别对应为实验初始状态、态、3
6、3小时、小时、6 6小时和小时和3636小小时的蚁群聚类情况。时的蚁群聚类情况。 三三.模型建立模型建立 o基本模型经过利用个体与个体和个体与环境之间的交互作用，实基本模型经过利用个体与个体和个体与环境之间的交互作用，实现了自组织聚类，并成功的应用于机器人的控制中现了自组织聚类，并成功的应用于机器人的控制中(一群类似于蚂一群类似于蚂蚁的机器人在二维网格中随意移动并可以搬运基本物体，最终把蚁的机器人在二维网格中随意移动并可以搬运基本物体，最终把它们聚集在一起它们聚集在一起)。该模型成功的应用引起了各国学者的广泛关注。该模型成功的应用引起了各国学者的广泛关注和研究的热潮。和研究的热潮。oLumer
7、E和和FaietaB通过在通过在Denurbourg的基本分类模型中引入数的基本分类模型中引入数据对象之间相似度的概念，提出了据对象之间相似度的概念，提出了LF聚类分析算法，并成功的将聚类分析算法，并成功的将其应用到数据分析中。其应用到数据分析中。三三.模型建立模型建立 2.基于基于蚂蚁觅食行为和信息素的聚类分析模型蚂蚁觅食行为和信息素的聚类分析模型蚂蚁在觅食的过程中，能够分为搜索食物和搬运食物两个环节。蚂蚁在觅食的过程中，能够分为搜索食物和搬运食物两个环节。每个蚂蚁在运动过程中都将会在其所经过的路径上留下信息素，而且每个蚂蚁在运动过程中都将会在其所经过的路径上留下信息素，而且能够感知到信息素
8、的存在及其强度，比较倾向于向信息素强度高的方能够感知到信息素的存在及其强度，比较倾向于向信息素强度高的方向移动，同样信息素自身也会随着时间的流逝而挥发，显然某一路径向移动，同样信息素自身也会随着时间的流逝而挥发，显然某一路径上经过的蚂蚁数目越多，那么其信息素就越强，以后的蚂蚁选择该路上经过的蚂蚁数目越多，那么其信息素就越强，以后的蚂蚁选择该路径的可能性就比较高，整个蚁群的行为表现出了信息正反馈现象。径的可能性就比较高，整个蚁群的行为表现出了信息正反馈现象。四四.算法的实现算法的实现由于蚁群优化算法是迭代求取最优值，所以事先无需训练数据，故取由于蚁群优化算法是迭代求取最优值，所以事先无需训练数据
9、，故取59组数据确定类别组数据确定类别。流程图如下：。流程图如下：四四.算法的实现算法的实现重要程序代码介绍：重要程序代码介绍：1.程序程序初始化初始化l X = load(data.txt);l N,n=size(X); % N =测试样本数;n =测试样本的属性数;l K = 4; % K = 组数; l R = 100; % R = 蚂蚁数; l t_max = 1000; % t_max =最大迭代次数; l best_solution_function_value = inf; % 最佳路径度量值（初值为无穷大，该值越小聚类效果越好） 2.信息素矩阵信息素矩阵初始化初始化信息素矩阵维
10、数为信息素矩阵维数为N*K（样本数（样本数*聚类数）初始值为聚类数）初始值为0.01。l c = 10-2;l tau = ones(N,K) * c; %信息素矩阵，初始值为0.01的N*K矩阵（样本数*聚类数）四四.算法的实现算法的实现3.蚂蚁路径的选择及蚂蚁路径的选择及标识标识定义标识字符矩阵solution_string，维数为R*N+1，初始值都为0，以信息矩阵中信息素的值确定路径（即确定分到哪一组），具体方法如下： 如果该样本各信息素的值都小于信息素阈值q，则取信息素最大的为作为路径。若最大值有多个，则从相同的最大值中随机取一个，作为路径。 若信息数大于阈值q，则求出各路径信息素占
11、该样本总信息素的比例，以概率确定路径。 4.聚类中心聚类中心选择选择聚类中心为该类所有样本的各属性值的平均值。5.偏离误差偏离误差计算计算偏离误差的计算，即各样本到其对应的聚类中心的欧式距离之和MIN。 MIN越小，聚类效果越好。计算各只蚂蚁的MIN值，找到最小的MIN值，该值对应的路径为本次迭代的最佳路径。四四.算法的实现算法的实现6.信息素信息素更新更新对信息素矩阵进行更新，更新方法为：新值为原信息素值乘以(1 - rho)，rho为信息素蒸发率，在加上最小偏差值的倒数。程序如下：l for i = 1 : N l tau(i,best_solution(1,i) = (1 - rho)
12、* tau(i,best_solution(1,i) + 1/ tau_F; 信息数更新之后，再根据新的信息数矩阵，判断路径。进行迭代运算。直到达到最大迭代次数，或偏离误差达到要求值。四四.算法的实现算法的实现程序运行完以后，聚类结果如图所示。从图中可以看出基本蚁群聚类法的分类效果不太好。四四.算法的实现算法的实现程序运行结果：程序运行结果：t =1001time = 23.4018cluster_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.0
13、350best_solution_function_value = 6.3409e+04index1 =3 4 6 14 19 27 34 37 41 44 48 49 57index2 =1 2 7 9 15 23 24 40 43 45 50 58index3 =5 8 12 13 17 18 28 29 32 38 39 46 5455 56index4 =1 至至 15 列列10 11 16 20 21 22 25 26 30 31 33 35 36 42 4716 至至 19 列列 52 53 59五五.算法改进算法改进o 基于遗传变异基于遗传变异的算法改进的算法改进五五.算法改进算
14、法改进改进改进代码：代码：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(k,i); rrr=rand
15、int(1,1,1,K-1); lchange_cluster = current_cluster_number(rrr); lsolution_temp(k,i) = change_cluster; lend lend五五.算法改进算法改进程序运行完后，仿真结果如程序运行完后，仿真结果如图所图所示。从图中可以看出示。从图中可以看出MMAS聚类聚类效果比基本蚁群聚类效果要好，但分类效果还不是太好，说明该三元效果比基本蚁群聚类效果要好，但分类效果还不是太好，说明该三元色不适合使用该算法色不适合使用该算法分类。分类。五五.算法改进算法改进程序运行结果：程序运行结果：t =1001time =84.
16、9270cluster_center =1.0e+03 * 1.9095 2.3453 1.6705 0.4709 3.1052 2.2664 1.7053 2.0221 2.1305 1.6203 2.1557 2.0522best_solution_function_value = 4.1595e+04index1 =1 至 15 列1 3 8 14 15 19 22 24 26 33 36 39 41 434516 列47五五.算法改进算法改进index2 =1 至 15 列2 5 6 9 10 12 13 23 27 28 29 34 38 444616 至 18 列48 49 55i
17、ndex3 =11 16 17 18 20 37 40 42 50 52 56 58index4 =7 21 25 30 31 32 35 51 53 54 57 59六六.结论结论基于遗传算法的改进之后缩短了迭代次数，减少了计算量。聚类基于遗传算法的改进之后缩短了迭代次数，减少了计算量。聚类的效果要好于基本的蚁群算法。但是，从整体上来说两种算法的聚类的效果要好于基本的蚁群算法。但是，从整体上来说两种算法的聚类效果都不太好，说明该算法不适合于酒的分类，体现了蚁群算法的局效果都不太好，说明该算法不适合于酒的分类，体现了蚁群算法的局限性，但蚁群算法被成功应用到了旅行商问题上，所以以后在应用该限性，但蚁群算法被成功应用到了旅行商问题上，所以以后在应用该算法时，我们应该根据具体问题而定。算法时，我们应该根据具体问题而定。
