当前位置：首页 > news >正文

基于RRT的优化器：一种基于快速探索随机树算法的新型元启发式算法

news 来源：原创 2025/8/25 23:48:19

受机器人路径规划中常用的快速探索随机树（RRT）算法的搜索机制的启发，我们提出了一种新颖的元启发式算法，称为基于RRT的优化器（RRTO）。这是首次将RRT算法的概念与元启发式算法相结合。RRTO的关键创新是其三种位置更新策略：自适应步长游走、基于绝对差异的自适应步长和基于边界的自适应步长。
这些策略使RRTO能够有效地探索搜索空间，同时引导人群走向高质量的解决方案，于2025年3月发表在SCI计算机类期刊 IEEE Access。
在这里插入图片描述

数学模型的RRTQ

RRTQ模型由四个主要阶段组成：RRTQ算法的初始化、自适应步长游走策略、绝对差值自适应步长策略和基于边界的自适应步长策略。

A. 初始化

为了满足元启发式算法的要求，RRTQ算法中的每个代理都被视为一个起始点和搜索实体。最初，整个种群Q被初始化，如公式(7)所示。RRTQ种群由n个RRTQ代理 $q_{ij}$ 组成，每个代理包含d维搜索参数。因此，整个种群Q可以由公式(8)表示。

$\begin{bmatrix} W_1 \\ W_2 \\ \vdots \\ W_n \end{bmatrix}; \quad W_i = [q_{i1}, q_{i2}, \cdots q_{id}]$

$\begin{bmatrix} q_{11} & q_{12} & \cdots & q_{1d} \\ q_{21} & q_{22} & \cdots & q_{2d} \\ \vdots & \vdots & \ddots & \vdots \\ q_{n1} & q_{n2} & \cdots & q_{nd} \end{bmatrix}$

其中i表示RRTQ代理的索引，d表示RRTQ维度的索引。每个粒子的初始化由公式(9)定义。

$q_{ij} = L_j + r_1 \cdot (U_j - L_j), \quad i = 1, 2, \cdots n; \quad j = 1, 2, \cdots d$

这里， $L_j$ 和 $U_j$ 分别是粒子在维度j上的下界和上界。初始化过程涉及在这些边界内随机化每个粒子的参数，以有效分布粒子在整个搜索空间中，从而提高多样性并防止过早收敛到局部最优。初始化后，计算每个粒子的位置，初始适应度值作为目标函数F的输入参数，如公式(10)所示。

$f_i = F(W_i)$

B. 自适应步长游走策略

RRT算法以其在广泛探索未知区域时使用固定步长向随机选择点迭代的能力而闻名。然而，在复杂条件下，固定步长可能导致效率低下的探索。为了解决这个问题，我们将RRTQ的随机采样机制建模为自适应步长游走策略，以增强RRTQ算法的搜索能力。

为了在探索和开发之间平衡优化过程，设计了两种类型的函数，其迭代次数不同。K和E的函数表达式分别在公式(11)和公式(12)中给出。为了直观反映这两种函数的特性，它们在1000次迭代后进行了可视化，如图4所示。K是区间[0, 1]上的单调递减函数，早期阶段逐渐减少，后期阶段迅速减少。E是区间[0, 1]上的单调递增函数，早期阶段快速增长，后期阶段逐渐增加。

$\frac{\ln(T - t)}{\ln(T)}$

$\sqrt[t]{T}$
在这里插入图片描述

图4展示了E和K的可视化（迭代次数取1000为例）。

自适应步长游走的数学建模公式如下所示：

$q_{i,j}^{\text{new}} = q_{i,j} + s_3$

$s_3 = \left( r_1 - \frac{K}{2} \right) \cdot K \cdot \frac{(U_{b_{ij}} - L_{b_{ij}})}{C}, \quad r_1 < K$

这里， $q_{i,j}^{\text{new}}$ 表示粒子的更新位置。 $q_{i,j}$ 表示当前粒子位置。 $s_3$ 是此策略中的自适应步长。 $r_1$ 是范围[0, 1]内的随机数， $K - K /2$ 确保了激活此策略时 $s_3$ 方向的随机性。步长 $s_3$ 随着迭代次数的增加而逐渐减小。 $L_{b_{ij}}$ 和 $U_{b_{ij}}$ 分别是搜索空间的下界和上界。 $C = 10$ 表示步长因子，确定此参数的方法将在第7节的敏感性分析中详细讨论。仅当 $r_1 < K$ 时执行步长更新，该条件在早期迭代中最小化随机游走，导致稀疏更新。相反，此条件允许在后期迭代中更频繁地进行探索，从而实现更密集的更新。这种方法增强了算法在后期迭代中逃离局部最优的能力。在RRTQ代理的迭代过程中，如果代理的位置超过边界，则碰撞检测机制将其调整回边界。

