曹 霞，曹 民 CAO Xia,CAO Min

（上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

克隆選擇是生物免疫系統(tǒng)理論的重要學(xué)說(shuō)。克隆選擇機(jī)制是指能在機(jī)體內(nèi)選擇出能識(shí)別和消滅相應(yīng)抗原的免疫細(xì)胞，使之激活、分化和增殖，進(jìn)行免疫應(yīng)答，最終消除抗原[1]。1999年，De Castro和Von Zuben提出了基于免疫系統(tǒng)克隆選擇理論的克隆選擇算法[2]，該算法是基于抗體與抗原的親和度的大小及比例進(jìn)行抗體的選擇和克隆，通過(guò)構(gòu)造記憶單元來(lái)記憶優(yōu)良抗體，通過(guò)隨機(jī)產(chǎn)生的新抗體對(duì)舊抗體的替代，實(shí)現(xiàn)種群多樣性。克隆選擇算法兼顧全局與局部搜索，具有多樣性好、收斂速度快、求解精度高、克服早熟問(wèn)題等優(yōu)勢(shì)。

目前，在使用免疫算法求解路徑優(yōu)化問(wèn)題已取得一些成果。張樂(lè)等人提出基于人工免疫理論的提取免疫疫苗和注射疫苗的新算法求解TSP問(wèn)題[3]。戚玉濤等人提出了求解TSP問(wèn)題免疫算法的動(dòng)態(tài)疫苗策略，將先驗(yàn)知識(shí)引入算法中，以提高算法的求解性能[4]。劉朝華等人提出一種基于抗體局部最優(yōu)免疫優(yōu)勢(shì)的克隆選擇算法求解TSP問(wèn)題，在深度搜索和廣度尋優(yōu)之間取得了平衡[5]。這些改進(jìn)的算法在求解TSP問(wèn)題中均取得了一定的效果。

為更高效地解決TSP問(wèn)題，本文提出引入疫苗接種策略的克隆選擇算法（Immune Clonal Selection Algorithm Introduced into Vaccination Strategy，ICSA-VS）。實(shí)驗(yàn)仿真證明該算法具有隨機(jī)性、自適應(yīng)性、多樣性、收斂快等特點(diǎn)，避免迭代過(guò)程陷入局部最優(yōu)狀態(tài)，實(shí)現(xiàn)了免疫的自我調(diào)節(jié)功能。

1 問(wèn)題描述及定義

1.1 TSP問(wèn)題簡(jiǎn)述

TSP（Travelling Salesman Problem） 問(wèn)題可以描述為：給定n個(gè)城市C=｛C1,C2,…,CN｝，其中任意兩個(gè)城市之間的距離D（i,j）=（Ci,Cj），有一個(gè)旅行商從某一城市出發(fā)，訪問(wèn)各城市一次且僅有一次后再回到原出發(fā)城市，要求找出一條最短的巡回路徑Lmin=｛Lmin（1 ）,Lmin（2 ）,…,Lmin（N ）｝。

1.2 克隆選擇算法

定義1 抗體則是TSP問(wèn)題的候選路徑（實(shí)數(shù)編碼），即歷遍n個(gè)城市，且每個(gè)城市只經(jīng)過(guò)一次的n個(gè)城市序號(hào)的排列。

定義2 抗原是求解TSP問(wèn)題的最短路徑。

定義3 親和度的大小表現(xiàn)為抗體與抗原的結(jié)合強(qiáng)度。親和力計(jì)算公式定義如下：

其中，i=1,2,…,m，L（i）是第i只螞蟻歷遍n個(gè)城市的路徑長(zhǎng)度，Lmax為最長(zhǎng)路徑長(zhǎng)度，Lmin為最短路徑長(zhǎng)度。該式表明，螞蟻經(jīng)過(guò)n個(gè)城市的路徑長(zhǎng)度越短，其對(duì)應(yīng)的親和力越大。親和度越大，表明抗體與抗原之間結(jié)合力越強(qiáng)。

定義4 抗體濃度表征抗體種群的多樣性好壞，當(dāng)某抗體對(duì)抗原的親和度高，且抗體濃度低時(shí)，該抗體將被大量克隆。

