姓名：劉慧林；學(xué)號(hào)：21021210619；學(xué)院：電子工程學(xué)院

前言

多因子進(jìn)化算法是多任務(wù)進(jìn)化算法的一種范式，旨在利用單個(gè)種群來(lái)同時(shí)解決多個(gè)優(yōu)化任務(wù)，是南洋理工大學(xué)的Yew-Soon Ong教授于2016年提出來(lái)的[1]，簡(jiǎn)稱MFEA（或MFO，Multifactorial Optimization）。MFEA利用的是基于種群搜索的隱式并行性，嘗試去發(fā)掘不同任務(wù)之間的隱性關(guān)聯(lián)并借此加快各個(gè)問題的收斂。本文將從一個(gè)初學(xué)者的角度，簡(jiǎn)單地探討一下MFEA。

閱前提示：閱讀本文需要有一定的進(jìn)化算法與多目標(biāo)優(yōu)化的基礎(chǔ)知識(shí)，若無(wú)相關(guān)基礎(chǔ)，可先閱讀參考文獻(xiàn)2。

MFEA的定義

首先，我們定義一個(gè)具有a個(gè)不等式約束條件與b個(gè)等式約束條件的最小值優(yōu)化任務(wù)T為

為了使算法具有普適性，假設(shè)待優(yōu)化的各個(gè)任務(wù)之間相互獨(dú)立，即不給出任何各個(gè)任務(wù)之間的依賴關(guān)系的先驗(yàn)知識(shí)。同時(shí)，假設(shè)所有任務(wù)都是求最小值（求最大值的可以轉(zhuǎn)換為求最小值），定義第j個(gè)任務(wù)為，其搜索空間為，目標(biāo)函數(shù)定義為，則MFEA旨在找到如下的一組解：

其中為搜索空間上的可行解，K為任務(wù)的數(shù)量，該復(fù)合問題被稱為K因子問題（K-factorial problem）。

為了方便解決問題，有如下定義：。

定義1：因子代價(jià)（Factorial Cost）：個(gè)體在任務(wù)上的因子代價(jià)定義為：

其中，為一個(gè)較大的懲罰系數(shù)，和分別為對(duì)的目標(biāo)值和總約束違背量。若對(duì)是可行的（即零約束違背，符合所有的約束條件），則有。

定義2：因子等級(jí)（Factorial Rank）：個(gè)體在任務(wù)上的因子等級(jí)定義為該個(gè)體在種群中的索引，種群中所有個(gè)體的索引按因子代價(jià)從小到大排列后確定。當(dāng)多個(gè)個(gè)體具有相同的因子代價(jià)時(shí)，采用random tie-breaking方法選擇。

定義3：適應(yīng)度標(biāo)量（Scalar Fitness）：個(gè)體的適應(yīng)度標(biāo)量定義為：，其中.

定義4：技能因子（Skill Factor）:個(gè)體的技能因子為該個(gè)體在所有任務(wù)中表現(xiàn)最好的任務(wù)的索引，即:

定義5：多因子最優(yōu)解（Multifactorial Optimality）：個(gè)體的目標(biāo)值為，當(dāng)且僅當(dāng)存在一個(gè)，使對(duì)于所有的都成立時(shí)，稱為多因子最優(yōu)解，其中.

根據(jù)定義3，當(dāng)兩個(gè)個(gè)體的適應(yīng)度標(biāo)量關(guān)系為時(shí)，稱為個(gè)體支配，記作。

多任務(wù)優(yōu)化與多目標(biāo)優(yōu)化的區(qū)別

