采用動態知識因子的基于知識共享的優化算法 *

袁 磊，王 勇，2，趙艷玲

（1.廣西民族大學 人工智能學院，廣西 南寧 530006；2.廣西混雜計算與集成電路設計分析重點實驗室，廣西 南寧 530006）

0 引言

元啟發式算法在科學和工程等領域得到廣泛的應用，其優越性也得到界內研究者的廣泛認可，因而自20世紀70年代Holland提出遺傳算法（GA）［1］以來，元啟發式算法的研究越來越受到國內外研究者的重視。目前在國內外刊物或國際會議上發表的有關元啟發式算法研究成果大體上可分為兩類：一是原創性提出新算法（如粒子群算法（PSO）［2］，蝗蟲優化算法（GOA）［3］，鯨魚算法（WOA）［4］，黑猩猩優化算法（COA）［5］，社會模擬算法樣式（SMO）［6］、教學優化算法（TLBO）［7］，算數優化算法（AOA）［8］、哈里斯鷹優化算法（HHO）［9］，知識共享算法（GSK）［10］等）；一是修改或完善現有算法或混合各種算法（如文獻［11-14］等）。由于包括文獻［1-10］在內的這些新算法通常存在全局收斂速度慢、易陷入局部最優等不足，因而需要人們去完善這些現有算法，以改善其優化性能。

基于知識共享的優化算法（Gaining-sharing knowledge based algorithm for solving optimization problems， GSK）［10］是由Mohamed等人從人類獲取和共享知識過程中得到啟發，于2019年提出的一種新的群智能優化算法。GSK具有算法模型簡單易懂、易于編程實現等優點。然而，GSK存在全局搜索能力不強、收斂速度慢、易陷入局部極值等不足，仍有待進一步完善。針對GSK之不足，Mohamed等人［11］提出改進版本的GSK，稱之為APGSK，該APGSK用自適應概率參數來控制知識比率，以平衡全局探索與局部開發。然而從文獻［11］給出的具體實例實驗與仿真結果上看，APGSK的收斂速度相對較慢、優化精度也不高。Zhong等人［12］提出將GSK與HHO相結合的混合差分進化算法，稱之為DEGH。該算法首先構建一個混合變異算子，用于平衡全局探索和局部開發；其次利用交叉概率自適應來加強差分變異、交叉和選擇之間的聯系。然而從文獻［12］列出的具體實例實驗結果上看，該算法的全局搜索能力不強、收斂速度較慢、優化精度不高。Xiong等人［13］只是將GSK應用于求解決太陽能光伏模型參數提取問題，并沒對GSK進行改進。綜合以上分析，文獻［11］和［12］提出的改進版本GSK在優化精度方面比標準GSK有所提高，但提升的程度非常有限，仍存在較明顯的全局搜索能力不強、收斂速度較慢、易陷入局部最優等問題，仍有待進一步完善。針對這一問題，本文對GSK進行改進，提出采用動態知識因子的基于知識共享的優化算法（Gaining-sharing knowledge based algorithm Using Dynamic Knowledge-factor，DKGSK），并通過具體實例仿真來驗證本文提出改進策略的有效性和可行性。

1 GSK簡介

基于知識共享的優化算法（GSK）將人類知識的獲取分為初級（junior）和高級（senior）兩個階段：第一階段稱為初級獲取與分享階段；第二階段稱為高級獲取與分享階段。GSK算法把每個人（一生中）在中前期（幼年期或早期）、中后期（成年期）獲得知識的階段分別稱為初級階段和高級階段。GSK算法模型如下：

設N為特定人群總人數（種群規模），D是人可獲取知識的學科領域數（表示人的知識全部從D個學科獲取，表征搜索空間維數是D），以xij表示第i人從第j學科中獲取知識，以xi=(xi1，xi2，…，xiD)表示第i人的知識維度，f(xi)為其適應度值，i=1，…，N。

1.1 確定使用初級獲取與分享知識的維度數

搜索開始時，首先計算第i人xi使用初級方案（初級獲取）更新的維度數，從而也就確定了使用高級方案（高級獲取）的維數。具體方法如下：設t時刻第i人的位置為xi(t)=(xi1(t)，…，xiD(t))，則由公式（1）計算：

其中：k稱為知識率，是大于0的實數（GSK在數值實驗中取k=10），Tmax為最大迭代次數，t為當前迭代次數。記Djun為不超過D(juniorphase)的最大正整數。則在t+1時刻，xi(t)=(xi1(t)，…，xiD(t))的前Djun個維按初級獲取知識方案進行更新，后Dsen個維則按高級獲取知識方案進行更新，其中：

