研究人工免疫算法中旅行商問題

研究人工免疫算法中旅行商問題

　　
0.引言
早在18世紀，愛爾蘭的數學家哈密爾頓和英國的數學家托馬斯就已經對旅行商問題（TSP）進行數學研究，而旅行商問題一般形式的研究則是由數學家卡爾·門格爾于19世紀三十年代在維也納和哈佛大學首次進行研究的。對旅行商問題的研究往往是出于把它作為一個可應用于解決大規模的組合最優化問題的一般方法的一個平臺，然而這并不是說在很多領域中旅行商問題找不到其具體的應用。事實上，旅行商問題有許許多多的應用，它可以看成是許多領域內復雜工程優化問題的抽象形式，諸如郵路問題、網絡布線問題、物流配送問題、電路板鉆孔問題等等，這些應用給旅行商問題的研究帶來了活力，并且幫助指導今后的研究工作。旅行商問題本身的應用范圍正在不斷擴張，它的研究方法也正迎來越來越廣闊的發展前景�？梢钥闯�，不論從理論還是實際應用來講，研究TSP問題取得的每一步進展都將會有非常重大的意義。

　　多年來人們一直尋求求解TSP問題的算法，其中有傳統的算法如動態規劃法、分支極限法等，但由于其僅能用于求解規模較小的TSP問題，在實際應用中的局限性使其無法適用于求解大規模的TSP問題。近年來，現代流行的智能算法也越來越受到研究人員們的廣泛關注，當然人們也正在努力的探索，試圖用其求解TSP問題。這些算法包括神經網絡、遺傳算法、蟻群算法等。本文欲用另外一種人工智能算法--人工免疫算法,來求解TSP問題。中國碩士論文網提供大量免費碩士畢業論文,如有業務需求請咨詢網站客服人員！

　　1.旅行商問題的概述
　　1.1 旅行商問題的描述：

　　旅行商問題，簡單地說，就是某一旅行商要去n 個城市去旅行，他要把這n 個城市都逛一次而且不重復，最后回到原出發城市,問給定所有城市之間的旅行成本，哪一種旅行路徑成本最�。繛榱撕喕�，成本可理解為旅行商走過的最短距離。即已知n 個城市以及各城市間的距離，某一旅行商從某個城市出發訪問每個城市有且僅一次，最終返回原出發城市，怎樣走才能使其所走的線路最短？

　　用圖論來描述，那就是已知帶權圖 G=(C，L)，尋找出總權值最小的一條路徑。其中C={c1，c2，…，cn}表示n 個城市的集合，L={ lij | ci，cj∈C}是集合C 中元素（城市）兩兩連接的集合，每條邊lij，都存在與之對應的權值dij，實際應用中dij 可以表示距離、費用、時間、油量等。

　　從旅行商問題的描述來看，似乎其并不是很復雜，理解起來也是很簡單，但其的確是一個非常復雜的問題。對于n 個城市的旅行商問題，可供選擇的路徑數目我們可以這樣計算：

　　起始城市訪問其他城市有n-1 個選擇，第二個城市有n-2 個選擇，依此類推，倒數第2 個城市只有1 個選擇，總的可選擇的路徑數為?n ?1?! ? (n ?1)(n ? 2)(n ? 3). . . 3 2 1。另外，我們所研究的標準的旅行商問題其旅行成本是對稱的，即城市i 到城市j 的旅行成本和城市j 到城市i 的旅行成本是一樣的，故對于一個包含n 個城市的旅行商問題，可供選擇的路徑有(n ?1)!/ 2種。當n 較小時，我們可通過羅列各種路徑并從中找出最短路徑，但隨著值n的變大，可供選擇的路徑數迅速增加，用羅列的辦法已經無能為力了，這時必須尋求其他解法來搜索最短的路徑。

　　1.2 旅行商問題的數學建模：

　　旅行商問題( TSP)在數學上可以描述為以下優化問題。

