1.簡介

元啟發(fā)式算法（MH）是自然啟發(fā)的全局優(yōu)化算法，往往比較簡單，可以在短時(shí)間內(nèi)解決問題，具有一定的好處。但是，隨著問題變得更加復(fù)雜，算法所能獲得的解往往不是問題的最優(yōu)解，這就限制了其應(yīng)用場(chǎng)景。因此，提高現(xiàn)有算法的性能和求解精度對(duì)于擴(kuò)展其應(yīng)用能力至關(guān)重要。在傳統(tǒng)優(yōu)化算法中，往往有兩個(gè)概念，即探索和利用。探索是指大范圍的離散搜索，用于避免陷入局部最優(yōu)，而利用是指小范圍的集中探索，用于提高算法精度。 如何平衡探索與利用是增強(qiáng)算法性能和問題適應(yīng)性的關(guān)鍵。本文提出了一種全新的策略，命名為引導(dǎo)學(xué)習(xí)策略（GLS）來解決上述問題。GLS通過計(jì)算近幾代個(gè)體歷史位置的均方差來獲得種群的分散程度，并推斷出算法當(dāng)前需要什么指導(dǎo)。當(dāng)算法偏向于探索時(shí)，就會(huì)引導(dǎo)算法去探索。反之，就會(huì)引導(dǎo)算法去探索。正是因?yàn)檫@種策略能夠識(shí)別算法當(dāng)前的需求并提供輔助，才能提高大多數(shù)算法的性能。

2.提出的GLS

2.1 GLS的設(shè)計(jì)靈感

