第二章 蚁群算法.ppt

智能优化计算 全局信息素更新 只针对全局最优解进行更新： 2.4 改进的蚁群优化算法 2.4.3 蚁群系统 智能优化计算 最大－最小蚂蚁系统（max-min ant system, MMAS）的改进之处 （1）每次迭代后，只有最优解（最优蚂蚁）所属路径上的信息被更新； （2）为了避免过早收敛，将各条路径可能的信息素限制于[τmin ,τmax]； （3）初始时刻，各路径上信息素设置为τmax ，在算法初始时刻，ρ取较小值时算法有更好的发现较好解的能力。 2.4 改进的蚁群优化算法 2.4.4 最大－最小蚂蚁系统 智能优化计算 信息素的全局更新 使所有蚂蚁完成一次迭代后，进行信息素更新： 2.4 改进的蚁群优化算法 2.4.4 最大－最小蚂蚁系统 智能优化计算 基于排序的蚂蚁系统（rank-based version of ant system, ASrank） 每次迭代完成后，蚂蚁所经路径按从小到大的顺序排列，并对它们赋予不同权值，路径越短权值越大。全局最优解权值为w，第r个最优解的权值为max{0,w-r}。 2.4 改进的蚁群优化算法 2.4.5 基于排序的蚂蚁系统 智能优化计算 基于排序的蚂蚁系统（rank-based version of ant system, ASrank） 信息素更新： 2.4 改进的蚁群优化算法 2.4.5 基于排序的蚂蚁系统 智能优化计算 优化结果比较 对对称TSP各迭代10000次，对非对称TSP各迭代20000次： 2.4 改进的蚁群优化算法 2.4.6 各种蚁群优化算法的比较 TSP实例 MMAS ACS ASelite AS Eil51.tsp 427.6 428.1 428.3 437.3 kroA100.tsp 21320.3 21420.0 21522.83 22471.4 D198.tsp 15972.5 16054.0 16205.0 16705.6 Lin318 42220.2 42570.0 43422.8 45535.2 Ry48p.atsp 14553.2 14565.4 14685.2 15296.4 Ft70.atsp 39040.2 39099.0 39261.8 39596.3 Kro124p.atsp 36773.5 36857.0 37510.2 38733.1 Ftv170.atsp 2828.8 2826.5 2952.4 3154.5 智能优化计算 典型应用列表 2.5 蚁群优化算法的应用 2.5.1 典型应用 智能优化计算 如何应用 用蚁群算法解决数据分类（数据挖掘任务中的一种）的问题： 预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。 当数据量很大时，难以人为判别分类。 2.5 蚁群优化算法的应用 2.5.2 医学诊断的数据挖掘 智能优化计算 如何应用 分类的规则： IF term1 AND term2 AND … THEN class 每个term是一个三元组（属性、关系符、属性取值） 希望在一个规则中使用最少的判别语句，采用蚁群优化算法达到最优的选择。 2.5 蚁群优化算法的应用 2.5.2 医学诊断的数据挖掘 智能优化计算 例：非典型肺炎 考虑如下因素： 2.5 蚁群优化算法的应用 2.5.2 医学诊断的数据挖掘 属性 发热 职业 胸部阴影 流行病学史 值 （0,1,2,3） （0,1,2） （0,1,2） （0,1,2） 说明 0：不考虑该属性 1：37.5℃以下 2：37.5 ℃ ～38.5 ℃ 3：38.5 ℃以上 0：不考虑该属性 1：医务人员 2：其他人员 0：不考虑该属性 1：无 2：有 0：不考虑该属性 1：无 2：有 智能优化计算 例：非典型肺炎 结构图： 一个蚂蚁从始点行走至终点，得到一条路径{0, 2, 1, 0}，其对应的规则为 IF （职业＝其他人员）AND（胸部阴影＝无）THEN （非典型肺炎） 对此路径，应给予非常差的评价。 2.5 蚁群优化算法的应用 2.5.2 医学诊断的数据挖掘 智能优化计算 蚁群算法的实现 假设a表示属性的总个数，第i个属性的取值域中可取