信息篩選多任務優化自組織遷移算法

程美英，錢 乾，倪志偉，朱旭輝

（1.湖州師范學院經濟管理學院，浙江湖州 313000；2.浙江省教育信息化評價與應用研究中心，浙江湖州 313000；3.湖州師范學院教師教育學院，浙江湖州 313000；4.合肥工業大學管理學院，合肥 230009）

（?通信作者電子郵箱02550@zjhu.edu.cn）

0 引言

自組織遷移算法（Self-Organized Migrating Algorithm，SOMA）［1］是一種新型基于群體的智能優化算法，自2004 年提出至今已得到廣泛研究，現有成果主要集中于兩方面:1）改進SOMA，彌補易陷入局部最優、收斂速度慢、求解精度低等缺陷。文獻［2］引入機會策略產生擾動向量，提供比基本SOMA更多的位置選擇來增強個體尋優能力；文獻［3］在SOMA 中引入自適應參數控制、領導個體選擇及給最優個體建立外部檔案等策略提高種群多樣性；文獻［4］在每次迭代過程中按照與領導者的歐氏距離均勻選擇粒子進行移動，提高SOMA 收斂速度和精度等。2）將SOMA 應用于解決實際優化問題。文獻［5］在可重構制造業中引入SOMA 最小化機器模塊變化；文獻［6］將SOMA 用于機器人躲避動態障礙物并抓取移動目標；文獻［7］引入SOMA解決多層次圖像閾值分割問題等。

基于群體的智能優化算法通過個體之間的協作能“涌現”出智能行為，實則具有隱含并行性，而這種并行性表現在兩方面:一是算法的內在并行，即本身適合大規模并行；二是算法的內涵并行性，群體智能算法采用種群的方式組織搜索，因而可以搜索解空間內的多個區域，并相互交流信息，具備很強的多任務優化能力（多任務優化指在某一時刻同時處理多個不同的優化問題［8］）。基于群體智能算法的多任務優化［9］概念開創了將具有“隱”并行性的進化算法應用于多任務處理的新局面。文獻［9］首次探索多因子遺傳機制，提出多任務處理多因子進化算法（MultiFactorial Evolution Algorithm，MFEA），在多層次多任務優化［10］、多目標多任務優化［11］等領域中均得到較好應用；文獻［12］在MFEA 基礎上，引入擬牛頓迭代、重新初始化部分適應值較差解、自適應選擇策略，提高MFEA 求解多任務性能；文獻［13］通過實驗證明MFEA 可保持種群的動態多樣性，但MFEA 的本質在于有效信息傳遞；文獻［14］以數據驅動獲取任務之間的相關信息，自適應實現任務之間的信息傳遞；文獻［15］基于閉式解自動降噪編碼器顯示實現多任務之間映射；文獻［16-17］首次將自然界生物種群中的協同進化機制與粒子群算法相結合，子種群間按一定概率或連續停滯若干代后交互信息，實現多任務優化；文獻［18］引入等級因子、標量因子和技能因子構造多任務環境，每次讓最合適的粒子求解最合適的任務。

現有SOMA 關注點主要集中在單個任務優化上，在多任務優化領域研究甚少，且現有關于在多任務優化領域如何避免無關信息共享造成“負遷移”現象的研究成果并不多。基于上述問題，本文的主要工作為:通過有效探索SOMA 的“隱并行性”，共享和協調種群中有效信息，實現多任務優化，然后引入信息篩選機制有效遏制多任務負遷移消極影響，提出信息篩選多任務優化自組織遷移算法（SOMA for Multi-task optimization with Information Filtering，SOMAMIF）。仿真實驗以一組函數優化問題和一組離散優化問題為例驗證了SOMAMIF的有效性。

1 基本SOMA描述

SOMA 的社會生物學基礎是社會環境下群體的自組織行為，如一群動物在尋找食物時，若某一個體率先發現食物，則成為群體領先者，其他個體通過改變自身運動方向遷移至領先者附近，在搜索過程中某個體若比先前領先者更為成功，則它成為群體中新的領先者，其他個體再次改變運動方向遷移至該新領先者所在位置，直至達到或接近全部最優解。SOMA基本步驟如下:

步驟1 初始化種群中個體位置和所有參數。

