基于改進克隆選擇算法的路徑優化問題研究

曹 霞，曹 民 CAO Xia,CAO Min

（上海理工大學 光電信息與計算機工程學院，上海 200093）

0 引言

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

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

為更高效地解決TSP問題，本文提出引入疫苗接種策略的克隆選擇算法（Immune Clonal Selection Algorithm Introduced into Vaccination Strategy，ICSA-VS）。實驗仿真證明該算法具有隨機性、自適應性、多樣性、收斂快等特點，避免迭代過程陷入局部最優狀態，實現了免疫的自我調節功能。

1 問題描述及定義

1.1 TSP問題簡述

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

1.2 克隆選擇算法

定義1 抗體則是TSP問題的候選路徑（實數編碼），即歷遍n個城市，且每個城市只經過一次的n個城市序號的排列。

定義2 抗原是求解TSP問題的最短路徑。

定義3 親和度的大小表現為抗體與抗原的結合強度。親和力計算公式定義如下：

其中，i=1,2,…,m，L（i）是第i只螞蟻歷遍n個城市的路徑長度，Lmax為最長路徑長度，Lmin為最短路徑長度。該式表明，螞蟻經過n個城市的路徑長度越短，其對應的親和力越大。親和度越大，表明抗體與抗原之間結合力越強。

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

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

定義5 克隆增殖是指選擇親和度高的抗體復制。克隆增殖是克隆選擇算法所特有的，是依據抗體親和力和濃度的高低進行克隆：抗體親和力越高，濃度越低，其被克隆的概率越大，克隆的數目越多。克隆公式如下：

式（2） 中，n為城市數量，Xi（）k表示第i個抗體第k個經過的城市序號。

第i個抗體濃度計算公式為：

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

在本文的算法中，首先對抗體的親和力按遞減的順序排序，然后根據親和力大小，按照克隆公式確定每個抗體的克隆個數，親和度大的抗體，克隆規模大；親和度小的抗體，克隆規模小。克隆增殖可以保證較優的個體有較大的生存空間，提高種群的整體素質。

定義6 克隆變異是指抗體按一定的突變概率，隨機選取抗體中兩個點互換位置，形成新的抗體。克隆變異可以防止算法早熟，提高算法的全局搜索能力。本算法采用自適應變異概率，根據抗體的親和力值自適應調整變異概率。克隆變異公式如下：

從式（5）可以看出，抗體的親和力越大，其對應的變異率就越小。

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

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

定義9 抗體補充算子是指隨機產生抗體規模為T的候選抗體加入新抗體群，該算子可以增加抗體群的多樣性。

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

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

定義10 疫苗可以利用所求問題的一些特征信息或問題的先驗知識提取，是對最佳個體基因的估計，具備最佳個體局部基因為上可能特征[6]。本文采用輪盤賭隨機選擇算法從候選疫苗種群（親和度較高的抗體群）中選出疫苗，將剩余的候選疫苗種群作為預克隆抗體。

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

圖1 多點交叉示意圖

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

3 結果分析

本文使用的是全國31個省會城市作為實例進行測試。改進的克隆選擇算法的參數設置如下：抗體種群規模為36，選取候選疫苗庫的比例因子為0.7，克隆比例因子為380，抗體變異概率0.01。實驗仿真結果如圖3、圖4所示。由圖1可知，本文算法收斂的，在迭代次數達到50次后，最優路徑保持在15 669.9634。圖4為本文算法優化后的路線圖。

圖2 算法流程圖

圖3 親和度收斂過程

圖4 最優化路徑圖

為驗證程序求解效率，本文同時對基于遺傳算法（GA）、免疫算法（IA） 和蟻群算法（ACO）解決TSP問題[8]進行了測試，測試的種群規模為36。將4種算法各運行30次，實驗最優結果如表1。圖5、圖6為4種算法的親和度收斂過程和最優路徑圖。

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

4 結 論

本文在克隆選擇算法基礎上引入疫苗接種策略，對路徑優化問題建立模型并求解，實驗結果表明，該算法采用疫苗選取、克隆增殖、克隆抑制、交叉等策略，使算法具有多樣性、隨機性、自適應性、收斂性。通過仿真實驗，綜合進化代數、計算時間和最短路徑方面來看，ICSA-VS算法求解問題的效率相對其他算法更好。

表1 4種算法仿真結果對比

圖5 4種算法收斂性比較

圖6 4種算法得出的最優路徑線路圖

[1]田玉玲，段富.免疫優化算法、模型及應用[M].北京：國防工業出版社，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]張樂，陸金桂.改進的免疫算法求解TSP問題[J].計算機工程與設計，2005,26(4):978-984.

[4]戚玉濤，劉芳，焦李成.求解TSP問題免疫算法的動態疫苗策略[J].西安電子科技大學學報,2008,35(1):37-42.

[5]劉朝華，張英杰，吳建輝.一種求解TSP問題的改進克隆選擇算法[J].系統仿真學報，2010,22(7):1627-1631.

[6]叢爽.智能控制系統及其應用[M].合肥：中國科學技術大學出版社，2013.

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

[8]包子陽，余繼周.智能優化算法及其MATLAB實例[M].北京：電子工業出版社，2016.