適應(yīng)度二次選擇的QPSO和SA協(xié)同搜索大規(guī)模離散優(yōu)化算法

張兆娟，王萬(wàn)良，唐繼軍

（1.浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023；2.天津大學(xué)智能與計(jì)算學(xué)部，天津 300050）

1 引言

近年來(lái)，海量數(shù)據(jù)資源和計(jì)算能力的提升對(duì)大數(shù)據(jù)時(shí)代網(wǎng)絡(luò)優(yōu)化等問(wèn)題產(chǎn)生巨大影響，傳統(tǒng)優(yōu)化算法難以面對(duì)大規(guī)模優(yōu)化問(wèn)題時(shí)搜索空間急劇增長(zhǎng)的挑戰(zhàn)。針對(duì)通信領(lǐng)域，不同的任務(wù)調(diào)度方式影響數(shù)據(jù)中心的利用率、能耗和通信網(wǎng)絡(luò)效果。另一方面，計(jì)算智能算法在面對(duì)大規(guī)模、復(fù)雜、高維的優(yōu)化問(wèn)題時(shí)，優(yōu)化能力會(huì)受到限制。此時(shí)，單一算法的優(yōu)化能力大大削減，但將多種算法協(xié)同能夠發(fā)揮混合算法的效率，從而提升優(yōu)化的性能[1-2]。

面對(duì)大規(guī)模、高維數(shù)據(jù)情形，混合優(yōu)化策略可用于特征選擇、入侵檢測(cè)、通信網(wǎng)絡(luò)的優(yōu)化調(diào)度等領(lǐng)域。Gheyas 等[3]提出模擬退火（SA,simulated annealing）和遺傳算法（GA,genetic algorithm）的結(jié)合算法，可以基于GA 的全局搜索和SA 的避開(kāi)局部最優(yōu)能力對(duì)大規(guī)模的特征子集進(jìn)行選擇。張震等[4]采用遺傳算子對(duì)粒子群算法進(jìn)行了改進(jìn)，并聯(lián)合禁忌搜索對(duì)入侵檢測(cè)的高維數(shù)據(jù)特征進(jìn)行選擇。王晟等[5]提出一種基于遺傳算法和禁忌搜索算法混合優(yōu)化的移動(dòng)代理測(cè)量調(diào)度方法，用于無(wú)線傳感器網(wǎng)絡(luò)中移動(dòng)代理派遣次序的優(yōu)化調(diào)度。葉苗等[6]結(jié)合問(wèn)題實(shí)際背景設(shè)計(jì)出混合人工蜂群求解算法，對(duì)無(wú)線傳感器網(wǎng)絡(luò)中新的最小暴露路徑問(wèn)題進(jìn)行求解。

一個(gè)優(yōu)化算法的性能主要取決于以下4 個(gè)方面的能力[7]：較好的全局搜索能力、快速收斂到最優(yōu)解附近、較好的局部搜索能力、較高的計(jì)算效率。面對(duì)大規(guī)模、高維、離散搜索空間急劇增長(zhǎng)的挑戰(zhàn)，單一算法的優(yōu)化能力呈現(xiàn)一定的局限性，協(xié)同優(yōu)化算法能夠克服上述不足。由于計(jì)算智能算法一般存在早熟現(xiàn)象，因此容易陷入局部最優(yōu)。計(jì)算智能算法主要從初始解的選取和局部最優(yōu)能力的跳出2 個(gè)方面進(jìn)行改進(jìn)。

由于種群規(guī)模的存在能夠增加解的多樣性、SA突跳性有助于量子粒子群優(yōu)化（QPSO,quantum-behaved particle swarm optimization）算法跳出局部最優(yōu)，本文提出了一種改進(jìn)的離散量子粒子群和模擬退火協(xié)同優(yōu)化（IDQPSO-SA,improved discrete QPSO combined with SA）算法。IDQPSO-SA引入適應(yīng)度二次選擇機(jī)制，使量子粒子群優(yōu)化算法適合于求解離散優(yōu)化問(wèn)題，而且采取鑲嵌結(jié)構(gòu)，結(jié)合了SA 和QPSO 各自的優(yōu)點(diǎn)。IDQPSO-SA 的整個(gè)搜索包含2 個(gè)階段：先利用QPSO 的并行搜索和保留歷史信息能力執(zhí)行搜索；再將QPSO 搜索的個(gè)體最優(yōu)解作為SA 初始解，利用SA 概率突跳性來(lái)提升全局搜索能力。

2 基于適應(yīng)度二次選擇的離散QPSO 和SA協(xié)同優(yōu)化算法

2.1 基于適應(yīng)度二次選擇的全局平均最優(yōu)位置更新策略

