基于RRT的優(yōu)化器：一種基于快速探索隨機(jī)樹算法的新型元啟發(fā)式算法，附完整代碼

受機(jī)器人路徑規(guī)劃中常用的快速探索隨機(jī)樹（RRT）算法的搜索機(jī)制的啟發(fā)，我們提出了一種新穎的元啟發(fā)式算法，稱為基于RRT的優(yōu)化器（RRTO）。這是首次將RRT算法的概念與元啟發(fā)式算法相結(jié)合。RRTO的關(guān)鍵創(chuàng)新是其三種位置更新策略：自適應(yīng)步長游走、基于絕對差異的自適應(yīng)步長和基于邊界的自適應(yīng)步長。 這些策略使RRTO能夠有效地探索搜索空間，同時引導(dǎo)人群走向高質(zhì)量的解決方案，于2025年3月發(fā)表在SCI計(jì)算機(jī)類期刊 IEEE Access。

數(shù)學(xué)模型的RRTQ

RRTQ模型由四個主要階段組成：RRTQ算法的初始化、自適應(yīng)步長游走策略、絕對差值自適應(yīng)步長策略和基于邊界的自適應(yīng)步長策略。

A. 初始化

為了滿足元啟發(fā)式算法的要求，RRTQ算法中的每個代理都被視為一個起始點(diǎn)和搜索實(shí)體。最初，整個種群Q被初始化，如公式(7)所示。RRTQ種群由n個RRTQ代理組成，每個代理包含d維搜索參數(shù)。因此，整個種群Q可以由公式(8)表示。

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

這里，和分別是粒子在維度j上的下界和上界。初始化過程涉及在這些邊界內(nèi)隨機(jī)化每個粒子的參數(shù)，以有效分布粒子在整個搜索空間中，從而提高多樣性并防止過早收斂到局部最優(yōu)。初始化后，計(jì)算每個粒子的位置，初始適應(yīng)度值作為目標(biāo)函數(shù)F的輸入?yún)?shù)，如公式(10)所示。

B. 自適應(yīng)步長游走策略

RRT算法以其在廣泛探索未知區(qū)域時使用固定步長向隨機(jī)選擇點(diǎn)迭代的能力而聞名。然而，在復(fù)雜條件下，固定步長可能導(dǎo)致效率低下的探索。為了解決這個問題，我們將RRTQ的隨機(jī)采樣機(jī)制建模為自適應(yīng)步長游走策略，以增強(qiáng)RRTQ算法的搜索能力。

為了在探索和開發(fā)之間平衡優(yōu)化過程，設(shè)計(jì)了兩種類型的函數(shù)，其迭代次數(shù)不同。K和E的函數(shù)表達(dá)式分別在公式(11)和公式(12)中給出。為了直觀反映這兩種函數(shù)的特性，它們在1000次迭代后進(jìn)行了可視化，如圖4所示。K是區(qū)間[0, 1]上的單調(diào)遞減函數(shù)，早期階段逐漸減少，后期階段迅速減少。E是區(qū)間[0, 1]上的單調(diào)遞增函數(shù)，早期階段快速增長，后期階段逐漸增加。

圖4展示了E和K的可視化（迭代次數(shù)取1000為例）

自適應(yīng)步長游走的數(shù)學(xué)建模公式如下所示：

這里，表示粒子的更新位置。表示當(dāng)前粒子位置。是此策略中的自適應(yīng)步長。是范圍[0, 1]內(nèi)的隨機(jī)數(shù)，確保了激活此策略時方向的隨機(jī)性。步長隨著迭代次數(shù)的增加而逐漸減小。和分別是搜索空間的下界和上界。表示步長因子，確定此參數(shù)的方法將在第7節(jié)的敏感性分析中詳細(xì)討論。僅當(dāng)時執(zhí)行步長更新，該條件在早期迭代中最小化隨機(jī)游走，導(dǎo)致稀疏更新。相反，此條件允許在后期迭代中更頻繁地進(jìn)行探索，從而實(shí)現(xiàn)更密集的更新。這種方法增強(qiáng)了算法在后期迭代中逃離局部最優(yōu)的能力。在RRTQ代理的迭代過程中，如果代理的位置超過邊界，則碰撞檢測機(jī)制將其調(diào)整回邊界。

自適應(yīng)步長游走策略不僅促進(jìn)了RRTQ代理對當(dāng)前位置的深入探索，還通過結(jié)合全局隨機(jī)初始化方法，大大增強(qiáng)了全局搜索的有效性，有效防止算法陷入局部最優(yōu)。這種方法提高了粒子探索搜索空間的能力，與RRT算法的隨機(jī)探索特性緊密結(jié)合，從而實(shí)現(xiàn)對搜索空間的更有效覆蓋。自適應(yīng)步長游走策略的偽代碼如算法1所示。

算法1 自適應(yīng)步長游走策略

C. 絕對差值基礎(chǔ)自適應(yīng)步長策略

在RRT算法中，使用固定步長向隨機(jī)選擇點(diǎn)迭代在不同階段的適應(yīng)性是有限的。為了增強(qiáng)RRTQ算法的全局探索能力，引入了絕對差值基礎(chǔ)自適應(yīng)步長策略。該策略通過計(jì)算當(dāng)前粒子位置和當(dāng)前最優(yōu)位置之間的絕對差值動態(tài)調(diào)整步長。

更新基于當(dāng)前最優(yōu)位置，如公式(15)所示。該過程使用公式(16)計(jì)算代理的更新步長。

這里，表示代理的更新位置。表示當(dāng)前最優(yōu)代理的位置。參數(shù)是范圍[0, 1]內(nèi)的隨機(jī)數(shù)，是此策略中的關(guān)鍵角色，隨著迭代次數(shù)的增加，激活此策略的可能性增加。嚴(yán)格激活標(biāo)準(zhǔn)有效地平衡了探索和開發(fā)。設(shè)置為公式(17)通過測試。絕對差值反映了當(dāng)前和最優(yōu)粒子之間的距離，反映了當(dāng)前和最優(yōu)位置。是自適應(yīng)步長調(diào)整因子，如公式(18)所示。用于控制RRTQ代理的更新方向。用于生成隨機(jī)擾動，b設(shè)置為公式(19)。

這種設(shè)計(jì)不僅增強(qiáng)了步長更新的方向性，引導(dǎo)粒子朝向全局最優(yōu)位置，還通過引入隨機(jī)和非線性調(diào)整確保了搜索過程中的多樣性和全局探索能力。

絕對差值基礎(chǔ)自適應(yīng)步長策略通過調(diào)整步長在搜索空間的廣泛探索和局部微調(diào)之間實(shí)現(xiàn)了有效的平衡。這種策略通過動態(tài)調(diào)整搜索路徑中的自適應(yīng)步長，提高了算法的全局優(yōu)化性能和效率。該策略確保了在算法的后期階段，代理可以更精細(xì)地調(diào)整其位置。邊界自適應(yīng)步長策略結(jié)合RRT算法的局部擴(kuò)展機(jī)制，提高了RRTQ算法在接近目標(biāo)區(qū)域時的搜索精度和效率。該策略的偽代碼在算法2中給出。

算法2 絕對差值基礎(chǔ)自適應(yīng)步長策略

D. 基于邊界的自適應(yīng)步長策略

為了實(shí)現(xiàn)更精確的優(yōu)化，引入了基于邊界的自適應(yīng)步長策略。該策略的核心是使用非常小的隨機(jī)步長進(jìn)行探索，幫助RRTQ代理仔細(xì)搜索周圍區(qū)域。這不僅確保了對當(dāng)前最優(yōu)位置的局部搜索，還防止陷入局部最小值。

更新基于當(dāng)前最優(yōu)位置，如公式(21)所示。該過程使用公式(20)計(jì)算代理的更新步長。

這里，表示代理的更新位置。是當(dāng)前最優(yōu)代理位置。參數(shù)是范圍[0, 1]內(nèi)的隨機(jī)數(shù)。表示每個粒子維度的邊界長度。隨著迭代次數(shù)的變化而變化，用于生成周期性擾動。的值在公式(22)中定義。激活函數(shù)，如公式(23)所示，在迭代的后期階段起著關(guān)鍵作用，減少了激活此策略的可能性。更嚴(yán)格的激活標(biāo)準(zhǔn)顯著降低了算法的計(jì)算負(fù)擔(dān)。是控制粒子更新方向的自適應(yīng)調(diào)整因子，并確保步長自適應(yīng)減少，如公式(24)所示。

