SIR-DNA傳染病動力學優化算法*

陸秋琴，黃光球

西安建筑科技大學 管理學院，西安 710055

1 引言

DNA計算[1]是利用DNA雙螺旋結構和堿基互補配對規律進行信息編碼，將要運算的對象映射成DNA分子鏈，通過生物酶的作用，生成各種數據池，再按照一定的規則將原始問題的數據運算高度并行地映射成DNA分子鏈的可控的生化反應過程，然后利用分子生物技術，檢測所需要的運算結果[2]。

DNA計算包括分子內DNA計算[3]、分子間DNA計算[1]和超分子DNA計算[2]。分子內DNA計算借助于分子內的形態轉移操作，用單DNA分子構建可編程的狀態機[3]；分子間DNA計算集中在不同DNA分子間的雜交反應，使其作為計算中的一個基本步驟[1]；超分子DNA計算是利用不同序列的原始DNA分子的自裝配過程進行計算[4-5]。

DNA計算利用DNA反應的強大并行計算能力，已成功地解決了許多NP難題。吳帆等人[4]提出了一種基于DNA自組裝模型來求解N皇后問題的DNA計算方法，該算法降低了生化解的錯誤率。李肯立等人[5]通過引入DNA自組裝模型，提出了一種求解最大團問題的DNA計算方法，該算法給出了DNA分子的編碼方案及結果檢測的實驗方法。姚慶安等人[6]提出一種基于k-臂分子和粘貼計算求解最短路徑問題的DNA計算模型。徐京雷等人[7]提出了一種基于改進的閉環模型求解TSP問題的DNA算法，該算法能在較低的時間復雜度內解決TSP問題。馬瑩等人[8]將著色問題轉化為求最大獨立集問題，然后通過質粒DNA分子生物實驗得到最大獨立集，證明了該質粒DNA算法有效并且是可行的。吳雪等人[9]針對最大匹配問題，應用DNA粘貼計算模型尋求該問題最優解的生物操作過程，實例表明該算法是可行的。

目前，DNA計算的大量研究還停留在紙面上，很多設想和方案沒有條件付諸實驗[2]，對維數較高的優化問題的求解還存在一些困難。為解決此問題，本文從一個新的角度提出了一種新的DNA算法。本文算法依據一種傳染病在一個生態系統中傳播的場景構造而得，該生態系統中動物被感染后，傳染病攻擊該動物的某些DNA片斷，從而導致該動物具有類似遺傳病的缺陷。本文算法不需依賴生物實驗即可進行優化計算。

在現實世界，人群中經常爆發的很多傳染病均可用KM倉室建模方法[10-11]描述。傳染病在個體之間的傳播，使得個體之間的相互作用關系體現得淋漓盡致；一種傳染病攻擊的是人類個體的少部分器官，將該現象映射到對優化問題的求解，就是每次處理的變量個數只是全部變量的極少部分。因此，該算法具有求解高維問題的天然優勢。為簡單起見，本文利用SIR疾病傳播場景來說明本文的思路，所提出的優化算法稱為SIR-DNA算法。

2 SIR-DNA算法設計

考慮優化問題：

式中，Rn是n維歐氏空間；X=(x1,x2,…,xn)是一個n維決策向量；H為搜索空間，又稱解空間；f(X)為目標函數；gi(X)≥0為第i個不等式約束條件，i=1,2,…,I，I為不等式約束條件個數。目標函數f(X)和約束條件gi(X)不需要特殊的限制條件。

把優化模型式（1）中約束條件所形成的可行解空間設想成一個生態系統ES。假設ES包含有N個動物，每個動物稱為一個個體，這些個體的編號是1,2,…,N。有一種傳染病Z在該生態系統中傳播，動物被感染后，傳染病Z攻擊該動物的某些DNA片斷，從而導致該動物具有類似遺傳病的缺陷。在現實世界，HIV、天花、SARS、寨卡等傳染病毒就是這樣的病毒。

2.1 動物個體DNA分子

