历安毛子代枚大” 二、 蚁群算法 XIDIAN UNIVERSITY 蚁群算法的数学模型 >利用TSP问题来说明这个数学模型，TSP问题 可以描述为：给定一系列城市和每对城市之间 的距离，求访问每一座城市一次并回到起始城 市的最短回路。 >蚁群算法有两大步骤： ·路径构建 ·信息素更新 7
1 蚁群算法的数学模型 利用TSP问题来说明这个数学模型，TSP问题 可以描述为：给定一系列城市和每对城市之间 的距离，求访问每一座城市一次并回到起始城 市的最短回路。 蚁群算法有两大步骤： • 路径构建 • 信息素更新 二、蚁群算法 7
历些毛子种技大学 二、蚁群算法 XIDIAN UNIVERSITY 1 蚁群算法的数学模型 路径构建 每只蚂蚁都随机选择一个城市作为初始位置，按照一个随 机比例p(t)选择下一个要达到的城市。 p步(t)为时刻蚂蚁k从城市转移到城市的概率，此概率由两个因 素决定，一是该路径上信息素浓度，二是城市间的距离。 p听0=ju(9 ∑It(t)][n(t)]F' jeallow_k (2-1) 其中，(t)为该该段路径上的信息素浓度； u(0=击为启发函 数，即两城市距离的倒数，allow k为k可选城市集合，即未走过的 城市集合。α为信息素重要程度因子，B为启发函数因子，表示距离 的相对重要性。 6
1 蚁群算法的数学模型 • 路径构建 每只蚂蚁都随机选择一个城市作为初始位置，按照一个随 机比例 𝑝𝑖𝑗 𝑘 𝑡 选择下一个要达到的城市。 𝑝𝑖𝑗 𝑘 𝑡 为t时刻蚂蚁k从城市i转移到城市j的概率,此概率由两个因 素决定，一是该路径上信息素浓度，二是城市间的距离。 （2-1） 其中，𝜏𝑖𝑗(𝑡)为该该段路径上的信息素浓度； 𝜂𝑖𝑗 𝑡 = 1 𝑑𝑖𝑗 为启发函 数，即两城市距离的倒数， allow_k为k可选城市集合，即未走过的 城市集合。𝛼为信息素重要程度因子，𝛽为启发函数因子, 表示距离 的相对重要性。 二、蚁群算法 8 𝑝𝑖𝑗 𝑘 𝑡 = [𝜏𝑖𝑗(𝑡)] 𝛼 [𝜂𝑖𝑗(𝑡)] 𝛽 [𝜏𝑖𝑗(𝑡)] 𝛼[𝜂𝑖𝑗(𝑡)] 𝛽 , 𝑗𝜖𝑎𝑙𝑙𝑜𝑤_𝑘
历要毛子代枚大学 二、蚁群算法 XIDIAN UNIVERSITY 1 蚁群算法的数学模型 信息素更新 当所有蚂蚁到达终点时，必须把各路径的信息素浓度重新更新 一次，信息素的更新分为两部分：蒸发和增强 tij(t+1)=(1-p)*t(t)+∑1△t步(2-2) ， 如果蚂蚁k经过路径) △= C 0, 其他 0<p<1为信息素蒸发率，△x为第k只蚂蚁在城市与城市连接路 径上释放信息素而增加的信息素浓度：Q为信息素强度，在一定程度 上影响算法的收敛速度；C为在本轮中蚂蚁所走路径的总长度
1 蚁群算法的数学模型 • 信息素更新 当所有蚂蚁到达终点时，必须把各路径的信息素浓度重新更新 一次，信息素的更新分为两部分：蒸发和增强 𝜏𝑖𝑗 𝑡 + 1 = 1 − 𝜌 ∗ 𝜏𝑖𝑗 𝑡 + ∆𝜏𝑖𝑗 𝑚 𝑘 𝑘=1 （2-2） 0 < 𝜌 < 1为信息素蒸发率，∆𝜏𝑖𝑗 𝑘 为第k只蚂蚁在城市i与城市j连接路 径上释放信息素而增加的信息素浓度;Q为信息素强度，在一定程度 上影响算法的收敛速度；Ck为在本轮中蚂蚁k所走路径的总长度。 二、蚁群算法 9 ij 0 k k Q k ij C ，如果蚂蚁 经过路径 ， 其他
历些毛子代枝大学 二、蚁群算法 XIDIAN UNIVERSITY 蚁群算法的数学模型 >信息素更新的作用 ●信息素挥发：避免算法过快地向局部最优区域集中，有助于 搜索区域的扩展。 ●信息素增强：实现由单个蚂蚁无法实现的集中行动。基本蚁 群算法的离线更新方式是在蚁群中的m只蚂蚁全部完成n个城 市的访问后，统一对残留信息进行更新处理。 10
1 蚁群算法的数学模型 信息素更新的作用 信息素挥发：避免算法过快地向局部最优区域集中，有助于 搜索区域的扩展。 信息素增强：实现由单个蚂蚁无法实现的集中行动。基本蚁 群算法的离线更新方式是在蚁群中的m只蚂蚁全部完成n个城 市的访问后，统一对残留信息进行更新处理。 二、蚁群算法 10
历柴毛子代枚大学 二、蚁群算法 XIDIAN UNIVERSITY 1 蚁群算法的数学模型 >总结 在TSP问题中，首先随机设置m只蚂蚁的位置，即出发城市，且初始状态各城 市间路径上的信息素浓度相同，对每只蚂蚁构造路径，从出发城市，根据概 率公式，运用轮盘赌选择法依次选择下一个要到达的城市，直至经过所有城 市得到本轮的路径。至此m只蚂蚁便得到m条路径，即m个解向量。 。 在一轮结束之后，需要更新信息素浓度。根据公式，计算所有城市间的信息 素浓度并更新。 。 接着进行下一轮迭代，此时由更新后的信息素浓度来构造路径，如此进行迭 代，直到达到最大迭代次数或算法收敛，算法结束。 11
1 蚁群算法的数学模型 总结 • 在TSP问题中，首先随机设置m只蚂蚁的位置，即出发城市，且初始状态各城 市间路径上的信息素浓度相同，对每只蚂蚁构造路径，从出发城市，根据概 率公式，运用轮盘赌选择法依次选择下一个要到达的城市，直至经过所有城 市得到本轮的路径。至此m只蚂蚁便得到m条路径，即m个解向量。 • 在一轮结束之后，需要更新信息素浓度。根据公式，计算所有城市间的信息 素浓度并更新。 • 接着进行下一轮迭代，此时由更新后的信息素浓度来构造路径，如此进行迭 代，直到达到最大迭代次数或算法收敛，算法结束。 二、蚁群算法 11