1.2 不同階段知識獲取與分享方法

記xi(t)為第i人于t時刻的位置（i=1，…，N），f(xi)為其適應度值。根據適應度值將人群按升序排列：xbest(t)，…，xi-1(t)，xi(t)，xi+1(t)，…，xworst(t)，并且從[0，1]中取一個隨機數rand：

針對初級獲取與分享階段，首先給定kf（知識因子）和kr（知識比率），其中kf>0，0

若rand≤kr，則xi(t)的前Djun個維均按公式（3）更新知識：

否則（即rand>kr時）不更新，i=1，…，N，j=1，…，Djun。即xi(t)的前Djun個維均采用初級獲取知識方案更新知識。其中：xi-1(t)和xi+1(t)分別是比xi(t)更好和更差的兩個“人”，作為xi(t)獲取知識的來源，再從群體中隨機選擇另一個“人”xr(t)作為知識共享的來源。注：若xi(t)為當前最優個體，則以xbest+1(t)和xbest+2(t)作為其獲取知識的來源；若xi(t)為當前最差個體，則以xworst-1(t)和xworst-2(t)作為其獲取知識的來源。

針對高級獲取與分享階段，首先將種群分為最好人群（人數為p?N）、中等人群（人數為(1-2p)?N）、最差人群（人數為p?N）三個群體（GSK在數值實驗中取p=0.1）。然后每個“人”使用如下方案更新知識：

若rand≤kr，則xi(t)按公式（4）更新知識：

否則（即rand>kr時）不更新。i=1，…，N，j=Djun+1，…，D。其中xp-best(t)、xm(t)和xp-worst(t)為分別從最好人群、中等人群、最差人群中隨機選擇的一個個體。

GSK實現步驟如下：

Step1：給定目標函數f(x)，種群規模N，搜索空間維數D，最大迭代次數Tmax，知識率k，知識因子kf，知識比率kr，種群最好人群比例p。

Step2：初始化種群xi(t)，評估每一個體的適應度值f(xi(t))，i=1，…，N。

Step3：根據適應度值將種群按升序排列：xbest(t)，…，xi-1(t)，xi(t)，xi+1(t)，…，xworst(t)。

Step4：利用公式（1）和（2）確定Djun和Dsen=D-Djun。

Step5：從[0，1]中取一個隨機數rand，若rand≤kr，則xi(t)的前Djun維度均采用公式（3）更新知識，后DDjun維度均采用公式（4）更新知識；否則不更新。

Step6：評估每一個體的適應度值f(xi(t))，i=1，…，N。

Step7：判斷是否滿足終止條件：若滿足則轉Step8；否則轉Step3。

Step8：算法終止，并根據適應度值將最優位置作為優化問題的最優解。

2 本文算法

分析標準GSK算法模型：不管是在初級階段還是在高級階段，搜索個體的前Djun個維均按公式（3）更新位置、后D-Djun個維則均按公式（4）更新位置。顯然，GSK的公式（3）和（4）中，每個維更新位置時，其步長均由知識因子kf確定，然而kf是給定的常數（GSK在數值實驗中取kf=0.5），因此，GSK種群中個體每個維的搜索步長是固定的，也就是說，GSK種群中的每一個體在搜索空間中均采用“同一時刻步長完全相同、同步跳躍”的搜索策略。這使得種群個體搜索明顯缺乏隨機性和靈活性，限制了個體的搜索靈活性和自主性，降低了個體的搜索能力和效率，造成算法搜索效率低下，最終導致GSK的全局搜索能力不強、全局收斂速度較慢、優化精度不高之不足。針對GSK存在的問題，本文提出相應的改進策略，詳述如下：

2.1 針對GSK公式(3)之不足，本文對其作如下改進

i=1，…，N，j=1，…，Djun。其中r為［0，1］中的隨機數。

2.2 針對GSK的公式(4),作如下改進

i=1，…，N，j=Djun+1，…，D。其中w=(1-t/Tmax)4，L(λ)為列維飛行［14］：

公式（5）中的r?kf和公式（6）中的L(λ)?kf均是隨機可變的， 而標準GSK的知識因子kf是固定的。因此，本文將r?kf和L(λ)?kf統稱為動態知識因子（本文算法在數值實驗中取kf=1.8）。

