科学家如何把蚂蚁的信息素转换为数学公式?

来源:百度知道 编辑:UC知道 时间:2024/06/03 22:58:33
昨天看纪实频道,他说蚂蚁公式可以更方便的调节交通,运输等,我很好奇,请问下哪位知道,蚂蚁公式是什么样的?而且怎么转换的啊?谢谢了

看样子楼主已经知道了信息素这个概念,在此我也不赘述了。

目前蚁群算法主要用在组合优化方面,基本蚁群算法的思路是这样的:
1. 在初始状态下,一群蚂蚁外出,此时没有信息素,那么各自会随机的选择一条路径。
2. 在下一个状态,每只蚂蚁到达了不同的点,从初始点到这些点之间留下了信息素,蚂蚁继续走,已经到达目标的蚂蚁开始返回,与此同时,下一批蚂蚁出动,它们都会按照各条路径上信息素的多少选择路线(selection),更倾向于选择信息素多的路径走(当然也有随机性)。
3. 又到了再下一个状态,刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation),而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁,重复第2个步骤。
每个状态到下一个状态的变化称为一次迭代,在迭代多次过后,就会有某一条路径上的信息素明显多于其它路径,这通常就是一条最优路径。

关键的部分在于步骤2和3:
步骤2中,每只蚂蚁都要作出选择,怎样选择呢?
selection过程用一个简单的函数实现:
蚂蚁选择某条路线的概率=该路线上的信息素÷所有可选择路线的信息素之和
假设蚂蚁在i点,p(i,j)表示下一次到达j点的概率,而τ(i,j)表示ij两点间的信息素,则:
p(i,j)=τ(i,j)/∑τ(i)
(如果所有可选路线的信息素之和∑τ(i)=0,即前面还没有蚂蚁来过,概率就是一个[0,1]上的随机值,即随机选择一条路线)
步骤3中,挥发和增强是算法的关键所在(也就是如何数学定义信息素的)
evaporation过程和reinforcement过程定义了一个挥发因子,是迭代次数k的一个函数
ρ(k)=1-lnk/ln(k+1)
最初设定每条路径的信息素τ(i,j,0)为相同的值
然后,第k+1次迭代时,信息素的多少
对于没有蚂蚁经过的路线:τ(i,j,k+1)=(1-ρ(k))τ(i,j,k),显然信息素减少了
有蚂蚁经过的路线:τ(i,j,k+1)=(1-ρ(k))τ(i,j,k)+ρ(k)/|W|,W为所有点的集合

为什么