多目標協同進化算法及其應用研究

李學哲，趙美虹，唐佳佳

（蘇州科技學院電子與信息工程學院，江蘇蘇州215009）

多目標協同進化算法及其應用研究

李學哲，趙美虹，唐佳佳

（蘇州科技學院電子與信息工程學院，江蘇蘇州215009）

協同進化算法（簡稱CEA：Co-Evolution Algorithm）是通過模擬競爭與協同并存的生物進化機理來求解問題的人工智能技術，它特別適用于維數較高或結構復雜系統的優化問題。文中在多目標協同進化算法研究基礎上，設計了基于協同進化的血壓峰值并行搜索算法，通過峰值與周期信息的“相互”協同作用，使脈搏波峰值解不斷地優化，從而提高了搜索速度和準確性，同時也為血壓示波法提出了一種新的峰值檢測方法。

協同進化；適應度；多目標優化；示波法

1 協同進化系統的機理及多目標優化協同進化算法

1.1 協同進化系統的機理

達爾文進化論認為，生存競爭、優勝劣汰是生物進化的最活躍因素，而現代生物進化理論顯示，與競爭密切聯系的協同作用也是影響生物進化的重要因素，甚至在反映自然進化過程方面更全面、更準確。協同進化論是在遺傳進化論的基礎上，充分考慮了種群與環境之間、種群與種群之間的進化過程中，相互作用、相互適應、共同進化的過程。進化過程中的相互競爭與相互協同并存，相互制約與相互受益并存，這就是所謂的協同進化[1]。從信息處理角度來看，協同進化系統包含著模式識別、記憶、相互學習、反饋機制、多樣性遺傳、克隆選擇、自適應和分布式處理等多種控制機理，以及各機理之間的網絡化的信息傳遞。由此可見，協同進化系統是一種具有高度并行、分布式和自適應特點的信息處理學習系統。生物學證據表明：協同進化能夠大大加快生物進化的歷程，因此，借鑒協同思想的進化算法具有巨大的優越性，對于解決維數較高或結構復雜的系統優化問題效果非常顯著，而這種計算機理為人類提高信息處理技術水平，提供新的概念、理論和方法。

1.2 協同進化算法和多目標優化協同進化算法

自20世紀50年代中期創立了仿生學以來，人們從生物進化的機理中受到啟發，提出了許多用以解決復雜優化問題的方法。如蟻群算法、協同進化算法等。其中，協同進化算法（Co-Evolutionary Algorithm CEA）就是基于自然協同進化論而發展起來的新型現代智能算法，是近年來針對進化算法的不足而興起的一個研究熱點[2]。協同進化算法在進化算法的基礎上，充分考慮了種群與環境之間的競爭、種群與種群之間的進化過程中協調。借鑒自然界中不同生物種群之間相互作用、相互適應、協同進化的過程，協同進化算法把一個復雜的問題分解為若干個相對簡單的子問題，分配給多個子群體分別進行進化操作，子群體之間定期進行信息的交互，通過合作或競爭的關系，共同協調完成對問題的求解，因此，它特別適用于維數較高或結構復雜系統的優化問題。

多目標優化（multi-objective optimization）是工程應用和科學研究方面的重要研究課題形式之一，實際中各子目標之間往往是相互沖突，照顧了一個子目標的“利益”，必然會導致其他至少一個子目標的“利益”受到損失，由此可見，對多個目標優化問題實際上不可能存在絕對的或者是唯一的最優解，而是存在一個折衷解的集合，稱為Pareto最優解集。因此，求解多目標優化問題的關鍵就是使新一代的非支配集不比上一代差，如此進化使得群體的非支配集不斷地逼近真正的最優邊界（True Pareto Optimal Front），最終得到Pareto解集中的一個或多個滿意解。

通常，多目標優化問題一般可表述為由n個決策變量，M個目標函數和K種約束條件組成，最優化目標用下式表示

式中，X=（x1，x2，…，xn）∈D為決策向量；y=（f1，f2，…，fn）∈Y表示目標向量；D為決策向量形成的決策空間；Y為目標向量形成的目標空間。