　　2.人工免疫算法的基本原理2.1 生物免疫系統及其運行機制生物免疫系統是自然界生物所必備的防御系統, 它是一種由眾多細胞、分子和組織等子系統構成的復雜系統，這些子系統之間存在著復雜的相互聯系，具有識別“自己”和“非己”，消除和消滅異物的功能。生物免疫系統又分為先天免疫系統和自適應免疫系統。先天免疫系統是一種與生俱來的天然防御系統，具有識別一定微生物并消滅這種微生物的能力，但對于絕大數外來侵入病毒的殺傷力較弱，這時候自適應免疫系統就開始發揮它的重要作用了，它能夠自適應的學習外來侵入病毒物質或分子的模式結構，中立或消除該種物質。

　　自適應免疫系統的運行機制可以簡單的概括為：在抗原的激勵下，巨噬細胞分化抗原為顆粒狀物質，抗原呈遞細胞將這些物質呈遞到巨噬細胞的表面；通過識別的途徑，被激活T細胞分化和分泌淋巴因子，并使B細胞應答；B細胞對來自激活的T細胞的信號做出反應——被激活并進行分化和繁殖，分泌出抗體蛋白；抗體纏住、中立并毀滅這些抗原，其他多余的T細胞和B細胞變為記憶細胞。這樣反復循環若干代數將最終產生能夠消滅抗原的有效抗體。

　　免疫系統中B細胞的功能主要是產生抗體,抗體由氨基酸排列組成, 氨基酸的不同排列方式形成不同的抗體;而T細胞則主要實現免疫調節功能。

　　2.2人工免疫系統及人工免疫算法的基本步驟
　　人工免疫系統即根據生物免疫系統的運行機制構造的一種仿生系統。在構造人工免疫系統時, 首先要構造的就是人工抗原和抗體,在人工免疫系統中, 一個抗體或抗原可以用一個字符串表示，生物抗體由氨基酸的不同排列組成，因此, 人工抗體（字符串）中的字符應相當于生物抗體中的氨基酸。為使人工免疫系統具有與生物免疫系統類似的自我調節機制,可以用親和力來描述抗體和抗原之間的匹配程度，用濃度來描述每種抗體在整個抗體群中所占份額�？贵w和抗原之間的親和力反映了候選解和最優解的接近程度, 也即反映候選解對約束條件和目標函數的滿足程度。對于親和力較大的抗體作為記憶細胞加以重點保留，又通過濃度調節來保持抗體的多樣性；再對經過選擇的抗體群（通過親和力和濃度進行促進抑制得到的抗體群）進行繁殖變異產生新的抗體群。不斷地循環，最終也將會找到滿足要求的最優解。

　　步驟1：抗原識別——對實際問題進行抽象，產生目標函數和約束條件作為抗原。

　　步驟2：產生初始抗體——若抗原為新抗原，則隨機產生N個抗體構成初始抗體群，記憶庫為空集；若抗原為已經出現的抗原，則從記憶庫中隨機選擇部分記憶細胞，以及隨機產生部分抗體構成規模為N的初始抗體群。

　　步驟3：親和力、濃度計算——親和力反映了候選解和最優解的接近程度，濃度反應了候選解之間的相似性。

　　步驟4：記憶細胞更新——與抗原有最大親和力的抗體加給記憶細胞。 由于記憶細胞數目有限，新產生的具有更高親和力的抗體替換較低親和力的抗體。

　　步驟5：終止條件——當達到給定代數或已經連續幾代都沒能找到更好的解則終止，否則轉到步驟（6）重復執行。

　　步驟6：抗體的促進和抑制——高親和力抗體受到促進，高濃度抗體受到抑制。通常通過計算抗體成活的期望值來實施。

　　步驟7：產生新抗體群——通過人工免疫算子產生多種抗體，再加上記憶細胞中的抗體代替原抗體群，形成下一代抗體群。

　　3.旅行商問題的人工免疫算法
　　3.1 旅行商問題的人工免疫算法的基本步驟:

　　人工免疫算法的映射關系:抗原對應為遍歷各城市的最短路徑；抗體對應為一條遍歷路徑；親和力對應為抗體所決定的路徑與抗原的最短路徑的匹配程度。算法的基本步驟:

　　步驟1:隨機生成一個規模為N的初始抗體群path。

　　步驟2:計算抗體群path中的每個抗體的親和力Affi和濃度density。

　　步驟3:選擇親和力較高的抗體生成記憶細胞群體MemoryLab，其規模為N1。

　　步驟4:依據親和力和濃度對路徑path中各個抗體的進行選擇并繁殖,得新抗體群path2。親和力越高、濃度越低則繁殖越多;反之, 則繁殖越少。

　　步驟5:通過人工免疫算子對抗體群path2進行變異等操作,得到抗體群path3。親和力越低則變異率越高;親和力越高則變異率越低。

　　步驟6: 將path3 并入path, 計算抗體群path中的每個抗體對抗原的親和力。刪除親和力低的和重復的抗體,使群體總規模保持為N。

　　步驟7: 重復執行步驟2到步驟7,直到循環次數達到設定值或經過若干次循環仍沒有找到更優解。

　　3.2 抗體的編碼以及初始抗體群體的產生：

　　抗體的編碼方式模擬了生物抗體的蛋白質結構, 把每個城市看成是一個氨基酸分子, 將城市之間的邊看作是連接氨基酸分子的肽鍵。一條遍歷n個城市的路徑則相當于一條包含n個不同氨基酸分子的肽鏈。

　　抗體按所走城市的順序進行編碼, 每一個抗體編碼字符串形如: (C1, C2 ,…,Ci ,…,Cn )其中Ci 表示遍歷城市的編號。一個字符串抗體只能代表一個候選解,但一個候選解允許有一個以上的字符串抗體相對應。在確定抗體的編碼方式時, 應盡量使字符串抗體和候選解之間形成一一對應的關系, 以縮小抗體空間、提高搜索效率。可根據TSP問題有每個城市有且只能訪問一次和任意的Ci不等于Cj的約束條件。另外對于有n 個城市的旅行商問題,從其中的一個城市出發,遍歷其余(n-1)個城市且每個城市只去一次的路徑有(n-1) ! /2條。 對這n個城市編號,其號碼分別為1, 2, 3,…, n；并且把商人出發城市編為第1號,其它城市可以隨意編號,把這n個城市的編號任意排列成一個長度為n的字符串都可以形成一個抗體。 因此抗體空間含有n! 個抗體,而解空間含有(n-1) ! /2個可行解。這n ! 個抗體只代表(n-1)! /2個可行解。 因此免疫算法要在抗體空間中搜索到與抗原匹配的抗體,比在解空間中搜索到最優解更難。

　　基于抗體的編碼，初始抗體群的產生一般都是隨機的產生，這樣是為了能夠增加整個抗體群體的多樣性。

　　3.3 親和力計算免疫系統通過識別在抗原和抗體之間的獨特型或者抗體和抗體之間的獨特型產生多種抗體，抗原和抗體之間結合強度一般用親和力來估計——抗原與抗體之間親和力越大，抗原與抗體之間的匹配越好。

　　免疫算法中的難點之一就是親和力計算。親和力函數的設計往往在很大程度上決定算法的優劣性。對TSP問題來說,常見的親和力定義方法是取抗體所對應的路徑長度的倒數。

　　對應的路徑長度通常為較大的正數, 致使親和力通常變得很小,且密集分布于一個狹窄區間內, 不利于體現抗體的優劣。另一方面,該方法沒有體現抗體與抗原之間的聯系。為此可進一步對其進行改進，得親和力得定義為:

　　A（k）= L /L(k)其中L為抗原對應的旅行商路線的總長度,即TSP問題的最短路徑。但我們往往不知道最短路徑是多長，否則也沒必要進行搜索。為此可以把L設為當前抗體群中的抗體的最短路徑，但這往往使親和力保持較高，并且也聚集在一個較短的空間范圍內（但較簡簡單單的取路徑的倒數有較大的改進）這為如何實現抗體的促進和抑制帶來一定的難度，為此必須為抗體被擴增數進行相應的設計，見3.4。

　　3.4 抗體濃度抗體的濃度用于調節抗體的規模，基于濃度的選擇機制，既促進親和力高的抗體，又可抑制濃度高的抗體，從而保證了算法的收斂性及抗體群體的多樣性。濃度函數的定義和定義抗體親和力的定義一樣，對算法的優劣性也同樣具有非常的地位�？蓪⒖贵w濃度函數定義如下式:其中, n 為抗體數量，s (abi , abj )表示抗體間的相似性。抗體的濃度表示與其相似的抗體占整個群體的比例。判斷抗體間的相似性有多種方法。

　　一種是基于信息熵的判斷方法，通過這種方法能夠較容易地與生物免疫系統中的抗體對應，更能夠客觀地反應其含義。根據抗體群平均信息熵的概念計算抗體濃度的方法可知，抗體群的所有抗體在同一基因座上的等位基因各不相同時，抗體群的平均信息熵最大，抗體的相似性最�。环粗�，相似性較大。但是，在優化計算中，這種利用信息熵的概念計算抗體濃度的方法存在一定得問題，例如抗體A=（1，2，3，4，5）與抗體B=(2，3，4，5，1)之間的信息熵較大，但其卻對應同一條路徑。

　　其中D( abi , abj )表示抗體abi和abj的歐基里德距離, T為預設的指定閾值。這種算法也同樣具有基于信息熵的判斷方法的缺點，但該判斷方法相對簡單。

　　在此提出一種求解濃度的方法：首先，對某一個具體的抗體ab先從抗體群中尋找和其親和力相近的抗體abk（可以將兩親和力作差，求絕對值，絕對值小于某一閾值暫且將其認為是相似抗體，以待作進一步篩選）。其次，拿這個具體抗體ab和從第一步搜尋到的其他抗體abk作比較——先從抗體ab（字符串）的第一個字符char1到抗體abk中尋找相同的字符char1，將抗體abk中的字符char1左兩個右兩個字符存入一個數組a中，同時也將抗體ab（字符串）的第一個字符char1左兩個右兩個字符存入另一個數組b中（字符串第一個字母的左兩個字符為該字符串的的最后兩個字符，同時最后一個字符的右兩個字符為該字符串的前兩個，字符串第二個字母的選擇同理），判斷兩數組a和b中有幾個相同的字符；再從第一個抗體ab中的第二個字符char2到第二個抗體abk中去找，得相同數，依次類推，將總的相同數相加作為該抗體的相似性數k。最后基于前兩步對所有抗體求得相似性數ki，定義第i個抗體abi的抗體濃度為： ? =ki / sum?ki ?。

　　3.5 抗體促進和抑制
　　將抗體群中的抗體根據其親和力大小按升序排列, 得到: {ab1 ,ab2 , …, abn }, 且A(i)<A(i+1), i = 1, 2, …,n-1。從抗體群中選擇親和力較大的m個抗體進行擴增。但擴增的數量受親和力刺激的同時還要受濃度的調節。高親和力、低濃度的抗體擴增數多；低親和力、高濃度的抗體擴增數少。

　　3.6 人工免疫
　　算子為了能對未知抗原產生免疫應答,可通過免疫算子來產生新的抗體。在生物免疫系統中新抗體一般是通過變異得到的，但為了進一步提高免疫算子的多樣性我們可引入遺傳算法中的交叉操作算子。現對部分人工免疫算子作一些簡要的介紹：

　�。�1） 字符換位算子：字符換位操作即是對抗體A，隨機取兩個正整數i,j，以一定的概率交換抗體A中一對字符ci,cj的位置。