多任務(wù)優(yōu)化（MFO）與多目標(biāo)優(yōu)化（MOO）有很多相似的地方，比如都是利用單個(gè)種群同時(shí)優(yōu)化多個(gè)問題，但這兩種算法上其實(shí)在本質(zhì)上是有所不同的。從其定義可知，多任務(wù)優(yōu)化當(dāng)中，不同優(yōu)化任務(wù)的約束條件不同，即各個(gè)任務(wù)不在同一搜索空間（當(dāng)然，MFEA中將所有的任務(wù)映射到了統(tǒng)一的搜索空間，但其本質(zhì)上還是在不同的搜索空間對(duì)各個(gè)任務(wù)進(jìn)行求解）。而對(duì)于多目標(biāo)優(yōu)化，所有的優(yōu)化問題都有統(tǒng)一的約束條件。在多任務(wù)優(yōu)化中，我們假設(shè)各個(gè)優(yōu)化任務(wù)之間沒有顯式的關(guān)系，但多目標(biāo)優(yōu)化中的各個(gè)問題往往存在一些沖突。并且，多任務(wù)優(yōu)化的目的是并行地找到所有問題的最優(yōu)解，單個(gè)個(gè)體只需要關(guān)心它最擅長(zhǎng)的任務(wù)，而多目標(biāo)優(yōu)化則是尋找一個(gè)面向所有問題的折衷的解（Pareto最優(yōu)解）。為了更好地展示兩種范式的區(qū)別，我們借用下圖進(jìn)行說(shuō)明。

MFEA1.png

如圖，在多目標(biāo)優(yōu)化中，常常認(rèn)為解之間沒有孰優(yōu)孰劣，但都優(yōu)于解，即支配。而在多任務(wù)優(yōu)化中，則會(huì)認(rèn)為解優(yōu)于解，即。因?yàn)楹驮谌蝿?wù)2上表現(xiàn)很好，和在任務(wù)1上表現(xiàn)很好，我們不關(guān)心它們?cè)谄渌蝿?wù)上的表現(xiàn)如何。

詳解MFEA

MFEA不僅受到了達(dá)爾文主義的啟發(fā)，還受到了拉馬克主義的啟發(fā)，因此文獻(xiàn)[1]的作者認(rèn)為MFEA屬于模因計(jì)算（memetic computation）領(lǐng)域，父代將通過交配、變異和垂直文化傳播把基因和模因（又稱文化基因）傳給后代，具體細(xì)節(jié)將在接下來(lái)的部分中進(jìn)行介紹。首先，給出MFEA的基本結(jié)構(gòu)的偽代碼

算法1：MFEA的基本結(jié)構(gòu)：

1、生成一個(gè)多個(gè)體種群并將其儲(chǔ)存在current-pop（P）中。
2、在多任務(wù)環(huán)境中，對(duì)每一個(gè)優(yōu)化任務(wù)進(jìn)行評(píng)估。
3、計(jì)算每個(gè)個(gè)體的技能因子t（skill factor）。
4、while （不滿足終止條件） do
（1）、在current-pop上應(yīng)用遺傳算子來(lái)生成offspring-pop (C)，參見下文的算法2。
（2）、僅對(duì)選定的優(yōu)化任務(wù)評(píng)估offspring-pop中的個(gè)體，見下文算法3。
（3）、合并offspring-pop與current-pop，生成intermediate-pop (P∪C)。
（4）、更新intermediate-pop中每個(gè)個(gè)體的標(biāo)量適應(yīng)度（scalar fitness）和技能因子 （skill factor）。
（5）、在intermediate-pop中選擇適應(yīng)度最高的個(gè)體，組成新的種群current-pop（P）。
5、end while</pre>

1、種群初始化

假設(shè)K個(gè)優(yōu)化任務(wù)同時(shí)執(zhí)行，其中第j個(gè)任務(wù)的維數(shù)由給出。據(jù)此，我們定義一個(gè)統(tǒng)一的搜索空間，該空間的維度。種群初始化時(shí)，每個(gè)個(gè)體隨機(jī)生成一個(gè)維的隨機(jī)向量，向量中的每個(gè)元素的取值在區(qū)間[0,1)上，這個(gè)隨機(jī)向量代表個(gè)體的染色體。在統(tǒng)一的搜索空間上，第i維用一個(gè)隨機(jī)鍵值表示，固定的范圍表示統(tǒng)一搜索空間的約束。在處理第j個(gè)任務(wù)時(shí)，我們使用個(gè)體染色體的第個(gè)隨機(jī)鍵值，然后將該變量映射到任務(wù)上。假設(shè)某個(gè)實(shí)際任務(wù)的第i個(gè)變量在區(qū)間內(nèi)，則通過如下公式，將統(tǒng)一搜索空間的隨機(jī)鍵值映射到對(duì)該任務(wù)有意義的輸入：