動物的每條染色體攜帶一個DNA分子，DNA是由分別帶有4種堿基A、T、C、G的脫氧核苷酸鏈接組成的雙螺旋長鏈分子。在這條雙螺旋的長鏈中，共有約30億個堿基對，而基因則是DNA長鏈中有遺傳效應的一些片段。在組成DNA的數量浩瀚的堿基對中，有一些特定位置的單個核苷酸經常發生變異引起DNA的多態性，人們稱之為位點。染色體、基因和位點的結構關系如圖1所示。在DNA長鏈中，位點個數約為堿基對個數的1/1 000。由于位點在DNA長鏈中出現頻繁，多態性豐富，近年來成為人們研究DNA遺傳信息的重要載體。大量研究表明，動物的許多表型性狀差異以及對傳染病毒的易感性等都可能與某些位點相關聯，或和包含有多個位點的基因相關聯。

Fig.1 Structure of chromosomes,genes and loci圖1 染色體、基因和位點的結構關系

對于ES中的每個動物個體，采用A、T、C、G的編碼方式來獲取每個位點的信息，因為染色體具有雙螺旋結構，所以用兩個堿基的組合表示一個位點的信息，如表1所示。表1中，在位點rs100015位置，不同樣本的編碼都是T和C的組合，有3種不同編碼方式TT、TC和CC。類似地，其他位點雖然堿基的組合不同，但也只有3種不同編碼。

Table 1 Loci name and loci alleles of DNAfragments表1 DNA片段位點名稱和位點等位基因信息

在ES中，傳染病Z攻擊的是動物個體W個特殊基因中某些位點，這些特殊基因稱為致病基因，而這W個致病基因均由R個位點組成，其編號為1,2,…,R；每個位點均由3個堿基對組成。對于不同的動物個體，傳染病Z攻擊的是W個致病基因中的哪些基因完全是隨機的；若某個致病基因被攻擊，組成該基因的R個位點中的哪些位點受到攻擊也完全是隨機的。染病個體治愈后會獲得短期免疫力，與免疫相關的特殊基因也有W個，這些特殊基因稱為免疫基因，每個免疫基因也包含R個位點；愈后個體在哪些免疫基因中的哪些位點獲得免疫，也是完全隨機的；雖然個體在不同免疫基因的不同位點上獲得免疫力，但是免疫效果都是一樣。為計算處理方便，將A、T、C、G采用二進制編碼分別表示為00、01、10、11。

2.2 SIR模型轉換成個體類別轉換方程

將ES中的動物群分成易感者類（S）、染病者類（I）和治愈者類（R）。易感個體一旦與染病者接觸，就會因感染而變成染病者；染病者經過治療后會成為治愈者；治愈者能夠獲得暫時的免疫，但免疫喪失后又會變成易感者。假設該傳染病不是惡性的，故在一個時間段內，該傳染病不會造成動物死亡；此外，不考慮該時間段內個體的出生、死亡、遷入和遷出。故可假設該ES中的動物個體數N為常數。若傳染病的發生率是飽和接觸率，則基于KM經典的假設[10-11]，該生態系統可用SIR傳染病模型描述[12]，如圖2所示，其數學模型為式（2）所示。

式中，β為動物種群飽和接觸傳染率；γ為治愈系數；α為免疫喪失率；S(t)、I(t)、R(t)分別為時期t易感者、染病者和治愈者的占比。

Fig.2 Bin structure of SIR epidemic model圖2 SIR傳染病倉室結構

因S(t)+I(t)+R(t)=1，S(t)、I(t)和R(t)實際上描述了一個概率分布，故對任意一個個體來說，S(t)、I(t)、R(t)相當于該個體屬于易感者類、染病者類和治愈者類的概率，不妨將其分別稱為易感概率、染病概率和治愈概率。因此，式（2）實際上是計算任意一個個體在時期t的屬于易感者類、染病者類和治愈者類的概率的方程。為快速計算起見，將式（2）寫成遞推形式，并注意到式（2）中有一個方程是多余的，可以去掉，故對于個體i來說，有：

在時期t，采用式（3）計算出個體i的Si(t)、Ii(t)和Ri(t)。顯然，在某個時期，任何一個個體只能處于S類、I類和R類中的某一個類。于是，個體i在時期t處于S類、I類和R類3個類別中的哪個類，可由Si(t)、Ii(t)和Ri(t)所決定的概率分布確定。表2中所列情況符合圖2描述的SIR模型的類別轉換情形。

