全局路径规划 - 02 蚁群算法

算法流程:

  1. 设整个蚂蚁群中蚂蚁的数量为\(m\),城市的数量为\(n\),城市\(i\)与城市\(j\)之间的相互距离为\(d_{ij} \left( i,j=1,2,\cdots,n \right)\),\(t\)时刻城市与城市连接路径上的信息素浓度为\(\tau_{ij} \left(t\right)\)。初始时刻,各个城市间连接路径上的信息素浓度相同,不妨设为\(\tau_{ij} \left(0\right) = \tau_0\)。

  2. 蚂蚁\(k\left(k=1,2,……,m\right)\)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市,设\(P_{ij}^k \left( t\right)\)表示时刻\(t\)蚂蚁\(k\)从城市\(i\)转移到城市\(j\)的概率,其计算公式如下:

    \[P_{ij}^k= \begin{cases} \frac {\left[ \tau_{ij} \left( t \right) \right] ^ \alpha \cdot \left[ \eta_{ij} \left( t \right) \right] ^ \beta } {\Sigma_{s \in \text {allow}_k} \left[ \tau_{is} \left( t \right) \right] ^ \alpha \cdot \left[ \eta_{is} \left( t \right) \right] ^ \beta }, & {s \in \text {allow}_k } \\ 0, & {s \notin \text {allow}_k } \end{cases}\]

    其中,\(\eta_{ij} \left( t \right)\)为启发函数,,\(\eta_{ij} \left( t \right)=\frac {1}{d_{ij}}\)表示蚂蚁从城市\(i\)转移到城市\(j\)的期望程度,\(\text {allow}_k\)为蚂蚁\(k\)待访问城市的集合。开始时,\(\text {allow}_k\)中有个\(\left ( n-1 \right)\)元素,即包括了蚂蚁\(k\)除了发城市的其他所有城市。随着时间的推进,\text {allow}_k中的元素不断减少,直至为空,即表示所有的城市都访问完毕,\(\alpha\)为信息素重要程度因子,其值越大,表示信息素的浓度在转移中起的作用越大;\(\beta\)为启发函数重要程度因子,其值越大,表示启发函数在转移中的作用越大,即蚂蚁会以较大的概率转移到距离短的城市。

  3. 在蚂蚁释放信息素的同时,各个城市间连接路径上的信息素逐渐小时,设参数\(\rho \left ( 0 < \rho < 1 \right)\)表示信息素的挥发程度。因此,当所有蚂蚁完成一次循环后,各个城市间连接路径上的信息素浓度需要进行实时更新,具体公式如下:

    \[\tau _{ij} \left( t+1 \right) = \left( 1-\rho \right) \times \tau_{ij} \left( t\right) + \Delta \tau _{ij},\, 0 < \rho <1 \\ \Delta \tau_{ij} = \Sigma_{k=1}^{m} \Delta \tau_{ij}^k \]

    其中,\(\Delta \tau_{ij}^k\)表示第\(k\)只蚂蚁在城市\(i\)与城市\(j\)连接路径上释放的信息素浓度,\(\Delta \tau_{ij}\)表示所有蚂蚁在城市\(i\)与城市\(j\)连接路径上释放的信息素浓度之和。

注:在ant cycle system模型中,\(\Delta \tau_{ij}^k\)的计算公式为:

\[\Delta \tau_{ij} = \begin{cases} Q/L_k, & \text{第k只蚂蚁从城市i访问城市j} \\ 0, & \text {其他} \end{cases} \]

上一篇:elasticsearch多级嵌套查询笔记


下一篇:c-隐藏窗口的PrintWindow和BitBlt