受量子空間中粒子運(yùn)動(dòng)的啟發(fā)，Sun 等[8]于2004 年提出了一種能夠保證全局收斂的QPSO 算法。由于QPSO 算法只需控制一個(gè)參數(shù)，全局搜索能力較強(qiáng)，已廣泛應(yīng)用于網(wǎng)絡(luò)通信聚類[9]、最優(yōu)設(shè)計(jì)等領(lǐng)域[10]。QPSO 算法中平均最優(yōu)位置的引入能夠提升搜索后期粒子跳出局部最優(yōu)解的概率。但是，由于傳統(tǒng)QPSO 算法是針對(duì)連續(xù)空間設(shè)計(jì)的，平均最優(yōu)位置計(jì)算方法是直接對(duì)所有粒子個(gè)體位置進(jìn)行連續(xù)求和再平均而得。因此，已有QPSO 不適合離散工程優(yōu)化問(wèn)題。

本文引進(jìn)適應(yīng)度二次選擇機(jī)制，提出一種適用于離散優(yōu)化問(wèn)題的全局平均最優(yōu)位置更新策略。首先，對(duì)所有適應(yīng)度值進(jìn)行平均，距離平均適應(yīng)度值位置最近的個(gè)體則為初次得到的平均最優(yōu)位置；然后，選擇大于第一次求得的平均適應(yīng)度值的個(gè)體，并和第一次求得的平均適應(yīng)度值進(jìn)一步進(jìn)行平均，得到第二次平均的適應(yīng)度值；最后，選擇距離第二次求得的平均適應(yīng)度值位置最近的個(gè)體，確定為最終平均最優(yōu)位置。

平均最優(yōu)位置更新式為

其中，M表示種群數(shù)目，f(pbesti)表示個(gè)體最優(yōu)對(duì)應(yīng)的適應(yīng)度值，cbest 表示第一次選擇得到的平均最優(yōu)位置，f(cbest)表示第一次求得的平均適應(yīng)度值。

二次選擇策略考慮了量子機(jī)制的不確定性，并從目標(biāo)函數(shù)的角度提出了全局平均最優(yōu)位置更新的方法；此外，充分考慮了種群分布帶來(lái)的影響，即第一次選擇將整個(gè)種群都進(jìn)行了平均，并在第二次選擇時(shí)保留了整個(gè)種群較優(yōu)的個(gè)體。綜合分析，本文提出的二次選擇的更新策略有助于保留整個(gè)種群的多樣性，也適用于任何離散工程優(yōu)化問(wèn)題。

2.2 更新進(jìn)化流程

步驟1采用個(gè)體最優(yōu)和全局最優(yōu)位置的保優(yōu)原則更新局部吸引子。

IDQPSO-SA 中局部吸引子的進(jìn)化更新采用保優(yōu)原則，通過(guò)交換序列實(shí)現(xiàn)迭代更新。針對(duì)離散工程優(yōu)化問(wèn)題，交換操作是指就維度而言進(jìn)行個(gè)體之間位置的交換，多個(gè)交換操作組成了交換序列。局部吸引子更新式為

其中，P id表示局部吸引子，μ表示0～1 的隨機(jī)數(shù)，pbest 表示個(gè)體最優(yōu)位置，gbest 表示整個(gè)種群的全局最優(yōu)，符號(hào)“⊕”表示交換pbest 和gbest 的位置。

由于Pid的更新迭代綜合考慮了整個(gè)種群的局部最優(yōu)和全局最優(yōu)，即pbest 和gbest 對(duì)整個(gè)種群的進(jìn)化都有影響，從左到右依次對(duì)比pbest 和gbest 序列并交換更優(yōu)維度，可以使Pid向更優(yōu)的方向進(jìn)化。

步驟2采用個(gè)體和平均最優(yōu)位置、局部吸引子二次保優(yōu)原則更新個(gè)體位置。

IDQPSO-SA 的個(gè)體進(jìn)化更新主要依據(jù)個(gè)體位置、平均最優(yōu)位置、局部吸引子保優(yōu)原則進(jìn)行，其中個(gè)體位置和平均最優(yōu)位置分別用Xid和mbest 表示。整個(gè)更新過(guò)程包含2 個(gè)階段：首先依據(jù)mbest 和從左到右交換更優(yōu)維度得到一個(gè)基本交換序列ss1和進(jìn)化位置Xid，即其中soi表示從Xid到mbest 需要進(jìn)行的交換算子；然后，根據(jù)式，進(jìn)一步和局部吸引子Pid進(jìn)行第二次交換。IDQPSO-SA 的個(gè)體進(jìn)化更新式為

其中，X id(t+1)表示個(gè)體當(dāng)前位置，t表示當(dāng)前迭代次數(shù)，β表示擴(kuò)張?收縮因子。

步驟3采用SA 嵌入量子粒子群優(yōu)化算法更新個(gè)體。

