Mantegna 算法与 Lévy 飞行

[原文链接]

Lévy 飞行是基于 Lévy 分布的随机搜索过程. Lévy 飞行是一种随机行走, 其中步长服从 Lévy 分布. 它通过模拟自然界中动物在寻找食物或迁徙过程中, 采取的长距离跳跃和短距离滑行相结合的移动模式. 其核心特点是步长的概率分布为重尾分布, 即存在相对较高的概率出现大跨步, 这使得动物能够在广阔的范围内进行搜索.

与传统的随机游走策略相比, Lévy 飞行策略具有以下优势:

* 提高搜索效率: 通过长距离跳跃, Lévy 飞行策略能够快速扩大搜索范围, 提高搜索效率;

* 跳出局部最优解: Lévy 飞行策略在搜索过程中偶尔会出现大跨步, 有助于跳出局部最优解, 寻找全局最优解;

* 适应性强: Lévy 飞行策略适用于各种复杂环境, 能够有效应对路径规划中的不确定性.

因此, Lévy 飞行算法作为一种高效的优化路径规划方法, 目前被广泛应用于智能优化算法中, 如麻雀搜索算法、鲸鱼优化算法、粒子群优化算法、蜣螂优化算法等等.

Mantegna 算法

Mantegna 算法是 Mantegna 于 1994 年提出的用于模拟对称 Lévy 稳定过程. 根据 Mantegna 算法, 可以通过生成两个正态分布的数据计算得到服从 Lévy 分布的数据. 采用北太天元数值计算通用软件来实现该算法的代码如下:

function [s] = levyrnd(beta, m, n)
%LEVYRND - Mantegna 算法生成对称 Lévy 稳定分布随机数组.
%
% 用法:
%   levyrng(beta);              - 生成单个服从参数为 beta 的 Lévy 分布数据；
%   levyrng(beta, m);           - 生成 m x m 维服从参数为 beta 的 Lévy 分布矩阵;
%   levyrng(beta, m, n);        - 生成 m x n 维服从参数为 beta 的 Lévy 分布矩阵.
%
% 示例:
% >> rng(1234);
% >> levyrnd(1.8)
% 0.5299
% >> levyrnd(0.5, 2)
%  0.7074   -0.0853
% -2.1705 -219.2879
% >> levyrnd(1.1, 2, 3)
% -0.6688    0.2140   -1.8900
% -3.4959    0.2340  -24.1111
%    
    narginchk(1, 3);
    if nargin == 1
        m = 1;
        n = 1;
    elseif nargin == 2
        n = m;    
    end
    % 计算 u ~ N(0, sigma^2) 的方差
    num = gamma(1 + beta) * sin(pi * beta / 2);
    den = gamma((1 + beta)/2) * beta * 2^((beta - 1)/2);
    sigma = (num / den)^(1/beta);
    % 生成随机变量 u 和 v, v ~ N(0, 1).
    u = normrnd(0, sigma, m, n);
    v = normrnd(0, 1, m, n);
    % 生成 Lévy 分布数据
    s = u ./ abs(v).^(1/beta);
end

Lévy 飞行

利用 Mantegna 算法, 可以生成一系列的服从 Lévy 分布的随机步长, 模拟 Lévy 飞行. 值得注意的是, 随机游走是在任意维度空间中, 一个点随机地向任意方向前进任意长度的距离, 然后不断的重复.

我们模拟从原点出发, 随机向任意方向前进步长为 $s$ 的 Lévy 飞行. 模拟过程如下:

clear;
clc;
% Lévy 分布参数
beta = 1.5;
% Lévy 飞行步数
n = 1000;
% 生成随机方向
angles = 2 * pi * rand(n, 1);
% 初始化数据
x = zeros(n + 1, 1);
y = zeros(n + 1, 1);
% 生成 Lévy 步长
s = levyrnd(beta, n, 1);
% 循环游走
for i = 1:n
    x(i + 1) = x(i) + cos(angles(i)) * s(i);
    y(i + 1) = y(i) + sin(angles(i)) * s(i);
end
% 绘制 Lévy 飞行随机游走
plot(x, y);
title("Levy 飞行策略");
xlabel("x");
ylabel("y");

得到的结果如图所示: