即插即用！全新記憶回溯策略：一種元啟發式算法的進化更新機制，含完整免費MATLAB代碼

1. 簡介

元啟發式算法的搜索域總是不斷變化，這使得難以適應多樣化的優化問題。為了克服上述問題，提出了一種稱為記憶回溯策略（MBS）的進化更新機制，包括思維階段、回憶階段和記憶階段。總體而言，MBS的采用通過結合群體記憶、線索回憶和記憶遺忘機制來提高MHS的效率。這些策略提高了算法探索搜索空間、優化搜索過程和逃避局部最優的能力。MBS將應用于三種不同類型的MHS算法：基于進化（LSHADE_SPACMA）、基于物理（隨機分形搜索，SFS）和基于生物（海洋捕食者算法，MPA），以展示MBS的普適性。

2. 提出的方法

2.1. MBS的設計靈感

動物性是區分生物和非生物的重要特征，是個體發展早期出現的基本認知能力之一。人類在嬰兒早期就能區分生物和非生物[47]，這幾乎是一種天生的能力。從進化的角度來看，對環境中生物體的敏感性可以幫助個體生存和繁殖，因為它們可能是自然敵人或競爭對手，對它們的生存構成威脅，以及對生存有益的食物或配偶[48]。研究表明，人類的感知系統具有優先感知和處理重要信息的特征[49]。然而，僅僅檢測和感知重要信息不足以幫助人類適應環境。真正反映適應價值的是隨后的認知處理和受感知影響的行為反應[50]，其中記憶是一個核心組成部分。回憶的三種主要方式包括自由回憶、識別和線索回憶。在其中，線索回憶指的是先學習某事物，然后將新學到的事物（線索）與以前學到的事物聯系起來。哈德認為，遺忘不是記憶功能的失敗，而是記憶的一種功能。環境總是在不斷變化，為了生存，動物必須適應新環境。允許新信息覆蓋舊信息可以幫助動物更好地生存[51]。

因此，為了模擬記憶的保存和回憶，并將其應用于MHS，本文提出了以下定義。

2.2. MBS定義

首先，我們將個體與事件進行比較，個體的每個維度的值與條件（線索）進行比較，適應度值是事件結果。因為當個體完全相等時，它們的適應度值相等，即當事件的條件相等時，它們的結果相等。這有利于將MBS應用于不同類型的算法，并可以合理解釋。

受生物記憶機制的啟發，當發現事件的線索時，可以回憶事件的條件，事件的結果可以被回憶。然而，當生物不知道當前結果是否是最佳時，它們會嘗試獲得與記憶中不同的結果，并嘗試實現更好的結果。因此，當存在記憶時，它們將使用記憶混淆機制或記憶導向機制來嘗試新方法。所有生物的記憶都是有限的，因為適當的記憶大小有助于快速有效的回憶，而“環境總是在不斷變化，為了生存，動物必須適應新環境。允許新信息覆蓋舊信息可以幫助動物更好地生存”。因此，我們引入了記憶周期的概念。記憶周期的容量越少，單個記憶周期的容量越大，回憶成功的可能性越大，但回憶時間也會越長。為了更好地平衡回憶時間和收益，提高算法適應新環境的速度，本文假設每個算法有20個記憶周期，其中每個52次評估（或迭代）經歷一個記憶周期。同時，覆蓋將用于模擬生物遺忘。同時，生物通常會優先忘記不好的記憶，而后來忘記好的記憶。因此，在每個記憶周期結束時，當前記憶周期中的記憶將被整合并用于模擬生物思維和總結，以便下一個記憶周期優先考慮當前記憶周期中更差的記憶。

該策略主要包括以下階段：思考階段、回憶階段和記憶階段，其數學定義如下所示。

2.3. MBS的數學定義和偽代碼

(1) 思考階段

傳統方法直接計算算法獲得的個體的適應度值，使用MBS在思考階段，首先通過回憶階段獲得的記憶來確定它們是否以前經歷過。如果不是，將直接計算其適應度值，并將記憶階段的結果直接用作新方法的結果。如果結果將直接獲得作為新方法的結果，并且記憶階段將被執行以比較哪種方法更好并保留更好的方法。由于算法處于記憶的早期階段并且具有有限的記憶內容，因此無法通過記憶為算法提供良好的指導。此外，算法應在早期階段專注于探索。總體而言，算法在第一個記憶周期中不會執行面向記憶的機制，但只會執行記憶混淆機制。同時，為了模擬生物在發現它們以前經歷過的部分過程后通常只改變部分過程的行為，引入了以下內容：h表示需要更改的過程數，j表示需要更改的過程。具體計算過程如下：

$j = \{w_1, w_2, ..., w_h\}$
$\text{randperm}(\text{dim})$
$\text{ceil}(\text{dim}/5)$
$\text{popnew} = \text{pop}(w)$

其中randperm(dim)表示dim的自然數的隨機排列，dim是問題維度，ceil()是向上取整和向下取整函數，j是h維的非重復子索引，取w的前h個值。popnew是該個體的新位置，初始值與第i個個體pop(:,i)一致。

為了模擬生物渴望獲得更好結果并嘗試改變已知過程的行為，采用了記憶混淆機制。當個體成功回憶并執行時，計算將使用以下數學模型進行。

$\text{popnew}(j) = \text{pop}(i,j) + \text{step}(j), a \leq r_i$
$\text{step}(j) = \tan(\pi * (r_2 - 0.5)) * (-lb(j))/\log_2(\text{FEs})$

其中r1和r2是0和1之間的隨機值，參數a是執行記憶混淆或記憶導向機制的概率，ub(j)和lb(j)分別是第j維的上限和下限，FEs是當前評估次數。