近年來，從協同進化機理出發衍射出了多種協同進化算法，多目標優化協同進化算法（MOCEA）就是其中之一。它利用協同進化算法為多目標優化問題尋找Pareto最優解集，此算法除了具有進化算法的克隆選擇、群體多樣性和自我濃度調節等功能外，還設計了體現協同計算的協同算子（合作、吞并和分裂算子），使得進化計算在保持種群的多樣性的同時，又實現了帶有“方向性”的搜索，因此，該算法具有很強的并行搜索能力、較快收斂速度、群體規模動態調整、Pareto最優個體保存于群體外并不斷更新等特點，能在很大程度上克服基于權重系數的多目標進化算法的許多缺點。相對于其他多目標搜索算法而言，MOCEA是一種“廣”、“優”俱佳的智能算法。首先，MOCEA利用克隆選擇、突變和協同算子“有方向”地增強群體多樣性，隱含著較強的隨機、并行全局搜索能力和加快多目標進化算法的收斂速度；其次，通過記憶、聚類算法、濃度控制、克隆抑制、免疫選擇等操作機理的相互作用，在群體協同進化中實現了非支配解集不斷地優化過程；第三，可以通過約束條件避免非法解的出現，保證了最優解的“合法性”。

2 多目標協同進化算法的應用設計

血壓是檢查和評價血管系統功能的重要指標，在血壓測量儀器中，絕大多數無創血壓計和血壓Holter都采用示波法[3]。示波法測量的關鍵技術在于脈搏波峰值的識別，其主要原理是必須精確識別出各個脈搏波的峰值，進而擬合出峰值的包絡曲線，依據波形特征法或幅度系數法分別確定出所對應的收縮壓和舒張壓[4]，脈搏波的峰值識別算法對血壓測量的準確性起到了關鍵的作用。現有血壓計的脈搏波的判別技術和校正方法不盡相同，主要有最大上升斜率判別法、比值判別法、拐點判別法等[3]。這些方法是以時間順序、串行、局部地檢測峰值，方法比較簡單，誤差較大，文中在基于免疫算法的脈搏波分析與處理方法研究的基礎上[5]，首次提出了利用協同進化算法的脈搏波峰值函數優化方法，它為無創血壓的測量增添了新的技術手段。

協同進化算法是一種隨機、并行的全局搜索方法，已逐漸成為解決多目標優化問題的新興而有效的工具[6]。文中提出了基于MOCEA的脈搏波峰值識別算法，它是用脈搏波峰特征值和脈搏波的周期作為優化指標，利用兩指標的協同進化，實現了全局的快速并行搜索和局部的優化搜索，使之比現有脈搏波峰值搜索方法具有更多的優點。

2.1 脈搏波峰值和周期特征指標的計算

2.1.1 脈搏波峰特征值的計算脈搏波峰特征值用下式表示

式中：p_value（xi）表示峰值函數，praise（xi）為獎勵函數，punish（xi）為罰函數。

p_value（xi）值是通過計算i點附近范圍內的差分值來實現的，計算公式如下

式中，NC為差分點個數，λ1為權重系數，其中

獎勵函數praise（xi）是根據脈搏波的特點（前沿很陡，后沿較平緩）和脈搏波幅值的不同，對i點一定范圍（上升半徑）內用斜率值來計算的，其計算方法如下：

Step1：計算第i個點的幅值與脈搏波的最大值的比值，它乘以脈搏波的上升時間的最小閾值得到本個波的上升半徑。

Step2：在第i個點的前后上升半徑內，均勻各取出d個點，計算這2d個點與i點之間的直線斜率。

Step3：在前d點中，比較斜率大于0的點的斜率，得到最大斜率kb_max，如果kb_max＞k閾值，則mi=1，否則為kd/k閾值。

Step4：判斷后d個點的斜率，如果其中有一點與i點斜率大于0，則ni=0，否則為1。

Step5：praise（xi）=mi×ni×λ2（λ2為權重系數）。

罰函數punish（xi）是對不符合約束條件的點，實施懲罰。比如測量時，由于患者手臂的運動等各種原因產生的干擾波形，它的特征與正常的脈搏波不同，因此，對于不滿足約束條件的干擾數據，可使用罰函數對其進行剔除。

2.1.2 周期特征值的計算周期指標值用下式表示

式中：Tp表示本峰值點對前后（q+r）/2個相臨峰值點的平均周期；Tp，i表示本峰值點對之前后（q+r）/2個峰值點的周期；N為計算峰值點的周期個數。Cp，j表示p峰值點與j峰值點之間的谷點個數（上述峰值點均指準峰值點）；Ts表示采樣周期。因此，可以用周期指標σ來評價峰值點的周期指標優劣。

2.2 個體適應度計算

由Zitzler[8-9]提出的適應度賦值方法確定個體的適應度，具體描述如下：設當前種群Pt的大小為N。