兩抗體Xi和Xj之間的相似性程度S（ i,j）計(jì)算公式如下：

定義5 克隆增殖是指選擇親和度高的抗體復(fù)制?？寺≡鲋呈强寺∵x擇算法所特有的，是依據(jù)抗體親和力和濃度的高低進(jìn)行克?。嚎贵w親和力越高，濃度越低，其被克隆的概率越大，克隆的數(shù)目越多?？寺」饺缦拢?/p>

式（2） 中，n為城市數(shù)量，Xi（）k表示第i個(gè)抗體第k個(gè)經(jīng)過(guò)的城市序號(hào)。

第i個(gè)抗體濃度計(jì)算公式為：

θ為克隆比例因子，Cfit（i）為第i個(gè)預(yù)克隆抗體的親和力，T（i）為抗體濃度。該式表明，克隆抗體的克隆大小與該抗體的親和力成正比，與其抗體濃度成反比。

在本文的算法中，首先對(duì)抗體的親和力按遞減的順序排序，然后根據(jù)親和力大小，按照克隆公式確定每個(gè)抗體的克隆個(gè)數(shù)，親和度大的抗體，克隆規(guī)模大；親和度小的抗體，克隆規(guī)模小?？寺≡鲋晨梢员ＷC較優(yōu)的個(gè)體有較大的生存空間，提高種群的整體素質(zhì)。

定義6 克隆變異是指抗體按一定的突變概率，隨機(jī)選取抗體中兩個(gè)點(diǎn)互換位置，形成新的抗體?？寺∽儺惪梢苑乐顾惴ㄔ缡?，提高算法的全局搜索能力。本算法采用自適應(yīng)變異概率，根據(jù)抗體的親和力值自適應(yīng)調(diào)整變異概率。克隆變異公式如下：

從式（5）可以看出，抗體的親和力越大，其對(duì)應(yīng)的變異率就越小。

定義7 克隆選擇是指將克隆抗體按親和力排序，按序選出與疫苗數(shù)量相同的抗體。

定義8 克隆刪除算子是指刪除親和力低于父代抗體的子代抗體，并用其父代抗體代替。

定義9 抗體補(bǔ)充算子是指隨機(jī)產(chǎn)生抗體規(guī)模為T的候選抗體加入新抗體群，該算子可以增加抗體群的多樣性。

1.3 基于引入疫苗策略的克隆選擇算法

本文算法在傳統(tǒng)免疫克隆選擇算法的基礎(chǔ)上采用實(shí)數(shù)編碼方式，根據(jù)求解問(wèn)題的要求將抗體種群按親和度大小選出候選疫苗種群，采用輪盤賭算法劃分疫苗和預(yù)克隆抗體，根據(jù)預(yù)克隆抗體親和度和濃度大小進(jìn)行克隆和變異抗體，并將疫苗和克隆變異后的抗體交叉接種，最后加入克隆循環(huán)補(bǔ)充算子和刪除算子。以下是對(duì)引入疫苗策略的描述：

定義10 疫苗可以利用所求問(wèn)題的一些特征信息或問(wèn)題的先驗(yàn)知識(shí)提取，是對(duì)最佳個(gè)體基因的估計(jì)，具備最佳個(gè)體局部基因?yàn)樯峡赡芴卣鱗6]。本文采用輪盤賭隨機(jī)選擇算法從候選疫苗種群（親和度較高的抗體群）中選出疫苗，將剩余的候選疫苗種群作為預(yù)克隆抗體。

定義11 疫苗交叉接種是指將選中的兩個(gè)疫苗，通過(guò)置換各自部分基因，從而產(chǎn)生兩個(gè)子代的過(guò)程。交叉的目的是為了產(chǎn)生下一代新的優(yōu)良個(gè)體，通過(guò)交叉操作，可以有效提高算法的搜索能力[7]。本文算法采用多點(diǎn)交叉，先在疫苗的位串無(wú)重復(fù)的隨機(jī)選定多個(gè)交叉點(diǎn)，并將交叉點(diǎn)之間的疫苗間續(xù)地相互交換，產(chǎn)生兩個(gè)新的后代。多點(diǎn)交叉如圖1所示。

圖1 多點(diǎn)交叉示意圖