自适应步长游走策略不仅促进了RRTQ代理对当前位置的深入探索，还通过结合全局随机初始化方法，大大增强了全局搜索的有效性，有效防止算法陷入局部最优。这种方法提高了粒子探索搜索空间的能力，与RRT算法的随机探索特性紧密结合，从而实现对搜索空间的更有效覆盖。自适应步长游走策略的伪代码如算法1所示。

算法1 自适应步长游走策略

在这里插入图片描述

C. 绝对差值基础自适应步长策略

在RRT算法中，使用固定步长向随机选择点迭代在不同阶段的适应性是有限的。为了增强RRTQ算法的全局探索能力，引入了绝对差值基础自适应步长策略。该策略通过计算当前粒子位置和当前最优位置之间的绝对差值动态调整步长。

更新基于当前最优位置，如公式(15)所示。该过程使用公式(16)计算代理的更新步长 $s_2$ 。

$q_{i,j}^{\text{new}} = q_{\text{best},j} + s_2$

$s_2 = \alpha_1 \cdot |q_{\text{best},j} - q_{i,j}|, r_2 < m_1$

这里， $q_{i,j}^{\text{new}}$ 表示代理的更新位置。 $q_{\text{best}}$ 表示当前最优代理的位置。参数 $r_2$ 是范围[0, 1]内的随机数， $m_1$ 是此策略中的关键角色，随着迭代次数的增加，激活此策略的可能性增加。严格激活标准 $|q_{\text{best},j} - q_{i,j}|$ 有效地平衡了探索和开发。 $m_1$ 设置为公式(17)通过测试。绝对差值 $|q_{\text{best},j} - q_{i,j}|$ 反映了当前和最优粒子之间的距离，反映了当前和最优位置。 $\alpha_1$ 是自适应步长调整因子，如公式(18)所示。 $r_2 - m_1)/2$ 用于控制RRTQ代理的更新方向。 $(r_2 - r_2) \cdot e^{b}$ 用于生成随机扰动，b设置为公式(19)。

$m_1 = E/(10)$

$\alpha_1 = 5 \cdot (r_2 - m_1/2) \cdot \cos(2 \cdot \pi \cdot r_2) \cdot e^{b}$

$e^{cm(e^{-\pi/4})}$

这种设计不仅增强了步长更新的方向性，引导粒子朝向全局最优位置，还通过引入随机和非线性调整确保了搜索过程中的多样性和全局探索能力。

绝对差值基础自适应步长策略通过调整步长在搜索空间的广泛探索和局部微调之间实现了有效的平衡。这种策略通过动态调整搜索路径中的自适应步长，提高了算法的全局优化性能和效率。该策略确保了在算法的后期阶段，代理可以更精细地调整其位置。边界自适应步长策略结合RRT算法的局部扩展机制，提高了RRTQ算法在接近目标区域时的搜索精度和效率。该策略的伪代码在算法2中给出。

算法2 绝对差值基础自适应步长策略

在这里插入图片描述

D. 基于边界的自适应步长策略

为了实现更精确的优化，引入了基于边界的自适应步长策略。该策略的核心是使用非常小的随机步长进行探索，帮助RRTQ代理仔细搜索周围区域。这不仅确保了对当前最优位置的局部搜索，还防止陷入局部最小值。

更新基于当前最优位置，如公式(21)所示。该过程使用公式(20)计算代理的更新步长 $s_3$ 。

$q_{i,j}^{\text{new}} = q_{\text{best}} + s_3$

$s_3 = (U_{b_{ij}} - L_{b_{ij}}) \cdot \cos \beta \cdot \alpha_2, r_3 < m_2$

这里， $q_{i,j}^{\text{new}}$ 表示代理的更新位置。 $q_{\text{best}}$ 是当前最优代理位置。参数 $r_3$ 是范围[0, 1]内的随机数。 $U_{b_{ij}} - L_{b_{ij}}$ 表示每个粒子维度的边界长度。 $\cos \beta$ 随着迭代次数的变化而变化，用于生成周期性扰动。 $\beta$ 的值在公式(22)中定义。激活函数 $m_2$ ，如公式(23)所示，在迭代的后期阶段起着关键作用，减少了激活此策略的可能性。更严格的激活标准显著降低了算法的计算负担。 $\alpha_2$ 是控制粒子更新方向的自适应调整因子，并确保步长自适应减少，如公式(24)所示。

$\beta = 10 \cdot \pi \cdot t/T$

$m_2 = E/50$

$\alpha_2 = r_3 \cdot (r_3 - m_2/2) \cdot K \cdot (1 - t/T)$

$r_3 - m_2/2$ 确保了激活此策略时方向的随机性，帮助避免局部最优。 $\cdot (1 - t/T)$ 确保了随着迭代次数的增加，步长自适应减小。

