即插即用！全新记忆回溯策略：一种元启发式算法的进化更新机制，含完整免费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 } j = \{w_1, w_2, ..., w_h\} j={w1​,w2​,...,wh​}
$$w=\text{randperm}(\text{dim})$$
$$h=\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\le r_i$$
$$\text{step}(j)=\tan (\pi \ast (r_2-0.5))\ast (-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$$
$$M=\text{Mmax}-\text{ceil}(\text{dim}\ast (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的数组。$po{p}_{i}n$：输入个体位置，是大小为1dim的数组。$po{p}_i{n}_{f}it：po{p}_{i}n$的个体适应度值，其值是值。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