Table 2 Legal class transfer of SIR epidemic model表2 SIR傳染病模型的合法類別轉換

既然優化問題式（1）的可行解空間與ES相對應，那么該ES中一個個體對應于優化問題式（1）的一個可行解，N個個體所對應的可行解集就是：

個體i的特征j對應于可行解Xi中的一個變量xij，j=1,2,…,K+n。因此，個體i與可行解Xi是等價概念。個體的體質強弱用體質指數IPI來表示，IPI指數對應于優化問題式（1）的目標函數值。好的可行解對應具有較高IPI值的個體，即體質強壯的個體，差的可行解對應具有較低IPI值的個體，即體質虛弱的個體。個體i的IPI指數計算方法為：

2.3 基因表達設計

在ES中，因動物個體的種類相同，故對于不同的個體，傳染病毒Z攻擊的W個特殊基因是相似的（如圖3（a）所示），但不會相同，該特殊基因組稱為致病基因組；這W個致病基因被攻擊后發生改變，就會使動物患病。類似地，對于同種動物個體，能夠對傳染病毒Z免疫的W個免疫基因是類似的，但不會相同，該基因組稱為免疫基因組，如圖3（b）所示；對于同種動物中的不同個體，傳染病被治愈后，這W個免疫基因會發生變化，會使動物獲得免疫。免疫基因組和致病基因組是不同序列的基因組。

因動物個體之間存在差異，故傳染病毒攻擊致病基因組中的哪些致病基因，以及若一個致病基因被攻擊，則該致病基因中的哪些位點發生改變，則完全因人而異。同理，當動物個體染病后被治愈并獲得短期免疫力，但該個體在免疫基因組中的哪些免疫基因，以及若一個免疫基因獲得免疫力，則該免疫基因中的哪些位點發生改變，完全因人而異。

傳染病毒Z攻擊動物個體的致病基因組和免疫基因組序列分別為：

式（5）、（6）中的基因Di、Vi，i=1,2,…,W，均由R個位點組成，即：

因每個動物個體是不相同的，故組成每個基因的位點是不相同的，從而對不同的動物個體來說，式（7）中的取值是不相同的，每個位點的取值均是從A、T、C、G中任取兩個進行組合。例如，假設X和Y是某個位點的堿基對，則可能的組合只有XX、XY、YY3個。若用二進制表示，則每個基因的總長度是12R個比特，而W個基因序列的總長度是12RW個比特。

2.4 基因表達與變量的對應關系設計

模型式（1）中的未知數變量有n+K個，其中n=|H|為實數變量個數，K=|D|為0、1整數變量個數。顯然，取W=n+K。于是，W個基因被傳染病毒Z攻擊，等價于n+K個未知數變量被處理。特別注意，傳染病毒Z每次只選擇幾個基因實施攻擊，此意味著每次只需處理n+K個未知數變量中的幾個變量，于是達到了天然降維的目的。

W個致病基因被攻擊后發生改變，在外顯特征上，動物個體會表現出一些奇特的特征，如艾滋病人的免疫喪失，麻風病人臉上出天花，SARS病人呼吸窘迫等。然而，在SIR-DNA算法中，將動物個體的外顯特征解釋為個體性狀，而一種個體性狀對應著模型式（1）的一個可行解。由所有個體性狀組成的表稱為個體性狀表，如圖4（a）所示。

Fig.3 Gene expression before and after immunization and individual animals are infected圖3 動物個體被傳染病毒攻擊前后和獲得免疫前后的基因表達

Fig.4 Corresponding relation between W disease-causing and immune-causing genes and W variables圖4 W個致病基因和免疫基因與W個變量的對應關系

從外顯特征看，若一個動物個體染上傳染病Z，也獲得對傳染病Z的免疫，該個體屬于S類；若一個動物個體染上傳染病Z，即其致病基因發生改變，該個體屬于I類；若一個動物個體染上傳染病Z后被治愈，即其致病基因復原，其免疫基因發生改變，該個體屬于R類。

