摘要
引力搜索算法（GSA）是一种基于引力学说的启发式算法，用于解决复杂的优化问题。本文应用 GSA 于二维路径规划问题，通过优化路径来避开障碍物并达到目标点。实验结果表明，GSA 在路径规划中具有良好的表现，尤其在多障碍场景中，其优化路径平滑且避障效果显著。
理论
引力搜索算法是基于质量相互引力的原理构建的。在 GSA 中，粒子之间的相互引力决定了它们的移动路径。每个粒子代表一个候选解，其质量与适应度成正比。质量较大的粒子吸引其他粒子靠近，最终系统收敛到最优解。
在路径规划问题中，路径可以看作是粒子的轨迹，障碍物则产生斥力。通过引力搜索算法，可以找到避开障碍物的最优路径。公式如下：
-
引力公式：
-
速度更新公式：
-
位置更新公式：
其中，𝐺是引力常数，𝑀𝑖和𝑀𝑗是粒子的质量，𝑅𝑖𝑗是粒子之间的距离。
实验结果
第一个图展示了一个二维路径规划结果，其中不同颜色的圆形代表了障碍物，黑色曲线是 GSA 规划出的路径，起点和终点分别标记为方块和星星。
第二个图则是适应度随代数的变化曲线。如图所示，在前 50 代适应度值急剧下降，这表明算法快速收敛到较优解，之后适应度保持稳定，表明找到了较为理想的路径。
部分代码
以下是用 MATLAB 实现的部分代码：
% 初始化参数
num_particles = 30; % 粒子数量
dim = 2; % 二维空间
max_iter = 500; % 最大迭代次数
% 随机初始化粒子位置和速度
positions = rand(num_particles, dim);
velocities = zeros(num_particles, dim);
% 适应度函数
function fit = fitness_function(position)
% 计算距离目标点的距离
target = [6, 6]; % 假设目标点为(6,6)
fit = norm(position - target);
end
% 主算法循环
for iter = 1:max_iter
% 更新引力常数
G = G0 * exp(-alpha * iter / max_iter);
% 计算适应度并更新粒子质量
fitness = arrayfun(@fitness_function, positions);
masses = fitness / sum(fitness);
% 计算引力和更新速度、位置
for i = 1:num_particles
F = zeros(1, dim);
for j = 1:num_particles
if i ~= j
r = norm(positions(i,:) - positions(j,:));
F = F + G * (masses(i) * masses(j)) / (r^2 + epsilon) * ...
(positions(j,:) - positions(i,:));
end
end
velocities(i,:) = rand * velocities(i,:) + F;
positions(i,:) = positions(i,:) + velocities(i,:);
end
% 检查是否到达目标
if min(fitness) < tolerance
break;
end
end
参考文献
❝
Mirjalili, S., 2015. The Ant Lion Optimizer. Advances in Engineering Software, 83, pp.80-98.
Rashedi, E., Nezamabadi-pour, H. and Saryazdi, S., 2009. GSA: A Gravitational Search Algorithm. Information Sciences, 179(13), pp.2232-2248.
（文章内容仅供参考，具体效果以图片为准）