2、遺傳機(jī)制

首先需要知道的是，在MFEA中，父代之間的交配并不隨機(jī)，它們會(huì)傾向與自己文化背景相同（即技能因子相同）的進(jìn)行交配，而對(duì)于文化背景不同的兩個(gè)個(gè)體，它們之間交配的概率由隨機(jī)交配概率rmp（random mating probability）決定。rmp用于平衡局部搜索空間的開發(fā)和全局搜索空間的探索。若設(shè)定rmp為1，則意味著個(gè)體之間的交配是完全隨機(jī)的，rmp為0則意味著完全不允許不同文化背景的個(gè)體進(jìn)行交配，這容易陷入局部最優(yōu)解。因此需要選擇一個(gè)合適的rmp，使算法能在局部搜索與全局搜索之間達(dá)到良好的平衡。在本文中，設(shè)定rmp為0.3。當(dāng)兩個(gè)個(gè)體不滿足如上的交配條件時(shí)，則會(huì)通過變異來(lái)產(chǎn)生后代。該過程的偽代碼如下：

算法2：選擇性交配

從current-pop中隨機(jī)選擇兩個(gè)父代個(gè)體pa和pb。
1、產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù)rand。
2、if (ta == tb) or (rand < rmp) then
(1)、父代個(gè)體pa與pb交叉，產(chǎn)生后代ca和cb。
3、else
(1)、父代pa輕微變異產(chǎn)生后代ca。
(2)、父代pb輕微變異產(chǎn)生后代cb。
4、end if</pre>

在上述過程中，使用的是兩種較為流行的遺傳算子，即模擬二進(jìn)制交叉（Simulated Binary Crossover，簡(jiǎn)稱SBX）和高斯變異（Gaussian Mutation）。

3、選擇性評(píng)估

顯然，如果每一個(gè)個(gè)體都要在所有任務(wù)上進(jìn)行評(píng)估，算法的時(shí)間復(fù)雜的會(huì)很大，并且這也沒有必要，因?yàn)樵贛FO中我們的目的是找到所有任務(wù)的最優(yōu)解，而不是用一個(gè)解去解決所有任務(wù)。因此MFEA中使用了一種選擇性評(píng)估的機(jī)制，對(duì)于個(gè)體而言，我們只需要關(guān)心它最擅長(zhǎng)的那個(gè)任務(wù)，只評(píng)估它表現(xiàn)最好的那個(gè)任務(wù)即可。當(dāng)個(gè)體產(chǎn)生后代后，后代擅長(zhǎng)的任務(wù)則首先通過垂直文化傳播確定，其過程如算法3所示。

算法3：通過選擇模仿的垂直文化傳播

對(duì)于一個(gè)個(gè)體c，它會(huì)有兩個(gè)父代（pa和pb）或者只有一個(gè)父代（pa或pb）--見算法2。
1、if (c有兩個(gè)父代) then
(1)、產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)rand。
(2)、if (rand<0.5) then
c模仿pa -> 該后代僅在任務(wù)ta時(shí)進(jìn)行評(píng)估（ta為pa的技能因子skill factor）。
(3)else
c模仿pb -> 該后代僅在任務(wù)tb時(shí)進(jìn)行評(píng)估。
(4)end if
2、else
c模仿它唯一的一個(gè)父代 -> 該后代僅在其父代任務(wù)上進(jìn)行評(píng)估。
3、end if
4、人為地將未評(píng)估的任務(wù)中c的因子損失（Factorial Cost）設(shè)置為無(wú)窮大。</pre>