通过这种微调机制，RRTQ算法可以更准确地调整其搜索路径，因为它接近搜索终点，最大化每次迭代的价值，从而提高算法的整体搜索效率和结果质量。该策略确保了在算法的后期阶段，代理可以更精细地调整其位置。边界自适应步长策略结合RRT算法的局部扩展机制，提高了RRTQ算法在接近目标区域时的搜索精度和效率。该策略的伪代码在算法3中给出。

算法3 基于边界的自适应步长策略

在这里插入图片描述

E. 提出的RRTQ算法

通过结合上述策略开发了提出的RRTQ算法。三种步长更新策略总结在表1中。其详细伪代码和机制图分别在算法4和图5中给出。RRTQ算法有效地整合了核心RRT搜索策略与自适应机制，使其能够有效地适应搜索过程的不同阶段。在早期迭代中，粒子具有更高的概率探索较大步长。在后期迭代中，它们自适应地采取较小步长，逐步细化最优粒子位置以实现更高精度的解决方案。值得注意的是，每种策略的贡献和有效性通过消融实验进行了评估，如第9节所讨论的。
在这里插入图片描述

G. -J. Lai, T. Li and B. -J. Shi, “RRT-Based Optimizer: A Novel Metaheuristic Algorithm Based on Rapidly-Exploring Random Trees Algorithm,” in IEEE Access, vol. 13, pp. 42744-42776, 2025, doi: 10.1109/ACCESS.2025.3547537.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% RRT-Based Optimizer source codes version 1.0
%
% Programmer: Guangjin Lai
% 
% Original paper: Guangjin Lai, Tao Li, Baojun Shi
%                 RRT-Based Optimizer: A novel metaheuristic algorithm based on rapidly-exploring random trees algorithm
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [Bestscore,Bestposition,Convergence_curve]=RRTO(N,Max_iter,lb,ub,dim,fobj)
disp('RRTO starts to work now! Plaease wait......   :)')
disp('-------------------------------------------   :)')
%% initialization
Lb=lb.*ones(1,dim);
Ub=ub.*ones(1,dim);
Bestposition=zeros(1,dim);
Bestscore=inf;
Convergence_curve=zeros(1,Max_iter);
newscore=zeros(1,N);
Pop=RRTO_initialization(N,dim,ub,lb);
Currentscore=zeros(1,N);
for i=1:NCurrentscore(1,i)=fobj(Pop(i,:));if Currentscore(1,i)<BestscoreBestscore=Currentscore(1,i);Bestposition=Pop(i,:);end
end
it=1;
C=10; % Penalty Factor
%% Main loop
while it <= Max_iterk = log(Max_iter - it)/log(Max_iter);E =(it/Max_iter)^(1/3);m1=E/10;m2=E/50;newpop = Pop;for i=1:Nfor j=1:dim% adaptive step size wandering strategyr1=rand();if r1 < kS1=(r1-(k/2))*k*(Ub(j)-Lb(j))/C;newpop(i,j) = Pop(i,j)+S1;end% absolute difference-based adaptive step size strategyr2=rand();if r2 < m1b = exp(cos(pi*(1-(1/it))));alpha1=5*(r2-m1/2)*cos(2*pi*r2)*exp(b);S2=alpha1*abs(Bestposition(1,j)-Pop(i,:));newpop(i,:)= Bestposition(1,j)+S2;end% boundary-based adaptive step size strategyr3=rand();if r3 < m2beta=10*pi*it/Max_iter;alpha2=r3*(r3-m2/2)*k*(1-it/Max_iter);S3=(Ub(j)-Lb(j))*cos(beta)*alpha2;newpop(i,j)=Bestposition(1,j)+S3;endendendfor i=1:N% Coliision detectionC_ub=newpop(i,:)>ub;C_lb=newpop(i,:)<lb;newpop(i,:)=ub.*C_ub+lb.*C_lb+(newpop(i,:).*(~(C_ub+C_lb)));newscore(1,i)=fobj(newpop(i,:));% Updataif newscore(1,i)<Currentscore(1,i)Currentscore(1,i) = newscore(1,i);Pop(i,:) = newpop(i,:);if newscore(1,i)< BestscoreBestscore=Currentscore(1,i);Bestposition=Pop(i,:);endendendConvergence_curve(it)=Bestscore;% Next generation untill termination criterionit=it+1;
end
disp('RRTO is finished now! You can check the results!       :)')
disp('----------------------------------------------------   :)')

数学模型的RRTQ

A. 初始化

B. 自适应步长游走策略

C. 绝对差值基础自适应步长策略

D. 基于边界的自适应步长策略

E. 提出的RRTQ算法

相关文章：