【算法应用】基于A*-蚁群算法求解无人机城市多任务点配送路径问题

1.A星算法原理

A*算法是一种基于图搜索的智能启发式算法，它具有高稳定性和高节点搜索效率。主要原理为：以起点作为初始节点，将其加入开放列表。从开放列表中选择具有最小总代价值$f(n)$的节点作为当前节点，其中$f(n)$由实际路径代价$g(n)$和到目标点估计代价$h(n)$组成。检查当前节点是否为目标节点，如果是，则算法结束并通过逆向追踪重建路径。如果不是，将当前节点移至封闭列表，并检查其所有邻居，对每个邻居更新或计算其代价，将未在开放或封闭列表中的邻居添加到开放列表。重复上述步骤直到目标节点被找到或开放列表为空。

2.蚁群算法原理

蚁群算法的灵感来源于蚂蚁觅食的行为。蚂蚁在寻找食物的过程中，会通过释放信息素来指导其他蚂蚁选择路径。当蚂蚁找到食物并返回巢穴时，它们沿途留下的信息素使得其他蚂蚁更倾向于选择信息素浓度更高的路径。通过不断的迭代和信息素更新，蚂蚁群体逐渐能够找到最优或近似最优的解。

对于第$k$只蚂蚁选择从节点$i$到节点$j$的路径，路径选择概率$P_{ij}^k$：
$$P_{ij}^k=\frac{({\tau }_{ij}^{\alpha })\cdot \left({\eta }_{ij}^{\beta }\right)}{{\sum }_{l\in N_i}\left({\tau }_{il}^{\alpha }\right)\cdot \left({\eta }_{il}^{\beta }\right)}$$

其中，${\tau }_{ij}$是$i,j$路径之间信息素浓度，${\eta }_{ij}$为启发式函数（对于TSP问题取距离倒数），$\alpha ,\beta$分别为权重因子。
在每一轮迭代后，信息素会根据蚂蚁的表现进行更新：
$${\tau }_{ij}(t+1)=(1-\rho )\cdot {\tau }_{ij}(t)+\Delta {\tau }_{ij}$$
其中，$\rho$为信息素挥发因子。

3.结果展示

4.代码获取