圖4描述了W個致病基因（如圖4（b）所示）、W個免疫基因（如圖4（c）所示）與W個變量的對應關系。圖4（a）中，每個圓點代表一個位點；前n個為基因對應n個實數型變量；后K個為基因對應K個0-1整數型變量。每個基因上選擇一個圓點，并組成一種個體性狀，它對應著動物個體的一種外顯特征。在本算法中，一種個體性狀對應著一個可行解。例如，圖中的所有黑點組成一個可行解。于是，對模型式（1）的求解最終轉化為在圖4（a）所示的各種離散點組合中，找出使模型式（1）的目標函數值達到最小的可行解，此為要尋找的全局最優可行解。

當傳染病毒Z發起對動物個體的攻擊時，因為該傳染病毒每次只選擇幾個基因實施破壞，例如圖4中傳染病毒Z在一次攻擊中只選擇基因1、基因2和基因n+1實施破壞，故只需對基因1、基因2和基因n+1所對應的變量進行處理即可。

由于一個位點只有12比特寬，要想獲得非常高精度的可行解，一個基因所包含的位點數為必需滿足212R≥Mr，即R≥(lbMr)/12。一般情況下，當R=1,2,3時，可以獲得10-4、10-7、10-10級別的精度。

模型式（1）中的變量既包含實數變量，又包含整數變量，其各值的編碼方法如下所述。

（1）實變量編碼方法

式中，ω為權重；δj稱為變量偏差，該值是從下列集合中選擇：

（2）整數變量編碼方法

K個0-1整數變量，可以直接采用的編碼方法。

2.5 演化算子設計

對圖2進行分解，存在下列兩種情況：

情況1在時期t，個體從類別A轉移到類別C，如圖5（a）所示，其中A,C∈{S,I,R}，但A≠C。大量的個體類別轉移都屬于這種情況。例如S→I、I→R、R→S等。

Fig.5 Two classes transfer of an individual at time t圖5 時期t個體的兩種類別轉移情形

為了能使某個體從類別A轉移到類別C，將已處于類別C的若干其他個體的某些基因上的位點傳給該個體的對應位點，也即使該個體的對應位點具有類別C的個體的基因上的位點。此舉實現了該個體從類別A轉移到類別C。例如，對于S→I轉移，將已處于I類的若干個體的某些基因上的位點傳給處于S類的某個體，即可使其感染上傳染病，即實現了S→I轉移。

情況2在時期t，當個體處于某個類別A時，A∈{S,I,R}，并沒有發生類別轉移，即相當于A→A，如圖5（b）所示。圖2中的每個節點隱含了圖5（b）所示的情形，例如S→S、I→I和R→R。

當某個體處于類別A時，為了能使該個體向好的方向發展，但其類別又保持不變，將已處于同樣類別A，但其IPI指數要高于該個體IPI指數的若干個強壯個體的某些基因上的位點傳給該個體的對應基因上的位點，也就是將IPI指數高的強壯個體向IPI指數低的虛弱個體傳遞強壯基因的信息，使得這些虛弱個體能向好的方向發展。

從易感、發病和治愈的個體中分別隨機挑選出L個個體，L≥1，u∈{S,I,R}，這些個體的IPI指數要高于當前個體i的IPI指數，分別形成強壯易感者集合、染病者集合和治愈者集合CPu={Xj1(t),Xj2(t),…,XjL(t)}。

（1）S-I算子設計。設當前易感個體i被感染，變為染病者，其類別從S→I，操作步驟如下：

（1.1）從W個致病基因中以概率p(p＜E0)隨機挑選出若干個致病基因，E0表示個體的致病基因被選中的最大概率，即基因被病毒攻擊的最大概率。

（1.2）若致病基因j被選中，則：

（1.2.1）從致病基因j的R個位點中隨機選出一個位點k與Y進行異或運算，記錄Inf(i,1)=j，Inf(i,2)=k。其中，若j≤n，則Y=111111；若n＜j≤n+K，則Y=1。此操作表示傳染病Z攻擊個體i的DNA。此步驟稱為基因位點操作。

（1.2.2）從強壯染病者集合CPI中隨機挑選出一個個體s，將其對應性狀表中的第j列的狀態值傳給個體i。如圖6所示，個體i的第j個致病基因原來的狀態值vi轉變為個體s的第j個致病基因原來的狀態值vs。該步驟相當于染病者傳播病毒信息給易感者。此步驟稱為個體性狀操作。