步驟2 計算所有個體適應值。

步驟3 比較得出當前領先者位置。

步驟4 按式（1）得出參數PRTVector。

步驟5 按式（2）更新個體位置。

步驟6 判斷是否滿足循環結束條件，若不滿足，轉步驟2。

步驟7 輸出全局最優解。

PRTVector依賴于PRT:若隨機 數rand小 于PRT，則PRTVector取值1，否則為0，如式（1）所示。

2 多任務SOMAMIF

為形象描述多任務環境中的信息遷移模式，這里僅以同時求解極小函數優化問題f1和f2為例，如圖1 所示。假設f2全局極值點位于B點，在AB區域，函數f1和f2的單調趨勢相反，當f1傳遞信息給f2，必會使得f2偏離極值點（信息負遷移）；而在BC區域，當f1傳遞信息給f2，必會加速f2收斂至極值解（信息正遷移）。若能利用BC區域的有效信息，將任務f1和f2綁定同時求解，必能同時加速f1和f2的收斂速度并提高二者的求解質量。

圖1 多任務信息遷移Fig.1 Multi-task information transfer

2.1 多任務SOMAMIF搜索空間設置

多任務環境中不同任務一般處于不同的維度，構建統一多任務搜索空間，使得不同維度的任務仍然可以傳遞有效信息。假設需要同時處理K個任務T1，T2，…，TK，任務Ta（a=1，2，…，K）的搜索空間和維數分別設為ψa和da，令多任務統一搜索空間Ψ=ψ1∪ψ2，…，∪ψK，維 數D=max｛d1，d2，…，dK｝，對Ta解碼時，只需取D的前da維。

2.2 多任務SOMAMIF信息篩選和遷移模式

在多任務環境中，無關的信息共享可能傷害多任務處理性能，即出現信息“負遷移”［8］，進而抑制干擾多任務優化性能，這是目前尚未完全解決的難題之一，本文引入信息篩選機制有效遏制“負遷移”消極影響。

假設需要同時處理K個任務，則隨機產生K個SOMA 子種群，子種群Pa（a∈{1，2，…，K}）用于處理任務Ta。各子種群在執行基本SOMA 的同時，實施如下的信息篩選和遷移過程，具體步驟如下:

步驟1 信息交互愿望（需求）。當任務Ta連續若干代停滯進化時，子種群Pa產生信息交互需求，即達到信息交互節點γ。

步驟2 信息獲取來源。自然界中的物種并非彼此孤立，生活在同一環境中的物種/種群通過交互信息達到共同進化。當任務Ta產生信息交互需求時，其他K-1個任務（或子種群）成為任務Ta獲取信息的主要來源，即:(T1，T2，…，TK) →Ta。

步驟3 信息篩選。選擇所有信息來源中對自己有用的信息，過濾無用信息，可在一定程度上保證信息的正向遷移。這里根據同時處理的任務個數選擇不同的信息遷移來源:

a）當K=2 時。若任務T1停滯進化，將任務T2中個體適應值快速排序，取排名前30%的個體位置作為信息遷移來源。

b）當K＞2 時。采用基于概率的信息選擇模式，隨機產生［0，1］的隨機數rand，當rand≤時，選擇任務T1作為信息遷移源，若Ta連續在λ代內不能改變進化停滯現象（即信息負遷移），則繼續按概率從剩余K-2 個任務中選擇信息遷移來源，如圖2所示。

圖2 多任務信息來源選擇示意圖Fig.2 Schematic diagram of multi-task information source selection

步驟4 信息遷移。假設t時刻，任務Ta停滯進化產生信息交互愿望，選中任務Tk作為信息遷移來源。按式（3）將任務Tk所在種群個體位置與任務Ta種群中的所有個體位置進行交叉。信息遷移不是單純的信息增加，而是遷移信息后，種群結構的重新調整。

多任務SOMAMIF偽代碼如下:

1） 隨機產生K個子種群Pa（a∈{1，2，…，K}）用于同時處理K個極小優化問題。

2） 初始化子種群Pa(t=0)（a∈{1，2，…，K}）中個體位置和參數。

3） 計算種群Pa(t=0)領先者fbesta(t=0)。

4） while（未滿足循環結束條件）

5）t=t+1；

