为提高算法中蚂蚁找到的近似解的效率，很多改进的蚁群算法都加入了局部搜索，特别是当问题域的启发信息不易获得时，加入局部搜索可以帮助找到更好的解。目前，局部搜索对所有解都实行，也可以只对部分解实行，本文只对当前可行解实行局部搜索。在局部搜索前，把所有的解按照目标函数值进行升序排列。本文将对具有高的目标函数值的头两个解进行局部搜索操作。局部搜索操作有很多种，这里选择交换操作。方法如下：
预先产生一个(0，1)间的随机数pls，以 pls=0.01为例。对表4-3中具有最高目标函数值的解集S10进行交换。为解集中的每个样本产生随机0.56367，0.35746，0.77456，0.46634，0.00139，0.54636，0.25635，0.35646，0.46324，0.14663。只有第五个样本的随机值小于pls，所以这个样本要被分到其他类当中。选择类中心与这个样本的距离最短的类为第 5 个样本要去的类。第 5 个样本原来在第二个类中，那么就要在另两个类中选取，经过计算将第 5 个样本重新分到第三类中去。继而对解集 S9也进行交换操作。对于通过交换而产生的新的解集要重新计算其目标函数值，与原解集的目标函数值比较，择优。执行过局部搜索之后，要对信息素值进行更新。信息素更新公式采用蚂蚁系统中的公式：
k?ij(t?1)?(1??)?ij(t)????ij i=1,...,N j=1,...,K
k?1k其中，τij(t)及τij(t +1)为样本 i 与类 j 在 t 及 t+1 时间的信息素浓度。
Q if ij?Lk?LK?k??ij??
??0 otherwiseLk为蚂蚁 k 所找到的最小目标函数值。
Q 为一参数值。
ρ为信息素蒸发参数，0<ρ<1。 至此，一次迭代结束。
4.3.1 改进后蚁群聚类算法流程
改进的蚁群聚类算法的主要步骤叙述如下：
步骤 1：初始化，包括蚂蚁数目 R、类的个数 K、转换规则参数 q0、局部搜索阈值等。
步骤 2：所有人工蚂蚁根据上一次的信息构建解集，计算各类中心。 步骤 3：在产生的解集找到要交换样本的 Sk实施局部搜索操作。 步骤 4：更新信息素值。
步骤 5：如果没有达到迭代次数预定值并且没有稳定解，则转步骤2，否则输出最优的分类解集。
算法基本流程如图4-7。
初始化每只蚂蚁分配到初始节点每只蚂蚁根据转换概率选择要转移的下一个节点进行信息素局部更新所有蚂蚁构建出问题的近似解？是否进行全局信息素更新否到达设定的迭代次数或出现稳定解？是结束搜索
图 4-7蚁群算法流程图
当然，迄今为止蚁群算法已经有了很多的变型或改进算法，但基于蚁群算法（ACA）寻找问题近似解的思想及实现优化过程的机制还是没有改变。由上图可见，蚁群算法区别于其他传统优化算法，因为它具有以下3个特点：
(1) 模拟了一种大自然真实存在的现象，并建立模型； (2) 不可确定性；
(3) 总是表现出一种并行性，不是在系统中强行加入，而是算法本身隐含具有的。
4.4 仿真实验对比分析
在4.2小节中本文详细介绍了基本蚁群算法的原理等，在本小节中将通过计算机仿真来理解基本蚁群算法的原理，并将作出的路径图和最终结果自动保存到文本文档(.txt)与Excel(.xls)中。
4.4.1 仿真环境与数据
为了详细对比出两种不同算法（改进前与改进后）算法优劣，本文实验采用同一种实验数据：样例网站则名老中医系统的日志数据，实验数据中纪录数共8136条，经过对这些日志数据的预处理，可以获取到能够用于传统蚁群算法与增加局部搜索算法后的蚁群算法条件的数据。
蚁群算法在实际问题的求解过程当中往往具有较高的效率，尽管在不同程度上取得了一定的效果，但是仍然存在着一些不足之处，主要表现在：1）如果一些参数α、β、ρ、m、Q设置不合理，那么就会导致迭代速度非常慢，并且结果误差较大；2）从蚁群算法本身来讲，其计算量非常大，相应的计算周期比较长；3）蚁群算法可以通过选取不同的路线来获得最优解，在具体循环次数的条件下，还可以根据不同的实际问题来对图像的内容进行优化处理，根据处理的结果来找到相应的最优解，这样就能够保证计算效率不会受到影响。从目前来看，蚁群算法的参数设置以及属性方面的研究仍然存在着较多的难点，其研究进度仍然只是停留在实验阶段，尚未大规模投入到实际应用当中。M. Dorigo等人结合具体的实验类型和数据来对蚁群算法的基本属性进行了全面性的分析和研究。
所以本实验中重要参数设置如下：
信息素浓度影响力参数α：所有算法α设为1.0。 启发式信息影响力参数β：所有算法β设为5.0。
信息素蒸发系数ρ((1-ρ)表示信息素的持久性系数)：所有算法ρ设为0.5(1-ρ即为0.5)。
蚂蚁数目m：本文将m设为问题规模n的2/5即m=n*2/5在算法开始时蚂蚁随机分布在各个城市上。（n为其中TSP问题中后面的数字，如:ATT48.TSP中48即为n值）。
TSP问题：本文使用ATT48.TSP的TSP问题。
4.4.2 对比实验
用4.2传统蚁群算法与4.3改进后蚁群算法的条件进行计算机仿真，为了有效的、科学的对算法有效性进行评价，采用准确度作为模型的评价标准。准确度定义如下：
Precision=R/(R+W)*100%
其中，R表示正确的结果，W表示错误结果。
设定θ为网页之间的转移概率的阈值，当转移概率大于该θ的路径即为用户感兴趣路径。若感兴趣路径阈值θ的值较低，那么不相关的网页被推荐。大量实验表明，θ=0.5最好，因此本文的θ值为0.5，本文改进后的蚁群算法与对比的传统蚁群算法对于不同的事务长度，用户感兴页面进行日志挖掘后预测的准确度如表4.4所示：
表4.4挖掘准确度对比
事务长度 本文改进后蚁群算法 3 4 5 6 7 8 9 65 73 82 87 83 86 89 56 62 69 81 79 85 89 传统的蚁群算法
图4.8两种算法的预测准确度（蓝色为改进后，红色为传统算法）
根据图4.8可知，相对于传统蚁群算法，本文设计的改进后的蚁群算法的日
志挖掘准确度更高，能更加有效地跟踪用户的兴趣变化，主要由于蚁群算法采用信息素机制实现正负反馈机制。对比结果表明，基于蚁群算法的Web网站日志挖掘模型可以很好挖掘用户的兴趣路径，蚂蚁之间的协作作用改善了用户浏览页面预测的准确度，动态跟踪用户浏览行为。
另外，本文选取另外的网页页面个数分别为50、100、200的网站，对其网站日志采用本文的日志获取方法进行了提取，然后根据大小将其划分为四个测试用命，大小分别为1 M，2 M，3 M，4 M，并继续对数据进行预处理，使之符合本文算法与传统蚁群算法条件，然后考察其CPU执行时间。实验结果为传统蚁群算法的CPU时间大于本文算法的CPU时间；而且随着测试用例的日志数量的增加，本文改进后的算法执行时间增加速率较慢，对传统蚁群算法的执行时间增加的幅度相对较大；缺点为本文算法对于网站上的链接数目敏感，如果网站上的URL数目增多，本文算法的执行时间延长，而传统蚁群算法执行时间与URL个数无关。
最后，本文也评测了网站服务器的性能受用户行为获取机制的影响。本文统计了50次在用户行为获取机制加载前后，用户计算机浏览器中载入网站页面所需的时间，加载时间的平均增量为140毫秒，用户基本的上网行为不会受到影响。
本节将改进后的蚁群算法引入到Web日志挖掘建模中，通过蚁群算法的正负反馈机制和路径概率选择机制快速找到用户目标网页，仿真实验结果对比表明，改进后的蚁群算法提高了网页日志挖掘中的预测精度，更能反映出用户的浏览兴趣与意图。
4.5 改进后的蚁群聚类算法应用场景实验
上节利用蚁群聚类算法对人工数据进行了分析，现在本文会利用该算法对2005年中国24所高校综合实力进行分类，同时来验证蚁群聚类算法的实际应用效果。
下面是2005年中国24所高校综合实力数据集，见表 4-5，表4.5主要表示的是24个样本集合，每个样本集合都有其独特的属性，通过设置10只蚂蚁来对下列3个样本进行分析，迭代次数1000次。
表 4-52005年中国24所高校综合实力数据表：
指标 序号 1 清华大学 100.0 声誉得分 学术资源得分 93.1 学术成果得分 100.0 学生情况得分 100.0 教师资源得分 100.0 物资资源得分 100.0