SA 算法[11]主要依據(jù)不可逆動(dòng)力學(xué)的思想，在某一溫度下經(jīng)過(guò)不斷降溫，在全局空間中基于蒙特卡羅（Monte Carlo）迭代啟發(fā)式隨機(jī)搜索最優(yōu)解，同時(shí)能以一定概率跳出局部極小值并最終趨于全局最優(yōu)。由于QPSO 搜索存在進(jìn)化緩慢、“早熟”、后期易陷入局部最優(yōu)現(xiàn)象，本文結(jié)合SA 和QPSO各自的優(yōu)點(diǎn)，提出IDQPSO-SA。

SA 是一種根據(jù)給定函數(shù)利用概率方式獲取近似全局最優(yōu)解的啟發(fā)式算法，能夠通過(guò)突跳性來(lái)擴(kuò)大搜索范圍和接受較差解，從而避免算法陷入局部最優(yōu)。傳統(tǒng)模擬退火算法若采取隨機(jī)產(chǎn)生初始解的方式，適應(yīng)能力較差。IDQPSO-SA 算法采用鑲嵌結(jié)構(gòu)，其中模擬退火進(jìn)行種群更新的主要思路為：在初始階段，將量子粒子群優(yōu)化算法搜索得到的個(gè)體最優(yōu)位置作為輸入初始解；然后，由狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新個(gè)體，利用狀態(tài)接受函數(shù)以一定概率接受新個(gè)體，溫度按一定比例下降并將該新個(gè)體作為下一輪迭代時(shí)的當(dāng)前解；不斷迭代直至溫度達(dá)到終止條件后產(chǎn)生最終解，完成整個(gè)IDQPSO-SA 算法的混合搜索。

2.3 IDQPSO-SA 的實(shí)現(xiàn)

IDQPSO-SA 中，每個(gè)個(gè)體分別獨(dú)立進(jìn)化，每一次進(jìn)化促使整個(gè)種群更好地適應(yīng)整個(gè)環(huán)境。隨著迭代的不斷進(jìn)化，搜索到的全局最優(yōu)解越來(lái)越接近理論意義上的最優(yōu)。當(dāng)適應(yīng)度函數(shù)評(píng)估次數(shù)達(dá)到終止條件時(shí)，整個(gè)搜索進(jìn)程停止；否則，重復(fù)搜索直至收斂。本文提出的IDQPSO-SA 算法的流程如圖1 所示。

3 基于IDQPSO-SA 的祖先基因推斷優(yōu)化

3.1 祖先基因推斷優(yōu)化問(wèn)題的研究現(xiàn)狀

最近，全球疫情給全世界帶來(lái)了新的挑戰(zhàn)，而對(duì)冠狀病毒基因組序列進(jìn)行分析以確定溯源具有非常大的現(xiàn)實(shí)意義。事實(shí)上，針對(duì)新冠病毒溯源分析，即祖先基因推斷屬于典型的離散工程優(yōu)化問(wèn)題。尤其在基因組數(shù)據(jù)規(guī)模擴(kuò)大時(shí)，搜索空間急劇增長(zhǎng)的問(wèn)題日益顯著。本文以基因組的推斷為背景，探討大規(guī)模離散工程優(yōu)化問(wèn)題的協(xié)同算法效果。祖先基因推斷是系統(tǒng)進(jìn)化樹重建的關(guān)鍵環(huán)節(jié)，能夠?yàn)樯飳W(xué)深層進(jìn)化模式的發(fā)現(xiàn)等很多重要問(wèn)題提供幫助，構(gòu)建進(jìn)化樹以尋找不同生物的種間同源基因和種內(nèi)同源基因，廣泛應(yīng)用于生物學(xué)、基因組學(xué)和病毒學(xué)領(lǐng)域，如對(duì)冠狀病毒基因組序列進(jìn)行溯源分析、蛋白質(zhì)和流行性疾病網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)、藥物設(shè)計(jì)等[12-16]。

基于簡(jiǎn)約方法進(jìn)行祖先基因推斷被廣泛研究。2009 年，Xu[17]提出了一種基于充分子圖（AS-Median,adequate subgraph median）的分支定界方法，基于子圖的迭代貪心搜索求解祖先基因推斷優(yōu)化問(wèn)題，但適用于小規(guī)模數(shù)據(jù)集。2015 年，F(xiàn)eij?o 等[18]提出一種基于中間基因組的系統(tǒng)發(fā)育重建算法，能夠在保持性能時(shí)花費(fèi)較低的計(jì)算成本。另一方面，計(jì)算智能由于啟發(fā)式信息的搜索特點(diǎn)[19]，也被應(yīng)用于祖先基因推斷的研究中。2013 年，Gao 等[20]提出基于遺傳算法的祖先基因推斷求解算法（GA-Median），GA-Median 主要集成了遺傳算法與基因組分類策略來(lái)推斷祖先基因。進(jìn)一步，Gao等[21]采用協(xié)同進(jìn)化遺傳算法，通過(guò)分而治之和共享初始節(jié)點(diǎn)集合的策略來(lái)提升葉子節(jié)點(diǎn)規(guī)模增大時(shí)祖先基因推斷的準(zhǔn)確性。Xia 等[22]提出基于模擬退火算法的求解方法（SA-Median），SA-Median的計(jì)算成本較低但獲取的解性能低于AS-Median和GA-Median。