Fig.6 State value vitransferring into vsof the j th disease gene of individual i圖6 個體i的第j個致病基因狀態值vi變為vs

（2）I-R算子設計。設當前染病個體i被治愈，變為治愈者，其類別從I→R，操作步驟如下：

（2.1）將個體i的所有發生變異的致病基因位點進行復原，即查找個體i的Inf(i,1)和Inf(i,2)，找到個體i的發生變異的致病基因和位點，將其與Y再次進行異或運算，即可實現復原。

（2.2）從W個免疫基因中以概率p(p＜F0)隨機挑選出若干個免疫基因，F0表示個體的免疫基因被選中的最大概率，F0=E0。若免疫基因j被選中，則：

（2.2.1）從免疫基因j的R個位點中隨機選出一個位點k與Y進行異或運算，記錄Rec(i,1)=j，Rec(i,2)=k。其中，若j≤n，則Y=111111；若n＜j≤n+K，則Y=1。此操作表示治愈者獲得免疫。

（2.2.2）從強壯染病者集合CPR中隨機挑選出一個個體s，將其對應性狀表中的第j列的狀態值傳給個體i。如圖6所示。該步驟相當于強壯治愈者將其免疫信息傳給染病者，使其治愈并獲得免疫。

（3）R-S算子設計。設當前治愈者個體i失去免疫力，變為易感者，其類別從R→S，操作步驟如下：

（3.1）將個體i的所有使其獲得免疫力的免疫基因位點進行復原，即查找個體i的Rec(i,1)和Rec(i,2)，找到個體i的使其獲得免疫力的免疫基因和位點，將這些免疫基因位點與Y再次進行異或運算，即可實現復原，從而使其喪失免疫力。

（3.2）從W個免疫基因中以概率p(p＜F0)隨機挑選出若干個免疫基因，若免疫基因j被選中，則從強壯易感者集合CPS中隨機挑選出一個個體s，將其對應性狀表中的第j列的狀態值傳給個體i。如圖6所示。該步驟相當于強壯易感者將其易感信息傳給治愈者，使其治愈并喪失免疫力。

（4）S-S算子、I-I算子、R-R算子設計。因這3個算子不存在類別轉換，故不進行基因位點操作，但要進行個體性狀操作。這3個算子的設計方法類似，其設計方法為：設當前個體i的類別為u，u∈{S,I,R}，從個體i的W個基因中以概率p(p＜E0)隨機挑選出若干個基因，若基因j被選中，則從該類別的強壯者集合CPu中隨機挑選出一個個體s，將其對應個體性狀表中的第j列的性狀值傳給個體i。如圖6所示。該步驟相當于強壯者將其特有的信息傳給當前個體i，使該個體變為更強狀態。此操作相當于弱者向強者學習，使自身變強壯。W個基因選擇方法是：若u=S，則選W個未染病的致病基因；若u=I，則選W個已染病的致病基因；若u=R，則選W個已免疫的免疫基因。

（5）生長算子設計。個體i的生長算子可以描述為：

式中，Vi(t)是Xi(t)的一個副本，用于臨時保存Xi(t)的值；Xi(t)=(xi1(t),xi2(t),…,xin(t))；函數IPI(Vi(t))和IPI(Xi(t))按式（4）計算。

2.6 SIR-DNA算法構造方法

算法1 SIR-DNA算法

（1）初始化：①令時期t=0，最大迭代次數G=108，N=100～200，精度ε=10-8，R=3～5，L=3～ 5，F0=E0=0.000 1～0.01；②初始化N個正常個體X1(0),X2(0),…,XN(0)；③在N個正常個體中隨機選擇30%的個體使其致??；④在剩下的正常個體中隨機選擇30%的個體使其獲得免疫力。

（2）計算ai=Rand(0,1)，bi=Rand(0,1)，ci=Rand(0,1)；Si(0)=ai/(ai+bi+ci)，Ii(0)=bi/(ai+bi+ci)，Ri(0)=1-Si(0)-Ii(0),i=1,2,…,N。