說明：a）公式（5）和（6）中的w?xi，j(t)表示：個體i對知識的吸取具有習慣性，并保持其這一習慣性趨勢。w=(1-t/Tmax)4是一個關于算法搜索時間t的單調遞減函數，當t=1時，w=(1-1/Tmax)4≈1（本文算法置Tmax=300），t=300時，w=0 。換言之，w從算法搜索前期到后期逐步從1單調遞減到0；w在算法前期的值相對較大，從而加快了個體的搜索速度，使群體能以較快速度遍歷整個空間。這有利于算法進行全局探索、可為后期開展局部搜索盡可能多地積累和反饋信息；w在算法后期下降較慢，并隨著搜索時間t的增加而趨于0。因而在w的作用下，可提升個體的局部搜索精度，進而增強算法的局部開發能力。b）公式（5）表示：個體i是由向量w?xi，j(t)與向量rkf×Δ 根據平行四邊形法則來控制其搜索的，其中Δ=[(xi-1，j(t)-xi+1，j(t))+(xr，j(t)-xi，j(t))]或[(xi-1，j(t)-xi+1，j(t))+ (xi，j(t)-xr，j(t))]。而r為［0，1］中的隨機數，因而個體i可以在由第一部分w?xi，j(t)與第二部分rkf×Δ 所確定的平行四邊形覆蓋的范圍內開展精細化搜索，其搜索步長具有隨機性和靈活性，這使其全局探索與局部開發能力均得到了提升。c）公式（6）表示：個體i是利用w?xi，j(t)與L(λ)×Ω 來控制 其 搜 索 的，其 中Ω=kf?[(xp-best，j(t)-xp-worst，j(t))+(xm，j(t)-xi，j(t))]或kf?[(xp-best，j(t)-xp-worst，j(t))+(xi，j(t)-xm，j(t))]。由于列維飛行L(λ)具有隨機行走特性和行走步長呈現重尾的分布特征，故采用這一方法來控制個體搜索可使搜索步長更具靈活性和隨機性，當搜索個體陷入局部最優位置時，利用列維飛行能以較大概率實現大跨步跳出當前最優位置，進而可提升算法跳出局部最優的能力、增強算法的局部開發能力。d）到算法后期，w幾乎為0，故個體i在算法后期主要由rkf×Δ或L(λ)×Ω控制，即其主要是從比其更優的個體中吸取知識，亦即在后期側重開展局部搜索，進而增強了群體的局部搜索能力。

本文算法已對標準GSK中的“Step5：從[0，1] 中取一個隨機數rand，若rand≤kr，則xi(t)的前Djun維度均采用公式（3）更新知識，后D-Djun維度均采用公式（4）更新知識；否則不更新”進行了修改，去掉其中的“從[0，1] 中取一個隨機數rand，若rand≤kr”條件，進一步簡化了算法實現條件。

2.3 算法實現步驟

本文算法（DKGSK）實現步驟如下：

Step1：給定目標函數f(x)，種群規模N，搜索空間維度D，最大迭代次數Tmax，知識率k，知識因子kf，種群最好人群比例p（本文算法在實驗中取kf=1.8，k=10，p=0.1）。

Step2：初始化種群xi(t)，并評估適應度值f(xi(t))，i=1，…，N。

Step3：根據適應度值將種群按升序排列：xbest(t)，…，xi-1(t)，xi(t)，xi+1(t)，…，xworst(t)。

Step4：由公式（1）和（2）確定Djun和Dsen=D-Djun。

Step5：xi(t)分別根據公式（5）和（6）更新其前Djun個維和后D-Djun個維。

Step6：評估每一個體的適應度值f(xi(t))，i=1，…，N。

Step7：判斷是否滿足終止條件：若滿足則轉Step8；否則轉Step3。

Step8：算法終止，并根據適應度值將最優位置作為優化問題的最優解。

2.4 算法時間復雜度分析

設最大迭代次數是T，種群規模是N，探索空間維數是D。初始化種群的時間復雜度是O(N)，計算初級階段維數的時間復雜度是O(T)，排序時間復雜度是O(N(N-1)T/2)，因而標準GSK的時間復雜度是O(N(N-1)T/2)+O(NDT)+O(N)+O(T)。在AGSK中，引入自適應權重與列維飛行的時間復雜度為O(NT)，故DKGSK的時間復雜度是O(N(N-1)T/2)+O(NDT)+O(NT)+O(N)+O(T)，若略去時間復雜度之低次項，則兩種算法的計算時間復雜度是一致的。

3 數值實驗

為 了 測 試 本 文 算 法（DKGSK）的 性 能，本 文 將DKGSK與 標 準GSK［10］、PSO［2］、WOA［4］、APGSK［11］、DEGH［12］作算法性能對比分析，以驗證本文算法（DKGSK）的優化性能。

3.1 測試函數