確保了激活此策略時方向的隨機(jī)性，幫助避免局部最優(yōu)。確保了隨著迭代次數(shù)的增加，步長自適應(yīng)減小。

通過這種微調(diào)機(jī)制，RRTQ算法可以更準(zhǔn)確地調(diào)整其搜索路徑，因?yàn)樗咏阉鹘K點(diǎn)，最大化每次迭代的價值，從而提高算法的整體搜索效率和結(jié)果質(zhì)量。該策略確保了在算法的后期階段，代理可以更精細(xì)地調(diào)整其位置。邊界自適應(yīng)步長策略結(jié)合RRT算法的局部擴(kuò)展機(jī)制，提高了RRTQ算法在接近目標(biāo)區(qū)域時的搜索精度和效率。該策略的偽代碼在算法3中給出。

算法3 基于邊界的自適應(yīng)步長策略

E. 提出的RRTQ算法

通過結(jié)合上述策略開發(fā)了提出的RRTQ算法。三種步長更新策略總結(jié)在表1中。其詳細(xì)偽代碼和機(jī)制圖分別在算法4和圖5中給出。RRTQ算法有效地整合了核心RRT搜索策略與自適應(yīng)機(jī)制，使其能夠有效地適應(yīng)搜索過程的不同階段。在早期迭代中，粒子具有更高的概率探索較大步長。在后期迭代中，它們自適應(yīng)地采取較小步長，逐步細(xì)化最優(yōu)粒子位置以實(shí)現(xiàn)更高精度的解決方案。值得注意的是，每種策略的貢獻(xiàn)和有效性通過消融實(shí)驗(yàn)進(jìn)行了評估，如第9節(jié)所討論的。

 

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:N
? ? Currentscore(1,i)=fobj(Pop(i,:));
? ??if?Currentscore(1,i)<Bestscore
? ? ? ? Bestscore=Currentscore(1,i);
? ? ? ? Bestposition=Pop(i,:);
? ? end
end
it=1;
C=10; % Penalty Factor
%% Main loop
while?it <= Max_iter
? ? k =?log(Max_iter - it)/log(Max_iter);
? ? E =(it/Max_iter)^(1/3);
? ? m1=E/10;
? ? m2=E/50;
? ? newpop = Pop;
? ??for?i=1:N
? ? ? ??for?j=1:dim
? ? ? ? ? ? % adaptive step size wandering strategy
? ? ? ? ? ? r1=rand();
? ? ? ? ? ??if?r1 < k
? ? ? ? ? ? ? ? S1=(r1-(k/2))*k*(Ub(j)-Lb(j))/C;
? ? ? ? ? ? ? ? newpop(i,j) = Pop(i,j)+S1;
? ? ? ? ? ? end
? ? ? ? ? ? % absolute difference-based adaptive step size strategy
? ? ? ? ? ? r2=rand();
? ? ? ? ? ??if?r2 < m1
? ? ? ? ? ? ? ? b = 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 strategy
? ? ? ? ? ? r3=rand();
? ? ? ? ? ??if?r3 < m2
? ? ? ? ? ? ? ? beta=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;
? ? ? ? ? ? end
? ? ? ? end
? ? end
? ??for?i=1:N
? ? ? ? % Coliision detection
? ? ? ? C_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,:));
? ? ? ? % Updata
? ? ? ??if?newscore(1,i)<Currentscore(1,i)
? ? ? ? ? ? Currentscore(1,i) = newscore(1,i);
? ? ? ? ? ? Pop(i,:) = newpop(i,:);
? ? ? ? ? ??if?newscore(1,i)< Bestscore
? ? ? ? ? ? ? ?Bestscore=Currentscore(1,i);
? ? ? ? ? ? ? ?Bestposition=Pop(i,:);
? ? ? ? ? ? end
? ? ? ? end
? ? end
? ? Convergence_curve(it)=Bestscore;
? ? % Next generation untill termination criterion
? ? it=it+1;
end
disp('RRTO is finished now! You can check the results! ? ? ? :)')
disp('---------------------------------------------------- ? :)')