6） for（對任意子種群Pa）

7） for（對任意個體i，i∈Pa）

8） 按式（1）～（2）更新個體i位置；

9） 計算個體i適應值；

10） end for

11） 比較得出子種群Pa當前領先者

13）counta=counta+1

14） end if

15） if（counta==γ）

16） 子種群Pa產生信息交互需求；

17） 按圖2選擇信息來源；

18） 按式（3）實施信息遷移，并評價個體適應值；

19）counta=0

20） end if

21） 比較子種群Pa全局極值解；

22）end for

23）end while

24）輸出K個任務全局最優解。

2.3 多任務SOMAMIF復雜度分析

這里僅以同時處理2 個任務（即K=2）為例。設子種群P1和P2規模分別為m，最大迭代次數為Maxiter，任務T1維數為d1，任務T2維數為d2，假設d1＞d2，則多任務搜索空間維數為D=max{d1，d2}=d1，當計算任務T2適應值 時，取d1中 的前d2維。

2.3.1 時間復雜度分析

SOMAMIF 同時優化2 個任務的時間復雜度等于求解任務T1時間復雜度Q1和T2時間復雜度Q2之和。其中:

1）優化任務T1時間復雜度Q1分析。

a）子種群P1運行時間復雜度包括:初始化子種群P1中m個個體位置時間復雜度為O(m·d1)；初始化參數s、PRT時間復雜度為O(1)；計算個體適應值時間復雜度為O(m·d1)；比較得出當前領導者位置時間復雜度為O(m)；計算參數PRTVector時間復雜度為O(1)；更新個體遷移后位置時間復雜度為O(m·d1)；更新子種群P1領先者位置時間復雜度為O(d1)。經過Maxiter次迭代后得=O(Maxiter·m·d1)。

b）子種群P1篩選信息、P2向P1遷移信息復雜度包括:假設在整個算法Maxiter次迭代過程中，子種群P2向P1傳遞了θ1次信息，每次產生信息交互需求時，將子種群P2個體適應值進行快速排序時間復雜度為O(mlogm)，每次信息遷移產生新位置的時間復雜度為O(m·d1)，計算新位置適應值時間復雜度為O(m·d1)，比較得出新領導者位置時間復雜度總時間為O(m)，總體復雜度為O(θ1·m·d1)；其他操作時間復雜度常數次O(1)。綜合分析，得=O(θ1·m·d1)，則Q1==O(Maxiter·m·d1)+O(θ1·m·d1)。

2）優化任務T2時間復雜度Q2分析。

優化任務T2的過程與T1相似，也包括兩部分:

a）子種群P2運行時間復雜度包括:初始化子種群P2中m個個體位置時間復雜度為O(m·d1)；初始化參數s、PRT時間復雜度為O(1)；計算個體適應值時間復雜度為O(m·d2)；比較得出當前領導者位置時間復雜度為O(m)；計算參數PRTVector時間復雜度為O(1)；更新個體位置時間復雜度為O(m·d1)；更新子種群P2領先者位置時間復雜度為O(d2)。綜合上述分析，因d1＞d2，經過Maxiter次迭代后得Q12=O(Maxiter·m·d1)。

b）子種群P2篩選信息、P1向P2遷移信息復雜度包括:假設在整個算法Maxiter次迭代過程中，子種群P1向P2傳遞了θ2次信息，每次產生信息交互需求時，將子種群P1個體適應值進行快速排序時間復雜度為O(mlogm)，每次信息遷移產生新位置的時間復雜度為O(m·d1)，計算新位置適應值時間復雜度為O(m·d2)，比較得出新領導者位置時間復雜度總時間為O(m)，總體復雜度為O(θ1·m·d1)；其他操作時間復雜度常數次O(1)。綜合分析，得=O(θ2·m·d1)。則Q2==O(Maxiter·m·d1)+O(θ2·m·d1)。

因θ1＜Maxiter，θ2＜Maxiter，綜 合1）和2），得 出SOMAMIF 求解兩個不同優化任務的時間復雜度如式（4）所示:

2.3.2 空間復雜度分析

1）任務T1所需存儲空間包括如下兩部分:

a）子種群P1所需存儲空間:存儲子種群P1中m個個體位置所需空間為m·d1；存儲P1領先者位置所需空間為d1。