圖1 IDQPSO-SA 算法的流程

面對(duì)大規(guī)模祖先基因組推斷，SA-Median、GA-Median 和 AS-Median 體現(xiàn)出不同特點(diǎn)。SA-Median 具有最低的計(jì)算開(kāi)銷，但除時(shí)間成本以外的其他性能指標(biāo)受限。此外，SA-Median 并不具有并行性，進(jìn)化搜索時(shí)由于沒(méi)有冗余和歷史信息從而搜索能力有限。GA-Median 通過(guò)生成較多的候選解從而不斷進(jìn)行解的選擇來(lái)保證所求解質(zhì)量，但GA-Median 的計(jì)算開(kāi)銷太大。AS-Median 的計(jì)算開(kāi)銷和存儲(chǔ)空間會(huì)隨著進(jìn)化事件的增加而快速增長(zhǎng)，對(duì)硬件配置的要求隨基因組規(guī)模和距離的增大而急劇上升。以上分析表明，SA-Median、GA-Median和AS-Median 的可擴(kuò)展性受限，不適用于解決大規(guī)模和距離較遠(yuǎn)的祖先基因推斷問(wèn)題。

針對(duì)祖先基因推斷應(yīng)用實(shí)例，n個(gè)基因序列包含2n n! 個(gè)祖先基因組可能性，在大規(guī)模、高維、基因組距離較遠(yuǎn)時(shí)整個(gè)搜索空間會(huì)急劇增長(zhǎng)。此時(shí)，已有的求解算法在硬件內(nèi)存、存儲(chǔ)空間、計(jì)算開(kāi)銷上都面臨一定的不足。QPSO 具備較強(qiáng)的全局搜索能力，且SA 由于突跳性能夠在一定程度上避開(kāi)局部最優(yōu)。因此，本文提出IDQPSO-SA，采用基于平均適應(yīng)度值的二次選擇更新全局平均最優(yōu)位置的策略，克服傳統(tǒng)QPSO 算法無(wú)法應(yīng)用于離散問(wèn)題的不足，將二次切割與連接（DCJ,double cut joining）排序策略引入IDQPSO-SA 來(lái)降低搜索空間大小、提升祖先基因推斷的搜索效率。

3.2 基因進(jìn)化事件與DCJ 操作

基因組由有序的帶符號(hào)的基因序列組成并表示為{g1,g2,…,gi,…,gj,…,gn}。其中，基因的正向和反向分別由g或?g表示。對(duì)于基因gi，頭部和尾部分別由表示。正向表示方向從頭到尾，而反向則表示方向從尾到頭?？紤]方向后，基因組可以是線性或圓形（當(dāng)頭和尾重合）形式。

1) 基因組進(jìn)化事件

基因組進(jìn)化事件包括倒位（inversion）、轉(zhuǎn)換（transition）、易位（translocation）、裂解（fission）和合并（fission）。采用倒位操作，則該基因組表示為{g1,g2,…,gi?1,?g j,?gj?1,…,?g i,gj+1,…,gn}。假設(shè)j＜k，并給定3 個(gè)基因序列{g i,g j,gk}，當(dāng)進(jìn)行轉(zhuǎn)換操作后則生成一個(gè)新的基因組{g1,g2,…,gi?1,gj+1,…,g k?1,gi,…,g j,gk,…,gn}。易位是指當(dāng)一條染色體的末端斷裂時(shí)，將其附加到另一條染色體的末端。裂解是指將一條染色體分裂成2 條染色體。合并是指將2 條染色體合并成一條染色體。

如果gi緊隨著gj，則定義gi和gj相鄰，2 個(gè)連續(xù)基因的鄰接（adjacenc y）具有4 種類型：。此外，當(dāng)2個(gè)基因在一個(gè)基因組中相鄰但在另一個(gè)基因組中不相鄰，且該端是末端不與任何其他基因相鄰時(shí)，則產(chǎn)生斷點(diǎn)。

2) DCJ 距離

DCJ 操作由Yancopoulos 等[23]提出，包含了所有基因組進(jìn)化事件。常見(jiàn)的DCJ 操作包含以下4 種。

DCJ 距離定義為一個(gè)基因組轉(zhuǎn)化為另一個(gè)基因組所需進(jìn)行的DCJ 操作數(shù)目。不同的DCJ 操作會(huì)影響奇數(shù)邊和環(huán)的個(gè)數(shù)，且會(huì)進(jìn)一步影響鄰接圖的結(jié)構(gòu)，基于鄰接和端的關(guān)系構(gòu)建的鄰接關(guān)系如圖2所示?；蚪MG1與基因組G2的進(jìn)化距離為

