芯耀
377
1.簡介
元啟發(fā)式算法（MH）是自然啟發(fā)的全局優(yōu)化算法，往往比較簡單，可以在短時間內(nèi)解決問題，具有一定的好處。但是，隨著問題變得更加復(fù)雜，算法所能獲得的解往往不是問題的最優(yōu)解，這就限制了其應(yīng)用場景。因此，提高現(xiàn)有算法的性能和求解精度對于擴展其應(yīng)用能力至關(guān)重要。在傳統(tǒng)優(yōu)化算法中，往往有兩個概念，即探索和利用。探索是指大范圍的離散搜索，用于避免陷入局部最優(yōu)，而利用是指小范圍的集中探索，用于提高算法精度。 如何平衡探索與利用是增強算法性能和問題適應(yīng)性的關(guān)鍵。本文提出了一種全新的策略，命名為引導(dǎo)學(xué)習(xí)策略（GLS）來解決上述問題。GLS通過計算近幾代個體歷史位置的均方差來獲得種群的分散程度，并推斷出算法當(dāng)前需要什么指導(dǎo)。當(dāng)算法偏向于探索時，就會引導(dǎo)算法去探索。反之，就會引導(dǎo)算法去探索。正是因為這種策略能夠識別算法當(dāng)前的需求并提供輔助，才能提高大多數(shù)算法的性能。
2.提出的GLS
2.1 GLS的設(shè)計靈感
在建構(gòu)主義學(xué)習(xí)理論中，假設(shè)知識是建構(gòu)起來的。知識是由學(xué)習(xí)者在試圖理解他們經(jīng)驗的意義時建構(gòu)起來的。在獲取知識的過程中，學(xué)習(xí)者不是簡單地記憶老師提供的信息，而是建構(gòu)自己對知識的理解。建構(gòu)主義強調(diào)理解是學(xué)習(xí)的目標(biāo)，而不是記憶或模仿。理解是一個復(fù)雜的過程，學(xué)習(xí)者通過與環(huán)境的互動、與同伴的交流和主動思考來建構(gòu)自己的知識和意義。學(xué)習(xí)者總是處于學(xué)習(xí)過程的中心，根據(jù)他們先前的經(jīng)驗來解釋外部世界。 因此，學(xué)習(xí)者不是被知識填充的被動接受者，而是尋求意義的主動有機體。建構(gòu)主義認(rèn)為學(xué)生應(yīng)該發(fā)展有效利用知識的能力，而這種能力只有在有意義的活動語境中才能實現(xiàn)。學(xué)生僅僅獲得惰性的概念和常規(guī)是不夠的，因為當(dāng)面臨需要解決的問題時，這些是無法回憶起來的。社會建構(gòu)主義學(xué)習(xí)理論在一個促進相互增強的循環(huán)過程中將主觀和客觀知識聯(lián)系起來。 在這個循環(huán)往復(fù)的過程中，新知識的形成首先源于個體對新知識的主觀建構(gòu)，即個體通過自身的創(chuàng)造過程，基于自己的主觀知識創(chuàng)造新知識，潛在地有助于客觀知識的積累。通過個體主觀建構(gòu)產(chǎn)生的新知識通過各種媒介（印刷的、手寫的、口語的或電子的）表現(xiàn)出來，由他人基于一定的客觀標(biāo)準(zhǔn)進行審視和評價，然后被人們重新表述和接受，從而成為客觀知識。在學(xué)習(xí)過程中，客觀知識被個體內(nèi)化和重新建構(gòu)，成為基于獲得意義的個人主觀知識[48]。 如果學(xué)生在經(jīng)驗豐富的教師的個別指導(dǎo)下學(xué)習(xí)，教師可以根據(jù)學(xué)生的需求提供線索、參與或?qū)嵺`的機會和及時的強化。在這種情況下，教師和學(xué)生可以隨時溝通和調(diào)整，有效地向?qū)W生提供反饋和指導(dǎo)。因此，在個別教學(xué)中，反饋和指導(dǎo)過程以微妙和非正式的方式發(fā)生。但是，在教學(xué)對象是幾十名學(xué)生的課堂教學(xué)背景下，即使教師使用了最好的線索，提供了最好的參與機會和強化，仍然不可能對所有學(xué)生產(chǎn)生同樣的效果。 這意味著，盡管教師有豐富的經(jīng)驗和能力根據(jù)學(xué)生的情況調(diào)整教學(xué)內(nèi)容和過程，但要讓每個學(xué)生都取得最佳的學(xué)習(xí)成績是極其困難的。因此，一些學(xué)生在學(xué)習(xí)過程中難免會犯錯誤，這就需要教師及時反饋和指導(dǎo)，幫助他們正確解決問題[49]。 艾賓浩斯遺忘曲線結(jié)合了各種記憶機制來反映記憶保持的平均下降。記憶類型大致分為短期記憶和長期記憶。在從短期記憶向長期記憶的過渡中，一個重要因素是訓(xùn)練間隔。實驗表明，持續(xù)的高強度訓(xùn)練不能直接形成長期記憶。只有納入間隔訓(xùn)練才能有效地將短期記憶轉(zhuǎn)化為長期記憶。因此，建立適當(dāng)?shù)姆答侀g隔至關(guān)重要。
2.2.方法定義
算法中探索和利用的概念類似于個人對客觀知識的吸收和主觀建構(gòu)。算法需要平衡探索和利用兩者，以有效地解決問題。與教學(xué)中的反饋類似，算法中探索和利用的動態(tài)平衡需要識別算法的當(dāng)前需求。本文定義反饋結(jié)果Vo用于分析算法的當(dāng)前需求，定義α作為確定如何引導(dǎo)算法的參數(shù)。具體數(shù)值將在下面的“參數(shù)敏感性分析”部分介紹。本文中，經(jīng)驗上限（反饋間隔）Cmax。Cmax越大，引導(dǎo)次數(shù)越少，單次引導(dǎo)時間越長，Cmax越小，引導(dǎo)次數(shù)越多，單次引導(dǎo)時間越短，C定義為初始經(jīng)驗值0，St用于存儲學(xué)習(xí)經(jīng)驗，該機制主要有反饋階段和引導(dǎo)階段兩個階段。 在反饋階段，會根據(jù)反饋結(jié)果Vo對算法進行引導(dǎo)。因為可以通過計算歷史個體的分散程度（學(xué)習(xí)經(jīng)驗）St來判斷算法當(dāng)前的需求，當(dāng)算法的歷史個體分散時，認(rèn)為算法在探索，當(dāng)歷史個體集中時，則認(rèn)為算法在剝削。并且可以使用均方差計算分散程度。為了更好地教育學(xué)生，我們將反饋結(jié)果歸一化，以便不同的班級可以應(yīng)用同一組指標(biāo)。因此，Vo的計算公式定義如下：
其中??是計算標(biāo)準(zhǔn)差的函數(shù)，?是學(xué)習(xí)經(jīng)驗，存儲歷史中最近的??個體?，?用于歸一化??以防止其受到上下界變化的影響，?和??分別是問題的上下界。
作者認(rèn)為，通過良好的教學(xué)方法，即使是簡單的指導(dǎo)也能取得良好的結(jié)果，因此將使用兩個簡單的公式來表示探索和開發(fā)，以指導(dǎo)算法。使用最簡單的表示探索的公式，并對其進行小的修改以生成新位置，如公式 (3)-A 所示。使用最簡單的表示開發(fā)的公式，如公式 (3)-B 所示，通過全局隨機生成新位置。
其中??是歷史最佳個體，?是 0 到 1 之間的隨機數(shù)。
在指導(dǎo)階段，算法將被引導(dǎo)以獲得指導(dǎo)結(jié)果?。當(dāng)檢測到算法當(dāng)前需要開發(fā)（）時，將使用公式 (3)-A 來指導(dǎo)算法并利用歷史最佳個體。當(dāng)檢測到算法當(dāng)前需要探索（）時，將使用公式 (3)-B 來指導(dǎo)算法并探索全局空間。
2.3. GLS 操作過程的圖形表示
當(dāng)問題維度?，種群大小?，經(jīng)驗上限??時，策略的操作過程的圖形表示如圖 1、圖 2 所示。在這些圖中，淺藍(lán)色點表示個體的當(dāng)前位置，淺橙色點表示由 GLS 指導(dǎo)生成的新位置，淺綠色點表示歷史個體的位置，紅色點表示歷史最佳個體的位置，橙色箭頭表示有效替換，其中新位置具有更好的適應(yīng)度值并替換原始個體，藍(lán)色箭頭表示無效替換，其中新位置具有較差的適應(yīng)度值且不替換原始個體。
圖1 一維問題中GLS的引導(dǎo)開發(fā)過程
圖2 一維問題中GLS的引導(dǎo)探索過程
如圖 1 所示，當(dāng)個體的位置相對分散時，認(rèn)為算法當(dāng)前需要探索。在這種情況下，將使用公式 (3)-A 生成新位置，新生成的位置將相對集中。如圖 2 所示，當(dāng)個體的位置相對集中時，認(rèn)為算法當(dāng)前需要開發(fā)。在這種情況下，將使用公式 (3)-B 生成新位置，新生成的位置將相對分散。
當(dāng)問題維度?，種群大小?，經(jīng)驗上限??時，假設(shè)算法在第一維度進行探索，在第二維度進行開發(fā)。這可以如圖 3 所示表示，GLS 的執(zhí)行結(jié)果如圖 4 所示。在這些圖中，?和??分別表示問題在第一維度的上下界，而??和??表示問題在第二維度的上下界。同一個體在兩個維度中的位置由淺藍(lán)色或淺橙色虛線連接。在圖 3 中，第一維度與圖 1 中的情況一致，而第二維度與圖 2 中的情況一致，因此結(jié)果顯然也一致。如圖 4 所示，因為??和??的適應(yīng)度值更好，?和??將被??和??替換。此時，個體位置更加平衡，表明 GLS 可以在算法的不同維度中平衡探索和開發(fā)。執(zhí)行 GLS 后，開發(fā)維度仍然傾向于探索，算法狀態(tài)中沒有突然的強制切換，這更好地防止了 GLS 拖低算法的原始性能并嘗試通過維度擴展來提高算法性能。當(dāng)問題維度更高時，只需通過維度擴展來增加維度。
圖3.二維問題中GLS的執(zhí)行過程
圖4 二維問題中GLS執(zhí)行后的個體位置
2.4. GLS 的偽代碼和流程圖
GLS 的偽代碼可以在算法 1 中看到，流程圖可以在圖 5 中看到。其中，?是當(dāng)前評估次數(shù)，?是最大評估次數(shù)。從偽代碼和流程圖中不難看出??主要影響 GLS 的執(zhí)行頻率，較大的??會降低 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）框架的流程圖