為了模擬生物渴望獲得更好結果并嘗試接近記憶中更好位置的行為，引入了記憶導向機制。當個體成功回憶并執行時，計算將使用以下數學模型進行。

$\text{popnew}(j) = \frac{\sum_{\text{mi}=M}^{\text{Mmax}} \text{Memory}(\text{mi},j)}{(\text{Mmax} - M + 1)}, a > r_i$
$\text{Mmax} - \text{ceil}(\text{dim} * (3/2 - r_3))$

其中Mmax是內存大小的上限，其值是最大評估次數的5%。Mmax是內存中的個體位置，r3是0和1之間的隨機值。

在引入偽代碼之前，需要了解以下參數：Mw是當前內存位置，其值是值，初始值為0。Mmax是MBS的上限內存大小，其值是值。Memory是內存中的個體位置數組，大小為Mmaxdim。個體內存是大小為Mmax * 1的數組。pop：當前位置是大小為Ndim的數組，N是種群中的個體數。popfit是當前種群適應度值，是大小為N1的數組。popnew：當前個體的新位置，是大小為Ndim的數組。popnewfit：popnew的適應度值，是大小為N1的數組。 $pop_in$ ：輸入個體位置，是大小為1dim的數組。 $pop_in_fit：pop_in$ 的個體適應度值，其值是值。FEs是最大評估次數，其值是值。當前評估次數是a值。以下是思考階段的偽代碼。
在這里插入圖片描述

算法1. 思考階段的MBS算法

(1). 回憶階段

在回憶階段，人們會根據線索逐漸回憶，當線索被打斷時，就認為沒有匹配的經驗。圖1、圖2、圖3模擬了成功回憶的過程，其中綠色虛線表示比較后相等的兩個值，紅色虛線表示不等。圖1顯示了假設Memory(1, 1)、Memory(3, 1)和Memory(Mmax, 1)在使用記憶索引wh = {1, 2, 3, …, Mmax-1, Mmax}和當前回憶維度n=1進行回憶時與pop_in(1, 1)一致。因此，記憶索引wh將僅保留1、3和Mmax，然后重復上述操作，直到當前回憶維度n=2，直到記憶索引wh是一個值。如圖3所示，當記憶索引wh是一個值時，只需比較所有維度中與pop_in對應的Memory即可確定記憶中是否有相應的結果。
在這里插入圖片描述
圖1.線索召回，當內存索引wh={1,2,3，…， Mmax-1，Mmax}和召回的當前維度n=1時。

圖2.線索召回，當內存索引wh={1,3， Mmax}且召回的當前維度n=2時

圖3.線索召回成功，記憶指數wh=3

在記憶階段，Mw是當前的記憶位置指標，Mmax是最大的記憶容量。當Mw大于Mmax時，Mw會回到開始，即1。同時，由于每個記憶周期中的回憶思維過程，下一個記憶周期會優先忘記不好的記憶，稍后忘記更好的記憶。因此，記憶會根據其適應度值進行排序，適應度值較差的記憶被優先放置以進行覆蓋。它的偽代碼如算法3。

2.4. MBS各階段流程圖

圖4、圖5、圖6分別顯示了召回階段、記憶階段和思考階段的算法流程。圖7顯示了MBS版本算法和基本算法的區別。紅色箭頭表示它存在于基本算法中，但不存在于MBS版本算法中，而綠色箭頭表示它不存在于基本算法中，存在于MBS版本算法中。
在這里插入圖片描述

%% Thinking stage
function [Mw,Memory,Memoryf,pop,popf,FES]=...Memorybacktracking(Mmax,Mw,Memory,Memoryf,pop,fobj,FES,dim,lu)i=1;% global githowdeswhich1=findMemory(Memory,pop(i,:));if isequal(Memory(which1,:),pop(i,:))% githowdes=githowdes+1;popnew=pop;popf=Memoryf(which1,:);how=ceil(dim/5);what1=randperm(dim);what2=what1(1:how);if rand<0.8&&FES>Mmaxpopnew(i,what2)=mean(Memory(Mmax-dim+ceil(sign(rand-0.5)*rand*dim/2):Mmax,what2),1);elsepopnew(i,what2)=popnew(i,what2)+tan(pi.*(rand(1,how)-0.5)).*(lu(2,what2)-lu(1,what2))/log(FES);endpopnew(popnew>lu(2,:))=rand.*(lu(2,popnew>lu(2,:)) - lu(1,popnew>lu(2,:))) + lu(1,popnew>lu(2,:));popnew(popnew<lu(1,:))=rand.*(lu(2,popnew<lu(1,:)) - lu(1,popnew<lu(1,:))) + lu(1,popnew<lu(1,:));which1=findMemory(Memory,popnew(i,:));if isequal(Memory(which1,:),popnew(i,:))popnewf(i,1)=Memoryf(which1,1);elsepopnewf(i,1)=feval(fobj,popnew(i,:));FES=FES+1;[Mw,Memory,Memoryf]=saveMemory(Mmax,Mw,Memory,Memoryf,popnew(i,:),popnewf(i,1));endif popnewf(i,1)<popfpop=popnew(i,:);popf=popnewf(i,1);endelsepopf(i,1)=feval(fobj,pop(i,:));FES=FES+1;[Mw,Memory,Memoryf]=saveMemory(Mmax,Mw,Memory,Memoryf,pop(i,:),popf(i,1));endend

Heming Jia, Chenghao Lu, Zhikai Xing, Memory backtracking strategy:an evolutionary updating mechanism for meta-heuristic algorithms.DOI: https://doi.org/10.1016/j.swevo.2023.101456