3) DCJ Median 問(wèn)題

3 個(gè)基因組定義了最小的無(wú)根二叉樹，祖先基因推斷問(wèn)題定義如下：給定3 個(gè)基因組和一個(gè)祖先基因組，若能使該祖先基因組到3 個(gè)基因組的DCJ距離之和最小化，則該祖先基因組的推斷轉(zhuǎn)化為中位基因（Median）問(wèn)題的求解。因此，祖先基因推斷問(wèn)題稱為DCJ Median 問(wèn)題。如圖3 所示，Median到給定3 個(gè)基因組的進(jìn)化距離之和為

圖2 2 個(gè)基因組的鄰接關(guān)系

給定3 個(gè)基因組G1、G2和G3，G m表示祖先基因組，那么DCJ Median 定義為3 個(gè)給定基因組到祖先基因組的距離之和S3的最小值。

圖3 DCJ Median 問(wèn)題

4) DCJ 排序策略

由于n個(gè)基因序列包含2n n! 個(gè)祖先基因組可能性，若采取窮盡搜索則計(jì)算開(kāi)銷較高，隨著數(shù)據(jù)規(guī)模的不斷增加，搜索空間快速增長(zhǎng)的問(wèn)題日益顯著。因此，若只采用IDQPSO-SA 來(lái)進(jìn)行大規(guī)模祖先基因離散問(wèn)題的推斷，則會(huì)由于計(jì)算代價(jià)過(guò)高而在一段非常長(zhǎng)的時(shí)間內(nèi)無(wú)法收斂。為了克服計(jì)算開(kāi)銷過(guò)高的不足，進(jìn)一步加速搜索進(jìn)程，本文采用DCJ 排序策略引入IDQPSO-SA 算法來(lái)求解DCJ Median 問(wèn)題（QPSOSA-Median）。

DCJ 距離定義為一個(gè)基因組轉(zhuǎn)化為另一個(gè)基因組所需進(jìn)行的DCJ 操作個(gè)數(shù)，由于不同的DCJ 操作會(huì)影響奇數(shù)邊和環(huán)的個(gè)數(shù)、鄰接圖的結(jié)構(gòu)，因此不同的DCJ 操作的進(jìn)化成本不一樣。祖先基因的推斷作為進(jìn)化重建的關(guān)鍵，其目標(biāo)是確立一個(gè)Median，其到已給定基因組的進(jìn)化距離最小。DCJ排序策略的主要思想如下。針對(duì)2 個(gè)基因組，存在多種不同的DCJ 操作來(lái)完成進(jìn)化，但是不同的DCJ操作求得的進(jìn)化距離是不一樣的。從進(jìn)化操作出發(fā)，選擇一條能夠提升搜索空間效率的方法，若所求解的祖先基因組剛好位于基因組Gi轉(zhuǎn)化為Gj的路徑上，則可以節(jié)約搜索空間，從而實(shí)現(xiàn)整個(gè)進(jìn)化成本的最小化。該策略被稱為DCJ 排序策略。本文采用的DCJ 操作都是指最優(yōu)DCJ 操作，不包括中性和反最優(yōu)操作。

3.3 基于QPSOSA-Median 的祖先基因推斷

3.3.1 QPSOSA-Median 的初始化

1) 基于DCJ 排序的種群初始化

在QPSOSA-Median 中，整個(gè)種群初始化的核心是生成一系列的候選祖先基因組。其中，初始候選解會(huì)進(jìn)一步影響QPSOSA-Median 的性能。高維時(shí)搜索空間較大，若隨機(jī)選擇一個(gè)候選祖先基因組則可能造成與真正最優(yōu)的祖先基因進(jìn)化距離非常遠(yuǎn)，從而導(dǎo)致搜索很難收斂。為此，在該QPSOSAMedian 中引入DCJ 排序策略。依據(jù)從Gi到Gj的距離產(chǎn)生6 個(gè)候選Median，然后隨機(jī)選擇一個(gè)作為QPSOSA-Median 的初始解。

2) 設(shè)定進(jìn)化成本為適應(yīng)度函數(shù)

在QPSOSA-Median 中，適應(yīng)度函數(shù)反映整個(gè)物種進(jìn)化的好壞，而且物種的適應(yīng)度值決定是否能夠在下一代進(jìn)化中被保留，其中更優(yōu)適應(yīng)度值的物種能夠以更大概率在進(jìn)化過(guò)程中生存下來(lái)。針對(duì)DCJ Median 問(wèn)題，一種有效的方法是采用進(jìn)化距離成本MS（median score）作為適應(yīng)度函數(shù)，3 個(gè)基因組與候選祖先基因組之間的DCJ 距離成本為

3.3.2 基于DCJ 排序策略的祖先基因組進(jìn)化更新

1) 基于適應(yīng)度二次選擇的全局平均最優(yōu)Median 更新