（1）標識種群Pt中的Pareto最優解集p（Pt），并計算任意i∈p（Pt）的適應度

其中，j為Pt中的任意個體。

（2）計算Ptp（Pt）中每個個體的適應度

相應的選擇方法為：①隨機從Pt中選出兩個個體i，j；②如果F（i）＜F（j），則令Pt+1←Pt+1+｛i｝，否則Pt+1←Pt+1+｛j｝。

2.3 基于協同進化算法的血壓峰值搜索算法

血壓峰值搜索算法有周期和峰值兩個目標函數，在下述算法中設立pa、pb兩個種群，其大小均為N；Oa和Ob分別為對應種群的Pareto最優解集；外部集，大小為，Pm為變異概率。具體峰值搜索計算方法如下：

Step4：采用2.2節中個體適應度計算方法分別計算種群中每個個體的適應度，并選出新的種群。

3 協同多峰值尋優算法測試結果

圖1是利用上述算法對血壓峰值的并行搜索結果，可以看出從初始種群開始，通過個體所攜帶的峰值與周期信息的“相互”協同作用，保證了無論是針對群體多樣性的交叉變異操作，還是個體之間的“協作”進化等操作都有著明顯的“方向性”，使脈搏波峰值的解不斷地優化，從而加快收斂速度，體現了協同進化的優越性[4]。

圖1 協同進化算法對脈搏波多峰值尋優結果

4 結語

文中在協同算法理論研究的基礎上，將協同進化計算與血壓峰值檢測具體應用相結合，設計了基于協同進化算法的血壓峰值搜索算法。該算法具有并行、全局搜索之特點，克服了傳統血壓串行、局部搜索峰值算法的不足，為示波法血壓測量技術提出了一種新的峰值檢測方法。該方法對多峰值識別準確，在速度和精度等方面都有著明顯的優點。毋庸置疑，隨著協同進化算法的不斷發展，必將被廣泛地應用于工程技術、管理科學和社會科學等各領域，它具有廣闊的應用前景。

[1]戚玉濤，劉芳，任元，等.基于合作模型的協同免疫多目標優化算法[J].電子學報，2014，42（5）：858-867.

[2]張勰，趙嶷飛，劉宏志，等.基于協同進化遺傳算法的航班進港優化調度[J].交通運輸系統工程與信息，2014，14（2）：94-101.

[3]甄斌，周永進，王素品，等.示波法血壓測量的實現與討論[J].生物醫學工程學雜志，1999，16（1）：42-45.

[4]張政波，吳太虎.無創血壓測量技術與進展[J].中國醫療器械雜志，2003，27（3）：196-199.

[5]李學哲.基于MOIA的脈搏波峰值并行搜索的研究[J].計算機工程與應用，2007，43（15）：246-248.

[6]焦李成，劉靜，鐘偉才.協同進化計算與多智能體系統[M].北京：科學出版社，2006.

[7]Zitzler E，Thiele L.Evolution Algorithms for Muti-objective Optimization：Methods and Application[M].Zurich：Swiss Federal Institute of Technology，1999：114.

[8]Zitzler E，Thiele L.Evolutionary algorithms：a comparative case study and the strength pareto approach[J].IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271.

[9]黃席樾，張著洪.基于免疫應答原理的多目標優化免疫算法及其應用[J].信息與控制，2003，32（3）：209-213.

Multi-objective co-evolutionary algorithm and its application

LI Xuezhe，ZHAO Meihong，TANG Jiajia
（School of Electronic&Information Engineering，SUST，Suzhou 215009，China）

Co-evolutionary algorithm is used to solve the problem by simulating the competition and collaborative coexistence mechanism of biological evolution of artificial intelligence technology.It is particularly suitable for high dimension or structural optimization of complex systems.On the basis of multi-objective co-evolutionary algorithm，this paper designed a blood pressure peak parallel search algorithm based on co-evolution.Through the synergy between peak and period information，the peak pulse wave continuously optimizes the solution，thereby improving the search speed and accuracy.We also proposed a new method for detecting the peak oscillometric method of blood pressure.

co-evolution；fitness；multi-objective optimization；oscillographic method

TP274

A

1672－0687（2015）03－0043－04

責任編輯：艾淑艷

2014－12－14

蘇州科技學院院科研基金資助項目（Z1325）

李學哲（1965-），男，北京人，副教授，研究方向：計算機控制，醫療電子儀器，數控系統。