適應度二次選擇的QPSO和SA協同搜索大規模離散優化算法

張兆娟，王萬良，唐繼軍

（1.浙江工業大學計算機科學與技術學院，浙江 杭州 310023；2.天津大學智能與計算學部，天津 300050）

1 引言

近年來，海量數據資源和計算能力的提升對大數據時代網絡優化等問題產生巨大影響，傳統優化算法難以面對大規模優化問題時搜索空間急劇增長的挑戰。針對通信領域，不同的任務調度方式影響數據中心的利用率、能耗和通信網絡效果。另一方面，計算智能算法在面對大規模、復雜、高維的優化問題時，優化能力會受到限制。此時，單一算法的優化能力大大削減，但將多種算法協同能夠發揮混合算法的效率，從而提升優化的性能[1-2]。

面對大規模、高維數據情形，混合優化策略可用于特征選擇、入侵檢測、通信網絡的優化調度等領域。Gheyas 等[3]提出模擬退火（SA,simulated annealing）和遺傳算法（GA,genetic algorithm）的結合算法，可以基于GA 的全局搜索和SA 的避開局部最優能力對大規模的特征子集進行選擇。張震等[4]采用遺傳算子對粒子群算法進行了改進，并聯合禁忌搜索對入侵檢測的高維數據特征進行選擇。王晟等[5]提出一種基于遺傳算法和禁忌搜索算法混合優化的移動代理測量調度方法，用于無線傳感器網絡中移動代理派遣次序的優化調度。葉苗等[6]結合問題實際背景設計出混合人工蜂群求解算法，對無線傳感器網絡中新的最小暴露路徑問題進行求解。

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

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

2 基于適應度二次選擇的離散QPSO 和SA協同優化算法

2.1 基于適應度二次選擇的全局平均最優位置更新策略

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

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

平均最優位置更新式為

其中，M表示種群數目，f(pbesti)表示個體最優對應的適應度值，cbest 表示第一次選擇得到的平均最優位置，f(cbest)表示第一次求得的平均適應度值。

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

2.2 更新進化流程

步驟1采用個體最優和全局最優位置的保優原則更新局部吸引子。

IDQPSO-SA 中局部吸引子的進化更新采用保優原則，通過交換序列實現迭代更新。針對離散工程優化問題，交換操作是指就維度而言進行個體之間位置的交換，多個交換操作組成了交換序列。局部吸引子更新式為

其中，P id表示局部吸引子，μ表示0～1 的隨機數，pbest 表示個體最優位置，gbest 表示整個種群的全局最優，符號“⊕”表示交換pbest 和gbest 的位置。

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

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

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

其中，X id(t+1)表示個體當前位置，t表示當前迭代次數，β表示擴張?收縮因子。

步驟3采用SA 嵌入量子粒子群優化算法更新個體。

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

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

2.3 IDQPSO-SA 的實現

IDQPSO-SA 中，每個個體分別獨立進化，每一次進化促使整個種群更好地適應整個環境。隨著迭代的不斷進化，搜索到的全局最優解越來越接近理論意義上的最優。當適應度函數評估次數達到終止條件時，整個搜索進程停止；否則，重復搜索直至收斂。本文提出的IDQPSO-SA 算法的流程如圖1 所示。

3 基于IDQPSO-SA 的祖先基因推斷優化

3.1 祖先基因推斷優化問題的研究現狀

最近，全球疫情給全世界帶來了新的挑戰，而對冠狀病毒基因組序列進行分析以確定溯源具有非常大的現實意義。事實上，針對新冠病毒溯源分析，即祖先基因推斷屬于典型的離散工程優化問題。尤其在基因組數據規模擴大時，搜索空間急劇增長的問題日益顯著。本文以基因組的推斷為背景，探討大規模離散工程優化問題的協同算法效果。祖先基因推斷是系統進化樹重建的關鍵環節，能夠為生物學深層進化模式的發現等很多重要問題提供幫助，構建進化樹以尋找不同生物的種間同源基因和種內同源基因，廣泛應用于生物學、基因組學和病毒學領域，如對冠狀病毒基因組序列進行溯源分析、蛋白質和流行性疾病網絡結構預測、藥物設計等[12-16]。

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

圖1 IDQPSO-SA 算法的流程

面對大規模祖先基因組推斷，SA-Median、GA-Median 和 AS-Median 體現出不同特點。SA-Median 具有最低的計算開銷，但除時間成本以外的其他性能指標受限。此外，SA-Median 并不具有并行性，進化搜索時由于沒有冗余和歷史信息從而搜索能力有限。GA-Median 通過生成較多的候選解從而不斷進行解的選擇來保證所求解質量，但GA-Median 的計算開銷太大。AS-Median 的計算開銷和存儲空間會隨著進化事件的增加而快速增長，對硬件配置的要求隨基因組規模和距離的增大而急劇上升。以上分析表明，SA-Median、GA-Median和AS-Median 的可擴展性受限，不適用于解決大規模和距離較遠的祖先基因推斷問題。

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

3.2 基因進化事件與DCJ 操作

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

1) 基因組進化事件

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

如果gi緊隨著gj，則定義gi和gj相鄰，2 個連續基因的鄰接（adjacenc y）具有4 種類型：。此外，當2個基因在一個基因組中相鄰但在另一個基因組中不相鄰，且該端是末端不與任何其他基因相鄰時，則產生斷點。

2) DCJ 距離

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