（3）計算個體i的SIR類別：SIRi(0)=GetSIR(Si(0),Ii(0),Ri(0))，i=1,2,…,N；函數GetSIR()用于確定個體i將處于何種類別。

（4）執行下列操作：

（5）結束。

函數GetSIR(pS,pI,pR)的定義如下：

2.7 SIR-DNA算法的降維特征的理論分析

將式（1）的目標函數展開成如下形式：

SIR-DNA算法的求解過程最終歸結為不斷修改變量x1,x2,…,xn的取值，使得目標函數值A不斷向理論最優解靠近。在演化過程中，n個變量中的每個變量取值的修改過程是相互獨立的；當一個變量的取值被修改后，只能使目標函數值A向3個方向變化：比當前值更好，比當前值更差，與當前值一樣。不妨假定這3種情形出現的概率相同，均為1/3。假設SIR-DNA算法每次進化有m個變量的取值同時改變，則能使目標函數值A向好的方向改變的概率為p=1/3m。

顯然，當m=n時，即每次進化時n個變量的取值同時改變，此時能使目標函數值A向好的方向發展的概率最低，即p=3-n。因此，每次進化時同時對n個變量的取值進行更新是最不可取的策略，該策略既耗時，又使目標函數值A向好的方向發展的概率達到最低。

另一方面，當m=1時，即每次進化時只修改1個變量的取值，此時能使目標函數值A向好的方向發展的概率最大，即p=1/3。因此，每次進化時只對1個變量的取值進行更新是可取的策略，該策略能使A向好的方向發展的概率達到最大。

上面的分析給出了SIR-DNA算法在求解過程中每次處理變量數的一般規律，這是一個普適規律。然而，由于求解過程的復雜性，每次只修改1個變量的取值不一定性能最佳，但一般規律是：無論n多大，每次參與運算的變量數都不要超過10個，即1≤nE0＜10。

上述分析表明，SIR-DNA算法具有天然降維特征。

2.8 SIR-DNA算法時間復雜度

SIR-DNA算法的時間復雜度如表3所示。

Table 3 Time complexity of SIR-DNA表3 SIR-DNA算法的時間復雜度計算表

2.9 SIR-DNA算法收斂性和穩定性分析

從S-S、S-I、I-I、I-R、R-R、R-S算子的定義可知，任何一個試探解的新一代的生成只與該試探解的當前狀態有關，而與該試探解以前是如何演變到當前狀態的歷程無關，因而SIR-DNA算法的演化過程具有Markov特性。因老的試探解無需保留，故可以使算法的空間復雜度降到最低。

從生長算子的定義可知，若從當前位置出發，下一步搜索方向只有兩個，即要么向比當前位置更好的方向搜索，要么留在當前位置不動。因此，SIRDNA算法具有“步步不差”的搜索特征。

由于SIR-DNA算法的演化過程具有Markov特性和“步步不差”特性，根據文獻[13]可得如下定理。

定理1 SIR-DNA算法具有全局收斂性。

SIR-DNA算法的穩定性依賴于SIR傳染病動力學模型的解的穩定性，即微分方程組（2）的解的穩定性。文獻[12]給出了該模型的解保持全局穩定性的條件，本文不再贅述。于是，SIR傳染病模型可以幫助SIR-DNA算法選擇最合理的參數實現穩定收斂。

3 SIR-DNA算法與其他算法比較

本文使用CEC2013[14]所提供的國際上通用的基準函數來測試SIR-DNA算法的性能，本文選擇的6個基準函數，如表4所示。在表4中，O是一個n維決策向量。這里用SIR-DNA算法去求解表4所示的基準函數，其參數是n=50，N=200，O的值隨機產生。選擇7種優化算法與SIR-DNA算法進行比較，這些算法如表5所示。

用這些算法獨立求解每個基準函數51次，計算結果如表6所示。表6的排名1是按平均最佳目標函數值排序，排名2是按平均最佳目標函數值和CPU時間排序。表7是8種算法所得最優解的非參數Wilcoxon秩和檢驗。表中，h-val=1表明SIR-DNA算法能夠以99%的概率優于其他算法，h-val=-1表示SIR-DNA算法明顯劣于其他算法，而h-val=0表示SIR-DNA算法與其他算法的結果差異不顯著。