講到這里，我們不妨一起來(lái)看看MFEA的遺傳與垂直文化傳播的過程的具體代碼，該代碼是MFEA的作者給出的Matlab代碼，有需要的小伙伴可以點(diǎn)擊這里去官網(wǎng)下載。（這里先挖個(gè)坑，有空我寫個(gè)Python版本的供大家學(xué)習(xí)）

%%% Chromosome是個(gè)體對(duì)象
%%% crossover()為交配函數(shù)
%%% mutate()為變異函數(shù)
for i = 1 : pop/2
p1 = indorder(i); %前半部分的一個(gè)個(gè)體
p2 = indorder(i+(pop/2)); %后半部分的一個(gè)個(gè)體
child(count)=Chromosome();
child(count+1)=Chromosome();
if (population(p1).skill_factor == population(p2).skill_factor) || (rand(1)<rmp) % 雜交
u = rand(1,D_multitask);
cf = zeros(1,D_multitask);
cf(u<=0.5)=(2u(u<=0.5)).^(1/(mu+1));%SBX的參數(shù)
cf(u>0.5)=(2(1-u(u>0.5))).^(-1/(mu+1));
child(count) = crossover(child(count),population(p1),population(p2),cf);
child(count+1) = crossover(child(count+1),population(p2),population(p1),cf);
sf1=1+round(rand(1));%隨機(jī)生成0或1
sf2=1+round(rand(1));
if sf1 == 1 %選擇性模仿
child(count).skill_factor=population(p1).skill_factor;
else
child(count).skill_factor=population(p2).skill_factor;
end
if sf2 == 1
child(count+1).skill_factor=population(p1).skill_factor;
else
child(count+1).skill_factor=population(p2).skill_factor;
end
else %變異
child(count)=mutate(child(count),population(p1),D_multitask,sigma);
child(count).skill_factor=population(p1).skill_factor;%直接模仿
child(count+1)=mutate(child(count+1),population(p2),D_multitask,sigma);
child(count+1).skill_factor=population(p2).skill_factor;
end
count=count+2;
end</pre>

4、選擇操作

如算法1所示，MFEA遵循一種精英選擇策略，以保證優(yōu)秀的個(gè)體能夠世代相傳。

小結(jié)

多任務(wù)學(xué)習(xí)（Mulititask Learning）是一個(gè)已經(jīng)提出了很多年的概念，屬于機(jī)器學(xué)習(xí)的一個(gè)分支，旨在同時(shí)學(xué)習(xí)多個(gè)任務(wù)。而進(jìn)化多任務(wù)則是近幾年才被提出來(lái)的概念，進(jìn)化多任務(wù)則是嘗試?yán)眠M(jìn)化算法的隱式并行性去同時(shí)解決多個(gè)任務(wù)，本文所闡述的MFEA是進(jìn)化多任務(wù)的一種具體范式，與傳統(tǒng)的進(jìn)化算法相比，該算法首先是將不同的搜索空間映射到統(tǒng)一的搜索空間以實(shí)現(xiàn)同時(shí)對(duì)多個(gè)任務(wù)進(jìn)行優(yōu)化，然后引入技能因子與垂直文化傳播的概念，以減少評(píng)估次數(shù)，加快算法的收斂，該算法在一些經(jīng)典的優(yōu)化函數(shù)上有比單任務(wù)優(yōu)化更好的結(jié)果，更快的收斂速度（見參考文獻(xiàn)[1]），可以說(shuō)是入門進(jìn)化多任務(wù)一個(gè)必學(xué)的一個(gè)算法。

參考文獻(xiàn)

[1] A. Gupta, Y. Ong and L. Feng, "Multifactorial Evolution: Toward Evolutionary Multitasking," in IEEE Transactions on Evolutionary Computation, vol. 20, no. 3, pp. 343-357, June 2016, doi: 10.1109/TEVC.2015.2458037.

[2] 公茂果, 焦李成, 楊咚咚,等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào), 2009, 20(002):271-289.