求解高維函數的果蠅免疫協同優化算法?

張曉茹 王 丹 周錦程

（1.黔南民族醫學高等專科學校 都勻 558000）（2.黔南民族師范學院數學與統計學院 都勻 558000）（3.黔南民族師范學院復雜系統與智能優化實驗室 都勻 558000）（4.黔南民族師范學院計算機與信息學院 都勻 558000）

1 引言

伴隨經濟的高速發展，優化問題不斷涌現，群體智能算法隨之而生并獲得廣泛應用［1～3］。2011年，Pan 教授［4］從果蠅嗅覺、視覺特征出發，提出果蠅優化算法（fruit fly optimization algorithm，FOA），因其諸多優點［5］而成為各領域的研究焦點。該算法在收斂效率等方面卻不甚理想，致使改進型的果蠅算法［6～9］涌現，旨在增強算法前期全局與后期局部的搜索能力，以提高算法的優化效果和效率。但是，大多改進工作主要是對基本FOA 算法缺陷的修補。而昆蟲學表明［10～15］，果蠅僅憑借先天性的三重免疫防線即可高效抵御病原物質的入侵，此為算法設計的靈感來源。而著眼于果蠅自身簡單又高效的免疫機制，探究關于果蠅免疫算法的工作較為稀缺［16］。故本文從果蠅先天免疫系統應答模式出發，繼續探討求解高維函數的果蠅免疫協同優化算法（Cooperative Fruit-fly immune optimization algorithm，CFIOA）。

本文的創新點在于充分模擬果蠅先天防御機制的黑化作用、細胞免疫及體液免疫之間的協同應答模式，提出果蠅先天性免疫理論模型及果蠅免疫協同優化算法。

2 免疫理論及算法描述

2.1 果蠅先天性免疫理論模型

果蠅僅有先天性免疫機制，缺少T 細胞、B 細胞、抗體及補體，而作為傳播細菌等的載體，卻能保障自身安全，主要依靠其三種協同應答的先天性免疫機制［10～15］。黑化作用作為第一道防線，是抵御病原微生物最直接的免疫反應。當果蠅表皮受損時，將誘導蛋白酶水解，產生凝血及黑化作用，進一步促進傷口的愈合，抑制微生物的繁殖［10］。細胞免疫主要包括吞噬、黑化和包裹作用，以達到清除病原的目的，其中吞噬是最主要的免疫方式［12］。Toll 信號通路和Imd 信號通路構成主要的體液免疫，不同果蠅機體被傳染，將激活相應的Toll或Imd，產生與之對應的抗菌肽，分泌到血淋巴中，以清除入侵病原體等［10］。

實際上，果蠅的三種先天性應答機制不是獨立工作，卻是相互影響、協同作用的。體現在：1）體液免疫對血細胞的功能有一定程度的影響，另外黑化作用中又需要晶細胞；2）Toll 信號通路一定程度上促進體液免疫、細胞免疫的相互作用［11］，并且它的激活又是這兩種應答協同免疫的結果；3）黑化作用一方面可以促進傷口的愈合，另一方面又與吞噬作用、包裹作用相關聯［13］。綜上，獲得果蠅先天性免疫理論模型，如圖1。

圖1 果蠅先天性免疫理論模型

2.2 算法描述

求解如下問題（P）：

其中，D為有界的閉區域，維數n≤1000；f(x)為優化的目標函數，候選解x?D，x=(x1,x2,…,xn)。由函數最值定理知，問題（P）必有最優解。

模擬上述果蠅理論模型，獲得CFIOA的算法流程圖，見圖2。此算法由內、外兩個循環構成，其中內循環主要模擬清除入侵微生物的免疫過程，對同一種群中的個體同步執行進化、個體數量遞減的操作，以高效尋求各子群的優質個體；外循環負責動態更新所獲的最優個體，以高效獲取群體最優。為方便算法描述，將果蠅個體視為問題候選解，外來有機體對應于求解問題（P）的最優解。結合圖1 和圖2，具體算法如下。

圖2 CFIOA流程圖

步驟1 參數設置：種群總規模記N，最大外循環、內循環的迭代數依次記Gout、Gin，選擇率參數ω，α,β,δ；

步驟2 置外循環數t←1。生成N個隨機個體，即初始種群P(1)，計算個體距離并歸一化。記第t代種群為P(t)，其最優個體記xbest；

步驟3 模擬黑化作用：依據閾值α除去P中較弱個體，剩余個體則成種群P*；

步驟4 置內循環數m←1。種群劃分：隨機選取P*中w(1-α)N個體組成A 群；依閾值β將P*-A劃分為稀疏群體B、稠密群體C；

步驟5 模擬免疫過程：

步驟5.1 群體A、B、C的最優個體分別記Abest、Bbest、Cbest，進一步更新群體最優xbest；各子群按照適應度的優劣各刪除δ%劣質個體；

步驟5.2 模擬細胞免疫：群體A 的個體xj的進化策略：

獲種群A*。a、b是搜索區間左、右端的向量；s=min{x-a,b-x}，xdist是x到A的距離；

步驟5.3 模擬Toll 信號通路：種群B 中個體xj的更新策略：

獲種群B*。r是0～1之間的隨機數；

步驟5.4 模擬Imd 信號通路：種群C 中個體xj的變異策略：

獲種群C*。其中：

步驟5.5P(t)←A*∪B*∪C*。若P（t）中最優個體優于xbest，則及時更新xbest；

步驟5.6 若m

步驟6 若t

否則，輸出xbest。