1.4 統(tǒng)計(jì)學(xué)方法 采用RevMan5.3軟件進(jìn)行數(shù)據(jù)分析。計(jì)量資料采用加權(quán)均數(shù)差(WMD)或標(biāo)準(zhǔn)化均數(shù)差(SMD)進(jìn)行分析，各效應(yīng)量均以95%可信區(qū)間(CI)表示。對(duì)納入的文獻(xiàn)進(jìn)行異質(zhì)性檢驗(yàn)，若P≥0.05，I2≤50%，則采用固定效應(yīng)模型進(jìn)行分析；若P≤0.05，I2≥50%，則采用隨機(jī)效應(yīng)模型分析。

假設(shè)種群規(guī)模為M，并且給定3 個(gè)基因組{G1,G2,G3}，候選Media n 基因組總數(shù)為M× 6 × 6，因此初始候選基因組中有36M個(gè)候選Median 基因組，隨機(jī)選擇一個(gè)并計(jì)算其到給定的3 個(gè)基因組之間的 DCJ 距離。為了提升個(gè)體的多樣性，QPSOSA-Median 采用的基于適應(yīng)度二次選擇更新平均最優(yōu)位置的策略是針對(duì)整個(gè)種群的。首先，對(duì)初始候選解的進(jìn)化距離成本進(jìn)行平均，保存小于平均進(jìn)化成本的個(gè)體，淘汰大于平均進(jìn)化成本的個(gè)體；然后，對(duì)上一輪已經(jīng)保存?zhèn)€體的進(jìn)化距離成本第二次求平均；最后，選擇與第二次求得的平均進(jìn)化成本最接近的個(gè)體作為全局平均最優(yōu)祖先基因組。該全局平均最優(yōu)祖先基因組充分體現(xiàn)了生物基因序列離散化的特點(diǎn)，也反映了整個(gè)種群的多樣性。

2) 采用DCJ 排序策略和保優(yōu)原則更新局部吸引子

QPSOSA-Median 算法中采用DCJ 排序策略指引和全局最優(yōu)位置的保優(yōu)原則更新局部吸引子。更新過(guò)程中，參數(shù)μ設(shè)為0.5，即局部最優(yōu)Median 和全局最優(yōu)Median 具有相同的權(quán)重系數(shù)。由于DCJ排序策略進(jìn)行交換和2 個(gè)比較基因組之間的目標(biāo)順序有關(guān)，目標(biāo)基因組應(yīng)選取進(jìn)化距離成本較低的基因組。由于全局最優(yōu)在任何情況下都不差于個(gè)體局部最優(yōu)，針對(duì)局部最優(yōu)和全局最優(yōu)的迭代更新過(guò)程，從pbest 到gbest 分別以距離產(chǎn)生 6個(gè)候選基因組，然后選擇最優(yōu)的一個(gè)基因組作為候選局部吸引子Pid。該單次DCJ 排序更新局部吸引子的策略能夠確保整個(gè)種群都向進(jìn)化成本最低的方向迭代進(jìn)化。

3) 采用二次DCJ 排序策略和保優(yōu)原則更新Median

祖先基因組的更新主要包含2 個(gè)階段，采用個(gè)體和平均最優(yōu)位置、局部吸引子二次保優(yōu)原則更新個(gè)體，并采用DCJ 排序策略指導(dǎo)最優(yōu)Median 基因組的搜索。在第一個(gè)階段，基于mbest 從左到右將DCJ 排序策略應(yīng)用于Xid，其中Xid表示當(dāng)前求得的Median，mbest 表示平均最優(yōu)候選Median。在第二個(gè)階段，在和Pid之間應(yīng)用DCJ 排序策略來(lái)更新當(dāng)前Median。此外，為了增強(qiáng)QPSO 的搜索能力，QPSOSA-Median 進(jìn)一步采用DCJ 排序策略來(lái)啟發(fā)式搜索Median 基因組，從當(dāng)前候選Median 到3 個(gè)給定的基因組之間隨機(jī)取樣，然后從取樣中選擇一個(gè)作為下一代的Median 基因組。

4) 采用IDQPSO-SA 算法更新Median

IDQPSO-SA 算法主要采用鑲嵌結(jié)構(gòu)，即將模擬退火算法增加到QPSO 的更新過(guò)程中，種群更新的主要思路為：在初始階段，當(dāng)QPSO 中所有個(gè)體實(shí)現(xiàn)了進(jìn)化更新后，將個(gè)體最優(yōu)Median 作為SA 的初始解；然后，針對(duì)所有個(gè)體，依據(jù)SA 的狀態(tài)產(chǎn)生函數(shù)生成新的個(gè)體，狀態(tài)接受函數(shù)以一定概率選擇接受新個(gè)體；SA 進(jìn)行退火操作，并將更新后的個(gè)體傳遞到下一輪進(jìn)行迭代；整個(gè)SA不斷迭代直至溫度達(dá)到設(shè)定的終止條件，整個(gè)IDQPSO-SA 算法的混合搜索完成。此時(shí)，全局最優(yōu)Median 則為整個(gè)IDQPSO-SA 算法推斷的祖先基因組。

