求解高維函數(shù)的果蠅免疫協(xié)同優(yōu)化算法?

張曉茹 王 丹 周錦程

（1.黔南民族醫(yī)學(xué)高等?？茖W(xué)校 都勻 558000）（2.黔南民族師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 都勻 558000）（3.黔南民族師范學(xué)院復(fù)雜系統(tǒng)與智能優(yōu)化實(shí)驗(yàn)室 都勻 558000）（4.黔南民族師范學(xué)院計(jì)算機(jī)與信息學(xué)院 都勻 558000）

1 引言

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

本文的創(chuàng)新點(diǎn)在于充分模擬果蠅先天防御機(jī)制的黑化作用、細(xì)胞免疫及體液免疫之間的協(xié)同應(yīng)答模式，提出果蠅先天性免疫理論模型及果蠅免疫協(xié)同優(yōu)化算法。

2 免疫理論及算法描述

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

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

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

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

2.2 算法描述

求解如下問題（P）：

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

模擬上述果蠅理論模型，獲得CFIOA的算法流程圖，見圖2。此算法由內(nèi)、外兩個(gè)循環(huán)構(gòu)成，其中內(nèi)循環(huán)主要模擬清除入侵微生物的免疫過程，對(duì)同一種群中的個(gè)體同步執(zhí)行進(jìn)化、個(gè)體數(shù)量遞減的操作，以高效尋求各子群的優(yōu)質(zhì)個(gè)體；外循環(huán)負(fù)責(zé)動(dòng)態(tài)更新所獲的最優(yōu)個(gè)體，以高效獲取群體最優(yōu)。為方便算法描述，將果蠅個(gè)體視為問題候選解，外來有機(jī)體對(duì)應(yīng)于求解問題（P）的最優(yōu)解。結(jié)合圖1 和圖2，具體算法如下。

圖2 CFIOA流程圖

步驟1 參數(shù)設(shè)置：種群總規(guī)模記N，最大外循環(huán)、內(nèi)循環(huán)的迭代數(shù)依次記Gout、Gin，選擇率參數(shù)ω，α,β,δ；

步驟2 置外循環(huán)數(shù)t←1。生成N個(gè)隨機(jī)個(gè)體，即初始種群P(1)，計(jì)算個(gè)體距離并歸一化。記第t代種群為P(t)，其最優(yōu)個(gè)體記xbest；

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

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

步驟5 模擬免疫過程：

步驟5.1 群體A、B、C的最優(yōu)個(gè)體分別記Abest、Bbest、Cbest，進(jìn)一步更新群體最優(yōu)xbest；各子群按照適應(yīng)度的優(yōu)劣各刪除δ%劣質(zhì)個(gè)體；

步驟5.2 模擬細(xì)胞免疫：群體A 的個(gè)體xj的進(jìn)化策略：

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

步驟5.3 模擬Toll 信號(hào)通路：種群B 中個(gè)體xj的更新策略：

獲種群B*。r是0～1之間的隨機(jī)數(shù)；

步驟5.4 模擬Imd 信號(hào)通路：種群C 中個(gè)體xj的變異策略：

獲種群C*。其中：

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

步驟5.6 若m

步驟6 若t

否則，輸出xbest。

在上述算法設(shè)計(jì)中，步驟3 對(duì)應(yīng)黑化作用的免疫過程；步驟5.2 模擬細(xì)胞免疫中吞噬、包裹機(jī)制，并結(jié)合最優(yōu)個(gè)體Bbest、Cbest來確定新個(gè)體的進(jìn)化方向；步驟5.3、5.4 借助最優(yōu)個(gè)體Abest、Bbest、Cbest及xbest的相關(guān)信息，實(shí)現(xiàn)個(gè)體更新，受啟發(fā)于三種免疫機(jī)理的協(xié)同應(yīng)答機(jī)制。

3 數(shù)值實(shí)驗(yàn)

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

為測(cè)試各算法求解高維函數(shù)的優(yōu)化能力，以上算法在維數(shù)n=500 時(shí)展開數(shù)值實(shí)驗(yàn)比較與分析（文獻(xiàn)［5］已對(duì)n=100、200 維的數(shù)值比較實(shí)驗(yàn)與算法性能進(jìn)行分析），以比較各算法求解類型多樣的高維函數(shù)優(yōu)化的共性和個(gè)性；另外，為驗(yàn)證本文算法CFIOA 具有更強(qiáng)的優(yōu)化能力，特進(jìn)行維度n=800、900及1000的求解實(shí)驗(yàn)。

3.1 500維數(shù)值實(shí)驗(yàn)與性能分析

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

表1 500維的統(tǒng)計(jì)結(jié)果

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

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

3.2 算法差異性分析

為明確算法的優(yōu)化效率，獲得500 維時(shí)，各算法單獨(dú)求解10個(gè)問題100次的時(shí)間均值，如表2。

表2 各算法的平均運(yùn)行時(shí)間分析（單位：s）

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

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

表3 各算法秩檢驗(yàn)結(jié)果

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

3.3 CFIOA的高維性能測(cè)試與分析

算法CFIOA 獨(dú)立求解維數(shù)為800、900 及1000時(shí)的f1～f10各100次，獲得的優(yōu)化目標(biāo)均值如表4。

表4 CFIOA關(guān)于800～1000維函數(shù)的優(yōu)化結(jié)果

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

4 結(jié)語

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