本文選取12個已被廣泛用來測試算法優化性能的基準測試函數（具體見表1），作為算法數值實驗與優化性能對比分析的測試實例，這些基準測試函數當中包含5個單峰函數和7個多峰函數。其中：單峰函數主要用來測試算法的收斂速度，多峰函數則用來測試算法的全局搜索能力和規避陷入局部最優的能力。

表1 基準測試函數

3.2 實驗參數設置

為了數值實驗測試結果的公平性，本文實驗針對六種對比算法均統一設置種群規模為100、最大迭代次數為300。對于GSK［10］、PSO［2］、WOA［4］、APGSK［11］、DEGH［12］這五種算法的其余參數，均與相對應的文獻［10］、［2］、［4］、［11］、［12］的設置一致。

3.3 實驗結果分析

為了盡可能避免隨機性對數值實驗結果的影響，本文在做數值實驗測試時，六種算法針對每一個測試問題都獨立進行30次實驗，并將運行結果（最優值、平均值、標準差）記錄下來。這些評價指標總體上反應了算法優化能力的強弱以及算法穩定性的好壞。其中：“最優值”評價指標反映了算法的全局搜索能力和優化精度，“平均值、標準差”評價指標能夠反映算法的穩定性能。本文針對30維和200維搜索空間分別做數值實驗，得到的實驗結果見表2。

為了便于觀察和比較六種算法各自的收斂速度，本文也給出了六種算法分別求解這12個基準測試函數時得到的適應度進化曲線圖，具體如圖1所示。

本文根據實驗數據表2和進化曲線圖1來分析這六種對比算法各自的優化性能。

從“最優值”上看：本文算法（DKGSK）找到F1～F5，F7～F12這11個測試函數的理論最優值；WOA只找到F8和F9這兩個函數的理論最優值；其余的四種算法均沒有找到這12個測試函數的理論最優值。六種對比算法都沒有找到F6的理論最優值，但本文算法（DKGSK）找到F6的最優值均比其他五種算法更接近理論最優值，且優化精度均比其他五種算法至少高2個數量級。這說明在六種對比算法當中，本文算法（DKGSK）的全局搜索能力最強、優化精度最高、比其他五種對比算法明顯具有較大的優勢。

從“平均值”和“標準差”上看：本文算法（DKGSK）求解F1～F5，F7～F12這11個測試函數時得到的“平均值、標準差”均與理論最優值相同；WOA求解F8和F9得到的“平均值、標準差”與理論最優值相同，而求解其余10個函數得到的“平均值、標準差”均與理論最優值有偏差；其余四種算法求解這12個測試函數時得到的“平均值、標準差”均與理論最優值有偏差。DKGSK求解F6時得到的“平均值、標準差”與理論最優值有點偏差，但偏差量比較小（小于10-4），且偏差的程度均比其他五種算法的小。這說明本文算法找到全局最優值的概率明顯高于其余五種對比算法，算法的穩定性均好于其他五種對比算法；這對DKGSK用于求解工程等方面的優化問題提供了技術可靠性。

從圖1的（a）~（l）上看：相較于其他五種對比算法，本文算法（DKGSK）的進化曲線均位于對比算法的進化曲線當中之最底下、下降的速度是最快的。本文算法求解F1～F5、F7～F12這11個測試函數時得到的進化曲線均到達理論最優位置；WOA只有求解F8和F9時得到的進化曲線能到達理論最優位置，其余的10個測試函數的進化曲線均沒能到達理論最優位置；另外四種算法（GSK，PSO，APGSK，DEGH）求解這12個測試函數得到的進化曲線均沒能到達理論最優位置。這說明了本文算法的收斂速度最快、優化精度最高。

圖1 函數收斂圖

為了進一步測試這六種對比算法各自的優化性能，本文再用六種算法分別求解表1中的12個函數當D=200時的優化表現，以考查六種算法的魯棒性問題。具體得到的實驗結果均列在表2中。

基于表2的實驗數據進一步分析六種對比算法各自的性能。

表2 30/200維基準測試函數測試結果對比