在建構(gòu)主義學(xué)習(xí)理論中，假設(shè)知識(shí)是建構(gòu)起來的。知識(shí)是由學(xué)習(xí)者在試圖理解他們經(jīng)驗(yàn)的意義時(shí)建構(gòu)起來的。在獲取知識(shí)的過程中，學(xué)習(xí)者不是簡單地記憶老師提供的信息，而是建構(gòu)自己對(duì)知識(shí)的理解。建構(gòu)主義強(qiáng)調(diào)理解是學(xué)習(xí)的目標(biāo)，而不是記憶或模仿。理解是一個(gè)復(fù)雜的過程，學(xué)習(xí)者通過與環(huán)境的互動(dòng)、與同伴的交流和主動(dòng)思考來建構(gòu)自己的知識(shí)和意義。學(xué)習(xí)者總是處于學(xué)習(xí)過程的中心，根據(jù)他們先前的經(jīng)驗(yàn)來解釋外部世界。 因此，學(xué)習(xí)者不是被知識(shí)填充的被動(dòng)接受者，而是尋求意義的主動(dòng)有機(jī)體。建構(gòu)主義認(rèn)為學(xué)生應(yīng)該發(fā)展有效利用知識(shí)的能力，而這種能力只有在有意義的活動(dòng)語境中才能實(shí)現(xiàn)。學(xué)生僅僅獲得惰性的概念和常規(guī)是不夠的，因?yàn)楫?dāng)面臨需要解決的問題時(shí)，這些是無法回憶起來的。社會(huì)建構(gòu)主義學(xué)習(xí)理論在一個(gè)促進(jìn)相互增強(qiáng)的循環(huán)過程中將主觀和客觀知識(shí)聯(lián)系起來。 在這個(gè)循環(huán)往復(fù)的過程中，新知識(shí)的形成首先源于個(gè)體對(duì)新知識(shí)的主觀建構(gòu)，即個(gè)體通過自身的創(chuàng)造過程，基于自己的主觀知識(shí)創(chuàng)造新知識(shí)，潛在地有助于客觀知識(shí)的積累。通過個(gè)體主觀建構(gòu)產(chǎn)生的新知識(shí)通過各種媒介（印刷的、手寫的、口語的或電子的）表現(xiàn)出來，由他人基于一定的客觀標(biāo)準(zhǔn)進(jìn)行審視和評(píng)價(jià)，然后被人們重新表述和接受，從而成為客觀知識(shí)。在學(xué)習(xí)過程中，客觀知識(shí)被個(gè)體內(nèi)化和重新建構(gòu)，成為基于獲得意義的個(gè)人主觀知識(shí)[48]。 如果學(xué)生在經(jīng)驗(yàn)豐富的教師的個(gè)別指導(dǎo)下學(xué)習(xí)，教師可以根據(jù)學(xué)生的需求提供線索、參與或?qū)嵺`的機(jī)會(huì)和及時(shí)的強(qiáng)化。在這種情況下，教師和學(xué)生可以隨時(shí)溝通和調(diào)整，有效地向?qū)W生提供反饋和指導(dǎo)。因此，在個(gè)別教學(xué)中，反饋和指導(dǎo)過程以微妙和非正式的方式發(fā)生。但是，在教學(xué)對(duì)象是幾十名學(xué)生的課堂教學(xué)背景下，即使教師使用了最好的線索，提供了最好的參與機(jī)會(huì)和強(qiáng)化，仍然不可能對(duì)所有學(xué)生產(chǎn)生同樣的效果。 這意味著，盡管教師有豐富的經(jīng)驗(yàn)和能力根據(jù)學(xué)生的情況調(diào)整教學(xué)內(nèi)容和過程，但要讓每個(gè)學(xué)生都取得最佳的學(xué)習(xí)成績是極其困難的。因此，一些學(xué)生在學(xué)習(xí)過程中難免會(huì)犯錯(cuò)誤，這就需要教師及時(shí)反饋和指導(dǎo)，幫助他們正確解決問題[49]。 艾賓浩斯遺忘曲線結(jié)合了各種記憶機(jī)制來反映記憶保持的平均下降。記憶類型大致分為短期記憶和長期記憶。在從短期記憶向長期記憶的過渡中，一個(gè)重要因素是訓(xùn)練間隔。實(shí)驗(yàn)表明，持續(xù)的高強(qiáng)度訓(xùn)練不能直接形成長期記憶。只有納入間隔訓(xùn)練才能有效地將短期記憶轉(zhuǎn)化為長期記憶。因此，建立適當(dāng)?shù)姆答侀g隔至關(guān)重要。

2.2.方法定義

算法中探索和利用的概念類似于個(gè)人對(duì)客觀知識(shí)的吸收和主觀建構(gòu)。算法需要平衡探索和利用兩者，以有效地解決問題。與教學(xué)中的反饋類似，算法中探索和利用的動(dòng)態(tài)平衡需要識(shí)別算法的當(dāng)前需求。本文定義反饋結(jié)果Vo用于分析算法的當(dāng)前需求，定義α作為確定如何引導(dǎo)算法的參數(shù)。具體數(shù)值將在下面的“參數(shù)敏感性分析”部分介紹。本文中，經(jīng)驗(yàn)上限（反饋間隔）Cmax。Cmax越大，引導(dǎo)次數(shù)越少，單次引導(dǎo)時(shí)間越長，Cmax越小，引導(dǎo)次數(shù)越多，單次引導(dǎo)時(shí)間越短，C定義為初始經(jīng)驗(yàn)值0，St用于存儲(chǔ)學(xué)習(xí)經(jīng)驗(yàn)，該機(jī)制主要有反饋階段和引導(dǎo)階段兩個(gè)階段。 在反饋階段，會(huì)根據(jù)反饋結(jié)果Vo對(duì)算法進(jìn)行引導(dǎo)。因?yàn)榭梢酝ㄟ^計(jì)算歷史個(gè)體的分散程度（學(xué)習(xí)經(jīng)驗(yàn)）St來判斷算法當(dāng)前的需求，當(dāng)算法的歷史個(gè)體分散時(shí)，認(rèn)為算法在探索，當(dāng)歷史個(gè)體集中時(shí)，則認(rèn)為算法在剝削。并且可以使用均方差計(jì)算分散程度。為了更好地教育學(xué)生，我們將反饋結(jié)果歸一化，以便不同的班級(jí)可以應(yīng)用同一組指標(biāo)。因此，Vo的計(jì)算公式定義如下：

其中??是計(jì)算標(biāo)準(zhǔn)差的函數(shù)，?是學(xué)習(xí)經(jīng)驗(yàn)，存儲(chǔ)歷史中最近的??個(gè)體?，?用于歸一化??以防止其受到上下界變化的影響，?和??分別是問題的上下界。

作者認(rèn)為，通過良好的教學(xué)方法，即使是簡單的指導(dǎo)也能取得良好的結(jié)果，因此將使用兩個(gè)簡單的公式來表示探索和開發(fā)，以指導(dǎo)算法。使用最簡單的表示探索的公式，并對(duì)其進(jìn)行小的修改以生成新位置，如公式 (3)-A 所示。使用最簡單的表示開發(fā)的公式，如公式 (3)-B 所示，通過全局隨機(jī)生成新位置。

其中??是歷史最佳個(gè)體，?是 0 到 1 之間的隨機(jī)數(shù)。

在指導(dǎo)階段，算法將被引導(dǎo)以獲得指導(dǎo)結(jié)果?。當(dāng)檢測(cè)到算法當(dāng)前需要開發(fā)（）時(shí)，將使用公式 (3)-A 來指導(dǎo)算法并利用歷史最佳個(gè)體。當(dāng)檢測(cè)到算法當(dāng)前需要探索（）時(shí)，將使用公式 (3)-B 來指導(dǎo)算法并探索全局空間。

2.3. GLS 操作過程的圖形表示

當(dāng)問題維度?，種群大小?，經(jīng)驗(yàn)上限??時(shí)，策略的操作過程的圖形表示如圖 1、圖 2 所示。在這些圖中，淺藍(lán)色點(diǎn)表示個(gè)體的當(dāng)前位置，淺橙色點(diǎn)表示由 GLS 指導(dǎo)生成的新位置，淺綠色點(diǎn)表示歷史個(gè)體的位置，紅色點(diǎn)表示歷史最佳個(gè)體的位置，橙色箭頭表示有效替換，其中新位置具有更好的適應(yīng)度值并替換原始個(gè)體，藍(lán)色箭頭表示無效替換，其中新位置具有較差的適應(yīng)度值且不替換原始個(gè)體。

圖1 一維問題中GLS的引導(dǎo)開發(fā)過程

圖2 一維問題中GLS的引導(dǎo)探索過程

如圖 1 所示，當(dāng)個(gè)體的位置相對(duì)分散時(shí)，認(rèn)為算法當(dāng)前需要探索。在這種情況下，將使用公式 (3)-A 生成新位置，新生成的位置將相對(duì)集中。如圖 2 所示，當(dāng)個(gè)體的位置相對(duì)集中時(shí)，認(rèn)為算法當(dāng)前需要開發(fā)。在這種情況下，將使用公式 (3)-B 生成新位置，新生成的位置將相對(duì)分散。

當(dāng)問題維度?，種群大小?，經(jīng)驗(yàn)上限??時(shí)，假設(shè)算法在第一維度進(jìn)行探索，在第二維度進(jìn)行開發(fā)。這可以如圖 3 所示表示，GLS 的執(zhí)行結(jié)果如圖 4 所示。在這些圖中，?和??分別表示問題在第一維度的上下界，而??和??表示問題在第二維度的上下界。同一個(gè)體在兩個(gè)維度中的位置由淺藍(lán)色或淺橙色虛線連接。在圖 3 中，第一維度與圖 1 中的情況一致，而第二維度與圖 2 中的情況一致，因此結(jié)果顯然也一致。如圖 4 所示，因?yàn)??和??的適應(yīng)度值更好，?和??將被??和??替換。此時(shí)，個(gè)體位置更加平衡，表明 GLS 可以在算法的不同維度中平衡探索和開發(fā)。執(zhí)行 GLS 后，開發(fā)維度仍然傾向于探索，算法狀態(tài)中沒有突然的強(qiáng)制切換，這更好地防止了 GLS 拖低算法的原始性能并嘗試通過維度擴(kuò)展來提高算法性能。當(dāng)問題維度更高時(shí)，只需通過維度擴(kuò)展來增加維度。

圖3.二維問題中GLS的執(zhí)行過程

圖4 二維問題中GLS執(zhí)行后的個(gè)體位置

2.4. GLS 的偽代碼和流程圖

GLS 的偽代碼可以在算法 1 中看到，流程圖可以在圖 5 中看到。其中，?是當(dāng)前評(píng)估次數(shù)，?是最大評(píng)估次數(shù)。從偽代碼和流程圖中不難看出??主要影響 GLS 的執(zhí)行頻率，較大的??會(huì)降低 GLS 的執(zhí)行頻率。然而，?主要影響 GLS 中指導(dǎo)公式的選擇，較大的??是，越傾向于探索指導(dǎo)。

function?[gbest,gbestval,pop,popf,FES]=GLS(gbest,gbestval,pop,popf,lu,V0,A,fobj,FES,FESmax,i)

?[N,dim]=size(pop);
?which_dim=V0>A;
?pop_new=which_dim.*(gbest+tan(pi.*(rand(N,dim)-0.5)).*(lu(2,:)-lu(1,:))./V0)+...
? ? ?(~which_dim).*(rand(N,dim).*(lu(2,:)-lu(1,:)));
for?i1 =?1?: N
? ? ?pop_new_use=pop_new(i1,:);
? ? ?pop_new_use(pop_new_use>lu(2,:))=rand.*(lu(2,pop_new_use>lu(2,:)) - lu(1,pop_new_use>lu(2,:))) + lu(1,pop_new_use>lu(2,:));
? ? ?pop_new_use(pop_new_use<lu(1,:))=rand.*(lu(2,pop_new_use<lu(1,:)) - lu(1,pop_new_use<lu(1,:))) + lu(1,pop_new_use<lu(1,:));
? ? ?popnew_usef=feval(fobj,pop_new_use);
? ? ?FES = FES +?1;
? ? ?if?(i1<=i?&& popnew_usef < popf(i1) &&?isreal(pop_new_use) && sum(isnan(pop_new_use))==0)
? ? ? ? ?popf(i1) = popnew_usef;
? ? ? ? ?pop(i1, :) = pop_new_use;
? ? ?end
? ? ?if?(popnew_usef < gbestval &&?isreal(pop_new_use) && sum(isnan(pop_new_use))==0)
? ? ? ? ?gbestval = popnew_usef;
? ? ? ? ?gbest = pop_new_use;
? ? ?end
? ? ?if?FES >= FESmax
? ? ? ? ?return
? ? ?end
end

end

圖5 引導(dǎo)學(xué)習(xí)策略（GLS）框架的流程圖