b）子種群P1篩選、遷移信息所需存儲空間:存儲新位置所需存儲空間為m·d1。

2）任務T2所需存儲空間包括如下兩部分:

a）子種群P2所需存儲空間:存儲子種群P2中m個個體位置所需空間為m·d1；存儲P2領先者位置所需空間為d2。

b）子種群P2篩選、遷移信息所需存儲空間:存儲新位置所需存儲空間為m·d1。

因d1＞d2，綜合1）和2），得出SOMAMIF 求解兩個不同優化任務的空間復雜度如式（5）所示:

由式（4）～（5）可知:本文多任務SOMAMIF 求解兩個不同任務的時間和空間復雜度均為多項式。

將本文算法與文獻［16］算法、文獻［18］算法進行對比分析，設置相同迭代次數Maxiter、種群規模m、最大搜索空間維數d1。文獻［16］的協同多任務粒子群優化（MultiTasking Coevolutionary Particle Swarm Optimization，MT-CPSO）算法同時處理兩個不同任務時間和空間復雜度分別為O(Maxiter·m·d1)、O(m·d1)。

當種群規模m小于等于函數維數d1，即m≤d1時，文獻［18］的信息交互多任務粒子群優化（Information Exchange Particle Swarm Optimization for Multitasking，IEPSOM）算法同時求解兩個不同任務的時間和空間復雜度分別為O(Maxiter·m·d1)和O(m·d1)；當m＞d1時，文獻［18］算法同時求解兩個不同任務的時間和空間復雜度分別為O(Maxiter·m2)和O(m2)。

綜合上述對比分析可知，本文多任務SOMAMIF的時間復雜度和空間復雜度與MT-CPSO算法、IEPSOM算法相當。

3 仿真實驗與結果分析

3.1 SOMAMIF求解多任務高維函數優化問題

本節以8 個經典benchmark 函數優化問題為例，如式（6）～（13），按函數和維數構造不同多任務組合，在同一時刻處理3 個優化問題，以驗證SOMAMIF 求解多任務性能。為強調SOMAMIF多任務環境中信息篩選機制的優異性能，這里采用消融法比較信息篩選前后算法性能差異，若信息篩選前后涉及到相同的參數，則設為一致。

為方便描述，將上述8 個函數名稱進行簡寫，并給出函數全局最優值，如表1所示。

表1 函數簡稱及最優值Tab.1 Function abbreviation and optimal value

當SOMA 中未引入信息篩選機制處理50 維Sphere 函數優化問題時，將其標簽設為50S；若采用多任務SOMAMIF 同時處理50 維Sphere function、50 維Ackley function、50 維Rastrigin function，則將其標簽設為（50S，50A，50R），依此類推，將上述8個函數分成如下6個多任務組:

F1={50S，50A，50R，(50S，50A，50R)}

F2={50S，50G，50Q，(50S，50Q，50G)}

F3={50SD，50SS，50Z，(50SD，50SS，50Z)}

F4={100S，100A，100R，(100S，100A，100R)}