Table 4 Benchmark functions表4 基準函數

從表6中可以看出，這8個算法按精度排序如下：

按精度和CPU耗時的排序如下：

從表7中可以知道，SIR-DNA算法的性能明顯優于7種被比較的算法。

圖7（a）～（c）說明8個算法求解F2、F20和F22時的樣本收斂曲線，其中的水平和垂直軸采用對數刻度。從表6中可以看出，當SIR-DNA算法求解F2、F20時，其發現最優解所需時間要比被比較算法少；當SIR-DNA算法求解F22時，其發現最優解的精度和所需時間稍遜于DSDA算法，但比其他算法要好。綜合看來，SIR-DNA算法的綜合性能要優于被比較算法，表明其計算速度快。從圖7（a）～（b）可以看出，SIR-DNA算法的收斂曲線大部分在被比較算法的左側，表明其收斂速度很快；從圖7（c）可以看出，SIRDNA算法的收斂曲線在被比較算法的右側，表明其收斂速度慢于某些算法，但是只有SIR-DNA算法獲得的最優解最好。

Table 5 Parameters of 7 compared algorithms表5 7種參與比較的算法的參數

Table 7 Results comparison of Wilcoxon rank sum test(α=0.01)表7 Wilcoxon秩和檢驗結果比較(α=0.01)

4 結論

本文采用SIR傳染病動力學理論與DNA分子結構理論相結合的方法構建出SIR-DNA算法。在該算法中，SIR傳染病模型的優勢和特性如下：

（1）S-S、S-I、I-I、I-R、R-R、R-S算子不與優化問題相關，從而使SIR-DNA算法具有通用性。

（2）利用傳染病傳播時所誘發的6個狀態轉移，從多種角度天然地實現個體之間信息的充分交換，降低了個體陷入局部最優的概率。

（3）因病毒每次攻擊的是個體的很少部分特征，每次運算只涉及到很少一部分特征參與運算，從而實現天然降維。

（4）SIR-DNA算法利用SIR傳染病動力學理論，使搜索過程達到生態穩定時出現收斂，而SIR傳染病模型可以幫助算法選擇合理的參數實現收斂。

在SIR-DNA算法中，由于采用SIR傳染病模型作為基礎，從一個新的角度構造了能反映DNA特征的優化算法，其特征在于：

（1）SIR-DNA算法不是直接與DNA算法進行結合，從而避免了DNA算法的缺陷，即DNA計算時需要借助生物實驗，無法求解高維優化問題等。

Fig.7 Convergence curves when 8 algorithms solve F2、F20、F22圖7 8個算法求解F2、F20、F22時的收斂曲線

（2）SIR-DNA算法納入DNA特征的方法是，將DNA中的基因和位點進行編碼，采用隨機修改關鍵基因及其位點的方法來模擬病毒對DNA的攻擊或獲得免疫力，從而無需生物實驗即可進行計算。

迄今為止，已經發現了數以千計的傳染病。本文的SIR-DNA算法為將這些傳染病轉化為能求解的非常復雜的優化問題的群智能優化算法提供了參考。

[1]Adleman L M.Molecular computation of solution to combinatorial problems[J].Science,1994,266(5187):1021-1024.

[2]Zhang Xuncai,Zhao Hailan,Cui Guangzhao,et al.Research advances and prospect of DNAcomputing[J].Computer Engineering andApplications,2007,43(10):44-47.

[3]Takahashi K,Yaegashi S,Asanuma H,et al.Photo-and thermoregulation of DNA nanomachines[C]//LNCS 3892:Proceedings of the 11th International Workshop on DNA Computing,London,Jun 6-9,2005.Berlin,Heidelberg:Springer,2005:336-346.

[4]Wu Fan,Li Kenli.An algorithm in tile assembly model forNqueen problem[J].Acta Electronica Sinica,2013,41(11):2174-2180.

[5]Li Kenli,Luo Xing,Wu Fan,et al.An algorithm in tile assembly model for maximum clique problem[J].Journal of Computer Research and Development,2013,50(3):666-675.