在上述算法設計中，步驟3 對應黑化作用的免疫過程；步驟5.2 模擬細胞免疫中吞噬、包裹機制，并結合最優個體Bbest、Cbest來確定新個體的進化方向；步驟5.3、5.4 借助最優個體Abest、Bbest、Cbest及xbest的相關信息，實現個體更新，受啟發于三種免疫機理的協同應答機制。

3 數值實驗

借助Windows 10/CPU 3.60GHz/RAM 16.0GB/VC++平臺進行數值統計實驗與分析。比較算法有近年公開發表的FFO［17］、IFFO［17］、MFOA［18］和MDFOA［19］。測 試 函 數 有 單 模 態（f1～f7）和 多 模 態（f8～f10），測試區域與文獻［5］一致。測試函數的搜索區域既有非對稱區間又有對稱區間，搜索區域范圍相差較大，能充分檢測算法的全局搜索與局部挖掘能力。各算法在相同參數條件N=60，G=225下獨立求解每個問題100 次，其他參數與相應文獻設置相同。通過多次數值實驗的比較與分析，CFIOA中的參數分別取值為

為測試各算法求解高維函數的優化能力，以上算法在維數n=500 時展開數值實驗比較與分析（文獻［5］已對n=100、200 維的數值比較實驗與算法性能進行分析），以比較各算法求解類型多樣的高維函數優化的共性和個性；另外，為驗證本文算法CFIOA 具有更強的優化能力，特進行維度n=800、900及1000的求解實驗。

3.1 500維數值實驗與性能分析

取定n=500，上述算法獨立進行求解各問題100次，各算法優化的均值如表1；繪制函數f1、f4、f7、f10的平均搜索曲線如圖3。其中，f*為500 維時各函數的理論最優值；t為算法迭代次數；ft為100 次獨立運行下第t代群體搜索到的最優值的均值。

表1 500維的統計結果

圖3 500維函數f1、f4、f7、f10的平均搜索曲線

從表1 的數值對比發現，高維函數優化對算法模塊的設計、算法搜索能力、求解效率等方面均提出了較大挑戰。隨著問題維數的增加，除CFIOA外，四種參與比較的算法呈現倍數甚至指數級的下降。而CFIOA 在10 個求解問題中，仍有80%的函數可以達到理論極值，說明該算法受問題維數的影響較小。結合文獻［5］，CFIOA 對于f8的優化結果看，隨著問題維數100、200、500 的增加，所獲得的的優化均值分別為其理論極值的47%、35%、20%，持續下降的優化極值占比，說明高維多模態函數的優化難度較大，對算法模塊的設計有更高的要求，但CFIOA求解該問題的均方差較大，說明該算法的種群多樣性得以維持，各子群協同進化的模塊設計保證了算法的優化效果與算法的收斂性。結合表1 與圖3 信息可知，CFIOA 較其他比較算法而言，其尋優速度、收斂精度（除f8外），種群多樣性等方面均有較為明顯的優勢，受問題維數的影響也相對較小，進一步驗證了該算法CFIOA的優化穩定性和尋優效率。

3.2 算法差異性分析

為明確算法的優化效率，獲得500 維時，各算法單獨求解10個問題100次的時間均值，如表2。

表2 各算法的平均運行時間分析（單位：s）

對比表2 各算法優化不同維度函數的平均運行時間可知，對于同一維度的函數，CFIOA 所需時間最短，源于其內、外循環的模塊設計以及模擬黑化作用的淘汰方式在很大程度上降低了計算量，進而縮短了運行時間，其他算法依次是IFFO、MDFOA、FFO、MFOA。

為分析各算法所獲得的優化解是否存在明顯差異，以上述算法求解各問題的平均優化值為樣本，依托Friedman［20］和Friedman 秩檢驗［20］方法，將結果統計在表3。特別地，顯著性水平取α=5%且有

表3 各算法秩檢驗結果

從表3數據知，優化問題為500維時，本文算法一方面具有最小的F 值以及FA 值，另一方面獲得的統計值都大于5.99。綜上說明，CFIOA 獲得了優于其他比較算法的解，其解的質量存在顯著性優勢［20～21］。

3.3 CFIOA的高維性能測試與分析

算法CFIOA 獨立求解維數為800、900 及1000時的f1～f10各100次，獲得的優化目標均值如表4。

表4 CFIOA關于800～1000維函數的優化結果

由表4 的數據信息知，算法CFIOA 求解維數為800、900、1000 時分別有60%、40%、30%的函數可以搜索到理論極值，說明問題維數的增加對算法尋優性能提出了更高、更全面的挑戰。對于問題f1、f4、f7、f8時，隨維數的增加，難以搜索到理論極值，卻具有較大的均方差，從而有相差較大的最優解，一方面說明該算法的個體信息具有多樣性，另一方面也說明該算法的局部與全局搜索能力較好，有能力跳出局部極值，更進一步保證了算法的持續尋優。但該算法CFIOA 仍存在不足，如參數靈敏度的調控、高維函數的優化精度等，如何平衡好算法優化效果與求解效率將是下一步完善算法設計的關鍵。

4 結語

果蠅極為簡單有效的先天性免疫機制，使得作為細菌、真菌傳播載體的果蠅自身而不被感染，受此啟發著眼于果蠅先天性協同免疫機制，構建果蠅免疫理論模型，進一步獲得果蠅免疫協同優化算法。各種免疫機制獨立又相互影響的應答機理是協同思想設計的主要來源，這為算法的模塊設計提供了思路。大量數值結果及分析可知，算法CFIOA在搜索速度、前期全局、后期局部、種群多樣性、跳出局部極值等方面的能力具有明顯優勢。