F5={(100S，100G，100Q，(100S，100G，100Q)}

F6={(100SD，100SS，100Z，(100SD，100SS，100Z)}

F1、F2、F3、F4、F5、F6分別用于比較在SOMA 中引入信息篩選機制前后，50S、50A、50R、50G、50Q、50SD、50SS、50Z、100S、100A、100R、100G、100Q、100SD、100SS、100Z的求解性能。

算法參數設置如下:多任務組合F1、F2、F4、F5搜索空間設為[-30，30]，F3、F6搜索空間均設為[-10，10]，子種群規模為50，迭代次數為500，步長step=0.08。同時，多任務SOMAMIF中的信息遷移節點γ=10。多任務組合F1、F2、F3、F4、F5、F6單獨運行30次求平均值實驗結果如表2所示。

表2 引入信息篩選機制前后本文算法求解多任務高維函數優化問題的實驗結果Tab.2 Experimental results of proposed algorithm solving multi-task high-dimensional function optimization problems before and after introducing information filtering mechanism

當SOMA 中未引入信息篩選機制求解50 維函數，如50S、50A、50R、50G、50Q、50SD、50SS、50Z時，最優適應值分別為0.101 681、0.208 711、5.755 48、0.108 872、1、1.6E-11、0.000 708 014、66.539 5，平均適 應值分別為1.837 051、1.275 379、54.948 31、0.247 349、11.5、44.9、0.166 966、96.012 77，而引入信息篩選機制的多任務SOMAMIF 求解任務（50S，50A，50R）、（50S，50Q，50G）、（50SD，50SS，50Z）組合時，50S、50A、50R、50Q、50G、50SD、50SS、50Z最優適應值均達到了全局極值解0，平均適應值也遠遠優于未引入信息篩選機制的SOMA。當上述8 個函數維數上升到100 維時，多任務SOMAMIF 所得結果也明顯優于SOMA，這說明本文提出的多任務算法通過子種群之間的信息篩選和遷移能顯著提高解的質量。

表3 將本文多任務SOMAMIF 運行結果與文獻［16］的多任務MT-CPSO 算法、文獻［18］的多任務IEPSOM 算法進行對比，本文算法和MT-CPSO算法、IEPSOM算法在求解上述50維和100 維函數時，實驗結果基本相當，但本文算法在求解100R、100SS、100Z時性能優于MT-CPSO 算法，且除了求解50SD、100SD這兩個函數時稍劣于IEPSOM 算法外，本文算法求解其他函數結果均優于IEPSOM 算法。這些結果在SOMAMIF 和MT-CPSO 算法、SOMAMIF 和IEPSOM 算法威 爾克森符號秩檢驗結果中得到了進一步證實（設置信度水平為0.05），結果如表4所示。

表3 不同算法求解多任務高維函數優化問題的平均適應值對比Tab.3 Average fitness comparison of different algorithms in solving multi-task high-dimensional function optimization problems

表4 不同算法求解多任務高維函數優化問題威爾克森符號秩檢驗結果Tab.4 Wilcoxon signed-rank test results of different algorithms in solving multi-task high-dimensional function optimization problems

圖3 進一步給出信息篩選前后，高維函數50S、50A、50R、50Q、50G、50SD、50Z、100S、100A、100R、100G、100Z單獨運行30 次的平均收斂曲線。由圖3 可知，當SOMA 中未引入信息篩選機制時，上述50維或100維函數收斂速度緩慢，均停滯在局部極值解附近，而SOMAMIF能明顯同時加速多個任務的收斂，使其快速收斂至全局最優解。

圖3 信息篩選前后高維函數平均收斂曲線圖Fig.3 Average convergence curves for high-dimensional functions before and afterinformation filtering

3.2 SOMAMIF結合分形維數提取學生返鄉關鍵制約因素

2020 年一場突發疫情席卷全球，不可避免地對中國乃至世界經濟造成較大沖擊，企業穩崗壓力增大，一些企業裁員數上升，勞動力市場需求“縮水”，失業人員增加。2020 屆全國普通高校畢業生874 萬，比上一年增加了40 萬人，增量、增幅均為近年之最，這讓原本嚴峻的就業形勢雪上加霜。盡管地方政府出臺了一系列措施，積極鼓勵大學生返鄉創業就業，但收效甚微。有效識別制約大學生返鄉關鍵因素，可為地方政府鼓勵和引導大學生返鄉就業政策制定、調整提供科學參考依據。因影響大學生返鄉因素眾多，并可能存在多重共線性，冗余因素的存在不僅導致計算效率低下，還在一定程度上干擾辨識過程。

大學生返鄉關鍵制約因素挖掘過程實質上是一個特征選擇過程，屬于典型的二元離散優化問題。本節以SOMAMIF為搜索策略，將種群中粒子位置通過Sigmoid 函數轉換成1 或0，1或0分別表示該因素是或否被選擇為返鄉關鍵制約因素，分形維數作為子集評估度量準則，同時提取戶籍所在地分別為縣及以下和三線以上城市的大學生返鄉關鍵制約因素。

目前計算數據集分形維數的方法較多，這里采用盒計數法。假設數據集指標個數為L，數據點落在邊長為r的L維格子中，其關聯分形維數如式（14）所示:

其中:s(r)=Cr，w為落入第w個格子的數據點數；r為格子半徑，［r1，r2］為數據集無標度空間。數據集中數據點每維采用十進制實數表示，根據點坐標值和盒子半徑統計該半徑下每個盒子中落入點數的平方和，根據不同半徑r得到一系列不同點對（lnr，lns(r)），擬合后所得直線斜率，即為關聯分形維數。

3.2.1 數據集描述及數據預處理

仿真實驗以高校學生為研究對象，將受訪學生分成兩組:

①戶籍所在地為縣及以下高校學生；

②戶籍所在地為三線及以上城市高校學生。

涉及到的返鄉因素共14 個，分別為:1）所在大學類型；2）學歷；3）家庭情況；4）學習成績；5）當前就業形勢；6）自身求職競爭力；7）父母是否支持返鄉；8）家鄉薪資待遇；9）家鄉生活成本；10）回鄉就業優惠政策；11）家鄉生活節奏工作壓力；12）對家鄉未來發展環境滿意度；13）對家鄉基礎設施滿意度；14）對家鄉居住環境滿意度。返鄉意愿有兩種:愿意返鄉就業/不愿意返鄉就業。

構建基于SOMAMIF的多任務組:

1）任務T1:挖掘戶籍所在地為縣及以下高校學生返鄉關鍵制約因素。

2）任務T2:挖掘戶籍所在地為三線及以上城市高校學生返鄉關鍵制約因素；

其中任務T1實例數為383，任務T2實例數為43。

3.2.2 多任務高校學生返鄉關鍵制約因素提取結果分析

按式（14）分別計算任務T1和T2原始數據集分形維數為2.713 13、4.185 62，然后向上取整得任務T1返鄉關鍵制約因素個數為3（即，任務T2返鄉關鍵制約因素個數為5（即。

將子種群規模設為50，迭代次數為20，信息遷移節點γ=3。采用本文多任務SOMAMIF結合分形維數同時求解任務T1和T2后，得到戶籍所在地為縣及以下高校學生返鄉關鍵制約因素為:父母是否支持返鄉、家鄉薪資待遇和家鄉居住環境滿意度；戶籍所在地為三線及以上城市高校學生返鄉關鍵制約因素為:父母是否支持返鄉、家鄉薪資待遇、家鄉生活成本、家鄉生活節奏工作壓力、對家鄉基礎設施滿意度，約簡率分別為78.57%和64.29%。

進一步采用支持向量機（Support Vector Machine，SVM）計算得出返鄉關鍵制約因素提取前后數據集的平均分類準確率，任務T1和T2原始數據集的平均分類準確率分別為72.913 65%和82.226 18%，最優返鄉關鍵制約因素平均分類準確率分別為73.262 31%和82.824 75%，平均分類準確率分別提高了0.348 66個百分點和0.598 57個百分點。

圖4 和圖5 分別給出了引入信息篩選機制前后算法單獨運行30 次時，不同戶籍高校學生返鄉關鍵制約因素的平均分類準確率收斂曲線。

圖4 信息篩選前后任務T1平均收斂曲線Fig.4 Average convergence curves for task T1 before and after information filtering

圖5 信息篩選前后任務T2平均收斂曲線Fig.5 Average convergence curves for task T2 before and after information filtering

由圖4～5 可知，多任務（T1，T2）的收斂速度明顯優于T1和T2，能顯著縮短返鄉關鍵制約因素的提取時間。

表5 進一步給出了不同戶籍高校學生返鄉關鍵制約因素提取前后威爾克森符號秩檢驗結果，設置信度水平為0.05，由表5可知，T1和（T1，T2）、T2和（T2，T1）的差距顯著。

表5 返鄉關鍵制約因素提取前后威爾克森符號秩檢驗結果Tab.5 Wilcoxon signed-rank test results before and after key home returning constraints extraction

4 結語

本文通過挖掘自組織遷移算法的“隱并行性”，在基本SOMA 中基于信息遷移機制在同一時間內有效求解多個不同優化問題，并引入基于概率的信息選擇方法，在一定程度上保證了信息的正向遷移，能顯著提高多任務的求解質量并加速各優化問題的收斂，為多任務優化提供了一種新穎的高性能計算模型。本文從全新視角研究SOMA，既拓寬了SOMA 的知識內涵，也為后續研究推廣到其他群智能算法實現多任務處理，奠定了理論和實驗基礎。