A gravity search algorithm with a distance-fitness evaluation strategy for path planning

在计算机科学领域，人们一直在为一个难题而苦苦挣扎：如何找到一个变量过多、无法逐一检查的最优解。想象一下，你正试图在一个充满丘陵和山谷的广袤且大雾弥漫的景观中寻找最低点。你无法看到整张地图，也无法走遍每一条路径。为了解决这个问题，科学家们开发了“群智算法”（swarm intelligence algorithms），这种算法模仿了鸟类或蚂蚁等动物群体如何协作寻找食物或建造巢穴。其中一种方法是引力搜索算法（Gravity Search Algorithm）。它将每一个潜在的解视为一个具有质量的粒子。就像行星通过引力相互吸引一样，这些粒子也在相互吸引。一个粒子的质量越大——意味着它的解越好——它的引力就越强。随着时间的推移，整个粒子群会向着最重、最有希望的解漂移，希望能在这片浓雾中找到那个绝对的最佳答案。

然而，这种方法存在一个缺陷。在复杂的、多雾的景观中，粒子经常会陷入困境。它们可能会发现一个小山谷，看起来像是底部，但实际上那只是深邃峡谷侧边的一个小凹陷。一旦群体在此定居，它们就会停止寻找更好的目标，认定自己已经找到了奖赏。这被称为“早熟收敛”（premature convergence），它会让计算机得到一个还不错但并非最好的答案。中国桂林信息技术学院的研究人员致力于修复这一弱点。他们想要创造一种能够探索更广阔世界而不被困在局部低洼处的算法版本，确保即使在最困难的地形中也能找到真正的最低点。

由冯志超、隋建、罗珍珍领导的团队开发了一个名为 SDGSA 的新版本算法。其改进的核心在于对粒子行为方式的两项具体调整。首先，他们调整了“引力”本身。在原始方法中，粒子间的吸引力以固定且可预测的速度减弱。新团队使这种减弱速率变得灵活：在搜索的早期阶段，即粒子仍在探索未知领域时，引力减弱缓慢，允许它们走得更远、更广；随着搜索的推进以及粒子逐渐接近某个解，引力会更快地减弱，从而鼓励它们集中精力研究最有希望的区域。这种动态调整防止了群体过早得出结论，也避免了在接近答案时浪费时间漫无目的地游荡。

第二个、也是更为显著的变化，是算法如何决定谁是“领导者”。在旧系统中，群体仅仅跟随得分最高的单个粒子。然而，新系统采用了一种“距离-适应度”（distance-fitness）策略。它不仅看一个解有多好，还会观察该解相对于其他解所处的位置。如果一个粒子的得分很高，但却紧挨着群体中的其他成员，算法就会意识到它无法提供新的信息。相反，它会寻找那些得分较高且远离人群的粒子。这确保了群体在向高质量解移动的同时，能持续探索新的、未知的区域。通过平衡“优质得分”与“距离”的需求，该算法维持了一个多样化的探索者群体，使得整个团队很难被困在单一的、次优的山谷中。

为了测试这些变化是否真的奏效，研究人员让新算法经历了一系列严格的试验。他们使用了五十八个不同的复杂数学问题，涵盖了从简单的曲线到高度纠缠的多维谜题。他们将新的 SDGSA 与原始的引力搜索方法以及其他十一个目前科学家和工程师常用的流行优化算法进行了对比。结果显而易见。在绝大多数测试中，新算法找到了比竞争对手更好的解。它在避开那些困扰旧方法的局部陷阱方面表现得尤为出色。在许多情况下，当其他算法止步于一个“尚可”的解时，它找到了真正的最佳答案。数据表明，新方法不仅更准确，而且更高效，能以更少的计算步骤达到这些高质量的解。

随后，研究人员将他们的算法从抽象的数学世界带入实际应用：无人驾驶飞行器（即无人机）的飞行路径规划。目标是在避开山脉和危险威胁区的同时，引导无人机从起点到达目的地，并保持飞行路径尽可能短且平滑。他们创建了两种不同的场景：第一种是带有规则山脉的相对简单的地形；第二种是更为复杂的环境，拥有不规则的地形和大型、重叠的危险区。在两种情况下，他们都将新算法与标准的引力搜索法进行了对比。

实景模拟的结果令人震惊。在第一种场景中，新算法规划出的路径比标准方法找到的路径缩短了近百分之四十，并且完成规划过程所需的时间不到原来的一半。在第二种更混乱的场景中，这种优势更加明显。新算法找到的路径比标准方法缩短了百分之四十，并将总飞行成本降低了百分之六十。可视化结果显示，虽然标准方法经常采取绕路、低效且靠近障碍物的路线，但新算法能在复杂的地形中找到直接且安全的通道。这证明了对数学模型的改进可以直接转化为现实工程任务中的切实利益。

这项研究得出结论：通过使引力拉力具有自适应性，并赋予“距离”与“质量”同等的价值，该算法成为了解决困难问题的强大工具。它不再依赖于关于如何移动或跟随谁的单一、僵化的规则。相反，它平衡了“探索未知”的冲动与“利用已知优选区域”的需求。这种平衡使其能够在复杂优化问题的迷雾景观中航行而不迷失方向。对于设计无人机、管理交通流量或管理能源网的工程师来说，这意味着他们拥有了一个更不容易陷入困境、且更有可能找到真正最佳路径的工具。这项工作表明，通过适当的调整，即使是简单的、受自然启发的想法，也可以被精炼以应对现代技术中最复杂的挑战。