QPSOSA-Median 中，每個(gè)物種分別獨(dú)立進(jìn)化，每一次進(jìn)化促使整個(gè)生態(tài)系統(tǒng)更好地適應(yīng)整個(gè)環(huán)境。隨著迭代的不斷進(jìn)化，搜索到的全局最優(yōu)解越來(lái)越接近理論意義上的祖先。當(dāng)適應(yīng)度函數(shù)評(píng)估次數(shù)達(dá)到終止條件時(shí)，整個(gè)搜索進(jìn)程停止，否則重復(fù)搜索直至收斂。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置

所有基于計(jì)算的智能算法以相同的適應(yīng)度評(píng)估次數(shù)為標(biāo)準(zhǔn)，設(shè)為300 000 次。其中，GA-Median和AS-Median僅運(yùn)行一輪，因?yàn)榛诙啻螌?shí)驗(yàn)經(jīng)驗(yàn)，GA-Median 和AS-Median 的計(jì)算開(kāi)銷較高。雖然種群規(guī)模影響QPSOSA-Median 的性能，但影響有限，且基于實(shí)驗(yàn)經(jīng)驗(yàn)，隨著種群規(guī)模的提升，計(jì)算開(kāi)銷顯著增加。因此將本文種群規(guī)模設(shè)為20。參數(shù)設(shè)置如下：QPSO 最大迭代次數(shù)和種群規(guī)模分別為1 000和20；SA 算法迭代次數(shù)為8 000，初始溫度和冷卻速率分別為10 和0.9；GA-Median 最大迭代次數(shù)為100，每個(gè)采樣步驟生成50 個(gè)基因組。

4.2 QPSOSA-Median 與SA-Median 的性能比較

為了評(píng)估QPSOSA-Median 的性能，本文主要考慮以下4 個(gè)性能指標(biāo)：進(jìn)化成本、求得的Median到真實(shí)祖先的進(jìn)化距離、鄰接準(zhǔn)確率和運(yùn)行時(shí)間。其中，鄰接準(zhǔn)確率定義為推斷的Median 基因組和真實(shí)祖先之間的交集與其并集的比值，即

其中，Acc(Gm,Gt)表示鄰接準(zhǔn)確率，Gm和Gt分別表示推斷的Median 基因組和真實(shí)祖先。

QPSOSA-Median 與SA-Median 的性能比較如表1 所示。從表1 可以看出，同SA-Median 相比，隨著進(jìn)化事件個(gè)數(shù)的增加，本文提出的QPSOSA-Median能夠取得較小的進(jìn)化成本。此外，QPSOSA-Median減少了與真實(shí)祖先之間的進(jìn)化距離，提升了鄰接準(zhǔn)確率。然而，由于QPSOSA-Median 包含多個(gè)獨(dú)立物種分別進(jìn)行搜索，計(jì)算開(kāi)銷比SA-Median 更加昂貴。此外，同SA-Median 相比，QPSOSA-Median 在大部分情況下性能都較優(yōu)，且不隨進(jìn)化事件個(gè)數(shù)的增加而增加計(jì)算開(kāi)銷，因?yàn)橛?jì)算開(kāi)銷主要和算法的收斂速度有關(guān)，QPSOSA-Median 集成了QPSO 和SA 的混合算法的全局和突跳性的優(yōu)勢(shì)更有助于收斂。綜上，QPSOSA-Median 同SA-Median 相比，能夠提升求解Median 的性能。

4.3 QPSOSA-Median與GA-Median 和AS-Median的性能比較

1) 進(jìn)化成本

進(jìn)化成本是所有指標(biāo)當(dāng)中最能反映求得的Median 基因組與真實(shí)祖先之間的關(guān)系的，進(jìn)化成本較低表示性能更優(yōu)。QPSOSA-Median、GA-Median和AS-Median 的進(jìn)化成本比較如表2 所示。對(duì)表2結(jié)果進(jìn)行分析可知，QPSOSA-Median 的進(jìn)化成本最小，AS-Median 次之，GA-Median 最大。進(jìn)一步地，同AS-Median 進(jìn)行對(duì)比分析，QPSOSA-Median和AS-Median之間的差距隨著進(jìn)化事件個(gè)數(shù)的增加而逐漸增大。從以上分析可得，QPSOSA-Median非常具有競(jìng)爭(zhēng)力。

表1 QPSOSA-Median 與SA-Median 的性能比較

表2 QPSOSA-Median、GA-Median 和AS-Media的進(jìn)化成本比較

2) 與真實(shí)祖先之間的平均進(jìn)化距離