2 算法流程圖（如圖2所示）

3 結(jié)果分析

本文使用的是全國(guó)31個(gè)省會(huì)城市作為實(shí)例進(jìn)行測(cè)試。改進(jìn)的克隆選擇算法的參數(shù)設(shè)置如下：抗體種群規(guī)模為36，選取候選疫苗庫(kù)的比例因子為0.7，克隆比例因子為380，抗體變異概率0.01。實(shí)驗(yàn)仿真結(jié)果如圖3、圖4所示。由圖1可知，本文算法收斂的，在迭代次數(shù)達(dá)到50次后，最優(yōu)路徑保持在15 669.9634。圖4為本文算法優(yōu)化后的路線圖。

圖2 算法流程圖

圖3 親和度收斂過(guò)程

圖4 最優(yōu)化路徑圖

為驗(yàn)證程序求解效率，本文同時(shí)對(duì)基于遺傳算法（GA）、免疫算法（IA） 和蟻群算法（ACO）解決TSP問(wèn)題[8]進(jìn)行了測(cè)試，測(cè)試的種群規(guī)模為36。將4種算法各運(yùn)行30次，實(shí)驗(yàn)最優(yōu)結(jié)果如表1。圖5、圖6為4種算法的親和度收斂過(guò)程和最優(yōu)路徑圖。

從圖5可以看出ICSA-VS在迭代50次后，最短路徑數(shù)值趨于穩(wěn)定，與其他算法相比，迭代次數(shù)最少。雖然IA在算法的運(yùn)行時(shí)間上需要的最少，但是尋優(yōu)效果沒(méi)有ICSA-VS好。圖6為4種算法優(yōu)化后的線路圖。就最短路徑來(lái)看，ACO得出的最短路徑為15 660.2378，與ICSA-VS的相對(duì)誤差為0.062%。結(jié)合進(jìn)化代數(shù)、計(jì)算時(shí)間和最短路徑來(lái)看，ICSA-VS求解TSP問(wèn)題的效率相對(duì)其他算法好。

4 結(jié) 論

本文在克隆選擇算法基礎(chǔ)上引入疫苗接種策略，對(duì)路徑優(yōu)化問(wèn)題建立模型并求解，實(shí)驗(yàn)結(jié)果表明，該算法采用疫苗選取、克隆增殖、克隆抑制、交叉等策略，使算法具有多樣性、隨機(jī)性、自適應(yīng)性、收斂性。通過(guò)仿真實(shí)驗(yàn)，綜合進(jìn)化代數(shù)、計(jì)算時(shí)間和最短路徑方面來(lái)看，ICSA-VS算法求解問(wèn)題的效率相對(duì)其他算法更好。

表1 4種算法仿真結(jié)果對(duì)比

圖5 4種算法收斂性比較

圖6 4種算法得出的最優(yōu)路徑線路圖

[1]田玉玲，段富.免疫優(yōu)化算法、模型及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2013.

[2]De Castro L N,Von Zuben F J.Learning and optimization using the clonal selection principle[J].IEEE Transactions on Evolutionary Computation,2002,6(3):239-251.

[3]張樂(lè)，陸金桂.改進(jìn)的免疫算法求解TSP問(wèn)題[J].計(jì)算機(jī)工程與設(shè)計(jì)，2005,26(4):978-984.

[4]戚玉濤，劉芳，焦李成.求解TSP問(wèn)題免疫算法的動(dòng)態(tài)疫苗策略[J].西安電子科技大學(xué)學(xué)報(bào),2008,35(1):37-42.

[5]劉朝華，張英杰，吳建輝.一種求解TSP問(wèn)題的改進(jìn)克隆選擇算法[J].系統(tǒng)仿真學(xué)報(bào)，2010,22(7):1627-1631.

[6]叢爽.智能控制系統(tǒng)及其應(yīng)用[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2013.

[7]李榮鈞，劉小龍,等.基于微生物行為機(jī)制的粒子群優(yōu)化算法[M].廣州：華南理工大學(xué)出版社，2015.

[8]包子陽(yáng)，余繼周.智能優(yōu)化算法及其MATLAB實(shí)例[M].北京：電子工業(yè)出版社，2016.