DCJ 距離定義為一個基因組轉化為另一個基因組所需進行的DCJ 操作數目。不同的DCJ 操作會影響奇數邊和環的個數，且會進一步影響鄰接圖的結構，基于鄰接和端的關系構建的鄰接關系如圖2所示?；蚪MG1與基因組G2的進化距離為

3) DCJ Median 問題

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

圖2 2 個基因組的鄰接關系

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

圖3 DCJ Median 問題

4) DCJ 排序策略

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

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

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

3.3.1 QPSOSA-Median 的初始化

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

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

2) 設定進化成本為適應度函數

在QPSOSA-Median 中，適應度函數反映整個物種進化的好壞，而且物種的適應度值決定是否能夠在下一代進化中被保留，其中更優適應度值的物種能夠以更大概率在進化過程中生存下來。針對DCJ Median 問題，一種有效的方法是采用進化距離成本MS（median score）作為適應度函數，3 個基因組與候選祖先基因組之間的DCJ 距離成本為

3.3.2 基于DCJ 排序策略的祖先基因組進化更新

1) 基于適應度二次選擇的全局平均最優Median 更新

1.4 統計學方法 采用RevMan5.3軟件進行數據分析。計量資料采用加權均數差(WMD)或標準化均數差(SMD)進行分析，各效應量均以95%可信區間(CI)表示。對納入的文獻進行異質性檢驗，若P≥0.05，I2≤50%，則采用固定效應模型進行分析；若P≤0.05，I2≥50%，則采用隨機效應模型分析。

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

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

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

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

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

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

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

QPSOSA-Median 中，每個物種分別獨立進化，每一次進化促使整個生態系統更好地適應整個環境。隨著迭代的不斷進化，搜索到的全局最優解越來越接近理論意義上的祖先。當適應度函數評估次數達到終止條件時，整個搜索進程停止，否則重復搜索直至收斂。

4 實驗結果與分析

4.1 實驗環境和參數設置

所有基于計算的智能算法以相同的適應度評估次數為標準，設為300 000 次。其中，GA-Median和AS-Median僅運行一輪，因為基于多次實驗經驗，GA-Median 和AS-Median 的計算開銷較高。雖然種群規模影響QPSOSA-Median 的性能，但影響有限，且基于實驗經驗，隨著種群規模的提升，計算開銷顯著增加。因此將本文種群規模設為20。參數設置如下：QPSO 最大迭代次數和種群規模分別為1 000和20；SA 算法迭代次數為8 000，初始溫度和冷卻速率分別為10 和0.9；GA-Median 最大迭代次數為100，每個采樣步驟生成50 個基因組。

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

為了評估QPSOSA-Median 的性能，本文主要考慮以下4 個性能指標：進化成本、求得的Median到真實祖先的進化距離、鄰接準確率和運行時間。其中，鄰接準確率定義為推斷的Median 基因組和真實祖先之間的交集與其并集的比值，即

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

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

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

1) 進化成本

進化成本是所有指標當中最能反映求得的Median 基因組與真實祖先之間的關系的，進化成本較低表示性能更優。QPSOSA-Median、GA-Median和AS-Median 的進化成本比較如表2 所示。對表2結果進行分析可知，QPSOSA-Median 的進化成本最小，AS-Median 次之，GA-Median 最大。進一步地，同AS-Median 進行對比分析，QPSOSA-Median和AS-Median之間的差距隨著進化事件個數的增加而逐漸增大。從以上分析可得，QPSOSA-Median非常具有競爭力。

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

表2 QPSOSA-Median、GA-Median 和AS-Media的進化成本比較

2) 與真實祖先之間的平均進化距離

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

表3 3 種算法推斷的Median 基因組與真實祖先之間的平均進化距離比較

3) 鄰接準確率

鄰接準確率表示的是祖先基因組與真實祖先之間的交集與并集的比值，鄰接準確率越大表明性能 越 好。QPSOSA-Median、GA-Median 和AS-Median 的鄰接準確率比較如表4 所示。與GA-Median 和AS-Median 相比，針對不同基因進化事件個數，QPSOSA-Median 獲取的鄰接準確率優于SA-Median 和GA-Median。此外，在基因進化事件數目小于或等于650 時，GA-Median 最差；但當事件數大于650 時，AS-Median 的性能最差。表4充分表明QPSOSA-Median 在鄰接準確率這一指標上具有優越的性能。

表4 QPSOSA-Median、GA-Median 和AS-Median的鄰接準確率比較

4) 運行時間

QPSOSA-Median、GA-Median 和AS-Median的運行時間如表5 所示。隨著基因進化事件數量的增加，AS-Median 的運行時間急劇增加，當基因進化事件為1 000 時，需要耗費長達40 h。其次，為了統計分析，本文生成20 個實例進行驗證，計算一個實例需要耗費10 h 以上，整個實例則需要耗費9 天。GA-Median 的計算代價太高。綜合對比，QPSOSA-Median 計算開銷比 GA-Median 和AS-Median 低得多。

表5 QPSOSA-Median、GA-Median 和AS-Median 的運行時間

5 結束語

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

盡管IDQPSO-SA 算法在不同的進化事件下進行測試驗證了性能，但有許多問題值得進一步研究。例如，將本文提出的改進的協同算法用于對大規模優化問題采用的分布式網絡進行調度從而減少能耗；對初始解的選取進行優化和采用分布式計算來降低計算開銷；結合計算智能算法中的搜索策略來加速搜索過程；采用深度學習來深度挖掘進化歷史，從大數據分析的角度為大規模優化問題提供新的見解等；增加協同算法的實際應用，如對冠狀病毒基因組序列進行分析以溯源。