本文算法（DKGSK）找到F1～F5，F7～F12這11個函數的“最優值、平均值、標準差”都是函數理論最優值；WOA只找到F8和F9這兩個函數的“最優值、平均值、標準差”是函數理論最優值；其余的四種算法找到這12個測試函數的“最優值、平均值、標準差”都不是函數理論最優值，與理論最優值有偏差。本文算法找到F6的“最優值4.383E-06”非常接近理論最優值0，比D=30時找到的最優值9.906E-06還要好，找到的“平均值2.436E-05，標準差2.350E-05”也非常接近理論最優值，與D=30時找到的“平均值3.4565E-05，標準差2.057E-05”相當。本文算法找到F6的“最優值、平均值、標準差”都比其他五種對比算法更接近理論最優值，優化精度都比其他五種算法至少高2個數量級。標準GSK、DEGH、APGSK、PSO求解這12個函數時找到的“最優值”出現了明顯地偏離理論最優值的“失靈”現象，且偏離還比較大。基于以上分析，說明了將搜索空間維度從30增加到200時，本文算法（DKGSK）的全局搜索能力并沒有減弱、優化精度并沒有下降、算法穩定性也沒有下降，沒有出現隨著搜索空間維度的增加而出現“失靈”的現象。這進一步說明了本文算法的穩定性和魯棒性比較好，規避陷入局部最優的能力比較強。

3.4 DKGSK主要參數確定方法

記p=最好人群/群體規模N。為了研究p之不同值對DKGSK優化性能的影響，本文針對p=0.1，0.2，0.3，0.4分別做數值實驗。表1中的F6是一個具有多極小點但只有一個全局最小點(0，…，0)的多峰函數，由于受random[0，1)的擾動，要找到其全局最小點相對較難，故尋找F6的最小點是較能考驗算法的全局探索和局部開發能力的。因此，本文就以F6作為確定p值之測試函數。實驗種群規模為100，最大迭代次數300，D=30。針對p之不同值，均獨立運行30次，考查p取不同值時算法穩定性的變化情況。利用繪制箱線圖來反映30次運行結果，可容易觀察到多組連續型定量數據分布的中心位置和散布范圍。當p取不同值時，DKGSK 的中位數線均靠近全局最小位置，且大部分數據都接近理論最優位置。這說明DKGSK具有較強的全局尋優能力、較強的跳出局部最優能力和較好的優化精度，采用的改進策略是有效和可行的。從箱線圖的高度上看，p取4個不同值時，大部分數據點都沒有嚴重偏離理論最優位置。從偏離理論最優位置上看，當p=0.1時，沒有出現偏離理論最優位置的數據點，而p取其余3個值時，均出現偏離理論最優位置的數據點。因此，本文算法（DKGSK）在數值實驗中取p=0.1。

其次，為了研究知識因子kf之不同值對DKGSK 優化性能的影響，本文針對kf= 0.5，1，1.2，1.5，1.8 分別做實驗。實驗設置種群規模為100，最大迭代次數為150，D=30。從實驗結果上看：DKGSK求解F1～F5和F7～F12在kf=1.8時的表現最好、求解F6在kf=1.5時的表現比較好。因此，本文算法（DKGSK）在實驗中取kf=1.8。

3.5 Wilcoxon秩和檢驗

為進一步驗證本文算法（DKGSK）的尋優性能，將DKGSK分別與GSK，DEGH，APGSK，PSO，WOA算法進行Wilcoxon秩和檢驗。在顯著性水平為0.05的條件下檢驗算法之間的顯著差異性，其中p表示檢驗的數值，若p值小于0.05，則表明算法之間的尋優結果存在顯著性差異，否則無明顯差異。N表示數據無效即檢驗的所有樣本數據相同，算法不具有顯著差異性。從測試數據可以看出，p值小于0.05的占絕大多數。因此，DKGSK與其他五種對比算法具有非常顯著的差異性，并且DKGSK的全局優化能力最強。

4 結論

針對標準GSK之不足，本文提出采用動態知識因子的基于知識共享的優化算法（DKGSK）。首先，利用單調遞減自適應權重函數來控制個體的移動步長，使個體在算法前期能以較大步長在搜索空間中進行全局探索活動，讓種群個體盡快遍歷整個搜索空間，增強了算法的全局探索能力，為算法后期的局部搜索活動提供了更多有用的信息；個體在算法后期以較小步長開展局部搜索活動，提升了個體的局部搜索能力，增強了算法的局部優化能力，從而使算法的全局探索和局部開發能力均得到提升。其次，利用動態知識因子來調控個體搜索，針對初級獲取階段和高級獲取階段，分別通過0至1之間的均勻隨機函數和列維飛行函數來調控個體搜索，使個體搜索步長更具隨機性，提升了個體搜索能力，從而增強了算法的局部開發能力。此外，當個體搜索陷入局部最優時，借助列維飛行可使其跳出當前最優位置，從而使算法跳出局部最優的能力得到提升。通過與標準GSK和改進版本GSK作數值實驗與仿真結果比較，驗證了本文算法在全局收斂速度、優化精度、算法穩定性方面均得到了明顯的提高，規避陷入局部最優的能力得到了增強。后續研究將重點考慮將本文算法應用于數據分類、工程優化設計等方面的應用中。