【智能算法应用】引力搜索算法求解二维路径规划问题
摘要
引力搜索算法（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_particlesF = zeros(1, dim);for j = 1:num_particlesif i ~= jr = norm(positions(i,:) - positions(j,:));F = F + G * (masses(i) * masses(j)) / (r^2 + epsilon) * ...(positions(j,:) - positions(i,:));endendvelocities(i,:) = rand * velocities(i,:) + F;positions(i,:) = positions(i,:) + velocities(i,:);end% 检查是否到达目标if min(fitness) < tolerancebreak;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.
（文章内容仅供参考，具体效果以图片为准）