3種算法推斷的Median基因組與真實(shí)祖先之間的平均進(jìn)化距離比較如表3 所示。從表3 可以看出，總體來(lái)看，QPSOSA-Median 在不同的基因進(jìn)化事件數(shù)時(shí)與真實(shí)祖先之間的平均進(jìn)化距離最小，AS-Median 平均進(jìn)化距離最大。當(dāng)進(jìn)化事件個(gè)數(shù)為850 和950 時(shí)，雖然QPSOSA-Median 求得的Median基因組與真實(shí)祖先之間的平均進(jìn)化距離比GA-Median 大，但是結(jié)果和GA-Median 非常接近。此外，在基因組進(jìn)化事件相對(duì)較小時(shí)，QPSOSA-Median 所求得的與真實(shí)祖先之間的平均進(jìn)化距離與GA-Median 差距較大。

表3 3 種算法推斷的Median 基因組與真實(shí)祖先之間的平均進(jìn)化距離比較

3) 鄰接準(zhǔn)確率

鄰接準(zhǔn)確率表示的是祖先基因組與真實(shí)祖先之間的交集與并集的比值，鄰接準(zhǔn)確率越大表明性能 越 好。QPSOSA-Median、GA-Median 和AS-Median 的鄰接準(zhǔn)確率比較如表4 所示。與GA-Median 和AS-Median 相比，針對(duì)不同基因進(jìn)化事件個(gè)數(shù)，QPSOSA-Median 獲取的鄰接準(zhǔn)確率優(yōu)于SA-Median 和GA-Median。此外，在基因進(jìn)化事件數(shù)目小于或等于650 時(shí)，GA-Median 最差；但當(dāng)事件數(shù)大于650 時(shí)，AS-Median 的性能最差。表4充分表明QPSOSA-Median 在鄰接準(zhǔn)確率這一指標(biāo)上具有優(yōu)越的性能。

表4 QPSOSA-Median、GA-Median 和AS-Median的鄰接準(zhǔn)確率比較

4) 運(yùn)行時(shí)間

QPSOSA-Median、GA-Median 和AS-Median的運(yùn)行時(shí)間如表5 所示。隨著基因進(jìn)化事件數(shù)量的增加，AS-Median 的運(yùn)行時(shí)間急劇增加，當(dāng)基因進(jìn)化事件為1 000 時(shí)，需要耗費(fèi)長(zhǎng)達(dá)40 h。其次，為了統(tǒng)計(jì)分析，本文生成20 個(gè)實(shí)例進(jìn)行驗(yàn)證，計(jì)算一個(gè)實(shí)例需要耗費(fèi)10 h 以上，整個(gè)實(shí)例則需要耗費(fèi)9 天。GA-Median 的計(jì)算代價(jià)太高。綜合對(duì)比，QPSOSA-Median 計(jì)算開(kāi)銷比 GA-Median 和AS-Median 低得多。

表5 QPSOSA-Median、GA-Median 和AS-Median 的運(yùn)行時(shí)間

5 結(jié)束語(yǔ)

為了解決大規(guī)模離散工程優(yōu)化面臨的高維等復(fù)雜性難題，本文提出一種結(jié)合量子粒子群優(yōu)化的全局搜索和模擬退火的概率突跳性的協(xié)同算法。首先，從目標(biāo)函數(shù)求得的適應(yīng)度值出發(fā)，提出一種基于適應(yīng)度二次選擇的全局平均最優(yōu)位置更新策略，克服傳統(tǒng)QPSO 進(jìn)化更新方法不適合離散工程優(yōu)化問(wèn)題的不足；其次，將 DCJ 排序策略引入IDQPSO-SA 來(lái)降低搜索空間大小。通過(guò)在大規(guī)模且距離較遠(yuǎn)的不同基因組進(jìn)化事件的數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文提出的算法同已有算法相比能夠取得較好的性能，這進(jìn)一步表明了本文算法的有效性和穩(wěn)定性。

盡管IDQPSO-SA 算法在不同的進(jìn)化事件下進(jìn)行測(cè)試驗(yàn)證了性能，但有許多問(wèn)題值得進(jìn)一步研究。例如，將本文提出的改進(jìn)的協(xié)同算法用于對(duì)大規(guī)模優(yōu)化問(wèn)題采用的分布式網(wǎng)絡(luò)進(jìn)行調(diào)度從而減少能耗；對(duì)初始解的選取進(jìn)行優(yōu)化和采用分布式計(jì)算來(lái)降低計(jì)算開(kāi)銷；結(jié)合計(jì)算智能算法中的搜索策略來(lái)加速搜索過(guò)程；采用深度學(xué)習(xí)來(lái)深度挖掘進(jìn)化歷史，從大數(shù)據(jù)分析的角度為大規(guī)模優(yōu)化問(wèn)題提供新的見(jiàn)解等；增加協(xié)同算法的實(shí)際應(yīng)用，如對(duì)冠狀病毒基因組序列進(jìn)行分析以溯源。