　　（2） 字符串移位算子：字符串移位操作是從抗體A中隨機取出一個字符子串A1, 以一定的概率依次往左（或往右）移動字符串A1中的各個字符, 最左（或最右）邊的一個字符則移動到最右(或最左)邊的位置。

　�。�3） 字符串逆轉算子：字符串逆轉操作是對抗體A中隨機取出一個子字符串，以一定的概率將其首尾倒置。

　�。�4） 字符串重組算子：字符串重組操作是在抗體A中隨機取一個子字符串A1，以一定的概率使字符串A1中字符重新排列。重新排列的目的是提高抗體的親和力，具體方法與所求解的問題有關。

　　（5） 優質串保留算子：如果若干個抗體與抗原之間的親和力都很大, 且這些抗體包含了一個相同的子字符串, 則稱這個子字符串為優質字符串, 簡稱優質串。如果抗體中存在優質串, 則在抗體產生過程中以一定概率使該優質串不受破壞。

　�。�6） 新抗體引人算子：若抗體群中的抗體失去了多樣性, 則可以產生新的抗體替換掉其中的一部分,以保持抗體群中抗體的多樣性。新抗體引人操作是當抗體群中有k個抗體相同時, 對其中的（k-1）個抗體以一定概率用新產生的抗體替換。

　�。�7） 有序交叉算子：隨機取兩個正整數i,j，兩后代現分別按對應位置復制雙親X1、X2匹配段中的兩個子串A1、A2，在對應位置交換雙親匹配段以外的城市，如果交換后，后代X1中的某一城市a與子串A1中的城市重復，則將該城市取代子串A2中的城市a具有相同位置的城市，直到與子串A1中的城市均不重復為止，對后代X2也采用相同的方法。

　　4. 應用實驗研究
　　為了驗證人工免疫算法的的有效性，本文針對從TSPLIB中摘取的Swiss42的TSP數據運用人工免疫算法對其用MATLAB進行多次應用實驗。對抗體群規模N=50，記憶細胞的規模N1=20，交叉概率Pc=0.9，變異概率Pm=0.05，參數因子? =5，? =5，? =0.1，總的循環代數Tc=1000，進行了多次計算，每次計算隨機產生不同的初始抗體。計算結果如表1所示，搜索到最優路徑的情況。

　　實驗結果表明本文提出的旅行商問題的人工免疫算法能夠有效地搜索到最優值，其中的一些參數調節也能夠較有效的改變搜索能力和收斂速度，但從上面的一些數據可知本文提出的算法仍有一些不足之處，如怎樣選擇最佳參數等。

　　5.結語
　　本文提出了一種基于人工免疫理論的基本算法來求解旅行商問題。免疫算法通過抗體與抗原間的親和力以及抗體與抗體之間的濃度來保留優質抗體和保持抗體群種的多樣性。

　　對高親和力、低濃度的抗體進行促進；對低親和力、高濃度的抗體進行抑制，并加大變異程度。由其獨特的特征，在優化問題規模不大、搜索空間較小的情況下防止算法陷入局部最優，具有更強的全局搜索能力，但對更大規模的優化問題時有收斂速度較慢等不足，由此產生了各種各樣的改進版的人工免疫算法，如結合遺傳算法等其他算法的混合式算法，這些都為對人工免疫算法的研究帶來了廣闊的前景。

本碩士論文來源于中國碩士論文網，參考文獻：http://www.lunwenad.com/wzlb-6.html，轉載敬請保留鏈接，謝謝。

【研究人工免疫算法中旅行商問題】相關文章：

現代企業績效管理問題研究05-03

論組織學習研究的若干問題06-04

感知無線電的關鍵問題研究05-30

新刑訴法下社區矯正問題研究09-05

大學生文學素養降低問題研究論文04-24

刑事二審程序的若干問題研究05-11

淺析中小企業招聘存在的問題及對策研究04-21

中國農村留守老年人保障問題研究05-11

森林旅游面臨的主要問題及對策研究開提報告06-04

尋釁滋事罪問題研初中數學教育研究05-31