[6]Yao Qing'an,Zheng Hong,Wang Hongmei.DNA computing model for shortest path problem based onk-armed molecule and sticker operation[J].Journal of Jilin University:Information Science Edition,2014,32(6):653-656.

[7]Xu Jinglei,Zhao Hongchao,Liu Xiyu.Closed circle DNA algorithm of traveling salesman problem[J].Computer Engineering&Science,2014,36(1):111-114.

[8]Ma Ying,Yin Zhixiang.DNA computing model for the graph vertex coloring problem by plasmids[J].Journal of Anhui University of Science and Technology:Natural Science,2015,35(2):64-67.

[9]Wu Xue,Song Chenyang,Zhang Nan,et al.DNA algorithm for maximum matching problem based on sticker computation model[J].Computer Science,2013,40(12):127-132.

[10]Kermack W O,Mckendrick A G.Contributions to the mathematical theory of epidemics[J].Proceedings of the Royal Society of London:SeriesA,1927,115(772):700-721.

[11]Kermack W O,Mckendrick A G.Contributions to the mathematical theory of epidemics(II):the problem of endemicity[J].Proceedings of the Royal Society of London,1932,138(795):55-83.

[12]Wang Qian,Wang Tingting.Stability analysis of a SIRS epidemic model[J].Journal of Capital Normal University:Natural Science Edition,2016,37(2):5-11.

[13]Huang Guangqiu.SIS epidemic model-based optimization[J].Journal of Computation Science,2014,5(1):32-50.

[14]Liang J J,Qu B Y,Suganthan P N,et al.Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization,201212[R].Singapore:Nanyang Technological University,2013.

[15]Chuang Yaochen,Chen C T,Hwang C.A simple and efficient real-coded genetic algorithm for constrained optimization[J].Applied Soft Computing,2016,38:87-105.

[16]Koro?ec P,?ilc J,Filipi? B.The differential ant-stigmergy algorithm[J].Information Sciences,2012,192:82-97.

[17]Beheshti Z,Shamsuddin S M.Non-parametric particle swarm optimization for global optimization[J].Applied Soft Computing,2015,28:345-359.

[18]Al-Roomi A R,El-Hawary M E.Metropolis biogeographybased optimization[J].Information Sciences,2016,360:73-95.[19]Mukherjee R,Debchoudhury S,Das S.Modified differential evolution with locality induced genetic operators for dynamic optimization[J].European Journal of Operational Research,2016,253(2):337-355.

[20]Zhao Zhiwei,Yang Jingming,Hu Ziyu,et al.A differential evolution algorithm with self-adaptive strategy and control parameters based on symmetric Latin hypercube design for unconstrained optimization problems[J].European Journal of Operational Research,2016,250(1):30-45.

[21]Li Genghui,Cui Laizhong,Fu Xianghua,et al.Artificial bee colony algorithm with gene recombination for numerical function optimization[J].Applied Soft Computing,2017,52:146-159.

附中文參考文獻:

[2]張勛才,趙海蘭,崔光照.DNA計算的研究進展及展望[J].計算機工程與應用,2007,43(10):44-47.

[4]吳帆,李肯立.基于自組裝的N皇后問題DNA計算算法[J].電子學報,2013,41(11):2174-2180.

[5]李肯立,羅興,吳帆,等.基于自組裝模型的最大團問題DNA計算算法[J].計算機研究與發展,2013,50(3):666-675.

[6]姚慶安,鄭虹,王紅梅.基于k-臂分子求解最短路徑的DNA計算模型[J].吉林大學學報:信息科學版,2014,32(6):653-656.

[7]徐京雷,趙洪超,劉希玉.旅行商問題的閉環DNA算法[J].計算機工程與科學,2014,36(1):111-114.

[8]馬瑩,殷志祥.圖頂點著色問題的質粒DNA計算[J].安徽理工大學學報:自然科學版,2015,35(2):64-67.

[9]吳雪,宋晨陽,張楠,等.最大匹配問題的粘貼DNA算法[J].計算機科學,2013,40(12):127-132.

[12]王茜,王婷婷.SIRS傳染病模型的穩定性分析[J].首都師范大學學報:自然科學版,2016,37(2):5-11.